Research map / Reinforcement learning / Policy gradient and actor-critic
On the Convergence of Continuous 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.
Gives the first finite-time convergence analysis of single-sample, single-timescale actor-critic with Markovian sampling in continuous state-action spaces, via a novel Lyapunov framework.
Problem
Finite-time convergence of the canonical single-timescale actor-critic with linear critic and Markovian sampling is unknown for continuous state-action spaces; prior analyses are limited to finite actions, i.i.d. sampling from unknown distributions, or two-timescale/double-loop variants.
Approach
A Lyapunov function combining critic and actor errors is used to analyze coupled single-timescale updates; an operator-based analysis shows the Markovian actor sampling (reset with probability 1-γ) converges to the discounted state visitation distribution, enabling continuous-space bounds without i.i.d. sampling.
Key results
- Finite-time rate of Õ(T^{-1/2}) for both average squared critic error and policy gradient norm (plus O(ϵ_app) approximation error), implying Õ(ϵ^{-2}) sample complexity.
- Stepsize ratio c must satisfy c < λ/(4B L_c) for convergence of the Lyapunov function.
- Proves the Markovian actor sampling distribution converges geometrically (rate γ) to the discounted state visitation distribution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed single-timescale actor-critic with Markovian sampling in continuous state-action spaces | Actor-critic with linear function approximation · Discounted reward, continuous state-action spaces | sample complexity: O(ϵ−2) -> ˜O(ϵ−2) | Helped |
| Use Markovian sampling for both actor and critic updates | Continuous single-timescale actor-critic · Continuous state-action spaces | actor error: O(log2 T/√T) + O(ϵapp) | Helped |
Limitations
- Requires linear function approximation of the critic with approximation error ϵ_app that does not vanish.
- Logarithmic factor from mixing time; relies on uniform ergodicity and a simulator capable of resets for actor sampling.
- Assumes bounded-support policies and a projection on critic parameters.
Experimental setup
Metrics: expected squared critic error expected squared policy gradient norm
Baselines: Chen et al. 2021 Olshevsky & Gharesifard 2023 Chen & Zhao 2024 Wu et al. 2020
Builds on: Chen et al. 2021 single-timescale actor-critic Olshevsky & Gharesifard 2023 Wu et al. 2020 two-timescale actor-critic Chen & Zhao 2024 Zhang et al. 2020 policy gradient smoothness
Closest papers by meaning
- On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.90)
- Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.89)
- Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization (ICML 2024 · similarity 0.88)
- Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning (ICLR 2025 · similarity 0.87)
- Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation (AAAI 2025 · similarity 0.87)
- A Theoretical Justification for Asymmetric Actor-Critic Algorithms (ICML 2025 · similarity 0.87)
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.