Research map / Reinforcement learning / Policy gradient and actor-critic
Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves global convergence of the Multi-level Actor-Critic (MAC) average-reward policy gradient method without mixing-time oracle knowledge, achieving a sqrt(tau_mix) dependence, and shows a gridworld advantage over PPGAE.
Problem
Global convergence of average-reward policy gradient methods typically requires oracle knowledge of the mixing time, which is hard to estimate and forces impractically long trajectories in large state spaces.
Approach
Extends the convergence analysis of the Multi-level Actor-Critic (MAC), which uses geometric-length MLMC gradient estimators and Adagrad stepsizes, to global optimality in the infinite-horizon average-reward setting, obtaining a sqrt(tau_mix) dependence with no mixing-time knowledge.
Key results
- MAC achieves a higher moving-average success rate than PPGAE, Vanilla AC, and REINFORCE in a 15x15 sparse gridworld over 300 episodes with 100 trials.
- Theory gives a mixing-time dependence of sqrt(tau_mix) for MAC without mixing-time knowledge, versus tau_mix^2 for PPGAE, and an O(T^{-1/4}) rate.
- The paper finds that the MLMC-based reward tracking analysis in prior work needed correction, replacing a square-root-of-tau term with a corrected bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAC instead of PPGAE | Average-reward policy gradient · Average-reward global convergence | mixing time dependence: $\wo{\tau_{mix}^2}$ -> $\wo{\sqrt{\tau_{mix}}}$ | Helped |
| Use MAC instead of PPGAE | Policy gradient on the 15-by-15 sparse gridworld · 15-by-15 sparse gridworld | success rate | Helped |
| Use MAC instead of Vanilla AC | Policy gradient on the 15-by-15 sparse gridworld · 15-by-15 sparse gridworld | success rate | Helped |
| Use MAC instead of REINFORCE | Policy gradient on the 15-by-15 sparse gridworld · 15-by-15 sparse gridworld | success rate | Helped |
Surprising findings
- The original reward-tracking analysis (Lemma D.1 of the prior MAC work) contained an error; the authors provide a corrected proof that removes a square root term.
Limitations
- Experiments are limited to a single small 15x15 gridworld proof-of-concept.
- Convergence requires an ergodicity assumption and linear critic function approximation with approximation error terms.
- Rate remains O(T^{-1/4}) and the bound includes a critic approximation error term.
Experimental setup
Benchmarks: 15x15 sparse gridworld goal-reaching navigation
Metrics: moving average success rate
Baselines: PPGAE Vanilla AC REINFORCE
Builds on: MAC (multi-level actor-critic) PPGAE general policy gradient global convergence framework for discounted/average rewa
Closest papers by meaning
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.92)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.89)
- Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation (AAAI 2025 · similarity 0.89)
- Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.88)
- Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning (ICML 2024 · similarity 0.88)
- On the Second-Order Convergence of Biased Policy Gradient Algorithms (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.