发表在 Management Science, 2023. DOI: https://doi.org/10.1287/mnsc.2023.4725
Keywords: limited data; data-driven decisions; minimax regret; sample average approximation; empirical optimization; finite samples; distributionally robust optimization
文章旨在研究给定数据量（data size）时的最优策略（optimal policy），以及研究这种策略的效果到底有多好（遗憾界）。
对于一个经典的 newsvendor 损失函数 $$ c(x, D):=b(D-x)^{+}+h(x-D)^{+} $$ 需求分布 $D$ 是未知的。记 $q=b/(h+b)$ .
我们假定 $D \in \mathcal{F}=\left\{F \in \mathcal{G}: \mathbb{E}_F[D]<\infty\right\}$，记 $\text{OPT}(F):=c_F(x_F^\ast)$ 是某个分布 $F$ 下最优的 cost。
我们不知道真实的分布 $F$，只有 $n$ 个 sample $\textbf{D}_1^n = (D_1, D_2, \dots, D_n)$，一个策略（policy）将 sample 映射为概率分布
$$ \pi: \mathbf{D}_1^n \longmapsto G_{\mathbf{D}_1^n} \in \mathcal{F} $$ 定义一个策略，在给定分布函数 $F$ 和样本数量 $n$ 时的 out-of-sample 平均 cost 为 $$ \mathcal{C}(\pi, F, n):=\mathbb{E}_{\mathbf{D}_1^n \sim F}\left[\mathbb{E}_{x \sim \pi\left(\mathbf{D}_1^n\right)}\left[c_F(x)\right]\right] $$ 用相对遗憾（relative regret）来评估一个策略的效果 $$ \mathcal{R}_n(\pi, F):=\frac{\mathcal{C}(\pi, F, n)-\operatorname{opt}(F)}{\operatorname{opt}(F)} $$ 因为我们不知道 $F$ 是什么，所以选取在所有可能的分布上的最差表现作为优化的目标 $$ \sup _{F \in \mathcal{F}} \mathcal{R}_n(\pi, F) $$ 在这种目标下，我们自然会想知道，最好的策略会达到什么样的相对遗憾呢 $$ \mathcal{R}_n^\ast:=\inf _{\pi \in \Pi_n} \sup _{F \in \mathcal{F}} \mathcal{R}_n(\pi, F) . $$
分析这个问题有两大困难，一是评价是建立在任意的概率分布上的，二是我们要从所有可行的策略中找到最优的。“任意的概率分布”、“所有可行的策略”，这都是很抽象的东西。文章的精彩之处是将这两个抽象的东西具化为一个有限维的情况。
Performance Analysis of SAA
提起数据驱动的优化，第一个想起的莫过是 SAA 方法，于是文章首先讨论了 SAA 在上述理论框架下的表现。
本质上，SAA 就是拿经验分布作为真实分布，因为 newsvendor 的解是一个分位数，所以 SAA 策略本质上也就是选取经验分布的一个分位点。 $$ D_{1: n} \leq \ldots \leq D_{n: n}, \qquad \pi^{\mathrm{SAA}}\left(\mathbf{D}_1^n\right)=D_{\lceil q n\rceil: n} $$
Order Statistic Policies
注意到 SAA 策略本质上是选择一个 $\lceil qn\rceil$ 的分位点，我们可以将这种思想推广到分为点的概率分布上。在给出 SAA 的性质之前，文章先分析了这类一般情况。 $$ \pi^{\boldsymbol{\lambda}}: \mathbf{D}_1^n \longmapsto \sum_{i=1}^n \lambda_i \mathbb{1}\left\{x \geq D_{i: n}\right\} $$ 这里策略 $\pi^\boldsymbol{\lambda}$ 以概率 $\lambda_i$ 选择 $D_{i:n}$ .
对于 $\pi^{\boldsymbol{\lambda}}$，文章给出了其 cost (Proposition 1)；在 $\eqref{Theorem-1}$ 中，文章给出了关于概率分布的 reduction。
$$ \sup _{F \in \mathcal{F}} \mathcal{R}_n\left(\pi^{\boldsymbol{\lambda}}, F\right)=\sup _{\mu \in[0,1]} \mathcal{R}_n\left(\pi^{\boldsymbol{\lambda}}, \mathcal{B}(\mu)\right) \tag{Theorem 1.} \label{Theorem-1} $$
这里 $\mathcal{B}(\mu)$ 表示均值为 $\mu$ 的伯努利概率分布。这个定理说明了，我们评价一个策略，只需要在所有伯努利分布上计算遗憾值即可。
Performance Analysis of SAA
文章在 Theorem 2 中给出了 SAA 的 finite sample performance。相比之前的文章使用 concentration inequality 来推导，这篇文章使用全新的方法证到了更紧的 bound。
如上表（文章的 Table 2.）所示，当 critical quantile $q=0.7$ 的时候，根据文章给出的界，要想把 relative regret 控制在 5% 内，只需要 84 个 sample，远远少于 Levi et al. (2015) 文章中给出的值。
接着文章话锋一转，使用数值实验来说明了 SAA 一个巨大的缺点：其 relative regret 随样本数量的增加不是单调下降的。这意味着，单纯使用 SAA 方法，数据越多，效果不一定约好；这是很令人惊讶的结果。
Optimal Data-Driven Policy
尽管 SAA 是一个看起来好的方法，但它不是最优的。
文章接着证明了，实际上我们不需要去考虑所有的策略，只需要去考虑所有的 Order Statistic Policy 就可以了，最优的 Order Statistic Policy 也是最优的策略。
$$ \inf _{\pi \in \Pi_n} \sup _{F \in \mathcal{F}} \mathcal{R}_n(\pi, F)=\inf _{\pi^\lambda \in \Pi_n^{O S}} \sup _{F \in \mathcal{F}} \mathcal{R}_n\left(\pi^\lambda, F\right) \tag{Theorem 3.} $$
至此，我们寻找最优策略，只需要在 Order Statistic Policy 这类策略里面寻找即可。
也就是说，我们只需要关心下面的值： $$ \inf _{\pi^\lambda \in \Pi_n^{O S}} \sup _{p \in \Delta([0,1])} \mathbb{E}_{\mu \sim p}\left[\mathcal{R}_n\left(\pi^\lambda, \mathcal{B}(\mu)\right)\right] $$ 文章在 Theorem 4 中给出了 optimal policy 的结构：
对任意的样本数量 $n$，存在 $k\in \{2, \dots, n\}$ 和 $\gamma\in [0, 1]$ 使得 $$ \pi^{k, \gamma} :\to \begin{cases} D_{k:n}, & \text{prob}=\gamma\\ D_{k-1:n}, & \text{prob}=1-\gamma \end{cases} $$ 是最优的。文章指出，数值实验上 $k$ 一般等于 $\lceil qn \rceil$ 或者 $\lceil qn\rceil + 1$ .
最优策略并不是一个单纯的分位点策略，而是一个在最优分位点附近的随机策略。
文章给出的计算最优策略的算法：
