liveBook · Manning

TD-learning

As explained in Applied Reinforcement Learning

Temporal-difference learning updates value estimates incrementally using observed rewards and estimates of subsequent values.

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

How Applied Reinforcement Learning covers it

How deep it goes
Derives the one-step TD error and update, then implements a tabular simulation and extends the update to linear function approximation.
Examples
Works through restaurant table scheduling and compares sampled value estimates with an analytical solution.
What you can do after
Build a tabular TD learner from scratch to estimate state values from simulated experience.
How it connects
Connects bootstrapping to dynamic programming, Monte Carlo estimation, action values, SARSA, and Q-learning.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.