Deterministic fixed points

On a complete metric space, a map satisfying d(Tx,Ty)≤c d(x,y)d(Tx,Ty)\leq c\,d(x,y) with 0≤c<10\leq c<1 has a unique fixed point. Banach’s theorem gives convergence of xk+1=Txkx_{k+1}=Tx_k and the bound d(xk,x∗)≤ckd(x0,x∗)d(x_k,x^*)\leq c^k d(x_0,x^*). Completeness and a strict contraction coefficient are substantive assumptions.

Finite discounted-MDP expectation and optimality operators are γ\gamma-contractions in the sup norm. This argument does not directly cover average-reward or general undiscounted problems. A projection associated with approximation may also change the norm and contraction properties.

Noisy root finding

A stochastic approximation has the form

xk+1=xk+αk(h(xk)+Mk+1),∑kαk=∞,∑kαk2<∞.x_{k+1}=x_k+\alpha_k\bigl(h(x_k)+M_{k+1}\bigr),\qquad \sum_k\alpha_k=\infty,\quad \sum_k\alpha_k^2<\infty.

Noise needs suitable martingale-difference or Markov-noise conditions and moment bounds. Step sizes alone do not establish convergence: bounded iterates, stability of the mean field, asynchronous visitation, and coverage must also be addressed. Constant step sizes normally retain fluctuations rather than giving exact asymptotic convergence.

Different mathematical roles

Concept Role Limit
Contraction Shrinks distances under iteration Does not fully analyze noisy updates
Banach theorem Existence, uniqueness, and deterministic iteration Does not establish neural optimization success
Robbins–Monro Finds roots through stochastic observations Requires noise, stability, and step-size assumptions
Dvoretzky-type results Control specific stochastic recursions Do not imply arbitrary nonlinear off-policy convergence

Applying the argument to RL

Tabular Q-learning needs visitation and step-size conditions for each state–action pair. Linear TD needs a stated sampling policy and norm; off-policy bootstrapping with approximation can destabilize ordinary TD. Two-timescale methods additionally require a separation between fast and slow recursions.

A stable learning curve is not a proof. A useful demonstration starts with exact value iteration, then introduces sample noise, a constant step size, or missing coverage to identify where each guarantee stops applying.

Related reading: Bellman errors and GTD2/TDC.

Selected references from the source notes