One-sentence Summary

Researchers from the Institute of Automation, Chinese Academy of Sciences, the University of Chinese Academy of Sciences, and Tsinghua University use $\operatorname{Pass}@(K,T)$Pass@(K,T) to show that multi-turn agentic RL gains depend on sufficient interaction budgets and mainly strengthen error recovery and long-horizon resilience rather than single-step decision quality, and they introduce BudgetMix RL, which varies interaction budgets during training to achieve robust performance across diverse execution settings.

Key Contributions

• The paper uses Pass@(K,T) evaluation across sampling breadth K and interaction depth T to show that trajectory-level multi-turn RL gains depend on sufficient turn budgets and diminish significantly when budgets tighten.
• The analysis identifies that these gains arise mainly from long-horizon execution and error recovery rather than consistently stronger single-step decisions, and finds that step-level action quality can decline under multi-turn RL.
• The paper proposes BudgetMix RL, a training strategy that varies interaction budgets during training, and experiments show it improves robustness across execution settings while mitigating declines in step-level action quality.

Introduction

Multi-turn agentic reinforcement learning has become an important approach for improving long-horizon LLM agents in tasks such as coding and tool use, but it remains unclear exactly which capabilities are improved and whether the resulting agents stay reliable under realistic deployment budgets. Prior evaluation primarily focuses on trajectory-level task success or single-turn Pass@K sampling breadth, missing the interaction-depth dimension and step-level action quality that are central to agentic settings. The authors introduce a two-dimensional Pass@(K,T) evaluation and step-level analyses, showing that agentic RL gains depend on sufficient interaction budgets and mainly come from stronger long-horizon execution and error recovery rather than consistently better single-step actions. They further identify this budget dependence as a hidden deployment risk and propose BudgetMix RL to improve performance across budgets while mitigating declines in step-level action quality.

Method

Multi-Turn Agentic Reinforcement Learning

The authors formulate agent learning as a multi-turn interaction between a policy and an environment. For a task $x \sim D$x∼D, the agent maintains an interaction history

At each turn $t$t, the agent samples an action from its policy,

and the environment returns the next observation according to

Actions can represent tool calls, terminal operations, or code execution. Given an interaction budget of at most $T$T turns, an episode produces a trajectory

which is scored by a terminal verifier through a reward $R(\tau_{\leq T})$R(τ≤T​). This formulation supports both outcome-only reinforcement learning, such as GRPO, and process-level credit assignment methods, such as GiGPO.

Pass@(K, T): Sampling Breadth and Interaction Depth

To evaluate agent performance across both sampling breadth and interaction depth, the authors introduce the metric $\operatorname{Pass}@(K, T)$Pass@(K,T). Conventional agent evaluations typically report trajectory success. In contrast, single-turn reinforcement learning often uses $\operatorname{Pass}@K$Pass@K, which measures the probability that at least one of $K$K independent samples succeeds. This corresponds to sampling breadth.

Interactive agents introduce an orthogonal axis: the maximum interaction budget $T$T available per trajectory, which controls interaction depth. The metric $\operatorname{Pass}@(K, T)$Pass@(K,T) captures both dimensions simultaneously:

Under this definition, $K$K controls breadth while $T$T controls depth. Fixing the total sampling budget to a constant $C$C and sweeping over $T$T yields the trajectory-level metric $\operatorname{Pass}@T = \operatorname{Pass}@(K=C, T)$Pass@T=Pass@(K=C,T), which isolates the interaction-depth axis.

BudgetMix RL: Optimizing Across Interaction Budgets

The main training method proposed by the authors is BudgetMix RL. It is designed to preserve long-horizon execution capabilities and trajectory-level gains while encouraging more careful single-step decisions and reducing reliance on extra interaction budget for downstream error recovery.

BudgetMix RL keeps the same reward mechanism as traditional multi-turn agentic reinforcement learning but varies the interaction budget across training trajectories. It can be combined with existing agentic RL algorithms, including GRPO, PPO, and GiGPO.

Standard multi-turn agentic RL samples trajectories under a fixed maximum budget $T_{\max}$Tmax​ and optimizes either outcome rewards or per-step rewards. However, this objective does not explicitly distinguish solutions that require different amounts of interaction as long as they finish within the allowed budget. BudgetMix makes a single modification to this procedure. For a task instance $x$x with full budget $T_{\max}(x)$Tmax​(x), the authors construct candidate budgets at 10% intervals and uniformly sample one budget per task group:

During training, the total budget and the remaining budget are provided within the prompt. Any trajectory that exceeds its assigned budget without completing the task receives a reward of zero. The reward signal design remains consistent with traditional multi-turn RL.

The central idea of BudgetMix is to turn the interaction budget $T$T from an evaluation dimension in $\operatorname{Pass}@(K, T)$Pass@(K,T) into a training dimension. The interaction budget changes the conditions under which the same reward can be obtained. A tighter budget limits opportunities for retries and therefore places greater demands on earlier decisions, while an ample budget preserves opportunities for long-range execution. By sampling different budgets during training, the policy is exposed to both regimes and is encouraged to produce trajectories that remain effective under varying interaction constraints.

Experiment

The authors evaluate multi-turn agentic reinforcement learning with a two-dimensional Pass@(K,T) measure across sampling breadth and interaction depth, using GRPO on DeepCoder-MT, BFCL, InterCode-SQL, and FrozenLake. They find that agentic RL can push trajectory-level success beyond the base model's capability boundary, but gains depend on sufficient interaction budgets and are not driven by uniformly better single-step actions; instead, RL improves error recovery and later-stage execution while individual action quality can decline. Likelihood and training analyses attribute this to accumulating trajectory-level policy shifts rather than stronger local decisions, and process supervision or budget mixing can partly stabilize these tradeoffs.

BudgetMix improves Pass@8 over the base model and standard full-budget RL under constrained interaction budgets across FrozenLake, DeepCoder-MT, BFCL-v3, and InterCode-SQL. The average advantage over full-budget RL is largest at the tightest budget and narrows as the budget increases, while full-budget performance remains comparable. This suggests BudgetMix strengthens performance stability across budgets without compromising long-horizon execution. Under 25%, 50%, and 75% of maximum interaction budget, BudgetMix outperforms both the base model and full-budget RL on all four tasks, with the strongest average gains at the tightest budget. At 100% interaction budget, BudgetMix maintains parity with full-budget RL, preserving long-horizon task performance.

BudgetMix is evaluated on FrozenLake, DeepCoder-MT, BFCL-v3, and InterCode-SQL under constrained interaction budgets, measuring Pass@8 relative to a base model and standard full-budget reinforcement learning. It improves performance over both baselines at 25%, 50%, and 75% of the maximum interaction budget, with the largest average gains at the tightest budget and a narrowing advantage as the budget increases. At 100% budget, BudgetMix remains comparable to full-budget RL, indicating that it stabilizes performance under limited budgets without sacrificing long-horizon task execution.