Foundations — Bellman equations

This page assumes nothing. Before we can read a single boxed formula in the parent note, we must earn every letter in it. We will meet each symbol, draw the picture it stands for, and say why the topic cannot live without it. Read top to bottom — each item leans on the one above.

1. The world as a set of rooms — the state $s$

The picture. Imagine a tiny 2×2 grid of rooms. Standing in a particular room is being in a particular state. The letter $s$ is just a name-tag we pin on a room.

Why the topic needs it. Every value question begins "how good is it to be in this state?" Without a name for "where we are," there is nothing to attach a number to. The set of all possible states is written $\mathcal{S}$; a next state (the room we step into) gets an apostrophe: $s^{\prime }$, read "s-prime."

2. The moves you can make — the action $a$

The picture. From a room, arrows point to the doors. Picking action $a$ = "right" means walking through the right-hand door. A next action (chosen from the room you arrive in) is $a^{\prime }$, "a-prime."

Why the topic needs it. Value depends on what you do. The action-value function $Q^{\pi }(s,a)$ literally asks "how good is choosing door $a$ from room $s$?" — impossible to phrase without a symbol for the door.

3. The point score — the reward $r$ and $R_{t+1}$

Two notations, one idea:

• $r$ — a generic reward value (a possible payout, used inside sums).
• $R_{t+1}$ — the actual reward received on the step from time $t$ to time $t+1$. The capital $R$ with a subscript is a random variable: before you move you don't know the exact number, you only know its probabilities.

The picture. As the agent hops room→room, a little number pops up on each arrow it crosses. Collect them all and you have a stream of rewards $R_1,R_2,R_3,\dots$

Why the topic needs it. Reward is the only signal telling the agent what "good" means. Everything — value, policy, optimality — is built to maximise collected reward.

4. Time steps and the subscript $t$

The picture. Freeze the walk into frames. Frame $0$: agent in $s$. Frame $1$: agent in the next room having collected $R_1$. The subscript on $R_{t+1}$, $S_t$, $A_t$ just says which frame.

Why the topic needs it. The value is a sum over future time: ${\sum }_{t=0}^{\infty }$. Without a clock there is no "future" to sum over.

5. Distant reward counts less — the discount factor $\gamma$

The picture. Stack bars for the reward you get now, next step, the step after… Multiply each successive bar by $\gamma$, then ${\gamma }^2$, then ${\gamma }^3$. The bars fade toward zero — near reward is tall and bright, far reward is short and dim.

Why this tool and not just "add everything"? If you simply added infinitely many rewards of, say, $+1$, you would get $\infty$ — a useless value that can't be compared. Multiplying by ${\gamma }^t$ with $\gamma <1$ makes a geometric series that converges to a finite number: $1+\gamma +{\gamma }^2+\cdots =\frac{1}{1-\gamma }.$ That is exactly why the parent note insists $\gamma \in [0,1)$ — the half-open bracket keeps the sum finite. See Discount Factor for the full story.

6. Averaging over uncertainty — the expectation $\mathbb{E}[\cdot ]$

The picture. A wheel of fortune split into slices. Each slice is an outcome; the slice's width is its probability. Spin many times, average the payouts — that average is $\mathbb{E}[X]$.

Why the topic needs it. Two things are uncertain in RL: which door the policy picks, and where the world actually drops you. Value must be an average over both, so every value function carries an $\mathbb{E}$. The subscript ${\mathbb{E}}_{\pi }$ just says "averaging while following policy $\pi$."

7. The agent's habit — the policy $\pi$

The picture. In each room, the doors are tinted by how likely the agent is to use them. A "uniform random" policy tints all four doors equally ($0.25$ each). A confident policy paints one door bright and the rest faint.

Why the topic needs it. Value is always relative to behaviour. $V^{\pi }$ means "value if you keep acting like $\pi$." Change the habit, change the value. The whole point of RL is to reshape $\pi$ toward the best possible one, written ${\pi }^{\ast }$ ("pi-star"). Policy Gradient Methods tune $\pi$ directly.

8. The rules of the world — the dynamics $p(s^{\prime },r\mid s,a)$

The picture. Standing in room $s$, you push door $a$. The world rolls its own dice and lands you in some $s^{\prime }$ with some $r$. $p$ lists how likely each landing is. In a deterministic grid, one landing has probability $1$ and the rest $0$.

Why the topic needs it. The agent's future depends on the world's response, not just its own choice. $p$ is the world's contribution to the average — that's the inner ${\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)$ in every Bellman equation.

This "the future only depends on the current state and action, not the whole history" property is what makes the world a Markov Decision Process.

9. The number we chase — the return and the value functions $V^{\pi },Q^{\pi }$

The picture. Take the fading reward bars from §5 and sum their heights. That single total height is the return.

Why two of them? $V$ answers "how good is this room?"; $Q$ answers "how good is this specific door from this room?" — and $Q$ is what Q-Learning learns directly, because comparing doors is exactly how you pick the best action.

The link between them: since $V$ averages $Q$ over the doors the policy might pick, $V^{\pi }(s)={\sum }_a\pi (a\mid s)Q^{\pi }(s,a).$

10. The whole trick in one line — bootstrapping and the $\max$

The return $G_t$ obeys a tiny self-referential identity — split off the first reward: $G_t=R_{t+1}+\gamma G_{t+1}.$ "Total future = one step now + a $\gamma$-shrunk copy of the total future from next step." Taking expectations turns this into the Bellman equation. Replacing an unknown value by an estimate of the next value is called bootstrapping — see Bootstrapping and Temporal Difference Learning.

The picture. Line up the $Q$-values for every door out of a room; $\max$ picks the tallest bar, $\arg \max$ points to it. This is the optimal agent's rule: always walk through the tallest-value door.

Why $\max$ vs. the averaging ${\sum }_a\pi$? A fixed policy $\pi$ averages over its (possibly random) door choices → use ${\sum }_a\pi (a\mid s)$. An optimal agent is no longer random — it chooses the best door → use ${\max }_a$. That single swap turns a Bellman expectation equation into a Bellman optimality equation.

Prerequisite map

Everything on this page pours downward into the parent Bellman Equations note. If any box above is fuzzy, that boxed formula there will feel like magic instead of arithmetic.

Equipment checklist

Test yourself — cover the right side and answer aloud.