mlsanityData to 7 Oct 2026

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach

arXiv 2407.18878 ↗First posted 26 Jul 2024cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of tildeO(1/√T) for average-reward Markov Decision Processes (MDPs) (where T is the horizon length), without requiring the knowledge of mixing and hitting times. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 23 of its 35 references that are in the map. First posted on arXiv 26 Jul 2024.

Builds on

23 of 35 references.

References · 23

  1. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  2. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  3. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  4. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  5. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  6. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  7. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  8. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  9. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  10. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  11. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  12. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
11 more
  1. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  2. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  3. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  4. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  5. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  6. 2019Reinforcement Learning for Joint Optimization of Multiple Rewardscited by 15
  7. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  8. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  9. 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximationcited by 11
  10. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
  11. 2024Reinforced Sequential Decision-Making for Sepsis Treatment: The POSNEGDM Framework with Mortality Classifier and Transformercited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 9.

14 papers.

Sort:

By area:

  1. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  2. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  3. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 6
  4. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  5. 2025Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Accesscited by 2
  6. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 2
  7. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  8. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  9. 2026On the Convergence of Self-Improving Online LLM Alignmentcited by 1
  10. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  11. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  12. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0
2 more
  1. 2026Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Accelerationcited by 0
  2. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0