# Toward Efficient Exploration by Large Language Model Agents

arXiv: https://arxiv.org/abs/2504.20997 · HTML: https://mlsanity.com/paper/2504.20997/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 79 of its 123 references that are in the map.
- First posted on arXiv 29 Apr 2025.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 30 of 79)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback](https://mlsanity.com/paper/2309.00267/) (2023)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review](https://mlsanity.com/paper/1805.00909/) (2018)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Using cognitive psychology to understand GPT-3](https://mlsanity.com/paper/2206.14576/) (2022)
- [Reward Design with Language Models](https://mlsanity.com/paper/2303.00001/) (2023)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [In-context Reinforcement Learning with Algorithm Distillation](https://mlsanity.com/paper/2210.14215/) (2022)
- [Formal Limitations on the Measurement of Mutual Information](https://mlsanity.com/paper/1811.04251/) (2018)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)

## Built on by (most cited first, 17 of 17)

- [From Language to Action: A Review of Large Language Models as Autonomous Agents and Tool Users](https://mlsanity.com/paper/2508.17281/) (2025)
- [Representation-Based Exploration for Language Models: From Test-Time to Post-Training](https://mlsanity.com/paper/2510.11686/) (2025)
- [Are Large Language Models Reliable AI Scientists? Assessing Reverse-Engineering of Black-Box Systems](https://mlsanity.com/paper/2505.17968/) (2025)
- [Formalizing Learning from Language Feedback with Provable Guarantees](https://mlsanity.com/paper/2506.10341/) (2025)
- [Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning](https://mlsanity.com/paper/2505.20561/) (2025)
- [Dynamic Risk Assessments for Offensive Cybersecurity Agents](https://mlsanity.com/paper/2505.18384/) (2025)
- [CaRT: Teaching LLM Agents to Know When They Know Enough](https://mlsanity.com/paper/2510.08517/) (2025)
- [ABBEL: Learning Natural-Language Belief States for Memory-Efficient Interaction](https://mlsanity.com/paper/2512.20111/) (2025)
- [Improving the Data-efficiency of Reinforcement Learning by Warm-starting with LLM](https://mlsanity.com/paper/2505.10861/) (2025)
- [Cognitive Models and AI Algorithms Provide Templates for Designing Language Agents](https://mlsanity.com/paper/2602.22523/) (2026)
- [Using Cognitive Models to Improve Language Model Simulation of Human Persuasion Games](https://mlsanity.com/paper/2606.17657/) (2026)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [Reasonably reasoning AI agents can avoid game-theoretic failures in zero-shot, provably](https://mlsanity.com/paper/2603.18563/) (2026)
- [A Survey of Reinforcement Learning for Large Language Models under Data Scarcity: Challenges and Solutions](https://mlsanity.com/paper/2604.17312/) (2026)
- [Agent2UCB: Agentic System for Generative Engine Optimization](https://mlsanity.com/paper/2608.29063/) (2026)
- [Success Leaves Detours: Learning Executable Walkthroughs for Long-Horizon Agents](https://mlsanity.com/paper/2609.22120/) (2026)
- [Large Language Model Orchestration under Heterogeneous Preferences via Explicit Persona Inference](https://mlsanity.com/paper/2610.07587/) (2026)

## Abstract (arXiv)

A burgeoning area within reinforcement learning (RL) is the design of sequential decision-making agents centered around large language models (LLMs). While autonomous decision-making agents powered by modern LLMs could facilitate numerous real-world applications, such successes demand agents that are capable of data-efficient RL. One key obstacle to achieving data efficiency in RL is exploration, a challenge that we demonstrate many recent proposals for LLM agent designs struggle to contend with. Meanwhile, classic algorithms from the RL literature known to gracefully address exploration require technical machinery that can be challenging to operationalize in purely natural language settings. In this work, rather than relying on finetuning or in-context learning to coax LLMs into implicitly imitating a RL algorithm, we illustrate how LLMs can be used to explicitly implement an existing RL algorithm (Posterior Sampling for Reinforcement Learning) whose capacity for statistically-efficient exploration is already well-studied. We offer empirical results demonstrating how our LLM-based implementation of a known, data-efficient RL algorithm can be considerably more effective in natural language tasks that demand prudent exploration.