Agents and Multi-Turn RL#

Everything in this chapter so far shared one quiet assumption: the model speaks once, the episode ends, a grade arrives. Agents — models that search the web, call tools, execute code, and interact with users or systems across many turns — break that assumption, and with it, most of the conveniences the chapter has enjoyed. This page is the chapter’s honest ending: less settled than the previous four, because the field is less settled. The principles below are stable; the systems built on them are changing by the month.

The MDP, revised#

Put the Section 4.1 table side by side with its agentic revision:

Component	Single-turn generation (4.1)	Agentic interaction
Transition	Deterministic concatenation	Stochastic, unknown: tool outputs, web pages, user replies
Action	Next token	Tokens composing into tool calls and messages — two granularities
Horizon	One response, $\le T_{\max}$ tokens	Many turns; thousands of tokens across an episode
Reward	Terminal; a grade on one response	Terminal on the whole trajectory, often a fuzzy completion check
Reset	Free — sample a new prompt	Expensive: stateful sandboxes, browsers, mutated codebases
Observability	Full (the state is the context)	Partial: the world has state the context window never saw

Each row deletes a luxury:

Transitions. A tool’s output is not a function of the policy’s parameters. The environment is back, stochastic and unknown — the model-based/model-free distinction that Section 4.1 collapsed un-collapses, and all of Section 2’s reasoning about expectations over next states applies again in earnest.
Reward. Sparser than ever (one signal after thousands of tokens and dozens of decisions) and often fuzzier than ever: “did the agent resolve the issue?” is a verifier in name only, with all the exploitable gaps of th verifier-hacking deep dive — now spread over a long trajectory with side effects.
Resets. Sampling a fresh math problem was free. Restoring a browser session, a container, or a half-modified repository is not — rollouts become the dominant cost of training, and infrastructure, not algorithm, is frequently the binding constraint (second deep dive).
Observability. The context window is the agent’s state, but the environment has state of its own — files changed three turns ago, a page it never opened. Formally we have drifted from MDP to POMDP; practically, context management (what to keep, summarize, or forget) has become part of the policy.

The rollout, and where RL attaches#

The training loop, in pseudocode (the env here is real machinery — a code sandbox, a browser, a simulated user):

def agentic_rollout(policy, env, max_turns):
    obs = env.reset()                       # task description
    trajectory = []
    for turn in range(max_turns):
        turn_text = policy.generate(context(trajectory, obs))  # reasoning + tool calls
        obs, done = env.step(turn_text)     # execute tools; observe results
        trajectory.append((turn_text, obs))
        if done:
            break
    reward = env.verify(trajectory)         # task success, often 0/1
    return trajectory, reward

The dominant current recipe attaches RL to this loop in the least imaginative way possible — and that is a fair summary of the state of the art: collect trajectories, compute one outcome reward each, and run GRPO/PPO with that reward broadcast to every token of every turn, tool outputs masked out of the loss (they are observations, not actions — the policy must not get gradient for text it did not choose). This is Section 4.4’s bandit reading stretched over its longest horizon yet: a thirty-turn trajectory, one scalar, no statement about which turn earned it. That it works at all is the same free lunch as before — the pretrained prior does the heavy lifting, and RL reweights. But the longer the horizon, the thinner the bandit reading stretches, which is where the chapter’s deleted machinery starts returning.

Everything returns#

The chapter’s arc was deletion: DPO deleted the loop, RLVR deleted the learned reward, GRPO deleted the critic. The agentic frontier is the arc running in reverse — each deleted component is being reinvented, because the problem that justified it is back:

The critic wants to return. With one reward over thousands of decisions, credit assignment is again the central difficulty — and per-step value estimates were always the classical answer. Turn-level critics and process rewards are active research precisely because the group baseline stops being enough (first deep dive).
The learned reward wants to return. Fuzzy task completion cannot be checked by exact match, so learned judges of trajectories — reward models by another name — reappear, with every caveat of Section 4.2 intact.
Offline RL wants to return. When rollouts are expensive, you cannot afford to throw away old trajectories — replaying and reweighting stale data is exactly the off-policy problem, coverage assumptions and all, from the DTR/batch-RL bridge page.
Exploration is a real problem again. Sampling temperature sufficed when a fresh attempt was free and consequence-free. An agent exploring a live system has neither property — its mistakes persist, which makes exploration both a sample- efficiency problem (Section 2’s bandits, at last with real stakes) and a safety one, the same reason clinical DTRs are learned from logged data rather than by experimenting on patients.

The full-circle sentence — worth saying out loud here: an agent is a dynamic treatment regime with a very large action space. Multi-stage decisions, stochastic transitions between stages, a delayed outcome, learning constrained by the cost and risk of interaction: the structure of Section 2’s DTR page is the structure of the frontier. The finite-horizon, $\gamma = 1$, backward-induction toolkit was never a warm-up — it was the destination.

Deep dive: credit assignment across turns

The clean way to think about multi-turn credit is a hierarchical decomposition: a turn-level MDP layered on the token-level one. Let $s_k$ be the full context after turn $k$ and let the macro-action $u_k$ be the entire $k$-th assistant turn (all its tokens and tool calls). With terminal reward and $\gamma = 1$, values satisfy the finite-horizon Bellman recursion over turns,

$$ Q(s_k, u_k) \;=\; \mathbb{E}_{s_{k+1} \sim P(\cdot \mid s_k, u_k)} \big[ V(s_{k+1}) \big], \qquad V(s_K) \;=\; R(\tau), $$

where the expectation is over the environment's response — nontrivial now, unlike 4.1 — and $K$ is the final turn. This is backward induction over stages, formally identical to the DTR setting, and it yields the object outcome reward cannot provide: a turn-level advantage $A(s_k, u_k) = Q(s_k, u_k) - V(s_k)$ that says this tool call helped; that one hurt, with the token-level policy gradient inside each turn weighted by its turn's advantage.

The estimation strategies on offer, in increasing order of machinery:

Monte-Carlo turn values. From a state $s_k$, branch: roll out several independent completions of the episode and average their outcomes to estimate $V(s_k)$ — GRPO's group trick applied at every turn boundary rather than once at the prompt. Unbiased and simple; the cost multiplies with the horizon, which is painful precisely when rollouts are expensive.
Learned turn-level critics. A value head over contexts, trained on trajectory outcomes — the component GRPO deleted, reinstated one level up the hierarchy (e.g. ArCHer's actor-critic-over-turns design). Everything Section 3 said about critics with sparse terminal signal applies; the saving grace is that turns number in the tens where tokens number in the thousands.
Process rewards. A learned judge grades each step's contribution directly. Densest signal, strongest assumptions — and a learned reward model on the loose again, with the verifier-hacking caveats of 4.4 transposed to intermediate steps.

No consensus winner exists as of this writing; outcome-only broadcast remains the production default for its simplicity, with turn-level methods winning in studies where horizons are long and environments are cheap enough to branch. The honest summary: the field is re-learning, one level up, why Sections 2 and 3 invented value functions.

Deep dive: when rollouts are the bottleneck — asynchrony and staleness

A GRPO step on math problems generates its own data in seconds. An agentic rollout can take minutes of wall-clock — sandboxes boot, pages load, tests run — and different trajectories take wildly different times. Synchronous training (all rollouts finish, then one update) leaves accelerators idle; every serious system therefore decouples actors (machines running rollouts against the current-ish policy) from the learner (machines updating weights), with finished trajectories streaming into a queue and refreshed weights streaming back (the design popularized for LLM-scale RL by Kimi k1.5's partial rollouts, descending from the IMPALA lineage of classical deep RL).

The price is that data arrives stale: a trajectory in the queue was generated by $\pi_{\theta_{\text{old}}}$ several updates behind the learner's $\pi_\theta$. This is not a new problem — it is the off-policy problem, and the chapter has already deployed its standard tools: the importance ratio $\rho_t = \pi_\theta / \pi_{\theta_{\text{old}}}$ corrects the mismatch in expectation, and PPO-style clipping (or V-trace-style truncation) caps the variance of the correction. What changes at agentic horizons is the arithmetic: a trajectory-level ratio is a product of thousands of token ratios, so tiny per-token drift compounds exponentially — sequence-level importance correction is hopeless, per-token clipped correction is the only viable form, and even it decays as staleness grows. Hence the operational rule every async system enforces: bound the lag (drop or down-weight trajectories more than a few versions old), because past a staleness horizon, data is not just noisy but actively misleading.

Note what happened here: an infrastructure decision (asynchrony, made for hardware utilization) forced an algorithmic commitment (per-token clipped off-policy correction with bounded staleness). At the agentic frontier the two design spaces are no longer separable — a genuinely new feature of this era, and a reasonable guess at where the next round of algorithmic ideas will come from.

Closing the chapter#

One paragraph of stock-taking for the lecture. The chapter began by claiming that an LLM is a policy and that nothing new needed inventing — and then kept the receipts: RLHF was PPO with a learned reward and a KL leash; DPO was the KL-regularized objective solved in closed form and estimated like a reward model; GRPO was REINFORCE with a Monte-Carlo baseline; and the agentic frontier is finite-horizon backward induction wearing a browser. Every era’s “new” method was a judicious choice of which classical component to keep, delete, or approximate — which means the fundamentals of Sections 2 and 3 were never background material. They are the design space.

Next, the same machinery leaves the chatbox entirely: Section 5 — RL in science, where the environments are tokamaks, tensor decompositions, and beamlines.

References.

Nakano et al. (2021), WebGPT: Browser-Assisted Question-Answering with Human Feedback;
Yao et al. (2022), ReAct: Synergizing Reasoning and Acting in Language Models;
Jimenez et al. (2024), SWE-bench: Can Language Models Resolve Real-World GitHub Issues?;
Zhou et al. (2024), ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL;
Kimi Team (2025), Kimi k1.5: Scaling Reinforcement Learning with LLMs;
Espeholt et al. (2018), IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
Murphy (2005), A Generalization Error for Q-Learning (and the DTR literature of the Section 2 bridge page).