Asymptotic Optimal Control of Markov-Modulated Restless Bandits - LAAS-Réseaux et Communications Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Asymptotic Optimal Control of Markov-Modulated Restless Bandits

Résumé

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.
Fichier principal
Vignette du fichier
Sigmetrics_mod_env_accepted_v7_HAL (1).pdf (411.01 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-01696329 , version 1 (09-02-2018)

Identifiants

  • HAL Id : hal-01696329 , version 1

Citer

Santiago Duran, Ina Maria Maaike Verloop. Asymptotic Optimal Control of Markov-Modulated Restless Bandits. ACM Sigmetrics 2018, Jun 2018, Irvine, United States. ⟨hal-01696329⟩
132 Consultations
17 Téléchargements

Partager

Gmail Facebook X LinkedIn More