ArXiv: 2602.06554
🎯 Pitch
In multi-turn agentic RL, standard backbone algorithms like PPO and GRPO provably cannot achieve both critic-free operation and convergence guarantees—you get one or the other. This paper introduces SeeUPO, which resolves the impossibility by reformulating multi-turn interaction as a series of bandit problems solved in reverse execution order, guaranteeing monotonic improvement and global optimality without a critic network. On AppWorld and BFCL v4, SeeUPO delivers 24–55% relative gains over baselines while completely eliminating the training collapses that plague existing critic-free methods.
1. Executive Summary
This paper systematically analyzes the convergence properties of backbone RL algorithms in multi-turn agentic scenarios and introduces SeeUPO (Sequence-level Sequential Update Policy Optimization), a novel critic-free algorithm with formal convergence guarantees. The analysis categorizes existing methods along two dimensions—advantage estimation (GAE vs. GRAE) and policy update mechanisms (REINFORCE vs. PPU)—revealing a fundamental trade-off where no mainstream algorithm simultaneously achieves both critic-free operation and convergence guarantees in multi-turn settings. SeeUPO resolves this by modeling multi-turn interactions as sequentially-executed multi-agent bandit problems with reverse-order turn-by-turn policy updates (enabling backward induction from turn 𝑇 down to turn 1), inheriting monotonic improvement from the HAML framework and achieving provable convergence to global optimality. On AppWorld and BFCL v4 benchmarks with Qwen3-14B and Qwen2.5-14B, SeeUPO achieves relative gains of 43.3%–54.6% and 24.1%–41.9% respectively over PPO, GRPO, and GSPO baselines while avoiding the catastrophic training collapses observed in critic-free alternatives, establishing that multi-turn convergence can be guaranteed without a critic network only when updates respect reverse execution order through backward induction.
2. Context and Motivation
The Core Problem: RL Algorithms for LLM Agents Lack Verified Convergence Guarantees in Multi-Turn Settings
Reinforcement learning has become the dominant paradigm for training LLM-based AI agents that interact with environments across multiple turns—navigating websites, executing tool calls, managing multi-step workflows. The field has rapidly adopted a small set of backbone algorithms: PPO, GRPO, RLOO, GSPO, and their variants. However, the paper identifies a critical gap: none of these backbone algorithms have been systematically analyzed or verified for convergence in multi-turn agentic scenarios. As the authors state in Section 1:
"the theoretical soundness of these backbone algorithms in agentic RL scenarios, particularly in multi-turn settings, remains an open question"
This matters because multi-turn interaction is fundamentally different from the single-turn settings where these algorithms were originally developed and validated. In single-turn RL for LLMs (e.g., math reasoning, instruction following), each episode consists of generating one complete response given a prompt—a contextual bandit where the "state" is just the initial prompt and there are no intermediate environmental dynamics. Multi-turn agentic tasks, by contrast, involve sequential interactions where the agent acts, receives environmental feedback (API responses, page states, tool outputs), and then acts again. This introduces genuine MDP dynamics: non-deterministic state transitions, temporal credit assignment across turns, and the potential for compounding errors.
The practical consequence of missing convergence guarantees is what the paper demonstrates empirically: training instability and catastrophic performance collapse in existing methods when applied to multi-turn benchmarks. In Figure 4(c), both GRPO and GSPO exhibit dramatic performance degradation on the Qwen2.5-14B + AppWorld configuration—training curves that crash well below their peak performance. This isn't a minor inefficiency; it's a fundamental failure mode where the algorithms "lose" learned behaviors, making them unreliable for production deployment where stable convergence is essential.
Why This Problem Matters: The Shift from Single-Turn to Agentic AI
The significance of this problem extends beyond academic curiosity. The field is undergoing a decisive shift from single-turn LLM interactions toward agentic AI systems that operate autonomously across extended interactions with tools, APIs, and environments. The paper catalogs multiple dimensions of this shift in Section 1:
- Interaction scope: Moving from single-turn task reasoning to multi-turn interactive planning (Chai et al., 2025; Wang et al., 2025; Xi et al., 2025).
- Capability integration: Evolving from static capability modules (separate planning, tool-use, memory components) to unified policy optimization where RL trains these as interdependent, trainable behaviors (Qian et al., 2025; Yan et al., 2025).
- Multimodal integration: Extending from text-only generation to embodied and multimodal perception agents (Feng et al., 2025; Li et al., 2025).
- Evolutionary mechanisms: Progressing from heuristic-based self-correction to RL-driven self-improvement loops (Wang et al., 2025; Guan et al., 2025; Zhai et al., 2025).
Across all these directions, researchers converge on a small set of backbone RL algorithms. This creates a brittle foundation: if the underlying algorithms lack convergence guarantees in the very multi-turn settings where they're being deployed, the entire edifice of agentic AI research rests on theoretically unsound footing. The paper's empirical results validate this concern concretely—the catastrophic training failures in Figure 4 aren't hypothetical edge cases but reproducible failure modes that manifest on standard benchmarks with standard models.
The theoretical significance is equally important. The convergence properties that are well-understood for PPO and REINFORCE in traditional RL (continuous control, game playing) don't automatically transfer to the LLM fine-tuning context. The combination of sequence-level modeling, critic-free advantage estimation (motivated by the impracticality of training separate value networks at LLM scale), and multi-turn interaction creates a regime where existing guarantees may not hold. The paper provides the first systematic analysis of which combinations do and don't preserve convergence properties in this new setting.
Where Prior Approaches Fall Short
The paper identifies specific limitations organized along two axes: advantage estimation methods and policy update mechanisms.
The Advantage Estimation Landscape: GAE vs. GRAE
Generalized Advantage Estimation (GAE) (Schulman et al., 2016) is the standard approach in PPO-based actor-critic RL. It estimates advantages using TD errors computed via a learned value function (critic) network. The advantage for a state-action pair at time $t$ is a $\lambda$-weighted sum of future TD errors:
where $\delta_t = r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$ and $V_\phi$ is the learned value function. GAE trades off bias and variance through $\lambda$, with the theoretical guarantee of unbiasedness when the value function is perfectly approximated ($V_\phi = V^\pi$). However, this comes with two practical costs in the LLM context:
- Computational overhead: Training a separate critic network alongside the policy (often of comparable size) doubles the GPU and memory requirements. As shown in Table 3, PPO requires 16 GPUs vs. 8 for critic-free methods.
- Value estimation difficulty in multi-turn settings: Non-stationary state transitions across turns make accurate token-level value function estimation significantly harder. The critic must predict the expected return from arbitrary intermediate states within multi-turn trajectories—a harder learning problem than in single-turn settings.
Group Relative Advantage Estimation (GRAE) emerged as a critic-free alternative, popularized by RLOO (Ahmadian et al., 2024) and adopted in GRPO (Shao et al., 2024). The core idea is elegantly simple: for a given initial state (query) $s_0$, sample $N$ independent response trajectories, compute the mean reward $\bar{R} = \frac{1}{N}\sum_{i=1}^N R^{(i)}$, and assign each state-action pair the advantage $\hat{A}^{\text{GRAE}}(s_t, a_t) = R^{(i)} - \bar{R}$. This eliminates the critic entirely—no separate network to train, no value function approximation errors to worry about.
But the paper identifies a structural bias that has been largely overlooked. In an MDP (as opposed to a contextual bandit), the baseline $\bar{R}$ approximates $V(s_0)$ (the value at the initial state), while the true advantage requires the state-dependent baseline $V(s_t)$ (the value at the current state). The difference between these is the structural bias:
The bias is $V(s_t) - V(s_0)$, which is generally non-zero and grows with the number of turns as the agent accumulates reward through interaction. In a 10-turn trajectory where the agent earns progressively more reward, $V(s_5) - V(s_0)$ could be substantial. This means GRAE systematically mis-estimates the quality of actions at later turns relative to earlier ones.
The Policy Update Landscape: REINFORCE vs. PPU
REINFORCE (Williams, 1992; Sutton et al., 1998) is the vanilla policy gradient algorithm. It is fully on-policy: data is collected under the current policy, used for a single gradient update, then discarded. The gradient estimator is:
REINFORCE has well-understood convergence properties when combined with unbiased advantage estimates—it can be viewed as stochastic gradient ascent on the expected return objective. However, its sample efficiency is poor because each data batch is used only once (no importance sampling correction for off-policy updates).
Proximal Policy Update (PPU), the mechanism underlying PPO, addresses sample efficiency by allowing multiple updates per data batch while constraining how far the policy can shift. This is achieved through a clipped surrogate objective:
where $r_t(\theta) = \pi_\theta(a_t \mid s_t) / \pi_{\theta_{\text{old}}}(a_t \mid s_t)$ is the importance sampling ratio and $\epsilon$ (typically 0.2) bounds how much the new policy can differ from the old one. PPU has established monotonic improvement guarantees when the advantage function is accurately estimated.
The critical interaction: PPU's clipping behavior depends on the sign of the advantage estimate $\hat{A}_t$. When $\hat{A}_t > 0$ (action was good), PPU encourages increasing its probability but caps the ratio at $1 + \epsilon$. When $\hat{A}_t < 0$ (action was bad), PPU encourages decreasing probability but floors the ratio at $1 - \epsilon$. If advantage estimates have a structural bias that flips the sign, the clipping mechanism enforces constraints in the wrong direction entirely.
Why Existing Combinations Break
The paper systematically analyzes all four combinations of advantage estimation and policy update mechanisms (Table 1, Sections 3.1-3.2, Appendices C-H):
GAE + PPU (PPO): This is the only combination with full convergence guarantees in multi-turn settings, relying on the critic to provide unbiased advantage estimates (Appendix F, Theorem 6). However, it requires perfect value function approximation, which is increasingly difficult in multi-turn agentic scenarios. Moreover, the computational cost of the critic network is substantial—PPO needs 16 GPUs vs. 8 for critic-free methods (Table 3).
GRAE + REINFORCE (RLOO): Under undiscounted ($\gamma = 1$) objectives with bounded rewards in finite-horizon MDPs, REINFORCE with trivial drift ($\mathfrak{D} \equiv 0$) and trivial neighborhood ($\mathcal{N} = \Pi$) provides convergence guarantees (Appendix E, Theorem 5). The structural bias $V(s_t) - V(s_0)$ is a state-dependent baseline that vanishes in the policy gradient due to the baseline invariance lemma (Appendix D, Lemma 1). However, this only holds under $\gamma = 1$; with discounting, the gradient becomes biased (Appendix D.3). Multi-turn scenarios often require discounting for practical reasons (bounding credit assignment horizons, handling sparse rewards), making this condition restrictive.
GAE + REINFORCE: No existing algorithm instance exists for good reason—this combination is Pareto-dominated. It retains GAE's critic dependency while lacking PPU's trust region constraints. If the value function is imperfect (as is typical), biased GAE estimates can be amplified through REINFORCE's unbounded updates. In contrast, GAE + PPU achieves better sample efficiency with bounded updates, while GRAE + REINFORCE eliminates critic dependency entirely.
GRAE + PPU (GRPO, GSPO, REINFORCE++): This is the combination deployed in many popular critic-free algorithms, and the paper demonstrates it fundamentally breaks convergence guarantees in MDPs (Appendix G, Theorem 7). The mechanism is subtle but devastating:
- In MDPs: GRAE introduces structural bias
$\Delta(s_t) = V(s_t) - V(s_0)$that does not vanish with more samples (Appendix G, Lemma 4). When this biased estimate is used in PPU's clipped objective, the resulting drift function$\mathfrak{D}^{\text{GRAE-PPU}}$has the form (Appendix G, Lemma 5):
-
Violation of drift properties: At the reference policy (
$\bar{\pi} = \pi$), the ReLU term is zero (since$r = 1$and$\text{clip}(1) = 1$), leaving$\mathfrak{D}^{\text{GRAE-PPU}}_\pi(\pi \mid s_t) = -\Delta(s_t) \neq 0$. This violates the zero-at-origin property required for the drift to serve as a valid distance metric. Furthermore, when$\Delta(s_t)$is large positive,$\mathfrak{D}$can be negative, violating non-negativity (Appendix G, Theorem 7, parts 1-2). -
PPU's clipping breaks baseline invariance: Standard policy gradients are invariant to state-dependent baselines—the structural bias
$\Delta(s_t)$cancels out in the gradient computation. However, PPU's clipped objective is non-linear with respect to the advantage estimate, meaning the bias does NOT cancel. The sign of the advantage determines whether PPU clips at$1 - \epsilon$or$1 + \epsilon$. If$\Delta(s_t)$flips the sign of a truly negative advantage from negative to positive, PPU will increase the probability of a bad action—exactly the opposite of the correct update (Appendix G, detailed example in Theorem 7, part 4). -
Contextual bandit exception: In single-turn settings (contextual bandits),
$V(s_t) = V(s_0)$since there's only one state. The structural bias vanishes, and GRAE-PPU becomes a valid Mirror Learning instance (Appendix H, Theorem 8). This explains why GRPO and GSPO work well on single-turn reasoning tasks but fail catastrophically on multi-turn agentic tasks. -
Group variance normalization as an additional violation: GSPO and GRPO further divide advantages by the group standard deviation. The paper proves (Appendix H.3, Theorem 9) that this breaks convergence guarantees unless the variance is identically 1 for all states. The proof shows that the drift function's non-negativity property requires
$\delta(s) = 1$for$A \geq 0$cases and$\delta(s) \leq 1$for$A < 0$cases, forcing$\delta(s) \equiv 1$. In practice, reward variance varies across queries, violating this condition.
The Fundamental Trade-Off
The paper's central theoretical insight (Section 3.2) is that these analyses reveal an unavoidable trade-off in existing algorithm designs:
"mainstream backbone RL algorithms struggle to simultaneously achieve both critic-free operation and convergence guarantees in multi-turn scenarios"
Critic-dependent methods (GAE-PPU): Achieve convergence guarantees but require accurate value function estimation, which is computationally expensive and increasingly difficult in multi-turn settings with non-stationary transitions.
Critic-free methods (GRAE-based): Eliminate the critic's computational burden but either:
- Require undiscounted objectives (GRAE-REINFORCE) which are impractical in many multi-turn settings, or
- Break monotonic improvement through structural bias in PPU's clipped objective (GRAE-PPU).
This trade-off is not a minor inefficiency—it means that none of the algorithms currently used at scale for agent training have verified convergence properties in the very multi-turn settings they're being deployed in. The empirical consequences are visible in Figure 4: GRPO and GSPO exhibit training collapse (Qwen2.5-14B + AppWorld), while PPO—despite convergence guarantees—requires substantially more compute and may still suffer from critic estimation errors in complex environments.
How SeeUPO Positions Itself
The paper positions SeeUPO as a resolution to this trade-off: a critic-free algorithm that does achieve convergence guarantees in multi-turn settings by fundamentally restructuring the problem rather than trying to fix either component in isolation (Section 4.1).
The key intellectual move is to model multi-turn interaction as a sequentially-executed multi-agent bandit problem, where each turn is abstracted as a virtual agent. This modeling choice accomplishes two things simultaneously:
-
Transforms the convergence problem: Multi-turn convergence analysis becomes multi-agent convergence analysis, allowing the paper to leverage the Heterogeneous-Agent Mirror Learning (HAML) framework (Zhong et al., 2024), which provides monotonic improvement guarantees for sequential policy updates in cooperative multi-agent settings.
-
Eliminates the structural bias: In the bandit setting (each "agent" makes a single decision given the conversation history), there are no state transitions—each turn's action is evaluated against its immediate reward and the optimal continuation value. This means GRAE's structural bias vanishes (as shown in Appendix H), making critic-free advantage estimation unbiased and compatible with PPU-style updates.
The reverse update order ($T \rightarrow T-1 \rightarrow \cdots \rightarrow 1$) is the crucial design choice that elevates monotonic improvement (already guaranteed by HAML) to global optimality. Under reverse order, when updating turn $t$, all subsequent turns $t+1, \ldots, T$ have already been updated to their optimal policies given their continuation values. This enables backward induction: each turn optimizes against the true optimal continuation value $V^*$, ensuring the fixed point of the iterative process is the globally optimal joint policy (Appendix B, Theorem 2). In contrast, forward or random update orders only guarantee Nash equilibrium convergence through the standard HAML framework—which in cooperative settings may correspond to suboptimal local equilibria.
SeeUPO's practical instantiation (SeeUPPO-GRAE, Section 4.2) combines:
- PPO-style clipping for policy updates (implementing the HAML mirror operator via gradient-based optimization)
- GRAE with batch-level normalization for advantage estimation (preserving convergence properties while ensuring numerical stability)
- Turn-oriented batch construction (Figure 3) that organizes samples by turn for sequential updates, as opposed to concatenating sliced turns or using full trajectories
The empirical positioning is clear: SeeUPO is not proposed as "one more algorithm" in the crowded space of LLM RL methods, but as the first algorithm that simultaneously achieves critic-free operation and provable convergence in multi-turn agentic settings. The baseline comparisons in Table 2 and Figure 4 demonstrate that this theoretical advantage translates to practical gains: 43.3%–54.6% relative improvement over baselines on Qwen3-14B, stable training without the catastrophic collapses that plague existing critic-free methods, and competitive computational efficiency (8 GPUs vs. PPO's 16 GPUs, with ~1.5× training time compared to other critic-free methods).
3. Technical Approach
3.1 Reader Orientation
The paper develops SeeUPO (Sequence-level Sequential Update Policy Optimization), a training algorithm that fine-tunes LLM-based agents to perform multi-turn interactive tasks (like navigating applications or calling APIs) using reinforcement learning. The system solves the problem of training instability in multi-turn agentic RL: existing backbone algorithms either require expensive critic networks that are hard to train accurately in multi-turn settings (PPO with GAE), or eliminate the critic but lose convergence guarantees due to structural bias in advantage estimation (GRPO, GSPO, RLOO). SeeUPO resolves this by reformulating multi-turn interaction as a sequentially-executed multi-agent bandit problem and applying reverse-order turn-by-turn policy updates that enable backward induction to global optimality, all while maintaining critic-free advantage estimation.
3.2 Big-Picture Architecture (Diagram in Words)
The system has four major components that operate in a training loop:
-
Multi-Agent Decomposition Module — Takes multi-turn interaction trajectories (state
$\boldsymbol{s}_0$, actions$\boldsymbol{a}_1, \ldots, \boldsymbol{a}_T$, team reward$r$) and abstracts each turn into a virtual agent with its own policy$\boldsymbol{\pi}_t(\boldsymbol{a}_t \mid \boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$. All agents share the same LLM parameters$\boldsymbol{\theta}$but are treated as functionally distinct decision-makers operating sequentially. -
Turn-Oriented Batch Constructor (Figure 3) — During data collection, instead of batching entire trajectories or concatenating sliced turns, samples from identical turns across different trajectories are organized into separate pools
$\mathcal{D}_t = \{(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1}, \boldsymbol{a}_t)\}$. This enables turn-by-turn sequential policy updates in the next component. -
Sequential Policy Updater (Reverse Order) — Updates the shared policy parameters
$\boldsymbol{\theta}$sequentially for each turn$t = T, T-1, \ldots, 1$using a PPO-style clipped objective with GRAE-based advantage estimates. A recursively maintained quantity$M_t(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$propagates importance-sampling corrections from already-updated subsequent turns, implementing the HAML mirror operator (Equation 6). -
Global Advantage Estimator (GRAE, Batch-Normalized) — For each initial state
$\boldsymbol{s}_0$in the batch, samples$G$joint actions, computes team rewards, and estimates the global advantage as$\hat{A}^{\hat{\boldsymbol{\pi}}^k}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) = r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) - \bar{r}(\boldsymbol{s}_0)$. Batch-level normalization (subtract batch mean, divide by batch standard deviation) is applied for numerical stability while preserving convergence properties (Appendix H.3.3).
Information flows as follows: raw multi-turn trajectories enter → decomposed into turn-level pools → global advantages computed via GRAE with batch normalization → policies updated sequentially in reverse turn order, with each update incorporating importance-sampling corrections from turns already optimized → updated policy used for next iteration's data collection.
3.3 Roadmap for the Deep Dive
- First, the multi-agent modeling abstraction (Section 4.1), since it is the foundational reformulation that enables all subsequent analysis and determines what structures the algorithm can exploit.
- Second, the reverse-order sequential update mechanism and its HAML theoretical foundations (Section 4.1), because the update order is the crucial design choice that elevates monotonic improvement to global optimality.
- Third, the practical instantiation: SeeUPPO-GRAE (Section 4.2), covering the PPO-style clipped objective, the recursive
$M_t$quantity, and turn-oriented batch construction—the concrete algorithm that implements the theoretical framework. - Fourth, the GRAE-based advantage estimation with batch normalization (Section 4.2), since advantage estimation must be both unbiased (to preserve convergence) and numerically stable (to work in practice).
- Fifth, the formal global optimality guarantee (Appendix B, Theorem 2), walking through why the reverse update order enables backward induction and how the dropping-the-drift argument certifies optimality for each turn.
3.4 Detailed, Sentence-Based Technical Breakdown
This is primarily a theoretical analysis paper with a novel algorithm whose core contribution is reformulating multi-turn RL as a sequentially-executed multi-agent problem with reverse-order updates, thereby inheriting convergence guarantees from the HAML framework.
Multi-Agent Modeling: Abstracting Turns as Virtual Agents
The foundational insight of SeeUPO is to reframe multi-turn interaction as a cooperative multi-agent problem where each turn is a distinct "agent" making a single decision (a contextual bandit), and the agents execute sequentially (turn 1 acts first, then turn 2, etc.). This abstraction is described in Section 4.1 and illustrated in Figure 2.
Formally, the problem is modeled as follows. Given a multi-turn task with maximum $T$ turns:
-
Global state:
$\boldsymbol{s}_0 \in \mathcal{S}_S$is the initial task state (the user's query or goal specification). All agents share this same initial state—there are no intermediate environmental state transitions in the bandit formulation. Instead, the "state" for agent$t$is the initial state plus the action history from preceding agents:$(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$. -
Sequence-level actions: Agent
$t$'s action$\boldsymbol{a}_t \in \mathcal{A}_S$is the complete response generated at turn$t$(e.g., a full API call with parameters, a complete reasoning step with tool invocation). This is "sequence-level" because each action is an entire generated sequence, not individual tokens. The joint action$\boldsymbol{a}_{1:T} = (\boldsymbol{a}_1, \boldsymbol{a}_2, \ldots, \boldsymbol{a}_T)$is the concatenation of all agents' actions. -
Agent policies: Each agent
$t$has a policy$\boldsymbol{\pi}_t(\boldsymbol{a}_t \mid \boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$that conditions on the initial state and all previous agents' actions. Crucially, all agents share the same underlying LLM parameters$\boldsymbol{\theta}$(parameter sharing), but they are treated as functionally distinct because the conditioning context$(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$differs. The paper argues (Section 6, Limitations) that the large parameter space of modern LLMs provides sufficient representational capacity for different turns to develop functionally distinct behaviors despite parameter sharing—the policies are non-homogeneous from a turn-level perspective even with shared weights. -
Team reward: All agents optimize a shared reward
$r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$, which equals the final task reward or cumulative return across all turns. This is a cooperative multi-agent setting: there is no conflict between agents, and the joint objective is simply the expected reward$J(\hat{\boldsymbol{\pi}}) = \mathbb{E}_{\boldsymbol{s}_0 \sim d, \boldsymbol{a}_{1:T} \sim \hat{\boldsymbol{\pi}}} [r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})]$. -
State transitions: There are none in the bandit formulation. Each agent makes exactly one decision, and the "evolution of the interaction" is implicitly modeled through the sequentially executed policies. This is what transforms multi-turn MDPs into bandit problems: the temporal structure is captured through the sequential execution order among agents, not through environmental state transitions.
Why this abstraction is powerful. The multi-agent modeling accomplishes three things simultaneously:
-
Eliminates the structural bias of GRAE. In a contextual bandit, there is only one state per agent (the initial state plus history). GRAE estimates advantage as
$r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) - \bar{r}(\boldsymbol{s}_0)$, and since there are no intermediate state transitions, the baseline$\bar{r}(\boldsymbol{s}_0)$is the correct baseline for evaluating actions at the turn level—the structural bias$V(\boldsymbol{s}_t) - V(\boldsymbol{s}_0)$that plagues GRAE in MDPs simply does not arise (Appendix H, Lemma 6). This makes GRAE an unbiased advantage estimator in the bandit setting, enabling critic-free operation without sacrificing correctness. -
Enables decomposition of the global advantage. The multi-agent advantage decomposition lemma from HAML (Zhong et al., 2024; Appendix A.2, Equation 12) states that for any agent subset
$i_{1:m}$:
where $A^{i_j}_{\boldsymbol{\pi}}(s, \boldsymbol{a}_{i_{1:j-1}}, \boldsymbol{a}_{i_j}) = Q^{i_{1:j}}_{\boldsymbol{\pi}}(s, \boldsymbol{a}_{i_{1:j}}) - Q^{i_{1:j-1}}_{\boldsymbol{\pi}}(s, \boldsymbol{a}_{i_{1:j-1}})$ is the multi-agent advantage function that evaluates the contribution of agent $i_j$ given previous agents' actions $\boldsymbol{a}_{i_{1:j-1}}$.
This decomposition means that the global advantage (how good the entire interaction was) can be broken down into turn-specific contributions through the sequential update mechanism. When updating turn $t$'s policy, the algorithm uses the HAML mirror operator (Equation 14, Appendix A.2) which computes the local advantage for agent $t$ conditioned on the already-updated policies of subsequent turns. This performs implicit turn-level credit assignment: turn $t$'s contribution is evaluated against the optimal continuation value provided by turns $t+1, \ldots, T$.
- Leverages existing multi-agent theory. By casting the problem in multi-agent terms, SeeUPO can directly inherit the monotonic improvement guarantee from HAML (Theorem 1, Appendix A.2): if each agent's policy update uses a valid drift functional and neighborhood operator, and updates are performed sequentially, the expected joint return is monotonically non-decreasing:
$J(\hat{\boldsymbol{\pi}}^{k+1}) \geq J(\hat{\boldsymbol{\pi}}^k)$for all iterations$k$.
The training-phase specificity. The paper emphasizes that this multi-agent modeling is a methodological shift in data treatment during training, not a deployment-time mechanism. At inference time, the agent generates responses turn by turn as usual; the "virtual agents" exist only during training to structure the optimization problem. This distinction matters because it means SeeUPO does not require any changes to the execution environment or additional coordination infrastructure—it is purely a training algorithm.
Reverse-Order Sequential Update: The Mechanism for Global Optimality
The sequential update mechanism is the core operational component of SeeUPO. At each training iteration $k$, after collecting a batch of multi-turn trajectories under the current joint policy $\hat{\boldsymbol{\pi}}^k$, the algorithm updates each turn's policy sequentially, one at a time, incorporating information from turns that have already been updated in the current iteration.
The update order. The paper makes a specific and theoretically motivated choice: reverse execution order, meaning turn $T$ is updated first, then turn $T-1$, then $T-2$, down to turn 1. This is not arbitrary—it is essential for the global optimality guarantee (Appendix B, Theorem 2). The reverse order enables backward induction: when updating turn $t$, all subsequent turns $t+1, \ldots, T$ have already been updated to their (conditionally) optimal policies given the continuation context. Therefore, turn $t$ optimizes against the true optimal continuation value $V^*$ rather than the current (potentially suboptimal) continuation value.
The HAML update rule for SeeUPO (Equation 3). For turn $t$ in the reverse update order, the policy update solves:
where:
$\hat{\pi}^k_t$is the policy for turn$t$at the start of iteration$k$(the sampling policy),$\bar{\pi}_t$is the candidate policy being optimized (the variable of the argmax),$\mathcal{U}_{\hat{\pi}^k_t}(\hat{\pi}^k_t)$is the neighborhood operator for turn$t$, defining the search space for policy updates—it must satisfy continuity, compactness, and contain a closed ball around the current policy (Appendix A.2). In the practical implementation, this is implemented through PPO-style clipping, which implicitly defines a trust region,$\beta_{\hat{\pi}^k}$is the sampling distribution over initial states$\boldsymbol{s}_0$,$\mathbb{E}_{\boldsymbol{a}_{t+1:T} \sim \hat{\pi}^{k+1}_{t+1:T}, \boldsymbol{a}_t \sim \bar{\pi}_t} [A^{\hat{\pi}^k}_t]$is the expectation of the local advantage function for turn$t$, where actions$\boldsymbol{a}_{t+1:T}$are sampled from the already-updated policies of subsequent turns$\hat{\pi}^{k+1}_{t+1:T}$, and the action$\boldsymbol{a}_t$is sampled from the candidate policy$\bar{\pi}_t$,$\mathfrak{D}_{\hat{\pi}^k_t}(\bar{\pi}_t \mid \boldsymbol{s}_0, \hat{\pi}^{k+1}_{t+1:T})$is the heterogeneous-agent drift functional (HADF, Equation 13 in Appendix A.2), which quantifies the cost of updating from$\hat{\pi}^k_t$to$\bar{\pi}_t$, conditioned on the subsequent turns having updated to$\hat{\pi}^{k+1}_{t+1:T}$. It must satisfy non-negativity ($\mathfrak{D} \geq 0$with equality when$\bar{\pi}_t = \hat{\pi}^k_t$) and zero gradient at the reference policy.
What this equation computes in operational terms. For each turn $t$ in reverse order, the algorithm searches over candidate policies $\bar{\pi}_t$ within a constrained neighborhood of the current policy. For each candidate, it computes the expected local advantage: how much better (or worse) the turn-$t$ actions $\boldsymbol{a}_t$ sampled from $\bar{\pi}_t$ are compared to the current policy, given that subsequent turns will follow their already-improved policies $\hat{\pi}^{k+1}_{t+1:T}$. This expectation is then penalized by the drift functional, which measures how far $\bar{\pi}_t$ diverges from $\hat{\pi}^k_t$. The candidate that maximizes this penalized objective is selected as $\hat{\pi}^{k+1}_t$.
Why this form enables backward induction. The crucial difference from standard policy gradient methods is the expectation over $\boldsymbol{a}_{t+1:T} \sim \hat{\pi}^{k+1}_{t+1:T}$. Because updates happen in reverse order, when optimizing turn $t$, the policies for turns $t+1, \ldots, T$ have already been updated in this iteration. This means turn $t$ optimizes against the best available continuation policies, not the old policies from iteration $k$. As the algorithm converges, these continuation policies approach optimality, and turn $t$'s optimization problem becomes:
which, by the dropping-the-drift argument (Appendix B, Step 4), yields the globally optimal policy for turn $t$ given optimal subsequent behavior.
Local advantage function computation (Equation 4). The expectation over local advantages cannot be computed directly because it requires sampling from the updated policies $\hat{\pi}^{k+1}_{t+1:T}$, which means re-running data collection. Instead, SeeUPO uses an importance-sampling trick to estimate this expectation using the already-collected data under the old policy $\hat{\pi}^k$:
where:
- The first factor
$(\frac{\bar{\pi}_t}{\hat{\pi}^k_t} - 1)$is the importance-sampling correction for turn$t$'s action: it reweights the data collected under$\hat{\pi}^k_t$to reflect what would happen under the candidate policy$\bar{\pi}_t$. The$-1$term has zero gradient with respect to$\bar{\pi}_t$and can be omitted in gradient computation; it is included for the theoretical derivation to match the mirror operator form. - The second factor
$\frac{\hat{\pi}^{k+1}_{t+1:T}}{\hat{\pi}^k_{t+1:T}}$is the importance-sampling correction for subsequent turns: it reweights the old-policy trajectories to reflect the already-updated policies of turns$t+1$through$T$. This factor encodes the sequential update information—it tells turn$t$'s update how the subsequent turns' policies have changed. $\hat{A}^{\hat{\pi}^k}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$is the global advantage estimate computed from the entire trajectory (Equation 5/9).
What this equation computes. Starting from the global advantage $\hat{A}^{\hat{\pi}^k}$ (a single scalar per trajectory indicating whether the whole interaction was better or worse than average), the expectation reweights each trajectory by two importance-sampling ratios. The first ratio corrects for the candidate policy $\bar{\pi}_t$ potentially assigning different probability to $\boldsymbol{a}_t$ than the old policy. The second ratio corrects for subsequent turns' policies having been updated—if the updated subsequent policies would have been much more (or less) likely to produce $\boldsymbol{a}_{t+1:T}$, this reweights the advantage accordingly. The result is an estimate of the local advantage for turn $t$ conditioned on optimal subsequent behavior, computed entirely from data collected under the old policy.
Why this form—the global advantage decomposition. This formulation effectively performs implicit turn-level credit assignment. The product of importance-sampling ratios decomposes the global advantage into turn-specific contributions: if subsequent turns' policies have improved substantially (making $\frac{\hat{\pi}^{k+1}_{t+1:T}}{\hat{\pi}^k_{t+1:T}}$ large for good trajectories), turn $t$ gets more credit for actions that lead to states where subsequent improvements are possible. Conversely, if a trajectory was already poor regardless of subsequent improvements, turn $t$'s contribution is appropriately discounted.
Practical Instantiation: SeeUPPO-GRAE Algorithm
The theoretical framework (HAML update rule with reverse order) admits multiple possible implementations. The paper presents one concrete instantiation, SeeUPPO-GRAE (Algorithm 1, Section 4.2), which combines PPO-style clipping for policy updates with GRAE for advantage estimation. The authors emphasize this is not the only possible instantiation—one could substitute TRPO-style trust region constraints or alternative advantage estimators—but SeeUPPO-GRAE is what they implement and evaluate.
Algorithm Structure (Algorithm 1 pseudocode)
The algorithm operates iteratively, with each iteration $k = 0, 1, \ldots, K-1$ consisting of three phases:
Phase 1: Data Collection (Step 2a).
- Sample a dataset
$\mathcal{D}_k = \{(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}, r)\}$by: for each of$B$initial states$\boldsymbol{s}_0$, sample$G$independent trajectories$\boldsymbol{a}_{1:T}$from the current joint policy$\hat{\boldsymbol{\pi}}^k$, and collect the corresponding team rewards$r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$. - Organize the collected data into
$T$turn-specific sample pools: for each turn$t \in \{1, \ldots, T\}$, construct pool$\mathcal{D}_t = \{(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1}, \boldsymbol{a}_t)\}$. This turn-oriented batch construction (Figure 3) is a key architectural difference from methods that batch entire trajectories (like PPO) or concatenate sliced turns. - For tasks with fewer than the maximum
$T$turns, placeholder (no-op/null action) samples are introduced to maintain uniform batch structure. The figure demonstrates this with "Sample 6" as a placeholder.
Why turn-oriented batching. The sequential update mechanism updates each turn's policy separately. Having pre-organized pools $\mathcal{D}_t$ means each update step $t$ directly accesses samples from the corresponding turn position, without needing to slice trajectories or handle variable-length sequences during the update. This also naturally handles the fact that different trajectories may have different actual numbers of turns—short trajectories get padded with placeholders in later-turn pools.
Phase 2: Joint Advantage Estimation (Step 2b). For each trajectory $(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$ in the full-trajectory pool $\mathcal{D}_T$:
- Compute the joint (global) advantage using GRAE:
where $\bar{r}(\boldsymbol{s}_0) = \frac{1}{G}\sum_{i=1}^G r(\boldsymbol{s}_0, \boldsymbol{a}^{(i)}_{1:T})$ is the mean reward over the $G$ trajectories sampled from the same initial state $\boldsymbol{s}_0$.
- Initialize the recursive quantity:
$M_{T+1}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) = \hat{A}^{\hat{\pi}^k}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$. This$M_{T+1}$serves as the starting point for the backward recursion that propagates importance-sampling corrections through the turns.
What this advantage represents. In the bandit setting, the advantage function degenerates to $A^{\hat{\pi}^k}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) = r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) - \mathbb{E}_{\boldsymbol{a}'_{1:T} \sim \hat{\pi}^k}[r(\boldsymbol{s}_0, \boldsymbol{a}'_{1:T})]$. GRAE estimates the expectation using the group mean $\bar{r}(\boldsymbol{s}_0)$, making the advantage estimate the centered reward: positive if the trajectory's reward is above average for that initial state, negative if below. This is an unbiased estimate in the bandit setting because there are no intermediate state values to confound the baseline.
Phase 3: Sequential Policy Update (Step 2c). For turns $t = T, T-1, \ldots, 1$ (reverse order):
- Update the policy parameters to obtain
$\boldsymbol{\pi}_{\boldsymbol{\theta}^{k+1}_t}$by computing the gradient with respect to$\boldsymbol{\theta}$of the PPO-style clipped objective (Equation 6). - If
$t > 1$: compute$M_t$for the next (earlier) turn's update via the recursive formula (Equation 8). - If
$t = 1$: set$\boldsymbol{\theta}^{k+1} = \boldsymbol{\theta}^{k+1}_1$—the parameters after updating all turns become the parameters for the next iteration.
Return: After $K$ iterations, return the final optimized policy $\boldsymbol{\pi}_K$.
PPO-Style Clipped Objective (Equation 6)
The concrete policy update for turn $t$ maximizes:
where:
$\mathcal{D}_t = \{(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1}, \boldsymbol{a}_t)\}$is the turn-specific sample pool—note that it contains only the conditioning context up to turn$t-1$and the action at turn$t$, not the full trajectory,$r_t(\boldsymbol{\theta}) = \frac{\boldsymbol{\pi}_{\boldsymbol{\theta}}(\boldsymbol{a}_t \mid \boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})}{\boldsymbol{\pi}_{\boldsymbol{\theta}^k}(\boldsymbol{a}_t \mid \boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})}$is the sequence-level importance sampling ratio for turn$t$, computed analogously to GSPO. This ratio compares the probability of generating the entire turn-$t$response$\boldsymbol{a}_t$under the current (being-optimized) parameters$\boldsymbol{\theta}$versus the reference (sampling) parameters$\boldsymbol{\theta}^k$,$\epsilon$is the clipping parameter (set to 0.2, consistent with standard PPO), which bounds the importance ratio to$[1 - \epsilon, 1 + \epsilon]$, preventing any single update from moving the policy too far from the reference,$M_{t+1}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$is the recursive importance-sampling product from turns$t+1$through$T$, initialized as$M_{T+1} = \hat{A}^{\hat{\pi}^k}(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$(Equation 7) and updated after each turn's optimization (Equation 8).
What this objective computes. For each sample in the turn-$t$ pool, it computes the probability ratio $r_t(\boldsymbol{\theta})$ of the turn-$t$ action under the new vs. old policy. This ratio is multiplied by $M_{t+1}$, which already incorporates importance-sampling corrections from all subsequent turns. The $\min$ and $\text{clip}$ operations implement the standard PPO conservative update: if the ratio moves outside $[1 - \epsilon, 1 + \epsilon]$, the objective is clipped to prevent large policy changes. The gradient of this objective with respect to $\boldsymbol{\theta}$ is computed and used for parameter updates.
Why the $M_{t+1}$ factor replaces the advantage. In standard PPO, the objective is $\min(r_t(\theta) \hat{A}_t, \text{clip}(r_t(\theta), 1 \pm \epsilon) \hat{A}_t)$ where $\hat{A}_t$ is the advantage for that specific state-action pair. In SeeUPO, $M_{t+1}$ plays the role of the advantage, but it is not just the turn-$t$ advantage—it is the global advantage multiplied by the importance-sampling ratios of all already-updated subsequent turns. This encodes the sequential update structure: when updating turn $t$, the "advantage" used is the global advantage filtered through the lens of how subsequent turns' policies have changed. This implements the expectation structure in Equation 4, where the global advantage is decomposed into turn-specific contributions.
Recursive $M_t$ Computation (Equations 7-8)
The quantity $M_t(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})$ is the operational mechanism that propagates sequential update information backward through the turns. It is initialized and updated as follows:
Initialization (Equation 7):
For the terminal turn $T$ (the first to be updated in reverse order), $M_{T+1}$ is simply the global advantage estimate. There are no subsequent turns, so no importance-sampling corrections are needed yet.
Recursive update (Equation 8): After updating turn $t$'s policy to $\boldsymbol{\pi}_{\boldsymbol{\theta}^{k+1}_t}$:
where $\boldsymbol{\theta}^{k+1}_t$ are the parameters after optimizing turn $t$, and $\boldsymbol{\theta}^k$ are the parameters at the start of iteration $k$ (the reference policy used for sampling).
What this recursion computes. $M_t$ is the product of the global advantage and the importance-sampling ratios of all turns from $t$ through $T$ (they have all been updated by this point). Explicitly expanding the recursion:
This matches the structure of Equation 4: when updating turn $t-1$ (the next turn in reverse order), $M_t$ provides exactly the factor $\frac{\hat{\pi}^{k+1}_{t:T}}{\hat{\pi}^k_{t:T}} \cdot \hat{A}^{\hat{\pi}^k}$, which multiplies the turn-specific ratio $(\frac{\bar{\pi}_{t-1}}{\hat{\pi}^k_{t-1}} - 1)$ to give the local advantage estimate.
Why recursion rather than direct computation. The recursive update is efficient: each $M_t$ is computed from $M_{t+1}$ with a single multiplication per trajectory, rather than recomputing the product over all subsequent turns from scratch. Since parameter sharing means $\boldsymbol{\theta}^{k+1}_t$ is the current state of the shared parameters after turn $t$'s update, the ratios for each turn are computed as the updates proceed, naturally accumulating the product.
Turn-Oriented Batch Construction (Figure 3)
Figure 3 illustrates the batch construction approach, which is a key architectural design choice distinguishing SeeUPO from other methods. The figure shows an example with maximum $T = 3$ turns, using the React + Reasoning-Augmented Template paradigm.
Vanilla approach (top of figure): Constructs batches by concatenating entire trajectories or by slicing turns from different trajectories and concatenating them. This intermixes samples from different turn positions within the same batch, requiring the policy update to handle heterogeneous contexts (turn-1 samples, turn-2 samples, etc.) simultaneously. This is what methods like PPO, GRPO, and GSPO effectively do.
SeeUPO approach (bottom of figure): Organizes samples into turn-specific pools. All turn-1 actions from all trajectories go into pool $\mathcal{D}_1$, all turn-2 actions go into $\mathcal{D}_2$, and so on. The conditioning context $(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$ is preserved with each sample. For trajectories shorter than $T$ turns, placeholder (no-op) samples are introduced. The figure shows "Sample 6" as a placeholder in the turn-2 and turn-3 pools—it contributes a "do nothing" action that doesn't affect the policy gradient (its importance ratio is 1, and its advantage is 0).
Why this approach is necessary for sequential updates. The sequential update mechanism requires that when updating turn $t$, the algorithm has access to all samples from that turn position. If samples were intermixed (as in the vanilla approach), the update for turn $t$ would need to first separate turn-$t$ samples from others, then update, then compute $M_t$ for use in turn $t-1$'s update. Turn-oriented batching pre-organizes the data so that each sequential update step directly accesses its relevant pool without additional filtering.
GRAE-Based Advantage Estimation with Batch Normalization
SeeUPO's advantage estimation operates in the bandit setting, where the global advantage function has a particularly simple form (Equation 5, Section 4.1):
Practical GRAE implementation (Equation 9). In practice, the expectation is estimated using the group mean over $G$ trajectories sampled from the same initial state:
where $\bar{r}(\boldsymbol{s}_0) = \frac{1}{G}\sum_{i=1}^G r(\boldsymbol{s}_0, \boldsymbol{a}^{(i)}_{1:T})$ is the Monte Carlo estimator of $V^{\hat{\pi}^k}(\boldsymbol{s}_0) = \mathbb{E}_{\boldsymbol{a}_{1:T} \sim \hat{\pi}^k}[r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})]$.
What this estimator computes. For each trajectory in the group of $G$ samples from the same initial state, subtract the group's average reward from the trajectory's actual reward. Trajectories with above-average reward get positive advantages (the policy should be encouraged toward these actions); below-average trajectories get negative advantages (the policy should be discouraged). The magnitude of the advantage reflects how much better or worse the trajectory was compared to the current policy's expected performance.
Why this estimator is unbiased in the bandit setting (Appendix H, Lemma 6). In a contextual bandit, there are no state transitions—each agent makes exactly one decision given the initial state and history. The true advantage function is:
where $V^{\boldsymbol{\pi}}_{\text{Bandit}}(\boldsymbol{s}_0) = \mathbb{E}_{\boldsymbol{a}_{1:T} \sim \boldsymbol{\pi}}[r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})]$. GRAE estimates this by replacing $V^{\boldsymbol{\pi}}_{\text{Bandit}}(\boldsymbol{s}_0)$ with the group mean $\bar{r}(\boldsymbol{s}_0)$. As $G \to \infty$, $\bar{r}(\boldsymbol{s}_0) \to V^{\boldsymbol{\pi}}_{\text{Bandit}}(\boldsymbol{s}_0)$ by the law of large numbers, so $\hat{A}^{\text{GRAE}} \to A^{\boldsymbol{\pi}}_{\text{Bandit}}$—the estimator is consistent and unbiased.
The critical contrast with MDPs is that there is no structural bias $V(\boldsymbol{s}_t) - V(\boldsymbol{s}_0)$ because there is only one state per agent. The multi-agent decomposition transforms the multi-turn MDP into multiple single-decision bandit problems, each conditioned on a different history, and within each agent's bandit, GRAE is unbiased.
Batch-level normalization. After computing raw advantage estimates $\hat{A}^{\hat{\pi}^k}$, the algorithm applies batch-level normalization for numerical stability:
where $\mu_{\mathcal{B}}$ is the mean advantage over the entire batch and $\sigma_{\mathcal{B}}$ is the batch standard deviation.
Why batch-level normalization preserves convergence (Appendix H.3.3). The key insight is that batch-level normalization applies constants ($\mu_{\mathcal{B}}$ and $\sigma_{\mathcal{B}}$) that are identical for all samples in the batch and do not depend on the candidate policy $\bar{\pi}_t$ being optimized. The argmax of the policy optimization problem is invariant to adding/subtracting constants and multiplying by positive constants:
Since the argmax is unchanged, the drift functional $\mathfrak{D}$ remains completely unaffected—it has the same properties (non-negativity, zero gradient) as without normalization. This is in fundamental contrast to group-level normalization (as used in GSPO and GRPO), which applies state-dependent scaling factors $\delta(\boldsymbol{s})$ that vary across queries. The paper proves (Appendix H.3, Theorem 9) that group-level normalization breaks convergence guarantees unless $\delta(\boldsymbol{s}) \equiv 1$ identically for all states—a condition that essentially never holds in practice because reward variance differs across tasks.
Practical configuration. The training configuration (Section 5.1.3) specifies: learning rate $1 \times 10^{-6}$ for the actor network, batch size 32, clipping parameter $\epsilon = 0.2$, KL penalty coefficient 0.002, and $G = 8$ rollouts per instance during training. Training runs for 75 epochs on AppWorld and 50 epochs on BFCL v4. The React + Reasoning-Augmented Template paradigm (Zhai et al., 2025) is used for both base models.
Computational efficiency (Table 3). SeeUPO's sequential update mechanism incurs additional training time compared to other critic-free methods: approximately 1.5× the average training step time of GRPO and GSPO (e.g., 4303.71s vs. 2802.99s for Qwen3-14B averaged across benchmarks). However, it uses the same GPU resources as other critic-free methods (8 GPUs), compared to PPO's 16 GPUs (2 clusters). The paper argues this overhead is acceptable given the substantially faster convergence and higher final performance.
Global Optimality Guarantee (Appendix B, Theorem 2)
The paper establishes SeeUPO's convergence to global optimality (not just Nash equilibrium, which HAML guarantees for general cooperative games) through Theorem 2 in Appendix B. This is a stronger result enabled by the specific structure of the multi-turn bandit setting.
Theorem statement (simplified). Consider a multi-turn contextual bandit with execution order $1 \to 2 \to \cdots \to T$, bounded rewards $|r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T})| \leq R_{\max}$, valid drift functionals and neighborhood operators, and accurately estimated advantage functions. Under the reverse update order ($T \to T-1 \to \cdots \to 1$), the policy sequence generated by the HAML update rule (Equation 22) converges: (1) the value sequence converges to some limit $V(\boldsymbol{s}_0)$, and (2) any limit point $\bar{\boldsymbol{\pi}}$ of the policy sequence is globally optimal: $J(\bar{\boldsymbol{\pi}}) = J^* = \max_{\hat{\boldsymbol{\pi}}} J(\hat{\boldsymbol{\pi}})$.
Proof structure (5 steps). The proof, adapted from the HAML framework and the dropping-the-drift argument in Mirror Learning (Grudzien et al., 2022), proceeds as follows:
Step 1 (Value Convergence). By Theorem 1 (the Fundamental Theorem of HAML, Appendix A.2), the policy sequence satisfies monotonic improvement: $J(\hat{\boldsymbol{\pi}}^{k+1}) \geq J(\hat{\boldsymbol{\pi}}^k)$ for all $k$. Since rewards are bounded by $R_{\max}$, the value sequence $\{V^{\hat{\pi}^k}(\boldsymbol{s}_0)\}$ is monotonically non-decreasing and bounded above, hence converges to some limit $V(\boldsymbol{s}_0)$. This step does not depend on the update order—any valid HAML instantiation provides monotonic improvement.
Step 2 (Characterization of Limit Points). By compactness of the policy space and the Bolzano-Weierstrass theorem, the policy sequence has at least one limit point $\bar{\boldsymbol{\pi}}$. Using Berge's Maximum Theorem (which ensures that the argmax of a continuous optimization problem converges as the problem parameters converge), the paper shows that at any limit point, each turn's policy $\bar{\pi}_t$ satisfies a fixed-point condition: it maximizes the HAML mirror operator given the fixed subsequent policies $\bar{\boldsymbol{\pi}}_{t+1:T}$. This is proved by contradiction: if some candidate policy $\pi' \neq \bar{\pi}_t$ achieved a strictly higher mirror objective, then by the monotonic improvement property, the joint policy with $\pi'$ substituted for $\bar{\pi}_t$ would achieve strictly higher value than $V(\boldsymbol{s}_0)$, contradicting that $V(\boldsymbol{s}_0)$ is the limit of the value sequence.
Step 3 (Turn $T$ Global Optimality via Dropping the Drift). For the terminal turn $T$, the fixed-point condition becomes (simplified):
The paper applies the dropping-the-drift argument: suppose there exists some action $\boldsymbol{a}^*_T$ with strictly higher reward than the expected reward under $\bar{\pi}_T$. The expected reward $\mathbb{E}_{\boldsymbol{a}_T \sim \pi_T}[r]$ is an affine function of $\pi_T(\cdot \mid \boldsymbol{s}_0, \boldsymbol{a}_{1:T-1})$, so its Gâteaux derivative in the direction of the Dirac delta at $\boldsymbol{a}^*_T$ is strictly positive at $\bar{\pi}_T$. By the zero gradient property of the drift functional, the derivative of the drift in that direction is zero. Therefore, the derivative of the full HAML objective (expected reward minus drift) is strictly positive, meaning a small step toward $\boldsymbol{a}^*_T$ would increase the objective—contradicting that $\bar{\pi}_T$ is the argmax. Hence, no such $\boldsymbol{a}^*_T$ exists, and $\bar{\pi}_T$ is the globally optimal policy for turn $T$.
Step 4 (Backward Induction to Earlier Turns). With $\bar{\pi}_T = \pi^*_T$ established as the base case, the proof proceeds by induction backward through the turns. The inductive hypothesis: assume $\bar{\pi}_{t+1:T} = \pi^*_{t+1:T}$. This means for any history $(\boldsymbol{s}_0, \boldsymbol{a}_{1:t})$, the continuation value under $\bar{\pi}_{t+1:T}$ equals the optimal continuation value $V^*(\boldsymbol{s}_0, \boldsymbol{a}_{1:t})$ (Definition 1, Appendix B). The fixed-point condition for turn $t$ then becomes:
Applying the dropping-the-drift argument again: if there were an action $\boldsymbol{a}^*_t$ with $V^*(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1}, \boldsymbol{a}^*_t) > \mathbb{E}_{\boldsymbol{a}_t \sim \bar{\pi}_t}[V^*(\boldsymbol{s}_0, \boldsymbol{a}_{1:t})]$, then a small step toward $\boldsymbol{a}^*_t$ would increase the HAML objective (the derivative of the expected $V^*$ is positive, the derivative of the drift is zero), contradicting optimality. Therefore, $\bar{\pi}_t = \pi^*_t$. By induction from $t = T$ down to $t = 1$, $\bar{\boldsymbol{\pi}} = \boldsymbol{\pi}^*$.
Step 5 (Conclusion). Since any limit point $\bar{\boldsymbol{\pi}}$ of the policy sequence is globally optimal, $J(\bar{\boldsymbol{\pi}}) = J^*$, establishing convergence to the global optimum.
Why reverse order is essential for global optimality (not just Nash). The proof critically depends on the inductive hypothesis $\bar{\pi}_{t+1:T} = \pi^*_{t+1:T}$. Under reverse order, when updating turn $t$, all subsequent turns have already been updated using the same fixed-point condition, so the inductive hypothesis holds naturally. Under forward order, when updating turn $t$, subsequent turns $t+1, \ldots, T$ would still be at the old policies, so the continuation value would be $V^{\hat{\pi}^k}$ rather than $V^*$. The fixed-point condition would guarantee optimality with respect to the old continuation value, not the optimal one—the policy might be conditionally optimal given suboptimal subsequent behavior but not globally optimal. Under random order, the logical dependency structure is completely disrupted because earlier turns might be updated after later turns in some iterations but before them in others, preventing the consistent backward induction.
What this guarantee means in practice. The theorem establishes that SeeUPO's training process will, in the limit of infinite iterations and under the stated assumptions (accurate advantage estimation, valid drift/neighborhood operators, bounded rewards, compact policy space), converge to a policy that is globally optimal for the multi-turn task. This does not mean the practical algorithm with finite iterations, finite samples, and neural network approximation achieves exact global optimality—but it means the algorithm has the correct asymptotic behavior, unlike GRAE-PPU methods which provably lack even this property in MDPs. This theoretical soundness manifests empirically as training stability (no catastrophic collapse) and monotonic performance improvement (Figure 4).
Assumptions and their validity in the practical instantiation. The theorem assumes accurate advantage estimation. In SeeUPPO-GRAE, GRAE provides unbiased estimates in the bandit setting (Appendix H, Lemma 6). The PPO-style clipping mechanism has been proven to correspond to a valid drift functional and neighborhood operator within the Mirror Learning framework (Grudzien et al., 2022), and HAPPO (Zhong et al., 2024) established that PPU-style sequential updates constitute a valid HAML instantiation. Therefore, the practical algorithm satisfies the theorem's conditions, providing theoretical grounding for the empirical results.
4. Key Insights and Innovations
Innovation 1: A Diagnostic Taxonomy That Identifies the Fundamental Trade-Off Between Critic-Free Operation and Convergence Guarantees
The paper's most distinctive intellectual contribution is not SeeUPO itself but the diagnostic framework it develops in Section 3. By decomposing every mainstream backbone RL algorithm into two independent design axes—advantage estimation (GAE vs. GRAE) and policy update mechanism (REINFORCE vs. PPU)—the paper reveals a structural incompatibility that had been invisible to the field. Prior work treated these algorithms as monolithic entities (PPO, GRPO, RLOO, GSPO), evaluated them empirically, and drew conclusions about which "worked better." The paper's taxonomy shows that this monolithic view obscures the real problem: critic-free operation and convergence guarantees are mutually exclusive in multi-turn settings under existing algorithm designs, and the choice between them is forced by the interaction between the two axes, not by any single component.
This is fundamentally a theoretical diagnostic contribution, not an algorithmic one. The field knew that GRPO sometimes exhibited training instability and that PPO was computationally expensive, but these were treated as separate practical concerns rather than symptoms of a single underlying conflict. The taxonomy reveals why: GRAE introduces structural bias $V(s_t) - V(s_0)$ that is harmless for vanilla policy gradients (baseline invariance makes it cancel) but catastrophic for PPU's clipped objective (the clipping direction depends on the sign of the advantage, which the bias can flip). This explains the contradictory empirical picture—GRPO works on single-turn reasoning where $V(s_t) = V(s_0)$ (the structural bias vanishes), but collapses on multi-turn tasks where intermediate values diverge from the initial value.
The significance goes beyond this specific finding. The taxonomy provides a generative framework: any future algorithm combining a new advantage estimator with a new update mechanism can be analyzed by asking whether the estimator produces bias that interacts destructively with the update mechanism's non-linearities. This converts ad-hoc empirical trial-and-error into principled analysis. The paper's Table 1 and the corresponding appendices (C-H) essentially provide a convergence property lookup table for the Cartesian product of design choices, which is a reusable intellectual tool for the field.
Evidence. The taxonomy's explanatory power is validated by the diversity of empirical failures it correctly predicts: GRPO and GSPO collapse on Qwen2.5-14B + AppWorld (Figure 4c), while PPO remains stable but expensive; GSPO's additional group-variance normalization introduces a second, independent violation of convergence conditions (Appendix H.3, Theorem 9); and RLOO's convergence under undiscounted objectives explains why it works in some settings but not others. The taxonomy provides a unified causal account for all of these without resorting to post-hoc speculation.
Innovation 2: Reformulating Multi-Turn Interaction as Sequentially-Executed Multi-Agent Bandits—A Structural Trick That Eliminates the Bias at Its Source
While Section 3 covers the mechanism of multi-agent modeling in detail, the conceptual innovation here is the diagnostic insight that the structural bias $V(s_t) - V(s_0)$ is an artifact of the modeling choice, not an intrinsic property of multi-turn interaction. The dominant modeling paradigm in LLM agent training—inherited from classical RL—treats multi-turn trajectories as MDPs where each turn is a timestep, the state is the conversation history, and the reward arrives at the end. Under this modeling, GRAE's baseline $\bar{r}$ estimates $V(s_0)$ but the true advantage requires $V(s_t)$ at each intermediate state; the structural bias is an unavoidable consequence of the MDP formulation itself.
SeeUPO's multi-agent bandit reformulation is conceptually distinctive not because it's technically complex (it's straightforward: each turn becomes a virtual agent making one decision), but because it recognizes that the temporal structure of multi-turn interaction can be captured through the ordering among agents rather than through state transitions. By eliminating state transitions entirely, the model eliminates the very concept of $V(s_t)$ for intermediate $t$—there is only $V(s_0)$, which is exactly what GRAE estimates. The bias doesn't need to be corrected or mitigated; it ceases to exist because the modeling no longer generates it.
This is a reframing contribution rather than a technical one. The field's default assumption was that multi-turn tasks are MDPs—this is how RL textbooks define sequential decision-making, and it's how PPO, GRPO, and their variants were originally conceived. SeeUPO challenges this assumption by showing that for the specific purpose of policy optimization (as opposed to value estimation or planning), the MDP formulation is not just unnecessary but actively harmful: it introduces a bias that must then be fought with critic networks, trust regions, or other mechanisms. The multi-agent bandit formulation is a more natural fit for the actual structure of the optimization problem (train all turns jointly toward a shared terminal reward), even if it's less natural for describing the environment's dynamics.
Comparison to prior work. Prior multi-agent approaches to multi-turn tasks (e.g., HAML's application to general cooperative games) required random update orders to guarantee Nash equilibrium convergence. SeeUPO's insight that the fixed sequential execution order enables backward induction—and therefore global optimality rather than just Nash—is possible only because the multi-agent reformulation makes the execution order explicit and exploitable. In the MDP formulation, the turns are just timesteps in a single agent's trajectory; there is no natural notion of "updating turns in reverse order" because there are no separate turn policies to update. The multi-agent abstraction creates the degrees of freedom that the reverse-order update mechanism then exploits.
Evidence. The global optimality guarantee (Theorem 2, Appendix B) depends on the bandit formulation: the dropping-the-drift argument requires that the advantage function degenerates to $r(\boldsymbol{s}_0, \boldsymbol{a}_{1:T}) - V(\boldsymbol{s}_0)$ (Equation 5), which is only true when there are no intermediate state values to account for. The empirical validation in Table 4 confirms that forward and random update orders—which would still provide monotonic improvement but not global optimality—significantly underperform reverse order (60.80% avg@4 for reverse vs. 55.20% for natural vs. 42.29% for random on Qwen3-14B), consistent with the theoretical prediction.
Innovation 3: Verifier Over-Optimization as a First-Class Failure Mode That Limits Even Convergent Algorithms
While Section 3 covers the mechanism of PPO's clipping interacting with GRAE's bias, the deeper conceptual insight is that convergence guarantees are not just about asymptotic correctness—they protect against a specific, diagnosable failure mode that manifests as catastrophic training collapse. The paper doesn't just prove that GRAE-PPU lacks convergence guarantees; it provides an explicit, mechanistic account of what goes wrong during training when those guarantees are absent.
The account (Appendix G, Theorem 7, Part 4) goes beyond "the algorithm might not converge" to show exactly how a single PPU update can increase the probability of actions with truly negative advantage. The mechanism: GRAE's structural bias $\Delta(s_t)$ can flip the sign of the advantage estimate (a truly negative advantage of $-5$ plus a structural bias of $+10$ yields $+5$). PPU's clipping direction depends on the sign of the estimate: positive-sign estimates trigger clipping at the upper bound ($1 + \epsilon$), pushing probability upward; negative-sign estimates trigger clipping at the lower bound ($1 - \epsilon$), pushing probability downward. When the sign is flipped, the clipping constraint enforces the wrong direction—the algorithm believes it's being conservative (staying within the trust region) while actually moving in the direction that degrades performance.
This is analogous to—but distinct from—the well-known verifier over-optimization problem in reward-model-guided RLHF, where policies learn to exploit imperfections in learned reward models. The difference is that here, the "verifier" is the advantage estimator, and the "over-optimization" is not gradual exploitation but abrupt sign-flip-induced policy degradation. The connection to prior work is the broader theme that non-linear policy optimization objectives are fragile to systematic errors in the signal they optimize against. PPU's clipping, designed as a conservative mechanism to prevent destructive large updates, becomes destructive when the signal it's being conservative about has the wrong sign.
Significance beyond this paper. This diagnostic insight has implications for algorithm design beyond multi-turn agentic RL. Any algorithm that conditions its update direction on the sign of an estimated quantity—PPU's clipping on advantage sign, but also potentially trust-region methods, natural gradient methods with learned metrics, or any optimization with asymmetric constraints—is vulnerable to this class of failure when the estimation error is systematic (biased) rather than zero-mean (noisy). The paper provides a template for analyzing such interactions: derive the drift function in the Mirror Learning framework, check whether the structural bias survives at the reference policy, and verify the non-negativity and zero-at-origin properties.
Evidence. The catastrophic training collapses in Figure 4(c) (GRPO and GSPO on Qwen2.5-14B + AppWorld) are not gradual degradation—they are abrupt drops consistent with the sign-flip mechanism. In contrast, SeeUPO shows monotonic improvement throughout training, consistent with the theoretical prediction that its bandit formulation prevents structural bias from arising. The normalization experiment (Table 5) provides additional evidence: group-level normalization (which introduces state-dependent scaling, violating the drift functional properties as shown in Theorem 9) achieves 60.28% avg@4 but without theoretical guarantees, while batch-level normalization achieves 60.80% avg@4 with preserved convergence properties—the empirical difference is small, but the theoretical difference (guaranteed vs. unguaranteed stability) is fundamental.
Innovation 4: Batch-Level Normalization as a Theoretically-Sound Alternative to Group-Level Variance Normalization
This is a smaller but practically significant innovation. The dominant trend in critic-free LLM RL—starting with GRPO and carried through GSPO—has been to normalize advantages at the group level: divide each advantage by the standard deviation of rewards within the group of samples from the same query. This was motivated by training stability concerns (un-normalized advantages can have very different scales across queries) but, as the paper proves (Appendix H.3, Theorem 9), it breaks the drift functional properties required for Mirror Learning convergence unless the group variance is identically 1 for all queries.
The conceptual contribution is recognizing that the argmax-invariance property of the policy optimization objective can be exploited to achieve numerical stability without sacrificing theoretical correctness. Batch-level normalization applies constants ($\mu_{\mathcal{B}}$ and $\sigma_{\mathcal{B}}$) that are identical for all samples in the update batch. Since the argmax is invariant to adding/subtracting constants and multiplying by positive constants, the normalized and un-normalized objectives have the same optimizer. Consequently, the drift functional—which is derived from the structure of the optimization objective, not from the specific values of the advantages—remains completely unchanged. The normalization provides numerical stability (preventing gradient scales from varying wildly across batches) while preserving exactly the same theoretical guarantees as using raw advantages.
This is an elegance contribution: a simpler solution that achieves the practical goal (stable training) without the theoretical compromise. The prior approach (group-level normalization) solved the stability problem by modifying the objective in a way that introduced state-dependent scaling factors, which then required complicated analysis to understand when they did or didn't break convergence. The batch-normalization approach solves the same problem by operating at a level where the optimization is invariant, making the theoretical analysis trivial—no new proofs needed, no edge cases to worry about.
Evidence. Table 5 shows that batch-level normalization (60.80% avg@4) performs comparably to group-level normalization (60.28% avg@4) and substantially better than no normalization (47.08% avg@4). The key point is not that batch normalization is empirically superior to group normalization (the difference is small) but that it achieves comparable empirical performance while preserving the theoretical guarantees that group normalization breaks. The invariance argument in Appendix H.3.3 provides the formal justification; Table 5 provides the empirical validation that the theoretical correctness doesn't come at a practical cost.
5. Experimental Analysis
Evaluation Methodology
-
Dataset. The paper evaluates on two multi-turn agentic benchmarks: AppWorld (Trivedi et al., 2024), a controllable world of apps and people for benchmarking interactive coding agents with programmatic evaluation through task goal completion tests; and BFCL v4 (the Berkeley Function Calling Leaderboard multi-turn benchmark, Patil et al., 2025), which uses state-based checks and response-based checks with force-terminated runs counted as incorrect. Trajectories are truncated at a maximum of 10 steps. The multi-turn nature of both benchmarks—exposing multi-step API/tool interactions under sparse terminal rewards—makes them ideal testbeds for evaluating multi-turn agent training algorithms where the paper's theoretical concerns about convergence are most salient.
-
Base model(s). Two model families are used: Qwen2.5-14B-Instruct (Yang et al., 2025b) and Qwen3-14B (Yang et al., 2025a). These serve as the agent's policy network. The dual-model evaluation is deliberate: Qwen3-14B has "built-in reasoning capabilities" (per the paper, Section 5.2.1) representing a stronger starting point, while Qwen2.5-14B is a weaker model where RL training must induce larger behavioral changes. This span allows the paper to test whether SeeUPO's advantages are robust to base model capability—a crucial dimension since training stability problems are often most severe when the model must learn substantially new behaviors.
-
Metrics. Two metrics are reported: avg@4 (averaging task completion scores over 4 independent rollouts per instance) and pass@4 (the success rate when sampling 4 independent rollouts per instance—an instance "passes" if at least one of the 4 rollouts succeeds). These are standard in the LLM agent evaluation literature, capturing both expected performance (avg@4) and the ability to find a correct solution with multiple attempts (pass@4). The combination distinguishes between methods that consistently produce correct solutions versus those that occasionally succeed through lucky sampling. All values are reported as percentages.
-
Baselines. Three backbone RL algorithms are compared, each representing a distinct point in the paper's design taxonomy (Table 1): PPO (GAE + PPU, token-level, critic-dependent with convergence guarantees in multi-turn settings under perfect value function approximation—Appendix F, Theorem 6); GRPO (GRAE + PPU, token-level, critic-free but with structural bias breaking monotonic improvement in MDPs—Appendix G); and GSPO (GRAE + PPU, sequence-level, critic-free, with the additional group-variance normalization that independently breaks convergence guarantees—Appendix H.3). These three baselines span the dominant approaches in LLM agent training: the only algorithm with multi-turn convergence guarantees (PPO), the most widely-adopted critic-free method at the token level (GRPO), and the state-of-the-art sequence-level variant (GSPO). The base models without any RL training are also reported as a reference point (e.g., Qwen2.5-14B at 15.16% avg@4, 21.39% pass@4; Qwen3-14B at 30.22%, 41.05%).
-
Generation budget / compute accounting. Training uses 8 rollouts per instance (
$G = 8$), batch size 32, learning rate$1 \times 10^{-6}$for the actor network, clipping parameter$\epsilon = 0.2$, KL penalty coefficient 0.002. Models train for 75 epochs on AppWorld and 50 epochs on BFCL v4. Fairness in sample utilization is enforced: "all algorithms use the same number of samples, and samples are utilized the same number of times within each update step" (Section 5.1.3). Computational efficiency is separately measured via Training Step Time (seconds per training step) and GPU count (number of H20 96GB GPUs required), with PPO using 2 clusters (16 GPUs) and GRPO, GSPO, and SeeUPO each using 1 cluster (8 GPUs). This acknowledges that PPO's critic network doubles its computational footprint—a practical cost that the critic-free methods avoid but at the expense (the paper argues) of convergence guarantees. -
Cross-validation / statistical protocol. There is no formal cross-validation protocol for the main results—the paper reports final performance after training for the full epoch budget (75 for AppWorld, 50 for BFCL v4). Training curves (Figures 1, 4, 5) show the trajectory of performance over epochs, providing a qualitative picture of stability and convergence speed. The additional comparative experiments on update order (Section 5.3.1) and normalization strategy (Section 5.3.2) use Qwen3-14B on both benchmarks as the default configuration, testing one variable at a time. The paper does not report confidence intervals, standard errors, or statistical significance tests, which is a notable limitation for interpreting whether observed differences (particularly the smaller ones in the normalization experiment) are statistically reliable.
Main Quantitative Results
The results are organized into three categories: overall performance comparison against baselines (Section 5.2.1), training dynamics analysis (stability and convergence behavior visible in learning curves), and computational efficiency (Section 5.2.2). I present them together since they are reported in the same tables and figures.
Overall Performance and Training Stability
Table 2 reports the headline performance numbers. On Qwen3-14B, SeeUPO achieves 60.80% avg@4 and 72.85% pass@4 (averaged across AppWorld and BFCL v4). This represents relative improvements over baselines ranging from 43.3% (vs. GRPO's 42.43% avg@4) to 54.6% (vs. GSPO's 39.32% avg@4). On the stronger base model, PPO achieves 39.42% avg@4 and 53.20% pass@4—substantially below SeeUPO despite having the theoretical convergence guarantees that the other baselines lack. On Qwen2.5-14B, SeeUPO achieves 53.07% avg@4 and 63.59% pass@4, with relative improvements ranging from 24.1% (vs. PPO's 42.77%) to 41.9% (vs. GSPO's 37.44%). The gap between SeeUPO and baselines is larger on Qwen3-14B than on Qwen2.5-14B, consistent with the interpretation that a stronger base model provides more "capability to amplify" through better test-time training strategies.
Per-benchmark breakdown (Table 2) reveals substantial heterogeneity. On AppWorld with Qwen3-14B, SeeUPO achieves 63.60% avg@4 and 80.70% pass@4, compared to PPO's 35.09% / 54.39%, GRPO's 40.35% / 57.89%, and GSPO's 32.89% / 52.63%. On BFCL v4 with the same model, SeeUPO achieves 58.00% avg@4 and 65.00% pass@4, compared to PPO's 43.75% / 52.00%, GRPO's 44.50% / 53.00%, and GSPO's 45.75% / 55.00%. The gap is consistently larger on AppWorld than on BFCL v4 across all model-baseline combinations—AppWorld appears to be the more challenging benchmark where training instability is more pronounced. The BFCL v4 results show a more compressed range (baselines are closer to each other), with PPO, GRPO, and GSPO all in the 43–51% range for avg@4 on Qwen2.5-14B.
Base model without RL provides a lower bound: Qwen2.5-14B achieves only 15.16% avg@4 and 21.39% pass@4; Qwen3-14B achieves 30.22% and 41.05%. All RL methods substantially improve over these zero-shot baselines, but the improvement is far from uniform—on Qwen2.5-14B + AppWorld, GSPO actually underperforms relative to what one might expect given its performance on other configurations (24.12% avg@4, though this is still above the 4.83% base rate).
Training curves (Figure 4) reveal the stability dimension that the final-performance table cannot capture. The four subplots show training success rate (y-axis) against epochs (x-axis) for: (a) Qwen3-14B on AppWorld, (b) Qwen3-14B on BFCL v4, (c) Qwen2.5-14B on AppWorld, (d) Qwen2.5-14B on BFCL v4. The most striking pattern is in subplot (c)—Qwen2.5-14B + AppWorld—where both GRPO and GSPO exhibit catastrophic performance collapse. GRPO rises from near-zero to approximately 35% success rate around epoch 20, then plummets to near-zero by epoch 40. GSPO shows a similar trajectory with an earlier peak. PPO and SeeUPO, in contrast, show monotonic or near-monotonic improvement throughout training, with SeeUPO achieving the highest final performance (approximately 50% by epoch 75) and PPO reaching approximately 40%.
In subplot (a)—Qwen3-14B + AppWorld—the pattern is less catastrophic but still informative. SeeUPO rises steadily and maintains a clear lead (reaching approximately 63% by epoch 75), while PPO, GRPO, and GSPO all converge to similar final performance (roughly 35–40%) but with visibly noisier training curves. GRPO shows a slight dip around epoch 60 before recovering. In subplot (b)—Qwen3-14B + BFCL v4—SeeUPO maintains a lead (reaching approximately 58%), with baselines clustered around 44–46%. In subplot (d)—Qwen2.5-14B + BFCL v4—the curves are more compressed, with SeeUPO reaching approximately 55% and baselines around 50–51%, but SeeUPO's advantage, while smaller, is consistent across epochs.
Figure 1 provides an alternative visualization of the same data as bar charts: subplots (a)–(b) show training curves (same as Figure 4a–b), while (c)–(f) show test curves split by benchmark and model. The test curves mirror the training dynamics, confirming that SeeUPO's superior training performance transfers to held-out evaluation. The gap between SeeUPO and baselines in the test curves is visually large for Qwen3-14B on both benchmarks and narrower (but still present) for Qwen2.5-14B.
Computational Efficiency (Table 3)
The efficiency analysis is necessary context for interpreting the performance gains: do they come at an unacceptable computational cost? Table 3 reports Training Step Time (seconds per training step) and GPU count for each method on each model-benchmark combination.
On Qwen3-14B (averaged across benchmarks): PPO takes 2790.67 seconds per step using 16 GPUs; GRPO takes 2802.99 seconds using 8 GPUs; GSPO takes 2888.71 seconds using 8 GPUs; SeeUPO takes 4303.71 seconds using 8 GPUs. SeeUPO is approximately 1.54× slower than the critic-free methods (GRPO, GSPO) and 1.54× slower than PPO per step, but uses half the GPUs of PPO (8 vs. 16). The multiplier factors (shown as red superscripts in the table) indicate SeeUPO's computation time relative to each baseline: 1.54× vs. GRPO, 1.49× vs. GSPO, 1.54× vs. PPO (averaged).
On Qwen2.5-14B: PPO takes 2814.81 seconds (16 GPUs), GRPO 2558.66 seconds (8 GPUs), GSPO 2364.85 seconds (8 GPUs), SeeUPO 3894.89 seconds (8 GPUs). Multipliers: 1.38× vs. PPO, 1.52× vs. GRPO, 1.65× vs. GSPO.
The paper contextualizes this overhead (Section 5.2.2): "with approximately 1.5× the training time, SeeUPO achieves notably faster convergence speed and reaches final performance levels far exceeding those of other algorithms." The claim of "faster convergence speed" is somewhat ambiguous—Figure 4 shows SeeUPO generally reaching higher performance at every epoch, but the per-epoch wall-clock time is longer. The more precise statement is: for a given amount of wall-clock time, SeeUPO may or may not outperform baselines depending on when the comparison is made; but for a given number of training steps (samples processed), SeeUPO consistently achieves higher performance.
Per-benchmark variation: On AppWorld with Qwen3-14B, SeeUPO takes 5462.35 seconds per step vs. GRPO's 2938.37 (1.86× multiplier)—the largest overhead observed. On BFCL v4 with Qwen3-14B, SeeUPO takes 3145.06 seconds vs. PPO's 2579.04 (1.22× multiplier)—the smallest overhead. The AppWorld overhead is larger because AppWorld trajectories are presumably longer (more turns means more sequential update steps per iteration), amplifying the cost of the turn-by-turn update mechanism.
Ablation Studies and Robustness Checks
All ablation experiments use Qwen3-14B on both AppWorld and BFCL v4. The paper investigates two design dimensions: update order (Section 5.3.1) and normalization strategy (Section 5.3.2).
Update order (Table 4, Figure 5): The paper compares three orderings for the sequential policy update—natural order (turn 1 → turn 2 → … → turn $T$), reverse order (turn $T$ → $T-1$ → … → turn 1, the default), and random order (randomly sampled permutation at each iteration). Reverse order achieves the best performance: 60.80% avg@4 and 72.85% pass@4 (averaged across benchmarks). Natural order achieves 55.20% avg@4 and 67.22% pass@4—competitive but clearly worse. Random order performs substantially worse at 42.29% avg@4 and 53.31% pass@4, with a particularly dramatic gap on AppWorld (33.33% avg@4 and 45.61% pass@4 for random vs. 63.60% and 80.70% for reverse). The random order's poor performance on AppWorld is notable: while random orders have been proven effective in synchronous multi-agent RL (Zhong et al., 2024), they fail in this sequential setting because "random order completely disrupts the logical chain inherent to the execution sequence" (Section 5.3.1), preventing the backward induction mechanism that reverse order enables. The natural order's intermediate performance is consistent with the theory: it maintains monotonic improvement (HAML guarantees this regardless of order) but each update only achieves local optimality given the current (not yet updated) subsequent policies, rather than optimizing against the optimal continuation value that backward induction provides.
Normalization strategy (Table 5): Three variants of advantage normalization are compared: no normalization (raw GRAE advantages), group-level normalization (normalize within each group of samples from the same initial state, as used in GSPO), and batch-level normalization (subtract batch mean, divide by batch standard deviation, the default). Batch-level normalization achieves the best overall performance: 60.80% avg@4 and 72.85% pass@4. Group-level normalization achieves nearly identical performance: 60.28% avg@4 and 70.10% pass@4. No normalization performs substantially worse: 47.08% avg@4 and 58.45% pass@4, confirming that some form of normalization is essential for numerical stability. On AppWorld specifically: no normalization achieves 39.91% avg@4 and 57.89% pass@4; group normalization achieves 62.35% and 79.21%; batch normalization achieves 63.60% and 80.70%. On BFCL v4: no normalization achieves 54.25% and 59.00%; group normalization achieves 58.20% and 61.00%; batch normalization achieves 58.00% and 65.00%. The key finding is not that batch normalization is empirically superior to group normalization (the gap is small and inconsistent across metrics—batch has higher pass@4 but nearly identical avg@4 on BFCL v4) but that batch normalization achieves comparable empirical performance while preserving the theoretical convergence guarantees that group normalization breaks (Appendix H.3, Theorem 9). The no-normalization result is a useful lower bound showing that raw advantages, while theoretically sound, lead to unstable training in practice—likely because reward scales vary substantially across tasks, causing gradient magnitudes to fluctuate.
Training dynamics for ablations (Figure 5): The training curves for the update order comparison show that reverse order maintains the steadiest improvement trajectory. Natural order improves more slowly but eventually reaches competitive performance (subfigure a, Qwen3-14B + AppWorld: natural order appears roughly 10–15 percentage points below reverse order throughout training). Random order shows erratic behavior—on AppWorld, it fails to improve substantially beyond baseline performance, remaining below 40% throughout training while reverse order rises to ~63%. On BFCL v4 (subfigure b), the gap between orderings is smaller but consistent with the same ranking: reverse > natural > random.
Implicit ablation: base model capability: While not presented as a formal ablation, the comparison across Qwen2.5-14B and Qwen3-14B serves this purpose. The relative improvement from SeeUPO over baselines is larger on the stronger model (43–55% improvement on Qwen3-14B vs. 24–42% on Qwen2.5-14B), suggesting that SeeUPO's benefits are not limited to weak models that "need more help"—in fact, the opposite pattern holds. This is consistent with the theoretical framework: a stronger base model can produce higher-quality candidate actions at each turn, giving the sequential optimization more room to find improvements through better coordination across turns. The weaker model may hit a capability ceiling where no turn-level coordination strategy can compensate for fundamentally poor individual turn decisions.
Implicit ablation: benchmark difficulty: AppWorld appears consistently harder than BFCL v4 across all methods (lower absolute scores for every algorithm-model combination in Table 2). The gap between SeeUPO and baselines is larger on AppWorld, suggesting that the benefits of sequential optimization with convergence guarantees are most pronounced on harder tasks where training instability is a greater risk. On BFCL v4, where baselines perform reasonably well and training is more stable (Figure 4d shows no catastrophic collapse for any method), SeeUPO's advantage is smaller but still present.
Negative result: the cost of sequential updates. Table 3 implicitly serves as an ablation on the computational cost of the turn-by-turn update mechanism. The 1.5× training time multiplier is the price of the convergence guarantees and improved performance. Whether this is acceptable depends on the deployment context—the paper argues yes because the performance gains and stability improvements outweigh the cost, but a practitioner with tight training budget constraints might reach a different conclusion if their baseline (say, GRPO) happens to not exhibit catastrophic collapse on their specific task distribution.
Negative result: group normalization doesn't hurt empirically (on these benchmarks). Despite the theoretical proof that group-level normalization breaks convergence guarantees (Theorem 9, Appendix H.3), it achieves nearly identical performance to batch-level normalization in Table 5. This is a noteworthy finding because it suggests that the theoretical violation—while real—may not manifest as measurable degradation on these specific benchmarks at this scale. Several interpretations are possible: the group variances might be close enough to 1 that the violation is mild; the training horizon (75 epochs) might be insufficient for the theoretical instability to surface; or the benchmarks might not contain the specific query distributions that trigger the failure mode. This doesn't invalidate the theoretical analysis—the violation is still a violation regardless of whether it manifests empirically in a given configuration—but it cautions against overclaiming the practical importance of this specific issue on these benchmarks. A more comprehensive evaluation across a wider range of tasks and training durations would be needed to determine when group normalization's theoretical violation becomes empirically consequential.
Critical Assessment
Claim from the executive summary: SeeUPO "resolves the fundamental trade-off between critic-free operation and convergence guarantees." This claim is the paper's central theoretical contribution, and the evidence supporting it has two components. The negative component—that existing critic-free methods lack multi-turn convergence guarantees—is well-supported by the theoretical analysis in Appendices D, G, and H. The GRAE structural bias derivation (Theorem 4, part 1, Appendix D), the GRAE-PPU drift function violation (Theorem 7, Appendix G), and the group-variance normalization violation (Theorem 9, Appendix H.3) are mathematically rigorous and correctly identify specific, non-trivial failure modes. The positive component—that SeeUPO provides convergence guarantees—is supported by Theorem 2 (Appendix B), which proves global optimality under reverse update order in the multi-turn bandit setting. However, the connection between the theorem and the practical algorithm (SeeUPPO-GRAE) requires several assumptions: accurate advantage estimation (GRAE is unbiased in bandits, which is satisfied), valid drift functional and neighborhood operator (PPO-style clipping satisfies these, per prior work cited), and bounded rewards with compact policy space (standard). The gap between the theoretical guarantees and the empirical implementation is not fully closed—specifically, the theorem assumes the HAML update rule is solved exactly at each step (Equation 22 is an argmax, not a gradient step), while the practical algorithm uses multiple gradient steps with a clipped objective as an approximation to this argmax. This is a standard gap in RL theory (the Mirror Learning framework accommodates approximate solutions via the neighborhood operator, but the quality of the approximation matters), and the paper doesn't discuss how closely the gradient-based updates approximate the ideal argmax.
The empirical evidence for the "resolution" is the training stability result in Figure 4. The catastrophic collapse of GRPO and GSPO on Qwen2.5-14B + AppWorld (subfigure c) provides a dramatic demonstration that the theoretical failure mode (GRAE-PPU breaking monotonic improvement) manifests in practice. SeeUPO's stable training on the same configuration, combined with monotonic improvement across all four scenarios, is consistent with the theoretical prediction that its convergence guarantees translate to practical stability. However, the evidence is limited to two benchmarks, two model families, one training paradigm (React + Reasoning-Augmented Template), and one scale (14B parameters). Whether the catastrophic collapse of GRPO/GSPO would reproduce on other multi-turn benchmarks (web navigation, dialogue, code generation with execution feedback) is unknown. Whether SeeUPO's stability advantage persists at different model scales (e.g., 7B, 32B, 70B) is unknown. Whether the specific training template matters (the paper uses Zhai et al., 2025's paradigm throughout) is unknown. These are not necessarily weaknesses of the paper—every empirical study has limited scope—but they qualify the strength of the "resolution" claim. The paper demonstrates that SeeUPO resolves the trade-off in the configurations tested, which is evidence in favor of the general claim but not proof of it.
Claim from the executive summary: "achieving provable convergence to global optimality." The "provable" part is solid within the stated assumptions (Theorem 2, Appendix B). The "global optimality" part deserves scrutiny. The theorem proves that limit points of the policy sequence are globally optimal within the space of policies representable by the multi-agent bandit formulation. However, there are two subtle limitations. First, the bandit formulation itself restricts the policy class: each turn's policy conditions on $(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$ and produces a complete sequence $\boldsymbol{a}_t$. This means the policy cannot, for example, condition on intermediate environmental feedback within a turn—it's a "sequence-level" policy that generates the entire turn response given the conversation history. If the true optimal behavior requires within-turn adaptation to environmental signals, this formulation cannot represent it. Second, the global optimality is with respect to the modeled multi-agent game, not necessarily the original MDP. The transformation from MDP to multi-agent bandit is lossy in the sense that it abstracts away within-turn dynamics. Whether this matters empirically depends on the benchmark—the results suggest it doesn't substantially limit performance on AppWorld and BFCL v4 (since SeeUPO outperforms methods that do model token-level dynamics, like PPO and GRPO), but this might not generalize to tasks where within-turn adaptation is critical.
The ablation experiments are informative but incomplete. The update order comparison (Table 4) provides strong evidence that reverse order is superior to natural and random orders, consistent with the backward induction theory. However, there's a missing ablation: what happens if you use the multi-agent bandit formulation but update all turns simultaneously (joint optimization) rather than sequentially? This would test whether the multi-agent decomposition itself provides benefits independent of the sequential update mechanism—a useful decomposition of the method's two components (modeling + update order). The normalization comparison (Table 5) is similarly informative but incomplete: what happens if you vary the group size $G$ used for GRAE estimation? The paper uses $G = 8$ throughout; smaller $G$ would increase variance in the advantage estimates, potentially destabilizing training even with batch normalization, while larger $G$ would increase data collection cost. Understanding the sensitivity to $G$ would help practitioners choose this hyperparameter.
The missing baseline: PPO with sequence-level modeling. The paper compares SeeUPO against PPO at the token level (GAE + PPU, token-level MDP). But SeeUPO's key innovations are (a) sequence-level modeling (b) multi-agent decomposition (c) reverse-order sequential updates. A natural baseline would be PPO applied at the sequence level—treating each turn's response as an action, using a sequence-level critic (estimating $V(\boldsymbol{s}_0, \boldsymbol{a}_{1:t-1})$), and updating with a sequence-level PPU objective. This would isolate the contribution of the multi-agent decomposition and reverse-order updates from the contribution of simply switching to sequence-level modeling. The paper includes GSPO (which is sequence-level GRAE-PPU) but not a sequence-level GAE-PPU baseline. If such a baseline performed comparably to SeeUPO, it would suggest that the multi-agent decomposition is not essential; if it performed worse, it would strengthen the case for SeeUPO's specific approach.
The catastrophic collapse of GRPO/GSPO is a key piece of evidence for the paper's theoretical claims, but its interpretation requires care. The paper argues that this collapse demonstrates the GRAE-PPU structural bias breaking monotonic improvement. However, there are alternative explanations that the paper doesn't fully rule out. GRPO and GSPO differ from SeeUPO in multiple ways simultaneously: they use token-level or different sequence-level formulations, they don't use turn-oriented batching, they don't use sequential updates, and GSPO uses group-variance normalization. The collapse could be caused by any of these differences, or by interactions between them, rather than by the specific structural bias mechanism the paper identifies. The theoretical analysis (Appendix G) makes a strong case that the structural bias should cause problems, but the empirical demonstration doesn't isolate this mechanism from other confounds. A targeted experiment—for example, taking GSPO and only changing its advantage estimation to use a sequence-level critic (GAE instead of GRAE) while keeping everything else the same—would provide cleaner evidence that the advantage estimation bias is the causal factor. Such an experiment is not reported.
The computational efficiency analysis (Table 3) is informative but the interpretation is incomplete. The paper reports Training Step Time and GPU count but does not report total wall-clock time to reach a given performance threshold, which is the metric that matters for practical deployment decisions. Figure 4 shows SeeUPO reaching higher performance at every epoch, but if each epoch takes 1.5× longer, the fair comparison is performance vs. total wall-clock time, not performance vs. epochs. The paper's statement that SeeUPO achieves "notably faster convergence speed" (Section 5.2.2) is ambiguous—if "speed" means epochs, it's true; if "speed" means wall-clock time, the answer depends on the performance threshold and isn't directly reported. A plot of performance vs. cumulative training FLOPs or wall-clock time would be more informative for practitioners.
The small gap between group-normalized and batch-normalized SeeUPO (Table 5) is a genuine robustness check that partially validates the theoretical concern while also setting realistic expectations. The fact that group normalization—which provably breaks convergence guarantees—achieves 60.28% vs. 60.80% for batch normalization suggests that the theoretical violation, while real, has small empirical consequences on these benchmarks. This is both a strength of the paper (it reports the result honestly rather than hiding it) and a limitation (it suggests the theoretical concern about normalization may be less practically urgent than the paper implies). Future work could identify benchmark characteristics or training regimes where the group normalization violation matters more—perhaps tasks with highly heterogeneous reward variances across queries, or longer training horizons where the theoretical instability has more time to compound.
Overall assessment of experimental support. The experiments provide strong evidence for SeeUPO's practical superiority over existing backbone algorithms on the tested benchmarks and models—the performance gaps in Table 2 are large enough (24–55% relative improvement) that statistical significance concerns are minimal, and the training stability advantage in Figure 4 is visually unambiguous. The experiments provide moderate evidence for the claimed theoretical mechanism—the catastrophic collapse of GRPO/GSPO is consistent with the structural bias theory, but alternative explanations are not fully ruled out, and the paper would be strengthened by experiments that more cleanly isolate the causal role of advantage estimation bias. The experiments provide preliminary evidence for the global optimality claim—the reverse order outperforming natural and random orders (Table 4) is consistent with backward induction, but this is an indirect test (the theorem is about asymptotic convergence, which finite-training experiments cannot directly verify).
6. Limitations and Trade-offs
The Multi-Agent Bandit Abstraction Discards Within-Turn Dynamics
The assumption or constraint. SeeUPO's foundational modeling choice—abstracting each turn as a single bandit decision where the action is the complete turn response $\boldsymbol{a}_t$—treats the generation of that response as atomic. The sequence-level formulation explicitly "models multi-turn interactions by incorporating turn transitions and environmental feedback into the state through concatenation" (Section 2.1), meaning there are no intermediate states within a turn where the policy could observe partial results and adapt. The paper acknowledges this scope constraint implicitly when it distinguishes token-level RL (where "each token generation step corresponds to a timestep in the MDP") from sequence-level RL, describing the latter as providing "a more natural abstraction for multi-turn interactions" (Section 2.1) without claiming it captures within-turn dynamics.
The consequence. For tasks where optimal behavior requires within-turn adaptation—for instance, receiving a partial API error mid-generation and adjusting the remaining parameters, or observing intermediate computation results and changing course—the sequence-level formulation cannot represent these behaviors. The policy generates the entire turn response conditioned only on the conversation history before the turn begins. If the environment provides feedback during generation (streaming responses, progressive tool outputs), this information is invisible to the policy at decision time. Whether this matters empirically depends on the task: for AppWorld and BFCL v4, the results suggest it does not substantially limit performance (SeeUPO outperforms token-level methods like PPO and GRPO), but for tasks like interactive coding with execution feedback or multi-step reasoning with intermediate verification, the sequence-level constraint could be a fundamental ceiling on achievable performance. Additionally, the paper does not discuss whether the sequence-level importance sampling ratio $r_t(\boldsymbol{\theta})$ in Equation 6—which compares full response probabilities under old and new policies—suffers from higher variance than token-level ratios due to the combinatorial explosion of possible sequences.
What evidence exists in the paper. No experiment directly tests the impact of the sequence-level abstraction on within-turn adaptability. The benchmarks used (AppWorld, BFCL v4) are turn-based: the agent produces a complete response, the environment executes it, and the next turn begins. This task structure is well-matched to the sequence-level formulation, so the experiments cannot reveal whether the abstraction would hurt on tasks requiring within-turn reactivity. The paper does not compare SeeUPO against a token-level variant of itself (which would be a natural ablation—using the same reverse-order sequential updates but at the token level) to isolate the effect of the sequence-level choice.
Mitigation status. The paper does not address this limitation. The sequence-level abstraction is presented as a feature ("a more natural abstraction") rather than a trade-off. Future work could explore hybrid formulations where some turns are treated as sequence-level bandits and others allow token-level adaptation, or where the policy conditions on partial within-turn feedback through a structured input format.
Difficulty Estimation and Data Collection Cost Are Not Accounted For
The assumption or constraint. SeeUPO's training procedure requires, at each iteration, collecting $B \times G$ full multi-turn trajectories (batch size $B = 32$, group size $G = 8$, so 256 trajectories per iteration) by executing the current policy in the environment. For each of the $G$ trajectories from the same initial state, the group mean reward $\bar{r}(\boldsymbol{s}_0)$ must be computed before advantage estimation can proceed. This means the data collection phase involves interacting with the target environment (AppWorld, BFCL v4) for potentially hundreds of steps per trajectory (up to 10 turns with tool calls at each turn). The paper does not account for the environment interaction cost in its computational efficiency analysis (Table 3), which reports only GPU training step time.
The consequence. The true cost of training SeeUPO includes both the GPU computation and the environment interaction cost—API calls, tool executions, or simulator steps. For benchmarks like AppWorld that simulate complex application environments, this interaction cost could dominate the training budget. In a production setting where training involves calling real APIs or interacting with live systems, the data collection cost could be the binding constraint, not the GPU training time. Furthermore, the $G = 8$ trajectories per initial state are collected specifically to compute the group mean for GRAE. If $G$ were reduced (to save data collection cost), the variance of the advantage estimates would increase, potentially destabilizing training—but the paper provides no sensitivity analysis on $G$ to guide practitioners on this trade-off. The batch-level normalization in Table 5 partially mitigates variance sensitivity, but the interaction with $G$ is unexplored.
What evidence exists in the paper. Table 3 reports Training Step Time in seconds, which appears to measure only the GPU computation time for the policy update phase, not the data collection phase. The paper states that training runs for "75 epochs on AppWorld and 50 epochs on BFCL v4" (Section 5.1.3) but does not report the total number of environment interactions, the average trajectory length, or the wall-clock time for data collection. The computational efficiency analysis therefore captures only one component of the total cost, making it difficult for practitioners to estimate the full resource requirements for deployment.
Mitigation status. Not addressed. The paper focuses on the algorithmic efficiency of the update mechanism (comparing Training Step Time across methods) without discussing data collection costs. For academic benchmarks where environment interaction is simulated and fast, this is a minor omission; for real-world deployment where interaction is expensive or rate-limited, it is a significant gap. The paper suggests no methods for reducing the number of environment interactions (e.g., off-policy data reuse, smaller $G$ with alternative variance reduction, or using a learned baseline instead of the group mean for advantage estimation).
Convergence to Global Optimality Requires a Fixed Maximum Number of Turns
The assumption or constraint. The multi-agent bandit formulation assumes a fixed maximum number of turns $T$ known in advance. The turn-oriented batch construction (Figure 3, Section 4.2) organizes samples from identical turn positions into separate pools $\mathcal{D}_1, \ldots, \mathcal{D}_T$, with placeholder (no-op) samples introduced for trajectories with fewer than $T$ turns. The backward induction proof (Appendix B, Theorem 2) operates over the fixed set of turns $\{1, \ldots, T\}$, recursively defining the optimal continuation value $V^*(\boldsymbol{s}_0, \boldsymbol{a}_{1:t})$ from $t = T$ down to $t = 1$.
The consequence. For tasks where the number of turns varies substantially or is unbounded (e.g., open-ended dialogue, iterative refinement until a convergence criterion is met, exploration tasks where the agent decides when to stop), the fixed-$T$ formulation creates two problems. First, trajectories that exceed $T$ turns must be truncated, discarding potentially informative later interactions and training the turn-$T$ policy on truncated data that may not represent actual terminal behavior. Second, trajectories that are much shorter than $T$ produce many placeholder samples (no-op actions in pools $\mathcal{D}_{t}$ for $t$ beyond the trajectory's actual length). These placeholders contribute zero-gradient updates, but they occupy space in the batch construction and dilute the effective sample size for later-turn policies. If the average trajectory length is $\bar{T} \ll T_{\max}$, most samples in later-turn pools are placeholders, making it difficult to learn good policies for those turn positions. Third, the global optimality guarantee applies to the $T$-turn bandit game, not to the original potentially-variable-length task—if the optimal behavior involves terminating early, the bandit formulation forces a $T$-turn interaction and may learn suboptimal turn-padding strategies.
What evidence exists in the paper. The paper does not report the distribution of trajectory lengths on AppWorld or BFCL v4, the value of $T$ used in experiments, or the fraction of samples that are placeholders. Figure 3 illustrates the batch construction with a "Sample 6" placeholder but provides no statistics on how common such placeholders are in practice. The 10-step trajectory truncation limit (Section 5.1.1) is mentioned but not analyzed in terms of how many trajectories hit this limit. These omissions make it difficult to assess how significant the fixed-$T$ constraint is for the evaluated benchmarks.
Mitigation status. The paper acknowledges a related concern in Section 6 (Limitations and Future Work) when discussing parameter sharing: "the HAML framework theoretically requires heterogeneous policies across agents, which in traditional RL corresponds to non-shared network parameters." However, this addresses a different issue (representational capacity with shared parameters) and does not discuss the fixed-$T$ constraint. The placeholder mechanism is presented as a practical solution (Algorithm 1, Figure 3) without analysis of its limitations. Future work could explore variable-$T$ formulations, perhaps by incorporating a termination action that allows the agent to stop early, or by dynamically constructing batch pools based on actual trajectory lengths rather than a fixed maximum.
The 14B-Parameter Scale Is Not Justified and Generalization to Other Scales Is Unknown
The assumption or constraint. All experiments use 14B-parameter models (Qwen2.5-14B-Instruct and Qwen3-14B). The paper provides no justification for this specific scale and no analysis of how SeeUPO's behavior—in terms of performance, stability, or computational overhead—varies with model size. The HAML framework's assumption of heterogeneous policies (each turn treated as a distinct agent with its own policy) is addressed in Section 6 with the argument that "the sufficiently large parameter space provides ample representational capacity for different turns or roles to develop functionally distinct behaviors, making the policies non-homogeneous from a turn-level perspective despite parameter sharing." This argument suggests that SeeUPO's effectiveness might depend on the model being "large enough" for parameter sharing to support turn-specific specialisation, but the threshold for "large enough" is unexplored.
The consequence. A practitioner considering SeeUPO for a 7B model (common for on-device or cost-constrained deployment) or a 70B model (common for maximum capability) cannot predict how the method will perform. At smaller scales, the shared parameters might lack sufficient capacity to represent distinct turn-specific behaviors, potentially causing the sequential updates to interfere destructively—updating the policy for turn $t$ might degrade performance for turn $t-1$ because the parameters cannot simultaneously encode both optimal policies. At larger scales, the 1.5× training time overhead (Table 3) may become proportionally more painful (if training a 70B model already stretches compute budgets) or less painful (if the performance gains justify the cost at scale). The paper provides no evidence either way. Additionally, the computational efficiency numbers in Table 3 are specific to the 14B scale on H20 GPUs—training step times for 7B or 70B models on different hardware would scale non-linearly and cannot be extrapolated from the reported numbers.
What evidence exists in the paper. None. The paper only evaluates 14B models. The dual-model evaluation (Qwen2.5-14B and Qwen3-14B) tests different base capabilities but not different scales. The relative improvement from SeeUPO is larger on Qwen3-14B (43–55%) than on Qwen2.5-14B (24–42%), suggesting that SeeUPO benefits more when the base model is stronger, but this is evidence about capability, not scale—a 7B model could be "strong" on a simpler task and a 70B model could be "weak" on a harder task. The interaction between model scale and SeeUPO's effectiveness is a separate dimension that the experiments do not address.
Mitigation status. The paper does not discuss scale as a limitation. Section 6 mentions that the heterogeneity assumption "becomes increasingly justified with larger-scale architectures such as Mixture-of-Experts (MoE) models, where different experts can specialize for different turns," which implies awareness that scale matters but provides no empirical evidence. Future work on scaling SeeUPO to different model sizes would be essential for practical deployment guidance, particularly for smaller models where parameter sharing conflicts might be more severe.
The Theoretical Guarantees Assume Exact Argmax Solutions, While the Practical Algorithm Uses Gradient-Based Approximations
The assumption or constraint. Theorem 2 (Appendix B) proves that the policy sequence generated by the HAML update rule (Equation 22) converges to global optimality. This update rule is an exact argmax: at each step, the algorithm finds the policy $\hat{\pi}^{k+1}_t$ that exactly maximizes the mirror operator objective over the neighborhood $\mathcal{U}_{\hat{\pi}^k_t}(\hat{\pi}^k_t)$. The practical algorithm SeeUPPO-GRAE (Section 4.2) approximates this argmax through multiple gradient steps on the clipped PPO objective (Equation 6). The relationship between the number of gradient steps, the learning rate, the clipping parameter $\epsilon$, and the quality of the argmax approximation is not analyzed.
The consequence. There is a gap between what the theorem guarantees (exact argmax at each sequential update step) and what the algorithm does (stochastic gradient-based optimization of a surrogate objective). If the gradient-based updates fail to closely approximate the exact argmax—due to insufficient optimization steps, poor conditioning of the loss landscape, or the surrogate objective being a poor proxy for the true mirror operator—the theoretical guarantees may not transfer to the practical algorithm. Specifically, the monotonic improvement guarantee (Theorem 1, Appendix A.2) requires that each agent's update improves the joint return. Gradient-based updates with a clipped objective are designed to approximate this behavior, but they are not guaranteed to do so—a poorly chosen learning rate or insufficient optimization could produce updates that degrade performance. The empirical training curves (Figure 4) show SeeUPO maintaining stable, monotonically improving performance, suggesting the gradient approximation works in practice on these benchmarks. However, without an analysis of the approximation quality, a practitioner cannot diagnose when the approximation might fail or how to tune hyperparameters (number of gradient steps per turn, learning rate schedule, $\epsilon$) to ensure it doesn't.
What evidence exists in the paper. The paper's training hyperparameters (Section 5.1.3) specify the learning rate ($1 \times 10^{-6}$), batch size (32), and clipping parameter ($\epsilon = 0.2$), but do not specify how many gradient steps are taken per turn update in the sequential update phase (Step 2c of Algorithm 1). The pseudocode is ambiguous: Step 2c says "Update policy parameters to obtain $\boldsymbol{\pi}_{\boldsymbol{\theta}^{k+1}_t}$ via Equation 6" without indicating whether this is a single gradient step or multiple steps. The statement that "all algorithms use the same number of samples, and samples are utilized the same number of times within each update step" (Section 5.1.3) implies a fixed number of gradient steps shared across methods, but this number is not reported. Without knowing how many gradient steps are taken, it's impossible to assess how closely the algorithm approximates the exact argmax. The ablation on update order (Table 4, Figure 5) provides some evidence that the gradient-based approximation captures the qualitative behavior predicted by the theory (reverse order > natural order > random order), but this is indirect.
Mitigation status. Not addressed. The paper treats the PPO-style gradient-based update as a valid instantiation of the HAML mirror operator, citing prior work (Grudzien et al., 2022; Zhong et al., 2024) that established the connection. However, those prior works analyze the connection at the level of the objective function (showing that the clipped objective corresponds to a valid drift functional), not at the level of optimization quality (showing that gradient steps on this objective reliably approximate the argmax). The gap between objective-level correspondence and optimization-level approximation is not discussed. Future work could analyze the relationship between optimization hyperparameters and convergence, perhaps by measuring the drift functional value achieved by gradient-based updates vs. the theoretical optimum, or by providing bounds on the suboptimality introduced by approximate optimization.
The Empirical Evaluation Is Limited to Two Benchmarks from a Single Task Family (Tool-Augmented Agents)
The assumption or constraint. The paper evaluates SeeUPO on two benchmarks: AppWorld (interactive coding agents navigating application workflows) and BFCL v4 (multi-turn function calling). Both fall within the same broad task family: tool-augmented agents where the LLM interacts with APIs, receives structured feedback, and uses that feedback to plan subsequent actions. The tasks feature sparse terminal rewards, multi-step interactions, and programmatic evaluation. The paper provides no evaluation on other multi-turn agentic task families: web navigation (e.g., WebArena, Mind2Web), dialogue (e.g., MultiWOZ, Taskmaster), code generation with execution feedback (e.g., SWE-bench, HumanEval with iterative refinement), embodied interaction, or multi-turn reasoning without tools.
The consequence. The paper's central claim—that SeeUPO "resolves the fundamental trade-off between critic-free operation and convergence guarantees in multi-turn scenarios"—is supported empirically only for the specific multi-turn structure found in tool-augmented tasks. Different task families may present different challenges that affect SeeUPO's performance or the relative ranking of methods. For instance, dialogue tasks often have dense turn-level rewards (user satisfaction signals) rather than sparse terminal rewards, which could change the credit assignment problem that SeeUPO's reverse-order updates are designed to solve. Web navigation tasks involve visual perception and much longer horizons (potentially dozens of turns), which could stress the fixed-$T$ formulation and the computational cost of sequential updates. Tasks with highly stochastic environments might increase the variance of GRAE's advantage estimates, potentially requiring larger group sizes $G$ or more sophisticated baseline estimation. Conversely, some task families might be easier for existing methods than the benchmarks tested—if GRPO and GSPO don't exhibit catastrophic collapse on other multi-turn tasks, SeeUPO's stability advantage would be less pronounced, and the cost of sequential updates (1.5× training time) might not be justified.
What evidence exists in the paper. The two benchmarks, while both tool-augmented, do exhibit different characteristics that provide some evidence of robustness. AppWorld appears consistently harder (lower absolute scores for all methods in Table 2), and the catastrophic collapse of GRPO/GSPO occurs only on AppWorld (Qwen2.5-14B, Figure 4c) while BFCL v4 shows stable training for all methods (Figure 4d). This suggests that the training instability problem is benchmark-dependent—it manifests on the harder, more complex environment but not on the relatively easier one. SeeUPO maintains stable training on both, which is evidence of robustness across these two difficulty levels. However, the qualitative similarity of the task structures (both involve API/tool interactions with sparse terminal rewards) limits the generalizability of this finding to structurally different task families.
Mitigation status. Not addressed. The paper acknowledges no limitation regarding benchmark diversity. The selection of "two tool-augmented, agentic benchmarks" (Section 5.1.1) is presented as a feature (they "expose multi-step API/tool interactions under sparse terminal rewards, making them ideal testbeds for evaluating multi-turn agent training algorithms") rather than a constraint on the scope of empirical claims. The conclusions (Section 6) generalize broadly about "multi-turn scenarios" and "RL algorithms for LLM training" without qualifying that the empirical evidence comes from a specific task family. Future work evaluating SeeUPO on web navigation, dialogue, code generation with execution feedback, and other multi-turn task families would be necessary to establish the breadth of its advantages.
7. Implications and Future Directions
How This Work Changes the Landscape
This paper shifts the conversation around LLM agent training from algorithm-as-monolith empiricism to algorithm-as-compositional-system theory. Before this work, the field evaluated backbone RL algorithms (PPO, GRPO, RLOO, GSPO) as atomic entities—researchers compared them on benchmarks, observed which "worked better," and drew conclusions without understanding why they worked differently. The paper's decomposition along two axes (advantage estimation × policy update mechanism) reveals that these empirical differences are not mysterious properties of "PPO-ness" or "GRPO-ness" but predictable consequences of how the two components interact. This reframes algorithm selection from an empirical art to a diagnostic science: rather than asking "which algorithm is best?", researchers can now ask "does my advantage estimator introduce structural bias, and does my update mechanism have sign-dependent non-linearities that interact with that bias?"
The magnitude of this shift is conceptual reframing, not paradigm shift. The individual pieces (GAE, GRAE, REINFORCE, PPU) were all known; the paper's contribution is showing that their interactions form a phase diagram with sharp boundaries—GAE + PPU converges, GRAE + REINFORCE converges under undiscounted objectives, GRAE + PPU breaks in MDPs but works in bandits—rather than a smooth spectrum of trade-offs. This is analogous to how the discovery that certain drug combinations produce toxicity while each drug individually is safe changed pharmacology from trial-and-error to mechanism-based prediction. The "toxicity" here is training collapse, and the "mechanism" is structural bias $\Delta(s_t) = V(s_t) - V(s_0)$ interacting with PPU's sign-dependent clipping.
A concrete reconciliation the paper provides: why GRPO works on single-turn math reasoning but collapses on multi-turn agentic tasks is no longer a mystery explained post-hoc by "multi-turn is harder." The taxonomy provides the mechanism: in single-turn (contextual bandit) settings, $V(s_t) = V(s_0)$ identically for all $t$ (there is only one state), so GRAE's structural bias $\Delta(s_t)$ is zero and GRAE-PPU inherits PPU's convergence guarantees (Appendix H, Theorem 8). In multi-turn MDPs, $V(s_t)$ evolves as the agent accumulates reward, the structural bias becomes non-zero, and GRAE-PPU's drift function violates the non-negativity and zero-at-origin properties required by Mirror Learning (Appendix G, Theorem 7). This explains the entire empirical picture—GRPO's single-turn success and multi-turn failure—with a single mechanism, rather than requiring separate explanations for each observation.
Research directions that become more attractive:
- Mechanistic analysis of other RL components. The paper's taxonomy approach—decompose an algorithm into independent design axes, analyze how each axis affects convergence properties, then study interactions—is a template that could be applied to other RL components not covered here: KL penalty formulations, advantage normalization schemes, off-policy correction methods, and sequence-level vs. token-level credit assignment. Future algorithms can be analyzed by placing them in the taxonomy and checking which cell they occupy, rather than requiring de novo theoretical analysis.
- Critic-free methods with bandit reformulations. The paper's central trick—transforming an MDP into a multi-agent bandit to eliminate structural bias—suggests a general design pattern: if a critic-free method suffers from
$V(s_t) - V(s_0)$bias, perhaps the problem formulation (not the estimator) can be restructured to make that bias vanish. This is a different approach from prior work that tried to correct the bias within the estimator (e.g., by subtracting learned baselines or using critic ensembles). The HAML framework provides the theoretical scaffolding for such reformulations. - Drift functional verification as an algorithm design tool. The Mirror Learning framework's requirements (non-negativity, zero gradient, closed ball neighborhood) are not just analysis tools—they are design constraints. A developer proposing a new advantage normalization scheme or clipping variant can check whether the resulting drift functional satisfies these properties before running expensive experiments. The paper's analysis of GSPO's variance normalization (Theorem 9, Appendix H.3) demonstrates this: a few lines of algebra show the drift function requires
$\delta(\boldsymbol{s}) \equiv 1$for non-negativity, immediately flagging group-level normalization as theoretically unsound without needing to observe training collapse.
Research directions that become less attractive:
- Incremental improvements to GRAE within the MDP formulation. The paper's analysis (Theorem 7, Appendix G) shows that GRAE's structural bias interacts destructively with PPU's clipping in a way that cannot be fixed by improving the estimator (e.g., larger group sizes, leave-one-out corrections, or learned baselines). The bias
$\Delta(s_t) = V(s_t) - V(s_0)$is not an estimation error that shrinks with more samples—it's a structural mismatch between what GRAE estimates ($Q(s_t, a_t) - V(s_0)$) and what PPU requires ($A(s_t, a_t) = Q(s_t, a_t) - V(s_t)$). Efforts to "fix" GRPO by tweaking its advantage estimator while keeping the MDP formulation are fighting the wrong battle. The paper's solution—change the formulation, not the estimator—suggests this line of work has hit a fundamental limit. - Developing ever-more-sophisticated token-level critic architectures for multi-turn tasks. PPO with GAE-PPU remains the only algorithm in the taxonomy with full multi-turn convergence guarantees, but it requires accurate token-level value function estimation—a problem that becomes harder as the number of turns, the complexity of environmental feedback, and the stochasticity of interactions increase. If SeeUPO's sequence-level bandit reformulation works well across a broad range of multi-turn tasks, the motivation for solving the hard token-level value estimation problem diminishes: why build better critics when reformulating the problem makes critics unnecessary?
Follow-Up Research This Work Enables
Stress-test SeeUPO on task families with qualitatively different multi-turn structures. The paper evaluates on tool-augmented agents (AppWorld, BFCL v4) featuring sparse terminal rewards, structured API interactions, and moderate turn counts. The strongest test of the multi-agent bandit formulation's generality would be to apply SeeUPO to a task where the abstraction is least natural—for example, open-ended multi-turn dialogue (MultiWOZ, Taskmaster) where rewards may be turn-level and dense, or web navigation (WebArena) with extended horizons of 20+ turns and visual state representations. If SeeUPO maintains stability and outperforms baselines on dialogue tasks (where the "optimal continuation value" $V^*$ is more ambiguous because rewards are not purely terminal), it would validate the formulation's robustness. If it underperforms PPO on dialogue while excelling on tool-use tasks, it would map the boundary conditions of the bandit abstraction—revealing which multi-turn structures benefit from reformulation and which are better served by MDP-native approaches. A particularly informative experiment would be to measure the correlation between $\bar{T}$ (average trajectory length) and SeeUPO's relative improvement over baselines: the theory predicts that the structural bias $\Delta(s_t)$ grows with turn count, so SeeUPO's advantage should be larger on longer-horizon tasks, but the fixed-$T$ placeholder mechanism might create countervailing degradation if most trajectories are much shorter than $T_{\max}$.
Characterize the gradient-step-to-argmax approximation gap and its practical consequences. Theorem 2 (Appendix B) guarantees convergence when each sequential update exactly solves the argmax in Equation 22, but SeeUPPO-GRAE approximates this argmax through gradient steps on a clipped surrogate objective. A systematic study varying the number of gradient steps per turn update—from 1 (extreme approximation) to, say, 50 (near-argmax)—would reveal how optimization quality affects training stability and final performance. If SeeUPO remains stable with only 1-2 gradient steps per turn, the theoretical gap between exact-argmax and approximate-gradient is benign, and the algorithm can be made substantially faster by reducing the inner-loop optimization cost (which is the major contributor to the 1.5× training time overhead in Table 3). If stability degrades with fewer gradient steps, the gap is practically significant, and the algorithm's hyperparameters must be carefully tuned to approximate the argmax—a constraint that should be documented for practitioners. Measuring the achieved drift functional value $\mathfrak{D}_{\hat{\pi}^k_t}(\hat{\pi}^{k+1}_t \mid \ldots)$ after different numbers of gradient steps would quantify how close the gradient-based update is to the theoretical optimum that guarantees monotonic improvement, providing a diagnostic tool for detecting when optimization is insufficient.
Test whether the multi-agent decomposition itself provides benefits independent of the sequential update order. The paper's ablation (Table 4) compares reverse, natural, and random update orders within the multi-agent bandit formulation but does not include a simultaneous joint update where all turns are optimized together in a single PPO-style step—i.e., a sequence-level PPO with shared parameters across turns but without any sequential structure. This baseline would isolate whether the multi-agent decomposition (treating turns as separate bandits with importance-sampling corrections) provides value above and beyond simply applying PPO at the sequence level, or whether the decomposition's benefits are entirely contingent on the sequential update mechanism. If simultaneous joint update performs comparably to reverse-order sequential updates, the multi-agent modeling is the key innovation and the update order is less important. If simultaneous joint update performs substantially worse (closer to the natural-order or random-order results), the sequential update mechanism—and specifically the reverse order—is essential, and the multi-agent decomposition is primarily valuable as the structure that enables sequential updates. This experiment would clarify the causal decomposition of SeeUPO's performance: modeling vs. update order vs. their interaction.
Investigate the interaction between model scale and parameter sharing in the multi-agent formulation. The paper acknowledges (Section 6) that the HAML framework assumes heterogeneous policies across agents, while SeeUPPO-GRAE uses shared parameters for all turns, arguing that large models have sufficient capacity for turn-specific specialization. A scaling study—evaluating SeeUPO on 7B, 14B, 32B, and 70B models on the same benchmarks—would test this argument empirically. If SeeUPO's relative improvement over baselines increases with model scale (larger gains at 70B than at 7B), it supports the capacity argument: bigger models better accommodate the functionally-distinct turn policies that the sequential updates try to learn. If improvement is constant or decreases with scale, the capacity argument is weak and the sequential updates may interfere destructively regardless of model size. A related experiment would be to compare fully shared parameters (the current design) against turn-specific adapters or turn-specific LoRA modules—a lightweight form of explicit heterogeneity that wouldn't substantially increase parameter count but would give each turn dedicated representational capacity. If turn-specific adapters improve performance, it would confirm that parameter sharing is a bottleneck; if they make no difference, the capacity of a 14B model is already sufficient and heterogeneity is being achieved implicitly.
Measure whether the fixed-$T$ placeholder mechanism degrades performance when actual trajectory lengths are highly variable. The paper's batch construction (Figure 3, Algorithm 1) pads all trajectories to the same maximum number of turns $T$ using placeholder (no-op) samples. A diagnostic experiment: vary the maximum $T$ (e.g., 5, 10, 15, 20 turns) on a benchmark with variable-length trajectories and measure how performance on early-turn policies degrades as $T$ exceeds the typical trajectory length. The theory predicts that when most trajectories are much shorter than $T$, the later-turn pools are dominated by placeholders with zero-gradient updates, diluting the effective sample size for those turn policies. This shouldn't directly harm early-turn policies (turns 1-3 are still trained on real data), but the backward induction mechanism requires good later-turn policies to provide accurate continuation values for earlier-turn optimization—if turns 10-15 are trained predominantly on placeholders, their policies may be poor, degrading the continuation values that turns 1-9 optimize against. An alternative dynamic-$T$ scheme—constructing batch pools adaptively based on actual trajectory lengths, with $T$ set to the maximum in each batch—could be compared to the fixed-$T$ design to quantify the cost of fixed padding.
Apply the taxonomy analysis to a broader set of advantage estimation and update mechanism combinations. The paper analyzes four combinations (GAE-PPU, GRAE-REINFORCE, GAE-REINFORCE, GRAE-PPU) but the design space is larger than explored here. For instance, multi-step GRAE: rather than using the terminal reward as the baseline, compute GRAE-style advantages using $k$-step returns with bootstrapping from a learned value function, creating a spectrum between pure GRAE and pure GAE. At $k=0$, this is standard GRAE (biased in MDPs, per Appendix D). At $k=\infty$, this is Monte Carlo returns with a GRAE baseline (the bias persists but the variance-reduction properties change). For intermediate $k$, the bias-variance trade-off is different from both GAE and GRAE, and analyzing it within the Mirror Learning framework could reveal whether there exists a $k$ that preserves convergence guarantees while reducing variance compared to both extremes. Similarly, Leaky PPU: what if PPU's clipping were asymmetric—$\epsilon_{\text{upper}} \neq \epsilon_{\text{lower}}$—to be more conservative in the direction that GRAE's bias might be pushing incorrectly? The sign-flip failure mode in Theorem 7 (Appendix G, Part 4) occurs when positive bias flips a negative advantage to positive, causing PPU to increase the probability of a bad action (clipping at $1+\epsilon$). If $\epsilon_{\text{upper}}$ were smaller than $\epsilon_{\text{lower}}$, this could bound the damage from sign-flipped advantages, potentially making GRAE-PPU more robust even without full convergence guarantees.
Practical Applications and Downstream Use Cases
Stable fine-tuning of customer-facing agentic AI systems. Organizations deploying LLM agents in production—for customer support, IT helpdesk automation, or enterprise software navigation—need training pipelines that do not catastrophically collapse during scheduled fine-tuning. The catastrophic failure of GRPO and GSPO on AppWorld (Figure 4c, dropping from ~35% to near-zero within 20 epochs) is a concrete illustration of the risk: a production pipeline that periodically fine-tunes agents on new interaction data could silently degrade if using an algorithm without convergence guarantees. SeeUPO's monotonic training curves across all four model-benchmark configurations (Figure 4) mean the system operator can reliably expect that more training will not make the agent worse—a property that is table stakes for production ML but not guaranteed by the critic-free algorithms currently most popular for LLM training. The computational cost trade-off is favorable: SeeUPO requires 8 GPUs (vs. PPO's 16) and ~1.5× the per-step time of GRPO/GSPO, but eliminates the risk of having to roll back to an earlier checkpoint after a collapse. For a team running weekly fine-tuning jobs, the stability guarantee eliminates an entire class of operational incidents.
Cost-efficient training of multi-turn tool-use agents for specialized domains. The results on BFCL v4 (Table 2) show SeeUPO achieving 58.00% avg@4 on Qwen3-14B, compared to 43.75–45.75% for baselines—a ~30% relative improvement on a benchmark specifically designed for realistic multi-turn API usage. For organizations building domain-specific agents (legal research with document retrieval APIs, financial analysis with data query tools, scientific workflow automation with lab equipment APIs), this translates directly to higher task completion rates with the same model size and training budget. The 43.3–54.6% relative improvement on Qwen3-14B means a domain-specific agent trained with SeeUPO could substantially outperform one trained with GRPO at the same compute cost, potentially making the difference between a viable product and an unreliable prototype. The turn-oriented batching approach is particularly relevant here: domain-specific tasks often have well-defined turn structures (standard operating procedures, templated workflows) where the fixed-$T$ formulation's assumptions are naturally satisfied, and the placeholder mechanism's drawbacks are minimal because most trajectories follow the expected number of steps.
Self-improvement data generation for agent capabilities. The paper's Section 1 mentions "RL-driven self-evolution" as a key research direction, and SeeUPO's training stability makes it suitable for iterative self-improvement pipelines where each generation of training data comes from the previous generation's policy. In a STaR/ReST-style loop (Zelikman et al., 2022; Singh et al., 2024), the agent generates solutions, solutions above a quality threshold are added to the training set, and the policy is fine-tuned on the expanded set. If the RL algorithm used for fine-tuning exhibits non-monotonic behavior (like GRPO/GSPO on AppWorld), the self-improvement loop can enter a death spiral: a bad policy update → degraded data generation → worse training data → further degradation. SeeUPO's monotonic improvement guarantee (Theorem 1, Appendix A.2), while not eliminating the risk of distribution shift from off-policy data, at least ensures that the RL update step itself does not actively degrade the policy. The 4× generation efficiency documented in the paper's Table 2 (SeeUPO achieving 60.80% vs. 39.32–42.43% from baselines on the same number of samples) also means self-improvement loops can iterate faster—fewer samples are "wasted" on trajectories that don't contribute to improvement, accelerating the cycle of generate → filter → train.
When to Prefer This Method
The paper explicitly positions SeeUPO against three named alternatives—PPO, GRPO, and GSPO—with clear trade-offs along the axes of convergence guarantees, critic dependency, and computational cost. The following decision rules are grounded in the paper's theoretical analysis and empirical results:
-
Prefer SeeUPO over GRPO or GSPO when the task involves multi-turn interaction with potential for intermediate state values to diverge from initial values (i.e., tasks where the agent accumulates meaningful reward or state change across turns), and when training stability is important enough to justify a ~1.5× per-step training time overhead. The catastrophic collapse of both GRPO and GSPO on Qwen2.5-14B + AppWorld (Figure 4c) demonstrates that this is not a theoretical edge case—on the hardest multi-turn benchmark tested, these methods fail entirely while SeeUPO maintains stable improvement. The relative gain of 43–55% on Qwen3-14B (Table 2) and the elimination of training collapse risk make this a strong preference for any production deployment of multi-turn agents.
-
Prefer PPO over SeeUPO when computational budget is extremely tight on wall-clock time per training step (PPO's per-step time of 2790–2815s is faster than SeeUPO's 3895–4304s, Table 3) and the task's state space is simple enough that accurate token-level value function estimation is feasible. PPO remains the only algorithm in the taxonomy with full convergence guarantees in multi-turn MDPs under standard assumptions (Appendix F, Theorem 6), and if the critic can be trained reliably (which requires 16 GPUs vs. SeeUPO's 8), it avoids the fixed-
$T$placeholder issue and the sequence-level within-turn dynamics limitation. However, PPO's empirical performance on AppWorld and BFCL v4 is substantially below SeeUPO's (39.42% vs. 60.80% avg@4 on Qwen3-14B, Table 2), suggesting that the critic estimation problem is genuinely hard on these benchmarks, making PPO's theoretical guarantees not fully realized in practice. -
Prefer GRPO or GSPO over SeeUPO when the task is single-turn (contextual bandit) or effectively single-turn (multi-turn tasks where intermediate turns convey no substantial reward or state information beyond what the initial query captures). The paper's theory (Appendix H, Theorem 8) shows that GRAE-PPU converges in contextual bandits, so the structural bias that causes multi-turn failure does not arise. In this regime, GRPO and GSPO offer critic-free operation and faster per-step training time (2365–2803s vs. SeeUPO's 3895–4304s, Table 3) without the stability risk that manifests in multi-turn settings. The paper's results do not directly test this claim on single-turn tasks, but the theoretical analysis (Appendix H.1, Lemma 6-7) strongly supports it. The fixed-
$T$placeholder mechanism and turn-oriented batching are unnecessary overhead for single-turn tasks, further tilting the practical trade-off toward the simpler methods in this regime.
