Multi-armed bandits with switching costs

The multi-armed bandit problem with switching cost is investigated. It is shown that along optimal policies, decisions about the processor allocation need to be made only at stopping times that achieve an appropriate index (the well known “Gittins index” or a “switching index” that is defined for switching cost). Furthermore, sufficient conditions for optimality of allocation strategies, based on limited look-ahead techniques, are established. These conditions together with the above mentioned feature of optimal scheduling strategies simplify the search for an optimal allocation policy. Nevertheless, the determination of optimal allocation policies remains a difficult and challenging task