Finite-Time Error Bounds for Biased Stochastic Approximation with Applications to Q-Learning

Gang Wang, Georgios B. GiannakisAISTATS 2020 · OpenReview

Abstract

Stochastic Approximation (SA) is a cornerstone of Reinforcement Learning (RL), yet providing finite-time convergence guarantees for practical algorithms like Q-learning remains a significant theoretical challenge. This paper introduces a novel analysis framework for biased SA procedures under Markovian noise. By employing a "multistep Lyapunov function" that averages progress over a look-ahead window, the authors derive the first finite-time mean-square error (MSE) bounds for unmodified Q-learning with linear function approximation. These bounds hold from any initial distribution and do not require the "burn-in" periods or algorithm modifications common in previous literature.

Introduction

Stochastic Approximation (SA) provides the mathematical foundation for many iterative optimization and reinforcement learning algorithms. While the asymptotic convergence of these methods—proving they work as time approaches infinity—is well-established, modern machine learning necessitates a more granular understanding. Specifically, researchers require "finite-time" analysis to determine the sample complexity: how many iterations are required to reach a target level of accuracy?

Analyzing RL algorithms like Q-learning in a finite-time regime is notoriously difficult due to three primary factors:

  1. Markovian Noise: Unlike standard optimization, RL data is typically collected along a trajectory, meaning samples are correlated rather than independent and identically distributed (i.i.d.).
  2. Gradient Bias: Q-learning updates are inherently biased because the target value depends on the current parameter estimate.
  3. Mixing Time Constraints: Many existing proofs only apply after a "burn-in" period (the mixing time of the underlying Markov chain), leaving the early, critical stages of learning uncharacterized.

The Multistep Lyapunov Framework

The core innovation of this work is the introduction of a multistep Lyapunov function. In classical stability analysis, a Lyapunov function acts as an "energy" metric that should decrease at every step as the algorithm approaches a solution. However, in the presence of biased updates and correlated Markovian noise, this energy can fluctuate significantly in the short term, making single-step analysis difficult.

The authors propose a function that "looks ahead" $T$ steps into the future. By analyzing the cumulative progress over this window, the framework effectively "cancels out" the gradient bias and the noise correlation by exploiting the ergodic properties of the Markov chain. This look-ahead strategy allows for a rigorous convergence proof for a broad class of biased, nonlinear SA procedures without requiring artificial modifications to the algorithm.

Finite-Time Bounds for Q-Learning

The authors apply this general framework to Q-learning with linear function approximation. This is a particularly challenging case because the "target" in the Bellman equation changes as the weights are updated, creating a moving target that complicates the bias.

Key Theoretical Results

  • Explicit MSE Formula: The paper derives an explicit bound for the Mean-Square Error (MSE) at any iteration $k$. The error is decomposed into a transient term (which decays exponentially) and a steady-state error term (proportional to the stepsize $\epsilon$).
  • No Burn-in Required: Unlike prior state-of-the-art results, these bounds are valid from $k=0$. The analysis does not require the Markov chain to reach a stationary distribution before the guarantees apply.
  • Unmodified Algorithms: Many theoretical guarantees require a "projection step"—manually constraining parameters to a bounded set—to ensure stability. This work provides bounds for the unmodified version of Q-learning used in practice.
  • Improved Dependency: For linear SA with Markovian noise, the steady-state error bound improves upon previous benchmarks (such as Srikant & Ying, 2019) by removing the restrictive dependency on the Markov chain's mixing time $\tau$.

Significance and Applications

While the primary application demonstrated is Q-learning, the underlying SA framework is highly general. It can be extended to other temporal difference (TD) learning variants, such as TD-learning or Gradient Temporal Difference (GTD) methods. By providing a path to analyze biased updates without i.i.d. assumptions, this work bridges the gap between theoretical stability and the practical realities of RL.

Limitations and Future Directions

Despite the breakthrough in handling Markovian noise and bias, several avenues for future research remain:

  • Nonlinear Approximation: The specific application to Q-learning assumes linear function approximation. Extending these tight finite-time bounds to deep neural networks (nonlinear approximation) remains an open challenge.
  • Constant Stepsize Focus: The results primarily address constant stepsizes. While this is common in practice, it results in a non-zero steady-state error. Future work may further explore the nuances of diminishing stepsize schedules within this multistep framework.
  • Parameter Sensitivity: The derived bounds involve constants related to the MDP's properties and the Lyapunov function. Calculating these exact constants for high-dimensional, complex environments remains difficult, which can limit the ability to predict exact iteration counts for specific real-world problems.

Conclusion

This paper provides a significant advancement in RL theory by introducing the multistep Lyapunov function. By moving beyond the limitations of single-step analysis and i.i.d. assumptions, the authors provide a more realistic and robust framework for understanding the finite-time behavior of biased stochastic approximation, offering the first comprehensive convergence guarantees for standard Q-learning under Markovian noise.

Summary updated

Abstract

Inspired by the widespread use of Q-learning algorithms in reinforcement learning (RL), this present paper studies a class of biased stochastic approximation (SA) procedures under an ‘ergodic-like’ assumption on the underlying stochastic noise sequence. Leveraging a \emph{multistep Lyapunov function} that looks ahead to several future updates to accommodate the gradient bias, we prove a general result on the convergence of the iterates, and use it to derive finite-time bounds on the mean-square error in the case of constant stepsizes. This novel viewpoint renders the finite-time analysis of \emph{biased SA} algorithms under a broad family of stochastic perturbations possible. For direct comparison with past works, we also demonstrate these bounds by applying them to Q-learning with linear function approximation, under the realistic Markov chain observation model. The resultant finite-time error bound for Q-learning is \emph{the first of its kind}, in the sense that it holds: i) for the unmodified version (i.e., without making any modifications to the updates), and ii), for Markov chains starting from any initial distribution, at least one of which has to be violated for existing results to be applicable.
BibTeX
@inproceedings{wang2020finite,
  author = {Gang Wang and Georgios B. Giannakis},
  title = {{Finite-Time Error Bounds for Biased Stochastic Approximation with Applications to Q-Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=dpB0AaVjY6},
}
Figure