*** Welcome to piglix ***

Temporal difference learning


Temporal difference (TD) learning is a prediction-based machine learning method. It has primarily been used for the reinforcement learning problem, and is said to be "a combination of Monte Carlo ideas and dynamic programming (DP) ideas." TD resembles a Monte Carlo method because it learns by sampling the environment according to some policy, and is related to dynamic programming techniques as it approximates its current estimate based on previously learned estimates (a process known as bootstrapping). The TD learning algorithm is related to the temporal difference model of animal learning.

As a prediction method, TD learning considers that subsequent predictions are often correlated in some sense. In standard supervised predictive learning, one learns only from actually observed values: A prediction is made, and when the observation is available, the prediction mechanism is adjusted to better match the observation. As elucidated by Richard Sutton, the core idea of TD learning is that one adjusts predictions to match other, more accurate, predictions about the future. This procedure is a form of bootstrapping, as illustrated with the following example:

Mathematically speaking, both in a standard and a TD approach, one would try to optimize some cost function, related to the error in our predictions of the expectation of some random variable, E[z]. However, while in the standard approach one in some sense assumes E[z] = z (the actual observed value), in the TD approach we use a model. For the particular case of reinforcement learning, which is the major application of TD methods, z is the total return and E[z] is given by the Bellman equation of the return.

In a Markov decision process, temporal difference aims to estimate the state value function following a policy , . Temporal difference achieve it by value iteration, that is, in each step, old estimates are updated by observed immediate reward. In tabular TD, estimates values are store in a table indexed by states. The update rule is:


...
Wikipedia

...