An index policy for multiarmed multimode restless bandits
Article No.: 61, Pages 1 - 6
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.
References
[1]
E. Altman. Constrained Markov Decision Processes. Chapman & Hall/CRC, Boca Raton, FL, 1999.
[2]
B. Ata and K. E. Zachariadis. Dynamic power control in a fading downlink channel subject to an energy constraint. Queueing Syst., 55:41--69, 2007.
[3]
T. B. Crabill. Optimal control of a service facility with variable exponential service times and constant arrival rate. Management Sci., 18:560--566, 1972.
[4]
J. C. Gittins and D. M. Jones. A dynamic allocation index for the sequential design of experiments. In J. Gani, K. Sarkadi, and I. Vincze, editors, Progress in Statistics (European Meeting of Statisticians, Budapest, 1972), pp. 241--266. North-Holland, Amsterdam, The Netherlands, 1974.
[5]
M. E. Mayorga, H.-S. Ahn, and J. G. Shanthikumar. Optimal control of a make-to-stock system with adjustable service rate. Probab. Engrg. Inform. Sci., 20:609--634, 2006.
[6]
J. Niño-Mora. Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab., 33:76--98, 2001.
[7]
J. Niño-Mora. Restless bandit marginal productivity indices, diminishing returns and optimal control of make-to-order/make-to-stock M/G/1 queues. Math. Oper. Res., 31:50--84, 2006.
[8]
J. Niño-Mora. Dynamic priority allocation via restless bandit marginal productivity indices. TOP, 15:161--198, 2007. Followed by six discussions by I. J. B. F. Adan and O. J. Boxma, E. Altman, O. Hernández-Lerma, R. Weber, P. Whittle, and D. D. Yao.
[9]
D. G. Pandelis and D. Teneketzis. On the optimality of the Gittins index rule for multi-armed bandits with multiple plays. Math. Methods Oper. Res., 50:449--461, 1999.
[10]
H. Sabeti. Optimal selection of service rates in queueing with different cost. J. Operations Res. Soc. Japan, 16:15--35, 1973.
[11]
R. Serfozo. Optimal control of random walks, birth and death processes, and queues. Adv. in Appl. Probab., 13:61--83, 1981.
[12]
R. Weber. Comments on: "Dynamic priority allocation via restless bandit marginal productivity indices" {TOP 15:161--198, 2007} by J. Niño-Mora. TOP, 15:211--216, 2007.
[13]
P. Whittle. Restless bandits: Activity allocation in a changing world. In J. Gani, editor, A Celebration of Applied Probability, spec. vol. 25A of J. Appl. Probab., pp. 287--298. Applied Probability Trust, Sheffield, UK, 1988.
Index Terms
- An index policy for multiarmed multimode restless bandits
Recommendations
Computing an index policy for multiarmed bandits with deadlines
ValueTools '08: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and ToolsThis paper introduces the multiarmed bandit problem with deadlines, which concerns the dynamic selection of a live project to engage out of a portfolio of Markovian bandit projects expiring after given deadlines, to maximize the expected total ...
Fairness of Exposure in Online Restless Multi-armed Bandits
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent SystemsRestless multi-armed bandits (RMABs) generalize the multi-armed bandits where each arm exhibits Markovian behavior and transitions according to their transition dynamics. Solutions to RMAB exist for both offline and online cases. However, they do not ...
Characterization and computation of restless bandit marginal productivity indices
ValueTools '07: Proceedings of the 2nd international conference on Performance evaluation methodologies and toolsThe restless bandit problem furnishes a powerful modeling paradigm for settings involving the optimal dynamic priority allocation to multiple stochatic projects, given as binary-action (active/passive) Markov decision processes (MDPs). Though generally ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Create-Net
Publisher
ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)
Brussels, Belgium
Publication History
Published: 20 October 2008
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 106Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in