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

Abstract

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.

Cited by in corpus (12)

• Reinforcement Learning via Fenchel-Rockafellar Duality
• Statistical Linear Estimation with Penalized Estimators: an Application to Reinforcement Learning
• Deep Residual Reinforcement Learning
• Proximal Algorithms and Temporal Differences for Large Linear Systems: Extrapolation, Approximation, and Simulation
• Rate of Convergence and Error Bounds for LSTD($\lambda$)
• Adaptive Temporal-Difference Learning for Policy Evaluation with Per-State Uncertainty Estimates
• A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning
• Fully Distributed Actor-Critic Architecture for Multitask Deep Reinforcement Learning
• Optimal oracle inequalities for solving projected fixed-point equations
• Stable and Efficient Policy Evaluation
• O${}^2$TD: (Near)-Optimal Off-Policy TD Learning
• On Generalized Bellman Equations and Temporal-Difference Learning