see-upo-sequence-level-rl

name	see-upo-sequence-level-rl
title	SeeUPO: Sequence-Level Agentic-RL with Convergence Guarantees
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2602.06554
keywords	["Agentic RL","Multi-turn Agents","Convergence Guarantees","Critic-Free","Backward Induction"]
description	Train multi-turn AI agents with convergence guarantees using sequential backward-induction updates, eliminating the need for separate critic networks while maintaining theoretical optimality. Use for long-horizon agentic reasoning where monotonic improvement and global optimality are required.

SeeUPO: Backward-Induction RL for Multi-Turn Agents

Multi-turn agent training presents a fundamental challenge: existing RL methods cannot simultaneously achieve critic-free operation (no separate value function) and convergence guarantees in sequential decision settings. Standard on-policy methods like PPO apply advantage estimation at every timestep independently, but multi-turn interactions require coordinating updates across timesteps where later decisions depend on earlier ones.

SeeUPO solves this by reframing multi-turn interaction as sequential bandit problems and applying backward induction—a classical technique from game theory. By updating turns in reverse execution order (last turn → first turn), the method ensures each turn optimizes against the true optimal continuation value of subsequent turns, enabling global optimality convergence without a learned value function.

Core Concept

Standard RL updates policy parameters simultaneously across all timesteps: ∇J = E[∇ log π(a_t|s_t) · Â_t]

This works well for single-step decisions but creates misalignment in sequential settings. When updating turn t, turns t+1...T have not yet been optimized, so the true continuation value is unknown. A critic attempts to approximate it, but critic errors compound across turns.

SeeUPO inverts this: update turns from T→1. When updating turn t:

• All turns t+1...T are already optimal (updated previously)
• The continuation value is known exactly: V_t^* = max_a E[R_{t:T}|a_t]
• Turn t optimizes against true optimal continuation, not estimated value

This sequential coordination enables monotonic improvement and convergence to globally optimal policies.

Architecture Overview

• Backward Induction Setup: Structure agent trajectories as sequence of T turns, where each turn is a decision point
• Per-Turn Policy: Each turn has its own policy π_t(a|s_t); updates occur sequentially from t=T→1
• GRAE Advantages: Use Group Relative Advantage Estimation (critic-free) for per-turn advantage computation
• Sequential Updates: Update turn t using advantages computed relative to turn t's group rollouts, knowing turns t+1:T are optimal
• Convergence Mechanism: Backward induction ensures monotonic improvement; each update improves the full trajectory, not just isolated decisions

Implementation

The implementation requires three components: trajectory structuring, backward-induction updates, and advantage estimation.

First, structure your multi-turn trajectories for backward induction:

import torch
 torch.nn  nn

 :
    

     ():
        
        .states = states
        .actions = actions
        .rewards = rewards
        .log_probs = log_probs
        .num_turns = num_turns
        .returns = ._compute_returns()

     ():
        
        returns = []
        cumulative = 
         r  (.rewards):
            cumulative = r +  * cumulative
            returns.append(cumulative)
         ((returns))

     ():
        
         {
            : .states[t],
            : .actions[t],
            : .log_probs[t],
            : .returns[t]  t < (.returns)  
        }