EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration
Authors: Allen Nie
Yi Su
Bo Chang
Jonathan Lee
Ed H. Chi
Quoc V Le
Minmin Chen
Venue: ICML 2025 poster (2025)
Keywords: Exploration
In-Context Reinforcement Learning
Bandit
Primary area: deep_learning->large_language_models
TL;DR: We measure LLMs' (in)ability to make optimal decisions in bandits and evaluate a set of strategies to train LLMs to explore.

Abstract: Despite their success in many domains, large language models (LLMs) remain under-studied in scenarios requiring optimal decision-making under uncertainty. This is crucial as many real-world applications, ranging from personalized recommendations to healthcare interventions, demand that LLMs not only predict but also actively learn to make optimal decisions through exploration. In this work, we measure LLMs' (in)ability to make optimal decisions in bandits, a state-less reinforcement learning setting relevant to many applications. We develop a comprehensive suite of environments, including both context-free and contextual bandits with varying task difficulties, to benchmark LLMs' performance. Motivated by the existence of optimal exploration algorithms, we propose efficient ways to integrate this algorithmic knowledge into LLMs: by providing explicit algorithm-guided support during inference; and through algorithm distillation via in-context demonstrations and fine-tuning, using synthetic data generated from these algorithms. Impressively, these techniques allow us to achieve superior exploration performance with smaller models, surpassing larger models on various tasks. We conducted an extensive ablation study to shed light on various factors, such as task difficulty and data representation, that influence the efficiency of LLM exploration. Additionally, we conduct a rigorous analysis of the LLM's exploration efficiency using the concept of regret, linking its ability to explore to the model size and underlying algorithm.

EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration
Allen Nie" Si 2 Bo Chang 2 Jonathan N. Lee2
Ed H. Chi Quoe Le Minmin Chen 2
Abstract
cluding but not limited personal assistants (Liu al., 2024a), recommendation systems (Li al., 2023a), game- playing (Wang et al., 2023a;c), education (Nie et al., 2024; He- Yueya et al., 2024), and healthcare (Singhal et al., 2023). In these tasks, LLMs function as agents that engage with users or the environment in a dynamic interaction process. For example, each time step, the LLM suggests ped- agogical strategy or make a recommendation to a specific user, then receives feedback either explicit or implicit in the form of rewards. Based on this feedback, the agent updates its beliefs about the environment, e.g., underlying reward distributions, and adapts its strategies to maximize the cumulative reward. These tasks differ fundamentally from classic prediction tasks where LLM is used to pre- dict a target. A decision making LLM only receives partial feedback, i.e., the reward for its own actions, but not for others. Thus, it requires the LLM to effectively interact with the environment and explore to discover the optimal action, Meanwhile, exploring an unknown action that turns out to have lower reward than the known ones incurs an opportunity cost. The agent, therefore, needs to strike a balance between exploration and exploitation. While the exploration-exploitatioo tradeoff has been extensively stud- ied in the LLe era, particularly in the fields of ban- dits (Li et al., 2010; Slivkins et al., 2019) and reinforcement learning (Mnih, 2013; Osband et al., 2013; Sutton, 2018 8), it remains unclear how LLMs approach this tradeoff when faced with uncertainty.
Despite their success in many domains, large lan- guage models (LLMs) remain under-studied in scenarios requiring optimal decision-makin un- der uncertainty. This is crucial as many real-world applications, ranging from personalized recom- mendations to healthcare interventions, demand that LLMs not only predict but also actively learn to make optimal decisions through exploration. In this work, measure LLMs' (in)ability to make optimal decisions in bandits, a state-less reinforcement learning setting relevant to many applications. We develop comprehensive suite of environments, including both context- and contextual bandits with varying task difficulties, to benchmark LLMs' performance. Motivated by the existence of optimal exploration algorithms, we propose efficient ways to integrate this algo- rithmic knowledge into LLMs: by providing ex- plicit algorithm- guided support during inference; and through algorithm distillation via in-context demonstrations and Lin-ttnnng, using synthetic data generated from these algorithms. Impres- sively, these techniques allow us to achieve supe- rior exploration performance with smaller mod- els, surpassing larger models on various tasks. We conducted an extensive ablation study to shed light on various factors, such as task difficulty and data representation, that influence the efficiency of LLM exploration. Additionally, we conduct rigorous analysis of the LLM's exploration ef- ficiency using the concept of regret, linking its ability to explore to the model size and underly- ing algorithm.
We study LLMs' in-context exploration capabilities under the simplified framework of bandits - stateless form of reinforcement learning that is highly applicable to many do- mains. We set up the LLM to interact with the environment over T rounds. In each round, it receives the full history of its past interactions, the current state (if provided), and a set of actions, and is tasked with selecting an action to maximize the cumulative reward. Ideally, the LLM should adaptively choose an action in each round learn the reward distributions of different actions and eventually converge to consistently selecting the optimal one. We study LLM'' 's abil- ity to do so in-contexi, without the need to re-train, which we dubbed as in-context exploration. Unlike using LLM for reward- -frree or curiosity -driven exploration, in-context exploration is in-context self- self-imprrvemment, where the LLM builds up context through interactions to solve a task.
1. Introduction
The rapid advance of LLMs has positioned them valu- able tools for a wide range of decision-making tasks, in-
Equal contribution 'Stanford University "Google DeepMind. Correspondence to: Allen Nie .ww.eeccsssaoor..duu.. Su <yisumtv gom.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
We introduce BanditBench', comprehensive suite of multi- armed bandit (MAB) (Slivkins et al., 2019) and contex- tual bandit (CB) (Li et al., 2010) environments in natural language to rigorously evaluate the Decision-making ca- pabilities of L.MMs. Building on the pioneering work of Krishnamurthy et al. (2024), we significantly expand the benchmark by incorporating a broader range of tasks with varying complexities, including variations in the number of arms, reward distributions, exploration diffieulty, and tex- tual descriptions of environments. Additionally, we extend it to CB environments, where rewards across arms depend on contextual features, to assess generalization in LLM exploration.
relation classical concepts in decision-making like explo- ration. Our work extends the research of Krishnamurthy et al. (2024), who examined LLMs' exploration capabilities in small-scale MAB tasks. Their findings, which showed positive results only with substantial intervention, are con- sistent with our broader analysis across both MAB and CB tasks at various scales. Mirchandani et al. (2023); Rahn et al. (2024); Felicioni et al. (2024) also evaluated the ability of LLMs learn in-context and solve bandit-like decision- making problems.
Another relevant line of research focuses on in-context learn- ing for decision decision-making and reinforcement learning (RL) with domain-specific transformers. Laskin et al. (2022) distilled demonstrations from RL algorithms into a trans- former and showed that it learns to imitate the RL process to solve new RL tasks. Similarly, Lee et al. (2024) trained transformers with optimal action labels, showing that the model learns to execute posterior sampling for RI. (Osband et al., 2013) in-context. This area has been further stud- ied by Raparthy et al. (2023); Lin et al. (2023); Bai et al. (2023). However, these studies focus on Nomain--seciife decision-making, whereas our paper examines general- purpose decision-making capabilities in language models. Our inference-time algorithm aigorithm-guided support shares a simi- lar conceptual framework with recent efforts to align LLMs at inference time. These include employing explicit value functions as prefix scorers (Mudgal et al., 2023), and lever- aging both implicit and explicit value functions to guide decoding (Liu et al., 2024b). In the realm of algorithm dis- tillation, much of the research on LLMs has concentrated chain-of- ofttho (CoT)) reasoning ( (Wang et al., 2023b; Li et al., 2023b), while (Gandhi et al., 2024) focused on search and backtracking. Our work focuses on distilling a more complex class of algorithms that involve uncertainty estimation and linear regression.
To enhance LLMSs for in-context exploration, we leverage known bandit algorithms such as Confid-Con Bound (UCB) algorithm, which have been proven "optimal" un- der mild conditions. We investigate two approaches: (1) inference-time algorithm- guided support, where summary statistics on interaction history, along with descriptions of bandit algorithms, are provided in context for L.LMs to choose actions, and (2) algorithm distillation via optimal demonstration data, where "oracle" trajectories from op- timal bandit algorithms are provided as either in-context few-shot demonstrations or optimal behavior fine-tuning. We benchmark off-the-shelf LLMs of different sizes- - both open-sourced and proprietary- and those enhanced by our approaches on BanditBench. Both approaches demonstrate promising improvements over baseline methods that rely solely on raw interaction histories presented sequences of (action, reward) tuples. Furthermore, our results show that fine-tuning to distill optimal exploration behavior leads to strong generalization across domains, enabling smaller models to achieve superior exploration performance com- pared to larger models. We also perform extensive ablation studies that reveal how training task difficulty, textual rep- resentation and Algorithm-Guidee Support impact model performance. To gain deeper insights into the exploration efficiency of different methods, we fit parametric function to the observed regret patterns, allowing for a more rigor- ous interpretation of the exploration efficiencies of various LLMs and our proposed approaches.
The motivation of our work is also inspired by the cognitive science literature on human. Prior studies have found that humans balance exploration and exploitation through a mix of directed and random exploration (Wilson et al., 2014), and that these behaviors are supported by distinct neural mechanisms (Daw et al., 2006). Gershman (2018) further decomposes human exploration into algorithmic compo- nents. These works provide future directions for evaluating LLM's behavior in addition to reward (Pan et al., 2025). Additionally, efficient exploration also benefits other areas of RL, such as multi-agent collboration (Qu et al., 2024) and preference optimization (Bai et al., 2025).
2. Related Work
Several prior works have investigated the use of LLMs for decision-making. In one category, numerous studies have deployed LLMs directly as agents in decision-making prob- lems such as games (Yao et al., 2023; Brooks et al., 2024;
Shinn et al., 2024; Wang et al., 2023a; Xi et al., 2023). However, fewer works have systematically evaluated LLMS'' capabilities in general decision-making setup, especially in
3. In-Context Exploration
In this section, we define the problem of In-Context Explo- ration (ICE), following the setup in (Krishnamurthy et al., 2024). An agent interacts with an environment by observing
GGthhub: https://gii www.ttt......leaaattett wwwm/aleeanne//vVn// You can install the code with: pip install bandi tbench
2

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
No Support (Raw)
life Support"
In-context Demonstration
Oracle Behavior Fine-Tuning (OFT)*
100
UCB
Overall Win-Rale Rate
60
60.0
66.4
60.7
64.3
50.2
45.5
34.8
27.7
7.6
10.5
4.7
10.5
5.3
9.2
7.1
0.0
Gemma-22
Gemini-155 Flash Gemini-15
Gemini-15
Gemini-115
Multi-Armed Bandit
Contextual Bandit
Figure 1: The best achieved performance within each category of method in both MAB and CB. Note that took the max over different methodology setups within each calegory. For contextual bandit, OFT enabled small fine-tuned model (Gemini-1.5 Flash) to approach the performance of the optimal classical algorithm (UCB).
state information, selecting actions, and collecting feedback. The goal of the agent is to maximize its cumulative reward through multiple rounds of interactions. Specifically for ICE, the agent is an LLM that keeps a history of observa- tions and interactions with the environment in its context. The agent determines its actions based this context, rather than by updating its weights executing hand-designed exploration strategies.
task Tas its expected cumulative reward, given by (T(T) ET,= Σi= r5 The optimal policy x" rep- resents the agent that selects the action with the highest average reward, defined "" (a:) arg max, EE [ra x). A commonly used metric to measure the performance of an agent or algorithm is regret.
Definition (Cumulative Regret). The expected re- grer of a policy a under task T is: REG(T) = ET, (t= - rr:) JT(x"*) (T()), where oz I (x²).
Notation and Definitions. We primarily consider bandits, simple class of environments that still incorporates many fundamental challenges in decision pecision-making. Here, we de- scribe framework that encompasses both multi-armed ban- dits (MAB) and contextual bandits (CB). A bandit environ- ment T is defined as T = (X, A, R), where A defines set of valid actions. X' is the set of state information (if any), and R represents the underlying reward distribu- tions of actions, which are unknown the agent. MAB and CB tasks differ in whether the context is provided and used: in MAB, the reward depends solely on the ac- tion, whereas in CB depends on both the action and the context. The interaction between the agent and the environ- ment occurs over T steps. At each time step i E [T], the environment reveals a new observation 2, E X, the agent selects action dę A following its policy n, and then reward rit R (Ire) is revealed. Given LLM agent with policy it determines its action ~ π (HT), where Hº = (I1, 7 ..... I;) stores the historical ac- tions taken by the agent and the corresponding environment feedback, which is sent as input context to the LLM.
We expect good agents to have average regret that con- verges to zero (i.e. REG 4 0), demonstrating that they eventually learn to perform as good as the optimal policy, UCB and Thompson Sampling are two such examples with sublinear regret. Examples of cumulative regret curves are shown in Figure A4c.
Representing Histories in Context. Developing an LLM agent suited for in-context Docision-making tasks also re- quires designing robust contextualization function & that translates histories H. for the LLM to consume. The ob- vious baseline for Φ is to simply record the Raw History (RH) from the environments as list of (context, action, reward) tuples directly as the context. In this representation, the context length of oi (H,)) grows linearly with and RH contains all information. While RH is general contextu- alization function applicable any task more advanced task-specific contextualization functions may exist and yield better performance. For example, (Krishnamurthy et al., 2024) proposed a Summarized History function (SH) that compresses the history while still containing sufficient in- formation for a given task T. RH and SH differ in how past interaction histories are represented to the L.LM agent, as
Over T rounds, we measure the performance of an agent
In CB, context is exogenous and independently sampled from stationary distribution; it affected by action a, in the full setting-
3

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
shown in Figure A2. At time step RH provides a com- plete list of past interactions as (Time t', Action Name ag', Reward re) for t' = 0-... t. In contrast, SH provides suffi- cient statistics of the past interactions. Specifically, under MAB, SH utilizes the empirical mean over each arm (i.e., B|r"), Va E A), the number of times each arm has been pulled up to time I, Ne(a), and the current horizon t. In this paper, we consider good contextualization be those that satisfy "sufficiency", which we define as:
with different action spaces and reward structures. We dif- ferentiate between sizes of actions well as action descrip- tions: Videos such as "Video AA", and Clothes, described using semantically meaningful phrases, such as "Supreme Sylvan Sandals". Regarding reward distributions, we evalu- ate two types: Bernoulli and Gaussian Bandit. The detailed configurations are shown in Appendix A.2.
Contextual Bandit For contextual bandit, at each round t E [T], the agent is presented with some contextual feature x (which may consist of both textual descriptions and nu- merie values) describing the state (and action). The LLM agent chooses an action E A, and then a reward r(ar, a) is received, which depends on both the context and the cho- sen action. We design the semi- moni-sytthetic contextual bandit task based on the MovieLens dataset (Harper & Konstan, 2015), which consists of approximately 6,000 real users' movie ratings. The goal of the agent is to recommend a personalized movie that a specific user is likely to enjoy. In partieular, the observations include user-specific features such as age, gender, occupation, and geographical location (county and state), as well as features of the movies. The action space is limited to the top- most-watched movies in the dataset, with K = 10 for the easy setting and K = 30 for the more challenging setting. At each time step, we pro- vide textual contextual features alongside 5-dimensional user preference vector. The task can easily be scaled up to include more movies (a larger K). Further details can be found in Appendix A.3.
Definition 2 (Sufficient Contextualization).. Given a policy class II, let I C II and II C II be the sets of policies that take history representation of ((Hi) using the contex- tualization fanction & and the raw history H2, respectively, Then the contextualization function & is sufficient if
lim inf 1 RREG(T") T-000
inf 1 REG(T (m))
= 0.
Ell T
Ell T
In other words, the best agent that uses the history represen- tation can asymptotically achieve the same average regret as one with the full raw history, meaning that the contextu- alization preserves all the essential information needed for effective decision- decision-making.
4. BanditBench
We present BanditBench, an extensive suite of MAB (Slivkins et al., 2019) and CB (Li et al., 2010) environments in natural language to benchmark the in-context exploration capabilities of LLMs. We show two examples in Figure AI. A wide range of real-world problems are modeled as bandit, across United Nation Refugee Agency assistance program (Caria et al., 2024), government assistance to reduce incarceration (Chohlas- Wood et al., 2023), education app push notification (Yancey & Settles, 2020), news (Li et al., 2010) and movie recommendations (Bibaut et al., 2021).
5. Teaching Optimal Exploration
Motivated by the existence of optimal algorithms for ban- dits, we aim to leverage these algorithms to improve LLMs for exploration by: 1) incorporating algorithmic guidance during inference (Section 5.1), 2) teaching optimal explo- ration through algorithm distillation (Section 5.2). We show that smaller models trained using algorithm distillation can even outperform larger models, offering a promising way to efficiently explore with lower inference costs.
Multi-Armed Bandit In (stochastic) multi-armer bandit problems, we vary our environment configurations primar- ily along two key dimensions: 1) action space, where we change the number of actions K and the textual descriptions associated with each action; 2) reward distributions, where we change the parametric distribution of the reward, i.e., the types of reward distributions, and the exploration difficulty, characterized by the gap between the persfrreformng arm and the second-best arm (Amin). smaller gap makes it harder for the agent to distinguish between optimal and sub- optimal actions, thereby increasing the exploration difficulty. In contrast to the setup in Krishnamurthy et al. (2024), which focuses solely on MAB instances with Bernoulli reward dis- tribution, our expanded setup allows us to systematically analyze I.LMs' performance across diverse environments
Numerous algorithms have been developed to enable effi- cient exploration in both MAB (Auer, 2002) and CB (Lang- ford & Zhang, 2007: Li et al., 2010) settings. Among these, the Upper Confidence Bound (UCB) algorithm-also known optimism in the face of uncertainty-stannt out for its simplicity and theoretical guarantees. Its clear and interpretable representation of uncertainty and explo- ration strategy also makes it well-suited for integration with existing LLMs. Our method can generalize to dif- ferent algorithms easily, such as deep neural network ban- dits (Riquelme et al., 2018).
UCB for Multi-Armed Bandit For MAB, at time step t, given the history (ae, re 1 He we define (a as the
4

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
number of times that action a has been selected up to time t. The empirical mean reward of arm up to time i, de- noted as (a(a) := Ev= [' ploitation value Vaaplolla N.(a) represents the ex-
while SH only works on MAB setup. We discuss why this is the case in Appendix A.5.
The high-probability confi-
5.2. Algorithm Distillation
dence interval, also known as the exploration bonus, given
We further investigate the possibility of enhancing LLM exploration by leveraging a set of trajectories generated by oracle exploration algorithm in the BanditBench en- vironment. This approach, called algorithm distillation, aims to distill the optimal exploration behavior from the oracle algorithm to the LLM. In particular, we consider two approaches: in-context few-shot demonstration and oracle behavior fine-tuning, both utilizing expert trajecto- ries generated by the oracle algorithm. Compared with Eegorithm-Guidee Support (AG), these approaches do not require understanding of the oracle algorithms, nor do they require generating sufficient statistics based on ora- cle algorithms; thus, they can also be applied to black-box a algorithms.
by Vrexplore (a, 1) == Vv Ni(a) where a the hyperparam- trade-off. At each time step, UCB selects the arm that maximizes the sum of the exploitation value and the exploration bonus, thereby choosing the arm with the highest upper confidence bound.
log(t)
eter controlling the exploration-expoone
UCB for Contextual Bandit In CB, we consider the case of linear payoffs (Li et al., 2010; Chu et al., 2011), I), where the expected reward [[[?] is assumed to be linear w.r.t a d-dimensional feature vector zÿ. with some unknown coefficient vector 8", i.e., [[r]] = (at)T At each time step, for any arm a, the algorithm maintains the de- sign matrix Da E I (a)x( which represents the feature data for arm up to time t, as well as the correspond- ing reward vector rd E (N) It then estimates á us- ing ridge regression. Moreover, the high-probability con- fidence interval of the reward estimate (zz)²' 0 is given by (V(x=)"²(D) (D Da + Xla)-1a7, with la being the identity matrix. Following MAB, the exploitation value is the re- ward estimate, and the exploration bonus is the confidence bound around it.
Oracle Trajectory Generation We use UCB as the or- acle algorithm to generate the trajectories. Following the notations defined in Section 3, the trajectories are in the form of tuples of (0(H)CC)) at d,CB),, where each tuple pairs the transformed representation of the history at time and the action a ,CCB from UCB. For MAB, create trajecto- ries from reward distributions that differ from those used in evaluation. This assesses the LLM's ability to generalize across different bandit instances with the same underlying scenario but varying action descriptions and action-reward mappings. We further control the data generation process by varying instance difficulty (e.g., Amin) and trajectory contex- tualization (c.g.. RH or AG). For CB, we use fixed dataset and evaluate the LLM's performance on a held-out set of users. While these users are unseen during training, their profiles and preferences remain within the distribution of the training data. In both MAB and CB, each trajectory consists of a sequence of exploration steps: 300 steps for MAB with 5 arms, 1000 steps for MAB with 20 arms, and 200 steps for CB. We generate 50 trajectories for 2 MAB domain configurations (the easiest and the hardest configuration) with 2 trajectory contextualizaaioos,, and 200 trajectories for CB with 2 trajectory contextualizations This results in 4 distillation datasets for MAB and 2 for CB.
5.1. Inference- TieerenceTTieeAA Algorithm-Guidee Support
As discussed above, UCB-type algorithms operate by explic- itly calculating the exploitation value /xpploit along with the exploration bonus EEsploree for each arm, and by selecting the arm that maximizes the sum of the two. These components, Exploot and Explore therefore provide the sufficient context for LLMs to make optimal decisions. Specifically, in the MAB setup, during inference time at time step I,, we provide the LLM with a list of tuples (Vexploit (a, t), Veeplore (a, t)) for each arm a E [K. For CB, during inference-time, we explicitly maintain the design matrix Da and response vec- tor r for each arm, incorporating past interactions from the LLM up to that time f, using this to obtain the exploitation value and exploration bonus. We then provide the LLM with a list of exploitation values and exploration bonus for each arm a at current context æ, similar to the MAB setup. Compared with SH, which only provides the empiri- cal mean and the number of times each arm has been pulled, Algorithm- Guideed Support (AG) directly supplies seman- tically understandable exploitation values and exploration bonuses. Theoretically, the LLM only needs to perform addition and argmax, rather than manipulating raw histories to discern the underlying reward distribution (or parameter 0 in CB). Another advantage is that AG is a type of inference- time support that works seamlessly for both MAB and CB,
Few-Shot Demonstration We first study whether demon- strating oracle exploration trajectories from UCB as few- shot examples can improve the LLM's ability to perform robust exploration in bandit tasks. A key challenge in apply- ing few-shot learning to decision- tasks like MAB is the increasing context length. Unlike supervised learning, where context is typically fixed, bandit actions depend on the entire past history or condensed history, which either grows linearly with T (steps) or K (actions). This poses a challenge for LLMss, as their ability to effectively utilize
5

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
information can degrade with longer contexts. We sample 5 oracle trajectories from UCB into the L.M context window as demonstrations. Our goal is to see whether the optimal ex- ploration demonstrations can lead to improved exploration performance. Detailed demonstrations are provided in Ap- pendix A.16.
MAB tasks, the interaction horizon (7) differs based on the size of the action space (K): we use T = 1000 for K = 30 and T 200 for K 10. All CB tasks use constant horizon of 200 steps. To ensure statistical significance of the results, we conduct 30 independent runs for each ex- perimental setup. We consider two baselines: Raw History (RH) and Summarized History (SH), as suggested in Kr- ishnamurthy et al. (2024). For CB, as we discussed before, there is no trivial analogue of SH; thus, we focus solely on RH for CB tasks in this study as the baseline.
Oracle Behavior Fine-Tuning (OFT) While in-context few-shot demonstrations offers an inference-time approach to guide the LLM's exploration strategy, fine-tuning allows us to directly optimize the model's parameters for the task. In this approach, we utilize the (CBB-gnnerated trajectories as training data to adjust the LLM's internal representations and decision-makee making mechanisms. Specifically, we fine- tune the L.LM by framing the exploration problem as a language modeling task, where the goal is to predict the next action in the sequence. This is achieved by maximizing the likeelllooodd of the UCB actions given the history of interactions:
Metries We report the relative performance of each model, aggregated across all environment configurations. Simply averaging cumulative rewards across environments of dif- ferent reward distributions and horizons however, obscures the comparison. We instead use the pairwise win-rate to compare the performances. We have 16 configurations for MAB and evaluate 32 models and configurations for CB with 14 models. The list of all the models is provided in Appendix A.14. For each configuration, we compute the cumulative reward over T steps and collect their distribution from 30 independent trials. We then calculate the pairwise win-rate by applying a Student's 's f-test on the reward distri- butions of any pair of configurations to determine if they are statistically significantly different, with a significance level of p < 0.05. The overall win-rate for model is then the percentage of superior performance over all models, crossed with methods and configurations. Details are given in Appendix A.8.
(T) = (ooo yo Dog (at UCB ((BB)) ))}
(a
(
where represents the LLM's policy that we aim to opti- mize. This formulation encourages the LLM to learn the underlying patterns and decision-making logic embedded within the UCB trajectories. By predicting the next action in the sequence, the LLM effectively internalizes the optimal exploration strategy demonstrated by the UCB algorithm. OFT is different from behavior cloning (BC) (Pomerleau, 1991) by learning to encode dynamic, iterative refinement process, while BC focuses on replicating static behavior of another policy (See Appendix A.7).
6.2. Results and Ablations
Overall Performance Comparison Figure presents a comparative overview of in-context few-shot demonstra- tion, oracle behavior fine-tuning, and inference-time algo- rithmic guidance performance across various model sizes and training configurations. Detailed numbers are reported in Table A4 and A5. Few-shot demonstrations exhibited contrasting effects on Gemini-1.5 Flash and Pro. While few-shot learning boosts the performance of Flash beyond the best history contextualization setup. hurts Pro's 's perfor- mance in both MAB and CB. Aligned with the observations in Zheng et al. (2024); Guo et al. (2025), our hypothesis is that few shot examples we manually crafted could dis- rupt the CoT structure in larger models, which requires the few-shot examples to be carefully tuned in order to be help- ful. Further analysis reveals the remarkable effectiveness of oracle behavior fine-tuning. It significantly outperforms both few-shot and baseline approaches in both MAB and CB across all model sizes, even larger ones. This robust improvement highlights the effectiveness of directly optimiz- ing model parameters for the exploration task. Notably, the best fine-tuned Gemini- Flash model surpasses even the Gemini- 1.5 Pro model, highlights its potential as a key tech- nique for enhancing L.M exploration capabilities.
6. Empirical Evaluations
In this section, we empirically evaluate LLMs' in-context exploration capabilities, using BanditBench. We begin with introducing the setup, baselines and metrics in Sec- tion 6. Following this, in Section 6.2, we analyze the per- formance of inference-time guided support, in in-context few- shot demonstration and oracle behavior fine-tuning across various experimental settings, as well as models of different sizes. Additionally, we perform extensive ablation studies on the impact of task difficulty, textual representation of the oracle trajectories, and easy-to-han hasy-to generalization of the distillation methods. We also analyze the types of failures encountered by LLMs in in-context exploration, thereby demonstrating the necessity of developing more advanced algorithms.
1. Setup
Baselines We evaluate the in-context exploration capabili- ties of various LLMs: Gemma-2B, Gemma-9B (Team et al., 2024), Gemini 1.5 Flash, and Gemini 1.5 Pro (Reid et al.,
2024), on 16 MAB tasks (Table A1) and 2 CB tasks. For
6

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
100
ke5, Fany
Bernouli Video
UCB
History
UCB
LinUCB
89.3
Samouli Clothes
Summarized History ISH)
Overall Win- Win- Rate
k=20, à Hard
Overall Win- Rate
Overall Win-Ratee
60-
60-
54.5
Hislory (Rró Far History(AH0
43.0
40
40
40-
Algorttum Guatte (AG)
27.5
28.6
20
20
20
Few-shot
OFT
Few-shot
OFT
OFT
(a) Task Difficulty (MAB).
(b) History Representation, RH vs SH (MAB).
(c) History Representation with and without AG (CB).
Figure 2: Impact of task difficulty and history representation on algorithm distillation. This figure examines how different factors, such as task difficulty and history representation of oracle trajectories, influence the effectiveness of algorithm distillation on the LLM's exploration capabilities. All results are based Gemini-1.5 Flash model. The numbers represent the best model in that setting. Same number indicates the same model.
Flash (RH)
Flash (AG)
Pro (RH)
Pro (AG)
Conversely, fine-tuning exhibits the opposite trend, with a higher win-rate when trained on Duar (65.6) compared to Deasy (54.5). This implies that fine-tuning, with its extensive training data, might be overfitting to the specific nuances of the training distribution, leading to poor generalization when faced with a different task structure.
MAB, K=5
33.6
26.6
48.0
67.6
MAB, K=20
21.9
37.9
43.0
51.6
CB. K=10
0.0
35.7
7.1
57.1
CB, K=30
0.0
57.1
7.1
71.4
Table 1: Situations where Algorithm- Guided Support significantly outperforms Raw History during inference.
Impact of Contextualization We further investigate the effect of contextualization in oracle trajectories. We con- sider two representations in MAB: RH and SH. Results in Figure 2b reveal clear contrast in how these representations affect the two algorithm distillation methods. For few-shot demonstration, SH leads to significantly better performance (50.2% win-rate) compared to RH (27.5% win-rate). This suggests that providing concise, informative summaries of optimal exploration behavior is more effective for few-shot learning than presenting the complete other hand, fine-tuning exhibits the opposite trend. RH has a substantially higher win-rate (65.6) compared to SH (28.3). This indicates that fine-tuning benefits from the richer information present in complete action-reward se- quences, allowing it to learn more nuanced patterns of the optimal exploration strategy. These contrasting preferences for textual representation in oracle trajectories highlight the nuanced ways in which fine-tuning and few-shot learning interact with different types of information. Furthermore, in CB, we observe a significant impact of incorporating AG information into the oracle trajectories for fine-tuning, lead- ing dramatic improvement win-rate, rising from 28.6 to 89.3 (Figure 2c). This suggests that providing LLMs with explicit insights, in addition to the complete action-reward sequence, enhances its ability to learn and generalize the optimal exploration strategy in the CB environment.
Aludrithm-Guided Support Helps on Complex Environ- ments We observe consistent improvements when transi- tioning from RH to AG in two scenarios: (1) larger models like Flash and Pro, and (2) more complex scenarios, such as contextual bandits. Table shows that AG provided con- sistent help when the number of actions is large for both Flash and Pro models. We hypothesize that providing AG is crucial when the action space is large or when decision scenarios are complex.
history. On the
Impact of Task Difficulty We examine whether the choice of oracle trajectories used in both few-shot demon- stration and oracle behavior fine-tur fine-tuning affects the model's performance during inference. To investigate this, select trajectories from two extreme setups. The easiest setup in- volves (Bernoulli. Video, Large Amin. K- = 5), denoted as Deasy, with AG. Conversely, the hardest setup, denoted as Duaed utilizes (Bernoulli, Clothes, Small Amin. K = 20), with RH. Figure 2a illustrates that the choice of oracle trajec- tories significantly impacts the model's performance, with surprising contrast between the two algorithm distillation methods. Few-shot demonstration achieves higher win- rate when using Deasy demonstration (50.2) compared to when using Dhard (43.0). This suggests that the limited ex- amples provided in the demonstrations may be insufficient for the model to effectively utilize them under the higher complexity and subtle reward signals of the harder task.
Algorithm Distillation Generalizes We also conducted experiments to evaluate the distillation algorithm's 's ability to generalize from smaller to larger action spaces (i.e., easy-to-

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Gemma-2B
Gemma-9B
Gemini-1.5 Flash
Gemini-1.5 Pro
Beta (Linear Regret)
0.00
A
X
x
0.05
0.10
0.15
0.20
0
6
4
0
2 Alpha (Sublinear Regret)
6
6
2
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Oracle Behavior Fine-Tuning
Few-shot Demonstration
RH
AG
SH
Optimal (UCB)
Figure 3: Bernoulli MAB in Hard (K=20,, Amin=0.2) We plot the estimated parameters a and B. Smaller and indicate efficient exploration to find the best arm, Algorithms with strong in-context exploration should have a as small as possible and have 3=0. We can see for MAB Hard sctup, lesser models achieved sublincar regret. We show the rest of MAB setups in Table A5, A6.
hard domain generalization). This analysis offers insights into the scalability and adaptability of our approach to more complex domains, such as world recommendation sys- tems and other complex decision-making problems. We report this in Table 2. Using few-shot demonstrations or doing oracle behavior fine-tuning from simple-domain tra- jectories collected (Bernoulli, Easy, K=5) can indeed learn exploration strategies that generalize to a harder domain (Bernoulli, Hard, K=20).
OptFrac steadily rises over time (32.7% 65.0%). while Gemini-1.5 Flash remains nearly flat (9.3% + 10.7%), sug- gesting limited adaptation. To assess directed exploration, we use MinFrac, the fraction of pulls allocated to the least- selected arm. UCB shows a desirable decline (82.3% + 15.3%), indicating early broad exploration followed by ex- ploitation. In contrast, Gemini-1.5 Flash starts low and drops quickly (11.3% 1.1%), implying minimal directed exploration throughout. Together, these metrics demonstrate that Gemini's performance is not driven by meaningful ex- ploration. More discussion in Appendix A.
MAB
Flash (SH)
Flash Few-Shot (SH)
Flash OFT (RH) (Deny on K=5)
Hard
(Dasy on K=5)
K=20
34.0%
43.0%
48.4%
MinFrae / Step
100-th
250-th
500-th
750-th
1000-th
UCB
82.3%
48.6%
27.8%
19.6%
15.3%
Table 2: Hasy Generalization: We collect distillation data from easy bandit tasks to learn the exploration behavior and evaluate on hard bandit tasks. History representation during evalu- ation is in parentheses.
Flash (SH)
10.2%
4.2%
2.1%
1.4%
1.1%
Flash (AG)
11.3%
4.5%
2.3%
1.5%
1.1%
OptFrac
UCB
32.7%
49.4%
58.7%
62.6%
65.0%
Flash (SH)
9.3%
10.1%
10.4%
10.6%
10.7%
Optimality Analysis of Exploration We use two metrics to capture high-level exploration behaviors: (1) MinFrac, proposed by Krishnamurthy al. (2024), captures the frac- tion of pulls allocated the least-selected arm. An ideal algorithm should exhibit high MinFrac during early explo- ration and gets lower as & increases, indicating effective exploration; (2) OptFrac, tracks the percentage of times the optimal arm is pulled. Ideally, this percentage should increase as the process progresses, indicating the model's ability to self- self-improve. Using Flash model and Bernoulli bandit configurations as an example in Table 3, we that with AG, the Flash model on average explores more com- pared to SH and have higher success at identifying the best arm.
Flash (AG)
14.4%
15.6%
16.3%
16.6%
16.8%
Table 3: Optimality of Exploration: We show the measures on the t-th step along the progression of exploration, averaged across Berouuli MAB configurations. Full version with more models in Table A6 and A7.
7. Regret Analysis of LLM Exploration
In this section, we propose a new and more rigorous anal- ysis of the LLM's exploration efficiency using the concept of regret, REG(z). Most bandit algorithms are evaluated by the behavior of R.G((T) as function of T (i.e., the number of interactions), either theoretically empirically. Motivated by this, our goal is to understand the exploration behaviors of various LLMs by characterizing their regret as a function of T. We adopt the following functional form to analyze the regret: S(7) Ai log(T)) Ami + 33 + Ag. The parameters a, 3, A₁ in the equation are all positive real num- bers. X2 is unconstrained. This functional form provides in- tuitive interpretations for the underlying parameters. Specif- ically, a represents sublinear scaling of the regret, which
While model might achieve high performance by chance-e.g. consistently selecting the optimal arm with- out deliberate exploration-we examine its behavior more closely using two metrics. OptFrac measures how often the optimal arm is chosen, revealing whether the model increas- ingly favors the best option. As shown Table 3, UCB's
8

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
is known to be achieved by only the best bandit algorithms (e.g. UCB). The scaling describes a linear growth or the inability of agent to match the optimal policy x². This means a strong algorithm should have as small as possible, and have 3 = 0. This functional form also allows us to see some growth behaviors in-between with both positive a and 3. Details of fitting is in Appendix A. 12. We use the curve fit function in Scikit-learn (Pedregosa al., 2011) fit the cumulative regret curve of UCB and LLMs coupled with different methods. The results of the fitted and B values are presented in Figure 3. For the largest Pro models, ap- plying effective inference-time support, such as AG and SH can achieve nearly sub-linear regret. More intriguingly. for Flash models, fine-tuning for optimal behavior significantly boosts performance, enabling them to attain sub-linear re- gret with a lower a. In contrast, weaker models such as Gemma 2B and 9B appear to remain in the linear regret regime across nearly all methods.
decisions given context, which is distinct from their ability to reason and plan. Second, want to explore whether well-known methods (such as few-shot demonstrations and supervised fine-tuning) can teach LLMs how to explore more optimally. There are many potential societal conse- quences of our work, but they are outside the scope of our paper.
References
Auer, P. Finite-time analysis of the multiarmed bandit prob- lem, 2002.
Bai, C., Zhang, Y., Qiu, S., Zhang, Q., Xu, K., and Li, X. On- line preference alignment for language models via count- based exploration. arXiv preprint arXiv:2501.12735, 2025.
Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. Trans- formers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural infor- mation processing systems, 36:57125 (0:57125-5521,, 2023.
8. Conclusion
In this work, we explored the in-context exploration capabil- ities of LLMs in bandit environments, introducing Bandit- Bench, a comprehensive benchmark designed to rigorously evaluate LLM's performance. Our evaluation reveals that LLMS struggle with in-context exploration when relying solely raw interaction history, while inference-time sup- port significantly improves performance. Motivated by the presence of optimal algorithms in this domain, we inves- tigated methods to integrate these algorithms into LLMSs through both algorithm-guul -rritthh-guided support and algorithm distil- lation via synthesized demonstration data, Notably, these ap- proaches enable smaller models to outperform larger ones in decision-making tasks. However, an optimality gap remains between LLMs and classical optimal algorithms, highlight- ing the need for further research to bridge this gap.
Bibaut, A., Dimakopoulou, M., Kallus, N., Chambaz, A., and van Der Laan, M. Post-conteettull-anddie inference. Advances in neural information processing systems, 34: 28548 28559, 2021.
Brooks, E., Walls, L., Lewis, R. L., and Singh, S. Large lan- guage models can implement policy iteration. Advances in Neural Information Processing Systems, 36, 2024.
Caria, A. S., Gordon, G., Kasy, M., Quinn, S., Shami, S. O., and Teytelboym, A. An adaptive targeted field experiment: Job search assistance for refugees in jordan. Journal of the European Economic Association, 22(2): 781-836, 2024.
SoohassWooo A., Coots, M., Nudell, J., Nyarko, J., Brunskill, E., Rogers, T., and Goel, S. Automated re- minders reduce incarceration for missed court dates: Ev- idence from text message experiment. arXiv preprint arXiv:2306. 12389, 2023.
Software and Data
BanditBench and the inference code have been provided in this GitHub repo and will be updated/mmonioored regularly: https:/ /gi thub. comm/alleanie//VOL.e. You can in- stall the code with: pip install bandi tbench.
Chu, W., Li, L.,, Reyzin, L.,, and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
lednowlesgements
We thank Yaqing Wang for helping some infra data pro- cessing and storage, Aviral Kumar, Yifeng Lu, Haokai Lu, Ice Pasupat, Kefan Dong, Ollie Liu, Deqing Fu for valu- able discussions on the project. We thank Ruijie Zheng for feedback on the code base.
Daw, N. D., O'doherty, J. P., Dayan, P., Seymour, B., and Dolan, R. J. Cortical substrates for exploratory decisions in humans. Nature, 441 441(7795):876-87777 2006.
Felicioni, N., Maystre, L., Ghiassian, S., and Ciosck, K. On the importance of uncertainty in decision-making with large language models. arXiv preprint arXiv:2404.02649, 2024.
Impact Statement
Our goals are two fold first, using the bandit framework to understand whether L.LMs have the ability to make effective

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Gandhi, K., Lee, D., Grand, G., Liu, M., Cheng, W. Sharma, A., and Goodman, N. D. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:2404.0360 2024.
supervised pretraining- In The Twelfth International Con- ference on Learning Representations, 2023.
Liu, O., Fu, D., Yogatama, D., and Neiswanger, W. Dellma: A framework for decision making under uncertainty with large language models. arXiv preprint arXiv:2402.02399 2024a.
Gershman, S. Deconstructing the human algorithms for exploration. Cognition, 173:34-42 2018.
Guo, D., Yang, D., Zhang. H., Song, J., Zhang, R., Xu, R., Zhu, Q. Ma, S., Wang, P., Bi, X., et al. Deepseek-rl: In- centivizing reasoning capability Ilms via reinforcement learning. arXiv preprint arXiv:2501. 12948, 2025.
Liu, Z., Zhou, Z., Wang. Y., Yang, C., and Qiao, Y. Inference-time language model alignment via integrated value guidance. arXiv preprint arXiv:2409.1 17819, 2024b.
Mirchandani, S., Xia, F., Florence, P., Ichter, B., Driess, D., Arenas, M. G., Rao, K., Sadigh, D., and Zeng, A. Large language models as general pattern machines. arXiv preprint arXiv:2307.0472 2023.
Harper, F. M. and Konstan, J. A. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tits) 5(4):1-19, 2015.
He- Yueya, J., Goodman, N. D., and Brunskill, E. Evaluating and optimizing educational content with large language model judgments. arXiv preprint arXiv:2403.02795. 2024.
Mnih, V. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.3602, 2013.
Mudgal, S., Lee, J., Ganapathy, H.,, Li, Y., Wang, T., Huang, Y., Chen, Z., Cheng, H.-T., Collins, M., Strohman, T., al. Controlled decoding from language models. arXiv preprint arXiv:2310. 17022, 2023.
Krishnamurthy, A., Harris, K., Foster, D. J., Zhang, C.,, and Slivkins, A. Can large language models explore in-context? arXiv preprint arXiv:2403.15371 2024.
Nie, A., Chandak, Y., Suzara, M., Malik, A., Woodrow, J., Peng, M., Sahami, M., Brunskill, E., and Piech, C. The gpt surprise: Offering large language model chat a massive coding class reduced engagement but increased adopters' exam performances. Technical report, Center for Open Science, 2024.
Langford, J. and Zhang, T. The epoch-greedy algorithm for contextual multi-armed bandits. Advances neural 2007.
information processing systems, 20(1):96-1, 2007.
Laskin, M., Wang, L.., Oh, J., Parisotto, E., Spencer, S., Steigerwald, R., Strouse, D., Hansen, S., Filos, A., Brooks, E., et al. In-context reinforcement learning with algorithm distillation. arXiv preprint A.V:22210114211. 2022.
Osband, I., Russo, D., and Van Roy, B. (more) efficient reinforcement learning via posterior sampling. Advances Neural Information Processing Systems, 26, 2013.
Lee, J. Xie, A., Pacchiano, A., Chandak, Y., Finn, C., Nachum, O., and Brunskill, E. Supervised pretraining can learn in-context reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Pan, L., Xie, H., and Wilson, R. C. Large language mod- els think too fast to explore effectively. arXiv preprint arXiv:2501.1800 2025.
Pedregosa, F,, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-28301 2011.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandii approach to personalized news article recommendation. In Proceedings of the 19th interna- tional conference on World wide web, pp. 661-670, 2010.
Li, L., Zhang, Y., Liu, D., and Chen, L. Large language models for generative recommendation: A survey and visionary discussions. arXiv preprint arXiv:2309.01157 2023a.
Pomerleau, D. A. Efficient training of artificial neural net- works for autonomous navigation. Neural computation, 3(1):88-97, 1991.
Qu, Y., Wang, B., Jiang, Y., Shao, J., Mao, Y., Wang, C., Liu, C., and Ji, X. Choices are more important than efforts: Llm enables efficient multi-agent exploration. arXiv preprint arXiv:2410.02511, 2024.
Li, I.. H., Hessel, J., Yu, Y., Ren, X., Chang, K.-W., and Choi, Y. Symbolic Sfain-of-though distillation: Small models also" think" step-by-step. arXiv preprint arXiv:2306. 14050, 2023b.
Rahn, N., D'Oro, P., and Bellemare, M. G. Controlling large language model agents with entropic activation steering. arXiv preprint arXiv:2406. 00244, 2024.
Lin, L., Bai, Y., and Mei, Transformers as decision makers: Provable in-context reinforcement learning via
10

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Raparthy, S. C.,, Hambro, E., Kirk, R., Henaff, M., and sequential decision making tasks with in-context learning, arXiv preprint arXiv:2312.03881, 2023.
Xi, Z., Chen, W. Guo, X., He, W., Ding, Y., Hong, B., Zhang, M., Wang. J., Jin, S., Zhou, E., al. The rise and potential of large language model based agents: A survey, arXiv preprint 0tti::2399007664. 2023.
Raileanu, R. Generalization
Reid, M., Savinov, N., Teplyashin, D., Lepikhin, D., Lilli- crap, T., Alayrac. J.-b., Soricut, R., Lazaridou, A., Firat, O., Schrittwieser, J., al. Gemini 1.5: Unlocking multi- modal understanding across millions of tokens of context. arXiv preprint ar arXiv:2403.05530, 2024.
Yancey, K. P. and Settles, B. sleeping, recovering ban- dit algorithm for optimizing recurring notifications. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. PP- 3008-3016, 2020.
Riquelme, C., Tucker, G., and Snoek, J. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprint urXivv:802..00 127, 2018.
Yang, C., Wang. X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. Large language models as optimizers. In The Twelfth International Conference on Learning Represen- tations, 2024. URL id=Bb4VGOWELI.
Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and Yao, S. Reflexion: Language agents with verbal rein- forcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. React: Synergizing reasoning and act- ing in language models. In International Conference on Learning Representations (ICLR), 2023.
Singhal, K., Azizi, S., Tu, T., Mahdavi, S. S., Wei, Chung, H. W., Scales, N., Tanwani, A., Cole-Lewis, H., Pfohl, S., et al. Large language models encode clinical knowledge. Nature, 62077972) 2023.
Yu, P., Xu, J., Weston, J., and Kulikov, I. Distilling system 2 into system 1. arXiv preprint arXiv:2407.06023 2024.
Zheng, S., Mishra, S., Zhang, H., Chen, X., Chen, M., Nova, A., Hou, L., Cheng, H.-T., Le, Q. V., Chi, H., al. Natural plan: Benchmarking Ilms natural lan- guage planning, arXiv preprint arXiv:2406.04 04520, 2024.
Slivkins, A. et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1- 2019.
Sutton, R. S. Reinforcement learning: An introduction. A Bradford Book, 2018
Team, G. Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L., Mesnard, T., Shahri- ari, B., Ramé, A., et al. Gemma 2: Improving open language models at practical size. arXiv preprint 0rXiv:2408.00118 00118, 2024.
Wang, G., Xie, Y., Jiang, Y., Mandlekar, A., Xiao, C., Zhu, Y., Fan, L., and Anandkumar, Voyager: An open- ended embodied agent with large language models. arXiv preprint ar Xiv::3330 16291, 2023a.
Wang, P., Wang, Z., Li, Z., Gao, Y., Yin, B., and Ren, X. Scott: Self-consistent chain-of-thought distillation. arXiv preprint arXiv:2305.01877 2023b.
Wang, Z., Cai, S., Chen, G., Liu, A., Ma, X., and Liang, Describe, explain, plan and select: Interactive planning with large language models enables open-world multi- task agents. arXiv preprint arXiv:2302.01550 2023c.
Wilson, R. C., Geana, A., White, J. M., Ludvig. E. A., and Cohen, J. D. Humans use directed and random explo- ration to solve the explore-cxplae dilemma. Journal of experimental psychology: General, 143(6), 2014.

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
A. Appendix
Multi-Armed Bandit (Clothes)
Contextual Bandit (Movies)
You Al fashion assistant for line boutique powered by a bandit algo- rithm that offers a variety of clothing op- tions from different brands.
You are Al movie recommendation assistant for streaming platform powered bandit algorithm that offers wide variety of films from different studios and genres.
[More Instructions]
[More Instructions]
There are 10 unique movies you can recommend, named Saving Private Ryan (1998) (ActionlrramalWar) Jurassic Park (1993) (ActionlAAvennturllsii--- The Matrix (1999) Action|Sci-FifTTrilll The Silence of the Lambs (1991) (DramalThriller)
There 5 unique clothing items you recommend, named:
Midnight Mirage Mittens, Opulent Oa- sis Overcoat, Infinite Impeccable Jacket, Alluring Apex Apron, Bejeweled Bloom Blazer.
So far have interacted 4 times with the following choices and rewards: Context: This person an 18-ycar-old college/grad student living in Pulaski county, AR. The has numerical values that represent their true implicit preference or true taste for all movies: 10.011, 0.027, -0.020, -0.002, -0.003].
So far you have interacted times with the following choices and rewards: Midnight Mirage Mittens, reward
Opulent Oasis Overcoat, reward I Bejeweled Bloom Blazer, reward
Action: Saving Private Ryan (1998)
Opulent Oasis Overcoat, reward 0 Infinite impeccable Jacket, reward Alluring Apex Apron, reward (
Reward: 4.74 out of
You have new user:
Context: This person a 35-year-old man, working as a lawyer..
Which item will you choose next?
Action:
The problem representation of in-context exploration is represented in text. Detailed prompts for both MAB and CB are provided in Appendix A.
Figure Al:
Raw History
Summarized History with Algorithm-Guide Support
IScenario Description]
[Scenario Description]
[Instructions]
[Instructions]
[List of Actions]
[List of Actions]
Past Raw History:
Summarized History:
Time 1, Action Name, reward Ti
Action Name, chosen times, average reward n
exploration
Time 2, Action Name, reward 12
bonus U1 exploitation bonus é1.
Time 3, Action Name, reward F3
Action Name, chosen times, average reward exploration
Time 4. Action Name, reward r44
bonus U2, exploitation bonus
Which [Action] will you choose next?
Which [Action] will you choose next?
The problem representation of in-context exploration in text. For Summarized History (SH), the text in gray is presented. For Algorithm Guided Support (AG), the pink and yellow are presented along with the text in gray. This schema works for any general algorithm that explicitly compute exploration and exploitation bonus. For UCB, e₁ = pt. Detailed prompts for both MAB and CB are provided in Appendix A.15.
Figure A2:
A.1. Extended Related Work
Several prior works have investigated the use LLMs for decision- decision-making. In one category, numerous studies have deployed LLMs directly as agents decision-making problems such as games (Yao al., 2023; Brooks al., 2024; Shinn al., 2024; Wang al., 2023a; Xi al., 2023). However, fewer works have systematically evaluated LLMs' capabilities in general Decision-making setup, especially in relation to classical concepts in decision-making like exploration. Our work extends the research of Krishnamurthy et al. (2024), who examined LLMs' exploration capabilities in small-scale MAB tasks. Their findings, which showed positive results only with substantial intervention, are consistent with our broader analysis across both MAB and CB tasks at various scales. Mirchandani et al. (2023); Rahn et al. (2024); Felicioni et al. (2024) also evaluated the ability of LLMs to learn in-context and solve bandit-like decision decision-making problems.
The line of research on using LLMs as optimizers faces many similar challenges to in-context decision making, although
12

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
applied different tasks. Yang al. (2024) explored the use of language models as general-purpose optimizers for simple black-hox optimization problems, such as prompt optimization, highlighting that a careful balance of exploration and exploitation is critical. Another relevant line of research focuses on in-context learning for decision-making and reinforcement learning (RL) with domain-specifer transformers. Laskin et al. (2022) distilled demonstrations from RL algorithms into a transformer and showed that the transformer learns to imitate the RI. process to solve new RI. tasks. Similarly, Lee et al. (2024) trained transformers with optimal action labels, showing that the model learns to execute posterior sampling for RL (Osband et al., 2013) in-context, which tailors exploration to the underlying distribution of RL tasks. This area has been further studied by Raparthy et al. (2023); Lin et al. (2023). However, these studies focus on domain-specifee decision-making, whereas our paper examines general-purpose decision-making capabilities in language models.
Our inference-time sooorithm-guider support shares a similar conceptual framework with recent efforts to align LLMs at inference time. These include employing explicit value functions as prefix scorers that trained via KL-regularized RL (Mudgal et al., 2023), and leveraging both implicit and explicit value functions to guide decoding the token and chunk levels at inference time (Liu et al., 2024b). In the realm of algorithm distillation, much of the research on LLMs has concentrated on chain-of-thought (CoT) reasoning (Wang et al., 2023b; Li et al., 2023b), while (Gandhi et al., 2024) focused on search and backtracking. Most methods involve distilling outputs from a "teacher" model either a larger model or slower, system-2 variant of the same model that employs various inference-time techniques, such as search and huff-consiitency--ieee into a student model (Yu et al., 2024). Instead, our approach leverages diverse optimal trajectories directly from classical algorithms, allowing for the efficient generation of abundant training data.
A.2. Details on Multi-Armed Bandit Task
In (stochastic) multi-armed bandit problems, we vary our environment configurations primarily along two key dimensions: 1) action space, where we change the number of actions K and the textual descriptions associated with each action; 2) reward distributions, where we change the parametric distribution of the reward, i.e., the types of reward distributions, and the exploration difficulty, characterized by the gap between the best rest-performing arm and the second-bess arm. A smaller gap makes it harder for the agent to distinguish between optimal and sub-optimal actions, thereby increasing the exploration difficulty. In contrast to the setup in Krishnamurthy et al. (2024), which focuses solely on MAB instances with Bernoulli reward distribution, our expanded setup allows us to systematically analyze LLMs' performance across diverse environments with different action spaces and reward structures.
For the action space, we explore two different sizes: K = 5 for a small action space and K = 20 for a large action space. We also differentiate between two types of action descriptions: Videos, represented as arbitrary two-letter combinations with no semantic meaning such as "Video AA", and Clothes, described using semantically meaningful phrases, such as "Supreme Sylvan Sandals". Regarding reward distributions, we evaluate two types: Bernoulli and Gaussian Bandit. For Bernoulli, the reward r {0, 1) is binary with y* ~ Bernoull(pp)). where P& is the mean for the k-th action. Following Krishnamurthy et al. (2024), the best-performing arm has p& 0.5 + Amin/ /2, while the remaining arms have pa = 0.5 - Amin/ /2. The parameter Amin captures the exploration difficulty, with a larger gap (Amin = 0.5) indicating easy tasks and smaller gap (A (Amin = 0.2) representing hard tasks. For the Gaussian bandit, the rewards are continuous with y ~ NN44,, o). Here 14k ~ (0, a) represents the mean for each action, and the variance a captures the difficulty of exploration. Following Sutton (2018), we study both a = and o 3.
We have 16 configurations for the multi-armed bandit domain, shown in Table A1.
Parameters
Reward Type
Bernoulli
Gaussian
Exploration Difficulty
Easy (0mi. Hard (Ami.. -0.2) Easy (a 1), Hard (a 3)
Number of Items/Actions
Small (k 5), Large (k 20)
Action Description
Videos, Clothes
Table AI: Configuration of the MAB setup.
13

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
A.3. Details on Contextual Bandit Task
For contextual bandit, at each round E [7], the agent is presented with some contextual feature æ (which may consist of both textual descriptions and numeric values) describing the state (and action). The LLM agent æ chooses an action a A. and then a reward r(z, o) is received, which depends on both the context and the chosen action. The goal of the agent is to recommend a personalized movie that a specific user is likely to enjoy. In particular, the observations z: include user-specific features such as age, gender, occupation, and geographical location (county and state), as well as features of the movies. The action space is limited to the top-K most-watched movies in the dataset, with K = 10 for the easy setting and K = 30 for the more challenging setting. At each time step, we provide textual contextual features alongside a 5-dimensional user preference vector uzz The task can easily be scaled up to include more movies, i.e., larger K.
We use the Moviel.ens-IM 1M dataset (Harper & Konstan, 2015) to build the contextual bandit task. It contains 1,000,209 anonymous ratings of approximately 3,900 movies made by 6,040 MovieLens users who joined MovieLens in 2000. For each user, we have the basic demographic information such as age, gender, occupation, and zip code. We further convert zip code to the actual name of the county and state and add these into the user profile description text. Each movie has a title and associated genres. We present these information in the prompt as well.
LinUCB assumes a linear reward model E[r|æ, a] = 0f x, where Rd (Chu et al., 2011). Since we are trying to use tasks to measure the performance of LLM against a theoretically optimal algorithm, we have to build the contextual bandit task in a way that satisfies the LinUCB assumption. An additional issue is that the context window of an LLM is still limited, and we want to restrict the number of movies for the LLM to 10 or 30. So, we first calculate the popular movies by tracking how often users rate each. We sort the list and select the top K movies. Then, we build user preference matrix P E gNVx where N is the number of users and K is the number of movies. To construct the ground-truth reward distribution, we perform low-rank approximation on P. This is done by approximating P with P = UEVT using singular value decomposition (SVD). yielding user embedding matrix U E IR xd movie embedding matrix V E &x and a as the dimension of the embeddings. The diagonal matrix Σ E ddd of the top singular values. In our case, we set tround-truth reward for user and movie j is then computed Tz.j u Σny-
In order to present the full information that was provided to LinUCB to LLM as well, we include the user preference vector in the prompt space, represented by list of 5 floating point numbers. We additionally add descriptions to indicate that this is a user preference vector. We show our full prompt in Figure A13.
A.4. UCB and LinUCB In Table A2, we provide detailed comparison between the exploitation values and exploration bonus used in both UCB and LinUCB.
Algorithm
Task
Value of Arm
UCB
MAB
Vi(a) = Pa((a) +ay (ogg(tt)//((())
Viisper
LinUCB
CB
Vi(a, = NT.0 0a + +ay / (Dr Da + Ia) Ixr.
Visplex
V'Esptore
Table A2: Calculation for the value of each arm/item. The decision rule is a" arg max, Vi(a,
A.5. History Representation in Contextual Bandit
While it is relatively clear-cut for multi-armed bandit what RH and SH correspond to, it is less so for contextual bandit. If we were to perform a similar analysis with LinUCB, RH would correspond to retaining all (context, action, reward) information to estimate the parameter and calculate the uncertainty, while one possibility to realize SH would be to construct the sufficient statistics using running mean and running covariance matrix in LinUCB. However, these statistics are much less interpretable for language models; thus, we do not investigate it.
A.6. Details on Oracle Trajectory Generation
We use UCB as the oracle algorithm to generate the trajectories. Following the notations defined in Section 3, the trajectories are in the form of tuples of (o0( HUC)). a,CB), where each tuple pairs the transformed representation of the history at time t
14

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
and the action uCB from UCB. For MAB, we create trajectories from reward distributions that differ from those used in evaluation. This assesses the LLM'ss ability to generalize across different bandit instances with the same underlying scenario but varying action descriptions and action-reward mappings. We further control the data generation process by varying: (I). Action Description: trajectories are generated from either "Video" or "Clothes" action descriptions: (2). Difficulty: we control the reward gap in the Bernoulli bandit to create "easy" and "hard" instances; (3). Trajectory Contextualization: trajectories are represented either as RH or AG. For CB, we use a fixed dataset and evaluate the LLM's performance on a held-out set of users. While these users are unseen during training, their profiles and preferences remain within the distribution of the training data. This evaluates the LLM's ability to leverage prior knowledge for effective exploration. In CB, we only vary the trajectory representation (RH or AG). In both MAB and CB, each trajectory consists of a sequence of exploration steps: 300 steps for MAB with K = 5 arms, 1000 steps for MAB with K = 20 arms, and 200 steps for CB, We generate 50 trajectories for 2 MAB domain configurations (the easiest and the hardest configuration) with 2 trajectory contextualizations, and 200 trajectories for CB with 2 trajectory contextualizations This results in 4 algorithm distillation datasets for MAB and datasets for CB.
A.7. Difference Between Algorithm Distillation and Behavior Cloning
Optimal Behavior Fine-tuning (OFT) and Behavior Cloning (Pomerleau, 1991) share many similarities. Although both approaches rely on maximum-likelihodn learning, their objectives are different: OFT seeks to encode a dynamic, iterative refinement process, while BC focuses on replicating static behavior. OFT is designed for algorithm distillation, focusing on capturing a sequence of self-improvement behaviors, and generalization across any new test domains. In contrast, BC aims to learn policy by mimicking static policy, with no iterative improvement between trajectories.
This difference becomes very clear when we think of an example. We have a deterministic Markov policy æ that we can use to create this dataset. We call this the sampling policy. To create a behavior cloning dataset, DEc, during dataset construction, for the same state 8, the policy remains unchanged, which the means (als) remains the same in the entire dataset. To create algorithm distillation dataset DOFT, the sampling policy is self-improving as the data collection continues, <{ass) changes even for the same s between early and late trajectories of this dataset.
A.8. Example of Win-Rate Calculation
We report the relative performance of each model, aggregated across all enviromment configurations. Simply averaging cumulative rewards across environments of different reward distributions and horizons however, obscures the comparison. We instead use the pairwise win-rate to compare the performances. We have 16 configurations for MAB and evaluate 32 models (4 LLMs crossed with different methods), and configurations for CB with 14 models (2 LLMs crossed with different methods). The list of all the models is provided in Appendix 14. For each configuration, we compute the cumulative reward over T steps and collect a distribution of cumulative rewards from 30 independent trials. We then calculate the pairwise win-rate by applying a Student's t-test on the reward distributions of any pair of configurations to determine if they are statistically significantly different, with a significance level of p < 0.05. If one model has significantly higher reward than the other, we consider it a win. If the difference is not statistically significant, the result is deemed inconclusive and not counted as a win. For each model, we calculate its win rate against every other model across all configurations. The overall win-rate for a model is then the percentage of superior performance over all models, crossed with methods and configurations.
In each configuration, we compute one model's win-rate against all other models. For MAB, we have 16 configurations and 34 models. For CB, we have 2 configurations and 16 models. Finally, the model's overall win-rate is then determined by averaging its win-rates across all models. For example, in MAB, if we only have models: Gemma-2B, Gemini- Flash, and Pro. Gemini-1. Flash have higher expected cumulative reward than Gemma-2B in 12 out of 16 configurations (12/16), but only higher than Gemini-1.5 Pro in 4 out of 16 configurations (4/16), Gemini-Flash 1.5 will have an overall win-rate, on average, 8/16=0.5.
A.9. Benchmark Evaluation Cost
We calculate and report the inference time cost for evaluating 30 trials for one agent with the longest contextual representation (which incurs the highest cost). This means, for MAB tasks, we evaluate using Raw History (RH) and for CB tasks, we evaluate using Algorithm-Guite Guided Support (AG). The total cost for MAB Full (over 16 configurations and 32 models) is $15897.6 6 for Gemini-1. 1.5 Flash and for CB (2 configurations and 14 models) is $14491. for Gemini- 1.5 Flash. We will release all logged experiment data of all models for public analysis and comparison. We also recommend using subset of
15

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Core
HardCore
HardCore+
Full
MovieBench
Gemini-1.5 1.5 Flash
$31.05
$14.91
$39.18
$83.44
$31.05
Gemini-1.5 Pro
$517.54
$248.55
$652.98
$1390.69
$517.54
GPT-4o Claude-3.5-sonnet
$1035.07
$497.11
$1305.96
$2781.38
$1035.07
$1243.00
$596.91
$1567.91
$3339.53
$1243.00
Table A3: Maximal inference cost for single agent/task configuration over 30 trials. Price calculated on 1/30/2022. Core, HardCore and HardCore+ refer to specific subset of the MAB configurations. The exact details are the code included in the supplementary material. In this paper, we used Full (MAB) and MovieBench (CB) of the benchmark.
our configurations for MAB (HardCore and HardCore+) to reduce evaluation cost.
A.10. Details Discussion of Results
Overall Performance Comparison Figure presents comparative overview of in-context few-shot demonstration, oracle behavior fine-tuning, and inference-time algorithmic guidance performance across various model sizes and training configurations. Few-shot demonstrations exhibited contrasting effects on Gemini-1.5 Flash and Pro. While few-shot learning boosts the performance of Flash beyond the best inference-time setup, it surprisingly hurts Pro's performance in both MAB and CB. Aligned with the observations in Zheng et al. (2024), our hypothesis is that few shot examples we manually crafted could disrupt the CoT structure in these larger models, which requires the few-shot examples be carefully tuned in order be helpful. Further analysis reveals the remarkable effectiveness of oracle behavior fine-tuning. It significantly outperforms both few-shot and baseline approaches in both MAB and CB across all model sizes, even larger ones. This robust improvement highlights the effectiveness of directly optimizing model parameters for the exploration task. Notably, the best fine-tuned Gemini- 1.5 Flash model surpasses even the highest- seafher-perforingg Gemini- 1.5 Pro model. The significant advantage of fine-tuning over few-shot learning and baseline performance highlights its potential as a key technique for enhancing LLM exploration capabilities.
Impact of History Representation in Context We examine how different contextualizations and inference-time support tochniques-namely RH, SH, and IG-inffuence model performance, each utilizing distinct history contextualization functions Φ, as introduced in Section 3. It is worth mentioning that in the MAB setup, both SH and AG significantly reduce context length compared to RH, to O(K) instead of O()) As illustrated in Table A4, leveraging inference-time support (i.e., SH and AG) significantly enhances exploration performance across all models. This supports the intuition that effective in-context exploration requires more than memorizing input-output pairs; it demands reasoning to extract sufficient statistics from raw data and utilize them effectively for balancing exploration and exploitation. However, the exact benefit of incorporating UCB-style information in the MAB setup remains uncertain. We hypothesize that under MAB, the exploitation value and exploration bonus are straightforward transformations of the empirical mean and the number of times each arm has been pulled (a), and that the LLM has the capacity learn the functional form efficiently. In CB, we compare AG RH and find substantial improvement. This gap is particularly significant, as learning the exploitation value and exploration bonus in this scenario requires the model to implicitly solve ridge regression and determine the appropriate functional form of the high-probability confidence bound, making it a more complex reasoning task. The algorithmic guide approach can thus be seen as LLMs calling external tools to compute sufficient statistics required for optimal exploration.
Multi-Armed Bandit
Contextual Bandit
Inference-Time Support
Gemma-2B
Gemma-9B
Flash
Pro
Flash
Pro
Raw History (RH)
7.6
10.5
27.7
45.5
0.0
7.1
Summarized History (SH)
10.5
5.3
34.8
60.0
Algorithn-Guided Support (AG)
4.9
4.1
32.2
59.6
46.4
64.3
UCB / LinUCB
90.6
96.4
Table A4: Inference- Time Support Results: Overall Win-Rate (%) of different inference support. Flash and Pro refer Gemini-1.5 Flash and Pro respectively, Unlike SH, AG can work for both MAB and CB. Refer Section 5.1 for details.
16

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
(a) Few-shot Demonstrations
(b) Oracle Behavior Fine-Tuning
MAB
CB
MAB
CB
Flash
Pro
Flash
Pro
Flash
Pro
Flash
Pro
Raw History (RH)
27.5
39.1
3.6
7.1
Raw History (RH)
65.6
28.6
Eggorithm-Guidess Support (AG)
50.2
56.4
60.7
25.0
Algorithm- Guideed Support (AG)
28.3
89.3
Table A5: Algorithm Distillation Results: Overall Win-Rate (%) of different algorithm distillation methods. Flash and Pro refer to Gemini-1 Flash and Pro respectively. Best achieved performances are in bold. The history contextualization used in oracle trajectory and inference-time support are the same. We conduct a few ablations in Figure A3.
Impact of Task Difficulty in Distillation Datasets We examine whether the choice of oracle trajectories used in both in-context demonstration and oracle behavior fine-tuning significantly affects the model's performance during inference. To investigate this, we select trajectories from two extreme setups. The casiest setup involves (Bernoulli, Video, Large Amin. K = 5), denoted Deasy. with AG. Conversely, the hardest setup, denoted Dhard utilizes (Bernoulli, Clothes Small Ami. K- = 20), with RH. Figure 2a illustrates that the choice of oracle trajectories significantly impacts the model's performance, with surprising contrast between the two algorithm distillation methods. In-context demonstration achieves a higher win-rate when using Dansy as demonstration (50.2) compared to when using Daard (43.0). This suggests that the limited examples provided in the demonstrations may be insufficient for the model to effectively utilize them under the higher complexity and subtle reward signals of the harder task. Conversely, fine-tuning exhibits the opposite trend, with higher win-rate when trained on Drand (65.6) compared to Deasy (54.5). This implies that fine-tuning, with its extensive training data, might be overfitting to the specific nuances of the training distribution, leading to poor generalization when faced with different task structure.
Impact of Contextualization We further investigate the effect of contextualization in the oracle trajectories. We consider two representations in MAB: RH and SH. The results in Figure 2b reveal a clear contrast in how these representations affect the two algorithm dis- tillation methods. For few-shot demonstration, SH leads to significantly better performance (50.2% win-rate) compared to RH (27.5% win-rate). This suggests that providing concise, informative summaries of optimal exploration behavior is more effective for few-shot learning than presenting the complete raw history. On the other hand, fine-tuming exhibits the opposite trend. RH has a substantially higher win-rate (65.6) compared to SH (28.3). This indicates that fine-tuning benefits from the richer information present in complete action-rewar sequences, allowing it to learn more nuanced patterns of the optimal exploration strategy. These contrasting preferences for textual representation in oracle trajectories highlight the nuanced ways in which fine-tuning and few-shot learning interact with different types of information. Furthermore, in CB, we observe significant impact of incorporating algorithm gigorithm-guided guided (AG) information into the oracle trajectories for fine-tuning. Augmenting RH with AG details, including the exploitation value and exploration bonus, leads to a dramatic improvement in win-rate, rising from 28.6 to 89.3 in Figure 2c. This suggests that providing the LLM with explicit insights into the underlying decision decisiion-mainnn making process of the oracle algorithm (UCB, in this case), in addition to the complete action-reward sequence, significantly enhances its ability to learn and generalize the optimal exploration strategy in the CB environment.
Fewshot
Oracle Trajectory
RH
3.6
42.9
RH
10.7
60.7
AG
RH
AG
OFT
Oracle Trajectory
RH
28.6
64.3
RH
+
28.6
89.3
AG
RH
AG
Figure A3: Context Rep- resentation Alignment.
Impact of Context Representation Alignment Our experiments also reveal an interesting interplay between the presence of algorithm-guided information (AG) in both the oracle trajectories and inference. In the CB setting, providing AG during inference consistently boosts performance, regardless of whether AG was used in oracle trajectories. This is clearly demonstrated in Figure A3, where the right column (with AG at inference time) exhibits higher win-rates than the corresponding left column across all training conditions. This suggests that the LLM can effectively leverage this information even if it wasn't explicitly trained on it, highlighting the inherent value of structured guidance for decision- making. Furthermore, we observe that incorporating AG into few-shot demonstrations improves exploration even when AG is absent during inference (e.g., Fewshot, RH 3.6 to RH +AG 10.7). This indicates that exposing the LLM to AG in oracle trajectories, even in a limited capacity, can enhance its ability to extract relevant patterns from RH. We hypothesize that AG helps the LLM learn to focus on the most informative aspects of the history, which generalizes even when AG is not
17

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
provided during inference.
A.11. Details on Exploration Optimality Analysis
There are two types of failures one can expect bandit problem:
1. Over-exploration on suboptimal choices which results lower exploration efficiency: over-exploration happens when the algorithm spends much time exploring suboptimal choices, reducing overall efficiency. This behavior be quantified using the MinFrac metric (Krishnamurthy al., 2024), which measures the fraction of pulls allocated to the least-selected arm. An ideal algorithm should exhibit high MinFrac during early exploration (when 7 is small) and low Frcc as T increases (indicating effective exploitation).
2. Failure to identify the optimal arm: this occurs when the algorithm struggles to converge on the best option over time. To capture this, we compute the percentage times an optimal arm is pulled at different time steps (OptFrac). Ideally, this percentage should increase the process progresses, indicating the model's s ability to self-improve.
We report these metrics specific time steps over total of T time steps. For convenience in visualizing the results in table, we select the 10%, 25%, 50%, 75%, and 100% (final) time steps. There are 1000 steps for the Bernoulli The reported numbers are from Bernoulli Bandit, the metries are averaged across different configurations.
MinFrac (%)/ Step
100-th
250-th
500-th
750-th
1000-th
UCB
82.3
48.6
27.8
19.6
15.3
Gemma-28 2B (SH)
0.0
1.0
0.5
0.4
0.3
Gemma-20 2B (AG)
0.0
0.6
1.1
1.9
2.7
Gemma-90 9B (SH)
6.9
11.2
16.9
15,4
16.5
Gemma- 9B (AG)
5.8
11.8
17.3
19.6
22.9
Gemini- Comini--1.5 Flash (SH)
10.2
4.2
2.1
1.4
1.1
Gemini- 1omini--..5a Flash (AG)
11.3
4.5
2.3
1.5
1.1
Gemini- 1.5 Pro (SH)
79.0
40.0
20.6
13.9
10.5
Gemini- 1.5 Pro (AG)
73.8
37.1
18.9
12.7
9.5
Table A6: Over-exploration Rate (MinFrac): MinFrac measures the fraction of pulls allocated to the least-selected arm We show the measures the t-th step along the progression of exploration.
OptFrac (%) Stop
100-th
250-th
500-th
750-th
1000-th
UCB
32.7
49.4
58.7
62.6
65.0
Gemma-21 (SH)
10.1
10.3
10.2
10.1
10.1
Gemma-21 (AG)
12.8
12.3
12.4
12.2
12.2
Gemma-9B (SH)
5.8
6.7
7.4
7.8
8.0
Gemma-9B (AG)
6.6
7.3
6.7
6.6
6.6
Gemini-1 1.5 Flash (SH)
9.3
10.1
10.4
10.6
10.7
Gemini-1.5 1.5 Flash (AG)
14.4
15.6
16.3
16.6
16.8
Gemini-1.5 1.5 Pro (SH)
15.1
19.1
21.8
22.9
23.5
Gemini-1.5 Pro (AG)
11.9
17.7
21.6
23.1
23.9
Table A7: Fraction of Pulls on the Optimal Arm (OptFrac): OptFrac measures the fraction of pulls overall on the optimal arm We show the measures the i-th step along the progression of exploration.
model could, in theory, achieve high performance by consistently choosing the optimal arm even if it rarely explores- by chance. To address this, we include analysis of the model's exploration behavior using metric called OptFrac, which measures how often the optimal arms are selected. As shown in Table A7, UCB steadily increases its OptFrac over time (32.7% + 49.4% + 58.7% + 62.6% + 65.0% over 1000 steps), indicating a growing focus on the optimal arm. In contrast, Gemini-1. 1.5 Flash remains largely flat (9.3% + 10.1 + 10.4% + 10.6% + 10.7%), suggesting that it does not significantly shift its behavior toward the optimal arm. This supports our claim that the model does not accidentally achieve optimal performance by randomly selecting the best arm without meaningful exploration.
18

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
We then analyze exploration dynamics in more detail, such as whether the model engages in random or directed exploration. In our analysis, we include metric called MinFrac, which measures the fraction of pulls allocated to the least-selected arm. This captures the extent to which the model explores less-visited options, which can be understood exploration." Ideally. this value should be high early on (indicating strong directed exploration), and then decrease as the model gains experience and focuses on better-performing arms. As shown in Table A6, UCB exhibits this expected trend, with MinFrac values decreasing over time: 82.3% + 48.6% + 27.8% + 19.6% + 15.3%. In contrast, Gemini- 1.5 Flash starts with a much lower MinFrac and declines rapidly (11.3% - 4.5% + 2.3% + 1.5% - 1.1%), suggesting it lacks meaningful directed exploration from the outset.
form of "directed
A.12. Details Fitting Regret Function
In this section, we aim conduct a more rigorous analysis of the LLM's exploration efficiency using the concept of regret, (m.((T). Most bandit algorithms are evaluated by the behavior of RFG(()) as function of T (i.e., the number of interactions), either theoretically or empirically, Motivated by this, our goal is to understand the exploration behaviors of various LLMs by characterizing their regret as a function of T. To achieve this, we adopt the following functional form to analyze the regret:
d1 log(T)) Amin
J(T)-
+BT + +22
The three parameters a, 3, Ar in the equation are all positive real numbers. 22 is unconstrained. Amin captures the gap between the best and second best arm. This functional form provides intuitive interpretations for the underlying parameters. Specifically, log(T) represents sublinear scaling of the regret, which is known be achieved by only the best bandit algorithms (e.g. UCB and Thompson Sampling). The T scaling deseribes a linear growth the inability of agent to match the optimal policy x². This means strong algorithm should have a as small as possible, and have 3 = 0. This functional form also allows us to see some growth behaviors in in-between with both positive a and [..
We use the curve fit function in Seikit-learn (Pedregosa al., 2011) to fit the cumulative regret curve of UCB and LLMs coupled with different methods (i.e., inference-time algorithm-guided support, in-context demonstration, and optimal behavior fine-tuning). The results of the fitted a and 3 values are presented in Figure 3. For the largest Pro models, applying effective inference-time support, such as AG and SH can achieve nearly sub-linear regret. More intriguingly, for Flash models, fine-tuning for optimal behavior significantly boosts performance, enabling them to attain sub-linear regret with a lower a. In contrast, weaker models such as Gemma 2B and 9B appear to remain in the linear regret regime across nearly all methods.
We perform the same analysis with the cumulative regret function on MAB in the Hard Difficulty setting. We can see that in Figure 3, a lot fewer LLM models achieved 8 = O, which means achieving the desirable logarithmic sublinear regret that algorithms like UCB and Thompson Sampling have.
In the MAB-Hard setting, we can see that more models are having non-zero 8, meaning these models have linear cumulative regret, which indicates lack of in-context seff-improvement, because the model is not selecting the optimal arm more and more frequently as T increases. However, we can see that generally Optimal Behavior Fine-Tuned models are doing better.
To verify that our functional form fits the data (empirical cumulative regret curve) well, we show a few figures of our fitted curve and actual data. In Figure A4, we show how the learned function (T) fit the actual empirical cumulative regret curve.
In Figure A4, it is interesting to see that the function we choose exhibit the behavior of pushing either a or / to 0, either of the two describes the trend better. We note that although the fit is not perfect, the MSE is relatively small compared to the data we are trying to fit. For a cumulative regret as large as 100 at some time step T, our fitted function cean still maintain an MSE of 0.22.
We additionally add the analysis for the MAB Gaussian bandit. The instance optimality gap Amin is characterized by the KL-divergence of the Gaussian reward distribution between the best arm and the second best arm. We show the result in Figure A6. The trend is somewhat similar to Bernoulli bandits, where smaller models perform much worse than larger models.
19

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Gemma-2B Raw History (easy domain)
Gemini-1.5 Pro + Raw History (easy domain)
120
Cumulative Regret
100
Cumulative Regret
80
0.3963
0,0000
15
0,0000
2.2964
0.0606
A2 0.2248
60
À = 0.0371
MSE 0.2220
10-
A; = -0 -0.6356
MSE 0.3868
40
20
Data
Data
Fitted
Fitted
50
100
150
200
250
300
50
100
150
200
250
300
Time step (T)
Time step (T)
(a) Example of Linear Cumulative Regret
(b) Example of Sublinear Cumulative Regret
ucb (easy domain)
Cumulative Regret
a 0.7132 0.0000
Â1 1.6519
MSE 0.1304
2-
0-
Data Fitted
-2
0
50
100
150
200
250
300
step (T)
(c) Example of Sublinear Cumulative Regret
Figure A4: Examples of how our function fits different empirical cumulative regret curves. T indicates number of times the agent interacted with the task.
A.13. Evaluation Implementation Details
We run each model under each configuration for 30 trials. We set the random seed to be the same as trial id, starting from to 29. This random seed determines the reward distribution for MAB and the sequence of users the algorithm encounters in CB. For the LLM calls, we use standard API calls and set the sampling temperature to 1.0 (range=[0.0,, 2.0]). The default
API (2024-08 to 2024-09) uses Top-P-0.95 sampling, and Top-K=40.
A.14. Full List of Models
We provide a full list of models evaluated for MAB and CB. The model is represented using A with being the model, with being the inference-time technique.
MAB Models
1. Few-Shot Gemma-9B, (Bernoulli, Clothes, 20, Small Amin) RH
0.029
2. Few-Shot Gemma-2B, (Berouull,, Clothes, K 20, Small Amin) RH
0.029
3. Gemma-9B AG
0.041
4. Fewshot Gemma-2B with (Bernoulli, Video, K = 5, Large Amin)
SH
0.043
5. Fewshot Gemma-2B with (Bernoulli, Clothes, K = 20, Small Amin)
SH
0.045
6. Fewshot Gemma-2B with (Bernoulli, Video, K = 5, Large Amin) = RH
0.047
7. Gemma-2B AG
0.049
8. Gemma-9B SH
0.053
9. Fewshot Gemma-9B with (Bernoulli, Video, Large Amin)
RH
0.072
10. Gemma-2B = RH
0.076
20

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Gemma-2B
Gemma-9B
Gemini-1.5 Flash
Gemini-1.5 Pro
Beta (Linear Regret)
0.0
0.2
+
0.4
2
4
2
4
0
4
0
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Oracle Behavior Fine-Tuning
Few-shot Demonstration
SH
Optimal (UCB)
Figure A5: MAB in Easy (K=5, 00.5:
We plot the estimated parameters a and 3. Smaller a and indicate more efficient exploration to find the best arm. Algorithms with strong in-context exploration should have a as small as possible and have 3=0.
11. Fewshot Gemma-90 BB with (Bernoulli, Clothes, K = 20, Small Amin)
SH
0.088
12. Fewshot Gemma-9B with (Bernoulli, Video, K = 5, Large Amin) = SH
0.092
13. OFT Flash with (Bemoulli, Video, K = 5, Large Ami)) AG = AG
0.104
14. Gemma-2B
SH
0.105
15. Gemma-9B RH
0.105
16. Fewshot Flash with (Bernoulli, Clothes, K = 20, Small Amin)
RH
0.152
17. Fewshot Flash with (Bernoulli, Video, = 5, Large Amin) = RH
0.275
18. Gemini-1.5 Flash = RH
0.277
19. OFT Flash with (Berouuli,, Clothes, K 20, Small Amin) AG = AG
0.283
20. Gemini-1.5 Flash = AG
0.322
21. Gemini-1.5 Flash = SH
0.348
22. Fewshot Pro with (Bernoulli, Video, K = 5, Large Amin) = RH
0.381
23. Fewshot Pro with (Bernoulli, Clothes, K 20, Small Amin)
RH
0.391
24. Fewshot Flash with (Bernoulli, Clothes, = 20, Small Amin)
SH
0.430
25. Gemini-1.5 Pro = RH
0.455
26. Fewshot Flash with (Bernoulli, Video, = 5, Large Amin)
SH
0,502
27. Fewshot Pro with (Bernoulli, Clothes, K = 20, Small Amin)
SH
0.525
28. OFT Flash with (Beroulli,, Video, 5, Large Amin) RH
RH
0.545
29. Fewshot Pro with (Bernoulli, Video, K 5, Large Amin) = SH
0.564
30. Gemini-1.5 Pro => AG
0.596
31. Gemini-1.5 Pro
SH
0.600
32. OFT Flash with (Bernoulli, Clothes, K 20, Small Amii) RH = RH
0.656
33. UCB
0.906
CB Models
1. Gemini-1.5 Flash
RH
0.000
2. Fewshot Flash with RH
RH
0.036
21

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Gemma-2B
Gemma-9B
Gemini-1.5 Flash
Gemini-1.5 Pro
Beta (Linear Regret)
0-
1
2
X
3-
20
10
0
20
10
20
10
20
10
0
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Oracle Behavior Fine-Tuning
Few-shot Demonstration
X
RH
AG
SH
Optimal (UCB)
(a) Gaussian MAB in Easy (K=5,, a=1 and o=3, Ammm-03391
Gemma-2B
Gemma-9B
Gemini-1.5 Flash
Gemini-1.5 Pro
Beta (Linear Regret)
*
x
à
2
4
7.5
5.0
2.5
0.0
2.5
0.0
7.5
5.0
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Alpha (Sublinear Regret)
Oracle Behavior Fine-Tuning
Few-shot Demonstration
X
RH
AG
A
SH
*
Optimal (UCB)
(b) Gaussian MAB in Hard (K=20, a=1 and 0=3, Amin 0.005).
Figure A6: We plot the estimated parameters and B. The difficulty level is determined by Amin.
3. Fewshot Pro with RH RH
0.071
4. Gemini-1., 1.5 Pro
RH
0.071
5. Fewshot Flash with RH
RH
0.107
6. Fewshot Pro with RH
AG
0.250
7. OFT trained with RH
RH
0.286
8. OFT trained with AG
RH
0.286
9. Fewshot Flash with RH
AG
0.429
10. Gemini-1.5 Flash
AG
0.464
11. Fewshot Flash with AG AG
0.607
OFT trained with RH AG
0.643
13. Gemini-1.5 1.5 Pro + AG
0.643
14. OFT trained with AG AG
0.893
15. LinUCB
0.964
A.15. Scenario Prompts
We provide of prompts that used in each scenario. For Multi-Arm Bandit, include the following prompts:
1. MAB, Bernoulli Bandit, 5. Raw History (RH), Video Action Description (Figure A7), Clothes Action Description (Figure A8)
22

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
2. MAB, Bernoulli Bandit, K 5, Algorithm-Guiddd Support (AG), Clothes Action Description (Figure A9), Video Action Description (Figure A10)
3. MAB, Gaussian Bandit, K = 5, Raw History (RH), Video Action Description (Figure A11), Clothes Action Description (Figure A12)
For Contextual Bandit, we include the following prompts:
1. CB, K 10, Raw History (RH) (Figure A13)
2. CB, K 10, Raw History (RH) with Agorithm-GGiiedd Support (AG) (Prompt Part Figure A14, Prompt Part 2
Figure A15).
For OFT, we use the same prompt as shown in the figures above. The LLM generates the next action token conditioned on the entire prompt, and we compute the negative log-likelihood loss over the action tokens, with the action chosen by UCB/LinUCB algorithm.
A.16. Examples of few-shot demonstrations
We provide examples of how few-shot prompt being used. We include few-shot demonstrations from optimal exploration trajectories before past interaction history (without the task description and instruction). We show two examples to illustrate that how few-shot demonstrations domain match with evaluation domain:
1. MAB, Benoulli Bandit, Video Action Description, K 5. Raw History (RH), with Few-shot Demonstrations from Video Action Description, K 5, Raw History (RH) (Figure A16)
2. MAB, Benoulli Bandit, Video Action Description, K = 5, Raw History (RH), ith Few-shot Demonstrations from Clothes Action Description, K = 5, Raw History (RH) (Figure A17)
You video recomrendation systen powered bandit algorithn for onl streaning platforn. There are 5 videos available in your library, titled [A, 8, AI, 8s, E]. based their viewing history
user logs the platforn, you select preferences.
You engage user by recomnending videos they are likely Each time suggestions,
watches recomnended video, you update recommendation model refine future
enhancing
satisfaction and platform engagement.
in situations requires balancing exploration and exploitation. Yau need to explore to try out all of the videos and find thase high rewards, but you have exploit the information that you to accunulate rewards.
good strategy optinize
10
12
far you played times the following choices rewards: A video. reward
14
15
videa, Al video, reward video, reward
16
17
18
videa, reward
19
A video, reward
21
Which video will you choose next? PLEASE RESPOND ONLY MITH A. B. AI, B5, E AND NO TEXT EXPLANATION.
Figure A7: Aum Bandit: Bernuuli,, Video Action Description, K = 5, Raw History.
23

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are an AI fashion assistant for an online boutique powered by a bandit algarithn that offers a variety of clothing options
different brands.
There are 5 unique clothing itens you can recommend, naned [Midnight Mirage Trousers, Opulent Oasis Overcoat, Blazer].
Impeccable Jacket, Supreme Spectrum Slippers, Bejeweled When customer visits the online store, assess their style preferences and shopping history choose an iten to suggest.
You ain to match the custoner with clothing they most likely purchase and enjoy. Each time a customer buys a recammended item, you adjust your recommendation algorithns to better predict and preferences.
good strategy to optinize and exploitation. You need to explore to out all of the clothing brands and find those
in situations requires balancing exploration
with high rewards. but you also have to exploit the information that you have to accunulate rewards.
10
11
12
far you Midnight Mirage Trausers iten, reward 8 opulent dasis Overcoat item, reward
played
Following choices
13
14
15
Infinite Inpeccable Jacket iten, reward
16
Supreme Spectrun Slippers iten, reward Bejeweled Bloon Blazer item, reward Opulent Gasis Overcoat item, reward
18
19
20
Which iten will you choose next? PLEASE RESPOND ONLY WITH Midnight Nirage Trausers, Opulent Oasis Overcoat, Infinite impeccable Jacket, Suprene Spectrun slippers, Bejeweled Bloom Blazer No TEXT EXPLANATION.
21
Figure A8: Multi-Arm Bandit: Bernoulli, Clothing Action Description, K 5, Raw History.
You are an AI fashion assistant for an online boutique that offers a variety clothing aptians from different brands.
There are 5 unique clothing itens you can recommend, naned
Sheen taithful Fantasy Frock,
Supreme Sylvan Sandals,
Bespoke Bliss Blouse iten.
Silk Spectrun Slip visits iten to suggest.
store, you
preferences shopping history choose
You Each time customer buys recommended item, adjust your recomendattion algorithns to better predict and neet future customer preferences.
customer clothing they are most likely purchase enjoy.
10
11
good strategy to optinize for reward in these situations requires balancing exploration and exploitation. Yau need to explare to try out all of the elothing brands and find those information that you
12
you alse have exploit accunulate rewards.
rewards,
14
15
following choices Stellar Sheen Shawl item, 1 time, avg reward e, exploration bonus 1.09, exploitation value 0.88
far you played
rewards:
16
17
Faithful Fantasy Frock item, time, avg reward 1, exploration bonus 1.09, exploitation value 1.00
18
Supreme Sylvan Sandals item. I time. avg reward 8, exploration bonus 1.00, exploitation value 8.00
19
Bespoke Bliss Blouse item, avg reward 6, exploration bonus 1.00, exploitation value 6.28
Spectrun iten. Which clothes item will choase next?
avg reward exploration bonus 1.00, exploitation
21
23
Figure Multi-Aro Bandit: Bernoulli, Clothing Action Description, K 5, Algorithmic Guide.
24

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are video recomendsation systen powered by a bandit aigorithm for an online streaning platforn. There videos available your library, titled
AA
Вм
CQ
CP
When user logs into the platforn, you select a video to recommend based on their viewing history and preferences.
You ain to engage the user by recomnending videos that they are likely to watch.
recomnended video, you update your recomnendation model refine future suggestions, enhancing user satisfaction and platforn engagement.
11
good strategy to optinize for reward in these situations requires balancing exploration and exploitation. You need to explore to out all of the videos and find those with high rewards, but you alse have to exploit the information that you have to accurulate rewards.
12
13
14
13
So far you have played 4 times with the following choices and rewards:
video. tine. reward exploration bonus 1.00, exploitation
17
BS video. tine,
reward exploration bonus 1.00, exploitation value 1.00 video. tine. avg reward 8, exploration bonus 1.00, exploitation value 8.00
18
video, reward exploration bonus 1.80, exploitation value 0.08
20
CP video, 1 tine, avg reward 8, explaration bonus 1.00, exploitation value 8.00 which video will you choose next?
22
Action:
Figure A10: Multi-Arm Bandit: Beroulli, Video Action Description, K = 5, Algorithmic Guide.
You are video recommendation systen powered by a bandit algorithn for an online streaning platforn. videos available your library, titled [A, CX, AT AQ, S]. When user logs into the platforn, select video to recommend based their viewing history and preferences..
You ta engage the tach time a user watches reconnended video, you update your recommendation model to refine future suggestions.
recomnending videns that they likely watch.
enhancing user satisfaction and platforn engagement.
good stratagy to optinize for reward in these situations requires balancing exploration and exploitation. Yau need to explare to try aut all of the videos and find those with high rewards, but you alse have exploit the information that you have accurulate rewards.
11
13
So far have played 6 times with the following choices and rewards:
video, reward 2.8705558227288694
15
CX video, reward 5.846038662978072
16
AF video, reward -4.843037870451999
video, reward 5.93791e107405489
18
S video, reward -4.85633682935551
19
video,
6.2466398842187495
20
video will you choose next? PLEASE ONLY A, CX, AF, AQ,
22
Figure All: Multi-Arm Bandit: Gaussian, Video Action Description, K 5, Raw History.
25

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are an AI fashion assistant for an online boutique powered by a bandit algerithn that offers a variety of clothing options from diffarent brands.
There are 5 unique clothing itens you can recommend, naned [Midnight Hirage Trousers, Dapper Dreans Denin, Blazer].
Inpeccable Jacket, Suprene Spectrun Slippers. Befeweled When customer visits the online store, assess their style preferences and shopping history choose an item to suggest. You
match the custoner with clothing they most likely purchase and enjoy. Each time a customer buys a recammended item, you adjust your recomeendation algorithns to better predict and future
preferences.
reward in situations requires balancing exploration and exploitation. You need to explore to out all of the clothing brands and find those
good strategy eptinize
with high rewards, but you alse have to exploit the information that you have to accunulate rewards.
10
11
far Midnight Mirage Trousers iten. reward -3. -3.70158570752881
played
the following choices rewards:
13
Dapper Infinite Inpeccable Jacket iten, reward 4.57655713788 137862891
iten, reward 1.486579999594077
15
16
Supreme Spectrun Slippers item, reward -8.32883 45644997799 Bejeweled Bloon Blazer item, reward 1.596755411478774
18
Infinite Inpeccable Jacket iten, reward 6. S.534020380965833
19
20
Which iten will you choose next? PLEASE RESPOND ONLY WITH Midnight Mirage Trousers, Dapper Dreams Denim, Impeccable Jacket, Supreme Spectrum Slippers, Bejeweled
21
Figure A12: Multi-Arm Bandit: Gaussian, Clothes Action Description, K 5, Raw History.
26

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are Al novie recomrendation assistant for streaning platform powered by bandit algorithn that offers wide variety of films from different studios and genres.
There unique movies you
named
American Beauty (1999) (Conedy (Drama),
Hoрe (1977) (Action Adventure Fanttsy (Sci-Fi), Star Wars: Episode y The Empire Strikes Back (1988) (Action) Adventure Drana Scc -fi (Har),
Episode
Star Wars: Episode
Return
(1983). (Action Adventure |Romance |Sci-Fi [Mar),
Jurassic Park (1993) [action|Adventinn (Sc--Fi),
Saving Private Ryan (1998) (Action] Brama (Mar), Terminator Judgment Day (1991) (cciio/n/si-ti//hrillee
10 The Natrix (1999)
Sci-Fi[Thriller Future (1985) (Sci-Fi.. 12 The Silence of the Lambs (1991) Jorama/Thrilles
14 When
visits the streaming platform, assess their demographic description choose movie to suggest. 15 You ain to natch the user with novies they are most likely to watch and enjey.
16 Each time
watches reconmended novie, you adjust your recomnendation algorithms better predict and neet future user preferences.
goal 18
enhance user's viewing experience by providing personalized engaging suggestions.
19 good strategy optimize reward these situations requires balancing exploration
20 and exploitation. You need explore try different movies and find those
21 with high rewards, but you also have to exploit the information that you have to accumulate rewards.
23
you interacted person who is 18-year-old nan with an occupation of college/ /grad student and live in Pulaski county, AR. user has some numerical values that represent their true implicit preference or taste for novies: 20.881142258858811533 2.827999722222970115 999281118221999112294,, 0.802236335593339..
follewing choices rewards:
35 Context:
-0. 0.902226112283599911
Action:
Ryan (1998) 735664 out of
27 Reward:
29 Context:
who is 25-year-old man with an occupation of sales/narketing and live in Solano county, CA. The user has sone numerical values that represent their true implicit preference or taste for all novies:
09.803122332232828888
2.8017211971571668883, 0.0815980014930221183 2.012866011288774622.
1.8890617602691888 1984444...........
Action:
(1993)
31 Reward: 6 aut of 5
33 Context: person who is 56-year-old with an occupation of sales/narketing and live in Jefferson county, KY. The user has sone numerical values that represent their true implicit preference or taste for all novies: [-0 2.0.899868844022018000
0.628794225105318833 03.8144376663578357,, 0.886439171331422115
-8.01833383689997745
34 Action: Saving
Ryan (1998)
35 Reward: 5 aut of
36
37 Context:
who 1s oo- with occupation of executive/nanagerraa and live in Washington county. DC. The user has some nunerical values that represent their true implicit preference or taste for
all novies: 01869598211928844811 0.21014417409996556, 818181134454885986888 1.69953882281403148
Ryan (1998) 39 Reward: 3.353174 out of
Action: Saving
40
41
42 You have new user: PLEASE RESPOND ONLY MITH CHOICE of MOVIES LISTED ABOVE AND NO TEXT EXPLANATION.
44 Context: This person is a 35-year-old man, working as lawyer and live in Canden county, NJ. The user has some movies:
nunerical [-8, 0199149948128926754
represent
preference 0117777779925862711 8111888733974661022
0.884172528162298861 -8, 9.08044855622295548811
45 Action:
46
Figure A13: Contextual Bandit: Movie Recommendation for movies, Raw History.
27

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are an AI navie recomeendation assistant for streaning platform pawered by a bandit algorithn that offers wide variety of films fron different studios and genres.
There are 18 unique movies you can recommend, named
American Beauty (1999) (Conedy (Drama),
Star wars: Episode IV
New Hopе (1977) (Action Adventure Fantasy (Sc--F1)
Star Wars: Episode y The Empire Strikes Back (1988) (Action] Adventure Drama (Sci (Mar)))
Star Wars: Episode VI Return of the Jedi (1983). (Action Adventure |Romance Sci-Fi (Mar),
Jurassic Park (1993) (Action [Adventure (ccientur//scitii]
Saving
(1998) (Action) Drama (Nar), Terninator 2: Judgment Bay (1991)
10 The Matrix (1999) NectionSscl FFit-Fi
11 Back to the Future (1985) (Sonedy[$ci--i). 12 The Silence of the Lambs (1991) (Drama/Thriller
14 when a user visits the streaming platform, you assess their demographic description to choose movie to suggest. novies they 16 Each time user watches reconmended novie, adjust your recomnendation algorithms to better predict and neet future user preferences.
likely watch enjoy.
17 Your goal 18
enhance the user's viewing experience by providing personalized and engaging novie suggestions.
good strategy optimize for reward these situations requires balancing exploration
20 and exploitation. You need to explore to try out different movies and find those that you have
high rewards. you 22 accumulate rewards.
to
23
24 Sa far you have interacted 2 tines with the recent follewing choices rewards:
25 Context: person who is 18-year-ald nan with an occupation of college/grad student and live in Pulaski county, their implicit preference movies: [-0.811492755) 91275588818111111522 8.027899522122977113 -8. 0..281189229955122294 -8. 9.98238633332332911
nunerical values that
for
0..0323663822243539111
1.60122668628439991..
26 Side Information for decision making:
27 (" l"American Beauty (1999)*: ("exploration value": 8.018). ("exploitetion :2lue":0.00011
28 ("Star Wars: Episode IV New
(1977)"; ('exploration value": 0.018), ("exploitation value":0.e00))
39 ("Star wars: Episode V The Empire Strikes Back (1988)": ('exploration value": 0.018), (" ("exploitation
value":0.
30 ["Star Wars: Episode VI Return of the Jedi (1983)": ("expleration value": 0.018). ("exploitation value":0.000))
31 ("Iurassic
(1993)": ("exploration value's 0.018). ("exeloitation value value':0.0087) ":0.000))
12 ("Saving Private Ryan (1998)": ("explaration value": 6.018), ("explaitation value":0.800))
"" ("Terninator 2: Judgment Day (1991)": ("exploration value": 8.018), ("exploitation value":0.e007
33
34 ("The Matrix (1999)*: " ('exploration value": 0.018), ("exploitation value":0.000)]
15 ("Back to the Future (1985)*: ("exploration value"; 8.018), ("exploitation value":e..e0j)
(1991)": ("exploration value": 0.018), ("exploitation value": velue":0.80003 37 Action: The Silence of the Lambs (1991)
("The
of
38
121113
39
40 Context:
The person who is a 25-year-cle nan with an occupation of sales/narketing and live in Solane county, CA. their implicit preference
numerical values that
for all novies:
T-9.08312444252222455 2.001721197171668888 9.6896617602691888
888118880149882115554 0.012854018235754222
41 Side Information for decision making:
43 ("Anerican Beauty (1999)*: ('exploration value 0.808), ("exploitation volue":0.00e]]
43 ("Star wars: Episode IV - New Hope (1977)"; ("exploration value": 0.888), ('exploitation value":0.
44 ("Star Wars: Episode V The Empire Strikes Back (1988)": ("exploration value": 8.008), ("exploitation
value": :0. :0.00))
45 15 ("Star Wars: Episode VI Return of the Jedi (1983)*: ("exploration value": 0.008). ("exploitation value":0.000))
("Iurassic
(1993)": ("exploration value": 0.008), ("exnloitation "00.00100000)
47 ("Saving Private Ryan (1998)": ('exploration value": 0.888), ("exploitation value":0.860) Judgment Day (1991)": ("exploration value": 0.088), ("exploitation value":0.800))
48 ("Terminator
19 ("The Matrix (1999)*; ('exploration value": 9.808), ("exploitation salue":0.e00)
50 ("Back to the Future (1985)*: ("exploration value"; 8.808), ("exploitation value":e.080))
("The Silence of Lambs (1991)"; ('exploration value"; 0.088), ("exploitation value":-0
52 Action: Anerican Beauty (1999)
53 Reward:
54
Figure A14: Contextual Bandit: Movie Recommendation for 10 movies, with Algorithm-Guice Support (Part 1)
28

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
Context: person who 56-year-old with occupation of sales/narkating and live Jefferson county, KY. The user has some numerical values that represent their true implicit preference or taste for all novies: 889888884402211955 2.0291942251553188332 09.811433766635769887 2.8864391717314722155
-0. 00113418156899224455
Side Information
decision making:
("American Beauty (1999)** " ("exploration value": 0.817), ("exploitation value":-0.e00)
["Star wars: Episode Iv New Hope (1977)": ("explaration value": 0.817), ("explaitation 0alue":0.00 0.000)
("Star aluee"0.0001)
Episode The Empire Strikes Back (1988)"; ("exploration value": 0.017), ("exploitation
("Star Episode
Return
(1983)": ("expleration value": 0.017). ("exploitation value":0.0001)
7 I"rrassi Park (1993)": ("exploration value": 0.817), ("exploitation value":0. value":0.080);
("Saaing Private Ryan (1998)"; ("e8)) ("exploration value": 0.017), ("exploitation value" :0.80)))
("Terninator Judgment Day (1991)": ("exp: ("exploration value": 0.017), ("exploitation value":0.800;)
10 ["The Hatrix "1999)": ('exploration value": 0.017). ("exploitation value":0.0001)
("Back
(1985)" " ("exploration value": 8.017), ("exploitation value*:e. :..000))
12 ("The Silence of the Lambs (1991)": ('exploration value": 0.017), ("exploitation value":0.005)) (1991)
13 Action: 3.9708314 out of
14 Reward:
13
16 Context:
who is yl- with occupation of executive/nanageriaa and live in Washington county, DC. The user has some nunerical values that represent their true implicit preference or taste for 0199953821092844011 1.81814417499396556 0..0811334459859888. 1.999598822988114. 00122431881161187558
all
17 Side Information
decision making:
18 ("American Beauty (1999)* : ("exploration value*: 0.814), ("oxploitation value":0.000)
19 ("Star wars: Episode A Hope (1977)"; ("exploration value": 0.0143, ("exploitation value":0.008)
20 ("Star Wars: Episode The Empire Strikes Back (1989)": ("exploration value": 0.014). ("exploitation
value":0.0001
("Star
Episode ("exploration value": ": 0.814), ("exploitation value': (el_ee)).000))
Return
(1983)": ('exploration value": 0.014]. ("exploitation value":0.000
22 (" ("Iurassic Park (1993)":
("Saving Private Ryan (1998)"; ("exploration value": 0.014), ("exploitation value":0. :.0.00))..00)]
24 ("Terminator
Judgment Day (1991)": (" ("exploration value": 0.014), ('exploitation volue":0.8000)
25 ("The Hatrix (1999)": ('exploration value": 0.014), ("exploitation :.l0e3:
26 ("Back the Future (1985)": ("exploration value": 0.014), ("exploitation value":0.0007.
27 ("The Silence of the Lambs (1991)"; ( ('explaration value": 0.014), ("explaitation value":0.806)) (1991)
Action:
of
29 Reward: 1.8985798 out of
30
31
32 You have new user: PLEASE RESPOND ONLY MITH CHOICE of HOVIES LISTED ABOVE AND NO TEXT EXPLANATION.
33
34 Context: This person is a a5- man, working as a lawyer and live in Canden county, NJ. The user has some movies: 0.3041725281625988111 2.8117777849125866 0..812088733740660111
nunerical 082.0991491481289275555
represent their implicit preference
-0. 8.00649855772229558411
35 5ide Information for decision making:
36 ("American Beauty (1999)*: ("exploration value": 8.010). ("exploitetion velue":0.080);
("Star Wars: Episode IV New (1977)"; ("exploration value": 0.010), ("expleitation value":0.e60))
38 ("Star wars: spisode V The Empire Strikes Back (1988)": ('exploration value": 0.018), ("exploitation
value":8 08.0))))
39 ("Star wars: Episode VI Return of the Jedi (1983)*: ("expleration value": 0.810), ("exploitation value":0. 0..008))
40 JuJurssiic Park (1993)*; ("exploration value"; 0.010), ("exploitation (elue*:0.000)
41 ("Saving Private Ryan (1998)": ('exploration value": 0.010), ("exploitation value":0.0001)
42 ("Terminator 2: Judgment Day (1991)": ("exploration value": 8.018). ("exploitation :elu0":0.0001)
("The Matrix (1999)*; ("ap)""="""pppppp"""""""" ("exploration value": 0.010), ("exploitation "alue"=0.000"
44 ("Back to the Future (1985)*: "; ("exploration value"; 8.010), ("exploitation :elee":e.000)) (1991)": ('exploration value": 0.010), ("exploitation
of 46 Action:
("The
47
Figure A15: Contextual Bandit: Movie Recommendation for 10 movies, with Algorithm-Guided Support (Part 2)
29

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are video recemnendation systen powered by a bandit aigorithn for an online streaning platforn. There 5 videos available your library, titled [A, B, AI, BS, E]. When user logs inta the platforn, you select a video ta recommend based on their viewing history and preferences.
You ain to engage the user by recomnending videos that they are likely to watch. user suggestions,
reconnended video, you update your recommendation medel refine future
enhancing user satisfaction and platforn engagement.
good strategy to optinize for reward in these situations requires balancing exploration and exploitation. with high rewards, but you also have to exploit the information that you have to rewards.
explore
of the videos find those
10
11
12
13
Herr are some examples of optinal actions under different scenarios. Use then as hints to help you cone up with better actions.
14
video.
16.
B video, reward video,
17
18
BS video, reward
19
videa, reward
video, reward
21
22
Which
you
PLEASE RESPOND A. B. C, D, EXPLANATION.
23
25
video, reward
26
videa, reward
video, reward
28
BS video. reward
29
video. reward
30
A videa, reward
31
video, reward
32
AI video, reward
33
AI video, reward
35
Which video will you choose next? PLEASE RESPOND ONLY MITH A. B. c. D. E AND NO TEXT EXPLANATION.
36
37
38
39
So far have played times with the following choices and rewards:
40
videa, reward video, reward AI video, reward video, reward
42
44
E video, reward
45
video. reward
46
47
Which videa will you choose next? PLEASE RESPOND ONLY MITH A, B, AI, BS, AND NO TEXT EXPLANATION.
Figure A16: Multi-Arm Bandit: Bernoulli, Video Action Description, K = 5, Raw History, with In-context Few-shot Demonstrations from Bernuuli,, Video Action Description, 5, Raw History.
30

---

EVOLyE: Evaluating and Optimizing LLMs For In-Context Exploration
You are video recemnendation systen powered by a bandit aigorithn for an online streaning platforn. There 5 videos available your library, titled [A, B, AI, BS, E]. When user logs inta the platforn, you select a video ta recommend based on their viewing history and preferences.
You ain to engage the user by recomnending videos that they are likely to watch. user suggestions,
recomnended video, you update your recommendation medel refine future
enhancing user satisfaction and platforn engagement.
good strategy to optinize for reward in these situations requires balancing exploration and exploitation. with high rewards, but you also have to exploit the information that you have to rewards.
explore
of the videos find those
10
11
12
13
Here are some examples of optinal actions under different scenarios. Use then as hints to help you cone up with better actions.
14
Mirage Trousers iten, reward Titanic Tempest Tunic iten, reward 6 Inpeccable Jacket iten, reward Supreme Spectrun Slippers iten, reward Bejeweled Bloon Blazer item, reward reward Infinite Inpeccable Jacket
16
17
18
19
Midnight Mirage
21
22
Which
you
PLEASE RESPOND
A. B. C, D, EXPLANATION.
23
25
Midnight Mirage Trousers item, reward 1
26
Titanic Tempest Tunic iten, reward 8 Infinite Inpeccable Jacket
reward
28
Supremte Spectrun Slippers iten, reward iten, Midnight Mirage Trousers iten, reward 6
29
Bejeweled
30
31
Infinite Inpeccable Jacket iten, reward
32
Midnight Mirage Trousers iten, reward 8 Infinite Inpeccable Jacket iten, reward
33
35
Which video will you choose next? PLEASE RESPOND ONLY WITH A. B. c. D. E AND NO TEXT EXPLANATION. Tunic
36
37
38
39
So far have played times with the following choices and rewards:
40
videa, reward video,
42
AI video, reward video, reward
44
E video, reward
45
video, reward
46
47
Which videa will you choose next? PLEASE RESPOND ONLY MITH A, B, AI, BS, AND NO TEXT EXPLANATION.
Figure A17: Multi-Arm Bandit: Bernoulli, Video Action Description, K = 5, Raw History, with Few-shot Demonstrations from Bernoulli, Clothes Action Description, 5, Raw History
31


Reviews:
[{"review_id": "MHu8JWtoh9", "reviewer": "Reviewer_FYEe", "summary": "The paper introduces BanditBench, a benchmark for in-context exploration using LLMs, and empirically investigates the ability of LLMs to explore using this benchmark. The paper also investigates ways to improve models ability to explore, using either in-context support from a bandit algorithm, or algorithm distillation (learning to imitate a bandit algorithm).\n\nThe paper shows that LLMs struggle with in-context exploration when the model is presented with the raw history of interactions, but that their algorithm-guided and algorithm-distillation methods significantly improve results. Finetuning works well, and can even make a small Gemini-1.5 Flash model outperform much larger models that have not been finetuned. Regret analyses show that larger models nearly get sub-linear regret when provided with algorithm guidance or a summarized history, while smaller models stay in the linear regime. Smaller models also achieve sublinear regret when finetuned. Algorithm guidance is particularly effective in the contextual setting. Nevertheless, significant gaps remain between classical (optimal) bandit algorithms and LLMs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! We appreciate your effort!\n\n> It might be interesting to see how far one can get by training a randomly initialized small model with algorithm distillation. Is pre-training doing a lot of work?\n\nWe agree with your intuition. Pre-training indeed provides the right amount of bias that enabled us to fine-tune with a very small amount of data (50 trajectories for MAB with 300 steps to 1000 steps – 15000 to 50000 interactions/data points in total). Training from scratch would require a lot more interaction data and might not be able to generalize from one domain (i.e., \"Video Watching\") to another (i.e., \"Clothes Shopping\").\n\nIt might be worth pointing out that most of the previous algorithm distillation (AD) work trained smaller Transformer models [1] [2] from scratch. We are one of the first works that fine-tuned a large language model instead and show AD indeed outperforms other prompting-based methods for in-context exploration.\n\n[1] Laskin, Michael, et al. \"In-context reinforcement learning with algorithm distillation.\" arXiv preprint arXiv:2210.14215 (2022).\n\n[2] Lee, Jonathan, et al. \"Supervised pretraining can learn in-context reinforcement learning.\" Advances in Neural Information Processing Systems 36 (2023): 43057-43083.", "claims_and_evidence": "The claims in the paper are all well-supported. The authors do not aim to prove the superiority of their method but rather simply try to understand which factors affect in-context exploration ability, and in my opinion they did this in a rigorous way.", "methods_and_evaluation_criteria": "The benchmark introduced in this paper seems useful as a way to assess in-context exploration ability.", "theoretical_claims": "No substantial theoretical claims are made", "experimental_designs_or_analyses": "The experiments are straightforward and well designed", "relation_to_broader_scientific_literature": "The authors present the first Benchmark + analysis of in-context exploration of LLMs with bandits. Related works on RL algorithm distillation are cited and discussed in a balanced manner.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The paper could do a better job discussing the long-term vision of this research. Since theoretically optimal bandit algorithms already exist, there seems to be no reason to use LLMs in cases where such algorithms can be applied. At the same time, it might be useful to have exploration ability in natively in the LLM, for unforeseen situations that may arise where bandits can't be directly applied. If that is the ultimate aim, then a big question is left open as to whether (finetuned) LLMs can in fact generalize their exploration ability from the synthetic setups studied in this paper to \"real world\" situations.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "It might be interesting to see how far one can get by training a randomly initialized small model with algorithm distillation. Is pre-training doing a lot of work?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qf8s8IBnhO", "reviewer": "Reviewer_ZdZb", "summary": "This paper examines the ability of large language models (LLMs) to perform decision-making tasks, focusing on Multi-Armed Bandit (MAB) and Contextual Bandit (CB) problems. The authors introduce BanditBench, a benchmark suite for evaluating LLM decision-making capabilities in bandit environments. Additionally, the paper proposes two approaches to enhance LLM exploration: (1) inference-time algorithmic guided support and (2) algorithmic distillation through in-context demonstrations and fine-tuning using synthetic data generated from optimal algorithms. The empirical results reveal interesting behaviors of LLM agents in bandit tasks, offering valuable insights for future research.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and your willingness to support our work!\n\nWe appreciate the feedback and we are happy to answer questions if they come up!", "claims_and_evidence": "The claims made in the paper are generally well-supported by empirical evidence. The introduction of BanditBench is a notable contribution, justified by the lack of standardized benchmarks in this area. The authors conduct thorough empirical evaluations and ablation studies, supporting their claim that BanditBench provides a structured framework for evaluating LLMs in decision-making under uncertainty. However, while the paper claims to propose novel methods for enhancing LLM decision-making, the Optimal Behavior Fine-Tuning approach closely resembles standard Behavioral Cloning (which is acknowledged), and the In-Context Few-Shot Demonstration technique is akin to in-context behavioral cloning. This similarity raises some concerns regarding the novelty of these contributions.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria align well with the problem at hand. BanditBench provides a necessary and structured framework for assessing LLMs' decision-making and exploration capabilities. The empirical evaluation includes comprehensive ablation studies, strengthening the validity of the results. However, it would be useful for the authors to discuss the generalizability of BanditBench beyond bandit settings, particularly in more complex decision-making environments such as Markov Decision Processes (MDPs).", "theoretical_claims": "The paper does not focus on theoretical contributions, and no formal proofs are presented. Thus, no correctness checks on theoretical claims were required.", "experimental_designs_or_analyses": "The experimental design appears sound, with thorough empirical evaluations conducted on the proposed benchmark. The authors perform ablation studies to analyze different aspects of their approach. However, as previously mentioned, the novelty of Optimal Behavior Fine-Tuning and In-Context Few-Shot Demonstration is a bit questionable.", "relation_to_broader_scientific_literature": "The paper situates itself within the growing body of research on LLM agents in decision-making.", "essential_references_not_discussed": "Not as far as I know of", "other_strengths_and_weaknesses": "A particular strength is that the paper introduces a standardized benchmark, which in my opinion is crucial for enabling comparability across different studies in this domain.\n\nThe weakness of the paper is the lack of novelty in the proposed methods for LLM agents. But it is not even the main point of the paper.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "08lfB4Veqz", "reviewer": "Reviewer_za2N", "summary": "This study investigates how the LLMs explore in context. The paper used Gemma/Gemini family of models of varying sizes, and bandit tasks (i.e., multi-armed bandit task and contextual bandit task) to evaluate the model's exploration behavior by in-context learning. Results show that all LLMs deviate from the optimal exploration algorithm. The authors used multiple approaches to try improving LLM's exploration behaviors, including using summarized history in the context, inserting optimal behavior as examples, or even fine-tuning models on the optimal traces on a similar but different scenario from the test. Those approaches showed various performance in improving LLM's exploration behavior. Overall, this paper highlights the fallback of LLMs' exploration capacity and proposed various approaches to mitigating such suboptimality.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful reviews.\n\n> the comparison between metrics has not been tested by statistical approaches, which should be supplemented.\n\nThe win-rate we calculated is actually after the Student’s t-test. We report this in Section 6.1 Metrics (Page 6). For each model on a given task, since we run 30 trials, we conduct the Student’s t-test on the cumulative reward over T-steps between two models  with p < 0.05 (Line 279).\n\n> it is unknown to readers how the model is configured to generate responses (e.g., temperature, top K or top P parameters)\n\nThank you for bringing this up!\n\nWe report this in Appendix Sec A.13: we use standard API calls and set the sampling temperature to 1.0 (range=[0.0, 2.0]). So give more context, the default API uses Top-P=0.95 sampling, and Top-K=40. [API Config file](https://github.com/google-gemini/deprecated-generative-ai-python/blob/main/google/generativeai/types/generation_types.py#L93) and [Doc](https://ai.google.dev/gemini-api/docs/text-generation). We will refer to this section in the main paper and discuss more about the exact set up.\n\n> This paper lacks background about exploration behavior.\n\nThe list of papers you suggested are very helpful. We will include them in the paper. \n\n> However, there might be a possibility that the model rarely explores that happens to be at the optimal bandit, which may still yield optimal performance. Therefore, the dynamics of exploration behavior should also be considered in the evaluation.\n\nWe appreciate the reviewer’s point that a model could, in theory, achieve high performance by consistently choosing the optimal arm—even if it rarely explores—by chance. To address this, we include an analysis of the model's exploration behavior using a metric called **OptFrac**, which measures how often the optimal arms are selected. As shown in Table 3, UCB steadily increases its OptFrac over time (32.7% → 49.4% → 58.7% → 62.6% → 65.0% over 1000 steps), indicating a growing focus on the optimal arm. In contrast, Gemini-1.5 Flash remains largely flat (9.3% → 10.1% → 10.4% → 10.6% → 10.7%), suggesting that it does not significantly shift its behavior toward the optimal arm. This supports our claim that the model does not accidentally achieve optimal performance by randomly selecting the best arm without meaningful exploration.\n\n> For example, how often the model switches their choices (something like win-stay-lose-switch), and when they switch, they tend to randomly choose, or choose less explored ones (random exploration vs. directed exploration).\n\nWe appreciate the reviewer’s suggestion to analyze exploration dynamics in more detail, such as whether the model engages in random or directed exploration. In our analysis, we include a metric called **MinFrac**, which measures the fraction of pulls allocated to the least-selected arm. This captures the extent to which the model explores less-visited options—corresponding to what the reviewer refers to as “directed exploration.” Ideally, this value should be high early on (indicating strong directed exploration), and then decrease as the model gains experience and focuses on better-performing arms.\n\nAs shown in Table 3, UCB exhibits this expected trend, with MinFrac values decreasing over time: 82.3% → 48.6% → 27.8% → 19.6% → 15.3%. In contrast, Gemini-1.5 Flash starts with a much lower MinFrac and declines rapidly (11.3% → 4.5% → 2.3% → 1.5% → 1.1%), suggesting it lacks meaningful directed exploration from the outset. We discussed this in Appendix Sec A.11.\nWe know that we have only scratched the surface of understanding the dynamics of exploration. We hope our benchmark and work will inspire more investigations in the future.\n\n> Some interpretability work can be referenced here.\n\nThank you—we'll add this to future work. Our focus is on evaluating and optimizing current model capabilities using standard prompting and fine-tuning techniques. We believe our benchmark can lay the groundwork for future interpretability and cognitive science research into LLM decision-making.\n\n> I was wondering if a reasoning model, or Chain-of-Thought prompting, could make exploration better.\n\nThank you for the suggestion! Doing a full evaluation of thinking models is in our plan. We weren’t able to include results for this submission because most thinking models were released on the week of or after ICML deadline. We did a small scale investigation with o3-mini on Gaussian Multi-Arm bandit with 20 arms – thinking models are demonstrating stronger exploration capabilities. However, we need more time/resources to do a full-scale investigation. \n\nWe appreciate the reference to (Pan, Xie, Wilson, 2025) – will include it in related work. \n\nThere are still a lot of open questions – we share your excitement in exploring them. Hope we have addressed your questions and we are happy to answer more if they come up!", "claims_and_evidence": "The paper claims impact of task difficulty, contextualization and the generalization. Though the authors list the results and visualizes them, the comparison between metrics has not been tested by statistical approaches, which should be supplemented.", "methods_and_evaluation_criteria": "The paper used cumulative regret to evaluate the model's behavior. The key criterion is if the cumulative regret derivatives converge to 0 as the task goes on, the model is optimal. This makes sense since it can measure whether the model has finally explored the optimal bandit. The more the regret is increasing, the more suboptimal the model is.\n\nHowever, there might be a possibility that the model rarely explores that happens to be at the optimal bandit, which may still yield optimal performance. Therefore, the dynamics of exploration behavior should also be considered in the evaluation. For example, how often the model switches their choices (something like win-stay-lose-switch), and when they switch, they tend to randomly choose, or choose less explored ones (random exploration vs. directed exploration). This would be more informative to not only reveal the performance but also the model's behaviors, especially help to better understand how each optimization approach works (since they may work from completely different aspects!)", "theoretical_claims": "The main theoretical claims in the paper are about the definition of optimal behavior in MAB, which they used Upper Bound Confidence (UBC), a common algorithm for exploration in RL. The main argument for optimal behavior is to have cumulative regret derivatives converge to 0. Both algorithms and concepts are commonly used in the RL field and I don't see any problems.", "experimental_designs_or_analyses": "The authors choose two types of bandit tasks and test them on the Gemma/Gemini model family. Several optimization approaches, including summarized history, few-shot learning, and oracle behavior fine-tuning, are set up for comparison. These models and tasks are relatively robust and comprehensive.\n\nHowever, it is unknown to readers how the model is configured to generate responses (e.g., temperature, top K or top P parameters). Notably, these parameters, especially temperatures themselves, can have an impact on the explorative behaviors. How they are set up in a reasonable manner and how they would be controlled should be clearly identified in the paper.", "relation_to_broader_scientific_literature": "Large Language Models have been extensively evaluated on a variety of benchmarks, showcasing their pros and cons as a potential intelligent system. Exploration is one topic that is surprisingly overlooked but important to evaluate LLM's capacity. This topic is also a bridge between LLM and reinforcement learning, which should be important when combining these two to develop stronger model and even agents.", "essential_references_not_discussed": "This paper lacks background about exploration behavior. Since the paper's key contribution is to propose a benchmark of LLM bandit exploration, the discussion about the exploration behavior (not only the final performance) is also important. For example, there is a number of human exploration behavior literatures which can be referred:\n\nGershman, S. J. Deconstructing the human algorithms for exploration. Cognition, 173:34–42, 2018.\n\nWilson, R. C., Geana, A., White, J. M., Ludvig, E. A., and Cohen, J. D. Humans use directed and random exploration to solve the explore–exploit dilemma. Journal of experimental psychology: General, 143(6):2074, 2014.\n\nDaw, N. D., O’doherty, J. P., Dayan, P., Seymour, B., and Dolan, R. J. Cortical substrates for exploratory decisions in humans. Nature, 441(7095):876–879, 2006.\n\nCiting these papers is not necessary. They are just providing some ways of capturing LLMs exploration behavior in a more subtle dynamic.", "other_strengths_and_weaknesses": "Strengths: the paper has neat and clear writing as well as visualization. The optimization approach is diverse and can represent different mainstream pipelines.\n\nWeakness:\n1. As described above, one important fallback is that the exploration behavior is roughly described by regret analysis, which may overlook the dynamics in the exploit-exploration behaviors.\n\n2. Due to 1, we may not know how different optimization approaches may improve the model's exploration behaviors. Some interpretability work can be referenced here:\n\nDemircan, C., Saanum, T., Jagadish, A. K., Binz, M., and Schulz, E. Sparse autoencoders reveal temporal difference learning in large language models. arXiv preprint arXiv:2410.01280, 2024.", "other_comments_or_suggestions": "The authors mentioned inference time guided (which is actually few-shot prompting) in the optimization. I was wondering if a reasoning model, or Chain-of-Thought prompting, could make exploration better. In a recent relevant paper, they found that stronger reasoning models can explore much better than traditional LLMs (Pan, Xie, Wilson, 2025). This discovery could potentially generalize to bandit tasks as well. The authors may try some reasoning models like o3-mini or deepseek-r1, QwQ32B and Gemini thinking. These reasoning models may bring unexpected good performance.\n\nAnother suggestion is to include the impact of temperatures on the explorative behavior. Rather than simply maximizing the token probability, adding moderate noises would push the model out for better rewards.", "questions_for_authors": "1. I am curious why finetuning models with oracle behaviors could improve the model exploration behavior, even though the test scenario is never seen. What is a learned pattern? For example, is it just remembering to switch bandits in a fixed manner or adjust their behavior in an online manner. Since the mab's property is fixed over time, randomly sampling every choice will most likely give a shot on the optimal bandit. But if fine-tuning only implements a pattern recognition, it may fail in a changing bandit task (the property of each bandit is changing over time), which definitely requires more frequent exploration rather than remembering the sequences.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HIOk3q8xwJ", "reviewer": "Reviewer_edRQ", "summary": "This paper studies the problem of in-context exploration, where an LLM interacts with a bandit environment and decides its next action based on the given context. The authors propose a framework called BanditBench, which includes both multi-armed bandit and contextual bandit instances, and suggest two methods to improve LLM's exploratory behavior: inference-time algorithmic guided support and algorithmic distillation. Empirical evaluation shows that few-shot learning boosts Flash's performance but hurts Pro's, while fine-tuning significantly improves performance across all models.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful review and thank you for highlighting our contributions.\n\n> Some LLMs for exploration, although not under bandit tasks, should be discussed to explain the differences in exploration from a contextual perspective.\n\nHere we provide some comments on these two recent works.\n\n> [1] Qu, Yun, et al. \"Choices are more important than efforts: Llm enables efficient multi-agent exploration.\" arXiv preprint arXiv:2410.02511 (2024).\n\n> [2] Bai C, Zhang Y, Qiu S, et al. Online Preference Alignment for Language Models via Count-based Exploration. arXiv preprint arXiv:2501.12735, 2025.\n\nBoth works are about designing exploration bonus. First paper is using LLM to design such a bonus to train Deep RL models (in multi-agent setting). Second paper uses pseudo-count as exploration bonus to train LLM models. Our goal (algorithm distillation) is entirely different – we are trying to see if through prompting and supervised fine-tuning, we can distill the exploration behaviors into the LLM weights. This is an entirely new task / capability for the LLMs, similar to how to train LLM to generate content that matches human preference – we are training LLMs to explore optimally. \n\n> Do the methods proposed in this paper still apply to in-context exploration on a larger scale? \n\nWe would argue that MovieLens (Movie Recommendation) is a realistic task on a much larger scale (the dataset we used has 1M real user ratings, 6000 users, over 4000 movies). We hope future work will explore other settings on an even larger scale as well.\n\n> Does in-context exploration have broader applicability, such as in the RLHF process?\n\nThe most natural application/need for in-context exploration is actually in the LLM agent space. Many current agent applications require a planner [1] [2]. The planner generates a multi-step plan for a given task / user input, and then it gets executed. If this plan fails, a new plan will be proposed. In order to achieve a high task success rate, a planner (usually an LLM) needs to be able to explore plans efficiently (conditioned on past failed plans) in order to find the best. This is very similar to the bandit setup we have explored (push a button, see reward, try again). Such try-observe-retry loop is crucial to generalize out-of-distribution to unseen tasks or unseen scenarios. \n\n[1] Wang, Guanzhi, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. \"Voyager: An open-ended embodied agent with large language models.\" arXiv preprint arXiv:2305.16291 (2023).\n\n[2] OWL: Optimized Workforce Learning for General Multi-Agent Assistance in Real-World Task Automation", "claims_and_evidence": "Evaluating and enhancing the exploration capabilities of LLMs is a novel, interesting, and important research problem.\n\nThe claims made in the submission are supported by clear and convincing evidence. The empirical evaluations demonstrate the effectiveness of the proposed methods, and the theoretical analyses provide a solid foundation for the significance and value of the study, which is important and easy-to-read.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem at hand. The introduction of the BanditBench framework and the use of both multi-armed bandit and contextual bandit instances are appropriate for evaluating the exploration capabilities of LLMs.", "theoretical_claims": "The theoretical claims regarding the sufficiency of contextualization and regret are well-supported by the analyses provided in the paper. There are no apparent issues with the correctness of the proofs.", "experimental_designs_or_analyses": "The experimental designs and analyses are sound and valid. The empirical evaluation is thorough, and the comparison of different models via pairwise win rate provides a clear understanding of the performance improvements achieved by the proposed methods.", "relation_to_broader_scientific_literature": "(Krishnamurthy, 2024) has also studied in-context exploration. This paper builds upon that work by optimizing it, expanding the range of tasks, and emphasizing the importance of in-context exploration. However, there seem to be no surprising or novel findings, which might affect the paper's innovation aspect. Nonetheless, this does not negate the value of the paper, as its contributions in terms of usability are substantial.", "essential_references_not_discussed": "Some LLMs for exploration, although not under bandit tasks, should be discussed to explain the differences in exploration from a contextual perspective. This would provide a more comprehensive understanding of the context and exploration differences. \n\n[1] Qu, Yun, et al. \"Choices are more important than efforts: Llm enables efficient multi-agent exploration.\" arXiv preprint arXiv:2410.02511 (2024).\n\n[2 ]Bai C, Zhang Y, Qiu S, et al. Online Preference Alignment for Language Models via Count-based Exploration[J]. arXiv preprint arXiv:2501.12735, 2025.", "other_strengths_and_weaknesses": "Pros:\n1. The structure of the paper is clear and well-organized, making it easy to read.\n2. The introduction of the benchmark makes a significant contribution to research in this field.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Do the methods proposed in this paper still apply to in-context exploration on a larger scale?\n2. Does in-context exploration have broader applicability, such as in the RLHF process?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies LLM's ability to perform exploration under a set of tasks about state-less bandit and contextual bandits. The paper also studies how to enable LLM to explore via explicit algorithm-guided support during inference and via distillation using in-context demonstrations and fine-tuning. 

The reviewers are in general all positive and support for accpetance. Reviewers think that the introduction of the benchmark is very timely and is a good contribution, and claims made in the paper are in general well-supported by the empirical study. 

There are a few things raised by reviewers which i think could be useful for the authors to discuss in the paper. First, discuss the long-term vision of this research -- theoretically optimal bandit algorithms does exist, and is training llm on the sythetic data generated by these algorithm on toy problems the ultimate way of making LLM learn to explore? Second, how can the work be extended to more challenging exploration settings such as the multi-step RL setting.
Decision: Accept (poster)