Research map / Learning theory and algorithms / Sample complexity

Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization

ICML 2024 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of MDPs · 0 citations (OpenAlex)

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.

Provides the first last-iterate global convergence analysis of actor-critic with multi-layer neural network actor and critic under Markovian sampling in continuous state-action spaces, achieving Õ(ε⁻³) sample complexity.

Problem

Existing actor-critic theory lacks a single analysis covering multi-layer neural networks, Markovian sampling, continuous spaces, last-iterate performance, and global optimality (MMCLG); prior global results are mostly average-iterate or limited to linear/shallow/finite-space settings.

Approach

Combines a smoothness assumption on the policy parametrization with a weak gradient domination property of the MDP to bound the last-iterate optimality gap by critic estimation errors, and decomposes the critic error into approximation, Markovian sampling, and finite-width/optimization errors so the bound holds for deep networks and continuous action spaces without relying on action-space cardinal

Key results

• Establishes last-iterate global convergence with sample complexity Õ(ε^-3) for actor-critic with neural network actor and critic under Markovian sampling.
• Theorem gives J*-J(λ_t) bounded by Õ(1/t) + Õ(1/√n) + Õ(L^-1/4) + Õ(m^-1/12 D^7/2) + Õ(γ^J) + Õ(√ε_bias) + Õ(√ε_approx).
• Choosing t=Õ(ε^-1), n=Õ(ε^-2), L=Õ(ε^-4), J=Õ(log(1/ε)) yields total sample count t·n=Õ(ε^-3).

Limitations

• Relies on strong assumptions such as approximation-closure of the critic class and overparameterized neural networks for small bias error.
• Finite-width error term m^-1/12 D^7/2 does not vanish for finite networks.
• Analysis is theoretical with no empirical experiments.

Experimental setup

Metrics: sample complexity last-iterate optimality gap J*-J(λ_t)

Baselines: Kumar et al. neural actor-critic Wang et al. neural actor-critic Olshevsky and Gharesifard linear actor-critic Kumar et al. last iterate analysis Xu et al. linear actor-critic

Builds on: TD3 weak gradient domination (Ding et al.) Neural Tangent Kernel

Closest papers by meaning

• Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.91)
• On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.89)
• Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation (AAAI 2025 · similarity 0.88)
• Actor-Critics Can Achieve Optimal Sample Efficiency (ICML 2025 · similarity 0.88)
• On the Convergence of Continuous Single-timescale Actor-critic (ICML 2025 · similarity 0.88)
• Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.88)