  We study the problem of planning restless multi-armed bandits (RMABs) with
multiple actions. This is a popular model for multi-agent systems with
applications like multi-channel communication, monitoring and machine
maintenance tasks, and healthcare. Whittle index policies, which are based on
Lagrangian relaxations, are widely used in these settings due to their
simplicity and near-optimality under certain conditions. In this work, we first
show that Whittle index policies can fail in simple and practically relevant
RMAB settings, even when the RMABs are indexable. We discuss why the optimality
guarantees fail and why asymptotic optimality may not translate well to
practically relevant planning horizons.
  We then propose an alternate planning algorithm based on the mean-field
method, which can provably and efficiently obtain near-optimal policies with a
large number of arms, without the stringent structural assumptions required by
the Whittle index policies. This borrows ideas from existing research with some
improvements: our approach is hyper-parameter free, and we provide an improved
non-asymptotic analysis which has: (a) no requirement for exogenous
hyper-parameters and tighter polynomial dependence on known problem parameters;
(b) high probability bounds which show that the reward of the policy is
reliable; and (c) matching sub-optimality lower bounds for this algorithm with
respect to the number of arms, thus demonstrating the tightness of our bounds.
Our extensive experimental analysis shows that the mean-field approach matches
or outperforms other baselines.
