Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms

Abstract

We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments.