{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T22:15:48Z","timestamp":1780438548117,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62102029"],"award-info":[{"award-number":["62102029"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012236","name":"Beijing Institute of Technology Research Fund Program for Young Scholars","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012236","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>\n            The best arm identification problem in multi-armed bandit model has been widely applied into many practical applications, such as spectrum sensing, online advertising, and cloud computing. Although lots of works have been devoted into this area, most of them do not consider the cost of pulling actions, i.e., a player has to pay some cost when she pulls an arm. Motivated by this, we study a ratio-based best arm identification problem, where each arm is associated with a random reward as well as a random cost. For any\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\delta\\in(0,1)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , with probability at least\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1-\\delta\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , the player aims to find the arm with the largest ratio of expected reward to expected cost using as few samplings as possible. Specifically, we consider two settings: (1) the precise setting, i.e., identifying the precise optimal one; (2) the Probably Approximate Correct (PAC) setting, which identifies the\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -optimal one. For the precise setting, we design the elimination-type algorithms and provide a fundamental lower bound which asymptotically matches the upper bound, while in the PAC setting, an UCB-type algorithm which amed\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -RCB algorithm is proposed. We show that for all algorithms, the sample complexities, i.e., the pulling times for all arms, grow logarithmically as\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{1}{\\delta}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            increases. Moreover, compared to existing works, the running of our algorithms is independent of the arm-related parameters, which is more practical. Finally, we validate our theoretical results through numerical experiments.\n          <\/jats:p>","DOI":"10.1145\/3712290","type":"journal-article","created":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T13:57:12Z","timestamp":1737727032000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Cost-aware Best Arm Identification in Stochastic Bandits"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9270-1810","authenticated-orcid":false,"given":"Zhida","family":"Qin","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1820-9499","authenticated-orcid":false,"given":"Wenhao","family":"Xue","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2229-054X","authenticated-orcid":false,"given":"Lu","family":"Zheng","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5200-1409","authenticated-orcid":false,"given":"Xiaoying","family":"Gan","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1557-7829","authenticated-orcid":false,"given":"Hongqiu","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3790-3743","authenticated-orcid":false,"given":"Haiming","family":"Jin","sequence":"additional","affiliation":[{"name":"John Hopcroft Center for Computer Science, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7796-9168","authenticated-orcid":false,"given":"Luoyi","family":"Fu","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,16]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM41043.2020.9155362"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2018.2866198"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486279"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2018.2818742"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2995920"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3583687"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737654"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2021.3085088"},{"key":"e_1_3_1_11_2","first-page":"217","volume-title":"International Conference on Machine Learning","author":"Zhou Yuan","year":"2014","unstructured":"Yuan Zhou, Xi Chen, and Jian Li. 2014. Optimal PAC multiple arm identification with applications to crowdsourcing. In International Conference on Machine Learning. PMLR, 217\u2013225."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2954310"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2023.3250269"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3507910"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.3390\/s18051445"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3544969"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/2936924.2937036"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2014.6814096"},{"key":"e_1_3_1_19_2","first-page":"1283","volume-title":"International Conference on Machine Learning","author":"Wu Yifan","year":"2015","unstructured":"Yifan Wu, Andras Gyorgy, and Csaba Szepesvari. 2015. On identifying good options under combinatorially structured feedback in finite noisy environments. In International Conference on Machine Learning. PMLR, 1283\u20131291."},{"key":"e_1_3_1_20_2","first-page":"937","volume-title":"Uncertainty in Artificial Intelligence Conference (UAI)","author":"Yu Xiaotian","year":"2018","unstructured":"Xiaotian Yu, Han Shao, Michael R. Lyu, and Irwin King. 2018. Pure exploration of multi-armed bandits with heavy-tailed payoffs. In Uncertainty in Artificial Intelligence Conference (UAI), 937\u2013946."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2019.8849327"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2022.3217131"},{"key":"e_1_3_1_23_2","first-page":"59","volume-title":"Advances in Neural Information Processing Systems","author":"Maron Oded","year":"1993","unstructured":"Oded Maron and Andrew Moore. 1993. Hoeffding races: Accelerating model selection search for classification and function approximation. In Advances in Neural Information Processing Systems, 59\u201366."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390241"},{"key":"e_1_3_1_25_2","unstructured":"Andreas Maurer and Massimiliano Pontil. 2009. Empirical Bernstein bounds and sample variance penalization. arXiv:0907.3740. Retrieved from https:\/\/arxiv.org\/abs\/0907.3740"},{"key":"e_1_3_1_26_2","first-page":"3212","volume-title":"Advances in Neural Information Processing Systems","author":"Gabillon Victor","year":"2012","unstructured":"Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. 2012. Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems. 3212\u20133220."},{"key":"e_1_3_1_27_2","first-page":"1036","volume-title":"Advances in Neural Information Processing Systems","author":"Cao Wei","year":"2015","unstructured":"Wei Cao, Jian Li, Yufei Tao, and Zhize Li. 2015. On top-k selection in multi-armed bandits and hidden bipartite graphs. In Advances in Neural Information Processing Systems, 1036\u20131044."},{"key":"e_1_3_1_28_2","first-page":"828","article-title":"Best-arm identification in linear bandits","author":"Soare Marta","year":"2014","unstructured":"Marta Soare, Alessandro Lazaric, and R\u00e9mi Munos. 2014. Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, 828\u2013826.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/648301.755490"},{"issue":"6","key":"e_1_3_1_30_2","first-page":"1079","article-title":"Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems","volume":"7","author":"Even-Dar Eyal","year":"2006","unstructured":"Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. 2006. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research 7, 6 (2006), 1079\u20131105.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_1_31_2","first-page":"511","volume-title":"International Conference on Machine Learning (ICML)","volume":"10","author":"Kalyanakrishnan Shivaram","year":"2010","unstructured":"Shivaram Kalyanakrishnan and Peter Stone. 2010. Efficient selection of multiple bandit arms: Theory and practice. In International Conference on Machine Learning (ICML), Vol. 10, 511\u2013518."},{"key":"e_1_3_1_32_2","first-page":"655","volume-title":"International Conference on Machine Learning (ICML)","volume":"12","author":"Kalyanakrishnan Shivaram","year":"2012","unstructured":"Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. 2012. PAC subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning (ICML), Vol. 12, 655\u2013662."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46128-1_35"},{"key":"e_1_3_1_34_2","first-page":"228","volume-title":"Annual Conference Computational Learning Theory","author":"Kaufmann Emilie","year":"2013","unstructured":"Emilie Kaufmann and Shivaram Kalyanakrishnan. 2013. Information complexity in bandit subset selection. In Annual Conference Computational Learning Theory. 228\u2013251."},{"key":"e_1_3_1_35_2","first-page":"1120","volume-title":"37th Conference on Uncertainty in Artificial Intelligence","volume":"161","author":"Lu Pinyan","year":"2021","unstructured":"Pinyan Lu, Chao Tao, and Xiaojin Zhang. 2021. Variance-dependent best arm identification. In 37th Conference on Uncertainty in Artificial Intelligence, Vol. 161, 1120\u20131129."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3222231"},{"key":"e_1_3_1_37_2","first-page":"2820","volume-title":"the 22nd International Conference on Artificial Intelligence and Statistics","author":"Ren Wenbo","year":"2019","unstructured":"Wenbo Ren, Jia Liu, and Ness B. Shroff. 2019. Exploring \\(k\\) out of top \\(\\rho\\) fraction of arms in stochastic bandits. In the 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2820\u20132828."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10802"},{"key":"e_1_3_1_39_2","first-page":"991","volume-title":"International Conference on Machine Learning","author":"Chaudhuri Arghya Roy","year":"2019","unstructured":"Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. 2019. PAC identification of many good arms in stochastic multi-armed bandits. In International Conference on Machine Learning. PMLR, 991\u20131000."},{"key":"e_1_3_1_40_2","first-page":"805","volume-title":"Algorithmic Learning Theory","author":"Jourdan Marc","year":"2021","unstructured":"Marc Jourdan, Mojm\u00edr Mutn\u1ef3, Johannes Kirschner, and Andreas Krause. 2021. Efficient pure exploration for combinatorial bandits with semi-bandit feedback. In Algorithmic Learning Theory. PMLR, 805\u2013849."},{"key":"e_1_3_1_41_2","first-page":"1531","volume-title":"International Conference on Machine Learning","author":"Chen Wei","year":"2020","unstructured":"Wei Chen, Yihan Du, Longbo Huang, and Haoyu Zhao. 2020. Combinatorial pure exploration for dueling bandit. In International Conference on Machine Learning. PMLR, 1531\u20131541."},{"key":"e_1_3_1_42_2","unstructured":"Nuoya Xiong and Wei Chen. 2022. Combinatorial pure exploration of causal bandits. arXiv:2206.07883. Retrieved from https:\/\/arxiv.org\/abs\/2206.07883"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27819-1_46"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.5555\/1813231.1813240"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.059"},{"key":"e_1_3_1_46_2","first-page":"41","volume-title":"Annual Conference on Learning Theory (COLT)","author":"Audibert Jean-Yves","year":"2010","unstructured":"Jean-Yves Audibert, S\u00e9bastien Bubeck, and R\u00e9mi Munos. 2010. Best arm identification in multi-armed bandits. In Annual Conference on Learning Theory (COLT), 41\u201353."},{"key":"e_1_3_1_47_2","first-page":"2222","volume-title":"Advances in Neural Information Processing Systems","author":"Gabillon Victor","year":"2011","unstructured":"Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, and S\u00e9bastien Bubeck. 2011. Multi-bandit best arm identification. In Advances in Neural Information Processing Systems, 2222\u20132230."},{"key":"e_1_3_1_48_2","first-page":"1133","volume-title":"International Conference on Machine Learning","author":"Carpentier Alexandra","year":"2015","unstructured":"Alexandra Carpentier and Michal Valko. 2015. Simple regret for infinitely many armed bandits. In International Conference on Machine Learning. PMLR, 1133\u20131141."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-13-2122-1"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2018.2885123"},{"key":"e_1_3_1_51_2","first-page":"187","volume-title":"International Conference on Machine Learning","author":"Alieva Ayya","year":"2021","unstructured":"Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. 2021. Robust pure exploration in linear bandits with limited budget. In International Conference on Machine Learning. PMLR, 187\u2013195."},{"issue":"6","key":"e_1_3_1_52_2","first-page":"2809","article-title":"Self-unaware adversarial multi-armed bandits with switching costs","volume":"34","author":"Alipour-Fanid Amir","year":"2021","unstructured":"Amir Alipour-Fanid, Monireh Dabaghchian, and Kai Zeng. 2021. Self-unaware adversarial multi-armed bandits with switching costs. IEEE Transactions on Neural Networks and Learning Systems 34, 6 (2021), 2809\u20132822.","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10881"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.2946646"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712290","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3712290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:28Z","timestamp":1750295428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,16]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3712290"],"URL":"https:\/\/doi.org\/10.1145\/3712290","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,16]]},"assertion":[{"value":"2024-01-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}