Asymptotic Optimal Control of Markov-Modulated Restless Bandits

Abstract : This paper studies optimal control subject to changing conditions. This is an area that recently received a lot of attention as it arises in numerous situations in practice. Some applications being cloud computing systems where the arrival rates of new jobs fluctuate over time, or the time-varying capacity as encountered in power-aware systems or wireless downlink channels. To study this, we focus on a restless bandit model, which has proved to be a powerful stochastic optimization framework to model scheduling of activities. In particular, it has been extensively applied in the context of optimal control of computing systems. This paper is a first step to its optimal control when restless bandits are subject to changing conditions, the latter being modeled by Markov-modulated environments. We consider the restless bandit problem in an asymptotic regime, which is obtained by letting the population of bandits grow large, and letting the environment change relatively fast. We present sufficient conditions for a policy to be asymptotically optimal and show that a set of priority policies satisfies these. Under an indexability assumption, an averaged version of Whittle's index policy is proved to be inside this set of asymptotic optimal policies. The performance of the averaged Whittle's index policy is numerically evaluated for a multi-class scheduling problem in a wireless downlink subject to changing conditions. While keeping the number of bandits constant, we observe that the average Whittle index policy becomes close to optimal as the speed of the modulated environment increases.
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.laas.fr/hal-01696329
Contributor : Santiago Duran <>
Submitted on : Friday, February 9, 2018 - 12:14:54 PM
Last modification on : Friday, October 11, 2019 - 8:23:20 PM
Long-term archiving on : Wednesday, May 2, 2018 - 2:00:08 PM

Identifiers

  • HAL Id : hal-01696329, version 1

Citation

Santiago Duran, Ina Verloop. Asymptotic Optimal Control of Markov-Modulated Restless Bandits. ACM Sigmetrics 2018, Jun 2018, Irvine, United States. ⟨hal-01696329⟩

Share

Metrics

Record views

206

Files downloads

328