Elamur Research⌕
☰
home / papers / 2026 / Large Language Model-Enhanced Multi-Armed Bandits

Large Language Model-Enhanced Multi-Armed Bandits

Paper · 2026 · Jiahang Sun, Zhiyong Wang, Runhan Yang et al.

Summary

Earlier work prompts a pretrained LLM to pick bandit arms directly, but these agents often explore poorly. This paper reverses the roles. A classical multi-armed bandit (MAB) algorithm makes the decisions, and an LLM, used without fine-tuning, only forecasts rewards through in-context learning from the history of arm features and observed rewards.

Three algorithms follow this design:

  • TS-LLM treats sampled LLM predictions as Thompson sampling draws. Its temperature starts high to encourage exploration and shrinks over time.
  • RO-LLM plugs a deterministic (temperature 0) LLM into the regression-oracle method of Foster and Rakhlin (2020), which handles exploration explicitly.
  • TS-LLM-DB adapts the approach to dueling bandits with pairwise preference feedback. It relies on the fact that the Borda function and the latent reward share the same maximizer.

On synthetic tasks, all methods beat direct LLM arm selection. On contextual bandits built from two real text datasets, the advantage is large when arm features carry no semantics the LLM can exploit. An added benefit is that the reward function class need not be specified in advance.

Key points

  • In synthetic stochastic MAB with linear and square reward functions, TS-LLM and RO-LLM consistently outperform direct LLM arm selection (as in Krishnamurthy et al., 2024).
  • The contextual MAB experiments use two text datasets, including AmazonCat-13K.
    • When arms have meaningful semantics, direct selection performs about as well as TS-LLM.
    • When they do not, TS-LLM is far better.
    • This advantage also holds with Llama-3.3-70B-Instruct and Qwen2.5-72B-Instruct.
  • The dueling setting assumes BTL preference feedback. Regret is reported for the first selected arm, which also serves as the recommended arm.
  • Ablation results:
    • A decaying temperature beats every fixed temperature tested.
    • In TS-LLM-DB, more sampled arms (N) for the Borda estimate lower regret but cost more API calls.
    • In RO-LLM, γ=1 over-explores; γ=10 works best for linear rewards, while γ=5 is better for square rewards.
  • Limitations include the cost of LLM API calls and dependence on the LLM's few-shot prediction accuracy.

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

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksInformation Systems · 1,437 worksDecision Sciences · 209 worksManagement Science and Operations Research · 108 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

Cite

Cite as Jiahang Sun, Zhiyong Wang, Runhan Yang, Chenjun Xiao, John C.S. Lui and Zhongxiang Dai. 2026. Large Language Model-Enhanced Multi-Armed Bandits. 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.368

@inproceedings{sun2026large,
  title = {{Large Language Model-Enhanced Multi-Armed Bandits}},
  author = {Jiahang Sun, Zhiyong Wang, Runhan Yang, Chenjun Xiao, John C.S. Lui and Zhongxiang Dai},
  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.368},
  url = {https://doi.org/10.18653/v1/2026.acl-long.368}
}

References

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

  1. Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.14992. find
  2. Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. 2011. Improved algorithms for linear stochastic bandits. In Proc. NeurIPS, pages 2312–2320. find
  3. Keegan Harris and Aleksandrs Slivkins. 2025. Should you use your large language model to explore or exploit? arXiv preprint arXiv:2502.00225. — [arXiv:2502.00225](https://arxiv.org/abs/2502.00225) find
  4. K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. 2016. The extreme classification repository: Multi-label datasets and code. http://manikvarma.org/downloads/X C/XMLRepository.html. ↗
  5. David R Hunter. 2004. Mm algorithms for generalized bradley-terry models. Annals of Statistics, 32(1):384– 406. find
  6. Zhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang, and Yunhe Wang. 2024. Forest-of-thought: Scaling test-time compute for enhancing llm reasoning. arXiv preprint arXiv:2412.09078.
  7. Dingyang Chen, Qi Zhang, and Yinglun Zhu. 2024. Efficient sequential decision making with large language models. arXiv preprint arXiv:2406.12125. find
  8. Yuheng Cheng, Ceyao Zhang, Zhengwen Zhang, Xiangrui Meng, Sirui Hong, Wenhao Li, Zihao Wang, Zekai Wang, Feng Yin, Junhua Zhao, and Xiuqiang He. 2024. Exploring large language model based intelligent agents: Definitions, methods, and prospects. arXiv preprint arXiv:2401.03428. — [arXiv:2401.03428](https://arxiv.org/abs/2401.03428) find
  9. Zhenwen Dai, Federico Tomasi, and Sina Ghias-sian. 2024. In-context exploration-exploitation for reinforcement learning. arXiv preprint arXiv:2403.06826. — [arXiv:2403.06826](https://arxiv.org/abs/2403.06826) find
  10. Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. 2024. Tree search for language model agents. arXiv preprint arXiv:2407.01476. find
  11. Akshay Krishnamurthy, Keegan Harris, Dylan J Foster, Cyril Zhang, and Aleksandrs Slivkins. 2024. Can large language models explore in-context? arXiv preprint arXiv:2403.15371. — [arXiv:2403.15371](https://arxiv.org/abs/2403.15371) find
  12. Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, DJ Strouse, Steven Hansen, Angelos Filos, Ethan Brooks, Maxime Gazeau, Himanshu Sahni, Satinder Singh, and Volodymyr Mnih. 2022. In-context reinforcement learning with algorithm distillation. arXiv preprint… — [arXiv:2210.14215](https://arxiv.org/abs/2210.14215) find
  13. Jonathan Lee, Annie Xie, Aldo Pacchiano, Yash Chandak, Chelsea Finn, Ofir Nachum, and Emma Brunskill. 2023. Supervised pretraining can learn in-context reinforcement learning. Advances in Neural Information Processing Systems, 36. find
  14. Xuheng Li, Heyang Zhao, and Quanquan Gu. 2024. Feel-Good Thompson Sampling for Contextual Dueling Bandits. arXiv preprint arXiv:2404.06013. — [arXiv:2404.06013](https://arxiv.org/abs/2404.06013) find
  15. Xiaoqiang Lin, Zhongxiang Dai, Arun Verma, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. 2024. Prompt optimization with human feedback. arXiv preprint arXiv:2405.17346. — [arXiv:2405.17346](https://arxiv.org/abs/2405.17346) find
  16. Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, and 178 others. 2024a. DeepSeek-v3 technical report. arXiv preprint arXi… find
  17. Ollie Liu, Deqing Fu, Dani Yogatama, and Willie Neiswanger. 2024b. DeLLMa: A framework for decision making under uncertainty with large language models. arXiv preprint arXiv:2402.02392. — [arXiv:2402.02392](https://arxiv.org/abs/2402.02392) find
  18. Tennison Liu, Nicolás Astorga, Nabeel Seedat, and Mihaela van der Schaar. 2024c. Large language models to enhance bayesian optimization. arXiv preprint arXiv:2402.03921. — [arXiv:2402.03921](https://arxiv.org/abs/2402.03921) find
  19. R Duncan Luce. 2005. Individual choice behavior: A theoretical analysis. Courier Corporation. find
  20. Viraj Mehta, Vikramjeet Das, Ojash Neopane, Yijia Dai, Ilija Bogunovic, Jeff Schneider, and Willie Neiswanger. 2023. Sample efficient reinforcement learning from human feedback via active exploration. find
  21. Giovanni Monea, Antoine Bosselut, Kianté Brantley, and Yoav Artzi. 2024. Llms are in-context reinforcement learners. arXiv preprint arXiv:2410.05362. — [arXiv:2410.05362](https://arxiv.org/abs/2410.05362) find
  22. Subhojyoti Mukherjee, Josiah P Hanna, Qiaomin Xie, and Robert Nowak. 2024. Pretraining decision transformers with reward prediction for in-context multi-task structured bandit learning. arXiv preprint arXiv:2406.05064. — [arXiv:2406.05064](https://arxiv.org/abs/2406.05064) find
  23. Allen Nie, Yi Su, Bo Chang, Jonathan N Lee, Ed H Chi, Quoc V Le, and Minmin Chen. 2024. Evolve: Evaluating and optimizing llms for exploration. arXiv preprint arXiv:2410.06238. find
  24. OpenAI. 2023a. ChatGPT. https://chat.opena i.com. ↗
  25. OpenAI. 2023b. GPT-4 technical report. arXiv preprint arXiv:2303.08774.
  26. Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. 2016. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29. find
  27. Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. 2023. Epistemic neural networks. Advances in Neural Information Processing Systems, 36:2795–2823. find
  28. Sameer Singh, Amarnag Subramanya, Fernando Pereira, and Andrew McCallum. 2012. Wikilinks: A large-scale cross-document coreference corpus labeled via links to wikipedia. University of Massachusetts, Amherst, Tech. Rep. UM-CS-2012, 15. find
  29. William R Thompson. 1933. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285– 294. find
  30. Andrey Vasnetsov. 2018. Oneshot-wikilinks. https://www.kaggle.com/generall/oneshotw ikilinks. ↗
  31. Arun Verma, Zhongxiang Dai, Xiaoqiang Lin, Patrick Jaillet, and Bryan Kian Hsiang Low. 2024. Neural dueling bandits. arXiv preprint arXiv:2407.17112. — [arXiv:2407.17112](https://arxiv.org/abs/2407.17112) find
  32. Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, Wayne Xin Zhao, Zhewei Wei, and Ji-Rong Wen. 2024. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345.
  33. Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, and John Lui. 2023. Online clustering of bandits with misspecified user models. Advances in Neural Information Processing Systems, 36. find
  34. Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang, Limao Xiong, Yuhao Zhou, Weiran Wang, Changhao Jiang, Yicheng Zou, Xiangyang Liu, and 10 others. 2023. The rise and potential of large language mode…
  35. Fanzeng Xia, Hao Liu, Yisong Yue, and Tongxin Li. 2024. Beyond numeric awards: In-context dueling bandits with llm agents. arXiv preprint arXiv:2407.01887. — [arXiv:2407.01887](https://arxiv.org/abs/2407.01887) find
  36. Yichong Xu, Aparna Joshi, Aarti Singh, and Artur Dubrawski. 2020. Zeroth order non-convex optimization with dueling-choice bandits. In Conference on Uncertainty in Artificial Intelligence, pages 899–908. PMLR. find
  37. An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, and 23 others. 2024a. Qwen2.5 technical report. arXiv preprint arX… find
  38. Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. 2024b. Large language models as optimizers. In Proc. ICLR.
  39. Shuhua Yang, Hui Yuan, Xiaoying Zhang, Mengdi Wang, Hong Zhang, and Huazheng Wang. 2024c. Conversational dueling bandits in generalized linear models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3806–3817. find
  40. 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. Advances in Neural Information Processing Systems, 36. find
  41. Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. 2012. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538–1556. find
  42. Di Zhang, Jianbo Wu, Jingdi Lei, Tong Che, Jiatong Li, Tong Xie, Xiaoshui Huang, Shufei Zhang, Marco Pavone, Yuqiang Li, Wanli Ouyang, and Dongzhan Zhou. 2024. Llama-berry: Pairwise optimization for o1-like olympiad-level mathematical reasoning. arXiv preprint arXiv:2410.02884. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sun-2026-large-language-model-enhanced-multi/