Beyond Numeric Awards: In-Context Dueling Bandits with LLM Agents

Authors: Fanzeng Xia, Hao Liu, Yisong Yue, Tongxin Li
Primary area: foundation or frontier models, including LLMs
Keywords: Large Language Models (LLMs), In-Context Decision-Making, Dueling Bandits

Abstract:
In-context reinforcement learning (ICRL) is a frontier paradigm for solving reinforcement learning problems in the foundation model era. While ICRL capabilities have been demonstrated in transformers through task-specific training, the potential of Large Language Models (LLMs) out-of-the-box remains largely unexplored. Recent findings highlight that LLMs often face challenges when dealing with numerical contexts, and limited attention has been paid to evaluating their performance through preference feedback generated by the environment. This paper is the first to investigate the performance of LLMs as in-context decision-makers in the problem of Dueling Bandits (DB), a stateless preference-based reinforcement learning setting that extends the classic Multi-Armed Bandit (MAB) model by querying for preference feedback. We compare GPT-3.5 Turbo, GPT-4, GPT-4 Turbo, Llama 3.1, and o1-preview against nine well-established DB algorithms. Our results reveal that our top-performing LLM, GPT-4 Turbo, possesses an understanding of relative decision-making sufficient to achieve low weak regret in DB by quickly selecting the best arm in duels. However, we observed that an optimality gap exists between LLMs and classic DB algorithms in terms of strong regret. LLMs struggle to converge and consistently exploit even when explicitly prompted to do so, and are sensitive to prompt variations. To overcome these issues, we introduce an agentic flow framework: LLM with Enhanced Algorithmic Dueling (LEAD), which integrates off-the-shelf DB algorithms with LLM agents through fine-grained adaptive interplay. We show that LEAD has theoretical guarantees inherited from classic DB algorithms on both weak and strong regret. We validate its efficacy and robustness even with noisy and adversarial prompts. The design of such an agentic framework sheds light on how to enhance the trustworthiness of general-purpose LLMs used for in-context decision-making tasks.

Decision: reject
Reviewer scores: 5, 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1730211949576

thread_type:
official_review

<thread_object>
creator: reviewer_fhh8

<content>
summary:
This submission studies the abilities of large language models (LLMs) in dueling bandit settings. In dueling bandits, a decision-maker (in this case, an LLM) chooses a pair of arms at each time-step, but only observes the binary outcome of a noisy comparison between the two selected arms. This submission asks whether LLMs are effective in-context agents for solving dueling bandit problems. 

In dueling bandits, the learner selects 2 of K arms for a noisy comparison at each round, i.e. a duel. The probability an arm wins a duel is proportional to how “distinguishable” the two arms are from one another. The dueling bandit problem is given to the LLM via a natural language description, with an externally-summarized history, and the LLM is prompted to use zero-shot chain-of-thought reasoning. In dueling bandits, the goal is to maximize the cumulative reward over the time horizon, where the reward is the sum of the (unknown) probabilities that the two chosen arms are the best arm. The performance of dueling bandit algorithms are measured by strong and weak regret. Strong regret compares the cumulative performance of the best arm against both arms chosen by the algorithm, and weak regret compares the best arm against the better of the two selected arms.

The authors empirically compare 5 LLMs against 8 baseline dueling bandit algorithms in 2 stochastic environments. They find that GPT-3.5 Turbo and GPT-4 fail to solve the dueling bandits problem, but GPT-4 Turbo outperforms state-of-the-art dueling bandit algorithms in terms of weak regret. Across all LLMs, they find that performance degrades as the number of arms increases. They capture this via the notion of a relative distance window, which is the maximum number of arms that an LLM agent can effectively handle in a dueling bandit problem while maintaining state-of-the-art performance. 

Somewhat surprisingly, the authors find that GPT-4 turbo achieves lowest weak regret among all LLMs & SOTA baselines, but it struggles to converge to a single best arm. In contrast, O1-preview shows better strong regret performance than GPT-4 turbo, but its weak regret performance is significantly worse. The authors conclude that GPT-4 turbo can serve as an effective decision-maker in the short term, by quickly identifying and exploiting the best arm with low variance across different instances. However, its long-term performance is hindered by over-estimation bias and lack of convergence. 

Motivated by these findings, the authors propose an algorithm (LEAD) for using LLMs to solve dueling bandit problems. The algorithm has two phases. In phase 1, the algorithm starts with a set of candidate options. Given two options suggested by the language model, the algorithm identifies a winner between them. This winning option is then compared with each remaining option in the candidate set until it either loses or all options have been matched. If the winning option remains undefeated, a "TrustLLM" flag is set to True; if it is defeated, the flag is set to False. In Phase 2, if the winning option from Phase 1 is defeated, the algorithm performs one round of a secondary selection process, using an estimated preference matrix to choose an "incumbent" option. After Phase 2, the algorithm returns to Phase 1, repeating the process until only the best option remains in the candidate set.

Under an assumption that the worst-case behavior of the LLM is equivalent to a randomizer that selects action pairs uniformly-at-random, the authors show that there exists an attacker strategy such that any standalone LLM agent will suffer high expected regret. The authors also prove theoretical guarantees for LEAD under an assumption on the abilities of the LLM. 

Empirically, the authors find that LEAD exhibits competitive performance with baselines in terms of strong regret, and LEAD has superior performance in terms of weak regret. They also show that LEAD can overcome a biased history, whereas a standalone LLM cannot.

strengths:
Studying the abilities of LLM agents in in-context reinforcement learning problems is an exciting new direction. While the authors are not the first to do this, they are the first to consider the ability of LLMs in dueling bandits problems. The authors provide a fairly comprehensive set of empirical results, both in benchmarking the performance of LLM agents and proposing a mitigation (LEAD) to improve their performance. The submission is also well-written for the most part.

weaknesses:
I found the theoretical results to be somewhat unsatisfying. For one, while the lower bound is correct as-stated, it seems to not capture the spirit of the problem, as (presumably) the reason to use an LLM to solve a decision-making task is that the decision-maker belives the LLM has learned some useful knowledge about said problem somewhere during its training. As such, if the problem instance resembles something adversarial, it would probably be better to deploy an off-the-shelf algorithm for dueling bandits. 

I also had a hard time parsing Theorem 4.2. In particular, the regret bounds only kick in when the two arms the LLM recommends always contains the best arm. This seems overly restrictive, and would probably not hold in practice. In fact, is this property even known to be satisfied for any off-the-shelf dueling bandit algorithms?

questions:
Is my understanding of the assumption in Theorem 4.2 correct?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730555720813

thread_type:
official_review

<thread_object>
creator: reviewer_dsfz

<content>
summary:
The authors explore the use of LLMs in the dueling bandits problem. They find that GPT-4 Turbo is the strongest LLMs in their experiments. They create a dueling bandit algorithm that can take LLM advice initially but then switches to an algorithm with guarantees if the advice goes bad. By tuning hyperparameters, they can get their LLM advice guided algorithm to perform on par with the strongest competing (LLM-less methods).

strengths:
- They are able to achieve strong empirical performance with an LLM-advised algorithm that still maintains worst-case theoretic guarantees. This could be especially valuable in the setting where there is text or image context that is provided for each arm that can be exploited by an LLM or VLM. For example, in an information retrieval setting, each arm could come with text describing what it is returned, and the context could be the search query.

weaknesses:
- Right now, the motivation of the paper is not very clear. There seems to be no reason to want to use an LLM-guided dueling bandit algorithm unless there is text or image context for the arms. None of the experiments have this, and the authors do not discuss what this could be.

As is, there is no performance benefit to the LLM-guided version—it is slower, more expensive, and does random stuff sometimes. Yes, it can perform comparably sometimes, but requires hyperparameter tuning to do so.
- The presentation is bad—flow is awkward, lots of key details are deep in the appendix (for example, the MatchArms procedure). Much of the main body text is not very impactful. There are many citations that should be parenthetical. 
- From an LLMology perspective, the central mystery is why o1 preview is worse than GPT 4 here. This problem should be easily amenable to o1 style synthetic data, so we can probably conclude that it wasn't included in the o1 training data, but still, the extended CoT should be helpful. The LLMologists would probably appreciate some analysis of when o1 preview fails.

questions:
1. Why is it important to develop an LLM-guided algorithm for dueling bandits?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730568384795

thread_type:
official_review

<thread_object>
creator: reviewer_yncf

<content>
summary:
This paper investigates the capabilities of Large Language Models (LLMs) as decision-makers in the dueling bandits setting, focusing on preference feedback instead of numerical rewards. The authors evaluate models like GPT-4 TURBO and compare their performance against classic DB algorithms. While GPT-4 TURBO demonstrates strong short-term decision-making by identifying the Condorcet winner with low weak regret, it struggles with long-term convergence and prompt sensitivity. To address these limitations, the authors introduce LEAD (LLM-Enhanced Adaptive Dueling), a hybrid algorithm combining LLM capabilities with the theoretical guarantees of traditional DB algorithms. LEAD shows improved robustness and efficacy, even under noisy or adversarial prompts.

strengths:
The paper uniquely applies LLMs to a DB context, demonstrating their strengths and vulnerabilities.

Comprehensive experiments show how LLMs compare with state-of-the-art DB algorithms and the advantages of the LEAD framework.

LEAD is designed with strong theoretical underpinnings that ensure bounded regret, which is essential for real-world applications.

weaknesses:
The LEAD algorithm essentially combines LLM capabilities with the IF2 algorithm, which might be perceived as a straightforward application rather than a fundamentally new algorithm.

questions:
1. The paper mentions theoretical guarantees for LEAD. Are these guarantees entirely new, or do they largely extend those of IF2? If novel, could you explain the key differences and how these guarantees are specific to the hybrid nature of LEAD?

2. How does the LEAD algorithm scale when the number of arms or the problem complexity increases? Are there any significant computational trade-offs when integrating LLMs with IF2, particularly in larger decision-making environments?

3. The paper focuses on dueling bandit problems. Can the approach be generalized to other types of decision-making or preference-based learning problems? If so, are there adjustments needed to apply LEAD outside the DB context?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730640441645

thread_type:
official_review

<thread_object>
creator: reviewer_g8se

<content>
summary:
This paper analyzes the in-context decision-making abilities of LLMs in dueling bandits, which is a preference-based variant of the multi-armed bandit problem. The authors compare the performance of various model including GPT-4 and Llama in small dueling bandit problems (e.g., K=5 arms). Here, the performance of the LLMs is measured by their weak and strong Codorcet winner regret. Overall, the results suggest that the LLMs are incapable of realiably minimizing regret with the exception of GPT-4 Turbo (w.r.t. weak regret). The authors finally propose to combine LLM and explore-then-commit dueling bandit algorithms.

strengths:
- I believe there is currently quite some interest in evaluations of in-context decision-making capabilities of LLMs w.r.t. exploratory and interactive learning behavior (see, e.g., prior work by Krishnamurthy et al. (2024)). 
- The authors test a wide range of models including GPT-4 Turbo, Llama 3.1, and o1-preview. 
- The experiments are described in detail. 
- The authors propose a framework to integrate LLMs with existing (explore-then-commit) dueling bandit algorithms, which is conceptually interesting.

weaknesses:
- All evaluations are performed on utility-based (i.e., reward-based) dueling bandits with a linear link function, which is arguably as similar as one can formulate the dueling bandit to the multi-armed bandit. This doesn't really capture the full complexity of learning from preference feedback. In particular, throughout all considered problems SST and STI are satisfied and no ablation w.r.t. the effect of this additional structure on in-context learning abilities are included. It would be much more interesting to test the ability of in-context learning on problems without transitivity in my opinion. 
- Related to the above point, the paper only considers problem where the Condorcet winner exists. There are many alternative solution concepts in dueling bandits such as the Borda winner, Copeland winner, and von Neumann winner, which are guaranteed to exist. 
- Oddly enough in your baselines you didn't include Versatile-DB (Saha and Gaillard 2022), which is the only near-optimal dueling bandit algorithm known (afaik) for the dueling bandit problem without additional assumptions. 
- From my point of view the contributions of this paper are primarily empirical. Still, I want to comment on the shortcomings and lack of significance of the theoretical contributions: 
	- Assumption 1 states that the LLM behaves the same as a uniform sampler in the worst-case so that Theorem 4.1 simply states that a uniform sampler has regret at least T/K in the worst-case, which is obvious. In Theorem 4.2, the properties of the LLM also don't matter since the guarantee for strong and weak regret simply uses that the number of additional comparisons due to the LLM is bounded by design (we don't even have to use the information generated by the LLM choices).

questions:
- I don't understand the purpose of equation (4), i.e., the "relative decision window". Without defining the function $h$ I don't understand what it tells us. The function $I$ is also not defined concretely. Could you elaborate further? Is the point you're trying to make just that as the number of arms increases LLM performance decreases? 
- The claim (line 224) that "This reveals relative decision-making abilities emerge as the general capabilities of LLMs grow via ..." is too strong in my opinion, as the evaluation are performed only on dueling bandits with a strict order. Could you defend this claim; especially, in view of the limited class (and size) of dueling bandit problems you consider in this paper? 

Other minor suggestions:
- Make sure to use \citep instead of \cite or \citet to have parentheses around your references when they are not referred to actively: For example, in the first line, it should be (Wei et al. 2022) instead of Wei et al. (2022).  
- Line 36 typo: rewards instead of awards
</content>
</thread_object>

</thread>
<thread>
creation date:
1732763661765

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of the Modifications Made in the Manuscript

comment:
We sincerely appreciate the valuable feedback from the reviewers and will address them carefully in each individual rebuttal. We have revised the manuscript to address the concerns raised and to clarify the positioning and scope of our paper. We have highlighted the significant modifications in the current version as summarized below:

1. **Abstract**:  
The abstract (and the overall presentation of the paper) has been reframed to clearly position our focus on the In-Context Reinforcement Learning (ICRL) [1, 2, 3, 4] capabilities of general-purpose LLMs and their challenges. We refined the presentation to emphasize that our method introduces an agentic flow framework to bridge the identified optimality gap between LLMs and DB algorithms.

2. **Introduction**:  
The Introduction has been revised to emphasize ICRL's unexplored potential with LLM agents and to strengthen our motivation with a focus on understanding the emergent In-Context Dueling Bandit abilities and strategic behaviors of LLMs.

3. **Experimental Results**:  
We added one baseline, Versatile Dueling Bandits [5], and two intransitive instances (Intransitive-Easy and Intransitive-Hard) to systematically evaluate LLM performance in the standard context-free Dueling Bandits setting with a Condorcet winner. We also adjusted the presentation to better summarize and explain LLM's success and failure modes.

4. **Conclusion**:  
The conclusion has been revised to emphasize the limitations of LLMs, aiming to understand how language-based reasoning can inspire robust agentic frameworks that translate words into actions through the interplay between rule-based experts and in-context LLM agents.

5. **Appendix**:  
We added exemplars of system biases, a comparison of o1 and 4turbo ratios (Best Arm Inclusion Ratio, Converged Best Arm Ratio, and Suboptimal Duel Ratio), a description of the Intransitive Case, and experimental results for Intransitive-Easy and Intransitive-Hard.

[1] Laskin, Michael, et al. "In-context reinforcement learning with algorithm distillation." arXiv preprint arXiv:2210.14215 (2022).

[2] Lee, Jonathan, et al. "Supervised pretraining can learn in-context reinforcement learning." Advances in Neural Information Processing Systems 36 (2024).

[3] Krishnamurthy, Akshay, et al. "Can large language models explore in-context?." arXiv preprint arXiv:2403.15371 (2024).

[4] Nie, Allen, et al. "EVOLvE: Evaluating and Optimizing LLMs For Exploration." arXiv preprint arXiv:2410.06238 (2024).

[5] Saha, Aadirupa, and Pierre Gaillard. "Versatile dueling bandits: Best-of-both-world analyses for online learning from preferences." arXiv preprint arXiv:2202.06694 (2022).
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper evaluates LLMs as decision-makers in dueling bandits settings and proposes LEAD, a hybrid algorithm combining LLM capabilities with traditional dueling bandit algorithms. While showing some promise in weak regret performance with LLMs, the work has significant limitations including overly simplified evaluation settings, insufficient theoretical analysis, and unclear practical benefits.