Zap Meets Momentum: Stochastic Approximation Algorithms with Optimal Convergence Rate

Adithya M. Devraj, Ana Busic, Sean P. Meyn

Abstract

Acceleration is an increasingly common theme in the stochastic optimization literature, notably through Nesterov's method and Polyak's momentum technique. This paper introduces two new algorithms for root-finding problems: PolSA (Polyak Stochastic Approximation), which utilizes a specially designed matrix momentum, and NeSA (Nesterov Stochastic Approximation), a simplified variant. Motivated by reinforcement learning (RL), where algorithms like TD- and Q-learning are framed as stochastic approximation (SA), we aim to achieve optimal asymptotic variance. While Stochastic Newton-Raphson (SNR) is the gold standard for optimality, its computational cost is often prohibitive. We demonstrate, both theoretically and empirically, that PolSA parameter estimates couple with those of the ideal SNR algorithm, providing a computationally efficient path to optimal performance.

Introduction

Stochastic Approximation (SA) serves as the mathematical foundation for modern Reinforcement Learning. Finding the "root" of a Bellman equation amidst noisy data is the central task of algorithms like Q-learning. Historically, practitioners have faced a trade-off:

  1. Standard SA: Computationally efficient but slow to converge.
  2. Stochastic Newton-Raphson (SNR): Mathematically optimal in terms of asymptotic variance but requires $O(d^3)$ matrix inversions per step.
  3. Polyak-Ruppert Averaging: Achieves optimal variance but often suffers from poor transient behavior.

This research introduces a "third way" through PolSA and NeSA, algorithms that achieve SNR-level performance with the computational simplicity of momentum-based methods.

Methods: Matrix Momentum

The primary innovation is the transition from scalar momentum to matrix momentum.

  • PolSA: Unlike traditional "Heavy-Ball" momentum that uses a single scalar, PolSA employs a matrix momentum term. By designing this matrix based on estimates of the system's Jacobian, the algorithm effectively "pre-conditions" updates, mimicking a Newton step without the $O(d^3)$ cost.
  • NeSA: A variant of Nesterov’s accelerated gradient method adapted for root-finding. It is computationally leaner than PolSA and particularly effective when updates are sparse, maintaining $O(d)$ complexity.

Theoretical Foundation: The Coupling Result

The core theoretical contribution is a coupling result. For linearized models with martingale noise, the error sequence of PolSA is proven to "couple" with the error sequence of the ideal SNR algorithm. In essence, PolSA eventually behaves identically to the most efficient algorithm known, but at a fraction of the computational cost.

Visual demonstration of PolSA trajectories coupling with the optimal SNR trajectory as the gain parameter $\zeta$ increases.

As shown in the figure above, as the gain parameter $\zeta$ increases, the PolSA trajectories (dashed lines) increasingly align with the SNR trajectory (solid orange line). This visual evidence confirms that PolSA successfully captures the optimal second-order dynamics through first-order-like updates.

Experimental Results

The algorithms were evaluated on various Markov Decision Processes (MDPs), ranging from simple 6-state models to larger shortest-path problems ($d=117$).

  • Optimal Variance: PolSA achieves the same optimal asymptotic covariance as SNR in linear settings.
  • Q-learning Success: In non-linear Q-learning experiments, PolSA and SNR produced nearly identical error distributions after $10^6$ iterations, significantly outperforming standard Watkins Q-learning.
  • Computational Efficiency: NeSA demonstrated dramatic speedups in "clock sampling" environments, reducing Bellman error much faster than traditional methods while remaining highly scalable.

Conclusion and Future Work

PolSA and NeSA bridge the gap between simple momentum and second-order optimization. By utilizing matrix momentum, these algorithms achieve optimal asymptotic variance without the heavy computational burden of matrix inversion. While current proofs focus on linearized models, empirical results in non-linear Q-learning are highly promising. Future research will focus on formal non-linear proofs and extending these matrix momentum techniques to Deep Reinforcement Learning (DQN).

Summary updated

Abstract

Acceleration is an increasingly common theme in the stochastic optimization literature. The two most common examples are Nesterov's method, and Polyak's momentum technique. In this paper two new algorithms are introduced for root finding problems: 1) PolSA is a root finding algorithm with specially designed matrix momentum, and 2) NeSA can be regarded as a variant of Nesterov's algorithm, or a simplification of PolSA. The PolSA algorithm is new even in the context of optimization (when cast as a root finding problem). The research surveyed in this paper is motivated by applications to reinforcement learning. It is well known that most variants of TD- and Q-learning may be cast as SA (stochastic approximation) algorithms, and the tools from general SA theory can be used to investigate convergence and bounds on convergence rate. In particular, the asymptotic variance is a common metric of performance for SA algorithms, and is also one among many metrics used in assessing the performance of stochastic optimization algorithms. There are two well known SA techniques that are known to have optimal asymptotic variance: the Ruppert-Polyak averaging technique, and stochastic Newton-Raphson (SNR). The former algorithm can have extremely bad transient performance, and the latter can be computationally expensive. It is demonstrated here that parameter estimates from the new PolSA algorithm couple with those of the ideal (but more complex) SNR algorithm. The new algorithm is thus a third approach to obtain optimal asymptotic covariance. These strong results require assumptions on the model. A linearized model is considered, and the noise is assumed to be a martingale difference sequence. Numerical results are obtained in a non-linear setting that is the motivation for this work: In PolSA implementations of Q-learning it is observed that coupling occurs with SNR in this non-ideal setting.
BibTeX
@misc{devraj2019zap,
  author = {Adithya M. Devraj and Ana Busic and Sean P. Meyn},
  title = {{Zap Meets Momentum: Stochastic Approximation Algorithms with Optimal Convergence Rate}},
  year = {2019},
  eprint = {1809.06277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.06277},
}
Figure