Foundations T22 / 27 · Stochastic Approximation
Stochastic Approximation: Every Term in the Learning-Rate Formula
Every condition for xn+1 = x_n + a_n(observation − x_n) to converge corresponds to a class of blow-up: a step size that never shrinks jitters forever; one that shrinks too slowly drags a noise tail. The two Robbins-Monro conditions are the final word on the learning rates of TD and Q-learning.
One-line takeaway
For a noisy iteration to converge to the true value, the step size must satisfy Σa_n=∞ (travel far enough) and Σa_n²<∞ (limited noise accumulation). A constant step size fails the second — it converges to a neighborhood of the truth and then jitters forever, with a steady-state variance a σ²/2 that can be computed exactly. This is the mathematical identity of loss that stops dropping and only jitters late in training.
Every update rule of TD(0), Q-learning, and actor-critic is a fill-in-the-blank exercise on this article's template. After this article, learning-rate schedules are no longer mysticism: which schedules truly converge, which jitter forever, and how much — all computable.
Why this tool exists
Start from the simplest case: estimate an unknown constant θ from observations that are θ plus noise. Naive averaging (the sample mean) certainly works, but it must store the whole history. Can we update in a stream, changing one number per arriving sample? xn+1 = x_n + a_n(observed x_n − x_n).
This form deserves a hard stare: it is the TD(0) update (replace θ with V(s), the observation with r+γV(s')), it is the SGD update (replace the observation with the gradient), and it is the skeleton of Q-learning. So the answer to when it converges transfers verbatim to all of these algorithms.
Intuition rehearsal: with fixed step size a, the update performs a random walk around the truth — the noise of a new observation is multiplied by a and injected, while the old error is decayed by a factor (1−a). Steady state is the balance of the two: injection a²σ² versus the decayed roughly 2a×variance, so the equilibrium variance ≈ aσ²/2. A step size that never reaches zero ⇒ noise keeps being injected ⇒ eternal jitter. This can be made rigorous, but first let the numbers speak (see the experiment).
Definitions
Definition 10.1 The Robbins-Monro problem
Find a root of an equation / the optimum of an objective, but you only get noisy observations: xn+1 = x_n − a_n·(the noisy version of the gradient information). Estimating a mean is the simplest special case: observation = θ + ε_n.
Why define it this wayEvery RL problem of the form update value/policy from samples can be written in this shape. It is the 1951 prototype of SGD.
Definition 10.2 Step-size conditions (Robbins-Monro 1951)
The step-size sequence {a_n} satisfies: (C1) Σ a_n = ∞; (C2) Σ a_n² < ∞. The classic example a_n = 1/n: C1 the harmonic series diverges ✓, C2 Σ1/n² = π²/6 converges ✓.
Why define it this wayC1 governs whether you can get there: a finite sum of step sizes may stop you midway. C2 governs whether you can settle once there: the injected noise variance is proportional to a_n², so only a finite second-order sum accumulates finite variance. You need both, and they pull in opposite directions — which is why an optimal schedule walks a tightrope between the two.
Theorems and proofs
Theorem 10.1 The Robbins-Monro convergence theorem (statement + heuristic argument)
With zero-mean noise, finite variance, and step sizes satisfying C1+C2, x_n converges almost surely to the true value θ*. With fixed step size a it converges to a neighborhood: the steady-state standard deviation of limsup |x_n−θ*| ≈ √(aσ²/2).
Proof
The full proof (Dvoretzky 1956) is out of bounds. Here is the skeleton of the decomposition argument: the error e_n = x_n − θ* satisfies the recursion en+1 = (1−a_n)e_n − a_n εn+1, i.e. deterministic decay × (1−a_n) plus noise injection −a_n ε.
Deterministic part: if Σa_n=∞, the product of decay factors Π(1−a_n)=0 — any initial error is ground away. Noise part: the steady-state equation v = (1−a)²v + a²σ² gives v = a²σ²/(2a−a²) ≈ aσ²/2 (for small a). With decreasing step sizes and Σa_n²<∞, the total injected noise variance is finite — the tail terms become arbitrarily small and the error tends to 0. ∎ (skeleton-level argument)
NoteHonest labeling: this is an argument at the level of making the numbers interpretable, not a full proof. The full version needs the ODE/supermartingale methods (Borkar's book). But note that this argument already yields the exact formula for the steady-state variance at fixed step size — it is correct, and it is tested below.
Theorem 10.2 Two time scales (statement)
Two coupled stochastic approximations run simultaneously: the fast variable uses step sizes a_n, the slow one b_n; if b_n/a_n → 0 (the slow one effectively freezes relative to the fast), then in the analysis the slow variable can be treated as a constant — the fast variable first converges to the equilibrium point parameterized by the slow variable, and the slow variable then moves along the equilibrium flow.
Proof
The proof (Borkar's ODE method) is out of bounds; statement and usage only.
NoteThe theoretical form of actor-critic: the critic uses a larger step size (fast tracking of V^π), the actor a much smaller one (treating the critic as quasi-exact). If both step sizes are of the same order, the actor improves a policy that has not finished being evaluated — the premise of the improvement theorem (T8) fails. This also explains why the target network must update slowly: it plays the role of the slow time scale.
Work it by hand
Estimate a mean with θ=3.7 and observation noise σ=1. With fixed step size a=0.05, what is the steady-state standard deviation? What change would halve it? Then use series to show why a_n=1/√n does not qualify.
- Steady-state variance formula (Theorem 10.1): v = aσ²/(2−a) ≈ aσ²/2 = 0.05×1/2 = 0.025 → steady-state standard deviation ≈ 0.158.
- Halving the variance requires halving a (0.025) — the fixed-step-size dilemma: denoising and speed conflict (large a converges fast but jitters; small a jitters less but barely moves).
- [object Object]
- The consequence of breaking C2: the injected noise variance Σa_n²σ² = ∞, no convergence — even though the step size really is shrinking. 1/n^0.4 shares the guilt (Σ1/n^0.8 diverges).
Steady-state standard deviation 0.158; halving it requires halving the step size (sacrificing speed); 1/√n does not qualify because Σa_n²=Σ1/n=∞. This series test is the only formula you need to memorize when writing learning-rate schedules: exponential decay and 1/n^p (p>1/2) qualify; 1/n^p (p≤1/2) does not.
Run the numbers
Where the numbers come from
Estimating θ=3.7 (noise σ=1), 60k steps, four step-size schedules (each reporting x@100 / x@1k / x@10k / x@60k):
- Fixed a=0.05: 3.484 / 3.559 / 3.883 / 3.823 — permanent jitter around the truth (theoretical steady-state sd 0.158)
- Fixed a=0.3: 4.075 / 3.939 / 4.241 / 3.808 — jittering much harder (steady-state sd √(0.15)≈0.39)
- a_n=1/n: 3.805 / 3.728 / 3.690 / 3.701 — true convergence (0.001 from the truth at 60k steps)
- a_n=1/n^0.4: 2.872 / 3.633 / 3.746 / 3.803 — fast early but residual noise late (Σa_n² diverges, C2 broken)
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Robbins-Monro conditions | The legitimacy of TD/Q-learning rate schedules (1/n-type qualifies, constant-type only reaches a neighborhood) | used in → |
| The fixed-step-size neighborhood | The mathematical identity of loss that stops dropping and only jitters: steady-state variance aσ²/2 | used in → |
| Two time scales | Fast critic, slow actor; slow target-network updates | used in → |
| Convergence premises | Full Q-learning convergence also requires infinitely many visits to every (s,a) pair — exploration turned into a theorem | used in → |
Boundaries: where this article stops
Where this article stops: the full proof of Dvoretzky's theorem, the ODE method, stochastic approximation under Markov noise (the transition kernel itself changes — exactly the real situation of TD; Borkar has results but the proofs are heavy) — none covered. Honest statement: the full convergence proofs of TD/Q-learning (Jaakkola-Tsitsiklis 1994, Tsitsiklis-Van Roy 1997) = this article + Markov chain theory (T6) stacked; the function-approximation version in deep RL still has no general convergence guarantee (the deadly triad, /fund/approx/).
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01What does each Robbins-Monro condition govern? Give one schedule that violates C2.
C1 (Σa_n=∞) governs whether you can get there — a finite total step size may stop you midway; C2 (Σa_n²<∞) governs whether noise accumulates — the injected variance is proportional to a_n². Examples violating C2: a_n=1/√n (Σ1/n=∞) or 1/n^0.4. In the experiment the latter still carries O(0.1) noise after 60k steps.
02What is the phenomenon of loss that stops dropping and only jitters late in fixed-step-size training? How big is the jitter?
The steady state of fixed-step-size stochastic approximation: it converges to a neighborhood of the truth and then jitters forever, with steady-state variance ≈ aσ²/2. For a=0.05, σ=1, sd≈0.158. This is not a bug and not a learning rate that is too large — it is the mathematical nature of a fixed step size. True convergence requires a decreasing schedule.
03Why must the target network update slowly? Answer with two time scales.
The two-time-scale theorem: only when the slow variable (target/actor) freezes relative to the fast one (online net/critic) does the convergence analysis of the fast variable hold. If the target updates at the same speed, the regression target itself drifts — you are chasing a moving target, and chasing causes oscillation (the third element of the deadly triad is related to this).
04TD(0) with a constant learning rate 0.01: does it theoretically converge to V^π?
Not to the exact value; it converges to a neighborhood of V^π (of order aσ²/2, where σ² is the variance of the TD error). In the tabular setting, exact convergence uses a 1/n-type schedule (per state-action pair visit counts); in deep RL, people accept neighborhood solutions — this is the theoretical origin of late-training curves that jitter, and that is normal.