Thompson Sampling with Information Relaxation Penalties

References

• Agrawal S, Goyal N (2017) Near-optimal regret bounds for Thompson sampling. J. ACM 64:1–24.Google Scholar
• Berry DA , Fristedt B (1985) Bandit Problems: Sequential Allocation of Experiments , Monographs on Statistics and Applied Probability (Chapman & Hall, London).Crossref, Google Scholar
• Bradt RN , Johnson SM , Karlin S (1956) On sequential designs for maximizing the sum of n observations. Ann. Math. Statist. 27(4):1060–1074.Crossref, Google Scholar
• Brown DB , Haugh MB (2017) Information relaxation bounds for infinite horizon Markov decision processes. Oper. Res. 65(5):1355–1379.Link, 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
• Brown DB , Smith JE , Sun P (2010) Information relaxations and duality in stochastic dynamic programs. Oper. Res. 58(4):785–801.Link, Google Scholar
• Bubeck S , Liu C-Y (2013) Prior-free and prior-dependent regret bounds for Thompson sampling. Burges CJ, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 26 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Davis MHA , Karatzas I (1994) A deterministic approach to optimal stopping. Kelly FP , ed. Probability, Statistics, and Optimisation (John Wiley & Sons Ltd., Hoboken, NJ), 455–466.Google Scholar
• Desai VV , Farias VF , Moallemi CC (2012a) Bounds for Markov decision processes. Lewis FL , Liu D , eds. Reinforcement Learning and Approximate Dynamic Programming for Feedback Control (John Wiley & Sons, Inc., Hoboken, NJ), 452–473.Crossref, Google Scholar
• Desai VV , Farias VF , Moallemi CC (2012b) Pathwise optimization for optimal stopping problems. Management Sci. 58(12):2292–2308.Link, Google Scholar
• Ding W , Qin T , Zhang X-D , Liu T-Y (2013) Multi-armed bandit with budget constraint and variable costs. Proc. 27th AAAI Conf. Artificial Intelligence, vol. 27, no. 1 (AAAI Press, Palo Alto, CA), 232–238.Google Scholar
• Farias VF, Gutin E (2022) Optimistic Gittins indices. Oper. Res. 70(6):3432–3456.Google Scholar
• Gittins JC (1979) Bandit processes and dynamic allocation indices. J. Royal Statist. Soc. B 41(2):148–177.Crossref, Google Scholar
• Gutiérrez-Peña E , Smith AFM (1995) Conjugate parameterizations for natural exponential families. J. Amer. Statist. Assoc. 90(432):1347–1356.Google Scholar
• Haugh MB , Kogan L (2004) Pricing American options: A duality approach. Oper. Res. 52(2):258–270.Link, Google Scholar
• Haugh MB , Lacedelli OR (2019) Information relaxation bounds for partially observed Markov decision processes. IEEE Trans. Automatic Control 65(8):3256–3271.Crossref, Google Scholar
• Haugh MB , Lim AEB (2012) Linear-quadratic control and information relaxations. Oper. Res. Lett. 40(6):521–528.Crossref, Google Scholar
• Haugh MB , Wang C (2014) Dynamic portfolio execution and information relaxations. SIAM J. Financial Math. 5(1):316–359.Crossref, Google Scholar
• Kaufmann E , Cappé O , Garivier A (2012a) On Bayesian upper confidence bounds for bandit problems. Lawrence ND, Girolami M, eds. Proc. 15th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 22 (PMLR, New York), 592–600.Google Scholar
• Kaufmann E , Korda N , Munos R (2012b) Thompson sampling: An asymptotically optimal finite-time analysis. Bshouty NH, Stoltz G, Vayatis N, Zeugmann T, eds. Proc. 23rd Internat. Conf. Algorithmic Learning Theory (Springer, Berlin, Heidelberg), 199–213.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. 29th Annu. Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 49 (PMLR, New York), 1214–1245.Google Scholar
• Min S, Maglaras C, Moallemi CC (2019) Thompson sampling with information relaxation penalties. Wallach H, Larochelle H, Beygelzimer A, Alché-Buc FD, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Niño-Mora J (2011) Computing a classic index for finite-horizon bandits. INFORMS J. Comput. 23(2):254–267.Link, Google Scholar
• Rockafellar RT , Wets RJ-B (1991) Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119–147.Link, Google Scholar
• Rogers LCG (2002) Monte Carlo valuation of American options. Math. Finance 12(3):271–286.Crossref, Google Scholar
• Russo D , Van Roy B (2014) Learning to optimize via posterior sampling. Math. Oper. Res. 39(4):1221–1243.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
• Russo D, Van Roy B (2022) Satisficing in time-sensitive bandit learning. Math. Oper. Res. 47(4):2815–2839.Google Scholar
• Thompson W (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3–4):285–294.Crossref, Google Scholar