证明中提出的具体决策程序是在每个样本ψ的样本模拟下包络函数最大值ε范围内获得的任何程序∈ ψn，对于某些ε>0的情况。我们称之为ε-maximin经验法则，我们将在下一小节重新讨论它的性质。在这里，我们还最终看到了MPAC可学习性和上一节定理3.1中的下包络函数之间的密切联系，这一点在整篇文章中都有所提及。定理3中下包络函数的特殊形式。1使其易于使用经验过程理论中的方法进行分析，这些方法用于定理4.1的证明。还请注意假设3.1，这是获得惩罚的界限所必需的*在OREM 3.1中，这个结果也需要。如果没有这个惩罚的约束，定理4.1通常是不成立的。定理4.1第（ii）部分的证明表明，如果policytransform下包络的每个“分量”，即矩函数和函数φ-满足熵增长条件，则类H`bc的度量熵也可以控制。结合命题4.1的结果，定理4.1第（ii）部分的结果表明，我们提出的ε-maximin决策规则可以获得接近最大值（超过γ）的结果∈ Γ）以高概率转换策略的下包络。我们的可学习性结果适用于任何政策空间，这似乎令人惊讶。然而，这是由于（4.7）中的函数类Φ缓和了政策空间的复杂性，因为只有通过此类函数，政策才能影响政策转换。通过使类Φ满足熵增长条件，我们隐含地限制了策略空间的复杂性。

请注意，该定理仅提供了PAMPAC可学习性的充分条件，并且可能会有其他结果直接对策略空间Γ施加复杂性约束，而不是对Φ施加复杂性约束。现在，我们将使用激励性示例来验证相关政策空间的可学习性。例1（同时离散选择（续））。再次考虑关于同步离散的示例1。在这种情况下，我们有：Φ：={{πk（γ（·）；θ）≥ u} ：（u，θ）∈ U×Θ}，（4.11）在力矩条件下：E{英国≤ πk（z，y）-Kθ)}-max{Lπk（z，y）-Kθ), 0} -0.5{Zk=z，Y-k=y-k}≤ 0，（4.12）E0.5-{英国≤ πk（z，y）-Kθ)}-麦克斯{-Lπk（z，y）-Kθ), 0}{Zk=z，Y-k=y-k}≤ 0，（4.13）对于k=1，K、 尽管如此∈ Z和所有y-k、 y-K∈ YK-1.附录C.1.3中给出了Φ和与上述力矩条件相关的力矩函数类的熵增长条件验证的详细信息。此外，在我们对这个例子的假设下，从定理4.1导出的收敛速度为O（n）-1/2).例2（项目评估（续））。再次考虑关于项目评估的示例2。在这种情况下，我们有：Φ：={{g（γ（z））≥ u} （u）- u） +u:（u，u，u，g）∈ U×G}，（4.14）在力矩条件下：E[（D- g（Z，X））{Z=Z，X=X}]≤ 0, Z∈ Z、 x∈ 十、 （4.15）E[（g（Z，X）- D） {Z=Z，X=X}]≤ 0, Z∈ Z、 x∈ 十、 （4.16）E[（{U≤ g（z，x）}- g（z，x））{x=x}]≤ 0, Z∈ Z、 x∈ 十、 （4.17）E[（g（z，X）-{U≤ g（z，x）}{x=x}]≤ 0, Z∈ Z、 x∈ 十、 （4.18）E[t（z，X）-{Z=Z，X=X}]≤ 0, Z∈ Z十、∈ 十、 （4.19）E[{Z=Z，X=X}-t（z，x）]≤ 0, Z∈ Z十、∈ 十、 （4.20）和：E“Ud{Z=Z，X=X}Xz∈Zt（z，x）-{X=X}t（z，X）#≤ 0, Z∈ Z、 x∈ 十、 d∈ {0,1}，（4.21）E“Ud{X=X}t（z，X）-{Z=Z，X=X}Xz∈Zt（z，x）#≤ 0, Z∈ Z、 x∈ 十、 d∈ {0, 1}.

（4.22）关于Φ和与上述矩函数相关的函数类的熵增长条件验证的详细信息，见附录C.2.3。此外，在我们对这个例子的假设下，从定理4.1导出的收敛速度为O（n）-1/2）.5事后理论结果定理4.1给出了在给定环境下PAMPAC可学习性的充分条件。然而，虽然结果表明，可能在事前（即观察特定样本之前）就可以了解给定的政策空间，但它并没有为我们提供任何有用的事后（即观察样本之后）决策规则执行情况的信息。这反映了一个关于PAC可学习性的众所周知的投诉，并为统计学习文献中关于数据依赖的过度风险界限的文献提供了依据；参见Bartlettet等人（2002年）、Koltchinskii（2001年）和Koltchinskii（2006年）的例子，以及Boucheron等人（2005年）或orKoltchinskii（2011年）的综述。因此，在确定一类特定政策的可学习性后，评估给定决策规则在给定样本中的有限样本性能可能会引起不同的兴趣。这将在接下来的小节中完成。我们将把注意力集中在定理4.1证明中使用的特定决策规则上，该规则在定理的假设下被证明满足PAMPAC可学习性的要求。使用的决策规则可以是任意ε-下包络函数I`b[~n]（γ）的经验公式的最大化子，这就是为什么我们将其称为ε-马克西敏经验法则。定义5.1（ε-最大化经验福利）。修正任何ε≥ 0和letbI`b[~n]（γ）表示定理3.1在（Y，Z）的经验测度下的下包络。那么d:ψn→ Γ是ε-极大极小经验（eME）规则如果：bI`b[~n]（d（ψ））+ε≥ supγ∈ΓbI`b[Γ]（γ）。（5.1）备注5.1。

请注意，通常情况下，“ε”是必要的（尽管它可以任意变小），因为可能无法获得Bi`b[~n]（·）的上确界。此外，与我们关于PAMPAC可学习性的结果不同，下一小节中的所有结果都与数据相关，并且不依赖于策略决策问题中涉及的任何函数类的任何特定属性（超出可测量性）。因此，无需验证熵增长条件，或任何其他有助于学习能力的条件，以使用前面的结果。在实践中，我们仍然建议在使用结果之前验证政策空间可学习性的充分条件。5.1 Maximin经验规则的理论结果在本节中，我们获得了任意固定κ的cn（d，κ）值的界，其中d为eME规则。为了描述我们的程序，我们将首先为H`b类引入一个依赖于数据的复杂性度量。我们使用的复杂性度量基于经验的Rademacher复杂性，这是Bartlettet al.（2002）、Koltchinskii（2001）和Koltchinskii（2006）（以及其他人）在经验风险最小化的背景下提出的。定义5.2（经验Rademacher复杂性）。设F是一类可测函数F:Y×Z→R.F的经验Rademacher复杂度为：|Rn | |（F）：=supf∈FnnXi=1ξi·f（yi，zi）, （5.2）式中ξ是Rademacher随机变量的实现；也就是说，ξ∈ {-1,1}和P（ξi=-1） =P（ξ=1）=1/2。备注5.2。值得强调的一个技术点是，当被视为潜在产品概率空间的函数时，经验Rademacher复杂性可能不是一个可测量的函数。

虽然我们在附录B.2.1中说明了Rademachercomplexity | | Rn | | | | | | | | | | | | | | | | | | | | H`B）是-（Y×Z）n上的代数，这对于本文的目的是有效的。在我们的上下文中，H`B类的经验Rademacher复杂性仅依赖于观测到的经验分布和Rademacher随机变量的n次绘制；因此，可以通过Rademacher分布进行模拟后计算。有了这个新的定义，我们得到了以下结果：定理5.1。假设假设假设2.1、2.2、2.3和3.1成立。让我们来看看→ [~n\'b，~nub] R可以是丰富的、可测的函数，并且假设对于每个γ∈ Γ，随机集G-（·，θ）和G？（·，θ，γ）区域对于每个θ几乎肯定是非空的∈ Θ*. 设{（yi，zi）}ni=1be i.i.d.根据一些分布PY，Zsatisfyingour假设，设d:ψn→ Γ对于某些ε>0的情况，可能是eME决策规则。此外，让H<∞满足| h |≤ 每小时∈ H`b，并设：cn（κ）=4 | | Rn | | |（H`b）+s72 ln（2/（2）- κ） ）Hn+5ε。（5.3）对于任何样本量n和任何κ∈ （0,1）我们有：infPY，Z∈PY，ZP纽约，Zsupγ∈Γinfs∈SI[~n]（γ，s）- infs∈SI[~n]（d（ψ），s）≤ cn（κ）≥ κ. （5.4）证据。见附录B。定理5.1给出了两个密切相关的结果。首先，对于κ的任何固定值∈ （0，1）定理表明，当处于最坏情况时，eME规则在依赖于状态的策略变换的最大值的cn（κ）内获得，概率至少为κ。简单的比较静力学表明，当n较大和/或| | Rn | |（H`b）和H较小时，Cn（κ）的值较小。

计算Cn（κ）唯一困难的部分是计算Rademacher复杂度，这在计算上与计算定理3.1中下限的经验版本一样困难。我们再次看到了PAMPAC可学习性和定理3.1中的下包络函数之间的密切联系。定理3.1中下包络函数的特殊形式使得它特别适合于使用浓度不等式进行分析，浓度不等式用于定理5的证明。1.同样，该结果需要假设3.1：没有惩罚的最终（已知）值*,无法推导定理5.1中的有限样本结果。最后，我们再次提到，与关于PAMPAC可学习性的定理4.1不同，定理5.1没有对基础函数类H`b施加任何限制。特别是，该类函数不需要满足定义4.2中的熵增长条件，也不需要满足任何其他关于可学习性的充分条件，这意味着即使在PAMPAC不可学习的情况下，定理5.1也适用。因此，定理5.1能够为eME规则提供有限的样本保证，但必然对收敛速度保持沉默。5.2最优策略集的界限上一小节使用了一个特定的规则，即eME规则，并得出了该规则性能的有限样本理论保证。然而，eME规则只是一个特定的规则，对于各种原因，它可能不是决策者选择的规则。为了补充上一小节的结果，在本小节中，我们将提供一些关于替代政策规则的理论结果。为了理解该方法，让我们定义函数：E*（γ） ：=supγ∈Γinfs∈SI[~n]（γ，s）- infs∈SI[~n]（γ，s）=supγ∈ΓI`b[Γ]（γ）- I`b[~n]（γ），（5.5）和集合：G*(δ) := {γ ∈ Γ：E*(γ) ≤ δ}. （5.6）我们把集合称为G*（δ） δ-水平集。

本小节的目标是提供δ的近似值-概率至少为κ的水平集。如果我们可以这样做，那么通过构造任何决策规则d:ψn→ Γ在δ的近似值范围内映射-水平集将有cn（d，κ）≤ δ. 可能有许多决策规则在我们近似于δ的范围内映射-水平集，因此我们的理论结果将适用于大量的决策规则。作为我们分析的副产品，我们还将表明，对于δ的某些值，eME规则将包含在δ中-概率至少为κ的水平集。同样，本节的结果没有对函数H`b的基本类施加任何限制，即使在Γ不是PAMPAC可学习的情况下也适用。来介绍我们关于δ的结果-水平集，我们必须首先引入一些额外的符号。特别是定义：En（γ）：=supγ∈Γinfs∈SbI[~n]（γ，s）- infs∈SbI[~n]（γ，s）=supγ∈ΓbI`b[Γ]（γ）-bI`b[~n]（γ），（5.7）对于δ>0，定义集合：Gn（δ）：={γ∈ Γ：En（γ）≤ δ}. （5.8）集合Gn（δ）代表δ的经验版本-水平集。下面的定理表明，对于足够大的δ-水平集包含在经验δ的放大和收缩中-高概率的水平集。定理5.2。假设假设假设2.1、2.2、2.3和3.1成立。还假设：V→ [~n\'b，~nub]R是一个有界的可测函数，对于每个γ∈ Γ，随机集G-（·，θ）和G？（·，θ，γ）区域对于每个θ几乎肯定是非空的∈ Θ*. 让H<∞ 满足| h |≤ 每小时∈ H`b，假设{（yi，zi）}ni=1是来自某个分布PY的i.i.d.，z满足了我们的假设。定义：Hn，`b（δ）：={h`b（·，·，θ，γ，λ）-h`b（·，·，θ，γ，λ）：θ，θ∈ Θ, γ, γ∈ Gn（δ），λ，λ∈ {0，1}J}，其中Hn，`b（δ）有一个统一的界Hn（δ）≤ 2H<∞.

此外，设tj:=pclog（cj），其中c=5和c=（3/（2（1））- κ） ）2/5，并设{δj}∞j=0可能是一个随着δ>2H而减小到零的序列。选择某人∈ (1, ∞), 设b=2- 1/a，let:Tn（δ）：=2 | | Rn | |（Hn，`b（bδj））+3tjHn（bδj）√n、 如果δ∈ （δj+1，δj]对于某些j≥ 00，否则，（5.9）和：T[n（σ）：=supδ≥σTn（δ）δ，（5.10）T]n（η）：=infnσ>0:T[n（σ）≤ ηo.（5.11）最后，设置δ*> T] n（1）-1/a）。那么对于任何δ≥ aδ*我们有：infPY，Z∈PY，ZPnY，Z（Gn（δ/a） G*(δ)  Gn（bδ））≥ κ.证据见附录B。定理5.2与统计学习文献中的结果非常相似，即经验风险最小化问题中的超额风险边界问题。特别是，结果的证明使用了Koltchinski（2006）和Koltchinski（2011）开发的技术，后者给出了教科书式的处理方法。定理5.2给出了这些技术在存在部分识别的情况下对政策选择问题的新应用。与本文中的其他结果类似，定理5.2在很大程度上依赖于定理3.1中的下包络函数的形式。同样，假设3.1是必需的，因为定理5.2要求惩罚参数u的确定（和已知）值*.直觉上，定理5.2表示，对于δ的适当大值-函数（·）的水平集Gn（δ）可用于近似δ-水平集G*函数E的（·）*(·). 结果的重要组成部分是选择这样一个“适当大的δ值”特别是，我们的近似工作所需的δ值必须大于δ值*根据定理，其中δ*与定点方程的解有关。函数Tn（·）、T[n（·）和T]n（·）与定点方程的关系如图4所示，并在其相关标题中进行了描述。

如图所示，函数Tn（δ）是一个左连续阶跃函数，在区间[0，δ]上大于或等于零，否则为零。定理5.2的证明依赖于引理5.1，理解定理5.2的最佳方法是首先理解引理5.1。引理5.1。假设定理5.2的假设都成立。定义：H`b（δ）：={H`b（·，·，θ，γ，λ）-h`b（·，·，θ，γ，λ）：θ，θ∈ Θ, γ, γ∈ G*(δ), λ, λ∈ 其中H`b（δ）有一个统一的界H（δ）≤ 2H<∞. 此外，设tj:=pclog（cj），其中c=5，c=（3/（2（1））-κ） ）2/5，并设{δj}∞j=0可能是一个随着δ>2H而减小到零的序列。同样，设：T（δ）：=2 | | Rn | |（H`b（δj））+3tjH（δj）√n、 如果δ∈ （δj+1，δj]，0，否则，（5.12）[- 和]-变换取自Koltchinskii（2006），这些变换的性质见附录A.3。Koltchinskii（2011年）。图4：该图显示了确定δ的程序中的步骤（iv）-水平仪。选择递减序列{δj}∞j=0，决策者得出δ值*这样δ*> T] n（1）- 1/a）。在图中，这发生在区间（δ，δ）（当然，情况并非如此）。该图还说明了Tn（δ）是一个阶跃函数的事实。最后，该图说明了[- 和]-Tn（δ）的变换与定点方程有关。特别是，该图显示了Tn（δ）=δ的固定点，其精确由T]n（1）给出。此外，Tn（δ）=δ（1）的执行点- 1/a）由T]n（1）给出- 1/a）。和：T[（σ）：=supδ≥σT（δ）δ，（5.13）T]（η）：=infnσ>0:T[（σ）≤ ηo.（5.14）最后，假设δ**> T] （1）-1/a）对于一些a∈ (1, ∞). 那么对于任何δ≥ aδ**我们有：infPY，Z∈PY，ZPnY，Z（Gn（δ/a） G*(δ)  Gn（（2）-1/a）δ）≥ κ.证据见附录B。

注意，引理5.1与定理5.2非常相似，唯一的例外是引理5.1中的函数类H`b（δ）不同于定理5.2中的函数类Hn，`b（δ）。注意，hn，`b（δ）表示H`b（δ）的“可行版本”，因为H`b（δ）依赖于未知δ-水平集G*（δ） 式中，Hn，`b（δ）取决于经验δ-水平集Gn（δ）。启发性的证明可能有助于对这些结果如何工作提供某种意义。提供定理5.2或引理5.1的一个必要步骤是将量En（γ）和E联系起来*（γ） ，这正是引理5.1的证明。除此之外，引理5.1的证明证明了一个连接数量En（γ）和E的重要对象*（γ） 由δ7给出→ supθ，θ∈Θsupγ，γ∈G*（δ） supλ，λ∈∧|（Pnh`b（·，θ，γ，λ）- Pnh`b（·，θ，γ，λ））-（Ph`b（·，θ，γ，λ）- 式中：Pnh`b（·，θ，γ，λ）：=nnXi=1h`b（yi，zi，θ，γ，λ），phb（·，θ，γ，λ）：=Zh`b（y，z，θ，γ，λ）dPY，z。量（5.15）很容易被视为特定经验过程的超范数。注意，这个经验过程依赖于通过G和G的未知人口数量*（δ） 通过函数sp h`b（·，θ，γ，λ）和ph`b（·，θ，γ，λ），它们依赖于未知的真概率测度。而对G的依赖*（δ） 目前不可避免的是，通过使用（5.12）中的函数T（δ），可以消除对phb（·，θ，γ，λ）和phb（·，θ，γ，λ）的依赖。因此，引理5.1中的函数T（δ）与定理5.2中的函数Tn（δ）略有不同，它被构造为每个δ的量in（5.15）的上包络∈ [0，δ]，在概率至少为κ的事件上。用上界T（δ）代替（5.15），引理5.1的证明表明，如果σ：=E*（γ） ，以下不等式适用于事件En:E*(γ) ≤ En（γ）+T（σ），（5.16）En（γ）≤ E*（γ） +T（σ）。

（5.17）现在注意，如果δ**= T] （1）-1/a）+ε对于任何ε>0，则T（δ）≤ (1 -1/a）·每个δ的δ≥ δ**. 此外，通过构造δ的值**将接近最小的可能值，这是正确的。现在，用σ=E确定γ*(γ) ≥ δ**. 那么很明显：T（σ）≤1.-A.E*（γ） ，（5.18）将这个结果与（5.16）和（5.17）相结合，我们得到了满足E*(γ) ≥ δ**我们有：E*(γ) ≤ aEn（γ），（5.19）En（γ）≤ 是*(γ). （5.20）引理5.1证明的其余部分致力于证明以下不等式成立，从技术上讲，（5.15）对Ph`b（·θ，γ，λ）和Ph`b（·θ，γ，λ）的依赖性是通过非对称不等式（c.f.Van Der Vaart and Wellner（1996）引理2.3.1）和Hoe-ffing型浓度不等式消除的，这正好导致上界T（δ），它以很高的概率成立。任何γ∈ Γ关于事件En:E*(γ) ≤ a（En（γ）∨ δ**) , （5.21）En（γ）≤ b（E）*(γ) ∨ δ**) , （5.22）在建立了这些不等式之后，可以直接认为Gn（δ/a） G*(δ)  当δ≥ aδ**. 直观地，定理5.2的证明证明了H`b（δ），T（·）（及其[- 和]-变换）和δ**引理5.1中定义的可替换为其可行版本Hn、`b（δ）、Tn（·和[- 和]-变换）和δ*定义见定理5.2。定理5.2建议采用以下程序来近似δ-水平仪。决策者首先计算En（γ）作为γ的函数（例如，通过在Γ上建立网格）。政策制定者有时重视∈ (1, ∞) 并构造了一个序列{δj}∞j=0随（1）减小到零- 1/a）δ>2H。一般来说，如果序列{δj}∞j=0具有较小的初始增量。然后policymaker计算δ*> T] n（1）-1/a）。这是通过以下程序完成的：（i）决策者接受NI.i.d。

Rademacher随机变量ξ的绘制。（ii）在jthstep（从第0步开始），决策者使用En（γ）计算Rademacher复杂度| | | Rn | |（Hn，`b（bδj））和公式（5.2）。（iii）决策者使用En（γ）来计算Hn的统一上界Hn（δj），`b（δj）（或者她可以简化2H）。（iv）决策者确定是否存在任何价值δ∈ （δj+1，δj]使得Tn（δj）/δ≥ 1.-1/a.o如果是，决策者停止并设置δ*= δ+η，其中η>0和δ∈ （δj+1，δj]等于满足Tn（δj）/δ的任何值≤ 1.-1/a.o如果不是，决策者重复迭代j+1的步骤（i）和（ii）。图4中提供了该步骤的说明。根据定理5.2，决策者就知道了≥ δ*, δ-最小集G（δ）将包含在样本模拟δ中-最小集Gn（bδ），并将包含样本模拟δ-概率至少为κ的极小集Gn（δ/a）。请注意，此过程中的计算瓶颈来自重复计算Rademacher复杂度。除了本身有趣之外，定理5.2还揭示了前一小节的结果。特别地，定理5.2和引理B.9的证明导致以下结果，这是定理5.2的推论。请注意，第一个不平等是微不足道的，因为当E*(γ) ≥ δ**, 如果E*(γ) ≤ δ**, 然后是E*(γ) ≤ aδ**,因为a>1。第二个不等式是非平凡的，依赖于附录中引理B.9给出的辅助结果。推论5.1。假设定理5.2的假设成立，让δ*如定理5.2所示。对于任何ε>0的情况，让^γ∈ Γ是eME决策规则选择的政策。

如果δ≥ δ*≥ ε>0，则：infPY，Z∈PY，ZP纽约，Z（E）*(^γ) ≤ δ) ≥ κ.那是^γ∈ G*（δ） 当δ≥ δ*≥ ε > 0.这个结果表明，如果ε≤ δ*那么我们上一小节的eME规则将包含在δ中-水平集G*（δ） 当δ≥ δ*可能性很大。这应该作为使用eME规则的一些额外理由，因为它表明，当*和ε都很小，这是理论5建议的程序。2不会导致决策规则大大优于eME规则。6结论本论文的目的是为界定反事实数量和决策制定一个通用且新颖的框架。我们的框架适用于部分识别和/或不完整的模型。此外，我们不需要潜变量的参数分布假设，我们允许依赖于潜变量的矩条件。我们引入了策略变换，并认为许多反事实量可以写成某些函数的策略变换。然后，我们引入了一个考虑弱优势的偏好关系，并使用一个类似于计算学习理论中的PAC可学习性模型的框架讨论了政策选择问题。我们的理论结果分为事前（即观察样品前）和事后（即观察样品后）适用的结果。对于我们的事前结果，我们引入了“学习”策略空间的概念，并为策略空间的可学习性提供了充分的条件。对于事后结果，我们为特定政策规则的执行提供了理论保证。在本文中，我们还演示了如何将结果应用于同时离散选择示例和程序评估示例。这项工作有许多明显的扩展，可能会很有趣。

本文特别关注理论发展，其中的例子主要用于教学目的。需要进一步开发示例和实证应用，以清楚地说明和充分调查该方法在实践中的优缺点。此外，本文基本上没有提到实现，在某些环境下，实现可能会很复杂。显然，需要进一步开发有效的算法来实现这些程序。最后，PAC可学习性与频繁决策理论文献之间的关系需要进一步调查和澄清。我们相信所有这些扩展都是未来研究的富有成效的途径。参考Saliprantis，C.D.和Border，K.C.（2006）。有限维分析：搭便车指南。斯普林格。北卡罗来纳州阿隆、南卡罗来纳州本·大卫、北卡罗来纳州塞莎·比安奇和豪斯勒（1997年）。尺度敏感维度、一致收敛性和可学习性。ACM杂志（JACM），44（4）：615-631。Andrews，D.W.和Shi，X.（2013）。基于条件矩不等式的推理。《计量经济学》，81（2）：609-666。Andrews，D.W.和Shi，X.（2017）。基于许多条件矩不等式的推理。《经济计量学杂志》，196（2）：275-287。Angluin，D.和Laird，P.（1988年）。从嘈杂的例子中学习。机器学习，2（4）：343-370。Bartlett，P.L.，Boucheron，S.，和Lugosi，G.（2002）。模型选择和误差估计。机器学习，48（1-3）：85-113。Bartlett，P.L.，Bousquet，O.，Mendelson，S.，等人（2005年）。本地rademacher的复杂性。《统计学年鉴》，33（4）：1497-1537。Bartlett，P.L.，Long，P.M.，和Williamson，R.C.（1996）。脂肪粉碎和真实价值函数的可学习性。计算机与系统科学杂志，52（3）：434-452。贝洛尼，A.，布尼，F.A.，和切尔诺朱科夫，V.（2019年）。

具有许多动量等式的pi模型中的子向量推理。技术报告，cemmap工作文件。Beresteanu，A.，Molchanov，I.，和Molinari，F.（2011）。具有凸现预测的模型中的清晰识别区域。《计量经济学》，79（6）：1785-1821。Beresteanu，A.，Molchanov，I.，和Molinari，F.（2012）。使用随机集理论进行部分识别。《计量经济学杂志》，166（1）：17-32。Bertsekas，D.P.和Shreve，S.（1978年）。随机最优控制：离散时间情况。学术出版社。Blumer，A.，Ehrenfeucht，A.，Haussler，D.，和Warmuth，M.K.（1989）。可学习性和vapnikchervonenkis维度。ACM杂志，36（4）：929-965。S.布切龙、O.布斯克和G.卢戈西（2005年）。分类理论：对一些近况的调查。《概率与统计》，9:323-375。Bousquet，O.，Koltchinskii，V.，和Panchenko，D.（2002年）。凸函数复杂性的一些局部测度和推广界。在计算学习理论国际会议上，第59-73页。斯普林格。Bresnahan，T.F.和Reiss，P.C.（1990）。进入垄断市场。《经济研究评论》，57（4）：531-553。Bresnahan，T.F.和Reiss，P.C.（1991）。离散博弈的经验模型。计量经济学杂志，48（1-2）：57-81。布罗克，W.A.和杜洛夫，S.N.（2001）。社会互动的离散选择。《经济学研究回顾》，68（2）：235-260。Carneiro，P.，Heckman，J.J.和Vytlacil，E.J.（2011）。估算教育的边际回报。《美国经济评论》，101（6）：2754-81。张伯伦，G.（2011）。治疗选择的贝叶斯方面。《牛津贝叶斯计量经济学手册》，第11-39页。Chernozhukov，V.，Chetverikov，D.，Kato，K.，等人（2013年）。高维随机向量和的最大值的高斯近似和乘法器引导。

《统计年鉴》，41（6）：2786-2819。Chernozhukov，V.，Hong，H.，和Tamer，E.（2007）。经济计量模型中参数设置的估计和置信域。《计量经济学》，75（5）：1243-1284。Chesher，A.和Rosen，A.（2012）。离散结果的联立方程模型：一致性、完整性和识别。工作文件。Chesher，A.和Rosen，A.（2015）。结构计量经济学模型提供的识别集的特征。技术报告，cemmap工作文件。Chesher，A.和Rosen，A.M.（2014）。二元结果的工具变量随机系数模型。《计量经济学杂志》，17（2）：S1-S19。Chesher，A.和Rosen，A.M.（2017a）。广义工具变量模型。《计量经济学》，85（3）：959-989。Chesher，A.和Rosen，A.M.（2017b）。具有异质性的不完全英文拍卖模型。技术报告，cemmap工作文件。Chesher，A.和Rosen，A.M.（2020年）。同时离散选择的结构建模。工作文件。Chesher，A.，Rosen，A.M.，和Smolinski，K.（2013）。多重离散的工具变量模型。数量经济学，4（2）：157-196。Ciliberto，F.，Murry，C.，和Tamer，E.T.（2018）。航空市场的市场结构和竞争。可通过SSRN 2777820获得。科恩·D·L.（2013）。测量理论。斯普林格。Corbae，D.，Stinchcombe，M.B.，和Zeman，J.（2009）。数学分析、经济预测理论和计量经济学导论。普林斯顿大学出版社。Dolgopolik，M.（2016）。线性罚函数精确性的统一理论。优化，65（6）：1167-1202。Dontchev，A.L.和Rockafellar，R.T.（2009）。隐函数和解映射。斯普林格·莫诺格。数学达德利，R.M.（2010）。真实分析和概率。剑桥大学出版社。达德利，R.M.（2014）。一致中心极限定理。剑桥大学出版社。达德利，R.M.，金恩，e.和津恩，J.（1991）。

统一和通用的glivenko cantelli课程。《理论概率杂志》，4（3）：485-510。艾克兰，I.，加利孔，A.，和亨利，M.（2010）。最优运输和不完全特定经济模型的可靠性。经济理论，42（2）：355-374。Galichon，A.和Henry，M.（2006）。不完全模型中的推理。工作文件。Galichon，A.和Henry，M.（2009）。部分识别参数的非识别限制和信任区域测试。计量经济学杂志，152（2）：186-196。Galichon，A.和Henry，M.（2011）。在具有多重平衡的模型中设置识别。经济研究回顾，78（4）：1264-1298。金恩，e.，科尔钦斯基，V.，等人（2006年）。比率型经验过程的集中不等式和渐近结果。《概率史记》，34（3）：1143-1216。吉恩·e.，科尔钦斯基，V.和韦尔纳，J.A.（2003年）。经验过程的比率极限定理。InStochastic不等式及其应用，第249-278页。斯普林格。Haile，P.A.和Tamer，E.（2003）。用英语拍卖的不完全模型进行推理。《政治经济学杂志》，111（1）：1-51。豪斯勒博士（1992年）。pac模型在神经网络和其他学习应用中的决策理论推广。信息与计算，100（1）：78-150。赫克曼，J.J.（2010）。在结构评估和项目评估方法之间建立桥梁，以评估政策。经济文献杂志，48（2）：356-98。Heckman，J.J.和Vytlacil，E.（2005）。结构方程、处理效果和经济计量政策评估1。《计量经济学》，73（3）：669-738。Heckman，J.J.和Vytlacil，E.J.（1999）。用于识别和界定治疗效果的局部工具变量和潜变量模型。美国国家科学院院刊，96（8）：4730-4734。希梅尔伯格，C.（1975）。可测量的关系。《数学基础》，87（1）：53-72。平野，K。

和Porter，J.R.（2009）。统计处理规则的渐近性。《计量经济学》，77（5）：1683-1701。Hurwicz，L.（1950年）。识别概念的概括。《动态经济模型中的统计推断》，10:245–57。Ichimura，H.和Taber，C.R.（2000年）。直接估计政策影响。工作文件。Imbens，G.W.和Angrist，J.D.（1994年）。确定和估计当地平均治疗效果。《计量经济学》，62（2）：467-475。Io Offe，A.（2016年）。度量正则性——综述第1部分。学说《澳大利亚数学学会杂志》，101（2）：188–243。贾平（2008）。沃尔玛进城后会发生什么：折扣零售业的实证分析。《计量经济学》，76（6）：1263-1316。约万诺维奇，B.（1989年）。具有多重平衡的模型的可观察含义。计量经济学：计量经济学学会杂志，1431-1437页。Kaido，H.，Molinari，F.，和Stoye，J.（2019年）。部分识别中的约束条件。arXiv预印本arXiv:1908.09103。Kalouptsidi，M.，北村，Y.，利马，L.，和Souza Rodrigues，E.（2019年）。动态模型和反事实的部分识别和推断。工作文件。凯西，M.（2016）。部分认同、分配偏好和政策的福利排名。《经济学与统计学评论》，98（1）：111–131。卡恩斯，M.J.和夏皮雷，R.E.（1994）。有效的概率概念无分布学习。计算机与系统科学杂志，48（3）：464-497。卡恩斯，M.J.，瓦济拉尼，U.V.，和瓦济拉尼，U.（1994）。计算学习理论导论。麻省理工学院出版社。北川，T.和Tetenov，A.（2018年）。应该治疗谁？治疗选择的经验福利最大化方法。《计量经济学》，86（2）：591-616。科尔钦斯基五世（2001年）。Rademacher惩罚和结构风险最小化。IEEE信息论学报，47（5）：1902-1914。Koltchinski，V.（2006年）。

风险最小化中的局部rademacher复杂性和oracle不等式。《统计年鉴》，34（6）：2593-2656。Koltchinski，V.（2011年）。甲骨文在经验风险最小化和稀疏恢复问题上的不平等性：圣面粉经济学院第三十八卷，2008年，第2033卷。斯普林格科学与商业媒体。Koltchinskii，V.和Panchenko，D.（2000年）。Rademacher处理和限制函数学习的风险。在高维概率II中，第443-457页。斯普林格。T.C.库普曼斯、H.鲁宾和R.B.莱普尼克（1950）。测量动态经济学的方程组。动态经济模型中的统计推断，10。科索罗克，M.R.（2008）。介绍经验过程和半参数推理。斯普林格。刘易斯·D.（1979）。反事实依赖和时间之箭。不，我们，第455-476页。Li，L.（2019）。在一大类结构经济计量模型中识别结构和反事实参数。工作文件。罗志强、彭俊生和拉尔夫·D.（1996）。具有平衡约束的数学程序。剑桥大学出版社。Manski，C.和Tetenov，A.（2014）。统计处理规则的分位数性能使用假设专家将一个群体分配给两个处理。技术报告，cemmap工作文件。曼斯基，C.F.（1988）。不确定性下决策的序数效用模型。理论与决策，25（1）：79-104。曼斯基，C.F.（2004）。异质人群的统计处理规则。《计量经济学》，72（4）：1221-1246。曼斯基，C.F.（2011）。现实主义理性。《理论与决策》，71（2）：195-210。Marshak，J.（1953年）。政策和预测的经济衡量。计量经济学方法研究，第1-26页。马萨特，P.（2000年）。集中不等式在统计学中的一些应用。《图卢兹学院科学年鉴：数学》第9卷第245-303页。姆巴科普，E。

和Tabord Meehan，M.（2019年）。治疗选择的模型选择：惩罚福利最大化。arXiv预印本arXiv:1609.03167。宫内（2016）。具有非负外部性的成对稳定网络的结构估计。《计量经济学杂志》，195（2）：224-235。Mogstad，M.，Santos，A.，和Torgovitsky，A.（2018）。使用工具变量推断与政策相关的治疗参数。《计量经济学》，86（5）：1589-1619。Mohri，M.，Rostamizadeh，A.，和Talwalkar，A.（2018）。机器学习的基础。麻省理工学院出版社。Molchanov，I.（2017年）。随机集理论。斯普林格科学与商业媒体。摩根，M.S.（1990）。计量经济学思想的历史。剑桥大学出版社。I.穆里菲、M.亨利和R.米恩戈（2018年）。茎主选择罗伊模型的精确界限和可测试性。可从SSRN 2043117获得。I.Mouri Fie和Y.Wan（2020年）。在使用mte的项目评估中进行分层敏感性分析。工作纸。Munkres，J.（2014）。拓扑结构。培生教育。彭俊生（1997）。数学规划中的误差界。数学规划，79（1-3）：299-332。Parthasarathy，K.R.（2005）。度量空间上的概率测度，第352卷。美国数学学会。Pearl，J.（2009）。因果关系：模型、推理和推理。斯普林格。Pollard，D.（1990年）。经验过程：理论与应用。NSF-CBMS概率与统计区域会议系列，第i-86页。杰斯特。秦，D.和吉尔伯特，C.L.（2001）。时间序列计量经济学史上的误差项。计量经济学理论，17（2）：424-450。罗斯泰克，M.（2010）。决策论中的分位数最大化。《经济研究评论》，77（1）：339-371。罗素·T·M.（2019）。治疗效果分析中联合分布函数的锐界。《商业与经济统计杂志》，第1-15页。Schennach，S.M.（2014）。

通过模拟进行熵潜变量积分。《计量经济学》，82（1）：345-385。Shalev Shwartz，S.和Ben David，S.（2014）。理解机器学习：从理论到算法。剑桥大学出版社。Shalev Shwartz，S.，Shamir，O.，Srebro，N.，和Sridharan，K.（2010）。可学习性、稳定性和一致性。机器学习研究杂志，11（10月）：2635-2670。Shreve，S.E.和Bertsekas，D.P.（1978）。有限时域离散时间随机最优控制的替代理论框架。暹罗控制与优化杂志，16（6）：953-978。Shreve，S.E.和Bertsekas，D.P.（1979）。动态规划中普遍可测量的策略。运筹学数学，4（1）：15-30。斯坦奇科姆，M.B.和怀特，H.（1992）。随机集上随机函数极值的一些可测性结果。《经济研究评论》，59（3）：495-514。斯托耶，J.（2009）。使用有限样本的Minimax后悔治疗选择。计量经济学杂志，151（1）：70-81。斯托耶，J.（2011）。模糊性下的统计决策。《理论与决策》，70（2）：129-148。斯托耶，J.（2012）。具有协变量或实验有效性有限的极小极大后悔治疗选择。计量经济学杂志，166（1）：138-156。Syrgkanis，V.，Tamer，E.，和Ziani，J.（2018）。对信息假设较弱的拍卖进行推断。arXiv预印本arXiv:1710.03830。Tamer，E.（2003年）。具有多个平衡点的不完全同时离散响应模型。经济研究综述，70（1）：147-165。Tebaldi，P.，Torgovitsky，A.，和Yang，H.（2019）。加州医疗保险交易所需求的非参数估计。技术报告，国家经济研究局。Tetenov，A.（2012年）。基于非对称极大极小后悔标准的统计治疗选择。《经济计量学杂志》，166（1）：157-165。托戈维茨基，A.（2019年）。

通过扩展子分布进行部分识别。数量经济学，10（1）：105-144。Uetake，K.和渡边，Y.（2019年）。通过合并进入：根据具有外部性的双边匹配模型进行估计。可通过SSRN 2188581获得。Valiant，L.（2013年）。也许大致正确：大自然在复杂世界中学习和繁荣的算法。基本书籍（AZ）。Valiant，L.G.（1984年）。一种可以学习的理论。第十六届ACM计算理论年度研讨会论文集，第436-445页。ACM。Van Der Vaart，A.W.和Wellner，J.A.（1996年）。弱收敛。弱收敛和经验过程，第16-28页。斯普林格。Vapnik，V.（1995年）。统计学习理论的本质。斯普林格科学与商业媒体。瓦普尼克案（1998年）。统计学习理论。纽约Vidyasagar，M.（2002年）。学习和概括的理论。斯普林格·维拉格。Vytlacil，E.（2002年）。独立性、单调性和潜在指数模型：一个等价结果。《计量经济学》，70（1）：331-341。沃尔德·A.（1950）。统计决策函数。威利。预备赛。1随机集理论的预备知识本附录介绍了随机集理论的一些关键要素。由于可测性问题在随机集理论中起着重要作用，我们从定义可测多功能开始，并展示其与随机集定义的联系。定义A.1（效应可测量性，随机集）。让(Ohm, A、 P）是一个概率空间，设V是一个Polishspace，设OV表示V上所有开集的集合。多功能V：Ohm → 对于每一个A，Fv被称为E eff∈ 我们有-（A） ：={ω∈ Ohm : V（ω）∩ A 6=} ∈ A.

概率空间上的一个可测闭值多函数(Ohm, A、 P）称为随机闭集。从这个定义中，我们可以看出，随机闭集是一种可测量的闭多功能函数，它将基本概率空间中的元素提取到某些波兰空间上的闭集集合。可测量的闭合多功能函数有时也称为弱可测量。当潜在的概率空间(Ohm, A、 P）是否完全有效可测量性等同于（i）和（V）-（B）∈ A全部B∈ B（V）（Borel可测性）和（ii）V-（F）∈ A代表所有F∈ FV（强可测量性）。我们在这篇论文中的主要兴趣是当V是有限维欧氏空间的子集时，尽管框架更一般。虽然对于许多结果来说，可测量性是可测量性的正确概念，但很难验证。还有其他一些条件对效率的可测量性是有效的，但我们发现一个条件在示例中特别有用。让d表示波兰空间V上的度量，让V：Ohm → FVS应该是多功能的。到V上集合V（ω）的距离由：d（V，V（ω））：=inf{d（V，V）：V给出∈ V（ω）}。根据Himmelberg（1975）的结果，多功能V的可测性等同于d（V，V（ω））的可测性（作为来自Ohm 到[0，∞]) 每v∈ V.在整篇论文中，理解两个随机集相互分布的含义也很重要，这将在下一个定义中提供。定义A.2（同分布随机集）。让(Ohm, A、 P）是一个概率空间，设V是一个波利斯空间。我们说两个随机集V和V*分布相同，用V表示~ 五、*, 如果为了everyA∈ 我们有P（ω：V（ω）∩ A 6=) = P（ω：V）*(ω) ∩A 6=).最后，随机集理论中的一个重要概念是从随机集中进行选择。

直观地说，一个随机集V可以理解为满足V（ω）的随机变量V的集合∈ V（ω）P-a、 这类随机变量称为随机集V中的选择，其定义如下。参见Aliprantis and Border（2006）第18章参见Molchanov（2017）定理1.3.3，第59页。定义A.3（选择、条件选择）。随机元素V：Ohm → 如果V（ω），V被称为V的（可测量）选择∈ P的V（ω）-几乎所有ω∈ Ohm. 随机集V的所有可测量选择的族将用Sel（V）表示。虽然在符号中被抑制，但选择序列Sel（·）既取决于随机集V的分布，也取决于潜在的概率空间。事实上，同一概率空间上的两个相同分布的随机集可能有不同的选择族。然而，来自同一概率空间上两个随机闭集的选择族的弱闭凸包是一致的。此外，当潜在的概率空间是非原子的时，不必采用凸壳。见正文定义3.1之后的讨论。A.2 PAC可学习性正如引言中所述，我们对可学习性的定义与Valiant（1984）中规定的可学习性定义有关。因此，从计算学习理论中理解可学习性的概念将是有用的。为了清晰起见，我们将省略技术细节。在一个有监督的学习问题中，研究者被假定有一个i.i.d.样本ψ=（（yi，zi））ni=1来自真实度量PY，Z。研究者还被假定有一类函数F，称为假设空间。研究人员的目标是选择一个函数f:Z→ Y、 从假设空间F中调用一个假设（或一个分类器或一个预测器），该假设空间F可以准确地预测给定值Z中Y的值。

给定函数f的性能∈ F根据损失函数进行测量。也就是说，假设研究者有一些函数L:Y×Y→ R，使得L（y，f（z））测量预测f（z）时产生的损失，结果的真实值为y。然后，选择好假设f的问题转化为选择f的问题∈ F尽量减少预期损失或风险。在这种情况下，决策规则是一个可测量的映射d:ψn→ F，从假设空间中选择一个假设；在学习理论中，这种决策规则被称为算法。到目前为止，读者应该注意到与统计学和计量经济学中的决策问题相似之处。然而，在评估给定的统计决策规则时，各领域之间会出现重大差异。特别是，计算机科学家对在有限样本中以高概率实现接近最小可能风险的规则感兴趣。为了严格地定义这一点，让^f∈ F是某个决策规则（或算法）选择的假设d:ψn→ F.自^F∈ F取决于观察到的样本，在此之前它将是arandom变量。现在fix任意值（c，κ）∈ R++×（0,1）。然后，如果：infPY，Z，则^f近似于有限样本中最优决策规则的性能∈PY，ZP纽约，Zinff∈FE[L（y，f（z））]- E[L（y，^f（z））]≤ C≥ κ、 （A.1）对于较小的c值∈ R+和大的κ值∈ （0，1）样本量为n时，PY是Y×Z上所有Borel概率测度的集合，因此决策规则的性能与Molchanov（2017）第79页示例1.4.2一致。所有可能的分布PY，Z∈ PY，Z.我们现在可以引入（不可知）PAC可学习性的概念，该概念最初由Haussler（1992）提出。定义A.4（不可知PAC可学习性）。

如果存在一个函数ζF:R+×（0,1），则假设类F对于损失函数L可能是（不可知的）近似正确（PAC）可学习的→ N如此，对于任何（c，κ）∈ R++×（0,1）→ N、 如果N≥ ζF（c，κ）然后有一些决策过程d:ψn→ f:f=d（ψ）满足（A.1）。备注A.1。这一定义忽略了Valiant（1984）论文中关于PAC可学习性的原始定义的一个重要组成部分，该定义还要求算法（决策规则）可以在多项式时间内处理（相对于其输入长度）。对于一些人来说，这可能是一个严重的遗漏，因为算法能被有效处理的要求被视为可学习性不计算学习理论的核心组成部分。换句话说，假设空间是（不可知的）PAC可学习的，如果我们能保证（a.1）适用于对（c，κ）的任何选择∈ R++×（0，1）表示足够大的n。这里，c称为容错参数，κ称为置信参数。定义的“不可知”部分指的是假设类别F可能包括也可能不包括真正的标签函数F*: Z→ Y事实上，这种“真正的”标签功能甚至可能不存在。与评估决策规则的其他常用方法相比，PAC框架的一个主要优势是其分析的可处理性，以及通过集中不等式和经验过程理论的技术进行分析的适应性。事实上，当判定规则d:ψn→ F对应于经验风险最小化规则，众所周知，PAC的可学习性是由经验风险对总体风险的一致收敛（在PY、Zand和F上）所暗示的。在特定的学习问题中，这种一致收敛相当于可学习性（参见Alon等人（1997）和Shalev Shwartzet等人（2010）中的讨论）。

这意味着经验过程理论中成熟的工具可以用来建立一类特定函数的可学习性。直觉上，一个特定的函数类是否可以学习取决于函数类的“复杂性”。有各种各样的方法来衡量F的复杂性，其中一些是在当前的论文中遇到的。一般来说，表现出较少复杂性的类比表现出更多复杂性的类更容易学习，如果一类函数太复杂，它可能无法学习。B证明标记B.1（通用符号）。为了避免重复，我们在定理4.1、定理5.1、引理5.1和引理B.9的顶部引入了一些常用的符号。特别是对于任何θ∈ Θ和γ∈ Γ注意，考虑外部概率是必要的，因为选择^f的抽样不确定性不是由内部期望解决的。这一观点在Valiant（2013）中很明显。例如，参见Shalev Shwartz和Ben David（2014）引理4.2。让λ*（θ，γ）和^λ（θ，γ）满足：phb（·θ，γ，λ）*（θ，γ））=maxλ∈λphb（·，θ，γ，λ），（b.1）Pnh`b（·，θ，γ，^λ（θ，γ））=maxλ∈λPnh`b（·，θ，γ，λ）。（B.2）现在对于任何γ∈ Γ，让θ*θ满足：phb（·，θ）*(γ), γ, λ*(θ*(γ), γ)) ≤ infθ∈ΘP h`b（·，θ，γ，λ）*（θ，γ））+ε，（B.3）Pnh`B（·θ（γ），γ，λ（θ（γ），γ））≤ infθ∈ΘPnh`b（·，θ，γ，^λ（θ，γ））+ε，（b.4）最后，让γ*γ满足：phb（·，θ）*(γ*), γ*, λ*(θ*(γ*), γ*)) ≥ supγ∈ΓP h`b（·θ）*(γ), γ, λ*(θ*(γ), γ)) -ε、 （B.5）Pnh`B（·，θ（γ），γ，λ（θ（γ），γ））≥ supγ∈ΓPnh`b（·，^θ（γ），γ，^λ（^θ（γ），γ））- ε. （B.6）有了这些定义，很容易证明：supγ∈Γinfθ∈Θmaxλ∈∧phb（·，θ，γ，λ）≤ infθ∈Θmaxλ∈∧phb（·，θ，γ）*, λ） +3ε，（B.7）supγ∈Γinfθ∈Θmaxλ∈λPnh`b（·，θ，γ，λ）≤ infθ∈Θmaxλ∈λPnh`b（·，θ，^γ，λ）+3ε。

（B.8）此外，我们随时可以选择γ*^γ满足：infθ∈Θmaxλ∈∧phb（·，θ，^γ，λ）≤ infθ∈Θmaxλ∈∧phb（·，θ，γ）*, λ） ，（B.9）infθ∈Θmaxλ∈∧Pnh`b（·，θ，γ）*, λ) ≤ infθ∈Θmaxλ∈λPnh`b（·，θ，^γ，λ）。（B.10）备注B.2（可测量性）。我们不会在每一个证明中评论可测量性问题，而是让读者参考附录B.2.1（即命题B.1和推论B.1）中的讨论。研究表明，本文中某些通常（Borel）不可测量的量仍然是可普遍测量的。这允许我们使用外部度量来解决可测量性问题，尽管这在许多证明中是隐含的。然而，我们也注意到，所有可测量性问题也可以通过限制Θ和Γ最多有几个点来解决。B.1主要结果的证明命题2.1的证明。假设我们有γ7→ infs∈SI[~n]（γ，s）是普遍可测量的。每个决策规则的可测性：ψn→ Γ（以及由此产生的普适可测性），以及普适可测函数在合成下闭合的事实，这意味着映射ψ7→infs∈SI[~n]（d（ψ），s）是普遍可测的。在注意到supγ后，引理B.2给出了结果∈Γinfs∈SI[~n]（γ，s）是每个PY，Z的常数∈ PY，Z（因此扮演LemmaB中的“c（P）”角色）。2). 引理3.1的证明。确定满足假设3.2的δ>0的值。我们将着重于证明（3.8）成立，因为（3.9）的证明类似。通过引理B.3的迭代应用，（3.8）可以重写为：infθ*∈Θ*津福∈G-（y，z，θ）*)英菲？∈G（y，z，u，θ，γ）~n（v）dPY，z-津福∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）~n（v）dPY，z≤ Cd（θ，Θ）*).注意，这个不等式对于任何C≥ θ为0时∈ Θ*. 因此，当θ∈ Θ*δ\\ Θ*.

此外，对于后一种情况，必须找到C的值≥ 0:Z英孚∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）- 英孚∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）dPY，Z≤ Cd（θ，θ），对于任何θ，θ∈ Θ*δ. 然而，要在上一次展示中找到，必须找到以下内容：infu∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）- 英孚∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）≤ Cd（θ，θ），（B.11）（y，z）-a、 s.固定任意ε>0，并让（y，z）∈ Y×Z可以是任意对（在（3.10）和（3.11）中的空集之外）。对于任何θ，θ∈ Θ*让我们*, U*, Y*和y*满足：u*∈ G-（y，z，θ），y*∈ G（y，z，u）*, θ、 γ），u*∈ G-（y，z，θ），y*∈ G（y，z，u）*, θ、 γ）和：ψ（y，z，u）*, Y*) ≤ 英孚∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）+ε，ν（y，z，u）*, Y*) ≤ 英孚∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）+ε。为了简单起见，我们将表示v*:= （y，z，u）*, Y*) 和v*:= （y，z，u）*, Y*). 现在，根据提案3C。1 inDontchev and Rockafellar（2009），条件（3.11）暗示：dH（G？（y，z，u，θ，γ），G？（y，z，u，θ，γ））≤ `d（θ，θ），θ, θ∈ Θ*δ（y，z，u）-a、 因此，自从*∈ G（y，z，u，θ，γ）假设存在y∈ G（y，z，u，θ，γ）使得*) ≤ `d（θ，θ）。此外，根据命题3C。1在Dontchev和Rockafellar（2009）中，条件（3.10）意味着：-（y，z，θ），G-（y，z，θ））≤ `d（θ，θ），θ, θ∈ Θ*δ.因此，既然你*∈ G-（y，z，θ）假设存在u∈ G-（y，z，θ）使得d（u，u*) ≤ `d（θ，θ）。回想一下，度量空间（X，d）的两个非空子集A和B之间的hausdorff距离由以下公式给出：dH（A，B）：=max苏帕∈Ainfb∈Bd（a，b），supb∈宾法∈广告（a，b）.现在让我们定义v:=（y，z，u，y）。然后我们有：infu∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）- 英孚∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）≤ ~n（v）*) -~n（v）*) + ε≤ ~n（v）-~n（v）*) + 2ε≤ L k d（（y，u），（u*, Y*)) + 2ε≤ L~nmax{d（y，y）*), d（u，u）*)} + 2ε≤ L~nmax{`，`}d（θ，θ）+2ε，适用于所有θ，θ∈ Θ*δ.由于ε>0是任意的，我们得出结论，Cin（B.11）可以被取为等于L~nmax{`，`}。这就完成了证明。定理3.1的证明。

我们将展示下界，因为上界的证明是对称的。我们将证明以下等式和不等式序列：I[~n]（γ）：=Z~n（v）dPVγ≥ infθ∈Θ*infPU | Y，Z∈PU | Y，Z（θ）infPY？γ| Y，Z，U∈皮耶？γ| Y，Z，U（θ，γ）Z~n（v）dPVγ（B.12）=infθ∈ΘinfPU | Y，Z∈PU | Y，Z（θ）infPY？γ| Y，Z，U∈皮耶？γ| Y，Z，U（θ，γ）Z~n（v）dPVγ+u*JXj=1λ`bj（θ，PY，Z）EPY，Z，U[mj（y，Z，U，θ）]！（B.13）=infθ∈ΘinfPU | Y，Z∈PU | Y，Z（θ）Zinfy？∈G（y，z，u，θ，γ）~n（v）dPY，z，u+u*JXj=1λ`bj（θ，PY，Z）EPY，Z，U[mj（y，Z，U，θ）]！（B.14）=infθ∈Θ津福∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）+u*JXj=1λ`bj（θ，PY，Z）mj（y，Z，u，θ）！dPY，Z（B.15）=infθ∈Θmaxλj∈{0,1}Zinfu∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）+u*JXj=1λjmj（y，z，u，θ）！dPY，Z.（B.16）不平等（B.12）是显而易见的。等式（B.13）源自引理B.4。等式（B.14）和（B.15）来自引理B.3。最后，（B.16）来自引理B.5。定理4.1的证明。设F是一类实值函数，设ψ=（（yi，zi））ni=1指定一个特定的函数，我们将乘积度量作为sup度量；也就是说，如果（X，d）和（X，d）是两个度量空间，那么productmetric d∞关于定义为d的X×Xis∞（（x，x），（x，x））=maxd（x，x），d（x，x）.样本向量取样本空间ψn中任意f，f的值∈ F定义标准：| | F- f | |ψ，2:=nXi=1（f（yi，zi）-f（yi，zi））！1/2.回想一下：h`b（y，z，θ，γ，λ）：=infu∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）+u*JXj=1λjmj（y，z，u，θ）！。为便于注释，我们将定义为：Pnh`b（·θ，γ，λ）：=nnXi=1infui∈G-（yi，zi，θ）infy？我∈G（yi，zi，ui，θ，γ）~n（vi）+u*JXj=1λjmj（yi，zi，ui，θ）！，phb（·，θ，γ，λ）：=Zinfu∈G-（y，z，θ）infy？∈G（y，z，u，θ，γ）ν（v）+u*JXj=1λjmj（y，z，u，θ）！dPY，Z.对于任何判定规则d:ψn→ Γ和任何PY，Z∈ PY，Z，我们用马尔可夫不等式和定理3.1:P纽约，Zsupγ∈Γinfs∈SI[~n]（γ，s）- infs∈SI[~n]（d（ψ），s）≥ C≤总工程师supγ∈Γinfs∈SI[~n]（γ，s）- infs∈SI[~n]（d（ψ），s）=总工程师supγ∈ΓI`b[Γ]（γ）- I`b[~n]（d（ψ））. （B.17）现在注意对称化（例如。