Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits

We consider a general infinite horizon Heterogeneous Restless multi-armed Bandit (RMAB). Heterogeneity is a fundamental problem for many real-world systems largely because it resists many concentration arguments. In this paper, we assume that each of the N arms can have different model parameters. Model predictive control is a well-known control strategy that repeatedly solves a finite-horizon optimization problem of length τ to produce a policy that can be applied to an infinite-horizon setting. In this paper, we adopt this approach by repeatedly solving a finite linear program, yielding what we call the LP-update policy for the infinite-horizon problem. Under a mild assumption of uniform ergodicity, we show an O (sqrt 1/N) suboptimality gap on this well-known algorithm that works very well in practice. In addition to the LP-update policy we are able to derive a finite-horizon policy (LP-update with recomputation) that segments the infinite time horizon into finite horizon problems that allow us to explicitly connect the length of computation time to the acceptable error tolerance. Our simulations demonstrate that our algorithm works extremely well even when this finite-horizon, τ, is very small (in our case 5), which makes it computationally efficient. Our theoretical results draw on techniques from the model predictive control literature by invoking the concept of dissipativity and generalize quite easily to the more general weakly coupled heterogeneous Markov Decision Process setting. In addition, we draw a parallel between our own policy and the LP-index policy by showing that the LP-index policy corresponds to τ=1.