mlsanityData to 7 Oct 2026

Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes

arXiv 2309.01922 ↗First posted 5 Sep 2023cs.LG cs.AIcited by 22

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider an infinite horizon average reward Markov Decision Process (MDP). Distinguishing itself from existing works within this context, our approach harnesses the power of the general policy gradient-based algorithm, liberating it from the constraints of assuming a linear MDP structure. We propose a policy gradient-based algorithm and show its global convergence property. We then prove that the proposed algorithm has tildeO(T3/4) regret. Remarkably, this paper marks a pioneering effort by presenting the first exploration into regret-bound computation for the general parameterized policy gradient algorithm in the context of average reward scenarios.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 20 of its 36 references that are in the map. First posted on arXiv 5 Sep 2023.

Builds on

20 of 36 references.

References · 20

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  6. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  8. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  9. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  10. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  11. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  12. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
8 more
  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  2. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  3. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  4. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  5. 2020Deep Reinforcement Learning Based Intelligent Reflecting Surface for Secure Wireless Communicationscited by 21
  6. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  7. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  8. 2023Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritizationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 7; 2026: 7.

22 papers.

Sort:

By area:

  1. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  2. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  3. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  4. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  5. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  6. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 6
  7. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
  8. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 6
  9. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  10. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  11. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  12. 2025Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPscited by 3
10 more
  1. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 2
  2. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  3. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  4. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  5. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  6. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  7. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  8. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  9. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  10. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0