Finite dimensional algorithms for the hidden Markov model multi-armed bandit problem

TitleFinite dimensional algorithms for the hidden Markov model multi-armed bandit problem
Publication TypeConference Paper
Year of Publication1999
AuthorsKrishnamurthy, V., and J. Mickova
Conference NameAcoustics, Speech, and Signal Processing, 1999. ICASSP '99. Proceedings., 1999 IEEE International Conference on
Pagination2865 -2868 vol.5
Keywordsbroadband networks, finite dimensional algorithms, finite dimensional optimal solution, Gittins index, hidden Markov model, hidden Markov models, HMM, intelligent sensor, intelligent sensors, manufacture, manufacturing systems, multi-armed bandit problem, multiple targets tracking, robotics, robots, scheduling, suboptimal algorithms, target tracking, telecommunication traffic, traffic scheduling

The multi-arm bandit problem is widely used in scheduling of traffic in broadband networks, manufacturing systems and robotics. This paper presents a finite dimensional optimal solution to the multi-arm bandit problem for hidden Markov models. The key to solving any multi-arm bandit problem is to compute the Gittins (1979, 1989) index. In this paper a finite dimensional algorithm is presented which exactly computes the Gittins index. Suboptimal algorithms for computing the Gittins index are also presented and experimentally shown to perform almost as well as the optimal method. Finally an application of the algorithms to tracking multiple targets with a single intelligent sensor is presented


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia