Temporal difference learning

Temporal difference (TD) learning refers to a class of model-free reinforcement learning methods which learn by bootstrapping from the current estimate of the value function. These methods sample from the environment, like Monte Carlo methods, and perform updates based on current estimates, like dynamic programming methods. While Monte Carlo methods only adjust their estimates once the outcome is known, TD methods adjust predictions to match later, more-accurate predictions about the future, before the outcome is known. This is a form of bootstrapping, as illustrated with the following example: Suppose you wish to predict the weather for Saturday, and you have some model that predicts Saturday's weather, given the weather of each day in the week. In the standard case, you would wait until Saturday and then adjust all your models. However, when it is, for example, Friday, you should have a pretty good idea of what the weather would be on Saturday – and thus be able to change, say, Saturday's model before Saturday arrives. Temporal difference methods are related to the temporal difference model of animal learning.

Temporal difference (TD) learning refers to a class of model-free reinforcement learning methods which learn by bootstrapping from the current estimate of the value function. These methods sample from the environment, like Monte Carlo methods, and perform updates based on current estimates, like dynamic programming methods. While Monte Carlo methods only adjust their estimates once the outcome is known, TD methods adjust predictions to match later, more-accurate predictions about the future, before the outcome is known. This is a form of bootstrapping, as illustrated with the following example: Suppose you wish to predict the weather for Saturday, and you have some model that predicts Saturday's weather, given the weather of each day in the week. In the standard case, you would wait until Saturday and then adjust all your models. However, when it is, for example, Friday, you should have a pretty good idea of what the weather would be on Saturday – and thus be able to change, say, Saturday's model before Saturday arrives. Temporal difference methods are related to the temporal difference model of animal learning. V^\pi(s) = E_{a \sim \pi}\left\{\sum_{t=0}^\infty \gamma^tR_{t+1}\Bigg| S_0=s\right\}. We drop the action from the notation for convenience. V^\pi satisfies the Bellman Equation: V^\pi(s)=E_{\pi}\{R_1 + \gamma V^\pi(S_1)|S_0=s\}, so R_1 + \gamma V^\pi(S_1) is an unbiased estimate for V^\pi(s) . This observation motivates the following algorithm for estimating V^\pi . The algorithm starts by initializing a table V(s) arbitrarily, with one value for each state of the MDP. A positive learning rate \alpha is chosen. We then repeatedly evaluate the policy \pi , obtain a reward r and update the value function for the current state using the rule: V(S_t) \leftarrow (1 - \alpha) V(S_t) + \underbrace{\alpha}_{\text{learning rate}} [ \overbrace{R_{t+1} + \gamma V(S_{t+1})}^{\text{The TD target}} ] where S_t and S_{t+1} are the current and next states, respectively. The value R_{t+1} + \gamma V(S_{t+1}) is known as the TD target, and R_{t+1} + \gamma V(S_{t+1}) - V(S_t) is known as the TD error. The lambda ( \lambda ) parameter refers to the trace decay parameter, with 0 \leqslant \lambda \leqslant 1 . Higher settings lead to longer lasting traces; that is, a larger proportion of credit from a reward can be given to more distant states and actions when \lambda is higher, with \lambda = 1 producing parallel learning to Monte Carlo RL algorithms. ==Notes== ===Works cited=== ==Further reading== See final chapter and appendix. ==External links== Connect Four TDGravity Applet (+ mobile phone version) – self-learned using TD-Leaf method (combination of TD-Lambda with shallow tree search) Self Learning Meta-Tic-Tac-Toe Example web app showing how temporal difference learning can be used to learn state evaluation constants for a minimax AI playing a simple board game. Reinforcement Learning Problem, document explaining how temporal difference learning can be used to speed up Q-learning TD-Simulator Temporal difference simulator for classical conditioning

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375126803 under CC BY-SA 4.0; modifications have been made.