{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T07:07:02Z","timestamp":1776064022553,"version":"3.50.1"},"reference-count":101,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            We consider\n            <jats:bold>\n              <jats:italic>Bandits with Knapsacks<\/jats:italic>\n            <\/jats:bold>\n            (henceforth,\n            <jats:italic>\n              <jats:bold>BwK<\/jats:bold>\n            <\/jats:italic>\n            ), a general model for multi-armed bandits under supply\/budget constraints. In particular, a bandit algorithm needs to solve a well-known\n            <jats:italic>knapsack problem<\/jats:italic>\n            : find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the \u201cclassic\u201d adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the\n            <jats:italic>competitive ratio<\/jats:italic>\n            : the ratio of the benchmark reward to algorithm\u2019s reward.\n          <\/jats:p>\n          <jats:p>\n            We design an algorithm with competitive ratio\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>T<\/jats:italic>\n            ) relative to the best fixed distribution over actions, where\n            <jats:italic>T<\/jats:italic>\n            is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version, and use it as a subroutine to solve the latter.\n          <\/jats:p>\n          <jats:p>Our algorithm is the first \u201cblack-box reduction\u201d from bandits to BwK: it takes an arbitrary bandit algorithm and uses it as a subroutine. We use this reduction to derive several extensions.<\/jats:p>","DOI":"10.1145\/3557045","type":"journal-article","created":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T11:03:14Z","timestamp":1660820594000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Adversarial Bandits with Knapsacks"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4180-4657","authenticated-orcid":false,"given":"Nicole","family":"Immorlica","sequence":"first","affiliation":[{"name":"Microsoft Research, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8569-5694","authenticated-orcid":false,"given":"Karthik","family":"Sankararaman","sequence":"additional","affiliation":[{"name":"Meta AI, Menlo Park, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8616-1611","authenticated-orcid":false,"given":"Robert","family":"Schapire","sequence":"additional","affiliation":[{"name":"Microsoft Research, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6899-6383","authenticated-orcid":false,"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"6584","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Abernethy Jacob D.","year":"2017","unstructured":"Jacob D. Abernethy and Jun-Kun Wang. 2017. On Frank-Wolfe and equilibrium computation. In Advances in Neural Information Processing Systems (NIPS). 6584\u20136593."},{"key":"e_1_3_3_3_2","article-title":"A reductions approach to fair classification","author":"Agarwal Alekh","year":"2017","unstructured":"Alekh Agarwal, Alina Beygelzimer, Miroslav Dud\u00edk, John Langford, and Hanna Wallach. 2017. A reductions approach to fair classification. Fairness, Accountability, and Transparency in Machine Learning (FATML) (2017).","journal-title":"Fairness, Accountability, and Transparency in Machine Learning (FATML)"},{"key":"e_1_3_3_4_2","first-page":"19","volume-title":"15th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS)","author":"Agarwal Alekh","year":"2012","unstructured":"Alekh Agarwal, Miroslav Dud\u00edk, Satyen Kale, John Langford, and Robert E. Schapire. 2012. Contextual bandit learning with predictable rewards. In 15th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS). 19\u201326."},{"key":"e_1_3_3_5_2","volume-title":"31st Intl. Conf. on Machine Learning (ICML)","author":"Agarwal Alekh","year":"2014","unstructured":"Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. 2014. Taming the monster: A fast and simple algorithm for contextual bandits. In 31st Intl. Conf. on Machine Learning (ICML)."},{"key":"e_1_3_3_6_2","volume-title":"15th ACM Conf. on Economics and Computation (ACM-EC)","author":"Agrawal Shipra","year":"2014","unstructured":"Shipra Agrawal and Nikhil R. Devanur. 2014. Bandits with concave rewards and convex knapsacks. In 15th ACM Conf. on Economics and Computation (ACM-EC)."},{"key":"e_1_3_3_7_2","volume-title":"29th Advances in Neural Information Processing Systems (NIPS)","author":"Agrawal Shipra","year":"2016","unstructured":"Shipra Agrawal and Nikhil R. Devanur. 2016. Linear contextual bandits with knapsacks. In 29th Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_3_8_2","volume-title":"29th Conf. on Learning Theory (COLT)","author":"Agrawal Shipra","year":"2016","unstructured":"Shipra Agrawal, Nikhil R. Devanur, and Lihong Li. 2016. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In 29th Conf. on Learning Theory (COLT)."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2773183.2773195"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780558"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_3_13_2","first-page":"107","volume-title":"24th Conf. on Learning Theory (COLT)","author":"Audibert Jean-Yves","year":"2011","unstructured":"Jean-Yves Audibert, S\u00e9bastien Bubeck, and G\u00e1bor Lugosi. 2011. Minimax policies for combinatorial prediction games. In 24th Conf. on Learning Theory (COLT). 107\u2013132."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_3_3_15_2","volume-title":"29th Conf. on Learning Theory (COLT)","author":"Auer Peter","year":"2016","unstructured":"Peter Auer and Chao-Kai Chiang. 2016. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In 29th Conf. on Learning Theory (COLT)."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646143"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.24"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2559152"},{"key":"e_1_3_3_19_2","first-page":"128","volume-title":"13th ACM Conf. on Electronic Commerce (ACM-EC)","author":"Badanidiyuru Ashwinkumar","year":"2012","unstructured":"Ashwinkumar Badanidiyuru, Robert Kleinberg, and Yaron Singer. 2012. Learning on a budget: Posted price mechanisms for online procurement. In 13th ACM Conf. on Electronic Commerce (ACM-EC). 128\u2013145."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3164539"},{"key":"e_1_3_3_21_2","volume-title":"27th Conf. on Learning Theory (COLT)","author":"Badanidiyuru Ashwinkumar","year":"2014","unstructured":"Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. 2014. Resourceful contextual bandits. In 27th Conf. on Learning Theory (COLT)."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.63"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/502969"},{"key":"e_1_3_3_24_2","volume-title":"The New Palgrave Dictionary of Economics, 2nd ed.","author":"Bergemann Dirk","year":"2006","unstructured":"Dirk Bergemann and Juuso V\u00e4lim\u00e4ki. 2006. Bandit problems. In The New Palgrave Dictionary of Economics, 2nd ed., Steven Durlauf and Larry Blume (Eds.). Macmillan Press."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0640"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/2448473.2448483"},{"key":"e_1_3_3_27_2","volume-title":"14th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS)","author":"Beygelzimer Alina","year":"2011","unstructured":"Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert E. Schapire. 2011. Contextual bandit algorithms with supervised learning guarantees. In 14th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS)."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"e_1_3_3_30_2","first-page":"266","volume-title":"28th Conf. on Learning Theory (COLT)","author":"Bubeck S\u00e9bastien","year":"2015","unstructured":"S\u00e9bastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. 2015. Bandit convex optimization: \\( \\sqrt{T} \\) regret in one dimension. In 28th Conf. on Learning Theory (COLT). 266\u2013278."},{"key":"e_1_3_3_31_2","first-page":"72","volume-title":"49th ACM Symp. on Theory of Computing (STOC)","author":"Bubeck S\u00e9bastien","year":"2017","unstructured":"S\u00e9bastien Bubeck, Yin Tat Lee, and Ronen Eldan. 2017. Kernel-based methods for bandit convex optimization. In 49th ACM Symp. on Theory of Computing (STOC). ACM, 72\u201385."},{"key":"e_1_3_3_32_2","volume-title":"25th Conf. on Learning Theory (COLT)","author":"Bubeck S\u00e9bastien","year":"2012","unstructured":"S\u00e9bastien Bubeck and Aleksandrs Slivkins. 2012. The best of both worlds: Stochastic and adversarial bandits. In 25th Conf. on Learning Theory (COLT)."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_3_3_35_2","first-page":"921","volume-title":"36th Intl. Conf. on Machine Learning (ICML)","author":"Cardoso Adrian Rivera","year":"2019","unstructured":"Adrian Rivera Cardoso, Jacob D. Abernethy, He Wang, and Huan Xu. 2019. Competing against Nash equilibria in adversarially changing zero-sum games. In 36th Intl. Conf. on Machine Learning (ICML). 921\u2013930."},{"key":"e_1_3_3_36_2","article-title":"Online saddle point problem with applications to constrained online convex optimization","author":"Cardoso Adrian Rivera","year":"2018","unstructured":"Adrian Rivera Cardoso, He Wang, and Huan Xu. 2018. Online saddle point problem with applications to constrained online convex optimization. arXiv preprint arXiv:1806.08301 (2018).","journal-title":"arXiv preprint arXiv:1806.08301"},{"key":"e_1_3_3_37_2","volume-title":"39th Intl. Conf. on Machine Learning (ICML)","author":"Castiglioni Matteo","year":"2022","unstructured":"Matteo Castiglioni, Andrea Celli, and Christian Kroer. 2022. Online learning with knapsacks: The best of both worlds. In 39th Intl. Conf. on Machine Learning (ICML)."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/1137817"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743496"},{"key":"e_1_3_3_40_2","article-title":"Bandit convex optimization for scalable and dynamic IoT management","author":"Chen Tianyi","year":"2018","unstructured":"Tianyi Chen and Georgios B. Giannakis. 2018. Bandit convex optimization for scalable and dynamic IoT management. IEEE Internet of Things Journal (2018).","journal-title":"IEEE Internet of Things Journal"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2017.2750109"},{"key":"e_1_3_3_42_2","first-page":"273","volume-title":"43rd ACM Symp. on Theory of Computing (STOC)","author":"Christiano Paul","year":"2011","unstructured":"Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. 2011. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In 43rd ACM Symp. on Theory of Computing (STOC). ACM, 273\u2013282."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745847"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.01.003"},{"key":"e_1_3_3_45_2","first-page":"71","volume-title":"10th ACM Conf. on Electronic Commerce (ACM-EC)","author":"Devanur Nikhil R.","year":"2009","unstructured":"Nikhil R. Devanur and Thomas P. Hayes. 2009. The AdWords problem: Online keyword matching with budgeted bidders under random permutations. In 10th ACM Conf. on Electronic Commerce (ACM-EC). 71\u201378."},{"key":"e_1_3_3_46_2","first-page":"29","volume-title":"12th ACM Conf. on Electronic Commerce (ACM-EC)","author":"Devanur Nikhil R.","year":"2011","unstructured":"Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. 2011. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In 12th ACM Conf. on Electronic Commerce (ACM-EC). 29\u201338."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v27i1.8637"},{"key":"e_1_3_3_48_2","volume-title":"27th Conf. on Uncertainty in Artificial Intelligence (UAI)","author":"Dud\u00edk Miroslav","year":"2011","unstructured":"Miroslav Dud\u00edk, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. 2011. Efficient optimal learning for contextual bandits. In 27th Conf. on Uncertainty in Artificial Intelligence (UAI)."},{"key":"e_1_3_3_49_2","first-page":"182","volume-title":"18th Annual European Symp. on Algorithms (ESA)","author":"Feldman Jon","year":"2010","unstructured":"Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. 2010. Online stochastic packing applied to display ad allocation. In 18th Annual European Symp. on Algorithms (ESA). 182\u2013194."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_3_51_2","first-page":"385","volume-title":"16th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"Flaxman Abraham","year":"2005","unstructured":"Abraham Flaxman, Adam Kalai, and H. Brendan McMahan. 2005. Online convex optimization in the bandit setting: Gradient descent without a gradient. In 16th ACM-SIAM Symp. on Discrete Algorithms (SODA). 385\u2013394."},{"key":"e_1_3_3_52_2","first-page":"325","volume-title":"9th Conf. on Learning Theory (COLT)","author":"Freund Yoav","year":"1996","unstructured":"Yoav Freund and Robert E. Schapire. 1996. Game theory, on-line prediction and boosting. In 9th Conf. on Learning Theory (COLT). 325\u2013332."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"e_1_3_3_55_2","unstructured":"Jason Gaitonde Yingkai Li Bar Light Brendan Lucier and Aleksandrs Slivkins. 2022. Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence. (2022). Working paper available at https:\/\/arxiv.org\/abs\/2205.08674."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470980033"},{"key":"e_1_3_3_57_2","first-page":"496","volume-title":"36th Intl. Colloquium on Automata, Languages and Programming (ICALP)","author":"Guha Sudipta","year":"2007","unstructured":"Sudipta Guha and Kamesh Munagala. 2007. Multi-armed bandits with metric switching costs. In 36th Intl. Colloquium on Automata, Languages and Programming (ICALP). 496\u2013507."},{"key":"e_1_3_3_58_2","first-page":"827","volume-title":"52nd IEEE Symp. on Foundations of Computer Science (FOCS)","author":"Gupta Anupam","year":"2011","unstructured":"Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi. 2011. Approximation algorithms for correlated knapsacks and non-martingale bandits. In 52nd IEEE Symp. on Foundations of Computer Science (FOCS). 827\u2013836."},{"key":"e_1_3_3_59_2","first-page":"830","volume-title":"20th Intl. Joint Conf. on Artificial Intelligence (IJCAI)","author":"Gy\u00f6rgy Andr\u00e1s","year":"2007","unstructured":"Andr\u00e1s Gy\u00f6rgy, Levente Kocsis, Ivett Szab\u00f3, and Csaba Szepesv\u00e1ri. 2007. Continuous time associative bandit problems. In 20th Intl. Joint Conf. on Artificial Intelligence (IJCAI). 830\u2013835."},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.5555\/1314498.1314575"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_3_3_62_2","first-page":"784","volume-title":"27th Advances in Neural Information Processing Systems (NIPS)","author":"Hazan Elad","year":"2014","unstructured":"Elad Hazan and Kfir Y. Levy. 2014. Bandit convex optimization: Towards tight bounds. In 27th Advances in Neural Information Processing Systems (NIPS). 784\u2013792."},{"key":"e_1_3_3_63_2","first-page":"580","volume-title":"27th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"Hsu Justin","year":"2016","unstructured":"Justin Hsu, Zhiyi Huang, Aaron Roth, and Zhiwei Steven Wu. 2016. Jointly private convex programming. In 27th ACM-SIAM Symp. on Discrete Algorithms (SODA). 580\u2013599."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_3_3_65_2","first-page":"1054","volume-title":"24th Advances in Neural Information Processing Systems (NIPS)","author":"Kale Satyen","year":"2010","unstructured":"Satyen Kale, Lev Reyzin, and Robert E. Schapire. 2010. Non-stochastic bandit slate problems. In 24th Advances in Neural Information Processing Systems (NIPS). 1054\u20131062."},{"key":"e_1_3_3_66_2","first-page":"2564","volume-title":"35th Intl. Conf. on Machine Learning (ICML)","author":"Kearns Michael","year":"2018","unstructured":"Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2018. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In 35th Intl. Conf. on Machine Learning (ICML). 2564\u20132572."},{"key":"e_1_3_3_67_2","first-page":"2286","volume-title":"33rd Conf. on Learning Theory (COLT)","author":"Kesselheim Thomas","year":"2020","unstructured":"Thomas Kesselheim and Sahil Singla. 2020. Online learning with vector costs and bandits with knapsacks. In 33rd Conf. on Learning Theory (COLT). 2286\u20132305."},{"key":"e_1_3_3_68_2","volume-title":"18th Advances in Neural Information Processing Systems (NIPS)","author":"Kleinberg Robert","year":"2004","unstructured":"Robert Kleinberg. 2004. Nearly tight bounds for the continuum-armed bandit problem. In 18th Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_3_69_2","volume-title":"21st Advances in Neural Information Processing Systems (NIPS)","author":"Langford John","year":"2007","unstructured":"John Langford and Tong Zhang. 2007. The epoch-greedy algorithm for contextual multi-armed bandits. In 21st Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_3_3_73_2","volume-title":"50th ACM Symp. on Theory of Computing (STOC)","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris, Vahab Mirrokni, and Renato Paes-Leme. 2018. Stochastic bandits robust to adversarial corruptions. In 50th ACM Symp. on Theory of Computing (STOC)."},{"key":"e_1_3_3_74_2","first-page":"2503","article-title":"Trading regret for efficiency: Online convex optimization with long term constraints","volume":"13","author":"Mahdavi Mehrdad","year":"2012","unstructured":"Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. 2012. Trading regret for efficiency: Online convex optimization with long term constraints. J. of Machine Learning Research (JMLR) 13, Sep. (2012), 2503\u20132528.","journal-title":"J. of Machine Learning Research (JMLR)"},{"key":"e_1_3_3_75_2","first-page":"1115","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Mahdavi Mehrdad","year":"2013","unstructured":"Mehrdad Mahdavi, Tianbao Yang, and Rong Jin. 2013. Stochastic convex optimization with multiple objectives. In Advances in Neural Information Processing Systems (NIPS). 1115\u20131123."},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_3_3_78_2","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1007\/978-3-642-31594-7_59","volume-title":"39th Intl. Colloquium on Automata, Languages and Programming (ICALP)","author":"Molinaro Marco","year":"2012","unstructured":"Marco Molinaro and R. Ravi. 2012. Geometry of online packing linear programs. In 39th Intl. Colloquium on Automata, Languages and Programming (ICALP). 701\u2013713."},{"key":"e_1_3_3_79_2","article-title":"Online convex optimization with time-varying constraints","author":"Neely Michael J.","year":"2017","unstructured":"Michael J. Neely and Hao Yu. 2017. Online convex optimization with time-varying constraints. arXiv preprint arXiv:1702.04783 (2017).","journal-title":"arXiv preprint arXiv:1702.04783"},{"key":"e_1_3_3_80_2","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3053436"},{"key":"e_1_3_3_81_2","first-page":"3066","volume-title":"27th Advances in Neural Information Processing Systems (NIPS)","author":"Rakhlin Alexander","year":"2013","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2013. Optimization, learning, and games with predictable sequences. In 27th Advances in Neural Information Processing Systems (NIPS). 3066\u20133074."},{"key":"e_1_3_3_82_2","volume-title":"33rd Intl. Conf. on Machine Learning (ICML)","author":"Rakhlin Alexander","year":"2016","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2016. BISTRO: An efficient relaxation-based method for contextual bandits. In 33rd Intl. Conf. on Machine Learning (ICML)."},{"key":"e_1_3_3_83_2","first-page":"3311","volume-title":"28th Intl. Joint Conf. on Artificial Intelligence (IJCAI)","author":"Rangi Anshuka","year":"2019","unstructured":"Anshuka Rangi, Massimo Franceschetti, and Long Tran-Thanh. 2019. Unifying the stochastic and the adversarial bandits with knapsack. In 28th Intl. Joint Conf. on Artificial Intelligence (IJCAI). 3311\u20133317."},{"key":"e_1_3_3_84_2","first-page":"471","volume-title":"16th ACM Conf. on Electronic Commerce (ACM-EC)","author":"Rogers Ryan","year":"2015","unstructured":"Ryan Rogers, Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. 2015. Inducing approximately optimal flow using truthful mediators. In 16th ACM Conf. on Electronic Commerce (ACM-EC). 471\u2013488."},{"key":"e_1_3_3_85_2","first-page":"519","volume-title":"18th ACM Conf. on Electronic Commerce (ACM-EC)","author":"Roth Aaron","year":"2017","unstructured":"Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, and Zhiwei Steven Wu. 2017. Multidimensional dynamic pricing for welfare maximization. In 18th ACM Conf. on Electronic Commerce (ACM-EC). 519\u2013536."},{"key":"e_1_3_3_86_2","first-page":"949","volume-title":"48th ACM Symp. on Theory of Computing (STOC)","author":"Roth Aaron","year":"2016","unstructured":"Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. 2016. Watch and learn: Optimizing from revealed preferences feedback. In 48th ACM Symp. on Theory of Computing (STOC). 949\u2013962."},{"key":"e_1_3_3_87_2","first-page":"1760","volume-title":"Intl. Conf. on Artificial Intelligence and Statistics (AISTATS)","author":"Sankararaman Karthik Abinav","year":"2018","unstructured":"Karthik Abinav Sankararaman and Aleksandrs Slivkins. 2018. Combinatorial semi-bandits with knapsacks. In Intl. Conf. on Artificial Intelligence and Statistics (AISTATS). 1760\u20131770."},{"key":"e_1_3_3_88_2","doi-asserted-by":"publisher","DOI":"10.5555\/2207821"},{"key":"e_1_3_3_89_2","volume-title":"30th Conf. on Learning Theory (COLT)","author":"Seldin Yevgeny","year":"2017","unstructured":"Yevgeny Seldin and G\u00e1bor Lugosi. 2017. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. In 30th Conf. on Learning Theory (COLT)."},{"key":"e_1_3_3_90_2","volume-title":"31st Intl. Conf. on Machine Learning (ICML)","author":"Seldin Yevgeny","year":"2014","unstructured":"Yevgeny Seldin and Aleksandrs Slivkins. 2014. One practical algorithm for both stochastic and adversarial bandits. In 31st Intl. Conf. on Machine Learning (ICML)."},{"key":"e_1_3_3_91_2","first-page":"1167","volume-title":"22nd Intl. World Wide Web Conf. (WWW)","author":"Singla Adish","year":"2013","unstructured":"Adish Singla and Andreas Krause. 2013. Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In 22nd Intl. World Wide Web Conf. (WWW). 1167\u20131178."},{"key":"e_1_3_3_92_2","article-title":"Dynamic Ad Allocation: Bandits with Budgets","author":"Slivkins Aleksandrs","year":"2013","unstructured":"Aleksandrs Slivkins. 2013. Dynamic Ad Allocation: Bandits with Budgets. A technical report on arxiv.org\/abs\/1306.0155. (June 2013).","journal-title":"A technical report on arxiv.org\/abs\/1306.0155"},{"key":"e_1_3_3_93_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000068"},{"key":"e_1_3_3_94_2","volume-title":"33rd Intl. Conf. on Machine Learning (ICML)","author":"Syrgkanis Vasilis","year":"2016","unstructured":"Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert E. Schapire. 2016. Efficient algorithms for adversarial contextual learning. In 33rd Intl. Conf. on Machine Learning (ICML)."},{"key":"e_1_3_3_95_2","volume-title":"29th Advances in Neural Information Processing Systems (NIPS)","author":"Syrgkanis Vasilis","year":"2016","unstructured":"Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E. Schapire. 2016. Improved regret bounds for oracle-based adversarial contextual bandits. In 29th Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_3_96_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v24i1.7758"},{"key":"e_1_3_3_97_2","first-page":"1134","volume-title":"26th AAAI Conference on Artificial Intelligence (AAAI)","author":"Tran-Thanh Long","year":"2012","unstructured":"Long Tran-Thanh, Archie Chapman, Alex Rogers, and Nicholas R. Jennings. 2012. Knapsack based optimal policies for budget-limited multi-armed bandits. In 26th AAAI Conference on Artificial Intelligence (AAAI). 1134\u20131140."},{"key":"e_1_3_3_98_2","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722220"},{"key":"e_1_3_3_99_2","first-page":"3828","volume-title":"31st Advances in Neural Information Processing Systems (NIPS)","author":"Wang Jun-Kun","year":"2018","unstructured":"Jun-Kun Wang and Jacob D. Abernethy. 2018. Acceleration through optimistic no-regret dynamics. In 31st Advances in Neural Information Processing Systems (NIPS). 3828\u20133838."},{"key":"e_1_3_3_100_2","doi-asserted-by":"publisher","DOI":"10.5555\/2770678.2770686"},{"key":"e_1_3_3_101_2","volume-title":"31st Conf. on Learning Theory (COLT)","author":"Wei Chen-Yu","year":"2018","unstructured":"Chen-Yu Wei and Haipeng Luo. 2018. More adaptive algorithms for adversarial bandits. In 31st Conf. on Learning Theory (COLT)."},{"key":"e_1_3_3_102_2","doi-asserted-by":"publisher","DOI":"10.5555\/1971947"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3557045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3557045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:52Z","timestamp":1750286932000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3557045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":101,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3557045"],"URL":"https:\/\/doi.org\/10.1145\/3557045","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"2019-11-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}