# Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

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

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

## 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, 30 of 41)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentation](https://mlsanity.com/paper/2202.06558/) (2022)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [A Primal-Dual Approach to Constrained Markov Decision Processes](https://mlsanity.com/paper/2101.10895/) (2021)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Learning in Markov Decision Processes under Constraints](https://mlsanity.com/paper/2002.12435/) (2020)
- [Concave Utility Reinforcement Learning with Zero-Constraint Violations](https://mlsanity.com/paper/2109.05439/) (2021)
- [Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL](https://mlsanity.com/paper/2008.13319/) (2020)
- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [Probabilistic Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2503.07671/) (2025)
- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm](https://mlsanity.com/paper/2402.02042/) (2024)
- [Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm](https://mlsanity.com/paper/2505.15138/) (2025)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Anytime-Constrained Reinforcement Learning](https://mlsanity.com/paper/2311.05511/) (2023)

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