期权定价中的维度诅咒与最优解

对于事件A，I（A）将表示相应的指示器功能。Leopt公司= infτ∈TE【Zτ】，和【OPT】= supτ∈TE[Zτ]。2.2. 简单直觉我们从给出方法背后的简单直觉开始。我们希望计算OPT=infτ∈TE[Zτ]。根据简单的样本路径论证，infτ∈TE[Zτ]≥ E[铸币厂∈[1，T]Zt]。我们现在观察到E[微型∈[1，T]Zi | Ft]，T∈ [1，T]是鞅w.r.t F，optionalstopping定理暗示infτ∈TE[Zτ]=E[薄荷∈[1，T]Zt]+infτ∈TE公司Zτ- E[微型∈[1，T]Zi | Fτ]. （1） 对于t∈ [1，T]，让Zt= Zt和Zt= Zt公司- E[微型∈[1，T]Zi | Ft]。那么（1）等价于toOPT=infτ∈TE[Zτ]=E[薄荷∈[1，T]Zt]+infτ∈TE[Zτ]。（2） 现在，我们简单地观察到，我们可以递归地在问题infτ上重复这个过程∈TE[Zτ]，然后是所有后续问题。正如我们将看到的（并且有些引人注目的是），这会产生一个n显式扩展，并快速收敛到最佳值，这是可以模拟的！2.3. 新颖的纯对偶解决方案我们通过陈述新的纯对偶表示来请求对结果的形式化陈述，这形成了上述简单的直觉。在这里，我们只讨论了关于最优值的含义（在最小化框架中），并将相关对偶鞅（以及与网络流的连接）的正式讨论留给第3节。然后，我们对OPTis的纯双重表示如下。对于k≥ 1和t∈ [1，T]，设Zk+1t= Zkt公司- E迷你∈[1，T]Zki | Ft. 设Z a和zk表示各自的随机过程，我们注意到它们是非负的（通过条件期望的基本性质和Z的非负性）。对于k≥ 1、让香港= E[铸币厂∈[1，T]Zkt]。定理1。

OPT=P∞k=1Hk。我们注意到，在许多方面，定理1的陈述是相当令人惊讶的，因为它表明，一般路径相关的最优停止问题的值有一个r表示，它看起来非常像一个闭式解。为了明确这一点，让我们更明确地给出前几个术语。H=E造币厂∈[1，T]gt（Y[T]）; H=E造币厂∈[1，T]gt（Y[t]）- E迷你∈[1，T]gi（Y[i]）| Ft;H=E“薄荷糖∈[1，T]gt（Y[T]）- E迷你∈[1，T]gi（Y[i]）| Ft- E迷你∈[1，T]gi（Y[i]）- Eminj公司∈[1，T]gj（Y[j]）| Fi|英尺!#.请注意，第一项H对应于明显的下限。后面的术语是优雅而明确的FIMA期望值，每一个都可以通过模拟计算得出，其中kthChen和Goldberg：《战胜期权定价中的维度诅咒》和《最优止损术语》只涉及k个嵌套条件期望值。现在，我们给出了最优阈值的相应结果。Letτ*表示Zt第一次停止的停止时间- EP∞k=1mini∈[1，T]Zki | Ft= 如果[1，T]中不存在这样的时间，则在时间Tif停止。推论1。W、 第1页 t型∈ [1，T]s.T.Zt- EP∞k=1mini∈[1，T]Zki | Ft= 0和τ*是停止问题infτ的最优解∈TE[Zτ]。Nam ely，E【Zτ】*] = 选择。2.4. 近似保证和收敛速度Theorem 1的威力在于，当单位被截断时，它允许严格的近似保证。让Ek=Pki=1Hi。定理2。假设w.p.1 Zt∈ [0，1]对于所有t∈ [1，T]。那么对于所有k≥ 1, 0 ≤ 选择- 埃克≤k+1。因此，在k项之后截断我们的展开式会在mostk+1处产生一个绝对误差。

请注意，这与其他纯对偶方法（以及基本上在一般路径依赖下解决此问题的所有其他方法）的已知结果形成了鲜明对比，因为我们的近似方法允许我们明确地权衡近似误差和所需的嵌套水平（条件期望）。人们可能希望，如果一个人最初的停止问题在某种程度上是“容易的”，那么他就可以表现出更快的收敛速度。通过递归应用Hil和Kertz（1983）的著名先知不等式，我们的下一个结果证明了事实确实如此。让我们定义h：[0，1]→ [0，1]为函数s.t.h（x）= (1 - x） 日志（1-x） 。对于k≥ 2和x∈ [0，1]，让hk（x）=h类香港-1（x）, i、 e.函数H与自身构成k次。然后我们证明如下。定理3。假设w.p.1 Zt∈ [0，1]对于所有t∈ [1，T]。那么对于所有k≥ 1，可选-埃克≤ 香港（可选）。此外，对于每个固定的x∈ [0，1]，{hk（x），k≥ 1} 是一个收敛到0的单调递减序列；和limx↓0h（x）=limx↑1h（x）=0。定理3暗示，如果OPT接近0或1，那么在只进行一轮之后，我们的方法将具有非常小的误差。尽管规范化参数立即将eorems 2和3扩展到了whichw的情况。p、 1兹特∈ [0，U]对于某些一般上界U，这种方法可能是不可取的，因为误差相对于（可能较大的）上界，而且过程可能是无界的。我们现在给出了一个一般的界，它不需要这样的规范化假设，代价是收敛速度较慢。这种放缓是根本性的，还是仅仅是我们分析的产物，仍然是一个有趣的问题。Chen和Goldberg：击败期权定价中的维度诅咒和最优阻止理论4。

在非负性以外的任何假设下，对于所有k≥ 1，可选- 埃克≤ 2 ×E[（ZT）]选项×k-×可选。我们注意到s o long g asE[（ZT）]orem 4表明，我们的方法在相对误差方面也能快速收敛。在第4节中，我们描述了我们的方法的一种修改，即使这种假设不成立，该方法也会在相对误差中快速收敛，如i.i.d.设置和著名的Robbins问题，统计学家和问题学家赫伯特·罗宾斯（HerbertRobbins）推广的路径依赖最优停止理论中的一个基本开放问题（也是唯一尚未解决的所谓秘书问题的原始变量），他在1990年的实时搜索与选择国际会议上（Bruss（2005））发表了一句著名的话（在他去世之前），他“希望看到这个问题在我去世之前得到解决”。通过下面的下界结果，我们现在证明了定理2的线性收敛性一般不能得到改进。定理5。对于任意n≥ 2，存在一个T=2，P（Zt）的最优停止问题∈ [0，1]）=t为1∈ [1，2]，尚未选择- 埃克≥4N所有k≤ n、 当然，定理5是最坏的情况，对于许多问题，我们的方法可能比定理2更快地收敛。在第4节中，我们描述了一些额外示例的收敛特性，并将深入理解我们方法的实例特定收敛速度作为未来研究的一个有趣方向。2.5. 算法结果我们现在在最小化和最大化框架中描述定理1和2的总体算法含义，并在i.2.5.1的适当范围内模拟HI的自然方法。

算法分析的形式化计算和抽样模型。获取样本和数据驱动算法：在我们的分析中，我们将有兴趣确切了解需要什么样的“获取随机性”，因为我们希望证明我们的方法是“数据驱动的”。在期权定价设置中，这种特征是非常可取的，因为人们不太可能获得例如联合密度函数（Broadie et al.（2000））。为此，我们有时会仔细说明，给定的算法只能通过访问某个“基本模拟”来访问随机性，该模拟只能生成基础过程Y的单个样本路径（可能以部分历史为条件）。我们现在正式定义了e（随机算法）B中的一个简化，我们将非正式地称之为“基础模拟器”，Chen和Goldberg：《战胜期权定价和最优止损中的维度诅咒》，这将为我们的算法提供获取Y.Fort信息的主要手段∈ [1，T]和γ∈ t、 设Y（γ）表示以事件{Y[t]=γ}为条件分布为Y的随机矩阵。我们假设存在一个具有以下性质的随机算法B。B作为输入t∈ [1，T]和γ∈ t、 并输出一个独立的Y（γ）样本，独立于之前B生成的任何样本。同样，我们让B（0，) 返回Y的独立样本（无条件）。我们假设B需要C个计算时间单位来终止并生成任何这样的样本。这里C当然可能取决于T、D和其他参数a，尽管我们假设C不取决于特定的输入T，γ到B。

我们注意到，对于许多过程来说，即使生成模拟样本路径也可能是相当具有挑战性的，这里有许多有趣的探索，围绕着如何将OUR框架与生成单个样本路径非常昂贵和/或只能生成近似样本路径的设置相结合。这些问题通常超出了本文的范围，并为未来的研究留下了方向，感兴趣的读者可以参考Glasserman（2013）、Dieker（2004）、an d Blanchet et al.（2017）等其他相关背景；以及Warin（2018）和Hutzenthaler等人（2018）在高维环境下模拟PD Es的相关最新进展。计算模型和运行时间分析：接下来，我们必须形式化一个计算模型，以分析使用B的算法的运行时间。为简单起见，我们主张在一个时间单位内可以对任意两个数字进行加法、减法、乘法、除法、最大值和最小值，不考虑这些数字的值。我们将忽略所有与读取、写入和在内存中存储数字以及将数字输入函数相关的计算成本。我们也假设t对于任何t∈ [1，T]和γ∈ t、 我们可以根据计算时间计算gt（γ），其中G可能再次依赖于t，D和其他参数，尽管我们再次假设G不依赖于t，γ的特定选择。我们进一步假设C，G≥ 1、关于基于样本的算法复杂性的其他相关形式化，我们请感兴趣的读者参考Halman（2015b）、Swamy和Shmoys（2012）、Levi et al.（2007）、C ooper et al.（2012）以及关于机器学习相关概念的大量文献（例如Servedio（1999）、Kakade（2003）、Daskalakis et al.（2018）、Sidford et al.（2018））。

我们注意到，对我们的结果如何融入计算复杂性理论的更广泛框架的更正式的分析将超出本文的范围，并将此类研究作为未来工作的一个有趣方向。2.5.2. 主要算法结果。现在，我们统计了我们的主要算法结果，这些结果允许在所需精度（就参数而言）与gene ral高维路径相关设置中所需的运行时间和样本之间进行权衡，类似于近似算法理论中的多项式时间近似方案（PTAS）的概念（Shmoys和Williamson（2011），Swamy和Shmoys（2012），Halman（2015b））。keyChen和Goldberg：战胜期权定价和最优止损中的维数诅咒鉴于我们的结果，即使在存在全路径依赖和高维数的情况下，对于任何给定的误差参数，都可以在T，仅通过模拟单个样本路径的成本来决定维度（以及更普遍的状态空间），其中只需要一个多项式数量的此类模拟。此外，我们的方法是数据驱动的，基本上不需要任何超出生成样本能力的分布知识。据我们所知，这些结果是此类结果中的第一个，并且证明了即使在路径依赖和高维环境中也可能出现这样的结果。我们也不知道我们的分析，边界是最坏的情况，在几乎所有的情况下，我们都选择了在紧度边界上进行简单的分析。Fu rthermore，所有相关项实际上都必须通过模拟进行估计，其误差通过我们的展开式传播，这一事实意味着我们实现的运行时间（尽管对于任何固定的，T中的多项式）将比定理2所暗示的速度慢得多。

我们将提供更严密的分析和设计更快的算法作为未来研究的有趣方向，特别是当潜在问题表现出额外的结构时。如前所述，为了将定理1和定理2转化为算法，我们采用自然的方法，模拟i的适当范围。如定理2-4所建议的，在不同质量（如矩和上界）的相对缩放的不同假设下，对于需要多少相关系列的项才能达到给定的近似水平，人们可能能够证明不同的结果。此外，近似的精确概念同样重要，例如，一个人是在寻求绝对误差还是相对误差，以及一个人是满足于相对于上界的误差，还是e[（ZT）]。然后，这些选择决定了我们的方法所需的计算和样本复杂性。我们注意到，有大量不同的设置可以考虑沿着这些路线，调整我们的方法，并在许多不同的假设集下得出略有不同的结果。我们没有试图在这里对相关的可执行性景观进行全面分类，将这种努力作为未来研究的一个有趣方向。相反，我们关注两种说明性设置。首先，在具有绝对误差度量的最小化框架中，我们考虑Zt的设置∈ [0，1]对于所有t∈ [1，T]，即归一化情况。从某种意义上说，这种设置是我们的方法最基本的，并且说明了大多数关键思想。我们注意到，通过应用一个简单的变换，我们对这种规范化情况的所有结果（也就是w.r.t.实施有效的停止策略）基本上保持不变到最大化设置，尽管为了清楚起见，我们没有正式声明和证明这种变换。

第二，在相对误差度量的最大化框架中，我们考虑了一个更为一般的设置：在这个设置中，我们假设的只是方差的平方系数（即方差与squ的比值为平均值）f chen和Goldberg：在期权定价和最优停止Maxt中击败维数诅咒∈[1，T]zt是一个很好的边界，可以看作一个常数。对于第二个结果，我们注意到，我们不要求过程有界或其他任何东西，并且注意到，在许多Interest设置中，对相关变化系数的这种适度要求应该保持不变。我们注意到，我们的a lg算法是递归构造的，构建了一种有效模拟Zk+1的方法，而不是一种有效模拟Zk的方法，而且，此类嵌套方案（尽管性质不同）之前已在文献中考虑过（Kolodko et al.（20 06））。叉≥ 1和，δ∈ （0，1），让我们定义fk（，δ）= 102（k-1)× -2（k-1） ×（T+2）k-1×1+对数（δ）+对数（）+对数（T）k-1、在假设Z归一化为位于[0,1]的情况下，我们在最小化io n框架f或近似选择加入绝对误差中陈述了我们的结果。定理6。假设w.p.1 Zt∈ [0，1]对于所有t∈ [1，T]。那么对于所有k≥ 1，存在一个随机算法^bk，它以任意，δ作为输入∈ （0，1），并实现以下功能。在总计算时间内，最多（C+G+1）fk+1（，δ），并且仅访问mostfk+1（，δ）处的随机性调用基本模拟器B，返回满足P|十、- 香港|≤ ≥1.- δ.结合定理6、orem 2和简单的并集界，我们将得到以下结果。推论2。假设w.p.1 Zt∈ [0，1]对于所有t∈ [1，T]。然后存在一个随机算法a，它以任意，δ作为输入∈ （0，1），并实现以下功能。

总计算时间最多（C+G+1）exp（200-2） T6-1.1+对数（δ）6-1，并且只能在mostexp（200）访问随机性-2） T6-1.1+对数（δ）6-1调用基本模拟B，返回满足P的随机数X|十、- 选项|≤ ≥ 1.- δ.接下来，我们在最大化框架中陈述了我们的结果，以近似[选择相对误差]和假设最大方差的平方系数∈[1，T]zt可以创建为常数。我们注意到，正如在许多其他问题中一样，在极小化和极大化框架之间的近似困难中，re似乎是一个不对称的问题，并且推导出在极小化框架中可以推导出有效相对误差近似算法的同等一般条件仍然是未来研究的一个有趣方向。为了便于说明我们的结果、算法和分析，在本案例中，我们假设我们的算法的输入不仅是和δ，而且是最大值的前两个矩∈[1，T]Zt。Chen和Goldberg：战胜期权定价和最优止损中的维度诅咒尽管这些数量当然可以从数据中估计，例如使用基本模拟器，将此估计纳入我们的算法中，引入了与我们的主要目标相关的细节和复杂性，因此，我们简单地假设这些量在应用我们的算法之前已经估计过了。同样，为了说明清楚，我们假设对这两个时刻有确切的了解，即在许多实际情况下，人们可能会有相关的（概率）估计，我们注意到，根据这些考虑因素，可以很容易地修改算法，以略微不同的保证和增加的复杂性为代价，无法描述我们的方法和结果。定理7。