Analysis of Search Heuristics in the Multi-Armed Bandit Setting

Jasmin Brandt; Barbara Hammer; Timo Kötzing; Jurek Sander

cs.NEApr 9, 2026

Analysis of Search Heuristics in the Multi-Armed Bandit Setting

Authors: Jasmin Brandt, Barbara Hammer, Timo Kötzing, Jurek Sander

Organizations: University of Bielefeld Bielefeld, Germany · Hasso Plattner Institute University of Potsdam Potsdam, Germany

Abstract

We consider the classic Multi-Armed Bandit setting to understand the exploration/exploitation tradeoffs made by different search heuristics. Since many search heuristics work by comparing different options (in evolutionary algorithms called "individuals"; in the Bandit literature called "arms"), we work with the "Dueling Bandits" setting. In each iteration, a comparison between different arms can be made; in the binary stochastic setting, each arm has a fixed winning probability against any other arm. A Condorcet winner is any arm that beats every other arm with a probability strictly higher than $1/2$ . We show that evolutionary algorithms are rather bad at identifying the Condorcet winner: Even if the Condorcet winner beats every other arm with a probability $1-p$ , the (1+1) EA, in its stationary distribution, chooses the Condorcet winner only with constant probability if $p=Ω(1/n)$ . By contrast, we show that a simple EDA (based on the Max-Min Ant System with iteration-best update) will choose the Condorcet winner in its maintained distribution with probability $1-Θ(p)$ . As a remedy for the (1+1) EA, we show how repeated duels can significantly boost the probability of the Condorcet winner in the stationary distribution.

Figures & tables

Figure 1. Plot of the upper and lower bounds on the probability that arm $i$ is the best in expectation for different arms and instantiations of the Plackett-Luce model. Upper bound of probability that arm $i$ is the best in expectation converges to $1$ for larger number of duels. Upper bound of probability that arm $i$ is the best in expectation converges to $1$ for larger number of duels. Analogously the lower bound converges to $0$. This occurs faster for larger differences of the utilities. — Figure 1. Plot of the upper and lower bounds on the probability that arm $i$ is the best in expectation for different arms and instantiations of the Plackett-Luce model. Upper bound of probability that arm $i$ is the best in expectation converges to $1$ for larger number of duels. Upper bound of probability that arm $i$ is the best in expectation converges to $1$ for larger number of duels. Analogously the lower bound converges to $0$ . This occurs faster for larger differences of the utilities.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2. Lower bound for the probability that arm $1$ is in expectation the winner over arm $2$ after up to $10$ duels for different instantiations of the underlying Plackett-Luce Model. Lower bound for the probability that arm $1$ is in expectation the winner over arm $2$ after up to $10$ duels increases for larger number of duels. Lower bound for the probability that arm $1$ is in expectation the winner over arm $2$ after up to $10$ duels increases for larger number of duels. Higher bound for larger difference in the utilities.

Figure 3. Lower bound for the probability that a specific arm wins in expectation at most $t$ times over all other arms at after up to $10$ duels for different instantiations of the underlying Plackett-Luce Model. Lower bound for the probability that a specific arm wins in expectation at most $t$ times over all other arms at after up to $10$ duels decreases for larger number of duels. Lower bound for the probability that a specific arm wins in expectation at most $t$ times over all other arms at after up to $10$ duels decreases for larger number of duels.

Figure 4. Lower bound for the probability that a specific arm wins in expectation at least $t$ times over all other arms at after up to $10$ duels for different instantiations of the underlying Plackett-Luce Model. Lower bound for the probability that a specific arm wins in expectation at least $t$ times over all other arms at after up to $10$ duels increases for larger number of duels. Lower bound for the probability that a specific arm wins in expectation at least $t$ times over all other arms at after up to $10$ duels increases for larger number of duels. Higher bound for larger difference in the utilities.

Explore similar work

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives
Mar 19, 2026S Akash, Pratik Gajane, Jawar SinghMulti-Armed Bandits Adversarial Bandits
Indian Institute of Technology Patna, India · University of Orléans, France
The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
Mar 16, 2026El Mehdi Saad, Victor Thuot, Nicolas VerzelenBest-Arm Identification Multi-Armed Bandits
CC-UM6P-Rabat · INRAE, MISTEA, Institut Agro, Univ. Montpellier Montpellier, France · MISTEA +1
Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
Jun 1, 2026Pu Wang, Yao-Xiang DingMulti-Armed Bandits Best-Arm Identification
State Key Lab of CAD&CG, Zhejiang University

Mar 19, 2026J/K move · Enter open · S save

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives

S Akash, Pratik Gajane, Jawar Singh

Indian Institute of Technology Patna, India · University of Orléans, France

Multi-Armed Bandits Adversarial Bandits Pairwise Preference Learning

Open paper AskPDF arXiv

Multi-dueling bandits, where a learner selects

m \geq 2

arms per round and observes only the winner, arise naturally in many applications including ranking and recommendation systems, yet a fundamental question has remained open: can a single algorithm perform optimally in both stochastic and adversarial environments, without knowing which regime it faces? We answer this affirmatively, providing the first best-of-both-worlds algorithms for multi-dueling bandits under both Condorcet and Borda objectives. For the Condorcet setting, we propose

\texttt{MetaDueling}

, a black-box reduction that converts any dueling bandit algorithm into a multi-dueling bandit algorithm by transforming multi-way winner feedback into an unbiased pairwise signal. Instantiating our reduction with

\texttt{Versatile-DB}

yields the first best-of-both-worlds algorithm for multi-dueling bandits: it achieves

O(\sqrt{KT})

pseudo-regret against adversarial preferences and the instance-optimal

O\left(\sum_{i \neq a^\star} \frac{\log T}{Δ_i}\right)

pseudo-regret under stochastic preferences, both simultaneously and without prior knowledge of the regime. For the Borda setting, we propose

\texttt{SA-MiDEX}

, a stochastic-and-adversarial algorithm that achieves

O\left(K^2 \log KT + K \log^2 T + \sum_{i: Δ_i^{\mathrm{B}} > 0} \frac{K\log KT}{(Δ_i^{\mathrm{B}})^2}\right)

regret in stochastic environments and

O\left(K \sqrt{T \log KT} + K^{1/3} T^{2/3} (\log K)^{1/3}\right)

regret against adversaries, again without prior knowledge of the regime. We complement our upper bounds with matching lower bounds for the Condorcet setting. For the Borda setting, our upper bounds are near-optimal with respect to the lower bounds (within a factor of

K

) and match the best-known results in the literature.

Abstract

Explore similar work

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives

The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits