Foundations of value-based RL: a family tree and a Q table

One selected branch, not all of RL: value-based methods from the trial-and-error idea (1898) to DQN (2015). Arrows: which problem led to which fix, not a strict line of descent. Years: first publication (DQN: preprint and Nature).

The drawing starts with one branch of reinforcement learning, the value-based methods that learn a score for each choice, from the trial-and-error idea in 1898 to DQN in 2015. Each later method fixes something an earlier one does badly. Then we'll follow Q-learning on a small grid, where you can replay a real run one update at a time.

A value predicts future reward. A state value tells you what to expect from a situation, while an action value, written $Q(s,a)$ , tells you what to expect after action $a$ in state $s$ . A policy chooses actions.

Part 1. Previously: the problems behind the methods.

A value-based family tree, one problem at a time

Each numbered branch names something the parent method can't do well, then points to a method that changes that mechanism. Monte Carlo, for example, waits until the episode ends to use its full return, and Q-learning replaces that unfinished tail with a guess. Learning from the gap between one guess and the next is temporal-difference (TD) learning. A blue node names the part of the series that works through it, and the map comes from my game Breaking Bellman.

Tap a branch number for its problem, or a method for a card with its dates and a checked quote. On a phone, the tree turns into a list that you scroll inside the drawing.

Is this all of classical RL? No. Most of these nine are the table methods in the first part of Sutton and Barto's textbook, and DQN carries Q-learning over to a neural network. The tree leaves out actor-critic methods, policy gradients such as PPO, SAC, model-based RL, offline RL and RLHF. You'd run the table versions as they are only on problems small enough for a table, like this grid. DQN runs whole, with later add-ons such as Double DQN. In bigger methods they live on as parts: PPO estimates advantages from TD errors, and TD3 and SAC keep replay, target networks and a second Q estimate.

1. A lucky first result can trap a greedy choice

The first payout is a noisy clue, not the machine’s true average. If you always pick the largest estimate, one lucky result can keep you on the worse machine; ε-greedy exploration keeps trying alternatives.

First two pulls. Machine B has the higher true average, but A looks better so far.

2. The reward arrives after the choices that earned it

A win at the end tells you the whole attempt worked, but it does not say which earlier choices helped. Monte Carlo uses the completed return to teach those earlier states and actions, rather than crediting only the last move.

A four-move corridor: three ordinary moves pay zero; the final move pays +1. The earlier choices still matter.

3. Waiting for a complete outcome delays learning

Monte Carlo needs the episode to finish before its full return is available. A long episode delays those updates, while a continuing task may never supply an ending; Q-learning can update from one transition by using a guess for what follows. Part 2 shows the waiting and backward credit step by step.

At step 3 of a 10,000-step episode, a completed-return update still waits. A one-step update can already use the transition just observed.

4. One-step backups can move a late reward slowly

An early one-step update reads the next state’s current estimate, which may still be zero. In this forward-only chain, starting with every action-value estimate Q at zero, step size α = 1 and discount γ = 1, the +1 moves back one cell per episode. An n-step target can bridge several transitions in one backup.

Forward-action values with deterministic forward visits, initial Q = 0 and α = γ = 1.

5. The greedy target can miss the risk of exploratory moves

Q-learning’s max asks what happens after the best next choice, even when your behavior sometimes takes a random one. Near a cliff, that difference can be expensive; Sarsa values the behavior actually followed, including its exploratory risk.

From the same state, the greedy move stays safe while one exploratory move falls. Sarsa's target includes the risk of those exploratory actions.

6. Sampling one next action adds noise to the target

Here Q is the action-value estimate and γ is the discount. Even with the same next state and unchanged Q values, Sarsa’s target changes with the action you happen to sample. Expected Sarsa averages over the known action probabilities, removing this source of noise; random rewards and transitions can still vary.

With reward 0 and γ = 1, a sampled target can be 1, 5 or 9. The policy-weighted target is 5.

7. The largest noisy estimate often won by getting lucky

When estimates wobble around the truth, taking the maximum tends to select positive errors. Double Q-learning lets one estimate choose the action and another score it, reducing this maximization bias.

All three true action values are 0. The picked +0.9 is noise; a separate estimate can score that same action differently.

8. A table cannot cover a large state space

A table learns a separate entry for every state and action, so a new image can mean another unvisited row. DQN uses a neural network with shared weights to predict Q values from the observation, allowing related inputs to share learning. That generalization can help, but it can also be wrong.

A table leaves an unseen observation blank. Shared network weights connect predictions for related observations.

The nine methods: dates, context and a checked quote

Tap a method in the tree to open its card, or read them all here. Each card gives two dates where they differ: when the idea was first published, and when it was shown to work, proved or named. Every quote was checked against the original text on 22 October 2026.

Trial and error

Puzzle-box experiments published 1898 · classic statement of the Law of Effect 1911 (Edward Thorndike). The idea itself is older.

Keep what was followed by a good result and drop what was followed by a bad one. Thorndike named this the Law of Effect after watching cats learn to escape puzzle boxes.

What it fixes. Nobody has to show the right answer. The result itself is the teacher.

Where it still fails. It doesn’t say when to try something new instead of repeating what worked (branch 1), or which earlier action earned a result that arrives late (branch 2).

“Of several responses made to the same situation, those which are accompanied or closely followed by satisfaction to the animal will, other things being equal, be more firmly connected with the situation, so that, when it recurs, they will be more likely to recur …”

Edward L. Thorndike, Animal Intelligence: Experimental Studies (Macmillan, 1911), p. 244. Source

ε-greedy exploration

Idea in Watkins’s 1989 thesis, and earlier use is likely · the name in print by 1996 (Richard Sutton)

Usually take the action with the best current estimate, but a small fraction ε of the time pick one at random. Every action keeps getting tried, so a lucky early estimate can still be corrected.

What it fixes. A greedy learner that locks onto whatever looked good first (branch 1).

Where it still fails. With a fixed ε, it explores at the same rate forever, and its random tries ignore what the learner already knows.

“In our experiments, actions were selected according to what we call the ε-greedy policy.”

Richard S. Sutton, “Generalization in Reinforcement Learning: Successful Examples Using Sparse Coarse Coding”, NIPS 8 (1996), p. 1039. Source

Monte Carlo control

Averaged returns as action values 1968 (Michie and Chambers, BOXES) · Monte Carlo ES, an early explicit Monte Carlo control method, 1998 (Sutton and Barto, first edition)

Play an episode to the end, then move each action’s value toward the average of the full returns that followed it. There is no model and no guessing: every target is a real outcome.

What it fixes. Credit for a reward that arrives late (branch 2). The whole return reaches every earlier choice.

Where it still fails. Nothing updates until the episode ends, which is slow for long episodes and impossible when an episode never ends (branch 3).

“Only on the completion of an episode are value estimates and policies changed.”

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (MIT Press, 2018), chapter 5. Source

Q-learning

Proposed 1989 with an outline of a convergence proof (Chris Watkins, PhD thesis) · proved in detail 1992 (Watkins and Dayan)

Update after every step, using the reward you just got plus the discounted best value of the next state. It learns the value of the greedy policy while the agent explores, which makes it off-policy.

What it fixes. Waiting for the episode to end (branch 3).

Where it still fails. One-step backups move a late reward slowly (4). The values ignore the agent’s own exploratory slips, so it walks the cliff edge (5). The max over noisy estimates runs high (7), and a table needs a row for every state (8).

“Although this is a very simple idea, it has not, as far as I know, been suggested previously.”

In his next sentence, Watkins added that someone had probably considered it before.

Christopher J. C. H. Watkins, Learning from Delayed Rewards, PhD thesis, University of Cambridge (1989), p. 96. Source

n-step TD (temporal difference)

Proposed 1989 (Watkins, PhD thesis), a year after TD(λ) (Sutton, 1988) · shown practical by Cichosz (1995) and van Seijen (2016)

TD stands for temporal difference: the update learns from the gap between a prediction now and a later one. n-step TD uses n real rewards, then one guess for the rest. With n = 1 you get the one-step update. With n long enough to reach the end, you get Monte Carlo.

What it fixes. One-step backups that pass a late reward back one state per update (branch 4).

Where it still fails. Each update waits n steps, and when those rewards come from a different policy (replayed or off-policy data) they need corrections.

TD and dopamine. Wolfram Schultz’s lab recorded dopamine neurons in monkeys in the 1980s and early 1990s: they fire more when a reward is better than predicted, hold steady when it arrives as predicted, and fire less when it is worse. In 1996 Montague, Dayan and Sejnowski proposed the one-step TD error as a model of that signal. The TD part shows in two details: after training, the burst moves from the reward to the cue that predicts it, and a missing reward causes a dip at the time the reward was due. It’s a strong model of one dopamine signal, not a copy of the brain. Dopamine neurons also respond to novel stimuli, their role in punishment is still debated, mouse recordings suggest they encode a spread of possible rewards, and a 2022 study argues that dopamine release in one pathway signals learned causes of reward, not prediction errors.

“n-step methods span a spectrum with MC methods at one end and one-step TD methods at the other. The best methods are often intermediate between the two extremes.”

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (MIT Press, 2018), chapter 7. Source

Dopamine: Montague, Dayan and Sejnowski, J. Neurosci. 16 (1996), abstract and introduction (PDF); Schultz, Dayan and Montague, Science 275 (1997), p. 1594 (PDF); Sutton and Barto, §§15.3 and 15.4; Dabney et al., Nature 577 (2020) abstract (PMC); Jeong et al., Science 378 (2022) abstract (PMC).

Sarsa

Proposed 1994 (Gavin Rummery and Mahesan Niranjan, Cambridge technical report, whose footnote credits the name SARSA to Rich Sutton) · used as the method’s name by Sutton in a 1996 paper

Move the estimate toward the value of the action the agent really takes next, exploratory moves included. It learns the value of the policy it follows, which makes it on-policy.

What it fixes. A greedy target that ignores the risk of exploratory moves (branch 5). On the cliff it learns the longer, safer path.

Where it still fails. The target depends on one sampled next action, so it is noisy (branch 6), and it reaches the optimal policy only if exploration fades over time.

“Though Rich Sutton suggests SARSA, as you need to know State-Action-Reward-State-Action before performing an update.”

G. A. Rummery and M. Niranjan, “On-line Q-learning using connectionist systems”, Technical Report CUED/F-INFENG/TR 166, Cambridge University Engineering Department (1994), p. 6, footnote 3. Source

Expected Sarsa

Proposed 1994 (George John, AAAI-94 student abstract, as “Q̄-learning”) · analyzed and tested 2009 (van Seijen, van Hasselt, Whiteson and Wiering)

Replace the one sampled next action with the average over all next actions, weighted by how likely the current policy is to take each one.

What it fixes. The noise from sampling one next action (branch 6), while keeping Sarsa’s awareness of exploration.

Where it still fails. It needs the probability of every next action. That is easy for ε-greedy over four moves and hard for large or continuous action sets.

“That is, update V̂(x) with the expected, not the maximal, future reward, taking into account the exploration policy when calculating the expected reward.”

George H. John, “When the Best Move Isn’t Optimal: Q-learning with Exploration”, Proceedings of AAAI-94 (Student Abstracts), p. 1464. Source

Double Q-learning

Proposed and tested 2010 (Hado van Hasselt, NIPS 23)

Keep two estimates. One picks the best next action and the other says what that action is worth, so a lucky overestimate in one is not automatically trusted. Watkins had already warned in his 1989 thesis (p. 177) that taking the maximum of estimates is “dubious statistical practice”.

What it fixes. Maximization bias: the largest of several noisy estimates tends to come out too high (branch 7).

Where it still fails. It can underestimate instead, and each estimate learns from only half of the updates.

“These overestimations result from a positive bias that is introduced because Q-learning uses the maximum action value as an approximation for the maximum expected action value.”

Hado van Hasselt, “Double Q-learning”, Advances in Neural Information Processing Systems 23 (2010), abstract. Source

DQN (Deep Q-Network)

arXiv preprint 2013 (Mnih et al.: replay, no target network yet) · Nature 2015 (49 Atari games, adds the target network)

Q-learning with a deep convolutional network that reads raw screen pixels. Random samples from a replay memory and, in the 2015 version, a periodically frozen copy of the network for the targets keep training stable.

What it fixes. A table that needs a separate row for every state (branch 8).

Where it still fails. It still overestimates values, needs many samples (50 million frames per game in 2015) and handles only discrete actions. Parts 3 and 5 show why bootstrapping, a shared network and replayed data together can diverge.

“We present the first deep learning model to successfully learn control policies directly from high-dimensional sensory input using reinforcement learning.”

Volodymyr Mnih et al., “Playing Atari with Deep Reinforcement Learning”, arXiv:1312.5602 (2013), abstract. Source

Where the tree stops

The tree follows the action-value line only, from Thorndike’s puzzle-box experiments (1898) to DQN (arXiv 2013, Nature 2015). The deep-RL refinements it leaves out start in 2015, among them Double DQN. The cut is a choice of branch as much as of years: actor-critic methods (1983) and REINFORCE (1992) are older than Sarsa and are not in it either.

“Classical RL” has no fixed boundary, so the tree makes no claim to cover it. Seven of its nine methods are in Part I of Sutton and Barto, which covers problems small enough for “the approximate value functions to be represented as arrays, or tables”. Trial and error comes from the book’s history section, and DQN from its applications chapter (§16.5).

What is still in use

The arrows do not claim that later methods descend from these nine, but several of their mechanisms run inside newer methods. PPO’s advantage estimate is a sum of TD errors δ_t = r_t + γV(s_t+1) − V(s_t), each weighted by a power of γλ (Schulman et al., 2017, Eqs. 11 and 12). TD3 keeps a replay buffer and target networks, and trains its two critics with “a novel clipped variant of Double Q-learning” (Fujimoto et al., 2018, §4.2). SAC samples from a replay buffer, uses a target value network, and “makes use of two Q-functions to mitigate positive bias”, citing Double Q-learning (Haarnoja et al., 2018, §4.2).

Not shown: actor-critic (Barto, Sutton and Anderson, 1983), Dyna (1990) and other model-based RL, REINFORCE (1992) and the policy gradient theorem (1999), TRPO (2015), DDPG (2015), PPO (2017), SAC and TD3 (2018); Double DQN, prioritized replay and dueling networks (2015), distributional RL (2017) and Rainbow (2017); MuZero (2019); offline RL such as CQL (2020) and IQL (2021); RL from human feedback such as InstructGPT (2022) and GRPO (2024). Parts 4 to 8 come back to several of them.

The arrows show which problem leads to which fix, not who built on whom, and some of them join ideas from the same year. n-step returns appear in the same 1989 thesis as Q-learning and grew from TD(λ), which is a year older. Expected Sarsa’s first version is from the same year as Sarsa.

Q-learning on a grid

Q-learning keeps one score for every cell and move: an estimate of all the reward still to come after that move, with later rewards counting a little less. It nudges one score after every step (Sutton and Barto, §6.5). The drawing lays that table out on the grid itself, so where a number sits tells you its cell and its move.

The grid has 4 rows and 12 columns. You start at the bottom left, the flag sits at the bottom right, and the ten cells between them are cliff. Every move costs −1, a step into the cliff costs −100 and sends you back to the start, and a move into the outer wall leaves you in place. Every score starts at 0, so the grid in the drawing is empty for now.

The grid in numbers

Item	Value
Cells	48: 37 cells you can stand on, 10 cliff cells, 1 flag
Moves	up, right, down, left
Reward $r$	−1 per step, −100 for a cliff step (back to the start)
Table	37 cells × 4 moves = 148 scores that can change, all 0 at the start

The table

Each cell is cut along its diagonals into four triangles, one per move: the top triangle holds the score for moving up, the right one for moving right, and so on. That score is $Q(s,a)$ , for move $a$ in cell $s$ , and less negative is better. Red triangles are moves into the cliff, and the arrow in each cell points at its highest score.

The drawing now shows the recorded table after 10,000 updates. Follow the arrows from the start: up once, right eleven times along the edge of the cliff, then down onto the flag. That is the shortest route, 13 moves. Every triangle that points down into the cliff from that row is deep red, about −112, because that move falls.

The bar above the drawing replays the run. Step one update at a time or drag the slider: the yellow triangle is the score the update changes, and the red square follows its cell. Click a cell, or use the arrow keys, to pin the red square while you step. On a phone the map hides the numbers, and the close-up in the next section shows them.

Two readouts of one table

The robot needs both a prediction and a choice. In the start cell, up scores −12.25 and right scores −112.13. The close-up under the map reads both from the same four triangles: the value is the largest score, −12.25, and the move is the one that has it, up.

\begin{aligned} V_Q(s) &= \max_a Q(s,a) \\ \pi_Q(s) &= \arg\max_a Q(s,a) \end{aligned}

Notation: Q, V, π and the star

Read $Q(s,a)$ as the learned score for action $a$ in state $s$ . From those four scores, $V_Q(s)$ takes the largest and the policy $\pi_Q(s)$ takes the corresponding action. So $\max$ returns a number, while $\arg\max$ returns an action, using a fixed rule for ties. A star marks the optimal quantities: $q_*$ is the optimal action value, $v_*$ the optimal state value and $\pi_*$ an optimal action choice. A subscript $Q$ means a readout of the current learned table, which need not be optimal. With $Q=q_*$ , these readouts are optimal.

Readout	Learned table	At the optimum
Action values	$Q(s,a)$ : score for move $a$	$q_*(s,a)$
Cell value	$V_Q(s)$ : largest score	$v_*(s)$
Policy	$\pi_Q(s)$ : its move	$\pi_*(s)$

The update

The Bellman equation splits the future into one reward and the next state's value, and Q-learning turns that into an update. The target is the reward plus the discounted best score in the next cell, and the old score moves part of the way toward it:

Q-learning update Watkins 1989; Sutton and Barto, Eq. 6.8

\begin{aligned} Q(s,a) \leftarrow Q(s,a) + \alpha\,\Big[\,&\underbrace{r + \gamma \max_{a'} Q(s',a')}_{\text{target}} \\ &- Q(s,a)\Big] \end{aligned}

The target uses one observed move in place of the Bellman equation's average, and the current $Q$ stands in for the future. Learning from that estimate is bootstrapping. The bracket, target minus old score, is the TD error: how far one step's outcome missed the table's prediction.

Here the drawing jumps to update 6 and works it by hand. In the start cell the robot tries left, bumps the wall and stays put, for a reward of −1. The yellow triangle is the score that changes, and the blue one is the best score it borrows from where it landed, the start cell again, at −0.5. So the target is $-1+0.99(-0.5)=-1.495$ and the TD error is $-1.495-(-0.5)=-0.995$ , worse than predicted. With a step size of 0.5 the old −0.5 moves halfway, to −0.9975. The −50 in that cell came from update 5, a step off the cliff. Step the bar and the board redraws for any of the first 400 updates.

Dopamine neurons in monkeys fire more when a reward beats the prediction and less when it falls short, a lot like a TD error (Schultz, Dayan and Montague, 1997). The n-step TD card in the tree says where that match stops.

Symbols, the Bellman equation and the full algorithm

A vertical bar in an expectation means conditioning on the observed state and action. The arrow $\leftarrow$ means replacing the old entry, and $\varepsilon=0.1$ is the probability of a uniformly random exploratory move.

Symbol	Meaning
$s$ , $a$	Current cell and move; random variables $S_t$ , $A_t$ at time $t$
$r$ , $s'$	The reward and the next cell ( $R_{t+1}$ , $S_{t+1}$ )
$a'$	Any move in the next cell
$\gamma = 0.99$	Discount: later rewards count a little less
$\alpha = 0.5$	Step size: how far $Q$ moves toward the target
$\mathbb{E}$	Average over what the world does. This grid has no randomness, so it is the one outcome.
Flag reached	Nothing follows: target = $r$

Bellman optimality equation Sutton and Barto, Eq. 3.20

\begin{aligned} q_*(s,a) = \mathbb{E}\Big[\,&R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \\ &\Big|\; S_t = s,\ A_t = a\Big] \end{aligned}

Q-learning, as in the recorded run (ε = 0.1, α = 0.5, γ = 0.99)

Set Q(s, a) = 0 for every cell s and move a. Set s = start cell.
Repeat for 10,000 updates:
With probability ε pick a random move a. Otherwise pick a = argmax Q(s, ·), at random on a tie.
Take a. Observe r and s′. A fall gives r = −100 and s′ = start.
If s′ is the flag: target = r. Otherwise: target = r + γ · max Q(s′, ·).
Q(s, a) ← Q(s, a) + α · (target − Q(s, a))
Set s = s′. After the flag, or after 200 steps, restart at the start cell.

Two real updates, 5 and 6

Does a fall and a wall collision teach the same thing? Read both columns with the same rule: reward plus discounted best score in the next cell, then move the old entry halfway toward that target. Here $r$ is reward, $s'$ the next cell and $Q$ the updated action value. These columns come from the seed-202 update log described in the data drawer.

	Update 5	Update 6
Move	start, right (cliff)	start, left (wall)
$r$	−100	−1
Best score in $s'$	0	−0.5
Target	−100	−1.495
$Q$ , old → new	0 → −50	−0.5 → −0.9975

Step the bar back one update to see update 5 drawn the same way.

Credit travels backward

How does a cost at one cell reach a choice made before arrival? Look at two neighbors in the drawing: the cell just above the start, and the cell one step to its right.

At update 19 the robot moves right from the cell above the start, and that score falls from 0 to −0.5. It was the cell's last zero, so its best score drops to −0.5 too. At update 24 the robot moves left from the neighbor back into it, and its target borrows that new best score. From the recorded log:

\begin{aligned} \text{target}_{24} &= -1 + 0.99(-0.5) \\ &= -1.495 \\ Q_{\text{new}}(\text{neighbor},\text{left}) &= 0 + 0.5(-1.495 - 0) \\ &= -0.7475 \end{aligned}

Before update 19 that same move would have borrowed 0, and its target would have been −1. The extra −0.495 is a cost seen after arriving, passed back one cell. Repeat that thousands of times and the costs of later moves reach earlier choices.

Compare with the settled route

This check asks what repeated backups would produce after values settle. Every move costs −1, including entry to the flag. Hold the discount at 0.99 and start from terminal value zero, then work backward from the flag along the bottom route:

Move	Calculated target
Next to the flag, down onto it	$-1$
One cell earlier, right	$-1 + 0.99(-1) = -1.99$
Two cells earlier, right	$-1 + 0.99(-1.99) = -2.9701$

These are calculated optimal values, rather than recorded learning updates. Compare them with the finished table at the end of the route: −1.00 in the last cell's down triangle, then −1.99 and −2.97 in the right triangles of the two cells before it. A cliff move inherits the restart cost: $-100 + 0.99(-12.2479) \approx -112.13$ .

A working route before a settled table

Training explores on one move in ten. A greedy walk freezes the current table and follows its favorite moves without exploration. Those two walks can disagree:

After update	Route cells with error $<10^{-6}$ (of 13)	$V_Q$ (start)	Greedy walk $\pi_Q$
185	0	−2.45	No flag; exploratory training first reaches it here.
1,000	0	−5.36	No flag
1,670	0	−8.42	Flag in 17 steps (first time)
1,998	1	−9.73	Flag in 13 steps (first time)
1,999	1	−9.73	Loops between the cell above the start and the cell above that: there, right fell below up
2,000	1	−9.73	Same loop
3,000	10	−12.25	Flag in 13 steps
10,000	13	−12.25	Flag in 13 steps

The route-cell count compares learned row maxima with value iteration, counting those with absolute error $<10^{-6}$ . At the start, the reference value is −12.2479 (rounded). Even after 10,000 updates, when 33 of 37 decision states favor an optimal move, 13 cell values are still off by more than 0.01.

The finished table, walked with no random movesArrows: the largest number in each cell. Same recorded run as the widget.

A reward at the end, moving backward (interactive)

The cliff grid charges −1 on every move, so even an early update has something to read. A reward that only comes at the end is harder: until it reaches a state, that state's estimate stays at zero and says nothing. To watch it travel, take a simpler task than the grid. It's a corridor of 16 states, S0 to S15, with one action in each. The step out of S15 pays +1, every other step pays 0, and the discount is 0.95. So the right value of state $S_i$ is $0.95^{15-i}$ : 1 for S15, 0.95 for S14, and about 0.463 for S0. Every estimate starts at 0.

The one-step target is the Q-learning target from above, with only one action to take the maximum over: $r+0.95\,Q(\text{next})$ . The eight-step target adds up the next eight rewards before it reads the table, then adds $0.95^8$ times the estimate eight states ahead. Near the end there are fewer than eight steps left, and the target is just the rewards that remain.

Rounds of updates, all values starting at 0

Assumptions in this visual. Each round updates every state at once from a snapshot of the previous round's table. The step size is α = 1, so each update copies its target. The only reward is the +1 at the end. Together these make the round counts below exact for this corridor. Online learning updates states in the order the agent visits them, and replay in the order it samples them, so real counts differ.

Completed rounds: 0 of 16

One-step target r + 0.95 × Q(next)

Eight-step target 8 rewards + 0.95⁸ × Q(8 ahead)

With one-step targets, each round moves the reward back by one state, because a state can only read the next one, and the next one only changed last round. S15 gets its value in round 1 and S0 in round 16. With eight-step targets, round 1 already fills in S8 to S15, since their eight steps reach the end without reading the table. In round 2, S0 to S7 read those values eight states ahead, and every state is done.

Those counts come from the snapshot schedule. Part 2's corridor uses forward online updates instead and gets the same one-state-per-walk pattern for one-step targets. It also shows that replaying the same transitions backward would carry the reward the whole way in one pass. Sutton and Barto's Figure 7.4 makes the same point after a single episode: the one-step method strengthens only the last action that led to the reward, and the n-step method strengthens the last n.

Moving the reward back faster isn't free. Here's the target for S0 from one attempt, starting from the finished table, where every estimate is right:

A wrong estimate enters the one-step target almost whole: $0.95\times0.4=0.38$ . The eight-step target reads the table only after eight real rewards, so the same error is scaled down to $0.95^8\times0.4\approx0.27$ . That's the bias from an inaccurate continuation, and a longer target has less of it. In exchange, the eight-step target contains whatever actually happened in those eight steps. The one-off −2 moves it by $0.95^3\times2\approx1.71$ in this attempt, and the one-step target doesn't see it at all, because the estimate it reads is an average over many attempts.

That doesn't mean a bad later step erases the credit for a good early one. Averaged over many attempts, later outcomes are part of the right answer for the policy that produced them. What they add is variance: each single target swings more. So a longer target trades error from the estimate for noise from later outcomes, and which one matters more depends on how good the estimates are and how random the later steps are. Part 2's horizon section explains why that isn't a fixed rule. One more catch for Q-learning: it wants the value of the greedy policy, so if the later steps were exploratory moves, an eight-step target measures the exploring policy instead. Off-policy n-step methods correct for that (Sutton and Barto, Section 7.3).

Where these numbers come from

Teaching calculation, computed in the page. The one-step update in round $k$ is $Q_k(S_i)=r_{i+1}+0.95\,Q_{k-1}(S_{i+1})$ , and the eight-step update is $Q_k(S_i)=\sum_{j=0}^{h-1}0.95^{j}r_{i+j+1}+0.95^{8}\,Q_{k-1}(S_{i+8})$ , with $h=\min(8,16-i)$ and the last term dropped when $i+8\ge16$ . That is the n-step return of Sutton and Barto, Section 7.1, Eq. 7.1, applied to every state from a copy of the previous table. The only nonzero reward is $r_{16}=1$ . The second box uses the finished values $0.95^{15-i}$ , adds 0.4 to every estimate for the first tick box, and adds $0.95^{3}\times(-2)$ to the eight-step sum for the second.

When it converges

A route can work while other scores are still wrong. The guarantee covers the whole table in the limit, if every cell and move keeps getting tried and the step size shrinks without stopping learning. The drawing shows why: one sweep of expected updates multiplies the largest gap between two guesses of the table by at most $\gamma = 0.99$ . The run's fixed step size of 0.5 is outside the guarantee.

The exact conditions, and why the expected target is stable

Let $n$ count all updates, with $Q_n$ the current table and $q_*$ the optimal table. Each state-action pair has its own update count $k$ and step sizes $\alpha_k$ . The first sum below requires unlimited total adjustment, and the second limits the accumulated squared step size. For example, $\alpha_k=1/(k+1)$ for $k=1,2,\dots$ satisfies both. The arrow $\to$ means convergence:

\begin{aligned} &\sum_k \alpha_k = \infty, \quad \sum_k \alpha_k^2 < \infty \\ &\Longrightarrow\; Q_n(s,a) \to q_*(s,a) \ \text{with probability 1} \end{aligned}

Why is the expected target stable? Let $T_*$ map a whole candidate table to its expected Bellman target. Start with two candidate tables $q,u$ and call their largest absolute entrywise difference $e$ . Taking a maximum and averaging cannot increase that difference. Discounting then bounds the new difference by $\gamma e$ , and the drawing applies this bound twice with $\gamma=0.99$ .

This guarantee assumes:

Finite, stationary task. Finitely many states and actions; fixed Markov reward and transition laws.
Bounded rewards. Finite reward magnitudes and discount $0 \le \gamma < 1$ .
Repeated updates. Every nonterminal pair is sampled infinitely often, with step sizes in $[0,1)$ satisfying both sums.

Watkins and Dayan (1992), pages 280 to 282, prove this discounted case. The recorded run uses fixed $\alpha=0.5$ , outside the guarantee.

Pros and cons of a Q table

A small table lets you inspect every prediction, as we did here. Each weakness below points to the part that addresses it; the run counts come from the data drawer and are not a general ranking.

Pros

No model. Learn from moves and results.
Immediate updates. Learn every step, while behavior can include exploration.
Readable estimates. Print the table and inspect what each choice expects.

Cons and next methods

Exploration costs. 171 falls in 10,000 updates; 150 came after update 2,000, all on nonfavorite moves. On-policy targets address this.
Table growth. 37 decision states require 148 action values. Function approximation shares estimates across situations.
Noisy maxima. Lucky estimates favor worse choices. Double Q separates picking from scoring, costing a second table. Open “Noisy maxima” below.
Approximation stability. Bootstrapping with function approximation and off-policy data can diverge: the deadly triad in part 5.

Noisy maxima: the mirage mechanism and recorded results

You first choose between two doors. Right ends the episode with reward 0. Left pays 0 now, then offers a choice among ten noisy machines; each pays −0.1 on average and ends the episode. So right is better.

Q-learning backs up the largest machine estimate into the left-door value. One lucky machine estimate can make that door look profitable, even though every machine's true mean is negative.

Illustrative machine row	Current estimates
Machines 1 to 5	−0.4, −0.2, +0.6, −0.1, +0.2
Machines 6 to 10	−0.3, +0.1, −0.2, 0, −0.1

These estimates are made up to expose the mechanism. With no discount ( $\gamma=1$ ), the left-door target is $0 + 1(0.6)=0.6$ , against right's terminal target of 0. From $Q(\text{left})=0$ , step size 0.1 moves the estimate to +0.06.

Door targets, for this illustrative machine row

Left: target = 0 + max Q(machine state, ·) = 0.6.
Right: target = 0, because the episode ends.

Averaging many noisy maxima tends to run high. Let $i$ index machines and $X_i$ be machine $i$ 's noisy estimate. $\mathbb E$ averages over that estimation noise, $\max_i$ takes the largest machine estimate and $\ge$ means at least. Then the inequality says that averaging the biggest estimate gives at least the biggest average estimate:

\mathbb{E}\big[\max_i X_i\big] \;\ge\; \max_i \mathbb{E}[X_i]

For unbiased machine estimates, the right side is −0.1; selecting their maximum can raise the left side. This is maximization bias (Sutton and Barto, Example 6.7).

The worse door wins at first, then losesLabels: each door's share of episodes so far. One recorded run.

Averaged over 300 runs	Left door
Share of episodes, first tenth	85.0%
Share of episodes, last fifth	11.3%
Share from random moves alone	about 5%
Estimate at the end (true value −0.1)	−0.036

The late left share remains above the random-choice baseline, so the worse door is chosen more often than exploration alone requires. Its final estimate also remains too high. The source drawer gives the settings and the limit on attributing the measured effect.

A one-state example: exploration at the slot machines

The grid adds consequences that unfold over time. A bandit isolates the exploration problem: every pull returns to the same situation. Its one-row table estimates the immediate payout, so we can see the effect of trying other actions without a later-state target.

Explore or exploit: the bandit

Which of ten slot machines should you pull? Each pays a hidden average plus noise. This bandit has one state, so its table has one row: $Q(a)$ estimates machine $a$ 's mean payout; $n(a)$ counts its pulls, including the latest one, and $r$ is that pull's reward. Let $\varepsilon$ be the probability of exploring with a uniformly random machine.

Q(a) \leftarrow Q(a) + \tfrac{1}{n(a)}\bigl(r - Q(a)\bigr)

Ten slot machines, 1,000 pulls (ε = 0 is greedy, ε = 0.1 explores a little)

Set Q(a) = 0 and n(a) = 0 for each machine a.
Repeat for 1,000 pulls:
With probability ε pick a random machine. Otherwise pick argmax Q(a), at random on a tie.
Pull it and observe the payout r. Set n(a) = n(a) + 1.
Q(a) ← Q(a) + (r − Q(a)) / n(a)

The factor $1/n(a)$ makes this a running sample average: each new payout receives one equal share of the updated mean.

For example, a machine with two payouts totaling 4 has estimate 2. A third payout of −1 gives $2+(-1-2)/3=1$ , the mean of all three payouts. The table stores that running mean, not the latest reward. Sutton and Barto, §2.4. Greedy picks the largest estimate and can stay with a lucky early choice. With $\varepsilon=0.1$ , one pull in ten explores, so other estimates get a chance to improve.

ε = 0: it never leaves its first pickGold: true average. Blue: belief. Crown: best machine. One recorded run.

ε = 0.1: it finds the best machineSame machines, same table. One recorded run.

Rule, 200 runs	Share of the last 200 pulls on the best machine
Greedy, ε = 0	35.5%
Random pull 1 in 10, ε = 0.1	77.5%

Exact numbers: slot machines

Re-run of settings the game already uses, with its own RLA.run at commit 681cae3.

Here $n$ counts pulls of one machine, so $1/n$ is its running-average step size. These are measured finite-run results, not a convergence claim. Ten machines with true averages drawn from a standard normal distribution, payout noise with standard deviation 1, 1,000 pulls, running averages (step size $1/n$ ), 200 runs. Greedy starts all numbers at zero and breaks ties at random. Share of the last 200 pulls on the best machine, averaged over runs: greedy 35.5%, with random pulls 77.5%. Runs with less than half of the last 200 pulls on the best machine: 64.5% for greedy, 15.0% with random pulls. Even with perfect greedy choices, the expected best-machine share is 91%: $0.9 + 0.1/10$ . A finite run can be higher or lower.

The clip pair uses one run where greedy never pulled the best machine in its last 200 pulls and the other robot spent 92.5% there. I chose it because it shows the gap clearly. It is an example, not a typical run. Both robots share one set of machines.

Two other ways to explore: start optimistic, or add a bonus

The slot-machine drawer above sets up the simplest case: ten machines, each paying a hidden average plus noise, and a one-row table where $Q(a)$ is the running average of machine $a$ 's payouts. Picking a random machine one pull in ten, as ε-greedy does, put 77.5% of the last 200 pulls on the best machine, against 35.5% for pure greedy. But random pulls never stop. Even once you know the best machine, one pull in ten goes somewhere else. Two other rules aim the exploration at what you haven't tried.

Start optimistic. Set every estimate to +5, far above any machine's likely average, and act greedily. Each pull disappoints, so the pulled machine's estimate drops and the learner moves to another one still at +5, until every machine has been tried. Sutton and Barto, §2.6, show this with a constant step size of 0.1. With a running average, the first payout replaces the start value completely, since $1/n(a)=1$ on the first pull. So optimism buys exactly one pull of each machine. The book also calls it far from a generally useful approach: the push to explore is temporary, so it can't help when the machines change over time.

Add a bonus for what you haven't tried. The upper confidence bound (UCB) rule picks

A_t=\arg\max_a\Big[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}\,\Big],

where $t$ counts all pulls so far, $N_t(a)$ is the same count as $n(a)$ , and $c>0$ sets the size of the bonus (§2.7, Eq. 2.10). A machine that has never been pulled counts as the largest, so each one gets tried first. The bonus shrinks as a machine gets pulled and grows slowly while it's left alone. The book's limits: UCB is harder than random pulls to extend beyond bandits, to machines that change, and to large state spaces, and it's usually not practical with function approximation.

Rule, same 200 runs, no random pulls	Share of the last 200 pulls on the best machine
Greedy, start 0, running average	35.5%
Greedy, start +5, running average	63.5%
Greedy, start 0, step 0.1	51.4%
Greedy, start +5, step 0.1	83.5%
UCB, $c=2$ , running average	82.0%

The rules interact. In the game's log, UCB with a constant step of 0.1 dropped to 67.0%. The log's explanation, backed by a follow-up probe: a constant step keeps only about the last 20 payouts, so its error stops shrinking, while the bonus keeps shrinking as if the estimate were still getting more precise. And the constant step alone lifts plain greedy from 35.5% to 51.4%, a gain the log doesn't explain.

Where these numbers come from

The rows come from the game's batch 24 in its experiment log, on the same 200 seeds and the same world as the drawer's greedy and random-pull runs, with standard errors of 1.6 to 3.5 points over seeds. The 67.0% is UCB with step 0.1 and start 0. Simulation, ten machines, 1,000 pulls per run.

From returns to the Bellman equation

Words and symbols used on this page

Symbol	Meaning
$s$ , $s'$	A state (the situation you are in) and the next state
$a$ , $a'$	An action and a candidate action in the next state
$r$ , $R_{t+1}$	The reward after the action at step $t$
$G_t$	The return: later rewards added up, each one more factor of $\gamma$
$\gamma$	The discount, between 0 and 1
$\alpha$	The step size of an update
$\varepsilon$	The chance of picking a random action
$\pi$	The policy: the rule that picks an action in each state
$Q(s,a)$	An estimate of return after action $a$ in state $s$
$V(s)$	An estimate of return from state $s$
$n$ , $T$	A number of steps and the step at which an episode ends
$n(a)$	The number of times action $a$ has been tried
$\pi(a\mid s)$	The probability that policy $\pi$ picks $a$ in $s$
$\arg\max$	The action attaining the largest value; $\max$ is the value itself
$v_\pi(s)$ , $q_\pi(s,a)$	The return you expect from $s$ , or after action $a$ in $s$ , following $\pi$
$v_$ , $q_$	The best of those over all policies
$\pi_*(s)$	An action attaining the optimal value in state $s$ , with a fixed tie rule
$t$ , $k$	Current time step and an index counting later steps
$S_t$ , $A_t$	The state and the action at step $t$
$\mathbb{E}$	The average over the action the policy picks and what the world does next

A state's value is an average of its actions' values

v_\pi(s) = \sum_a \pi(a \mid s)\, q_\pi(s,a)

For the best values, take the max in place of the average

\begin{aligned} v_*(s) &= \max_a q_*(s,a) \\ \pi_*(s) &= \arg\max_a q_*(s,a) \end{aligned}

Average over the actions the policy picks and you get the value of a state. Take the best action in place of the average and you get the best value.

Where the Bellman equation comes from

How can you learn about a whole future from one transition? Here $G_t$ is the return from step $t$ , $R_{t+1}$ is its first reward and $G_{t+1}$ is the remaining return. Split after that first reward, then take the expectation. The subscript $\pi$ on an expectation means following policy $\pi$ ; a vertical bar means conditioning on the stated starting state or action. The Bellman equation links each state's value to the next state's value.

G_t = R_{t+1} + \gamma G_{t+1}

Factor out $\gamma$ , then average over possible futures.

Bellman equation for a policy Eq. 3.14

v_\pi(s) = \mathbb{E}_\pi\!\left[R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s\right]

The first equation follows policy $\pi$ . For optimal action values, fix the current action $a$ , average over the world's resulting transition, then choose the best action after arrival:

Bellman optimality: maximize over the next action Eq. 3.20

\begin{aligned} q_*(s,a) = \mathbb{E}\Bigl[&R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \\ &\Bigm| S_t = s,\, A_t = a\Bigr] \end{aligned}

Once you have $q_*$ , taking the action with the largest value in each state is an optimal policy, so solving the second equation solves the problem.

Derivation from the return

The steps below expand, split and average the same reward sequence. $k$ counts rewards ahead of the current time. A fixed policy makes the conditional expected remaining return equal to its value at the next state. This is the bridge from recorded rewards to a reusable prediction.

1. The return Eq. 3.8

\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \end{aligned}

2. Factor out γ Eq. 3.9

\begin{aligned} G_t &= R_{t+1} + \gamma\bigl(R_{t+2} + \gamma R_{t+3} + \cdots\bigr) \\ &= R_{t+1} + \gamma\, G_{t+1} \end{aligned}

3. The episode ends at step T: nothing is left

G_T = 0

So the value of a terminal state is 0.

4. Values are expected returns Eq. 3.12 and 3.13

\begin{aligned} v_\pi(s) &= \mathbb{E}_\pi\!\left[G_t \mid S_t = s\right] \\ q_\pi(s,a) &= \mathbb{E}_\pi\!\left[G_t \mid S_t = s,\, A_t = a\right] \end{aligned}

Putting equation 2 into equation 4 gives the Bellman equation for a policy. The value is not a new reward: $R_{t+1}$ is real, and $\gamma\, v_\pi(S_{t+1})$ stands in for everything after it.

Double Q-learning: separate picking from scoring

Pick and score separately

When estimates are noisy, picking the largest also tends to pick lucky noise. Double Q-learning reduces this bias: one table picks the next action and the other scores it. Write those tables as $Q_1$ and $Q_2$ ; $\text{target}_1$ is the target when updating the first.

\text{target}_1 = r + \gamma\, Q_2\big(s', \arg\max_{a'} Q_1(s',a')\big)

Use: reduce maximization bias. Needs: separately learned estimates. Cost: two tables sharing the updates. The seventh branch of the tree shows a noisy selection and a separate score.

Algorithm: Double Q-learning

Keep both tables across steps. When updating $Q_1$ , select the action with $Q_1$ and evaluate it with $Q_2$ ; swap the roles when updating $Q_2$ . Apply the usual step-size update to the chosen table only. Separate scoring reduces selection bias; it does not guarantee an unbiased estimate at every finite step. Van Hasselt, 2010.

Double Q-learning target

Choose a table to update at random: each receives half the updates on average.
That table picks the best next action. The other table scores it.
Build the target from r plus γ times that score; update only the chosen table. Terminal target = r.

Continue with part 2, bootstrapping, which isolates how quickly a late reward reaches earlier choices. Or return to the method tree to choose another question.

Source checks

This note checks the theory used in the explanation; the next drawer identifies the recorded measurements. Here $t$ indexes time, $R_{t+1}$ is its next reward and a star marks an optimal value. The source's $x$ and $a$ mean state and action. Equation and section numbers are from Sutton and Barto, Reinforcement Learning: An Introduction, second edition. Watkins and Dayan is Q-learning, Machine Learning 8, pages 279 to 292, which I read as page images.

Notation. The book writes the reward after step $t$ as $R_{t+1}$ . The update is Eq. 6.8, and $q_*$ is defined in Section 3.6 with Eq. 3.16; Eq. 3.17 and Eq. 3.20 write it in terms of $v_*$ and as a Bellman equation.
Greedy readouts. Watkins and Dayan, pages 280 to 281: $V^*(x) = \max_a Q^*(x,a)$ , and the policy that takes a maximizing action is optimal. Page 281 says early Q values may not reflect the policy they define.
Convergence. Pages 280 to 282 set up a finite Markov task with fixed transition and reward laws, discount below 1, table representation, bounded rewards, repeated sampling and the per-pair step-size conditions. Section 4 treats the undiscounted absorbing extension separately. I did not check the convergence outline in Appendix 1 of the 1989 thesis.
Maximization bias. Sections 6.7 and Example 6.7. In the book the left action leads to many choices with mean −0.1. The game uses ten.

The recorded run: data, settings, command

The visible route and checkpoints describe one finite run. They establish what this seed did, rather than a general success rate. The widget shows that run, re-run so that its intermediate tables exist. The game's saved runs hold only the final table.

Source. Breaking Bellman, a small game I made, at commit 681cae3. I imported its RLA.run unchanged and wrapped the learner in a separate script only to record each update.
Settings. World cliff (4 by 12, step cost 1, fall cost 100, no slip), table, step size 0.5, discount 0.99, one random move in ten, 10,000 steps, seed 202. These are the game's careful-q settings. The learner acts, takes the step, then updates, as in the algorithm above.
Check. The final table equals the saved table of the recorded seed-202 run in all 192 entries.
Propagation example. Updates 19 and 24 above are read from the existing replay data in qtable-data.js, with the intervening entries replayed from zero. No new experiment was run.
Recorded. Full tables after updates 0, 1, 5, 20, 100, 185, 300, 1,000, 1,670, 2,000, 3,000 and 10,000, and every update from 1 to 10,000. The widget replays updates 1 to 400 and shows four later snapshots.
Command. SEED=202 node pilot-v2/snapshots.js > pilot-v2/snapshots-seed202.json, then node pilot-v2/make-widget-data.js. Every number in the checkpoint table comes from replaying the full update log (pilot-v3/verify_numbers.js). Reference values come from value iteration (5,000 sweeps, discount 0.99). Route-cell counts compare row maxima with absolute error < 1e-6, using the full-precision log and reference, rather than the rounded widget asset.
Greedy walk. Training breaks ties at random. The greedy walk breaks ties in the fixed order up, right, down, left, uses no random numbers and stops after 40 steps. The drawing shows no arrow in a cell with a tie. At 185 updates the walk never reaches the flag.
Falls. Replaying the log shows 4 falls were the table's own favorite move, all early. The other 167 were other moves, including all 150 after update 2,000 (pilot-v3/check_falls.js).

The finished table, all 37 nonterminal decision states, is below. Cells are (row, column), rows counted from the top. The last column is the value-iteration reference, rounded to two decimals.

Cell	Up	Right	Down	Left	Optimal reference
(0, 0)	-11.69	-11.58	-11.64	-11.47	-13.13
(0, 1)	-11.22	-11.25	-11.31	-11.31	-12.25
(0, 2)	-10.97	-10.59	-10.75	-11.19	-11.36
(0, 3)	-9.78	-9.81	-10.06	-10.78	-10.47
(0, 4)	-9.33	-9.06	-9.03	-9.23	-9.56
(0, 5)	-8.46	-8.30	-8.41	-8.76	-8.65
(0, 6)	-7.90	-7.48	-7.59	-8.20	-7.73
(0, 7)	-6.66	-6.62	-6.67	-7.38	-6.79
(0, 8)	-6.25	-5.74	-5.77	-5.76	-5.85
(0, 9)	-4.87	-4.84	-4.83	-5.59	-4.90
(0, 10)	-3.93	-3.91	-3.92	-4.18	-3.94
(0, 11)	-3.45	-3.57	-2.97	-3.56	-2.97
(1, 0)	-11.95	-12.04	-12.02	-12.15	-12.25
(1, 1)	-11.62	-11.32	-11.30	-11.90	-11.36
(1, 2)	-10.73	-10.46	-10.46	-10.67	-10.47
(1, 3)	-10.26	-9.56	-9.56	-9.79	-9.56
(1, 4)	-9.20	-8.65	-8.65	-9.48	-8.65
(1, 5)	-8.59	-7.73	-7.73	-8.28	-7.73
(1, 6)	-8.10	-6.79	-6.79	-8.14	-6.79
(1, 7)	-6.91	-5.85	-5.85	-6.80	-5.85
(1, 8)	-5.57	-4.90	-4.90	-5.08	-4.90
(1, 9)	-5.07	-3.94	-3.94	-5.56	-3.94
(1, 10)	-3.70	-2.97	-2.97	-4.63	-2.97
(1, 11)	-2.08	-2.48	-1.99	-2.67	-1.99
(2, 0)	-12.68	-11.36	-13.11	-12.25	-11.36
(2, 1)	-12.11	-10.47	-112.12	-12.25	-10.47
(2, 2)	-11.35	-9.56	-112.12	-11.36	-9.56
(2, 3)	-10.45	-8.65	-112.13	-10.47	-8.65
(2, 4)	-9.56	-7.73	-112.10	-9.56	-7.73
(2, 5)	-8.65	-6.79	-112.13	-8.65	-6.79
(2, 6)	-7.72	-5.85	-112.10	-7.73	-5.85
(2, 7)	-6.79	-4.90	-112.12	-6.79	-4.90
(2, 8)	-5.85	-3.94	-112.12	-5.85	-3.94
(2, 9)	-4.90	-2.97	-112.11	-4.90	-2.97
(2, 10)	-3.94	-1.99	-111.99	-3.94	-1.99
(2, 11)	-2.97	-1.99	-1.00	-2.97	-1.00
(3, 0)	-12.25	-112.13	-13.13	-13.13	-12.25

Exact numbers: mirage and cliff table

Read these as finite-run measurements, separately from the theoretical examples. Powers such as $10^{-13}$ denote comparison tolerances, not confidence intervals. These are re-runs of settings the game already uses, with its own RLA.run at commit 681cae3.

Mirage. Right door reward 0. Left door reward 0, then ten machines with mean −0.1 and standard deviation 1. Table, random moves 0.1, step size 0.1, no discount, 600 steps per run, 300 runs (about 467 episodes each). Left share 85.0% in the first tenth, 11.3% in the last fifth, estimate −0.036 at the end. Random moves alone give about 5%. I did not run a version without the max, so the cause is the book's explanation.
Cliff table, twenty runs. Table, random moves 0.1, step size 0.5, discount 0.99, 10,000 steps. In all 20 runs the start cell held −12.2479 and the greedy walk took 13 steps. The 13 route numbers agreed with value iteration to better than $10^{-13}$ . In the 37 decision states, the favorite move matched an optimal move in 34.5 cells on average. I did not examine why the rest differ. The number for a step off the route into the cliff was between −112.13 and −110.2, against an exact −112.13.
Seed 202. 33 of 37 decision states have an optimal favorite move. The four that do not are the top-left cell, its right-hand neighbor, the fourth cell of the top row and the cell just below the top-left. The largest gap to the exact value over 148 numbers is 2.68. The start cell was updated 767 times, row 2 cells 507 to 739 times, rows 0 and 1 cells 35 to 127 times.

How the clips were made

The clips illustrate particular runs; their appearance supplies no additional statistical evidence. The data drawers above state what was measured and how the example was selected. Each clip is a real recorded run drawn by a real browser with the game's own web/scenes.js at the same commit, unmodified. I replaced only the clock (30 frames per second) and encoded with ffmpeg (H.264). The run script and raw results are stored locally and are not published.

← All writing