Reinforcement Learning · One focused lesson
Monte Carlo waits for a completed journey. Temporal-difference learning starts from one transition.
Reading tips and color key
Start with the explanation and experiment. Open the symbol cards when you want the details. Teal: probabilities; blue: states; orange: actions; green: rewards; purple: values; gray: parameters and settings; crimson: losses and errors. Written labels give every symbol its role.
08 · When the rulebook is missing
Monte Carlo and temporal-difference learning
Why use it? The world gives experience instead of a complete transition model.
How does it work? Monte Carlo waits for the whole return. TD uses one reward plus a next-state estimate.
What does it give you? Both estimate a fixed policy’s value; changing action selection adds a control problem.
When does it struggle? MC waits and may have high variance. TD learns sooner, but bootstrapping carries errors from other estimates. Neither wins in every environment.
You could finish a trip, count all the points, and update your opinion of its starting tile. Or you could make one move and revise your opinion using the next tile’s current estimate. These are two different ways to build a learning target.
Monte Carlo prediction: finish, then average
Follow a fixed policy through complete episodes. For a chosen state, record the return following its first visit in each episode that reaches it. Average those returns to estimate the state’s value. This is first-visit Monte Carlo prediction.
Start s → … → finish
Journey 1 return
4
Start s → … → finish
Journey 2 return
7
Start s → … → finish
Journey 3 return
1
↓ Add returns 4 + 7 + 1 = 12 → divide by 3 journeys → value estimate 4
Each box contains a complete return from the same state under the same policy. The summation sign adds the boxes; the denominator counts them.
Equation anatomy · use completed sampled returns · show / hide
| Symbol | Meaning and kind | Form | Random? | Possible values | In code |
|---|---|---|---|---|---|
| \({\color{#172337}{\widehat{\color{#7542b0}{V}}({\color{#1d4ed8}{s}})}}\); \({\color{#172337}{\color{#1d4ed8}{s}}}\) | Estimated state value; selected state | Scalar table entry; state ID | Estimate varies across datasets; s fixed | Real returns; valid state | V[state] |
| \({\color{#172337}{\color{#087444}{g}}^{({\color{#525968}{i}})}({\color{#1d4ed8}{s}})}\) | Observed return after first visit in sampled episode i | Scalar sample | Recorded realization of a random return | Real reward units | episodeReturnFromFirstVisit |
| \({\color{#172337}{\color{#525968}{N}}({\color{#1d4ed8}{s}}),{\color{#525968}{i}}}\); \({\color{#172337}{\sum}}\) | Number of recorded returns; index; sum | Integers; operator | Fixed for collected data | \({\color{#172337}{\color{#525968}{N}}({\color{#1d4ed8}{s}})\ge1;\ 1\le {\color{#525968}{i}}\le {\color{#525968}{N}}({\color{#1d4ed8}{s}})}\) | V[s] += (G-V[s])/count[s] |
Recorded returns 4, 7, and 1 give a value estimate of 4. MC does not bootstrap: its target uses actual later rewards, not an estimated later value. It must wait for a complete return and can be noisy when journeys vary greatly. Basic prediction evaluates a policy; additional action selection and improvement turn it into control.
TD(0): learn after one transition
The next reward plus the next state’s estimate is a target available immediately. The difference between target and current prediction is the TD error. Move a controlled fraction toward that target.
Equation anatomy · target → error → update · show / hide
| Symbol | Meaning and kind | Form | Random? | Possible values | In code |
|---|---|---|---|---|---|
| \({\color{#172337}{\color{#7542b0}{V}},{\color{#7542b0}{V}}({\color{#1d4ed8}{S}}_{\color{#525968}{t}}),{\color{#7542b0}{V}}({\color{#1d4ed8}{S}}_{{\color{#525968}{t}}+1})}\) | Current estimate table and two selected entries | Vector; scalar lookups | Table fixed during this update; selected entries depend on trajectory | Real values | V[s], V[next] |
| \({\color{#172337}{\color{#1d4ed8}{S}}_{\color{#525968}{t}},{\color{#1d4ed8}{S}}_{{\color{#525968}{t}}+1}}\); \({\color{#172337}{\color{#087444}{R}}_{{\color{#525968}{t}}+1}}\) | Current/next state and observed reward | State IDs; scalar reward | Trajectory random; observed values now known | Valid states; real reward | {state,next,reward} |
| \({\color{#172337}{\color{#7542b0}{y}}_{\color{#525968}{t}}}\); \({\color{#172337}{\color{#ae2455}{\delta}}_{\color{#525968}{t}}}\) | One-step target; target minus prediction | Scalars | Random across transitions; fixed for this update | Real numbers; error may be negative or positive | error = target-V[s] |
| \({\color{#172337}{\color{#525968}{\alpha}},{\color{#525968}{\gamma}},{\color{#525968}{t}}}\); \({\color{#172337}{\leftarrow}}\) | Learning rate, discount, time; replace stored value | Two settings; index; assignment | Fixed here | \({\color{#172337}{0\lt {\color{#525968}{\alpha}}\le1;\ 0\le{\color{#525968}{\gamma}}\lt 1;\ {\color{#525968}{t}}\ge0}}\) | V[s] += alpha*error |
Try the numbers. Old value 4, reward 2, next estimate 10, discount 0.9: target 11, error 7. With learning rate 0.2, the new value is 4 + 0.2 × 7 = 5.4. It moves toward 11 rather than replacing itself with 11.
Build the target
2 + 0.9 × 10 = 11
Measure the gap
11 − 4 = 7
Move one fifth
0.2 × 7 = 1.4
New value = 4 + 1.4 = 5.4. The target borrows a next-state estimate; MC’s target waits for the journey’s actual remaining rewards.
TD learns sooner by borrowing an estimate. That borrowing is bootstrapping, and a poor next estimate can mislead the update. For a true terminal transition, use next value zero. A mere collection cutoff may need a continuation estimate; treating it as terminal changes the task.
Be First to Comment