Top-Two Thompson Sampling for Contextual Selection Problems

References

• [1] Agrawal S, Goyal N (2017) Near-optimal regret bounds for Thompson sampling. J. ACM 64(5):1–24.Crossref, Google Scholar
• [2] Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learn. 47:235–256.Crossref, Google Scholar
• [3] Avci H, Nelson BL, Wächter A (2021) Getting to “rate-optimal” in ranking & selection. Proc. 2021 Winter Simulation Conf. (WSC), vol. 1 (IEEE, Piscataway, NJ), 1–12.Google Scholar
• [4] Bubeck S, Wang T, Viswanathan N (2013) Multiple identifications in multi-armed bandits. Proc. 30th Internat. Conf. Machine Learn. (ICML), vol. 28 (PMLR), 258–265.Google Scholar
• [5] Cakmak S, Zhou E, Gao S (2021) Contextual ranking and selection with Gaussian processes. Proc. 2021 Winter Simulation Conf. (WSC), vol. 1 (IEEE, Piscataway, NJ), 1–12.Google Scholar
• [6] Chen CH (1996) A lower bound for the correct subset-selection probability and its application to discrete-event system simulations. IEEE Trans. Automatic Control 41(8):1227–1231.Crossref, Google Scholar
• [7] Chen Y, Ryzhov IO (2019) Complete expected improvement converges to an optimal budget allocation. Adv. Appl. Probab. 51(1):209–235.Crossref, Google Scholar
• [8] Chen Y, Ryzhov IO (2023) Balancing optimal large deviations in sequential selection. Management Sci. 69(6):3457–3473.Link, Google Scholar
• [9] Chen CH, He D, Fu M, Lee LH (2008) Efficient simulation budget allocation for selecting an optimal subset. INFORMS J. Comput. 20(4):579–595.Link, Google Scholar
• [10] Chen CH, Lin J, Yücesan E, Chick SE (2000) Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynam. Systems 10:251–270.Crossref, Google Scholar
• [11] Chick SE, Inoue K (2001) New two-stage and sequential procedures for selecting the best simulated system. Oper. Res. 49(5):732–743.Link, Google Scholar
• [12] Dembo A, Zeitouni O (1992) Large Deviations Techniques and Applications (Jones and Bartlett, Burlington, MA).Google Scholar
• [13] Ding L, Hong LJ, Shen H, Zhang X (2022) Knowledge gradient for selection with covariates: Consistency and computation. Naval Res. Logist. 69(3):496–507.Crossref, Google Scholar
• [14] Du J, Gao S, Chen CH (2024) A contextual ranking and selection method for personalized medicine. Manufacturing Service Oper. Management 26(1):167–181.Link, Google Scholar
• [15] Frazier PI, Powell WB, Dayanik S (2008) A knowledge-gradient policy for sequential information collection. SIAM J. Control Optim. 47(5):2410–2439.Crossref, Google Scholar
• [16] Gabillon V, Ghavamzadeh M, Lazaric A (2012) Best arm identification: A unified approach to fixed budget and fixed confidence. Adv. Neural Inform. Processing Systems 25:3212–3220.Google Scholar
• [17] Gao S, Chen W (2016) A new budget allocation framework for selecting top simulated designs. IIE Trans. 48(9):855–863.Crossref, Google Scholar
• [18] Gao S, Du J, Chen CH (2019) Selecting the optimal system design under covariates. Proc. 15th Internat. Conf. Automation Sci. Engrg. (CASE) (IEEE, Piscataway, NJ), 547–552.Google Scholar
• [19] Glynn P, Juneja S (2004) A large deviations perspective on ordinal optimization. Proc. 2004 Winter Simulation Conf. (WSC), vol. 1 (IEEE, Piscataway, NJ), 577–585.Google Scholar
• [20] Hong LJ, Fan W, Luo J (2021) Review on ranking and selection: A new perspective. Frontiers Engrg. Management 8(3):321–343.Crossref, Google Scholar
• [21] Hu R, Ludkovski M (2017) Sequential design for ranking response surfaces. SIAM/ASA J. Uncertainty Quant. 5(1):212–239.Crossref, Google Scholar
• [22] Jourdan M, Degenne R, Baudry D, de Heide R, Kaufmann E (2022) Top two algorithms revisited. Adv. Neural Inform. Processing Systems 35:26791–26803.Crossref, Google Scholar
• [23] Kalyanakrishnan S, Tewari A, Auer P, Stone P (2012) PAC subset selection in stochastic multi-armed bandits. ICML’12: Proc. 29th Internat. Conf. Machine Learn. (ICML), vol. 12 (Omnipress, Madison, WI), 227–234.Google Scholar
• [24] Kapur KC, Lamberson LR (1977) Reliability in Engineering Design (John Wiley & Sons, New York).Google Scholar
• [25] Kato M, Ariu K, Imaizumi M, Uehara M, Nomura M, Qin C (2022) Best arm identification with contextual information under a small gap. Preprint, submitted September 15, https://arxiv.org/abs/2209.07330.Google Scholar
• [26] Kaufmann E, Kalyanakrishnan S (2013) Information complexity in bandit subset selection. Proc. 26th Conf. Learn. Theory (COLT) (PMLR), 228–251.Google Scholar
• [27] Kaufmann E, Korda N, Munos R (2012) Thompson sampling: An asymptotically optimal finite-time analysis. Bshouty NH, Stoltz G, Vayatis N, Zeugmann T, eds. Algorithmic Learn. Theory. ALT 2012, Lecture Notes in Computer Science, vol. 7568 (Springer, Berlin, Heidelberg), 199–213.Google Scholar
• [28] Li H, Lam H, Peng Y (2024) Efficient learning for clustering and optimizing context-dependent designs. Oper. Res. 72(2):617–638.Link, Google Scholar
• [29] Li X, Zhang X, Zheng Z (2018) Data-driven ranking and selection: High-dimensional covariates and general dependence. Proc. 2018 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 1933–1944.Google Scholar
• [30] Miao S, Chao X (2022) Online personalized assortment optimization with high-dimensional customer contextual data. Manufacturing Service Oper. Management 24(5):2741–2760.Link, Google Scholar
• [31] Neu G, Olkhovskaya J (2020) Efficient and robust algorithms for adversarial linear contextual bandits. Proc. 33rd Conf. Learn. Theory, vol. 125 (PMLR), 3049–3068.Google Scholar
• [32] Pasupathy R, Szechtman R, Yücesan E (2010) Selecting small quantiles. Proc. 2010 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 2762–2770.Google Scholar
• [33] Pearce M, Branke J (2018) Continuous multi-task Bayesian optimisation with correlation. Eur. J. Oper. Res. 270(3):1074–1085.Crossref, Google Scholar
• [34] Peng Y, Zhang G (2022) Thompson sampling meets ranking and selection. Proc. 2022 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 3075–3086.Google Scholar
• [35] Peng Y, Chong EK, Chen CH, Fu MC (2018) Ranking and selection as stochastic control. IEEE Trans. Automatic Control 63(8):2359–2373.Crossref, Google Scholar
• [36] Peng Y, Chen CH, Fu MC, Hu JQ (2013) Efficient simulation resource sharing and allocation for selecting the best. IEEE Trans. Automatic Control 58(4):1017–1023.Crossref, Google Scholar
• [37] Peng Y, Chen CH, Fu MC, Hu JQ (2017) Gradient-based myopic allocation policy: An efficient sampling procedure in a low-confidence scenario. IEEE Trans. Automatic Control 63(9):3091–3097.Crossref, Google Scholar
• [38] Réda C, Kaufmann E, Delahaye-Duriez A (2021) Top-m identification for linear bandits. Proc. 24th Internat. Conf. Artificial Intelligence Statist. (AISTATS) (PMLR), 1108–1116.Google Scholar
• [39] Russo D (2020) Simple Bayesian algorithms for best-arm identification. Oper. Res. (6):1625–1647.Link, Google Scholar
• [40] Russo DJ, Van Roy B, Kazerouni A, Osband I, Wen Z (2018) A tutorial on Thompson sampling. Foundations Trends Machine Learn. 11(1):1–96.Crossref, Google Scholar
• [41] Ryzhov IO (2016) On the convergence rates of expected improvement methods. Oper. Res. 64(6):1515–1528.Link, Google Scholar
• [42] Shang X, Heide R, Menard P, Kaufmann E, Valko M (2020) Fixed-confidence guarantees for Bayesian best-arm identification. Proc. 23rd Internat. Conf. Artificial Intelligence Statist. (AISTATS) (PMLR), 1823–1832.Google Scholar
• [43] Shen H, Hong LJ, Zhang X (2021) Ranking and selection with covariates for personalized decision making. INFORMS J. Comput. 33(4):1500–1519.Abstract, Google Scholar
• [44] Shi X, Peng Y, Zhang G (2024) Top-two Thompson sampling for selecting context-dependent best designs. Proc. 2024 Winter Simulation Conf. (IEEE, Piscataway, NJ), 3400–3411.Google Scholar
• [45] Soare M, Lazaric A, Munos R (2014) Best-arm identification in linear bandits. Adv. Neural Inform. Processing Systems 27:828–836.Google Scholar
• [46] Syrgkanis V, Luo H, Krishnamurthy A, Schapire RE (2016) Improved regret bounds for oracle-based adversarial contextual bandits. Adv. Neural Inform. Processing Systems 29:3143–3151.Google Scholar
• [47] Thompson WR (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
• [48] van der Vaart AW (1998) Asymptotic Statistics, Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [49] Williams D (1991) Probability with Martingales (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [50] Woerndl W, Schueller C, Wojtech R (2007) A hybrid recommender system for context-aware recommendations of mobile applications. Proc. 23rd Internat. Conf. Data Engrg. (ICDE) (IEEE, Piscataway, NJ), 871–878.Google Scholar
• [51] You W, Qin C, Wang Z, Yang S (2023) Information-directed selection for top-two algorithms. Proc. 36th Annual Conf. Learn. Theory (PMLR), 2850–2851.Google Scholar
• [52] Zhang G, Li H, Peng Y (2020) Sequential sampling for a ranking and selection problem with exponential sampling distributions. Proc. 2020 Winter Simulation Conf. (IEEE, Piscataway, NJ), 2984–2995.Google Scholar
• [53] Zhang G, Chen S, Huang K, Peng Y (2025) Efficient learning for selecting top-m context-dependent designs. IEEE Trans. Automation Sci. Engrg. 22:3210–3225.Crossref, Google Scholar
• [54] Zhang G, Chen B, Jia QS, Peng Y (2023a) Efficient sampling policy for selecting a subset with the best. IEEE Trans. Automatic Control 68(8):4904–4911.Crossref, Google Scholar
• [55] Zhang G, Peng Y, Zhang J, Zhou E (2023b) Asymptotically optimal sampling policy for selecting top-m alternatives. INFORMS J. Comput. 35(6):1261–1285.Link, Google Scholar
• [56] Zhang S, Lee LH, Chew EP, Xu J, Chen CH (2015) A simulation budget allocation procedure for enhancing the efficiency of optimal subset selection. IEEE Trans. Automatic Control 61(1):62–75.Crossref, Google Scholar