Skip to main content
Chapter 1 ran a scripted agent through the clamp repair. The agent read, edited, tested, and submitted, and the hidden tests then returned one number. Before we can ask a model to learn that behavior, we need a precise language for it. That language must say what the agent controls, what it observes, what is random, what the objective is, and how the quality of a decision is measured when its consequence arrives several turns later. This chapter supplies that language. It is the standard theory of Markov decision processes, but every object is built in a few lines of torch on a repair MDP, a seven-state abstraction of the clamp episode. Because the MDP is tiny, we can compute values exactly with a linear solve, check them against sampling, find the optimal policy, and differentiate the objective with autograd. None of those exact computations survive the move to a language model, and seeing precisely why they fail explains the design of everything from Chapter 6 onward. We save two functions for the rest of the book, discounted_return and policy_evaluation, plus the repair MDP builder and value_iteration, which later chapters use as exact references.

​
2.1 Markov Decision Processes

An RL problem has two parts: an agent that chooses actions, and an environment that responds. The interface between them is a loop. At each step tt the environment is in a state sts_t, the agent chooses an action ata_t, and the environment returns a reward rtr_t and a next state st+1s_{t+1}. The loop ends when the environment reaches a terminal state. A Markov decision process (MDP) formalizes that loop as a tuple (S,A,P,R,ρ0,γ)(\mathcal{S}, \mathcal{A}, P, R, \rho_0, \gamma):
  • S\mathcal{S} is the set of states and A\mathcal{A} the set of actions.
  • P(s′∣s,a)P(s' \mid s, a) is the transition probability of moving to s′s' after taking aa in ss.
  • R(s,a)R(s, a) is the expected immediate reward for taking aa in ss.
  • ρ0\rho_0 is the distribution of the initial state.
  • γ∈[0,1]\gamma \in [0, 1] is the discount factor (Section 2.4).
The word Markov is a claim about the state: the distribution of (rt,st+1)(r_t, s_{t+1}) depends on the history only through (st,at)(s_t, a_t), Pr⁡(st+1,rt∣s0,a0,…,st,at)=Pr⁡(st+1,rt∣st,at).\Pr(s_{t+1}, r_t \mid s_0, a_0, \dots, s_t, a_t) = \Pr(s_{t+1}, r_t \mid s_t, a_t). That property is what makes a state a state. Everything in this chapter depends on it, and Section 2.7 and the design problems return to the cases where it fails.

​
The repair MDP

We abstract the clamp episode into seven states. The agent starts with the file unread. Reading moves it to read. Editing produces either edited_ok or edited_bad, and the probability of a correct edit depends on whether the agent is informed: an edit made after reading the file, or after seeing a failing test, succeeds with probability 0.8; any other edit is a guess that succeeds with probability 0.3. Testing an edited file moves it to passed or failed. Submitting ends the episode in done and pays reward 1 if the file is correct, 0 otherwise. All numbers are invented for teaching; they are not measured on any model.
repair_transitions is the specification in words: reading is only useful once, testing only changes an edited file, and every edit is a fresh random draw. Reading or testing in other states leaves the state unchanged, which is a self-loop that costs a step. A tabular MDP stores PP as a tensor of shape [S, A, S] and RR as [S, A]. We fill both from the specification. The terminal state done gets an all-zero row in PP: an episode that reaches it simply stops. This makes PP substochastic (rows sum to 1 for live states and 0 for the terminal state), a convention that lets us solve for values without special-casing termination.
The reward lives on the submit action from a correct state. An optional step_cost charges every action; Section 2.9 uses it. Let us check the tensors.
Output:
Every live state-action row is a probability distribution, the terminal row is zero, and the only positive rewards are in the submit column for edited_ok and passed. Figure 2.1 draws the same tensors. Figure 2.1: The repair MDP. Solids are states, tracks are transitions labeled with action and probability, and the two accented (blue) submissions pay reward 1. Follow the two edit branches. From unread a guess lands in edited_ok only 30% of the time. From read or failed the informed edit succeeds 80% of the time. The test arrows do not change whether the file is correct; they only move the agent to a state that reports it. Under full observability, as here, a report of something the agent already knows has no value. Section 2.7 shows that it acquires value as soon as the agent cannot see the state.

​
2.2 Policies, Trajectories, and Returns

A policy π(a∣s)\pi(a \mid s) is a distribution over actions for each state. In a tabular MDP it is a tensor policy: [S, A] whose rows sum to 1. A deterministic policy puts all of its mass on one action per state. For a language model, the policy is the model itself: πθ(a∣s)\pi_\theta(a \mid s) is the probability that the model emits action aa given its context. A policy and an MDP together define a distribution over trajectories τ=(s0,a0,r0,s1,a1,r1,…,sT)\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_T): pπ(τ)=ρ0(s0)∏t=0T−1π(at∣st) P(st+1∣st,at).p_\pi(\tau) = \rho_0(s_0) \prod_{t=0}^{T-1} \pi(a_t \mid s_t)\, P(s_{t+1} \mid s_t, a_t). The factorization separates what the agent controls (π\pi) from what it does not (ρ0\rho_0 and PP). That separation is the reason policy gradients work without a model of the environment: Chapter 6 differentiates log⁡pπ(τ)\log p_\pi(\tau) and the PP factors vanish because they do not depend on θ\theta. The return of a trajectory is the discounted sum of its rewards, G0=∑t=0T−1γtrt,G_0 = \sum_{t=0}^{T-1} \gamma^{t} r_t, and the objective of RL is the expected return from the initial distribution, J(π)=Eτ∼pπ[G0]J(\pi) = \mathbb{E}_{\tau \sim p_\pi}[G_0]. For a parameterized policy we write J(θ)J(\theta). Computing a return is the first function we save.
Output:
With γ=1\gamma = 1 both trajectories are worth 1: the return only records whether the repair succeeded. With γ=0.9\gamma = 0.9 the faster success is worth 0.92=0.810.9^2 = 0.81 and the slower one 0.93=0.7290.9^3 = 0.729, so discounting also encodes when. The padding zero after the second trajectory’s reward changes nothing, which is why padded reward tensors are safe here as long as padding is zero. To estimate JJ we can sample. The function below rolls out one episode by drawing an action from policy[s] and a next state from P[s, a] until the terminal row is reached.
We need concrete policies. deterministic_policy turns a list of one action name per state into a one-hot [S, A] tensor. We define three policies that we will use throughout the chapter:
  • careful reads, edits, tests, submits after a pass, and re-edits after a failure;
  • read-edit-submit reads, edits once, and submits without testing;
  • blind edits immediately and submits.
Now sample. Each line prints one episode of the careful policy as a sequence of actions with the state they led to.
Output:
The careful policy always ends with a successful submission, but the episode length is random: each failed test adds another edit and test. The randomness comes from the environment (PP), not the policy, which is deterministic. A Monte Carlo estimate of JJ averages returns over many episodes.
Output:
These are estimates with standard errors (see Appendix A.1). Under γ=0.9\gamma = 0.9 the careful policy is ahead of read-edit-submit, but by less than its 20-point advantage in success probability (1.0 versus 0.8) suggests, because its successes arrive later and are discounted more. Next we compute the same numbers exactly.

​
2.3 Value Functions and the Bellman Equations

The return from a single episode is noisy. The state-value function averages it out: Vπ(s)=Eπ[∑k≥0γkrt+k ∣ st=s],V^\pi(s) = \mathbb{E}_\pi\Big[\sum_{k \ge 0} \gamma^k r_{t+k} \,\Big|\, s_t = s\Big], and the action-value function conditions on the first action as well: Qπ(s,a)=Eπ[∑k≥0γkrt+k ∣ st=s,at=a].Q^\pi(s, a) = \mathbb{E}_\pi\Big[\sum_{k \ge 0} \gamma^k r_{t+k} \,\Big|\, s_t = s, a_t = a\Big]. Split the return into the first reward and the rest. The rest, from st+1s_{t+1} on, is a return of the same kind, so its conditional expectation is Vπ(st+1)V^\pi(s_{t+1}). This gives the Bellman expectation equations: Qπ(s,a)=R(s,a)+γ∑s′P(s′∣s,a) Vπ(s′),Vπ(s)=∑aπ(a∣s) Qπ(s,a).Q^\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s'), \qquad V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a). Substituting the first into the second removes QQ: Vπ=rπ+γPπVπ,rπ(s)=∑aπ(a∣s)R(s,a),Pπ(s,s′)=∑aπ(a∣s)P(s′∣s,a).V^\pi = r_\pi + \gamma P_\pi V^\pi, \qquad r_\pi(s) = \sum_a \pi(a\mid s) R(s,a), \quad P_\pi(s, s') = \sum_a \pi(a\mid s) P(s'\mid s,a). This is a linear system in ∣S∣|\mathcal{S}| unknowns, (I−γPπ)Vπ=rπ(I - \gamma P_\pi) V^\pi = r_\pi. It has a unique solution whenever I−γPπI - \gamma P_\pi is invertible. That holds for any γ<1\gamma < 1, because PπP_\pi is substochastic and its spectral radius is at most 1. For γ=1\gamma = 1 it holds exactly when the policy reaches the terminal state with probability 1 from every state (a proper policy). Solving the system is exact policy evaluation, the second function we save.
The two einsum/sum lines are the definitions of PπP_\pi and rπr_\pi; the solve is the Bellman equation. Compare with Monte Carlo.
Output:
The exact values of V(unread)V(\text{unread}) agree with the Monte Carlo estimates of Section 2.2 to within about one standard error, as they should. The full vectors show more. Under the careful policy, V(passed)=1V(\text{passed}) = 1: one step from a guaranteed reward, and that step is not discounted because the reward arrives at t=0t = 0 of the remaining episode. V(done)=0V(\text{done}) = 0 for every policy, since nothing follows termination. The action values follow from VV in one line, and they are what a policy improvement step compares. The advantage Aπ(s,a)=Qπ(s,a)−Vπ(s)A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s) measures how much better action aa is than the policy’s average behavior in ss. Chapter 7 is entirely about estimating it.
Output:
The columns are read, edit, test, submit. The advantage of the action the careful policy takes is exactly 0, by definition. The other entries are informative. In edited_ok, submitting has an advantage of +0.100+0.100: careful’s test spends a discounted step on a file that is already correct, which costs exactly the factor 1−0.91 - 0.9 of the reward. In edited_bad, submitting has an advantage of −0.696-0.696, because it throws away the whole value of the state. A policy that acts on these numbers would submit from edited_ok and keep testing from edited_bad, where test has the highest action value. That is the policy improvement step of Section 2.5. The final line checks the Bellman equation to machine precision.
Pitfall. torch.linalg.solve in float32 can drift visibly for γ\gamma close to 1, where I−γPπI - \gamma P_\pi is nearly singular. The repair MDP uses float64 throughout. The same concern appears at scale whenever long-horizon returns or log-probability sums are accumulated in low precision.

​
2.4 Discounting

The discount factor plays two different roles, and conflating them is a common source of confusion.
  1. A modeling choice. γ<1\gamma < 1 says that a reward kk steps later is worth γk\gamma^k of the same reward now. A geometric discount is equivalent to an episode that terminates independently with probability 1−γ1-\gamma at every step, so its effective horizon is about 1/(1−γ)1/(1-\gamma) steps.
  2. A mathematical convenience. γ<1\gamma < 1 guarantees that I−γPπI - \gamma P_\pi is invertible and that returns are bounded even for policies that never terminate.
A coding episode is finite: it ends with submit or when a turn budget runs out. Its success is what we care about, and an equivalent fix found in turn 5 rather than turn 3 is not worth less to the user. That argues for γ=1\gamma = 1 as the model of the task. But discounting changes which policy is preferred. Evaluate the three policies over a range of γ\gamma.
Output:
At γ=1\gamma = 1 the careful policy succeeds with probability 1, read-edit-submit with 0.8, and blind with 0.3; those are success probabilities, because the only reward is 1 at the end. As γ\gamma falls, every value falls, but careful falls fastest because its successes take more steps. Below roughly γ=0.85\gamma = 0.85 read-edit-submit overtakes careful: the discount is short-sighted enough to prefer a 20% chance of failure over the cost of testing. Figure 2.2 shows the crossing, together with the analogous effect of a per-step cost. Figure 2.2: Value of the initial state for three fixed policies, as a function of the discount (left, no step cost) and of the step cost (right, gamma = 1). Look at the two crossing points. In the left panel, discounting alone makes the untested policy preferable once γ\gamma is low enough. In the right panel, with γ=1\gamma = 1, a step cost does the same once it exceeds about 0.13 per action. Both knobs tell the agent that time is expensive, and both can change the optimal behavior, not merely the scale of the values. This is the content of the first two design problems in Section 2.9.

​
2.5 Optimal Policies and Why We Will Not Compute Them

Evaluation tells us how good a policy is. Improvement makes it better. The policy improvement theorem states: if π′\pi' is greedy with respect to QπQ^\pi, that is, π′(s)=arg⁡max⁡aQπ(s,a)\pi'(s) = \arg\max_a Q^\pi(s,a), then Vπ′(s)≥Vπ(s)V^{\pi'}(s) \ge V^\pi(s) for every state. The proof is short. Greediness gives Qπ(s,π′(s))≥Vπ(s)Q^\pi(s, \pi'(s)) \ge V^\pi(s); unroll the Bellman equation under π′\pi' one step at a time and apply the same inequality at every step. Iterating evaluation and improvement converges to an optimal policy π∗\pi^*, whose value satisfies the Bellman optimality equation: V∗(s)=max⁡a[R(s,a)+γ∑s′P(s′∣s,a) V∗(s′)].V^*(s) = \max_a \Big[R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s')\Big]. Value iteration applies the right-hand side as an update until it stops changing. For γ<1\gamma < 1 the update is a contraction in the max-norm, so it converges from any start.
Output:
The optimal policy reads, edits, and then does something no fixed policy above did: it submits immediately from edited_ok and tests from edited_bad. Testing a known-bad file is useful because it leads to failed, the state from which an informed edit succeeds 80% of the time, rather than a 30% guess from edited_bad. And it never tests a correct file, because it can see that the file is correct. The gap between careful and optimal is the cost of testing when the answer is already known.

​
Why this does not scale to language models

Value iteration needs a table with one entry per state and a sweep over all actions. For a language model under the token-level casting of Section 2.8, a state is a token prefix and an action is a token. Count them.
Output:
No table can index 10 to the five-thousandth power states, and the transition from a prefix to its successor includes an environment response we cannot enumerate. The alternative is to search directly in the space of policies. Parameterize πθ\pi_\theta and climb J(θ)J(\theta) by gradient ascent. On the repair MDP we can still do this exactly, because policy_evaluation is differentiable: it is an einsum and a linear solve.
Output:
The uniform random policy starts with a value near zero (0.0154): with a step cost of 0.05, a random agent pays for many useless actions and often submits an incorrect file. Gradient ascent on the softmax logits climbs to 0.8182 after 300 steps, close to the optimal 0.825, and the greedy actions of the learned policy match value iteration. The remaining gap is the slow final approach of a softmax policy toward a deterministic one: the logits must grow without bound to put all mass on one action. This is the policy gradient method with one luxury removed in the real setting: here ∇θJ\nabla_\theta J is computed exactly by differentiating through the model of the environment. A language model has no such model. Chapter 6 shows how to estimate the same gradient from sampled trajectories alone.

​
2.6 Bandits: The One-Step Case

A bandit is an MDP whose episodes last one step. There is no next state, so Q(a)=R(a)Q(a) = R(a) and the only question is which action has the highest expected reward. A contextual bandit adds a context xx drawn at the start: Q(x,a)=E[r∣x,a]Q(x, a) = \mathbb{E}[r \mid x, a]. Single-turn RLVR is a contextual bandit. The context is the prompt, the action is the entire response, and the reward is the verifier’s score of that response. The response is generated token by token, but the environment does not react between tokens, so the only stochasticity apart from the policy is in the prompt. Methods such as GRPO treat each prompt as a small bandit problem: sample GG responses, observe GG rewards, and push probability toward the better ones (Chapter 9). Bandits isolate the problem that the tabular MDP hid: exploration. The value of an action is unknown until it is tried, and a policy that stops trying an action can never learn that it was good. Compare a greedy learner, which always picks the arm with the highest estimated mean, with epsilon-greedy, which picks a random arm with probability ϵ\epsilon. We run 2,000 independent copies in parallel.
Output:
The greedy learner locks onto whichever arm looked best after its first noisy pulls and settles on the best arm in only 51.8% of runs, because nothing forces it to revisit an arm whose early pulls returned 0. With ϵ=0.05\epsilon = 0.05 the best arm wins in 73.8% of runs, and the average reward rises from 0.509 to 0.557. With ϵ=0.2\epsilon = 0.2 the best arm wins in 85.4% of runs, but the average reward does not improve further, because one pull in five is still spent at random. That is the exploration–exploitation trade-off. Language-model RL rarely uses explicit ϵ\epsilon-greedy, but the same problem is everywhere. The policy explores only through its own sampling distribution. Temperature and the entropy of πθ\pi_\theta (Chapter 10) are the exploration knobs. If the model never samples a successful repair for a task, the reward for that task is always 0, and no gradient method can learn from a signal it never observes. This is why the pass rate of the starting policy is the first number to check before an RL run (Chapter 1, Section 1.8).

​
2.7 Partial Observability

So far the agent saw the state. A real coding agent does not. It sees the issue text, the outputs of its tools, and its own messages. It does not see the hidden tests that will grade it, the parts of the repository it has not read, or whether its edit is correct. A partially observable MDP (POMDP) adds an observation function O(o∣s)O(o \mid s): the environment’s state evolves as in an MDP, but the agent receives only an observation oto_t. An agent in a POMDP should condition on its whole history ht=(o0,a0,o1,…,ot)h_t = (o_0, a_0, o_1, \dots, o_t), or on the belief bt(s)=Pr⁡(st=s∣ht)b_t(s) = \Pr(s_t = s \mid h_t), which is a sufficient statistic for it. A policy that maps only the current observation to an action can be strictly suboptimal. For a language model, the context window is the history: the model conditions on every earlier message and tool output. That is a strength, and it is also why context truncation (Section 2.9) is a modeling change rather than a mere engineering detail. In the repair MDP, make edited_ok and edited_bad look identical: after an edit, the agent sees only edited. Every other state is observed as itself.
Output:
With a step cost of 0.05 and γ=1\gamma = 1, the observation edited must lead to the same action in both hidden states. Submitting blindly after an edit is worth 0.65; testing first is worth 0.775. Under partial observability, testing is the better choice, because the test’s output reveals the hidden variable. The fully observed optimum, 0.825, is higher still. The difference between 0.825 and 0.775 is the value of the information that the agent cannot observe directly and must pay a step to acquire. The same structure appears at full scale. Reading files, running tests, and searching the repository are information-gathering actions. They earn no reward themselves, and their value exists only because the agent is partially observing its world. An outcome-only reward must teach the agent to take them, which is a credit-assignment problem (Chapter 7, Chapter 12). The hidden tests are also, by design, never observed. That is what makes them a reward the agent cannot fit directly (Chapter 11).

​
2.8 Three Ways to Cast an LLM Agent as an MDP

A language model agent fits the MDP framework in more than one way, and the choice decides what an “action”, a “step”, and an “advantage” mean in code. Take one scripted episode from Chapter 1, written as segments with their owners.
Output:
The word-level split stands in for a tokenizer here; Chapter 5 uses real token ids. The three castings are: Token level. The state is the full token prefix cic_i, the action is the next token yiy_i, and πθ(yi∣ci)\pi_\theta(y_i \mid c_i) is exactly what the model computes. Transitions are deterministic, ci+1=ci⊕yic_{i+1} = c_i \oplus y_i, except at tool boundaries, where the environment appends observation tokens the policy did not choose. Those are the only random transitions; in the toy episode there are three of them among the policy’s thirteen token decisions. This casting buys an exact match between the MDP’s policy and the network’s output distribution, so log-probabilities, ratios, and KL penalties are all per-token quantities (Chapter 3). It costs a very long horizon. A single terminal reward must be credited across thousands of decisions, and observation tokens must be excluded from the action set by a mask (Chapter 5). Turn level. The action is a whole message, here <call> edit swap_minmax </call>, and the state is the conversation so far. Its probability is the product of its token probabilities. The horizon shrinks to the number of turns, which is the natural scale for credit assignment: a turn-level advantage says “this tool call was good”. It costs an action space that is combinatorially large and a ratio πθ(a)/πold(a)\pi_\theta(a)/\pi_{\text{old}}(a) that is a product of many per-token ratios, so it can explode (Chapter 8). Episode level. The whole trajectory is one action, and the problem becomes a contextual bandit over trajectories, with the task as context and the final reward as payoff. This is the casting implicit in GRPO-style outcome RL (Chapter 9): every policy token in a trajectory receives the same trajectory-level advantage. It buys simplicity and no value function. It costs all credit assignment within the episode: a useless read and the decisive edit receive the same signal. These are not competing theories. They are three views of the same sampling process, and practical systems mix them. A common combination computes log-probabilities at the token level, advantages at the episode level, and masks at the turn level.

​
2.9 Design Problems in Practice

Problem: choosing the discount for finite coding episodes. Symptom: with γ<1\gamma < 1, the agent learns to skip verification steps. With γ=1\gamma = 1, a critic’s value estimates diverge or a policy that loops forever has undefined value. Cause: γ<1\gamma < 1 makes later success worth less, which changes the optimal policy (the crossing in Figure 2.2). γ=1\gamma = 1 leaves I−PπI - P_\pi singular for any policy that can avoid termination. Options: (a) γ=1\gamma = 1 with a hard turn or token budget that forces termination; this matches the task’s success criterion, but the budget becomes part of the environment and truncated episodes need a rule (Chapter 12). (b) γ\gamma slightly below 1, which keeps values bounded at the cost of a bias toward short episodes. (c) An explicit step cost (next problem), which expresses urgency in reward units rather than through the discount. Default: the book uses γ=1\gamma = 1 plus a turn budget, and treats any urgency as an explicit, measured cost. This is a recommendation, not a universal rule.
The singular case is easy to reproduce. A policy that reads forever never terminates.
Output:
With γ=0.99\gamma = 0.99 the never-terminating policy has a well-defined value of 0: it never earns a reward. With γ=1\gamma = 1 the linear system has no unique solution. A sampled training run does not raise an exception; instead the episode simply never ends, which is why the turn budget is a required part of the environment and not an optional optimization.
Problem: terminal rewards versus step costs. Symptom: after a step penalty is added to discourage long episodes, the agent starts submitting without testing, or submits immediately with no edit. Cause: a step cost cc subtracts cc times the expected episode length from every policy’s value, and policies of different lengths lose different amounts. Above a threshold, a shorter and less reliable policy becomes optimal; at a higher threshold, giving up is optimal. Options: (a) terminal reward only, with a budget, which is unbiased with respect to success but gives no pressure toward efficiency. (b) A small step cost, set well below the threshold at which the optimal policy changes. (c) Report cost separately and select among successful policies by cost during evaluation. Default: terminal reward only during early training, then a small step cost only if efficiency matters, after checking that it does not move the optimal policy on representative tasks.
Output:
Read the columns of the optimal plan. At a cost of 0, many policies tie at value 1 and the printed actions are an arbitrary tie-break among policies that all eventually succeed. From a cost of 0.05 to 0.3, the optimal policy keeps its shape while its value drops by 3.5 times the cost, because the optimal policy takes 3.5 actions on average. At 0.5 the optimal first action becomes submit from unread: the agent gives up immediately. Giving up costs one action, so it becomes optimal once 1−3.5c<−c1 - 3.5c < -c, that is, c>0.4c > 0.4, where the expected cost of attempting the repair exceeds its reward of 1. In an LLM run, this is the “agent learns to submit immediately” pathology of Chapter 12, reproduced in a seven-state table.
Problem: is the prefix a Markov state? Symptom: the same visible context leads to different outcomes, value estimates are noisy for no visible reason, or behavior changes after a context-management change. Cause: the token prefix is Markov for the agent’s decision process only when it contains everything that determines future observations and rewards. Three things break this. The environment has hidden state, such as the file system, hidden tests, and random seeds. The context may be truncated or summarized, which discards history the policy could have used. And a state abstraction may merge histories with different futures; in the repair MDP, edited_bad reached by a guess and edited_bad reached by an informed edit are one state only because we declared that edits do not remember how they were made. Options: (a) keep the full history in context, which is expensive at long horizons; (b) use explicit, faithful state summaries, such as having tools report the current diff, so that truncation loses less; (c) treat the problem as a POMDP and accept that values are conditioned on the observable history only. Default: treat the agent as a POMDP whose policy conditions on its full context; make tool outputs report relevant state explicitly; and treat any change in truncation or summarization as a change in the policy’s input distribution that requires re-evaluation.

​
Summary

  • An MDP (S,A,P,R,ρ0,γ)(\mathcal{S}, \mathcal{A}, P, R, \rho_0, \gamma) separates what the agent controls, π\pi, from what it does not, PP and ρ0\rho_0; the trajectory distribution factorizes into those parts, and this is why policy gradients do not need a model of the environment.
  • Value functions satisfy the linear Bellman expectation equations. For a tabular MDP, policy_evaluation solves them exactly, and the result matches Monte Carlo estimates within their error bars.
  • The discount and step costs are not neutral scalings: both can change which policy is optimal. For finite coding episodes, the book uses γ=1\gamma = 1 with a turn budget.
  • Value iteration finds the optimal policy only when states and actions can be enumerated. Language models cannot, so we optimize a parameterized policy by gradient ascent on J(θ)J(\theta), which on the repair MDP can still be done exactly by autograd.
  • Single-turn RLVR is a contextual bandit, and exploration is limited by the policy’s own sampling distribution. A real coding agent is partially observed, which is what gives information-gathering actions their value.
  • An LLM agent can be cast as a token-level, turn-level, or episode-level decision process. Practical systems take log-probabilities per token, advantages per episode or turn, and masks per turn.

​
Exercises

  1. Prove that I−γPπI - \gamma P_\pi is invertible for any γ<1\gamma < 1 when PπP_\pi is substochastic. (Hint: bound the spectral radius by the max row sum.) Then construct a two-state example in which it is singular at γ=1\gamma = 1.
  2. Change the informed edit success probability from 0.8 to 0.5. Recompute the value table of Section 2.4. Does the crossing between careful and read-edit-submit move to a higher or lower γ\gamma? Explain why before running the code.
  3. Modify make_repair_mdp so that test on edited_ok fails with probability 0.1 (a flaky test). How do V∗V^* and the optimal policy change? What does this predict about training against flaky verifiers (Chapter 11)?
  4. In Section 2.5, replace the exact JJ with a Monte Carlo estimate from 16 sampled episodes per step, computed by mc_value. Why can you no longer call backward() on it? What is missing? (This is the question Chapter 6 answers.)
  5. Extend run_bandit with an upper-confidence-bound rule: pick arg⁡max⁡aμ^a+clog⁡t/na\arg\max_a \hat\mu_a + c\sqrt{\log t / n_a}. Compare it with ϵ\epsilon-greedy at ϵ=0.05\epsilon = 0.05.
  6. Augment the repair MDP state so that it remembers whether the agent has read the file, and make edits from any state succeed with probability 0.8 if and only if the file has been read. How many states do you need? Which policy is optimal?
  7. Design review: your team proposes adding a reward of +0.1+0.1 for every test call, because “agents that test more succeed more”. Using Section 2.7 and the step-cost results, argue what the agent will learn, and propose a better way to encourage useful testing.