mlsanityData to 7 Oct 2026

Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles

arXiv 2403.11925 ↗First posted 18 Mar 2024cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

In the context of average-reward reinforcement learning, the requirement for oracle knowledge of the mixing time, a measure of the duration a Markov chain under a fixed policy needs to achieve its stationary distribution, poses a significant challenge for the global convergence of policy gradient methods. This requirement is particularly problematic due to the difficulty and expense of estimating mixing time in environments with large state spaces, leading to the necessity of impractically long trajectories for effective gradient estimation in practical applications. To address this limitation, we consider the Multi-level Actor-Critic (MAC) framework, which incorporates a Multi-level Monte-Carlo (MLMC) gradient estimator. With our approach, we effectively alleviate the dependency on mixing time knowledge, a first for average-reward MDPs global convergence. Furthermore, our approach exhibits the tightest available dependence of Oleft( √τmix right)known from prior work. With a 2D grid world goal-reaching navigation experiment, we demonstrate that MAC outperforms the existing state-of-the-art policy gradient-based method for average reward settings.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 21 of its 32 references that are in the map. First posted on arXiv 18 Mar 2024.

Builds on

21 of 32 references.

References · 21

  1. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  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. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  5. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  6. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  7. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  8. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  9. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  10. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  11. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  12. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
9 more
  1. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  2. 2021On-Policy Deep Reinforcement Learning for the Average-Reward Criterioncited by 29
  3. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 26
  4. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  5. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  6. 2021Continual Learning In Environments With Polynomial Mixing Timescited by 13
  7. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  8. 2023Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritizationcited by 9
  9. 2023VERN: Vegetation-aware Robot Navigation in Dense Unstructured Outdoor Environmentscited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  2. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  3. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  4. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  5. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  6. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0