eligibility trace
In plain wordsA 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.
A decaying record, kept for each 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. or parameter, of how recently and how often it was visited or contributed to an output, used to spread each TD errortemporal difference learning, n.: A 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. backward over the steps that preceded it. At each step every trace decays by a factor γλ and the trace of the current state (or the gradient of the current value estimate) is incremented; each weight is then updated in proportion to the TD error times its trace. This implements the 'backward view' of TD(λ), which for offline updating is equivalent to learning toward the λ-return, a geometrically weighted average of n-step returns, interpolating between one-step TD (λ = 0) and Monte Carlo methods (λ = 1). Traces speed credit assignmentcredit 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. for delayed rewards; they appear in 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.(λ) and Watkins's Q(λ), and the same weighting reappears in 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..
With λ = 0.9 the eligibility trace lets the goal reward update states visited dozens of steps earlier.
Origin
The notion of synaptic 'eligibility' comes from A. Harry Klopf's theory of goal-seeking 'hedonistic' neurons (1972; book 1982). Richard Sutton and Andrew Barto built traces into adaptive-element models from the late 1970s, and their 1981 Psychological Review paper is probably the first use of the term 'eligibility trace'. Their 1983 pole-balancing actor–critic system with Charles Anderson and Sutton's 1988 TD(λ) paper made traces a standard part of RL.
Related
- temporal difference learningtemporal difference learning, n.: A 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.
- 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.
- 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.
- 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.
- 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.
- 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.
Sources
- Sutton, R. S. & Barto, A. G. (1981). Toward a modern theory of adaptive networks: Expectation and prediction. Psychological Review 88(2), 135–170.
- Barto, A. G., Sutton, R. S. & Anderson, C. W. (1983). Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics SMC-13(5), 834–846.
- Klopf, A. H. (1982). The Hedonistic Neuron: A Theory of Memory, Learning, and Intelligence. Hemisphere.
Mentioned in
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., temporal difference learningtemporal difference learning, n.: A 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., 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., 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.