{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T17:28:40Z","timestamp":1784136520875,"version":"3.55.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T00:00:00Z","timestamp":1519862400000},"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":["IIS-0905467, CCF-0643934, AF-0910940"],"award-info":[{"award-number":["IIS-0905467, CCF-0643934, AF-0910940"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"crossref","award":["New Faculty Fellowship"],"award-info":[{"award-number":["New Faculty Fellowship"]}],"id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"crossref","award":["Research Grant"],"award-info":[{"award-number":["Research Grant"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, to Web search and advertising. In many of these application domains, the learner may be constrained by one or more supply (or budget) limits, in addition to the customary limitation on the time horizon. The literature lacks a general model encompassing these sorts of problems. We introduce such a model, called<jats:italic>bandits with knapsacks<\/jats:italic>, that combines bandit learning with aspects of stochastic integer programming. In particular, a bandit algorithm needs to solve a stochastic version of the well-known<jats:italic>knapsack problem<\/jats:italic>, which is concerned with packing items into a limited-size knapsack. A distinctive feature of our problem, in comparison to the existing regret-minimization literature, is that the optimal policy for a given latent distribution may significantly outperform the policy that plays the optimal fixed arm. Consequently, achieving sublinear regret in the bandits-with-knapsacks problem is significantly more challenging than in conventional bandit problems.<\/jats:p><jats:p>We present two algorithms whose reward is close to the information-theoretic optimum: one is based on a novel \u201cbalanced exploration\u201d paradigm, while the other is a primal-dual algorithm that uses multiplicative updates. Further, we prove that the regret achieved by both algorithms is optimal up to polylogarithmic factors. We illustrate the generality of the problem by presenting applications in a number of different domains, including electronic commerce, routing, and scheduling. As one example of a concrete application, we consider the problem of dynamic posted pricing with limited supply and obtain the first algorithm whose regret, with respect to the optimal dynamic policy, is sublinear in the supply.<\/jats:p>","DOI":"10.1145\/3164539","type":"journal-article","created":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T15:27:23Z","timestamp":1519918043000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":109,"title":["Bandits with Knapsacks"],"prefix":"10.1145","volume":"65","author":[{"given":"Ashwinkumar","family":"Badanidiyuru","sequence":"first","affiliation":[{"name":"Google Research, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 26th COLT.","author":"Abraham Ittai","year":"2013"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 31st ICML.","author":"Agarwal Alekh","year":"2014"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602844"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 29th NIPS.","author":"Agrawal Shipra"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2765026.2765038"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 29th COLT.","author":"Agrawal Shipra","year":"2016"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 28th UAI.","author":"Amin Kareem","year":"2012"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566386"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229023"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229026"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.30"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 27th COLT.","author":"Badanidiyuru Ashwinkumar","year":"2014"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0640"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2448473.2448483"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 14th ACM-SIAM SODA. 202--204","author":"Blum Avrim","year":"2003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2015.03.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"S\u00e9bastien Bubeck and Nicolo Cesa-Bianchi. 2012. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Found.Trends Mach. Learn. 5 1 (2012). S\u00e9bastien Bubeck and Nicolo Cesa-Bianchi. 2012. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Found.Trends Mach. Learn. 5 1 (2012).","DOI":"10.1561\/2200000024"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627903"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 14th AISTATS.","author":"Chu Wei"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 21th COLT. 355--366","author":"Dani Varsha","year":"2008"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566388"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993581"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 27th AAAI.","author":"Ding Wenkui","year":"2013"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 27th UAI.","author":"Dud\u00edik Miroslav","year":"2011"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/648301.755490"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888957"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_41"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.48"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 20th IJCAI. 830--835","author":"Gy\u00f6rgy Andr\u00e1s","year":"2007"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 20th COLT. 499--513","author":"Hazan Elad","year":"2007"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 18th NIPS.","author":"Kleinberg Robert","year":"2004"},{"key":"e_1_2_1_38_1","unstructured":"Robert Kleinberg. 2007. Lecture notes for CS 683 (week 2) Cornell University. Retrieved from http:\/\/www.cs.cornell.edu\/courses\/cs683\/2007sp\/lecnotes\/week2.pdf. Robert Kleinberg. 2007. Lecture notes for CS 683 (week 2) Cornell University. Retrieved from http:\/\/www.cs.cornell.edu\/courses\/cs683\/2007sp\/lecnotes\/week2.pdf."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946352"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873669"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 21st NIPS.","author":"Langford John","year":"2007"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 14th AISTATS.","author":"Lu Tyler","year":"2010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_59"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.20"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273587"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.293"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488490"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2692359.2692364"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 24th AAAI. 1211--1216","author":"Tran-Thanh Long"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 26th AAAI. 1134--1140","author":"Tran-Thanh Long"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 30th UAI.","author":"Tran-Thanh Long","year":"2014"},{"key":"e_1_2_1_56_1","first-page":"318","article-title":"Close the Gaps","volume":"62","author":"Wang Zizhuo","year":"2014","journal-title":"A Learning-While-Doing Algorithm for Single-Product Revenue Management Problems. Oper. Res."},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1111\/j.2517-6161.1980.tb01111.x","article-title":"Multi-armed Bandits and the Gittins Index","volume":"42","author":"Whittle Peter","year":"1980","journal-title":"J. Roy. Stat. Soc., Ser. B"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3164539","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3164539","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3164539","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:38Z","timestamp":1750212818000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3164539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3164539"],"URL":"https:\/\/doi.org\/10.1145\/3164539","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}