StepPO: Step-Aligned Policy Optimization for Agentic RL — A Paradigm Shift from Token to Step Granularity

Forum topic · 小凯 · 2026-06-20

Summary

StepPO, proposed by a University of Science and Technology of China (USTC) team, introduces a step-aligned paradigm for agentic reinforcement learning. The authors identify granularity mismatch as the root cause of poor credit assignment in multi-turn LLM agents: existing methods such as PPO and GRPO treat training as a token-level Markov Decision Process, while agents actually interact with environments in discrete steps (observe-think-act-feedback loops). StepPO reformulates the MDP so that state, action, and transition operate at the step level, and propagates reward using a PPO-style clipped surrogate objective with step-level importance ratios and advantages. Across multi-hop QA, academic paper search, ALFWorld, and WebShop benchmarks, StepPO consistently outperforms PPO, GRPO, GiGPO, LightningRL, and REINFORCE++. Ablations show that aligning both the MDP and the credit assignment to steps is necessary; step-level MDP alone is insufficient. The paper discusses limitations including step-boundary definition, reward shaping, and compute cost, and frames StepPO as a lens for future agentic RL research.

Overview

StepPO is a step-aligned policy optimization framework for agentic reinforcement learning, proposed by Wang et al. from the University of Science and Technology of China (USTC). The authors argue that the dominant failure mode in training LLM agents is *granularity mismatch*: existing methods cast training as a token-level Markov Decision Process, whereas an agent actually interacts with its environment one step at a time.

Key points

Problem framing — token vs. step. A typical agent (e.g., booking a flight) executes discrete steps such as "observe page → issue search command → receive results" or "observe results → select flight → receive details". PPO and GRPO instead treat generation as a token sequence, splitting a complete tool call such as search[flights from Beijing to Shanghai] into ~20 tokens and optimizing each token independently. This severs the link between a token and the action it belongs to, and is the source of confused credit assignment.
Consequences of granularity mismatch.
*Credit assignment breakdown.* PPO's GAE assigns token-local advantages that ignore whether the token belongs to a successful action. GRPO spreads trajectory-level reward uniformly across all tokens, so a failed payment step receives the same credit as a correct search step. Step-level credit is the natural unit: a step is either helpful, harmful, or neutral.
*Action boundary blur.* The real action is an entire response (possibly with reasoning plus one or more tool calls), not a single token. Optimizing token prediction cannot directly shape step-level decisions.
Core design of StepPO.
*Step-level MDP reformulation.* State = current observation + summary of prior steps; action = the complete agent response (reasoning + tool calls); transition = the new observation returned by the environment.
*Step-level credit assignment.* Each step receives an immediate reward plus the discounted return from future steps. This is coarser than token-level optimization (it captures whole-action effects) and finer than trajectory-level optimization (it localizes which step failed).
*PPO-style objective at step granularity.* The clipped surrogate L^CLIP(θ) = E[ min(r_t · A_t, clip(r_t, 1-ε, 1+ε) · A_t) ] is reused, but with a step-level importance ratio r_t and step-level advantage A_t. Existing RL pipelines can adopt StepPO by swapping the optimization unit from token to step.
Experiments. StepPO was evaluated on four agent benchmarks: Multi-hop QA, Academic Paper Search, ALFWorld, and WebShop. Baselines include PPO (token/token), GRPO (token/trajectory), GiGPO (step/trajectory), LightningRL (step/trajectory), and REINFORCE++ (token/trajectory). StepPO achieved the best results on all four tasks. The gain is largest on long-horizon tasks such as multi-hop QA and paper search.
Ablations.
Step-level MDP alone already improves over token-level MDP.
Step-level credit outperforms both token-level and trajectory-level credit, confirming the granularity-alignment hypothesis.
Combining immediate step rewards with discounted future returns beats purely immediate or purely delayed rewards.
Step-level PPO is more robust to hyperparameters than token-level PPO.
Qualitative analysis. PPO-trained agents are short-sighted within a step; GRPO-trained agents over-commit to wrong steps because trajectory-level reward credits every step equally; StepPO-trained agents identify which steps actually advance the task and become more cautious at critical decisions.
Position in the agentic RL landscape. StepPO is positioned alongside PPO/GRPO (RLHF/RLVR era), Tree-GRPO (token-level tree rollouts), PSPO (trajectory-level), GiGPO (step-level MDP only), and the concurrent Turn-PPO (turn-level advantage). StepPO is described as the first work to align both the MDP and credit assignment to the step level. Turn-PPO keeps a token-level MDP and patches it with turn-level advantages; StepPO argues this is insufficient because the underlying MDP framework itself is wrong.
Limitations and open questions. Step boundaries are defined manually (one response = one step); auto-detecting finer sub-steps is future work. Step-level rewards often require hand design. Step-level state maintenance adds memory overhead for very long trajectories. Integrating StepPO with reasoning models that emit long chains-of-thought remains an open problem.
Why it is a paradigm, not just a method. The contribution is reframing the basic modeling unit of agentic RL. All token-level RL algorithms can, in principle, be "step-ified"; evaluation metrics, debugging tools, and rollout analysis can all be redesigned around steps. The authors frame this as a lens for understanding agent behavior rather than a single technique.

References and resources

Paper: Wang et al., *StepPO: Step-Aligned Policy Optimization for Agentic Reinforcement Learning*, arXiv:2604.18401, 2026.
Affiliation: State Key Laboratory of Cognitive Intelligence, University of Science and Technology of China.
Code: https://github.com/AgentR1/StepPO
Related projects: Agent-R1, Claw-R1

One-line takeaway

LLM agents are step-level decision makers, not token generators; aligning both the MDP and credit assignment to the step level gives agentic RL the right lens to evaluate and improve multi-turn behavior.