Princeton University Library Catalog

A Survey of Strategies for the Multi-Armed Bandit Problem

Korać, Damjan [Browse]
Senior thesis
Bubeck, Sébastien [Browse]
Princeton University. Department of Operations Research and Financial Engineering [Browse]
Class year:
84 pages
Restrictions note:
Walk-in Access. This thesis can only be viewed on computer terminals at the Mudd Manuscript Library.
Summary note:
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.