Nonlinear two-timescale stochastic approximation reveals new bias behavior
Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation
Machine LearningArtificial Intelligence
Summary
When computers learn by adjusting two connected things at different speeds, some errors tend to stick around even when averaging over time. The authors analyzed these errors for complex systems influenced by certain random processes and found a new formula that explains the persistent bias. Their work helps better predict and reduce errors by considering how these two speeds relate, making learning methods like temporal-difference more accurate. They tested their ideas with examples and showed how to improve error correction in practice.
What this means in practice
- •For machine learning engineers: Improve algorithms that learn over two timescales by applying the new bias correction formulas for better accuracy and faster convergence.
- •For reinforcement learning developers: Enhance temporal-difference learning implementations by using the paper’s bounds on initialization error and extrapolation techniques to reduce bias during training.
Authors
A. Ch. Madhusudanarao, Rahul Singh
Abstract
Constant-step stochastic approximation generally has a nonzero stationary mean error that persists under time averaging. This paper studies that error for nonlinear two-timescale recursions driven by an exogenous finite-state Markov chain. Under stated smoothness assumptions and conditions on the stationary distribution, we derive a first-order bias expansion whose error bound remains uniform as the slow step size becomes much smaller than the fast step size. Fast-manifold coordinates keep the associated covariance equation regular in this limit. For fast step $η$ and slow step $\varepsilon$, the expansion reveals a mixed contribution $\varepsilon^2/η$ alongside terms linear in each step size. This dependence matters for bias reduction: along power-law step-size paths, the bias exponents need not be integers, so Richardson--Romberg extrapolation requires weights matched to the path. An exactly solvable nonlinear Markov example verifies the coefficients. We verify localization for temporal-difference learning and compare finite-run extrapolation at equal update budgets. For finite runs, we bound the initialization error of tail averages on both timescales under an additional coupling assumption. In the special case of additive independent noise, signed third-moment cancellation yields a sharper remainder.