Research map / Reinforcement learning / MDPs and planning
On the Convergence of Single-Timescale Actor-Critic
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 that single-timescale actor-critic with softmax policy and step sizes decaying as k^{-2/3} converges to a globally optimal policy with O(ε^{-3}) sample complexity, improving the prior O(ε^{-4}) bound.
Problem
Global convergence and sample complexity of single-timescale actor-critic in tabular discounted MDPs with softmax policy parameterization; prior analyses only gave stationary-point guarantees, translating to O(ε^{-4}) global complexity.
Approach
Derives coupled actor/critic error recursions and uses a Lyapunov term (sub-optimality plus squared critic error) combined with the gradient domination lemma, then solves the resulting recursion via an ODE tracking argument to bound sub-optimality directly, with step sizes decaying as k^{-2/3}.
Key results
- Single-timescale actor-critic with step sizes O(k^{-2/3}) achieves J*-E[J^{pi_k}] <= O(k^{-1/3}), i.e., O(ε^{-3}) sample complexity for ε-globally optimal policy.
- Prior single-timescale analyses with k^{-1/2} steps give O(ε^{-4}) global complexity via the stationary-point-to-global conversion.
- Numerical simulations on random MDPs show k^{-2/3} step size performs best among tested schedules (k^0, k^{-1/3}, k^{-1/2}, k^{-2/3}, k^{-1}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use actor and critic step sizes O(k^{-2/3}) | Single-timescale actor-critic · Discounted finite-state MDPs | sample complexity for ε-close globally optimal policy: O(\epsilon^{-4}) -> O(\epsilon^{-3}) | Helped |
| Use η_k = β_k = k^{-2/3} instead of the other tested schedules (ablation) | Single-timescale actor-critic · Random MDP simulations | convergence rate | Helped |
| Use η_k = β_k = 0.01k^0, k^{-1/3}, or k^{-1/2} instead of k^{-2/3} (ablation) | Single-timescale actor-critic · Random MDP simulations | convergence rate | Mixed |
| Use η_k = β_k = k^{-1} instead of k^{-2/3} (ablation) | Single-timescale actor-critic · Random MDP simulations | convergence rate | Hurt |
| Use the proposed actor-critic step-size schedule | Single-timescale actor-critic · Discounted finite-state MDPs | critic tracking error rate: O(k^{-1/4}) -> O(k^{-1/6}) | Hurt |
Surprising findings
- The critic error decays only as O(k^{-1/6}), slower than the O(k^{-1/4}) rate in prior work, even though the actor's suboptimality improves.
Limitations
- Analysis assumes tabular softmax parameterization with finite state and action spaces.
- Relies on i.i.d. sampling from the discounted occupation measure, not Markovian sampling.
- Requires a sufficient exploration assumption and bounded mismatch coefficient.
Experimental setup
Datasets: randomly generated tabular MDPs
Benchmarks: randomly generated tabular MDPs (5, 20, 50 states)
Metrics: suboptimality J*-J^pi convergence rate under different step size schedules
Baselines: single-timescale actor-critic with k^{-1/2} step sizes (O(ε^{-4}) global) two-timescale double-loop actor-critic (O(ε^{-3}) with buffer)
Builds on: gradient domination lemma sufficient increase lemma single-timescale actor-critic analyses
Closest papers by meaning
- Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.92)
- Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation (AAAI 2025 · similarity 0.91)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.91)
- On the Convergence of Continuous Single-timescale Actor-critic (ICML 2025 · similarity 0.90)
- Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization (ICML 2024 · similarity 0.89)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 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.