mlsanityData to 14 Oct 2026

Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints

arXiv 2405.14372 ↗First posted 23 May 2024cs.LGcited by 5

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In constrained Markov decision processes (CMDPs) with adversarial rewards and constraints, a well-known impossibility result prevents any algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against a best-in-hindsight policy that satisfies constraints on average. In this paper, we show that this negative result can be eased in CMDPs with non-stationary rewards and constraints, by providing algorithms whose performances smoothly degrade as non-stationarity increases. Specifically, we propose algorithms attaining tildeO (√T + C) regret and positive constraint violation under bandit feedback, where C is a corruption value measuring the environment non-stationarity. This can be Theta(T) in the worst case, coherently with the impossibility result for adversarial CMDPs. First, we design an algorithm with the desired guarantees when C is known. Then, in the case C is unknown, we show how to obtain the same results by embedding such an algorithm in a general meta-procedure. This is of independent interest, as it can be applied to any non-stationary constrained online learning setting.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 21 of its 36 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

21 of 36 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar

Other references · 20

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2020Exploration-Exploitation in Constrained MDPscited by 149
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2016Corralling a Band of Bandit Algorithmscited by 100
  5. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  6. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  7. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  8. 2018Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertisingcited by 61
  9. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 50
  10. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  11. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  12. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
8 more
  1. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 35
  2. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  3. 2017Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Studycited by 14
  4. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  5. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  6. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  7. 2024Markov Persuasion Processes: Learning to Persuade from Scratchcited by 8
  8. 2020Provably Efficient Model-Free Algorithm for MDPs with Peak Constraintscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 3.

5 papers.

  1. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 12
  2. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  3. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  4. 2024A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraintscited by 1
  5. 2025Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraintscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2024Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback
  2. 2026Rate-Optimal Algorithm for Adversarial Linear CMDPs
  3. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  4. 2026Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
  5. 2024Truly No-Regret Learning in Constrained MDPs
  6. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation
  7. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  8. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling