Abstract
We establish connections from optimizing Bellman Residual and Temporal Difference Loss to worst-case long-term predictive error. In the online learning framework, learning takes place over a sequence of trials with the goal of predicting a future discounted sum of rewards. Our first analysis shows that, together with a stability assumption, any no-regret online learning algorithm that minimizes Bellman error ensures small prediction error. Our second analysis shows that applying the family of online mirror descent algorithms on temporal difference loss also ensures small prediction error. No statistical assumptions are made on the sequence of observations, which could be non-Markovian or even adversarial. Our approach thus establishes a broad new family of provably sound algorithms and provides a generalization of previous worst-case results for minimizing predictive error. We investigate the potential advantages of some of this family both theoretically and empirically on benchmark problems.
Introduction
In Reinforcement Learning (RL), policy evaluation is the fundamental task of predicting the total discounted sum of future rewards—the value function—for a fixed strategy. While Temporal Difference (TD) learning is the standard tool for this task, it often suffers from instability or divergence when combined with function approximation. An alternative approach, Residual Gradient (RG), minimizes Bellman Error (BE) to maintain stability, but its theoretical guarantees typically rely on the assumption of a static, well-behaved Markov Decision Process (MDP).
This work addresses whether small prediction errors can be guaranteed even in environments that are changing, non-Markovian, or adversarial. By framing policy evaluation as an online learning problem, the authors provide a general framework that moves beyond specific linear update rules to include a broad family of provably sound algorithms.
Methodology
The authors treat observations as a sequence of trials and analyze two primary approaches to optimizing prediction error:
1. Optimizing Bellman Loss
The research demonstrates that any online learning algorithm characterized by both no-regret (performing as well as the best fixed predictor in hindsight) and stability (avoiding wild fluctuations in predictions between steps) will achieve small long-term prediction error. This result significantly generalizes the classic Residual Gradient algorithm and extends its applicability to complex function spaces, such as Reproducing Kernel Hilbert Spaces (RKHS).
2. Optimizing TD Loss
The paper applies Online Mirror Descent (OMD) and Implicit Online Learning algorithms to a reformulated TD loss. The analysis proves that these algorithms also ensure small prediction errors without requiring statistical assumptions about the observation sequence.
A key insight is that stability is essential; no-regret alone does not suffice for RL prediction guarantees. The difference between successive predictors must eventually diminish on average to ensure convergence to a reliable value function estimate.
Experimental Evaluation
The proposed framework was evaluated on standard RL benchmarks, including a Random Walk variant and the Puddle World navigation task.
As shown in the experimental results, modern online algorithms such as Online Newton Step (ONS) and Implicit Online Gradient Descent (OGD) demonstrate superior performance. These methods converge faster and reach lower average prediction errors compared to classic TD(0) and standard Residual Gradient. The empirical success of "Implicit" updates highlights their robustness in practical scenarios, often outperforming traditional methods.
Discussion and Future Work
This work establishes that TD and RG are best understood as online algorithms, providing a theoretical foundation for their use in adversarial or non-stationary environments. The derived mathematical bounds for Residual Gradient are asymptotically tighter than previous results as the discount factor $\gamma$ approaches 1.
However, some limitations remain. While the connection for Bellman Error is highly general, the analysis for TD loss is currently restricted to specific algorithm families like OMD. A significant open question is whether a similarly general connection exists between TD loss and all no-regret/stable algorithms. Additionally, while advanced algorithms like ONS offer better performance, their higher computational cost compared to simple TD may be a factor in large-scale applications.
Summary updated