Temporal-difference (TD) learning updates value estimates as experience arrives, rather than waiting for a complete outcome. Like a rolling business forecast, each update combines a near-term result with a revised estimate of what lies ahead. It is useful when decisions have consequences that unfold over time. section 6.1 section 4.1
After a transition from state s to s′ with reward r, the TD target is r + γV(s′). The TD error is δ = r + γV(s′) − V(s), and the update is V(s) ← V(s) + αδ. Here γ discounts the estimated future value, while α controls the size of the correction. At a terminal state, the target is just the reward. Using an existing estimate in the target is called bootstrapping. section 6.1 section 6.2 section 6.7
TD learning is model-free: it learns from experience without knowing transition probabilities. Unlike Monte Carlo estimation, it can update before an episode ends. A state value estimates how good a state is; for model-free action selection, action values connect estimates directly to available actions. SARSA and Q-learning extend TD ideas to action values, with on-policy and off-policy learning respectively. section 6.3 section 6.7
A restaurant’s premium table
A restaurant has four hours to decide whether to seat an always-available small party for $50 or wait for a large party worth $120, arriving with 30% probability each hour. With one hour left, seating is better than waiting: $50 exceeds the $36 expected from waiting. With two hours left and a discount factor of 0.9, waiting has an analytical value of $67.50. A TD simulation instead learns state values from sampled experience under a fixed policy: wait until one hour remains, then seat the small party. Its estimates can be compared with the analytical values, though individual sampled estimates may differ. 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
Follow the restaurant simulation’s step-by-step targets, TD errors, and value updates, including its terminal-state handling. section 6.2
TD errors also support function approximation. Rather than updating a single table entry, a linear model adjusts feature weights using the error, so one experience can influence estimates for multiple state–action pairs. section 8.1
