Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
99,857 characters · 19 sections · 76 citation commands
The newsvendor problem is a century-old model (edgeworth1888mathematical) that remains fundamental to the practice of operations management. In its original instantiation, a “newsvendor” is tasked with selecting a quantity of inventory before observing the demand for that inventory, with the demand itself randomly drawn from a {\em known} distribution. The newsvendor incurs a per-unit underage cost for unmet demand, and a per-unit overage cost for unsold inventory. The objective is to minimize the total expected cost, and the classic result is that the optimal inventory level is a certain problem-specific quantile (depending only on the underage and overage costs) of the demand distribution.
This paper is concerned with a modern instantiation of the same model, consisting of a {\em sequence} of newsvendor problems over time, each with {\em unknown} demand distributions that {\em vary} over time. While this version of the problem is arguably ubiquitous in practice today, it may be worth highlighting a few motivating examples:
Despite its ubiquity, this problem is far from resolved, precisely because the demand (or sequence of demand distributions) is both {\em nonstationary} and {\em unknown} -- indeed, the repeated newsvendor with stationary, but unknown demand was solved by levi2015data, and the same setting with known, but nonstationary demand can be treated simply as a sequence of completely separate newsvendor problems. At present, there are by and large two existing approaches to this problem:
To summarize, the repeated newsvendor with unknown, nonstationary demand (which from here on we refer to as the {\em Nonstationary Newsvendor}) admits policies with nontrivial guarantees, which can be made significantly better or worse by following predictions. This suggests the opportunity to design a policy that uses predictions {\em optimally}, in the sense that the predictions are utilized when accurate, and ignored when inaccurate. Ideally, such a policy would run without knowledge of (a) the accuracy of the predictions and (b) the method with which they are generated. {\em This is precisely what we accomplish in this paper.}
The primary purpose of this paper is to develop a policy that optimally incorporates {\em predictions} (defined in the most generic sense possible) into the {\em Nonstationary Newsvendor} problem. Naturally, a prerequisite to this is a fully-solved model of the Nonstationary Newsvendor without predictions. At present this prerequisite is only partially satisfied (via the work of keskin2021nonstationary), so a nontrivial portion of our contributions will be to fully solve this problem.
Without predictions, the Nonstationary Newsvendor consists of a sequence of newsvendor problems indexed by periods $t \in 1,\ldots,T$, each with unknown demand distribution $D_t$. The level of nonstationarity is characterized via a {\em variation parameter} $v\in[0,1]$, where $v=0$ essentially amounts to stationary demand, and $v=1$ is effectively arbitrary (in a little more detail: a deterministic analogue of quadratic variation is applied to the sequence of means $\{\mathbb{E}[D_1],\ldots,\mathbb{E}[D_T]\}$, and $v\in[0,1]$ is the exponent such that this quantity equals $T^v$). Finally, we measure the performance of any policy using {\em regret}, which is the expected difference in the total cost incurred by the policy versus that of an optimal policy that “knows” the demand distributions. At minimum we aim to design a policy that achieves {\em sub-linear} (i.e. $o(T)$) regret, as such a policy would incur a per-period cost that is on average no worse than the optimal, as $T$ grows. We will in fact design policies which achieve {\em order-optimal} regret with respect to the variation parameter $v$.
To this base problem, we introduce the notion of predictions. In each period we receive a prediction $a_t$ of the mean demand $\mu_t = \mathbb{E}[D_t]$ before selecting the order quantity. Our predictions are generic: no assumption is made on how they are generated. We measure the accuracy of the predictions through an {\em accuracy parameter} $a\in[0,1]$, defined such that $\sum_{t=1}^{T} |a_t-\mu_t| = T^a$. Notice that when $a=0$ the predictions are almost perfect, and when $a=1$ the predictions are effectively useless. We will characterize a precise threshold on $a$ (which depends on $v$) that determines when the predictions should be utilized. Our primary challenge will be to design a policy that makes use of the predictions only when they are sufficiently accurate, and {\em without} having access to $a$. As to the variation parameter $v$, we will separately consider policies which do and do not have access to $v$ -- this distinction will turn out to be {\em the} critical factor in classifying what is and is not achievable.
Our primary contributions can be summarized as follows.
\paragraph{ 1. Nonstationary Newsvendor (without predictions):} We completely solve the Nonstationary Newsvendor problem. This consists of first constructing a policy and proving an upper bound on its regret:
We then show that this regret is minimax optimal up to logarithmic factors:
As alluded to earlier, keskin2021nonstationary previously initiated the study of the Nonstationary Newsvendor. Our results are distinct in terms of both modeling and theoretical contributions. We will expound these distinctions more carefully later on.
\paragraph{ 2. Nonstationary Newsvendor with Predictions:} We construct a policy that {\em optimally} leverages predictions, i.e. it is robust to unknown prediction accuracy. To be precise, the previous contribution offers a policy that achieves $\tilde{O}(T^{(3+v)/4})$ regret, and predictions yield a simple policy that achieves $O(T^a)$ regret, so we would expect that the best possible regret is the minimum of these two quantities. We show this formally:
Our main algorithmic contribution is a policy which achieves this lower bound (up to log factors) {\em without} knowing the prediction accuracy:
\addtocounter{theorem}{-2} Finally, since our policy relies on knowledge of the variation parameter $v$, the remaining question is whether the same regret is achievable if both $v$ and $a$ are unknown. We show that in fact predictions {\em cannot} be incorporated in any meaningful way in this case:
\addtocounter{proposition}{-3}
Our theoretical results are summarized in the (ref). Each entry has a corresponding policy that achieves the stated regret, along with a matching lower bound.
\paragraph{ 3. Empirical Results:} Finally, we demonstrate the practical value of our model (namely the Nonstationary Newsvendor with Predictions) and our policy via empirical results on three real-world datasets that span our motivating applications above: daily web traffic for Wikipedia.com (of various languages), daily foot traffic across the Rossmann store chain, and daily visitors at a certain Japanese restaurant. These datasets together contain over one thousand individual time-series on which we generate predictions of varying quality, using four different popular forecasting and machine learning algorithms. We apply our policy, and compare its performance against the two most-natural baseline policies: our optimal policy without predictions, and the simple policy which always utilizes the predictions (these correspond to the two “existing approaches” described previously). A snapshot of our results, for the Rossmann stores depicted in (ref), is given in (ref).
More generally, on any given experimental instance (i.e. a time-series and a set of predictions), the minimum (maximum) of the costs incurred by these two baselines can be viewed as the best (worst) we can hope for. Thus we measure performance in terms of the proportion of the gap between these two costs incurred by our policy, so if this “optimality gap” is close to 0, our policy performs almost as good as the better one of the two baselines. Note that {\em randomly} selecting between the two baseline policies yields an (expected) optimality gap of 0.5. We find that in the Rossmann dataset, the average optimality gap is 0.26 when the predictions are accurate, and 0.28 when the predictions are inaccurate. In the Wikipedia dataset, the average optimality gap is 0.40 when the predictions are accurate, and 0.07 when the predictions are inaccurate. In the Restaurant dataset, the average optimality gap is 0.10 when the predictions are accurate, and 0.39 when the predictions are inaccurate. This demonstrates that our policy performs well, irrespective of the quality of the predictions.
The earliest works on the newsvendor model assume that the demand distribution is fully known arrow1958studies,scarf1960optimality. This assumption has then been relaxed, and we can divide the approaches in which the demand distribution is unknown into parametric and nonparametric ones. One of the most popular parametric approaches is the Bayesian approach, where there is a prior belief in parameters of the demand distribution, and such belief is updated based on observations that are collected over time. scarf1959bayes first applied the Bayesian approach to inventory models, and later this is studied in many works karlin1960dynamic,iglehart1964dynamic,azoury1985bayes,lovejoy1990myopic. liyanage2005practical introduced another parametric approach called operational statistics which, unlike the Bayesian approach, does not assume any prior knowledge on the parameter values. Instead it uses past demand observations to directly estimate the optimal ordering quantity.
Nonparametric approaches have been developed in recent years. The first example of a nonparametric approach is the SAA method, first proposed by kleywegt2002sample and shapiro2003monte. levi2007provably applied SAA to the newsvendor problem by using samples to approximate the optimal ordering quantity, and levi2015data improve significantly upon the bounds of levi2007provably for the same problem. Other non-parametric approaches include stochastic gradient descent algorithms burnetas2000adaptive,kunnumkal2008using,huh2009nonparametric and the concave adaptive value estimation (CAVE) method godfrey2001adaptive,powell2004learning. With the development of machine learning, ban2019big and oroojlooyjadid2020applying propose machine learning/deep learning algorithms using demand features and historical data to solve the newsvendor problem.
All the previous studies consider the newsvendor in a static environment where the demand distribution is the same over time. However, in reality the demand distribution is often nonstationary. There are two common practices to resolve this issue. The first is to model the nonstationarity and utilize past demand observations according to the model. One common way is to model the nonstationarity as a Markov chain. For example, treharne2002adaptive applied this idea to inventory management and aviv2005partially and chen2019coordinating applied this idea to revenue management. Another approach is to bound the nonstationarity via a variation budget, which has been applied to stochastic optimization besbes2015non, dynamic pricing keskin2017chasing, multi-armed bandit besbes2014stochastic, newsvendor problem keskin2021nonstationary, among others. Some of these works are applicable in the sense that our problem can be mapped to their settings (e.g. multi-armed bandit such as besbes2015non,karnin2016multi,luo2018efficient,cheung2022hedging), but these connections do not appear to be fruitful. In particular, the multi-armed bandit papers cited above typically consider a {\em limited-feedback} setting rather than the {\em full-feedback} setting explored in this work. Related to feedback, while our study provides a complete characterization of the regret behavior for the nonstationary newsvendor problem with {\em uncensored} demand, practical applications often involve {\em censored} demand. The nonstationary newsvendor problem under censored demand is an interesting direction for future research.
Beyond the bandit literature, it is worth mentioning recent work on online convex optimization (OCO) with limited nonstationarity. When the level of nonstationarity is {\em known}, the standard first-order OCO algorithms can be modified with carefully chosen restarts and updating rules (besbes2015non,yang2016tracking, chen2019nonstationary). There are also recent works that concern {\em unknown} nonstationarity, such as zhang2018adaptive, baby2019online, bai2022adapting, and huang2023stability. Finally, as mentioned before, keskin2021nonstationary is particularly relevant, so we delay a careful comparison to (ref).
The second common practice is to use predictions on the demand distribution of each time period. Predictions can often be obtained e.g. via machine learning, and a recent line of work looks to help decision-making by incorporating predictions. This framework has been applied to many online optimization problems such as revenue optimization munoz2017revenue, balseiro2022single, caching lykouris2021competitive,rohatgi2020near, online scheduling lattanzi2020online, and the secretary problem dutting2021secretaries. In this paper we will combine the nonstationarity framework and the prediction framework on the newsvendor problem.
Finally, most previous works involving algorithms with predictions analyzed algorithms' performances using competitive analysis (e.g. mahdian2012online,antoniadis2020secretary,balseiro2022single,jin2022online) and obtained optimal consistency-robustness trade-offs, where consistency is an algorithm's competitive ratio when the prediction is accurate, and robustness is the competitive ratio regardless of the prediction's accuracy. However, competitive ratio transfers to a regret bound that is linear in $T$. In contrast, we do regret analysis under this framework and design an algorithm that has near-optimal worst-case regret without knowing the prediction quality. Other papers with regret analyses under the prediction model include munoz2017revenue (revenue optimization in auctions), hao2023leveraging (Thompson sampling), hu2024constrained (constrained online two-stage stochastic optimization), and an2024best (online resource allocation).
We begin this section with a formal description of the {\bf Nonstationary Newsvendor}, along with a comparison to the problem of the same name from keskin2021nonstationary. Consider a sequence of newsvendor problems over $T$ time periods labeled $t=1,\dots, T$. At the beginning of each time period $t$, the decision-maker selects a quantity $q_t\in Q$, where $Q$ is a fixed subset of $\mathbb{R}^+$ bounded above by a quantity we denote as $Q_{\max}$.\footnote{All of our results carry through if $Q$ is allowed to depend on $t$.} Then the period's demand $d_t$ is drawn from an (unknown) demand distribution $D_t$, which depends on the time period $t$. These demand distributions are independent over time. Finally a cost is incurred -- specifically, there is a (known) per-unit underage cost $b_t \in [0,b_{\max}]$ and a (known) per-unit overage cost $h_t\in [0,h_{\max}]$, so that the total cost is equal to $$b_t(d_t-q_t)^{+}+h_t(q_t-d_t)^{+},$$ where $x^{+} = \max \{0, x\}$. The decision-maker observes the realized demand $d_t$,\footnote{The demand is not censored here, as is the case in all of the motivating examples in the introduction. The censored version of our problem is an interesting, but separate subject.} and thus the cost. Note that requiring $q_t \in Q$ does not impose any restriction on {\em modeling}, since $Q$ could simply be selected to be $\mathbb{R}$ (as in much of the literature). In fact, introducing $Q$ allows for modeling important practical concerns such as batched inventory or even simply the integrality of physical items. As we will discuss momentarily, this is a non-trivial concern insofar as theoretical guarantees are concerned.
To complete our description of the Nonstationary Newsvendor, we will need to (a) impose a few assumptions on the demand distributions, and then (b) describe how “nonstationarity” is quantified. These are, respectively, the subjects of the following two subsections.
We will assume that the demand distributions come from a known, parameterized family of distributions $\mathcal{D}$:
Assumption (ref) is fairly minimal. Parsing it in reverse: the sub-Gaussianity in part (b) allows for many commonly-used variables, such as the Gaussian distribution and any bounded random variable, while letting us eventually apply Hoeffding-type concentration bounds. Part (a) is particularly minimal at the moment, as $\mu$ represents an arbitrary parameterization of $\mathcal{D}$, but will become meaningful when combined with Assumption (ref). The choice of the symbol “$\mu$” might suggest that $\mu$ represents the mean of $\mathcal{D}_\mu$, and indeed this is what we will assume from here on. But it should be emphasized that our taking $\mu = \mathbb{E}[\mathcal{D}_\mu]$ is strictly for notational convenience (because we will frequently need to refer to the means of these distributions): if $\mu$ were any other parameterization of $\mathcal{D}$, we could simply define a mapping from $\mu$ to the mean values.
Now define $C(\mu,b,h,q)$ to be the expected newsvendor cost when selecting quantity $q \in Q$, given underage/overage costs $b$ and $h$, and demand distribution $\mathcal{D}_\mu$: $$C(\mu,b,h,q) = \mathbb{E}_{d\sim \mathcal{D}_\mu}[b(d-q)^+ + h(q - d)^+].$$ The critical assumption, with respect to the parameterization in Assumption (ref)(a), is that the expected cost is well-behaved as a function of $\mu$:
Note that in the above description, the Lipschitz constant $\ell$ may depend on $b,h,$ and $q$, but by continuity, there exists a single $\ell$ so that the above holds for all $b,h,q$ simultaneously.
Some useful examples of families $\mathcal{D}$ satisfying Assumptions (ref) and (ref) are the following:\footnote{Unfortunately, (ref) is not guaranteed to hold. For example, for the family of distributions $$\mathcal{D}_\mu \sim
,$$ the function $C(\mu,1,1,1)$ is discontinuous (and thus not Lipschitz) at $\mu = 1$. }
To understand the reasoning behind Assumption (ref), consider the problem faced at some time $t$. The optimal choice for the decision-maker here is
where $\mu_t$ is the mean of $D_t$ (i.e. $D_t \sim \mathcal{D}_{\mu_t}$), and $C_t(\mu,q) = C(\mu,b_t,h_t,q)$ to simplify the notation.\footnote{As a sanity check, the classical result for the newsvendor problem (arrow1958studies,scarf1960optimality) states that if $Q=\mathbb{R}$, then $q^*_t$ is the $b_t/(b_t+h_t)$-th quantile of $D_t$.} Since $D_t$ is unknown, it is likely that some $q_t \ne q_t^*$ will ultimately be selected, and we could measure the sub-optimality of this decision (i.e. regret, to be defined soon): $C_t(\mu_t,q_t) - C_t(\mu_t,q_t^*)$. It would be natural then to try to characterize this suboptimality as a function of $|q_t - q_t^*|$, but in fact all of the algorithms we will consider “work” by making an estimate $\hat{\mu}_t$ of $\mu_t$, and then selecting $\hat{q}_t \in \text{argmin}_{q\in Q}C_t(\hat{\mu}_t,q)$. So motivated, the purpose of Assumption (ref) is to allow us to “translate” error in our estimate of $\mu_t$ to (excess) costs. The following structural lemma makes this precise, and will be used throughout the paper.
Lemma (ref) states that estimation error of the mean $\mu_t$ translates {\em linearly} to excess cost. The proof of Lemma (ref) appears in Appendix (ref).
\paragraph{ Aside: Comparison to keskin2021nonstationary:} The final component in describing the Nonstationary Newsvendor is defining a proper quantification of nonstationarity. Before doing so, we delineate the {\em modeling} differences between our Nonstationary Newsvendor and that of keskin2021nonstationary. There are two primary differences:\footnote{Other minor differences: keskin2021nonstationary require the demand distribution to be bounded, and this assumption is easily relaxed.}
Besides the practical reasons why discrete quantities arise in practice (non-divisible items, batched inventory, etc.), the primary consequence of either of the two differences above is that they preclude a critical lemma used in keskin2021nonstationary (and in fact by levi2007provably) which states that $C(\mu_1,q_2^*)-C(\mu_1,q_1^*)$ (as defined in our Lemma (ref)) scales as $(q_1^* - q_2^*)^2$. This scaling does {\em not} necessarily hold when either the demand distribution or $Q$ is discrete. These relaxations in assumptions yield different lower bounds in the worst-case regret from keskin2021nonstationary, which we will discuss in detail later.
Just as in keskin2021nonstationary (and keskin2017chasing before that), we measure the level of nonstationarity via a deterministic analogue of quadratic variation for the sequence of means $\mu_1,\ldots,\mu_T$. Specifically, define a {\em partition} of the time horizon $\{1,\dots, T\}$ to be any subset of time periods $\{t_0,\dots, t_K\}$ where $1\leq t_0<\cdots < t_K\leq T$. Here the subset can have any size between 1 and $T$, i.e. $0\leq K\leq T-1$. Then for any sequence of means $\bm{\mu}=\{\mu_1,\dots,\mu_T\}$, its demand variation is
where $\mathcal{P}$ is the set of all partitions.
To motivate the use of partitions in the definition of $V_{\bm{\mu}}$, it is worth contrasting with a measure that may feel more natural, namely the sum of squared differences ({\em SSD}) between consecutive terms, $\sum_{t=2}^{T}\left(\mu_{t}-\mu_{t-1}\right)^2$, which corresponds to taking the densest possible partition $\{1,2,\ldots,T\}$. The maximum in the definition of $V_{\bm{\mu}}$ is {\em not} necessarily achieved by selecting the densest possible partition, but rather by setting $t_0,\dots, t_K$ to be the periods when the sequence $\mu_1,\dots,\mu_T$ changes direction. Thus, the demand variation penalizes {\em trends}, or consecutive increases/decreases, more so than the SSD. For example, the mean sequences $\bm{\mu_1}=\{1,2,3,4,5\}$ and $\bm{\mu_2}=\{1,0,1,0,1\}$, respective variations $V_{\bm{\mu_1}}=(5-1)^2=16$ and $V_{\bm{\mu_2}}=1^2+1^2+1^2+1^2+1^2=5$, despite having identical SSDs.
All of our theoretical guarantees (upper and lower bounds) will be parameterized by $V_{\bm{\mu}}$. This quantity of course depends on $T$, and so it is natural to allow $V_{\bm{\mu}}$ to grow $T$. It will turn out that the most natural parameterization of this growth is via what we will simply call the {\bf variation parameter} $v\in [0,1]$, such that $V_{\bm{\mu}} = BT^v$, where $B$ is some constant (which we take to be equal to one from here on). We denote the set of demand distribution sequences $\{D_1,\dots D_T\}$ whose means $\bm\mu=\{\mu_1,\dots,\mu_T\}$ satisfy $V_{\bm{\mu}}\leq T^v$ as $$\mathcal{D}(v)=\{\{D_1,\dots D_T\}: D_t\in\mathcal{D}\text{ for all }t\text{ and } V_{\bm{\mu}}\leq T^v\}.$$ In the next section, we will show via a minimax lower bound that non-trivial guarantees are only achievable when $v < 1$, and provide an algorithm which achieves the same bound.
\paragraph{ Aside: Time-Series Modeling:} At this point, we have fully described our model for the Nonstationary Newsvendor. All that remains is to define our performance metric, which we will do in the next subsection. We conclude this subsection with an important practical consideration with respect to time-series models and our variation parameter.
Consider, as an example, the following class of time-series models:
Here, $R(t)$ represents a deterministic (and usually simple, e.g. linear) function representing some notion of “trend,” and $S(t)$ represents a deterministic, periodic function representing some notion of “seasonality.” Finally, all stochastic behavior is captured by the random variables $\epsilon_t$, which are assumed to be independent and mean-zero. This time-series model is classic, and yet drives forecasting algorithms (e.g. exponential smoothing) which are still competitive in modern forecasting competitions (makridakis2000m3).
The above model raises an important practical issue: if there exists any (non-trivial) trend $R(\cdot)$ or seasonality $S(\cdot)$, then the demand variation of the sequence of means $\mu_t = R(t) + S(t)$ would scale at least as $T$, meaning $v = 1$ and no meaningful guarantee will be achievable. Our main observation is that time-series effects like trend and seasonality are easily detected and estimated, so that in any practical setting, estimates $\hat{R}(\cdot)$ and $\hat{S}(\cdot)$ should be available, and used to “de-trend” and “de-seasonalize” the data. Concretely, the Nonstationary Newsvendor would take place on the sequence $$ \tilde{d_t} = d(t) - \hat{R}(t) - \hat{S}(t) = (R(t)-\hat{R}(t)) + (S(t)-\hat{S}(t)) + \epsilon_t. $$ The resulting sequence of means $\mu_t = (R(t)-\hat{R}(t)) + (S(t)-\hat{S}(t))$ does not stem from the trend and seasonality, but rather the error in estimating the trend and seasonality. It is this error that is assumed to be nonstationary, but with reasonable variation parameter.
We conclude this section by formally defining our performance metric for any policy. A policy is simply a sequence of mappings $\pi=\{\pi_1,\dots,\pi_T\}$, where each $\pi_t$ is a mapping from $d_1,\dots, d_{t-1}$ to an order quantity $q_t\in Q$ at time $t$ (by convention, $\pi_1$ is a constant function).\footnote{Note that we are not considering randomized policies here, but all of our theoretical results (the lower bounds, in particular) hold even when randomization is allowed.} We measure the performance of a policy by its regret. Fix a sequence of demand distributions $\bm{D} = \{D_1,\dots, D_T$\}. Following the earlier notation from Eq. (ref), the regret incurred by a policy which selects order quantities $q_1,\ldots,q_T$ is $$\mathbb{E}^\pi_{\bm{D}}\left[\sum_{t=1}^T\left(C_t(\mu_t,q_t)-C_t(\mu_t, q^*_t)\right)\right],$$ where the expectation is with respect to the randomness of the realized demands. Recall that the demand distributions are independent, so $q_t^*$ as defined in Eq. (ref) depends only on $D_t$. In words, the regret measures the difference between the (expected) total cost incurred by the policy and that of a clairvoyant that knows the underlying demand distributions $\bm{D} = \{D_1,\dots, D_T$\}.\footnote{Note that this is different from a clairvoyant that knows the realized demands $d_1,\ldots,d_T$. Such a clairvoyant would incur zero cost.}
We will be concerned with the {\bf worst-case regret} of a policy across {families} of instances (i.e. sequences of demand distributions) controlled by the variation parameter $v$: $$\mathcal{R}^\pi(T)=\sup_{\bm{D}\in \mathcal{D}(v)} \mathbb{E}^\pi_{\bm{D}}\left[\sum_{t=1}^T\left(C_t(\mu_t,q_t)-C_t(\mu_t, q^*_t)\right)\right].$$ Note that if the worst-case regret $\mathcal{R}^\pi(T)$ of some policy is sublinear in $T$, then that policy is essentially cost-optimal on average as $T$ goes to infinity. In the next section, we will prove a lower bound on the achievable across all policies, and describe an algorithm which achieves this lower bound.
This section contains a complete solution (i.e. matching lower and upper bounds on regret) to the Nonstationary Newsvendor. We begin with the lower bound:
(ref) is a corollary of a more general lower bound ((ref) in the next section) -- it will turn out the Nonstationary Newsvendor is a special case of the Nonstationary Newsvendor with Predictions -- so the proof is omitted. (ref) states that the regret of any policy is at least $\Omega(T^{(3+v)/4})$. It is useful to contrast this with two existing results:
In the next two subsections, we will first analyze a simple algorithm which achieves the lower bound of (ref) when the variation parameter $v$ is known, and then use this as a building block for an algorithm which achieves the same bound when $v$ is unknown.
If we assume that $v$ is known, then designing a policy which achieves regret matching (ref) is fairly straightforward. In fact, a simple policy based on averaging a fixed number of past demand observations does the job (keskin2021nonstationary use the same policy). That policy, which we call the {\bf Fixed-Time-Window Policy} is defined in Algorithm (ref).
The Fixed-Time-Window Policy uses a carefully-selected “window” size $n$ that is on the order of $T^{(1-v)/2}$. At each time period $t$, it constructs an estimate $\hat{\mu}_t$ of the mean by averaging the observed demands from the previous $n$ periods, and then selects the optimal order quantity corresponding to $\hat{\mu}_t$. Note that Algorithm (ref) also includes a “scaling constant” $\kappa$ -- this should be thought of as a practical tuning parameter, but for the coming theoretical result, it can be chosen arbitrarily (e.g. $\kappa=1$ suffices).
The following result bounds the worst-case regret of the Fixed-Time-Window Policy:
As promised, Lemma (ref) shows that the Fixed-Time-Window Policy achieves regret that matches the lower bound in (ref). Its proof can be found in Appendix (ref), and amounts to bounding the estimation error incurred by demand noise (which is worse for smaller time windows) and demand mean variation (which is worse for larger time windows). The exact time window used in the policy comes from balancing these two sources of error.
The lower bound in (ref) holds for policies that “know” $v$. Naturally, it also holds for policies that do not know $v$, but an unanswered question at the moment is whether (a) the lower bound should be even larger when $v$ is unknown, or (b) there exists a policy that matches (ref) without knowing $v$. We show here that case (b) holds by constructing such a policy.\footnote{As a final comparison to keskin2021nonstationary, they do not consider the unknown $v$ setting.} Our policy, which we call the Shrinking-Time-Window Policy (Algorithm (ref)), at a high level uses the Fixed-Time-Window Policy with the smallest variation parameter that is consistent with the demand observed so far. In more detail:
This policy's regret matches (up to log factors) the lower bound in (ref):
The proof of (ref) can be found in Appendix (ref), but at a high level works as follows:
This concludes our discussion of the Nonstationary Newsvendor. In the next section, we turn to the second subject of this paper, which is the same problem with predictions.
As described in the introduction, it is likely that when the Nonstationary Newsvendor is faced practice, some notion of a “prediction” of future demand will be made. Such predictions can come from a diverse set of sources ranging from simple human judgement, to forecasting algorithms built on previous demand data, to more-sophisticated machine learning algorithms trained on feature information. The process of sourcing or constructing such predictions is orthogonal to our work. Instead, we treat these predictions as given to us endogenously (and in particular, we make no assumption on the accuracy of these predictions), and attempt to use these predictions optimally.
The {\bf Nonstationary Newsvendor with Predictions} problem assumes all of the setup, assumptions, and notation of the previous Nonstationary Newsvendor problem. In addition, at each time period $t$, we assume that the decision-maker receives a {\bf prediction} $a_t$ before selecting an order quantity $q_t \in Q$.\footnote{We are taking the predictions to be entirely deterministic, so for example, $a_t$ is not allowed to depend on the previously-observed demands $d_1,\ldots,d_{t-1}$. Our results hold if we extend to the setting in which the predictions are stochastic (and adapted to the demand filtration).} This prediction is meant to be an estimate of $\mu_t$, and so we measure the prediction error of a sequence $\bm{a}=\{a_1,\dots, a_T\}$ with respect to a sequence of means simply as $$\sum_{t=1}^{T}|a_t-\mu_t|.$$ Note that unlike demand variation, we have not used partitions here (and in fact, introducing partitions would not have any effect since we are measuring {\em absolute} rather than squared differences). Intuitively, we do not want to require the sequence of errors to be meaningful time-series: the predictions are generic, and their accuracy is allowed to change rapidly. Just as for the demand variation, the prediction error is expected to grow with the time horizon $T$, and the proper parameterization of this growth is via an exponent: we call the {\bf accuracy parameter} the smallest $a \in [0,1]$ such that the prediction error is at most $T^a$. We will always assume that $a$ is unknown to the decision-maker.
Naturally, the notion of a policy $\pi$ expands to include the predictions: $\pi=\{\pi_1,\dots,\pi_T\}$, where each $\pi_t$ is a mapping from $d_1,\dots, d_{t-1}$ and $a_1,\ldots,a_t$ to an order quantity $q_t\in Q$. The simplest policy, which “should” be used if the prediction error is known to be sufficiently small, is to simply behave as if the predictions were perfect. We call this the {\bf Prediction Policy} (Algorithm (ref)). The following observation collects a few (likely unsurprising) facts about the performance of this policy, with respect to worst-case regret (generalized in the “obvious” manner to incorporate prediction accuracy via the accuracy parameter $a$):
(ref)a) states that the Prediction Policy translates prediction error directly to regret (incidentally, it does this without “knowing” $a$). There are of course other ways in which the predictions could be used, but (ref)b) essentially states that there is nothing to be gained by doing so (even if $a$ is known). The proof of (ref)a) appears in Appendix (ref). (ref)b) is a direct corollary of (ref), which is given in the next subsection.
What exactly is achievable for the Nonstationary Newsvendor with Predictions depends heavily on whether or not $v$ and $a$ are known to the policy. To see this, it is worth first considering the two extremes.
\paragraph{ Case 1: Known $v$ and $a$:} A simple policy is available when $v$ and $a$ are both known. Compare the quantities $(3+v)/4$ and $a$. If the former quantity is smaller, apply the Fixed-Time-Window Policy. If the latter is smaller, apply the Prediction Policy. (ref) together imply that this achieves a worst-case regret of $O(T^{\min\{(3+v)/4,a\}})$. This is optimal, as demonstrated by the following result:
The proof of this result can be found in Appendix (ref), and relies on an explicit construction of a family of problem instances. Our construction breaks the total time horizon into cycles wherein the demand distribution is i.i.d.. We tune the length of each cycle to be small enough so that it is (provably) hard to detect the change in demand distributions and the predictions are essentially useless for most time periods in the cycle, and large enough so that the demand variation is within $T^v$ and the prediction error is within $T^a$.
\paragraph{ Case 2: Unknown $v$ and $a$:} At the opposite extreme, if $v$ and $a$ are both unknown, is it still possible to achieve $O(T^{\min\{(3+v)/4,a\}})$ worst-case regret? The answer is no:
(ref) states that the best we can hope for, when $v$ and $a$ are unknown, is a worst-case regret of at least $\Omega(T^{\max\{(3+v)/4,a\}})$. Indeed, it implies that no algorithm can achieve regret $O(T^{f(v,a)})$ for a function $f:[0,1] \times [0,1] \to [0,1]$ satisfying $f(v,a) \le \max\{(3+v)/4,a\}$ for all $v,a\in [0,1]$ and $f(v,a) < \max\{(3+v)/4,a\}$ for some $v,a\in [0,1]$. Note that (ref) shows {\em there exists} a pair of $v$ and $a$, and a corresponding problem instance, such that this lower bound holds. This is in contrast to a result showing that {\em for any} pair of $v$ and $a$, there exists a problem instance such that the lower bound holds, as is common in the literature (e.g. Theorem 1 of keskin2017chasing). This lower bound is easily achieved, for example by applying the Shrinking-Time-Window Policy or the Prediction Policy (or any blind randomization of the two). The proof of (ref) is in Appendix (ref). In contrast to Case 1, the lower bound construction here relies heavily on the fact that we do not know which one of $(3+v)/4$ and $a$ is smaller.
We have finally reached the problem which motivates this entire paper: designing an optimal policy for the Nonstationary Newsvendor with Predictions when the prediction error $a$ is unknown. We will assume that $v$ is known, since when $v$ is unknown, (ref) rules out the possibility of using the predictions to improve on what is already achievable without predictions. On the other hand, by (ref), the absolute best we could hope for is a policy which achieves a worst-case regret of $O(T^{\min\{(3+v)/4, a\}})$. In words, we would like a policy which, without knowing $a$, achieves the same regret had $a$ been known. Our main result is the design of such a policy.
Our policy is called the Prediction-Error-Robust Policy (PERP), and is given in Algorithm (ref). PERP utilizes the Fixed-Time-Window policy $\pi^{\mathrm{fixed}}$ in Section (ref) as an estimate of the true mean to track the quality of the predictions over time.
The intuition behind PERP is to follow the predictions until a time that is late enough to have evidence that the prediction quality is bad (compared to the Fixed-Time-Window Policy), while early enough to not incur much regret caused by the poor quality of the predictions. Because we do not observe the true past mean $\mu_t$ after time period $t$, we naturally use $\hat{\mu}_t^{\mathrm{fixed}}$ from the Fixed-Time-Window policy $\pi^{\mathrm{fixed}}$ as an estimation of $\mu_t$, and in turn keep tracking the cumulative difference the prediction quality $\left|a_t-\mu_t\right|$. We carefully choose the parameters in $\pi^{\mathrm{PERP}}$ so that this estimation is not accurate only with a small probability, and we can identify the prediction quality is bad if this cumulative difference is too large. By Proposition (ref), any policy can only achieve worst-case regret on the order of $T^{\min \{(3+v) / 4, a\}}$, so PERP is order-optimal.
\paragraph{ Aside: Unknown $v$ and Known $a$:} There are four possible scenarios depending on the knowledge of $v$ and $a$: known/unknown $v$ and known/unknown $a$. So far we have discussed three of them: known $v$ and $a$ ((ref)), unknown $v$ and $a$ ((ref)), and known $v$ and unknown $a$ ((ref)). For the sake of completeness, we discuss the remaining case of unknown $v$ and known $a$ in Appendix (ref), where we give a policy that achieves worst-case regret $\tilde{O}(T^{\min\{(3+v)/4, a\}})$. This is order-optimal by (ref).
Finally, we describe a set of experiments we performed to evaluate our policy (PERP) for the Nonstationary Newsvendor with Predictions. In all of our experiments, we compared PERP against the Shrinking-Time-Window Policy (NO-PRED) and the Prediction Policy (PURE-PRED). The main takeaways are:
The objective of our first batch of experiments was to fix one of the two theoretical parameters ($v$ or $a$) and test PERP's performance as the other parameters changes. To generate demand sequences, we used the parametric time-series model that corresponds to triple exponential smoothing (Holt Winters), a classic model for time-series data in the family of (ref). We give the exact formulas, and our choices of parameters, in Appendix (ref); for more on triple exponential smoothing, see winters1960forecasting. In our experiment, each demand sequence consisted of the demands for the next 365 time periods, with the realized demands generated as Poisson variables with the corresponding means. We ran two sets of experiments:
For each demand sequence and corresponding prediction, we ran NO-PRED, PURE-PRED, and PERP with equal overage and underage costs, and scaling constants $\kappa=\gamma=1$. Because the experiment was synthetic, the true underlying demand distribution was known at each time period. Therefore we also ran {\texttt OPT} as a benchmark, which simply ordered the optimal quantile at each time period. The variation parameter $v$ in PERP was calculated using the past demands of the pre-fixed 30 time periods by the definition in Section 2.2. We calculated the parameters $v$ and $a$ by their definitions (given in Section 2.2 and Section 4.1, respectively), scaled appropriately to make them lie in $[0,1]$. The resulted scatter plots are shown in (ref). In (a), $v$ is fixed, so the cost of NO-PRED (blue dots) is approximately the same for all instances. The cost of PURE-PRED (orange dots) is approximately exponential in $a$, which follows by (ref)a). In (b), $a$ is fixed, so the cost of \texttt{PURE-PRED} is approximately the same for all instances. The cost of \texttt{NO-PRED} is approximately exponential in $v$, which follows by (ref). Note that in both (a) and (b), the cost of \texttt{PERP} (green dots) is close to the minimal cost of \texttt{NO-PRED} and \texttt{PURE-PRED} across all instances, showing that \texttt{PERP}'s performance is robust in both $v$ and $a$.
We used real-world datasets to represent the “demand” sequences in our experiments. (ref) depicts example time series from each of these datasets. All datasets include {\em multiple} daily time series and are publicly available:
Each {\em instance} of our experiment represented a single Nonstationary Newsvendor with Predictions problem, with the realized demands taken from a single time series in our data (a single Rossmann store, a single language on Wikipedia, or a single restaurant). The overage and underage costs were constant within each instance, and without loss of generality the two costs for an instance can be characterized by the corresponding critical quantile (specifically the ratio of the underage cost to the sum). The time horizon for each instance was a set number of days taken from the end of the time series, with the preceding days used to train one of four prediction methods. These predictions were also updated over the course of the instance at a set frequency. For the Wikipedia dataset, this yielded a total of 2,880 possible instances, all of which were tested. The Rossmann dataset has multiple orders of magnitude more instances, so we randomly sampled 1,000 from this set. For the Restaurant dataset, we used a single prediction method to generate two sets of predictions for each restaurant: one only utilized the number of past visitors and the other incorporated the number of reservations as a feature, which gave 740 instances. (ref) describes all of the instances used.
For each instance, we applied NO-PRED, PURE-PRED, and PERP with scaling constants $\kappa=\gamma=1$, and the variation parameter $v$ in PERP was calculated using the past demands of the training data by the definition in Section 2.2. To generate predictions, we used four popular forecasting method ranging from classic to the state-of-the art:
For the Restaurant dataset, we used Prophet as the forecasting method, with and without the reservations as an additive linear feature. We treated the outputs of these methods as predictions of the {\em mean} demand. To estimate the demand distribution around this mean, we used the empirical distribution of the residuals of the same predictions on the training period.\footnote{That is, if the training data consists of $T_{\mathrm{train}}$ periods, which without loss we index as $\{t=-T_{\mathrm{train}}+1,T_{\mathrm{train}}+2,\ldots,-1,0\}$, then the demand distribution at any time $t$ was estimated to be $$\hat{\mu}_t+\text{Uniform}\left(\{d_s - \hat{\mu}_s: s=-T_{\mathrm{train}}+1,T_{\mathrm{train}}+2,\ldots,-1,0\}\right).$$} In practice, even if the prediction quality is good, the predictions of the first few days might incur large costs due to noise/instability of the predictions, which may cause PERP to misidentify the prediction quality. Therefore we restricted PERP to following the predictions for the first 20 days, only allowing switches afterward.
\paragraph{\bf Results:} Each instance yields three total costs: one incurred by PERP, and two incurred by the benchmark algorithms (NO-PRED and PURE-PRED). The primary performance metric we report is a form of optimality gap. For an instance $I$, let $\mathrm{cost}^{\mathrm{PURE-PRED}}(I)$ be the cost of PURE-PRED, and similarly define $\mathrm{cost}^{\mathrm{NO-PRED}}(I)$, $\mathrm{cost}^{\mathrm{PERP}}(I)$. Then the optimality gap (GAP) of PERP is defined as $$\mathrm{GAP}(I)=\frac{\mathrm{cost}^{\mathrm{PERP}}(I)-\min\{\mathrm{cost}^{\mathrm{PURE-PRED}}(I),\mathrm{cost}^{\mathrm{NO-PRED}}(I)\}}{ \left|\mathrm{cost}^{\mathrm{PURE-PRED}}(I) - \mathrm{cost}^{\mathrm{NO-PRED}}(I)\right| }.$$ If we think of PERP as trying to achieve the minimum of the costs incurred by the two benchmark policies, then GAP measures the excess cost that \texttt{PERP} incurs on top of this minimum, normalized so that $\mathrm{GAP}=0$ implies that the minimum has been achieved, and $\mathrm{GAP}=1$ implies that the maximum of the two costs was incurred.\footnote{GAP may technically be outside of $[0,1]$.}
Experiments on the datasets yielded the histograms in (ref). For each instance $I$, the value on the horizonal axis is $\log(\mathrm{cost}^{\mathrm{PURE-PRED}}(I)/\mathrm{cost}^{\mathrm{NO-PRED}}(I))$, which is greater than 0 if NO-PRED has a lower cost, and less than 0 if PURE-PRED has a lower cost. In the 1,000 Rossman instances NO-PRED had a lower cost 82.7% of the time, in the 2,880 Wikipedia instances NO-PRED had a lower cost 81.9% of the time, and in the 740 Restaurant instances NO-PRED had a lower cost 64.3% of the time. The values on the vertical axis are the GAPs. Note that most GAPs are small when the absolute values of the log difference are large. This shows PERP performs very well when the difference of costs between \texttt{NO-PRED} and \texttt{PURE-PRED} is large. On the other hand, there are instances where \texttt{PERP} has large GAPs, in particular there are instances with GAPs equal to 1 when the log difference of costs is close to 0. This happens because when the log difference of costs is close to 0, the cost of \texttt{NO-PRED} and the cost of \texttt{PURE-PRED} are close, so \texttt{PERP} may misidentify the prediction quality. Still, since the max cost and the min cost of the other two policies are close, even the GAPs are large in these instances, \texttt{PERP} does not perform badly.
We further divide the instances according to which of NO-PRED and PURE-PRED had lower cost in (ref) and (ref).
For comparison, if we did not know the prediction quality beforehand, uniformly random choosing between NO-PRED and PURE-PRED has an expected GAP of 0.5. Therefore PERP outperforms this natural benchmark in all cases of all datasets.
We proposed a new model incorporating predictions into the nonstationary newsvendor problem. We first gave a complete analysis of the Nonstationary Newsvendor (without predictions) by proving a lower regret bound and developing the Shrinking-Time-Window Policy, which was the first policy that achieves the lower bound up to log factors without knowing the variation parameter. We then considered the Nonstationary Newsvendor with Predictions and proposed the Prediction-Error-Robust Policy, which does not need to know the prediction quality beforehand, and achieves nearly optimal minimax worst-cast regret.