A Marginal Productivity Index Policy for the Finite-Horizon Multiarmed Bandit Problem

This paper addresses the discounted discrete-state finite-horizon multiarmed bandit problem. The goal is to design a well-grounded and tractable scheduling policy of index type. The approach is based on reformulating the model as a restless bandit problem, and then deploying the marginal productivity index (MPI) theory developed by the author in recent work, which extends the approach of Klimov (1974), Gittins (1979) and Whittle (1988). It is shown that the model satisfies the author´s sufficient conditions for existence of the MPI. An efficient recursive procedure is proposed for computing the finite-horizon MPI. This further furnishes a new method for approximating the infinite-horizon Gittins index.