PaperlayerView exact revision on arXiv

Source-linked AI summary

A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation

Jalaj Bhandari, Daniel Russo, Raghav Singal

arXiv:1806.02450v2cs.LGstat.ML

TL;DR

The paper addresses limited statistical-efficiency guarantees for temporal difference learning despite established asymptotic convergence results. It develops explicit finite-time analyses using gradient-descent-like insights and extends them to Markov-chain data, TD(λ), and Q-learning for high-dimensional optimal stopping.

  • Problem

    Despite asymptotic convergence guarantees, the statistical efficiency of temporal difference learning, including its data requirements, remained an important open problem.

  • Method

    The analysis interprets TD through projected Bellman fixed points, develops mean-path dynamics, and mirrors stochastic-gradient-descent techniques, using projection for Markov-chain observations.

  • Results

    The paper provides explicit finite-time bounds for TD, including single-trajectory Markov-chain data, and extends the analysis to TD(λ) and Q-learning for high-dimensional optimal stopping.

  • Takeaways & Limitations

    Finite-time analysis of TD can retain the simplicity of SGD analysis while covering eligibility traces and Q-function approximation in optimal stopping problems.

  • Takeaways & Limitations

    The Markov-chain analysis uses a projection step, and the ˜O(1/T) rate depends on the minimum eigenvalue of the feature covariance matrix.

Abstract

from arXiv · show

Temporal difference learning (TD) is a simple iterative algorithm used to estimate the value function corresponding to a given policy in a Markov decision process. Although TD is one of the most widely used algorithms in reinforcement learning, its theoretical analysis has proved challenging and few guarantees on its statistical efficiency are available. In this work, we provide a simple and explicit finite time analysis of temporal difference learning with linear function approximation. Except for a few key insights, our analysis mirrors standard techniques for analyzing stochastic gradient descent algorithms, and therefore inherits the simplicity and elegance of that literature. Final sections of the paper show how all of our main results extend to the study of TD learning with eligibility traces, known as TD($λ$), and to Q-learning applied in high-dimensional optimal stopping problems.

1 Introduction

The paper addresses the gap between known asymptotic convergence guarantees for TD and limited understanding of its statistical efficiency. It develops simple finite-time analyses that connect TD with stochastic gradient descent and extend to Markovian data, TD(λ), and Q-learning.

  • TD is widely used, but its statistical efficiency remains poorly understood despite established asymptotic convergence conditions.
  • Links with gradient descent: The analysis connects expected TD updates with gradient-descent properties, enabling simple convergence bounds that mirror stochastic gradient descent analyses.
  • Non-asymptotic treatment with Markovian noise: Markovian observations create biased, dependent updates, so the paper controls this bias and obtains bounds scaled by the chain’s mixing time.
  • An extendable approach: The approach extends to TD(λ) and Q-learning with function approximation for high-dimensional optimal stopping problems.

2 Problem formulation

The paper formulates on-policy value estimation in a Markov reward process and uses linear features to approximate value functions in large state spaces. It assumes bounded rewards, ergodicity, normalized full-rank features, and a finite state space for presentation.

  • The objective is to estimate a fixed policy’s value function from observed rewards and state transitions in an on-policy Markov reward process.
  • The formulation assumes bounded rewards and an ergodic process with a unique stationary distribution, ensuring a well-defined value function.
  • Value function approximation: A linear approximator represents each state’s value using a shared parameter vector and fixed feature vectors.
  • Feature regularity: Features are normalized and nonredundant, making the feature covariance matrix full rank with minimum eigenvalue ω > 0.
  • Feature regularity: Some finite-time bounds are independent of the conditioning of the feature covariance matrix, despite the full-rank assumption.

3 Temporal difference learning

TD(0) updates a linear value-function estimate online from the latest transition by moving predictions toward a sample Bellman target. The paper also tracks averaged iterates and analyzes the expected update dynamics.

  • Each transition defines a squared sample Bellman-error loss, whose negative gradient determines the parameter update with step-size α_t.
  • The algorithm can maintain an averaged parameter iterate, denoted by ¯θ_t, alongside the current iterate.
  • TD(0) processes each observed transition online and makes an incremental gradient-like update using only recent data.
  • Unlike ordinary stochastic gradients, TD’s update target depends on the current value estimate, creating a circular convergence question.
  • The long-run behavior is analyzed through the expected negative gradient step under stationary transition sampling.

4 Asymptotic convergence of temporal difference learning

Classical TD convergence is understood by viewing the algorithm as stochastic approximation to a projected Bellman fixed point. Bellman contraction establishes stability, while the ODE method proves asymptotic convergence but leaves finite-time effects less explicit.

  • TD’s update is not a gradient of any fixed objective, so convergence is analyzed through the projected Bellman equation instead.
  • Understanding the TD limit point: The TD limit point is the unique solution associated with the projected Bellman equation under the feature span.
  • Understanding the TD limit point: The projected Bellman operator is a contraction with modulus γ in the D-norm, supporting convergence to an approximate value function.
  • When the true value function lies in the feature span, TD has no approximation error at its limiting value function.
  • Asymptotic convergence via the ODE method: The ODE method establishes asymptotic convergence under appropriate conditions and Robbins–Monro step sizes, but obscures step-size, conditioning, and mixing-time effects.

5 Outline of analysis

The analysis develops finite-time bounds for TD by progressively extending mean-path insights from deterministic dynamics to independent and Markovian noise, then to TD(λ) and Q-learning. The bounds expose tradeoffs between conditioning, averaging, and dependence on mixing time.

  • Finite-time bounds: The paper first derives iterate-distance bounds showing constant step-sizes converge exponentially to a neighborhood of θ∗, while decaying step-sizes yield O(1/T) rates.These bounds depend on feature-covariance conditioning, and value-prediction error is bounded through distance to the TD fixed point.
  • Finite-time bounds: Iterate averaging gives slower O(1/T) convergence rates whose bounds and step-sizes are independent of feature-covariance conditioning.This guarantee measures the mean-squared prediction gap between the averaged iterate and the TD limit point.
  • Analysis progression: The analysis proceeds from deterministic mean-path TD to TD with i.i.d. observations and then to a single ergodic Markov sample path.Under Markov noise, projection ensures bounded iterates and the results scale by a factor of the mixing time relative to the i.i.d. case.
  • Extensions: The same framework extends under Markov noise to TD(λ), where eligibility traces introduce a more complex analysis and tradeoffs in choosing λ.The paper also applies the framework without modification to Q-learning for a class of high-dimensional optimal stopping problems.

6 Analysis of mean-path TD

Mean-path TD is analyzed as an Euler discretization whose expected updates share key descent properties with gradient descent on a quadratic loss. These properties yield finite-time convergence bounds, with rates shaped by the discount factor and feature covariance.

  • Mean-path TD: Mean-path TD is the Euler discretization of the ODE ˙θ_t = ¯g(θ_t), providing a deterministic model whose dynamics guide the noisy analyses.The paper develops insights into this recursion before extending them to settings with observation noise.
  • Finite-time rates: Fast geometric convergence is meaningful only when the feature covariance matrix is well conditioned, because the rate degrades as ω approaches zero.Here ω denotes the minimum eigenvalue of Σ.
  • Key properties: Expected TD updates mirror gradient-descent properties: they point toward θ∗, and their norm is bounded using the feature covariance matrix.These properties allow the analysis to use a recursion for ∥θ_t − θ∗∥² in which the descent term controls the second-order term.
  • Key properties: (1 − γ)∥V_θ∗ − V_θ∥²_D lower-bounds the alignment between the parameter error and the expected TD update.The bound follows from the correlation structure of successive value-prediction errors under stationarity.
  • Finite-time rates: The resulting mean-path convergence rates mirror gradient-descent bounds but include an additional dependence on the discount factor γ.When the minimum eigenvalue ω of Σ is not too small, geometric convergence dominates; an averaged iterate instead gives O(1/T) convergence independent of conditioning.

7 Analysis for the i.i.d. observation model

Under i.i.d. sampling from the stationary distribution, TD admits explicit finite-time guarantees that parallel standard SGD bounds. The rates vary with step-size and feature-covariance conditioning, with averaging enabling a conditioning-independent bound.

  • Observation model: The i.i.d. model samples TD tuples independently from the stationary distribution of the Markov reward process.The current iterate is therefore independent of the tuple driving its update.
  • Proof strategy: The unified analysis combines TD-specific properties with standard stochastic-gradient arguments and depends on σ2, the variance of TD updates at the stationary point.The resulting proofs mirror finite-time SGD analyses.
  • Finite-time guarantees: The averaged-iterate guarantee has a comparatively slow O(1/T) rate but is independent of the conditioning of the feature covariance matrix.This bound applies with iterate averaging and relatively large step-sizes.
  • Finite-time guarantees: O(1/T) convergence is obtained for a decaying step-size sequence, while the bound depends on the minimum eigenvalue ω of the feature covariance matrix.This is the faster rate available when the feature covariance matrix is well conditioned.
  • Finite-time guarantees: With a constant step-size, TD does not converge exactly to the fixed point, but sufficiently small step-sizes yield exponential convergence to within a limiting radius.The limiting error is controlled by gradient noise.

8 Analysis for the Markov chain observation model: Projected TD algorithm

For a single Markovian trajectory, dependent observations break the i.i.d. martingale structure and couple iterates with current updates. The paper addresses this using projected TD, information-theoretic control of the coupling, and mixing assumptions, obtaining finite-time bounds with mixing-time and conditioning dependencies.

  • Markovian dependence: Single-trajectory TD uses consecutive tuples from one Markov chain, whose dependence creates the main statistical challenge absent from the i.i.d. model.The conditional expected update at the current iterate need not equal the mean update because the iterate depends on past tuples.
  • Projected TD: Projected TD constrains iterates to a finite-radius Euclidean norm ball, ensuring uniformly bounded gradient norms needed to control gradient bias.The projection is used as an analytical regularity device and involves rescaling when an iterate exceeds the radius.
  • Assumptions: The analysis assumes uniform geometric mixing and starts the chain in its stationary distribution to simplify the bounds.The steady-state initialization is not essential under the mixing assumption, but it simplifies mathematical expressions.
  • Projected TD: The gradient norm satisfies ∥gt(θt)∥2 ≤ rmax + 2R under projected TD with projection radius R.This bound follows from bounded rewards, normalized features, and bounded iterates.
  • Finite-time bounds: The slow ˜O(1/T) bound is independent of covariance conditioning, whereas the faster rate depends on the minimum eigenvalue ω of Σ.For sufficiently small constant step-sizes, the iterates converge exponentially to within a radius of the TD fixed point.
  • Finite-time bounds: The Markovian bounds include mixing-time dependence, reflecting that roughly τmix observations provide information comparable to one independent stationary sample.Projected i.i.d. specialization would remove mixing-time terms and replace σ2 with the uniform gradient bound G2.

9 Extension to TD with eligibility traces

The paper extends finite-time analysis to TD(λ), whose eligibility traces can improve performance but complicate dependencies. The resulting bounds expose a trade-off: TD(λ) can have a better limiting error guarantee, while TD(0) has faster bounded convergence under constant step-sizes.

  • Algorithmic extension: TD(λ), parameterized by λ ∈ [0, 1], includes TD(0) as a special case and maintains an eligibility trace for past states.The trace is a geometrically weighted average of feature vectors from previously visited states.
  • Algorithmic extension: Eligibility traces redirect updates from the current feature vector to a trace vector, making analysis more difficult because of additional dependencies.The update uses the TD error multiplied by z0:t rather than the current-state feature vector.
  • Limiting behavior: The limiting TD(λ) fixed point has contraction factor κ < γ, and κ → 0 as λ → 1, improving its error guarantee toward the projected value function.The projected value function minimizes mean-square prediction error among representable value functions.
  • Finite-time bounds: The analysis establishes three finite-time bounds for projected TD(λ), including a robust ˜O(1/T) rate under an aggressive step-size.Other bounds include exponential convergence within a radius and an improved ˜O(1/T) dependence requiring knowledge of the minimum eigenvalue ω.
  • Finite-time bounds: For decaying step-sizes, the TD(λ) and TD(0) bounds are qualitatively the same.The dominant terms in the corresponding bounds are equal.
  • Finite-time bounds: For constant step-sizes, the bounds establish faster convergence for TD(0) than TD(λ), so TD(λ) requires more data to approach its limit point.The larger update-direction bound B caused by eligibility traces dominates the benefit of the smaller contraction factor κ in these bounds.

10 Extension: Q-learning for high dimensional Optimal Stopping

The paper extends its finite-time analysis to Q-learning with linear function approximation for high-dimensional optimal stopping problems. The extension relies on the same contraction and update properties used for TD(0), yielding the same convergence bounds in this setting.

  • Finite-time analysis: The paper applies its TD(0) techniques without modification to obtain finite-time Q-learning bounds for high-dimensional optimal stopping problems.The extension uses the same key lemmas, including descent-direction and noise-control properties.
  • Problem setting: Optimal stopping chooses when to terminate a process to maximize cumulative expected discounted rewards.The setting includes applications such as financial-derivative pricing.
  • Problem setting: Exact dynamic programming is practical only for small state spaces, motivating feature-based linear approximation of the optimal continuation-value function.The approximation represents values using fixed state features and a shared parameter vector.
  • Q-learning method: Q-learning forms a sampled Bellman target from continuation and termination rewards, then updates parameters by a gradient step on prediction error.Data are generated by an exploratory policy that always continues.
  • Convergence properties: The analyzed Q-learning variant converges asymptotically to the unique solution of a projected Bellman equation because the projected Bellman operator is a γ-contraction.The limiting error is bounded by the representational power of the linear approximation architecture.
  • Convergence properties: If the optimal Q-function is representable by the features, the approximation error vanishes and the algorithm converges to the optimal Q-function.The resulting stopping-policy error also depends on the feature representation.

11 Conclusions

The paper provides explicit finite-time guarantees for TD, including the challenging single-trajectory Markov-chain setting. Its SGD connection supports extensions to TD(λ) and Q-function approximation for optimal stopping.

  • Conclusions: The paper addresses the open problem of characterizing TD’s data efficiency despite prior asymptotic convergence guarantees.The contribution is a finite-time analysis of a foundational reinforcement-learning algorithm.
  • Conclusions: The analysis gives explicit finite-time bounds for TD when data come from a single trajectory of a Markov chain.The authors emphasize that this setting is substantially more complicated than simpler sampling models.
  • Conclusions: The approach retains the simplicity of stochastic-gradient-descent analysis while extending to TD(λ) and Q-function approximation for optimal stopping.These extensions are presented as applying gracefully across TD variants.
  • Open directions: The authors identify projection removal and problem-independent robust step-sizes as directions for future work.The current analysis uses projection for tractability, while its ˜O(1/T) step-size depends on the minimum covariance eigenvalue.

A.1 Restatement of the theorem and key lemmas from the main text

The appendix restates the projected TD and TD(λ) convergence frameworks and details the lemmas controlling progress, gradient or update bias, and Markovian noise. It also explains how eligibility-trace updates fit the same contraction-based proof strategy.

  • TD theorem: The projected TD theorem assumes R ≥ ∥θ∗∥2 and a Markov-chain observation model, with G = rmax + 2R controlling the update scale.The theorem is stated under the paper’s standing mixing assumption.
  • Proof ingredients: The proof uses descent toward θ∗ together with a bound on gradient bias caused by Markovian observations.The bias lemma applies to non-increasing step-size sequences and uses a mixing-time delay.
  • TD rates: The constant-step-size proof obtains geometric convergence by iterating a contraction inequality.The argument uses α0 < 1/(2ω(1 − γ)) and bounds the resulting geometric series.
  • TD rates: The decaying-step-size analysis yields a ˜O(1/T) bound and an O(log T/T) rate for the final iterate θT.The latter follows from the same displayed convergence relation used for the theorem.
  • TD(λ) proof strategy: For TD(λ), the update direction xt(θ, z0:t) and its stationary mean play roles analogous to TD(0)’s stochastic gradient and expected gradient.The proof controls observation noise by comparing the sampled update with its steady-state mean.
  • TD(λ) proof strategy: The TD(λ) analysis uses a stationary backward-view process with an infinite eligibility trace, introduced only for analysis and not by the algorithm.This construction makes the update sequence stationary and preserves its mean update direction.
  • TD(λ) theorem: The TD(λ) theorem assumes R ≥ ∥θ∗∥2 and uses κ in the step-size restriction, reflecting the contraction structure of the eligibility-trace operator.The stated restriction is αt = α0 < 1/(2ω(1 − κ)).

B.1 Proof strategy and key lemmas

The proof analyzes Projected TD(λ) through an error decomposition, then bounds the bias caused by Markovian dependence and eligibility traces. Combining these ingredients yields finite-time convergence results under different step-size schedules.

  • Proof strategy: The analysis decomposes the projected TD(λ) error into descent, update-noise, and bias terms.The resulting recursion holds for each sample path and uses non-expansiveness of projection.
  • Bias control: The main technical challenge is bounding the bias induced by coupled Markov transitions and history-dependent eligibility traces.The proof controls this bias using regularity, truncation, and independence arguments over a mixing-time window.
  • Bias control: The bias scales update-direction noise according to the Markov-chain mixing time and the eligibility-trace weighting.For constant step-size α, the analysis gives E[αζt(θt, z0:t)] ≈ B^2(6 + 12τmix λ(α))α^2.
  • Key lemmas: The expected-update direction contracts toward the TD(λ) limit through the projected Bellman operator.The proof uses that the operator is a contraction in the D-norm and has a unique fixed point.
  • Convergence bounds: Lemmas controlling update norms, contraction, regularity, and bias are combined to establish finite-time bounds for non-increasing step sizes.The proof treats constant and decaying step-size cases separately.
  • Bias control: Eligibility-trace truncation introduces an error that decays geometrically with the truncation horizon.The bound is proportional to B^2(γλ)^τ for finite traces and B^2(γλ)^t for the infinite-history comparison.

B.2 Proof of Theorem 4

Theorem 4 follows by combining the error recursion with the bias bound and solving it under constant or decaying step sizes. The resulting analysis also yields an iterate convergence rate for a decaying schedule.

  • Common recursion: Equation (47) provides the common recursion used to analyze different step-size choices.The proof starts from this recursion before specializing to constant or decaying schedules.
  • Constant step size: With a sufficiently small constant step size, the expected distance to the TD(λ) limit point converges exponentially to a step-size- and λ-dependent error level.The stated condition is α0 < 1/(2ω(1 −κ)).
  • Decaying step size: A decaying step size αt = 1/(ω(t + 1)(1 −κ)) yields a convergence rate of O(log T/T) for the iterate θT.The proof obtains this rate by summing the recursion and controlling the accumulated bias.
  • Technical bounds: The proof relies on uniformly bounded updates and Bellman-error terms within the projected parameter set.The projection keeps θt in ΘR, while normalized features support the update bounds.
  • Technical bounds: Eligibility-trace approximation errors are controlled by geometric decay in γλ, enabling finite-history bounds within the proof.For truncation horizon τ, the error is bounded by B^2(γλ)^τ.

C Proofs of Lemmas 13 and 16

The lemmas establish progress of expected updates toward the fixed point for TD(λ) and Q-function approximation. Their proof uses contraction of a projected operator in the D-norm.

  • Generalized progress lemma: The proof treats TD(λ) and Q-function approximation through a shared expected-update lemma.The general formulation replaces specific Bellman operators with a generic contraction operator.
  • Contraction argument: A contraction modulus γ bounds the projected operator’s deviation from its fixed point, establishing the descent relation used by the convergence proof.The fixed point is Φθ∗ in the projected value-function space.
  • Contraction argument: The expected update is related to the parameter error through the D-inner product after applying the feature projection.The derivation uses that projection preserves vectors in the feature span and is symmetric.
Loading 1806.02450v2…