Online Resource Allocation with Non-Stationary Customers
Xiaoyue Zhang Hanzhang Qin Mabel C. Chou
We propose a novel algorithm for online resource allocation with
non-stationary customer arrivals and unknown click-through rates. We assume
multiple types of customers arrive in a nonstationary stochastic fashion, with
unknown arrival rates in each period, and that customers' click-through rates
are unknown and can only be learned online. By leveraging results from the
stochastic contextual bandit with knapsack and online matching with adversarial
arrivals, we develop an online scheme to allocate the resources to
nonstationary customers. We prove that under mild conditions, our scheme
achieves a ``best-of-both-world'' result: the scheme has a sublinear regret
when the customer arrivals are near-stationary, and enjoys an optimal
competitive ratio under general (non-stationary) customer arrival
distributions. Finally, we conduct extensive numerical experiments to show our
approach generates near-optimal revenues for all different customer scenarios.