Elamur Research⌕
☰
home / papers / 2026 / SPARK: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning

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

Paper · 2026 · Jinyang Wu, Shuo Yang, Yuhao Shen et al.

Summary

Training LLM agents with reinforcement learning on long, multi-step tasks is difficult because successful trajectories are rare, especially when compute is limited. Earlier approaches add more rollouts and spread sampling evenly over every step. As a result, much of the budget goes to easy moves while hard choices stay under-explored.

SPARK replaces independent chain-style rollouts with a trajectory tree that has a fixed budget. A supervised fine-tuning stage first teaches the model to emit an <explore> tag in its reasoning when it is uncertain. During RL, the agent starts several root trajectories and splits a path into multiple continuations only where that tag appears. Elsewhere, the rollout proceeds linearly. The resulting trees are optimized with a GRPO objective using group-relative advantages and binary success rewards.

On ALFWorld, ScienceWorld and WebShop, SPARK outperforms SFT, GRPO, GiGPO and RLVMR, including on unseen splits, while using fewer training samples. The work suggests that letting the agent choose where to spend exploration yields better training data and stronger generalization at a similar cost.

Key points

  • Benchmarks are ALFWorld (L0–L2), ScienceWorld (L0–L2) and WebShop, with baselines SFT, GRPO, GiGPO and RLVMR. The authors report a +73.5% average improvement over the baselines.
  • Branching works in three stages: M parallel roots (typically 3–5), tag-triggered splitting with factor B, and a budget cap so that leaf count never exceeds N. B = 2 gave the best trade-off.
  • On the out-of-domain L2 split with a 1.5B model, the repetitive-action rate drops from 27.1% (GRPO) to 15.4%, a reduction of about 43%.
  • The <explore> trigger rate self-regulates during training. On ALFWorld it rises early, then falls to 0.29 by step 150. On WebShop it quickly settles near 0.17.
  • Code and checkpoints are available at github.com/jinyangwu/SPARK. The stated limitation is that the method may help less with very weak base models whose self-awareness is limited.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Tsinghua UniversityBeijing · China333 works · 87,019 citations🎓Zhejiang UniversityHangzhou · China172 works · 12,988 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

Cite

Cite as Jinyang Wu, Shuo Yang, Yuhao Shen, Shuai Zhang, Zhengqi Wen and Jianhua Tao. 2026. SPARK: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.1100

@inproceedings{wu2026spark,
  title = {{SPARK: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning}},
  author = {Jinyang Wu, Shuo Yang, Yuhao Shen, Shuai Zhang, Zhengqi Wen and Jianhua Tao},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.1100},
  url = {https://doi.org/10.18653/v1/2026.acl-long.1100}
}

References

45 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, and 1 others. 2025. Qwen2. 5-vl technical report. arXiv preprint arXiv:2502.13923. — Qwen2.5-VL Technical Report
  2. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé, Jared Kaplan, Harrison Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, and 34 others. 2021. Evaluating l…
  3. Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, and 1 others. 2025. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arX…
  4. Guanting Dong, Hangyu Mao, Kai Ma, Licheng Bao, Yifei Chen, Zhongyuan Wang, Zhongxia Chen, Jiazhen Du, Huiyang Wang, Fuzheng Zhang, Guorui Zhou, Yutao Zhu, Ji-Rong Wen, and Zhicheng Dou. 2026. Agentic reinforced policy optimization. In The Fourteenth International Conference on Learning Representati… find
  5. Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An. 2025. Group-in-group policy optimization for LLM agent training. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. find
  6. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, and 1 others. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948.
  7. Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 8154–8173, Singapore. Association for Computational Lingu… find
  8. Zhenyu Hou, Ziniu Hu, Yujiang Li, Rui Lu, Jie Tang, and Yuxiao Dong. 2025. TreeRL: LLM reinforcement learning with on-policy tree search. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12355–12369, Vienna, Austria. Associatio…
  9. Yuxiang Ji, Ziyu Ma, Yong Wang, Guanhua Chen, Xiangxiang Chu, and Liaoni Wu. 2025. Tree search for llm agent reinforcement learning. arXiv preprint arXiv:2509.21240. — [arXiv:2509.21240](https://arxiv.org/abs/2509.21240) find
  10. Muhammad Khalifa, Rishabh Agarwal, Lajanugen Logeswaran, Jaekyeom Kim, Hao Peng, Moontae Lee, Honglak Lee, and Lu Wang. 2025. Process reward models that think. arXiv preprint arXiv:2504.16828. — [arXiv:2504.16828](https://arxiv.org/abs/2504.16828) find
  11. Samuel Kotz and Norman L. Johnson, editors. 1992. Breakthroughs in Statistics: Methodology and Distribution. Springer New York, New York, NY. find
  12. Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Tianshun Xing, Shuyue Guo, Tianyu Zheng, Xin Zhou, Xingwei Qu, Wangchunshu Zhou, and 1 others. 2025. Treepo: Bridging the gap of policy optimization and efficacy and inference efficiency with heuristic tree-based modeling. arXiv preprint arXiv:2508.1744… find
  13. Wenlong Liang, Rui Zhou, Yang Ma, Bing Zhang, Songlin Li, Yijia Liao, and Ping Kuang. 2025. Large model empowered embodied ai: A survey on decision-making and embodied learning. arXiv preprint arXiv:2508.10399. — [arXiv:2508.10399](https://arxiv.org/abs/2508.10399) find
  14. MoonshotAI. 2025. Kimi-researcher: End-to-end rl training for emerging agentic capabilities. Accessed: 2025-06. find
  15. OpenAI. 2024a. Hello gpt-4o. Accessed: 2024-05. find
  16. OpenAI. 2024b. Learning to reason with LLMs. Accessed: 2024-09. find
  17. OpenAI. 2025. Introducing gpt-5. Accessed: 2025-08. find
  18. Qwen Team. 2024. Qwen2.5: A party of foundation models. Accessed: 2024-09. find
  19. Sahar Salimpour, Lei Fu, Farhad Keramat, Leonardo Militano, Giovanni Toffetti, Harry Edelman, and Jorge Peña Queralta. 2025. Towards embodied agentic ai: Review and classification of llm-and vlm-driven robot autonomy and interaction. arXiv preprint arXiv:2508.05294. — [arXiv:2508.05294](https://arxiv.org/abs/2508.05294) find
  20. Max-Philipp B. Schrader. 2018. gym-sokoban. https://github.com/mpSchrader/gym-sokoban. ↗
  21. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, and 1 others. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.
  22. Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. 2020. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03768.
  23. Joykirat Singh, Raghav Magazine, Yash Pandya, and Akshay Nambi. 2025. Agentic reasoning and tool integration for llms via reinforcement learning. arXiv preprint arXiv:2505.01441. — [arXiv:2505.01441](https://arxiv.org/abs/2505.01441) find
  24. Yifan Song, Da Yin, Xiang Yue, Jie Huang, Sujian Li, and Bill Yuchen Lin. 2024. Trial and error: Exploration-based trajectory optimization for llm agents. arXiv preprint arXiv:2403.02502. — [arXiv:2403.02502](https://arxiv.org/abs/2403.02502) find
  25. Ruosong Wang, Simon S Du, Lin Yang, and Sham Kakade. 2020. Is long horizon rl more difficult than short horizon rl? In The Thirty-fourth Annual Conference on Neural Information Processing Systems, volume 33, pages 9075–9085. find
  26. Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. 2022. ScienceWorld: Is your agent smarter than a 5th grader? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 11279–11298, Abu Dhabi, United Arab Emirates. Association for Comp… find
  27. Fang Wu, Weihao Xuan, Heli Qi, Aaron Tu, Ximing Lu, Li Erran Li, and Yejin Choi. 2026a. Deepsearch: Overcome the bottleneck of reinforcement learning with verifiable rewards via tree-based search. In The Fourteenth International Conference on Learning Representations. find
  28. Jinyang Wu, Mingkuan Feng, Shuai Zhang, Feihu Che, Zengqi Wen, and Jianhua Tao. 2024. Beyond examples: High-level automated reasoning paradigm in in-context learning via mcts. arXiv preprint arXiv:2411.18478. — [arXiv:2411.18478](https://arxiv.org/abs/2411.18478) find
  29. Jinyang Wu, Chonghua Liao, Mingkuan Feng, Shuai Zhang, Zhengqi Wen, Haoran Luo, Ling Yang, Huazhe Xu, and Jianhua Tao. 2025. Templaterl: Structured template-guided reinforcement learning for llm reasoning. arXiv preprint arXiv:2505.15692.
  30. Jinyang Wu, Guocheng Zhai, Ruihan Jin, Jiahao Yuan, Yuhao Shen, Shuai Zhang, Zhengqi Wen, and Jianhua Tao. 2026b. Atlas: Orchestrating heterogeneous models and tools for multi-domain complex reasoning. arXiv preprint arXiv:2601.03872.
  31. Shangyu Xing, Siyuan Wang, Chenyuan Yang, Xinyu Dai, and Xiang Ren. 2025. Lookahead tree-based rollouts for enhanced trajectory-level exploration in reinforcement learning with verifiable rewards. arXiv preprint arXiv:2510.24302. — [arXiv:2510.24302](https://arxiv.org/abs/2510.24302) find
  32. Zhicheng Yang, Zhijiang Guo, Yinya Huang, Xiaodan Liang, Yiwei Wang, and Jing Tang. 2025. Treerpo: Tree relative policy optimization. arXiv preprint arXiv:2506.05183. — [arXiv:2506.05183](https://arxiv.org/abs/2506.05183) find
  33. Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. 2022a. Webshop: Towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems, 35:20744–20757.
  34. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, volume 36, pages 11809–11822. Curran Associates, Inc. find
  35. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2022b. React: Synergizing reasoning and acting in language models. In The eleventh international conference on learning representations.
  36. Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. 2025. Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model? arXiv preprint arXiv:2504.13837. reinforcement learning for large reasoning models. arXiv preprint arXiv:2509.088…
  37. Qiyuan Zhang, Fuyuan Lyu, Zexu Sun, Lei Wang, Weixu Zhang, Wenyue Hua, Haolun Wu, Zhihan Guo, Yufei Wang, Niklas Muennighoff, and 1 others. 2025c. A survey on test-time scaling in large language models: What, how, where, and how well? arXiv preprint arXiv:2503.24235. find
  38. Wenlin Zhang, Xiangyang Li, Kuicai Dong, Yichao Wang, Pengyue Jia, Xiaopeng Li, Yingyi Zhang, Derong Xu, Zhaocheng Du, Huifeng Guo, Ruiming Tang, and Xiangyu Zhao. 2025d. Process vs. outcome reward: Which is better for agentic RAG reinforcement learning. In The Thirty-ninth Annual Conference on Neur… find
  39. Zijing Zhang, Ziyang Chen, Mingxiao Li, Zhaopeng Tu, and Xiaolong Li. 2025e. Rlvmr: Reinforcement learning with verifiable meta-reasoning rewards for robust long-horizon agents. arXiv preprint arXiv:2507.22844. — [arXiv:2507.22844](https://arxiv.org/abs/2507.22844) find
  40. Tianyu Zheng, Tianshun Xing, Qingshui Gu, Taoran Liang, Xingwei Qu, Xin Zhou, Yizhi Li, Zhoufutu Wen, Chenghua Lin, Wenhao Huang, and 1 others. 2025. First return, entropy-eliciting explore. arXiv preprint arXiv:2507.07017. — [arXiv:2507.07017](https://arxiv.org/abs/2507.07017) find
  41. Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. 2024. Webarena: A realistic web environment for building autonomous agents. In The Twelfth International Conference on Learning Representation…
  42. Sining Zhoubian, Dan Zhang, and Jie Tang. 2025. Rest-rl: Achieving accurate code reasoning of llms with optimized self-training and decoding. arXiv preprint arXiv:2508.19576. — [arXiv:2508.19576](https://arxiv.org/abs/2508.19576) find
  43. Yuexiang Zhai, Hao Bai, Zipeng Lin, Jiayi Pan, Shengbang Tong, Yifei Zhou, Alane Suhr, Saining Xie, Yann LeCun, Yi Ma, and Sergey Levine. 2024. Fine-tuning large vision-language models as decision-making agents via reinforcement learning. In Advances in Neural Information Processing Systems, volume… find
  44. Guibin Zhang, Hejia Geng, Xiaohang Yu, Zhenfei Yin, Zaibin Zhang, Zelin Tan, Heng Zhou, Zhongzhi Li, Xiangyuan Xue, Yijiang Li, and 1 others. 2025a. The landscape of agentic reinforcement learning for llms: A survey. arXiv preprint arXiv:2509.02547. — [arXiv:2509.02547](https://arxiv.org/abs/2509.02547) find
  45. Kaiyan Zhang, Yuxin Zuo, Bingxiang He, Youbang Sun, Runze Liu, Che Jiang, Yuchen Fan, Kai Tian, Guoli Jia, Pengfei Li, and 1 others. 2025b. A survey of find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wu-2026-spark-strategic-policy-aware-exploration/