Linear Stochastic Approximation (LSA) is the engine behind many fundamental algorithms in machine learning and control, most notably Temporal Difference (TD) learning in reinforcement learning and Stochastic Gradient Descent (SGD) on quadratic objectives. While practitioners love using constant stepsizes for their rapid, exponential convergence, this speed usually comes at the cost of a persistent "steady-state" error.
This paper provides a rigorous mathematical look at why this error exists when data is correlated (Markovian) and, more importantly, how to get rid of it almost for free.
TL;DR
When using constant stepsizes with Markovian data, LSA iterates converge to a biased solution that standard averaging cannot fix. This paper characterizes this bias as an infinite series and demonstrates that Richardson-Romberg extrapolation can cancel out these bias terms, delivering fast convergence, low variance, and high accuracy simultaneously.
What Problem Does This Paper Address?
In the ideal world of i.i.d. (independent and identically distributed) data, LSA with a constant stepsize $\alpha$ fluctuates around the true solution. If you average these iterates (a technique called Polyak-Ruppert averaging), the fluctuations cancel out, and you converge to the correct answer.
However, in real-world applications like Reinforcement Learning, data is rarely independent; it comes from a trajectory, making it Markovian. The authors show that in this setting, LSA is fundamentally biased. Even if you average your results forever, you will be stuck with an error proportional to the stepsize $\alpha$. This creates a painful trade-off: use a small stepsize for accuracy but suffer slow convergence, or use a large stepsize for speed but accept a large bias.
Methods
The authors bridge the gap between stochastic approximation and Markov chain theory:
- Joint Markov Chain Perspective: They treat the pair of (data, iterate) as a single time-homogeneous Markov chain. Using Wasserstein distance, they prove this joint process converges geometrically to a unique stationary distribution.
- Bias Expansion: They derive a novel infinite series expansion for the asymptotic bias. They show that the bias isn't just a random error but a structured vector: $Bias = \alpha B^{(1)} + \alpha^2 B^{(2)} + \dots$
- Richardson-Romberg (RR) Extrapolation: To eliminate the bias, they propose running $m$ LSA processes in parallel on the same data stream, each with a different stepsize. By taking a specific linear combination of their averaged iterates, they can cancel out the first $m-1$ terms of the bias expansion.
Datasets
The authors validated their theory using three distinct numerical setups:
- Synthetic LSA: Randomly generated linear systems driven by an 8-state Markov chain.
- Reinforcement Learning: The classic "Problematic MDP" (from Koller & Parr, 2000), a known difficult benchmark for TD learning with linear function approximation.
- Markovian SGD: A least-squares regression task where the data covariates are generated via a Metropolis-Hastings sampler to ensure temporal correlation.
Key Insights and Ideas
- Correlation Causes Non-linearity: The "aha moment" is that Markovian data introduces an implicit non-linear dependence between iterates. As shown in the dependency graphs below, the correlation between data points ($x_k$) creates a complex web of influence that doesn't exist in the i.i.d. case, leading to the persistent bias.
- Bias is Proportional to Mixing Time: The authors prove that the bias magnitude is roughly proportional to the product of the stepsize and the mixing time of the data. If the data stream is highly correlated (slow mixing), the bias is much worse.
- Extrapolation is "Data-Free": Because the parallel LSA runs use the exact same data stream, the extrapolation method is highly data-efficient. It requires more computation (running $m$ updates instead of one), but in the age of parallel processing, this is often a negligible cost for a massive gain in accuracy.
Key Results
- Geometric Convergence: The paper establishes non-asymptotic, geometric convergence rates for the iterates to reach their stationary distribution, confirming that constant stepsizes are indeed much faster than diminishing ones.
- Orders of Magnitude Improvement: In the TD(0) experiments on the "Problematic MDP," using RR extrapolation with 6 stepsizes reduced the final mean squared error by three orders of magnitude compared to standard tail-averaging.
- Bias Cancellation: They empirically confirmed that the bias is indeed proportional to $\alpha$, and that the RR scheme successfully shifts the error from $O(\alpha)$ down to $O(\alpha^m)$.
Limitations and Future Work
- Uniform Ergodicity: The theoretical proofs rely on the assumption that the underlying Markov chain is "uniformly ergodic," which might not hold for all complex, continuous-state environments.
- Dimension Scaling: The authors suggest that future work should focus on tightening how the error bounds scale with the dimension of the parameter vector.
- Beyond Linear: The most exciting frontier is extending these bias-reduction techniques to non-linear stochastic approximation, which would directly impact deep reinforcement learning algorithms like DQN or PPO.
Summary updated