A Survey of Strategies for the Multi-Armed Bandit Problem

Abstract

We explore, in increasing complexity, various strategies for addressing the Multi- Armed Bandit Problem in order to find the algorithm that maximizes the clickthrough rate in the Exploration and Exploitation Challenge 3 competition. The data used result from the actions of web site visitors who clicked on news articles, and we utilize different policies to decide how to optimally display the various articles. We implement several policies and find a score for two versions of each algorithm: one that is primed on test data and one that encounters the actual competition data without any prior knowledge. An Upper Con dence Bound strategy proves to outperform other algorithms for the tuned trials, and a more recent policy with bounded regrets serves as the best out of the box strategy.