Agentic & Long-horizon RL

The next step beyond single-turn reasoning RL (GRPO / RLVR, see the sibling repository reasoning-rl-frontier): Extending the reward signal from "one prompt, one response, one reward" to multi-turn trajectories (think → call tool → observe)*.

0. One-sentence evolution

Single-turn RLHF (prompt→response→reward) → Single-turn verifiable RLVR (correct/incorrect→reward) → Multi-turn agentic RL (trajectory→sparse terminal reward). What changes is not the loss function, but the shape of the episode: An episode consists of (reasoning, tool_call, observation) repeated over multiple turns1Enabling LLMs to interleave reasoning with tool calls (think→act→observe), thinking while acting.Yao 2022 ↗, and the reward is often given only once at the end (task success or failure).

TL;DR — quick anchors (2-minute pass)

• What changes is the episode shape, not the loss: single-turn RLHF→RLVR→multi-turn agentic RL; one episode = (think → tool call → observe) repeated, reward usually given only at the terminal.
• Long-horizon = POMDP: partially observable until the tool returns; action space = token + tool call + when to stop; core difficulty = credit assignment for sparse terminal reward + error accumulation.
• Three credit granularities: trajectory (shared) / turn (needs step reward or value) / token (turn-level advantage broadcast + action mask); finer = more accurate but more reliant on critic/PRM.
• GRPO group-relative baseline transfers naturally: normalize within-group terminal returns as baseline, no critic; but under sparsity an all-failure group → std=0 → advantage degenerates.
• Observation tokens must be masked: tool returns are environment-injected, not policy-generated; not masking = doing SFT on observations, polluting the policy gradient.
• Reward design: verifiable terminal reward (RLVR) is most stable; step/PRM reward eases sparsity but is easily gamed; long-horizon reward hacking = idling / premature stop / milestone gaming.
• Almost always two-stage: SFT warm-start (learn the format + lift success rate so RL has gradient) → RL to surpass demos; e.g. AgentTuning / Agent-FLAN / ReFT / ReSearch.
• Named recipes: ToolRL (shaping) / RAGEN-StarPO (Echo Trap) / WebRL (self-evolving curriculum) / SWE-RL (rule-based reward); 2025 improvements DAPO / CISPO / VAPO + system-level AReaL.
• Off-policy correction: PPO clip only controls variance, does not de-bias; async needs small policy lag / ESS / V-trace double clipping / global advantage normalization (REINFORCE++).
• If you know single-turn, you can transfer: just grab "trajectorize + mask + group-relative baseline".

1. What makes it long-horizon

2. Formalization (POMDP)

Consider a trajectory $\tau=(s_0,a_0,\dots,s_T,a_T)$ as a POMDP. The terminal task reward $R(\tau)\in\{0,1\}$ (success/failure) or a scalar score. The trajectory return is

$$G_t=\sum_{k=0}^{T-t}\gamma^{k}\,r_{t+k}.$$

In practice, a "turn" is often used as the decision granularity (turn-level MDP), while gradients still fall on the tokens generated within that turn — i.e., turn-level credit + token-level updates.

3. Credit assignment (core difficulty)

With only one terminal reward, the question is: Which turn and which token among these dozens should be rewarded/punished?

• trajectory-level: The entire trajectory shares one advantage — simplest, but also rewards "bad steps in a good trajectory".
• turn-level: Gives each turn an advantage (requires step rewards or value estimation).
• token-level: Most fine-grained; typically broadcast from the turn-level advantage to the tokens in that turn.

The idea of GRPO2Sampling a group of rollouts for the same task, using relative returns within the group as the baseline, eliminating the need for a critic.Shao 2024 ↗ is naturally transferable: Sample a group of trajectories for the same task, use the relative return within the group as the baseline (no critic needed):

$$A(\tau_i)=\frac{R(\tau_i)-\mathrm{mean}(R)}{\mathrm{std}(R)+\epsilon}.$$

A Process Reward Model (PRM)3Scoring each step of reasoning (process supervision), not just the final correctness.Lightman 2023 ↗ (scoring each step) is more friendly for long-horizon credit assignment, but annotation/training is more expensive and it can be hacked itself; an ORM (only looking at the outcome) is cheaper but has coarse credit assignment. Long-horizon scenarios often involve a compromise between the two.

4. Reward design

• Verifiable Outcome Reward (RLVR→agentic)4Using automatically determinable correctness (instead of a reward model) as the RL signal.Lambert 2024 ↗: The most stable terminal signal is one that can be automatically determined — unit tests passing, environment state achieved, answer verifiable.
• Process / Step Reward: Giving points for intermediate milestones alleviates sparsity but is prone to gaming (the agent learns to trigger milestones without solving the task).
• Long-horizon reward hacking: The longer the trajectory, the more shortcuts exist (idling to accumulate steps, repeatedly calling cheap tools). Mitigation: Focus on verifiable terminal rewards + step/token cost penalties + read-only but don't learn from tool outputs (see §5 masking).

5. Algorithm essentials

Two "long-horizon specific" details for multi-turn PPO5Policy gradient with clipping, the baseline algorithm for RLHF / agentic RL.Schulman 2017 ↗ / GRPO:

1. Observation Token Masking: Tool returns / environment observations are injected into the context, not generated by the policy — they must be masked out in the loss, otherwise it's equivalent to making the model "fit" the tool outputs (analogous to SFT loss masking).
2. Advantage Broadcasting + Masking: The turn-level advantage is broadcast to the tokens generated by the agent in that turn, then multiplied by the action mask.

import torch

def group_relative_advantages(returns, group_ids, eps=1e-6):
    """GRPO-style group relative advantage (no critic).
    returns:   (N,) terminal return per trajectory (e.g., success={0,1} or scalar score)
    group_ids: (N,) multiple rollouts for the same task share one group id
    """
    adv = torch.zeros_like(returns)
    for g in group_ids.unique():
        m = group_ids == g
        r = returns[m]
        adv[m] = (r - r.mean()) / (r.std(unbiased=False) + eps)
    return adv

def masked_pg_loss(logp, adv_per_token, action_mask):
    """Policy gradient loss: backpropagate only on tokens generated by the agent.
    logp:          (B,T) log-probability of the token taken under the current policy
    adv_per_token: (B,T) broadcast from turn-level advantage to tokens
    action_mask:   (B,T) 1=token generated by agent, 0=tool output/observation (masked)
    """
    pg = -(logp * adv_per_token) * action_mask
    return pg.sum() / action_mask.sum().clamp_min(1)

The rollout phase requires actually executing tools/environment within the loop (often asynchronously), leading to longer trajectories → more expensive sampling → a major system bottleneck for agentic RL.

6. Training pipeline: SFT warm-start → RL

Agent training is almost always two-stage: SFT warm-start → RL fine-tune. Under an open action space + sparse terminal reward, RL from a pretrained model barely explores any successful trajectory (success rate decays exponentially with steps, the group is often all-zero → vanishing gradient), and it doesn't even know the basic tool-call format. First SFT on expert / successful trajectories to learn the format and trajectory structure and raise the success rate to where RL produces a useful gradient, then RL to surpass the demonstrations.

• AgentTuning (arXiv:2310.12823): builds the AgentInstruct multi-task trajectories for hybrid SFT, improving agent ability without hurting general ability.
• Agent-FLAN (arXiv:2403.12881): separates "format following" from "agent reasoning" in the data and adds negative samples (teaching the model to decline wrong tool calls / suppress agent hallucination) — an improvement at the SFT-data-design level.
• ReFT (arXiv:2401.08967): SFT warm-start (CoT) → online PPO fine-tuning over self-sampled reasoning paths, improving generalization (no extra questions needed).
• ReSearch (arXiv:2503.19470): pure RL to learn to interleave search calls with CoT, with no supervised reasoning-step labels — putting tool use directly into RL.

7. Representative recipes

2025–2026 RL improvements (algorithm variants + systems):

• DAPO (2503.14476, ByteDance): clip-higher (raise the positive clip upper bound to prevent entropy collapse) + overlong reward shaping + dynamic sampling + token-level PG loss.
• CISPO (MiniMax-M1, 2506.13585): clips the IS weight (per-token) instead of zeroing low-probability tokens, retaining the gradient contribution of all tokens (including rare "reflective" tokens).
• VAPO (2504.05118): value-augmented PPO, addressing value bias + heterogeneous sequence lengths.
• AReaL (2505.24298) (systems-level, not an algorithm variant): a fully asynchronous RL system that decouples generation from training (cf. §5 rollouts are expensive).
• SkyRL-Agent (2511.16108, NovaSky/Berkeley) (systems-level): an asynchronous training stack for long-horizon multi-turn tool use; its core is an asynchronous pipeline dispatcher that overlaps CPU-bound runtime init / reward computation with GPU generation (so a mixed batch of long and short trajectories isn't throttled by the slow ones); the authors report ~1.55× throughput over naive async batching, and it interoperates with VeRL / Tinker backends. (an engineering speedup, not a new loss / new advantage.)
• T²PO (2605.02178) (exploration control · very recent preprint): uncertainty gating — it estimates how much "thinking/trying one more turn" reduces marginal uncertainty at each step, and uses that to trigger a thinking intervention (token level) / resample low-progress turns (turn level), reallocating compute away from already-resolved steps toward genuinely uncertain ones, mitigating wasted exploration budget over long horizons.

8. Bridge from single-turn

The GRPO / RLVR / loss masking from the sibling repository are the building blocks; Agentic RL ≈ applying them to trajectories + solving "credit assignment for sparse terminal rewards". If you understand single-turn, grasping the three points of "trajectory formulation + masking + group relative baseline" enables the transition.

Stratified follow-ups

L1 Basics

L2 Advanced

L3 Deep Dive

Deep-dive

Interview-trap level questions: The following Q&A assumes the interviewer is familiar with single-turn GRPO/PPO and asks about fine-grained mechanisms in multi-turn scenarios. Study notes, not author's research findings.

Q1. per-token vs per-turn advantage estimation — How does the discount in GAE transfer to multi-turn?

Core Contradiction: Single-turn RL defines advantage at the token granularity ($A_t = Q_t - V_t$); multi-turn scenarios have a two-level structure — temporal discounting between turns (turn-level) and token broadcasting within a turn.

GAE Transfer6GAE uses a λ-weighted sum of TD residuals to balance bias-variance: λ→1 approaches Monte Carlo, λ→0 approaches single-step TD.Schulman 2015 ↗:

$$\hat{A}_t^{\text{GAE}(\gamma,\lambda)} = \sum_{l=0}^{T-t}(\gamma\lambda)^l\,\delta_{t+l}, \quad \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t).$$

Replacing "one token" with "one turn," this formula is fully applicable to a turn-level MDP:

• $\gamma$ (turn discount): In sparse terminal reward scenarios, $\gamma\approx1$ is often set (no discounting), as each turn contributes actual value. A $\gamma$ that is too low will drive the advantage of early turns toward zero, wastefully discarding gradient signals.
• $\lambda$ (GAE smoothing coefficient): Controls the bias-variance trade-off — critic bootstrapping error in multi-turn episodes accumulates more easily. In practice, $\lambda<1$ is more critical than in single-turn; otherwise variance explodes exponentially with horizon.

Broadcasting from turn-level to token-level: All agent-generated tokens within the same turn share that turn's $\hat{A}^{\text{turn}}$. Observation tokens have mask=0. Thus, per-token gradients equal the per-turn advantage multiplied by the action-mask, with no additional approximation.

Interview Trap: "Since tokens share the same advantage, what's the difference between token-level and turn-level?" — The difference lies in which level calculates the discount and baseline. Turn-level lets discounts span turns and allows the value function to bootstrap at the turn granularity. Token-level is simply where the gradients land. Confusing the two leads to incorrect application of discounts at the wrong level (applying γ discount to each token is equivalent to applying γ^t decay to a very long sequence, making early token gradients nearly zero).

Q2. High variance in GRPO group baseline under single terminal rewards — Why? What are variance reduction techniques?

GRPO Group Baseline advantage:

$$A(\tau_i) = \frac{R(\tau_i) - \mu_g}{\sigma_g + \epsilon}, \quad \mu_g=\frac{1}{G}\sum_{j=1}^G R(\tau_j).$$

Two sources of variance explosion in multi-turn scenarios:

1. Binary 0/1 reward + small group size: If $G=8$ and success rate $p\approx0.1$, it's common for the group to have all zeros (8 failures) or only 1 success. For all zeros, $\sigma_g=0$, and the advantage degenerates to zero. For 1/8 successes, $\sigma_g$ is extremely small, causing a spike in advantage—a single sample dominates the entire batch update.
2. Trajectory length differences: The log-prob sum for long trajectories is numerically much larger than for short trajectories. If the advantage is directly multiplied by the token count, long trajectories naturally have larger gradients, creating an implicit length bias.

Variance Reduction Techniques:

Interview Trap: "Can GRPO fully replace PPO's critic?" — Yes for single-turn binary reward scenarios. In long-horizon sparse reward scenarios, the variance of the group baseline is often greater than that of the critic baseline, making the critic valuable again. In practice, a compromise is to use a small turn-level value head instead of a full PPO critic.

Q3. Importance-sampling / off-policy correction after multi-turn rollouts become stale

Problem Context: Agentic rollouts involve real tool calls (networking, databases, code execution) with second-level latency. When a rollout completes, the policy parameters may have already updated several steps, so $\pi_\theta \neq \pi_{\theta_\text{old}}$.

Importance Weight (IS weight):

$$w(\tau) = \frac{\pi_\theta(\tau)}{\pi_{\theta_\text{old}}(\tau)} = \prod_{t \in \text{agent tokens}} \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_\text{old}}(a_t|s_t)}.$$

Why continuous multiplication is dangerous: In a T-turn trajectory, agent tokens can number in the thousands. Even if each step's ratio $\approx1.05$, after continuous multiplication, the IS weight can be $\gg10$ — variance explodes, and a tiny number of samples dominate the gradient.

Engineering Correction Methods:

1. PPO clip5 ($\epsilon$ clip): Truncates each token's ratio to $[1-\epsilon, 1+\epsilon]$. Does not correct bias but effectively controls variance. Suitable for synchronous training, where policy lag does not exceed 1-2 mini-batches.
2. Sequence-level truncated IS (TIS): Truncates the entire trajectory's IS weight to an upper bound (e.g., 3.0). Simple but biased.
3. Use ESS to dynamically reduce learning rate: Monitor rollout staleness using effective sample size $\text{ESS}=(\sum w_i)^2/\sum w_i^2$. Automatically reduce learning rate when ESS falls below a threshold to avoid gradient shocks.
4. Prefix IS ratio: The theoretically correct correction term is the prefix IS ratio (the cumulative product over the entire sequence prefix), not independent truncation of per-token ratios. However, implementation is complex and numerically unstable.

Interview Trap: "Is using PPO clip enough?" — Yes for synchronous training. In asynchronous/agentic scenarios, policy lag can be dozens of steps. At that point, clip only treats the symptom (reduces variance but bias is large), effectively performing gradients on the incorrect distribution. It must be combined with a small policy lag design or ESS monitoring.

Q4. Specific forms of long-horizon reward hacking and mitigation

"Long-horizon" makes hacking easier: Single-turn hacking only requires finding a loophole in one response. A long-horizon agent can slowly accumulate shortcuts over dozens of steps, cover evaluation files, or exploit tool side effects.

Three typical forms:

Why it's more severe in long-horizons: Theoretical analysis7Scaling Laws for Reward Model Overoptimization: As KL divergence increases, gold reward first rises then falls; the difference between proxy reward and gold reward monotonically increases with KL.Gao 2022 ↗ shows that the difference between proxy reward and gold reward monotonically increases with KL divergence. The longer the trajectory, the greater the total KL divergence. According to the scaling law [7], hacking risk systematically increases.

Mitigation Combination:

1. Focus on verifiable terminal rewards4: Unit test pass / environment state achievement, harder to hack than neural network proxy rewards.
2. Step/token cost penalties: $R'(\tau) = R(\tau) - \alpha \cdot |\tau|$, directly suppresses looping.
3. Observation token read-only (loss mask): Prevents the agent from learning to "generate output formats that pass mock checks".
4. KL penalty term: $R' = R - \beta\,\text{KL}(\pi_\theta\|\pi_{\text{ref}})$, "brakes" before proxy reward and gold reward diverge.
5. Adversarial test set rotation: Regularly change evaluation samples to prevent the agent from memorizing shortcuts for specific test cases.

Q5. How does partial observability (POMDP) make value estimation difficult?

Information structure difference between single-turn RL and long-horizon agentic RL:

Single-turn reasoning: $V(s) \approx V(\text{prompt})$ — prompt is fully visible, value function input is complete.

Multi-turn agentic: $s_t$ = historical conversation + previous turn's tool return, but the next turn's tool return is unknown — the agent is in a POMDP, unaware of future observations.

Three specific difficulties:

1. Randomness of tool returns: The same action (API call) may return different content due to network state, external DB version differences — the value function needs to take expectation over this randomness, but during training, only one specific return is seen. Single-step bootstrapping ($V(s_{t+1})$) fits the value of a noisy observation, leading to slow convergence and hard-to-estimate bias.

2. Context length explosion: As turns increase, $s_t$ grows linearly (full history concatenation). If the value network uses the same LM backbone, its forward pass cost grows quadratically with context length — value bootstrapping itself becomes expensive.

3. Irreversibility of external state: The agent modifies a database/filesystem, and these side effects are not in the token stream — the value function cannot see the "hidden state of the environment". Traditional POMDP solutions (belief state) cannot be directly applied in the LLM context.

Practical Responses:

• Use a lightweight turn-level value head (attached to the hidden state of the last generated token) instead of a critic for the entire rollout.
• Summarize tool returns before feeding them into the value input to compress context.
• Accept higher bias: Use GAE with $\lambda<1$ to reduce reliance on distant bootstrapping, at the cost of slightly underestimating long-term advantage.

Q6. Exploration problem under long-horizon sparse rewards

Why single-turn RL exploration strategies are insufficient for long-horizons: In single-turn RL, random token sampling can explore. In multi-turn scenarios, the probability of success trajectories decays exponentially with turns — if each turn's correct probability is 0.8, after 10 turns the success rate drops to $0.8^{10}\approx 0.11$. The agent rarely sees positive rewards, and the training signal is nearly all zeros.

Three types of exploration strategies:

1. Curriculum learning: Start with short horizons / easy subtasks, gradually increasing difficulty. The core is to ensure positive rewards are frequent enough early in training to generate effective gradients. Cost: Requires automatic labeling of task difficulty or manual curriculum design.

2. Subgoal / milestone rewards (use with caution): Give small rewards at intermediate steps to guide exploration. Problem: As noted in Q4, milestones themselves can be gamed — must be combined with verifiable milestones (e.g., passing unit tests for sub-functions) rather than neural network scoring.

3. Replay + Prioritized Experience Replay: Retain a small number of historical success trajectories and resample them with higher probability — letting the model continually see "what is success" in extremely sparse environments. Cost: Introduces off-policy issues (see Q3).

4. Hindsight relabeling (HER, 1707.01495): Relabel a failed trajectory by the state it actually reached, treating that as the "goal" — the trajectory has reward=0 for the original goal but reward=1 for "the state it happened to achieve," so even under sparse binary reward you extract a positive signal from failure (equivalent to an implicit curriculum: there is always a subgoal that "succeeded in hindsight"). Key limitation: it needs a relabelable goal-conditioned space; open-ended agent tasks (e.g., "fix this bug") have no trivially relabelable goal from failure — "ran a bunch and didn't fix it" cannot be retroactively recast as "successfully fixed some other bug" — so on LLM agents HER usually applies only to subtasks with a goal-conditioned, relabelable achieved-goal space (reaching some state / retrieving a specified document) and cannot be blindly ported to general SWE/GUI.

Interview Follow-up: "If the task success rate is always <5%, can GRPO still be used?" — Practical experience: Group size needs to be large enough to guarantee at least 1 success within the group; otherwise, the entire group's advantage degenerates to all zeros, equivalent to running rollouts for nothing. At this point, it is recommended to first use SFT warm-starting (learning from a small set of successful trajectories) before switching to RL.

Q7. After masking observation tokens, which tokens actually receive advantage? PRM step-level credit vs pure ORM

Precise answer to "which tokens receive advantage":

Suppose a trajectory contains the following token sequence:

[system_prompt] [user_turn_1] [agent_think_1] [agent_act_1] [obs_1] [agent_think_2] [agent_act_2] [obs_2] … [agent_final]

Tokens with action_mask=1: All agent_think_* + agent_act_* + agent_final. Tokens with action_mask=0: system_prompt, user_turn_*, all obs_* (tool returns/environment observations).

Advantage broadcasting rule: If using turn-level GAE, then all mask=1 tokens within the same turn share that turn's $\hat{A}^{\text{turn}}$. The final gradient only flows to token positions with mask=1.

A common pitfall: If the agent's <think> block is treated as internal reasoning rather than an action (some implementations mask out CoT), then <think> tokens have mask=0, and the gradient does not flow through the reasoning chain — effectively training only "action selection" without training "reasoning quality". This is an implementation detail, tested in interviews to see if the semantics of masking are truly understood.

PRM (Process Reward) vs ORM (Outcome Reward) credit granularity comparison8Defining PRM's step-level reward as step-level advantage (change in future success probability) is theoretically equivalent to RL's Q-V difference and needs to be estimated using an independent prover policy, not the current policy.Setlur 2024 ↗:

PRM's step-level advantage definition: Theoretically, the cleanest PRM step-level reward is the "change in future success probability" brought by that step: $r_t^{\text{PRM}} = P(\text{success}|s_{t+1}) - P(\text{success}|s_t)$. This is definitionally equivalent to RL's advantage ($Q(s,a)-V(s)$)8Defining PRM's step-level reward as step-level advantage (change in future success probability) is theoretically equivalent to RL's Q-V difference and needs to be estimated using an independent prover policy, not the current policy.Setlur 2024 ↗. In practice, Monte Carlo rollout estimation of $P(\text{success}|s_t)$ is used, at the cost of requiring numerous rollouts per step.

Interview Trap: "If PRM is used, is the discount $\gamma$ no longer needed?" — Incorrect. PRM provides step-level rewards, which still need to be accumulated into a return using discounting or GAE. PRM solves "how much reward each step should get," not "how to convert multi-step rewards into gradient signals for the current policy."

References

All are original sources of classic foundational methods, verified item by item (title + arXiv ID). Click the superscript to jump, click ↩ to return.

1. Yao et al. ReAct: Synergizing Reasoning and Acting in Language Models. ICLR 2023. arXiv:2210.03629 — think→act→observe paradigm. ↩
2. Shao et al. DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. 2024. arXiv:2402.03300 — GRPO: Group relative baseline, critic-free. ↩
3. Lightman et al. Let's Verify Step by Step. 2023. arXiv:2305.20050 — Process supervision / PRM (PRM800K). ↩
4. Lambert et al. Tülu 3: Pushing Frontiers in Open Language Model Post-Training. 2024. arXiv:2411.15124 — RLVR: Using verifiable correctness as terminal reward. ↩
5. Schulman et al. Proximal Policy Optimization Algorithms. 2017. arXiv:1707.06347 — PPO (policy gradient baseline). ↩
6. Schulman et al. High-Dimensional Continuous Control Using Generalized Advantage Estimation. ICLR 2016. arXiv:1506.02438 — GAE: λ-weighted TD residuals, bias-variance trade-off. ↩
7. Gao et al. Scaling Laws for Reward Model Overoptimization. 2022. arXiv:2210.10760 — Scaling law of proxy vs gold reward with KL divergence. ↩
8. Setlur et al. Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning. 2024. arXiv:2410.08146 — PRM step-level advantage = change in future success probability, equivalent to Q-V difference. ↩