# SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 26 of its 36 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents](https://mlsanity.com/paper/2407.18901/) (2024)
- [ReTool: Reinforcement Learning for Strategic Tool Use in LLMs](https://mlsanity.com/paper/2504.11536/) (2025)
- [AgentTuning: Enabling Generalized Agent Abilities for LLMs](https://mlsanity.com/paper/2310.12823/) (2023)
- [FireAct: Toward Language Agent Fine-tuning](https://mlsanity.com/paper/2310.05915/) (2023)
- [UI-TARS-2 Technical Report: Advancing GUI Agent with Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2509.02544/) (2025)
- [ZeroSearch: Incentivize the Search Capability of LLMs without Searching](https://mlsanity.com/paper/2505.04588/) (2025)
- [Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks](https://mlsanity.com/paper/2503.09572/) (2025)
- [WebDancer: Towards Autonomous Information Seeking Agency](https://mlsanity.com/paper/2505.22648/) (2025)
- [SWEET-RL: Training Multi-Turn LLM Agents on Collaborative Reasoning Tasks](https://mlsanity.com/paper/2503.15478/) (2025)
- [Reinforcement Learning for Long-Horizon Interactive LLM Agents](https://mlsanity.com/paper/2502.01600/) (2025)
- [Process Reward Models for LLM Agents: Practical Framework and Directions](https://mlsanity.com/paper/2502.10325/) (2025)
- [Acting Less is Reasoning More! Teaching Model to Act Efficiently](https://mlsanity.com/paper/2504.14870/) (2025)
- [SPA-RL: Reinforcing LLM Agents via Stepwise Progress Attribution](https://mlsanity.com/paper/2505.20732/) (2025)
- [RLVMR: Reinforcement Learning with Verifiable Meta-Reasoning Rewards for Robust Long-Horizon Agents](https://mlsanity.com/paper/2507.22844/) (2025)
- [Harnessing Uncertainty: Entropy-Modulated Policy Gradients for Long-Horizon LLM Agents](https://mlsanity.com/paper/2509.09265/) (2025)

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

- [Hindsight Credit Assignment for Long-Horizon LLM Agents](https://mlsanity.com/paper/2603.08754/) (2026)
- [PhGPO: Pheromone-Guided Policy Optimization for Long-Horizon Tool Planning](https://mlsanity.com/paper/2602.13691/) (2026)
- [Progress-conditioned Group Policy Optimization for Long-Horizon Agentic Tasks](https://mlsanity.com/paper/2607.22724/) (2026)
- [CAPO: Critic-Guided Action-Aligned Policy Optimization for Advancing LLM Agent Capabilities](https://mlsanity.com/paper/2604.18401/) (2026)
- [BiPACE: Bisimulation-Guided Policy Optimization with Action Counterfactual Estimation for LLM Agents](https://mlsanity.com/paper/2606.25556/) (2026)
- [SPADER: Step-wise Peer Advantage with Diversity-Aware Exploration Rewards for Multi-Answer Question Answering](https://mlsanity.com/paper/2606.00593/) (2026)
- [TreeAdv: Tree-Structured Advantage Redistribution for Group-Based RL](https://mlsanity.com/paper/2601.03703/) (2026)
- [EnvRL: Learn from Environment Dynamics in Agentic Reinforcement Learning](https://mlsanity.com/paper/2606.17680/) (2026)
- [DRACO: Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training](https://mlsanity.com/paper/2609.04094/) (2026)
- [Odysseus: Scaling VLMs to 100+ Turn Decision-Making in Games via Reinforcement Learning](https://mlsanity.com/paper/2605.00347/) (2026)
- [Learning to Correct: Calibrated Reinforcement Learning for Multi-Attempt Chain-of-Thought](https://mlsanity.com/paper/2604.17912/) (2026)
- [DeepSearch-World: Self-Distillation for Deep Search Agents in a Verifiable Environment](https://mlsanity.com/paper/2607.07820/) (2026)
- [Process Reward Informed Tree Rollout for Effective Multi-Turn RL](https://mlsanity.com/paper/2607.15610/) (2026)
- [ContextPilot: Teaching Agents for Proactive Context Management via Fine-grained RL](https://mlsanity.com/paper/2608.28476/) (2026)
- [Co-Evolution of Policy and Internal Reward for Language Agents](https://mlsanity.com/paper/2604.03098/) (2026)
- [SCOUT: Active Information Foraging for Long-Text Understanding with Decoupled Epistemic States](https://mlsanity.com/paper/2605.04496/) (2026)
- [The Horizon Gap: Planning, Memory, Execution, Training, and Evaluation for Long-Horizon LLM Agents](https://mlsanity.com/paper/2608.06663/) (2026)
- [Bidirectional Context Self-Distillation for Reinforcement Learning of Skill-Based LLM Agents](https://mlsanity.com/paper/2608.09555/) (2026)
- [VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2608.28128/) (2026)
- [Explore More, Drift Less: Outcome-Only Reinforcement Learning Can Suffice for Long-Horizon Interactive Agents](https://mlsanity.com/paper/2609.01245/) (2026)
- [ProCredit: From Outcome Rewards to Progress Credit in Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.27532/) (2026)
- [Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.28963/) (2026)
- [PRICE the Action Chunks: Physical Relational Credit Assignment for Embodied Reinforcement Learning](https://mlsanity.com/paper/2609.38890/) (2026)
- [Choosing Before Acting: Comparative Value Estimation for Long-Horizon Tool-Use Agents](https://mlsanity.com/paper/2610.02330/) (2026)
- [Matched-Context Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2610.13755/) (2026)
- [LLM Value Functions for Credit Assignment in Agentic RL](https://mlsanity.com/paper/2610.15840/) (2026)
- [Of Errors and Echoes: Responsibility-Aware Credit Assignment for Tool-Use Agents](https://mlsanity.com/paper/2610.16027/) (2026)
- [Contextual Credit Policy Optimization](https://mlsanity.com/paper/2610.19103/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have demonstrated remarkable capabilities, enabling language agents to excel at single-turn tasks. However, their application to complex, multi-step, and long-horizon tasks remains challenging. While reinforcement learning (RL) offers a promising avenue for addressing these challenges, mainstream approaches typically rely solely on sparse, outcome-based rewards, a limitation that becomes especially problematic for group-based RL algorithms lacking critic models, such as Group Relative Policy Optimization (GRPO). In such methods, uniformly rewarding or penalizing all actions within a trajectory can lead to training instability and suboptimal policies, because beneficial and detrimental actions are often entangled across multi-step interactions. To address this challenge, we propose SALT, a novel and lightweight framework that provides a finer-grained advantage assignment, derived solely from outcome rewards. We achieve this by constructing a graph from trajectories of the same prompt, which allows us to quantify the quality of each step and assign advantages accordingly. Crucially, SALT is designed as a plug-and-play module that seamlessly integrates with existing group-based RL algorithms, requiring no modifications to the rollout procedure and introducing negligible computational overhead. Extensive experiments on the WebShop, ALFWorld, and AppWorld benchmarks with various model sizes demonstrate that SALT consistently improves performance. We also conduct a thorough analysis to validate the design choices behind SALT and offer actionable insights.