Temporal difference learning revisited

We have presented temporal difference (TD) procedures as a way of solving the multi-step prediction problem with a linear function approximation. In Chapter 4, we revisited the TD procedures in light of the Bellman equations and their operators. However, the initial TD procedures introduced by Sutton (1988) were not derived by directly optimising some objective function. The literature on TD methods has mainly ignored the problem of convergence to the true solution, apart from articles by Barnard (1993), who showed that TD(λ) methods were not true gradient descent methods, resulting in narrow convergence and instability, and by Baird (1995), who showed that these methods could not guarantee convergence when they were used with off-policy training. Several non-gradient descent approaches to this problem have been developed, but none have been completely satisfactory. For example, Bradtke and Barto (1996) introduced least squares temporal difference (LSTD) as a second-order method to guarantee stability, but at high computational cost. The theoretical understanding of the optimisation objective in both the linear and non-linear function approximation settings came later. For instance