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