Best of Many in Both Worlds: Online Resource Allocation with Predictions
  under Unknown Arrival Model
Lin An Andrew A. Li Benjamin Moseley Gabriel Visotsky
Online decision-makers today can often obtain predictions on future
variables, such as arrivals, demands, inventories, and so on. These predictions
can be generated from simple forecasting algorithms for univariate time-series,
all the way to state-of-the-art machine learning models that leverage multiple
time-series and additional feature information. However, the prediction quality
is often unknown to decisions-makers a priori, hence blindly following the
predictions can be harmful. In this paper, we address this problem by giving
algorithms that take predictions as inputs and perform robustly against the
unknown prediction quality.
  We consider the online resource allocation problem, one of the most generic
models in revenue management and online decision-making. In this problem, a
decision maker has a limited amount of resources, and requests arrive
sequentially. For each request, the decision-maker needs to decide on an
action, which generates a certain amount of rewards and consumes a certain
amount of resources, without knowing the future requests. The decision-maker's
objective is to maximize the total rewards subject to resource constraints. We
take the shadow price of each resource as prediction, which can be obtained by
predictions on future requests. Prediction quality is naturally defined to be
the $\ell_1$ distance between the prediction and the actual shadow price. Our
main contribution is an algorithm which takes the prediction of unknown quality
as an input, and achieves asymptotically optimal performance under both
requests arrival models (stochastic and adversarial) without knowing the
prediction quality and the requests arrival model beforehand. We show our
algorithm's performance matches the best achievable performance of any
algorithm had the arrival models and the accuracy of the predictions been
known. We empirically validate our algorithm with experiments.