{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T12:52:56Z","timestamp":1784638376261,"version":"3.55.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,16]],"date-time":"2022-11-16T00:00:00Z","timestamp":1668556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,16]],"date-time":"2022-11-16T00:00:00Z","timestamp":1668556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005722","name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005722","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a resource-aware variant of the classical multi-armed bandit problem: In each round, the learner selects an arm and determines a resource limit. It then observes a corresponding (random) reward, provided the (random) amount of consumed resources remains below the limit. Otherwise, the observation is censored, i.e., no reward is obtained. For this problem setting, we introduce a measure of regret, which incorporates both the actual amount of consumed resources of each learning round and the optimality of realizable rewards as well as the risk of exceeding the allocated resource limit. Thus, to minimize regret, the learner needs to set a resource limit and choose an arm in such a way that the chance to realize a high reward within the predefined resource limit is high, while the resource limit itself should be kept as low as possible. We propose a UCB-inspired online learning algorithm, which we analyze theoretically in terms of its regret upper bound. In a simulation study, we show that our learning algorithm outperforms straightforward extensions of standard multi-armed bandit algorithms.<\/jats:p>","DOI":"10.1007\/s10994-022-06271-z","type":"journal-article","created":{"date-parts":[[2022,11,16]],"date-time":"2022-11-16T23:02:36Z","timestamp":1668639756000},"page":"217-240","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Multi-armed bandits with censored consumption of resources"],"prefix":"10.1007","volume":"112","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6988-6186","authenticated-orcid":false,"given":"Viktor","family":"Bengs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eyke","family":"H\u00fcllermeier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,11,16]]},"reference":[{"issue":"4","key":"6271_CR1","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00453-003-1038-1","volume":"37","author":"N Abe","year":"2003","unstructured":"Abe, N., Biermann, A., & Long, P. (2003). Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4), 263\u2013293.","journal-title":"Algorithmica"},{"key":"6271_CR2","unstructured":"Abernethy, J., Amin, K., & Zhu, R. (2016). Threshold bandit, with and without censored feedback. In NeurIPS (pp. 4896\u20134904)."},{"key":"6271_CR3","unstructured":"Agrawal, S., & Goyal, N. (2012). Analysis of Thompson sampling for the multi-armed bandit problem. In COLT (pp. 1\u201339)."},{"key":"6271_CR4","doi-asserted-by":"crossref","unstructured":"Allmendinger, R., & Knowles, J. (2010). On-line purchasing strategies for an evolutionary algorithm performing resource-constrained optimization. In International Conference on Parallel Problem Solving from Nature (pp. 161\u2013170). Springer.","DOI":"10.1007\/978-3-642-15871-1_17"},{"key":"6271_CR5","doi-asserted-by":"crossref","unstructured":"Allmendinger, R., & Knowles, J. (2011). Policy learning in resource-constrained optimization. In GECCO (pp. 1971\u20131978).","DOI":"10.1145\/2001576.2001841"},{"issue":"3","key":"6271_CR6","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1162\/EVCO_a_00097","volume":"21","author":"R Allmendinger","year":"2013","unstructured":"Allmendinger, R., & Knowles, J. (2013). On handling ephemeral resource constraints in evolutionary search. Evolutionary Computation, 21(3), 497\u2013531.","journal-title":"Evolutionary Computation"},{"key":"6271_CR7","doi-asserted-by":"crossref","unstructured":"Allmendinger, R., & Knowles, J. (2015). Ephemeral resource constraints in optimization. In Evolutionary Constrained Optimization (pp. 95\u2013134). Springer.","DOI":"10.1007\/978-81-322-2184-5_4"},{"issue":"Nov","key":"6271_CR8","first-page":"397","volume":"3","author":"P Auer","year":"2002","unstructured":"Auer, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(Nov), 397\u2013422.","journal-title":"Journal of Machine Learning Research"},{"issue":"2\u20133","key":"6271_CR9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"47","author":"P Auer","year":"2002","unstructured":"Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2\u20133), 235\u2013256.","journal-title":"Machine Learning"},{"key":"6271_CR10","unstructured":"Auer, P., Chiang, C. K., Ortner, R., & Drugan, M. (2016). Pareto front identification from stochastic bandit feedback. In AISTATS (pp. 939\u2013947)."},{"key":"6271_CR11","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Kleinberg, R., & Slivkins, A. (2013). Bandits with knapsacks. In Annual Symposium on Foundations of Computer Science (pp. 207\u2013216). IEEE.","DOI":"10.1109\/FOCS.2013.30"},{"issue":"7","key":"6271_CR12","first-page":"1","volume":"22","author":"V Bengs","year":"2021","unstructured":"Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., & H\u00fcllermeier, E. (2021). Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22(7), 1\u2013108.","journal-title":"Journal of Machine Learning Research"},{"key":"6271_CR13","unstructured":"Bubeck, S. (2010). Bandits games and clustering foundations. Ph.D. thesis, Universit\u00e9 des Sciences et Technologie de Lille-Lille I."},{"issue":"5","key":"6271_CR14","first-page":"1655","volume":"12","author":"S Bubeck","year":"2011","unstructured":"Bubeck, S., Munos, R., Stoltz, G., & Szepesv\u00e1ri, C. (2011). X-armed bandits. Journal of Machine Learning Research, 12(5), 1655\u20131695.","journal-title":"Journal of Machine Learning Research"},{"key":"6271_CR15","unstructured":"Busa-Fekete, R., Sz\u00f6r\u00e9nyi, B., Weng, P., & Mannor, S. (2017). Multi-objective bandits: Optimizing the generalized Gini index. In ICML (pp. 625\u2013634)."},{"issue":"2","key":"6271_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3341617.3326158","volume":"3","author":"S Cayci","year":"2019","unstructured":"Cayci, S., Eryilmaz, A., & Srikant, R. (2019). Learning to control renewal processes with bandit feedback. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2), 1\u201332.","journal-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems"},{"key":"6271_CR17","unstructured":"Cayci, S., Eryilmaz, A., & Srikant, R. (2020). Budget-constrained bandits over general cost and reward distributions. In AISTATS (pp. 4388\u20134398)."},{"issue":"1","key":"6271_CR18","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1109\/TIT.2014.2365772","volume":"61","author":"N Cesa-Bianchi","year":"2014","unstructured":"Cesa-Bianchi, N., Gentile, C., & Mansour, Y. (2014). Regret minimization for reserve prices in second-price auctions. IEEE Transactions on Information Theory, 61(1), 549\u2013564.","journal-title":"IEEE Transactions on Information Theory"},{"key":"6271_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, learning, and games","author":"N Cesa-Bianchi","year":"2006","unstructured":"Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press."},{"issue":"5","key":"6271_CR20","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1016\/j.jcss.2012.01.001","volume":"78","author":"N Cesa-Bianchi","year":"2012","unstructured":"Cesa-Bianchi, N., & Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences, 78(5), 1404\u20131422.","journal-title":"Journal of Computer and System Sciences"},{"key":"6271_CR21","unstructured":"Dagan, Y., & Koby, C. (2018). A better resource allocation algorithm with semi-bandit feedback. In ALT (pp. 268\u2013320)."},{"key":"6271_CR22","doi-asserted-by":"crossref","unstructured":"Degroote, H. (2017). Online algorithm selection. In IJCAI (pp. 5173\u20135174).","DOI":"10.24963\/ijcai.2017\/746"},{"key":"6271_CR23","doi-asserted-by":"crossref","unstructured":"Degroote, H., Causmaecker, P. D., Bischl, B., & Kotthoff, L. (2018). A regression-based methodology for online algorithm selection. In Proceedings of the Eleventh International Symposium on Combinatorial Search, SOCS 2018 (pp. 37\u201345).","DOI":"10.1609\/socs.v9i1.18458"},{"issue":"8","key":"6271_CR24","doi-asserted-by":"publisher","first-page":"2493","DOI":"10.1109\/TNNLS.2018.2885123","volume":"30","author":"M Drugan","year":"2019","unstructured":"Drugan, M. (2019). Covariance matrix adaptation for multiobjective multiarmed bandits. IEEE Transactions on Neural Networks and Learning Systems, 30(8), 2493\u20132502.","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"6271_CR25","unstructured":"Gabillon, V., Ghavamzadeh, M., Lazaric, A., & Bubeck, S. (2011). Multi-bandit best arm identification. In NeurIPS (pp. 2222\u20132230)."},{"key":"6271_CR26","unstructured":"Gagliolo, M., & Schmidhuber, J. (2007). Learning restart strategies. In IJCAI (pp. 792\u2013797)."},{"key":"6271_CR27","doi-asserted-by":"crossref","unstructured":"Gagliolo, M., & Schmidhuber, J. (2010). Algorithm selection as a bandit problem with unbounded losses. In International Conference on Learning and Intelligent Optimization (LION) (pp. 82\u201396). Springer.","DOI":"10.1007\/978-3-642-13800-3_7"},{"key":"6271_CR28","unstructured":"Grill, J.B., Valko, M., & Munos, R. (2015). Black-box optimization of noisy functions with unknown smoothness. In NeurIPS (pp. 667\u2013675)."},{"key":"6271_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-05318-5","volume-title":"Automated machine learning: Methods, systems, challenges","author":"F Hutter","year":"2019","unstructured":"Hutter, F., Kotthoff, L., & Vanschoren, J. (2019). Automated machine learning: Methods, systems, challenges. Springer."},{"key":"6271_CR30","unstructured":"Jain, L., & Jamieson, K. (2018). Firing bandits: Optimizing crowdfunding. In ICML (pp. 2206\u20132214)."},{"key":"6271_CR31","unstructured":"Joulani, P., Gy\u00f6rgy, A., & Szepesv\u00e1ri, C. (2013). Online learning under delayed feedback. In ICML (pp. 1453\u20131461)."},{"issue":"1","key":"6271_CR32","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1162\/evco_a_00242","volume":"27","author":"P Kerschke","year":"2019","unstructured":"Kerschke, P., Hoos, H., Neumann, F., & Trautmann, H. (2019). Automated algorithm selection: Survey and perspectives. Evolutionary Computation, 27(1), 3\u201345.","journal-title":"Evolutionary Computation"},{"key":"6271_CR33","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Slivkins, A., & Upfal, E. (2008). Multi-armed bandits in metric spaces. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (pp. 681\u2013690).","DOI":"10.1145\/1374376.1374475"},{"key":"6271_CR34","unstructured":"Lattimore, T., Crammer, K., & Szepesv\u00e1ri, C. (2014). Optimal resource allocation with semi-bandit feedback. In UAI (pp. 477\u2013486)."},{"key":"6271_CR35","unstructured":"Lattimore, T., Crammer, K., & Szepesv\u00e1ri, C. (2015). Linear multi-resource allocation with semi-bandit feedback. In NeurIPS (pp. 964\u2013972)."},{"key":"6271_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401","volume-title":"Bandit algorithms","author":"T Lattimore","year":"2020","unstructured":"Lattimore, T., & Szepesv\u00e1ri, C. (2020). Bandit algorithms. Cambridge University Press."},{"key":"6271_CR37","doi-asserted-by":"crossref","unstructured":"Mandel, T., Liu, Y.E., Brunskill, E., & Popovi\u0107, Z. (2015). The queue method: Handling delay, heuristics, prior data, and evaluation in bandits. In AAAI (pp. 2849\u20132856).","DOI":"10.1609\/aaai.v29i1.9604"},{"issue":"1","key":"6271_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000038","volume":"7","author":"R Munos","year":"2014","unstructured":"Munos, R. (2014). From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends\u00ae in Machine Learning, 7(1), 1\u2013129.","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"6271_CR39","unstructured":"Pike-Burke, C., Agrawal, S., Szepesvari, C., & Grunewalder, S. (2018). Bandits with delayed, aggregated anonymous feedback. In ICML (pp. 4105\u20134113)."},{"key":"6271_CR40","doi-asserted-by":"crossref","unstructured":"Schede, E., Brandt, J., Tornede, A., Wever, M., Bengs, V., H\u00fcllermeier, E., & Tierney, K. (2022). A survey of methods for automated algorithm configuration. arXiv preprint arXiv:2202.01651.","DOI":"10.1613\/jair.1.13676"},{"key":"6271_CR41","unstructured":"Sharoff, P., Mehta, N., & Ganti, R. (2020). A farewell to arms: Sequential reward maximization on a budget with a giving up option. In AISTATS (pp. 3707\u20133716)."},{"issue":"1\u20132","key":"6271_CR42","first-page":"1","volume":"12","author":"A Slivkins","year":"2019","unstructured":"Slivkins, A. (2019). Introduction to multi-armed bandits. Foundations and Trends \u00ae in Machine Learning, 12(1\u20132), 1\u2013286.","journal-title":"Foundations and Trends \u00ae in Machine Learning"},{"issue":"3","key":"6271_CR43","first-page":"1","volume":"22","author":"S Trac\u00e0","year":"2021","unstructured":"Trac\u00e0, S., & Rudin, C. (2021). Regulating greed over time in multi-armed bandits. Journal of Machine Learning Research, 22(3), 1\u201399.","journal-title":"Journal of Machine Learning Research"},{"issue":"9","key":"6271_CR47","doi-asserted-by":"publisher","first-page":"10370","DOI":"10.1609\/aaai.v36i9.21279","volume":"36","author":"Alexander Tornede","year":"2022","unstructured":"Tornede, A., Bengs, V., & H\u00fcllermeier, E. (2022). Machine learning for online algorithm selection under censored feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9) 10370\u201310380. https:\/\/doi.org\/10.1609\/aaai.v36i9.21279","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"6271_CR44","unstructured":"Verma, A., Hanawal, M., Rajkumar, A., & Sankaran, R. (2019). Censored semi-bandits: A framework for resource allocation with censored feedback. In NeurIPS (pp. 14526\u201314536)."},{"key":"6271_CR45","unstructured":"Vernade, C., Capp\u00e9, O., & Perchet, V. (2017). Stochastic bandit models for delayed conversions. In UAI."},{"key":"6271_CR46","doi-asserted-by":"crossref","unstructured":"Yue, Y., & Joachims, T. (2009). Interactively optimizing information retrieval systems as a dueling bandits problem. In ICML (pp. 1201\u20131208).","DOI":"10.1145\/1553374.1553527"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06271-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06271-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06271-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T01:06:59Z","timestamp":1674349619000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06271-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,16]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["6271"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06271-z","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,16]]},"assertion":[{"value":"15 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}