PaperlayerView exact revision on arXiv

Source-linked AI summary

One Act, Many Masks: Effect-Marginal Policy Optimization for Long-Horizon Agents

Shaojin Ma, Ruitao Wang, Pengyi Li, Jie Yang, Liangyu Chen, Gangyi Zhao, Hongyao Tang, Yan Zheng, Jianye Hao

arXiv:2610.29427v1cs.LGstat.ML

TL;DR

Response-wise policy ratios can update textual responses differently even when they induce the same executable effect, leaving credit–update misalignment. EMPO shares effect-level policy ratios while preserving original credit signals, and consistently improves task performance and learning efficiency across the evaluated environments, model scales, and advantage estimators.

  • Problem

    Response-wise probability ratios can translate credit differently for textual responses that induce the same executable effect, creating credit–update misalignment.

    Source: §1 · pp. 1–2

  • Method

    EMPO shares length-normalized policy ratios across locally comparable responses with the same executable effect while preserving the base algorithm’s advantages.

    Source: §1 · p. 2

  • Results

    EMPO consistently improves task performance and learning efficiency across ALFWorld, WebShop, and Sokoban, different model scales, and advantage estimators.

    Source: §6 · p. 9

  • Takeaways & Limitations

    Effect-level ratio sharing changes within-cell gradient coupling and realized policy updates while retaining the supplied credit signals.

    Source: §1 · p. 2, §5.4 · p. 9

    Effect-cell construction may require more care for less structured tool interfaces, and responses outside eligible cells retain the base objective.

    Source: B LIMITATIONS · p. 13

Abstract

from arXiv · show

Recent advances in multi-turn reinforcement learning (RL) have substantially improved the performance of LLM agents on complex, long-horizon interactive tasks. However, despite progress in fine-grained credit assignment, policy optimization still applies these learning signals through response-specific probability ratios. Different textual responses can induce the same executable effect, yet credit differences arising from subsequent outcomes remain tied to their individual textual realizations. We identify this mismatch as credit-update misalignment. Our analysis reveals that credit-text pairing directly shapes policy-update directions, even when the policy context and executable effect are held fixed. Motivated by this finding, we propose Effect-Marginal Policy Optimization (EMPO), which aligns policy optimization with execution-level equivalence through an effect-level surrogate that couples updates across alternative textual realizations. EMPO preserves the original credit signals, integrates with both trajectory-level and step-level credit estimators, and requires no additional critics or rollouts. Experiments on ALFWorld, WebShop, and Sokoban show that EMPO outperforms strong baselines in both task performance and learning efficiency.

1 INTRODUCTION

Long-horizon LLM agents use RL, but response-wise probability ratios can produce different updates for textual responses that induce the same environment-level decision. EMPO shares policy ratios across execution-equivalent responses while preserving their original advantages, and improves task performance across the evaluated environments and model scales.

1 INTRODUCTION

  • Long-horizon LLM agents repeatedly perceive, reason, and act under partial observability, sparse feedback, and delayed rewards, making RL an important post-training paradigm.Source: §1 · p. 1
  • Credit–update misalignment is the mismatch between execution-level equivalence and realization-specific credit–gradient pairing in response-wise optimization.The within-effect covariance term captures how supplied credit pairs with realization-specific response scores, distinct from the quality of the credit estimator.Source: §1 · p. 2
  • EMPO shares policy ratios across locally comparable responses with the same executable effect while retaining each response’s original advantage.It uses existing rollout data and requires no additional critic, auxiliary model, reward model, or environment interaction.Source: §1 · p. 2
  • Across ALFWorld, WebShop, and Sokoban, EMPO improves overall task performance across environments and model scales with GRPO and GiGPO.The evaluation covers trajectory-level and step-level credit estimation.Source: §1 · pp. 2–3

2 RELATED WORK

Related work develops RL for interactive LLM agents and improves how credit is estimated or refined in long-horizon tasks. This paper studies a complementary policy-update problem: translating existing credit into updates when textual responses share an executable effect.

2 RELATED WORK

  • Prior work extends LLM-agent RL to interactive environments, including search, web interaction, tool use, and software-engineering tasks.Other work addresses multi-turn exploration and training stability.Source: §2 · p. 3
  • Long-horizon credit methods densify, localize, or calibrate supervision through process-level signals, trajectory comparisons, graphs, trees, and canonical actions.Examples include GiGPO, HGPO, SALT, Tree-GRPO, GraphGPO, ECPO, and GACA.Source: §2 · p. 3
  • Unlike methods focused on what credit is assigned or how it is estimated, EMPO changes how existing credit becomes policy updates for responses sharing an executable effect.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries describe an LLM agent’s interaction loop and group-based policy optimization. The paper’s overview places EMPO at the policy-update stage, sharing updates across execution-equivalent responses while retaining base-algorithm credit estimates.

3 PRELIMINARIES

  • At each step, an agent generates a textual response from its task and interaction context, an interface maps it to an action, and the environment returns a reward and next observation.The interaction may be modeled as an MDP or POMDP, without requiring access to the underlying state.Source: §3 · p. 3
  • EMPO groups locally comparable responses with the same canonical execution effect and aggregates their policy ratios into a shared effect ratio combined with the original advantages.Source: Figure 2 · p. 4
  • Group-based methods sample multiple trajectories per task and estimate relative advantages from the rollout group; EMPO leaves that estimator and the rollout procedure unchanged.Source: §3 · p. 4

4 EFFECT-MARGINAL POLICY OPTIMIZATION

EMPO reorganizes policy updates around executable effects rather than individual textual responses, while retaining the base algorithm’s credit estimates. It derives an effect-conditioned policy direction and implements it through a PPO-style objective.

4 EFFECT-MARGINAL POLICY OPTIMIZATION

  • EMPO operates at the policy-update stage, organizing probability changes across execution-equivalent responses while preserving the base algorithm’s credit estimates.It is designed to leave the underlying credit estimator unchanged.Source: §4 · p. 4, §4.2 · p. 5

4.1 CREDIT–UPDATE MISALIGNMENT

  • Credit–update misalignment arises because response-wise updates pair each supplied advantage with its realization-specific policy direction, including their within-group covariance.The local group contains responses with comparable contexts and the same executed effect.Source: §4.1 · pp. 4–5

4.2 EFFECT-CONDITIONED POLICY DIRECTION

  • An executable effect’s policy direction is jointly determined by alternative textual realizations, motivating a mean direction and cross-response combinations within the same context–effect group.EMPO retains the advantages supplied by the base algorithm.Source: §4.2 · p. 5

4.3 EFFECT-MARGINAL POLICY OBJECTIVE

  • The objective groups valid, comparable-context responses with the same effect, averages length-normalized ratios in eligible cells, retains individual advantages, and leaves other responses on their original token-level ratios.Only cells with at least two responses are eligible for aggregation; EMPO needs no additional environment interaction, critic, or auxiliary model.Source: §4.3 · pp. 5–6

5 EXPERIMENTS

Experiments evaluate EMPO across three long-horizon benchmarks, multiple model scales, and trajectory- and step-level credit estimators. EMPO improves task performance and learning efficiency, while ablations and policy-update analyses examine its components and effects.

5.1 EXPERIMENTAL SETUP

  • The evaluation covers ALFWorld, WebShop, and Sokoban, comparing EMPO-G and EMPO-GiG against baselines with two base algorithms and different credit-estimation granularities.The experiments use Qwen2.5-1.5B and 7B for ALFWorld and WebShop, and Qwen2.5-VL-3B for Sokoban.Source: §5.1 · p. 6

5.2 TASK PERFORMANCE AND LEARNING EFFICIENCY

  • Across ALFWorld, WebShop, and Sokoban, EMPO improves task performance across model scales and trajectory- and step-level estimators.On Qwen2.5-VL-3B-Instruct Sokoban, EMPO-G raises success from 72.7% to 84.4%, and EMPO-GiG from 75.0% to 81.3%.Source: Table 1 · p. 7, Table 2 · p. 7, §5.2 · pp. 7–8
  • Across all eight evaluated model–algorithm–environment settings, EMPO reduces TTT60, with the largest reduction reaching 36.5%.TTT60 is the training steps required to first reach a 60% success rate.Source: Table 3 · p. 7, §5.2 · p. 8

5.4 POLICY-UPDATE ANALYSIS

  • After ratio sharing, gradients within the same effect cell show clearer coupling, and EMPO-GiG has lower within-cell dispersion after a controlled policy step.Figure 3 compares response-level objective-gradient cosine similarities and reports within-cell dispersion of log-probability changes.Source: Figure 3 · p. 8, §5.4 · p. 9

5.3 ABLATION STUDY

  • Length normalization calibrates policy changes, effect-based grouping sets the coupling structure, and ratio sharing coordinates updates within each effect cell.Removing length normalization increases sensitivity to response length; arbitrary groups introduce interference between updates associated with different effects.Source: §5.3 · p. 8, Table 4 · p. 8

5.5 EFFECT-CELL STATISTICS

  • Eligible-cell response coverage rises from 64.6% to 79.5% on ALFWorld and 43.9% to 63.0% on Sokoban; WebShop reaches 25.3% mid-training and 23.4% late.The size distributions also include cells containing more than two responses.Source: §5.5 · p. 9, Figure 4 · p. 9

6 CONCLUSION

EMPO addresses credit–update misalignment by sharing length-normalized policy ratios across locally comparable responses with the same executable effect while preserving base-algorithm advantages. The conclusion reports improved task performance and learning efficiency across environments, model scales, and advantage estimators.

6 CONCLUSION

  • EMPO consistently improves task performance and learning efficiency across ALFWorld, WebShop, and Sokoban, different model scales, and advantage estimators.Further analysis reports more structured within-cell gradient coupling and more coordinated policy updates among execution-equivalent responses.Source: §6 · p. 9

A ALGORITHM

  • Training collects grouped trajectories and rewards, computes original response advantages, and identifies eligible effect cells using matched contexts and canonical effects.Source: A ALGORITHM · p. 13
  • For eligible cells, EMPO shares ratios across responses, computes its objective with unchanged advantages, and updates parameters with the base optimizer.Source: A ALGORITHM · p. 13

B LIMITATIONS

EMPO depends on identifying comparable interaction contexts and canonical executable effects, which are readily available in the structured-action environments considered. Effect-cell coverage varies, and responses outside eligible cells retain the base objective.

B LIMITATIONS

  • EMPO relies on identifying comparable interaction contexts and canonical executable effects, readily available in the structured-action environments considered.Source: B LIMITATIONS · p. 13
  • Effect-cell coverage varies across tasks and training stages because cells are formed from sampled responses.Source: B LIMITATIONS · p. 13
  • Responses outside eligible effect cells retain the base objective; extending construction and evaluation to more agent interfaces is future work.Source: B LIMITATIONS · p. 13

C THEORETICAL PROOFS

The proofs hold sampled responses, advantages, response lengths, and cell memberships fixed during differentiation. They examine effect-policy identities and local factorization, conditional variance, and the relationship between shared-ratio and advantage-aggregation objectives.

C THEORETICAL PROOFS

  • The derivations hold sampled responses, advantages, response lengths, and cell memberships fixed during differentiation.Source: C THEORETICAL PROOFS · p. 13

C.1 EFFECT-POLICY IDENTITIES AND LOCAL FACTORIZATION

  • The effect-score identity assumes the execution mapping is independent of policy parameters; the proofs also characterize the response-wise ratio gradient at the old-policy point.Source: §C.1 · pp. 13–14
  • The local factorization relates response-wise and shared-ratio surrogates through a within-cell covariance term coupling advantages and response scores.Source: §C.1 · p. 14

C.2 CONDITIONAL VARIANCE

  • The conditional-variance analysis considers conditionally independent responses and more general conditional covariance between advantages and scores, given a context–effect key.Source: §C.2 · pp. 14–15

C.3 RELATION TO ADVANTAGE AGGREGATION

  • With equal response weights and no clipping, shared-ratio and cell-mean-advantage aggregation coincide; PPO clipping can break that equivalence.Source: §C.3 · p. 15

D EXPERIMENTAL DETAILS

  • The experimental-details section introduces supplementary information on baselines, environments, and training configurations.Source: D EXPERIMENTAL DETAILS · p. 15

D.1 BASELINES

  • The listed baselines include actor–critic PPO, critic-free RLOO and GRPO, and GiGPO, which adds a step-level relative advantage to a trajectory-level one.Source: §D.1 · pp. 15–16

D.2 ENVIRONMENTS

  • The environments span household tasks in ALFWorld, simulated shopping in WebShop, and procedurally generated Sokoban boards with one box and a 15-interaction limit.Source: §D.2 · p. 16

D.3 TRAINING METRICS

The training metrics track optimization signals, policy deviation and diversity, task progress, and gradient scale.

D.3 TRAINING METRICS

  • The clipped policy-gradient loss reflects the optimization signal through estimated advantages, policy ratios, and clipping behavior.Source: §D.3 · p. 16
  • Token-level KL divergence tracks deviation from the fixed reference policy, while token entropy measures diversity in the token-level policy.Source: §D.3 · p. 16
  • Policy-ratio clip fraction measures how often likelihood ratios fall outside the PPO clipping interval; for EMPO it uses effective ratios.Source: §D.3 · p. 16
  • Rollout-batch reward and success rate track on-policy task progress, while gradient norm records actor-gradient scale before clipping.Source: §D.3 · p. 16

D.4 TRAINING DETAILS

The experiments compare training behavior, credit–direction covariance, and EMPO against advantage-side aggregation, alongside implementation and computing details. EMPO outperforms the aggregation variant in all reported settings.

D.4 TRAINING DETAILS

  • Experiments use Qwen2.5 models for ALFWorld and WebShop and Qwen2.5-VL-3B-Instruct for Sokoban, with 150 training iterations and evaluation every five iterations.The setup also specifies AdamW, rollout and evaluation temperatures, response length, and group size.Source: §D.4 · p. 17

D.5 COMPUTING RESOURCES

  • Experiments run on eight NVIDIA H100 GPUs, and EMPO uses the same actor model and environment rollouts as its corresponding base algorithm.Training uses verl-agent, PyTorch FSDP, and vLLM; optimizer-state offloading is enabled for 7B experiments.Source: §D.5 · p. 17

E.2 MAGNITUDE OF CREDIT–DIRECTION COVARIANCE

  • Within-effect covariance remains comparable in magnitude to the conventional response-wise update across analyzed ALFWorld cells under both GRPO and GiGPO.The covariance term captures sample-specific pairing between supplied credit and realization-specific policy directions.Source: §E.2 · p. 17, Figure 8 · p. 19

E.1 LEARNING CURVES

  • Training curves show EMPO generally reaches stronger policies earlier and maintains favorable learning progress across ALFWorld, WebShop, and Sokoban.These curves correspond to the TTT60 results reported in Table 3.Source: §E.1 · p. 17, Figure 5 · p. 18

E.3 COMPARISON WITH ADVANTAGE AGGREGATION

  • EMPO achieves higher performance than advantage-side aggregation in all reported settings, with a more pronounced difference for GiGPO on WebShop.The advantage-side variant remains competitive; the results reflect differences under clipping and practical loss weighting.Source: Table 6 · p. 18, §E.3 · p. 18

E.4 POLICY ADAPTATION AND RESPONSE DIVERSITY

Across ALFWorld and WebShop, EMPO retains higher later-stage token entropy while policy movement continues. Environment-specific prompt templates specify the task, action space, interaction history, and output format.

E.4 POLICY ADAPTATION AND RESPONSE DIVERSITY

  • EMPO maintains higher token entropy in later training while KL divergence and gradient norm reflect continued policy movement across ALFWorld and WebShop.This pattern appears with both trajectory-level GRPO and step-level GiGPO.Source: §E.4 · p. 19
  • EMPO couples execution-equivalent responses through a shared effect-level ratio, organizing policy changes around a common effect-conditioned direction.The resulting entropy dynamics provide a distribution-level view of coordinated updates.Source: §E.4 · pp. 19–20

F PROMPT TEMPLATES

Related papers

Loading 2610.29427v1…