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 (4)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Conservative Contextual Linear Bandits
• Online Convex Optimization in Adversarial Markov Decision Processes
• Constrained Upper Confidence Reinforcement Learning

Cited by in corpus (8)

• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
• A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes
• Balancing Constraints and Rewards with Meta-Gradient D4PG
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Safe Reinforcement Learning with Linear Function Approximation
• Adaptive Sampling for Estimating Distributions: A Bayesian Upper Confidence Bound Approach