A note on bandits with a twist

Abstract. A variant of the multi-armed bandit problem was recently introduced by Dimitriu, Tetali and Winkler. For this model (and a mild generalization) we propose faster algorithms to compute the Gittins index. The indexability of such models follows from earlier work of Nash on generalized bandits. Key words. Multiarmed bandit problem, generalized bandit problem, stochastic scheduling, priority rule, Gittins index, game AMS subject classifications. 60J10, 66C99, 60G40, 90B35, 90C40 1. Introduction. Th