Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms

Navdeep Kumar, Priyank Agrawal, Giorgia Ramponi, Kfir Yehuda Levy, Shie Mannor

Abstract

Actor-Critic (AC) methods are fundamental to reinforcement learning, yet their theoretical convergence properties, particularly in single-timescale settings, have remained poorly understood. This paper presents a theoretical breakthrough, improving the proven sample complexity for global convergence from $O(\epsilon^{-4})$ to $O(\epsilon^{-3})$. We introduce a novel ODE-based tracking framework and demonstrate that a non-standard $k^{-2/3}$ learning rate schedule is optimal for bridging the gap between empirical performance and mathematical theory. Our results establish a new state-of-the-art for single-timescale AC algorithms in infinite-horizon discounted MDPs.

Introduction

Actor-Critic (AC) algorithms are the workhorses of modern reinforcement learning, powering systems from AlphaGo to advanced robotics. These methods consist of two coupled components: an Actor that optimizes the policy and a Critic that evaluates action values. Theoretically, this coupling makes AC difficult to analyze, as the actor's updates depend on the critic's estimates, which in turn depend on the actor's evolving policy.

To simplify analysis, researchers often resort to "two-timescale" versions where the critic learns significantly faster than the actor. However, in practice, "single-timescale" updates—where both components are updated simultaneously—are preferred for their efficiency. Until now, the best proven sample complexity for a single-timescale AC to reach a globally optimal policy was $O(\epsilon^{-4})$. This work aims to provide a tighter, more realistic bound, bridging the gap between empirical success and mathematical understanding.

Methods

The authors analyze infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces and softmax-parameterized policies. Their approach introduces three key technical innovations:

  1. Unified Lyapunov Analysis: Instead of treating the actor and critic separately, the authors define a Lyapunov function that combines the actor's sub-optimality and the square of the critic's error. This allows for a holistic view of the system's "energy" decay.
  2. ODE Tracking Framework: The discrete updates of the AC algorithm are analyzed as trajectories following an Ordinary Differential Equation (ODE). This streamlined methodology helps solve the complex, interdependent recursions that typically hinder theoretical proofs.
  3. Optimized Step Sizes: While standard optimization often employs a $O(k^{-1/2})$ learning rate, this paper demonstrates that a decay rate of $O(k^{-2/3})$ for both the actor and critic is the "sweet spot" required to achieve the improved $O(\epsilon^{-3})$ complexity.

Results and Comparison

The core contribution of this work is the establishment of a sample complexity of $O(\epsilon^{-3})$ to reach an $\epsilon$-optimal policy. This represents a significant leap over the prior state-of-the-art of $O(\epsilon^{-4})$. Under the proposed $k^{-2/3}$ step size, the sub-optimality gap decreases at a rate of $O(k^{-1/3})$.

Comparison of sample complexity and convergence rates between this work and prior state-of-the-art single-timescale actor-critic analyses.

As shown in the comparison table above, this work achieves a better sample complexity and a stronger convergence guarantee ($J^* - J^\pi \le \epsilon$) compared to previous works that often focused on reaching stationary points ($\|\nabla J^\pi\| \le \epsilon$).

Numerical simulations on synthetic MDPs (with varying state and action space sizes) confirm these theoretical findings. The results demonstrate that the $k^{-2/3}$ learning rate schedule eventually outperforms common alternatives like $k^{-1/2}$ or constant rates in terms of final policy performance.

Discussion and Future Work

A key insight from this research is the $k^{-2/3}$ advantage. The authors found that the conventional $k^{-1/2}$ rate is sub-optimal for this coupled system; the $k^{-2/3}$ rate allows the actor to improve faster ($O(k^{-1/3})$) even if the critic error decreases more slowly ($O(k^{-1/6})$).

Despite this progress, limitations remain. The current analysis is restricted to tabular settings (finite state spaces) and does not yet incorporate the complexities of deep neural network function approximation. Additionally, while the authors assume i.i.d. sampling for simplicity, extending this to more realistic Markovian sampling is a clear next step. Finally, the authors suggest that reaching the theoretical lower bound of $O(\epsilon^{-2})$ will likely require a shift in focus from managing critic variance to minimizing critic bias.

Summary updated

Abstract

In this paper, we establish the global convergence of the actor-critic algorithm with a significantly improved sample complexity of $O(\epsilon^{-3})$, advancing beyond the existing local convergence results. Previous works provide local convergence guarantees with a sample complexity of $O(\epsilon^{-2})$ for bounding the squared gradient of the return, which translates to a global sample complexity of $O(\epsilon^{-4})$ using the gradient domination lemma. In contrast to traditional methods that employ decreasing step sizes for both the actor and critic, we demonstrate that a constant step size for the critic is sufficient to ensure convergence in expectation. This key insight reveals that using a decreasing step size for the actor alone is sufficient to handle the noise for both the actor and critic. Our findings provide theoretical support for the practical success of many algorithms that rely on constant step sizes.
BibTeX
@misc{kumar2024improved,
  author = {Navdeep Kumar and Priyank Agrawal and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor},
  title = {{Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms}},
  year = {2024},
  eprint = {2410.08868},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.08868},
}
Figure