Approximation Scheme When the size N **of the**
state space is large, one usually comes down to solving the Bellman Equation approximately. One possibility is to look for an approximate solution ˆv **in some specific** small space. The simplest and best understood choice is a linear parameterization: ∀i, vˆ(i) = Pm j=1 wjφj (i)
where m ≪ N, the φj **are some feature functions that**
should capture the general shape of v, and wj **are the**
weights that characterize the approximate value ˆv**. For**
all i and j, write φj the N**-dimensional vector corresponding to the** j th feature function and φ(i) the mdimensional vector giving the features of state i**. For**
any vector of matrix X, denote X′**its transpose. The**
following N × m feature matrix Φ = (φ1 . . . φm) =
(φ(i1). . . φ(iN ))′**leads to write the parameterization**
of v in a condensed matrix form: ˆv = Φw**, where**
w = (w1, ..., wm) is the m-dimensional weight vector. We will now on denote span **(Φ) this subspace**
of R
N and assume that the vectors φ1, ..., φm **form a**
linearly independent set.

Some approximation ˆv of v can be obtained by minimizing ˆv 7→ kvˆ−vk for some norm k· k, that is equivalently by projecting v onto span **(Φ) orthogonally with**
respect to k · k**. In a very general way, any symmetric**
positive definite matrix Q of R
N **induces a quadratic**
norm **k · k**Q on R
N **as follows:** kvkQ =
√v′Qv**. It**
is well known that the orthogonal projection with respect to such a norm, which we will denote Πk·kQ
,
has the following closed form: Πk·kQ = Φπk·kQ **where**
πk·kQ = (Φ′QΦ)−1Φ′Q **is the linear application from**
R

N to R
m that returns the coordinates of the projection of a point in the basis (φ1, . . . , φm**). With**
these notations, the following relations πk·kQ Φ = I and πk·kQ Πk·kQ = πk·kQ **hold.**
In an MDP approximation context, where one is modeling a stochastic system, one usually considers a specific kind of norm/projection. Let ξ = (ξi**) be some**
distribution on X such that ξ > **0 (it assigns a positive**
probability to all states). Let Ξ be the diagonal matrix with the elements of ξ **on the diagonal. Consider the**
orthogonal projection of R
N **onto the feature space**
span (Φ) with respect to the ξ**-weighted quadratic**
norm kvkξ =
qPN
j=1 ξivi 2 =
√v′Ξv**. For clarity**
of exposition, we will denote this specific projection Π := Πk·kΞ = Φπ where π := πk·kΞ = (Φ′ΞΦ)−1Φ′Ξ.

Ideally, one would like to compute the "best" approximation

* [16] M. C.  
vˆbest = Φwbest with w**best** = πv = πL−1r.

This can be done with algorithms like TD(1) / LSTD(1)(Bertsekas & Tsitsiklis, 1996; Boyan, **2002),** but they require simulating infinitely long trajectories and usually suffer from a high variance. The projections methods, which we focus on in this paper, are alternatives that only consider *one-step* **samples.**
TD(0) fix point method **The principle of the**
TD(0) method (TD for short) is to look for a fixed point of ΠT , that is, one looks for ˆvTD **in the space** span (Φ) satisfying ˆvTD = ΠT vˆTD**. Assuming that**
the matrix inverse below exists1**, it can be proved**2 that ˆvTD = ΦwTD **with**

$$w_{T D}=(\Phi^{\prime}\Xi L\Phi)^{-1}\Phi^{\prime}\Xi r$$
$$\left(1\right)$$
out by Antos et al. (2008);
′Ξr (1)
As pointed out by Antos et al. **(2008);** Farahmand et al. (2008); Sutton et al. **(2009),**
when the inverse exists, the above computation is equivalent to minimizing for ˆv ∈ span **(Φ) the TD**
error ETD(ˆv) := kvˆ − ΠT vˆkξ **down to 0**3.

BR minimization method **The principle of the**
Bellman Residual (BR) method is to look for ˆv ∈
span **(Φ) so that it minimizes the norm of the Bellman**
Residual, that is the quantity EBR(ˆv) := kvˆ − T vˆkξ.

Since ˆv is of the form Φw, it can be seen that EBR(ˆv) =
kΦw − γPΦw − rkξ = kΨw − rkξ **using the notation**
Ψ = L**Φ. Using standard linear least squares arguments, one can see that the minimum BR is obtained**
for ˆvBR = ΦwBR **with**

$$w_{B R}=(\Psi^{\prime}\Xi\Psi)^{-1}\Psi^{\prime}\Xi r.$$
$$\left(2\right)$$
′Ξr. (2)
Note that in this case, the above inverse always exists (Schoknecht, **2002).**

## 2. Two Simple Examples

Example 1 **Consider the 2 state MDP such that** P =
0 1 0 1 . Denote the rewards r1 and r2**. One**
thus have v**(1) =** r1 +
γr2 1−γ and v**(2) =** r2 1−γ
. Consider the one-feature linear approximation with Φ = (1 2)′,
with uniform distribution ξ = (.5 .5)′. Φ′**ΞΦ =** 52
,
therefore π =15 2 5
, and the weight of the best approximation is w**best** = πv =
1 5 r1 +2+γ 5(1−γ)
r2**. This example**
has been proposed by Bertsekas & Tsitsiklis **(1996) in** order to show that fitted Value Iteration can diverge if the samples are not generated by the stationary distribution of the policy. In (Bertsekas & Tsitsiklis, 1996), the authors only consider the case r1 = r2 = 0 1This is not necessary the case, as the forthcoming Example 1 (Section **2) shows.**
2 Section 4 **will generalize this derivation.**
3**This remark is also true if we replace** k · kξ **by any**
equivalent norm k · k. This observation lead **Sutton et al.** (2009) to propose original off-policy gradient algorithms for computing the TD solution.