Analysis of Search Heuristics in the Multi-Armed Bandit Setting

• URL: http://arxiv.org/abs/2604.08109v1
• Date: Thu, 09 Apr 2026 11:27:59 GMT
• Title: Analysis of Search Heuristics in the Multi-Armed Bandit Setting
• Abstract summary: We consider the classic Multi-Armed Bandit setting to understand the exploration/exploitation tradeoffs made by different searchs.<n>We show that evolutionary algorithms are rather bad at identifying the Condorcet winner.
• Score: 6.730459235906337
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare [6.353413440036643]
  We consider fairness in dueling bandits, a standard framework for online learning from preference data.<n>We adopt the well-established Nash Social Welfare objective, which maximizes the product of user utilities.<n>We present the Fair-Explore-Then-Commit and Fair-$$-Greedy algorithms with a Condorcet winner identification phase.
  arXiv  Detail & Related papers  (2026-05-03T16:47:24Z)
• The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits [6.244816393907942]
  We study best-arm identification in dueling bandits under the sole assumption that a Condorcet winner exists.<n>We introduce a new identification procedure that exploits the full gap matrix $_i,j=q_i,j-tfrac12$.<n>We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones.
  arXiv  Detail & Related papers  (2026-03-16T12:27:14Z)
• Deceptive Exploration in Multi-armed Bandits [22.14260167840733]
  We consider a multi-armed bandit setting in which each arm has a public and a private reward distribution.<n>An observer expects an agent to follow Thompson Sampling according to the public rewards, however, the deceptive agent aims to quickly identify the best private arm without being noticed.
  arXiv  Detail & Related papers  (2025-10-09T20:15:52Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  We consider the best arm identification problem in the $K-$armed bandit framework.<n>Agent is allowed to play a subset of arms at each time slot instead of one arm.<n>We propose an algorithm that constructs $log K$ groups and performs a likelihood ratio test to detect the presence of the best arm.
  arXiv  Detail & Related papers  (2025-02-03T15:10:08Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  We develop a general framework for clustering and distribution matching problems with bandit feedback.<n>We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding $delta$.<n>Our refined analysis uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as $delta$ vanishes.
  arXiv  Detail & Related papers  (2024-09-08T12:19:12Z)
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  We formulate a new variant of multi-player multi-armed bandit (MAB) model, which captures arrival of requests to each arm and the policy of allocating requests to players. The challenge is how to design a distributed learning algorithm such that players select arms according to the optimal arm pulling profile. We design an iterative distributed algorithm, which guarantees that players can arrive at a consensus on the optimal arm pulling profile in only M rounds.
  arXiv  Detail & Related papers  (2024-08-20T13:57:00Z)
• Top Two Algorithms Revisited [14.783452541904365]
  Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models. We provide a general analysis of Top Two methods, which identifies desirable properties of the leader, the challenger, and the (possibly non-parametric) distributions of the arms. Our proof method demonstrates in particular that the sampling step used to select the leader inherited from Thompson sampling can be replaced by other choices.
  arXiv  Detail & Related papers  (2022-06-13T09:03:24Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  We study the problem of identifying the best arm in a multi-armed bandit environment. A decision entity wishes to find the index of the best arm as quickly as possible, subject to an upper bound error probability. We show that this policy achieves an upper bound that depends on $R$ and is monotonically non-increasing as $Rtoinfty$.
  arXiv  Detail & Related papers  (2022-03-29T04:58:04Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent evaluations of the true reward of each arm. We derive different algorithmic approaches and theoretical guarantees depending on how the evaluations are generated.
  arXiv  Detail & Related papers  (2021-12-13T09:48:54Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  We present a reward model that captures set-dependent reward distribution and assumes no total order for arms. We develop a novel regret analysis and show an $Oleft(frack2 n log Tepsilonright)$ gap-dependent regret bound as well as an $Oleft(k2sqrtn T log Tright)$ gap-independent regret bound.
  arXiv  Detail & Related papers  (2021-03-03T23:08:59Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  We study the top-$k$ extreme contextual bandits problem, where the total number of arms can be enormous. We first propose an algorithm for the non-extreme realizable setting, utilizing the Inverse Gap Weighting strategy. We show that our algorithm has a regret guarantee of $O(ksqrt(A-k+1)T log (|mathcalF|T))$.
  arXiv  Detail & Related papers  (2021-02-15T19:10:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.