{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:48:54Z","timestamp":1764175734110,"version":"3.33.0"},"reference-count":30,"publisher":"MIT Press","issue":"2","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,1,21]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We study the real-valued combinatorial pure exploration problem in the stochastic multi-armed bandit (R-CPE-MAB). We study the case where the size of the action set is polynomial with respect to the number of arms. In such a case, the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We introduce the combinatorial gap-based exploration (CombGapE) algorithm, whose sample complexity upper-bound-matches the lower bound up to a problem-dependent constant factor. We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world data sets.<\/jats:p>","DOI":"10.1162\/neco_a_01728","type":"journal-article","created":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T21:23:42Z","timestamp":1733174622000},"page":"294-310","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":1,"title":["A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of the Multi-Armed Bandit"],"prefix":"10.1162","volume":"37","author":[{"given":"Shintaro","family":"Nakamura","sequence":"first","affiliation":[{"name":"The University of Tokyo, Bunkyo-ku, Tokyo 113-8654, Japan"},{"name":"RIKEN AIP, Chuo-ku, Tokyo 103-0027, Japan nakamurashintaro@g.ecc.u-tokyo.ac.jp"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masashi","family":"Sugiyama","sequence":"additional","affiliation":[{"name":"RIKEN AIP, Chuo-ku, Tokyo 103-0027, Japan"},{"name":"The University of Tokyo, Bunkyo-ku, Tokyo 113-8654, Japan sugi@k.u-tokyo.ac.jp"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2025,1,21]]},"reference":[{"key":"2025012818241636300_bib1","first-page":"41","article-title":"Best arm identification in multi-armed bandits","volume-title":"Proceedings of the 23rd Conference on Learning Theory","author":"Audibert","year":"2010"},{"key":"2025012818241636300_bib2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1013689704352","article-title":"Finite-time analysis of the multi- armed bandit problem","volume":"47","author":"Auer","year":"2002","journal-title":"Machine Learning"},{"issue":"1","key":"2025012818241636300_bib3","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539701398375","article-title":"The nonstochastic multiarmed bandit problem","volume":"32","author":"Auer","year":"2002","journal-title":"SIAM Journal on Computing"},{"key":"2025012818241636300_bib4","doi-asserted-by":"crossref","DOI":"10.1561\/2200000024","article-title":"Regret analysis of stochastic and nonstochastic multi-armed bandit problems","author":"Bubeck","year":"2012","journal-title":"Foundation and Trends in Machine Lending."},{"key":"2025012818241636300_bib5","first-page":"647","article-title":"Pure exploration of multi-armed bandit under matroid constraints","volume-title":"Proceedings of the 29th Conference on Learning Theory","author":"Chen","year":"2016"},{"key":"2025012818241636300_bib6","first-page":"482","article-title":"Nearly optimal sampling algorithms for combinatorial pure exploration","volume-title":"Proceedings of the 2017 Conference on Learning Theory","author":"Chen","year":"2017"},{"key":"2025012818241636300_bib7","first-page":"379","article-title":"Combinatorial pure exploration of multi-armed bandits","volume-title":"Advances in neural information processing systems, 27","author":"Chen","year":"2014"},{"volume-title":"Number: The language of science","year":"2007","author":"Dantzig","key":"2025012818241636300_bib8"},{"key":"2025012818241636300_bib9","first-page":"23956","article-title":"Combinatorial pure exploration with bottleneck reward function","volume-title":"Advances in neural information processing systems, 34","author":"Du","year":"2021"},{"key":"2025012818241636300_bib10","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v35i8.16892","article-title":"Combinatorial pure exploration with full- bandit or partial linear feedback","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Du","year":"2021"},{"key":"2025012818241636300_bib11","article-title":"Sequential experimental design for transductive linear bandits","volume-title":"Advances in neural information processing systems","author":"Fiez","year":"2019"},{"key":"2025012818241636300_bib12","first-page":"3212","article-title":"Best arm identification: A unified approach to fixed budget and fixed confidence","volume-title":"Advances in neural information processing systems, 25","author":"Gabillon","year":"2012"},{"key":"2025012818241636300_bib13","article-title":"Improved learning complexity in combinatorial pure exploration bandits","volume-title":"Proceedings of the 19th International Conference on Artificial Intelligence and Statistics","author":"Gabillon","year":"2016"},{"volume-title":"Algorithmic graph theory","year":"1985","author":"Gibbons","key":"2025012818241636300_bib14"},{"volume-title":"The traveling salesman problem and its variations","year":"2001","author":"Gutin","key":"2025012818241636300_bib15"},{"key":"2025012818241636300_bib16","first-page":"805","article-title":"Efficient pure exploration for combinatorial bandits with semi-bandit feedback","volume-title":"Proceedings of the 32nd International Conference on Algorithmic Learning Theory","author":"Jourdan","year":"2021"},{"key":"2025012818241636300_bib17","first-page":"511","article-title":"Efficient selection of multiple bandit arms: Theory and practice","volume-title":"Proceedings of the 27th International Conference on Machine Learning","author":"Kalyanakrishnan","year":"2010"},{"key":"2025012818241636300_bib18","first-page":"10371","article-title":"An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits","volume-title":"Advances in neural information processing systems","author":"Katz-Samuels","year":"2020"},{"issue":"1","key":"2025012818241636300_bib19","first-page":"1","article-title":"On the complexity of best-arm identification in multi-armed bandit models","volume":"17","author":"Kaufmann","year":"2016","journal-title":"Journal of Machine Learning"},{"issue":"9","key":"2025012818241636300_bib20","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1162\/neco_a_01299","article-title":"Polynomial-time algorithms for multiple-arm identification with full-bandit feedback","volume":"32","author":"Kuroki","year":"2020","journal-title":"Neural Computation"},{"journal-title":"Thompson sampling for real-valued combinatorial pure exploration of multi-armed bandit.","year":"2023","author":"Nakamura","key":"2025012818241636300_bib21"},{"issue":"1","key":"2025012818241636300_bib22","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/505241.505243","article-title":"An optimal minimum spanning tree algorithm","volume":"49","author":"Pettie","year":"2002","journal-title":"Journal of the ACM"},{"volume-title":"Production planning by mixed integer programming","year":"2010","author":"Pochet","key":"2025012818241636300_bib23"},{"key":"2025012818241636300_bib24","article-title":"Top-k combinatorial bandits with full-bandit feedback","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory","author":"Rejwan","year":"2020"},{"article-title":"Subgaussian random variables: An expository note","year":"2012","author":"Rivasplata","key":"2025012818241636300_bib25"},{"key":"2025012818241636300_bib26","first-page":"599","article-title":"Dijkstra\u2019s algorithm revisited: The dynamic programming connexion","volume":"35","author":"Sniedovich","year":"2006","journal-title":"Control and Cybernetics"},{"key":"2025012818241636300_bib27","article-title":"Best-arm identification in linear bandits","volume-title":"Advances in neural information processing systems","author":"Soare","year":"2014"},{"volume-title":"Optimal transport: Old and new","year":"2008","author":"Villani","key":"2025012818241636300_bib28"},{"key":"2025012818241636300_bib29","article-title":"Thompson sampling for (combinatorial) pure exploration","volume-title":"Proceedings of the 39th International Conference on Machine Learning","author":"Wang","year":"2022"},{"key":"2025012818241636300_bib30","first-page":"843","article-title":"A fully adaptive algorithm for pure exploration in linear bandits","volume-title":"Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistic","author":"Xu","year":"2018"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/37\/2\/294\/2482166\/neco_a_01728.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/37\/2\/294\/2482166\/neco_a_01728.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T18:24:37Z","timestamp":1738088677000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/37\/2\/294\/125500\/A-Fast-Algorithm-for-the-Real-Valued-Combinatorial"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,21]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,1,21]]},"published-print":{"date-parts":[[2025,1,21]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01728","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"type":"print","value":"0899-7667"},{"type":"electronic","value":"1530-888X"}],"subject":[],"published-other":{"date-parts":[[2025,2]]},"published":{"date-parts":[[2025,1,21]]}}}