mlsanityData to 7 Oct 2026

Provably Efficient Model-Free Algorithms for Non-stationary CMDPs

arXiv 2303.05733 ↗First posted 10 Mar 2023cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

We study model-free reinforcement learning (RL) algorithms in episodic non-stationary constrained Markov Decision Processes (CMDPs), in which an agent aims to maximize the expected cumulative reward subject to a cumulative constraint on the expected utility (cost). In the non-stationary environment, reward, utility functions, and transition kernels can vary arbitrarily over time as long as the cumulative variations do not exceed certain variation budgets. We propose the first model-free, simulator-free RL algorithms with sublinear regret and zero constraint violation for non-stationary CMDPs in both tabular and linear function approximation settings with provable performance guarantees. Our results on regret bound and constraint violation for the tabular case match the corresponding best results for stationary CMDPs when the total budget is known. Additionally, we present a general framework for addressing the well-known challenges associated with analyzing non-stationary CMDPs, without requiring prior knowledge of the variation budget. We apply the approach for both tabular and linear approximation settings.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 26 of its 42 references that are in the map. First posted on arXiv 10 Mar 2023.

Builds on

26 of 42 references.

References · 26

  1. 2016Concrete Problems in AI Safetycited by 1,582
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2021Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learningcited by 337
  6. 2020Exploration-Exploitation in Constrained MDPscited by 146
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  8. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  9. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  10. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  11. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 75
  12. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
14 more
  1. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  2. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  3. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  4. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  5. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  6. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  7. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  8. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  9. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  10. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  11. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  12. 2020Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Controlcited by 15
  13. 2019Reinforcement Learning with Dynamic Boltzmann Softmax Updatescited by 14
  14. 2014Energy-Aware Wireless Scheduling with Near Optimal Backlog and Convergence Time Tradeoffscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 4; 2025: 5; 2026: 6.

21 papers.

Sort:

By area:

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  2. 2023Constraint-Conditioned Policy Optimization for Versatile Safe Reinforcement Learningcited by 17
  3. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  4. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  5. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  6. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 5
  7. 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Timecited by 5
  8. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  9. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  10. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  11. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  12. 2025Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernelscited by 1
9 more
  1. 2025Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraintscited by 1
  2. 2026Safe Continual Reinforcement Learning Methods for Nonstationary Environments. Towards a Survey of the State of the Artcited by 1
  3. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  4. 2023Model-Free, Regret-Optimal Best Policy Identification in Online CMDPscited by 0
  5. 2025A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Modelscited by 0
  6. 2026Provably Safe Reinforcement Learning for Stochastic Reach-Avoid Problems with Entropy Regularizationcited by 0
  7. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  8. 2026Safe Continual Reinforcement Learning under Nonstationarity via Adaptive Safety Constraintscited by 0
  9. 2026Boundary-Seeking Policy Gradient for Safe Reinforcement Learningcited by 0