On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence

1 Introduction

• Linear function approximation represents the value function as θᵀφ(s), with feature dimension d much smaller than the state-space size.This approximation allows efficient TD(0) implementation on large state spaces.Source: §1 · p. 1
• The authors report that their non-asymptotic analysis fills a gap beyond available asymptotic convergence and rate results for TD(0) with function approximation.They note that prior finite-time LSTD bounds relied on a fast-mixing assumption, whereas their rate results do not impose that assumption.Source: §1 · pp. 2–3
• Finite-time analysis must account for samples generated before the Markov chain reaches its stationary distribution, while tuning the classic 1/n step size requires transition-dynamics knowledge.The paper handles mixing error under a mixing assumption and uses iterate averaging to alleviate the step-size dependency.Source: §1 · p. 2
• The centered TD(0) variant incorporates a centering sequence and converges faster than regular TD(0) in expectation.The paper reports an exponential rate when the underlying Markov chain mixes fast.Source: §1 · p. 3
• With a carefully chosen step size, TD(0) achieves O(1/√n) convergence in high probability and expectation, but the choice depends on transition-dynamics information.The step-size condition uses the smallest eigenvalue μ, which depends on the MDP’s transition dynamics.Source: §1 · p. 3
• Iterate averaging removes the step-size dependency while retaining the optimal convergence rate in both high probability and expectation.The paper motivates averaging as a way to use larger step sizes without requiring knowledge of stationary-distribution properties.Source: §1 · pp. 2–3
• The bounds guide step-size choices that yield empirical convergence for TD(0), its averaged variant, and its centered variant in two synthetic setups.The experiments are described as illustrating the usefulness of the bounds.Source: §1 · p. 3

• The policy-evaluation objective is to estimate V π for a given stationary policy in a discounted-reward MDP.The value function satisfies the fixed-point relation V = T π(V), with β denoting the discount factor.Source: §2 · p. 4
• TD(0) performs stochastic fixed-point iteration to estimate the value function for a policy.The value function is characterized by a Bellman fixed point; the updates use step sizes satisfying standard stochastic approximation conditions.Source: §2 · p. 4
• Linear features approximate the value function with a d-dimensional parameterization, where d is much smaller than the number of states.This addresses the curse of dimensionality associated with high-dimensional state spaces.Source: §2 · p. 4

3.1 Assumptions

• The analysis assumes an ergodic policy-induced Markov chain with a stationary distribution, alongside bounded rewards and full-column-rank features.Source: §3.1 · p. 4
• It also imposes bounded features and combined step-size/mixing conditions, with a separate uniform-mixing-bound variant.Source: §3.1 · pp. 4–5

3.2 Non-averaged case

• The non-averaged analysis establishes an optimal convergence rate when its step-size constants satisfy eigenvalue-dependent conditions.The required choice of c depends on µ, which the authors note entails knowledge of the underlying transition dynamics.Source: §3.2 · p. 5

3.3 Iterate Averaging

• Choosing the iterate-averaging exponent α close to 1 approaches an O(1/√n) convergence rate, but makes the bounding constants grow.The step-size constant c also cannot be chosen too large or too small.Source: §3.3 · p. 6

4 TD(0) with Centering (CTD)

• CTD reduces update variance by adding a zero-mean centering term based on the difference between sampled increments and the fixed-point function.The centering term is intended to make updates small near θ∗, whereas regular TD(0) relies on a decaying step size to keep iterates close.Source: §4 · p. 7
• At each epoch’s start, CTD samples an iterate from the previous epoch and then uses a large constant step size during the epoch.The epoch scheme combines this choice with averaging to obtain the stated exponential rate.Source: §4 · p. 7

4.1 Finite time bound

• The finite-time result assumes (A1)–(A4) and (A6”), and requires an epoch length M for which C1 < 1.The stated mixing assumption (A6”) is weaker than the assumption used for regular TD(0), facilitated by projecting CTD iterates onto an H-ball.Source: §4.1 · p. 8
• CTD has an exponential convergence rate, unlike the sublinear O(n^-1/2) rate stated for TD(0) with or without averaging.For finite-state settings, the chain is geometrically ergodic; for chains that do not mix exponentially fast, the mixing term can dominate.Source: §4.1 · p. 8

5.1.1 High probability bound

• The high-probability proof writes the centered error as martingale differences and uses their Lipschitz dependence on bounded random innovations for concentration.The martingale differences are defined relative to the filtration generated by the Markov-chain states.Source: §5.1.1 · p. 9

5.1.2 Bound in expectation

• The expectation proof decomposes the update into stationary drift, mixing error, and a martingale-difference term before unrolling the recursion.The expectation bound is stated under (A1)–(A6) and a sufficiently small step size.Source: §5.1.2 · pp. 12–13

5.1.3 Derivation of rates

• The rate derivation applies the general-step-size bounds to a decaying step-size sequence and considers separate regimes for the high-probability bound.The supplied rate derivation specifies γ_n through c0, c, and n, and uses a condition involving µ(1−β)c0c.Source: §5.1.3 · p. 16

5.2 Iterate Averaging: Proof of Theorem 2

• The analyzed iterate is the arithmetic average of θ1 through θn, and the high-probability bound applies once the step size satisfies the stated threshold.The proposition assumes γ_n ≤ µ(1−β)/(2(1+β)^2) for n > n0.Source: §5.2 · p. 17

5.2.1 Derivation of rates: High Probability Bound in Theorem 2

• The high-probability rate derivation treats the first n0 steps separately before using the expectation bound for the later steps.The derivation also bounds the influence of the initial steps.Source: §5.2.1 · p. 18

5.2.2 Derivation of rates: Expectation bound in Theorem 2

• For the expectation bound, the proof separates iterations before n0 from those at or after n0, bounding the initial phase by unrolling TD(0) and the later phase using Theorem 1.The threshold n0 is determined by the specific step-size sequence.Source: §5.2.2 · p. 19

Step 2: Bounding the variance using the centering term

• The proof bounds update variance using the centering term, applying the inequality that centering a random variable does not increase its expected squared norm.It then bounds the second term in the centering error and substitutes the resulting estimates into the recursion.Source: §5.3 · pp. 20–21

Step 3: Analysis for a particular epoch

• The epoch analysis unrolls the recursion within an epoch and then combines the bounds across epochs.The proof labels these as the epoch-specific analysis and the across-epoch combination.Source: §5.3 · p. 22

Step 5: Controlling the error terms

• Projection onto the H-ball keeps iterates bounded, and the proof uses that constraint when controlling error terms.The error bound also uses the feature-norm bound ∥φ(s_n)∥2 ≤ 1.Source: §5.3 · pp. 20, 23

6 Numerical Experiments

• In the two-state example, averaged TD(0) performs on par with TD(0), without requiring the same transition-dependent step-size setting.TD(0)'s step-size guideline requires knowledge of the transition structure through µ.Source: §6 · p. 23, Figure 2 · p. 24
• CTD reaches a normalized value difference of about 0.03 in the two-state example, but is omitted from that panel because TD(0) converges rapidly.The authors say the effect of averaging across CTD epochs is clearer in the second example.Source: Figure 2 · p. 24, §6 · p. 25
• In the 100-state example, all three algorithms converge, with CTD showing the lowest variance.The setting uses random transitions, bounded random rewards, and three-dimensional random features.Source: Figure 2 · p. 24, §6 · p. 25

7 Conclusions

• The paper derives non-asymptotic TD(0) bounds in both high probability and expectation, addressing the absence of finite-time convergence-rate bounds.The conclusions describe asymptotic rate results as already available.Source: §7 · p. 25
• Iterate averaging yields the optimal O(1/√n) rate, while the classic step-size choice proportional to 1/n requires knowledge of stationary-distribution properties to attain it.Source: §7 · p. 25
• The proposed centered TD(0) variant has an exponential convergence rate, and the bounds guide step-size choices in two synthetic experiments.Source: §7 · p. 25