{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:35:16Z","timestamp":1780497316611,"version":"3.54.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T00:00:00Z","timestamp":1560902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000774","name":"Defense Threat Reduction Agency","doi-asserted-by":"publisher","award":["HDTRA1-15-1-0003, HDTRA1-18-1-0050"],"award-info":[{"award-number":["HDTRA1-15-1-0003, HDTRA1-18-1-0050"]}],"id":[{"id":"10.13039\/100000774","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-NeTS-1514260, CNS-NeTS-1717045, CMMI-SMOR-1562065, CNS-ICN-WEN-1719371, CNS-SpecEES-1824337"],"award-info":[{"award-number":["CNS-NeTS-1514260, CNS-NeTS-1717045, CMMI-SMOR-1562065, CNS-ICN-WEN-1719371, CNS-SpecEES-1824337"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,6,19]]},"abstract":"<jats:p>We consider a bandit problem with K task types from which the controller activates one task at a time. Each task takes a random and possibly heavy-tailed completion time, and a reward is obtained only after the task is completed. The task types are independent from each other, and have distinct and unknown distributions for completion time and reward. For a given time horizon \u03c4, the goal of the controller is to schedule tasks adaptively so as to maximize the reward collected until \u03c4 expires. In addition, we allow the controller to interrupt a task and initiate a new one. In addition to the traditional exploration-exploitation dilemma, this interrupt mechanism introduces a new one: should the controller complete the task and get the reward, or interrupt the task for a possibly shorter and more rewarding alternative? We show that for all heavy-tailed and some light-tailed completion time distributions, this interruption mechanism improves the reward linearly over time. Applications of this model include server scheduling, optimal free sampling strategies in advertising and adaptive content selection. From a learning perspective, the interrupt mechanism necessitates learning the whole arm distribution from truncated observations. For this purpose, we propose a robust learning algorithm named UCB-BwI based on median-of-means estimator for possibly heavy-tailed reward and completion time distributions. We show that, in a K-armed bandit setting with an arbitrary set of L possible interrupt times, UCB-BwI achieves O(K\u0142og(\u03c4)+KL) regret. We also prove that the regret under any admissible policy is \u00d8mega(K\u0142og(\u03c4)), which implies that UCB-BwI is order optimal.<\/jats:p>","DOI":"10.1145\/3341617.3326158","type":"journal-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:18:56Z","timestamp":1561033136000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Learning to Control Renewal Processes with Bandit Feedback"],"prefix":"10.1145","volume":"3","author":[{"given":"Semih","family":"Cayci","sequence":"first","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Atilla","family":"Eryilmaz","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Srikant","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1987.1104485"},{"key":"e_1_2_1_2_1","volume-title":"Applied probability and queues","author":"Asmussen S\u00f8ren","unstructured":"S\u00f8ren Asmussen. 2008. Applied probability and queues. Vol. 51. Springer Science & Business Media."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.30"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03459"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879175"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-3711-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601986276"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2277869"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032374755"},{"key":"e_1_2_1_10_1","volume-title":"Probabilit\u00e9s et Statistiques","volume":"48","author":"Olivier","unstructured":"Olivier Catoni et al. 2012. Challenging the empirical mean and empirical variance: a deviation study. In Annales de l'Institut Henri Poincar\u00e9, Probabilit\u00e9s et Statistiques, Vol. 48. Institut Henri Poincar\u00e9, 1148--1185."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.01.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848225"},{"key":"e_1_2_1_13_1","unstructured":"Varsha Dani Thomas P Hayes and Sham M Kakade. 2008. Stochastic linear optimization under bandit feedback. (2008)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.15"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/505202.505230"},{"key":"e_1_2_1_16_1","volume-title":"Stochastic processes: theory for applications","author":"Gallager Robert G","unstructured":"Robert G Gallager. 2013. Stochastic processes: theory for applications .Cambridge University Press."},{"key":"e_1_2_1_17_1","volume-title":"Low-Regret Link Rate Selection in Rapidly-Varying Wireless Channels. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 540--548","author":"Gupta Harsh","year":"2018","unstructured":"Harsh Gupta, Atilla Eryilmaz, and R Srikant. 2018. Low-Complexity, Low-Regret Link Rate Selection in Rapidly-Varying Wireless Channels. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 540--548."},{"key":"e_1_2_1_18_1","volume-title":"Stopped random walks","author":"Gut Allan","unstructured":"Allan Gut. 2009. Stopped random walks .Springer."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gy\u00f6rgy Levente Kocsis Ivett Szab\u00f3 and Csaba Szepesv\u00e1ri. 2007. Continuous Time Associative Bandit Problems.. In IJCAI. 830--835.","DOI":"10.5555\/1625275.1625409"},{"key":"e_1_2_1_20_1","volume-title":"Proc. of ASA-IMS Conf. on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics .","author":"Harchol-Balter Mor","year":"1999","unstructured":"Mor Harchol-Balter. 1999. The E ect of Heavy-Tailed Job Size Distributions on Computer System Design.. In Proc. of ASA-IMS Conf. on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics ."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1363354105"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3042817.3043099"},{"key":"e_1_2_1_23_1","volume-title":"Multi-armed bandits in discrete and continuous time. Annals of Applied Probability","author":"Kaspi Haya","year":"1998","unstructured":"Haya Kaspi and Avishai Mandelbaum. 1998. Multi-armed bandits in discrete and continuous time. Annals of Applied Probability (1998), 1270--1290."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5178-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120206"},{"key":"e_1_2_1_27_1","volume-title":"Continuous multi-armed bandits and multiparameter processes. The Annals of Probability","author":"Mandelbaum Avi","year":"1987","unstructured":"Avi Mandelbaum. 1987. Continuous multi-armed bandits and multiparameter processes. The Annals of Probability (1987), 1527--1556."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.3150\/14-BEJ645"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2466587"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1069362376"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1215956.1215967"},{"key":"e_1_2_1_33_1","series-title":"Series B (Methodological)","volume-title":"Multi-armed bandits and the Gittins index. Journal of the Royal Statistical Society","author":"Whittle Peter","year":"1980","unstructured":"Peter Whittle. 1980. Multi-armed bandits and the Gittins index. Journal of the Royal Statistical Society. Series B (Methodological) (1980), 143--149."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Yingce Xia Haifang Li Tao Qin Nenghai Yu and Tie-Yan Liu. 2015. Thompson Sampling for Budgeted Multi-Armed Bandits.. In IJCAI. 3960--3966.","DOI":"10.5555\/2832747.2832801"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Yingce Xia Tao Qin Weidong Ma Nenghai Yu and Tie-Yan Liu. 2016. Budgeted Multi-Armed Bandits with Multiple Plays. In IJCAI. 2210--2216.","DOI":"10.5555\/3060832.3060930"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326158","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341617.3326158","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341617.3326158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:29Z","timestamp":1750200089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,19]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,19]]}},"alternative-id":["10.1145\/3341617.3326158"],"URL":"https:\/\/doi.org\/10.1145\/3341617.3326158","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,19]]},"assertion":[{"value":"2019-06-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}