Optimal Bayesian Online Allocation of Reusable Resources

Many modern online platforms allocate "reusable" capacity, where a resource unit is occupied for some duration and then becomes available again. Examples include cloud and edge computing platforms allocating compute or GPU memory to jobs, rental marketplaces, and service systems in which capacity cycles between busy and idle states. Motivated by these applications, we study a Bayesian online resource allocation problem with reusable resources.&nbsp; There are k units of each resource, and demand requests of heterogeneous types (i.e., rewards and usage durations) arrive according to non-stationary Poisson processes. Upon arrival, each request must be irrevocably assigned at most one unit of a resource. The goal is to maximize the total expected reward. Our main result is a simple online algorithm that obtains a 1-\sqrt{2/\pi k} + O(1/k) fraction of the reward obtained by the optimal omniscient algorithm. Our results advance the existing literature by directly generalizing the non-reusable setting of &nbsp;Wang et al. (2018) to the reusable setting, matching the best known bound in the non-reusable case, and hence solving an open problem by improving upon the best previously known guarantee of 1-O(\sqrt{\log k/k}) for reusable resources due to Feng, Niazadeh, and Saberi (2024). <br><br>Our results are obtained through a now-standard propose--then--admit framework. We upper bound the performance of the optimal omniscient algorithm by a fluid LP approximation, and then round the optimal fluid solution. Each request first proposes to a resource type according to the LP assignment probabilities, and then each resource runs an online admission-control policy to enforce ex-post capacity feasibility. Our main contribution is a simple and novel state-dependent admission-control policy for reusable resources that yields a constant per-proposal admission probability of Pr[Poisson(k)&lt;= k-1 | Poisson(k) &lt;= k]&nbsp;independent of time, rewards, or durations, which immediately leads to our main result. Our policy equalizes conditional admission probabilities (conditional on a request being made) among all potential requests. To this end, it synthetically increases the load at each time (so that the total load is exactly equal to the capacity) by adding "imaginary" requests when necessary, and then greedily accepting real and imaginary requests.