# Spark: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning

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

## Key facts

- Cited by 11 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 25 of its 41 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## 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, 25 of 25)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [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)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (2022)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [Trial and Error: Exploration-Based Trajectory Optimization for LLM Agents](https://mlsanity.com/paper/2403.02502/) (2024)
- [Process Reward Models That Think](https://mlsanity.com/paper/2504.16828/) (2025)
- [TreeRL: LLM Reinforcement Learning with On-Policy Tree Search](https://mlsanity.com/paper/2506.11902/) (2025)
- [Process vs. Outcome Reward: Which is Better for Agentic RAG Reinforcement Learning](https://mlsanity.com/paper/2505.14069/) (2025)
- [TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling](https://mlsanity.com/paper/2508.17445/) (2025)
- [RLVMR: Reinforcement Learning with Verifiable Meta-Reasoning Rewards for Robust Long-Horizon Agents](https://mlsanity.com/paper/2507.22844/) (2025)
- [Beyond Examples: High-level Automated Reasoning Paradigm in In-Context Learning via MCTS](https://mlsanity.com/paper/2411.18478/) (2024)
- [TemplateRL: Structured Template-Guided Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2505.15692/) (2025)
- [Large Model Empowered Embodied AI: A Survey on Decision-Making and Embodied Learning](https://mlsanity.com/paper/2508.10399/) (2025)
- [Towards Embodied Agentic AI: Review and Classification of LLM- and VLM-Driven Robot Autonomy and Interaction](https://mlsanity.com/paper/2508.05294/) (2025)
- [Lookahead Tree-Based Rollouts for Enhanced Trajectory-Level Exploration in Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2510.24302/) (2025)
- [Atlas: Orchestrating Heterogeneous Models and Tools for Multi-Domain Complex Reasoning](https://mlsanity.com/paper/2601.03872/) (2026)
- [ReST-RL: Reinforcing LLM Reasoning through Unified Self-Training and Value-Guided Search](https://mlsanity.com/paper/2508.19576/) (2025)

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

- [OPID: On-Policy Skill Distillation for Agentic Reinforcement Learning](https://mlsanity.com/paper/2606.26790/) (2026)
- [SEED: Self-Evolving On-Policy Distillation for Agentic Reinforcement Learning](https://mlsanity.com/paper/2607.14777/) (2026)
- [StepOPSD: Step-Aware Online Preference Self-Distillation for Agent Reinforcement Learning](https://mlsanity.com/paper/2605.27140/) (2026)
- [StreamMeCo: Long-Term Agent Memory Compression for Efficient Streaming Video Understanding](https://mlsanity.com/paper/2604.09000/) (2026)
- [FACT-E: Causality-Inspired Evaluation for Trustworthy Chain-of-Thought Reasoning](https://mlsanity.com/paper/2604.10693/) (2026)
- [UI-Copilot: Advancing Long-Horizon GUI Automation via Tool-Integrated Policy Optimization](https://mlsanity.com/paper/2604.13822/) (2026)
- [Maestro: Reinforcement Learning to Orchestrate Hierarchical Model-Skill Ensembles](https://mlsanity.com/paper/2605.22177/) (2026)
- [MetaResearcher: Scaling Deep Research via Self-Reflective Reinforcement Learning in Adversarial Virtual Environments](https://mlsanity.com/paper/2606.19893/) (2026)
- [VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2608.28128/) (2026)
- [OPTS-TTPO: Enhancing Finite-Sample Policy-Gradient Learning with Tree Search](https://mlsanity.com/paper/2609.40035/) (2026)
- [SPROUT: Scaling Agentic Reinforcement Learning for Long-Horizon Software Engineering](https://mlsanity.com/paper/2610.14405/) (2026)

## Abstract (arXiv)

Reinforcement learning has empowered large language models to act as intelligent agents, yet training them for long-horizon tasks remains challenging due to the scarcity of high-quality trajectories, especially under limited resources. Existing methods typically scale up rollout sizes and indiscriminately allocate computational resources among intermediate steps. Such attempts inherently waste substantial computation budget on trivial steps while failing to guarantee sample quality. To address this, we propose Spark (Strategic Policy-Aware exploRation via Key-state dynamic branching), a novel framework that selectively branches at critical decision states for resource-efficient exploration. Our key insight is to activate adaptive branching exploration at critical decision points to probe promising trajectories, thereby achieving precise resource allocation that prioritizes sampling quality over blind coverage. This design leverages the agent's intrinsic decision-making signals to reduce dependence on human priors, enabling the agent to autonomously expand exploration and achieve stronger generalization. Experiments across diverse tasks (e.g., embodied planning), demonstrate that textscSpark achieves superior success rates with significantly fewer training samples, exhibiting robust generalization even in unseen scenarios. Our code and checkpoints are available at https://github.com/jinyangwu/SPARK.