RobotGuide
Math foundations/Stochastic Approximation: Every Term in the Learning-Rate Formula

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.

about 55 min2 theorems4 proof steps4 self-test questions

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 ε.

E[en+1²] = (1−a_n)² E[e_n²] + 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.

  1. 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.
  2. 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).
  3. [object Object]
  4. 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).
Answer

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 hereThe counterpart in RLUsed in
Robbins-Monro conditionsThe legitimacy of TD/Q-learning rate schedules (1/n-type qualifies, constant-type only reaches a neighborhood)used in →
The fixed-step-size neighborhoodThe mathematical identity of loss that stops dropping and only jitters: steady-state variance aσ²/2used in →
Two time scalesFast critic, slow actor; slow target-network updatesused in →
Convergence premisesFull Q-learning convergence also requires infinitely many visits to every (s,a) pair — exploration turned into a theoremused 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.

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min