Beyond Numeric Awards: In-Context Dueling Bandits with LLM Agents
Large Language Models (LLMs);In-Context Decision-Making;Dueling Bandits
Yes
No ethics review needed.
- 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
- 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.
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.
- 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).
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
1. Why is it important to develop an LLM-guided algorithm for dueling bandits?
- 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.
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).
- 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.
Yes
No ethics review needed.
Is my understanding of the assumption in Theorem 4.2 correct?
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.
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.
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?
@inproceedings{
anonymous2024beyond,
title={Beyond Numeric Awards: In-Context Dueling Bandits with {LLM} Agents},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=sGfVBi15uY},
note={under review}
}
In-context decision-making is an important capability of artificial general intelligence, which Large Language Models (LLMs) have effectively demonstrated in various scenarios. However, 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 decision-makers in the context of Dueling Bandits (DB). We compare GPT-3.5 Turbo, GPT-4, GPT-4 Turbo, Llama 3.1, and o1-preview against eight well-established DB algorithms. Our results reveal that LLMs, particularly GPT-4 Turbo, quickly identify the Condorcet winner, thus outperforming existing state-of-the-art algorithms in terms of weak regret. Nevertheless, LLMs struggle to converge even when explicitly prompted to do so and are sensitive to prompt variations. To overcome these issues, we introduce a hybrid algorithm: LLM-Enhanced Adaptive Dueling (LEAD), which takes advantage of both in-context decision-making capabilities of LLMs and theoretical guarantees inherited from classic DB algorithms. We show that LEAD has theoretical guarantees on both weak and strong regret and validate its robustness even with noisy and adversarial prompts. The design of such an algorithm sheds light on how to enhance trustworthiness for LLMs used in decision-making tasks where performance robustness matters.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Large Language Models (LLMs) In-Context Decision-Making Dueling Bandits
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/7c9c3a9a9edbdee97fabdfd75db958bd3232ac5c.pdf
foundation or frontier models, including LLMs
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Beyond Numeric Awards: In-Context Dueling Bandits with LLM Agents
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission