Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning

Adithya M. Devraj, Ana Bušić, Sean Meyn

Abstract

Acceleration is an increasingly common theme in the stochastic optimization literature. In this paper, two new algorithms are introduced for root-finding problems: PolSA, a root-finding algorithm with specially designed matrix momentum, and NeSA, a variant of Nesterov's algorithm. This research is motivated by reinforcement learning, where TD- and Q-learning can be cast as stochastic approximation (SA) algorithms. While Stochastic Newton-Raphson (SNR) and Ruppert-Polyak averaging are known to have optimal asymptotic variance, they often face computational or transient performance hurdles. We demonstrate that parameter estimates from the new PolSA algorithm couple with those of the ideal SNR algorithm, providing a third approach to obtain optimal asymptotic covariance. Numerical results in non-linear Q-learning settings confirm that this coupling occurs even in non-ideal conditions.

Introduction

Many Reinforcement Learning (RL) tasks, such as TD-learning and Q-learning, are essentially root-finding problems: the goal is to find a parameter vector $\theta$ that makes the expected Bellman error zero. In Stochastic Approximation (SA), performance is judged by two primary metrics: transient performance (initial speed) and asymptotic variance (noise levels near the solution).

The "gold standard" for low variance is Stochastic Newton-Raphson (SNR), but it requires inverting a $d \times d$ matrix at every step, which is computationally prohibitive in high dimensions. Conversely, Ruppert-Polyak averaging, while theoretically optimal, often suffers from poor transient performance. This paper proposes a middle ground: algorithms that are computationally efficient like standard momentum methods but mathematically optimal like SNR.

Proposed Algorithms: PolSA and NeSA

The authors propose moving beyond simple scalar momentum to Matrix Momentum.

  • PolSA (Polyak Stochastic Approximation): This is a "Matrix Heavy-Ball" method. Instead of a scalar, it uses a matrix $M_n$ based on an estimate of the system's Jacobian. The core theoretical contribution is a "coupling" result: the iterates of PolSA stay incredibly close to the iterates of the "ideal" SNR algorithm, allowing PolSA to inherit SNR's optimal variance without the $O(d^3)$ cost of matrix inversion.
  • NeSA (Nesterov Stochastic Approximation): A simplified version inspired by Nesterov’s accelerated gradient. It is easier to implement and particularly well-suited for high-dimensional problems where the Jacobian is sparse, such as in Watkins’ Q-learning.

The Power of Coupling

The central insight is that PolSA can be viewed as a linearization of Nesterov’s method. By carefully choosing the matrix momentum term, the algorithm is "tricked" into behaving like a second-order Newton method. This is formally proven through coupling: the difference between PolSA and SNR algorithms vanishes faster than the error itself.

Evolution of parameter estimates $\theta_n(1)$ over time $n$, showing PolSA coupling with SNR for various values of $\zeta$.

As illustrated in Figure 1, as the parameter $\zeta$ increases, the trajectories of PolSA (dashed lines) converge toward the SNR trajectory (solid orange line). The inset highlights this coupling effect for larger $\zeta$, where the stochastic fluctuations of PolSA become synchronized with those of the optimal SNR method.

Experimental Results

The algorithms were evaluated using synthetic Markov Decision Process (MDP) environments for stochastic shortest path problems.

  • Efficiency in Q-learning: In Watkins’ Q-learning, update matrices are often extremely sparse. NeSA takes advantage of this, offering a massive speedup in computation per iteration compared to methods requiring matrix-vector products or inversions.
  • Superior Convergence: In tests on larger MDPs ($d=19$ and $d=117$), NeSA and PolSA significantly outperformed standard Watkins' Q-learning.
  • Exploration Impact: Results showed that "Clock Sampling" (deterministic exploration) combined with NeSA led to faster convergence and lower variance than standard online exploration.

Conclusion and Future Work

PolSA and NeSA provide a computationally efficient path to optimal asymptotic variance in stochastic approximation. While the current theoretical proofs rely on linearized models, the empirical success in non-linear Q-learning suggests broad applicability. Future work will focus on adaptive techniques to improve transient performance and extending these matrix momentum concepts to deep reinforcement learning where $\theta$ represents neural network weights.

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{devraj2019optimal,
  author = {Adithya M. Devraj and Ana Bušić and Sean Meyn},
  title = {{Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning}},
  year = {2019},
  eprint = {1809.06277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.06277},
}
Figure