01 · MDPs & the RL Objective

What you're learning

The formal object every RL algorithm optimizes, built from the ground up: the Markov Decision Process, the return, policies, value functions, and the Bellman equations. By the end you should be able to write down $J(\pi )$, derive the Bellman expectation equations yourself, and see exactly why generating tokens from an LLM is an instance of this same structure — the seam we exploit in lesson 05.

This is lesson 01 of the rl-for-llms curriculum. Everything downstream — policy gradients, PPO, GRPO, RLHF — is a way of estimating or improving one of the quantities defined here. Get these anchors solid and the rest is machinery.

---

1. Learning map

graph TD
    A["Sequential decision problem<br/>(agent ↔ environment)"] --> B["Markov property<br/>state is sufficient"]
    B --> C["MDP tuple<br/>(S, A, P, R, γ)"]
    C --> D["Trajectory τ<br/>rollout"]
    D --> E["Return G_t<br/>discounted sum of reward"]
    C --> F["Policy π(a|s)"]
    E --> G["RL objective<br/>J(π) = E_τ[Σ γ^t r_t]"]
    F --> G
    G --> H["Value functions<br/>V^π, Q^π, A^π"]
    H --> I["Bellman expectation<br/>equations"]
    I --> J["Optimality<br/>V*, Q*, Bellman optimality"]
    J --> K["Greedy improvement"]
    G --> L["LLM as MDP<br/>(teaser → lesson 05)"]

    style G fill:#4a4,color:#fff
    style L fill:#a44,color:#fff
    style C fill:#44a,color:#fff

We build strictly bottom-up: the problem setup forces the Markov property, which lets us write the MDP, which gives us the return, which — combined with a policy — is the objective. Value functions are the bookkeeping that makes the objective tractable, and Bellman equations are the recursion that makes value functions computable.

---

2. Why this matters

Before any math, the motivation. Supervised learning optimizes a per-example loss against a fixed label. RL optimizes behavior against a scalar signal that (a) may be delayed, (b) depends on your own choices, and (c) doesn’t tell you what the right action was — only how good the outcome ended up being. That last point is the whole game: you get evaluative feedback (“that was worth 0.7”), not instructive feedback (“you should have done $a^{\ast }$”).

For LLMs this is the difference between next-token cross-entropy (imitate the data) and RLHF/RLVR (produce outputs a reward model or verifier scores highly). The moment you want a model to optimize for something you can score but can’t demonstrate token-by-token — helpfulness, correctness of a proof, a passing unit test — you are in the RL setting whether you call it that or not. This lesson gives you the object that setting optimizes.

The core reframe

In supervised learning the data distribution is fixed. In RL the distribution of states you visit depends on your policy — improving the policy changes the data. This coupling (policy → state distribution → objective → policy gradient) is the source of nearly every RL difficulty: non-stationarity, exploration, off-policy correction. Keep it in mind; it’s why RL is harder than it “should” be.

---

3. The problem setup

An agent interacts with an environment in discrete time steps $t=0,1,2,\dots$. At each step:

1. The agent observes a state $s_t\in \mathcal{S}$.
2. It selects an action $a_t\in \mathcal{A}$.
3. The environment returns a scalar reward $r_t\in \mathbb{R}$ and transitions to a new state $s_{t+1}$.

graph LR
    A["Agent"] -->|"action a_t"| E["Environment"]
    E -->|"state s_{t+1}"| A
    E -->|"reward r_t"| A

The environment’s dynamics are captured by a transition distribution. In full generality this could depend on the entire history $h_t=(s_0,a_0,s_1,a_1,\dots ,s_t)$. That would be intractable — the history grows without bound and we could never estimate $P(s_{t+1}\mid h_t,a_t)$ from finite data.

The Markov property

We make the problem tractable by choosing a state representation for which the future is conditionally independent of the past given the present:

$P(s_{t+1}\mid s_t,a_t,s_{t-1},a_{t-1},\dots ,s_0,a_0)=P(s_{t+1}\mid s_t,a_t)$

This is the Markov property: the state $s_t$ is a sufficient statistic of the history for predicting the future. Nothing you’d learn by looking further back changes your prediction.

Markov is a property of the representation, not the world

Almost any process can be made Markov by folding enough history into the state. A raw camera pixel frame is not Markov (you can’t tell velocity from one frame); stack four frames and it is. So “is this Markov?” is really “did I put enough in the state?” This is exactly the lever we pull for LLMs in §10 — we define the state to be the full prefix, which is trivially Markov.

Markov ≠ memoryless in the colloquial sense

A Markov state can encode arbitrarily long dependencies — it just has to encode them in the state. The constraint is that the transition function looks only at the current state, not that the current state is small or forgetful.

Quiz: Is a partially observed environment (you see an observation $o_t$, not the true state $s_t$) Markov in $o_t$?

Answer

Not in general. If $o_t$ is a lossy function of the true latent state, then $P(o_{t+1}\mid o_t,a_t)$ can still depend on earlier observations that carried information about the hidden state. This is a POMDP (partially observed MDP). The standard fix is to build a belief state (a posterior over latent states) or a summary of history — e.g. an RNN/transformer hidden state — that is Markov. Recovering a Markov state from observations is a core modeling problem, and it’s why sequence models pair so naturally with RL.

---

4. The MDP formalism

A Markov Decision Process bundles everything above into a tuple:

$\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma )$

Symbol	Name	Meaning
$\mathcal{S}$	State space	set of possible states
$\mathcal{A}$	Action space	set of possible actions (may depend on $s$)
$P(s^{\prime }\mid s,a)$	Transition kernel	dynamics; Markov by construction
$R(s,a)$ or $R(s,a,s^{\prime })$	Reward function	expected immediate reward, $r_t=R(s_t,a_t)$
$\gamma \in [0,1]$	Discount factor	how much future reward is worth now

Often an initial state distribution ${\rho }_0(s_0)$ is included. Some formulations fold reward into the transition as a joint $P(s^{\prime },r\mid s,a)$ (this is Sutton & Barto’s convention¹); it changes nothing structural.

Trajectories / rollouts

Running a policy in the MDP produces a trajectory (a.k.a. rollout, episode):

$\tau =(s_0,a_0,r_0,s_1,a_1,r_1,\dots )$

Its probability under policy $\pi$ factorizes cleanly because of the Markov property:

$p_{\pi }(\tau )={\rho }_0(s_0){\prod }_{t\ge 0}\pi (a_t\mid s_t)P(s_{t+1}\mid s_t,a_t)$

This factorization is the engine of policy gradients

Notice $P$ does not depend on the policy parameters, but $\pi (a_t\mid s_t)$ does. When we later differentiate $\log p_{\pi }(\tau )$ w.r.t. policy params, the environment terms drop out entirely — we never need to know or differentiate the dynamics. That’s what makes model-free policy gradients possible, and it’s the whole reason lesson 02 works. Anchor it now.

An episode is episodic if it terminates (reaches a terminal state, after which no more reward accrues) or continuing if it runs forever. LLM generation is episodic — it ends at EOS or a length cap.

---

5. The return: what “good” means over time

A single reward $r_t$ isn’t the objective — we care about cumulative reward from now on. Define the return from time $t$ as the discounted sum of future rewards:

$G_t={\sum }_{k=0}^{\infty }{\gamma }^k{r}_{t+k}=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots$

which satisfies the recursion we’ll lean on constantly:

$G_t=r_t+\gamma G_{t+1}$

Why discount at all? Why $\gamma <1$?

Three independent motivations converge on the same $\gamma$:

1. Mathematical convergence. In a continuing task with bounded rewards $|r|\le R_{\max }$, the undiscounted sum diverges. With $\gamma <1$ it’s bounded: $|G_t|\le \frac{R_{\max }}{1-\gamma }$ (geometric series). This alone forces $\gamma <1$ for infinite-horizon problems.
2. Uncertainty / hazard. $\gamma$ can be read as a per-step survival probability: with prob $1-\gamma$ the episode ends before the next step. Discounting = valuing reward you’re more likely to actually collect.
3. Preference for sooner reward. Like a financial discount rate — reward now beats identical reward later.

$\gamma$ sets the effective horizon

The effective planning horizon is roughly $\frac{1}{1-\gamma }$ steps: $\gamma =0.99\Rightarrow \sim 100$ steps, $\gamma =0.9\Rightarrow \sim 10$ steps. Larger $\gamma$ = more far-sighted but higher-variance and harder-to-optimize (credit must propagate further). It is a genuine hyperparameter of the problem statement, not just the algorithm.

$\gamma$ is not innocuous for finite-horizon / sparse-reward tasks

Many LLM RL setups have a single terminal reward at step $T$. Then $G_0={\gamma }^T{r}_T$, and the choice of $\gamma$ silently down-weights long generations. In practice LLM-RL often uses $\gamma =1$ (undiscounted, finite horizon) precisely to avoid penalizing length — and manages variance through other means (baselines, per-token advantages). Don’t cargo-cult $\gamma =0.99$ into a sparse terminal-reward setting.

Quiz: With bounded reward $|r_t|\le 1$ and $\gamma =0.95$, what is the tightest upper bound on $|G_t|$?

Answer

$|G_t|\le {\sum }_{k=0}^{\infty }{\gamma }^k\cdot 1=\frac{1}{1-\gamma }=\frac{1}{0.05}=20$. This $\frac{R_{\max }}{1-\gamma }$ bound is worth memorizing — it appears constantly in RL analysis (error bounds, value clipping ranges, etc.).

---

6. Policies

A policy is the agent’s behavior: a mapping from states to actions.

• Stochastic: $\pi (a\mid s)$ is a distribution over actions. This is the general case and the one used for LLMs (the softmax over the vocabulary is a stochastic policy).
• Deterministic: $a=\mu (s)$, a single action per state. A special case, common in continuous control (DDPG², TD3³).

Why stochastic policies are the default in RL

Two reasons. (1) Exploration — a stochastic policy naturally tries different actions, which you need to discover which are good (§9). (2) Differentiability — for discrete actions, ${\pi }_{\theta }(a\mid s)$ as a softmax gives a smooth objective you can take gradients through, whereas $\arg \max$ does not. For LLMs the policy is literally ${\pi }_{\theta }(a_t\mid s_t)=\mathrm{softmax}(z_t)$ over the vocabulary, with $\theta$ the network weights and temperature controlling entropy.

A policy $\pi$ together with the MDP induces the trajectory distribution $p_{\pi }(\tau )$ from §4. Everything we optimize is an expectation under this distribution.

---

7. The RL objective

Now we can state what RL actually optimizes. Given the induced trajectory distribution, the objective is the expected return:

$J(\pi )={\mathbb{E}}_{\tau \sim p_{\pi }}\left[{\sum }_{t=0}^{\infty }{\gamma }^t{r}_t\right]={\mathbb{E}}_{\tau \sim p_{\pi }}\left[G_0\right]$

The goal of RL is to find

${\pi }^{\ast }=\arg {\max }_{\pi }J(\pi ).$

That’s it. Every algorithm in this curriculum — REINFORCE, actor-critic, PPO, GRPO — is a strategy for climbing $J(\pi )$ when you cannot compute it in closed form and can only sample trajectories.

What makes maximizing $J$ hard

You can’t differentiate $J(\pi )$ naively: the reward comes from an environment you don’t have gradients through, and the distribution you’re averaging over depends on the parameters you’re optimizing. The trajectory factorization (§4) is precisely what lets us get an unbiased gradient estimate anyway — that’s the log-derivative / REINFORCE trick, and it’s the entire content of lesson 02. For now, just internalize: $J(\pi )=\mathbb{E}[G_0]$ is the target.

Quiz: Two policies achieve the same expected return $J(\pi )$ but ${\pi }_A$ has much higher variance in $G_0$ across episodes. Are they equally good to the RL objective as stated?

Answer

Yes — the objective as written, $\mathbb{E}[G_0]$, is risk-neutral and cares only about the mean. Variance doesn’t enter. If you do care about worst-case or risk (a very live concern for deployed LLMs), you’re optimizing a different objective (e.g. CVaR, distributional RL, or a variance-penalized return). It’s worth being precise about this: much confusion comes from assuming the objective penalizes variance when it doesn’t unless you put it there.

---

8. Value functions: making the objective tractable

$J(\pi )=\mathbb{E}[G_0]$ is a single number about the start. To improve a policy we need to know how good individual states and actions are. Enter value functions.

State-value function — expected return starting from state $s$ and following $\pi$ thereafter:

$V^{\pi }(s)={\mathbb{E}}_{\tau \sim \pi }[G_t\mid s_t=s]$

Action-value (Q) function — same, but you commit to action $a$ first, then follow $\pi$:

$Q^{\pi }(s,a)={\mathbb{E}}_{\tau \sim \pi }[G_t\mid s_t=s,a_t=a]$

They’re linked by averaging over the policy’s action choice:

$V^{\pi }(s)={\mathbb{E}}_{a\sim \pi (\cdot \mid s)}[Q^{\pi }(s,a)]={\sum }_a\pi (a\mid s)Q^{\pi }(s,a)$

Advantage function — how much better is action $a$ than the policy’s average behavior at $s$:

$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$

The advantage is the single most important quantity for policy-gradient RL

$A^{\pi }(s,a)>0$ means ”$a$ beats what I’d usually do here — do more of it.” $A^{\pi }<0$ means “do less.” Note ${\mathbb{E}}_{a\sim \pi }[A^{\pi }(s,a)]=0$ by construction — the advantage is centered, which is exactly why subtracting $V^{\pi }$ as a baseline reduces gradient variance without adding bias (lesson 02). PPO⁴ and GRPO are, at their core, machinery for estimating $A^{\pi }$ well and taking controlled steps in its direction. GRPO’s trick is estimating the baseline $V$ from a group of sampled completions rather than a learned critic⁵ — but that’s getting ahead of ourselves.

Bellman expectation equations

Value functions have recursive structure — a direct consequence of $G_t=r_t+\gamma G_{t+1}$. Take the definition of $V^{\pi }$, peel off one step, and use the Markov property:

$V^{\pi }(s)={\mathbb{E}}_{a\sim \pi }[R(s,a)+\gamma {\mathbb{E}}_{s^{\prime }\sim P}[V^{\pi }(s^{\prime })\left]\right]$

Written out over the distributions:

$\boxed{V^{\pi }(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime }}P(s^{\prime }\mid s,a)[R(s,a)+\gamma V^{\pi }(s^{\prime })]}$

and analogously for $Q$:

$\boxed{Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)\sum _{a^{\prime }}\pi (a^{\prime }\mid s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })}$

These are the Bellman expectation equations⁶¹. They turn “sum an infinite horizon” into “one step of reward plus the discounted value of where you land.” That recursion is what makes value functions estimable — you can bootstrap $V^{\pi }(s)$ from $V^{\pi }(s^{\prime })$ (temporal-difference learning) instead of waiting for full returns.

Bellman expectation vs. Bellman optimality — don't conflate them

The equations above evaluate a fixed policy $\pi$ (they’re linear in $V$). The optimality equations in §9 involve a $\max$ (nonlinear) and characterize the best policy. “Bellman equation” is ambiguous — always know which one is meant.

Quiz: Derive the Bellman expectation equation for $V^{\pi }$ from $G_t=r_t+\gamma G_{t+1}$ in one line. Where exactly is the Markov property used?

Answer

$V^{\pi }(s)=\mathbb{E}[G_t\mid s_t=s]=\mathbb{E}[r_t+\gamma G_{t+1}\mid s_t=s]={\mathbb{E}}_{a,s^{\prime }}[R(s,a)+\gamma \mathbb{E}[G_{t+1}\mid s_{t+1}=s^{\prime }]]$. The last step — replacing $\mathbb{E}[G_{t+1}\mid s_t=s,a_t=a,s_{t+1}=s^{\prime }]$ with $\mathbb{E}[G_{t+1}\mid s_{t+1}=s^{\prime }]=V^{\pi }(s^{\prime })$ — is exactly where Markov is used: the future return depends on history only through the current state $s^{\prime }$. Without Markov you couldn’t collapse the conditioning and the recursion wouldn’t close.

---

9. Optimality and greedy improvement

There exists an optimal value function — the best achievable value at each state over all policies:

$V^{\ast }(s)={\max }_{\pi }{V}^{\pi }(s),Q^{\ast }(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$

A key theorem (for finite MDPs): there is always at least one deterministic optimal policy, and all optimal policies share the same $V^{\ast },Q^{\ast }$.¹ The optimal values satisfy the Bellman optimality equation — same recursion, but with $\max$ replacing the policy expectation:

$V^{\ast }(s)={\max }_a{\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)[R(s,a)+\gamma V^{\ast }(s^{\prime })]$
$Q^{\ast }(s,a)=R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a){\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })$

Greedy improvement (brief)

Given any $Q^{\pi }$, the greedy policy ${\pi }^{\prime }(s)=\arg {\max }_a{Q}^{\pi }(s,a)$ is guaranteed to be at least as good as $\pi$ (the policy improvement theorem). Alternating evaluate (compute $V^{\pi }$) and improve (go greedy) is policy iteration, and it converges to ${\pi }^{\ast }$.¹ Note the beautiful fact: ${\pi }^{\ast }$ is greedy w.r.t. its own $Q^{\ast }$ — that self-consistency is exactly the Bellman optimality equation.

Why LLM-RL rarely uses pure greedy/value iteration

Value/policy iteration assume a known, enumerable $P$ and a tractable $\arg \max$ over actions. LLMs have a known transition (deterministic string append!) but an astronomically large state space and a $|\mathcal{V}|$-way action set — you can’t sweep states. So LLM-RL is almost entirely policy-gradient / actor-based (sample trajectories, estimate advantages, nudge ${\pi }_{\theta }$), not value-iteration-based. The value function still shows up, but as a baseline/critic (PPO) or an implicit group baseline (GRPO), not as the thing you $\arg \max$ over.

Quiz: The Bellman optimality equation replaces ${\sum }_a\pi (a\mid s)$ with ${\max }_a$. What property does this destroy, and why does it matter computationally?

Answer

It destroys linearity. The Bellman expectation operator is affine in $V$, so evaluating a fixed policy is a linear system solvable in closed form. The $\max$ makes the optimality operator nonlinear (piecewise-linear, convex), so you can’t just invert a matrix — you iterate the operator (value iteration), relying on it being a $\gamma$-contraction in $\Vert \cdot {\Vert }_{\infty }$ to guarantee convergence to the unique fixed point $V^{\ast }$.⁷ This contraction property is the theoretical backbone of nearly all value-based RL.

---

10. LLM connection: generation is an MDP

Here is the reframe that makes this entire curriculum apply to language models.⁸ Consider an LLM generating a response token by token. Map it onto the MDP tuple:

MDP element	LLM instantiation
State $s_t$	the prompt + all tokens generated so far: $s_t=(x,y_{1:t})$
Action $a_t$	the next token $y_{t+1}\in \mathcal{V}$
Policy ${\pi }_{\theta }(a_t\mid s_t)$	the model’s softmax over the vocabulary
Transition $P(s_{t+1}\mid s_t,a_t)$	deterministic append: $s_{t+1}=s_t\Vert a_t$
Episode / trajectory	the full generated sequence, ending at EOS or length cap
Reward $r_t$	often 0 for all $t$ except the last — a single terminal score from a reward model or verifier

Two structural features make the LLM MDP special:

1. The transition is deterministic and known. Appending a token to a string has no stochasticity — $P$ is a delta function. All randomness lives in the policy. This is unusual and simplifying compared to control/robotics.
2. The state is trivially Markov. Since $s_t$ is the entire prefix, the future depends on nothing but $s_t$ by construction — no POMDP headaches (§3). We got Markov for free by defining the state as the whole context.

Sparse, terminal reward is the defining challenge

In RLHF/RLVR the reward typically arrives only at the end: $r_T=\text{RM}(x,y_{1:T})$ (or a 0/1 verifier), with $r_t=0$ otherwise. So $G_t={\gamma }^{T-t}{r}_T$ for every step — every token in the sequence shares credit for one terminal scalar. How to distribute that single reward across all the token-actions that produced it is the credit-assignment problem, and it is exactly what the advantage function $A^{\pi }(s,a)$ (§8) exists to solve. This is why PPO/GRPO spend all their effort estimating per-token advantages.

Don't over-read the analogy yet

The mapping is exact, but the algorithms need care: the action space is $\sim 10^5$ (huge softmax), the horizon is hundreds of tokens, and the “environment” (reward model) is itself a learned, gameable approximation. Reward hacking, KL-regularization to a reference policy, and length bias are all consequences we’ll tackle later. For now the takeaway is only the mapping itself.

Quiz: Given the deterministic-transition observation, simplify the trajectory probability $p_{\pi }(\tau )$ (§4) for an LLM. What survives?

Answer

Since $P(s_{t+1}\mid s_t,a_t)=1$ for the appended token and $0$ otherwise, every transition factor is $1$. So $p_{\pi }(\tau )={\rho }_0(s_0){\prod }_t{\pi }_{\theta }(a_t\mid s_t)$ — and with a fixed prompt, $p_{\pi }(\tau )={\prod }_t{\pi }_{\theta }(y_{t+1}\mid x,y_{1:t})$. That’s just the model’s sequence likelihood. The consequence is profound: $\log p_{\pi }(\tau )={\sum }_t\log {\pi }_{\theta }(y_{t+1}\mid s_t)$ is fully differentiable in $\theta$, so the policy-gradient log-derivative term (lesson 02) is literally the per-token log-prob you already compute during training. RL on LLMs reuses the exact same forward/backward pass as pretraining — only the weighting changes. This is the seam lesson 05 opens up.

---

11. Reading order

Work through these in order:

1. Primary text — value functions & Bellman: Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), Chapter 3 (Finite MDPs) — the definitive treatment of §§3–9 here. Then Chapter 4 (Dynamic Programming) for policy/value iteration and greedy improvement. Free PDF: incompleteideas.net/book/the-book-2nd.html
2. Intuition + notation you’ll reuse: OpenAI Spinning Up, “Part 1: Key Concepts in RL” — states/actions/policies, the RL objective $J(\pi )$, value functions, and the Bellman equations, in exactly the notation the rest of this curriculum uses.
3. Discounting done carefully: Sutton & Barto §3.3–3.4 (returns, episodic vs. continuing, the unified notation) — clears up the $\gamma =1$ vs $\gamma <1$ subtlety flagged in §5.
4. Optional depth (contraction/convergence proofs): Bertsekas, Dynamic Programming and Optimal Control, Vol. I — for the Bellman operator as a $\gamma$-contraction and why value iteration converges.
5. Bridge to LLMs (read after lesson 02): Ziegler et al., “Fine-Tuning Language Models from Human Preferences” — the paper that first cast LLM generation as the MDP in §10.

---

12. Practice problems

Practice problem 1: Terminal reward and effective credit

Problem: An LLM generates a sequence of $T=200$ tokens. The only nonzero reward is $r_T=1$ at the final step; all earlier rewards are 0. (a) Write $G_t$ for an arbitrary step $t<T$ as a function of $\gamma$. (b) With $\gamma =0.99$, compute the return credited to the first token vs. the last-generated token. (c) What does this imply, and why do many LLM-RL setups set $\gamma =1$?

Worked solution:
(a) With reward only at the end, $G_t={\sum }_{k=0}^{T-t}{\gamma }^k{r}_{t+k}={\gamma }^{T-t}{r}_T={\gamma }^{T-t}$.
(b) First token: $t\approx 0$, $G_0={\gamma }^{200}=0.99^{200}\approx 0.134$. Last token ($t=T$, or the step producing the final action): $G\approx {\gamma }^0=1$. So the discounting silently gives the first token $\sim 7\times$ less credit than the last — even though early tokens (e.g. setting up a correct chain of thought) may matter more.
(c) Discounting a sparse terminal reward introduces a positional bias unrelated to actual causal contribution, and penalizes longer correct answers. Setting $\gamma =1$ (finite horizon) gives every token equal claim to the terminal reward, letting the advantage estimator — not an arbitrary $\gamma$ — do the credit assignment. This is why GRPO⁵ and many PPO-for-LLM recipes use $\gamma =1$ (and often $\lambda$ close to 1 in GAE⁹).

Practice problem 2: Advantage is a re-centering, not new information

Problem: Show that for any state $s$, ${\sum }_a\pi (a\mid s)A^{\pi }(s,a)=0$. Then explain in one sentence why this makes $V^{\pi }(s)$ a variance-reducing baseline in the policy gradient but leaves the gradient unbiased.

Worked solution:
${\sum }_a\pi (a\mid s)A^{\pi }(s,a)={\sum }_a\pi (a\mid s)[Q^{\pi }(s,a)-V^{\pi }(s)]=\underset{=V^{\pi }(s)}{\underbrace{\sum _a\pi (a\mid s)Q^{\pi }(s,a)}}-V^{\pi }(s)\underset{=1}{\underbrace{\sum _a\pi (a\mid s)}}=V^{\pi }(s)-V^{\pi }(s)=0.$
Because the advantage sums to zero under $\pi$, subtracting the baseline $V^{\pi }(s)$ from $Q^{\pi }(s,a)$ in the policy gradient contributes ${\mathbb{E}}_a[\nabla \log \pi \cdot V^{\pi }(s)]=V^{\pi }(s){\mathbb{E}}_a[\nabla \log \pi ]=0$ in expectation — so the gradient’s mean is unchanged (unbiased) while its variance drops, since we no longer scale $\nabla \log \pi$ by the large, high-variance raw return. (Full derivation in lesson 02.)

---

13. What’s next

You now have the object every RL algorithm optimizes and the LLM mapping that makes it relevant. The next thread:

• 02-policy-gradients — how to actually climb $J(\pi )$ when you can only sample trajectories: the log-derivative trick, REINFORCE, baselines, and why the advantage function from §8 is the right thing to weight by. This is where the LLM seam from §10 becomes an algorithm.

Further out in the curriculum: actor-critic and GAE (estimating $A^{\pi }$ well) → PPO (controlled policy steps) → GRPO (group baselines, no critic) → the full RLHF/RLVR pipeline.

Before moving on, self-check

Can you (1) state $J(\pi )$ from memory, (2) derive the Bellman expectation equation for $V^{\pi }$, and (3) fill in the MDP tuple for an LLM without looking? If any of those is shaky, re-read the relevant section — everything downstream compounds on these three.

---

References

---

Part of rl-for-llms | Lesson 01 | Filed: 2026-09-02

Footnotes

1. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Finite MDPs, returns, value functions, and the Bellman expectation equations: Chapter 3. Existence of a deterministic optimal policy, the Bellman optimality equations, the policy improvement theorem, and convergence of policy iteration: Chapter 4 (Dynamic Programming). Free PDF: http://incompleteideas.net/book/the-book-2nd.html ↩ ↩² ↩³ ↩⁴

2. Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., & Wierstra, D. (2015). “Continuous Control with Deep Reinforcement Learning” (DDPG). arXiv:1509.02971. https://arxiv.org/abs/1509.02971 ↩

3. Fujimoto, S., van Hoof, H., & Meger, D. (2018). “Addressing Function Approximation Error in Actor-Critic Methods” (TD3). arXiv:1802.09477. https://arxiv.org/abs/1802.09477 ↩

4. Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). “Proximal Policy Optimization Algorithms.” arXiv:1707.06347. https://arxiv.org/abs/1707.06347 ↩

5. Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., Zhang, H., Zhang, M., Li, Y. K., Wu, Y., & Guo, D. (2024). “DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models.” arXiv:2402.03300. Introduces Group Relative Policy Optimization (GRPO), which replaces the learned critic with a group-relative (per-prompt) baseline. https://arxiv.org/abs/2402.03300 ↩ ↩²

6. Bellman, R. (1957). Dynamic Programming. Princeton University Press. Original formulation of the Bellman equation / principle of optimality for dynamic programming. ↩

7. Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control, Vol. I (4th ed.). Athena Scientific. Treats the Bellman operator as a $\gamma$-contraction in the sup-norm $\Vert \cdot {\Vert }_{\infty }$ and the convergence of value iteration to the unique fixed point. ↩

8. Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., & Irving, G. (2019). “Fine-Tuning Language Models from Human Preferences.” arXiv:1909.08593. Early formulation of autoregressive LLM generation as an RL/MDP problem with a reward model. https://arxiv.org/abs/1909.08593 ↩

9. Schulman, J., Moritz, P., Levine, S., Jordan, M., & Abbeel, P. (2015). “High-Dimensional Continuous Control Using Generalized Advantage Estimation” (GAE). arXiv:1506.02438. Introduces the $\lambda$ bias–variance knob for advantage estimation. https://arxiv.org/abs/1506.02438 ↩