JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Why the classics converge: contraction and stochastic approximation

The two pillars that make value iteration and Q-learning provably reach the right answer — a fixed point you contract toward, and noisy averaging that quietly converges.

The Bellman operator shrinks distances

Recall the Bellman optimality backup: take a value estimate, apply one step of look-ahead, and you get a new estimate. The key fact is that this map is a γ-contraction in the max-norm: if two value functions differ by at most d somewhere, after one backup they differ by at most γ·d. Errors shrink by a factor of γ < 1 every iteration.

(\mathcal{T}Q)(s,a) = \mathbb{E}_{s'}\!\left[\, r(s,a) + \gamma \max_{a'} Q(s',a') \,\right]

The Bellman optimality backup: one step of look-ahead. Because of the discount factor γ, this map is a γ-contraction.

A contraction has exactly one fixed point

The Banach fixed-point theorem says any contraction on a complete space has a unique fixed point, and iterating the map from any starting guess converges to it geometrically. For RL that fixed point is the optimal value function, and the satisfied equation is the Bellman optimality equation. This is the whole proof of value iteration in one breath: it is a contraction being iterated, so it must converge to the unique optimum.

Iterate a contraction from any starting guess and it converges to the same unique fixed point — here a Markov chain settling to its stationary distribution.

Interactive Markov chain whose state distribution converges to a single stationary distribution regardless of the starting state.

# Value iteration: contraction => geometric convergence
V = zeros(num_states)
for k in range(max_iters):
    V_new = bellman_optimality_backup(V)      # one application T*
    if max_norm(V_new - V) < (1 - gamma) * eps:
        break                                  # error now <= eps
    V = V_new
# ||V_k - V*||_inf <= gamma**k * ||V_0 - V*||_inf
Each sweep multiplies the error by γ; the stopping rule converts a small step into a true ε-bound.

Learning, not planning: noisy averaging

Value iteration needs the full model. Tabular Q-learning instead updates from single sampled transitions, so each backup is a noisy estimate of the true Bellman backup. To analyse it we leave pure contraction behind and pick up stochastic approximation: the theory of solving a fixed-point equation when you only observe unbiased-but-noisy values of the operator. Q-learning is exactly stochastic approximation applied to the Bellman optimality operator.

Tabular Q-learning on a gridworld: each step updates one cell from a single sampled transition — a noisy estimate of the Bellman backup.

Interactive gridworld where an agent learns Q-values cell by cell from sampled moves.

Step sizes that converge: Robbins–Monro

Noisy updates only settle if the step sizes are tuned just right. The Robbins–Monro conditions capture the balance: the step sizes must sum to infinity (so you can still move arbitrarily far and reach the answer) yet their squares must sum to a finite number (so the accumulated noise is eventually damped out). A schedule like αₜ = 1/t satisfies both; a constant step size satisfies the first but not the second, so it converges to a noisy neighbourhood rather than a point.

Q(s,a) \leftarrow Q(s,a) + \alpha_t \big[\, r + \gamma \max_{a'} Q(s',a') - Q(s,a) \,\big]

The Q-learning update: the step size αₜ weights the TD error. The Robbins–Monro conditions say exactly how αₜ must shrink for this to converge.

  1. Σ αₜ = ∞ — keep enough total motion to reach any target.
  2. Σ αₜ² < ∞ — make later steps shrink fast enough to average out noise.
  3. Every state-action pair must be visited infinitely often — exploration must not starve.

Putting it together — and where rates come from

With a contracting operator, Robbins–Monro step sizes, and infinitely-often visitation, Q-learning converges to the optimal action values with probability one. To go beyond 'it converges' to how fast, you bring in concentration bounds — inequalities (Hoeffding, Bernstein, Azuma) that say a sample average is close to its mean with high probability. They turn 'the noise washes out eventually' into an explicit sample complexity of the form Õ(SA·H³/ε²) per the dependence on states, actions, horizon, and accuracy.