mlsanityData to 14 Oct 2026

Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints

arXiv 2202.00150 ↗First posted 31 Jan 2022cs.LGcited by 29

Not on the map. Why?

Abstract (arXiv)

We study regret minimization for infinite-horizon average-reward Markov Decision Processes (MDPs) under cost constraints. We start by designing a policy optimization algorithm with carefully designed action-value estimator and bonus term, and show that for ergodic MDPs, our algorithm ensures widetildeO(√T) regret and constant constraint violation, where T is the total number of time steps. This strictly improves over the algorithm of (Singh et al., 2020), whose regret and constraint violation are both widetildeO(T2/3). Next, we consider the most general class of weakly communicating MDPs. Through a finite-horizon approximation, we develop another algorithm with widetildeO(T2/3) regret and constraint violation, which can be further improved to widetildeO(√T) via a simple modification, albeit making the algorithm computationally inefficient. As far as we know, these are the first set of provable algorithms for weakly communicating MDPs with cost constraints.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). Builds on 34 of its 45 references that are in the map. First posted on arXiv 31 Jan 2022.

Builds on

34 of 45 references.

References · 34

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2018Reward Constrained Policy Optimizationcited by 417
  4. 2020Exploration-Exploitation in Constrained MDPscited by 149
  5. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  6. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  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. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  11. 2020Stochastic Bandits with Linear Constraintscited by 68
  12. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
22 more
  1. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 62
  2. 2016Conservative Banditscited by 59
  3. 2016Conservative Contextual Linear Banditscited by 57
  4. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  5. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  6. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  7. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  8. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  9. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  10. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  11. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  12. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  13. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  14. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  15. 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
  16. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  17. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  18. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  19. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  20. 2020Improved Algorithms for Conservative Exploration in Banditscited by 16
  21. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  22. 2021Markov Decision Processes with Long-Term Average Constraintscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 14; 2024: 4; 2025: 3; 2026: 7.

29 papers.

Sort:

By area:

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  2. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  3. 2023Robust Average-Reward Markov Decision Processescited by 22
  4. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  5. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  6. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 14
  7. 2023Online Restless Multi-Armed Bandits with Long-Term Fairness Constraintscited by 10
  8. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  9. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  10. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  11. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 6
  12. 2023Online Nonstochastic Control with Adversarial and Static Constraintscited by 5
17 more
  1. 2024Bellman Diffusion Modelscited by 5
  2. 2023ACPO: A Policy Optimization Algorithm for Average MDPs with Constraintscited by 4
  3. 2024Adversarially Trained Weighted Actor-Critic for Safe Offline Reinforcement Learningcited by 4
  4. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  5. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  6. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Samplingcited by 2
  7. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  8. 2022An Empirical Evaluation of Posterior Sampling for Constrained Reinforcement Learningcited by 1
  9. 2023Graph Exploration for Effective Multi-agent Q-Learningcited by 1
  10. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  11. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  12. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  13. 2023Model-Free, Regret-Optimal Best Policy Identification in Online CMDPscited by 0
  14. 2023Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Needcited by 0
  15. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  16. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  17. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0