Beyond IID: data-driven decision-making in heterogeneous environments
Authors: Omar Besbes
Will Ma
Omar Mouchtaki
Venue: NeurIPS 2022 Accept (2022)
Keywords: data-driven algorithms
non-IID
sample average approximation
pricing
ski-rental
newsvendor

Abstract: In this work, we study data-driven decision-making and depart from the classical identically and independently distributed (i.i.d.) assumption.  We present a new framework in which  historical samples   are generated from unknown and different distributions, which we dub  \textit{heterogeneous environments}.  These distributions are assumed to lie in a heterogeneity ball with known radius and centered around the (also) unknown future (out-of-sample) distribution on which the performance of a decision will be evaluated. We quantify the asymptotic worst-case regret that is achievable by central data-driven policies such as Sample Average Approximation, but also by rate-optimal ones,   as a function of the radius of the heterogeneity ball. Our work shows that the type of achievable performance varies considerably across different combinations of problem classes and notions of heterogeneity. We demonstrate the versatility of our framework by comparing achievable guarantees for the heterogeneous version of widely studied  data-driven problems such as  pricing, ski-rental, and newsvendor. 
En route, we establish a new connection between data-driven decision-making and distributionally robust optimization.

Beyond IDD: data-driven decision-making in heterogeneous environments
Omar Besbes"
Will Ma
Omar Mouchtaki
Decision, Risk, and Operations Division
Columbia University
{ob2105, wm2428, om2316 Bgggb. columbia.edi
Abstract
In this work, we study data-driven secision-making and depart from the classical identically and independently distributed (i.i.d.) assumption. We present a new framework in which historical samples are generated from unknown and different distributions, which we dub heterogeneous environments. These distributions are assumed to lie in heterogeneity ball with known radius and centered around the (also) unknown future (out-of-sample) distribution on which the performance of a decision will be evaluated. We quantify the asymptotic worst-case regret that is achievable by central data-driven policies such as Sample Average Approximation, but also by rate-optimal ones, a function of the radius of the heterogeneity ball. Our work shows that the type of achievable performance varies considerably across different combinations of problem classes and notions of heterogeneity. We demonstrate the versatility of our framework by comparing achievable guarantees for the heterogeneous version of widely studied data-driven problems such pricing, ski-rental, and newsvendor. En route, we establish a new connection between data-driven decision-making and distributionally robust optimization.
Introduction
In optimization under uncertainty, the desirability of a decision (e.g., inventory) depends on an unknown future outcome (e.g., demand). Typically, past data is collected to be indicative of the future, and hence inform our decision. However, ideal data-driven decision-making requires postulating beliefs about the reliability of the past data, and importantly, whether the future may deviate from In practice, past data may depend on contexts, some of which can be controlled for, and some of which cannot (unobserved confounders). This may introduce data heterogeneity that is not "correctable." "
In this paper, we consider a framework for modeling how the future may deviate from past data. At high level, it accomplishes three goals: i.) capture different forms of future deviation, including central policy, which
no deviation, under the same umbrella; ii.) understand the performance makes the decision that optimizes the average objective value over past data, under different forms of unexpected deviation; dii.) if the central policy performs poorly, then derive modifications that are robust different forms of anticipated deviation, and quantify the achievable performance.
This framework is general, capturing different problems, and our analysis leads to insightful problem- specific conclusions. The only assumption is that the policy defined in ii.) above can be computed, which requires perfect counterfactual evaluation of any decision on all data points, as opposed to settings where past data affected by previous actions [5] 16
42 43). The policy described in it.) widely studied across different fields, known as Sample Average Approximation (SAA)
33
41
37 36 39). although we emphasize that also derive policies beyond SAA when it falters.
Authors ordered alphabetically.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Framework description
Framework (Section 2.1 Our first contribution lies in studying framework which models the future outcome as being drawn from an unknown distribution, and past data as being drawn independently from (also unknown) "nearby" distributions. In this way, past data is indicative of the future, and we emphasize that the samples of data can be drawn from different nearby distributions. In accord, we call this setting a heterogeneous environment. Using varying definitions of "nearby distribution" (e.g. based on Kolmogorow/ Wasserstein distances; see Section L.3 we analyze different forms of deviation possible between the past and future, and let a radius bound the allowed deviation. When O, our framework captures the classical independent and identically distributed (i.i.d.) setting, in which past data are drawn from the same distribution as the future outcome [37 45 4]. This framework presents another possible parametrization to interpolate between the i.i.d. setting and the adversarial one and shares conceptually similar goals to previous approaches considering algorithm analysis beyond worst-case [51] 7 [53
25
10 (4].
Performance measure (Section 2.2) We consider the performance of different data-driven policies, which map past data into a decision for given problem; SAA defines feasible data-driven policy for any problem. Regret is measured as the difference in objective between the policy's s decision and the optimal decision knowing the future distribution, taking an expectation over the draws of past data (which affect the policy's decision), any intrinsic randomness in the policy, and the outcome realization (which affects the objective of both the policy's decision and the optimal decision). We then take worst case regret over all possible distributions that could have been chosen for the future outcome and the data points, to evaluate the performance of fixed data-driven policy. We note that this performance depends on the problem (see Section [.3] for examples), the number of data points n, the definition of "nearby distribution," and the radius c.
1.2 General results
Our second contribution lies in developing a set of general results for this framework. A central result we present in Section is general reduction we develop in Theorem which we establish the following: asymptotically, as the number of samples goes to oo, the worst-case regret of a policy (in broad subclass call cimppll-szzeagnostii is upper- bounded by that of alternative problem with two major simplifications: i.) the worst-case is now taken over only a single distribution for historical environments opposed to a sequence of heterogencous distributions; and ii.) the decision- maker (DM) has access to the exact historical distribution. This upper bound can be seen as uniform distributionally robust optimization problem under a regret performance metric, and offers a systematic way to derive upper bounds for policies of interest. This result is closely related to equation (7) in [46] and discuss in detail the connections to their result after stating Theorem []]
We develop function of the future outcome that materializes (Section E In that case, we establish in Theorem 2 that SAA scales linearly in for both the Kolmogorov and Wasserstein forms of deviation. We also show that for this class of problems, the Lipschitz constant characterizes the hardness of the instance.
indeeeeiddeeeneentt results that hold whenever the objective function is Lipschitz as a
1.3 Problem-specine deviation-specife results
Our third contribution lies in deriving problem-specife conclusions in our general heterogeneous environments. In particular, we consider three classical problems in the context of our framework- newsvendor, pricing, and ski-rental that have received significant attention in the literature across Operations Research, Economics, and Computer Science in the known-prior, data-driven, distribu- tionally robust, adversarial, and advice-augmented settings. Problem-specifii results are obtained by using: i.) our general reduction and results to upper-bound their asymptotic worst-case regret, and ii.) a combination of algorithm design and the development of impossibility results (lower bounds) on the worst-case regret. We analyze the regret for the SAA policy as well as alternative policies.
Problem descriptions. First, we consider the newsvendor problem (Section 4.1 1, in which DM must decide how much capacity or inventory to plan in the face of unknown demand. The objective to minimize the sum of underage cost, paid for each unit by which capacity falls short of realized demand, and overage cost, paid for each unit of capacity in excess of demand that needs to sit idle. This is a foundational problem in Operations Research, with early focus on the setting where the demand distribution is known [see 47). and since then studied in various distributionally robust

---

settings but also in data- ones 40 [5 tradeoff in guessing an unknown value when there are asymmetric consequences for going under/over.
54 22 49]
Newsvendor captures the fundamental
Second, we consider the single-item pricing problem (Section 5.1 in which a DM must find the best price to offer customer with unknown willingness pay (wtp). The objective is maximize revenue. This is a foundational problem in Economics, with early focus on the setting with known
prior [see 48 52] and more recently in data-driven [2] 29 2 I7 and distributionally robust
12
23
settings. Pricing captures the fundamental tradeoff' between margin and volume.
Finally, consider the ski-rental problem (Section 5.2). in which DM must decide each day whether to buy skis or keep renting, without knowing the length of their trip. The objective is to minimize total cost, where buying eliminates the rental cost going forward. Although typically presented as an online problem that requires a decision to be made every day, any (randomized) buy- or-rent policy can be described by a (randomized) duration for which to rent skis, before committing to buying (if the trip has not ended by then). This is a foundational problem in Computer Science, critical to the development of competitive analysis [see [[]] which considers the adversarial setting where nothing is known, and recently also important to the development of advice- andiice-uugmened algorithms which receive prediction on the length of the ski trip [50 19]. Ski rental captures the fundamental tradeoff between proceeding with a suboptimal process vs. paying the cost of refactoring.
Definitions of "nearby distribution." " Our framework generally models past data to be drawn from distributions that lie within an e-distance of the future distribution, for any notion of distance between probability distributions. For our problems of interest, we focus Kolmogorov and Wasserstein (see Section 2. for formal definitions). This dichotomy suffices to demonstrate the importance of distance metric in determining performance in our problems of interest, and moreover, represents contrasting inductive philosophies about how the future might deviate from the past: Wasserstein allows every data point be erroneous by e, whereas Kolmogorov allows an e fraction of data points to be arbitrarily erroneous. We note that similar notions of "nearby distributions" were considered in [5T] in the online learning setting and in 7 Example 5] for the expert selection problem. Our work differs from these two papers because we consider an offline setting and our benchmark stronger since we focus on the oracle knowing the ground-truth out-of out-of-sample distribution, as opposed to the "best action in hindsight" benchmark.
specific distance metrics:
SAA vs. robustified policies. Finally, performance is demarcated by the policy used. We first provide tight asymptotic performance bounds for the SAA policy, which we note is agnostic to the heterogeneity that might arise. We then analyze the best-possible asymptotic performance bounds that can be achieved by any policy when the notion of distance and the radius are known.
In Table we present high level summary of our results across problem classes. We assume that the support of the unknown environment is in [0, .M] for some positive real number M which M can be interpreted as parametrizing the "extent" of uncertainty one faces (e.g., maximal values of demand in newsvendor) We track the dependence on both the heterogeneity radius e, as well as M. These results are for the asymptotic setting in which n co.
Kolmogorov
Wasserstein
SAA
((Me)
Lipschitz
Newsvendor ($4.1)
best policy SAA
O(Me)
O(e)
((Me)
(2(M)
Pricing 5.11
best policy
(Mc)
@(VMc)
Beyond Lipschitz
SAA best policy
(Me)
@(1)
Ski-rental 5.5.
Ō(e)*
@(VE)
Table 1: SAA and achievable performance for different problem classes and heterogeneity balls.
*(Here ê provides rate order up to logarathimic factors.)
For newsvendor problems, through combination of the general result for Hipschiz--ontinnen problems and lower bounds, we show that SAA actually achieves the optimal rate for asymptotic worst-case regret both as a function of e and M and that this rate is linear.
We then turn to problems whose objective is not Lipschitz. For the pricing problem, we establish that while under Kolmogorov distance, SAA is near-optimal and the optimal performance is again
3

---

of order Mc, the picture is starkly different under the Wasserstein distance. In this case, SAA has arbitrarily poor performance. We then show that robustification procedure that deflates SAA by an appropriate factor can yield the best achievable asymptotic worst-case regret that shrinks to zero at rate VMc. To our understanding, analyzing these non-SAA policies (which are required for good performance on pricing) deviates from standard analyses used in learning theory (see Remark (
A second prototypical problem that is not Lipschitz is the ski-rental problem. While SAA was near-optimal for the Kolmogorov distance for pricing and newsvendor, we establish the surprising fact that SAA, even under the Kolmogorov distance, has arbitrarily poor performance. Indeed, its asymptotic worst-case regret scales as θ (Me), while the optimal policy achieves a performance of @ (e). As a consequence, the performance of SAA can be arbitrarily worse than the optimal one as the support grows to infinity. Meanwhile, for the Wasserstein distance, we show that the performance of SAA is also suboptimal. Indeed, Indeed, SAA incurs regret of (1); but by inflating SAA appropriately, one can construct a policy that achieves order /e performance, which is the best dependence on c.
These examples demonstrate that SAA fails for both heterogeneity types for ski-rental, but also more broadly the intricate interplay between problem class and type of heterogeneity.
Connection to offline data corruption models. Different notions of offline data corruptions and
robustness have been previously studied in statistics [0, 26
learning theory [55 28
35
34
55
38
18 8 20 and, more recently in revenue management 13 14, 23 Most approaches consider
e-contamination settings [30] in which the adversary can shift a small proportion of data arbitrarily far from the true distribution. They consider either oblivious adversaries who fix a single corrupted distribution from which samples are generated or adaptive one who observe samples before corrupting them. [8] establishes that adaptive adversaries yield equivalent performance to oblivious ones in many settings. Closest to us are [12 [23] who study optimal auctions. They assume the distribution is common across all past observations; the former focuses on regret and the the latter ratio metric when data is generated from MHR distributions close in Kolmogorov distance. The framework we develop is anchored around setting that allows for heterogeneous "nearby" distributions for each past observation, and is general in that it allows us to unify a variety of problems/metrics and highlight how these affect the levels of achievable performance.
Connection online and batch learning in non-stationary environments. Our work also relate broadly to papers studying learnability in changing environment. [27 9 adopt universal learning approach and analyze algorithms which are able to achieve vanishing long-term average loss for general data-generation processes. 44 3 46 derive generalization guarantees in a setting where the
training set distribution may differ from the test set distribution.
2 Problem formulation: data-driven decisions in heterogeneous environments
We consider general stochastic optimization problem in which a DM wants to optimize an objective in stochastic environment. Formally, we denote by X' the decision space and by E the space of environment realizations. The objective of the DM is represented by a function which maps each pair of decision & E X' and environment realization & E E to an objective value.
X x E + R
The DM faces a subset of possible probability measures P C A (E), where A (E) denotes the space of probability measures supported on E. For every probability measure μ P, the goal of the DM is to optimize the objective defined as
X X-R R x + Egna [g(x,
g (.H)):
We extend the definition of 9 (-, (4) to allow for randomized decisions E A (X),, in which case we define G (p. (1) Ezzp [9 (I. n)] also take an expectation over the randomized decision.
Remark that depending on the nature of the problem, the objective could represent for example a function to maximize (profit) or to minimize (cost). In turn, we formally define for every μ E P. the optimal objective opt(μs) as the objective value achieved by an optimal action, given by an oracle operator ORACLE that is mapping from A (E) to X.

---

2.1 Heterogeneous environments
In the absence of distributional knowledge on the underlying environment, a common approach consists in assuming that historical samples are independent and identically drawn from a fixed probability measure μ. We relax the assumption that the samples are identically distributed and introduce a generalization of this framework that we refer to as s-heterogeneity.
Let d P P R be metric on P. Given target probability measure fa P and level of heterogeneity 6, we define the heterogeneity ball anchored around μa and with radius c as
(e(x)= {u E P, s.t (u, E
The heterogeneity ball (1) includes all distributions that within a distance of from μ. Next, we formally define a data-driven decision-making problem in a heterogeneous environment.
Definition (Data-driven decision-making problem in heterogeneous environment). A data- driven decision-making problem in heterogeneous environment is defined by the tuple: (X,E, d. g. ORACLE), where X is the set of possible actions, E the environment space, P is the space of measures nature can select from, d is metric on the space of measures, 9 is an objective function, and ORACLE is a mapping from environment measures target actions.
Focal metrics. The definition above is general, and the framework can be applied to a variety of metrics. In this work, we aim at developing an understanding of the effect of heterogeneity under various metrics and problem classes. We focus on two prototypical and central distances; Kolmogorov and Wasserstein. We formally define them in one dimension as follows.
Definition 2 (Kolmogorov and Wasserstein distances). Given environment spuce E C R and subset of probability meusures P supported on E, the Kolmogorov (resp. Wasserstein) distance dk (resp. dw) is defined for every P1, 42 as
/
dx (Mi, M2) -sup (F((E) F2(() and dw (21
(EF(E) F2(E)) dε, JSEE
EEE
where F1 (resp. F2) is the cumulative distribution associated with P1 (resp. (2).
Note that when E is compact interval of I., both distances are related for every pii μ12 P, dw (μ), u2) S diam 3 dk (11,
2.2 Data-driven policies and performance
Data-driven policies. In most settings, the probability measure l is unknown to the DM and the optimal objective орt(μ) not achievable. turn, the DM observes sequence of historical samples E1, fi,E2,...,4, En. representing the previous environment realizations. A data-driven policy is then a mapping from the past samples (randomized) decision. Define the empirical measure fign
1 Σ
Pegn (E) = n
1 E, =.)
for every & E E.
i=1
In a setting in which the order of the samples does not matter (as the one we will consider), to represent policy taking as input < : E.), one only needs to consider mappings that take as input the number of samples and the empirical measure. We define a data-driven policy as mapping from No x P to A (2t), the space of measures on the action space X, that associates (n, j)) to distribution of actions π (r., ft). We let II denote the set of all such mappings. We assume that such a mapping can be made with knowledge of the metric d and radius e. Moreover, we say that æ is in which case write π (ā)) for brevity.
sample-size-gnnosii if its decision does not depend
widely-studied policy that achieves excellent performance across a vast range of data-driven decision-making problems is Sample Average Approximation (SAA). Given an empirical distribution ü., SAA (denoted by SAAA selects the target action ORACLE (p), the best action associated with p.
Performance through worst-case regret. Given an out-of-sample distribution E P the best achievable objective is opt(p). For sequence of historical distributions VI,...:/4 Un. in Ue (n), the expected objective of a policy π is
Egron I9 (T (gg) ), 40].
5

---

In turn, we define the expected (absolute) regret of policy π II against an out-of-sample distribution j E P and sequence of n historical distributions PI....,22 Un E (1(
Rn (T,, ,4, VI,...., pn) := - [C (I (g" [)] - opt(p))
We note that we use the absolute value in this definition, as our framework applies to minimization and maximization problem. Once the type of problem is specified (i.e., the operator associated with ORACLE), this definition of regret coincides with the usual regret for minimization or maximization problems, as we will see in Sections 4 and S
when describing specific applications.
In this work. we will assess the performance of policy based on its worst-case expected regret. Given an instance I = (X, E, P, d.g. ORACLE), we define the worst-case expected regret of a data-driven policy т E for a degree of heterogeneity e 2 as
RZ,n (c) == sup
sup MEP P. (U,(p)
Rn (T, M.......... 1n))
(3)
We finally define the worst-cuse asymptotic regret a data-driven policy π E a e-heterogeneous environment as the number of samples grows large as
R I (c) == lim sup Di (c). n2 11+000
(4)
We sometimes write oo oo (c) instead of 9 (c) when the problem class is specified
to highlight the dependence on the Kolmogorov or Wasserstein metrics.
3 Reduction to distributionally robust optimization in the asymptotic regime
A significant challenge in the analysis of problem (4) stems from the difficulty to characterize potentially complex worst-case sequence of historical probability measures vi,.... Un and out-of- sample measure J.. We illustrate in the appendix that analyzing every element in the sequence of historical probability measures as a function of n is priori challenging as nature will attempt to use different distributions for each of the past environments. We will show that, asymptotically, it suffices to consider cases in which nature selects a common distribution for all of the past environments. Formally, define for simpple-izz--anostte policy ı E II the following optimization problem:
sup sup (opt(μ) (T(
(5)
pEP (E))
While Problem 5 resembles Problem (3), it differs on two crucial dimensions: i.) in Problem (5) nature selects the same distribution in the heterogeneity ball for all past environments; ti.) in Problem (5), the policy π is assumed to know the actual distribution of the past environments v, whereas in Problem 3 the policy only observed the empirical distribution of past realizations.
Next, we will establish that Problems (5) and are tightly connected under some mild assumptions. We introduce the following definition on the distance d defining the heterogeneity.
Definition (Empirical triangular convergence). We say that a distance d on the space of probability measures satisfies the empirical triangular convergence (ETC) property if and only if for every triangular array sequence of probability measures Siismeee all belonging to P, we have
lim d(pn: Fm))
a.s.,
n-+00
where (L)(E) = : 1 for samples Ei,n ~ Pi,n and fr, = a E Pin.-
The ETC property requires that the sequence of empirical distributions converges to the average of ground truth distributions for arbitrary triangular arrays. In what follows we also impose convexity on the metric d. We note that both properties are satisfied by many common distances on probability spaces, including the Kolmogorov and Wasserstein distances on compact sets, as we discuss in the appendix. We now state our first main result which establishes fundamental reduction.
Theorem (Upper bound reduction). Given an instance I = (X², E.P.P.d g. ORACLE), let π E be sample-size simplle-size-ane -igo-tagootic policy. Assume that g is bounded on X x E and that d is convex metric which satisfies the empirical triangular convergence property. Then
RT (t)
< lim sup sup (opt(μ)) g (T(P).
(6)
n- PEP (E),

---

Theorem establishes, that under some mild conditions, in the asymptotic regime, one may restrict attention problem (5). This reduction significantly simplifies the analysis of sample-size -ize--asssi-
policies" as problem () does not involve any form of randomness in the input received by the policy, and only allows the adversary to select a single distribution.
Remark (Relation (4 We note that 146 eq. (7) presents a finite-time bound the regret of SAA in a similar setting to ours. Therefore by taking the limit in their bound, one may derive an asymptotic performance guarantee for SAA. In our notation, their result imply that,
R7.00
susu sup sup 19 (I, - 9 (.
(7)
MEP vell (nr) zEX
Theorem 7 differs from because reduction applies to any policy in the wide range of sample- size-agnostic policies. In particular, this enables us to characterize the minimax optimal asymptotic regret even when SAA is not (rate) optimal (see Sections (.7and555 a.2
We also show the appendix that Theorem holds whenever E is finite without restricting the policy.
4 Lipschitz-continuous problems
In this section, we study broad class of problems for which the underlying objective function g(z, is Hppschttz-oontinuuu as function of the environment.
Theorem 2 (Upper bounds for Lipschitz-continuou objectives). Suppose that Egr [0, M) for some M > O. Let Ix (X, E, P, dx. .. ORACLE) and Iw (X, P.W, 9. ORACLE) be instances of the data-driven decision problem under the Kolmogorov and Wasserstein distances, respectively. Assume that for every x E X, the function g(x, :) is L--Lipschitz-contnuonn and that DRACLE is either a minimization or maximization oracle. Then for every 2 O.
ox (c) 2L M.C
and
Iw (c) 2L.
Theorem 2 implies that for this class of problems, the asymptotic regret of SAA vanishes as the radius of the heterogeneity ball goes to O. Furthermore, this theorem shows that the dependence of the asymptotic worst-case regret in the heterogeneity parameter e is at most linear. We show next that this dependence is the best possible for this class of problems and this notion of heterogeneity.
4.1 Newsvendor problem
Recall the newsvendor problem described in Section 1.3 Using M > 0 to denote an upper bound on demand, we let = = X [0, M), and our regret bounds may (or may not) depend on M. The objective function is the newsvendor cost which is parameterized by two quantities: cu the underage cost and e the overage cost. The cost of inventory level r E X when observing demand & E E is,
g(x, e, (E .r) co 1o--3 =)
:=max(= where (.)+ := max(- (- 0} is the positive part operator. The measure space P is the set of probability measures on E without restrictions and for every 4 E P, we define the cost of the oracle as opt(μ) mingex G (x, uu). Therefore the oracle mapping is defined as ORACLE l + arg min 9 (xc 14).
We note that the objective function g satisfies the l--ipschitz-contiiitty property on the environment realization variable & with L = max C.). Theorem 2 thus directly yields an upper bound on the achievable regret for this class of problems, for both Kolmogorov and Wasserstein, through the regret of SAA. We next show that these dependencies are the best possible, under any policy.
Proposition (Heterogeneous newsvendor). For the data- driven newsvendor problem a heteroge- nous environment under the Kolmogorov and Wasserstein distances, given any 0.
Cu
M inffxen 0%.00 S P3 (.
2 max (Cus co) - M,
2
Gu + Co
< inf
Ry W. (t) < R W. (e) <
2 max (Cus Co) e.
2
NNte that considering sample-size waw-ssiizzzasssiie policies is not very restrictive. As we will see in Section this class is sufficient to achieve optimal rates for the asymptotic worst-case regret function of c.
4 and
7

---

Proposition first shows that SAA is robust to deviation under multiple forms of heterogeneity and that the regret scales linearly with the radius of the heterogeneity ball for both distances. We show furthermore that the linear dependence is, for the newsvendor problem, the best rate achievable for any data-driven policy. We also note that the lower bound obtained for the newsvendor depends linearly on the Lipschitz constant I. through the factor (cu + Co).
Beyond newsvendor, the asymptotic worst-case regret of SAA over the general class of L-Lipschitz- continuous functions is of the order θ (L.e). This suggests that the performance of SAA may deteriorate for problems in which the objective function g is not smooth.
5
Beyond Lipschitz-continuuus problems
5.1 Pricing problem
Recall the pricing problem presented in Section 1.3 The environment space E = [0, M] represents the set of possible wtp. Similarly, the set of possible prices X is [0, M). The of considered probability measures P is the whole set of probability measures on [0, MM without restriction. The revenue generated by the DM with price decision
X when facing a customer with wtp f E E is,
g <) = x. 1 {}.
Therefore for any probability measure/ μ E P associated with the cumulative distribution F, we have that 9 (x, μt) = x1 - F(z)). The goal of the DM is to set a price x in order to maximize its revenue. Equivalently, the goal is to minimize the regret against the oracle which posts the optimal price given a wtp distribution. Formally, the oracle operator is defined as, ORACLE 1 + arg max,ex 9 (I, p))
Kolmogorov pricing, Remark that the pricing objective is not bupschitz-continuuse and that one cannot use the argument presented in Section 4.1 We show in the appendix that despite the lack of smoothness of the objective, SAA is still near-optimal in the asymptotic regime under the Kolmogorov distance. We derive an upper bound on the asymptotic worst-case regret SAA and matching universal lower bound showing that the best achievable performance is order θ (Me).
Failure of SAA in pricing with Wasserstein heterogeneity. In opposition to the strong performance achieved by SAA for pricing against Kolmogorov heterogeneity, our next proposition shows that this result does not hold if one considers instead the Wasserstein heterogeneity ball.
Proposition (SAA and Wasserstein pricing). For the data-driven pricing problem a heterogenous environment under the Wasserstein distance, we have for e >> 0 that
(c) M.
Proposition shows that, in stark contrast with Lipschitz problems, for the pricing problem, the asymptotic regret of SAA under Wasserstein heterogeneity does not shrink to zero as goes to zero. As matter of fact, the regret of M the worst possible, as the revenue of the oracle is bounded from above by M and the revenue of any data-driven policy is bounded from below by O. Quite notably, this result holds for any level of heterogeneity e, and an arbitrarily small deviation from the i.i.d. case leads to extremely poor performance, even with infinite data. We next propose a policy which "robustifies" SAA and we analyze it under the Wasserstein distance.
Robustification of SAA for Wasserstein pricing. The key challenge in pricing is that for two distributions μ and y such that dw (p, v) is arbitrarly small, price x could have high revenue for μ but a low revenue for v, and the difference in revenue between distributions may be arbitrarily large. This enabled us construct an instance for which the optimal price for the in-sample distribution generates a low revenue for the oft-of-sample distribution μ.
Remark 2 (Proof Sketch, Comparison with Standard Techniques). To the best of our understanding,
our analysis of policies beyond SAA requires a new technique. Assume M 1 for brevity, and consider the problem of pricing. We need to upper-bound the loss G (ORACLE (n), ,4) 9 (T()) A standard analysis of SAA, which satisfies 3AAA (v) = ORACLE (V), would write,
& (ORACLE (p) .4) G (ORACLE (V) .1) S 2 sup [( R)) G(x,
#eX
8

---

However, for certain decisions x, the error 6| (z, - G (z, can be non-vanishing even if the distance dw (w.())) v/) is vanishing. Our fix is the following, For a generic policy x. we write
G(ORACLE (1), .p) (TT))), p) & (G(ORACLE (14) 14) ((T(p))
+ (G(ORACLE (V) ,D) ((T())),
(8)
The key observation is that if we set T(V) not to ORACLE (V), but to ORACLE (v) - 5, then both large parentheses in (8) can be (identically) upper- hooper- using the relation we introduce in Proposition 3 Proposition 3. Let a and E annd let 21 and x2 be two prices such that 21 < 22. We have that,
dw (1, v)
g (x2, v) -9 (Z), (x2 21) M
Z2 21
Proposition 3 Jnveill an interesting tradeoff faced by DM who prices in a heterogeneous environ- ment. By selecting appropriately the difference between two prices x1 and 22, one can ensure that the gap in revenues for two different distributions can be controlled by the Wasserstein distance.
We next restrict attention to the class of policies which additively deviate from the action selected by SAA and leverage Proposition to define the correct deviation parameter.
Definition 4 (ñ-SAA policies). For any one-dimensional problem we say that a policy is a 6-SAA policy for every empirical distribution js, the policy selects the closest action in X to ORACLE (fi) +6, for some ó E R that could be positive or negative. We denote this policy by TTSAN6).
We note that when 8 = O, we recover the usual SAA policy. Our next result establishes the best possible regret dependence on c and M for the class of pricing problems, using a 6-SAA policy. Theorem 3 (Deviation for Wasserstein pricing). For the data-drived pricing problem in heteroge- environment under the Wasserstein distance, for any c O, let ô -VM c. Then,
VM -
SANd5 inf R. (c) S W. (e) S VM-E.
FEll
Theorem 3 shows that by appropriately deflating the price posted by SAA, one is able to be robust against Wasserstein heterogeneity and achieve worst-case asymptotic regret that vanishes to 0 as the degree of heterogeneity goes to O. This proves that one may operate efficiently for pricing under Wasserstein heterogeneity as goes
Our result establishes that in contrast with Lipschitz problems, it is now impossible to achieve a linear dependence in (since v > e), with the regret growing at rate of Ω2( VM e) under any policy. A small radius e has significantly higher impact in pricing problems than in, e.g., newsvendor problems.
We note that the deflated policy proposed in Theorem 3 improves over SAA when one can make use of the knowledge of c. It is worth noting that SAA does not need such knowledge. Furthermore, one can show that this deflated policy incurs a S (ve) regret for pricing under Kolmogorov distance and thus performs poorly compared to SAA in that setting. A natural question would be to understand the best achievable performance without knowledge of and/or d.
5.2 Ski-rental problem
We now consider the ski-rental problem in which renting skis costs $1 per unit of time while buying them costs Sh up-front, for some real value b. The environment space E represents the set of possible
lengths of the ski trip and decision represents the duration after which skis should be bought (if the ski trip has not ended by that time). We call x the rental duration. Let X' = E = [0. M). where we note that setting measures P is the whole space of probability measures supported on [0, M). For every rental duration X and any trip length E. the cost incurred is
.M indicates that skis should never be bought. The set of probability
g(x.E) = < 1 (5 < x) + (b+x) - 1
x}.
Finally, as the goal is to minimize cost we have that, ORACLE : + arg min & (z)
Wasserstein ski-rental. We proved in Section that SAA performs arbitrarily poorly in pricing under Wasserstein heterogeneity. We now show that SAA falters similarly for the Wasserstein ski-rental problem. Furthermore, we design and analyze a 8-SAA policy which inflates the action selected by SAA (i.e.,& 5 0) and achieves the best rate possible as a function of the heterogeneity radius. Formally, we show the following.

---

Theorem 4. For the data-dri data-driven ski-rental problem in heterogenous environment under the Wasser- stein distance, we have for e >> 0 that,
AW. (c) θ (1)
and
inf Ri o0 (c) = ( (vE).
Theorem 4 formalizes the failure of SAA for ski-rental under Wasserstein distance. A notable fact about the ski-rental problem under Wasserstein heterogeneity is that both the regret of SAA and of the optimal data-driven decision do scale with the size of the support. For pricing, SAA scaled linearly with M and the optimal policy scales v V.. The fact that 2a We = (()) in ski-rental requires a separate non-trivial proof in Theorem
Kolmogorov ski-rental. Under the Kolmogorov distance, had that SAA near-optimal for both the newsvendor and pricing problems. We establish next that the performance of SAA for the ski-rental problem under Kolmogorov distance is, surprisingly, highly suboptimal.
Theorem 5. For the data-driven ski-rental problem in heterogenous environment under the Kol- mogorov distance, we have for e > 0 that,
KK (c) θ (M-c and inf R. (t) O
where è provides rates order up logarithmic factors.
Theorem 5 shows that the asymptotic worst-case regret of SAA scales linearly with the radius of heterogeneity e and with the size of the support M. We also characterize the rate of the optimal asymptotic worst-case regret as function of e. The upper bound on the asymptotic regret is obtained in [9 through a variant of the SAA policy, which caps the maximum number of days to rent. We complement this result by providing matching lower bound. Note that, in contrast to the pricing and newsvendor problems, the scaling of SAA not optimal in M. As the scale of the support grows, the asymptotic worst-case regret of SAA is considerably worse than the optimal achievable rate.
6 Conclusion
All in all, the present results offer a systematic way of understanding and quantifying the implications of operating in heterogeneous environments. Our framework enables develop common language to compare achievable performance across central classes of problems and to unveil novel insights about the performance of central policy, Sample Average Approximation, when slightly deviating from the widely studied i.i.d. regime. In settings where SAA fails, we also design robustification procedures achieving rate-optimal asymptotic guarantees. key takeaway of this analysis across a broad class of problems and for different heterogeneity structures is that it is necessary to understand the structure of the problem we are facing but also the nature of the heterogeneity when designing data-driven policies that are robust to these environments.
To derive our performance guarantees, we established crucial connection between data-driven decision making in heterogeneous environments and distributionally robust optimization. While this work leverages this connection essentially derive bounds on achievable performances, believe that this connection may be of interest to develop new policies from first principles.
This work also opens many additional questions. First, our analysis characterizes the performance in the asymptotic regime where the sample size grows large, and could be complemented by quantifying the performance of policies with finite samples in heterogencous environments. Furthermore, results for Lipschitz problems pin down a key driver of performance, whereas isolating the properties of the policies and the framework elements that drive different levels of achievable performance beyond the Lipschitz case remains open. Another key question would be to understand whether there exists "best of both worlds" policy that does not use the knowledge of the type of heterogeneity and performs well across heterogeneity types (as opposed to the robustified policy designed for pricing and ski-rental). Finally, believe that additional exciting and practical complement to this work include incorporating contexts and deriving statistical tests to characterize the type of heterogeneity along with its radius and provide an empirical validation of the procedures developed here.
The fact that o (c) S M in pricing vacuous.
10

---

References
[1] Allouah, A., Bahamou, A. and Besbes, O. [2022], PPiiiing with samples', Operations Research 70(2), 1088-1104.
[2] Babaioff, M.. Gonezarowski, Y. A., Mansour, Y. and Moran, S. [2018], Are two (samples) really better than one?, in 'Proceedings of the 2018 ACM Conference on Economics and Computation', pp. 175-175.
[3] Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F. and Vaughan, J. W. [2010), 'A theory of learning from different domains', Machhne learning 79(1), 151-175.
[4] Bertsimas, D., Gupta, and Kallus, [2018), 'Robust sample average approximation', Mathematical Programming 171(1), 217-282.
[5] Besbes, O., Gur, Y. and Zeevi, A. [2014], 'Stochastic multi-armme-bandit problem with non- stationary rewards', Advances in neural information processing systems 27.
[6] Besbes, O. and Mouchtaki, O. [2021]. 'How big should your data really be? data-driven newsvendor: learning one sample time', working paper, Columbia University.
[7] Bilodeau, B., Negrea, J. and Roy, D. M. [2020), 'Relaxing the iid assumption: Adaptively minimax optimal regret via root-entropic regularization' arXiv preprint arXiv:2007.06552.
[8] Blanc, G., Lange, J., Malik, A. and Tan, L.-Y. [2021], 'On the power of adaptivity in statistical adversaries', arXiv preprint arXiv:2111.10352
[9] Blanchard, M. [2022], 'Universal online learning: An optimistically universal learning rule', arXiv preprint arXiv:2201.05944
[10] Block, A., Dagan, Y., Golowich, N. and Rakhlin, A. [2022], 'Smoothed online learning is as easy as statistical learning'. arXiv preprint arXiv:2202.04690.
[11] Borodin, A. and EI- Yaniv, R. [2005], Online computation and competitive analysis, cambridge university press.
[12] Brustle, J., Cai, Y. and Daskalakis, C. [2020], Multi-item mechanisms without item- independence: Learnability via robustness, in 'Proceedings of the 21st ACM Conference on Economics and Computation', pp. 715-761.
[13] Cai, Y. and Daskalakis, C. [2017], Learning multi-item auctions with (or without) samples, in '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', IEEE, pp. 516-527.
[14] Chen, X. and Wang, Y. [2020], 'Dynamic pricing with demand learning in the presence of outlier customers',
[15] Cheung, W. C. and Simchi-Levi, D. [2019], 'Sampling- based approximation schemes for capaci- tated stochastic inventory control models', Mathematics of Operations Research 44(2), 668 0622.
[16] Cheung, W. C., Simchi-Levi, D. and Zhu, R. [2022], 'Hedging the drift: Learning to optimize under nonstationarity'. Management Science 68(3), 1696-1713.
[17] Daskalakis, C. and Zampetakis, M. [2020], More revenue from two samples via factor revealing sdps, in 'Proceedings of the 21st ACM Conference on Economics and Computation', pp. 257- 272.
[18) Diakonikolas, I., Kamath, G., Kane, D., Li, J., Moitra, A. and Stewart, A. [2019], 'Robust estimators in high-dimensions without the computational intractability'. SIAM Journal Computing 48(2), 742-864.
[19] Diakonikolas, I., Kontonis, V., Tzamos, C., Vakilian, A. and Zarifis, N. [2021], Learning online algorithms with distributional advice, in 'International Conference on Machine Learning'. PMLR, pp. 2687-2696.

---

[20] Duchi. J. C. and Namkoong, H. [2021], 'Learning models with uniform performance via distributionally robust optimization', The Annals of Statisties 49(3), 1378 1406.
[21] Fu, H., Immorlica, N., Lucier, B. and Strack, [2015]. Randomization beats second price as prior-independent auction, in PProceedings of the Sixteenth ACM Conference on Economics and Computation pp. 323-323.
[22] Gallego, G. and Moon, [1993], 'The distribution free newsboy problem: review and exten- sions', Journal of the Operational Research Society 44(8), 825 8344.
"attiinns,Avanees Advances [23] Guo, W., Jordan, M. and Zampetakis, E. [2021], 'Robust learning of optimal auctions', in Neural Information Processing Systems 34.
[24] Haghtalab, N., Han, Y., Shetty, and Yang, [2022], 'Oracle-efficient online learning for beyond worst-case adversaries', arXiv preprint arXiv:220..0849.
[25] Haghtalab, N., Roughgarden, T. and Shetty, A. [2022], Smoothed analysis with adaptive adversaries, in '2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)', IEEE, pp. 942-953..
[26] Hampel, F. R. [1971], 'A general qualitative definition of robustness', The annals of mathemati- cal statistics 42(6), 1887-1896.
[27] Hanneke, [2021], 'Learning whenever learning possible: Universal learning under general stochastic processes.' J. Mach. Learn. Res. 22, 130-1.
[28] Haussler, D. [1992], 'Decision theoretic generalizations of the pac model for neural net and other learning applications', Information and computation 100(1), 78-150.
[29] Huang, 7.,, Mansour, Y. and Roughgarden, T. [2018), 'Making the most of your samples', SIAM Journal on Computing 47(3), 651-674.
[30] Huber, P. J. [1992], Robust estimation of a location parameter, in 'Breakthroughs in statistics", Springer, pp. 492-518.
[31] Kantorovich, L. V. and Akilov, G. P. [2016], Functional analysis, Elsevier.
[32] Kantorovich, L. V. and Rubinshtein, S. [1958), 'On space of totally additive functions', Vestnik of the St. Petersburg University: Mathematics 13(7), 52-59.
[33] Karnin, Z. S. and Anava, O. [2016), 'Multi-armed bandits: Competing with optimal sequences', Advances in Neural Information Processing Systems 29.
[34] Kearns, M. J., Schapire, R. E. and Sellie, L. M. [1994], "Toward efficient agnostic learning', Machine Learning 17(2), 115-141.
[35] Kearns, M. and Li, M. [1993], 'Learning in the presence of malicious errors', SIAM Journal on Computing 22(4), 807-837.
[36] Kim, S., Pasupathy, R. and Henderson, S. G. [2015], 'A guide sample average approximation', Handbook of simulation optimization pp. 207-243.
[37] Kleywegt, A. J., Shapiro, A. and Homem-de Mello, T. [2002], 'The sample average approxima- tion method for stochastic discrete optimization', SIAM Journal Optimization 12(2), 479-502.
[38] Klivans, A. R., Long, P. M. and Servedio, R. A. [2009], 'Learning halfspaces with malicious noise.", Journal of Machine Learning Research 10(12).
[39] Lam, H. [2021], 'On the impossibility of statistically improving empirical optimization: A second-order stochastic dominance perspective', arXiv preprint arXiv:2105.1341
[40] Levi, R., Perakis, G. and Uichanco, J. [2015], 'The data-driven newsvendor problem: new bounds and insights', Operations Research 63(6), 1294-1306.
[41] Luo, H., Wei, C.-Y., Agarwal, A. and Langford, J. [2018], Efficient contextual bandits in non-stationary worlds, in "Conference On Learning Theory', PMLR, pp. 1739-1776.
12

---

[42] Lykouris, T., Mirrokni, V. and Paes Leme, R. [2018], Stochastic bandits robust to adversarial corruptions, 'Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing', pp. 114-122.
[43] Lykouris, T., Simchowitz, M., Slivkins, A. and Sun, W. [2021]. Cormuption-robust exploration in episodic reinforcement learning, in "Conference on Learning Theory'. PMLR, pp. 9242-3245.
[44] Mansour, Y., Mohri, M. and Rostamizadeh, A. [2009), 'Domain adaptation: Learning bounds and algorithms', arXiv preprint arXiv:0902.3430.
[45] Mohajerin Esfahani, and Kuhn, D. [2018]. 'Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations! Mathemati- cal Programming 171(1), 115-166.
[46] Mohri, M. and Muñoz Medina, A. [2012], New analysis and algorithm for learning with drifting distributions, in 'International Conference on Algorithmic Learning Theory', Springer, pp. 124-138.
[47] Morse, P. M. and Kimball, G. E. [1946], Methods of operations research, Technical report, Center for Naval Analyses, Alexandria VA, Operations Evaluation Group.
[48] Myerson, R. B. [1981]. 'Optimal auction design', Mathematics of operations research 6(1), 58-
73.
[49] Perakis, G. and Roels, G. [2008], 'Regret in the newsvendor model with partial information', Operations Research 56(1), 188-203.
[50] Purohit, M., Svitkina, Z., and Kumar, R. [2018), 'Improving online algorithms via ml predic- tions', Advances in Neural Information Processing Systems 31.
[51] Rakhlin, A., Sridharan, K. and Tewari, A. [2011], 'Online learning: Stochastic and constrained adversaries', arXiv preprint arXiv:1104.500
[52] Riley, J. and Zeckhauser, R. [1983], 'Optimal selling strategies: When to haggle, when to hold firm', The Quarterly Journal of Economics 98(2), 267-289.
[53] Roughgarden, [2021], Beyond the worst-case analysis of algorithums, Cambridge University Press.
[54] Scarf, H. [1958], 'A min-max solution of an inventory problem', Studies in the mathematical theory of inventory and production.
[55] Servedio. R. A. [2003], 'Smooth boosting and learning with malicious noise', The Journal of Machine Learning Research 4, 633-648.
[56] Shorack, G. R. [1979], "The weighted empirical process of row independent random variables with arbitrary distribution functions', Statistica Neerlandica 33(4), 169-189.
[57] Williams, D. [1991], Probability with martingales, Cambridge university press.
13


Reviews:
[{"review_id": "zzkE_7aAfyJ", "reviewer": "Reviewer_xMuo", "summary": "The paper studies data-driven decision-making in heterogeneous environments; in particular, the goal is to solve a stochastic optimization problem based on previous observations that were sampled from a Wasserstein/Kolmogorov ball around the target distribution. Main results analyze the regret of sample average approximation policies. The regret rates vary significantly depending on the notion of heterogeneity and problem class.", "questions": "A natural question that arises is whether it is possible to somehow fix SAA to get the optimal rates for the ski-rental problem. I don't think this is necessary though.", "limitations": "The authors do not discuss limitations and potential negative societal impact explicitly. I don't see what they could say about negative societal impact, but perhaps they could add some discussion about limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is exceptionally clearly written, well-motivated, and (to my admittedly limited knowledge of this area) novel. The key technical result is Theorem 1, which establishes a reduction in which one only needs to consider one fixed data distribution as an input into the policy, as opposed to stochastic observations generated from different distributions over time. This is perhaps not too surprising, but is non-trivial nonetheless. From here it's not that hard to get Theorem 2 using standard properties of Wasserstein/Kolmogorov distances. The paper then shows that for the newsvendor problem the rate obtained in Theorem 2 is tight, which is nice. The non-Lipschitz problem section is more interesting and surprising: under Kolmogorov uncertainty, SAA is still near-optimal for the pricing problem, however under Wasserstein uncertainty, SAA fails. Interesting, SAA can still be robustified to work under Wasserstein uncertainty. For the ski-rental problem, for both kinds of uncertainty balls SAA is highly suboptimal. Overall this is a fairly well-rounded analysis of the three motivating problems, which some general results (Thm 1/2) which are not too surprising but valuable nevertheless.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ghfPrnaC7wM", "reviewer": "Reviewer_4sFh", "summary": "This paper presents a framework for analyzing data-driven decision-making across heterogeneous environments. The decision-making problems of interest include the newsvendor problem, the single-item pricing problem and the ski-rental problem. \n\nSpecifically, when future data distribution and past distributions are nearby in Kolmogorov or Wasserstein distances, the paper derives regret bounds where regret is against optimal policies that have knowledge of the future distribution. To facilitate the analysis, the paper considers an asymptotic regime in which a sequence of past distributions converges to one distribution which is assumed to be known. The paper provides bounds for both general Lipschitz-continuous problems and specific decision-making problems mentioned above.", "questions": "Does the robustified SAA policy also work for Kolmogorov pricing?", "limitations": "Open questions are addressed as limitations in Section 6. Potential societal impact is not discussed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The paper discusses related works on data corruptions and robustness. I am not familiar with the literature on learning across heterogeneous environments or out-of-sample generalization for the specific data-driven decision problems considered in this paper. However, for supervised learning, there appears to be a rich literature on domain adaptation and transfer learning, which seems related to this paper. For example, Mohri and Medina (2012) provide learning bounds in drifting environments; Ben-David, et al. (2010) characterizes transfer learning across different domains. The framework proposed in this paper seems novel.\n\nQuality: The results seem correct to me though I did not check the proofs in the appendix.\n\nClarity: The paper is well-written and easy to follow. I have some minor comments:\n\n(1) The three contributions in Section 3 are scattered in different subsections. It is a bit confusing when \"our third contribution\" appears near the top of Section 1.2 (line 70).\n\n(2) The acronym \"DM\" has not been introduced yet in line 59.\n\n(3) In line 111, at this point it is unclear what the support of the unknown environment and $M$ mean for the specific DM problems.\n\nSignificance: This paper provides a framework that unifies a collection of results for out-of-sample learning in different decision-making problems. Again, I am not very familiar with the literature for the decision-making problems of interest, but the results seem interesting and thorough and the paper could be of interest for people studying data-driven decision-making, transfer learning or learning theory. One limitation is that the analysis is done in the simplified asymptotic regime; it would be interesting to see results for a sequence of past distributions, similar to Theorem 1 of (Mohri and Medina, 2012).\n\n- Mohri, Mehryar, and Andres Muñoz Medina. \"New analysis and algorithm for learning with drifting distributions.\" International Conference on Algorithmic Learning Theory. Springer, Berlin, Heidelberg, 2012.\n- Ben-David, Shai, et al. \"A theory of learning from different domains.\" Machine learning 79.1 (2010): 151-175.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RHaR67g99WF", "reviewer": "Reviewer_kSQ2", "summary": "The paper proposes a new framework to quantify the deviation from historical (training) samples to future (test) samples. It considers three problems as special cases of the framework: newsvendor, pricing, and ski-rental. It examines sample-average-approximation (SAA) policy and derives upper and lower regret bounds. It also studies an inflation policy for the pricing problem where the SAA policy is suboptimal. The discussions are separated into two cases based on whether the underlying cost function is Lipschitz or not. ", "questions": "See above.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, and it proposes a new formulation for measuring the difference between historical and future samples. \n\nMy main concern is the technical contribution of the work, specifically, in the following aspects:\n-  New policies: the new measure doesn't seem to elicit new/insightful policies other than SAA. The paper looks more like an analysis of SAA under a heterogenous environment where the test data differs from the training data. For the pricing problem, it proposes a $\\delta$-SAA policy but other than that, all the upper bound analyses in this paper are based on the SAA policy. For the ski-rental problem, it mentioned: \"... we derive a deviation policy which inflates the SAA action ...\", but I didn't see the discussion of this inflated SAA policy (correct me if I missed anything here).\n- Generalization to sequential or multi-variate settings: All three examples in the paper focus on a static setting with a single-dimensional random variable. Thus the technical results look straightforward to me. I wonder whether the results can be generalized to a sequential setting, or a setting with features/covariates. \n- Robust optimization: In Theorem 1, the paper establishes distributionally robust optimization (DRO) as an asymptotic upper bound of the regret in this paper. For the finite-sample analysis, what if one adopts the DRO policy? Will that be sub-optimal or computationally intractable?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "HdxCArb7c1", "reviewer": "Reviewer_Jymp", "summary": "The authors study decision-making where the training data may each have been generated from a different distribution, provided all samples are still independent and the distributions are all close in some metric. For certain convex metrics, they upper bound asymptotic regret by a worst-case, data-independent notion. For Kolmogorov and Wasserstein distances, they apply this to 3 optimization problems and provide matching lower bounds. They also show that empirical risk minimization is suboptimal, and show that an algorithm with oracle knowledge of the constraint on training data can be optimal. ", "questions": "I have no questions beyond the limitations I raised above.", "limitations": "I see no negative societal impacts of this theoretical work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Summary of Review\n\nThe paper is clearly written and provides compelling results with matching upper and lower bounds for well-studied problems. The framing of the related literature and novelty of the data-generating process is lacking and requires improvements, and I believe the interpretation of the results (and their limitations) could be made more clear. All of my proposed changes are non-technical, and so I believe the authors can successfully make them in the revision period.\n\n## Soundness\n\nIn equation 9, triangle inequality (first line) and convexity (third line) are used for the metric $d$, and hence all mentions of the metric through the paper need to be appropriately qualified with these properties; this includes the statement of Theorem 1.\n\nLines 670--671, I don't think the argument is quite rigorous (the argument for equality (c) is intuitive but not clear that it's precise). Fortunately, it follows from first principles.\\\nSince the objective is linear in $\\beta$:\n$$\n   \\inf_{\\pi\\in\\Pi} \\sup_{\\mu\\in \\{\\mu_-, \\mu_+\\}} E_{\\mathbf{\\zeta} \\sim \\bar\\nu} \\mathcal{G}(\\pi(n, \\hat \\mu_{\\mathbf{\\zeta}}), \\mu) - \\mathrm{Opt}(\\mu) = \\inf_{\\pi\\in\\Pi} \\sup_{\\beta\\in \\Delta(\\mu_-, \\mu_+)} E_{\\mu\\sim\\beta} E_{\\mathbf{\\zeta} \\sim \\bar\\nu} \\mathcal{G}(\\pi(n, \\hat \\mu_{\\mathbf{\\zeta}}), \\mu) - \\mathrm{Opt}(\\mu)\n$$\nBy Fubini (everything is bounded):\n$$\n  =  \\inf_{\\pi\\in\\Pi} \\sup_{\\beta\\in \\Delta(\\mu_-, \\mu_+)} E_{\\mathbf{\\zeta} \\sim \\bar\\nu} E_{\\mu\\sim\\beta} \\mathcal{G}(\\pi(n, \\hat \\mu_{\\mathbf{\\zeta}}), \\mu) - \\mathrm{Opt}(\\mu)\n$$\nBy Jensen's:\n$$\n  \\geq  \\sup_{\\beta\\in \\Delta(\\mu_-, \\mu_+)} E_{\\mathbf{\\zeta} \\sim \\bar\\nu} \\inf_{\\pi\\in\\Pi} E_{\\mu\\sim\\beta} \\mathcal{G}(\\pi(n, \\hat \\mu_{\\mathbf{\\zeta}}), \\mu) - \\mathrm{Opt}(\\mu).\n$$\nAt this point it is precise to argue that this $\\inf_{\\pi\\in\\Pi}$ is achieved at a pointmass for the best $x\\in\\mathcal{X}$ with respect to $\\beta$, since there are no restrictions whatsoever on $\\Pi$.\n\nBeyond this, I checked Appendices A-C carefully, and Appendix D at a high level; I found no issues with correctness.\n\n## Novelty\n\nI believe that the authors overstate the novelty of their framework, claiming “Our first contribution lies in introducing a framework which models the future outcome as being drawn from an unknown distribution, and past data as being drawn independently from (also unknown) \"nearby\" distributions.” At a high level, nearly all of classical statistical robustness is focused on performance within a ball under some metric on probability distributions. Much more specifically, the data-generating process they introduce is not novel. https://arxiv.org/abs/1104.5070 introduce the setting where an adversary gets to select a different data-generating distribution on each round from within a (potentially changing over time) set of allowed distributions. One such choice for this set is obviously the balls considered in the present paper. https://arxiv.org/abs/2007.06552 also study this setting, providing an optimal algorithm with optimal dependence on the time horizon; their Example 5 exactly contains the setting of this work (for any distance on distributions). https://arxiv.org/abs/2102.08446, https://arxiv.org/abs/2202.08549, and https://arxiv.org/abs/2202.04690 also consider this setting for the ball defined by a specific measure of distance based on density ratios, providing optimal algorithms and characterizing optimal performance. Finally, the authors discuss offline corruption but neglect the significant literature on online corrupted data; this connection is less relevant, however, since these results often focus on the data being corrupted rather than the distribution being corrupted.\n\nIt is worth noting that the authors motivate their move to the asymptotic regime by saying it is “a significant challenge” to study the minimax game for finite time horizon, yet this is exactly what all of the above work does. The above works also allow for an adaptive adversary, that can select the distribution on each training data point by reacting to the player and the random realizations of data; of course their upper bounds would also apply to an oblivious (and independent) adversary like the one studied in this work. The present work considers a single decision, rather than a sequence of decisions, and so not all results are directly comparable; however, the significant study of “near IID” in the online learning literature warrants comparison from the authors.\n\n## Interpretation of results\n\nThe definition of SAA is precisely Oracle($\\hat\\mu$). Throughout the proofs, however, it is used on arbitrary distributions (of course, an arbitrary distribution could be concentrated on n points and be a sample average). This leads to statements like $\\pi^{\\mathrm{SAA}}(\\nu)$, which is then used as Oracle($\\nu$). Clearly, however, this policy is not data-dependent -- it acted on a distribution. This is not an issue with the results (they really do bound SAA acting on $\\hat\\mu$, asymptotically) or the proofs (everything goes through with a relabelling to Oracle($\\nu$)). It is purely an issue with interpretation and understanding of what's going on \"under the hood\". It seems this is all a consequence of the (unproven, but intuitive) claim that for independent data any optimal algorithm need only see $\\hat\\mu$ and that for the notion of performance, all that matters is the average asymptotically (this part is proven). However, the closeness of the empirical oracle asymptotically and the asymptotic oracle is less surprising when one writes them down this way. In summary, my suggestion is just be clear everywhere that the algorithm considered is Oracle($\\hat\\nu$), rather than calling it SAA.\n\nTheorem 3 is stated as though this is a strict improvement over SAA, however it requires advance knowledge of $\\epsilon$ (which is not true for SAA). Obviously, for robustness we do not expect to know $\\epsilon$, and I think this adaptivity should be discussed (leaving it as an open problem). It's worth noting that much of the earlier literature I mentioned above (missing from this paper) focuses on adapting to $\\epsilon$ for other problems.\n\n## Minor comments\n\n- Lemma 3 is so standard it's on Wikipedia, no need to reprove.\n- The proof of Prop 7 is very similar to that of Prop 1, with actual word-for-word repetition. Making these both follow from some more general lemma or intermediate result would be preferable.\n\n## Typos / Notation\n\n- I see no reason to let the optimization of g be “arbitrary”; pick max or min as a convention, the other case trivially will also hold by swapping the sign.\n- Expectations of the form $\\mathbb{E}_{\\zeta_i \\sim \\nu_i}$ (such as right after line 204) are somewhat sloppy notation. More preferable is to define some notation using $\\mathbf{\\zeta^n}$ and $\\mathbf{\\nu^n}$ (appropriately defined).\n- Line 610, should be $\\nu_{i,n} \\in \\mathcal{U}_{\\epsilon}(u_n)$.\n- Line 614, should just be $\\bar\\nu_n = (1/n)\\sum_{i=1}^n \\nu_{i,n}$.\n- Line 652, should quantify over $\\epsilon$ before doing algebra.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3IXjtzC3rcz", "reviewer": "Reviewer_mWJA", "summary": "In this work, the authors proposed a framework to model learning problems with  heterogeneous environments. The worst-case regret is analyzed in the asymptotic case. Specifically, an upper bound is derived via considering a simpler problem, and several lower bounds are derived for three specific problems.", "questions": "(1) Ln.59: \"DM\" is used before its definition.\n\n(2) Ln.133: \"demonstrates\" -> \"demonstrate\".\n\n(3) Ln.205-209: In the definition of the absolute regret, the authors mentioned that the absolute value is used to combine both the maximization/minimization cases. Does this hint that the expected objective value of a policy is always smaller/larger than opt(mu) when we consider the maximization/minimization problem? I wonder if it is possible that v_i are \"very good\" such that the expected objective value of pi is better than opt(mu)? I understand that this does not affect the worst-case regret in Eq.(3).\n\n(4) In Eq.(6), does the reverse inequality hold if we set eta = epsilon? Also, I am a little confused on the necessity of the limit. I think the right-hand side is decreasing in eta?", "limitations": "See my comments in the \"questions\" section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The framework in this work is interesting and important in many areas (operations research, economics and management science). I think this work is interesting to audiences in robust optimization, machine learning and operations research fields. The presentation of results is very clear and it is easy to follow. I have not read the appendix due to the time limit, but it seems to me that the theoretical results in this work are correct and sound. The only (minor) weakness may be the lack of non-asymptotic results. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept