Abstract
Joint online learning and resource allocation is a fundamental problem inherent in many applications. In a general setting, heterogeneous customers arrive sequentially, each of which can be allocated to a resource in an online fashion. Customers stochastically consume the resources, allocations yield stochastic rewards, and the system receives feedback outcomes with delay. We introduce a generic framework that judiciously synergizes online learning with a broad class of online resource allocation mechanisms, where the sequence of customer contexts is adversarial, and the customer reward and the resource consumption are stochastic and unknown. First, we propose an online algorithm for a general resource allocation problem, called personalized resource allocation while learning with delay, which strikes a three-way balance between exploration, exploitation, and hedging against adversarial arrival sequence. We provide a performance guarantee for this online algorithm in terms of Bayesian regret. Next, we develop our second online algorithm for an advance scheduling problem, called personalized advance scheduling while learning with delay (PAS-LD), and evaluate its theoretical performance. The PAS-LD algorithm has a more delicate structure and offers multiday scheduling while accounting for the no-show behavior of customers. We demonstrate the practicality and efficacy of our PAS-LD algorithm using clinical data from a partner health system. Our results show that the proposed algorithm provides promising results compared with several benchmark policies.