temporal difference learning
In plain wordsA way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches.
Reinforcement-learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. methods that improve valuevalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board. predictions by comparing successive guesses: after each step, the estimate for the statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next. just left is nudged toward the rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time. actually received plus the discounted estimate for the state reached. The difference, the TD error δ, drives learning, so updates happen online, without waiting for an episodeepisode, n.: One complete run of a task from start to finish — a single game of chess, one attempt at a maze — after which everything resets and the agent tries again. to end and without a model of the environment. Richard Sutton and Andrew Barto's textbook presents TD as a hybrid: it learns from sampled experience, as Monte Carlo methods do, but revises estimates partly on the basis of other estimates (bootstrapping), as dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step. does. TD(λ) blends one-step and multi-step targets using eligibility traceseligibility trace, n.: A fading short-term memory of which situations and actions an agent recently experienced, so that when a reward arrives the credit can be shared among the steps that led to it., spanning the range from TD(0) to Monte Carlo at λ = 1. Control algorithms built on TD include SARSASARSA, n.: A learning method in which an agent updates the score of its last move using the reward it got and the score of the move it actually picks next, so it learns the value of its own habits., Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next. and the critics of most actor–criticactor–critic, n.: A way of training an AI agent in which one part, the 'actor', makes the moves while another, the 'critic', learns to predict how well they will work out, and the actor improves by heeding the critic. methods.
The TD error spikes when the agent unexpectedly finds the key, then shifts earlier as it learns.
Origin
Richard Sutton named and analyzed the method in 'Learning to Predict by the Methods of Temporal Differences' (Machine Learning, 1988), building on his 1984 PhD thesis and on precursors he credited: Arthur Samuel's checkers player (1959), John Holland's bucket brigade and the Adaptive Heuristic Critic he developed with Andrew Barto. Gerald Tesauro's TD-GammonTD-Gammon, prop. n.: A backgammon program built at IBM in the early 1990s that taught itself to play at near world-champion level by playing more than a million games against itself. (1992) made it famous.
Usage note
Wolfram Schultz, Peter Dayan and Read Montague (1997) showed that dopamine neurons respond like a TD error — firing for unexpected rewards and, after learning, for the cues that predict them — one of the clearest links between AI theory and neuroscience.
Related
- Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next.
- SARSASARSA, n.: A learning method in which an agent updates the score of its last move using the reward it got and the score of the move it actually picks next, so it learns the value of its own habits.
- eligibility traceeligibility trace, n.: A fading short-term memory of which situations and actions an agent recently experienced, so that when a reward arrives the credit can be shared among the steps that led to it.
- value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board.
- Bellman equationBellman equation, n.: A rule saying that how good a situation is equals the reward you get now plus how good the next situation is, slightly discounted — so long-term planning can be solved one step at a time.
- TD-GammonTD-Gammon, prop. n.: A backgammon program built at IBM in the early 1990s that taught itself to play at near world-champion level by playing more than a million games against itself.
- actor–criticactor–critic, n.: A way of training an AI agent in which one part, the 'actor', makes the moves while another, the 'critic', learns to predict how well they will work out, and the actor improves by heeding the critic.
- Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating.
- dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step.
Sources
- Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning 3(1), 9–44. link.springer.com/article/10.1007/BF00115009
- Schultz, W., Dayan, P. & Montague, P. R. (1997). A neural substrate of prediction and reward. Science 275, 1593–1599.
Mentioned in
reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time., rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time., actor–criticactor–critic, n.: A way of training an AI agent in which one part, the 'actor', makes the moves while another, the 'critic', learns to predict how well they will work out, and the actor improves by heeding the critic., Arthur SamuelArthur Samuel, prop. n.: An American IBM engineer whose checkers program improved by playing against itself, and whose 1959 paper helped make 'machine learning' the name of a field., Bellman equationBellman equation, n.: A rule saying that how good a situation is equals the reward you get now plus how good the next situation is, slightly discounted — so long-term planning can be solved one step at a time., bootstrapbootstrap, n.: Estimating how much a result might vary by repeatedly re-drawing samples, with replacement, from the data you already have — like re-running a study many times without collecting new data., credit assignment problemcredit assignment problem, n.: The puzzle of figuring out which of many earlier decisions, or which parts of a system, deserve the credit or blame for a final outcome — like working out which moves won a chess game., dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step., model-free reinforcement learningmodel-free reinforcement learning, n.: Learning to act well purely from trial and error, without ever building an internal picture of how the world works — like learning a game by habit rather than by thinking moves ahead., Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next., returnreturn, n.: The total reward an AI agent collects from now until the end of a task, usually counting near-term rewards more than distant ones. Agents are trained to make this total as large as possible., Richard BellmanRichard Bellman, prop. n.: An American mathematician who invented dynamic programming, a way of solving long chains of decisions step by step, which became the mathematical core of reinforcement learning., Richard SuttonRichard Sutton, prop. n.: A Canadian computer scientist who, with Andrew Barto, laid the groundwork for teaching machines by trial, error and reward, and whose essay 'The Bitter Lesson' argues that methods that scale with computing power always win., value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board., Andrew BartoAndrew Barto, prop. n.: An American computer scientist who, with his student Richard Sutton, laid the foundations of reinforcement learning, the study of how machines learn by trial and error from rewards., Chris WatkinsChris Watkins, prop. n.: A British computer scientist who invented Q-learning in 1989, a simple way for an agent to learn which action is best in each situation purely from trial and error., deadly triaddeadly triad, n.: The risky combination of three common ingredients in reinforcement learning — approximation, learning from guesses, and learning from other strategies' data — which together can make learning spin out of control., eligibility traceeligibility trace, n.: A fading short-term memory of which situations and actions an agent recently experienced, so that when a reward arrives the credit can be shared among the steps that led to it., generalized advantage estimationgeneralized advantage estimation, n.: A recipe for judging how much better each action was than expected by blending short-term and long-term evidence, trading a little accuracy for much steadier learning., Gerald TesauroGerald Tesauro, prop. n.: An American IBM researcher whose program TD-Gammon learned backgammon purely by playing against itself and by the early 1990s rivaled the best human players, a landmark for machines that learn by trial and error., John HollandJohn Holland, prop. n.: An American scientist who invented genetic algorithms, which solve problems by breeding and mutating populations of candidate answers, and helped found the science of complex systems., SARSASARSA, n.: A learning method in which an agent updates the score of its last move using the reward it got and the score of the move it actually picks next, so it learns the value of its own habits., target networktarget network, n.: A slowly updated copy of an AI agent's learning network, used to compute the goals it learns toward, so those goals do not shift every time the network changes., TD-GammonTD-Gammon, prop. n.: A backgammon program built at IBM in the early 1990s that taught itself to play at near world-champion level by playing more than a million games against itself.