Elamur Research⌕
☰
home / papers / 2024 / EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration

EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration

Paper · 2024 · Allen Nie, Yi Su, Bo Chang et al.

Summary

LLMs are increasingly used as agents that must choose actions and learn from rewards. However, it is unclear whether they can trade off exploration against exploitation when they only observe feedback for their own choices. The authors study this in-context, with no weight updates, using bandit problems as a stateless form of reinforcement learning.

They release BanditBench, a set of natural-language multi-armed bandit (MAB) and contextual bandit (CB) environments. The environments vary the number of arms, reward distributions, difficulty and textual framing. They then test two ways of transferring knowledge from provably good algorithms such as UCB into LLMs:

  • Inference-time support: the prompt includes summary statistics or algorithm-guided hints.
  • Algorithm distillation: synthetic trajectories from optimal algorithms are used as few-shot demonstrations or for fine-tuning.

When given only raw interaction histories, LLMs explore poorly. Both enhancement strategies help, and fine-tuning lets smaller models outperform larger ones. A gap to classical algorithms still remains. The work offers a reproducible way to measure and improve LLM decision-making under uncertainty, which matters for applications such as recommendation and personalization.

Key points

  • Benchmark: BanditBench covers both MAB and CB tasks. It extends earlier work by Krishnamurthy et al. (2024) and can be installed via pip install banditbench. The code is at github.com/allenanie/EVOLvE.
  • Models evaluated: Gemma-2B, Gemma-9B, Gemini-1.5 Flash and Gemini-1.5 Pro, compared against UCB as the classical reference.
  • History formats: Raw History (RH) and Summarized History (SH) are compared. SH reports per-arm empirical means and pull counts. An algorithm-guided (AG) variant adds further support. The paper also formalizes when a textualization counts as "sufficient."
  • Fine-tuning result: Oracle Behavior Fine-Tuning (OFT) brought Gemini-1.5 Flash close to UCB on contextual bandits, and the fine-tuned model generalized across domains.
  • Regret analysis: The authors fit a parametric model to regret curves. Pro models with AG or SH support reach nearly sub-linear regret, and so do Flash models after OFT. Gemma models stay in the linear-regret regime under nearly all methods.

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

🎓Stanford UniversityStanford · United States567 works · 335,190 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksDecision Sciences · 306 worksManagement Science and Operations Research · 145 works

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

Cite

Cite as 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 In-Context Exploration. arXiv:2410.06238.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2410.06238 · arXiv 2410.06238

@misc{nie2024evolve,
  title = {{EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration}},
  author = {Allen Nie, Yi Su, Bo Chang, Jonathan N. Lee, Ed H. Chi, Quoc V. Le and Minmin Chen},
  year = {2024},
  doi = {10.48550/arxiv.2410.06238},
  eprint = {2410.06238},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2410.06238}
}

References

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

  1. P. Auer. Finite-time analysis of the multiarmed bandit problem, 2002. find
  2. C. Bai, Y. Zhang, S. Qiu, Q. Zhang, K. Xu, and X. Li. Online preference alignment for language models via count-based exploration. arXiv preprint arXiv:2501.12735, 2025. — [arXiv:2501.12735](https://arxiv.org/abs/2501.12735) find
  3. Y. Bai, F. Chen, H. Wang, C. Xiong, and S. Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36: 57125–57211, 2023. find
  4. E. Brooks, L. Walls, R. L. Lewis, and S. Singh. Large language models can implement policy iteration. Advances in Neural Information Processing Systems, 36, 2024. find
  5. W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011. find
  6. N. D. Daw, J. P. O’doherty, P. Dayan, B. Seymour, and R. J. Dolan. Cortical substrates for exploratory decisions in humans. Nature, 441(7095):876–879, 2006. find
  7. N. Felicioni, L. Maystre, S. Ghiassian, and K. Ciosek. On the importance of uncertainty in decision-making with large language models. arXiv preprint arXiv:2404.02649, 2024. — [arXiv:2404.02649](https://arxiv.org/abs/2404.02649) find
  8. K. Gandhi, D. Lee, G. Grand, M. Liu, W. Cheng, A. Sharma, and N. D. Goodman. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:2404.03683, 2024.
  9. S. J. Gershman. Deconstructing the human algorithms for exploration. Cognition, 173:34–42, 2018. find
  10. D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.
  11. F. M. Harper and J. A. Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1–19, 2015. find
  12. J. He-Yueya, N. D. Goodman, and E. Brunskill. Evaluating and optimizing educational content with large language model judgments. arXiv preprint arXiv:2403.02795, 2024.
  13. Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30–37, 2009. find
  14. A. Krishnamurthy, K. Harris, D. J. Foster, C. Zhang, and A. Slivkins. Can large language models explore in-context? arXiv preprint arXiv:2403.15371, 2024. — [arXiv:2403.15371](https://arxiv.org/abs/2403.15371) find
  15. J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96–1, 2007. find
  16. M. Laskin, L. Wang, J. Oh, E. Parisotto, S. Spencer, R. Steigerwald, D. Strouse, S. Hansen, A. Filos, E. Brooks, et al. In-context reinforcement learning with algorithm distillation. arXiv preprint arXiv:2210.14215, 2022. — [arXiv:2210.14215](https://arxiv.org/abs/2210.14215) find
  17. J. Lee, A. Xie, A. Pacchiano, Y. Chandak, C. Finn, O. Nachum, and E. Brunskill. Supervised pretraining can learn in-context reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024. find
  18. L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010. find
  19. L. Li, Y. Zhang, D. Liu, and L. Chen. Large language models for generative recommendation: A survey and visionary discussions. arXiv preprint arXiv:2309.01157, 2023a. find
  20. L. H. Li, J. Hessel, Y. Yu, X. Ren, K.-W. Chang, and Y. Choi. Symbolic chain-of-thought distillation: Small models can also" think" step-by-step. arXiv preprint arXiv:2306.14050, 2023b.
  21. L. Lin, Y. Bai, and S. Mei. Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining. In The Twelfth International Conference on Learning Representations, 2023. find
  22. O. Liu, D. Fu, D. Yogatama, and W. Neiswanger. Dellma: A framework for decision making under uncertainty with large language models. arXiv preprint arXiv:2402.02392, 2024a. — [arXiv:2402.02392](https://arxiv.org/abs/2402.02392) find
  23. Z. Liu, Z. Zhou, Y. Wang, C. Yang, and Y. Qiao. Inference-time language model alignment via integrated value guidance. arXiv preprint arXiv:2409.17819, 2024b. find
  24. S. Mirchandani, F. Xia, P. Florence, B. Ichter, D. Driess, M. G. Arenas, K. Rao, D. Sadigh, and A. Zeng. Large language models as general pattern machines. arXiv preprint arXiv:2307.04721, 2023.
  25. V. Mnih. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013. find
  26. S. Mudgal, J. Lee, H. Ganapathy, Y. Li, T. Wang, Y. Huang, Z. Chen, H.-T. Cheng, M. Collins, T. Strohman, et al. Controlled decoding from language models. arXiv preprint arXiv:2310.17022, 2023. find
  27. A. Nie, Y. Chandak, M. Suzara, A. Malik, J. Woodrow, M. Peng, M. Sahami, E. Brunskill, and C. Piech. The gpt surprise: Offering large language model chat in a massive coding class reduced engagement but increased adopters’ exam performances. Technical report, Center for Open Science, 2024. find
  28. I. Osband, D. Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013. find
  29. L. Pan, H. Xie, and R. C. Wilson. Large language models think too fast to explore effectively. arXiv preprint arXiv:2501.18009, 2025. — [arXiv:2501.18009](https://arxiv.org/abs/2501.18009) find
  30. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825–2830, 2011. find
  31. D. A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural computation, 3(1):88–97, 1991. find
  32. Y. Qu, B. Wang, Y. Jiang, J. Shao, Y. Mao, C. Wang, C. Liu, and X. Ji. Choices are more important than efforts: Llm enables efficient multi-agent exploration. arXiv preprint arXiv:2410.02511, 2024. — [arXiv:2410.02511](https://arxiv.org/abs/2410.02511) find
  33. N. Rahn, P. D’Oro, and M. G. Bellemare. Controlling large language model agents with entropic activation steering. arXiv preprint arXiv:2406.00244, 2024. — [arXiv:2406.00244](https://arxiv.org/abs/2406.00244) find
  34. S. C. Raparthy, E. Hambro, R. Kirk, M. Henaff, and R. Raileanu. Generalization to new sequential decision making tasks with in-context learning. arXiv preprint arXiv:2312.03801, 2023. — [arXiv:2312.03801](https://arxiv.org/abs/2312.03801) find
  35. M. Reid, N. Savinov, D. Teplyashin, D. Lepikhin, T. Lillicrap, J.-b. Alayrac, R. Soricut, A. Lazaridou, O. Firat, J. Schrittwieser, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint arXiv:2403.05530, 2024.
  36. N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
  37. K. Singhal, S. Azizi, T. Tu, S. S. Mahdavi, J. Wei, H. W. Chung, N. Scales, A. Tanwani, H. Cole-Lewis, S. Pfohl, et al. Large language models encode clinical knowledge. Nature, 620(7972):172–180, 2023.
  38. A. Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends® in Machine Learning, 12(1-2):1–286, 2019. find
  39. C. Snell, J. Lee, K. Xu, and A. Kumar. Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
  40. R. S. Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018. find
  41. G. Team, M. Riviere, S. Pathak, P. G. Sessa, C. Hardin, S. Bhupatiraju, L. Hussenot, T. Mesnard, B. Shahriari, A. Ramé, et al. Gemma 2: Improving open language models at a practical size. arXiv preprint arXiv:2408.00118, 2024. find
  42. G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint arXiv:2305.16291, 2023a. find
  43. P. Wang, Z. Wang, Z. Li, Y. Gao, B. Yin, and X. Ren. Scott: Self-consistent chain-of-thought distillation. arXiv preprint arXiv:2305.01879, 2023b.
  44. Z. Wang, S. Cai, G. Chen, A. Liu, X. Ma, and Y. Liang. Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents. arXiv preprint arXiv:2302.01560, 2023c.
  45. R. C. Wilson, A. Geana, J. M. White, E. A. Ludvig, and J. D. Cohen. Humans use directed and random exploration to solve the explore–exploit dilemma. Journal of experimental psychology: General, 143 (6):2074, 2014. find
  46. Z. Xi, W. Chen, X. Guo, W. He, Y. Ding, B. Hong, M. Zhang, J. Wang, S. Jin, E. Zhou, et al. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07864, 2023.
  47. S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023.
  48. P. Yu, J. Xu, J. Weston, and I. Kulikov. Distilling system 2 into system 1. arXiv preprint arXiv:2407.06023, 2024. find
  49. H. S. Zheng, S. Mishra, H. Zhang, X. Chen, M. Chen, A. Nova, L. Hou, H.-T. Cheng, Q. V. Le, E. H. Chi, et al. Natural plan: Benchmarking llms on natural language planning. arXiv preprint arXiv:2406.04520, 2024. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nie-2024-evolve-evaluating-optimizing-llms-context/