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

arXiv: https://arxiv.org/abs/2405.14372 · HTML: https://mlsanity.com/paper/2405.14372/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 21 of 21)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising](https://mlsanity.com/paper/1802.08365/) (2018)
- [Safe Reinforcement Learning on Autonomous Vehicles](https://mlsanity.com/paper/1910.00399/) (2019)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [Learning Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2403.03672/) (2024)
- [Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study](https://mlsanity.com/paper/1709.03465/) (2017)
- [No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions](https://mlsanity.com/paper/2305.17380/) (2023)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraints](https://mlsanity.com/paper/2304.14326/) (2023)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints](https://mlsanity.com/paper/2003.05555/) (2020)

## Built on by (most cited first, 5 of 5)

- [Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization](https://mlsanity.com/paper/2410.02275/) (2024)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Data-Dependent Regret Bounds for Constrained MABs](https://mlsanity.com/paper/2505.20010/) (2025)
- [A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints](https://mlsanity.com/paper/2407.05793/) (2024)
- [Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2509.20114/) (2025)

## 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.