Optimistic Gittins Indices

References

• Agrawal R (1995) Sample mean based index policies with O(log n) regret for the multi-armed bandit problem. Adv. Appl. Probabilities 27(4):1054–1078.Crossref, Google Scholar
• Agrawal S, Goyal N (2012) Analysis of Thompson sampling for the multi-armed bandit problem. Mannor S, Srebro N, Williamson RC, eds. Proc. Conf. on Learning Theory, Edinburgh, Scotland (JMLR), 39.1–39.26. http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf.Google Scholar
• Agrawal S, Goyal N (2013) Further optimal regret bounds for Thompson sampling. Mannor S, Srebro N, Williamson RC, eds. Proc. 16th Internat. Conf. on Artificial Intelligence and Statist., Scottsdale (JMLR), 99–107. http://proceedings.mlr.press/v31/agrawal13a.pdf.Google Scholar
• Audibert JY, Bubeck S (2010) Regret bounds and minimax policies under partial monitoring. J. Machine Learning Res. 11(Oct):2785–2836.Google Scholar
• Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multi-armed bandit problem. Machine Learning 47(2-3):235–256.Crossref, Google Scholar
• Berry DA, Fristedt B (1985) Bandit Problems: Sequential Allocation of Experiments. Monographs on Statistics and Applied Probability (Chapman and Hall, London).Crossref, Google Scholar
• Bertsekas DP (2011) Dynamic Programming and Optimal Control, vol. ii, 3rd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Niño-Mora J (1996) Conservation laws, extended polymatroids and Multi-armed Bandit problems: A polyhedral approach to indexable systems. Math. Oper. Res. 21(2):257–306.Link, Google Scholar
• Besson L, Kaufmann E (2018) What doubling tricks can and can’t do for multi-armed bandits. Preprint, submitted March 19, https://arxiv.org/abs/1803.06971.Google Scholar
• Bradt RN, Johnson S, Karlin S (1956) On sequential designs for maximizing the sum of n observations. Ann. Math. Statist. 27(4):1060–1074.Crossref, Google Scholar
• Brezzi M, Lai TL (2002) Optimal learning and experimentation in bandit problems. J. Econom. Dynamic Control 27(1):87–108.Crossref, Google Scholar
• Brown DB, Smith JE (2020) Index policies and performance bounds for dynamic selection problems. Management Sci. 66(7):3029–3050.Link, Google Scholar
• Chakravorty J, Mahajan A (2013) Multi-armed bandits, Gittins index, and its calculation. Methods Appl. Statist. Clinical Trials: Planning, Anal., Inferential Methods 2:416–435.Google Scholar
• Chapelle O, Li L (2011) An empirical evaluation of Thompson sampling. Adv. Neural Inform. Processing Systems 24:2249–2257.Google Scholar
• Cover TM, Thomas JA (2012) Elements of Information Theory (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Fang LS, Lai CC (1987) Characterization and purification of biliverdin reductase from the liver of eel, Anguilla japonica. Comparative Biochemistry Physiology Part B: Comparative Biochemistry 88(4):1151–1155.Crossref, Google Scholar
• Garivier A, Cappé O (2011) The KL-UCB algorithm for bounded stochastic bandits and beyond. Kakade S, von Luxburg U, eds. Proc. 24th Annual Conf. on Learning Theory, Budapest, Hungary (JMLR), 359–376. http://proceedings.mlr.press/v19/garivier11a/garivier11a.pdfGoogle Scholar
• Gittins JC (1979) Bandit processes and dynamic allocation indices. J. Royal Statist. Soc. B 41(2):148–177.Google Scholar
• Jogdeo K, Samuels SM (1968) Monotone convergence of binomial probabilities and a generalization of Ramanujan’s equation. Ann. Math. Statist. 39(4):1191–1195.Crossref, Google Scholar
• Katehakis MN, Robbins H (1995) Sequential choice from several populations. Proc. National. Acad. Sci. USA 92(19):8584.Crossref, Google Scholar
• Katehakis MN, Veinott AF Jr (1987) The multi-armed bandit problem: Decomposition and computation. Math. Oper. Res. 12(2):262–268.Link, Google Scholar
• Katehakis MN, Rothblum UG (1996) Finite state multi-armed bandit problems: Sensitive-discount, average-reward and average-overtaking optimality. Ann. Appl. Probabilities 6(3):1024–1034.Google Scholar
• Kaufmann E (2018) On Bayesian index policies for sequential resource allocation. Ann. Statist. 46(2):842–865.Crossref, Google Scholar
• Kaufmann E, Cappé O, Garivier A (2012a) On Bayesian upper confidence bounds for bandit problems. Lawrence N, ed. 15th Internat. Conf. Artificial Intelligence Statist. (AISTATS), Palma, Canary Islands (PLMR), 592–600.Google Scholar
• Kaufmann E, Korda N, Munos R (2012b) Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis. Algorithmic Learning Theory (Springer, Berlin).Google Scholar
• Korda N, Kaufmann E, Munos R (2013) Thompson sampling for 1-dimensional exponential family bandits. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems, Lake Tahoe, California (NeurIPS).Google Scholar
• Lai TL (1987) Adaptive treatment allocation and the multi-armed bandit problem. Ann. Statist. 15(3):1091–1114.Google Scholar
• Lai TL, Robbins H (1985) Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1):4–22.Crossref, Google Scholar
• Lattimore T (2016) Regret analysis of the finite-horizon Gittins index strategy for Multi-armed Bandits. Feldman V, Rakhlin A, Shamir O, eds. Proc. Conf. on Learning Theory, New York (JMLR), 1–32. http://proceedings.mlr.press/v49/lattimore16.pdf.Google Scholar
• Maillard OA, Munos R, Stoltz G (2011) A finite-time analysis of multi-armed bandits problems with Kullback-Leibler divergences. Kakade S, von Luxburg U, eds. Proc. Conf. on Learning Theory, Budapest, Hungary (JMLR), 497–514.Google Scholar
• Niño-Mora J (2007) A (2/3)n3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov Chain. INFORMS J. Comput. 19(4):596–606.Link, Google Scholar
• Powell WB, Ryzhov IO (2012) Optimal Learning, vol. 841 (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Robbins H (1952) Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc. (Nova Scotia) 58(5):527–535.Crossref, Google Scholar
• Russo D (2021) A note on the equivalence of upper confidence bounds and gittins indices for patient agents. Oper. Res. 69(1):273–278.Link, Google Scholar
• Russo D, Van Roy B (2018) Learning to optimize via information-directed sampling. Oper. Res. 66(1):230–252.Link, Google Scholar
• Scott SL (2010) A modern Bayesian look at the multi-armed bandit. Appl. Stochastic Models Bus. Industry 26(6):639–658.Crossref, Google Scholar
• Thompson WR (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3):285–294.Crossref, Google Scholar
• Tsitsiklis JN (1994) A short proof of the Gittins index theorem. Ann. Appl. Probabilities 4(1):194–199.Google Scholar
• Varaiya P, Walrand J, Buyukkoc C (1985) Extensions of the multi-armed bandit problem: The discounted case. IEEE Trans. Automated Control 30(5):426–439.Crossref, Google Scholar
• Weber R, et al. (1992) On the Gittins index for multi-armed bandits. Ann. Appl. Probabilities 2(4):1024–1033.Crossref, Google Scholar
• Whittle P (1980) Multi-armed bandits and the Gittins index. J. Royal Statist. Soc. B. 42(2):143–149.Google Scholar
• Whittle P (1988) Restless bandits: Activity allocation in a changing world. J. Appl. Probabilities 25(1):287–298.Crossref, Google Scholar
• Yao YC, et al. (2006) Some Results on the Gittins Index for a Normal Reward Process. Time Series and Related Topics (Institute of Mathematical Statistics).Google Scholar