Algorithms for the multi-armed bandit problem
The stochastic multi-armed bandit problem is an important model for studying the explorationexploitation tradeo in reinforcement learning. Although many algorithms for the problem are well-understood theoretically, empirical conrmation of their eectiveness is generally scarce. This paper presents a thorough empirical study of the most popular multi-armed bandit algorithms. Three important observations can be made from our results. Firstly, simple heuristics such as -greedy and Boltzmann exploration outperform theoretically sound algorithms on most settings by a signicant margin. Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identies for each algorithm the settings where it performs well, and the settings where it performs poorly. These properties are not described by current theory, even though they can be exploited in practice in the design of heuristics. Thirdly, the algorithms’ performance relative each to other is aected only by the number of bandit arms and the variance of the rewards. This nding may guide the design of subsequent empirical evaluations. In the second part of the paper, we turn our attention to an important area of application of bandit algorithms: clinical trials. Although the design of clinical trials has been one of the principal practical problems motivating research on multi-armed bandits, bandit algorithms have never been evaluated as potential treatment allocation strategies. Using data from a real study, we simulate the outcome that a 2001-2002 clinical trial would have had if bandit algorithms had been used to allocate patients to treatments. We nd