Eligibility Traces in Reinforcement Learning

A reinforcement-learning system may need to connect two events separated in time: an earlier synaptic event and a later reinforcement signal. The central question is how the system can preserve enough information about the earlier event for the later reward to affect the appropriate synapse. Miller's 1981 Law-of-Effect-like proposal addressed this problem with synaptically local contingent eligibility traces.

In Miller's proposal, eligibility is local to a synapse. An earlier sensory or synaptic event does not immediately need to produce the final learning change. Instead, that event can leave the synapse temporarily eligible. If a reinforcement signal arrives afterward, the signal can be related to the synapse that was previously marked. The trace therefore addresses temporal credit assignment: it helps connect a later outcome with an earlier event.

Miller's proposal also included a sensory analyzer unit with a critic-like role. The important function is not merely sensing input. The analyzer supplied reinforcement signals to neurons, providing the signal that could guide changes at synapses that had become eligible. This anticipates a central feature later associated with actor-critic architectures: one part of the system contributes behavior, while a critic-like mechanism supplies information related to reinforcement.

Seung's hedonistic synapse gives the learning problem a synapse-level interpretation. The synapse changes its neurotransmitter release probability according to which event is followed by reward: release or failure to release. The relevant distinction is between synaptic activity and the probability of the synapse's future neurotransmitter release. A hedonistic synapse therefore expresses learning as a reward-dependent change in release probability, rather than treating every synaptic event as an identical outcome.

The shared question across these ideas is how to connect a past event with a later reinforcement signal. The source connects Miller's proposal with the general features of reward-modulated STDP and connects the later actor-critic architecture with TD error. The useful comparison is therefore structural: an earlier synaptic or behavioral event is related to an eligibility-like record, a later reward-related signal arrives, and learning uses the relationship between the two. This relationship should not be mistaken for proof that all three approaches implement the same mechanism.

Bacterial chemotaxis belongs here as a metaphor for the problem of using consequences to guide future behavior. It should not be confused with the neural learning mechanisms themselves. The mechanisms discussed in this article are eligibility traces, reinforcement signals, reward-dependent synaptic release probability, reward-modulated STDP, and actor-critic use of TD error. The metaphor helps frame the learning question; it does not replace the variables and synaptic mechanisms used in those proposals.

Miller's proposal described a synapse keeping a temporary record so that a later reward could still change it. The same idea is used today in temporal-difference learning, where it is called an eligibility trace. A one-step method, TD(0), updates only the state it has just left, so a reward at the end of a long chain takes many episodes to reach the start. A trace lets one reward update every recently visited state at once.

Each state s has a trace e(s), a number that is 1 when the state is visited and then shrinks by a factor of γ λ on every following step. The parameter λ (lambda), between 0 and 1, sets how long the memory lasts. After each step the algorithm computes one TD error and applies it to every state in proportion to its trace.

The first update shrinks the trace of every state, the second adds 1 to the state just visited, and the third moves every state's value by the TD error times that state's own trace.

At the two ends of the range the method is familiar. With λ = 0 the trace vanishes after one step and the update is TD(0). With λ = 1 the trace decays only by γ and the combined updates over an episode match the Monte Carlo update, which waits for the full return.