mlsanityData to 14 Oct 2026

Instance-Dependent Regret for CMDPs with Step-Wise Constraints

arXiv 2610.02520 ↗First posted 1 Oct 2026cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity also fits: Safe and constrained RL

Abstract (arXiv)

We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order widetildeO(√SAHminmathbbV_Sigma,KVarstar+S√AH3minK,C+S2AH2) over K episodes, where H is the horizon of a single episode, while S and A are the numbers of states and actions, respectively. Here, Varstar is the maximum return variance among safe policies, mathbbV_Sigma is the variance accumulated before the first unsafe action is encountered, and C captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains widetildeO(H√SAK+S2AH2) step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in K. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 48 of its 56 references that are in the map. First posted on arXiv 1 Oct 2026.

Builds on

48 of 56 references.

Closest ancestors · 8

Same direction, newest first

  1. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs25 Mar
  2. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints28 May
  3. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces25 Feb
  4. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation14 Feb
  5. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism14 Oct
  6. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization3 Oct
  7. 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar
  8. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process26 Feb

Other references · 40

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2017Safe Reinforcement Learning via Shieldingcited by 449
  4. 2018Reward Constrained Policy Optimizationcited by 417
  5. 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  7. 2020Exploration-Exploitation in Constrained MDPscited by 149
  8. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  9. 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 115
  10. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  11. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  12. 2016Safe Exploration in Finite Markov Decision Processes with Gaussian Processescited by 75
28 more
  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  3. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  4. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  5. 2023Iterative Reachability Estimation for Safe Reinforcement Learningcited by 37
  6. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  7. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  8. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  9. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  10. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
  11. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  12. 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 25
  13. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  14. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  15. 2022ReVar: Strengthening Policy Evaluation via Reduced Variance Samplingcited by 16
  16. 2022Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Riskcited by 15
  17. 2022Safe Linear Bandits over Unknown Polytopescited by 14
  18. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 11
  19. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 10
  20. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 7
  21. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 5
  22. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 4
  23. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  24. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 4
  25. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 3
  26. 2025Your Learned Constraint is Secretly a Backward Reachable Tubecited by 3
  27. 2022Branching Reinforcement Learningcited by 2
  28. 2026Data- and Variance-dependent Regret Bounds for Online Tabular MDPscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds
  2. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins
  3. 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
  4. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  5. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  6. 2024Truly No-Regret Learning in Constrained MDPs
  7. 2026Provably Safe Reinforcement Learning for Stochastic Reach-Avoid Problems with Entropy Regularization
  8. 2025Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents