Elamur Research⌕
☰
home / papers / 2026 / Breaking the Impasse: Dual-Scale Evolutionary Policy Training for Social Language Agents

Breaking the Impasse: Dual-Scale Evolutionary Policy Training for Social Language Agents

Paper · 2026 · Minzheng Wang, Run Luo, Yanbo Wang et al.

Summary

The paper looks at what goes wrong when self-play reinforcement learning with verifiable rewards (RLVR) moves from closed tasks like math or code to open-ended social language games. In these games, players negotiate or deceive in free-form text. The authors call the failure an "evolution impasse." The agent's behaviour becomes uniform, match results stop varying, the value baseline settles on a fixed return, and advantages and gradients shrink toward zero. Prior self-play methods such as SPIRAL and MARS use role-conditioned advantage estimation (RAE) and still hit this problem.

The proposed method, DEPT, has two parts:

  • Time-scaled evolutionary perception. For each role, the method tracks a fast and a slow EMA baseline. It combines the gap between them with match-outcome entropy to measure how stuck training is.
  • Asymmetric advantage reshaping. When stagnation is detected, the method builds a contrastive advantage around the slow baseline. This penalises the outcomes that dominate and rewards rare trajectories.

Across several social games, DEPT beats strong baselines, keeps gradients alive and generalises better out of distribution. This makes self-play more practical for training socially capable LLM agents.

Key points

  • The games are Negotiation, Don't Say It and Two Dollar. Training uses backbones such as Qwen3-4B-Base, and win rate is measured against a fixed Gemini-2.0 opponent.
  • Without intervention, match entropy falls close to zero soon after early exploration. Win rate against Gemini-2.0 then declines, even while reward and game length keep rising.
  • DEPT adds under 0.0016% to per-iteration training time. Its gains over all baselines are statistically significant (p < 0.05).
  • Performance stays stable for the hyperparameter α_fast in the range [0.4, 0.6]. DEPT also yields more semantically diverse actions than the baselines.
  • One training run takes about 30 GPU-hours on 8 NVIDIA A800 GPUs. Reasoning-then-acting outputs increase inference latency.

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

🎓National University of SingaporeSingapore · Singapore180 works · 34,304 citations🏛️Chinese Academy of SciencesBeijing · China194 works · 23,906 citations🔬Institute of AutomationBeijing · China70 works · 14,251 citations🎓University of Chinese Academy of SciencesBeijing · China147 works · 8,480 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Minzheng Wang, Run Luo, Yanbo Wang, Zichen Liu, Yuqiao Tan, Tao Tan, Nan Xu, Lu Wang and Wenji Mao. 2026. Breaking the Impasse: Dual-Scale Evolutionary Policy Training for Social Language Agents. 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.2096

@inproceedings{wang2026breaking,
  title = {{Breaking the Impasse: Dual-Scale Evolutionary Policy Training for Social Language Agents}},
  author = {Minzheng Wang, Run Luo, Yanbo Wang, Zichen Liu, Yuqiao Tan, Tao Tan, Nan Xu, Lu Wang and Wenji Mao},
  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.2096},
  url = {https://doi.org/10.18653/v1/2026.acl-long.2096}
}

References

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

  1. Marwa Abdulhai, Isadora White, Charlie Victor Snell, Charles Sun, Joey Hong, Yuexiang Zhai, Kelvin Xu, and Sergey Levine. 2025. LMRL gym: Benchmarks for multi-turn reinforcement learning with language models. In Proceedings of ICML. find
  2. Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. 2019. Reinforcement learning: Theory and algorithms. https://rltheorybook.github.io/. ↗
  3. Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. 2018. Emergent complexity via multi-agent competition. In Proceedings of ICLR. find
  4. Federico Bianchi, Patrick John Chia, Mert Yuksekgonul, Jacopo Tagliabue, Dan Jurafsky, and James Zou. 2024. How well can llms negotiate? negotiationarena platform and analysis. In Proceedings of ICML, pages 3935–3951. find
  5. Zixiang Chen, Yihe Deng, Huizhuo Yuan, Kaixuan Ji, and Quanquan Gu. 2024. Self-play fine-tuning con-vertsweak language models to strong language models. In Proceedings of ICML, pages 6621–6642. find
  6. Pengyu Cheng, Tianhao Hu, Han Xu, Zhisong Zhang, Yong Dai, Lei Han, Nan Du, and Xiaolong Li. 2024. Self-playing adversarial language game enhances llm reasoning. In Proceedings of NeurIPS, pages 126515– 126543. find
  7. Gur-Ari, and Vedant Misra. 2022. Solving quantitative reasoning problems with language models. In Proceedings of NeurIPS, volume 35, pages 3843– 3857.
  8. Jinhao Duan, Renming Zhang, James Diffenderfer, Bhavya Kailkhura, Lichao Sun, Elias Stengel-Eskin, Mohit Bansal, Tianlong Chen, and Kaidi Xu. 2024. Gtbench: Uncovering the strategic reasoning capabilities of llms via game-theoretic evaluations. Proceedings of NeurIPS, 37:28219–28253. find
  9. Michael L Littman. 1994. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157–163. Elsevier. find
  10. Meta FAIR, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, and 1 others. 2022. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, 378(6624):1067–1074. find
  11. Bo Liu, Leon Guertler, Simon Yu, Zichen Liu, Penghui Qi, Daniel Balcells, Mickel Liu, Cheston Tan, Weiyan Shi, Min Lin, and 1 others. 2025a. Spiral: Self-play on zero-sum games incentivizes reasoning via multi-agent multi-turn reinforcement learning. arXiv preprint arXiv:2506.24119. — [arXiv:2506.24119](https://arxiv.org/abs/2506.24119) find
  12. Leon Guertler, Bobby Cheng, Simon Yu, Bo Liu, Leshem Choshen, and Cheston Tan. 2025. Textarena. arXiv preprint arXiv:2504.11442. — [arXiv:2504.11442](https://arxiv.org/abs/2504.11442) find
  13. Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. 2025b. Understanding r1-zero-like training: A critical perspective. In Proceedings of COLM.
  14. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, and 1 others. 2025. Deepseekr1 incentivizes reasoning in llms through reinforcement learning. Nature, 645(8081):633–638. find
  15. Zichen Liu, Changyu Chen, Xinyi Wan, Chao Du, Wee Sun Lee, and Min Lin. 2024. Oat: A research-friendly framework for llm online alignment. https://github.com/sail-sg/oat. ↗
  16. Thilo Hagendorff. 2023. Deception abilities emerged in large language models. arXiv preprint arXiv:2307.16513. — [arXiv:2307.16513](https://arxiv.org/abs/2307.16513) find
  17. Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, Jie Liu, Lei Qi, Zhiyuan Liu, and Maosong Sun. 2024. OlympiadBench: A challenging benchmark for promoting AGI with olympiad-level bilingual multimodal scientific problems. In Proce…
  18. Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring mathematical problem solving with the MATH dataset. In Proceedings of NeurIPS Datasets and Benchmarks Track.
  19. Wenyue Hua, Ollie Liu, Lingyao Li, Alfonso Amayuelas, Julie Chen, Lucas Jiang, Mingyu Jin, Lizhou Fan, Fei Sun, William Wang, and 1 others. 2024. Game-theoretic llm: Agent workflow for negotiation games. arXiv preprint arXiv:2411.05990. — [arXiv:2411.05990](https://arxiv.org/abs/2411.05990) find
  20. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the SIGOPS.
  21. John E Laird. 2019. The Soar cognitive architecture. MIT press. find
  22. Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy MAA. 2023. American mathematics contest 12 (amc 12). find
  23. MAA. 2024. American invitational mathematics examination (aime). find
  24. MAA. 2025. American invitational mathematics examination (aime). find
  25. Shuaiyi Nie, Siyu Ding, Wenyuan Zhang, Linhao Yu, Tianmeng Yang, Yao Chen, Tingwen Liu, Weichong Yin, Yu Sun, and Hua Wu. 2026. Attnpo: Attention-guided process supervision for efficient reasoning. arXiv preprint arXiv:2602.09953.
  26. OpenAI. 2024. simple-evals: A suite of lightweight evaluations for language models. https://github.com/openai/simple-evals. ↗
  27. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. 2022. Tra… — Training language models to follow instructions with human feedback
  28. Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. 2018. Stochastic variance-reduced policy gradient. In Proceedings of ICML, volume 80, pages 4026–4035. find
  29. Joon Sung Park, Joseph O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. 2023. Generative agents: Interactive simulacra of human behavior. In Proceedings of UIST, pages 1–22. find
  30. David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman. 2024. GPQA: A graduate-level google-proof q&a benchmark. In Proceedings of COLM.
  31. Tian Xia, Zhiwei He, Tong Ren, Yibo Miao, Zhuosheng Zhang, Yang Yang, and Rui Wang. 2024. Measuring bargaining abilities of llms: A benchmark and a buyer-enhancement method. In Findings of ACL, pages 3579–3602. find
  32. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, and 1 others. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.
  33. Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu. 2024. Language agents with reinforcement learning for strategic play in the werewolf game. In Proceedings of ICML, pages 55434–55464. find
  34. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, and 1 others. 2018. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1… find
  35. Theodore Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas Griffiths. 2023. Cognitive architectures for language agents. Transactions on Machine Learning Research. find
  36. Yuqiao Tan, Minzheng Wang, Shizhu He, Huanxuan Liao, Chengfeng Zhao, Qiunan Lu, Tian Liang, Jun Zhao, and Kang Liu. 2025. Bottom-up policy optimization: Your language model policy secretly contains internal policies. arXiv preprint arXiv:2512.19673. — [arXiv:2512.19673](https://arxiv.org/abs/2512.19673) find
  37. Yuqiao Tan, Minzheng Wang, Bo Liu, Zichen Liu, Tian Liang, Shizhu He, Jun Zhao, and Kang Liu. 2026. From p(y\|x) to p(y): Investigating reinforcement learning in pre-train space. find
  38. Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, and 1 others. 2025. Kimi k1. 5: Scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12599. — Kimi k1.5: Scaling Reinforcement Learning with LLMs
  39. Minzheng Wang, Yongbin Li, Haobo Wang, Xinghua Zhang, Nan Xu, Bingli Wu, Fei Huang, Haiyang Yu, and Wenji Mao. 2025a. Adaptive thinking via mode policy optimization for social language agents. arXiv preprint arXiv:2505.02156. — [arXiv:2505.02156](https://arxiv.org/abs/2505.02156) find
  40. Minzheng Wang, Xinghua Zhang, Kun Chen, Nan Xu, Haiyang Yu, Fei Huang, Wenji Mao, and Yongbin Li. 2025b. DEMO: Reframing dialogue interaction with fine-grained element modeling. In Findings of ACL, pages 11373–11401. find
  41. Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, Tianle Li, Max Ku, Kai Wang, Alex Zhuang, Rongqi Fan, Xiang Yue, and Wenhu Chen. 2024. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark…
  42. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, and 1 others. 2025a. Qwen3 technical report. arXiv preprint arXiv:2505.09388.
  43. Ruihan Yang, Yikai Zhang, Aili Chen, Xintao Wang, Jiangjie Chen, Siyu Yuan, Deqing Yang, and Yanghua Xiao. 2025b. ARIA: Training language agents with intention-driven reward aggregation. In Proceedings of NeurIPS. find
  44. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2023. React: Synergizing reasoning and acting in language models. In Proceedings of ICLR.
  45. Huining Yuan, Zelai Xu, Zheyue Tan, Xiangmin Yi, Mo Guang, Kaiwen Long, Haojia Hui, Boxun Li, Xinlei Chen, Bo Zhao, and 1 others. 2025. Mars: Reinforcing multi-agent reasoning of llms through self-play in strategic games. arXiv preprint arXiv:2510.15414. — [arXiv:2510.15414](https://arxiv.org/abs/2510.15414) find
  46. Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang. 2025. Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model? In Proceedings of NeurIPS.
  47. Wenyuan Zhang, Xinghua Zhang, Haiyang Yu, Shuaiyi Nie, Bingli Wu, Juwei Yue, Tingwen Liu, and Yongbin Li. 2026. Expseek: Self-triggered experience seeking for web agents. arXiv preprint arXiv:2601.08605.
  48. Xuhui Zhou, Hao Zhu, Leena Mathur, Ruohong Zhang, Haofei Yu, Zhengyang Qi, Louis-Philippe Morency, Yonatan Bisk, Daniel Fried, Graham Neubig, and Maarten Sap. 2024. SOTOPIA: Interactive evaluation for social intelligence in language agents. In Proceedings of ICLR.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2026-breaking-impasse-dual-scale-evolutionary/