Inside the Bellman loop: how value actually propagates

I went looking for a clean explanation of Bellman value iteration and kept bouncing off the same thing. The equation is written recursively:

def value(s):
    return reward(s) + gamma * value(next_state(s))

Recursion to a programmer means tree walking. Trees of futures. Stack frames. Maybe DFS. None of that is what value iteration actually does, and once you’ve half-believed the recursive picture you spend the next hour confused about how an infinite future is supposed to fit in memory.

This post is the version I wish someone had handed me. It’s about what the loop actually does inside, why the standard backup-diagram pictures are a bit of a trap, and why most of value iteration is much closer to spreadsheet recalculation than to recursive search.

It’s the third post in the Inside RL series. The first is the conceptual orientation; the second is about formalising your problem as an MDP. This one assumes you have a well-formed MDP and asks how the algorithm actually computes over it. The companion piece on the other side of the agent stack is Inside the ReAct loop — same shape of investigation, different loop.

The recursive bait

Take the Bellman equation in its compact form:

Read that the way a programmer reads code and you immediately picture this:

def value(s):
    if terminal(s):
        return reward(s)
    return reward(s) + gamma * value(next_state(s))

That function never returns in a continuing environment. The conceptual future is infinite. So either the author is hand-waving, or there’s a layer between the equation and the implementation that nobody is showing you.

There is. The recursion in the equation is a definition, not an execution plan. It tells you what relationship has to hold between V(s) and V(s') once the value table is correct. It does not tell you how to compute the table.

Backup diagrams aren’t execution traces

Open any RL textbook and the first picture is a backup diagram. A node, three branches, three children, dotted arrows showing value flowing back up. The book then says something like “value flows backward from the future to the present” and a programmer immediately translates that to “recursive expansion of the future.”

That is the trap. Backup diagrams are dependency diagrams — they show which estimates contribute to one update — not execution diagrams of an algorithm walking forward through time. If the same state appears at two leaves of the diagram, those two leaves are the same V[s] entry. They are not two recursive calls.

That distinction is the entire engineering reframing of value iteration. Once you see it, the rest falls out.

The mental shift the rest of this post argues for, condensed:

Each row reframes a piece of standard RL vocabulary as the system behaviour it actually produces at runtime. The rest of the post is a guided tour of why each row of the right column is the more useful frame.

The compression moment

This is the picture that fixed it for me. Start with the tree the equation seems to imply, then notice the same Markov state appears more than once. Then collapse it.

In a Markov decision process, “the same state” means exactly that — same future distribution, same downstream value. There is no benefit to evaluating two subtrees rooted at the same s. So you don’t. You keep one cell per state in a value table, and any predecessor that needs that future estimate reads the cell. The tree on the left is a conceptual model. The graph on the right is what your CPU actually does.

If you’ve ever used functools.lru_cache to turn a doubly-recursive Fibonacci into linear time, this is the same move. The Markov property says every repeated state is a cache hit. There is no future the cache doesn’t subsume.

One backup, one sweep

Now the real work. The RL term for “recompute one cell of the table from its downstream neighbours” is a backup, and it’s a confusingly chosen word — nothing is being saved or rolled back. It comes from “backing the value up the graph” toward predecessors, the way a manager backs up estimates from their reports. Every time you see “backup” in RL writing, mentally substitute “one cell update” and you’ll lose nothing.

A sweep is one backup for every state in the table, in some order. The cleanest analogy is one full pass of spreadsheet recalculation — every cell gets a chance to update from its neighbours before you check what changed.

A spreadsheet does exactly this. Cells have formulas that reference other cells; change one cell and the engine walks the dependency graph forward, recomputing whatever needs updating. Bellman value iteration is the same operation, with the value table standing in for the sheet and the Bellman equation standing in for the formulas.

Walk through it on a four-state chain. Discount is 0.9, the goal is worth 100, everything else is zero reward. The right column is the agent’s entire memory — that table is the state of the algorithm.

Three observations from stepping through it.

First, nothing recursive happens. Each backup is a single table read followed by a single table write. The cost of one sweep is exactly the number of states times the cost of one update. Linear, predictable, profileable.

Second, the environment doesn’t move. The transition graph, the rewards, the discount — all fixed across sweeps. What changes is the value table, not the world.

This was the one that tripped me up, and it’s worth unpacking slowly because it’s the moment the whole framework either clicks or stays murky. The natural programmer assumption — at least mine — is that “reaching S3 in 3 steps” must be a different thing from “reaching S3 in 10 steps.” The first feels more valuable. You got there faster. Common sense says faster paths are better. So surely V(S3 at step 3) and V(S3 at step 10) should be different numbers in the table?

In a pure MDP they aren’t. There is only one cell for S3, and it holds one number. Same state, same value. The Markov property says it directly: the future depends only on the current state, not on the path that got you there. From S3 onwards, the rest of the trajectory has the same distribution regardless of when you arrived. The expected sum of discounted future rewards has to be identical too. The “10 steps in” version of S3 doesn’t have a worse future ahead of it; it has exactly the same future ahead of it.

What is different is the discounted contribution S3 makes back to its predecessors. That distinction is the whole game. Take γ = 0.9, V(S3) = 100, and look at two different starting states upstream of it:

predecessor 3 steps from S3 → 0.9³  × 100 = 72.90
predecessor 10 steps from S3 → 0.9¹⁰ × 100 ≈ 34.87

V(S3) didn’t change. The discounted view from each predecessor did. The faster path looks more valuable because the predecessor’s equation applies fewer γ factors — not because S3 itself is worth more from one angle than another. The discount lives in the upstream cells, never in the destination cell.

Once you internalise that split, a bunch of RL behaviour stops looking like magic. Agents that “prefer” shorter trajectories, lower latency, fewer redundant actions — nobody coded those preferences in. They fall out of geometric discounting, applied automatically to every predecessor of every reward source. You get efficiency, urgency, and a bias toward decisive action without ever writing a reward function for any of them. That’s a remarkably high-leverage piece of mathematics for something most textbooks dispose of in a sentence about the discount factor.

The honest caveat is the one most beginner RL material skips. The whole argument above only holds because S3 actually is the same state at step 3 and at step 10. In a lot of real systems it isn’t. A robot’s battery has drained. The market’s opening hours are behind you. The deadline has moved. When that’s true, treating “S3 at step 10” as the same cell as “S3 at step 3” gives you a value table that doesn’t match reality, and the agent will make decisions that look bizarre — refusing to act now because some future plan is “just as good,” when in fact the future plan won’t have a battery left to execute it.

The fix isn’t to change the equation. It’s to expand the state. (S3, t=3) and (S3, t=10) become two cells, with their own values, derived from the same Bellman update. In finite-horizon RL this gets formalised as V_t(s) — “value of state s when t steps remain” — and the equation looks the same with one extra index. State augmentation is one of the most useful patterns to know in this whole area; it’s also one of the easiest to forget, which is how you end up with an agent that thinks every Tuesday is the same Tuesday.

The deeper point, the one the RL and control-theory communities keep making and the one that took me longer than it should have to absorb: “state” isn’t the physical configuration of the world. It’s whatever information you need to correctly predict the future. If the time of day changes the future distribution, the time of day is part of the state. If which user you’re serving changes the future, that’s state. If a queue’s current depth changes the future, that’s state. The Markov property isn’t a fact about the world — it’s a requirement your state representation has to satisfy. Anything you leave out that affects the future is a bug in your state definition, and the value table will be wrong in exactly the ways your omission predicts.

Third, the only thing that moves between sweeps is value, hop by hop, from the goal outward. Which raises an obvious question: does it matter what order you visit the states in?

Sync vs async, free 3× speedup

This is where the textbook story usually stops and the implementation lore takes over. There are two ways to run a sweep.

The clean, theoretically tidy version is synchronous: read all neighbour values out of V_old, write all results into V_new, then swap. Every state sees the same stale snapshot. Easy to reason about, easy to parallelise.

The faster version is asynchronous: update the table in place. Whichever state you visit next reads the freshest values its neighbours currently have, including any that were just written in this same sweep. If you traverse in the right order — outward from the goal — value cascades all the way to the start in a single pass.

Same graph. Same number of updates per pass. The asynchronous panel is at the fixed point after one sweep; the synchronous panel takes three. The difference is purely scheduling.

What’s actually different

Strip the labels off and the choice between sync and async is a single question: when an update writes a new value into the table, does the next update in the same pass get to see it?

Sync says no. Every update in the pass reads from a frozen snapshot of the previous pass’s values, and writes its result into a fresh table that no one will read until the pass is over. Updates don’t see each other. Each one is independent, which means a thousand of them can run in parallel without any coordination — but each one is also working from stale neighbours, so information only moves one hop per pass.

Async says yes. Each update reads whatever is currently in the table, including writes that earlier updates made in the same pass. Updates are no longer independent — they have to run in some order — but they get to see fresh neighbours, and if you happen to visit states in an order that respects the graph’s dependencies, a single pass can cascade value all the way from the goal to the start.

That’s the whole tradeoff: stale-but-parallel versus fresh-but-sequential. The same split shows up outside RL — numerical linear algebra has been arguing about it since the 1870s, where the two sides are called Jacobi and Gauss-Seidel — but the name isn’t load-bearing, the intuition is. RL inherited a hundred-year-old relaxation method; what it added was a graph to apply it to.

Picking who to update next

Async gives you fresh neighbours in the order you traverse — which raises the question of what order to traverse in when you don’t have a clean chain to walk down. The intuition that works: at any moment, ask each state how much would my value change if I recomputed it right now? Update the one with the biggest pending change. Then ask again.

The “how much would it change” number has a name in the RL literature — it’s called the Bellman residual — but it’s exactly what it sounds like. It’s the size of the update that’s queued up on that cell. A big residual means the cell is carrying stale information that everything downstream of it is still reading. Updating it first replaces that stale information with the freshest the algorithm currently has, and the freshness then radiates outward to whatever uses it.

The whole technique is called prioritised sweeping in the RL literature, but the mechanism is one most engineers have already built. It’s a priority queue keyed by “how much pending work is sitting here.” Pop the heaviest item, do the work, push anything affected back on with its new weight, repeat until the queue is empty.

Step through it. The queue starts with one entry — only S2 has anything new to learn from the Goal, because every other state’s neighbours are still at zero. One update there, and S2’s predecessors (S1 and S3) inherit pending updates of their own and get pushed onto the queue. Three pops later the queue is empty, the value field is converged, and no state was ever updated when it had nothing new to say.

The mental model that travels well is “do the heaviest pending work first.” Build systems use the same trick — don’t rebuild things that haven’t changed, and when something does, schedule its dependents. Reactive frameworks do it too. The RL name is just the version of that instinct applied to a Bellman update.

Why this isn’t a free lunch

Async sounds strictly better than sync, and on a single CPU running a moderate-sized MDP it usually is. But the parallelism story flips on bigger hardware. Sync’s stale-reads property is also its independence property — every cell reads from V_old and writes to V_new, so a thousand cells can update simultaneously with no coordination. On a GPU, where you have thousands of cores hungry for independent work, sync wins easily; the wasted information per sweep is more than paid for by the throughput. Async serialises by design: each update has to see the previous one’s write.

Most modern deep-RL systems lean sync for that reason — not because async is theoretically worse, but because the hardware they run on rewards independence.

The interesting failure mode at the other end is the opposite traversal order. Walk the chain forward in async mode — visit S1, then S2, then S3 — and it behaves no better than sync. Every node still reads stale neighbours, because the fresh information is being written downstream of where you’ve already been.

The wavefront moves at the speed of your traversal, in the direction of your traversal. Pick the wrong direction and you’ve lost the entire benefit.

This is the same lesson dynamic programming teaches in CS101 — fill the table in the order that respects dependencies — but it’s surprisingly easy to get wrong when the dependency graph isn’t acyclic. Prioritised sweeping side-steps the question by letting the residuals decide; fixed-order async lets you trip over it.

Discounting is just damping

The other thing the recursive view obscures is why this terminates at all. The cached values keep being rewritten using other cached values. Why don’t they oscillate forever, or blow up?

Because of γ. Discounting is the damping factor that turns the Bellman operator into a contraction mapping. Formally:

In English: each sweep cuts the worst-case error by at least a factor of γ. Errors shrink geometrically, so the value table converges to a unique fixed point. With γ = 1 and a positive-reward loop, the same equation diverges to infinity and there is no fixed point to find.

It’s worth being precise about what convergence actually is here, because the word makes it sound smaller than it is. The fixed point isn’t a number some single cell is converging to. It’s the entire value table reaching a state where every cell simultaneously agrees with its own Bellman equation — V(s) = R(s) + γV(s') holds for every state at once, with no leftover disagreement between neighbours.

The early iterations are full of local inconsistencies: V[S3] says 0, but plugging it into S2’s equation predicts something else; V[S2] is also 0, but its neighbours imply it shouldn’t be. Each sweep doesn’t pick one inconsistency to fix; it nudges every cell toward agreement with its neighbours, all at the same time.

The global consistency emerges from repeated local relaxation. That’s what’s actually converging — not a number, but a mutually consistent value field.

The other thing γ buys you is an effective planning horizon. Move the slider and watch the bars decay; 1/(1−γ) is roughly how many steps of future you can still feel from where you stand.

This is also why real RL systems run at γ = 0.99 or γ = 0.999 rather than 0.9. A planning horizon of ten steps is fine for grid worlds; it’s nowhere near enough for anything continuous. Pushing γ closer to 1 buys longer reach at the cost of slower convergence and more sensitivity to noise. Same trade-off you’d recognise from any low-pass filter — wider window, more lag.

The deeper point: convergence here isn’t an emergent property of the algorithm being clever. It’s a property of the Bellman operator being contractive, which is a property of γ being less than 1. The algorithm is barely doing anything — it’s iterating a contraction. The fixed-point theorem does the rest.

The family it belongs to

Once you see value iteration as repeated relaxation of a coupled system over a graph, it slots into a family of algorithms most engineers already understand.

Every entry in that table is the same shape: a set of values that depend on each other, an update rule that pulls each value toward consistency with its neighbours, and a contraction (explicit damping, monotonicity, finite state space, whatever) that guarantees you stop. The Bellman update is one row of that table. The RL community names it differently and writes the equation in expected-reward form, but the engineering substrate is the same.

If you’ve ever debugged a spreadsheet where one cell changed and you watched the cascade ripple through twenty others, you’ve watched value iteration. You just didn’t know it was called that.

What’s deliberately out of scope

Two things this post doesn’t touch on, both because they get their own posts in the series.

The first is action selection. Everything here works with V(s) — a single value per state — which is enough to talk about value propagation but never tells you which action to take from a given state. The version that does is Q(s, a), the action-value function, and the move from V to Q is the move from “this state is worth 72.9” to “from here, action A is worth 70 and action B is worth 75, so take B.” Same Bellman scaffolding, slightly bigger table. The next post in the series, Inside Q-learning, unpacks that move.

The second is what happens when the state space is too big to fit in a table. Atari frames, robot sensor streams, language model contexts — there’s no V[s] cell for every possible 84×84 image. The table becomes a function approximator (usually a neural network), and a small library of engineering tricks appears to recover the stability the table version got for free. That’s deep RL, and it’s the last post in the series: Inside deep RL.

Both sit on the same iterative-relaxation foundation this post walked through. The table is the bedrock; action selection and function approximation are what gets built on top.

Key takeaways

Three lines, in order.

The tree picture is for intuition. Use it to feel why a future state’s value matters to its predecessors. Don’t take it literally as an execution model.

The graph picture is the computation. Each state is one cell. Each backup is one read and one write. The “loop” is repeated traversal until nothing moves enough to care about.

The table is the implementation. When you sit down to code it, you’re maintaining V: dict[State, float], running a while loop, and stopping when max(abs(V_new[s] - V_old[s]) for s in states) < epsilon. Everything else in RL — action selection, function approximation, exploration, the deep variants — sits on top of that.

Once you have that ladder, the original equation reads completely differently. V(s) = R(s) + γ V(s') stops being a recursive definition that won’t terminate, and becomes the consistency constraint your iteration is trying to satisfy. The algorithm is a fixed-point solver. The math is what tells you the fixed point exists.

The same shape — stateless update function plus an external store that accumulates — shows up in another place this blog spends time on: tool-using LLM agents, where the transcript is the state and each tool call updates it. The mechanics are very different but the architecture rhymes. I wrote about the LLM side of it in Inside the ReAct loop. The Bellman loop is the older sibling.

If you want to go further, the entry points I’d give in order are: Sutton and Barto’s Reinforcement Learning chapter 4 for the canonical treatment of dynamic programming methods, David Silver’s RL lectures for a working researcher walking through the same material on a whiteboard, and Rich Sutton’s “The Bitter Lesson” for the strategic argument about why these methods keep winning. Read them in that order, then go reread the equation. It looks different from this side.