Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets
Zhuoxin Chen Will Ma

A Physics-Informed Machine Learning Approach for Solving Distributed Order Fractional Differential Equations
    Alireza Afzal Aghaeifn1cor1
    
============================================================================================================



§ ABSTRACT 
In the Newsvendor problem, the goal is to guess the number that will be drawn from some distribution, with asymmetric consequences for guessing too high vs. too low.
In the data-driven version, the distribution is unknown, and one must work with samples from the distribution.
Data-driven Newsvendor has been studied under many variants: additive vs. multiplicative regret, high probability vs. expectation bounds, and different distribution classes.
This paper studies all combinations of these variants, filling in many gaps in the literature and simplifying many proofs.
In particular, we provide a unified analysis based on the notion of clustered distributions, which in conjunction with our new lower bounds, 
shows that the entire spectrum of regrets between 1/√(n) and 1/n can be possible.





§ INTRODUCTION


1.5
In decision-making under uncertainty, one chooses an action a in the face of an uncertain outcome Z, and the loss incurred ℓ(a,Z) follows a given function ℓ.
In stochastic optimization, the outcome Z is drawn from a known distribution F, and the goal is to minimize the expected loss _Z∼ F[ℓ(a,Z)].
We let L(a) denote the expected loss of an action a, and a^* denote an optimal action for which L(a^*)=inf_a L(a).
In data-driven optimization, the distribution F is unknown, and one must instead work with independent and identically distributed (IID) samples drawn from F.
A data-driven algorithm prescribes an action  based on these samples, and one is interested in how its expected loss L() compares to the optimal expected loss L(a^*) from stochastic optimization.

This comparison can be made in a multitude of ways, differing along various dimensions.
First, one can measure either the difference L()-L(a^*) which is called the additive regret, or the scaled difference (L()-L(a^*))/L(a^*) which is called the multiplicative regret.
Second, note that both of these regrets are random variables, because L() depends on the IID samples drawn;
therefore, one can analyze either the probability that the regret is below some threshold, or analyze the expected regret.
Finally, different restrictions can be placed on the unknown distribution F.


In this paper we consider the multitude of ways in which L() has been compared to L(a^*) in the data-driven Newsvendor problem, starting with the work of <cit.>.
In the Newsvendor problem, action a represents an amount of inventory to stock, and outcome Z represents an uncertain demand to occur.
The loss function is given by

    ℓ(a,Z)=c_umax{Z-a,0}+c_omax{a-Z,0},

where c_u,c_o>0 represent the unit costs of understocking, overstocking respectively.
The goal in Newsvendor is to stock inventory close to demand, but err on the side of understocking or overstocking depending on how the costs c_u,c_o compare.
The optimal action when F is known involves defining q=c_u/c_u+c_o, and then setting a^* to be a q'th percentile realization from F, with q being called the critical quantile.



 §.§ Existing and New Results


We first define a restriction to be placed on the unknown distribution F, that is

similar to the notion of clustered distributions from <cit.> but used for a completely different problem.


Fix a Newsvendor loss function with critical quantile q∈(0,1).
For constants β∈[0,∞] and γ,ζ>0, a distribution with CDF F is said to be (β,γ,ζ)-clustered if

    |a-a^*|    ≤1/γ|F(a)-q|^1/β+1   ∀ a∈[a^*-ζ,a^*+ζ].



We make the following remarks on the definition of (β,γ,ζ)-clustered distributions.


  * Recall that a^* is an optimal action that is a q'th percentile realization from F. Intuitively, constraint (<ref>) is saying that for an action a far away from the optimal a^*, its quantile F(a) must also be far away from the critical quantile q.  This helps data-driven Newsvendor algorithms, whose actions  typically come with a guarantee on how close F() is to q, because constraint (<ref>) now implies a second guarantee on how close  is to a^*.


  * Because |F(a)-q|≤1, constraint (<ref>) is looser for larger β. It is not restricting F at all when β=∞.  On the other extreme, constraint (<ref>) is most restrictive when β=0, but is implied by F having a density that is at least γ over the interval [a^*-ζ,a^*+ζ] <cit.>, and our constraint is less restrictive because it does not impose the distribution to have a lower-bounded density over the entire interval.


  * Because F(a)∈[0,1], in order for there to exist any distributions satisfying (<ref>), one must have ζ≤1/γ(min{q,1-q})^1/β+1.  Therefore we will generally assume this about the parameters of (β,γ,ζ)-clustered distributions.




Having defined (β,γ,ζ)-clustered distributions, our main results are summarized in <Ref>.
To elaborate, we consider the standard Sample Average Approximation (SAA) algorithm for Newsvendor, which sets  equal to the q'th percentile of the empirical distribution formed by n IID samples.
We provide upper bounds on its additive and multiplicative regrets, that hold with high probability (i.e., with probability at least 1-δ for some small δ) and in expectation.
The O(·) notation highlights the dependence on n and δ, noting that the parameter β affects the rate of convergence as n→∞, whereas the other parameters q,γ,ζ may only affect the constants in front which are second order and hidden.
We recover convergence rates of n^-1/2 when β=∞ and n^-1 when β=0, which were previously known[These results are sometimes stated in terms of cumulative regret in their respective papers, in which case the n^-1/2 rate translates to ∑_n=1^N n^-1/2=Θ(√(N)) cumulative regret while the n^-1 rate translates to ∑_n=1^N n^-1=Θ(log N) cumulative regret.] in some cases as outlined in <Ref>.
Our results establish these convergence rates in all cases, unifying the literature, and moreover showing that the entire spectrum of rates from 1/√(n) (slowest) to 1/n (fastest) is possible as β ranges from ∞ to 0.

Our general upper bound of n^-β+2/2β+2 was achieved by the SAA algorithm, which did not need to know any of the parameters β,γ,ζ for the clustered distributions.
Meanwhile, our lower bound states that even knowing these parameters, any data-driven algorithm that draws n samples will incur Ω(n^-β+2/2β+2) additive regret with a constant probability.  This is then translated into similar lower bounds for multiplicative regret and in expectation.



  
Technical Highlights.
Our high-probability upper bounds are proven using the fact that F() is usually close to q, which follows the proof framework of <cit.>.  We extend their analysis to additive regret, and also show how to exploit assumptions about lower-bounded density (i.e., β=0) under this proof framework.
Moreover, we introduce the notion of clustered distributions for data-driven Newsvendor, which connects the two extremes cases of no assumption (β=∞) and lower-bounded density (β=0).

Our expectation upper bounds are proven by analyzing an integral (see (<ref>)) which follows <cit.>, who bounded the expected additive regret for β=0,∞.
We unify their results by considering all β∈[0,∞], and our β=0 result additionally allows for discrete distributions that are (0,γ,ζ)-clustered, instead of imposing that the distribution has a density.
Our proof also uses Chebyshev's inequality to provide tail bounds for extreme quantiles, which in our opinion simplifies the proof from <cit.>.
Finally, we recycle their integral to analyze expected multiplicative regret, which when β=∞ leads to a simplified proof of <cit.> on the exact worst-case expected multiplicative regret of SAA.

Our lower bound is based on a single construction that establishes the tight rate of Θ(n^-β+2/2β+2) for the entire spectrum of β∈[0,∞].
We construct distributions with low Hellinger distance between them <cit.>, which leads to simpler distributions and arguably simpler analysis compared to other lower bounds in the data-driven Newsvendor literature (e.g. <cit.>, <cit.>, <cit.>).  We also emphasize that in the special case where β=0, our lower bound of Ω(1/n) requires only two candidate distributions, instead of a continuum of candidate distributions and Bayesian inference à la the van Trees inequality <cit.>.  We provide a self-contained construction for β=0 using continuous distributions in <Ref>.



 §.§ Further Related Work




  
Learning theory.
Sample complexity has roots in statistical learning theory, which typically studies classification and regression problems under restricted hypothesis classes <cit.>.
Its concepts can also be extended to general decision problems <cit.>, or even specific inventory policy classes <cit.>.
However, data-driven Newsvendor results differ by considering multiplicative regret, having a specialized but unbounded loss function (there are no assumptions on demand being bounded), and typically requiring analyses that are tighter than uniform convergence.
In data-driven Newsvendor, it is also difficult to directly convert high-probability bounds into expectation bounds via an integral <cit.>, because the regret can be unbounded, while high-probability bounds only hold for small values of  (or equivalently, large values of n).
Our results further differ by considering specific restrictions on the distribution F.



  
Generalizations of data-driven Newsvendor.
Big-data Newsvendor is a generalization of data-driven Newsvendor where past demand samples are accompanied by contextual information, and the inventory decision can be made knowing the future context.
This model was popularized by <cit.>, and motivated by the notion of contexts from machine learning.
Meanwhile, data-driven inventory is a generalization of data-driven Newsvendor where one is re-stocking a durable good over multiple periods, that was also considered in the original paper by <cit.>.
Further variants of this model include learning censored demands <cit.>, capacitated order sizes <cit.>, lost sales <cit.>, and pricing <cit.>.
Our paper focuses on a single period without contexts, and does not aim to cover these generalizations.



§ PRELIMINARIES


In the Newsvendor problem, we make an ordering decision a, and then a random demand Z is drawn from a distribution with CDF F.
The domain for a, Z, and F is [0,∞).
The loss when we order a and demand realizes to be Z is defined as 
    ℓ(a,Z)=qmax{Z-a,0}+(1-q)max{a-Z,0},

for some known q∈(0,1), where we have normalized the unit costs of understocking, overstocking to be q,1-q respectively so that the critical quantile (as defined in the Introduction) is exactly q.
The expected loss of a decision a can be expressed as

    L(a)=_Z∼ F[ℓ(a,Z)]=∫_0^a (1-q)F(z) dz + ∫_a^∞ q(1-F(z))dz

following standard derivations based on Riemann-Stieltjes integration by parts.
We assume throughout that distribution F has finite mean; otherwise the expected loss of any decision is infinite.


The objective is to find an ordering decision a that minimizes the loss function L(a).
It is well-known that an ordering decision a is optimal if F(a)=q.
In general there can be multiple optimal solutions, or no decision a for which F(a) equals q exactly.
Regardless, an optimal solution a^*=F^-1(q)=inf{a:F(a)≥ q} can always be defined based on the inverse CDF, which takes the smallest optimal solution if there are multiple.
We note that by right-continuity of the CDF function, we have F(a^*)≥ q, and F(a)<q for all a<a^*.

In the data-driven Newsvendor problem, the distribution F is unknown, and instead must be inferred from n demand samples Z_1,…,Z_n that are drawn IID from F.
A general algorithm for data-driven Newsvendor is a (randomized) mapping from the demand samples drawn to a decision.
We primarily consider the Sample Average Approximation (SAA) algorithm, which constructs the empirical CDF (z)=1/n∑_i=1^n (Z_i≤ z) over z≥0 based on the samples, and then makes the decision =^-1(q)=inf{a:(a)≥ q}.
Similarly, we have ()≥ q, and (a)<q for all a<.

We are interested in the difference L()-L(a^*), which measures the loss of the SAA decision  in excess of that of the optimal decision a^*.  From (<ref>), we can see that

    L()-L(a^*)
       =∫_^a^* (q(1-F(z))-(1-q)F(z)) dz,    if ≤ a^* 
    ∫_a^*^ ((1-q)F(z)-q(1-F(z))) dz,    if >a^*
    
       =∫_^a^* (q-F(z)) dz.

We note L()-L(a^*) is a random variable, depending on the random demand samples drawn.
If we want to calculate its expectation, then from the linearity of expectation we can see that

    [L()]-L(a^*)
    =    [∫_0^∞((1-q)F(z)( > z) + q(1-F(z))(≤ z))dz] 
       -∫_0^a^* (1-q)F(z) dz -∫_a^*^∞ q(1-F(z))dz 
     =    ∫_0^∞ ((F(z) - qF(z))[ > z] + (q - qF(z))[≤ z])dz 
       -∫_0^a^* (F(z)-q F(z)) dz -∫_a^*^∞ (q-q F(z))dz 
     =    ∫_0^a^* (F(z)[ > z] + q[≤ z]-F(z)) dz + ∫_a^*^∞ (F(z)[ > z] + q[≤ z]-q)dz 
     =    ∫_0^a^* (q-F(z))[≤ z] dz + ∫_a^*^∞ (F(z)-q)[ > z] dz 
     =    ∫_0^a^*(q-F(z))[(z)≥ q]dz+∫_a^*^∞(F(z)-q)[(z)<q]dz.

To explain the final equality that leads to expression (<ref>):

if (z)≥ q, then =inf{a:(a)≥ q}≤ z from definition; otherwise, if (z)<q, then it is not possible for inf{a:(a)≥ q} to be as small as z because the function  is monotonic and right-continuous.

Hereafter we work only with expressions (<ref>), (<ref>), and (<ref>), omitting the random variable Z and implicitly capturing the dependence on random variables Z_1,…,Z_n through the empirical CDF .



§ HIGH-PROBABILITY UPPER BOUNDS


We first upper-bound the additive regret L()-L(a^*) incurred by the SAA algorithm.
When β<∞, the regret upper bound depends on the parameters β,γ from (β,γ,ζ)-clustered distributions, and the value of n at which our bound starts holding also depends on ζ.
When β=∞, parameters γ,ζ are irrelevant but the regret upper bound depends on q, being worse when q is close to 1, and also requires the distribution to have bounded mean, where we normalize this upper bound to 1.

 
Fix q∈(0,1) and β∈[0,∞],γ∈(0,∞),ζ∈(0,(min{q,1-q})^1/β+1/γ].

If β<∞, then whenever the number of samples satisfies n>log(2/δ)/2(γζ)^2β+2, we have

    L()-L(a^*)
    ≤1/γ(log(2/δ)/2n)^β+2/2β+2
    =O((log(1/δ)/n)^β+2/2β+2)

with probability at least 1-δ, for any δ∈(0,1) and any (β,γ,ζ)-clustered distribution.

If β=∞, then whenever the number of samples satisfies n≥2log(2/δ)/(1-q)^2, we have

    L()-L(a^*)
    ≤2/1-q√(log(2/δ)/2n)
    =O((log(1/δ)/n)^1/2)

with probability at least 1-δ, for any δ∈(0,1) and any distribution with mean at most 1.



By the DKW inequality <cit.>, we know that

    [sup_a≥0|(a)-F(a)|≤√(log(2/δ)/2n)]
    ≥ 1-2exp(-2n(√(log(2/δ)/2n))^2)=1-δ.

Therefore, with probability at least 1-δ, we have 

    sup_a≥0|(a)-F(a)|≤√(log(2/δ)/2n).

We will show that (<ref>) implies L()-L(a^*)≤1/γ(log(2/δ)/2n)^β+2/2β+2 when β∈[0,∞) (Case 1), and (<ref>) implies L()-L(a^*)≤2/1-q√(log(2/δ)/2n) when β=∞ (Case 2).

To begin with, we note that if ≤ a^*, then

    q-F()
    =()-()+q-F()
    ≤sup_a≥0|(a)-F(a)|

where the inequality holds because ()≥ q (by right-continuity of ). Otherwise if > a^*, then

    lim_a→^- (F(a)-q)
    =lim_a→^- (F(a)-q+(a)-(a) )
    ≤sup_a≥0|(a)-F(a)|

where the inequality holds because (a)<q for all a<.



  
Case 1: β∈[0,∞).
From the definition of (β,γ,ζ)-clustered distributions, we have

    F(a^*-ζ)≤ q-(γζ)^β+1<q-√(log(2/δ)/2n)
     F(a^*+ζ)≥ q+(γζ)^β+1>q+√(log(2/δ)/2n)

where the strict inequalities hold because n>log(2/δ)/2(γζ)^2β+2.
Applying (<ref>), we deduce that (a^*-ζ)<q and (a^*+ζ)>q.
From the definition of =inf{a:(a)≥ q}, we conclude that ≥ a^*-ζ and ≤ a^*+ζ respectively,

allowing us to apply the definition of (β,γ,ζ)-clustered distributions on .

When ≤ a^*, we derive from (<ref>) that

    L()-L(a^*)
    
    ≤(a^*-)(q-F())
    ≤1/γ(q-F())^1/β+1(q-F())
    =1/γ(q-F())^β+2/β+1,

where the second inequality applies the definition of clustered distributions.
By (<ref>) and (<ref>), we know L()-L(a^*)≤1/γ(log(2/δ)/2n)^β+2/2β+2.

On the other hand, when >a^*, we derive from (<ref>) that

    L()-L(a^*)
    
    ≤lim_a→^-(a-a^*)(F(a)-q)
    ≤lim_a→^-1/γ(F(a)-q)^1/β+1(F(a)-q)
    =1/γlim_a→^-(F(a)-q)^β+2/β+1,

where the first inequality follows from properties of the Riemann integral, and the second inequality applies the definition of clustered distributions.
This is at most 1/γ(log(2/δ)/2n)^β+2/2β+2 by (<ref>) and (<ref>).

Therefore, we conclude that
L()-L(a^*)≤1/γ(log(2/δ)/2n)^β+2/2β+2
holds universally for all possible values of  and a^* when β∈[0,∞).



  
Case 2: β=∞.
By the assumption that the mean of the distribution is no more than 1, we have

    ∫_0^∞(1-F(z))dz≤1.


When ≤ a^*, we derive

    ∫_0^∞(1-F(z))dz
        ≥∫_^a^*(1-F(z))dz
        ≥lim_a→ a^*-(a-)(1-F(a))
        ≥(a^*-)(1-q),

where the second inequality follows from properties of the Riemann integral, and the last inequality holds because F(a)<q for all a<a^*. This implies a^*-≤1/1-q.
Substituting into (<ref>), we have

    L()-L(a^*)
        =∫_^a^*(q-F(z))dz
        ≤(a^*-)(q-F())
        ≤1/1-q√(log(2/δ)/2n)≤2/1-q√(log(2/δ)/2n),

where the second inequality applies (<ref>) and (<ref>).

On the other hand, when >a^*, we similarly derive

    ∫_0^∞(1-F(z))dz
        ≥∫_a^*^(1-F(z))dz
        ≥(-a^*)lim_a→^-(1-F(a)),

where the second inequality is by properties of the Riemann integral.
Applying (<ref>), we obtain
(-a^*)lim_a→^-(1-F(a))≤1.
Meanwhile, we have

    lim_a→^-F(a)
        =lim_a→^-(F(a)-(a)+(a))
        ≤sup_a≥0|(a)-F(a)|+lim_a→^-(a)
        ≤√(log(2/δ)/2n)+q,

where the second inequality follows from (<ref>) and the fact that (a)<q for all a<. 
This is at most 1-q/2+q=1+q/2 by the assumption that n≥2log(2/δ)/(1-q)^2.
Substituting back into (-a^*)lim_a→^-(1-F(a))≤1, we derive -a^*≤1/1-1+q/2=2/1-q.
Substituting the final derivation into (<ref>), we get

    L()-L(a^*)
        =∫_^a^*(q-F(z))dz
        ≤(-a^*)lim_a→^-(F(a)-q)
        ≤2/1-q√(log(2/δ)/2n),

where the first inequality follows from the properties of the Riemann integral, and the second inequality uses (<ref>) and (<ref>).

Therefore, we conclude that
L()-L(a^*)≤2/1-q√(log(2/δ)/2n)
holds when β=∞.


We now upper-bound the multiplicative regret L()-L(a^*)/L(a^*) incurred by the SAA algorithm.  For multiplicative regret and β<∞, we need the further assumption that F(a^*-ζ),F(a^*+ζ) are bounded away from 0,1 respectively, to prevent the denominator L(a^*) from becoming too small.
In contrast to <Ref>, the regret upper bound for β<∞ now depends additionally on parameters ζ and τ, and the regret upper bound for β=∞ now worsens when q is close to 0 or 1 (whereas before it only worsened when q is close to 1).  This worsening when q is close to 0 or 1 has been shown to be necessary for multiplicative regret <cit.>.

 
Fix q∈(0,1) and β∈[0,∞],γ∈(0,∞),ζ∈(0,(min{q,1-q})^1/β+1/γ),τ∈(0,min{q,1-q}-(γζ)^β+1].

If β<∞, then whenever the number of samples satisfies n>log(2/δ)/2(γζ)^2β+2, we have

    L()-L(a^*)/L(a^*)≤1/γζτ(log(2/δ)/2n)^β+2/2β+2
    =O((log(1/δ)/n)^β+2/2β+2)

with probability at least 1-δ, for any δ∈(0,1) and any (β,γ,ζ)-clustered distribution satisfying F(a^*-ζ)≥τ, F(a^*+ζ)≤1-τ.

If β=∞, then whenever the number of samples satisfies n>log(2/δ)/2(min{q,1-q})^2, we have

    L()-L(a^*)/L(a^*)≤2/min{q,1-q}√(2n/log(2/δ))-1
        =O((log(1/δ)/n)^1/2)

with probability at least 1-δ, for any δ∈(0,1) and any distribution (with finite mean).


The β=∞ case was studied in <cit.>, who establish that n≥9/^2log(2/δ)/2(min{q,1-q})^2 samples is sufficient to guarantee a multiplicative regret at most , for ≤1.
In order to make our error bound of 2/min{q,1-q}√(2n/log(2/δ))-1 at most , we need n≥(2+)^2/^2log(2/δ)/2(min{q,1-q})^2, which always satisfies our condition of n>log(2/δ)/2(min{q,1-q})^2.
Therefore, the β=∞ case of our <Ref> can be viewed as an improvement over <cit.>, that holds for all >0, and moreover shows that a smaller constant is sufficient for ≤ 1 (because (2+)^2/^2≤9/^2).
We note however that a better dependence on min{q,1-q} was established in <cit.> for ≤1.


For β∈[0,∞), we derive from (<ref>) that

    L(a^*)   =∫_0^a^*(1-q)F(z)dz+∫_a^*^∞ q(1-F(z))dz 
       ≥∫_a^*-ζ^a^*(1-q)F(z)dz+∫_a^*^a^*+ζ q(1-F(z))dz 
       ≥∫_a^*-ζ^a^*(1-q)F(a^*-ζ)dz+∫_a^*^a^*+ζ q(1-F(a^*+ζ))dz 
       ≥∫_a^*-ζ^a^*(1-q)τ dz+∫_a^*^a^*+ζ qτ dz 
       =ζτ,

where the last inequality follows from the assumptions that F(a^*-ζ)≥τ and F(a^*+ζ)≤1-τ.

By <Ref>, we know that with probability at least 1-δ,
L()-L(a^*)≤1/γ(log(2/δ)/2n)^β+2/2β+2.
Therefore, we have that with probability at least 1-δ,
L()-L(a^*)/L(a^*)≤1/γζτ(log(2/δ)/2n)^β+2/2β+2.

The proof for β=∞ is deferred to <Ref>, due to similarities with <cit.>.




§ EXPECTATION UPPER BOUNDS

We first upper-bound the expected additive regret [L()]-L(a^*) incurred by the SAA algorithm. In contrast to <Ref>, here our regret upper bound for β<∞ depends on all three parameters β,γ,ζ and holds for all values of n, and also requires the distribution to have mean at most 1.  The regret upper bound for β=∞ still only has an inverse dependence on 1-q but not q.


Fix q∈(0,1) and β∈[0,∞],γ∈(0,∞),ζ∈(0,(min{q,1-q})^1/β+1/γ].

If β<∞, then we have

    [L()]-L(a^*) ≤2/γ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1+q+1/n(γζ)^β+1=O(n^-β+2/2β+2)

for any (β,γ,ζ)-clustered distribution with mean at most 1 and any number of samples n.

If β=∞, then we have

    [L()]-L(a^*)
           ≤(1/√(e)+2)1/(1-q)√(n)
        =O(n^-1/2)

for any distribution with mean at most 1 and any number of samples n.


For the β=0 and β=∞ cases, respective upper bounds of (n+q/1-q)exp[-2n(γζ)^2]+(2/1-q+1/2γ)1/n <cit.> and 4/(1-q)√(n) <cit.> were previously known,

both also under the assumption that the distribution has bounded[<cit.> assumed an upper bound of μ on the mean, instead of normalizing it to 1.  They also did not normalize the unit costs of understocking and overstocking to sum to 1.  The bounds we compare with here are obtained by substituting μ=1, ρ=q, and b+h=1 into their bounds.] mean.  Our upper bound for β=0 requires a less restrictive condition (based on clustered distributions) than the positive density condition in <cit.>.
Our upper bound for β=∞ has a better constant in front of 1/(1-q)√(n), because 1/√(e)+2<4.


We first consider the case where β=∞, and then the case where β∈[0,∞).



  
Case 1: β=∞.
Let a'=inf{a:F(a)≥ q+1-q/2√(n)}. We know a'≥ a^* from the definition of a^*=inf{a:F(a)≥ q}. Therefore, we derive from (<ref>) that

    [L()]-L(a^*) 
       =∫_0^a^*(q-F(z))[(z)≥ q]dz+∫_a^*^∞(F(z)-q)[(z)<q]dz 
       =∫_0^a^*(q-F(z))[(z)≥ q]dz+
    ∫_a^*^a'(F(z)-q)[(z)<q]dz+
    ∫_a'^∞(F(z)-q)[(z)<q]dz.


We note that if z<a^*, then q-F(z)>0 by definition of a^*, and we have

    [(z)≥ q]
        =[(z)-F(z)≥ q-F(z)]
        ≤exp(-2n(q-F(z))^2),

where the inequality follows from Hoeffding's inequality <cit.>. Otherwise if z≥ a^*, then F(z)-q≥0 by definition of a^*, and we have

    [(z)< q]
        =[F(z)-(z)> F(z)-q]
        ≤exp(-2n(F(z)-q)^2),

where the inequality again applies Hoeffding's inequality. So the first two terms in (<ref>) sum up to

    ∫_0^a^*(q-F(z))[(z)≥ q]dz+∫_a^*^a'(F(z)-q)[(z)<q]dz 
           ≤∫_0^a'|q-F(z)|exp(-2n|q-F(z)|^2)dz
        
       ≤a'/2√(en),

where the last inequality holds because the function g(x)=xe^-2nx^2 is at most 1/2√(en) for all x≥0.
Meanwhile, we derive

    ∫_0^∞ (1-F(z))dz
        ≥∫_0^a' (1-F(z))dz
        ≥lim_a→ a'^- a(1-F(a))
        ≥ a'(1-q-1-q/2√(n))
        ≥a'(1-q)/2,

where the second inequality follows from properties of the Riemann integral, the third inequality holds because F(a)<q+1-q/2√(n) for all a<a', and the last inequality holds for all positive integer n. Following the assumption that the mean of the distribution is no more than 1, we apply (<ref>) to deduce that a'≤2/1-q. Substituting this into (<ref>), we have

    ∫_0^a^*(q-F(z))[(z)≥ q]dz+
        ∫_a^*^a'(F(z)-q)[(z)<q]dz
           ≤1/(1-q)√(en).


For the third term in (<ref>), we have

    ∫_a'^∞(F(z)-q)[(z)<q]dz
           =∫_a'^∞(F(z)-q)[1/n∑_i=1^n(Z_i≤ z)<q]dz 
       =∫_a'^∞(F(z)-q)[1/n(n,F(z))< q]dz 
       =∫_a'^inf{a:F(a)=1}(1-F(z))dz(F(z)-q)[1/n(n,F(z))< q]/1-F(z)
       ≤sup_F∈[q+1-q/2√(n),1)(F-q)[1/n(n,1-F)≥ 1-q]/1-F,

where (n,F(z)) is a binomial random variable with parameters n and F(z), the second equality follows from the independence of samples, the third equality follows because [1/n(n,F(z))< q]=0 if F(z)=1, and the inequality uses ∫_a'^∞(1-F(z))dz≤∫_0^∞(1-F(z))dz≤1 by the assumption that the mean of the distribution is at most 1.

Consider a random variable X defined as 1/n(n,1-F). The expected value and variance of X are given by [X]=1-F and Var(X)=F(1-F)/n respectively. By Chebyshev's inequality <cit.>, we obtain that for all F∈[q+1-q/2√(n),1),

    [1/n(n,1-F)≥ 1-q]
        =[X≥ 1-q]
        
        ≤[|X-(1-F)|≥ F-q]
        ≤F(1-F)/n(F-q)^2.

Plugging it into (<ref>), we have 

    ∫_a'^∞(F(z)-q)[(z)<q]dz
        ≤sup_F∈[q+1-q/2√(n),1)F/n(F-q)≤2/(1-q)√(n).


Combining (<ref>) and (<ref>), we have
[L()]-L(a^*)≤(1/√(e)+2)1/(1-q)√(n).



  
Case 2: β∈[0,∞).
We decompose [L()]-L(a^*) into three separate parts as follows.
By (<ref>),

    [L()]-L(a^*)
           =∫_0^a^*(q-F(z))[(z)≥ q]dz+∫_a^*^∞(F(z)-q)[(z)<q]dz 
       =∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz+∫_a^*-ζ^a^*(q-F(z))[(z)≥ q]dz
         +∫_a^*^a^*+ζ(F(z)-q)[(z)<q]dz+∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz
       ≤∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz 
         +∫_a^*-ζ^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz 
         +∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz,

where the inequality is by Hoeffding's inequality.
We then analyze (<ref>), (<ref>), and (<ref>) separately.

For (<ref>), similar with the analysis of the third term in (<ref>) for the case where β=∞, we derive

    ∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz
           =∫_0^a^*-ζ(q-F(z))[1/n(n,F(z))≥ q]dz 
       =∫_0^a^*-ζ(1-F(z))dz(q-F(z))[1/n(n,F(z))≥ q]/1-F(z)
       ≤sup_F∈[0,q-(γζ)^β+1](q-F)[1/n(n,F)≥ q]/1-F
       ≤sup_F∈[0,q-(γζ)^β+1]F/n(q-F)
       ≤q/n(γζ)^β+1,

where the first inequality uses ∫_0^a^*-ζ(1-F(z))dz≤∫_0^∞(1-F(z))dz≤1 and F(a^*-ζ)≤ q-(γζ)^β+1 (by definition of clustered distributions), and the second inequality is by Chebyshev's inequality.

Similarly, for (<ref>) we have

    ∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz
           =∫_a^*+ζ^∞(F(z)-q)[1/n(n,F(z))< q]dz 
       =∫_a^*+ζ^inf{a:F(a)=1}(1-F(z))dz(F(z)-q)[1/n(n,F(z))< q]/1-F(z)
       ≤sup_F∈[q+(γζ)^β+1,1)(F-q)[1/n(n,1-F)≥ 1-q]/1-F
       ≤sup_F∈[q+(γζ)^β+1,1)F/n(F-q)
       ≤1/n(γζ)^β+1,

where the second equality follows because [1/n(n,F(z))< q]=0 if F(z)=1, the first inequality holds because ∫_a^*+ζ^∞(1-F(z))dz≤∫_0^∞(1-F(z))dz≤1 and F(a^*+ζ)≥ q+(γζ)^β+1 by definition of clustered distributions, and the second inequality follows from Chebyshev's inequality.

To analyze (<ref>), we need to consider two cases. When 1/2√(n)≥(γζ)^β+1, we know that ζ≤1/γ(1/2√(n))^1/β+1. Because the function g(x)=xe^-2nx^2 is at most 1/2√(en) for all x≥0, we obtain

    ∫_a^*-ζ^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz
        ≤∫_a^*-ζ^a^*+ζ1/2√(en)dz
        =ζ/√(en)≤2/γ√(e)(1/2√(n))^β+2/β+1.

On the other hand, for the case where 1/2√(n)<(γζ)^β+1, we know that 1/γ(1/2√(n))^1/β+1<ζ. Therefore, we can decompose (<ref>) into the following three terms:

    ∫_a^*-ζ^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz 
       =∫_a^*-ζ^a^*-1/γ(1/2√(n))^1/β+1|q-F(z)|exp[-2n|q-F(z)|^2]dz 
         +∫_a^*-1/γ(1/2√(n))^1/β+1^a^*+1/γ(1/2√(n))^1/β+1|q-F(z)|exp[-2n|q-F(z)|^2]dz 
         +∫_a^*+1/γ(1/2√(n))^1/β+1^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz .


When z∈[a^*-ζ,a^*-1/γ(1/2√(n))^1/β+1], we have

    |q-F(z)|
        ≥(γ|z-a^*|)^β+1≥(γ|a^*-(a^*-1/γ(1/2√(n))^1/β+1)|)^β+1
        =1/2√(n),

where the first inequality follows from definition of clustered distributions. Meanwhile, because the function g(x)=xe^-2nx^2 is monotonically decreasing on the interval [1/2√(n),∞), we obtain

    ∫_a^*-ζ^a^*-1/γ(1/2√(n))^1/β+1|q-F(z)|exp[-2n|q-F(z)|^2]dz
       ≤∫_a^*-ζ^a^*-1/γ(1/2√(n))^1/β+1(γ|z-a^*|)^β+1exp[-2n(γ|z-a^*|)^2(β+1)]dz.

Similarly, we derive that

    ∫_a^*+1/γ(1/2√(n))^1/β+1^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz
       ≤∫_a^*+1/γ(1/2√(n))^1/β+1^a^*+ζ(γ|z-a^*|)^β+1exp[-2n(γ|z-a^*|)^2(β+1)]dz.

Therefore, we can sum (<ref>) and (<ref>) to get

    (∫_a^*-ζ^a^*-1/γ(1/2√(n))^1/β+1+∫_a^*+1/γ(1/2√(n))^1/β+1^a^*+ζ)|q-F(z)|exp[-2n|q-F(z)|^2]dz
       ≤(∫_a^*-ζ^a^*-1/γ(1/2√(n))^1/β+1+∫_a^*+1/γ(1/2√(n))^1/β+1^a^*+ζ)
        (γ|z-a^*|)^β+1exp[-2n(γ|z-a^*|)^2(β+1)]dz.

To simplify the integral, we let x denote |z-a^*|, which yields

    (∫_a^*-ζ^a^*-1/γ(1/2√(n))^1/β+1+∫_a^*+1/γ(1/2√(n))^1/β+1^a^*+ζ)|q-F(z)|exp[-2n|q-F(z)|^2]dz 
       ≤2∫_1/γ(1/2√(n))^1/β+1^ζ(γ x)^β+1exp[-2n(γ x)^2β+2]dx 
       =2∫_1/γ(1/2√(n))^1/β+1^ζ(γ x)^2β+1/(γ x)^βexp[-2n(γ x)^2β+2]dx 
       ≤2/(1/2√(n))^β/β+1·exp[-2n(γ x)^2β+2]/2nγ(2β+2)|_ζ^1/γ(1/2√(n))^1/β+1
       ≤2/γ(β+1)(1/2√(n))^β+2/β+1,

where the last inequality holds because exp[-2n(γ x)^2β+2]|_ζ^1/γ(1/2√(n))^1/β+1≤exp[-2n(γ x)^2β+2]|_ζ^0≤1.

For (<ref>), because we have g(x)=xe^-2nx^2≤1/2√(en) for all x≥0, it follows that

    ∫_a^*-1/γ(1/2√(n))^1/β+1^a^*+1/γ(1/2√(n))^1/β+1|q-F(z)|exp[-2n|q-F(z)|^2]dz
           ≤∫_a^*-1/γ(1/2√(n))^1/β+1^a^*+1/γ(1/2√(n))^1/β+11/2√(en)dz 
       =2/γ√(e)(1/2√(n))^β+2/β+1.


Combining the results (<ref>) and (<ref>), we know that under the case where 1/2√(n)<(γζ)^β+1,

    ∫_a^*-ζ^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz
        ≤2/γ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1.

Note that this result is strictly greater than the result 2/γ√(e)(1/2√(n))^β+2/β+1 derived in (<ref>) for the case where 1/2√(n)≥(γζ)^β+1, so for any number of samples n, we have

    ∫_a^*-ζ^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz
        ≤2/γ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1.


Finally, by combining the results (<ref>), (<ref>), and (<ref>), we conclude that

    [L()]-L(a^*) ≤2/γ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1+q+1/n(γζ)^β+1

when β∈[0,∞).


We now upper-bound the expected multiplicative regret incurred by the SAA algorithm.  For multiplicative regret and β<∞, we need the further assumption that F(a^*-ζ),F(a^*+ζ) are bounded away from 0,1 respectively, to prevent the denominator L(a^*) from becoming too small.


Fix q∈(0,1) and β∈[0,∞], γ∈(0,∞), ζ∈(0,(min{q,1-q})^1/β+1/γ), τ∈(0,min{q,1-q}-(γζ)^β+1].

If β<∞, then we have

    [L()]-L(a^*)/L(a^*)≤max{1/n(γζ)^β+1min{q,1-q},2/γζτ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1}=O(n^-β+2/2β+2)

for any (β,γ,ζ)-clustered distribution satisfying F(a^*-ζ)≥τ, F(a^*+ζ)≤1-τ and any number of samples n.

If β=∞, then we have

    sup_F:μ(F)<∞[L()]-L(a^*)/L(a^*)   =max{sup_F∈(0,q)q-F/(1-q)F[1/n(n,F)≥ q],sup_F∈[q,1)F-q/q(1-F)[1/n(n,F) < q]}

for any number of samples n, where μ(F) denotes the mean of a distribution F, and (n,F) is a binomial random variable with parameters n and F.


The β=∞ case was studied in <cit.>, who characterized the exact value of sup_F:μ(F)<∞[L()]-L(a^*)/L(a^*) (instead of merely providing an upper bound), showing it to equal the expression in (<ref>).
This expression is then shown to be O(n^-1/2).
We derive the same expression using a shorter proof that bypasses their machinery, although their machinery has other benefits such as deriving the minimax-optimal policy (which is not SAA).
We note that an exact analysis of the worst-case expected additive regret sup_F:μ(F)<∞([L()]-L(a^*)) is also possible, even in a contextual setting <cit.>, but our simplification does not appear to work there.


For β∈[0,∞), we begin by using the same decomposition of [L()]-L(a^*) as in the proof of <Ref>. By (<ref>),

    [L()]-L(a^*)
       ≤∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz 
        +∫_a^*-ζ^a^*+ζ|q-F(z)|exp[-2n|q-F(z)|^2]dz
        +∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz
       ≤∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz+2/γ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1+∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz,

where the last inequality follows from (<ref>).

We similarly decompose L(a^*) into three terms as follows. By (<ref>),

    L(a^*) 
       =∫_0^a^* (1-q)F(z) dz+∫_a^*^∞ q(1-F(z))dz
       =∫_0^a^*-ζ (1-q)F(z) dz+(∫_a^*-ζ^a^* (1-q)F(z) dz+∫_a^*^a^*+ζ q(1-F(z))dz)+∫_a^*+ζ^∞ q(1-F(z))dz
       ≥∫_0^a^*-ζ (1-q)F(z) dz+τζ+∫_a^*+ζ^∞ q(1-F(z))dz,

where the last inequality applies (<ref>) given the assumption that F(a^*-ζ)≥τ, F(a^*+ζ)≤1-τ.

Therefore, we have

    [L()]-L(a^*)/L(a^*)
       ≤∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz+2/γ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1+∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz/∫_0^a^*-ζ (1-q)F(z) dz+τζ+∫_a^*+ζ^∞ q(1-F(z))dz
       ≤max{∫_0^a^*-ζ(q-F(z))[(z)≥ q]dz/∫_0^a^*-ζ (1-q)F(z) dz,2/γζτ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1,∫_a^*+ζ^∞(F(z)-q)[(z)<q]dz/∫_a^*+ζ^∞ q(1-F(z))dz}
       ≤max{sup_F∈(0,q-(γζ)^β+1](q-F)[1/n(n,F)≥ q]/(1-q)F, 
                2/γζτ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1, 
                sup_F∈[q+(γζ)^β+1,1)(F-q)[1/n(n,F) < q]/q(1-F)},

where the last inequality uses F(a^*-ζ)≤ q-(γζ)^β+1 and F(a^*+ζ)≥ q+(γζ)^β+1 from the definition of clustered distributions.

Next we analyze the maximum of the first and third terms in (<ref>). We derive

    max{sup_F∈(0,q-(γζ)^β+1](q-F)[1/n(n,F)≥ q]/(1-q)F,
        sup_F∈[q+(γζ)^β+1,1)(F-q)[1/n(n,F) < q]/q(1-F)}
       ≤max{sup_F∈(0,q-(γζ)^β+1]1-F/n(1-q)(q-F),sup_F∈[q+(γζ)^β+1,1)F/nq(F-q)}
       ≤max{1/n(1-q)(γζ)^β+1,1/nq(γζ)^β+1}
       =1/n(γζ)^β+1min{q,1-q},

where the first inequality follows from Chebyshev's inequality.

Substituting this into (<ref>), we have

    [L()]-L(a^*)/L(a^*)≤max{1/n(γζ)^β+1min{q,1-q},2/γζτ(1/β+1+1/√(e))(1/2√(n))^β+2/β+1}.


The proof for β=∞ is deferred to <Ref>, because it is simplifying an existing result from <cit.>.




§ ADDITIVE LOWER BOUND
 

We now lower-bound the additive regret of any (possibly randomized) data-driven algorithm for Newsvendor, showing it to be Ω(n^-β+2/2β+2) with probability at least 1/3.  This implies that the expected additive regret is also Ω(n^-β+2/2β+2).  The lower bound for multiplicative regret is similar, with the main challenge being to modify the distributions to satisfy F(a^*-ζ)≥τ,F(a^*+ζ)≤ 1-τ, so we defer it to <Ref>.

 
Fix q∈(0,1) and β∈[0,∞],γ∈(0,∞),ζ∈(0,(min{q,1-q})^1/β+1/γ].
Any learning algorithm based on n samples makes a decision with additive regret at least

    1/8max{γ,1}(q(1-q)/3√(n))^β+2/β+1=Ω(n^-β+2/2β+2)

with probability at least 1/3 on some (β,γ,ζ)-clustered distribution that takes values in [0,1].




Let C=q(1-q)/3, H=1/max{γ,1}(C/√(n))^1/β+1. Consider two distributions P and Q, whose respective CDF functions F_P and F_Q are:

    F_P(z)   =
        
            0,    z∈(-∞, 0)
    
            q+zC/H√(n),    z∈[0,H)
    
            1,   z∈[H,∞);
        
    
        F_Q(z)   =
        
             0,    z∈(-∞, 0)
    
            q+zC/H√(n)-C/√(n),    z∈[0,H)
    
            1,   z∈[H,∞).

We let L_P(a) and L_Q(a) denote the respective expected loss functions under true distributions P and Q, and from the CDF functions, it can be observed that the respective optimal decisions are a_P^*=0 and a_Q^*=H. We now show that any learning algorithm based on n samples will incur an additive regret at least 1/8max{γ,1}(q(1-q)/3√(n))^β+2/β+1 with probability at least 1/3, on distribution P or Q.



  
Establishing validity of distributions.
First we show that both P and Q are (β,γ,ζ)-clustered distributions. 
Note that the constraint ζ∈(0,(min{q,1-q})^1/β+1/γ] ensures that any z∈[a^*-ζ,a^*+ζ] with F(z)=0 or F(z)=1 would satisfy (<ref>); therefore it suffices to verify (<ref>) on z∈[0,H) for both P and Q. For distribution P, which has a^*=0, we have

    |F_P(z)-q|
        =zC/H√(n)
        =z/H(max{γ,1} H)^β+1
        =zmax{γ,1}^β+1H^β
        >(γ z)^β+1
        =(γ|z-0|)^β+1

for all z∈[0,H), where the second equality follows from C/√(n)=(max{γ,1} H)^β+1 and the inequality applies H>z. Therefore P is a (β,γ,ζ)-clustered distribution. 
It can be verified by symmetry that Q is also a (β,γ,ζ)-clustered distribution.

In addition, it can be elementarily observed that

    lim_z→ H^- F_P(z)=q+q(1-q)/3√(n)   ≤ q+1-q/3=1-2/3 (1-q) < 1
    
     F_Q(0)=q-q(1-q)/3√(n)   ≥ q-q/3=2/3 q > 0

which ensures the monotonicity of the CDF's for P and Q.

Finally, it is easy to see that H≤1, and hence both distributions P and Q take values in [0,1].



  
Upper-bounding the probabilistic distance between P and Q.
We analyze the squared Hellinger distance between distributions P and Q, denoted as H^2(P,Q).  Because P and Q only differ in terms of their point masses on 0 and H, standard formulas

for Hellinger distance yield

    H^2(P,Q)
    
       =1/2((√(q)-√(q-C/√(n)))^2+(√(1-q-C/√(n))-√(1-q))^2) 
       =1/2(q+q-C/√(n)-2√(q(q-C/√(n)))+1-q+1-q-C/√(n)-2√((1-q)(1-q-C/√(n)))) 
       =1/2(-2C/√(n)+2q-2q√(1-C/q√(n))+2(1-q)-2(1-q)√(1-C/(1-q)√(n))) 
       ≤1/2(-2C/√(n)+2q(C/2q√(n)+C^2/2q^2n)+2(1-q)(C/2(1-q)√(n)+C^2/2(1-q)^2n)) 
       =1/2(C^2/qn+C^2/(1-q)n) 
       =C^2/2nq(1-q),

where the inequality follows from applying 1-√(1-x)≤x/2+x^2/2, ∀ x∈[0,1].
We note that we are substituting in x=C/q√(n) and x=C/(1-q)√(n), which are at most 1 because C=q(1-q)/3.

Let P^n denote the distribution for the n samples observed by the algorithm under distribution P, and let Q^n denote the corresponding distribution under Q. Let TV(P^n,Q^n) denote the total variation distance between P^n and Q^n. By a relationship[Some sources such as <cit.> use a tighter upper bound of √(2H^2(P^n,Q^n)(1-H^2(P^n,Q^n)/2)) on TV(P^n,Q^n) (noting that their definition of H^2(P,Q) also differs, by not having the coefficient "1/2" in (<ref>)).  The weaker upper bound of √(2H^2(P^n,Q^n)) as used in <cit.> will suffice for our purposes.] between the total variation distance and Hellinger distance,


we have
    TV(P^n,Q^n)≤√(2H^2(P^n,Q^n)),
which is at most √(2nH^2(P,Q)) according to the additivity of the Hellinger distance.

By applying (<ref>), we obtain

    TV(P^n,Q^n)
        ≤C/√(q(1-q))
        =√(q(1-q))/3   ≤1/3.




  
Lower-bounding the expected regret of any algorithm.
Fix any (randomized) algorithm for data-driven Newsvendor, and consider the sample paths of its execution on the distributions P and Q side-by-side.  The sample paths can be coupled so that the algorithm makes the same decision for P and Q on an event E of measure 1-TV(P^n,Q^n)≥ 2/3, by definition of total variation distance.
Letting A_P,A_Q be the random variables for the decisions of the algorithm on distributions P,Q respectively,
we have that A_P and A_Q are identically distributed conditional on E.
Therefore, either [A_P≥H/2|E]=[A_Q≥H/2|E]≥1/2 or [A_P≤H/2|E]=[A_Q≤H/2|E]≥ 1/2.

First consider the case where [A_P≥H/2|E]=[A_Q≥H/2|E]≥1/2.
Note that if A_P≥H/2, then we can derive from (<ref>) that under the true distribution P,

    L_P(A_P) - L_P(a^*_P)
    ≥∫_0^H/2(F_P(z)-q)dz
    =∫_0^H/2 zC/H√(n) dz
    =CH/8√(n)
    =1/8max{γ,1}(q(1-q)/3√(n))^β+2/β+1.

Therefore, we would have

    [L_P(A_P)-L_P(a^*_P)≥1/8max{γ,1}(q(1-q)/3√(n))^β+2/β+1]
    ≥[A_P≥H/2]
    ≥[A_P≥H/2|E][E]≥1/2·2/3=1/3.


Now consider the other case where [A_P≤H/2|E]=[A_Q≤H/2|E]≥ 1/2.
If A_Q≤H/2, then we can similarly derive from (<ref>) that under the true distribution Q,

    L_Q(A_Q) - L_Q(a^*_Q)
    ≥∫_H/2^H(q-F_Q(z))dz
    
    =∫_H/2^H(C/√(n)- zC/H√(n)) dz
    =CH/8√(n)
    =1/8max{γ,1}(q(1-q)/3√(n))^β+2/β+1.

The proof then finishes analogous to the first case.


abbrvnat






§ Β=∞ CASES OF MULTIPLICATIVE REGRET




 §.§ High-probability Upper Bound
 

We prove <Ref> for β=∞.
To do so, we first analyze the case where ≤ a^*. We derive from (<ref>) that

    L(a^*)
        ≥∫_^a^* (1-q)F(z) dz
        ≥(1-q)F()(a^*-)
        ≥(1-q)(q-sup_a≥0|(a)-F(a)|)(a^*-),

where the last inequality follows from (<ref>). By (<ref>) and the assumption that n>log(2/δ)/2(min{q,1-q})^2, we have q>√(log(2/δ)/2n)≥sup_a≥0|(a)-F(a)|.
This enables us to derive from (<ref>) that

    L()-L(a^*)/L(a^*)   =∫_^a^* (q-F(z)) dz/L(a^*)
       ≤(a^*-)(q-F())/(1-q)(q-sup_a≥0|(a)-F(a)|)(a^*-)
       ≤sup_a≥0|(a)-F(a)|/q(1-q)-(1-q)sup_a≥0|(a)-F(a)|,

where the second inequality applies (<ref>).

For the case where >a^*, by (<ref>) and properties of the Riemann integral, we have

    L(a^*)
        ≥∫_a^*^ q(1-F(z)) dz
        ≥lim_a→^-q(1-F(a))(a-a^*)
        ≥ q(1-q-sup_a≥0|(a)-F(a)|)(-a^*),

where the last inequality follows from (<ref>).
By (<ref>) and the assumption that n>log(2/δ)/2(min{q,1-q})^2, we have 1-q>√(log(2/δ)/2n)≥sup_a≥0|(a)-F(a)|.
Therefore, we derive from (<ref>) that

    L()-L(a^*)/L(a^*)   =∫_a^*^ (F(z)-q) dz/L(a^*)
       ≤lim_a→^-(a-a^*)(F(a)-q)/q(1-q-sup_a≥0|(a)-F(a)|)(-a^*)
       ≤sup_a≥0|(a)-F(a)|/q(1-q)-qsup_a≥0|(a)-F(a)|,

where the first inequality is by properties of the Riemann integral, and the last inequality uses (<ref>).

Combining (<ref>) and (<ref>), we conclude that

    L()-L(a^*)/L(a^*)   ≤sup_a≥0|(a)-F(a)|/q(1-q)-max{q,1-q}sup_a≥0|(a)-F(a)|
       =sup_a≥0|(a)-F(a)|/max{q,1-q}(min{q,1-q} - sup_a≥0|(a)-F(a)|)
       ≤2sup_a≥0|(a)-F(a)|/min{q,1-q} - sup_a≥0|(a)-F(a)|

holds for both cases. Applying (<ref>), we have that with probability at least 1-δ,

    L()-L(a^*)/L(a^*)≤2√(log(2/δ)/2n)/min{q,1-q}-√(log(2/δ)/2n)
        =2/min{q,1-q}√(2n/log(2/δ))-1.




 §.§ Expectation Upper Bound
 

We see from (<ref>) and (<ref>) that

    [L()]-L(a^*)    =∫_0^a^*(q-F(z))[(z)≥ q]dz+∫_a^*^∞(F(z)-q)[(z)<q]dz
    
     L(a^*)    =∫_0^a^* (1-q)F(z) dz+∫_a^*^∞ q(1-F(z))dz.

Hence for any distribution with finite mean,

    [L()]-L(a^*)/L(a^*)   =∫_0^a^*(q-F(z))[(z)≥ q]dz+∫_a^*^∞(F(z)-q)[(z)<q]dz/∫_0^a^* (1-q)F(z) dz+∫_a^*^∞ q(1-F(z))dz
       ≤max{∫_0^a^*(q-F(z))[(z)≥ q]dz/∫_0^a^* (1-q)F(z) dz,∫_a^*^∞(F(z)-q)[(z)<q]dz/∫_a^*^∞ q(1-F(z))dz}
       =max{sup_F∈(0,q)q-F/(1-q)F[1/n(n,F)≥ q],sup_F∈[q,1)F-q/q(1-F)[1/n(n,F) < q]}.

This completes the upper bound on sup_F:μ(F)<∞[L()]-L(a^*)/L(a^*).

Next we show that this bound is tight. By symmetry, we assume the maximum is achieved at some F∈(0,q). Consider a Bernoulli distribution which takes the value 0 with probability F. Then we know that a^*=1, and the CDF of this distribution is

    F(z)=
            0,    z<0
    
            F,    z∈[0,1)
    
            1,    z≥1.

So for this Bernoulli distribution, we derive from (<ref>) and (<ref>) that

    [L()]-L(a^*) 
        
           =∫_0^1 (q-F)[(z)≥ q]dz
        =(q-F)[1/n(n,F)≥ q]
    
        L(a^*) 
        
           =∫_0^1(1-q)F dz
        =(1-q)F.

This implies
[L()]-L(a^*)/L(a^*)=q-F/(1-q)F[1/n(n,F)≥ q],
which shows that (<ref>) is tight and that the supremum in sup_F:μ(F)<∞[L()]-L(a^*)/L(a^*) can be achieved by Bernoulli distributions.



§ MULTIPLICATIVE LOWER BOUND
 

We now lower-bound the multiplicative regret of any data-driven algorithm, showing it to be Ω(n^-β+2/2β+2) with probability at least 1/3, which implies also a lower bound of Ω(n^-β+2/2β+2) on the expected multiplicative regret.

 
Fix q∈(0,1) and β∈[0,∞],γ∈(0,∞),ζ∈(0,(min{q,1-q})^1/β+1/γ),τ∈[0,min{q,1-q}-(γζ)^β+1].
Any learning algorithm based on n samples makes a decision with multiplicative regret at least

    1/16γζτ+8q(1-q)((q-τ)(1-q-τ)/3√(n))^β+2/β+1
        =Ω(n^-β+2/2β+2)

with probability at least 1/3 on some (β,γ,ζ)-clustered distribution satisfying F(a^*-ζ)≥τ and F(a^*+ζ)≤1-τ.



Let C=(q-τ)(1-q-τ)/3, H=1/γ(C/√(n))^1/β+1.
Consider two distributions P and Q, whose respective CDF functions F_P and F_Q are:

    F_P(z)   =
        
            0,    z∈(-∞, 0)
    τ,    z∈[0,2ζ)
    
            q+C(z-2ζ)/H√(n),    z∈[2ζ,2ζ+H)
    
            1-τ,    z∈[2ζ+H,4ζ+H)
    
            1,   z∈[4ζ+H,∞);
        
    
        F_Q(z)   =
        
            0,    z∈(-∞, 0)
    τ,    z∈[0,2ζ)
    
            q+C(z-2ζ-H)/H√(n),    z∈[2ζ,2ζ+H)
    
            1-τ,    z∈[2ζ+H,4ζ+H)
    
            1,   z∈[4ζ+H,∞).

We let L_P(a) and L_Q(a) denote the respective expected loss functions under true distributions P and Q, and from the CDF functions, it can be observed that the respective optimal decisions are a_P^*=2ζ and a_Q^*=2ζ+H. We now show that any learning algorithm with n samples will incur a multiplicative regret at least 1/16γζτ+8q(1-q)((q-τ)(1-q-τ)/3√(n))^β+2/β+1 with probability at least 1/3, on distribution P or Q.



  
Establishing validity of distributions.
First we show that both P and Q are (β,γ,ζ)-clustered distributions. 
For distribution P, which has a^*=2ζ, it suffices to verify (<ref>) on z∈[ζ,3ζ]. We split the interval into segments [ζ,2ζ) and [2ζ,3ζ].
When z is in the first segment, F_P(z)=τ, so

    |F_P(z)-q|=q-τ≥(γζ)^β+1≥(γ |z-2ζ|)^β+1,

where the first inequality follows from τ∈(0,min{q,1-q}-(γζ)^β+1], verifying (<ref>).
When z is in the second segment, for the case where ζ<H, it suffices to verify (<ref>) on z∈[2ζ,2ζ+H). We have

    |F_P(z)-q|
        =C(z-2ζ)/H√(n)
        =γ^β+1H^β(z-2ζ)
        >(γ|z-2ζ|)^β+1,

where the second equality applies C/√(n)=(γ H)^β+1 and the inequality follows from H>z-2ζ, verifying (<ref>).
On the other hand, for the case where ζ≥ H, it remains to verify (<ref>) on z∈[2ζ+H,3ζ]. We have F_P(z)=1-τ, so

    |F_P(z)-q|=1-τ-q
        ≥(γζ)^β+1≥(γ|z-2ζ|)^β+1,

where the first inequality follows from τ∈(0,min{q,1-q}-(γζ)^β+1], again verifying (<ref>). 
Therefore P is a (β,γ,ζ)-clustered distribution. 
It can be verified by symmetry that Q is also a (β,γ,ζ)-clustered distribution.

In addition, because C=(q-τ)(1-q-τ)/3, we obtain using the fact τ<q<1-τ that

    lim_z→ (2ζ+H)^-F_P(z)   =q+C/√(n)=q+(q-τ)(1-q-τ)/3√(n)<q+1-q-τ/3<1-τ≤1
    
        F_Q(2ζ)   =q-C/√(n)=q-(q-τ)(1-q-τ)/3√(n)>q-q-τ/3>τ≥0

which ensures the monotonicity of the CDF's for P and Q.

Finally, we have

    F_P(ζ)=τ≤ F_Q(ζ+H)
    
        F_P(3ζ)≤1-τ=F_Q(3ζ+H),

which ensures  F(a^*-ζ)≥τ and F(a^*+ζ)≤1-τ for both P and Q.



  
Upper-bounding the probabilistic distance between P and Q. 
We analyze the squared Hellinger distance between distributions P and Q.  Because P and Q only differ in terms of their point masses on 2ζ and 2ζ+H, standard formulas for Hellinger distance yield



    H^2(P,Q)
       =1/2((√(q-τ)-√(q-τ-C/√(n)))^2+(√(1-q-τ-C/√(n))-√(1-q-τ))^2)
    
           =1/2(-2C/√(n)+2(q-τ)-2(q-τ)√(1-C/(q-τ)√(n))+2(1-q-τ)-2(1-q-τ)√(1-C/(1-q-τ)√(n)))
       ≤1/2(-2C/√(n)+2(q-τ)(C/2(q-τ)√(n)+C^2/2(q-τ)^2n)+2(1-q-τ)(C/2(1-q-τ)√(n)+C^2/2(1-q-τ)^2n))
       =1/2(C^2/(q-τ)n+C^2/(1-q-τ)n),

where the inequality follows from 1-√(1-x)≤x/2+x^2/2, ∀ x∈[0,1].
We note that we are substituting in x=C/(q-τ)√(n) and x=C/(1-q-τ)√(n), which are at most 1 because C=(q-τ)(1-q-τ)/3.

Similar with the analysis in the proof of <Ref>, we have

    TV(P^n,Q^n)
           ≤√(2H^2(P^n,Q^n))
       ≤√(2nH^2(P,Q))
       ≤ C√(1/q-τ+1/1-q-τ)
       =√((q-τ)(1-q-τ)(1-2τ))/3
       ≤1/3.




  
Lower-bounding the expected regret of any algorithm.
Fix any (randomized) algorithm for data-driven Newsvendor, and consider the sample paths of its execution on the distributions P and Q side-by-side.  The sample paths can be coupled so that the algorithm makes the same decision for P and Q on an event E of measure 1-TV(P^n,Q^n)≥ 2/3, by definition of total variation distance.
Letting A_P,A_Q be the random variables for the decisions of the algorithm on distributions P,Q respectively,
we have that A_P and A_Q are identically distributed conditional on E.
Therefore, either [A_P≥2ζ+H/2|E]=[A_Q≥2ζ+H/2|E]≥1/2 or [A_P≤2ζ+H/2|E]=[A_Q≤2ζ+H/2|E]≥ 1/2.

First consider the case where [A_P≥2ζ+H/2|E]=[A_Q≥2ζ+H/2|E]≥1/2. By (<ref>), we have

    L_P(a_P^*)
           =∫_0^2ζ (1-q)τ dz+∫_2ζ^2ζ+H q(1-q-C(z-2ζ)/H√(n))dz+∫_2ζ+H^4ζ+H qτ dz
       =2ζτ+q(1-q)H-qCH/2√(n)
       <2ζτ+q(1-q)/γ,

where the inequality follows from H=1/γ(C/√(n))^1/β+1≤1/γ and qCH/2√(n)>0.
Note that if A_P≥2ζ+H/2, then we can derive from (<ref>) that under the true distribution P,

    L_P(A_P) - L_P(a^*_P)
    
    ≥∫_2ζ^2ζ+H/2(F_P(z)-q)dz
    =∫_2ζ^2ζ+H/2C(z-2ζ)/H√(n)dz
    =CH/8√(n)
    =1/8γ((q-τ)(1-q-τ)/3√(n))^β+2/β+1.

Therefore, we would have

    L_P(A_P)-L_P(a^*_P)/L_P(a^*_P)
    >1/16γζτ+8q(1-q)((q-τ)(1-q-τ)/3√(n))^β+2/β+1

with probability at least 
[A_P≥2ζ+H/2]
≥[A_P≥2ζ+H/2|E][E]
≥1/2·2/3
=1/3.

Now consider the other case where [A_P≤2ζ+H/2|E]=[A_Q≤2ζ+H/2|E]≥ 1/2.
By (<ref>), we have

    L_Q(a_Q^*)
           =∫_0^2ζ(1-q)τ dz+∫_2ζ^2ζ+H(1-q)(q+C(z-2ζ-H)/H√(n))dz+∫_2ζ+H^4ζ+H qτ dz
       =2ζτ+q(1-q)H-(1-q)CH/2√(n)
       <2ζτ+q(1-q)/γ

where the inequality follows from H≤1/γ and (1-q)CH/2√(n)>0. 
If A_Q≤2ζ+H/2, then we can derive from (<ref>) that under the true distribution Q,

    L_Q(A_Q) - L_Q(a^*_Q)
    
    ≥∫_2ζ+H/2^2ζ+H(q-F_Q(z))dz
    =∫_2ζ+H/2^2ζ+HC(2ζ+H-z)/H√(n) dz
    =CH/8√(n)
    =1/8γ((q-τ)(1-q-τ)/3√(n))^β+2/β+1.

The proof then finishes analogous to the first case.




§ CONTINUOUS LOWER BOUND FOR Β=0
 

We provide a self-contained lower bound of Ω(1/n) using two continuous distributions, which contrasts other lower bounds (see <cit.>) that use a continuum of continuous distributions.
Our two distributions are obtained by modifying those from <Ref> (which had point masses on 0 and H) to be continuous in the case where β=0.

 
Fix q∈(0,1) and γ∈(0,∞).
Any learning algorithm based on n samples makes a decision with additive regret at least

    q^2(1-q)^2/72max{γ,1}n=Ω(1/n)

with probability at least 1/3 on some continuous distribution with density at least γ over an interval in [0,1].



Let C=q(1-q)/3, H=C/max{γ,1}√(n). 
Fix η∈(0,min{min{q,1-q}-C/√(n)/γ,1/3q}].
Consider two distributions P and Q, whose respective CDF functions F_P and F_Q are:

    F_P(z)   =
        
            0,    z∈(-∞, 0)
    q/ηz,    z∈[0,η)
    
            q+C/H√(n)(z-η),    z∈[η,H+η)
    
            q+C/√(n)+1-q-C/√(n)/η(z-H-η),    z∈[H+η,H+2η)
    
            1,   z∈[H+2η,∞);
        
    
        F_Q(z)   =
        
            0,    z∈(-∞, 0)
    q-C/√(n)/ηz,    z∈[0,η)
    
            q-C/√(n)+C/H√(n)(z-η),    z∈[η,H+η)
    
            q+1-q/η(z-H-η),    z∈[H+η,H+2η)
    
            1,   z∈[H+2η,∞).

From the CDF functions, it can be observed that F_P(z), F_Q(z) are continuous, and that the respective optimal decisions are a_P^*=η and a_Q^*=H+η. We now show that any learning algorithm based on n samples will incur an additive regret at least q^2(1-q)^2/72max{γ,1}n with probability at least 1/3, on distribution P or Q.


It is easy to see that P and Q are continuous distributions with a positive density over interval [0,H+2η], where H+2η≤ C+ 2/3q ≤ 1.  To see that this density is at least γ, we need to check that all of the slopes

    q/η, C/H√(n), 1-q-C/√(n)/η, q-C/√(n)/η, 1-q/η

are at least γ.  We first derive that C/H√(n)=max{γ,1}≥γ.  We next derive that

    q/η≥q-C/√(n)/η≥q-C/√(n)/(min{q,1-q}-C/√(n)/γ)≥γ.

Similarly, we derive that

    1-q/η≥1-q-C/√(n)/η≥1-q-C/√(n)/(min{q,1-q}-C/√(n)/γ)≥γ

which completes the verification that P and Q have density at least γ over an interval in [0,1].


We next analyze the squared Hellinger distance between P and Q. Because the PDF's of P and Q only differ on [0,η) and [H+η,H+2η), standard formulas for Hellinger distance yield

    H^2(P,Q)
       =1/2∫_0^η(√(q/η)-√(q-C/√(n)/η))^2dz+1/2∫_H+η^H+2η(√(1-q/η)-√(1-q-C/√(n)/η))^2dz 
       =1/2(q+q-C/√(n)-2√(q(q-C/√(n)))+1-q+1-q-C/√(n)-2√((1-q)(1-q-C/√(n)))).

Note that this is the same as (<ref>). Therefore, following the analysis in the proof of <Ref>, we conclude that TV(P^n,Q^n)≤1/3.

Fix any (randomized) algorithm for data-driven Newsvendor, and consider the sample paths of its execution on the distributions P and Q side-by-side.  The sample paths can be coupled so that the algorithm makes the same decision for P and Q on an event E of measure 1-TV(P^n,Q^n)≥ 2/3, by definition of total variation distance.
Letting A_P,A_Q be the random variables for the decisions of the algorithm on distributions P,Q respectively,
we have that A_P and A_Q are identically distributed conditional on E.
Therefore, either [A_P≥H/2+η|E]=[A_Q≥H/2+η|E]≥1/2 or [A_P≤H/2+η|E]=[A_Q≤H/2+η|E]≥ 1/2.

First consider the case where [A_P≥H/2+η|E]=[A_Q≥H/2+η|E]≥1/2.
Note that if A_P≥H/2+η, then we can derive from (<ref>) that under the true distribution P,

    L_P(A_P) - L_P(a^*_P)
    
    ≥∫_η^H/2+ηC/H√(n)(z-η) dz
    =C^2/8max{γ,1}n
    =q^2(1-q)^2/72max{γ,1}n

Therefore, we would have

    [L_P(A_P)-L_P(a^*_P)≥q^2(1-q)^2/72max{γ,1}n]
    ≥[A_P≥H/2+η]
    ≥[A_P≥H/2+η|E][E]≥1/2·2/3=1/3.


Now consider the other case where [A_P≤H/2+η|E]=[A_Q≤H/2+η|E]≥ 1/2.
If A_Q≤H/2+η, then we can similarly derive from (<ref>) that under the true distribution Q,

    L_Q(A_Q) - L_Q(a^*_Q)
    
    
    ≥∫_H/2+η^H+η(C/√(n)- C/H√(n)(z-η)) dz
    =C^2/8max{γ,1}n
    =q^2(1-q)^2/72max{γ,1}n

The proof then finishes analogous to the first case.


