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:
- Standard SA: Computationally efficient but slow to converge.
- Stochastic Newton-Raphson (SNR): Mathematically optimal in terms of asymptotic variance but requires $O(d^3)$ matrix inversions per step.
- 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.
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