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

Published 1 January 1999

Vikram Krishnamurthy, J. Mickova

DOI10.1109/icassp.1999.761360

Citations12

TL;DR

A finite dimensional algorithm is presented which exactly computes the Gittins index and an application of the algorithms to tracking multiple targets with a single intelligent sensor is presented.

Abstract

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.

Keywords

Computer ScienceDecision Sciences

Journal of the Royal Statistical Society Series B (Statistical Methodology)Bandit Processes and Dynamic Allocation Indices

1,532 Citations1979John Gittins

Operations ResearchThe Optimal Control of Partially Observable Markov Processes over a Finite Horizon

1,499 Citations1973Richard D. Smallwood, Edward J. Sondik

If there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process, and an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined.

Journal of the Royal Statistical Society Series A (Statistics in Society)Multi-Armed Bandit Allocation Indices.

1,056 Citations1990J. A. Bather, John Gittins

3. Multi‐armed Bandit Allocation Indices: A meta-analyses of bandit allocation indices for the period April 1, 1991 to June 30, 1991, as well as a review of the periodical indices published in 1989, show clear trends in allocations between April and June.

Management ScienceState of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms

745 Citations1982George E. Monahan

A wide range of models in such areas as quality control, machine maintenance, internal auditing, learning, and optimal stopping are discussed within the POMDP-framework.

Annals of Operations ResearchA survey of algorithmic methods for partially observed Markov decision processes

544 Citations1991William S. Lovejoy

Several approximation methodologies are reviewed that have the potential to generate computationally feasible, high precision solutions for solving discrete-time, finite POMDPs over both finite and infinite horizons.

Journal of the Royal Statistical Society Series B (Statistical Methodology)Multi-Armed Bandits and the Gittins Index

530 Citations1980Peter Whittle

Mathematics of Operations ResearchThe Multi-Armed Bandit Problem: Decomposition and Computation

342 Citations1987Michael N. Katehakis, Arthur F. Veinott

It is shown that an approximate largest-index rule yields an approximately optimal policy for the N-project problem, and more efficient methods of computing the indices on-line and/or for sparse transition matrices in large state spaces than have been suggested heretofore.

IEEE Transactions on Automatic ControlExtensions of the multiarmed bandit problem: The discounted case

289 Citations1985Pravin Varaiya, Jean Walrand +1 more

A reformulation of the bandit problem yields the tax problem, which includes Klimov's waiting time problem, and an index rule is derived for the case where new machines arrive randomly.

Journal of the Operational Research SocietyMulti-armed Bandit Allocation Indices

124 Citations1989Peter W. Jones

The multi-armed Bandit Allocation Indices were introduced in 1989 as part of a larger effort to understand bandit allocation strategies and their applications in the context of asymmetric warfare.