Extensions of the multiarmed bandit problem: The discounted case

Abstract

There are N independent machines. Machine i is described by a sequence {X^{i}(s), F^{i}(s)} where X^{i}(s) is the immediate reward and F^{i}(s) is the information available before i is operated for the sth lime. At each time one operates exacfiy one machine; idle machines remain frozen. The problem is to schedule the operation of the machines so as to maximize the expected total discounted sequence of rewards. An elementary proof shows that to each machine is associated an index, and the optimal policy operates the machine with the largest current index. When the machines are completely observed Markov chains, this coincides with the well-known Gittins index rule, and new algorithms are given for calculating the index. A reformulation of the bandit problem yields the tax problem, which includes, as a special case, Klimov's waiting time problem. Using the concept of superprocess, an index rule is derived for the case where new machines arrive randomly. Finally, continuous time versions of these problems are considered for both preemptive and nonpreemptive disciplines.