mlsanityData to 14 Oct 2026

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

arXiv 2609.39093 ↗First posted 30 Sep 2026cs.LGcited by 0

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

Abstract (arXiv)

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions T. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves widetildeO(√T) regret and cumulative constraint violation with high probability in the tabular setting. The √T dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in T.

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 41 of its 61 references that are in the map. First posted on arXiv 30 Sep 2026.

Builds on

41 of 61 references.

Closest ancestors · 11

Same direction, newest first

  1. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret12 May
  2. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization8 Feb
  3. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm21 May
  4. 2025A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs16 Apr
  5. 2025Polynomial-Time Approximability of Constrained Reinforcement Learning11 Feb
  6. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling29 May
  7. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May
  8. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time23 May
  9. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents10 Mar
  10. 2024Truly No-Regret Learning in Constrained MDPs24 Feb
  11. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm3 Feb

Other references · 30

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  4. 2020Exploration-Exploitation in Constrained MDPscited by 149
  5. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  6. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  7. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  8. 2022Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentationcited by 69
  9. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  10. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  11. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  12. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
18 more
  1. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  2. 2021State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewardscited by 40
  3. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  4. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  5. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  6. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  7. 2020Learning in Markov Decision Processes under Constraintscited by 20
  8. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  9. 2020Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RLcited by 16
  10. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  11. 2025Probabilistic Shielding for Safe Reinforcement Learningcited by 12
  12. 2021Reinforcement Learning with Almost Sure Constraintscited by 11
  13. 2023Anytime-Constrained Reinforcement Learningcited by 6
  14. 2023ACPO: A Policy Optimization Algorithm for Average MDPs with Constraintscited by 4
  15. 2024Multi-agent assignment via state augmented reinforcement learningcited by 3
  16. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  17. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  18. 2026Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamicscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  2. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach
  3. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  4. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
  5. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs
  6. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints
  7. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  8. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process