Analysis of Search Heuristics in the Multi-Armed Bandit Setting
This work addresses the efficiency of search heuristics in multi-armed bandit problems, which is incremental as it builds on existing methods to analyze specific algorithms.
The paper tackled the problem of identifying a Condorcet winner in the Dueling Bandits setting, showing that the (1+1) EA only chooses it with constant probability under certain conditions, while a simple EDA achieves probability 1-Θ(p), and proposed repeated duels to improve the EA's performance.
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.