A fuel order may take days to affect sales. When its payoff arrives, TD(λ) helps assign credit to earlier decisions without waiting until the entire episode ends. It combines temporal-difference (TD) updates with eligibility traces: a short-term memory of recently visited states or state–action pairs. section 6.5 section 6.6
One-step TD updates quickly but looks only one step ahead; Monte Carlo learning waits for complete outcomes and can have high variance. TD(λ) offers a spectrum between them. Its λ parameter controls how far back credit is assigned: λ=0 corresponds to one-step TD, while λ=1 approaches Monte Carlo. Intermediate values trade bias against variance. section 6.5 section 6.7
The forward view describes a target as an exponentially weighted average of returns over different numbers of steps. Those returns depend on future experience. The backward view instead uses eligibility traces to distribute each current TD error—the discrepancy in a bootstrapped value update—across recent experience as learning proceeds. section 6.5
With eligibility traces, an agent can update at each step:
- Record the current state or state–action pair as eligible for credit. section 6.5 section 6.6
- Use the current TD error to update eligible entries, weighted by their traces. section 6.7 section 6.6
- Decay traces so more recent experience generally receives more credit than older experience. section 6.5 section 6.6
Fuel purchase scheduling
A gas station agent chooses fuel orders whose effects may take days to appear. SARSA(λ) uses the value of the next action actually chosen and sets the current trace to 1 in a replacing-trace implementation. The TD error then updates recently visited state–action pairs. Watkins’s Q(λ) instead uses the maximum next-action value and clears traces when the next action is non-greedy, preventing credit from propagating through exploratory actions. section 6.6 section 6.7
Listing 6.14 SARSA(λ) agent implementation
class SARSAEligibilityAgent(EligibilityTraceAgent):
def __init__(self, action_space_size: int, learning_rate: float,
discount_factor: float, lambda_param: float,
epsilon_start: float, epsilon_decay: float):
super().__init__(action_space_size, "SARSA(λ)", learning_rate,
discount_factor,
[CA]lambda_param, epsilon_start, epsilon_decay)
def update(self, state: EnvironmentState, action: int, reward: float,
next_state: EnvironmentState, next_action: int, done: bool):
state_key = state.to_tuple()
next_state_key = next_state.to_tuple()
current_q = self.q_table[state_key][action]
if done:
target = reward
else:
next_q = self.q_table[next_state_key][next_action] #A
target = reward + self.discount_factor * next_q
td_error = target - current_q
self.eligibility_traces[state_key][action] = 1.0 #B
self.update_traces_and_q_values(td_error) #C
Inspect the SARSA(λ) agent structure and its use of the actual next action. section 6.6
Eligibility traces make delayed credit assignment possible during learning, but λ is a choice rather than a guarantee of better performance. Use the comparison with one-step TD and Monte Carlo to reason about the desired balance between immediate updates and longer-term outcomes. section 6.5
