mlsanityData to 14 Oct 2026

Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret

arXiv 2605.11586 ↗First posted 12 May 2026cs.LG math.OCcited by 2

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. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of widetildeO(T2/3), improving upon the best known bounds, where T denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.

Key facts. Cited by 2 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 51 of its 68 references that are in the map. First posted on arXiv 12 May 2026.

Builds on

51 of 68 references.

Closest ancestors · 21

Same direction, newest first

  1. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards29 Mar
  2. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization8 Mar
  3. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPs20 Feb
  4. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization8 Feb
  5. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs7 Nov
  6. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints28 May
  7. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach26 May
  8. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm21 May
  9. 2025A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs16 Apr
  10. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces25 Feb
  11. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation14 Feb
  12. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism14 Oct
9 more
  1. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization3 Oct
  2. 2024Optimistic Q-learning for average reward and episodic reinforcement learning18 Jul
  3. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling29 May
  4. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May
  5. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs2 Apr
  6. 2024Horizon-Free Regret for Linear Markov Decision Processes15 Mar
  7. 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar
  8. 2024Truly No-Regret Learning in Constrained MDPs24 Feb
  9. 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. 2023Safe RLHF: Safe Reinforcement Learning from Human Feedbackcited by 656
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  5. 2020Exploration-Exploitation in Constrained MDPscited by 149
  6. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  8. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  9. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  10. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  11. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 50
  12. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
18 more
  1. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  2. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  3. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  4. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  5. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  6. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  7. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  8. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  9. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  10. 2020Learning in Markov Decision Processes under Constraintscited by 20
  11. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  12. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  13. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  14. 2023Accelerating Value Iteration with Anchoringcited by 11
  15. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 7
  16. 2025Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processescited by 6
  17. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 4
  18. 2021Markov Decision Processes with Long-Term Average Constraintscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0
  2. 2026Rate-Optimal Algorithm for Adversarial Linear CMDPscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
  2. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  3. 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
  4. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation
  5. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints
  6. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
  7. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses
  8. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints