Exploration-Exploitation in Constrained MDPs

2020-03-04 · Yonathan Efroni, Shie Mannor, Matteo Pirotta

In many sequential decision-making problems, the goal is to optimize a utility function while satisfying a set of constraints on different utilities. This learning problem is formalized through Constrained Markov Decision Processes (CMDPs). In this paper, we investigate the exploration-exploitation dilemma in CMDPs. While learning in an unknown CMDP, an agent should trade-off exploration to discover new information about the MDP, and exploitation of the current knowledge to maximize the reward while satisfying the constraints. While the agent will eventually learn a good or optimal policy, we do not want the agent to violate the constraints too often during the learning process. In this work, we analyze two approaches for learning in CMDPs. The first approach leverages the linear formulation of CMDP to perform optimistic planning at each episode. The second approach leverages the dual formulation (or saddle-point formulation) of CMDP to perform incremental, optimistic updates of the primal and dual variables. We show that both achieves sublinear regret w.r.t.\ the main utility while having a sublinear regret on the constraint violations. That being said, we highlight a crucial difference between the two approaches; the linear programming approach results in stronger guarantees than in the dual formulation based approach.

📄 PDF Abstract BibTeX arXiv:2003.02189

Code (0)

등록된 구현이 없습니다.

Tasks

Decision MakingSequential Decision Making

Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?

2026-01-28 · Hao Liang, Jiayu Cheng, Sean R. Sinclair, Yali Du arxiv

Exogenous MDPs (Exo-MDPs) capture sequential decision-making where uncertainty comes solely from exogenous inputs that evolve independently of the learner's actions. This structure is especially common in operations rese…

Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning

2018-02-12 · ICML 2018 7 · Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, Ronald Ortner

We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound $c$ on the span of the optimal bias functi…

Efficient Exploration reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff

2024-05-28 · Jian Qian, Haichen Hu, David Simchi-Levi

Motivated by the recent discovery of a statistical and computational reduction from contextual bandits to offline regression (Simchi-Levi and Xu, 2021), we address the general (stochastic) Contextual Markov Decision Proc…

Density Estimation Multi-Armed Bandits

Reward Shaping via Diffusion Process in Reinforcement Learning

2023-06-20 · Peeyush Kumar

Reinforcement Learning (RL) models have continually evolved to navigate the exploration - exploitation trade-off in uncertain Markov Decision Processes (MDPs). In this study, I leverage the principles of stochastic therm…

Navigate reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning to Explore and Exploit in POMDPs

2009-12-01 · NeurIPS 2009 12 · Chenghui Cai, Xuejun Liao, Lawrence Carin

A fundamental objective in reinforcement learning is the maintenance of a proper balance between exploration and exploitation. This problem becomes more challenging when the agent can only partially observe the states of…

Active Learning Reinforcement Learning