Analysis of Search Heuristics in the Multi-Armed Bandit Setting

A team of computer scientists has published a rigorous analysis comparing how different search heuristics handle the classic exploration-exploitation dilemma, framed as a 'Dueling Bandits' problem. In this stochastic setting, each option (or 'arm') has a fixed probability of beating another, and the goal is to identify the 'Condorcet winner'—the arm that beats all others with a probability greater than 1/2. The researchers proved that a standard (1+1) Evolutionary Algorithm performs poorly, only selecting the optimal winner with a constant probability even when its advantage is significant (p=Ω(1/n)). This highlights a fundamental weakness in how this classic EA balances trying new options versus sticking with known good ones.

In a striking contrast, the paper demonstrates that a simple Estimation of Distribution Algorithm (EDA), specifically one based on the Max-Min Ant System with an iteration-best update, is far more effective. This EDA maintains a probability distribution over arms and was shown to select the Condorcet winner with a much higher probability of 1-Θ(p). As a potential fix for the underperforming (1+1) EA, the authors also show that employing repeated duels between arms can significantly boost the probability of the correct winner appearing in the algorithm's stationary distribution. The findings, accepted at the GECCO 2026 conference, provide formal guidance for algorithm selection in areas like hyperparameter tuning, online recommendation systems, and any AI application requiring optimal decision-making under uncertainty.