Online Resource Allocation under Horizon Uncertainty
We study stochastic online resource allocation: a decision maker needs to
allocate limited resources to stochastically-generated sequentially-arriving
requests in order to maximize reward. Motivated by practice, we consider a
data-driven setting in which requests are drawn independently from a
distribution that is unknown to the decision maker. Online resource allocation
and its special cases have been studied extensively in the past, but these
previous results crucially and universally rely on a practically-untenable
assumption: the total number of requests (the horizon) is known to the decision
maker in advance. In many applications, such as revenue management and online
advertising, the number of requests can vary widely because of fluctuations in
demand or user traffic intensity. In this work, we develop online algorithms
that are robust to horizon uncertainty. In sharp contrast to the known-horizon
setting, we show that no algorithm can achieve a constant asymptotic
competitive ratio that is independent of the horizon uncertainty. We then
introduce a novel algorithm that combines dual mirror descent with a
carefully-chosen target consumption sequence and prove that it achieves a
bounded competitive ratio. Our algorithm is near-optimal in the sense that its
competitive ratio attains the optimal rate of growth when the horizon
uncertainty grows large.