A Finite Time Analysis of Two Time-Scale Actor Critic Methods

Yue Wu; Weitong Zhang; Pan Xu; Quanquan Gu

Source-linked AI summary

A Finite Time Analysis of Two Time-Scale Actor Critic Methods

Yue Wu, Weitong Zhang, Pan Xu, Quanquan Gu

arXiv:2005.01350v3May 4, 2020cs.LGmath.OCstat.ML

TL;DR

Finite-time convergence and sample complexity for two time-scale actor-critic methods under non-i.i.d. data have been largely open. This paper provides a non-asymptotic analysis of an online two time-scale method and proves convergence to a first-order stationary point with O~(ε^-2.5) sample complexity.

Problem
Finite-time convergence, sample requirements, and learning-rate choices for two time-scale actor-critic methods under non-i.i.d. data remain largely unresolved.
Method
The paper analyzes an online two time-scale actor-critic algorithm using simultaneous actor and critic updates with non-i.i.d. samples.
Results
The actor converges to an ε-approximate first-order stationary point of the non-concave performance function with O~(ε^-2.5) sample complexity.
Takeaways & Limitations
The analysis provides a finite-time convergence and sample-complexity guarantee for a practical two time-scale actor-critic method using non-i.i.d. Markovian samples.
Takeaways & Limitations
The reported O~(ε^-2.5) complexity is the lowest achieved so far for classic two time-scale actor-critic methods, while better policy-evaluation algorithms may improve it.

Abstract

from arXiv · show

Actor-critic (AC) methods have exhibited great empirical success compared with other reinforcement learning algorithms, where the actor uses the policy gradient to improve the learning policy and the critic uses temporal difference learning to estimate the policy gradient. Under the two time-scale learning rate schedule, the asymptotic convergence of AC has been well studied in the literature. However, the non-asymptotic convergence and finite sample complexity of actor-critic methods are largely open. In this work, we provide a non-asymptotic analysis for two time-scale actor-critic methods under non-i.i.d. setting. We prove that the actor-critic method is guaranteed to find a first-order stationary point (i.e., $\|\nabla J(\boldsymbolθ)\|_2^2 \le ε$) of the non-concave performance function $J(\boldsymbolθ)$, with $\mathcal{\tilde{O}}(ε^{-2.5})$ sample complexity. To the best of our knowledge, this is the first work providing finite-time analysis and sample complexity bound for two time-scale actor-critic methods.

1 Introduction

Two time-scale actor-critic methods combine policy improvement with temporal-difference value estimation, but their finite-time behavior remains insufficiently understood. This work analyzes a practical non-i.i.d. setting and introduces a proof framework for sharper convergence characterization.

Actor-critic methods combine actor policy-gradient updates with critic temporal-difference estimation of the policy gradient.
The analyzed two time-scale method updates actor and critic simultaneously, with the actor using a smaller step size than the critic.
Finite-time analysis remains largely missing, including how many samples are needed and how actor and critic learning rates should be chosen.
The method reaches an ε-approximate stationary point of the non-concave performance function after at most O~(ε^-2.5) samples without i.i.d. data assumptions.
The proof framework tightly characterizes estimation error in two time-scale algorithms and avoids an extra artificial O(t^ξ) factor introduced by iterative refinement.

2 Related work

Related work establishes asymptotic actor-critic convergence and finite-time results for related stochastic-approximation settings, while concurrent work studies a different two time-scale algorithm with the same sample-complexity order. This paper distinguishes its classical online update structure and broader approximation scope.

Non-i.i.d. reinforcement-learning analyses address biased noise caused by correlations between samples and trainable parameters.
Prior work established asymptotic convergence for two time-scale actor-critic methods, while finite-time stochastic-approximation analyses often assumed i.i.d. data.
A concurrent study achieved the same O~(ε^-2.5) sample complexity for two time-scale actor-critic methods.
This paper analyzes a classical algorithm with one actor and one critic update per iteration, unlike a concurrent method requiring a fresh episode for critic estimation.
The concurrent analysis requires compatible function approximation, whereas this paper does not require that specific linear function class.

3 Preliminaries

The preliminaries formulate average-reward reinforcement learning as an ergodic Markov decision process and derive policy-gradient and actor-critic updates. The analyzed online algorithm uses a linear TD(0) critic, advantage estimates, and continuous sample-path updates.

3.1 Markov decision processes: The environment is modeled as a discrete-time Markov decision process with finite actions, transition probabilities, bounded rewards, and a policy-induced stationary distribution.
3.1 Markov decision processes: The paper uses the average-reward setting, where ergodicity connects long-run rewards with expected rewards under the stationary distribution.
3.2 Policy gradient theorem: The performance function is the expected reward under the stationary distribution induced by the parameterized policy.
3.2 Policy gradient theorem: The policy gradient expresses performance improvement through expected action-value contributions weighted by policy-log-gradient terms.
3.3 REINFORCE with a baseline: REINFORCE estimates the policy gradient by using summed trajectory returns as estimated Q-values, while baselines can reduce variance.
3.4 The two time-scale actor-critic algorithm: The critic uses linear function approximation and TD(0), while the algorithm also updates an average-reward estimator and projects critic parameters.
3.4 The two time-scale actor-critic algorithm: Algorithm 1 is an online one-step actor-critic method that simultaneously updates actor and critic parameters using the advantage, represented by the temporal-difference error.
3.4 The two time-scale actor-critic algorithm: The method uses one naturally generated sample path and continuously inherits the critic from the previous iteration instead of restarting sampling.

4 Main theory

The theory analyzes two-time-scale actor-critic with linear TD evaluation under Markovian data, using assumptions that make the critic target well behaved and establish convergence rates for actor and critic. Combining these bounds yields an ε-approximate stationary point with Õ(ε^-2.5) sample complexity, while the rate depends on the actor and critic step-size exponents.

Assumptions: The analysis uses TD(0) with linear function approximation, bounded approximation error, uniform ergodicity, and policy regularity assumptions.The critic estimates the state-value function through a linear function class, while the Markov chain assumptions control non-i.i.d. noise.
Assumptions and propositions: The TD limiting point ω*(θ) is Lipschitz in the policy parameter, so the critic tracks a slowly moving target as the actor updates.This slow target movement is central to the two-time-scale interpretation: the actor moves slowly while the critic follows the target induced by the actor.
Actor convergence: The actor convergence theorem bounds gradient error using critic estimation error, actor-drift error, and the averaged critic error over a recent time window.The theorem applies a decaying actor step size α_t = c_α/(1+t)^σ and requires the critic error sequence to be bounded.
Critic convergence: The critic error reflects Markovian noise and semi-gradient variance together with the slow drift of the actor, with their dominance determined by σ−ν relative to ν.When the actor is much slower, Markovian noise and gradient variance dominate; when it is not sufficiently slower, target drift contributes more strongly.
Convergence rate and sample complexity: Setting σ = 3/5 and ν = 2/5 gives actor and critic step sizes O(1/t^3/5) and O(1/t^2/5), respectively, and convergence rate Õ(t^-2/5).Because each iteration uses one sample, the resulting sample complexity is Õ(ε^-2.5).
Convergence rate and sample complexity: The Õ(ε^-2.5) complexity improves on the O(ε^-4) complexity reported for decoupled actor-critic analyses, while better policy-evaluation algorithms may improve it further.The paper identifies GTD and TDC as possible alternatives to vanilla TD(0) for reducing sample complexity.

5 Conclusion and discussion

The paper presents a first finite-time analysis of two time-scale actor-critic methods with non-i.i.d. Markovian samples and linear function approximation. It proves non-asymptotic convergence and sample complexity, while identifying possible extensions and improvements.

The analysis covers an online, one-step two time-scale actor-critic algorithm with non-i.i.d. Markovian samples and linear function approximation.
The proof technique may extend to other two time-scale reinforcement learning algorithms.
Compatible features could address critic function approximation error and enable finite-time analysis for natural actor-critic methods.
Regularizing the critic could ensure boundedness and remove the assumption on the maximum eigenvalue.

Broader impact

The paper connects its finite-time actor-critic analysis to estimating training requirements and selecting learning rates. It also identifies a proof roadmap for the theoretical results.

The sample complexity bound could estimate the training time required for reinforcement learning models.
The finite-time bound could guide learning-rate selection by optimizing dominant-term constant factors.
The paper provides a roadmap for the main theory, with detailed proofs in the appendix.

A.1 Proof Sketch of Theorem 4.5

The proof sketch analyzes actor convergence through smoothness of the performance function, decomposition of update errors, and bounds on Markovian and estimation effects. It uses auxiliary chains and time-window averaging to control non-i.i.d. dependence.

Smoothness of J(θ) enables a gradient-ascent-style analysis despite the performance function being non-concave.
The actor-update error is decomposed into critic and reward-estimation bias, linear-approximation error, stochastic policy-gradient terms, and Markovian noise.
The proof separately bounds approximation, Markovian-bias, variance, policy-drift, and average-reward-estimation terms.
Uniform ergodicity and an auxiliary Markov chain control dependence when both policy and evaluation parameters change.
The critic analysis uses linear TD(0), bounded features, and matrix conditions to control the value-function estimation error.

C.1 Proof of Theorem 4.5

The detailed proof formalizes the actor update as a smooth stochastic-gradient process and bounds its approximation, Markovian, estimation, and variance errors. These bounds are combined to obtain averaged gradient-control inequalities.

The proof represents the actor update using a Lipschitz performance gradient and a decomposition of stochastic-gradient errors.
The update-error terms include critic and reward-estimation bias, linear approximation error, Markovian noise, and stochastic-gradient variance.
The critic approximation and Markovian noise are characterized by separate lemmas used to bound the actor-update error.
The proof bounds each error contribution, substitutes the bounds into the one-step inequality, and rearranges the result.
The resulting inequality controls averaged squared policy gradients together with estimation-error and approximation-error terms.

C.2 Proof of Theorem 4.7: Estimating the Average Reward

The proof analyzes the critic’s parameter and average-reward estimation under Markovian noise and a moving policy, using recursive error bounds and auxiliary lemmas. It controls bias, parameter drift, and two time-scale interactions before telescoping the resulting inequalities.

Setup: The analysis defines J(θ) as the average reward under policy πθ and introduces notation for the critic’s probabilistic dependencies.The stationary average reward is expressed through the state-action distribution and one-step reward.
Bias control: Markovian bias is controlled with auxiliary-chain arguments that separate policy drift, average-reward drift, and deviation from stationarity.The proof uses lagged iterates and total-variation-based comparisons to manage non-i.i.d. observations.
Critic recursion: The critic recursion is unrolled and its squared error is decomposed into terms involving estimation noise, average-reward error, actor drift, and quadratic step sizes.The proof bounds the critic update using projection, norm inequalities, and a bounded combined update.
Two time scales: The proof exploits σ > ν so the actor-to-critic step-size ratio remains bounded, enabling the recursive inequalities to be rearranged and telescoped.The resulting bounds collect multiple terms and express their growth using O(·) notation.
Conclusion: The final critic bound follows by collecting the component estimates and referring to the exact constants in the displayed intermediate bounds.The proof concludes after establishing the required recursive estimate.

C.4 Proof of Corollary 4.9

The corollary substitutes the theorem’s bounds and optimizes the two time-scale exponents. This yields a finite-time guarantee for reaching an approximate stationary point of the average-reward objective.

Rate optimization: σ = 3/5 and ν = 2/5 optimize the bound obtained from Theorem 4.5.The exponents are selected by optimizing the theorem’s bound.
Stationarity guarantee: The resulting condition targets an ε-approximate stationary point of J, ignoring approximation error.The corollary frames the guarantee in terms of the gradient-based stationarity criterion.

D.1 Proof of Lemma C.1

The lemmas establish bounds needed to control Markovian-noise terms in the actor-critic analysis. They decompose these terms across parameter drift, auxiliary-chain deviations, and stationary-distribution effects.

Bias decomposition: The proof decomposes Markovian bias into changes across time-lagged parameters and differences between original, auxiliary, and stationary tuples.This decomposition isolates temporal dependence from policy and parameter variation.
Auxiliary bounds: The auxiliary bounds control Ξ through actor-parameter drift and average-reward drift over the lag interval.The displayed estimate bounds the two drift contributions with constants multiplying ||θ_t − θ_{t−τ}|| and |η_t − η_{t−τ}|.
Bounding technique: Cauchy-Schwarz and norm properties are repeatedly used to derive the component inequalities and complete the auxiliary proofs.The proof explicitly applies these inequalities to the successive bounds.
Critic-dependent terms: The corresponding Λ analysis applies the same decomposition pattern to the critic parameter, actor parameter, and auxiliary-chain transition.The proof invokes separate auxiliary lemmas for each component before collecting the terms.

E.1 Proof of Lemma D.1

The proof establishes Lipschitz and boundedness properties for the policy-gradient-related terms used in the analysis. It combines reward, feature, parameter, and distributional bounds through total variation and ergodicity arguments.

Term construction: The proof defines the temporal-difference-like quantity δ and expresses h(O, θ) as δ(O, θ)∇log πθ(a|s).This representation is used to compare h across policy parameters.
Lipschitz control: The function h is bounded and Lipschitz in θ after combining bounds on the reward discrepancy, features, and the stationary policy distribution.The argument uses total variation distance and Proposition 4.4 to control distributional changes.
Summary bounds: The proof summarizes ∇J(θ) as Gθ-bounded and LJ-Lipschitz, while the centered h term is 3Lh-Lipschitz and 2UδB-bounded.These properties are combined by the triangle inequality for the final bound.
Ergodicity: Ergodicity bounds the total-variation distance between the original and auxiliary tuples over the lag interval.The auxiliary-chain distribution is related to the stationary transition structure through the ergodicity assumption.