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

arXiv: https://arxiv.org/abs/2511.13091 · HTML: https://mlsanity.com/paper/2511.13091/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 36 references that are in the map.
- First posted on arXiv 17 Nov 2025.

## Builds on (most cited first, 29 of 29)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [RT-2: Vision-Language-Action Models Transfer Web Knowledge to Robotic Control](https://mlsanity.com/paper/2307.15818/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024)
- [UI-TARS: Pioneering Automated GUI Interaction with Native Agents](https://mlsanity.com/paper/2501.12326/) (2025)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [AndroidWorld: A Dynamic Benchmarking Environment for Autonomous Agents](https://mlsanity.com/paper/2405.14573/) (2024)
- [AppAgent: Multimodal Agents as Smartphone Users](https://mlsanity.com/paper/2312.13771/) (2023)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [Navigating the Digital World as Humans Do: Universal Visual Grounding for GUI Agents](https://mlsanity.com/paper/2410.05243/) (2024)
- [A Real-World WebAgent with Planning, Long Context Understanding, and Program Synthesis](https://mlsanity.com/paper/2307.12856/) (2023)
- [CodeAgent: Enhancing Code Generation with Tool-Integrated Agent Systems for Real-World Repo-level Coding Challenges](https://mlsanity.com/paper/2401.07339/) (2024)
- [Mobile-Agent-v3: Fundamental Agents for GUI Automation](https://mlsanity.com/paper/2508.15144/) (2025)
- [Mobile-Agent-v2: Mobile Device Operation Assistant with Effective Navigation via Multi-Agent Collaboration](https://mlsanity.com/paper/2406.01014/) (2024)
- [You Only Look at Screens: Multimodal Chain-of-Action Agents](https://mlsanity.com/paper/2309.11436/) (2023)
- [Multimodal Web Navigation with Instruction-Finetuned Foundation Models](https://mlsanity.com/paper/2305.11854/) (2023)
- [Embodied Agent Interface: Benchmarking LLMs for Embodied Decision Making](https://mlsanity.com/paper/2410.07166/) (2024)
- [ARPO:End-to-End Policy Optimization for GUI Agents with Experience Replay](https://mlsanity.com/paper/2505.16282/) (2025)
- [Language Understanding for Text-based Games Using Deep Reinforcement Learning](https://mlsanity.com/paper/1506.08941/) (2015)
- [MobileSteward: Integrating Multiple App-Oriented Agents with Self-Evolution to Automate Cross-App Instructions](https://mlsanity.com/paper/2502.16796/) (2025)
- [MobileIPL: Enhancing Mobile Agents Thinking Process via Iterative Preference Learning](https://mlsanity.com/paper/2505.12299/) (2025)

## Built on by (most cited first, 12 of 12)

- [Proximity-Based Multi-Turn Optimization: Practical Credit Assignment for LLM Agent Training](https://mlsanity.com/paper/2602.19225/) (2026)
- [How Mobile World Model Guides GUI Agents?](https://mlsanity.com/paper/2605.10347/) (2026)
- [Xiaomi-GUI-0 Technical Report](https://mlsanity.com/paper/2606.31410/) (2026)
- [PhoneBuddy: Training Open Models for Agentic Phone Use](https://mlsanity.com/paper/2606.23049/) (2026)
- [ExpThink: Experience-Guided Reinforcement Learning for Adaptive Chain-of-Thought Compression](https://mlsanity.com/paper/2605.07501/) (2026)
- [3SPO: State-Score-Supervised Policy Optimization for LLM Agents](https://mlsanity.com/paper/2606.09961/) (2026)
- [AppDeltaWorld: Transition-Grounded Delta Code World Model for Mobile GUI Agents](https://mlsanity.com/paper/2608.05891/) (2026)
- [Every Step Counts: Step-Level Credit Assignment for Tool-Integrated Text-to-SQL](https://mlsanity.com/paper/2605.04719/) (2026)
- [PhoneWorld: From Real-App Trajectories to Dynamic and Verifiable Environments for Phone-Use Agents](https://mlsanity.com/paper/2605.29486/) (2026)
- [Task-Adaptive Rubrics for GUI Reward Modeling](https://mlsanity.com/paper/2608.24174/) (2026)
- [GSAR: Goal-State-Anchor Rewards for Mobile GUI Agents with Self-Evolving Data Synthesis](https://mlsanity.com/paper/2608.22847/) (2026)
- [CLIFT: Conformal Self-Verification for Web Agent Training and Test-Time Scaling](https://mlsanity.com/paper/2610.06829/) (2026)

## Abstract (arXiv)

Multi-turn interaction remains challenging for online reinforcement learning. A common solution is trajectory-level optimization, which treats each trajectory as a single training sample. However, this approach can be inefficient and yield misleading learning signals: it applies uniform sampling across tasks regardless of difficulty, penalizes correct intermediate actions in failed trajectories, and incurs high sample-collection costs. 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 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. Finally, it applies a step-level GRPO augmentation to refine updates for low-success tasks. Experiments on OSWorld and AndroidWorld show that STEP substantially improves sample efficiency and training stability over trajectory-level GRPO, converging faster and generalizing better under the same sampling budget.