Research Article
An Index Policy for Multiarmed Multimode Restless Bandits
@INPROCEEDINGS{10.4108/ICST.VALUETOOLS2008.4410, author={Jos\^{e} Ni\`{o}o-Mora}, title={An Index Policy for Multiarmed Multimode Restless Bandits}, proceedings={3rd International ICST Conference on Performance Evaluation Methodologies and Tools}, publisher={ICST}, proceedings_a={VALUETOOLS}, year={2010}, month={5}, keywords={Markov decision processes dynamic resource allocation multimode projects restless bandits index policies}, doi={10.4108/ICST.VALUETOOLS2008.4410} }- José Niño-Mora
Year: 2010
An Index Policy for Multiarmed Multimode Restless Bandits
VALUETOOLS
ICST
DOI: 10.4108/ICST.VALUETOOLS2008.4410
Abstract
This paper introduces and addresses the multiarmed multimode restless bandit problem, concerning the optimal dynamic allocation of a shared resource to a collection of projects which can be operated in multiple modes, subject to a peak resource consumption constraint, thus extending the conventional multiarmed restless bandit problem where projects are restricted to a binary-mode (active or passive) operation. After discussing a motivating application, concerning the optimal dynamic power allocation to multiple users sharing a wireless downlink communication channel subject to a peak energy constraint, a general approach is developed to design and compute a tractable heuristic policy based on marginal productivity indices (MPIs) defined separately for each project. Sufficient conditions are given which ensure both the existence of such an index and the validity of an adaptive-greedy algorithm for its computation. Such conditions extend to multimode projects those introduced by the author in earlier work for binary-mode projects.