mlsanityData to 14 Oct 2026

A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraints

arXiv 2304.14326 ↗First posted 27 Apr 2023cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We study online learning in episodic constrained Markov decision processes (CMDPs), where the learner aims at collecting as much reward as possible over the episodes, while satisfying some long-term constraints during the learning process. Rewards and constraints can be selected either stochastically or adversarially, and the transition function is not known to the learner. While online learning in classical (unconstrained) MDPs has received considerable attention over the last years, the setting of CMDPs is still largely unexplored. This is surprising, since in real-world applications, such as, e.g., autonomous driving, automated bidding, and recommender systems, there are usually additional constraints and specifications that an agent has to obey during the learning process. In this paper, we provide the first best-of-both-worlds algorithm for CMDPs with long-term constraints, in the flavor of Balseiro et al. (2023). Our algorithm is capable of handling settings in which rewards and constraints are selected either stochastically or adversarially, without requiring any knowledge of the underling process. Moreover, our algorithm matches state-of-the-art regret and constraint violation bounds for settings in which constraints are selected stochastically, while it is the first to provide guarantees in the case in which they are chosen adversarially.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 14 of its 29 references that are in the map. First posted on arXiv 27 Apr 2023.

Builds on

14 of 29 references.

References · 14

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  3. 2020Exploration-Exploitation in Constrained MDPscited by 149
  4. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  5. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  6. 2018Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertisingcited by 61
  7. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 50
  8. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  9. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
  10. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  11. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 35
  12. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
2 more
  1. 2017Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Studycited by 14
  2. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 6; 2025: 2.

9 papers.

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  2. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 16
  3. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  4. 2024Markov Persuasion Processes: Learning to Persuade from Scratchcited by 8
  5. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  6. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 6
  7. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  8. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcited by 1
  9. 2024A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraintscited by 1