Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes

Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, Karthikeyan ShanmugamNeurIPS 2020 · OpenReview

Introduction

Stochastic Approximation (SA) serves as the mathematical backbone for many Reinforcement Learning (RL) algorithms, allowing systems to iteratively solve fixed-point equations—like the Bellman equation—using only noisy samples. While we have long known that these algorithms eventually converge asymptotically, obtaining a "finite-sample analysis" (knowing exactly how many iterations are needed to reach a specific error bound) is notoriously difficult.

This paper introduces a novel framework for analyzing the finite-sample convergence of SA algorithms. By constructing a smooth Lyapunov function using "generalized Moreau envelopes," the authors provide the first-known convergence rates for the V-trace algorithm and achieve a highly efficient logarithmic dependence on state-space size for $L_\infty$-norm contractions.

The Challenge: Restrictive Assumptions in SA

Existing proofs for SA convergence typically rely on two restrictive assumptions:

  1. Bounded Noise: The noise in the system is uniformly bounded.
  2. Euclidean Contraction: The algorithm closes in on the solution in the standard Euclidean ($L_2$) norm.

In real-world RL, these assumptions often fail. Algorithms like Q-learning and V-trace contract in the $L_\infty$-norm (the maximum error across all states), and the noise often scales with the size of the current estimate (unbounded or "affine" noise). This paper bridges that gap, providing a rigorous recipe for finite-sample bounds under general norms and scaling noise.

Methodology: The Generalized Moreau Envelope

To prove convergence in optimization, researchers often use a "Lyapunov function"—a potential function that demonstrably decreases over time. For Euclidean spaces, the squared norm $\|x\|^2$ is a perfect, smooth Lyapunov function. However, for the $L_\infty$-norm, the squared norm is "pointy" and non-differentiable, making standard calculus-based analysis nearly impossible.

The authors overcome this by utilizing a technique from convex analysis called the Generalized Moreau Envelope.

  • Smoothing the Norm: They use an infimal convolution to create a smooth version of the squared norm. This effectively "rounds off the sharp corners" while remaining very close to the original function.
  • Negative Drift: They prove that the SA iterates exhibit a "negative drift" with respect to this smooth function. On average, each step demonstrably moves the algorithm closer to the fixed point.
  • Step-size Analysis: This framework is then applied to both constant and diminishing step-size regimes to derive explicit, finite-sample error bounds.

Key Insights and Results

The approach is general enough to recover existing state-of-the-art bounds for Q-learning while providing entirely new bounds for V-trace, a popular off-policy RL method used in large-scale systems like DeepMind’s IMPALA.

Comparison of convergence rates and dependencies across different SA algorithms.
  • Logarithmic Scaling: A massive breakthrough in this work is proving that for $L_\infty$ contractions, the error bound depends only on $\log(d)$, where $d$ is the number of states. Previous works often showed a polynomial dependence ($d^2$), which scales poorly for large problems. The authors also demonstrate that this $\log(d)$ dependence is "order-wise tight," meaning it is mathematically impossible to achieve a better dimensional dependence in this setting.
  • Handling "Affine" Noise: The framework successfully handles noise whose variance grows linearly with the size of the current estimate. This is a much more realistic model for RL than assuming noise is always small and bounded.
  • V-trace Convergence: The paper establishes the first finite-sample convergence rate for the V-trace algorithm. With properly chosen diminishing stepsizes, the error decreases at a rate of $O(1/k)$. For a constant stepsize $\epsilon$, the algorithm converges exponentially fast to a "noise ball" with a radius proportional to $\epsilon$.

Limitations and Future Work

While a significant theoretical step forward, the paper notes a few limitations:

  • Tabular Setting: The analysis primarily focuses on the tabular setting, where states and actions are stored in a discrete table. Extending this framework to function approximation (e.g., using Neural Networks to represent values) is a natural next step.
  • Bias in V-trace: The V-trace algorithm introduces a bias due to its truncation levels. While this paper analyzes the convergence to the truncated limit, choosing these parameters to optimally balance bias and variance in infinite state-action spaces remains an open challenge.
  • Synchronous Updates: The current analysis assumes synchronous updates, meaning all states are updated simultaneously. Because real-world RL often relies on asynchronous updates, further extensions of this Lyapunov approach will be necessary to cover those use cases.

Summary updated

Abstract

Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample error bounds while using different stepsizes. The idea is to construct a smooth Lyapunov function using the generalized Moreau envelope, and show that the iterates of SA have negative drift with respect to that Lyapunov function. Our result is applicable in Reinforcement Learning (RL). In particular, we use it to establish the first-known convergence rate of the V-trace algorithm for off-policy TD-learning [18]. Importantly, our construction results in only a logarithmic dependence of the convergence bound on the size of the state-space.
BibTeX
@inproceedings{chen2020finite,
  author = {Zaiwei Chen and Siva Theja Maguluri and Sanjay Shakkottai and Karthikeyan Shanmugam},
  title = {{Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=eGV22dD8lUI},
}
Figure