A Biostatistician Walks into a Casino: Bandits for Experimental Design

Abstract

We propose two novel algorithms for the multi-armed bandit problem, an online learning algorithm in which the learner decides how to allocate their resources among a set of actions and receives a reward accordingly. The learner is faced with the exploitation-exploration tradeoff, in which the learner attempts to maximize their rewards while only having a partial knowledge of the rewards associated with each action; the learner can gain such knowledge only by allocating resources to the action.

Our primary algorithm addresses the setting of logistic contextual bandits. In this setting, the learner is provided a context for each arm that is linked to its binary reward. We propose Polya-Gamma augmented Thompson sampling (PG-TS), a fully Bayesian approach that uses a Polya-Gamma distribution to perform exact sampling from the posterior distribution over parameters governing the relationship between contexts and rewards, and follows the Thompson sampling approach of using these sampled parameters to select an action according to its expected reward.

Our secondary algorithm addresses the problem of species discovery in a multiple-population setting. We propose Good-Toulmin estimated Thompson sampling (GT-TS), an approach that sequentially chooses populations from which to draw samples based on the expected number of unseen species that will be discovered according to the Good-Toulmin estimator.

We show that PG-TS and GT-TS demonstrate strong empirical behavior on both simulated and real-world data sets. Both algorithms have immediate biological applications, and can be used to improve the efficiency of experimental studies.