Simple Bayesian Algorithms for Identifying the Best Arm in a Multi-Armed Bandit
Wednesday, November 29, 2017 - 1:30pm
Event Calendar Category
Uncategorized
Speaker Name
Daniel Russo
Affiliation
Columbia University
Building and Room number
36-428 (Haus Room)
Abstract
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.
Russo will propose several 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. He will also present numerical experiments exhibiting performance surpassing competing approaches. Finally, if time permits, he will discuss how these ideas can be extended to address much more complex sequential decision-making problems.
Biography
Daniel Russo is an assistant professor in the Decision, Risk, and Operations division of the Columbia Business School. His research lies at the intersection of statistical machine learning and sequential decision-making, and contributes to the fields of online optimization, reinforcement learning, and sequential design of experiments. He joined Columbia in Summer 2017, after spending year as an assistant professor in the MEDS department at Northwestern's Kellogg School of Management and one year at Microsoft Research in New England as Postdoctoral Researcher. He received his PhD from Stanford University in 2015, under the supervision of Benjamin Van Roy. In 2011, he received his BS in Mathematics and Economics from the University of Michigan.