From Bellman to Rainbow

This is basically my notebook, cleaned up.

I spent a few weeks filling a legal pad with RL, and somewhere around the third page I realised the notes were better than most of the explanations I'd been reading. Not because they were more correct. Because they were written by someone who was confused ten minutes earlier and still remembered why. Every time something clicked I wrote down the thing that made it click, which is usually a dumb analogy or a question like "wait, why can't we just do X".

So that's what this is. Same order I learned it in, same questions in the same places, equations broken apart term by term because that's the only way I could read them. Where a slider explains it better than a paragraph, there's a slider — go play with them, they're the whole point.

I got the structure from naklecha's reinforcement learning guide, which is the best RL on-ramp I've found. Read it too. I've written it out in my own words, added the interactive bits, and carried it further into stuff that came out after Rainbow, which most intros skip.

Part one is value-based RL — methods that learn how good things are and figure out what to do from that. It ends at Rainbow DQN, because that's where this way of thinking runs out of road. I'm an ML engineer at Workday; I don't do RL day to day, so if I've got something wrong, tell me and I'll fix it.

RL can't be solved. It can only be estimated.

This was the first line I wrote in my notes and it's still the most useful one, so let's start there.

Take chess. You want the best move. The honest way to find it: look at every legal move, then every reply, then every reply to that, all the way down to checkmate, and pick the branch where you win. Done. That's the correct algorithm.

It's also a tree with about 10¹²⁰ leaves. There are roughly 10⁸⁰ atoms in the universe. You could turn every atom into a computer and you wouldn't finish.

So the right answer definitely exists, and you are definitely never going to compute it. Everything in this post is a different way of guessing it cheaply enough to be useful. Once I saw it that way the field stopped looking like a pile of acronyms. Every algorithm here is just someone going "hang on, my guess is wrong in this specific way" and patching it. That's the pattern. RTDP, MCTS, DQN, Double DQN — all of them are patches on a previous patch.

The setup: agent, environment, reward

Quick foundations before the maths. If you've done supervised learning, the thing to un-learn is labels.

In supervised learning somebody tells you the answer. This image is a cat. This email is spam. Loss goes down, everyone's happy. In RL nobody ever tells you the answer. You're dropped into a situation, you do something, and the world eventually goes "eh, that went badly" — maybe forty moves later, with no explanation of which move it hated. There's no label. There's a score at the end and a lot of guessing about who deserves the blame.

And that's it, really. One loop, over and over, until something ends:

Five words do most of the work. Worth pinning them down properly now, because every equation later is written in them.

Reward is not return

This one tripped me up, so: reward is what you got this step. Return is everything you'll collect from here to the end of the episode. Sacrificing a piece is negative reward and possibly very positive return.

The agent wants to maximise return. The environment only ever gives it reward. Every technique in this post is a way of bridging that gap.

The Markov assumption

One assumption makes all of the maths work: the current state has everything relevant about the future in it. How you got here doesn't matter, only where you are. Make that assumption and your problem is officially a Markov Decision Process, which is a fancy name for this tuple:

P(s′ | s, a) is the transition function: the probability of landing in s′ given that you took a in s. In chess it's deterministic — the board goes exactly where you put it. In most real problems it isn't: the wheels slip, the user does something unexpected, the dice come up wrong. When transitions are stochastic every V(s′) in this essay becomes an expectation over where you might land, and the shape of the equation is unchanged. I've written the deterministic version throughout because the extra expectation obscures more than it adds on a first read.

Also: the Markov assumption is false all the time and people ship anyway. Poker has cards you can't see. A robot's camera can't see behind itself. A conversation depends on what someone said ten turns ago. The standard move is to shove more history into the state until it's approximately Markov — which is exactly what Pong's four stacked frames are doing.

The three problems that make this hard

Naming these up front, because every algorithm in the rest of the post is aimed at one of them.

The middle one you have to feel rather than read. Three slot machines, unknown payout rates, go. Every pull you spend checking a machine is a pull you didn't spend on the best one — and you can't know which is best without checking.

Pull one machine over and over and that estimate gets sharp while the other two stay pure noise. Spread your pulls evenly and all three estimates are mediocre. Hit "always greedy" a few times and watch it lock onto whichever machine got lucky first and never look back. ε-greedy keeps a small budget for doubt, and usually finds the real winner.

That's the whole exploration problem, and note that it needed no states, no discounting and no Bellman equation to show up. Three slot machines is enough.

Three ways to attack it

Last thing before the maths, just so you know where you are on the map. Everything in RL is roughly one of three approaches, or a hybrid of them.

The value function

Right. We need a number that says how good a situation is. That's it, that's the value function: V(s) takes a state and gives you one number meaning "how well is this going for me".

Now here's the trick that starts everything. If you're playing well, then the value of your position is just the value of the position you'll be in after your best move:

s

the position you're in right now.

a

one legal move available from s.

s′

the position you land in after playing a. One s′ per action.

maxa

take the best of those next positions. This is the assumption that you will actually play your best move.

Say it out loud: the value of this chess position is the value of the position after the best move. Which is a definition of a thing in terms of itself, and yeah, that's allowed, and that recursion is basically the whole subject. To evaluate V(s) you need V(s′), which needs V(s″), until you hit something you actually know the value of — checkmate, stalemate, game over. Those are terminal states.

Which is worth sitting with for a second, because it took me a while. The terminal states are the only place real information gets into the system. Everything else — every value of every position in the middle of the game — is that information seeping backwards from the end. The agent doesn't know anything except how games finish.

Sooner is better: the discount factor

Problem with that equation: it thinks winning in three moves and winning in forty are the same thing. They are not the same thing. A win forty moves away needs forty things to go right, and your opponent gets forty chances to do something you didn't see coming. Far away = uncertain. We should be penalising it.

Fix: multiply future value by a discount factor γ between 0 and 1, once for every step you look ahead.

A reward k steps away is worth γ^k times its face value. At γ = 0.99 the agent is nearly patient; at γ = 0.5 anything past a handful of steps is rounding error. Drag it:

One parameter, three things for free. Reward now beats reward maybe-later. Long plans get taxed for being long. And the agent now prefers a fast win to a slow one, which is exactly what you want from anything acting in real time.

Rewards, and the Bellman equation

Still missing one thing. Some moves are just good right now — you take a queen, you score a point, the user clicks the thing. That's the reward function R(s, a): what you get paid on the spot. Bolt it on and you get the equation the entire field sits on top of:

R(s, a)

what you're paid on the spot. Often zero for most moves and large at the very end.

γ · V(s′)

everything you expect to collect afterwards, shrunk for being one step further out.

maxa

of all the immediate-plus-future totals available to you, keep the largest.

That's the Bellman equation and honestly that's the hard part done. Value now = reward now + discounted value next. Everything from here to the end of the post is people trying to compute that thing when they can't list the states, can't list the actions, or can't trust their own numbers.

A detour on action spaces

Quick aside, because that maxa is quietly assuming you can loop over the actions. Whether you can is a property of your problem, and it decides which algorithms you're even allowed to use.

Everything in part one assumes discrete actions. Continuous control is the thing that forces the jump to policy methods in part two — worth knowing that's the actual reason, otherwise DDPG and SAC just look like two more acronyms someone invented for fun.

From V to Q

Annoying thing about V(s): it tells you how good your position is, not what to do. To actually pick a move you'd have to simulate every action, look up the value of each resulting position, compare. Which means you need a model of the world good enough to predict s′ before you've been there. Usually you don't have one.

So: shove the action inside the function. Q(s, a), the action value function — how good is it to be in state s and take action a.

Same information. Different filing system. Huge difference in practice: with Q you just score the actions in front of you and take the biggest number. No simulator. No model of the world. That one move is why almost every algorithm below learns Q and not V.

Attempt one: walk around and update as you go

OK so the tree can't be fully traversed. But what if we partially traverse it, and only bother with actions that look sensible? Start where you are, take a decent-looking action, apply Bellman, move on, repeat until the game ends, then do it again. That's Real-Time Dynamic Programming and it's the simplest thing that works at all:

Step two is where the oldest fight in RL is hiding. Always take the best-looking action and you'll never find out that the door you ignored on move one led somewhere better. Always act randomly and you'll learn loads while losing every game. Pick one.

The usual answer is the laziest possible compromise, ε-greedy: roll a dice, and ε of the time act randomly, otherwise be greedy. Start ε near 1 (know nothing, try everything) and decay it as your numbers get trustworthy. Crude, works fine.

And here's the thing running. Each sweep applies Bellman once to every square. Shading is the current value estimate, arrow is what the agent would do. Hit "one sweep" a few times and watch information leak backwards from the goal, one square at a time — this is the "everything is inference from terminal states" thing from earlier, happening in front of you.

Where RTDP breaks

Attempt two: imagine the rest of the game

Think about RTDP in a maze. It has to actually walk down a corridor to learn anything about that corridor. MCTS doesn't — it can imagine walking down it. It plays the rest of the game out in its head, a few thousand times, and uses that to decide which corridor is worth really walking down. Four stages, on repeat until you run out of time.

1. Selection

Walk down the tree you've built so far. At each node, pick the child with the highest Upper Confidence Bound score:

Q(s, a)

the average value found so far by going this way. Exploit: go where you've had success.

N

how many times the parent node has been visited.

n

how many times this child has been visited.

c

the exploration constant. √2 is the classical choice, from the confidence-interval derivation the formula comes from.

Two terms, and they're fighting: Q(s, a) says "go where we've had success before" (exploit), the square root says "go somewhere new" (explore). The nice bit is how the fight resolves itself. The more you visit a child, the bigger n gets and the smaller its exploration bonus — you already know about this one, stop being curious. Meanwhile if you keep ignoring a child, ln(N) quietly climbs until it becomes interesting again.

So exploration isn't a coin flip taped onto the side like in ε-greedy. It's a term in the score, and it decays by itself. No schedule to babysit. This is much nicer and it's why I like this formula.

2. Expansion

Selection walks you to the edge of what you know. Now grow the tree: add one new child node. Not all of them — one. Adding a single node per iteration keeps memory manageable and lets the search decide where to spend its next node, instead of committing to a whole row of children it might never look at again.

3. Playout

From the new node, just play randomly until the game ends, and see who won. Sounds useless. Isn't — average a few thousand random playouts and you get a surprisingly decent read on whether a position is fundamentally good.

Though obviously you can do better than random. AlphaGo's big move was replacing the random rollout with a learned value network: estimate the outcome instead of coin-flipping your way to it. That swap is most of why it worked.

4. Backpropagation

Walk the result back up the path you came down and update what you know. Good paths get higher Q, so they get more attractive. Visited paths get smaller exploration bonuses, so they get less attractive. Nothing here is individually clever. The real power is repetition — run this loop a few hundred thousand times and the tree has quietly focused nearly all its attention on the moves that matter.

Learning from other people's experience

Everything so far learns only from its own actions. That's on-policy, and it's a real constraint: to learn anything, you have to have done it yourself. RTDP is on-policy.

Off-policy methods can learn from data somebody else generated — a logged dataset, human demonstrations, an older version of the model. Netflix and ChatGPT are both in this camp, and so is basically every RL system you've personally interacted with, for the very simple reason that no company is letting a randomly initialised agent go exploring on live users.

Recommendation is the cleanest example. You showed a title, the user rated it, and you want to shuffle your estimate towards what actually happened:

The bracket is just "how wrong were you". α is the learning rate, i.e. how much of being wrong you're willing to absorb in one go. You guessed 3.2, they gave it a 5, so you move up — barely at α = 0.01, most of the way at α = 0.9.

Worth memorising the shape — old estimate + a bit of the error — because every single update for the rest of this post is that shape wearing a different costume.

The state is too big, so describe it instead

A table indexed by raw chess positions is hopeless — there are effectively infinite of them. But you don't need the exact board. You need what a strong player notices when they glance at it: material count and distribution, piece activity and mobility, king safety, pawn structure, control of key squares, piece coordination, tempo and development.

Describe positions that way and the agent starts recognising kinds of position — it can carry what it learned from one game onto a board it's never seen, because strategically they're the same situation.

But this is flawed for chess, and here's why. Features describe the position in front of you. They say nothing about the chain of moves it leads to. A feature vector will happily tell you a position looks lovely four moves before it collapses. So we need the update to look forwards:

R + γ maxa′ Q(s′, a′)

the target: what you now believe Q(s, a) should have been, given the reward you actually received and the best you can do from where you ended up.

− Q(s, a)

subtract what you predicted. The difference is the temporal difference error — the gap between your prediction and a slightly better-informed prediction made one step later.

α

how much of that error to move by.

Now notice what's not in there: the action you actually took next. The target uses maxa′, the best action available from s′, regardless of what your exploring, occasionally-random self actually did. That one detail is what makes Q-learning off-policy, and it's why it can learn good behaviour from a dataset full of mediocre behaviour. Which is a genuinely wild property when you think about it.

Attempt three: let a network hold the table

Two massive issues with hand-picked features. One, we're going to miss subtle patterns that didn't occur to us. Two, we're treating the features as roughly independent when they absolutely aren't — a weak king is fine in a closed position and fatal in an open one.

Those are the two things neural networks are for. So instead of storing Q values in a table, let's train a network to predict them:

This is deep Q-learning, and training it is ordinary supervised learning where we make up our own labels. Four steps:

We square the error to punish being badly wrong much harder than being slightly wrong, and it gives us a gradient of −2(y − Q(s, a)) pointing straight at the target. Lovely. Ship it.

It doesn't work. It fails in four separate ways, and each fix is a paper. This is the most interesting part of the post, so slow down here.

Problem 1: the target moves

Look at the target again. Notice the θ in it. That's the same weights we're currently updating. Which means every gradient step changes the label we were trying to hit.

Follow the loop: you nudge Q(s, a) up a bit. That raises max Q(s′, a′). Which raises the target. Which tells you to nudge up again. Which raises the target again. It's an upward spiral of value estimates floating off into space, and on the way up the model forgets everything it actually learned. That's catastrophic forgetting, and it is exactly as bad as it sounds.

How do we fix it? Keep a second copy of the network with weights θ′ that we update much less often, and compute the target with the stale copy. That's the target network, and it's the main innovation in the DQN paper.

Now the target sits still long enough for you to aim at it. One line of code. It's the reason DQN worked at all.

Problem 2: consecutive frames are nearly identical

In chess and Pong we're learning from a sequence of actions and states, and consecutive states are almost identical. Frame 400 and frame 401 of Pong differ by about four pixels. Train on them back to back and you've broken the one assumption every optimiser makes — that your samples are independent. The network overfits hard to the last few seconds of play and forgets the rest of the game.

Second problem, same paragraph: we see each experience once and throw it away. Which is a bit mad, given experience is the expensive thing here.

Simple fix for both: don't train in order. Dump transitions (s, a, R, s′) in a big pool and train on random batches pulled out of it. That's the experience replay buffer. Correlation broken, and every experience gets reused dozens of times instead of once.

There's an optimisation on top called prioritised experience replay: sample the transitions with big TD error more often. Makes sense — the experiences you're most wrong about are the ones with the most left to teach you.

Problem 3: the estimates are systematically too high

Our Q values come out too optimistic. Why? Because we're still using the same network to pick actions and to say how good those actions were. It's grading your own homework.

Here's the mechanism, and it's sneakier than "the network is biased". Every estimate can be perfectly unbiased on its own, and taking a max over them will still come out too high — because the max preferentially picks whichever action happened to get the luckiest noise. Then that inflated number goes into the target, and the model learns from itself, and you get a feedback loop of increasingly optimistic predictions.

Don't take my word for it. Below are five actions whose true value is exactly zero. Take the max:

Both boxes should say 0.00. The left one never does. And that error gets fed back through the Bellman update every single step, so it compounds.

Simple fix: use different networks for the two jobs. One picks which action looks best, the other says how good it was. That's Double Deep Q-learning. That's the whole idea, and the right-hand box above is it working.

Problem 4: the architecture asks the wrong question

Q(s, a) answers "how good is taking this action in this state". Fine. But that's secretly two questions crammed into one number:

• How good is it just to be in this state, regardless of what I do?
• How much better or worse is this specific action than the others?

Those are different things and jamming them together is inefficient in about three ways.

The fix that works is to explicitly separate the two estimates. One trunk, two heads: a value stream producing the scalar V(s), and an advantage stream producing a vector A(s, a) of how much better each action is than average. Recombine them:

Why subtract the mean? Because without it the split is ambiguous — you could add 100 to V and subtract 100 from every A and get exactly the same Q out. Nothing forces either stream to mean anything. Pinning the advantages to average zero fixes that. Now one reward teaches the network about the whole state at once, and the advantage head only has to learn differences.

The recap, as a ledger

This is the page in my notes I keep coming back to. Read the left column top to bottom and you've got the whole history of value-based deep RL as a list of complaints.

Rainbow DQN: all of it at once

By 2017 there were half a dozen separate improvements to DQN, each in its own paper, each claiming a bump on Atari. Obvious question: are these the same fix wearing different hats, or genuinely different fixes? Rainbow answered it the boring, correct way — stack all seven, then remove them one at a time and see what breaks. They stack. The combination beat every individual piece by a mile.

Two of those didn't come up above, so quickly:

Noisy nets throw out ε-greedy and put learnable noise inside the network's weights instead. So exploration becomes something gradient descent tunes for you, and it can differ by state, instead of being a decay schedule you guessed at. Remember me complaining that the decay rate has no principled setting? This is the answer to that.

Distributional RL is the one I find genuinely interesting. Instead of predicting the expected return, predict the whole distribution of returns. Think about it: an action that pays +100 or −100 on a coin flip has an expected value of 0. So does an action that reliably pays 0. Same number, completely different situations, and the expectation throws that away. Learning the full distribution gives you a better training signal even if you only ever act on the mean.

The ablations are worth a look too. Prioritised replay and multi-step returns did the heavy lifting — pull either one out and nearly every game got worse. Dueling and Double Q barely mattered once everything else was in. Which is a good lesson in itself: how much a fix is worth depends entirely on what you've already fixed.

On my list to read properly: the distributed variants that run hundreds of actors in parallel feeding one learner. That's how these things actually get trained at any real scale, and I've only skimmed it.

What happened after Rainbow

Almost every intro stops at Rainbow, which leaves you thinking value-based RL was finished in 2018. It wasn't. The work since is less famous because none of it came with a "computer beats human at game" headline — but it's the part that actually matters if you ever have to make one of these work on a real problem. Short version of each, because I'm still working through most of these myself.

One honest caveat on all of it. This lineage stayed in games, robotics and recommendation. The RL that became famous in 2023 onwards — the RL inside chat models and reasoning models — came from the policy-gradient branch instead, for reasons that are about to become obvious.

Where the road ends

Rainbow is about the ceiling for this approach, and the ceiling has a very specific shape. Every single method above works by estimating how good things are and then taking a max over actions. That max needs a finite list of actions to loop through. Robot arms don't have one. Steering angles don't have one. A language model picking a token has 100,000, and picking a whole response has effectively infinite.

And there's something a bit daft about the whole setup when you say it out loud. First we predict how good the state is. Then how good the next action is. Then we take a max. All to decide what to do.

Why not just… directly learn what action to take?

One thing to flag before you go, because I had this wrong for a while. The RL that trains reasoning models is not descended from DQN. GRPO, RLOO, DPO, the verifiable-reward stuff — all policy gradient, and several of them throw out the value network entirely. So if you're here specifically to understand post-training, part one is scaffolding. What carries over is the vocabulary: return, discount, advantage, on-policy, off-policy. Those words mean exactly the same thing over there. The algorithms don't come with them.

The other thing that carries over, and I think it's the most useful thing in this whole post, is the habit. Every fix above came from someone asking one narrow question: what specifically is my estimate wrong about, and why. Moving target. Correlated samples. Biased max. Wrong factorisation. Four problems, four patches, one at a time.

That's the same question you end up asking when a reward model gets gamed, or a policy collapses into writing the same length of answer every time. Which is why this history is worth knowing even if you never write a line of DQN. See you in part two.