  The classic newsvendor model yields an optimal decision for a "newsvendor"
selecting a quantity of inventory, under the assumption that the demand is
drawn from a known distribution. Motivated by applications such as cloud
provisioning and staffing, we consider a setting in which newsvendor-type
decisions must be made sequentially, in the face of demand drawn from a
stochastic process that is both unknown and nonstationary. All prior work on
this problem either (a) assumes that the level of nonstationarity is known, or
(b) imposes additional statistical assumptions that enable accurate predictions
of the unknown demand.
  We study the Nonstationary Newsvendor, with and without predictions. We
first, in the setting without predictions, design a policy which we prove (via
matching upper and lower bounds) achieves order-optimal regret -- ours is the
first policy to accomplish this without being given the level of
nonstationarity of the underlying demand. We then, for the first time,
introduce a model for generic (i.e. with no statistical assumptions)
predictions with arbitrary accuracy, and propose a policy that incorporates
these predictions without being given their accuracy. We upper bound the regret
of this policy, and show that it matches the best achievable regret had the
accuracy of the predictions been known. Finally, we empirically validate our
new policy with experiments based on two real-world datasets containing
thousands of time-series, showing that it succeeds in closing approximately 74%
of the gap between the best approaches based on nonstationarity and predictions
alone.
