mlsanityData to 14 Oct 2026

Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs

arXiv 2404.02108 ↗First posted 2 Apr 2024cs.LGcited by 14

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We present two Policy Gradient-based algorithms with general parametrization in the context of infinite-horizon average reward Markov Decision Process (MDP). The first one employs Implicit Gradient Transport for variance reduction, ensuring an expected regret of the order tildeO(T2/3). The second approach, rooted in Hessian-based techniques, ensures an expected regret of the order tildeO(√T). These results significantly improve the state-of-the-art tildeO(T3/4) regret and achieve the theoretical lower bound. We also show that the average-reward function is approximately L-smooth, a result that was previously assumed in earlier works.

Key facts. Cited by 14 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 19 of its 31 references that are in the map. First posted on arXiv 2 Apr 2024.

Builds on

19 of 31 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles18 Mar

Other references · 18

  1. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  2. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  4. 2020Momentum Improves Normalized SGDcited by 139
  5. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  6. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  7. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  8. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  9. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  10. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  11. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  12. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
6 more
  1. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  2. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  3. 2021Better SGD using Second-order Momentumcited by 15
  4. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 13
  5. 2023Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritizationcited by 9
  6. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 8.

14 papers.

Sort:

By area:

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 15
  2. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  3. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  4. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 7
  5. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  6. 2024Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysiscited by 3
  7. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  8. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  9. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
  10. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  11. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  12. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0
2 more
  1. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0
  2. 2026Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  2. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  3. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  5. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  6. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  7. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Games
  8. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation