Exploration-Exploitation in Constrained MDPs

Abstract

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.

References in corpus (11)

• Safe Model-based Reinforcement Learning with Stability Guarantees
• Empirical Bernstein Bounds and Sample Variance Penalization
• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Online Learning: A Modern Introduction Using Convex Optimization
• Online Convex Optimization in Adversarial Markov Decision Processes
• Conservative Contextual Linear Bandits
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Constrained Upper Confidence Reinforcement Learning
• Conservative Bandits
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies

Cited by in corpus (22)

• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
• Reinforcement Learning for Multi-Objective and Constrained Markov Decision Processes
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Balancing Constraints and Rewards with Meta-Gradient D4PG
• A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification
• A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints
• Safe Reinforcement Learning with Linear Function Approximation
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Markov Decision Processes with Long-Term Average Constraints
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Concave Utility Reinforcement Learning with Zero-Constraint Violations
• Reward is enough for convex MDPs
• Online Selection of Diverse Committees
• Adaptive Sampling for Estimating Distributions: A Bayesian Upper Confidence Bound Approach