策略转换和学习最优策略

证明中提出的具体决策程序是在每个样本ψ的样本模拟下包络函数最大值ε范围内获得的任何程序∈ ψ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（σ）。