Lune

ACL Findings2026

STEP: Success-Rate-Aware Trajectory-Efficient Policy Optimization

Yuhan Chen, Yuxuan Liu, Long Zhang, Pengzhi Gao, Jian Luan, Wei Liu

Abstract

Multi-turn interaction remains challenging for online reinforcement learning. Current GRPObased methods-either at the trajectory level or the step level-still suffer from fundamental challenges in multi-turn settings: they allocate sampling uniformly across tasks regardless of difficulty, propagate misleading learning signals that penalize correct intermediate actions in failed trajectories, and incur high samplecollection costs under long-horizon environments. Step-level variants (e.g., GIGPO) mitigate some interaction-cost constraints by decomposing trajectories, yet they retain GRPO's sampling imbalance and still struggle with heterogeneous multi-turn tasks. To address these issues, we propose STEP (Success-rate-aware Trajectory-Efficient Policy Optimization), a framework that dynamically allocates sampling based on per-task success rates and performs fine-grained step-level optimization. STEP maintains a smoothed success-rate record to guide adaptive trajectory resampling, allocating more effort to harder tasks. It then computes success-rate-weighted advantages and decomposes trajectories into step-level samples, followed by a step-level GRPO augmentation that strengthens updates on low-success tasks. Experiments on OSWorld and AndroidWorld show that STEP substantially improves sample efficiency and training stability over both trajectory-level and existing step-level GRPO variants, converging faster and generalizing better under the same sampling budget.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • DAPO: An Open-Source LLM Reinforcement Learning System at Scale cites Training language models to follow instructions with human feedback
  • Direct Preference Optimization: Your Language Model is Secretly a Reward Model cites Training language models to follow instructions with human feedback
  • MobileIPL: Enhancing Mobile Agents Thinking Process via Iterative Preference Learning cites Direct Preference Optimization: Your Language Model is Secretly a Reward Model
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. MobileIPL: Enhancing Mobile Agents Thinking Process via Iterative Preference LearningHuang Kun, Weikai Xu, Yuxuan Liu, Quandong Wang et al.ICLR 2026 · 9 citations

Builds on18

  1. Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
  2. Direct Preference Optimization: Your Language Model is Secretly a Reward ModelRafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning et al.NeurIPS 2023 · 10,924 citations
  3. Toolformer: Language Models Can Teach Themselves to Use ToolsTimo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu et al.NeurIPS 2023 · 5,989 citations
  4. DAPO: An Open-Source LLM Reinforcement Learning System at ScaleQiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan et al.NeurIPS 2025 · 2,828 citations
  5. ALFWorld: Aligning Text and Embodied Environments for Interactive LearningMohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk et al.ICLR 2021 · 819 citations

Related papers

  1. Group-in-Group Policy Optimization for LLM Agent TrainingLang Feng, Zhenghai Xue, Tingcong Liu, Bo AnNeurIPS 2025 · 484 citations
  2. T2^2PO: Uncertainty-Guided Exploration Control for Stable Multi-Turn Agentic Reinforcement LearningHaixin Wang, Hejie Cui, Chenwei Zhang, Jiahui Gao et al.ICML 2026 · 2 citations
  3. Hierarchy-of-Groups Policy Optimization for Long-Horizon Agentic TasksShuo He, Lang Feng, Qi Wei, Xin Cheng et al.ICLR 2026 · 36 citations
  4. Multi-Task GRPO: Reliable LLM Reasoning Across TasksShyam Sundhar Ramesh, Xiaotong Ji, Matthieu Zimmer, Sangwoong Yoon et al.ICML 2026 · 8 citations
  5. Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement LearningCheng Xin, Shuo He, Lang Feng, Haiyang Xu et al.ICML 2026 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines