Simple Bayesian Algorithms for Pure-exploration

Thursday, December 6, 2018 - 9:00am - 10:00am
Lind 305
Dan Russo (Columbia University)
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 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. I will also present numerical experiments exhibiting performance surpassing competing approaches. Finally, if time permits, Time permitting, I will discuss how these ideas can potentially be extended to address much more complex sequential decision-making problems.