Evolve: Evaluating and Optimizing LLMs For Exploration

Thank you very much for your thoughtful review. We are adding your two suggested citations to the paper! Thanks for bringing them to our attention. Here we address some of your concerns:

Lack of novelty in some of the contributions We thank the reviewer for acknowledging the contribution from BanditBench. We would like to address your concerns about the novelty on algorithmic guided inference-time support and algorithmic distillation approach in detail. Conceptually, there is a fundamental difference between “Optimal Behavior Fine-tuning” and Behavior Cloning, where we refer to the discussion in the next bullet point:

• On Behavioral Cloning (BC) and Optimal Behavior Fine-Tuning (OFT): we totally agree that Optimal Behavior Fine-tuning shares some similarities with behavior cloning in training objectives. However, BC trains on a single policy's sampled trajectories, while OFT trains on trajectories of a policy that is self-improving. To put it more bluntly, BC learns to mimic behavior from a single, fixed policy. OFT trains on trajectories sampled from multiple policies, each policy updated by a learning algorithm (such as UCB update or policy gradient).
• Similarly, while “in-context few-shot demonstration” is similar to in-context behavioral cloning, there are many design choices and open questions that significantly impact its effectiveness. For instance, what type of few-shot examples should be included to ensure better generalization to new environments? Should they come from simple or challenging domains? What representations should be used? These decisions play a crucial role in shaping how the model understands, reasons, and generalizes in new test domains.

In Section 5.3.2, we provide a comprehensive study and evaluation of these factors. We believe this analysis is highly valuable for advancing our understanding of how to effectively perform in-context exploration in LLMs.

In particular, the technique that the paper calls "Optimal Behavior Fine-Tuning" seems to be exactly what is known in the literature as Behavioral Cloning.

Is "Optimal Behavior Fine-Tuning" what is known in the literature as Behavioral Cloning? If so, please change the name in your paper. It can be confusing to a reader.

We acknowledge that OFT and Behavioral Cloning (BC) share many similarities. However, there is a fundamental distinction between the two. 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 a policy by mimicking a static policy, with no iterative improvement between trajectories.

Although both approaches rely on maximum-likelihood learning, their goals are different: OFT seeks to encode dynamic, iterative refinement processes, while BC focuses on replicating static behavior.

Can the applicability of BanditBench be extended to other decision-making scenarios beyond bandit settings? Can you add some discussion about it in the paper?

I feel like recently LLM agents in more complex domains such as MDPs are very relevant and may be very useful in many real-world applications.

Thank you for the thoughtful suggestion! Extending BanditBench to decision-making scenarios beyond bandit settings, such as MDPs, is a natural and exciting direction. However, this transition introduces additional complexities that warrant careful consideration:

• Choice of Optimal Algorithm: In MDPs, only tabular setups have provably efficient exploration algorithms. It would be interesting to investigate whether incorporating in-context few-shot demonstrations from suboptimal algorithms could still provide performance gains over existing LLMs. This exploration could give us new insights into how LLMs can leverage sub-optimal strategies in more complex domains.
• Interpretability of Exploration Behavior: In bandit settings, self-improvement behaviors are relatively straightforward to define and analyze, with theoretical guarantees like worst-case upper bounds. These results allow us to derive functional forms, as discussed in Section 6, to interpret and measure an LLM's exploration behavior. In MDPs, this interpretability becomes more challenging.

Our method can naturally be extended to MDPs by fine-tuning on any behaviors/data derived from the best algorithms in the literature. We are interested in exploring how this scales to more complex environments and whether it can provide meaningful improvements for in-context exploration. Additionally, we fully agree that rigorously understanding LLMs' exploration behavior in MDPs is both a critical and exciting direction for future research. We will include this discussion in the revised version of the paper. Thank you for highlighting this!

We hope our responses have clarified your concerns and addressed your questions. We are happy to answer more questions if they arise. Thank you very much!

As the author/reviewer discussion period is getting close to an end (in 4 days -- Nov 26), we are wondering if our rebuttal addresses some of your concerns about the paper.

How practical is it to use LLMs for such explicit exploration? If you have explicit actions, it seems easier to use RAG with UCB/Thompson Sampling baked into the external retrieval system, resulting in optimal exploration.

Thank you for the insightful question! For explicit actions, LLMs excel at capturing nuanced relationships among semantically meaningful actions, leveraging their extensive pre-training on diverse data. This effectively injects prior knowledge into exploration algorithms, which is particularly helpful in cold-start scenarios where initial information is limited.

We fully agree that combining RAG with UCB/Thompson Sampling offers a robust approach by integrating an exploration component directly into the system. However, our motivation in this work is to investigate whether "exploration" capabilities can be embedded directly within the LLM itself. In this study, we focus on explicit actions as a starting point. Our hope is that the learned "exploration" behavior can generalize beyond explicit actions to implicit ones—cases where predefined actions are not available or practical, such as the intermediate steps required for solving math problems or complex coding tasks. We leave this as exciting future work.

Thank you for the review again. Did we answer all of your questions? Happy to expand on these more!

Thank you for your thoughtful review. We address your concerns point by point below:

In MAB, I would like to see a setting with variable sigma for each action, as the exploration problem for the LLMs might get easier when all of the actions share the same variance.

Thank you for your insightful question! In our current Gaussian domain environments from BanditBench, we vary task difficulty by adjusting the mean gaps between actions, following the approach outlined in [1]. This allows us to evaluate how different methods perform across both simple and complex domains, providing an initial understanding of their capabilities.

We completely agree that introducing variable variance across actions would add another layer of fine-grained difficulty, offering deeper insights into exploration behavior. However, due to the limited time during the rebuttal period, we were unable to complete evaluations for these tasks across all models (16 tasks, on top of 32 models = 512 evaluation runs). We plan to incorporate this environment into BanditBench and include it in the final version of the paper.

[1]. Richard S Sutton. Reinforcement learning: An introduction. 2018.

Why is OFT in Figure 2 present only for Gemini 1.5 Flash?

Due to resource constraints, we chose to test the OFT idea with a single model. Flash was selected as it strikes a balance between model capability and computational efficiency, making it a practical choice for evaluating this approach.

Any idea how the LLMs perform in larger action spaces? I can imagine that many real-world applications go well beyond K=30, and any discussion on these scaling laws would be very helpful.

That’s a great question! Here is a performance breakdown on MAB (K=5 to K=20).

We performed an additional analysis by computing the model average win-rate on domains with K=5 and K=20 in the MAB experiment.

RH shows Raw History.

AG shows model with algorithmic guide.

Larger action spaces (e.g., K=20) present greater challenges for all models, and we observe a notable performance drop for LLMs that rely on raw history. However, the techniques proposed in our paper, such as inference-time Algorithmic Guidance (AG) and oracle behavior fine-tuning (OFT), show increasing importance in these settings.

This suggests that while LLMs may struggle with scaling in raw-history setups, the enhancements explored in this work are particularly valuable for handling larger and more complex action spaces, making them essential for real-world applications with larger K.

Based on Figure 5, Gemma models perform terribly in exploration, even with all the techniques introduced in the paper. Do you have any explanation/hypotheses on why this is the case? Is it because of the model sizes?

Optimal decision-making is inherently a challenging task, and smaller models, such as the Gemma models, often struggle to generalize beyond the tasks they were specifically trained on. This limitation has been observed in prior works, such as GSM-1K [2] and Symbolic-Math [3], where smaller models exhibit significantly degraded performance when faced with even slight variations in task structure. The poor performance of Gemma might come from the following factors: (1). Limited capacity for complex reasoning: as smaller models lack the capacity to perform complicated reasoning required for optimal decision making, i.e., calculating the exploitation values, exploration bonus, and figuring out the best way to combine them; (2). Difficulty with generalization: it seems smaller models are poor at adapting to new tasks, leading to poor exploration behavior; (3). Long-context window: smaller models often struggle to effectively extract and utilize information from long contexts, and this basically prohibits the effective exploration.

[2] Zhang, Hugh, Jeff Da, Dean Lee, Vaughn Robinson, Catherine Wu, Will Song, Tiffany Zhao et al. "A careful examination of large language model performance on grade school arithmetic." arXiv preprint arXiv:2405.00332 (2024).

[3] Mirzadeh, I., Alizadeh, K., Shahrokhi, H., Tuzel, O., Bengio, S., & Farajtabar, M. (2024). Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models. arXiv preprint arXiv:2410.05229.

Thank you for your thoughtful review.

Krishnamurthy et al. 2024 study a very similar multi-armed bandit setting. While the multi-armed bandit results in this submission are more comprehensive, their findings are similar to Krishnamurthy et al.

We acknowledge that Krishnamurthy et al. 2024 explored LLM’s in-context learning abilities in the MAB setting. However, our work makes several key advancements:

1. A more comprehensive benchmark. For MAB, we add a Gaussian bandit setting, which requires LLM to process floating point numbers. Therefore, it assesses LLM for a different capability than the Bernoulli bandit in Krishnamurthy et al. 2024. We also include a broader range of tasks: evaluation with K=20 arms and two new scenario descriptions (video recommendation and clothes shopping).

2. Contextual bandit: We extend the MAB setting to include contextual bandits, further evaluating the generalization capability of LLMs for exploration in more complex environments.

3. Algorithmic distillation techniques: We also study efficient techniques to distill optimal exploration behavior, via few-shot in-context demonstrations and oracle behavior fine-tuning, which opened up the question about dataset selection (See Fig 4 (a)) – we found that shorter, simpler examples are better as few-shot examples, but longer and harder examples are better for fine-tuning.

4. Extensive Ablation studies: We conducted an extensive ablation study to understand how various factors, such as task difficulty and textual representation, influence the efficiency of LLM exploration. We also offer a regret analysis in Figure 5, characterizing the exploration capability with two fitted parameters alpha and beta.

Overall, while Krishnamurthy et al. (2024) focused on smaller-scale MAB tasks, we offer a more thorough analysis across MAB and CB tasks at various scales. Furthermore, our contributions extend well beyond merely enhancing the benchmark. More importantly, we delve deeper into developing effective methods for distilling optimal exploration behavior into LLMs, demonstrating the effectiveness of both in-context few-shot demonstration and optimal behavior finetuning. Additionally, our extensive ablation studies shed light on critical practical considerations, including the impact of task difficulty when selecting distillation examples and the importance of representation alignment. Furthermore, we offer a more rigorous analysis of the functional interpretation of LLM exploration behavior, providing a principled approach to measuring exploration efficiency.

If we give LLMs things which make it easier for them to compute an upper-confidence bound, are we testing the LLMs’ ability to explore, or their ability to implement UCB?

Given that UCB is often suboptimal in structured bandit tasks beyond the two studied in this work, do you believe your proposed mitigations will extend to more complicated tasks?

We would also like to clarify that the objective of our work is to assess and enhance LLMs’ inherent exploration capabilities in decision-making tasks. Our goal is not to replace UCB with LLM in these simple settings. Instead, we aim to investigate whether LLMs can reason about readily available information and perform efficient exploration accordingly. This will establish a foundation for efficient exploration in complex tasks with explicit/implicit action spaces. Furthermore, we are interested in whether algorithmic distillation can enhance LLMs’ exploration capabilities, and injecting UCB knowledge is one approach we employed. While our current work focuses on simplified settings, it lays the groundwork for future research into more complex scenarios.

We hope our responses have clarified your concerns and addressed your questions. We are happy to answer more questions if they arise. Thank you very much!

As the author/reviewer discussion period getting close to an end (in 4 days -- Nov 26), we are wondering if 1) Our rebuttal addresses some of your concerns about the paper; 2) there is anything else we can do in the next 4 days to change your opinion/position on the current rating?

Thank you so much for responding and engaging with us - we really appreciate it! We fully agree that evaluating and improving exploration capabilities with real-world decision-making tasks in mind is critical. We break down into the following points

Bandit Tasks We Provide Already Captures Many Real-World Decision Making Scenarios

As you pointed out, real-world decision making is complex, often involving unknown true value of each option (under different contexts). Bandits environments are exactly mathematical frameworks to study real-world decision making with uncertainty. Multi-arm bandits to study decision making with context-free and independent options, e.g., Duolingo app notification, UN job assistance program, which we included in the multi-armed bandits environments. Contextual bandits to study “structured” decision making, e.g., news article recommendation, movie recommendation, which we included in the contextual bandit environment.

Bandit Algorithms Produce Suboptimal Trajectories When Real-World Reward Model is Non-Linear

We studied UCB-inspired algorithms to supplement LLMs for decision-making in multi-arm bandits and LinUCB-inspired algorithms for contextual bandits. There are also more recent works on NeuralLinear [1] which combine the representation power of deep neural networks and linear bandits for even more complex tasks where the reward has a non-linear dependency on the context, but the uncertainty estimate is mostly encapsulated in linear bandits again. These algorithms have been successfully verified in real-world decision-making, such as solving industrial-scale video recommendations [2]. Our framework already handles such real-world cases, and essentially, our CB experiments aim to simulate tasks like move recommendations.

[1] Riquelme, Carlos, George Tucker, and Jasper Snoek. "Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling." arXiv preprint arXiv:1802.09127 (2018).

[2] Su, Yi, Xiangyu Wang, Elaine Ya Le, Liang Liu, Yuening Li, Haokai Lu, Benjamin Lipshitz et al. "Long-Term Value of Exploration: Measurements, Findings and Algorithms." In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp. 636-644. 2024.

Could you provide further analysis to help guide the selection of the most appropriate method in practical applications? Besides, could you clarify the numeric similarities observed in Figure 4?

We addressed the numerical similarities above - the identical values reflect the win-rate of the same model referenced in different contexts.

As for data selection, for in-context few-shot demonstration, easier, shorter, and simpler examples with clear-cut decisions tend to be the most effective as few-shot examples. We hypothesize that these straightforward cases are easier for the model to understand, reason through, and replicate in-context. Conversely, for OFT, selecting more challenging examples can help mitigate overfitting to simpler patterns and yield greater improvements by encouraging the model to generalize better to complex scenarios.

How well do the proposed methods generalize to domains with much larger action spaces, such as real-world recommendation systems that involve thousands of items or more complex decision-making problems where exploration becomes more challenging due to the increased task size and complexity?

Thank you for your thoughtful question! The challenge of exploration indeed scales with the size of the action space, and as the number of actions in a system grows significantly, the efficiency of any algorithm, including our proposed methods and classical ones like Linear UCB, is expected to decrease. However, hierarchical contextual bandit approaches, as explored in works such as [1], offer promising strategies to address this issue.

For example, hierarchical methods can leverage item embeddings or other clustering techniques (potentially could utilize other large language models) to group items and construct a tree structure. Our algorithm can then be applied effectively at different levels of this hierarchy, improving scalability while maintaining performance. There are many open research questions to explore, such as how to effectively construct the hierarchical tree, determining the optimal level at which the exploration algorithm can be most effectively applied, and even the potential of developing an LLM-based agent that integrates all these aspects. We consider these to be exciting directions for future work.

Additionally, we conducted experiments to test our algorithm's generalization by training it on data collected from smaller action spaces and evaluating it on larger action spaces (i.e., easy to hard domain generalization). This analysis provides valuable insights into how well our approach scales and adapts to more extensive domains, such as real-world recommendation systems or other complex decision-making problems.

Here, we show the performance of a fine-tuned Flash model on 5 arms and then evaluate on 20 arms, compared with the baseline:

We see that by using few-shot examples from K=5 (a simpler domain) or doing oracle behavior fine-tuning, both can generalize to a harder domain where K=20.

We hope we have addressed your concerns and questions thoroughly, and we are happy to answer more questions if they arise. Thank you very much!

[1] Show Me the Whole World: Towards Entire Item Space Exploration for Interactive Personalized Recommendations

Thank you for your thoughtful review. We address your concerns point by point below:

AG in MAB scenarios does not yield consistent improvements and that its performance remains relatively low compared to traditional bandit algorithms (UCB, LinUCB). Additionally, employing AG introduces extra computational overhead. A more detailed discussion of the effects of AG would be beneficial for understanding its role more clearly.

Thank you for your insightful comment! You’re absolutely right that for smaller models like Gemma-2B and 9B, the impact of AG is minimal and can even be negative in some cases. However, for larger models, we observe significant gains even in simpler setups like MAB, where Flash improves from 26.9% → 31.3% and Pro jumps from 44.1 → 57.8 - a substantial improvement of 13.7%. The improvements are even more pronounced in complex scenarios like contextual bandits, where AG provides notable benefits during inference, as highlighted in Table 1. The point you raised is very valid – with the additional computational cost, is AG worth it? Our findings suggest that in complex settings, such as contextual bandits, the performance boost offered by AG justifies the extra computational overhead.

Specifically, in Figure 4, the results across various tasks and methods exhibit oddly similar numerical values (e.g., 0.487, 0.636, 0.267). A deeper investigation into the reasons behind these results could enhance the applicability of the proposed approaches in real-world scenarios.

Thank you for your observation! To clarify, the identical win-rates of 0.487 in Fig 4(a) (Few-shot + Bernoulli Video k=5, Δ Easy) and Fig 4(b) (Few-shot + Summarized History) are not coincidental - they both refer to the same model. This model uses few-shot examples from Bernoulli Video k=5, Δ Easy and uses Summarized History as problem representation. Similarly, the identical value of 0.636 reflects the same scenario. Regarding the win-rate of 0.267 in Figure 4(c), we identified an error in our calculations. The correct win-rate for the Raw History OFT model should be 0.286. We have addressed this issue and updated the figures accordingly in the revised version of the paper. Thank you for bringing this to our attention!

Given that the results in Table 1 suggest that the use of Algorithmic Guidance (AG) does not lead to consistent improvements in MAB scenarios, could you provide further insights into the specific conditions under which SH and AG are most effective (especially compared with UCB or LinUCB)?

Thank you for your question. We observe consistent improvements when transitioning from raw history to Algorithmic Guidance (AG) in two key cases: (1) larger models like Flash and Pro, and (2) more complex scenarios, such as contextual bandits. As you noted, most real-world decision-making systems closely resemble contextual bandit frameworks. These systems often involve extremely large action spaces and typically rely on larger models to achieve optimal performance. To highlight the impact on (1) larger models, we conducted an additional analysis by calculating the average win-rate of the models across domains with action spaces of K=5 and K=20 in the MAB experiment. The breakdown of improvements with raw history (RH) versus Algorithmic Guidance (AG) across different numbers of actions is shown below:

RH shows Raw History.

AG shows model with algorithmic guide.

We see that AG provided consistent 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.

To illustrate (2). Complex scenarios, we observe a similar phenomenon:

Note that win-rate is computed as a comparison between models. We are showing by adding AG, in harder tasks, we are seeing a larger relative ranking improvement of models.

As the author/reviewer discussion period getting close to an end (in 4 days -- Nov 26), we are wondering if 1) Our rebuttal addresses some of your concerns about the paper; 2) there is anything else we can do in the next 4 days to change your opinion/position on the current rating?