mlsanityData to 7 Oct 2026

Exploration-Exploitation in Constrained MDPs

arXiv 2003.02189 ↗First posted 4 Mar 2020cs.LG stat.MLcited by 146

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 146 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 23; 2022: 21; 2023: 32; 2024: 27; 2025: 24; 2026: 19.

146 papers.

Sort:

By area:

  1. 2023Confronting Reward Model Overoptimization with Constrained RLHFcited by 96
  2. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  3. 2021Reward is enough for convex MDPscited by 82
  4. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  5. 2022Constrained Policy Optimization via Bayesian World Modelscited by 55
  6. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  7. 2021Safe Reinforcement Learning Using Advantage-Based Interventioncited by 45
  8. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  9. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  10. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  11. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  12. 2022Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizabilitycited by 32
38 more
  1. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  2. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  3. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  4. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  5. 2022MuZero with Self-competition for Rate Control in VP9 Video Compressioncited by 27
  6. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  7. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  8. 2023Long-Term Fairness with Unknown Dynamicscited by 25
  9. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  10. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  11. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  12. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  13. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  14. 2022Safe Reinforcement Learning Using Black-Box Reachability Analysiscited by 22
  15. 2024ActSafe: Active Exploration with Safety Constraints for Reinforcement Learningcited by 22
  16. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  17. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  18. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  19. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  20. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  21. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  22. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  23. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  24. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  25. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  26. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  27. 2022Robust Constrained Reinforcement Learningcited by 14
  28. 2022Safe Linear Bandits over Unknown Polytopescited by 13
  29. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  30. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  31. 2025Know When to Explore: Difficulty-Aware Certainty as a Guide for LLM Reinforcement Learningcited by 12
  32. 2022Variance-Aware Sparse Linear Banditscited by 11
  33. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  34. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  35. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  36. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  37. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  38. 2023Online Restless Multi-Armed Bandits with Long-Term Fairness Constraintscited by 10

50 most cited of 146 All 146 (JSON)