Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes

Dongyan Huo, Yudong Chen, Qiaomin Xie

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:

  1. Synthetic LSA: Randomly generated linear systems driven by an 8-state Markov chain.
  2. Reinforcement Learning: The classic "Problematic MDP" (from Koller & Parr, 2000), a known difficult benchmark for TD learning with linear function approximation.
  3. 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.
Figure 1: Dependency graphs of LSA. Left: i.i.d. data. Right: Markovian data.
  • 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

Abstract

We consider Linear Stochastic Approximation (LSA) with a constant stepsize and Markovian data. Viewing the joint process of the data and LSA iterate as a time-homogeneous Markov chain, we prove its convergence to a unique limiting and stationary distribution in Wasserstein distance and establish non-asymptotic, geometric convergence rates. Furthermore, we show that the bias vector of this limit admits an infinite series expansion with respect to the stepsize. Consequently, the bias is proportional to the stepsize up to higher order terms. This result stands in contrast with LSA under i.i.d. data, for which the bias vanishes. In the reversible chain setting, we provide a general characterization of the relationship between the bias and the mixing time of the Markovian data, establishing that they are roughly proportional to each other. While Polyak-Ruppert tail-averaging reduces the variance of the LSA iterates, it does not affect the bias. The above characterization allows us to show that the bias can be reduced using Richardson-Romberg extrapolation with $m\ge 2$ stepsizes, which eliminates the $m-1$ leading terms in the bias expansion. This extrapolation scheme leads to an exponentially smaller bias and an improved mean squared error, both in theory and empirically. Our results immediately apply to the Temporal Difference learning algorithm with linear function approximation, Markovian data, and constant stepsizes.
BibTeX
@inproceedings{huo2022bias,
  author = {Dongyan Huo and Yudong Chen and Qiaomin Xie},
  title = {{Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes}},
  booktitle = {SIGMETRICS (Abstracts)},
  year = {2022},
  url = {https://openreview.net/forum?id=dB6IIAFDxb},
}
Figure