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

References

• Asawa M., Teneketzis D. Multi-armed bandits with switching penalties. IEEE Trans. Automat. Control (1996) 41:328–348Crossref, Google Scholar
• Bertsimas D., Niño-Mora J. Conservation laws, extended polymatroids and multiarmed bandit problems; a polyhedral approach to indexable systems. Math. Oper. Res. (1996) 21:257–306Link, Google Scholar
• Bradt R. N., Johnson S. M., Karlin S. On sequential designs for maximizing the sum of n observations. Ann. Math. Statist. (1956) 27:1060–1074Crossref, Google Scholar
• Chen Y.-R., Katehakis M. N. Linear programming for finite state multi-armed bandit problems. Math. Oper. Res. (1986) 11:180–183Link, Google Scholar
• Dongarra J. J., Eijkhout V. Numerical linear algebra algorithms and software. J. Comput. Appl. Math. (2000) 123:489–514Crossref, Google Scholar
• Duan J.-C., Gauthier G., Simonato J.-G., Yao D. D., Zhang H., Zhou X. Y. A Markov chain method for pricing contingent claims. Stochastic Modeling and Optimization (2003) (Springer, New York) 333–362Crossref, Google Scholar
• Gittins J. C. Bandit processes and dynamic allocation indices. J. Roy. Statist. Soc. Ser. B (1979) 41:148–177Google Scholar
• Gittins J. C., Jones D. M., Gani J., Sarkadi K., Vincze I. A dynamic allocation index for the sequential design of experiments. Progress in Statistics (European Meeting of Statisticians, Budapest, 1972) (1974) (North-Holland, Amsterdam, The Netherlands) 241–266Google Scholar
• Kallenberg L. C. M. A note on M. N. Katehakis' and Y.-R. Chen's computation of the Gittins index. Math. Oper. Res. (1986) 11:184–186Link, Google Scholar
• Katehakis M. N., Rothblum U. G. Finite state multi-armed bandit problems: Sensitive-discount, average-reward and average-overtaking optimality. Ann. Appl. Probab. (1996) 6:1024–1034Crossref, Google Scholar
• Katta A.-K., Sethuraman J. A note on bandits with a twist. SIAM J. Discrete Math. (2004) 18:110–113Crossref, Google Scholar
• Kelly F. P. Multi-armed bandits with discount factor near one: The Bernoulli case. Ann. Statist. (1981) 9:987–1001Crossref, Google Scholar
• Klimov G. P. Time-sharing service systems. Part I.. Theory Probab. Appl. (1974) 19:532–551Crossref, Google Scholar
• Niño-Mora J. Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. (2001) 33:76–98Crossref, Google Scholar
• Niño-Mora J. Dynamic allocation indices for restless projects and queueing admission control: A polyhedral approach. Math. Program. (2002) 93:361–413Crossref, Google Scholar
• Niño-Mora J. Restless bandit marginal productivity indices, diminishing returns and optimal control of make-to-order/make-to-stock M/G/1 queues. Math. Oper. Res. (2006) 31:50–84Link, Google Scholar
• Niño-Mora J. An faster index algorithm and a computational study for bandits with switching costs. INFORMS J. Comput. (2007a) . ForthcomingGoogle Scholar
• Niño-Mora J. Characterization and computation of restless bandit marginal productivity indices. SMCtools '07, Proc. 2007 Workshop on Tools for Solving Structured Markov Chains. (2007b) (ACM Press, New York) . ForthcomingCrossref, Google Scholar
• Saaty T., Gass S. Parametric objective function.Part I. J. Oper. Res. Soc. Amer. (1954) 2:316–319Link, Google Scholar
• Sonin I. The elimination algorithm for the problem of optimal stopping. Math. Methods Oper. Res. (1999) 49:111–123Crossref, Google Scholar
• Sonin I. A generalized Gittins index for a Markov chain and its recursive calculation. (2005) . Technical report, Department of Mathematics, University of North Carolina at Charlotte, Charlotte, NCGoogle Scholar
• Varaiya P. P., Walrand J. C., Buyukkoc C. Extensions of the multiarmed bandit problem: The discounted case. IEEE Trans. Automat. Control (1985) 30:426–439Crossref, Google Scholar
• Whittle P. Multi-armed bandits and the Gittins index. J. Roy. Statist. Soc. Ser. B (1980) 42:143–149Google Scholar