Abstract
Temporal Difference (TD) learning with linear function approximation is notoriously sensitive to the choice of step-size (learning rate), often diverging if the rate is set too high. This paper introduces a mathematical upper bound for the step-size that guarantees local stability. By implementing this bound as a simple, parameter-free heuristic, the authors demonstrate a method that matches the performance of optimally tuned fixed learning rates while preventing divergence across classic reinforcement learning benchmarks. Unlike existing adaptive methods, this approach requires no meta-parameters and adds negligible computational overhead.
Introduction
In reinforcement learning, the step-size ($\alpha$) is a critical hyperparameter that determines how much a model updates its value estimates based on new data. Finding the right $\alpha$ presents three major challenges:
- The Divergence Trap: Excessive step-sizes cause errors to grow infinitely, a common failure mode in online learning with function approximation.
- The Bootstrapping Problem: TD learning updates estimates based on other estimates. Aggressive updates can propagate bad estimates, leading to a "death spiral" of increasing error.
- The Tuning Tax: Researchers typically rely on expensive grid searches to find a fixed step-size that works for a specific problem.
This research proposes an "Alpha Bound" method to adapt the step-size automatically and safely, ensuring that updates never move the model toward divergence.
The Alpha Bound Method
The authors derived their solution by analyzing the prediction error ($\delta_t$) before and after a weight update. The core intuition is that an update is successful if the magnitude of the error decreases without changing sign. If the error increases or flips sign significantly, the step-size was too large.
By manipulating standard TD update equations, they derived a theoretical upper bound for $\alpha$, simplified into the following practical heuristic: $$\alpha_t = \min[\alpha_{t-1}, |e_t^T (\gamma \phi_{t+1} - \phi_t)|^{-1}]$$ Where $e_t$ is the eligibility trace and $\phi$ represents the feature vectors. This calculation is $O(n)$, making it computationally efficient for large feature sets. Notably, this approach is "plug-and-play," requiring no meta-learning rates or prior models of the environment.
Experimental Evaluation
The method was evaluated on four classic reinforcement learning benchmarks: Mountain Car, Acrobot, Puddle World, and Cart Pole. All experiments utilized a Fourier basis (order 3) for linear function approximation within the RL-Glue framework.
Key Results
- Robustness to Initial Conditions: While standard TD learning diverged rapidly when the initial $\alpha_0$ was set high (e.g., 1.0), the Alpha Bound method automatically scaled the step-size down to a safe level. As shown in the Mountain Car results (Figure 4), the Alpha Bound maintains stable average rewards even as the initial step-size increases, whereas backoff methods eventually fail.
- Competitive Performance: The adaptive method consistently performed as well as the best-tuned fixed step-sizes found via grid search.
- Superiority Over Existing Adaptive Methods: The Alpha Bound outperformed other strategies like HL($\lambda$) and Autostep. As seen in the Puddle World comparison (Figure 5), Alpha Bound remains stable across the entire range of $\alpha_0$, while Autostep and Vanilla TD diverge once $\alpha_0$ exceeds a small threshold.
Discussion and Future Work
The Alpha Bound method effectively "hugs" the edge of the largest safe step-size, providing stability without sacrificing learning speed. However, some limitations remain:
- Scalar vs. Vector: The current method uses a single scalar step-size. Extending this to vector step-sizes (individual rates for each feature) could further accelerate convergence.
- Convergence Decay: While the bound prevents divergence, it does not naturally decay to zero. Future work could combine this bound with "search then converge" logic for perfect final convergence.
- Linearity: The current derivation is specific to linear function approximation; extending these proofs to non-linear models like deep neural networks remains a significant challenge.
In conclusion, the Alpha Bound provides a robust, parameter-free solution to one of the most persistent tuning problems in reinforcement learning, offering a safer and more efficient path for online TD learning.
Summary updated