Bertsekas (1995a) proposes a counterexample to the use of temporal difference methods for approximating value functions in the context of Markov chains and suggests that his results extend to the domain of Markov decision processes as well. Bertsekas uses a least-squares error with respect to the value function as the metric for evaluating the functions learned by TD(1) and TD(0). In the counterexample, the function learned by TD(0) is inferior to that learned by TD(1) when using this metric. However, we observe that other metrics produce different results.

Bertsekas’ examples are Markov chains with states 0,1,2,...,n. Each transition returns a reinforcement with the exception of state 0, which is cost-free and absorbing and is eventually reached from every other state. For each initial state x the objective is to estimate the expected total return V*(x) received when following a series of transitions from state x to the terminal state.

(0)

(1)

(2)

Noting that TD(1) finds a function that approximates the value function V* directly and TD(0) finds a function V in which approximates , we can better evaluate the empirical results Bertsekas presented.

The following two examples are identical to the examples presented in Bertsekas (1995a). We use a linear function approximator of the form V(x,w)=xw . The weight w was calculated exactly rather than approximated in simulation. The state transitions and associated reinforcements are deterministic. From state x we move to state x-1 with a given reinforcement r_x. All simulation runs start at state n and end at state 0 after visiting all the states n-1, n-2,...,1 in succession. The temporal difference associated with the transition from x to x-1 is r_x+V(x-1,w)-V(x,w)=r_x-w and the gradient is .

Figure 1 shows the value function V* and the functions learned by TD(1) and TD(0) for n=50 and for r₁=1, r_x=0 for all x1.

Figure 1: The optimal value function V* and the functions learned by TD(1) and TD(0) for the case r₁=1, r_x=0 for all x1. The function learned by TD(1) is a better approximation to V* than is TD(0) according to the 2-norm.

Figure (3) shows the value function V* as well as the functions learned by TD(1) and TD(0), respectively, for n=50 and for r_n=-(n-1), r_x=1 for all xn.

Figure 3: The optimal value function V*, and the functions learned by TD(1), direct TD(0), and residual gradient TD(0) for the case r_n=-(n-1), r_x=1 for all xn. V_TD(1) is the best approximation to V* according to the weighted or unweighted 2-norm.

Residual algorithms should be used if one prefers the weighting of states be a function of only the frequency with which a state is trained, and not a function of both the frequency with which a state is trained and the derivative of the value function with respect to the given state. Residual gradient TD(0) is an algorithm that weights the temporal error in a given state based solely on how often that state is visited. This update is presented in equation (6) and is the equivalent of residual gradient value iteration. The function learned by residual gradient TD(0), for the case where n=50, r_n=-(n-1), and r_x=1 for all xn., is also presented in Figure (3).

(6)

Figure (4) shows as well as , , and for this example. In Figure (4) we can see that the function learned by direct TD(0) is disproportionately influenced by the s in the higher (earlier) states, while residual gradient TD(0) weights the temporal difference errors equally.

Figure 4: and the functions learned by direct TD(0) and residual gradient TD(0) respectively for the case r_n=-(n-1), r_x=1 for all xn. =-49 when x=50. is the best approximation to according to the unweighted 2-norm and is the best approximation according to the weighted 2-norm.

Figure (5) depicts the following MDP. The state x is a two element vector {x₁,x₂}. In state {0,0} are two possible actions: transition to state {0,1}, or transition to state {1,0}. Each action leads to a Markov chain. The states succeeding state {0,0} are labeled [{0,1},{0,2},...,{0,n}] and [{1,0},(2,0},...{n,0}]. We assume that states {0,n} and {n,0} yield a return of 0 and are absorbing.

Figure 5: MDP with reinforcements r_{0,0}{1,0}=-1, r_{0,0}{0,1}=-2, r_{99,0}=-192, r_{0,99}=0, r_{x,0}=4, {{0,0},{99,0}}, and r_{0,x}=2, {{0,0} ,{0,99}}.

We use a linear approximation of the form V(x,w)=x₁w₁+x₂w₂. The optimal weights were calculated exactly. For this MDP, direct TD(0) and residual gradient TD(0) learned functions that yield the optimal policy: when in state {0,0}, transition to state {1,0}. TD(1) learned a function that yields the wrong policy: when in state {0,0}, transition to state {0,1}.

In Figures (6) and (7) it can be seen that TD(1) learned a function that is a better approximation of the value function V* than did either direct TD(0) or residual gradient TD(0), yet TD(1) yields a policy that is inferior to the policies generated when using either direct TD(0) or residual gradient TD(0). Also, in Figure (6) it can be seen that the function learned by TD(0) was affected by the disproportionately large derivative in state {99,0}, while residual gradient TD(0) equally weighted the temporal difference errors in all states. In Figure (7) it can be seen that the functions provided by direct TD(0) and residual gradient TD(0) are almost identical. In this case, the derivative in state {0,99} is 0 for direct TD(0), and therefore had little effect on the approximation. In Figure (7), it is clear that direct TD(0) and residual gradient TD(0) generated functions and that closely approximated .

In Bertsekas’ example TD(0) appeared worse than TD(1), but that is only the case when considering the 2-norm of the value function error. With respect to the difference in values TD(0) appears better than TD(1). These "differences" represent the degree to which the value function fails to satisfy the Bellman equation. It is not clear which metric should be used. For our example, the salient information associated with a state is not the accuracy of the approximation to the value function, but the accuracy of the approximation of the difference in the values of adjacent states. In other words, the information contained in the difference in the values of adjacent states is most relevant for making control decisions. TD(1) attempts to approximate the absolute value of each state. Both direct and residual gradient TD(0) attempt to find approximations of the optimal value function by learning a function whose differences approximate the differences of the optimal value function while simultaneously approximating the value of the terminal states. However, the function learned by direct TD(0) is also affected by a disproportional weighting of the temporal errors in different states. Direct TD(0) weights each state proportional to the frequency with which it is trained and the magnitude of . TD(1) and residual gradient TD(0) weight each state based solely on the frequency with which it is trained.

This research was supported under Task 2312 R1 by the United States Air Force Office of Scientific Research.