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

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.