{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:10:27Z","timestamp":1780089027849,"version":"3.54.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T00:00:00Z","timestamp":1780012800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2045641"],"award-info":[{"award-number":["2045641"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["2325956"],"award-info":[{"award-number":["2325956"]}]},{"name":"National Science Foundation","award":["2512128"],"award-info":[{"award-number":["2512128"]}]},{"name":"National Science Foundation","award":["2533814"],"award-info":[{"award-number":["2533814"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,5,29]]},"abstract":"<jats:p>\n                    We study the problem of sequentially allocating a reusable resource to stochastically arriving tasks whose rewards and durations are both random with unknown statistics. Upon each observable arrival (i.e., when the resource is idle), the task type and duration are revealed, and the decision-maker must immediately choose whether to accept or reject the task; noisy reward feedback is revealed only after making the decision. Arrivals that occur while the resource is busy are not observed. This setting captures practical admission-control problems with reusable resources, such as cloud job scheduling, crowdsourcing, and other partially observable service systems in which accepting a task temporarily makes a server or worker unavailable. We first establish a fundamental limit for the full-information offline (prophet) benchmark: no non-anticipatory online algorithm can guarantee more than a (1\/2) fraction of (\n                    <jats:bold>E<\/jats:bold>\n                    [\n                    <jats:italic toggle=\"yes\">OPT<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    )]), even when the reward and duration distributions are known. This impossibility motivates our use of (1\/2)-approximate regret, namely the additive gap to (1 over 2\n                    <jats:bold>E<\/jats:bold>\n                    [\n                    <jats:italic toggle=\"yes\">OPT<\/jats:italic>\n                    (\n                    <jats:bold>T<\/jats:bold>\n                    )]). To develop online algorithms, we first derive an infinite-dimensional linear program (LP) through a steady-state analysis, establishing an upper bound on the expected reward of offline optimum. The structure of this LP motivates a simple and effective threshold-based policy: a task is accepted only if its ''profitability'', defined as the ratio of its reward to its duration plus the expected waiting time, exceeds a specific threshold. Motivated by this insight, we develop online algorithms that estimate the profitability threshold from observed task arrivals. As a warm-up, we first propose an algorithm for the setting where the reward functions are known, and show that it achieves an 1\/2-approximate regret of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\u221a\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    ). We then extend the algorithm to the fully online learning setting with unknown reward functions, where we incorporate a nonparametric estimation procedure to learn the reward functions. The resulting algorithm preserves the 1\/2-competitive ratio and attains an 1\/2-approximate regret of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    <jats:sup>2\/3<\/jats:sup>\n                    ). Finally, we show that when task durations are also unobservable upon arrival and are revealed only after task completion, the problem fundamentally degenerates and no meaningful competitive guarantee is achievable. We demonstrate that by augmenting the model with a termination mechanism (allowing interrupting an ongoing task at the cost of losing its reward), the same order of approximate regret can be recovered.\n                  <\/jats:p>","DOI":"10.1145\/3805641","type":"journal-article","created":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:34:18Z","timestamp":1780086858000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning to Allocate Reusable Resources under Stochastic Rewards and Durations"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2858-0604","authenticated-orcid":false,"given":"Ativ","family":"Joshi","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5016-4281","authenticated-orcid":false,"given":"Qingsong","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-2254","authenticated-orcid":false,"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399484"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_2_1_4_1","volume-title":"International Conference on Machine Learning. PMLR, 404-413","author":"Atsidakou Alexia","year":"2021","unstructured":"Alexia Atsidakou, Orestis Papadigenopoulos, Soumya Basu, Constantine Caramanis, and Sanjay Shakkottai. 2021. Combinatorial blocking bandits with stochastic delays. In International Conference on Machine Learning. PMLR, 404-413."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.100"},{"key":"e_1_2_1_6_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 271-279","author":"Basu Soumya","year":"2021","unstructured":"Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. 2021. Contextual blocking bandits. In International Conference on Artificial Intelligence and Statistics. PMLR, 271-279."},{"key":"e_1_2_1_7_1","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Basu Soumya","year":"2019","unstructured":"Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. 2019. Blocking bandits. Advances in Neural Information Processing Systems, Vol. 32 (2019)."},{"key":"e_1_2_1_8_1","first-page":"8139","article-title":"Adversarial blocking bandits","volume":"33","author":"Bishop Nicholas","year":"2020","unstructured":"Nicholas Bishop, Hau Chan, Debmalya Mandal, and Long Tran-Thanh. 2020. Adversarial blocking bandits. Advances in Neural Information Processing Systems, Vol. 33 (2020), 8139-8149.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_9_1","unstructured":"Etienne Boursier Vianney Perchet and Alexandre Proutiere. 2021. Making the Most of Your Day: Online Learning for Optimal Allocation of Time. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1298-1325","author":"Caramanis Constantine","year":"2022","unstructured":"Constantine Caramanis, Paul D\u00fctting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenh\u00e4user. 2022. Single-sample prophet inequalities via greedy-ordered selection. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1298-1325."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341617.3326158"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.0612"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0270"},{"key":"e_1_2_1_15_1","volume-title":"Great expectations: the theory of optimal stopping","author":"Chow YS","year":"1971","unstructured":"YS Chow, H Robbins, and D Siegmund. [n.d.]. Great expectations: the theory of optimal stopping, 1971. Boston (Mass.) ([n.d.])."},{"key":"e_1_2_1_16_1","unstructured":"City of Chicago. 2024. Taxi Trips - 2024. https:\/\/data.cityofchicago.org\/Transportation\/Taxi-Trips-2024-\/ajtu-isnz\/about_data. Accessed: 2024-06-11."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329627"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.127"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456756"},{"key":"e_1_2_1_20_1","first-page":"3","article-title":"Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources","volume":"9","author":"Dickerson John P.","year":"2021","unstructured":"John P. Dickerson, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu. 2021b. Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources. ACM Transactions on Economics and Computation, Vol. 9, 3 (June 2021). https:\/\/arxiv.org\/abs\/1711.08345","journal-title":"ACM Transactions on Economics and Computation"},{"key":"e_1_2_1_21_1","article-title":"Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-Sided Arrivals","volume":"12","author":"Dickerson John P.","year":"2024","unstructured":"John P. Dickerson, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu. 2024. Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-Sided Arrivals. ACM Transactions on Economics and Computation, Vol. 12, 1 (2024).","journal-title":"ACM Transactions on Economics and Computation"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399513"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530893"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.0687"},{"key":"e_1_2_1_27_1","first-page":"631","volume-title":"Patras","author":"Fiat Amos","year":"2015","unstructured":"Amos Fiat, Ilia Gorelik, Haim Kaplan, and Slava Novgorodov. 2015. The temp secretary problem. In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, 631-642."},{"key":"e_1_2_1_28_1","volume-title":"International Conference on Machine Learning. PMLR, 10265-10284","author":"Foussoul Ayoub","year":"2023","unstructured":"Ayoub Foussoul, Vineet Goyal, Orestis Papadigenopoulos, and Assaf Zeevi. 2023. Last switch dependent bandits with monotone payoff functions. In International Conference on Machine Learning. PMLR, 10265-10284."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2021.4134"},{"key":"e_1_2_1_30_1","volume-title":"Online allocation of reusable resources via algorithms guided by fluid approximations. arXiv preprint arXiv:2010.03983","author":"Goyal Vineet","year":"2020","unstructured":"Vineet Goyal, Garud Iyengar, and Rajan Udwani. 2020. Online allocation of reusable resources via algorithms guided by fluid approximations. arXiv preprint arXiv:2010.03983 (2020)."},{"key":"e_1_2_1_31_1","volume-title":"Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research","author":"Goyal Vineet","year":"2025","unstructured":"Vineet Goyal, Garud Iyengar, and Rajan Udwani. 2025. Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research (2025)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_2_1_33_1","first-page":"58","article-title":"Automated online mechanism design and prophet inequalities","volume":"7","author":"Hajiaghayi Mohammad Taghi","year":"2007","unstructured":"Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. 2007. Automated online mechanism design and prophet inequalities. In AAAI, Vol. 7. 58-65.","journal-title":"AAAI"},{"key":"e_1_2_1_34_1","volume-title":"Online reusable resource allocations with multi-class arrivals. Available at SSRN 4320423","author":"Huo Tianming","year":"2022","unstructured":"Tianming Huo and Wang Chi Cheung. 2022. Online reusable resource allocations with multi-class arrivals. Available at SSRN 4320423 (2022)."},{"key":"e_1_2_1_35_1","volume-title":"Online reusable resource assortment planning with customer-dependent usage durations. Available at SSRN 4504713","author":"Huo Tianming","year":"2023","unstructured":"Tianming Huo and Wang Chi Cheung. 2023. Online reusable resource assortment planning with customer-dependent usage durations. Available at SSRN 4504713 (2023)."},{"key":"e_1_2_1_36_1","first-page":"8937","article-title":"Bandit task assignment with unknown processing time","volume":"36","author":"Ito Shinji","year":"2023","unstructured":"Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. 2023. Bandit task assignment with unknown processing time. Advances in Neural Information Processing Systems, Vol. 36 (2023), 8937-8957.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_37_1","volume-title":"Sparse Linear Bandits with Blocking Constraints. arXiv preprint arXiv:2410.20041","author":"Jain Adit","year":"2024","unstructured":"Adit Jain, Soumyabrata Pal, Sunav Choudhary, Ramasuri Narayanam, Harshita Chopra, and Vikram Krishnamurthy. 2024. Sparse Linear Bandits with Blocking Constraints. arXiv preprint arXiv:2410.20041 (2024)."},{"key":"e_1_2_1_38_1","first-page":"54","volume-title":"Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions. In 24th Annual European Symposium on Algorithms (ESA","author":"Kesselheim Thomas","year":"2016","unstructured":"Thomas Kesselheim and Andreas T\u00f6nnis. 2016. Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 54-1."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0714"},{"key":"e_1_2_1_42_1","volume-title":"IEEE INFOCOM 2023-IEEE Conference on Computer Communications. IEEE, 1-10","author":"Liu Qingsong","year":"2023","unstructured":"Qingsong Liu and Zhixuan Fang. 2023. Learning to schedule tasks with deadline and throughput constraints. In IEEE INFOCOM 2023-IEEE Conference on Computer Communications. IEEE, 1-10."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3727121"},{"key":"e_1_2_1_44_1","volume-title":"Conference on Learning Theory. PMLR, 975-999","author":"Magureanu Stefan","year":"2014","unstructured":"Stefan Magureanu, Richard Combes, and Alexandre Proutiere. 2014. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory. PMLR, 975-999."},{"key":"e_1_2_1_45_1","volume-title":"Redesigning VolunteerMatch's Search Algorithm: Toward More Equitable Access to Volunteers. Available at SSRN 4497747","author":"Manshadi Vahideh","year":"2023","unstructured":"Vahideh Manshadi, Scott Rodilitz, Daniela Saban, and Akshaya Suresh. 2023. Redesigning VolunteerMatch's Search Algorithm: Toward More Equitable Access to Volunteers. Available at SSRN 4497747 (2023)."},{"key":"e_1_2_1_46_1","first-page":"25281","article-title":"Blocked collaborative bandits: online collaborative filtering with per-item budget constraints","volume":"36","author":"Pal Soumyabrata","year":"2023","unstructured":"Soumyabrata Pal, Arun Suggala, Karthikeyan Shanmugam, and Prateek Jain. 2023. Blocked collaborative bandits: online collaborative filtering with per-item budget constraints. Advances in Neural Information Processing Systems, Vol. 36 (2023), 25281-25324.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897540"},{"key":"e_1_2_1_48_1","volume-title":"Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability","author":"Samuel-Cahn Ester","year":"1984","unstructured":"Ester Samuel-Cahn. 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability (1984), 1213-1216."},{"key":"e_1_2_1_49_1","volume-title":"Optimal stopping rules","author":"Shiryaev Albert N","unstructured":"Albert N Shiryaev. 2008. Optimal stopping rules. Springer."},{"key":"e_1_2_1_50_1","volume-title":"Asymptotic statistics","author":"Van der Vaart Aad W","unstructured":"Aad W Van der Vaart. 2000. Asymptotic statistics. Vol. 3. Cambridge university press."},{"key":"e_1_2_1_51_1","volume-title":"Reinforcement learning algorithm for reusable resource allocation with time-varying reward. Available at SSRN 4680309","author":"Wang Ziwei","year":"2023","unstructured":"Ziwei Wang, Jingtong Zhao, Yixuan Liu, and Jie Song. 2023. Reinforcement learning algorithm for reusable resource allocation with time-varying reward. Available at SSRN 4680309 (2023)."},{"key":"e_1_2_1_52_1","first-page":"231","article-title":"Admission Control of Service Requests in High-Speed Networks","volume":"50","author":"Wu Cynara C.","year":"2001","unstructured":"Cynara C. Wu and Dimitri P. Bertsekas. 2001. Admission Control of Service Requests in High-Speed Networks. IEEE Transactions on Vehicular Technology, Vol. 50, 1 (2001), 231-242.","journal-title":"IEEE Transactions on Vehicular Technology"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.0429"},{"key":"e_1_2_1_54_1","volume-title":"Learning to Schedule Online Tasks with Bandit Feedback. arXiv preprint arXiv:2402.16463","author":"Xu Yongxin","year":"2024","unstructured":"Yongxin Xu, Shangshang Wang, Hengquan Guo, Xin Liu, and Ziyu Shao. 2024. Learning to Schedule Online Tasks with Bandit Feedback. arXiv preprint arXiv:2402.16463 (2024)."},{"key":"e_1_2_1_55_1","first-page":"100","article-title":"Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates","volume":"30","author":"Yang Yuhong","year":"2002","unstructured":"Yuhong Yang and Dan Zhu. 2002. Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates. The Annals of Statistics, Vol. 30, 1 (2002), 100-121.","journal-title":"The Annals of Statistics"},{"key":"e_1_2_1_56_1","volume-title":"Online resource allocation for reusable resources. arXiv preprint arXiv:2212.02855","author":"Zhang Xilin","year":"2022","unstructured":"Xilin Zhang and Wang Chi Cheung. 2022. Online resource allocation for reusable resources. arXiv preprint arXiv:2212.02855 (2022)."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3805641","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3805641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:39:15Z","timestamp":1780087155000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3805641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,29]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,29]]}},"alternative-id":["10.1145\/3805641"],"URL":"https:\/\/doi.org\/10.1145\/3805641","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,29]]},"assertion":[{"value":"2026-05-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}