Abstract
This paper establishes a theoretical unification of Temporal Difference (TD) learning and Bellman Residual (BR) minimization. By introducing the "unified oblique projection view," the work demonstrates that both methods are instances of the same geometric operation—oblique projection—differing only in the direction of projection. This framework explains the practical performance gap between the two methods: while TD often achieves higher accuracy, it is susceptible to extreme numerical instability, whereas BR provides a more stable, albeit sometimes more biased, approximation.
Introduction
Policy evaluation—the estimation of a value function for a fixed policy—is a fundamental component of reinforcement learning. In large state spaces, linear function approximation is typically employed to find a solution within a manageable subspace. Historically, two primary methodologies have emerged:
- Temporal Difference (TD) learning, which seeks a fixed point of the projected Bellman operator.
- Bellman Residual (BR) minimization, which directly minimizes the residual error of the Bellman equation.
While TD is widely used and often empirically superior, it lacks the robust stability and performance guarantees associated with BR. This paper provides a common geometric language to reconcile these two approaches.
The Unified Oblique Projection View
The core contribution of this work is the proof that both TD and BR can be viewed as solutions to a projected Bellman equation: $\hat{v}_X = \Pi_X T \hat{v}_X$. The distinction lies entirely in the projection direction $X$.
Specifically, an oblique projection onto a subspace along a direction $X$ is used. For TD, the projection direction is the feature space itself ($X = \Xi \Phi$). For BR, the direction is the feature space transformed by the system's underlying dynamics ($X = \Xi L \Phi$). This geometric insight allows for the derivation of tighter error bounds using the spectral radius of small matrices, simplifying previous analytical frameworks.
Empirical Evaluation
The theoretical insights were tested using synthetic, random Markov Decision Processes (MDPs). The experimental setup involved:
- Chain-like MDPs with state spaces ranging from 2 to 30.
- Random Projections using 20 different feature matrices ($\Phi$) and random reward vectors for each MDP.
- Thousands of scenarios to compare the relative performance of TD and BR.
Results and Discussion
The experiments revealed a significant "stability-performance trade-off."
Numerical Instability vs. Average Performance
While TD often finds a solution closer to the true value function, it is "high-risk." As shown in the error ratio analysis, TD can suffer from extreme "pikes" of error when the projection is poorly aligned with the Bellman operator. In contrast, BR's error remains smooth and bounded, making it better on average despite its conservative nature.
Win Frequency
Interestingly, TD "wins" (provides a better approximation than BR) more than 50% of the time in simulations. This frequency of success explains its popularity in the field, even if its worst-case behavior is significantly worse than BR's.
Conclusion
The unified oblique projection view clarifies that neither TD nor BR is universally optimal. TD offers high frequency of success but carries a risk of divergence or massive error due to norm incompatibility. BR serves as a safer upper bound that keeps error in check. Future work includes extending this framework to $TD(\lambda)$ and exploring its implications for non-linear function approximation.