On 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. 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.

Introduction

Reinforcement Learning (RL) algorithms like Q-learning and Temporal Difference (TD) learning are fundamentally stochastic approximation (SA) methods designed to solve root-finding problems. In these settings, we aim to find a parameter vector $\theta^*$ such that an expected error function $\bar{f}(\theta^*) = 0$. Traditionally, researchers have balanced two competing performance metrics: transient performance (how quickly the algorithm approaches the solution) and asymptotic variance (the stability of the estimate once it is near the solution).

Existing methods often force a trade-off. Ruppert-Polyak averaging achieves optimal asymptotic variance but suffers from poor transient behavior. Conversely, Stochastic Newton-Raphson (SNR) provides optimal performance in both regimes but requires the inversion of a $d \times d$ matrix at every step, which is computationally prohibitive for high-dimensional problems. This work introduces a "third way" through matrix-valued momentum, bridging the gap between computational efficiency and statistical optimality.

Matrix Momentum: PolSA and NeSA

The core contribution of this research is the introduction of two new algorithms: PolSA (Polyak Stochastic Approximation) and NeSA (Nesterov Stochastic Approximation).

PolSA

PolSA utilizes a matrix momentum term $M$ that approximates the Jacobian of the objective function. Unlike standard scalar momentum, which applies a uniform weight to past updates, matrix momentum allows for directional acceleration. The authors demonstrate that by carefully designing this matrix, the algorithm's iterates can be made to "couple" with the ideal SNR algorithm.

NeSA

NeSA is a simplified variant inspired by Nesterov’s accelerated gradient descent. It is computationally lighter than PolSA and particularly effective in settings like Watkins’ Q-learning, where update matrices are sparse. NeSA maintains this sparsity, avoiding the dense matrix operations that plague second-order methods.

The Coupling Phenomenon

A central theoretical and empirical finding of this paper is the "coupling" between PolSA and SNR. Under certain conditions, the iterates of the PolSA algorithm eventually track the iterates of the theoretically ideal SNR algorithm almost perfectly. This means that PolSA can achieve the statistical benefits of a second-order method using only first-order updates augmented with matrix momentum.

Comparison of PolSA with different $\zeta$ values against SNR, demonstrating how PolSA iterates couple with the SNR path as $n$ increases.

As shown in the figure above, for larger values of the gain parameter $\zeta$, the PolSA trajectories (dashed lines) converge toward the noisy path of the SNR algorithm (solid orange line). This empirical evidence supports the claim that PolSA serves as a computationally efficient proxy for the optimal SNR method.

Experimental Results

The algorithms were tested on various Markov Decision Processes (MDPs), including a 6-state MDP and larger stochastic shortest path problems with up to 117 state-action pairs.

  1. Optimal Asymptotic Covariance: Theoretical proofs show that PolSA achieves the optimal asymptotic covariance $\Sigma^* = A^{-1} \Sigma^\Delta A^{-1T}$, matching the performance of SNR and Ruppert-Polyak averaging.
  2. Robustness in Non-linear Settings: While proofs are derived for linearized models, simulations of non-linear Q-learning demonstrate that the coupling phenomenon persists, with PolSA-D (a diagonal version) producing error distributions nearly identical to the "ideal" Zap SNR.
  3. Efficiency in Sparse Updates: In Q-learning tasks, NeSA significantly outperformed standard Watkins' Q-learning. Its ability to preserve update sparsity makes it highly scalable compared to dense matrix methods.

Conclusion and Future Directions

PolSA and NeSA offer a promising new framework for accelerating stochastic approximation in RL. By leveraging matrix momentum, these algorithms achieve the "gold standard" of asymptotic variance without the $O(d^3)$ cost of frequent matrix inversions.

Future work aims to extend the rigorous proofs of coupling from linearized models to fully non-linear systems. Additionally, exploring the application of these matrix momentum techniques to deep reinforcement learning—where parameters are high-dimensional neural network weights—remains a significant and exciting frontier.

Summary updated

Abstract

Acceleration is an increasingly common theme in the stochastic optimization\nliterature. The two most common examples are Nesterov's method, and Polyak's\nmomentum technique. In this paper two new algorithms are introduced for root\nfinding problems: 1) PolSA is a root finding algorithm with specially designed\nmatrix momentum, and 2) NeSA can be regarded as a variant of Nesterov's\nalgorithm, or a simplification of PolSA. The PolSA algorithm is new even in the\ncontext of optimization (when cast as a root finding problem).\n The research surveyed in this paper is motivated by applications to\nreinforcement learning. It is well known that most variants of TD- and\nQ-learning may be cast as SA (stochastic approximation) algorithms, and the\ntools from general SA theory can be used to investigate convergence and bounds\non convergence rate. In particular, the asymptotic variance is a common metric\nof performance for SA algorithms, and is also one among many metrics used in\nassessing the performance of stochastic optimization algorithms. There are two\nwell known SA techniques that are known to have optimal asymptotic variance:\nthe Ruppert-Polyak averaging technique, and stochastic Newton-Raphson (SNR).\nThe former algorithm can have extremely bad transient performance, and the\nlatter can be computationally expensive. It is demonstrated here that parameter\nestimates from the new PolSA algorithm couple with those of the ideal (but more\ncomplex) SNR algorithm. The new algorithm is thus a third approach to obtain\noptimal asymptotic covariance.\n These strong results require assumptions on the model. A linearized model is\nconsidered, and the noise is assumed to be a martingale difference sequence.\nNumerical results are obtained in a non-linear setting that is the motivation\nfor this work: In PolSA implementations of Q-learning it is observed that\ncoupling occurs with SNR in this non-ideal setting.\n
BibTeX
@misc{devraj2019matrix,
  author = {Adithya M. Devraj and Ana Bušić and Sean Meyn},
  title = {{On Matrix Momentum Stochastic Approximation and Applications to Q-learning}},
  year = {2019},
  eprint = {1809.06277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.06277},
}
Figure