Adaptive treatment allocation and the multi-armed bandit problem (Q1102059)

There are k distinct statistical populations each specified by a univariate density function characterized by a parameter of unknown value. The question concerns how \(x_ 1,x_ 2,...,x_ N\) should be sampled sequentially from the k populations in order to maximize (in some sense) the mean value of their sum. A class of simple allocation rules based on upper confidence bounds for the population parameters is proposed. These rules are shown to exhibit asymptotic optimality in both a Bayesian and a frequentist sense. A simulation study provides evidence that the rules perform well even for moderate values of N.