A restaurant deciding whether to seat a small party or wait for a larger one can update its expectations as events unfold, rather than waiting until closing time. The temporal-difference (TD) error measures the gap between a current value estimate and a new target based on the immediate reward and the estimated value of the next state. section 6.1 section 6.2
For a transition from state s to s′, the state-value TD error is δ = r + γV(s′) − V(s). Here r is the observed reward, γ discounts the next-state value, and V(s) is the current estimate. A positive error calls for an upward correction; a negative error calls for a downward correction. Zero means the estimate is locally consistent with this experience. section 6.1 section 8.1
The update V(s) ← V(s) + αδ scales that correction by the learning rate α. The target includes another estimate, V(s′), so this is bootstrapping: learning can happen after each step without waiting for the episode to end. At a terminal transition, the restaurant implementation uses the reward alone as the target. section 6.1 section 6.7 section 6.2
Restaurant table scheduling
An agent repeatedly decides whether to seat a small party for $50 or wait for a larger party. It updates the estimated value for the hours remaining from each observed transition, without needing the arrival probability as an input. After 1,000 episodes, the four-hour estimate is $85.17, compared with an analytical value of $85.47; estimates at other hours still differ more substantially. section 6.2
Listing 6.2 Temporal-difference learning algorithm
def td_learning(episodes=1000, alpha=0.1, gamma=0.9):
env = RestaurantEnv()
V = np.zeros(5) #A
for episode in range(episodes):
state = env.reset()
while True:
action = 1 if state <= 1 else 0 #B
next_state, reward, done = env.step(action)
if done:
target = reward #C
else:
target = reward + gamma * V[next_state] #D
td_error = target - V[state] #E
V[state] += alpha * td_error #F
if done:
break
state = next_state
return V
The implementation shows the terminal and nonterminal targets, the TD error, and the value update together. section 6.2
The same idea applies to action values. SARSA uses the value of the next action actually taken, while Q-learning uses the best estimated next action. With linear function approximation, the TD error instead adjusts feature weights, allowing one experience to affect estimates for similar situations. section 6.4 section 8.1


