Reusable Resource Allocation under Adversarial Arrivals: Learning with Delayed Feedback

Abstract

We study an online reusable resource allocation problem motivated by mobile edge AI platforms, where sequentially arriving requests must be immediately admitted and assigned to one of multiple edge service options with limited reusable capacities or offloaded to a remote central server. If accepted, a request occupies one service slot of the selected option for a random duration and yields a stochastic reward. The problem is particularly challenging because arrivals may be adversarial, reward and service-time statistics are both unknown and heterogeneous across request types and service options, and reward feedback can be delayed beyond service completion. To address these challenges, we propose an index-based online learning algorithm that combines optimistic reward estimates with a conservative, utilization-aware opportunity-cost penalty that captures the future value of reusable capacity. Using a primal-dual framework built on a novel reverse-order benchmark, we establish competitive-ratio guarantees under both bounded and light-tailed unbounded feedback delays. In particular, under a homogeneous reward-service model with i.i.d. inter-arrival times, our algorithm achieves an asymptotic competitive ratio of 1 - 1/e as reusable capacities grow large. Experimental results on a real-world dataset further demonstrate the effectiveness of our approach.