Learning to Allocate Reusable Resources under Stochastic Rewards and Durations
ACM SIGMETRICS Performance Evaluation Review · 20.07.2026 · 54 (1) · 1-3
DOI: 10.1145/3820171.3806839 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 27.07.2026. Verfasst von Ativ Joshi und 2 weiteren Autor:innen. Die Arbeit nennt 16 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
We study sequential allocation of a single reusable resource to stochastically arriving tasks in continuous time, where rewards and service durations are random with unknown statistics. When the resource is idle, the controller observes the arriving task's type and duration and must immediately accept or reject it; while the resource is busy, new arrivals are unobserved, which tightly couples learning and control. We first show that no non-anticipatory online policy can guarantee more than a 1/2 fraction of the full-information offline prophet benchmark, motivating the use of 1/2-approximate regret. To approach this limit, we derive an infinite-dimensional steady-state linear program that upper bounds the offline optimum and reveals a threshold structure: a task should be accepted when its profitability, defined as reward divided by duration plus expected waiting time, exceeds a critical threshold. Guided by this characterization, we develop online threshold-learning algorithms that achieve O (√ T ) 1/2-approximate regret when rewards are known and O (T 2/3 ) when reward functions are unknown. We further show that if durations are unobserved upon arrival, meaningful guarantees become impossible without additional flexibility, but can be recovered via task termination.
Förderung
- National Science Foundation
Zitieren
APA
Joshi, A., Liu, Q., & Hajiesmaili, M. (2026). Learning to Allocate Reusable Resources under Stochastic Rewards and Durations. ACM SIGMETRICS Performance Evaluation Review, 54(1), 1-3. https://doi.org/10.1145/3820171.3806839
Vancouver
Joshi A, Liu Q, Hajiesmaili M. Learning to Allocate Reusable Resources under Stochastic Rewards and Durations. ACM SIGMETRICS Performance Evaluation Review. 2026;54(1):1-3. doi:10.1145/3820171.3806839
BibTeX
@article{Joshi2026,
author = {Joshi, Ativ and Liu, Qingsong and Hajiesmaili, Mohammad},
title = {Learning to Allocate Reusable Resources under Stochastic Rewards and Durations},
journal = {ACM SIGMETRICS Performance Evaluation Review},
year = {2026},
volume = {54},
number = {1},
pages = {1--3},
doi = {10.1145/3820171.3806839}
}
EUVIMED