{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:32Z","timestamp":1781078312578,"version":"3.54.1"},"reference-count":101,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-0643934, CCF-0729102, CCR-0121154 and DMI-0600384"],"award-info":[{"award-number":["CCF-0643934, CCF-0729102, CCR-0121154 and DMI-0600384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ONR","award":["N000140610607"],"award-info":[{"award-number":["N000140610607"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is well understood, bandit problems with large strategy sets are still a topic of active investigation, motivated by practical applications, such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions that enable the design of efficient solutions.<\/jats:p>\n          <jats:p>\n            In this work, we study a general setting for the multi-armed bandit problem, in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the\n            <jats:italic>Lipschitz MAB problem<\/jats:italic>\n            . We present a solution for the multi-armed bandit problem in this setting. That is, for every metric space, we define an isometry invariant that bounds from below the performance of Lipschitz MAB algorithms for this metric space, and we present an algorithm that comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. We also address the full-feedback (\u201cbest expert\u201d) version of the problem, where after every round the payoffs from all arms are revealed.\n          <\/jats:p>","DOI":"10.1145\/3299873","type":"journal-article","created":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T12:23:16Z","timestamp":1559564596000},"page":"1-77","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Bandits and Experts in Metric Spaces"],"prefix":"10.1145","volume":"66","author":[{"given":"Robert","family":"Kleinberg","sequence":"first","affiliation":[{"name":"Computer Science Department, Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research NYC, New York, NY, USA USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[{"name":"Computer Science Department, Brown University, Providence, RI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,5,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 25th Advances in Neural Information Processing Systems (NIPS\u201911)","author":"Abbasi-Yadkori Yasin","year":"2011"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT\u201908)","author":"Abernethy Jacob","year":"2008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073978"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012992237273"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940779"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602844"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 24th Conference on Learning Theory (COLT\u201911)","author":"Amin Kareem","year":"2011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953023"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.016"},{"key":"e_1_2_1_10_1","first-page":"397","article-title":"Using confidence bounds for exploitation-exploration trade-offs","volume":"3","author":"Auer Peter","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10998-010-3055-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768841.1768884"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.016"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 31st International Conference on Machine Learning (ICML\u201914)","author":"Azar Mohammad Gheshlaghi","year":"2014"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559152"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2724705"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/120878768"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164539"},{"key":"e_1_2_1_21_1","volume-title":"The New Palgrave Dictionary of Economics","author":"Bergemann Dirk","edition":"2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-3711-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1069362389"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0640"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007335615132"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Blum Avrim","year":"2003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601986276"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 23rd Conference on Learning Theory (COLT\u201910)","author":"Bubeck S\u00e9bastien","year":"2010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981780.2981806"},{"key":"e_1_2_1_30_1","first-page":"1587","article-title":"Online optimization in X-armed bandits","volume":"12","author":"Bubeck S\u00e9bastien","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050345.2050363"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3150\/14-BEJ644"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442612"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258179"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","volume-title":"Prediction, Learning, and Games","author":"Cesa-Bianchi Nicol\u00f2","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Chan Hubert T.-H.","year":"2005"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2019797"},{"key":"e_1_2_1_39_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"1991"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 20th Advances in Neural Information Processing Systems (NIPS\u201907)","author":"Dani Varsha","year":"2007"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT\u201908)","author":"Dani Varsha","year":"2008"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning (ICML\u201912)","author":"Desautels Thomas","year":"2012"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566388"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Flaxman Abraham","year":"2005"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4949-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258616"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 24th Conference on Learning Theory (COLT\u201911)","author":"Garivier Aur\u00e9lien","year":"2011"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","volume-title":"Multi-Armed Bandit Allocation Indices","author":"Gittins John","DOI":"10.1002\/9780470980033"},{"key":"e_1_2_1_50_1","unstructured":"Anupam Gupta Mike Dinitz and Kanat Tangwongsan. 2007. Private communication.  Anupam Gupta Mike Dinitz and Kanat Tangwongsan. 2007. Private communication."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS\u201903)","author":"Gupta Anupam"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021042"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768841.1768888"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","volume-title":"Lectures on Analysis on Metric Spaces","author":"Heinonen J.","DOI":"10.1007\/978-1-4613-0131-8"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007918"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/3013558.3013568"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 23rd Conference on Learning Theory (COLT\u201910)","author":"Honda Junya","year":"2010"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 18th Advances in Neural Information Processing Systems (NIPS\u201904)","author":"Kleinberg Robert","year":"2004"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT\u201908)","author":"Kleinberg Robert","year":"2008"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873669"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","unstructured":"Robert Kleinberg Aleksandrs Slivkins and Eli Upfal. 2008. Multi-Armed Bandits in Metric Spaces. Technical report. Retrieved from http:\/\/arxiv.org\/abs\/0809.4882.  Robert Kleinberg Aleksandrs Slivkins and Eli Upfal. 2008. Multi-Armed Bandits in Metric Spaces. Technical report. Retrieved from http:\/\/arxiv.org\/abs\/0809.4882.","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201903)","author":"Robert"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the 25th Advances in Neural Information Processing Systems (NIPS\u201911)","author":"Krause Andreas","year":"2011"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_2_1_70_1","volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910)","author":"Lu Tyler","year":"2010"},{"key":"e_1_2_1_71_1","volume-title":"Proceedings of the 27th Conference on Learning Theory (COLT\u201914)","author":"Magureanu Stefan","year":"2014"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888305.1888326"},{"key":"e_1_2_1_73_1","volume-title":"Proceedings of the 24th Conference on Learning Theory (COLT\u201911)","author":"Maillard Odalric-Ambrym","year":"2011"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-1-1-17-27"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"e_1_2_1_76_1","volume-title":"Proceedings of the 26th Conference on Learning Theory (COLT\u201913)","author":"Minsker Stanislav","year":"2013"},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the 25th Conference on Advances in Neural Information Processing Systems (NIPS\u201911)","author":"Munos R\u00e9mi","year":"2011"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000038"},{"key":"e_1_2_1_80_1","volume-title":"Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI\u201907)","author":"Munos R\u00e9mi","year":"2007"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.20"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273587"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390255"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1952-09620-8"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_1_86_1","volume-title":"Chaos and Power Laws: Minutes from an Infinite Paradise","author":"Schroeder Manfred"},{"key":"e_1_2_1_87_1","doi-asserted-by":"crossref","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"Shalev-Shwartz Shai","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.5555\/3271139.3271275"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281116"},{"key":"e_1_2_1_90_1","volume-title":"Proceedings of the 25th Advances in Neural Information Processing Systems (NIPS\u201911)","author":"Slivkins Aleksandrs","year":"2011"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670330"},{"key":"e_1_2_1_92_1","volume-title":"Ranked bandits in metric spaces: Learning optimally diverse rankings over large document collections. J. Mach. Learn. Res. 14 (Feb","author":"Slivkins Aleksandrs","year":"2013"},{"key":"e_1_2_1_93_1","volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT\u201908)","author":"Slivkins Aleksandrs","year":"2008"},{"key":"e_1_2_1_94_1","volume-title":"Proceedings of the 27th International Conference on Machine Learning (ICML\u201910)","author":"Srinivas Niranjan","year":"2010"},{"key":"e_1_2_1_95_1","volume-title":"The Generic Chaining: Upper and Lower Bounds of Stochastic Processes","author":"Talagrand Michel"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/25.3-4.285"},{"key":"e_1_2_1_98_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning (ICML\u201913)","author":"Valko Michal","year":"2013"},{"key":"e_1_2_1_99_1","first-page":"739","article-title":"Estimate of the number of signals in error correcting codes","volume":"177","author":"Varshamov R. R.","year":"1957","journal-title":"Doklady Akadamii Nauk"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1556"},{"key":"e_1_2_1_101_1","volume-title":"Advances in Neural Information Processing Systems","author":"Wang Yizao"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.5555\/2770678.2770686"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299873","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3299873","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3299873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:23Z","timestamp":1750207403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,31]]},"references-count":101,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3299873"],"URL":"https:\/\/doi.org\/10.1145\/3299873","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,31]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}