Toward Efficient Exploration by Large Language Model Agents

Dilip Arumugam, Thomas L. Griffiths · 2025

Read Toward Efficient Exploration by Large Language Model Agents by Dilip Arumugam, Thomas L. Griffiths (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20997.txt.

Introduction

Dilip Arumugam and Thomas Griffiths hand a language model a classic exploration algorithm to run in plain words, in a 2025 paper. Agents that decide step by step need data thrift: each trial costs. Exploration, knowing when to probe the unknown, is the hard part, and many language model agents botch it. Classic reinforcement learning owns elegant fixes, but their machinery resists translation into talk.

Rather than fine-tune a model to ape good play, the authors let it carry out posterior sampling, a proven method that picks each act by a sampled guess of the world. The model does the bookkeeping in natural language. On word tasks that punish rash or timid probing, the explicit runner beat designs that left exploration to the model's gut. The authors frame the lesson broadly: known algorithms, run openly, can beat hints and vibes in agent design.

Catalog record

CREATORDilip Arumugam, Thomas L. Griffiths
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20997

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Toward Efficient Exploration by Large Language Model Agents Dilip Arumugam, Thomas L. Griffiths Abstract 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. 1 Introduction Large language models (LLMs) have rapidly permeated many areas of machine learning, demonstrating proficiency across a broad range of tasks ( Bommasani et al., 2021 ; Achiam et al., 2023 ; Touvron et al., 2023 ; Team et al., 2023 ; Hurst et al., 2024 ; Jaech et al., 2024 ) . This has inspired recent work studying how LLMs can best be used to solve sequential decision-making problems ( Silver & Sutton, 2025 ) . These efforts have led to the introduction of new designs for LLM agents that aim to learn optimal behavior through trial-and-error interaction within natural language environments ( Yao et al., 2023 ; Shinn et al., 2024 ; Monea et al., 2024 ; Klissarov et al., 2025 ) . While details vary by approach, broadly speaking these new agent designs involve one or more LLMs that interact to ultimately select actions within the environment. However, such agents still reside in the classic RL setting ( Sutton & Barto, 1998 ) and, consequently, must still grapple with the fundamental obstacles to data efficiency (generalization, exploration, and credit assignment) that the RL literature has studied for decades. While composing LLMs to arrive at new agent designs is the current norm, we propose that an alternative strategy is to re-examine existing RL algorithms and consider how LLMs might implement them in otherwise inaccessible environments. An RL algorithm consists of specifying inputs and detailing a sequence of steps for determining behavior at each time period. Why should the emergence and proliferation of LLMs change the fundamental principles of agent design? Instead, as visualized in Figure 1 , perhaps LLMs can be used to create new, potentially-inexact incarnations of existing RL algorithms via the subroutines needed to implement them. Figure 1: Abstractly, an RL algorithm is an ordered sequence of steps. Existing approaches for LLM agent design (left) orchestrate some number of LLMs to implicitly induce a RL algorithm. In contrast, this paper advocates for a novel agent design principle (right) whereby an existing RL algorithm is explicitly implemented by outsourcing individual steps to distinct LLMs. In this work, we focus on data-efficient RL with LLMs and isolate the key challenge of exploration. We demonstrate how modern LLMs afford a contemporary implementation of an existing RL algorithm, Posterior Sampling for Reinforcement Learning (PSRL) ( Strens, 2000 ; Osband et al., 2013 ) , that is both well-studied and whose capacity for good exploration is already known to yield provably-efficient RL in a number of problem classes. We empirically find that our LLM-based implementation of PSRL retains the strong exploration properties that, up to this point, have not only been primarily restricted to tabular domains but also been absent in recent designs for LLM agents. We further observe that the choice of LLM underlying the PSRL implementation matters and, in an environment with stochastic transition dynamics, show that upgrading to a more capable model (GPT-4o to o1-mini) is the difference between incurring linear regret and obtaining cumulative regret on par with classic PSRL. Altogether, our work underscores the importance of addressing exploration in the design of LLM agents, illustrates the considerable value that decades of RL research have to offer data-efficient decision-making with LLMs, and establishes a key distinction between LLMs that implement a RL algorithm versus a RL algorithm that is implemented with LLMs. 2 Problem Formulation All random variables are defined on a probability space (\Omega,\mathcal{F},\mathbb{P}) . For any arbitrary set \mathcal{X} , we use \Delta(\mathcal{X}) to denote the set of all probability distributions with support on \mathcal{X} . For any N\in\mathbb{N} , we denote the index set as [N]=\{1,2,\ldots,N\} . We formulate a sequential decision-making problem as a finite-horizon, episodic Markov Decision Process (MDP) ( Bellman, 1957 ; Puterman, 1994 ) defined by \mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{T},\beta,H\rangle . \mathcal{S} is a set of states, \mathcal{A} is a set of actions, \mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1] is a reward function providing evaluative feedback in the unit interval, \mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S}) is a transition function prescribing distributions over next states, \beta\in\Delta(\mathcal{S}) is an initial state distribution, and H\in\mathbb{N} is the maximum episode length or horizon. Within each of K\in\mathbb{N} total episodes, the agent acts for H steps beginning with an initial state s_{1}\sim\beta(\cdot) and, at each timestep h\in[H] , observes the current state s_{h}\in\mathcal{S} , selects an action a_{h}\in\mathcal{A} , enjoys a reward r_{h}=\mathcal{R}(s_{h},a_{h}) , and transitions to a next state s_{h+1}\sim\mathcal{T}(\cdot\mid s_{h},a_{h}) . An agent is characterized by its non-stationary, stochastic policy \pi:\mathcal{S}\times[H]\rightarrow\Delta(\mathcal{A}) , which encodes a pattern of behavior by mapping individual states and the current timestep to a probability distribution over actions. We assess the performance of a policy \pi in MDP \mathcal{M} at timestep h\in[H] when starting at state s\in\mathcal{S} and taking action a\in\mathcal{A} by its associated action-value function Q^{\pi}_{\mathcal{M},h}(s,a)=\mathbb{E}\left[\sum\limits_{h^{\prime}=h}^{H}\mathcal{R}(s_{h^{\prime}},a_{h^{\prime}})\bigm|s_{h}=s,a_{h}=a\right] . Taking the value function as V^{\pi}_{\mathcal{M},h}(s)=\mathbb{E}_{a\sim\pi_{h}(\cdot\mid s)}\left[Q^{\pi}_{\mathcal{M},h}(s,a)\right] , we define the optimal policy \pi^{\star} as achieving supremal value V^{\star}_{\mathcal{M},h}(s)=\sup\limits_{\pi\in\Pi}V^{\pi}_{\mathcal{M},h}(s) for all s\in\mathcal{S} , h\in[H] where \Pi denotes the class of all non-stationary, stochastic policies. For any episode k\in[K] , we let \tau_{k}=(s^{(k)}_{1},a^{(k)}_{1},r^{(k)}_{1},\ldots,s^{(k)}_{H},a^{(k)}_{H},r^{(k)}_{H},s^{(k)}_{H+1}) denote the random trajectory experienced by the agent executing its policy in the environment. Meanwhile, H_{k}=\{\tau_{1},\tau_{2},\ldots,\tau_{k-1}\}\in\mathcal{H} is the entire random history of interaction at the k th episode. Abstractly, a RL algorithm is a sequence \{\pi^{(k)}\}_{k\in[K]} where the policy deployed at each episode \pi^{(k)} is a function of the current history H_{k} . We may evaluate the performance of a RL algorithm on MDP \mathcal{M} via its cumulative regret: \textsc{Regret}(\{\pi^{(k)}\}_{k\in[K]},\mathcal{M})=\mathbb{E}\left[\sum\limits_{k=1}^{K}\left(V^{\star}_{\mathcal{M},1}(s_{1})-V^{\pi^{(k)}}_{\mathcal{M},1}(s_{1})\right)\mid\mathcal{M}\right], which aggregates performance shortfall between an agent’s chosen policy and the optimal policy in all episodes. Naturally, an agent designer seeks out a RL algorithm with minimal cumulative regret. 3 LLM Implementation of Posterior Sampling for Reinforcement Learning One of the major obstacles to data-efficient RL is exploration, where a learner must determine what data to collect from the environment to maximize long-term performance. While much of the early work on addressing exploration in RL (see Appendix A for a detailed review of prior work) adhered to “optimism in the face of uncertainty,” an alternative is to proceed in a Bayesian fashion. The Bayesian RL setting ( Bellman & Kalaba, 1959 ; Duff, 2002 ;

Read the complete text