TIGPO：用于长视域LLM智能体的时间实例图策略优化

# 时序实例图策略优化：面向长期LLM智能体  
来源：https://arxiv.org/html/2609.03383  
金伟威  
隶属机构：计算机科学系  
隶属单位：南京大学  
电子邮箱：[[email protected]](mailto:[email protected])  

###### 摘要  
基于图的策略优化通过将执行轨迹组织为状态转移图，改善了长期LLM智能体的奖励分配问题。然而，现有方法在每个策略更新中独立构建图，丢弃了早期策略发现的转移，并将优势估计限制在小批量、局部执行组内。我们提出*时序实例图策略优化*（TIGPO），该方法将基于图的奖励分配扩展到跨策略更新的维度。TIGPO为每个任务维护一个持久的转移图，允许不同策略版本发现的有效转移共同确定当前执行的奖励分配。为积极将当前探索与历史经验重新连接，TIGPO在固定的执行预算中分配“探索槽”用于常规任务采样，以及“重访槽”用于延迟重试先前探索过的任务。每次重访时，TIGPO将当前执行组与对应的早期探索组配对，构建跨时序参考。扩大的参考集旨在小执行组下稳定相对优势估计，而基于同一任务的直接比较则能捕捉训练阶段间的策略改进。历史转移和分数仅作为结构化且分离的统计参考，永远不会在策略损失中重新回放。在ALFWorld和WebShop上的实验表明，TIGPO持续优于先前的基于组和基于图的策略优化方法。  

## 1 引言  
大语言模型（LLM）已从静态文本生成器迅速演进为能够感知环境状态、基于观察进行推理并执行动作以完成复杂目标的交互式智能体（Yao等，2023）。代表性应用包括在模拟家庭环境中运行的具身智能体（Shridhar等，2021）和在电商环境中导航的网页智能体（Yao等，2022）。与单轮推理不同，这些任务要求智能体在长交互时序中做出一系列相互依赖的决策。奖励通常稀疏且延迟，仅在整个轨迹完成后才能确定成功与否。因此，为单个动作分配奖励仍然是LLM智能体强化学习（RL）的核心挑战。  

传统的Actor-Critic算法（如近端策略优化PPO）使用学习到的价值函数来估计动作优势（Schulman等，2017）。更近期的组相对策略优化（GRPO）则通过从采样输出组中估计相对优势，提供了一种无需价值函数的替代方案（Shao等，2024）。这种基于组的范式随后被扩展到长期智能体任务。GiGPO引入了情节级和锚点状态级的组，以获得更细粒度的相对优势（Feng等，2025）。GraphGPO更进一步，将执行转移聚合为状态转移图，并根据从中间状态到任务目标的图距离分配步级奖励（Cheng等，2026）。这些进展显著改善了细粒度奖励分配，且无需额外学习的价值模型。  

尽管取得了这些进展，现有的基于图的奖励分配仍然是*批内局部*的。在每次策略更新中，转移图仅从当前执行批次中采样的轨迹构建，并在之后丢弃。因此，在训练不同阶段发现的有效转移无法被连接。例如，一个早期策略可能发现了一个有希望的前缀但在达到目标前失败，而后期策略可能从重叠状态发现了成功的延续。如果这两个轨迹片段发生在不同的策略更新中，批内局部图无法恢复它们的连通性或通过生成的路径传播奖励。这一限制在小执行组下尤为明显，此时图覆盖稀疏，相对优势估计可能对单个成功或失败的轨迹敏感。  

一个看似直接的解决方案是保留历史轨迹并在后续更新中回放。然而，由早期策略生成的轨迹包含过时的动作和对数概率。直接将它们包含在当前策略损失中可能会引入分布不匹配。历史经验应改善对当前策略执行的奖励分配，而非自身接收梯度。这促使了本文的核心问题：  
> *基于图的奖励分配能否在跨策略更新积累经验的同时，保持在当前策略轨迹上的优化？*  

为回答这个问题，我们提出了*时序实例图策略优化*（TIGPO）。TIGPO维护一个按稳定任务ID索引的持久转移图。在每次策略更新期间，与同一任务相关的历史有效转移会与当前执行的转移组合，然后重新计算到目标的距离和基于图的优势。这使得不同策略版本发现的轨迹片段能够形成通向成功的完整路径，并为当前行为提供更密集的奖励信号。重要的是，历史转移仅作为结构参考使用：历史词元、动作和对数概率永远不会被包含在当前策略损失中。  

仅维护持久图并不能保证策略会返回先前探索过的任务。因此，TIGPO引入了“探索-重访”执行调度，将固定的组任务预算分配给常规探索和计划性重访。探索槽遵循原始任务采样器，而重访槽则在受控延迟后使用当前策略重新尝试先前探索过的任务。这些重访主动将当前探索与历史图结构重新连接，使策略能够在不增加每次更新执行预算的情况下扩展或完成早期更新发现的路径。计划性重访还提供了任务匹配的跨时序比较。对于每个重访组，TIGPO将其当前情节衍生分数与对应的早期探索组的分离分数结合。由此产生的扩大参考集旨在小执行组下稳定相对优势估计。同时，比较同一任务的两个策略阶段提供了策略改进的直接信号。只有当前重访轨迹接收梯度；早期分数仅作为分离的参考统计。  

我们在两个具有挑战性的长期智能体基准测试上评估TIGPO：ALFWorld和WebShop。在两个环境中，TIGPO始终优于先前的基于组和基于图的策略优化方法。这些结果表明，持久实例图、受控历史重访和跨时序组比较为长期奖励分配提供了互补的益处。  

我们的主要贡献总结如下：  
- • 我们引入了*跨更新持久实例图*，它连接了不同策略版本发现的有效转移，并改善了当前执行的步级奖励分配，而无需在策略损失中回放历史轨迹。  
- • 我们提出了一种*探索-重访执行调度器*，在固定执行预算下平衡常规任务探索与延迟的、特定任务的重访，使当前策略能够主动重用和扩展历史图结构。  
- • 我们开发了一种*跨时序比较机制*，将早期探索组的分离分数与对应的当前重访组配对。它提供了一个扩大的参考集，旨在稳定相对优势估计，同时捕捉训练阶段间的策略改进。  

## 2 相关工作  
#### 面向LLM智能体的强化学习。  
LLM越来越多地被用作交互式智能体，在外部环境中对观察进行推理并执行动作。ReAct（Yao等，2023）建立了一般的推理-行动范式，而ALFWorld（Shridhar等，2021）和WebShop（Yao等，2022）为具身和网页智能体提供了代表性基准测试。它们的长期交互时序和稀疏结果奖励使得细粒度奖励分配极具挑战性。PPO（Schulman等，2017）使用学习到的价值函数估计动作优势，而GRPO（Shao等，2024）则用组内奖励归一化替代了Critic。GiGPO（Feng等，2025）为智能体训练引入了情节级和锚点状态级的组，GraphGPO（Cheng等，2026）从当前执行批次构建的状态转移图中推导步级奖励。相比之下，TIGPO共同引入了持久的任务条件图记忆、计划性任务重访和跨时序比较，允许在不同策略阶段收集的经验改善对当前动作的奖励分配。  

#### 历史经验重用。  
经验回放通过保留和重新采样过去的转移来提高样本效率（Schaul等，2016），但在早期策略生成的轨迹上直接优化会引入策略外不匹配，可能需要显式校正（Espeholt等，2018）。TIGPO不会在策略目标中回放历史轨迹。历史转移仅作为图结构保留，而早期的执行分数作为分离的参考统计。所有接收梯度的轨迹均由当前策略新生成。因此，TIGPO重用了历史结构和统计，而不会在过时的动作或对数概率上执行策略更新。  

## 3 预备知识  
#### 基于组的策略优化。  
设 \(x \sim \mathcal{D}\) 表示定义有限时域马尔可夫决策过程 \(\mathcal{M}_x = (\mathcal{S}_x, \mathcal{A}_x, P_x, r_x)\) 的任务实例。在步骤 \(t\)，LLM策略 \(\pi_\theta\) 根据交互历史 \(h_{i,t}\) 采样动作 \(a_{i,t}\)，并观察下一个状态 \(s_{i,t+1}\)。一条执行 \(\tau_i = (s_{i,0}, a_{i,0}, \ldots, s_{i,T_i})\) 获得一个情节结果 \(R_i\)。在每次策略更新中，基于组的策略优化采样 \(B\) 个任务实例，并为每个任务生成 \(K\) 条执行，总执行预算为 \(N = BK\)。同一任务的 \(K\) 条执行形成一个*任务组*。对于任务 \(x\)，令 \(\mathcal{B}_x = \{\tau_i\}_{i=1}^K\) 和 \(\mathcal{Z}_x = \{R_i\}_{i=1}^K\) 分别表示其执行组和结果分数。GRPO（Shao等，2024）为每条执行分配一个组内情节优势：
\[
\widehat{A}^{\mathrm{ep}}_i = \operatorname{Norm}(R_i; \mathcal{Z}_x), \qquad \operatorname{Norm}(z; \mathcal{Z}) = \frac{z - \mu(\mathcal{Z})}{\sigma(\mathcal{Z}) + \epsilon},
\]
其中 \(\epsilon > 0\) 确保数值稳定性。一个执行中的所有动作继承相同的情节级优势。  

#### 基于图的步级奖励。  
GraphGPO（Cheng等，2026）进一步将任务 \(x\) 的执行转移聚合为一个有向状态转移图 \(G_x = (V_x, E_x)\)，其中相同状态被合并，有效转移形成有向边。令 \(g_x\) 为成功终端节点，\(d_{G_x}(s, g_x)\) 为从状态 \(s\) 到成功的最短路径距离。对于转移 \(s_{i,t} \xrightarrow{a_{i,t}} s_{i,t+1}\)，其图回报为：
\[
Q^{G}_{i,t} = C \gamma^{d_{G_x}(s_{i,t+1}, g_x)}, \qquad 0 < \gamma < 1.
\]
使用后继状态是因为它代表了当前动作的直接结果；因此，导致更接近成功的转移会获得更大的回报。共享相同源状态的转移的回报被归一化以获得步级图优势 \(\widehat{A}^{G}_{i,t}\)。GraphGPO然后将情节级和步级信号结合为：
\[
\widehat{A}_{i,t} = \lambda_{\mathrm{step}} \widehat{A}^{G}_{i,t} + \lambda_{\mathrm{ep}} \widehat{A}^{\mathrm{ep}}_i.
\]
上述图和比较统计均由当前执行组构建。因此，在一次策略更新中发现的转移结构无法为后续的相同任务尝试提供信息。TIGPO通过跨策略更新携带任务级图结构和比较信息来解决这一限制。  

## 4 方法  
图1：时序实例图策略优化（TIGPO）概览。(A) 在每次策略更新时，固定的 \(B\) 个任务组预算被划分为探索槽和重访槽，为每个任务生成 \(K\) 条新执行。(B) 执行转移被聚合成每个任务的图。对于被重访的任务，检索其历史图并与当前执行图组合，允许先前发现的转移提供通往目标的更短路径。(C) 更新后的时序图提供步级图奖励，而配对的探索和重访结果提供跨时序的情节优势。历史经验影响奖励分配，而策略目标仅在当前策略执行上优化。  

标准的基于组的策略优化仅从当前执行批次构建监督。因此，有用的转移结构在每次更新后被丢弃，而对相同任务的重复尝试被独立评估。我们提出*时序实例图策略优化*（TIGPO），它使用每个任务的累积历史来改善对当前策略执行的奖励分配，同时保持策略内优化。图1总结了该方法。如图1(A)所示，TIGPO将固定的 \(B\) 个任务组预算划分为探索槽和重访槽，为每个任务生成 \(K\) 条新执行。探索采样新的任务尝试，而重访则让当前策略返回先前尝试过的任务，而不增加总执行预算 \(BK\)。在图1(B)中，对于被重访的任务，其历史转移图与当前执行图组合，从而能够通过更短的路径到达目标。图1(C)展示了TIGPO如何利用跨时序比较：重访组的当前分数与早期探索组的分数配对，为相对优势估计提供更稳定的参考。