Special Seminar

Simple Bayesian algorithms for identifying the best arm in a multi-armed bandit
Wednesday, November 2, 2016 - 4:00pm to 5:00pm
Packard 202
Dan Russo (Northwestern)
Abstract / Description: 

This talk considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. Just as the multi-armed bandit problem crystallizes the tradeoff between exploration and exploitation, this "pure exploration" variant crystallizes the challenge of rapidly gathering information before committing to a final decision.

I will propose three simple Bayesian algorithms for allocating measurement effort, and by characterizing fundamental asymptotic limits on the performance of any algorithm, formalize a sense in which these seemingly naive algorithms are the best possible. I will also present numerical experiments exhibiting performance surpassing competing approaches.


Dan Russo is an assistant professor at Northwestern's Kellogg School of Management. He completed his PhD at Stanford in 2015 under the supervision of EE's Ben Van Roy, and spent the 2015-2016 academic year as a post-doc at Microsoft Research New England. His research lies at the intersection of statistical machine learning and sequential decision-making.