This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Niño-Mora, J. Search for Related Content

A (2/3)n³ Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain

Department of Statistics, Universidad Carlos III de Madrid, C/Madrid 126, 28903 Getafe, Madrid, Spain
jnimora{at}alum.mit.edu

This paper presents a new fast-pivoting algorithm that computes the n Gittins index values of an n-state bandit—in the discounted and undiscounted cases—by performing (2/3)n³ + O(n²) arithmetic operations, thus attaining better complexity than previous algorithms and matching that of solving a corresponding linear-equation system by Gaussian elimination. The algorithm further applies to the problem of optimal stopping of a Markov chain, for which a novel Gittins-index solution approach is introduced. The algorithm draws on Gittins and Jones' (1974) index definition via calibration, on Kallenberg's (1986) proposal of using parametric linear programming, on Dantzig's simplex method, on the Varaiya et al. (1985) algorithm, and on the author's earlier work. This paper elucidates the structure of parametric simplex tableaux. Special structure is exploited to reduce the computational effort of pivot steps, decreasing the operation count by a factor of three relative to conventional pivoting, and by a factor of 3/2 relative to recent state-elimination algorithms. A computational study demonstrates significant time savings against alternative algorithms.

Key words: dynamic programming; Markov; finite state; Gittins index; bandits; optimal stopping; Markov chain; simplex method; analysis of algorithms; computational complexity
History: received November 2005; revised August 2006; accepted August 2006.

This article has been cited by other articles:

				K. D. Glazebrook and R. Minty A Generalized Gittins Index for a Class of Multiarmed Bandits with General Resource Requirements Mathematics of Operations Research, February 1, 2009; 34(1): 26 - 44. [Abstract] [PDF]

				J. Nino-Mora A Faster Index Algorithm and a Computational Study for Bandits with Switching Costs INFORMS Journal on Computing, January 1, 2008; 20(2): 255 - 269. [Abstract] [PDF]