Research map / Reinforcement learning / MDPs and planning
A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
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.
Proposes MLMC-based Natural Actor-Critic (MLMC-NAC) for average-reward RL with general policy parametrization, achieving a state-space-independent global rate of Õ(1/√T) without knowledge of mixing or hitting times.
Problem
Global convergence of average-reward reinforcement learning with general (function-approximated) policy parametrization; prior actor-critic guarantees are Õ(T^{-1/4}) and prior order-optimal methods need mixing/hitting time knowledge and scale poorly with state-action space.
Approach
Combine a natural policy gradient subroutine with a TD critic, both estimated with multi-level Monte Carlo (MLMC) gradient estimators that remove the need for mixing-time knowledge, and refine the analysis to bound the error by the mean of the critic iterate rather than its expected norm, using a refined linear-recursion analysis that exploits the MLMC bias bound.
Key results
- Achieves a global convergence rate of Õ(T^{-1/2}) for average-reward MDPs with general policy parametrization, improving on the prior Õ(T^{-1/4}) actor-critic state of the art.
- The bound is independent of state and action space sizes and does not require knowledge of mixing or hitting times; the leading error term is O(sqrt(epsilon_app)+sqrt(epsilon_bias)) + Õ(t_mix^3 T^{-1/2}).
- Analysis shows that the critic error can be bounded through the mean iterate ||E[xi_t]-xi*|| rather than E||xi_t-xi*||, which a naive analysis would not give (would yield T^{-1/3}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MLMC-NAC instead of prior actor-critic methods | Average-reward RL with general policy parametrization · Average-reward MDPs | global convergence rate: \Tilde{\cO}(1/T^{1/4}) -> \Tilde{\cO}(1/\sqrt{T}) | Helped |
| Use MLMC gradient estimators without requiring knowledge of mixing time | MLMC-NAC · Average-reward MDPs | mixing-time knowledge requirement | Helped |
| Use MLMC-NAC with general policy parametrization | Average-reward RL · Infinite-state MDPs | state-space size dependence of convergence bound | Helped |
Limitations
- Bound contains approximation errors (epsilon_app, epsilon_bias) that do not vanish with T, and depends on t_mix^3 in the leading term.
- Requires strong assumptions: bounded and Lipschitz score functions, Fisher non-degeneracy, linear critic features, and ergodicity of every policy's chain.
- Purely theoretical; no empirical experiments reported.
Experimental setup
Metrics: global convergence rate average optimality gap J* - E[J(theta_k)]
Baselines: MAC NAC-CFA PPGAE PHPG MDP-OOMD UCRL2 PSRL
Builds on: natural policy gradient multi-level Monte Carlo gradient estimation MAC (actor-critic average reward) NAC-CFA
Closest papers by meaning
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.92)
- Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles (ICML 2024 · similarity 0.92)
- Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.92)
- Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation (AAAI 2025 · similarity 0.90)
- Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.89)
- On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.89)
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.