

![0_image_0.png](0_image_0.png) 

so that this diverging result was true even though the exact value function v(0) = v(1) = 0 did belong to the feature space. In the case r1 = r2 **= 0,**
the TD and BR methods do calculate the exact solution (we will see later that this is indeed a general fact when the exact value function belongs to the feature space). We thus extend this model by taking (r1, r2) 6= (0, **0). As a scaling of the reward is translated exactly in the approximation, we consider the**
general form (r1, r2) = (cos θ,sin θ).

Consider the TD solution: one has Φ′Ξ = 12 1,
(I − γP)Φ = (1 − 2γ 1 − γ), thus (Φ′**ΞΨ) =** 52 − 3γ and Φ′Ξr =
r1 2 + r2**. Eventually the weight of the**
TD approximation is wTD =r1+2r2 5−6γ
. One notices here that the value γ = 5/6 is singular. Now, consider the BR solution. One can see that (Ψ′ΞΨ)−1 =
(1−2γ)
2+(2−2γ)
2 2**and Ψ**′Ξr =
(1−2γ)r1+(2−2γ)r2 2**. Thus,**
the weight of the BR approximation is wBR =
(1−2γ)r1+(2−2γ)r2
(1−2γ)
2+(2−2γ)
2 .

For all these approximations, one can compute the squared error e **with respect to the optimal solution**
v: For any weight w ∈ {wbest, wTD, wBR}, e(w) = kv − Φwk 2 ξ =
1 2
(v(1) − w)
2 +
1 2
(v(2) − 2w)
2. In Figure 1, we plot the squared error ratios e(wT D)
e(w**best**)
and e(wBR)
e(w**best**)
on a log scale (they are by definition greater than 1) with respect to θ and γ**. It turns out that**
these ratios do not depend on θ **(instead of showing** this through painful arithmetic manipulations, we will come back to this point and prove it later on). This Figure also displays the graph with respect to γ **only.** We can observe that for any choice of reward function and discount factor, the BR method returns a better value than the TD method. Also, when γ **is in**
the neighborhood of 56
, the TD error ratio tends to ∞
while BR's stays bounded. This Example shows that there exists MDPs where the BR is consistenly better than the TD method, which can give an unbounded error. One should however not conclude too quickly that BR is *always* **better than TD. The literature contains several arguments in favor of TD, one of which**
is considered in the following Example. Example 2 Sutton et al. **(2009) recently described a** 3-state MDP example where the TD method computes the best projection while BR does not. The idea behind this 3-state example can be described in a quite general way4: Suppose we have a k + l**-state MDP,**
of which the Bellman Equation has a block triangular structure: v1 = γP1v1 + r1 / v2 = γP21v1 + P22v2 + r2 where v1 ∈ R
k and v2 ∈ R
l**(the concatenation of**
the vectors v1 and v2 form the value function). Suppose also that the approximation subspace span (Φ)
is R
k × S2 where S2 **is a subspace of** R
l**. For the first**
component v1**, the approximation space is the entire**
space R
k**. With TD, we obtain the exact value for**
the k **first components of the value, while with Bellman residual minimization, we do not: satisfying the**
first equation exactly is traded for decreasing the error in satisfying the second one (which also involves v1).

In an optimal control context, the example above can have quite dramatic implications, as v1 **can be related**
to the costs at some future states accessible from those states associated with v2**, and the future costs are all**
that matters when making decisions. Overall, the two methods generate different types of biases, and distribute error in different manners. In order to gain some more insight, we now turn on to some analytical facts about them.

## 3. A Relation And Stability Issues

Though several works have compared and considered both methods (Schoknecht, 2002; **Lagoudakis & Parr,**
2003; Munos, 2003; Yu & Bertsekas, **2008), the following simple fact has, to our knowledge, never been emphasized** *per se*:
Proposition 1 *The BR is an upper bound of the TD* error, and more precisely:

$$\forall{\hat{v}}\in\mathbf{span}\left(\Phi\right),E_{B R}({\hat{v}})^{2}=E_{T D}({\hat{v}})^{2}+\|{\mathcal{T}}{\hat{v}}-\Pi{\mathcal{T}}{\hat{v}}\|_{\xi}^{2}.$$
.
Proof **This simply follows from Pythagore, as Π**T vˆ− T vˆ is orthogonal to span (Φ) and ˆv − ΠT vˆ **belongs to**
span **(Φ).** 
This implies that if one can make the BR small, then the TD Error will also be small. In the limit case where 4The rest of this section is strongly inspired by a personal communication with Yu.