Milestone-Guided Policy Learning for Long-Horizon Language Agents

Zixuan Wang, Yuchen Yan, Hongxing Li, Teng Pan, Dingming Li, Ruiqing Zhang, Weiming Lu, Jun Xiao, Yueting Zhuang, Yongliang Shen
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:131595-131609, 2026.

Abstract

While long-horizon agentic tasks require language agents to perform dozens of sequential decisions, training such agents with reinforcement learning remains challenging. We identify two root causes: credit misattribution, where correct early actions are penalized due to terminal failures, and sample inefficiency, where scarce successful trajectories result in near-total loss of learning signal. We introduce a milestone-guided policy learning framework, BEACON, that leverages the compositional structure of long-horizon tasks to ensure precise credit assignment. BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments to credit partial progress, and estimates advantages at dual scales to prevent distant failures from corrupting the evaluation of local actions. On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO. Notably, on long-horizon ALFWorld tasks, BEACON achieves 92.9% success rate, nearly doubling GRPO’s 53.5%, while improving effective sample utilization from 23.7% to 82.0%. These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents. Code is in supplementary materials and will be publicly released.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-wang26jm, title = {Milestone-Guided Policy Learning for Long-Horizon Language Agents}, author = {Wang, Zixuan and Yan, Yuchen and Li, Hongxing and Pan, Teng and Li, Dingming and Zhang, Ruiqing and Lu, Weiming and Xiao, Jun and Zhuang, Yueting and Shen, Yongliang}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {131595--131609}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/wang26jm/wang26jm.pdf}, url = {https://proceedings.mlr.press/v306/wang26jm.html}, abstract = {While long-horizon agentic tasks require language agents to perform dozens of sequential decisions, training such agents with reinforcement learning remains challenging. We identify two root causes: credit misattribution, where correct early actions are penalized due to terminal failures, and sample inefficiency, where scarce successful trajectories result in near-total loss of learning signal. We introduce a milestone-guided policy learning framework, BEACON, that leverages the compositional structure of long-horizon tasks to ensure precise credit assignment. BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments to credit partial progress, and estimates advantages at dual scales to prevent distant failures from corrupting the evaluation of local actions. On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO. Notably, on long-horizon ALFWorld tasks, BEACON achieves 92.9% success rate, nearly doubling GRPO’s 53.5%, while improving effective sample utilization from 23.7% to 82.0%. These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents. Code is in supplementary materials and will be publicly released.} }
Endnote
%0 Conference Paper %T Milestone-Guided Policy Learning for Long-Horizon Language Agents %A Zixuan Wang %A Yuchen Yan %A Hongxing Li %A Teng Pan %A Dingming Li %A Ruiqing Zhang %A Weiming Lu %A Jun Xiao %A Yueting Zhuang %A Yongliang Shen %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-wang26jm %I PMLR %P 131595--131609 %U https://proceedings.mlr.press/v306/wang26jm.html %V 306 %X While long-horizon agentic tasks require language agents to perform dozens of sequential decisions, training such agents with reinforcement learning remains challenging. We identify two root causes: credit misattribution, where correct early actions are penalized due to terminal failures, and sample inefficiency, where scarce successful trajectories result in near-total loss of learning signal. We introduce a milestone-guided policy learning framework, BEACON, that leverages the compositional structure of long-horizon tasks to ensure precise credit assignment. BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments to credit partial progress, and estimates advantages at dual scales to prevent distant failures from corrupting the evaluation of local actions. On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO. Notably, on long-horizon ALFWorld tasks, BEACON achieves 92.9% success rate, nearly doubling GRPO’s 53.5%, while improving effective sample utilization from 23.7% to 82.0%. These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents. Code is in supplementary materials and will be publicly released.
APA
Wang, Z., Yan, Y., Li, H., Pan, T., Li, D., Zhang, R., Lu, W., Xiao, J., Zhuang, Y. & Shen, Y.. (2026). Milestone-Guided Policy Learning for Long-Horizon Language Agents. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:131595-131609 Available from https://proceedings.mlr.press/v306/wang26jm.html.

Related Material