LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality

Nicolas Gast, Bruno Gaujal, Chen Yan

We provide a framework to analyse control policies for the restless Markovian bandit model, under both finite and infinite time horizon. We show that when the population of arms go…