策略转换和学习最优策略

通过模拟进行熵潜变量积分。《计量经济学》，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）现在注意对称化（例如。