PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning

R. Srikant, Lei Ying

arXiv:1902.00923v3cs.LGstat.ML

TL;DR

The paper asks how to obtain finite-time error bounds for linear stochastic approximation and TD learning under Markovian noise, without i.i.d. samples or projection. It analyzes Lyapunov-function drift for constant-step-size recursions and finds Gaussian-type lower-order moment bounds, but potentially unbounded higher moments beyond a threshold.

  • Problem

    Finite-time error bounds were missing for TD learning with linear function approximation under Markovian noise without i.i.d. sampling or projection.

  • Method

    The paper studies a general linear stochastic approximation model through the drift of a Lyapunov function motivated by Stein’s method and linear ODE stability theory.

  • Results

    Lower-order moments of the squared 2-norm error are bounded by Gaussian moments, while higher moments beyond a threshold may be infinite in steady state.

  • Takeaways & Limitations

    The analysis yields finite-time moment bounds for TD algorithms with constant step size under Markovian noise, without a projection step or i.i.d. noise assumption.

  • Takeaways & Limitations

    The paper focuses on constant step sizes and does not discuss choosing step sizes to optimize convergence rates; it assumes a Hurwitz mean matrix.

Abstract

from arXiv · show

We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equilibrium point of an associated ordinary differential equation (ODE). We obtain finite-time bounds on the mean-square error in the case of constant step-size algorithms by considering the drift of an appropriately chosen Lyapunov function. The Lyapunov function can be interpreted either in terms of Stein's method to obtain bounds on steady-state performance or in terms of Lyapunov stability theory for linear ODEs. We also provide a comprehensive treatment of the moments of the square of the 2-norm of the approximation error. Our analysis yields the following results: (i) for a given step-size, we show that the lower-order moments can be made small as a function of the step-size and can be upper-bounded by the moments of a Gaussian random variable; (ii) we show that the higher-order moments beyond a threshold may be infinite in steady-state; and (iii) we characterize the number of samples needed for the finite-time bounds to be of the same order as the steady-state bounds. As a by-product of our analysis, we also solve the open problem of obtaining finite-time bounds for the performance of temporal difference learning algorithms with linear function approximation and a constant step-size, without requiring a projection step or an i.i.d. noise assumption.

1. Introduction

The paper develops finite-time analysis for linear stochastic approximation and applies it to TD learning with linear function approximation. Its approach handles Markovian noise without i.i.d. sampling or projection, while characterizing mean-square and higher-moment behavior.

  • The paper derives finite-time bounds on the distance between TD parameters and those minimizing the projected Bellman error.
  • Earlier TD convergence results established asymptotic convergence, while finite-time analyses assumed i.i.d. samples.
  • The analysis does not require i.i.d. noise or a projection step for constant-step-size algorithms with Markovian noise.
  • Finite-time bounds for linear stochastic approximation can be converted into bounds for TD algorithms because TD is a special case of that model.
  • Lower-order error moments can be bounded by Gaussian moments, whereas moments beyond a threshold may fail to exist in steady state.

2. Linear Stochastic Approximation with Markov Noise

The paper analyzes constant-step-size linear stochastic approximation with Markovian noise using Lyapunov drift, connecting finite-time behavior to the associated stable ODE. It derives mean-square and higher-moment bounds, including Gaussian-type lower-order bounds, possible divergence of sufficiently high steady-state moments, and sample-complexity implications.

  • Model and assumptions: The recursion uses a constant step size and Markovian state-dependent matrices and vectors, with the ODE equilibrium centered at zero under a Hurwitz mean matrix.The framework assumes bounded noise quantities, geometric mixing, and a Hurwitz matrix whose eigenvalues have strictly negative real parts.
  • Model and assumptions: Finite-time error is measured through E[||Θk||2n], the nth moment of the squared 2-norm deviation from equilibrium.This metric supports both mean-square analysis and higher-moment analysis.
  • Analysis approach: The main analysis studies one-step Lyapunov-function drift, with the chosen function also interpretable through Stein’s method and linear-ODE stability theory.For a Hurwitz matrix, the Stein equation and Lyapunov equation yield equivalent quadratic constructions.
  • Mean-square bounds: For k ≥ τ and κ1ǫτ + ǫγmax ≤ 0.05, Theorem 7 provides a finite-time mean-square bound whose convergence rate resembles that of the ODE when ǫ is small.The Markovian analysis includes a mixing-time transient τ that is absent from the corresponding ODE expression.
  • Sample complexity: If k ≥ τ + O(1/ǫ), the mean-square error becomes O(ǫτ), and related higher-moment bounds characterize when finite-time performance reaches steady-state order.The sufficient condition for steady-state moments through order n is only logarithmically different from the mean-square condition.
  • Higher-moment bounds: For lower orders, moments of ||Θk||2 are bounded by corresponding Gaussian moments, whereas sufficiently high steady-state moments can be infinite and the error lacks exponentially decaying tails.The higher-moment result holds for n = O(1/ǫτ), while beyond a threshold moments may fail to exist.

3. TD Learning

The paper applies its Markov-noise linear stochastic approximation framework to TD(0) and TD(λ) with linear function approximation. The resulting finite-time bounds rely on Markov-chain assumptions and apply without i.i.d. samples or projection, under conditions including full-rank features and bounded quantities.

  • TD(0): TD(0) estimates a policy’s value function from a Markov-chain trace using a linear approximation with d features, typically d << N.The state space has size N, while the parameter vector has dimension d.
  • TD(0): The TD(0) update is analyzed with a constant step size ǫ and can be written as a special case of linear stochastic approximation.This permits the general finite-time theorem to be applied to TD(0).
  • TD(0): For diminishing step sizes, TD(0) tracks an ODE and converges to its unique equilibrium point θ∗ when Φ is full rank.The equilibrium is then centered at zero to match the general stochastic approximation form.
  • TD(0): Finite-time bounds for TD(0) apply when the feature matrix Φ is full rank and feature and reward bounds φmax and cmax are finite.Under these conditions, the relevant Markov chain is geometrically mixing and the stated assumptions hold.
  • TD(λ): TD(λ) replaces the current-state feature direction with an eligibility trace, yielding a Markov-chain formulation whose state space is uncountable.After centering its equilibrium, the TD(λ) update has the general stochastic approximation form.

4. Conclusions

The paper establishes finite-time TD bounds for constant-step-size linear function approximation under Markovian noise without i.i.d. assumptions or projection. It also characterizes moment behavior, including Gaussian-type lower-order bounds and unbounded higher steady-state moments.

  • Conclusions: The paper obtains finite-time performance bounds for TD with linear function approximation and constant step size without i.i.d. noise assumptions or a projection step.The approach analyzes a general linear stochastic approximation model using a Lyapunov function motivated by Stein’s method.
  • Conclusions: Moments up to a certain order of the squared 2-norm approximation error can be upper-bounded by moments of a Gaussian random variable.Beyond a certain order, higher moments become unbounded in steady state.
  • Conclusions: The framework also extends to finite-time moment bounds for time-varying step sizes.

Appendix A. Proof of Lemma 3

The appendix proof recursively propagates bounds across iterations and controls the resulting expressions using monotonicity, elementary inequalities, and a small-step-size condition.

  • Appendix A. Proof of Lemma 3: The proof recursively applies an inequality to bound terms involving the initial parameter and the step-size-dependent quantities.The resulting bound includes terms proportional to ǫτ∥Θ0∥ and ǫτbmax.
  • Appendix A. Proof of Lemma 3: The proof uses that the relevant function is increasing in k to obtain a bound uniformly for 1 ≤ k ≤ τ.
  • Appendix A. Proof of Lemma 3: For small x, the proof bounds the derivative of (1 + x)^τ using log(1 + x) ≤ x and an exponential inequality.The argument invokes the condition ǫτ ≤ 1/4 to apply the bound.
  • Appendix A. Proof of Lemma 3: The proof combines the intermediate bounds and controls squared sums with (a + b)^2 ≤ 2a^2 + 2b^2.

Appendix C. Proof of Lemma 5

The proof of Lemma 5 decomposes the target expression into terms and bounds them using Markov-chain mixing, auxiliary lemmas, and elementary norm inequalities.

  • Appendix C. Proof of Lemma 5: The proof first specializes to the case k = τ, noting that the general case is essentially identical.
  • Appendix C. Proof of Lemma 5: It separately analyzes the terms in the decomposition and invokes the mixing-time assumption for one of the bounds.
  • Appendix C. Proof of Lemma 5: The remaining bounds use Lemma 3, followed by combination of inequalities (23)–(26).
  • Appendix C. Proof of Lemma 5: The final simplifications use 2∥Θ0∥ ≤ 1 + ∥Θ0∥^2, the triangle inequality, Lemma 3, and ǫτ ≤ 1/4.

Appendix D. Proof of Theorem 9

The proof of Theorem 9 uses induction and a Lyapunov-function drift analysis under Markovian mixing assumptions. It derives finite-time moment bounds by controlling the terms arising from the Lyapunov expansion.

  • Proof setup: The proof proceeds by induction, shifting the analysis to a system starting at iteration k_{n−1}.The notation also assumes bmax ≥ 1 without loss of generality and uses a positive definite matrix factor S satisfying S⊤S = P.
  • Drift analysis: The Lyapunov function is differentiated and expanded using gradients, Hessians, Taylor’s theorem, and the Lyapunov equation.The resulting terms are analyzed separately, with inequalities and the mixing assumption used to control them.
  • Moment bounds: The analysis establishes finite-time bounds for the relevant moments after choosing a block length k = τ and applying the induction assumption.The bounds extend to k ≥ τ by conditioning on Θ_{k−τ}, and the resulting inequalities are transferred back to the original system.

Appendix E. Example showing that higher moments may not exist

This example constructs a scalar stochastic recursion whose steady-state higher moments can fail to exist. The contradiction argument shows that the 2n-th moment is absent when n grows faster than 1/ǫ.

  • Example construction: The example uses independent Bernoulli variables X_k taking values in {−1, 1} and defines state-dependent coefficients A(X_k) and b(X_k).The associated ODE is obtained from A(−1) = −2, b(−1) = −1, and A(1) = b(1) = 1.
  • Moment argument: The steady-state 2n-th moment is analyzed by applying Taylor’s theorem to the stochastic recursion and conditioning on the sign of Θ_0.Independence of X_0 and Θ_0 permits separate consideration of positive and negative initial states.
  • Conclusion: When n = ω(1/ǫ), the contradiction proves that the 2n-th steady-state moment does not exist.

Appendix F. Diminishing Step Sizes

The diminishing-step-size analysis studies a stochastic recursion under a nonincreasing step-size sequence satisfying delayed-step conditions. It reuses drift analysis and modified lemmas to derive recursive finite-time bounds.

  • Assumptions: The step-size sequence is nonincreasing and must satisfy conditions involving k∗, κ_s, and k − τǫ_k for sufficiently large k.These assumptions ensure the delayed index used in the analysis is nonnegative.
  • Proof strategy: The proof applies drift analysis with the same Lyapunov function and establishes modified versions of earlier lemmas for diminishing step sizes.Lemma 13 replaces τ with τǫ_k and ǫ with ǫ_l, where l = k − τǫ_k.
  • Result: For k ≥ ˆk, the preceding lemmas are combined and recursively applied to obtain the theorem’s finite-time inequality.The recursion holds for every k satisfying the theorem’s assumptions.

Appendix G. Negative Definite ¯A

When the mean matrix ¯A is negative definite, the analysis can use the simpler quadratic Lyapunov function V(Θ_k) = ∥Θ_k∥2. This yields finite-time bounds under a stated step-size condition.

  • Lyapunov choice: Negative definiteness of ¯A permits using V(Θ_k) = ∥Θ_k∥2 instead of the more general Lyapunov construction.The argument applies for constant step size and k ≥ τ.
  • Bound construction: With P = I, Lemmas 4 and 5 bound the second and third terms in the drift expansion.Under this choice, γ_min = γ_max = 1.
  • Result: If k ≥ τ and κ_1ǫτ + ǫγ_max ≤ 0.05, Corollary 1 provides a finite-time bound.
Loading 1902.00923v3…