Printed in N. Ireland?Applied Probability Trust 1991 LET'ERS TO THE EDITOR ADDENDUM TO 'ON AN INDEX POLICY FOR RESTLESS BANDITS'

We show that the fluid approximation to Whittle's index policy for restless bandits has a globally asymptotically stable equilibrium point when the bandits move on just three states. It follows that in this case the index policy is asymptotic optimal. In [2] we investigated properties of an index policy for restless bandits that had been the subject of an interesting paper by Whittle [3]. We showed that if the fluid approximation to his index policy has a globally asymptotically stable equilibrium point then it is asymptotically optimal, for the problem of choosing which m out of n bandits to make active, as m, n-- 0, with m/n = a. We observed that the existence of such a point is guaranteed when the bandits move on just k = 2 states. However, a counterexample with k = 4 states showed that this is not the case in general (though with very small suboptimality). The conjecture that the index policy might be asymptotically optimal when the bandits move on k = 3 states was left unanswered. The present note confirms that conjecture. In this note we use the notation of [2] and refer to formula and theorem numbers in that paper. The state of the n arms (or bandits) under application of the index policy is expressed by a probability vector Zn(t) = (Zn1(t), z42(t), Zn3(t)). The fluid approximation to zn(t) is given by the solution to i = Q(z)z (10), where the qj,(z) are given by (9). Lemma 1. Assume the problem is indexable with index order 1, 2, 3. Then the fluid approximation for Zn(t) is globally asymptotically stable. Proof. Imposing the condition that z1(t) + z2(t) + z3(t) = 1 we eliminate z2(t) and the equation for i2(t), and we partition the region C = {z1(t), z3(t)- 0, zl(t)+ z3(t) 1} int