# Deriving Reinforcement Learning from the Bellman Equation

A café is either Quiet or Busy. Each period you can **serve** the customers who are there, or **prepare**: earn nothing today and make a Busy afternoon more likely. On average over a Quiet or Busy start, serving every period is worth 4.2 in discounted pay and preparing when Quiet and serving when Busy is worth 5.3. Neither policy is wrong in any single period. The second wins because the value of a state depends on where it leads, and where it leads depends on what you do there.

<figure class="mfig pf-figure" id="rl-bellman" aria-label="Each state's value equals what it pays now plus the discounted values of where it leads">
<div class="pf-plot"></div>
<figcaption><b>A value is a fixed point: it equals its own one-step backup.</b> Drag the probability of preparing when Quiet: both bars in each row stay the same length, because the value on top is the sum of the pieces below.</figcaption>
</figure>

That circularity is the **Bellman equation**, and almost all of reinforcement learning (RL) is a way of living with it. This essay derives it from a probability model, and then does something less usual: it re-adds the same rewards by *place* instead of by *time*. That move turns the problem into a linear program, turns policies into points of a polytope, and makes the zoo of RL subfields look like one picture seen from different distances.

The derivation has three steps. A value is the fixed point of a contraction, which says what an optimal answer is. The same quantity can be written as an inner product with a discounted occupancy, which says where the answer lives. And each subfield (model-based, model-free, online, offline, language-model RL) is a choice about which piece of that picture to estimate from data. The figures use one small exact model, the café, so every moving quantity has a known meaning. Where a figure has a ring handle, drag it, or focus the figure and use the arrow keys.

One colour code runs through the essay and the figures: <span class="k-data">blue</span> is what is given (rewards, data), <span class="k-policy">copper</span> is what the agent does (policy, occupancy), and <span class="k-value">violet</span> is value, the hidden quantity every Bellman equation is about.

## A decision process is a probability model

A **Markov decision process** (MDP) is a set of assumptions. Writing them down is most of the work, because every later claim can be traced to one of them.

1. **Finite states and actions.** States $s\in S$, actions $a\in A$. (The café: Quiet and Busy; Serve and Prepare.)
2. **The Markov property.** The next state depends on the past only through the current state and action: $P(s'\mid s,a)$.
3. **Stationarity.** $P$ and the reward $r(s,a)$ do not change with time.
4. **Bounded rewards.** $|r|\le r_{\max}$, so every sum below converges.
5. **Discounting.** A reward $t$ steps away is worth $\gamma^t$ with $0\le\gamma<1$.
6. **A start distribution** $\mu$ over states, with every state possible.

| State, action | Pays now | Next: Quiet | Next: Busy |
| --- | --- | --- | --- |
| Quiet, Serve | 0.3 | 0.9 | 0.1 |
| Quiet, Prepare | 0 | 0.2 | 0.8 |
| Busy, Serve | 1 | 0.7 | 0.3 |
| Busy, Prepare | 0 | 0.1 | 0.9 |

The café has $\gamma=0.9$ and starts Quiet or Busy with equal chance. A **policy** $\pi(a\mid s)$ says how to act in each state. A policy and an MDP together fix a probability distribution over whole trajectories $s_0,a_0,r_0,s_1,\dots$, and the **return** is $R=\sum_{t\ge0}\gamma^t r_t$. The objective is its expectation, $J(\pi)=\mathbb E[R]$.

Discounting has a probabilistic reading that pays off later. Suppose a clock ticks each period and stops the game with probability $1-\gamma$. Then $\gamma^t$ is the chance the game is still running at time $t$, and the discounted return is the *expected undiscounted* reward collected before the clock stops. The stopping time is geometric, with mean $1/(1-\gamma)$ periods.

## The Bellman equation is a consistency condition

The **value** of a state under $\pi$ is $V^\pi(s)=\mathbb E[G\mid s_0=s]$. Peel off the first step. The reward now is $r(s,a)$. What remains is the same game, started from the next state, shrunk by $\gamma$:

$$
\begin{gathered}
V^\pi(s)=\sum_a\pi(a\mid s)\Big[r(s,a)\\
+\gamma\sum_{s'}P(s'\mid s,a)\,V^\pi(s')\Big].
\end{gathered}
$$

In vector form, with $P_\pi$ the state-to-state matrix under $\pi$ and $r_\pi$ the reward it pays, this is $V^\pi=r_\pi+\gamma P_\pi V^\pi$. The unknown sits on both sides. It is an equation to *solve*, not a recursion to run, and it has exactly one solution:

$$
\begin{gathered}
V^\pi=(I-\gamma P_\pi)^{-1}r_\pi\\
=\sum_{t\ge0}\gamma^tP_\pi^t\,r_\pi .
\end{gathered}
$$

The inverse exists because $P_\pi$ is a stochastic matrix, so $\gamma P_\pi$ has spectral radius at most $\gamma<1$ and the series converges. The series is the same fact the other way round: the repeated one-step backup *is* the discounted sum over time. The **action value** $Q^\pi(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')$ is the bracket in the first display, and $V^\pi(s)$ is its average under $\pi$.

The figure at the top already shows why this matters. Drag the handle from "never prepare" to "always prepare when Quiet". Serving every period gives $V(\text{Quiet})=3.77$ and preparing when Quiet gives $4.97$, even though preparing pays nothing now. A policy that grabs the reward in front of it is blind to the second and third bars in each row.

## Optimality is the fixed point of a contraction

The best value in each state satisfies the same equation with an average replaced by a maximum:

$$
\begin{gathered}
V^\star(s)=\max_a\Big[r(s,a)\\
+\gamma\sum_{s'}P(s'\mid s,a)\,V^\star(s')\Big].
\end{gathered}
$$

Write the right-hand side as $(TV)(s)$. Then $V^\star=TV^\star$ is a fixed-point equation for the **Bellman optimality operator** $T$, and $T$ is a **contraction** in the max norm:

$$
\begin{gathered}
\|TV-TW\|_\infty\\
\le\gamma\,\|V-W\|_\infty .
\end{gathered}
$$

<details class="more"><summary>Derivation: why T contracts</summary>

Fix a state $s$ and an action $a$. The difference of the two brackets is $\gamma\sum_{s'}P(s'\mid s,a)\,(V-W)(s')$. Since $P(\cdot\mid s,a)$ is a probability vector, that is at most $\gamma\lVert V-W\rVert_\infty$ in absolute value. Maxima are 1-Lipschitz: $\lvert\max_a x_a-\max_a y_a\rvert\le\max_a\lvert x_a-y_a\rvert$. Combining the two gives the inequality for every $s$.

</details>

A contraction on a complete space has exactly one fixed point, and iterating it from any start converges geometrically: $V_k=T^kV_0$ satisfies $\lVert V_k-V^\star\rVert_\infty\le\gamma^k\lVert V_0-V^\star\rVert_\infty$ (Banach). That is **value iteration**. The figure runs it from two very different guesses; the dashed squares are the bound.

<figure class="mfig pf-figure" id="rl-contraction" aria-label="Value iteration from two starts shrinks inside max-norm balls around the optimal value">
<div class="pf-plot"></div>
<figcaption><b>Every backup shrinks the distance to the answer by at least a factor of the discount.</b> Drag the number of backups: both runs stay inside their squares, which contract by 0.9 per step, and meet at the optimal value.</figcaption>
</figure>

Acting greedily with respect to $V^\star$ gives an optimal policy, and the greedy choice is a *deterministic* one. In the café it prepares when Quiet and serves when Busy. **Policy iteration** reaches it differently: evaluate the current policy exactly, switch every state to its best action under that evaluation, and repeat. Each round can only improve the value, and with finitely many deterministic policies it stops after finitely many rounds. Both algorithms are about *values*. Nothing so far says where the agent spends its time, and that is the question the rest of the essay turns on.

## Re-add the same reward by place, not by time

Write the return as a sum over time, $\sum_t\gamma^t\,\mathbb E[r_t]$. Each term depends on where the agent is at time $t$. Collect the terms by **where** instead: how much discounted time does the agent spend in each state-action pair? That quantity is the **discounted occupancy**:

$$
\begin{gathered}
\htmlClass{eq-policy}{d^\pi}(s,a)=(1-\gamma)\sum_{t\ge0}\gamma^t\\
\times\Pr(s_t=s,\,a_t=a\mid\pi,\mu).
\end{gathered}
$$

It sums to one, so it is a probability distribution, and it has a clean reading in terms of the geometric clock. It is the law of the state and action *at the moment the clock stops*. Re-adding the reward by place gives

$$
\begin{gathered}
J(\pi)=\frac{1}{1-\gamma}\,\big\langle \htmlClass{eq-policy}{d^\pi},\ \htmlClass{eq-data}{r}\big\rangle\\
=\frac{1}{1-\gamma}\sum_{s,a}d^\pi(s,a)\,r(s,a).
\end{gathered}
$$

The expected reward at the stopping moment, times the expected number of periods. The two routes to $J$ are the same sum in a different order, and the figure adds both.

<figure class="mfig pf-figure" id="rl-regroup" aria-label="The same discounted reward added up by period and by state-action pair reaches the same total">
<div class="pf-plot"></div>
<figcaption><b>Adding by period and adding by place give one number.</b> Drag the number of periods included, for a policy that flips a fair coin in every state: the two stacked totals grow together and approach its return. Here $d_T$ is the unnormalised discounted visit count through period $T$, and the Prepare columns are empty because preparing pays nothing. The dashed outlines are the occupancy in the limit.</figcaption>
</figure>

The occupancy has a second description that carries all the structure. Follow $\pi$, but at each step restart from $\mu$ with probability $1-\gamma$. This is an ordinary Markov chain, and $d^\pi$ is its stationary distribution. Stationarity says that what flows into each state equals what flows out:

$$
\begin{gathered}
\sum_a d(s',a)=(1-\gamma)\,\mu(s')\\
+\gamma\sum_{s,a}P(s'\mid s,a)\,d(s,a)\\
\text{for every }s'.
\end{gathered}
$$

These **flow constraints** involve only $P$ and $\mu$. They do not mention $\pi$ or $r$. Everything about the policy is in how mass is split among the actions of each state, and everything about the reward is in the inner product. The objective is **linear** in $d$. The nonlinearity of RL, which comes from a policy acting on a chain, has been moved into the shape of the constraint set.

## The dual linear program

The Bellman optimality equation says $V^\star$ is the smallest vector that is at least the one-step backup of itself. That is a linear program (Manne, 1960). Over all value vectors $V$:

$$
\begin{gathered}
\min_V\ (1-\gamma)\langle\mu,V\rangle\\
\text{subject to}\quad V(s)\ \ge\ r(s,a)\\
+\gamma\sum_{s'}P(s'\mid s,a)\,V(s')\\
\text{for all }(s,a).
\end{gathered}
$$

Any feasible $V$ satisfies $V\ge TV$, and applying $T$ repeatedly (it preserves order) shows $V\ge V^\star$. So $V^\star$ is the pointwise smallest feasible vector, and minimizing a positive weighting of it, which needs $\mu>0$, picks it out. This linear program has one constraint per state-action pair. Its dual has one variable per state-action pair, and the variables are an occupancy.

<details class="more"><summary>Derivation: the dual from a Lagrangian</summary>

Attach a multiplier $d(s,a)\ge0$ to each constraint:

$$
\begin{gathered}
\mathcal L(V,d)=(1-\gamma)\langle\mu,V\rangle\\
+\sum_{s,a}d(s,a)\Big[r(s,a)\\
+\gamma\sum_{s'}P(s'\mid s,a)V(s')\\
-V(s)\Big].
\end{gathered}
$$

$V$ is unconstrained, so the minimum over $V$ is finite only if the coefficient of every $V(s')$ vanishes. That coefficient is $(1-\gamma)\mu(s')+\gamma\sum_{s,a}P(s'\mid s,a)d(s,a)-\sum_a d(s',a)$. Setting it to zero is exactly the flow constraint. What remains of $\mathcal L$ is $\sum_{s,a}d(s,a)\,r(s,a)$.

</details>

The dual is the occupancy picture, stated as an optimization:

$$
\begin{gathered}
\max_{d\ge0}\ \langle \htmlClass{eq-policy}{d},\htmlClass{eq-data}{r}\rangle\\
\text{subject to}\\
\text{the flow constraints.}
\end{gathered}
$$

By strong duality the two optima agree, $\langle d^\star,r\rangle=(1-\gamma)\langle\mu,V^\star\rangle$, and the roles are symmetric. The occupancy $d$ is the flow that the constraints route through the MDP. The value $V$ is the **price** the constraints put on being in a state: the shadow price of the flow constraint at that state. Values are not an invention of dynamic programming; they are multipliers.

Duality also gives optimality a second reading. Complementary slackness says a constraint with a positive multiplier is tight. Define the **advantage** $A^\star(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\star(s')-V^\star(s)$, which is at most zero by the constraints. Then

$$
d^\star(s,a)A^\star(s,a)=0\quad\forall(s,a):
$$

an optimal agent spends time only on actions whose advantage is zero. That is the Bellman optimality condition, read from the dual side.

## The state–action polytope

The feasible set of the dual is $\mathcal D=\{d\ge0:\ \text{flow constraints hold}\}$. It is a polytope. Three facts say what it contains.

1. **Every policy is a point.** The occupancy $d^\pi$ of any stationary policy satisfies the flow constraints, so it lies in $\mathcal D$.
2. **Every point is a policy.** Take any $d\in\mathcal D$ and set $\pi_d(a\mid s)=d(s,a)/\sum_{a'}d(s,a')$. Then $d$ solves the flow constraints for $\pi_d$, and for a fixed policy that system has only one solution (the matrix $I-\gamma P_\pi^\top$ is invertible). So $d=d^{\pi_d}$. Stochastic policies fill the interior.
3. **The corners are the deterministic policies.** Every state has mass at least $(1-\gamma)\mu(s)>0$, which is where full support of $\mu$ is used. A corner of the polytope has at most $|S|$ nonzero entries, because there are only $|S|$ independent equations. Each state needs at least one, so each has exactly one action.

A linear objective on a polytope is maximized at a corner. So **a deterministic stationary policy is optimal**, which we found by iteration before and now see from geometry: no randomness, no memory, no time dependence is needed. The polytope has dimension $|S|(|A|-1)$, which is 2 for the café, so it can be drawn flat.

<figure class="mfig pf-figure" id="rl-polytope" aria-label="The four deterministic policies are the corners of a quadrilateral; a rotating reward picks the optimal corner">
<div class="pf-plot"></div>
<figcaption><b>The reward is a direction, and the optimal policy is the corner it touches last.</b> Turn the reward arrow. The dashed line is a level set of the objective through the best corner. The hollow dot inside is the policy that flips a fair coin in every state. The axes are two of the four occupancy numbers; the other two follow from the flow constraints.</figcaption>
</figure>

Reading the picture is the point. The axes are the discounted time spent serving in each state. Turn the arrow and the optimum jumps between corners at the angles where an edge becomes perpendicular to the reward. Corners whose policies differ in one state's action are joined by an edge, so the **simplex method** on the dual walks policies one state at a time, while policy iteration changes every improving state at once, a shortcut across the polytope rather than a walk along an edge; for a fixed discount, Howard's policy iteration and Dantzig's pivoting rule are both known to run in strongly polynomial time (Ye, 2011). The picture also hints at why gradient methods on policies can work despite the nonconvexity of $J$ in $\pi$: the objective is linear in $d$, and the policy parameterization only curves the coordinates. A proof needs more than that hint, namely a gradient-domination argument.

## Reinforcement learning is estimating a piece of this picture

Everything above assumed $P$ and $r$ were known. That is **planning**, and it is the exact side of the table. Learning begins when they are not, and each subfield is a choice about what to estimate and what data to estimate it from.

| Setting | What you have | What you estimate | Where it lives in the picture |
| --- | --- | --- | --- |
| Model-based | Transitions you sampled | $\hat P,\hat r$, then solve exactly | A perturbed polytope |
| Model-free | Transitions you sampled | $V$ or $Q$ directly | The fixed point, by noisy backups |
| Online | Transitions you choose | The same, plus where to look | Optimism over plausible polytopes |
| Offline | A fixed dataset | The same, from $d^b$ | The part of the polytope the data covers |
| Language-model RL | Sampled completions and a reward | A baseline for the value | The one-step case |

### Model-based and model-free: which half do you estimate?

The Bellman equation has two ingredients: a model and a fixed point. A **model-based** method estimates the model, $\hat P(s'\mid s,a)$ and $\hat r$ from counts, and then solves the estimated MDP exactly, as if it were the truth. The error is the distance between two polytopes: the true one and the one built from $\hat P$. A **model-free** method skips the model. One observed transition $(s,a,r,s')$ gives a single sample of the backup, $r+\gamma\max_{a'}Q(s',a')$, whose mean is exactly $(TQ)(s,a)$. Averaging with a step size,

$$
\begin{gathered}
Q(s,a)\ \leftarrow\ Q(s,a)\\
+\alpha\Big[r+\gamma\max_{a'}Q(s',a')\\
-Q(s,a)\Big],
\end{gathered}
$$

is **Q-learning**: a stochastic approximation of the contraction's fixed point, which converges when every pair is visited infinitely often and the step sizes shrink suitably (Watkins and Dayan, 1992; Tsitsiklis, 1994). The contraction in the previous section is what makes this safe: each step moves toward a map that shrinks errors by $\gamma$, and decaying step sizes average the sampling noise out. Model-free methods store a value table or a network. Model-based methods store a simulator, and they can reuse data for other rewards. Neither is better in general, and the choice is mostly about what is easier to represent.

### Online RL: exploration and exploitation

When the agent chooses what data to collect, the estimates depend on its own behaviour. The simplest case has one state, so there is no Bellman recursion left, only uncertainty: a **bandit**. Arm A has been pulled 200 times with an average of 0.62. Arm B has an average of 0.55 from a handful of pulls. The average says "pull A". The honest statement is that B's true mean could still be well above 0.62, and the only way to find out is to pull it.

**Optimism** turns that into a rule: act as if the best world still consistent with the data were true. UCB1 pulls the arm with the highest upper bound $\hat m_k+\sqrt{2\ln N/n_k}$ (Auer, Cesa-Bianchi and Fischer, 2002).

<figure class="mfig pf-figure" id="rl-optimism" aria-label="Two arms with confidence intervals; the rarely pulled arm's upper bound is highest until enough pulls shrink it">
<div class="pf-plot"></div>
<figcaption><b>Optimism pulls whichever arm could still be best.</b> Drag the number of pulls of arm B on the log scale: its interval narrows, and by 120 pulls its upper bound drops below arm A's and the choice flips.</figcaption>
</figure>

The same idea scales to MDPs. In value iteration, add a bonus to each backup that shrinks with the visit count, and the resulting optimistic value iteration has regret of order $\sqrt{HSAT}$ in finite-horizon problems with horizon $H$, up to logarithms and lower-order terms, once $T$ is large (Azar, Osband and Munos, 2017). In the occupancy picture, optimism is a search over *plausible polytopes*: play the policy that is best in some MDP the data have not ruled out, which is, in spirit, how UCRL2 chooses (Jaksch, Ortner and Auer, 2010; it is stated for the average-reward setting). More data shrinks the set of plausible polytopes to the true one.

### Offline RL: searching only where the data cover

Now the data are fixed, collected by some behaviour policy $b$, and the agent cannot try anything. The data tell you about the occupancy $d^b$, and about nothing far from it. Evaluating a different policy $\pi$ from this data requires the ratio $d^\pi/d^b$, which is exactly the importance weight over occupancies. When $d^\pi$ puts mass where $d^b$ has none, the data cannot say what happens there.

A clean way to see the consequence is to ask for a **coverage multiple** $C$: the agent may only consider occupancies with $d(s,a)\le C\,d^b(s,a)$ for every pair. That is the polytope intersected with four half-planes.

<figure class="mfig pf-figure" id="rl-coverage" aria-label="The region of the polytope covered by data grows with the coverage multiple until it contains the optimum">
<div class="pf-plot"></div>
<figcaption><b>Data cover a region of the polytope, and the best covered policy can fall short of the best policy.</b> Drag the coverage multiple. The blue region is where the data allow a claim; the filled copper dot is the best policy inside it, and the hollow one is the best overall.</figcaption>
</figure>

In the figure the behaviour policy serves with probability $0.75$ when Quiet and $0.30$ when Busy. The best policy is reachable only once $C$ reaches $C^\star=\max d^\star/d^b\approx3.7$, a quantity closely related to the single-policy concentrability coefficient of offline-RL theory. Below it, the best covered policy earns less. **Pessimism** says to commit to what the data support: choose the policy with the best lower confidence bound on its value. Under that rule, theory ties the error to coverage of a good policy rather than of every policy, and it recovers the $1/N$ rate of imitation learning when the data come from a near-expert, against the usual $1/\sqrt N$ (Rashidinejad, Zhu, Ma, Jiao and Russell, 2021). Occupancy-based methods estimate the ratio $d^\pi/d^b$ directly through the same duality as above (Nachum and Dai, 2020).

The figure uses a hard constraint and the exact model. A real offline method replaces the hard constraint with a penalty that grows where estimates are uncertain, and its estimates carry error that the figure leaves out.

### Language models: a one-step problem with a group baseline

A language model is a policy over tokens. A prompt $q$ is the start state, the completion $o$ is the trajectory, and a verifier or reward model scores it once at the end. (The note uses $x,y$ for prompt and completion; here $q,o$ follow the GRPO paper.) Treated as one step, the discount is irrelevant and each prompt has its own simplex of completion distributions. The value of the prompt is $V(q)=\mathbb E_{o\sim\pi}[r(q,o)]$. When the only reward comes at the end, the Bellman recursion collapses: nothing needs to be bootstrapped, and the value is a plain expectation.

The policy gradient is $\nabla J=\mathbb E\big[(r(q,o)-b)\,\nabla\log\pi(o\mid q)\big]$, and any baseline $b$ that does not depend on $o$ leaves it unbiased and only changes its variance. The natural baseline is $V(q)$. PPO learns it with a critic network, usually as large as the policy. **GRPO** (Shao et al., 2024) samples a group of $G$ completions for the same prompt and uses the group itself, with $r=(r_1,\dots,r_G)$ the rewards of the $G$ completions:

$$
\hat A_i=\frac{r_i-\operatorname{mean}(r)}{\operatorname{std}(r)} .
$$

The numerator is a Monte Carlo estimate of the advantage with the group mean standing in for $V(q)$. In the paper's outcome-supervised form, every token of completion $i$ receives that same $\hat A_i$.

<figure class="mfig pf-figure" id="rl-grpo" aria-label="Eight sampled answers to one prompt; correct ones get positive advantage and wrong ones negative, and a group that all agrees gives none">
<div class="pf-plot"></div>
<figcaption><b>A group is its own baseline, and a group that agrees teaches nothing.</b> Drag the boundary to change how many of the eight answers are correct. Advantages sum to zero; at zero or eight correct they all vanish.</figcaption>
</figure>

Three consequences follow from the algebra. The advantages sum to zero in every group, so the update pushes up what beat the group and pushes down what did not. A group in which every completion earns the same reward has zero standard deviation and so contributes no gradient. And the group mean includes the sample it is correcting, which shrinks the gradient by a factor of $(G-1)/G$ in expectation, so leave-one-out baselines remove that bias at the price of nothing. The standard deviation here is the population one; implementations differ by a factor of $\sqrt{G/(G-1)}$.

The reference policy enters through a **KL penalty**, which the GRPO paper adds to the loss rather than to the reward. The one-step problem has an exact answer. Maximizing $\mathbb E_{o\sim\pi}[r(q,o)]-\beta\,\mathrm{KL}(\pi\,\Vert\,\pi_{\mathrm{ref}})$ over distributions on completions gives

$$
\begin{gathered}
\pi^\star(o\mid q)=\frac{\pi_{\mathrm{ref}}(o\mid q)e^{r(q,o)/\beta}}{Z(q)},\\
\max=\beta\log Z(q),
\end{gathered}
$$

because the objective equals $\beta\log Z-\beta\,\mathrm{KL}(\pi\,\Vert\,\pi^\star)$. This is the Bellman equation's **soft** form: the hard maximum becomes a log-sum-exp, and the optimal policy is a tilted copy of the reference. It is also the closed form that direct preference optimization starts from (Rafailov et al., 2023).

What the language-model setting gives up is credit assignment. Outcome supervision treats a long completion as a single action. Methods that keep a critic or use per-step rewards bring back the Bellman structure token by token, at the cost of learning a value function that is accurate at every position.

## What stays the same

Everything above is one object read in two languages.

| Question | Bellman side | Linear-program side |
| --- | --- | --- |
| What is the unknown? | Value $V$ | Occupancy $d$ |
| What is the objective? | $\mu$-weighted value, minimized | Reward inner product, maximized |
| What is optimal? | A fixed point of $T$ | A corner of the polytope |
| What does optimality mean? | Greedy with respect to $V^\star$ | Occupied actions have zero advantage |
| What does learning estimate? | $T$, from samples | The polytope and the reward, from data |

The subfields differ in what they estimate and what data they use, but they answer to the same two descriptions. A model-based method builds an approximate polytope. A model-free one follows noisy contractions to a fixed point. An online method keeps the set of polytopes the data allow and acts on the best. An offline method refuses to leave the part of the polytope the data reach. A language-model method has one simplex per prompt, and replaces the value by a sample average.

Back to the café. Serving every period is worth 4.2 and preparing when Quiet is worth 5.3. The first is the corner you reach by following the reward in front of you, and the second is the corner the objective touches last. The difference is not a trick of this example: it is the gap between a policy that is greedy about rewards and one that is greedy about values, and both Bellman and the polytope are ways of seeing it.

## Further reading

- [Puterman — *Markov Decision Processes*](https://onlinelibrary.wiley.com/doi/book/10.1002/9780470316887). The standard reference for the model, the operators and the linear-programming formulation.
- [Sutton and Barto — *Reinforcement Learning: An Introduction*](http://incompleteideas.net/book/the-book-2nd.html). Values, backups and the learning methods in Sections 3, 4 and 6.
- [Manne — *Linear programming and sequential decisions*](https://doi.org/10.1287/mnsc.6.3.259), Management Science 6(3), 1960. The original linear-programming formulation of the discounted problem.
- [de Farias and Van Roy — *The linear programming approach to approximate dynamic programming*](https://doi.org/10.1287/opre.51.6.850.24925). Why the LP view survives function approximation.
- [Nachum and Dai — *Reinforcement Learning via Fenchel-Rockafellar Duality*](https://arxiv.org/abs/2001.01866). The occupancy view applied to evaluation and policy optimization, online and offline.
- Watkins and Dayan — *Q-learning*, Machine Learning 8, 1992, and [Tsitsiklis — *Asynchronous stochastic approximation and Q-learning*](https://doi.org/10.1007/BF00993306), Machine Learning 16, 1994. Convergence of the model-free fixed-point iteration.
- [Ye — *The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate*](https://pubsonline.informs.org/doi/fpi/10.1287/moor.1110.0516). Policy iteration and the simplex method as walks on the polytope.
- [Auer, Cesa-Bianchi and Fischer — *Finite-time analysis of the multiarmed bandit problem*](https://doi.org/10.1023/A:1013689704352), Machine Learning 47, 2002. UCB1.
- [Azar, Osband and Munos — *Minimax Regret Bounds for Reinforcement Learning*](https://arxiv.org/abs/1703.05449). Optimistic value iteration.
- [Jaksch, Ortner and Auer — *Near-optimal Regret Bounds for Reinforcement Learning*](https://jmlr.org/papers/v11/jaksch10a.html). Optimism over plausible MDPs.
- [Rashidinejad et al. — *Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism*](https://arxiv.org/abs/2103.12021). Coverage, pessimism and the spectrum between offline RL and imitation.
- [Shao et al. — *DeepSeekMath*](https://arxiv.org/abs/2402.03300). The GRPO objective, its group advantage and its KL term.
- [Rafailov et al. — *Direct Preference Optimization*](https://arxiv.org/abs/2305.18290). The closed form of the KL-regularized optimum.