Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: The paper is well-written, and it proposes a new formulation for measuring the difference between historical and future samples. 

My main concern is the technical contribution of the work, specifically, in the following aspects:
-  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).
- 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. 
- 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?
questions: See above.
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

Specifically, 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.
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.

Quality: The results seem correct to me though I did not check the proofs in the appendix.

Clarity: The paper is well-written and easy to follow. I have some minor comments:

(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).

(2) The acronym "DM" has not been introduced yet in line 59.

(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.

Significance: 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).

- 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.
- Ben-David, Shai, et al. "A theory of learning from different domains." Machine learning 79.1 (2010): 151-175.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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. 
questions: (1) Ln.59: "DM" is used before its definition.

(2) Ln.133: "demonstrates" -> "demonstrate".

(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).

(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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: ## Summary of Review

The 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.

## Soundness

In 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.

Lines 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.\
Since the objective is linear in $\beta$:
$$
   \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)
$$
By Fubini (everything is bounded):
$$
  =  \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)
$$
By Jensen's:
$$
  \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).
$$
At 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$.

Beyond this, I checked Appendices A-C carefully, and Appendix D at a high level; I found no issues with correctness.

## Novelty

I 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.

It 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.

## Interpretation of results

The 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.

Theorem 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.

## Minor comments

- Lemma 3 is so standard it's on Wikipedia, no need to reprove.
- 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.

## Typos / Notation

- 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.
- 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).
- Line 610, should be $\nu_{i,n} \in \mathcal{U}_{\epsilon}(u_n)$.
- Line 614, should just be $\bar\nu_n = (1/n)\sum_{i=1}^n \nu_{i,n}$.
- Line 652, should quantify over $\epsilon$ before doing algebra.



questions: I have no questions beyond the limitations I raised above.
limitations: I see no negative societal impacts of this theoretical work.
review_title: null

Meta-review: metareview: This paper studies an interesting setting in which the future training data and the past data are generated from different distributions, but the two distributions are close in terms of Kolmogorov or Wasserstein distances.  The paper gives a nice set of algorithmic and impossibility results.  Initially, some reviewers had questions about the novelty of the framework and technical approaches; the authors have addressed most of these questions properly. 
confidence: Certain
Decision: Accept