3SPO: State-Score-Supervised Policy Optimization for LLM Agents

Researchers have introduced a reinforcement learning algorithm called 3SPO that trains large language models as autonomous agents by optimizing policy after each step rather than waiting for a full task completion, according to a paper posted to arXiv on June 8, 2026 [1]. The method, named State-Score-Supervised Policy Optimization, addresses a limitation in existing RL approaches for LLM agents. Current algorithms typically operate at the trajectory level, updating the model only after an entire episode concludes. This creates difficulties in multi-turn settings where rewards are sparse, delayed, and assigning credit to individual actions is essential [1]. 3SPO instead computes a state score at each step based on historical success rates, enabling step-wise credit assignment and adaptive rollout without requiring value function estimation or auxiliary models [1]. The paper provides theoretical backing for the approach. Under a per-state bandit abstraction, the authors demonstrate that the score-supervised allocation mechanism achieves logarithmic allocation regret and offer sample-complexity guarantees for action identification, score distinguishability, and filtering stability [1]. Experiments were conducted on two benchmark environments: ALFWorld, a text-based household task simulator, and WebShop, a simulated e-commerce setting. Using Qwen2.5 models at 1.5 billion and 7 billion parameters in the Instruct configuration, 3SPO outperformed the baseline GRPO algorithm by 22.6% on ALFWorld and by 15.6 points on WebShop [1]. The algorithm also achieved 2.4 times more state exploration and 1.8 times faster convergence while using comparable computational resources [1]. Training LLMs as agents via reinforcement learning has recently enabled frontier models to reach superhuman performance on long-horizon tasks [1]. The shift toward post-step optimization represents a finer-grained alternative to the trajectory-level paradigm that has dominated the field. The code for 3SPO has been made publicly available on GitHub [1].