Open bandit processes and optimal scheduling of queueing networks
- 1 June 1988
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 20 (2) , 447-472
- https://doi.org/10.2307/1427399
Abstract
Asymptotic approximations are developed herein for the optimal policies in discounted multi-armed bandit problems in which new projects are continually appearing, commonly known as ‘open bandit problems’ or ‘arm-acquiring bandits’. It is shown that under certain stability assumptions the open bandit problem is asymptotically equivalent to a closed bandit problem in which there is no arrival of new projects, as the discount factor approaches 1. Applications of these results to optimal scheduling of queueing networks are given. In particular, Klimov&s priority indices for scheduling queueing networks are shown to be limits of the Gittins indices for the associated closed bandit problem, and extensions of Klimov&s results to preemptive policies and to unstable queueing systems are given.Keywords
This publication has 10 references indexed in Scilit:
- Discrete multi-armed bandits and multi-parameter processesProbability Theory and Related Fields, 1986
- Extensions of the multiarmed bandit problem: The discounted caseIEEE Transactions on Automatic Control, 1985
- Arm-Acquiring BanditsThe Annals of Probability, 1981
- Multi-Armed Bandits and the Gittins IndexJournal of the Royal Statistical Society Series B: Statistical Methodology, 1980
- Time-Sharing Service Systems. IITheory of Probability and Its Applications, 1979
- Bandit Processes and Dynamic Allocation IndicesJournal of the Royal Statistical Society Series B: Statistical Methodology, 1979
- On Bayesian models in stochastic schedulingJournal of Applied Probability, 1977
- Optimal Control of Single-Server Queuing Networks and Multi-Class M/G/1 Queues with FeedbackOperations Research, 1977
- Time-Sharing Service Systems. ITheory of Probability and Its Applications, 1975
- Linear Statistical Inference and its ApplicationsPublished by Wiley ,1973