{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T18:32:11Z","timestamp":1763058731932,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"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":["1826320, 2019844, 2112471"],"award-info":[{"award-number":["1826320, 2019844, 2112471"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program"},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-1-2566"],"award-info":[{"award-number":["N00014-19-1-2566"]}],"id":[{"id":"10.13039\/100000006","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":[[2022,5,26]]},"abstract":"<jats:p>Considerable work has focused on optimal stopping problems where random IID offers arrive sequentially for a single available resource which is controlled by the decision-maker. After viewing the realization of the offer, the decision-maker irrevocably rejects it, or accepts it, collecting the reward and ending the game. We consider an important extension of this model to a dynamic setting where the resource is \"renewable'' (a rental, a work assignment, or a temporary position) and can be allocated again after a delay period d. In the case where the reward distribution is known a priori, we design an (asymptotically optimal) 1\/2-competitive Prophet Inequality, namely, a policy that collects in expectation at least half of the expected reward collected by a prophet who a priori knows all the realizations. This policy has a particularly simple characterization as a thresholding rule which depends on the reward distribution and the blocking period d, and arises naturally from an LP-relaxation of the prophet's optimal solution. Moreover, it gives the key for extending to the case of unknown distributions; here, we construct a dynamic threshold rule using the reward samples collected when the resource is not blocked. We provide a regret guarantee for our algorithm against the best policy in hindsight, and prove a complementing minimax lower bound on the best achievable regret, establishing that our policy achieves, up to poly-logarithmic factors, the best possible regret in this setting.<\/jats:p>","DOI":"10.1145\/3530893","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T17:16:18Z","timestamp":1654535778000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Learning To Maximize Welfare with a Reusable Resource"],"prefix":"10.1145","volume":"6","author":[{"given":"Matthew","family":"Faw","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]},{"given":"Orestis","family":"Papadigenopoulos","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]},{"given":"Constantine","family":"Caramanis","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]},{"given":"Sanjay","family":"Shakkottai","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055479"},{"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","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.100"},{"key":"e_1_2_1_5_1","unstructured":"Soumya Basu Orestis Papadigenopoulos Constantine Caramanis and Sanjay Shakkottai. 2021. Contextual blocking bandits. In Int'l Conf. on Artificial Intelligence and Statistics. PMLR 271--279.  Soumya Basu Orestis Papadigenopoulos Constantine Caramanis and Sanjay Shakkottai. 2021. Contextual blocking bandits. In Int'l Conf. on Artificial Intelligence and Statistics. PMLR 271--279."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535278"},{"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.1137\/1.9781611977073.54"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_1_10_1","volume-title":"An online learning approach to dynamic pricing and capacity sizing in service systems. arxiv","author":"Chen Xinyun","year":"2009","unstructured":"Xinyun Chen , Yunan Liu , and Guiyu Hong . 2020. An online learning approach to dynamic pricing and capacity sizing in service systems. arxiv : 2009 .02911 [math.PR] Xinyun Chen, Yunan Liu, and Guiyu Hong. 2020. An online learning approach to dynamic pricing and capacity sizing in service systems. arxiv: 2009.02911 [math.PR]"},{"key":"e_1_2_1_11_1","volume-title":"Herbert Ellis Robbins, and David Siegmund","author":"Chow Yuan Shih","year":"1971","unstructured":"Yuan Shih Chow , Herbert Ellis Robbins, and David Siegmund . 1971 . Great expectations: The theory of optimal stopping. Yuan Shih Chow, Herbert Ellis Robbins, and David Siegmund. 1971. Great expectations: The theory of optimal stopping."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329627"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"b","volume":"17","author":"Correa Jose","year":"2019","unstructured":"Jose Correa , Patricio Foncea , Ruben Hoeksma , Tim Oosterwijk , and Tjark Vredeveld . 2019 b . Recent Developments in Prophet Inequalities. SIGecom Exch. , Vol. 17 , 1 (May 2019), 61--70. Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. 2019 b. Recent Developments in Prophet Inequalities. SIGecom Exch. , Vol. 17, 1 (May 2019), 61--70.","journal-title":"Recent Developments in Prophet Inequalities. SIGecom Exch."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2020 ACM-SIAM Symp. on Discrete Algorithms, SODA 2020","author":"Correa Jos\u00e9 R.","year":"2020","unstructured":"Jos\u00e9 R. Correa , Andr\u00e9 s Cristi , Boris Epstein , and Jos\u00e9 A. Soto . 2020. The Two-Sided Game of Googol and Sample-Based Prophet Inequalities . In Proceedings of the 2020 ACM-SIAM Symp. on Discrete Algorithms, SODA 2020 , Salt Lake City, UT, USA, January 5--8 , 2020 . 2066--2081. Jos\u00e9 R. Correa, Andr\u00e9 s Cristi, Boris Epstein, and Jos\u00e9 A. Soto. 2020. The Two-Sided Game of Googol and Sample-Based Prophet Inequalities. In Proceedings of the 2020 ACM-SIAM Symp. on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5--8, 2020. 2066--2081."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456756"},{"volume-title":"Concentration of measure for the analysis of randomized algorithms","author":"Dubhashi Devdatt P","key":"e_1_2_1_17_1","unstructured":"Devdatt P Dubhashi and Alessandro Panconesi . 2009. Concentration of measure for the analysis of randomized algorithms . Cambridge University Press . Devdatt P Dubhashi and Alessandro Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms .Cambridge University Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_2_1_19_1","volume-title":"Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics","author":"Dvoretzky Aryeh","year":"1956","unstructured":"Aryeh Dvoretzky , Jack Kiefer , and Jacob Wolfowitz . 1956. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics ( 1956 ), 642--669. Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. 1956. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics (1956), 642--669."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399513"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884507"},{"volume-title":"Algorithms-ESA 2015","author":"Fiat Amos","key":"e_1_2_1_22_1","unstructured":"Amos Fiat , Ilia Gorelik , Haim Kaplan , and Slava Novgorodov . 2015. The temp secretary problem . In Algorithms-ESA 2015 . Springer , 631--642. Amos Fiat, Ilia Gorelik, Haim Kaplan, and Slava Novgorodov. 2015. The temp secretary problem. In Algorithms-ESA 2015 . Springer, 631--642."},{"volume-title":"Online Assortment Optimization with Reusable Resources. Management Science","author":"Gong Xiao-Yue","key":"e_1_2_1_23_1","unstructured":"Xiao-Yue Gong , Vineet Goyal , Garud N. Iyengar , David Simchi-Levi , Rajan Udwani , and Shuangyu Wang . 0. Online Assortment Optimization with Reusable Resources. Management Science , Vol. 0 , 0 ( 0), null. Xiao-Yue Gong, Vineet Goyal, Garud N. Iyengar, David Simchi-Levi, Rajan Udwani, and Shuangyu Wang. 0. Online Assortment Optimization with Reusable Resources. Management Science , Vol. 0, 0 ( 0), null."},{"key":"e_1_2_1_24_1","volume-title":"Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources. arxiv","author":"Goyal Vineet","year":"2002","unstructured":"Vineet Goyal , Garud Iyengar , and Rajan Udwani . 2021. Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources. arxiv : 2002 .02430 [cs.DS] Vineet Goyal, Garud Iyengar, and Rajan Udwani. 2021. Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources. arxiv: 2002.02430 [cs.DS]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_2_1_26_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 . 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_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"e_1_2_1_28_1","article-title":"Near-optimal Regret Bounds for Reinforcement Learning","volume":"11","author":"Jaksch Thomas","year":"2010","unstructured":"Thomas Jaksch , Ronald Ortner , and Peter Auer . 2010 . Near-optimal Regret Bounds for Reinforcement Learning . Journal of Machine Learning Research , Vol. 11 , 4 (2010). Thomas Jaksch, Ronald Ortner, and Peter Auer. 2010. Near-optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research , Vol. 11, 4 (2010).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_29_1","volume-title":"Think eternally: Improved algorithms for the temp secretary problem and extensions. arXiv preprint arXiv:1606.06926","author":"Kesselheim Thomas","year":"2016","unstructured":"Thomas Kesselheim and Andreas T\u00f6nnis . 2016. Think eternally: Improved algorithms for the temp secretary problem and extensions. arXiv preprint arXiv:1606.06926 ( 2016 ). Thomas Kesselheim and Andreas T\u00f6nnis. 2016. Think eternally: Improved algorithms for the temp secretary problem and extensions. arXiv preprint arXiv:1606.06926 (2016)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_2_1_32_1","volume-title":"On semiamarts, amarts, and processes with finite value. Probability on Banach Spaces (01","author":"Krengel Ulrich","year":"1978","unstructured":"Ulrich Krengel and Louis Sucheston . 1978. On semiamarts, amarts, and processes with finite value. Probability on Banach Spaces (01 1978 ), 197--266. Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Probability on Banach Spaces (01 1978), 197--266."},{"key":"e_1_2_1_33_1","unstructured":"Kailasam Lakshmanan Ronald Ortner and Daniil Ryabko. 2015. Improved regret bounds for undiscounted continuous reinforcement learning. In Int'l Conf. on Machine Learning. PMLR 524--532.  Kailasam Lakshmanan Ronald Ortner and Daniil Ryabko. 2015. Improved regret bounds for undiscounted continuous reinforcement learning. In Int'l Conf. on Machine Learning. PMLR 524--532."},{"volume-title":"Bandit Algorithms","author":"Lattimore Tor","key":"e_1_2_1_34_1","unstructured":"Tor Lattimore and Csaba Szepesv\u00e1ri . 2020. Bandit Algorithms . Cambridge University Press . https:\/\/doi.org\/10.1017\/9781108571401 10.1017\/9781108571401 Tor Lattimore and Csaba Szepesv\u00e1ri. 2020. Bandit Algorithms .Cambridge University Press. https:\/\/doi.org\/10.1017\/9781108571401"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0714"},{"volume-title":"Markov chains and mixing times","author":"Levin David A","key":"e_1_2_1_36_1","unstructured":"David A Levin and Yuval Peres . 2017. Markov chains and mixing times . Vol. 107 . American Mathematical Soc . David A Levin and Yuval Peres. 2017. Markov chains and mixing times . Vol. 107. American Mathematical Soc."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_2_1_38_1","volume-title":"Online regret bounds for undiscounted continuous reinforcement learning. arXiv preprint arXiv:1302.2550","author":"Ortner Ronald","year":"2013","unstructured":"Ronald Ortner and Daniil Ryabko . 2013. Online regret bounds for undiscounted continuous reinforcement learning. arXiv preprint arXiv:1302.2550 ( 2013 ). Ronald Ortner and Daniil Ryabko. 2013. Online regret bounds for undiscounted continuous reinforcement learning. arXiv preprint arXiv:1302.2550 (2013)."},{"volume-title":"Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc","author":"Ronan Fruit Jian QIAN","key":"e_1_2_1_39_1","unstructured":"Jian QIAN , Ronan Fruit , Matteo Pirotta , and Alessandro Lazaric . 2019. Exploration Bonus for Regret Minimization in Discrete and Continuous Average Reward MDPs . In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc , E. Fox, and R. Garnett (Eds.), Vol. 32 . Curran Associates, Inc. Jian QIAN, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. 2019. Exploration Bonus for Regret Minimization in Discrete and Continuous Average Reward MDPs. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc."},{"key":"e_1_2_1_40_1","volume-title":"Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints (STOC '16). ACM","author":"Rubinstein Aviad","year":"2016","unstructured":"Aviad Rubinstein . 2016 . Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints (STOC '16). ACM , NY , NY, USA , 324--332. Aviad Rubinstein. 2016. Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints (STOC '16). ACM, NY, NY, USA, 324--332."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039796"},{"key":"e_1_2_1_42_1","volume-title":"11th Innovations in Theoretical Computer Science Conf., ITCS 2020","author":"Rubinstein Aviad","year":"2020","unstructured":"Aviad Rubinstein , Jack Z. Wang , and S. Matthew Weinberg . 2020. Optimal Single-Choice Prophet Inequalities from Samples . In 11th Innovations in Theoretical Computer Science Conf., ITCS 2020 , January 12 --14 , 2020 , Seattle, Washington, USA (LIPIcs, Vol. 151). 60:1--60:10. Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. 2020. Optimal Single-Choice Prophet Inequalities from Samples. In 11th Innovations in Theoretical Computer Science Conf., ITCS 2020, January 12--14, 2020, Seattle, Washington, USA (LIPIcs, Vol. 151). 60:1--60:10."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"volume-title":"Optimal stopping rules","author":"Shiryaev Albert N","key":"e_1_2_1_44_1","unstructured":"Albert N Shiryaev . 2007. Optimal stopping rules . Vol. 8 . Springer Science & Business Media . Albert N Shiryaev. 2007. Optimal stopping rules . Vol. 8. Springer Science & Business Media."},{"key":"e_1_2_1_45_1","volume-title":"Near-optimal optimistic reinforcement learning using empirical bernstein inequalities. arXiv preprint arXiv:1905.12425","author":"Tossou Aristide","year":"2019","unstructured":"Aristide Tossou , Debabrota Basu , and Christos Dimitrakakis . 2019. Near-optimal optimistic reinforcement learning using empirical bernstein inequalities. arXiv preprint arXiv:1905.12425 ( 2019 ). Aristide Tossou, Debabrota Basu, and Christos Dimitrakakis. 2019. Near-optimal optimistic reinforcement learning using empirical bernstein inequalities. arXiv preprint arXiv:1905.12425 (2019)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376930.3376982"}],"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\/3530893","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530893","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:26Z","timestamp":1750183766000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530893"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5,26]]}},"alternative-id":["10.1145\/3530893"],"URL":"https:\/\/doi.org\/10.1145\/3530893","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2022-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}