A Unified Framework for Online Combinatorial Allocation of Reusable Resources under Endogenous Deterioration

This paper studies an online resource allocation problem, where resources are reusable, allocated in combinatorial bundles, and subject to endogenous performance deterioration. Unlike existing models that assume singleton decisions or stationary or exogenous dynamics, we consider a combinatorial decision structure where decisions involve selecting among resource-bundled options, while capturing a self-induced feedback loop in which system performance, like rewards, activation probabilities, and service times, degrade as a function of cumulative resource usage. This setting naturally arises in systems such as inference serving, routing, and content recommendation. We propose a unified framework that subsumes a broad class of existing models as special cases, and develop a ranking-like online policy, termed IPRANK, which employs an indicator-perturbation mechanism to induce a randomized ranking over configurations based on their size-penalized rewards. Our analysis is based on a queue-coupling argument and shows that under adversarial arrivals, the greedy policy inevitably suffers a competitive ratio with linear dependence on reward heterogeneity, whereas IPRANK achieves a competitive ratio with only logarithmic dependence, making it far more robust in heterogeneous environments. We further study several special cases with additional structural assumptions and demonstrate that IPRANK can leverage such structures to obtain sharper competitive guarantees.