Asymptotically efficient adaptive allocation rules for the multiarmed bandit problem with switching cost

The authors consider multiarmed bandit problems with switching cost, define uniformly good allocation rules, and restrict attention to such rules. They present a lower bound on the asymptotic performance of uniformly good allocation rules and construct an allocation scheme that achieves the bound. It is found that despite the inclusion of a switching cost the proposed allocation scheme achieves the same asymptotic performance as the optimal rule for the bandit problem without switching cost. This is made possible by grouping together samples into blocks of increasing sizes, thereby reducing the number of switches to O(log n). Finally, an optimal allocation scheme for a large class of distributions which includes members of the exponential family is illustrated.<>