mlsanityData to 14 Oct 2026

Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization

arXiv 2602.08000 ↗First posted 8 Feb 2026cs.LGcited by 4

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 unichain assumption and general policy parameterizations. Existing regret analyses for constrained reinforcement learning largely rely on ergodicity or strong mixing-time assumptions, which fail to hold in the presence of transient states. We propose a primal--dual natural actor--critic algorithm that leverages multi-level Monte Carlo (MLMC) estimators and an explicit burn-in mechanism to handle unichain dynamics without requiring mixing-time oracles. Our analysis establishes finite-time regret and cumulative constraint violation bounds that scale as tildeO(√T), up to approximation errors arising from policy and critic parameterization, thereby extending order-optimal guarantees to a significantly broader class of CMDPs.

Key facts. Cited by 4 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 25 of its 35 references that are in the map. First posted on arXiv 8 Feb 2026.

Builds on

25 of 35 references.

Closest ancestors · 7

Same direction, newest first

  1. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach26 May
  2. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm21 May
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach26 Jul
  4. 2024Optimistic Q-learning for average reward and episodic reinforcement learning18 Jul
  5. 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation3 Jun
  6. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles18 Mar
  7. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm3 Feb

Other references · 18

  1. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  2. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  3. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  4. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  5. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  6. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 35
  7. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  8. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  9. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  10. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  11. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  12. 2020Learning in Markov Decision Processes under Constraintscited by 20
6 more
  1. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  2. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  3. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  4. 2023Two-Stage Constrained Actor-Critic for Short Video Recommendationcited by 16
  5. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  6. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  2. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  3. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  4. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  4. 2024Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms
  5. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs
  6. 2024Truly No-Regret Learning in Constrained MDPs
  7. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
  8. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes