Multi-Turn and Agentic RL

Single-turn RLHF treats each model response as a complete episode: one prompt, one completion, one scalar reward. That simplification made InstructGPT tractable in 2022, but it breaks down the moment your model is expected to write code, execute it, observe the result, fix the bug, and repeat for ten iterations. At that point you have a sequential decision problem, and the credit assignment question becomes non-trivial: which of the twelve tool calls in the trajectory actually caused the test suite to pass?

This concept covers what changes - technically and algorithmically - when RL is applied to agents operating across multiple turns.

What Changes in Multi-Turn Settings

In single-turn RLHF, the Markov Decision Process (MDP) is degenerate: one state (the prompt), one action (the full completion), one reward. The KL-regularised objective from prior concepts holds:

J(π) = E_{x~D, y~π}[ r(x, y) ] - β · KL( π(·|x) || π_ref(·|x) )

The moment you extend to multi-turn, the episode becomes a trajectory τ = (s₀, a₀, s₁, a₁, ..., sₙ, aₙ) where each state sₜ is the conversation context so far and each action aₜ is the model's next token sequence (a message, a tool call, a scratchpad step). The reward R(τ) is typically only observed at the end - a test pass or fail, a human score on the final answer, an API response code.

Three structural difficulties emerge immediately:

Sparse reward. A trajectory of 20 turns receives a single terminal signal. Most intermediate steps are unobserved. Naive policy gradient has extremely high variance under these conditions.

Exponential state space. The context window grows with each turn. After ten turns of 200 tokens each, you are conditioning on 2,000 tokens of history. The policy is effectively a different function at every step.

Credit assignment. When the agent misread a tool output at turn 4, the final reward at turn 20 carries the blame, but the gradient flows through all 16 intervening steps equally unless you specifically address this.

Trajectory-Level Reward and Return Decomposition

The natural fix for sparse reward is to learn a value function or a per-step process reward model (PRM) that estimates expected future return from any intermediate state. With a value estimate V(sₜ), you can compute advantages at each step:

Aₜ = Rₜ + γ · V(sₜ₊₁) - V(sₜ)

Generalised Advantage Estimation (GAE) from the robotics RL literature applies directly; the main difference is that the "environment" here includes Python interpreters, web browsers, databases, or any external tool your agent can call.

An alternative grounded in preference learning is the Q-function view of DPO. Rafailov et al. (COLM 2024) showed that the token-level implicit reward in DPO satisfies the Bellman equation, making it equivalent to inverse Q-learning on a token-level MDP. This means step-level credit assignment emerges naturally if you train with turn-level preference pairs instead of response-level ones - though collecting such data is expensive.

A lighter-weight trick used in practice is turn-level reward shaping: assign a small positive reward for each completed tool call that makes progress (for example, a compiler that produces fewer errors), and the terminal reward for the final outcome. This is not principled credit assignment, but it dramatically reduces variance in sparse-reward settings.

Group Relative Policy Optimisation at the Trajectory Level

GRPO (introduced in DeepSeekMath, arxiv.org/abs/2402.03300) was designed for single-turn reasoning, but its structure adapts well to agentic settings. The algorithm samples G independent rollouts of the same prompt, scores each with a verifiable reward, and computes advantages by normalising within the group:

Aᵢ = (rᵢ - mean(r)) / std(r)

No separate critic network is needed. The gradient estimate is:

∇J = E[ Σ_t  Aᵢ · ∇ log π(aₜ|sₜ) ]

In an agentic context, each "rollout" is a full multi-turn trajectory. If you sample G=8 trajectories per task and score each by whether the final test passes, you get a relative advantage signal that is noisy but unbiased. The advantage of GRPO over PPO here is the absence of a value network, which saves memory and avoids the instability of training a critic on a rapidly shifting policy distribution in long-horizon tasks.

The Kimi k1.5 work (arxiv.org/abs/2501.12599) applied this style of RL to long-horizon reasoning chains - albeit in a mostly single-turn framing - and found that long-context scaling was essential: the model needed to be able to attend back to early reasoning steps when computing later ones.

Tool Use, External State, and Partial Observability

A further complication specific to tool-using agents: the environment is no longer fully within the model's context. A database query returns results the model has not seen; a code execution produces outputs that depend on the runtime environment, not just the conversation history. This introduces partial observability.

Formally, you are now solving a POMDP (Partially Observable MDP). The model's context window is its belief state - an approximation of the true environment state. Two practical consequences follow:

1. Exploration is harder. The model cannot mentally simulate what a tool call will return; it must actually execute it. On-policy RL (PPO, GRPO) requires live interaction with the environment during training. This means spinning up real or mock code execution, browser agents, or database sandboxes - substantial infrastructure cost compared to single-turn RLHF which only needs text generation.

2. The reward model generalises poorly. A reward model trained on static text-preference data has no reliable signal for whether a particular web search query was a good one. Task-specific verifiable rewards (does the code pass the unit tests? did the research task find the right answer?) partially bypass this, which is part of why RLVR works better in agentic settings than a learned reward model.

SWE-RL (arxiv.org/abs/2502.18449) showed that training Llama-3 70B on software engineering trajectories with rule-based rewards (patch applies, tests pass) reached a 41% solve rate on SWE-bench Verified, and the reasoning skills transferred to out-of-domain tasks. The reward signal was entirely verifiable and required no human preference labelling.

When It Falls Down

Credit assignment remains largely unsolved. Turn-level reward shaping introduces reward engineering bias. PRMs require expensive step-level labelling. GRPO variance is high when trajectories diverge early; most of G rollouts may fail for the same structural reason, leaving the group advantage near zero and the gradient uninformative.

Reward over-optimisation compounds across turns. Gao et al. (arxiv.org/abs/2210.10760) showed that proxy reward models degrade under heavy optimisation in single-turn settings. In multi-turn settings, the policy has more opportunities to find reward-model exploits - for example, generating verbose tool-call rationales that the reward model scores highly regardless of actual task progress. The KL penalty that ordinarily contains this divergence is harder to calibrate when trajectories vary in length by 10x.

On-policy training is infrastructure-heavy. Single-turn RLHF needs a text generation server and a reward model. Agentic RL needs isolated execution sandboxes, tool API mocks, rollback mechanisms for failed executions, and enough parallelism that G rollouts per prompt do not become the training bottleneck. Most academic labs cannot replicate this.

Length bias and shortcut solutions. Agents trained with outcome rewards often learn to produce very long reasoning traces that superficially appear thorough, or to call tools in patterns that happen to satisfy the reward without genuinely solving the task. Short-circuiting to a memorised answer format is also common when the training distribution does not cover diverse environments.

The RLVR capability question. Yue et al. (arxiv.org/abs/2504.13837, oral at NeurIPS 2025) found that RLVR-trained models do not acquire genuinely novel reasoning patterns; the capabilities appear to originate in the base model, with RL mainly shifting the sampling distribution toward them. If this holds for agentic tasks, the implication is that agentic RL is better viewed as a fine-tuning of pre-existing capability than a mechanism for learning new skills from scratch.

Further Reading

• Scaling Laws for Reward Model Overoptimization - Gao, Schulman, Hilton (2022)
• From r to Q*: Your Language Model is Secretly a Q-Function - Rafailov et al. (2024)
• SWE-RL: Advancing LLM Reasoning via RL on Open Software Evolution - Wei et al. (2025)
• Kimi k1.5: Scaling Reinforcement Learning with LLMs - Kimi Team (2025)