# Should One Compute The Temporal Difference Fix Point Or Minimize The Bellman Residual ? The Unified Oblique Projection View

Bruno Scherrer scherrer@loria.fr LORIA - INRIA Lorraine - Campus Scientifique - BP 239 54506 Vandœuvre-l`es-Nancy CEDEX FRANCE

## 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.

## Introduction

We consider linear approximations of the value function of the policy in the framework of Markov Decision Processes (MDP). We focus on two popular methods: the computation of the projected Temporal Difference fixed point **(TD(0), TD for short),**
which Antos et al. (2008); Farahmand et al. **(2008);** Sutton et al. **(2009) have recently presented as the** minimization of the mean-square projected Bellman Equation, and the minimization of the meansquare Bellman Residual **(BR). In this article, we**
present some new analytical and empirical data, that shed some light on both approaches. The paper is organized as follows. Section 1 **describes the MDP linear approximation framework and the two projection**
methods. Section 2 **presents small MDP examples,** where each method outperforms the other. Section 3 **highlights a simple relation between the quantities** TD and BR optimize, and show that while BR enjoys a performance guarantee, TD does not in general. Section 4 **contains the main contribution of this paper:**
we describe a unified view in terms of oblique projections of the Bellman equation, which simplifies and extends the characterization of Schoknecht **(2002) and**
the recent analysis of Yu & Bertsekas (2008). Eventually, Section 5 **presents some simulations, that address**
the following practical questions: which of the method gives the best approximation? and how useful is our analysis for selecting it a priori?

## 1. Framework And Notations

The model **We consider an MDP with a fixed policy, that is an uncontrolled discrete-time dynamic system with instantaneous rewards. We assume that**
there is a state space X of finite size N**. When at**
state i ∈ {1, .., N}, there is a **transition probability**
pij of getting to the next state j. Let ik **the state of**
the system at time k**. At each time step, the system is** given a reward γ kr(ik) where r is the instantaneous reward function, and 0 < γ < 1 is a **discount factor**.

The value at state i is defined as the total expected return: v(i**) := lim**N→∞ E
hPN−1 k=0 γ kr(ik)
i0 = i i. We write P the N × N **stochastic matrix whose elements**
are pij . v **can be seen as a vector of** R
N . v **is known**
to be the unique fixed point of the Bellman operator:
T v := r + γP v, that is v **solves the Bellman Equation**
v = T v and is equal to L−1r where L = I − γP.