Should one compute the Temporal Difference fix point or minimize the Bellman Residual? The unified oblique projection view

By Bruno Scherrer. 2010

108 citations recorded by the source corpus.

We investigate projection methods, for evaluating a linear approximation of the value function of a policy in a Markov Decision Process context. We consider two popular approaches, the one-step Temporal Difference fix-point computation (TD(0)) and the Bellman Residual (BR) minimization. We describe examples, where each method outperforms the other. We highlight a simple relation between the objective function they minimize, and show that while BR enjoys a performance guarantee, TD(0) does not in general. We then propose a unified view in terms of oblique projections of the Bellman equation, which substantially simplifies and extends the characterization of Schoknecht (2002) and the recent analysis of Yu & Bertsekas (2008). Eventually, we describe some simulations that suggest that if the TD(0) solution is usually slightly better than the BR solution, its inherent numerical instability makes it very bad in some cases, and thus worse on average.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Reinforcement Learning via Fenchel-Rockafellar Duality (2020, methodology): “Typically, the Q-values are estimated by finding the fixed point of the Bellman recurrence (Sutton et al., 2008, 2009; Scherrer, 2010; Liu et al., 2015; Dai et al., 2016; Du et al., 2017); i.”
Diagnosing Bottlenecks in Deep Q-learning Algorithms (2019, methodology): “, 2009b;a) and residual methods (Baird, 1995; Scherrer, 2010) can be seen as introducing a stationary objective that can be optimized with standard procedures such as gradient descent for increased stability.”
On Convergence of Emphatic Temporal-Difference Learning (2015, methodology): “The relation between the solution v = Φθ∗ of this equation and the desired value function vπ, in particular, the approximation error, can be analyzed then, using the oblique projection viewpoint (Scherrer, 2010) (for details, see also (Yu and Bertsekas, 2012)).”
Off-policy learning with eligibility traces: a survey (2013, background): “One of the motivations for this approach is that, as opposed to the matrix A of LSTD/LSPE/FPKF, Ā is invertible for all values of λ, and one can always guarantee a finite error bound with respect to the best projection (see Schoknecht (2002); Yu and Bertsekas (2008); Scherrer (2010)).”
Least Squares Temporal Difference Methods: An Analysis under General Conditions (2012, neutral): “There are approximation error bounds (Yu and Bertsekas [37]) and geometric interpretations of the approximation Φ r ∗ as an oblique projection of J ∗ (Scherrer [29]) in this case.”
Algorithms for Reinforcement Learning (2010, background): “(For sharper bounds, see Yu and Bertsekas 2008; Scherrer 2010.) From the error bound we see that Vθ(1) is the best approximation to V within F with respect to the norm ‖·‖μ (this should come at no surprise as TD(1) minimizes this mean-squared error by design). We also see that as we let λ → 0 the bo”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, methodology): “Note that LSTD and other methods in the least-squares family can also be extended to use eligibility traces (Thiery and Scherrer, 2010).”
Reinforcement Learning in Continuous State and Action Spaces (2012, background): “It is problem-dependent whether minimizing the residual error leads to better results than minimizing the projected error (Scherrer, 2010).”
Neural Network Ensembles in Reinforcement Learning (2015, methodology): “Scherrer [11] mathematically analyzed and compared the minimization of the Bellman Residual (BR) with the computation of the TD fixed-point using his projected view and has observed that minimizing the BR error reduces the TD error as well but not vice-versa.”
Is the Bellman residual a bad proxy? (2016, unknown): “(2)With a single action, this approach reduces to LSTD (Least-Squares Temporal Differences) [5], that can be arbitrarily bad in an off-policy setting [20].”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, methodology): “(9)Briefly speaking, [40] showed that the solutions of projected Bellman equations are oblique projections of vπ on the approximation subspace.”
Weighted Bellman Equations and their Applications in Approximate Dynamic Programming ∗ (2012, background): “Geometric Interpretation Scherrer [Sch10] showed a geometric interpretation of x̄ as an oblique projection of x∗, which holds also when ‖ · ‖ξ is a semi-norm:(2) 2We describe briefly the derivation.”
Policy evaluation with temporal differences: a survey and comparison (2015, methodology): “…of MSPBE often has a lower mean squared error, however, the solution may get unstable and may yield estimates arbitrarily far away from the true solution V π. Scherrer (2010) illustrated this effect by an example MDP with unstable MSPBE solutions for certain settings of the discount factor γ.”
Statistical linear estimation with penalized estimators: an application to reinforcement learning (2012, background): “3The MRP is said to be in a steady-state if the distribution of Xt is independent of t. 4 For a discussion of how well Wθ∗ approximates V the reader is directed to consult the paper by Scherrer (2010) and the references therein.”