{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T10:37:10Z","timestamp":1774003030876,"version":"3.50.1"},"reference-count":64,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>Although experimental design often focuses on selecting the single best alternative from a finite set, many pure-exploration problems pursue richer goals. Given a specific goal, adaptive experimentation aims to achieve it by strategically allocating sampling effort, with the underlying sample complexity characterized by a maximin optimization problem. In \"Dual-Directed Algorithm Design for Efficient Pure Exploration,\" Qin and You introduce a unified dual-directed framework for efficiently solving general pure-exploration problems, yielding a unified algorithm design principle that extends the top-two approach beyond best-arm identification. Their theoretical analysis proves asymptotic optimality for classical problems, such as Gaussian best-arm identification, thresholding bandits, and epsilon-best-arm identification. Extensive numerical experiments confirm these theoretical insights, showcasing significant improvements over existing methods. This dual-directed framework offers researchers and practitioners a powerful and versatile tool to navigate uncertainty and optimize exploration strategies effectively.<\/jats:p>","DOI":"10.1287\/opre.2023.0590","type":"journal-article","created":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T16:29:58Z","timestamp":1752596998000},"page":"1104-1125","source":"Crossref","is-referenced-by-count":0,"title":["Dual-Directed Algorithm Design for Efficient Pure Exploration"],"prefix":"10.1287","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4600-6147","authenticated-orcid":false,"given":"Chao","family":"Qin","sequence":"first","affiliation":[{"name":"Stanford Graduate School of Business, Stanford University, Stanford, California 94305"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0844-4194","authenticated-orcid":false,"given":"Wei","family":"You","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","unstructured":"Agrawal S, Juneja S, Glynn P (2020) Optimal \u03b4-correct best-arm selection for heavy-tailed distributions. Kontorovich A, Neu G, eds.\n                      Proc. 31st Internat. Conf. Algorithmic Learn. Theory,\n                      vol. 117 (PMLR, Cambridge, MA), 61\u2013110."},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Al Marjani A, Kocak T, Garivier A (2022) On the complexity of all \u03b5-best arms identification. Amini M-R, Canu S, Fischer A, Guns T, Novak PK, Tsoumakas G, eds.\n                      Proc. Joint Eur. Conf. Machine Learn. Knowledge Discovery Databases\n                      (Springer, Switzerland), 317\u2013332.","DOI":"10.1007\/978-3-031-26412-2_20"},{"key":"B3","volume-title":"Calculus","author":"Apostol TM","year":"1969"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1145\/3618299"},{"key":"B5","unstructured":"Bandyopadhyay A, Juneja SK, Agrawal S (2024) Optimal top two method for best arm identification and fluid analysis. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds.\n                      Proc. 38th Ann. Conf. Neural Inform. Processing Systems\n                      (Curran Associates Inc., Red Hook, NY)."},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728845"},{"key":"B7","unstructured":"Bubeck S, Wang T, Viswanathan N (2013) Multiple identifications in multi-armed bandits.\n                      Proc. Internat. Conf. Machine Learn.\n                      (JMLR, Cambridge, MA), 258\u2013265."},{"key":"B8","unstructured":"Chapelle O, Li L (2011) An empirical evaluation of Thompson sampling.\n                      Proc. Adv. Neural Inform. Processing Systems\n                      , vol. 24 (Curran Associates Inc., Red Hook, NY)."},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2022.4527"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0268"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008349927281"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706205"},{"key":"B13","volume-title":"Elements of Information Theory","author":"Cover TM","year":"2006"},{"key":"B14","author":"Degenne R","year":"2019","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B15","doi-asserted-by":"crossref","unstructured":"Eckman DJ, Henderson SG (2018) Guarantees on the probability of good selection.\n                      Proc. Winter Simulation Conf.\n                      (IEEE, Piscataway, NJ), 351\u2013365.","DOI":"10.1109\/WSC.2018.8632345"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1530"},{"key":"B17","unstructured":"Fan W, Hong LJ, Jiang G, Luo J (2024) Review of large-scale simulation optimization. Preprint, submitted March 23, https:\/\/arxiv.org\/abs\/2403.15669."},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1755"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1137\/070693424"},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Fu MC, Henderson SG (2017) History of seeking better solutions, aka simulation optimization.\n                      Proc. Winter Simulation Conf.\n                      (IEEE, Piscataway, NJ), 131\u2013157.","DOI":"10.1109\/WSC.2017.8247787"},{"key":"B21","doi-asserted-by":"crossref","unstructured":"Gao S, Chen W (2015) A note on the subset selection for simulation optimization.\n                      Proc. Winter Simulation Conf.\n                      (IEEE, Piscataway, NJ), 3768\u20133776.","DOI":"10.1109\/WSC.2015.7408534"},{"key":"B22","first-page":"998","volume-title":"Proc. Conf. Learn. Theory","author":"Garivier A","year":"2016"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1080\/07474946.2021.1847965"},{"key":"B24","unstructured":"Glynn P, Juneja S (2004) A large deviations perspective on ordinal optimization.\n                      Proc. Winter Simulation Conf\n                      . (ACM, New York)."},{"key":"B25","unstructured":"Glynn P, Juneja S (2018) Selecting the best system and multi-armed bandits. Preprint, submitted July 16, https:\/\/arxiv.org\/abs\/1507.04564."},{"key":"B26","unstructured":"Graepel T, Candela JQ, Borchert T, Herbrich R (2010) Web-scale Bayesian click-through rate prediction for sponsored search advertising in Microsoft\u2019s Bing search engine.\n                      Proc. 27th Internat. Conf. Machine Learn.\n                      (Omnipress, Madison, WI)."},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s42524-021-0152-6"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.1221"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-307502-4.50010-6"},{"key":"B30","unstructured":"Jourdan M, Degenne R, Kaufmann E (2023a) Dealing with unknown variances in best-arm identification.\n                      Proc. Internat. Conf. Algorithmic Learn. Theory\n                      (JMLR, Cambridge, MA), 776\u2013849."},{"key":"B31","doi-asserted-by":"crossref","unstructured":"Jourdan M, Degenne R, Kaufmann E (2023b) An \u03b5-best-arm identification algorithm for fixed-confidence and beyond.\n                      Proc. 37th Conf. Neural Inform. Processing Systems\n                      (Curran Associates Inc., Red Hook, NY).","DOI":"10.52202\/075280-0727"},{"key":"B32","first-page":"26791","volume":"35","author":"Jourdan M","year":"2022","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B33","unstructured":"Kalyanakrishnan S, Tewari A, Auer P, Stone P (2012) PAC subset selection in stochastic multi-armed bandits.\n                      Proc. 29th Internat. Conf. Machine Learn.\n                      , vol. 12 (Omnipress, Madison, WI), 655\u2013662."},{"key":"B34","unstructured":"Kato M, Ariu K (2024) The role of contextual information in best arm identification. Preprint, submitted June 26, https:\/\/arxiv.org\/abs\/2106.14077."},{"key":"B35","first-page":"228","volume-title":"Proc. Conf. Learn. Theory","author":"Kaufmann E","year":"2013"},{"issue":"1","key":"B36","first-page":"11140","volume":"22","author":"Kaufmann E","year":"2021","journal-title":"J. Machine Learn. Res."},{"key":"B37","author":"Kaufmann E","year":"2018","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1145\/502109.502111"},{"key":"B39","unstructured":"Komiyama J (2024) Suboptimal performance of the bayes optimal algorithm in frequentist best arm identification. Preprint, submitted February 10, https:\/\/arxiv.org\/abs\/2202.05193."},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1080\/07474946.2012.719433"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2023.00694"},{"key":"B42","unstructured":"Locatelli A, Gutzeit M, Carpentier A (2016) An optimal algorithm for the thresholding bandit problem.\n                      Proc. Internat. Conf. Machine Learn.\n                      (JMLR, Cambridge, MA), 1690\u20131698."},{"key":"B43","first-page":"20707","volume":"33","author":"Mason B","year":"2020","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B44","unstructured":"M\u00e9nard P (2019) Gradient ascent for active exploration in bandit problems. Preprint, submitted May 20, https:\/\/arxiv.org\/abs\/1905.08165."},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.41.12.1935"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177697299"},{"key":"B47","doi-asserted-by":"crossref","unstructured":"Pryzant R, Iter D, Li J, Lee YT, Zhu C, Zeng M (2023) Automatic prompt optimization with \u201cgradient descent\u201d and beam search.\n                      Proc. Conf. Empirical Methods Natural Language Processing\n                      (Association for Computational Linguistics, Stroudsburg, PA).","DOI":"10.18653\/v1\/2023.emnlp-main.494"},{"key":"B48","unstructured":"Qiao G, Tewari A (2024) An asymptotically optimal algorithm for the convex hull membership problem. Preprint, submitted February 3, https:\/\/arxiv.org\/abs\/2302.02033."},{"key":"B49","author":"Qin C","year":"2017","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1911"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1561\/2200000070"},{"key":"B52","unstructured":"Shang X, Kaufmann E, Valko M (2019) A simple dynamic bandit algorithm for hyper-parameter tuning.\n                      Proc. 6th ICML Workshop Automated Machine Learn\n                      . (ICML, San Diego, CA)."},{"key":"B53","unstructured":"Shang X, de Heide R, M\u00e9nard P, Kaufmann E, Valko M (2020) Fixed-confidence guarantees for Bayesian best-arm identification.\n                      Proc. Internat. Conf. Artificial Intelligence Statist.\n                      (JMLR, Cambridge, MA), 1823\u20131832."},{"key":"B54","author":"Simchi-Levi D","year":"2024","journal-title":"Management Sci."},{"key":"B55","first-page":"1794","volume-title":"Proc. Conf. Learn. Theory","author":"Simchowitz M","year":"2017"},{"key":"B56","author":"Tirinzoni A","year":"2022","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B57","author":"Wang PA","year":"2021","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2023.2447"},{"key":"B59","unstructured":"Wu D, Zhou E (2018a) Analyzing and provably improving fixed budget ranking and selection algorithms. Preprint, submitted November 26, https:\/\/arxiv.org\/abs\/1811.12183."},{"key":"B60","doi-asserted-by":"crossref","unstructured":"Wu D, Zhou E (2018b) Provably improving the optimal computing budget allocation algorithm.\n                      Proc. Winter Simulation Conf.\n                      (IEEE, Piscataway, NJ), 1921\u20131932.","DOI":"10.1109\/WSC.2018.8632199"},{"key":"B61","unstructured":"You W, Qin C, Wang Z, Yang S (2023) Information-directed selection for top-two algorithms.\n                      Proc. 36th Annual Conf. Learn. Theory\n                      (JMLR, Cambridge, MA), 2850\u20132851."},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2021.0333"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2065"},{"key":"B64","author":"Zhou X","year":"2024","journal-title":"Trans. Machine Learn. Res. (MIT Press, Cambridge, MA)."}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2023.0590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:12:20Z","timestamp":1773994340000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2023.0590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/opre.2023.0590"],"URL":"https:\/\/doi.org\/10.1287\/opre.2023.0590","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}