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

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 mean-square 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?

Framework and Notations

Approximation Scheme

Ideally, one would like to compute the “best” approximation

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 $\Pi{\cal T}$, that is, one looks for $\hat{v}_{TD}$ in the space $\mbox{\bf span}\left(\Phi\right)$ satisfying $\hat{v}_{TD}=\Pi{\cal T}\hat{v}_{TD}$. Assuming that the matrix inverse below existsThis is not necessary the case, as the forthcoming Example 1 (Section 2) shows., it can be provedSection 4 will generalize this derivation. that $\hat{v}_{TD}=\Phi w_{TD}$ with

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 $\hat{v}\in\mbox{\bf span}\left(\Phi\right)$ the TD error $E_{TD}(\hat{v}):=\|\hat{v}-\Pi{\cal T}\hat{v}\|_{\xi}$ down to 0This remark is also true if we replace $\|\cdot\|_{\xi}$ by any equivalent norm $\|\cdot\|$. This observation lead Sutton et al. (2009) to propose original off-policy gradient algorithms for computing the TD solution..

BR minimization method

The principle of the Bellman Residual (BR) method is to look for $\hat{v}\in\mbox{\bf span}\left(\Phi\right)$ so that it minimizes the norm of the Bellman Residual, that is the quantity $E_{BR}(\hat{v}):=\|\hat{v}-{\cal T}\hat{v}\|_{\xi}$. Since $\hat{v}$ is of the form $\Phi w$, it can be seen that $E_{BR}(\hat{v})=\|\Phi w-\gamma P\Phi w-r\|_{\xi}=\|\Psi w-r\|_{\xi}$ using the notation $\Psi=L\Phi$. Using standard linear least squares arguments, one can see that the minimum BR is obtained for $\hat{v}_{BR}=\Phi w_{BR}$ with

Note that in this case, the above inverse always exists (Schoknecht, 2002).

Two simple examples

Consider the 2 state MDP such that P={\tiny\left(\begin{array}[]{cc}0&1\\ 0&1\end{array}\right)}. Denote the rewards $r_{1}$ and $r_{2}$. One thus have $v(1)=r_{1}+\frac{\gamma r_{2}}{1-\gamma}$ and $v(2)=\frac{r_{2}}{1-\gamma}$. Consider the one-feature linear approximation with $\Phi=(1~{}2)^{\prime}$, with uniform distribution $\xi=(.5~{}.5)^{\prime}$. $\Phi^{\prime}\Xi\Phi=\frac{5}{2}$, therefore $\pi=\left(\frac{1}{5}\frac{2}{5}\right)$, and the weight of the best approximation is $w_{best}=\pi v=\frac{1}{5}r_{1}+\frac{2+\gamma}{5(1-\gamma)}r_{2}$. 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 $r_{1}=r_{2}=0$ 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 $r_{1}=r_{2}=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 $(r_{1},r_{2})\neq(0,0)$. As a scaling of the reward is translated exactly in the approximation, we consider the general form $(r_{1},r_{2})=(\cos\theta,\sin\theta)$.

Consider the TD solution: one has $\Phi^{\prime}\Xi=\left(\frac{1}{2}~{}1\right)$, $(I-\gamma P)\Phi=\left(1-2\gamma~{}1-\gamma\right)$, thus $(\Phi^{\prime}\Xi\Psi)=\frac{5}{2}-3\gamma$ and $\Phi^{\prime}\Xi r=\frac{r_{1}}{2}+r_{2}$. Eventually the weight of the TD approximation is $w_{TD}=\frac{r_{1}+2r_{2}}{5-6\gamma}$. One notices here that the value $\gamma=5/6$ is singular. Now, consider the BR solution. One can see that $(\Psi^{\prime}\Xi\Psi)^{-1}=\frac{(1-2\gamma)^{2}+(2-2\gamma)^{2}}{2}$ and $\Psi^{\prime}\Xi r=\frac{(1-2\gamma)r_{1}+(2-2\gamma)r_{2}}{2}$. Thus, the weight of the BR approximation is $w_{BR}=\frac{(1-2\gamma)r_{1}+(2-2\gamma)r_{2}}{(1-2\gamma)^{2}+(2-2\gamma)^{2}}$.

For all these approximations, one can compute the squared error $e$ with respect to the optimal solution $v$: For any weight $w\in\{w_{best},w_{TD},w_{BR}\}$, $e(w)=\|v-\Phi w\|_{\xi}^{2}=\frac{1}{2}(v(1)-w)^{2}+\frac{1}{2}(v(2)-2w)^{2}$. In Figure 1, we plot the squared error ratios $\frac{e(w_{TD})}{e(w_{best})}$ and $\frac{e(w_{BR})}{e(w_{best})}$ on a log scale (they are by definition greater than $1$) with respect to $\theta$ and $\gamma$.

It turns out that these ratios do not depend on $\theta$ (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 $\gamma$ 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 $\gamma$ is in the neighborhood of $\frac{5}{6}$, the TD error ratio tends to $\infty$ 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

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.

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:

The BR is an upper bound of the TD error, and more precisely:

This simply follows from Pythagore, as $\Pi T\hat{v}-T\hat{v}$ is orthogonal to $\mbox{\bf span}\left(\Phi\right)$ and $\hat{v}-\Pi{\cal T}\hat{v}$ belongs to $\mbox{\bf span}\left(\Phi\right)$. ∎∎

This implies that if one can make the BR small, then the TD Error will also be small. In the limit case where one can make the BR equal to 0, then the TD Error is also 0.

One of the motivation for minimizing the BR is historically related to a well-known result of Williams & Baird (1993): $\forall\hat{v},~{}\|v-\hat{v}\|_{\infty}\leq\frac{1}{1-\gamma}\|{\cal T}\hat{v}-\hat{v}\|_{\infty}.$ Since one considers the weighted quadratic norm in practiceMainly because it is computationnally easier than doing a max-norm minimization, see however (Guestrin et al., 2001) for an attempt of doing max-norm projection., the related resultThe proof is a consequence of Jensen’s inequality and the arguments are very close to the ones in (Munos, 2003). that really makes sense here is: $\forall\hat{v},~{}\|v-\hat{v}\|_{\xi}\leq\frac{\sqrt{C(\xi)}}{1-\gamma}\|{\cal T}\hat{v}-\hat{v}\|_{\xi}$ where $C(\xi):=\max_{i,j}\frac{p_{ij}}{\xi_{i}}$ is a “concentration coefficient”, that can be seen as some measure of the stochasticity of the MDPIf $\xi$ is the uniform law, then there always exists such a $C(\xi)\in(1,N)$ where one recalls that $N$ is the size of the state space; in such a case, $C(\xi)$ is minimal if all next-states are chosen with the uniform law, and maximal as soon as there exists a deterministic transition. See (Munos, 2003) for more discussion on this coefficient.. This result shows that it is sound to minimize the BR, since it controls (through a constant) the approximation error $\|v-\hat{v}_{BR}\|_{\xi}$.

On the TD side, there does not exist any similar result. Actually, the fact that one can build examples (like Example 1) where the TD projection is numerically unstable implies that one cannot prove such a result. Proposition 1 allows to understand better the TD method: by minimizing the TD Error, one only minimizes one part of the BR, or equivalently this means that one does not care about the term $\|{\cal T}v-\Pi{\cal T}v\|_{\xi}^{2}$, which may be interpreted as a measure of adequacy of the projection $\Pi$ with the Bellman operator ${\cal T}$. In Example 1, the approximation error of the TD projection goes to infinity because this adequacy term diverges. In (Munos & Szepesvári, 2008), the authors use an algorithm based on the TD Error and make an assumption on this adequacy term (there called the inherent Bellman error of the approximation space), so that their algorithm can be proved convergent.

A complementary view on the potential instability of TD, has been referred to as a norm incompatibility issue (Bertsekas & Tsitsiklis, 1996; Guestrin et al., 2001), and can be revisited through the notion of concentration coefficient. Stochastic matrices $P$ statisfy $\|P\|_{\infty}=1$, which makes the Bellman operator ${\cal T}$ $\gamma$-contracting, and thus its fixed point is well-defined. The orthogonal projection with respect to $\|\cdot\|_{\xi}$ is such that $\|\Pi\|_{\xi}=1$. Thus $P$ and $\Pi$ are of norm 1, but for different norms. Unfortunately, a general (tight) bound for linear projections is $\|\Pi\|_{\infty}\leq\frac{1+\sqrt{N}}{2}$ (Thompson, 1996) and it can be shownOne can prove that for all $x$, $\|Px\|_{\xi}^{2}\leq\|x\|_{\xi P}^{2}\leq C(\xi)\|x\|_{\xi}^{2}$. The argument for the first inequality involves Jensen’s inequality and is again close to what is done in (Munos, 2003). that $\|P\|_{\xi}\leq\sqrt{C(\xi)}$ (which can thus also be of the order of $\sqrt{N}$). Consequently, $\|\Pi P\|_{\infty}$ and $\|\Pi P\|_{\xi}$ may be greater than 1, and thus the fixed point of the projected Bellman equation may not be well-defined. A known exception where the composition $\Pi P$ has norm 1, is when one can prove that $\|P\|_{\xi}=1$ (as for instance when $\xi$ is the stationary distribution of $P$) and in this case we know from Bertsekas & Tsitsiklis (1996); Tsitsiklis & Van Roy (1997) that

Another notable such exception is when $\|\Pi\|_{max}=1$, as in the so-called “averager” approximation (Gordon, 1995). However, in general, the stability of TD is difficult to guarantee.

The unified oblique projection view

In the TD approach, we consider finding the fixed point of the composition of an orthogonal projection $\Pi$ and the Bellman operator ${\cal T}$. Suppose now we consider using a (non necessarily orthogonal) projection $\Pi$ onto $\mbox{\bf span}\left(\phi\right)$, that is any linear operator that satisfies $\Pi^{2}=\Pi$ and whose range is $\mbox{\bf span}\left(\Phi\right)$. In their most general form, such operators are called oblique projections and can be written $\Pi_{X}=\Phi\pi_{X}$ with $\pi_{X}=(X^{\prime}\Phi)^{-1}X^{\prime}$. The parameter $X$ specifies the projection direction: precisely, $\Pi_{X}$ is the projection onto $\mbox{\bf span}\left(\Phi\right)$ orthogonally to $\mbox{\bf span}\left(X\right)$. As for the orthogonal projections, the following relations $\pi_{X}\Phi=I$ and $\pi_{X}\Pi_{X}=\pi_{X}$ hold. Recall that $L=I-\gamma P$. We are ready to state the main result of this paper:

Write $X_{TD}=\Xi\Phi$ and $X_{BR}=\Xi L\Phi$. (1) The TD fix point computation and the BR minimization are solutions (respectively with $X=X_{TD}$ and $X=X_{BR}$) of the projected equation $\hat{v}_{X}=\Pi_{X}{\cal T}\hat{v}_{X}$. (2) When it exists, the solution of this projected equation is the projection of $v$ onto $\mbox{\bf span}\left(\Phi\right)$ orthogonally to $\mbox{\bf span}\left(L^{\prime}X\right)$, i.e. formally $\hat{v}_{X}=\Pi_{L^{\prime}X}~{}v$.

We begin by showing part (2). Writing $\hat{v}_{X}=\Phi w_{X}$, the fixed point equation is: $\Phi w_{X}=\Pi_{X}(r+\gamma P\Phi w_{x}).$ Multiplying on both sides by $\pi_{X}$, one obtains: $w_{X}=\pi_{X}(r+\gamma P\Phi w_{x})$ and therefore $w_{X}=(I-\gamma\pi_{X}P\Phi)^{-1}\pi_{X}r.$ Using the definition of $\pi_{X}$, one obtains:

The proof of part (1) now follows. The fact that TD is a special case with $X=\Xi\Phi$ is trivial by construction since then $\Pi_{X}$ is the orthogonal projection with respect to $\|\cdot\|_{\xi}$. When $X=\Xi L\Phi$, one simply needs to observe from Equations 2 and 4 and the definition of $\Psi=L\Phi$ that $w_{X}=w_{BR}$. ∎∎

Beyond its nice and simple geometric flavour, a direct consequence of Proposition 2 is that it allows to derive tight error bounds for TD, BR, and any other method for general $X$. For any square matrix $M$, write $\sigma(M)$ its spectral radius.

For any choice of $X$, the approximation error satisfies:

where $A=\Phi^{\prime}\Xi\Phi$, $B=(X^{\prime}L\Phi)^{-1}$ and $C=XL\Xi^{-1}L^{\prime}X$ are matrices of size $m\times m$.

Thus, for any $X$, the amplification of the smallest error $\|v-{\hat{v}}_{best}\|_{\xi}$ depends on the norm of the associated oblique projection, which can be estimated as the spectral radius of the product of small matrices. A simple corollary of this Proposition is the following: if the real value $v$ belongs to the feature space $\mbox{\bf span}\left(\Phi\right)$ (in such a case $v={\hat{v}}_{best}$) then all oblique projection methods find it ($\hat{v}_{X}=v$).

Proposition 2 implies that $v-\hat{v}_{X}=(I-\Pi_{L^{\prime}X})v=(I-\Pi_{L^{\prime}X})(I-\Pi_{\Xi\Phi})v.$ where we used the fact that $\Pi_{L^{\prime}X}\Pi_{\Xi\Phi}=\Pi_{\Xi\Phi}$ since $\Pi_{L^{\prime}X}$ and $\Pi_{\Xi\Phi}$ are projections onto $\mbox{\bf span}\left(\Phi\right)$. Taking the norm, one obtains $\|v-\hat{v}_{X}\|_{\xi}\leq\|I-\Pi_{L^{\prime}X}\|_{\xi}\|v-\Pi_{\Xi\Phi}v\|_{\xi}=\|\Pi_{L^{\prime}X}\|_{\xi}\|v-{\hat{v}}_{best}\|_{\xi}$ where we used the definition of ${\hat{v}}_{best}$, and the fact that $\|I-\Pi_{L^{\prime}X}\|_{\xi}=\|\Pi_{L^{\prime}X}\|_{\xi}$ since $\Pi_{L^{\prime}X}$ is a (non-trivial) projection (see e.g. (Szyld, 2006)). Thus Equation 3 holds.

In order to evaluate the norm in terms of small size matrices, one will use the following Lemma on the projection matrix $\Pi_{L^{\prime}X}=\Phi\pi_{L^{\prime}X}$:

Let $Y$ be an $N\times m$ matrix, and $Z$ a $m\times N$ matrix, then $\|YZ\|_{\xi}^{2}=\sigma\left((Y^{\prime}\Xi Y)(Z\Xi^{-1}Z^{\prime})\right).$

Thus, $\|\Pi_{L^{\prime}X}\|^{2}_{\xi}=\|\Phi\pi_{L^{\prime}X}\|^{2}_{\xi}=\sigma[(\Phi^{\prime}\Xi\Phi)(\pi_{L^{\prime}X}\Xi^{-1}(\pi_{L^{\prime}X})^{\prime})]=\sigma[\Phi^{\prime}\Xi\Phi(X^{\prime}L\Phi)^{-1}X^{\prime}L\Xi^{-1}L^{\prime}X(\Phi^{\prime}L^{\prime}X)^{-1}]=\sigma[ABCB^{\prime}].\qed$ ∎

Proposition 2 is closely related to the work of (Schoknecht, 2002), in which the author derived the following characterization of the TD and BR solutions:

The TD fix point computation and the BR minimization are orthogonal projections of the value $v$ respectively induced by the seminorm $\|\cdot\|_{Q_{TD}}$This is a seminorm because the matrix $Q_{TD}$ is only semidefinite (since $\Phi\Phi^{\prime}$ has rank smaller than $m<N$). The corresponding projection can still be well defined (i.e. each point has exactly one projection) provided that $\mbox{\bf span}\left(\Phi\right)\cap\{x;\|x\|_{Q_{TD}}=0\}=\{0\}$. with $Q_{TD}=L^{\prime}\Xi\Phi\Phi^{\prime}\Xi L$ and by the norm $\|\cdot\|_{Q_{BR}}$ with $Q_{BR}=L^{\prime}\Xi L$.

This “orthogonal projection” characterization and our “oblique projection” characterization are in fact equivalent. On the one hand for BR, it is immediate to notice that $\Pi_{\|\cdot\|_{Q_{BR}}}=\Pi_{L^{\prime}X_{BR}}$. On the other hand for TD, writing $Y=L^{\prime}X_{TD}$, one simply needs to notice that $\Pi_{L^{\prime}X_{TD}}=\Pi_{Y}=\Phi(Y^{\prime}\Phi)^{-1}Y^{\prime}=\Phi(Y^{\prime}\Phi)^{-1}(\Phi^{\prime}Y)^{-1}(\Phi^{\prime}Y)Y^{\prime}=\Phi(\Phi^{\prime}YY^{\prime}\Phi)^{-1}\Phi^{\prime}YY^{\prime}=\Pi_{\|\cdot\|_{Q_{TD}}}$. The work of Schoknecht (2002) suggests that TD and BR are optimal for different criteria, since both look for some $\hat{v}\in\mbox{\bf span}\left(\Phi\right)$ that minimizes $\|\hat{v}-v\|$ for some (semi)norm $\|\cdot\|$. Curiously, our result suggests that neither is optimal, since neither uses the best projection direction $X^{*}:=L^{\prime-1}\Xi\Phi$ for which $\hat{v}_{X^{*}}=\Pi_{L^{\prime}X^{*}}v=\Pi_{\Xi\Phi}v={\hat{v}}_{best}$ and this supports the empirical evidence that there is no clear “winner” between TD and BR.

Our main results, stated in Propositions 2 and 3, constitutes a revisit of the work of Yu & Bertsekas (2008), where the authors similarly derived error bounds for TD and BR. Our approach mimicks theirs: 1) we derive a linear relation between the projection $\hat{v}$, the real value $v$ and the best projection ${\hat{v}}_{best}$, then 2) analyze the norm of the matrices involved in this relation in terms of spectral radius of small matrices (through Lemma 1, which is taken from (Yu & Bertsekas, 2008)). From a purely quantitative point of view, our bounds are identical to the ones derived there. Two immediate consequences of this quantitative equivalence are that, as in (Yu & Bertsekas, 2008), (1) our bound is tight in the sense that there exists a worst choice for the reward for which it holds with equality, and (2) it is always better than that of Equation 3 from Bertsekas & Tsitsiklis (1996); Tsitsiklis & Van Roy (1997). However, our work is qualitatively different: by highlighting the oblique projection relation between $\hat{v}$ and $v$, not only do we provide a clear geometric intuition for both methods, but we also greatly simplify the form of the results and their proofs (see (Yu & Bertsekas, 2008) for details).

Last but not least, there is globally a significant difference between our work and the two works we have just mentionned. The analysis we propose is unified for TD and BR (and even extends to potential new methods through other choices of the parameter $X$), while the results in (Schoknecht, 2002) and (Yu & Bertsekas, 2008) are proved independently for each method. We hope that our unified approach will help understanding better the pros and cons of TD, BR, and related alternative approaches.

An Empirical Comparison

In order to further compare the TD and the BR projections, we have made some empirical comparison, which we describe now. We consider spaces of dimensions $n=2,3,..,30$. For each $n$, we consider projections of dimensions $k=1,2,..,n$. For each $(n,k)$ couple, we generate 20 random projections (through random matricesEach entry is a random uniform number between -1 and 1. $\Phi$ of size $(n,k)$ and random weight vectors $\xi$) and 20 random (uncontrolled) chain like MDP: from each state $i$, there is a probability $p_{i}$ (chosen randomly uniformly on $(0,1)$) to get to state $i+1$ and a probability $1-p_{i}$ to stay in $i$ (the last state is absorbing); the reward is a random vector. For the $20\times 20$ resulting combinations, we compute the real value $v$, its exact projection ${\hat{v}}_{best}$, the TD fix point $\hat{v}_{TD}$, and the BR projection $\hat{v}_{BR}$. We then deduce the best error $e=\|v-{\hat{v}}_{best}\|_{\xi}$, the TD error $e_{TD}=\|v-\hat{v}_{TD}\|_{\xi}$ and the BR $e_{BR}=\|v-\hat{v}_{BR}\|_{\xi}$. We also compute the bounds of Proposition 3 for both methods: $b_{TD}$ and $b_{BR}$. Each such experiment is done for 4 different values of the discount factor $\gamma$: $0.9$, $0.95$, $0.99$, $0.999$.

Using this raw data on $20\times 20$ problems, we compute for each $(n,k)$ couple some statistics, which we describe now. All the graphs that we display shows the dimension of the space $N$ and of the projected space $m$ on the $x-y$ axes. The $z$ axis correspond to the different statistics of interest.

Figure 2 shows the proportion of sampled problems where TD method returns a better approximation than BR (i.e. the expectation of the indicator function of $e_{TD}<e_{BR}$). It turns out that this ratio is consistently greater than $\frac{1}{2}$, which means that the TD method is usually better than the BR method. Figure 3 presents the ratio of time the bounds we have presented in Propostion 4 correctly guesses which method is the best (i.e. the expectation of the indicator function of $[e_{TD}<e_{BR}]=[b_{TD}<b_{BR}]$). Unless the feature space dimension is close to the state space dimension, the bounds do not appear very useful for such a decision. Figure 4 displays the expectation of $e_{TD}/e_{BR}$. One can observe that, on average, this expectation is bigger than $1$, that is the BR tends to be better, on average, than the TD error. This may look contradictory with our interpretation of Figure 2, but the explanation is the following: when the BR method is better than the TD method, it is by a larger gap than when it is the other way round. We believe this corresponds to the situation when the TD method in unstable. Figure 5 allows to confirm this point: it shows the expectation of the relative approximation errors with respect to the best possible error, that is the expectation of $e_{TD}/e$ and $e_{BR}/e$. One observes on all charts that this average relative quality of the TD fix point has lots of pikes (corresponding to numerical instabilities), while that of the BR method is smooth.

Conclusion and Future Work

We have presented the TD fix point and the BR minimization methods for approximating the value of some MDP fixed policy. We have described two original examples: in the former, the BR method is consistently better than the TD method, while the latter (which generalizes the spirit of the example of Sutton et al. (2009)) is best treated by TD. Proposition 1 highlights the close relation between the objective criteria that correspond to both methods. It shows that minimizing the BR implies minimizing the TD error and some extra “adequacy” term, which happens to be crucial for numerical stability.

Our main contribution, stated in Proposition 2, provides a new viewpoint for comparing the two projection methods, and potential ideas for alternatives. Both TD and BR can be characterized as solving a projected fixed point equation and this is to our knowledge new for BR. Also, the solutions to both methods are some oblique projection of the value $v$ and this is to our knowledge new for TD and BR. Eventually, this simple geometric characterization allows to derive some tight error bounds (Proposition 3). We have discussed the close relations of our results with those of Schoknecht (2002) and Yu & Bertsekas (2008), and argued that our work simplifies and extends them. Though apparently new to the Reinforcement Learning community, the very idea of oblique projections of fixed point equations has been studied in the Numerical Analysis community (see e.g. Saad (2003)). In the future, we plan to study more carefully this literature, and particularly investigate whether it may further contribute to the MDP context.

Concerning the practical question of choosing among the two methods TD and BR, the situation can be summarized as follows: the BR method is sounder than the TD method, since the former has a performance guarantee while the latter will never have one in general. Extensive simulations (on random chain-like problems of size up to $30$ states, and for many projection of all the possible space sizes) further suggest the following facts: (a) the TD solution is more often better than the BR solution; (b) however sometimes, TD failed dramatically; (c) overall, this makes BR better on average. Equivalently, one may say that TD is more risky than BR.

Even if TD is more risky, there remains several reasons why one may want to use it in practice, and which our study did not focus on. In large scale problems, one usually estimates the $m\times m$ linear systems through sampling. Sampling based methods for BR are more constraining since they generally require double sampling. Independently, the fact, highlighted by Propostion 1, that the BR is an upper bound of the TD error, suggests two things. First, we believe that the variance of the BR problem is higher than that of the TD problem; thus, given a fixed amount of samples, the TD solution might be less affected by the corresponding stochastic noise than the BR one. More generally, the BR problem may be harder to solve than the TD problem, and from a numerical viewpoint, the latter may provide better solutions. Eventually, we only discussed the TD(0) fix point method, that is the specific variant of TD($\lambda$) (Bertsekas & Tsitsiklis, 1996; Boyan, 2002) where $\lambda=0$. Values of $\lambda>0$ solve some of the weaknesses of TD(0): it can be show that the stability issues disappear for values of $\lambda$ close to $1$, and the optimal projection ${\hat{v}}_{best}$ is obtained when $\lambda=1$. Further analytical and empirical comparisons of TD($\lambda$) with the algorithms we have considered here (and with some “BR($\lambda$)” algorithm) constitute future research.

Eventually, a somewhat disappointing observation of our study is that the bounds of Proposition 3, which are the tightest possible bounds independent of the reward function, did not prove useful for deciding a priori which of the two methods one should trust better (recall the results showed in Figure 3). Extending them in a way that would take the reward into account, as well as trying to exploit our original unified vision of the bounds (Propositions 2 and 3) are some potential tracks for improvement.

Acknowlegments

The author would like to thank Janey Yu for helpful discussions, and the anonymous reviewers for providing comments that helped to improve the presentation of the paper.

References