Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms

Navdeep Kumar, Priyank Agrawal, Giorgia Ramponi, Kfir Yehuda Levy, Shie MannorSubmission to ICLR 2025 · Withdrawn

TL;DR

This paper establishes the global convergence of sample-based actor-critic algorithms with an improved sample complexity of $\tilde{O}(\epsilon^{-3})$, substantially improving upon the standard $O(\epsilon^{-4})$ rate. Crucially, the authors show that convergence does not require diminishing step sizes for both actor and critic: using a constant learning rate for the critic and a decaying learning rate for the actor is sufficient to handle stochastic noise and achieve global optimality.

What Problem Does This Paper Address?

Policy gradient and actor-critic algorithms power much of modern reinforcement learning (RL), yet their theoretical foundations still contain glaring gaps. While exact policy gradient methods achieve iteration complexity of $O(\epsilon^{-1})$, realistic sample-based actor-critic methods have lagged far behind.

Prior non-asymptotic analyses of actor-critic algorithms have typically established local convergence—bounding the expected squared norm of the gradient $\mathbb{E}[\|\nabla J\|^2] \le \epsilon^2$ using $O(\epsilon^{-2})$ samples. When translated to global optimality via gradient domination lemmas, this yields a slow sample complexity of $O(\epsilon^{-4})$. Moreover, classical two-time-scale stochastic approximation frameworks dictate that both the actor and the critic must use diminishing step sizes to average out stochastic noise, which contradicts widespread empirical practice where practitioners often use constant step sizes for the critic.

Methods

The authors analyze an online single-timescale Actor-Critic algorithm in finite-state, finite-action discounted Markov Decision Processes (MDPs) with softmax policy parameterization:

  • Algorithm Setup: At each step, a state-action pair is sampled according to the discounted state visitation distribution $d^{\pi_{\theta_k}}$. The policy parameters $\theta$ are updated via advantage-weighted updates, while the Q-function values are updated using standard temporal difference (TD) updates.
  • Asymmetric Learning Rates: The critic uses a constant step size $\beta_k = \beta$, while the actor uses a decaying step size $\eta_k = \Theta(k^{-2/3})$.
  • Bias Tracking via Contraction: Instead of trying to bound critic variance under diminishing step sizes, the authors bound the inner-product bias between true advantage and estimated advantage by leveraging the contraction property of the Bellman operator under a slowly varying policy.
  • ODE Tracking for Sub-Optimality Recurrences: The coupled system yields a non-trivial sub-optimality recurrence: $$a_k - a_{k+1} \ge \eta_k \left(c_1 a_k^2 - c_2 \eta_k\right)$$ The authors introduce an ordinary differential equation (ODE) comparison method to tightly solve this discrete recurrence.

Datasets

Not discussed in the paper. (This is a theoretical paper providing mathematical proofs; no empirical datasets or benchmark environments were used, aside from a synthetic numerical verification of the policy gradient bounds.)

Key Insights and Ideas

  • Decoupling Without Vanishing Critic Steps: Traditional wisdom assumes both the actor and critic must have decreasing step sizes to average out stochasticity. Here, the critic treats the actor's updates as adversarial perturbations whose magnitude shrinks over time (because $\eta_k \to 0$). Because the Bellman operator is a contraction, a constant critic step size contracts the tracking error at a geometric rate, keeping tracking bias proportional to the actor's step size: $\mathcal{O}(\eta_k)$.
  • Actor Handles the Noise: Because the critic's estimation bias naturally shrinks at rate $O(\eta_k)$, the actor's decreasing step size is sufficient on its own to average out both actor and critic noise.
  • First-Step Convergence Guarantees for Policy Gradients: As a bonus, applying the authors' ODE-tracking method to exact policy gradients sharpens prior bounds (e.g., Mei et al., 2022). Existing bounds on sub-optimality were vacuous for small iterations ($k < \mathcal{O}((1-\gamma)^{-5})$) because their constant exceeded the maximum possible return gap; the new analysis yields monotonically decreasing, meaningful upper bounds starting from step $k = 1$.

Key Results

  • Actor-Critic Global Sample Complexity: Global convergence to an $\epsilon$-optimal policy ($J^* - \mathbb{E}[J_k] \le \epsilon$) is achieved with a sample complexity of $\tilde{O}(\epsilon^{-3})$, improving on the existing $O(\epsilon^{-4})$ benchmark.
  • Convergence Rate: The expected sub-optimality of the online actor-critic algorithm decays at a rate of: $$J^* - \mathbb{E}[J_k] \le \mathcal{O}\left(k^{-1/3}\right)$$
  • Exact Policy Gradient Smoothness Factor: For the exact gradient setting, the asymptotic rate is improved by a factor of $(1-\gamma)^{-3}$ while providing non-trivial bounds for small $k$.

Limitations and Future Work

  • Discounted Distribution Sampling: The algorithm assumes direct access to sample states from the stationary visitation distribution $d^{\pi_{\theta_k}}$ at each iteration. Simulating this via Markov chain restarts adds an expected computational overhead factor of $\frac{1}{1-\gamma}$.
  • Tabular Softmax Policies: The analysis is restricted to finite state-action spaces and tabular softmax policy representations.
  • Future Directions: Extending this constant-critic, diminishing-actor framework to continuous state-action spaces, function approximation (e.g., neural policy and value parameterizations), and average-reward MDP settings.

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. 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},
}

Loading related content...

Figure