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

arXiv: https://arxiv.org/abs/2404.02108 · HTML: https://mlsanity.com/paper/2404.02108/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 19 of 19)

- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [Concave Utility Reinforcement Learning with Zero-Constraint Violations](https://mlsanity.com/paper/2109.05439/) (2021)
- [Better SGD using Second-order Momentum](https://mlsanity.com/paper/2103.03265/) (2021)
- [Momentum-Based Policy Gradient with Second-Order Information](https://mlsanity.com/paper/2205.08253/) (2022)
- [Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritization](https://mlsanity.com/paper/2305.05163/) (2023)
- [Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms](https://mlsanity.com/paper/2302.01450/) (2023)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)

## Built on by (most cited first, 14 of 14)

- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm](https://mlsanity.com/paper/2505.15138/) (2025)
- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach](https://mlsanity.com/paper/2505.19986/) (2025)
- [Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysis](https://mlsanity.com/paper/2408.04780/) (2024)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2603.08518/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)
- [Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs](https://mlsanity.com/paper/2607.28390/) (2026)
- [Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs](https://mlsanity.com/paper/2610.04117/) (2026)

## 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.