mlsanityData to 7 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 11

Not on the map. Why?

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 11 papers in the map (data through 7 Oct 2026). 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.

References · 19

  1. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  2. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  4. 2020Momentum Improves Normalized SGDcited by 136
  5. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  6. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  7. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  8. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  9. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  10. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  11. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  12. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
7 more
  1. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  2. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  3. 2021Better SGD using Second-order Momentumcited by 14
  4. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  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 6
  7. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 6.

11 papers.

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  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 6
  5. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  6. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
  7. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  8. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  9. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  10. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0
  11. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0