PaperlayerView exact revision on arXiv

Source-linked AI summary

SeeUPO: Sequence-Level Agentic-RL with Convergence Guarantees

Tianyi Hu, Qingxu Fu, Yanxi Chen, Zhaoyang Liu, Bolin Ding

arXiv:2602.06554v1cs.AI

TL;DR

Existing backbone RL algorithms lack verified convergence guarantees in multi-turn agentic settings and cannot generally combine critic-free operation with convergence. The paper analyzes these combinations and proposes SeeUPO, which models turns as sequential multi-agent bandits and updates policies in reverse order. Across AppWorld and BFCL v4, SeeUPO improves performance over baselines and maintains stable training, with a limitation concerning heterogeneous-policy assumptions.

  • Problem

    Mainstream backbone RL algorithms cannot simultaneously achieve critic-free operation and convergence guarantees in multi-turn settings.

  • Method

    SeeUPO models multi-turn interactions as sequentially executed multi-agent bandit problems and performs reverse-order, turn-by-turn policy updates.

  • Results

    43.3%–54.6% relative gains on Qwen3-14B and 24.1%–41.9% on Qwen2.5-14B are reported across AppWorld and BFCL v4, with superior training stability.

  • Takeaways & Limitations

    Reverse-order sequential updates provide a critic-free route to monotonic improvement and convergence to a globally optimal solution in multi-turn interactions.

  • Takeaways & Limitations

    The theoretical framework requires heterogeneous policies across agents, while the LLM implementation relies on parameter sharing to produce functionally distinct turn-level behaviors.

Abstract

from arXiv · show

Reinforcement learning (RL) has emerged as the predominant paradigm for training large language model (LLM)-based AI agents. However, existing backbone RL algorithms lack verified convergence guarantees in agentic scenarios, especially in multi-turn settings, which can lead to training instability and failure to converge to optimal policies. In this paper, we systematically analyze how different combinations of policy update mechanisms and advantage estimation methods affect convergence properties in single/multi-turn scenarios. We find that REINFORCE with Group Relative Advantage Estimation (GRAE) can converge to the globally optimal under undiscounted conditions, but the combination of PPO & GRAE breaks PPO's original monotonic improvement property. Furthermore, we demonstrate that mainstream backbone RL algorithms cannot simultaneously achieve both critic-free and convergence guarantees in multi-turn scenarios. To address this, we propose SeeUPO (Sequence-level Sequential Update Policy Optimization), a critic-free approach with convergence guarantees for multi-turn interactions. SeeUPO models multi-turn interaction as sequentially executed multi-agent bandit problems. Through turn-by-turn sequential policy updates in reverse execution order, it ensures monotonic improvement and convergence to global optimal solution via backward induction. Experiments on AppWorld and BFCL v4 demonstrate SeeUPO's substantial improvements over existing backbone algorithms: relative gains of 43.3%-54.6% on Qwen3-14B and 24.1%-41.9% on Qwen2.5-14B (averaged across benchmarks), along with superior training stability.

1 Introduction

The paper examines convergence gaps in backbone RL for LLM agents, especially multi-turn interactions, and proposes SeeUPO as a critic-free algorithm with theoretical guarantees. Experiments on AppWorld and BFCL v4 report substantial gains and improved training stability.

  • Motivation: Existing backbone RL algorithms lack established convergence guarantees for agentic scenarios, particularly multi-turn settings.The paper analyzes combinations of advantage estimation and policy update mechanisms to characterize their convergence properties.
  • Experiments: 43.3%–54.6% relative improvements are reported on Qwen3-14B, while 24.1%–41.9% relative improvements are reported on Qwen2.5-14B across AppWorld and BFCL v4.SeeUPO also demonstrates superior training stability compared with existing backbone RL algorithms.
  • Theoretical analysis: The analysis reveals that existing algorithms cannot simultaneously provide critic-free operation and convergence guarantees in multi-turn settings.This identifies the central trade-off addressed by SeeUPO.
  • Method: SeeUPO models multi-turn interactions as sequentially executed multi-agent bandit problems and updates policies in reverse execution order.Reverse-order updates enable backward induction, monotonic improvement, and convergence to a globally optimal solution.

2 Preliminaries

The preliminaries distinguish token-level and sequence-level RL, introduce GAE and GRAE for advantage estimation, and describe REINFORCE and PPU as policy update mechanisms. They also provide Mirror Learning and HAML concepts for analyzing monotonic improvement and convergence.

  • RL modeling: Token-level RL treats each token generation step as an MDP timestep, whereas sequence-level RL treats each complete response or turn as one action.Sequence-level RL reduces single-turn tasks to contextual bandits and represents multi-turn tasks with environmental state transitions.
  • Advantage estimation: GAE uses critic-based temporal-difference errors, while GRAE estimates advantages from each trajectory’s reward relative to a sampled group mean.GAE trades some unbiasedness for lower variance; GRAE is a critic-free approach.
  • Policy updates: REINFORCE directly optimizes expected return with fully on-policy samples, whereas PPU uses clipped importance-weighted objectives and permits multiple updates per batch.PPU constrains policy shifts while operating partially on-policy.
  • Convergence frameworks: Mirror Learning analyzes policy optimization through drift and neighborhood concepts, while HAML extends sequential policy updates to heterogeneous multi-agent settings.HAML coordinates updates to guarantee monotonic joint-return improvement and convergence to Nash equilibrium.

3 Analysis

The analysis shows that convergence depends on the pairing of advantage estimation and policy updates, exposing a multi-turn trade-off between critic-free operation and guarantees. These findings motivate SeeUPO’s sequence-level, reverse-order framework.

  • Multi-turn trade-off: Mainstream algorithms struggle to achieve both critic-free operation and convergence guarantees in multi-turn scenarios.Critic-dependent methods require accurate value estimates, while critic-free methods face clipping bias, undiscounted-setting requirements, or multi-turn credit-assignment bias.
  • Advantage estimation: GAE is unbiased under perfect value-function approximation, while GRAE is biased but has unbiased gradients under undiscounted settings.When the stated conditions are violated, GRAE’s estimator and gradient become biased.
  • Algorithm combinations: GRAE-REINFORCE guarantees gradient unbiasedness, monotonic improvement, and convergence under undiscounted objectives with bounded rewards in finite-horizon MDPs.REINFORCE’s trivial drift and unrestricted neighborhood support the convergence guarantee.
  • Algorithm combinations: GAE-PPU converges to a globally optimal policy under perfect value-function approximation, whereas GRAE-PPU lacks general monotonic-improvement and convergence guarantees.GRAE’s structural bias cannot be eliminated from PPU’s clipped objective, although contextual-bandit exceptions exist without group-variance normalization.
  • Motivation: This limitation motivates a framework designed to combine critic-free operation with convergence guarantees for multi-turn interactions.The paper presents SeeUPO as the response to this theoretical trade-off.

4 Method

SeeUPO reframes multi-turn interaction as sequential multi-agent bandit problems and updates turn policies in reverse execution order. This design supports backward induction, global optimality, critic-free advantage estimation, and practical turn-oriented training.

  • Fundamental Principles: The modeling framework transforms turn-level convergence analysis into agent-level analysis and multi-timestep MDPs into bandit problems.These transformations enable the use of MARL theory and unbiased advantage estimation without value-function estimation.
  • Multi-Agent Modeling: SeeUPO models each interaction turn as a virtual agent in a sequential multi-agent single-turn bandit problem.The sequence-level action is the complete response for that turn, and all turns share a global initial state and team reward.
  • Policy Update: SeeUPO updates policies sequentially in reverse execution order, T → T−1 → · · · → 1, using already-updated subsequent-turn policies.This resolves update conflicts and enables backward induction.
  • Advantage Estimation: The global advantage is estimated directly from sampled rewards in the bandit setting, producing an unbiased estimate without a separate critic.The local advantage computation decomposes the global advantage into turn-specific contributions through subsequent-turn importance ratios.
  • Theoretical Guarantees: Reverse updates inherit monotonic improvement and guarantee convergence to the globally optimal policy through backward induction.Each turn optimizes against the optimal continuation value after later turns have already been updated.
  • Practical Methods: SeeUPPO-GRAE is one practical SeeUPO instantiation, and batch-level advantage normalization improves numerical stability without changing the optimization argmax.SeeUPO organizes samples into turn-level pools rather than whole trajectories or concatenated sliced turns.

5 Experiments

Experiments evaluate SeeUPO on AppWorld and BFCL v4 against mainstream backbone RL algorithms under matched training configurations. SeeUPO achieves stronger performance and stability, while reverse-order updates and batch normalization provide the best empirical results.

  • Experimental Setup: SeeUPO is evaluated on AppWorld and BFCL v4, two multi-turn benchmarks with sparse terminal rewards and multi-step tool interactions.The study uses Qwen2.5-14B-Instruct and Qwen3-14B as policy backbones and compares against PPO, GRPO, and GSPO.
  • Experimental Setup: All algorithms use matched training configurations, including the same sample count and sample reuse within each update step.SeeUPO training uses a 1 × 10^-6 actor learning rate, batch size 32, PPO-style clipping of 0.2, KL penalty 0.002, and 8 rollouts per instance.
  • Main Results: SeeUPO demonstrates substantial performance improvements over existing backbone RL algorithms across both benchmarks and model backbones.Table 2 and Figure 4 report the overall comparison and training dynamics across four benchmark-model scenarios.
  • Training Stability: SeeUPO maintains stable training across all four scenarios, whereas GRPO and GSPO undergo performance collapse for Qwen2.5 with AppWorld.The paper attributes the baseline failure to advantage-estimation bias and missing monotonic-improvement guarantees in multi-turn settings.
  • Update Order: Reverse-order updates outperform natural and random orders on both benchmarks, reaching 63.60% avg@4 and 80.70% pass@4 on AppWorld.Reverse order also reaches 58.00% avg@4 and 65.00% pass@4 on BFCL v4, consistent with the paper’s backward-induction motivation.
  • Advantage Normalization: Batch-level normalization achieves the best overall performance while preserving convergence properties.No normalization gives the lowest empirical performance, whereas batch normalization stabilizes training without breaking the theoretical guarantees.

6 Conclusions

The paper analyzes convergence of backbone RL algorithms and proposes SeeUPO as a critic-free method with multi-turn convergence guarantees. Its theory relies on Mirror Learning and HAML, while acknowledging heterogeneity and modeling assumptions.

  • Conclusions: SeeUPO provides critic-free convergence guarantees for multi-turn agentic RL by modeling interactions as sequentially executed multi-agent bandit problems.Reverse-order policy updates enable backward induction and global optimality.
  • Conclusions: 43.3%–54.6% relative gains on Qwen3-14B and 24.1%–41.9% on Qwen2.5-14B were observed across AppWorld and BFCL v4.The experiments also report superior training stability.
  • Limitations and future work: HAML theoretically requires heterogeneous policies, while the paper argues that large LLM parameter spaces can support turn-level functional heterogeneity despite parameter sharing.Explicit turn-specific parameterization is identified as future work.
  • Limitations and future work: The discussion is grounded in next-token prediction, although sequence-level RL may extend to multi-token prediction and rectified-flow diffusion architectures.These alternative paradigms remain future research directions.
  • Theoretical foundation: Mirror-learning convergence guarantees require the drift function and neighbourhood operator to satisfy properties including nonnegativity, zero gradient, continuity, compactness, and closed-ball conditions.These assumptions define the admissible update structure.
  • Theoretical foundation: Mirror Learning formalizes policy updates through drift functions, neighbourhood operators, and mirror operators.These components support convergence analysis for policy optimization methods.

A.2 Heterogeneous-Agent Mirror Learning

HAML extends Mirror Learning to cooperative multi-agent reinforcement learning through conditional advantage decomposition and sequential policy updates. Under stated regularity conditions, it provides monotonic improvement, value convergence, and Nash-equilibrium guarantees.

  • Framework: HAML extends Mirror Learning to multi-agent settings while preserving monotonic improvement and convergence to Nash equilibria.The framework is used to analyze multi-turn policy updates.
  • Advantage decomposition: HAML virtually decomposes the joint advantage into conditional advantages and sequentially updates each agent according to its contribution to global advantage.The decomposition is virtual, so actual simultaneous or sequential execution does not affect it.
  • Heterogeneous-agent operators: The heterogeneous-agent drift functional captures the update cost for one agent given previously updated agents’ policies.This conditional drift extends the single-agent mirror-learning construction.
  • Update rule and conditions: HAML updates agents sequentially using neighbourhood operators that satisfy continuity, compactness, and closed-ball properties.The update also requires analogous nonnegativity and zero-gradient conditions for the drift functional.
  • Guarantees: Under HAML conditions, expected return is monotonically non-decreasing, value functions converge, and random update orders yield Nash-equilibrium limit points.Every permutation must have positive probability for the Nash-equilibrium result.
  • Advantage estimation: In contextual bandits, GRAE can provide unbiased advantage estimates by using the group mean reward as a baseline.This setting avoids the structural bias that arises in general MDPs.

B Global Optimality of SeeUPO

SeeUPO’s reverse-order sequential updates exploit the fixed execution order and contextual-bandit structure to strengthen conditional optimality into global optimality through backward induction. The proof establishes value convergence and globally optimal policy limit points under explicit regularity assumptions.

  • Global-optimality strategy: SeeUPO models multi-turn interactions as a contextual bandit and updates turns in reverse execution order to enable backward induction.The reverse order is T → T−1 → ··· → 1.
  • Proof structure: The value sequence converges because policy improvement is monotonic and returns are bounded above.This establishes convergence of values before characterizing policy limit points.
  • Proof structure: Each policy limit point satisfies a fixed-point condition for the HAML operator under the subsequent policies already updated in reverse order.Continuity, compactness, and sampling-distribution assumptions support passage to the limiting optimization problem.
  • Backward induction: The terminal turn is globally optimal, and backward induction extends this result from turn T to all earlier turns.The argument uses the optimal continuation value and dropping-the-drift reasoning.
  • Theorem: All policy-sequence limit points are globally optimal under reverse-order updates.The theorem assumes bounded rewards, compact policy space, and valid drift and neighbourhood operators.
  • Scope of guarantee: Non-reverse fixed orders may retain monotonic improvement but do not receive the same global-optimality guarantee.Their continuation policies are generally not optimal, so fixed-point optimality remains conditional.
  • Practical instantiation: The guarantee depends on unbiased advantage estimation, which GRAE supplies in SeeUPO’s contextual-bandit setting.SeeUPPO-GRAE combines HAML-compliant clipped updates with group-mean-baseline estimation.

C Bias of GAE

The GAE analysis shows that advantage-estimation bias depends on value-function error, discounting, and λ. GRAE is structurally biased in general MDPs, although its policy-gradient estimator is unbiased for undiscounted objectives and contextual bandits are a special case.

  • Bias bound: GAE bias is bounded by (1+γ−2γλ)/(1−γλ) · ϵmax, where ϵmax is the maximum value-estimation error.Perfect value estimation makes the bound zero.
  • Bias properties: GAE is unbiased under perfect value-function estimation, while its bias scales linearly with estimation error.Reducing value approximation error directly reduces advantage-estimation bias.
  • Bias properties: Larger λ values reduce GAE’s sensitivity to value-estimation errors, whereas larger γ generally increases susceptibility to bias.The coefficient approaches 1 as λ approaches 1 and generally increases with γ.
  • GRAE in MDPs: GRAE is structurally biased in general MDPs because its group-mean baseline estimates V(s0) rather than the state-dependent value V(st).The resulting bias is V(st) − V(s0), which is generally nonzero.
  • GRAE gradients: GRAE’s policy-gradient estimator is unbiased for the undiscounted objective but biased when γ < 1.The structural advantage bias does not necessarily bias the undiscounted policy gradient because the residual is action-independent.
  • Contextual bandits: Contextual bandits are a special case in which GRAE becomes unbiased.This property underlies its use in SeeUPO’s sequence-level contextual-bandit formulation.

D.3 Proof of GRAE Gradient Bias When γ̸ = 1

When γ < 1, GRAE's total-return gradient estimator is generally biased because future rewards receive action-dependent coefficients. This bias compounds multi-turn credit-assignment and structural-bias problems.

  • When γ < 1, the GRAE gradient estimator based on total return is biased in general.The undiscounted case γ = 1 is the exception identified in the analysis.
  • The non-baseline component depends on future rewards and has positive coefficients (1 −γ^k), yielding a generally nonzero expected gradient contribution.The past-dependent sum can be treated as a baseline given the current state.
  • In multi-turn settings, GRAE's group mean from initial state s0 creates credit-assignment issues for later-turn states.The cited discussion identifies this as a distinct challenge beyond discounting bias.
  • The structural bias |V(s_t) −V(s_0)| grows with the number of turns, while discounting bias compounds these problems when γ < 1.
  • REINFORCE can be analyzed through Mirror Learning, where its gradient-ascent update approximately solves a Generalized Policy Iteration step.The policy gradient is weighted by the current policy's state-visitation distribution.

E.2 Convergence Theorem

Under an undiscounted objective, GRAE-REINFORCE has an unbiased gradient and inherits Mirror Learning's monotonic-improvement and convergence framework. PPU likewise fits that framework through a clipping-derived drift function and a valid neighborhood operator.

  • Under γ = 1, the GRAE gradient estimator is unbiased and equals the policy gradient in expectation.This follows from baseline invariance.
  • REINFORCE's Mirror Learning representation supports monotonic improvement and convergence under the theorem's finite-horizon, bounded-reward assumptions.
  • PPU's clipping objective induces a nontrivial drift function, while its neighborhood operator N = Π satisfies continuity, compactness, and the closed-ball property.

F.2 Convergence Theorem

GAE-PPU achieves the stated convergence guarantee only with a perfect value function approximation. Under that assumption, GAE is unbiased and PPU's Mirror Learning conditions support monotonic improvement and convergence.

  • GAE-PPU's convergence theorem assumes a perfect value function approximation, V_ϕ = V^π.The assumptions also include bounded rewards and a compact parameter space.
  • With perfect value estimation, GAE's advantage estimator is unbiased: E[Â^GAE_t | s_t, a_t] = A^π(s_t, a_t).
  • PPU is represented in Mirror Learning with a clipping-derived drift function and the trivial neighborhood N = Π.
  • The resulting drift satisfies nonnegativity and zero-gradient properties required for the monotonic-improvement and convergence argument.
  • In general MDPs, GRAE introduces structural bias Δ(s_t) = V(s_t) −V(s_0) that does not vanish as sample size increases.The large-sample bias equals V(s_t) −V(s_0).

G.2 Convergence Failure Theorem

GRAE-PPU fails to retain convergence guarantees in general MDPs because structural bias breaks the required drift properties and can reverse clipped policy updates. In contextual bandits, the single-state structure removes this bias and restores the framework's conditions.

  • Convergence Failure Theorem: GRAE-PPU's structural bias causes violations of zero-at-origin and drift-nonnegativity properties required by Mirror Learning.The bias is Δ(s_t) = V(s_t) −V(s_0).
  • Convergence Failure Theorem: The broken drift conditions invalidate the monotonic-improvement proof and provide no guarantee against policy degradation.
  • Convergence Failure Theorem: In the two-state example, GRAE changes advantages from −5 to +5 for the bad action, reversing PPU's clipping direction.The true update decreases its probability, whereas the GRAE update increases it.
  • Convergence Failure Theorem: Under GRAE advantages, PPU can increase the bad action's probability to approximately 1.2 · π_old, although its true advantage is −5.The optimal direction would instead yield approximately 0.8 · π_old.
  • Convergence in Contextual Bandits: In contextual bandits, GRAE is unbiased because there is only one state, and GRAE-PPU's drift matches standard PPU's drift.The resulting drift satisfies the properties used for convergence.

H.3.1 GSPO Drift Function Derivation and Properties

The GSPO drift function satisfies the convergence-required nonnegativity and zero-gradient properties if and only if the state-dependent normalization factor δ(s) is identically 1. Because empirical group reward variability generally makes δ(s) vary across queries, variance normalization can break convergence guarantees, unlike batch-level normalization.

  • GSPO Drift Function Properties: State-dependent variance normalization breaks convergence guarantees when empirical reward variability makes δ(s) differ across queries.The normalization factor depends on the query state and can violate the drift properties required for monotonic improvement.
  • GSPO Drift Function Properties: δ(s) ≡1 is necessary and sufficient for the GSPO drift function to satisfy both nonnegativity and zero-gradient properties.The result combines separate lemmas establishing nonnegativity equivalence and zero-gradient sufficiency.
  • GSPO Drift Function Properties: When δ(s) ≠1, the drift function can become negative for some advantage and policy-ratio combinations, so monotonic improvement is no longer guaranteed.The proof can then establish only a lower bound involving a negative quantity rather than V_π̄(s) ≥ V_πold(s) for every state.
  • Batch-Level Normalization: Batch-level normalization preserves the optimal policy because its fixed batch-wide mean and standard deviation do not change the objective argmax.The resulting PPU drift functional remains unchanged, and the same invariance extends to sequential multi-agent updates.
  • Batch-Level Normalization: Group-level normalization differs from batch-level normalization because δ(s) varies across queries, whereas batch normalization applies identical constants to every sample.This distinction explains why batch-level normalization preserves drift properties while group-level normalization can break them.
Loading 2602.06554v1…