基于伪回归的最优停车动态规划

模拟m=1。。。，时间j时的M- 1轨迹（3.6）Xj-1，U（m）r，r=j。。。，J、 并修改（3.2）toY（J）m：=fτ（Xj-1，U（m）τ），其中（3.7）τ≡ minnr：r≥ j、 fr（Xj-1，U（m）r）≥ cr公司Xj公司-1，U（m）ro、 然后计算（3.3）并设置cj-1（z）根据（3.4）。算法1的相应修改显而易见。乍一看，这一过程的成本要高得多。然而，如果链X是自治的，我们可以假设它是w.l.o.g.事实上，我们模拟Firstx0，U（m）r，r=0。。。，J、 8 CHRISTIAN BAYER，MARTIN REDMANN，JOHN Schoenmakers数据：u，M，ψ，ψK，G，f，福建。结果：值函数vjand连续值cj，j=0，J、 1begin2vJ←- vJ=fJ3cJ←- cJ=04表示m←- 1至M DO5生成U（M）~ u6end7M←-ψk（U（m））m=1，。。。，Mk=1，。。。，K∈ RM×K8J←- J至1 DO9M←- 1至M DO10生成Xj-1，U（m）j11//这些r.v.被理解为独立的条件U（m）12end13Y（j）←-vj公司Xj公司-1，U（m）jm=1，。。。，M∈ RM14β（j）←-MG公司-1M>Y（j）15cj-1(·) ←-KXk=1β（j）kψk（·）16vj-1(·) ←- 最大值（fj-1（·），cj-1（·））17END18END算法1：百慕大期权TV的伪回归变量，然后采用（3.6）Xj-1，U（m）r=X0，U（m）r-j+1，r=j。。。，J、 （3.8）因此，对于自治的情况，一组完整的轨迹，就像在标准的LSalgorithm中一样，也适用于该算法。4、伪回归的精度分析在下一节中，我们分析了一种计算e[Y | X]的替代且可能更有效的伪回归程序，即（2.9），因为我们可以从给定X的条件分布中采样Y（尽管我们通常不清楚e[Y | X]）。4.1. 总体框架。假设在（2.9）中，可以从给定X的条件分布中采样Y，比如说ν（dy | X）。一个典型的例子是第3节中的设置，其中x=X0，xjand Y=gX0、xj+1= gXj、X0、xjj+1,对于某些任意x。

让我们考虑一个随机变量U，其值在某个域D中 Rd，根据集中在D上的概率度量u（dz）分布。然后，我们生成i.i.D.拷贝U（m），m=1。。。，U的M和forDYN的样本。OPT编程。通过伪回归9停止，每m=1。。。，M、 独立于ν的Y（M）dy | U（m）. 然后确定向量∈RMasY：=hY（1）。。。，Y（M）i>。现在对于线性独立系统（ψk：k=1，2，…），zψk（z）u（dz）<∞,考虑M×K矩阵xmmk：=ψKU（米）.假设我们明确知道由标量乘积gkl定义的矩阵G：=hψk，ψli（参见（3.1）），我们现在计算伪回归系数（4.1）β=MG-1M>Y，考虑伪回归近似（4.2）u（z）=KXk=1βkψk（z）≈ E[Y | U=z]，z∈ D、 显然，与标准回归的不同之处在于，从（2.13）来看，随机矩阵xmn>Nin（2.12）被G所取代。一般G-1可以在蒙特卡罗模拟之外以任意精度进行预计算，或明确知道系统的适当选择（ψk：k=1，2，…）和测量u。因此，（4.1）的计算只涉及KM初等运算，不需要随机矩阵求逆。此外，自然地，我们可以假设w.l.o.g.系统（ψk：k=1，2，…）是一个关于L（D，u）的正交系统，然后（4.1）简化为β=MN>Y.4.2。回归精度分析。关于伪回归方法的收敛性，我们基本上可以参考[2，3]，其中伪回归是在随机偏微分方程全局解的背景下应用的。然而，为了方便读者，让我们在这里以简明的形式回顾一下分析，与当前的术语和一个较少涉及的设置保持一致。定理4.1。

（精度伪回归）假设在（2.9）|u（z）|≤ D和Var[Y | X=z]<σ，对于所有z∈ D、 0<λmin≤ λ最小值GK公司≤ λmaxGK公司≤ λmax，对于所有K=1，2。。。，式中λminGK公司, 和λmaxGK公司, 表示正对称矩阵G的最小、最大特征值。然后它保持EZD | u（z）-u（z）|u（dz）（4.3）≤λmaxλminσ+D公里+infw∈ span{ψ，…，ψK}ZD | w（z）-u（z）|u（dz）。10 CHRISTIAN BAYER、MARTIN REDMANN、JOHN Schoenmakers定理4.1的证明见附录A.1。将定理4.1与标准回归估计（2.11）的相应定理进行比较很有趣：定理4.2。（精度标准回归）假设，| u（x）|≤ D和Var[Y | X=X]<σ，对于所有X∈ Rd，然后foreuD（x）=eu（x）if | eu（x）|≤ 如果eu（x）>D，则为DD-D如果eu（x）<-当某个普适常数c>0时，它认为Ez | euD（x）- u（x）|ux（dx）（4.4）≤ c最大值σ、 D（1+ln M）KM+8 infw∈ span{ψ，…，ψK}ZD | w（x）- u（x）|ux（dx），其中ux表示x在（2.9）中的分布。定理4.2的证明比定理4.1的证明复杂得多，并且在很大程度上依赖于经验过程理论中的统一大数定律。有关详细信息，请参见[7]。4.3. 伪LS和伪TV算法的收敛性。在本节中，我们研究了伪Longsta off–Schwartz和伪Tsitsiklis–van Roy算法的收敛性。让我们首先考虑伪LSmethod，它实际上是一种更复杂的方法。在相互作用粒子系统的背景下，我们遵循[11]和[4]中关于最佳停止的类似路线。更具体地说，我们考虑基于（3.6）的算法，其中对于每个练习日期，单独模拟样本（3.6），并考虑信息集gj：=σXj；M

，XJ-1.M带Xj；M：=Xj，U（m），mr，r=j。。。，J、 m=1。。。，M.让我们定义一个通用虚拟轨迹（Xl）l=0，。。。，j对应于独立于Gj的（精确）解，（4.5）ecj（x）：=EGj+1fτj+1Xτj+1Xj=x,式中，τJ=J，τJ：=J 1fj（Xj）≥cj（Xj）+ τj+1fj（Xj）<cj（Xj）.值得注意的是，在（4.5）中，ecj（·）是一个Gj+1-可测的随机函数，而估计cj（·）是一个Gj-可测的随机函数，因为cjalsode的构造依赖于Xj；M、 参见与（3.7）相关的（3.4）。在从j=j向后到j=1之后，我们得到了一系列近似连续函数cj（·），以及一系列相应的条件期望ecj（·）。伪LS方法的收敛性分析基于以下引理（参见文献[4]中的引理5]）。DYN公司。OPT编程。通过伪回归11引理4.3停止。对于条件期望（4.5），我们有，（4.6）kecj- cjkLp（u）≤J-1Xl=j+1kcl- clkLp（uj，l）和p≥ 1，uj，Lb为Xj，Ul，1的分布≤ j≤ l≤ J、 U型~ u和cj是真正的连续函数。该证明与文献[4]中类似引理5的证明几乎相同。为方便读者阅读，附录A.2中给出了相关信息。备注4.4。注意，不等式（4.6）涉及Gj+1-可测对象。将（4.6）与[11]中类似（尽管不同）的不等式进行比较也很有趣。现在，我们陈述与伪Longstaff–Schwartz算法相关的收敛定理。附录A.4中给出了证明。定理4.5。让我们假设定理4.1的条件已经满足。特别是，我们假设现金流fjare一致有界，即0≤ fj公司≤ D对于j=0，J、 有些D>0。因此，从那时起≤ cj公司≤D、 此外，我们可以假设0≤cj公司≤ D、 对于j=0，J

让我们进一步假设，更一般地说，采样密度ujt可能取决于算法1的Longstaff-Schwartz版本中的j，并且在j=0时满足uj>0，J- 1，andR∞:= 最大值0≤j<l<Jsupx∈Rduj，l（x）ul（x）<∞,其中Xj，Ujl~ uj，l.对于一般度量ν，normk·kL（νP） ：=Ehk·kL（ν）i，是由于对“综合”概率测度P的无条件期望而定义的。然后，自然数K、M和j=0，J- 1，kcj- cjkL（ujP）≤ ηεj，M，K1+R1/2∞(η + 1)J-j-1，式中εj，M，K：=rKM+maxj≤l<Jinfw∈ span{ψ，…，ψK}kcl- wkL（uj），（4.7）Uj~ uj，0≤ j<j，η>0是一个常数，不依赖于K、M、R和密度uj的选择。现在让我们考虑伪TV方法的收敛性。对于genericexact（虚拟）解决方案（Xl）l=0，。。。，根据Gj，我们现在将（4.5）重新定义为（4.8）ecj（x）：=EGj+1[vj+1（Xj+1）| Xj=x]，其中，在（4.8）中，ecj（·）是一个Gj+1可测量的随机函数，而估计cj（·）是一个Gj可测量的随机函数，现在通过（3.4）和（3.5）构建。伪TV方法的收敛性基于下一个引理。12克里斯蒂安·拜耳、马丁·雷德曼、约翰·舍恩马克斯·勒玛4.6。对于条件期望（4.5），我们有，（4.9）kecj- cjkLp（u）≤ kcj+1- cj+1kLp（uj，j+1），带p≥ 1，uj，j+1是Xj，Uj+1，1的分布≤ j<j，U~ u和cj是真正的连续函数。这个证明比引理4.3的证明要简单一些，见附录A.3。对于伪Tsitiklis–van Roy算法，我们现在有以下收敛定理，如附录A.5所示。定理4.7。让我们考虑与定理4.5中相同的假设和符号，但现在uj，j=1。。。，J、 是算法1的Tsitiklis–van Roy版本中的采样密度（一般取决于J）。

如果所有uj>0且满足，（4.10）R+：=最大值0≤j<j-1supx∈Rduj，j+1（x）uj+1（x）<∞,然后对于自然数K、M和j=0，J- 1，kcj- cjkL（ujP）≤ ηεj，M，KR1/2+（η+1）J-j- 1R1/2+（η+1）- 1，（4.11）式中εj，M，K：=rKM+maxj≤l<Jinfw∈ span{ψ，…，ψK}kcl- wkL（uj），Uj~ uj，0≤ j<j，η>0是一个常数，不取决于K、M、R和密度的选择uj.4.4。在选择度量值ul时。在上述结果的公式中，假设基础过程X的状态空间为Rd，但自然，如果X穿过Rd的某个开放子集，例如Rd>0，则结果也适用。我们取ul~ X0，Ul。那么我们有uj，l~ Xj、Ujl~ X0，Ul~ ul和thusR∞= 分别在定理4.5和定理4.7中，R+=1。对于准确度估计，我们得到，（4.12）kc- ckL（uP）≤ ηε0，M，K（η+2）J-1和（4.13）kc- ckL（uP）≤ ε0，M，K（η+1）J- 1.,分别地这一假设的抽样措施选择表明，原则上LS和TV的准确度界限（4.12）和（4.13）分别是可以达到的。实际上，这触及了Glasserman Yu（2002）中的基本点，其中一个建议是在每个步骤中搜索与基础过程分布正交的基函数。然而，在实践中，除了潜在的（多维）Black-Scholes模型之外，这几乎是不可能的。事实上，本文建议超越Glasserman Yu（2002）：基于REMS 4.5和4.7，我们建议寻找“合适的”密度u。。。，uJ-1一方面，密度u在某种意义上接近密度X0，Ul，对于l=0。。。，J、 使R∞< ∞, 另一方面，他们需要托丁。OPT编程。

通过伪回归13be停止，使得对于每个练习日期l，基函数ψlis的K维系统可用，使得hψ，ψi对于所有ψ，ψ都是已知的∈ ψl，或更好的hψ，ψi=Δψψ。让我们选择ulsuch thatsupx∈Rdul-1，l（x）ul（x）=supx∈RdRul-1（xl）pl-1，l（xl-1，x）dxl-1ul（x）≤ Rl，l=0。。。，J- 1，其中我们用pl，l（xl，xl）表示0的密度X0，xll≤ l<l<J。我们有，uJ，l（x）=ZdxjuJ（xj）pj，l（xj，xl）=Zdxj+1pj+1，l（xj+1，xl）ZdxjuJ（xj）pj，J+1（xj，xj+1）≤ Rj+1Zdxj+1uj+1（xj+1）pj+1，l（xj+1，xl）≤ ... ≤ Rj+1Rj+2··Rlul（x），因此我们可以∞:= 最大值0≤j≤l<JRj+1Rj+2···Rl=RR··RJ-1< ∞,和R+<∞ 分别在定理4.5和定理4.7中。示例4.8。设X由状态空间Rd+的It^o微分给出，letql，l（yl，yl）是（对数价格）过程的密度Ll，l=0。。。，J、 定义名称：=ln【Xl】和ln【x】：=ln（xi）i=1，。。。，D对于x∈ Rd+。假设ql-1，l（yl，yl）是次高斯分布，具有一些（可能复杂的）相关结构。典型情况是（4.14）ql-1，l（yl-1，yl）≤Rlq（2π）ddet（∑（l））exp-（yl）-1.- yl）T∑（l）-1（yl-1.- yl）=: Rlbql-1，l（yl-1，yl），对于简单协方差矩阵∑（l），例如对角矩阵。设ujbe采样随机变量Uj的密度∈ Rd+，由uj给出：=exp[Lj]，exp[y]：=经验（彝语）i=1，。。。，D用于y∈ Rd，其中Ljis从密度νj中采样。对于Rd上的任意非负Borel函数f+一个hasZf（x）uj（x）dx=Zf（exp[y]）、νj（y）dy=Zf（x）Дj（ln[x]）、dYk=1xkdx，其中（4.15）uj（x）=Дj（ln[x]）dYk=1xk，14 CHRISTIAN BAYER、MARTIN REDMANN、JOHN Schoenmakers和类似的一个具有（4.16）pl-1，l（xl-1，x）=ql-1，l（ln[xl-1] ，ln[x]）dYk=1xk，对于x的一步跃迁密度。

现在让我们取ν（y）：=bq0,1（y，y），并粗略地取，νl（yl）=Zdyl-1Дl-1（yl-1） bql-1，l（yl-1，yl）。然后我们得到（4.14）、（4.15）和（4.16）Zul-1（xl-1） pl公司-1，l（xl-1，x）dxl-1=ZДl-1（ln[xl-1] ）dYk=1xkl-1dxl-1··ql-1，l（ln[xl-1] ，ln[x]）dYr=1xr=ZДl-1（yl-1） dyl公司-1ql-1，l（yl-1，ln[x]）dYr=1xr≤ RlДl（ln[x]）dYr=1xr=Rlul（x）。5、计算成本我们现在将在Tsitiklis–van Roy算法和Longsta ff–Schwartz算法的背景下，讨论针对不同用例的两种不同方法的优缺点。当然，主要的问题是计算工作与精度之间的关系。比较定理4.1和4.2，我们发现误差是基函数K个数的函数，基函数ψ的选择，ψKand两种方法的样本数M大致相等。备注5.1。我们忽略了不同的常数以及附加的ln M Term定理4.2。在实践中，不同的常数当然会对运行时产生剧烈的影响，这就是为什么第6节中的数值实验至关重要的原因。一个更微妙的差异与计算误差的度量的选择有关。我们还注意到，我们只关注计算函数cj和vj的成本，因为计算的其他方面的成本可以忽略不计，与所选的回归方法无关。让我们回顾一下我们的一般设置：我们得到一个现金流过程Zj=fj（Xj），j=0，J、 它基于Rd值马尔可夫过程Xj，J=0，J、 我们想计算相应的百慕大期权价格。在下面，我们需要对模拟做出某些假设。假设5.2。我们可以精确地模拟马尔可夫过程X。更精确地说，给定一个样本Xj，我们可以模拟一个样本Xj+1，j=0。

J-1，正确地将成本标准化为1。假设5.2似乎将我们限制在诸如Black-Scholes或Achelier等简单模型上，对于这些模型，很容易进行精确模拟，但请注意，任何离散化错误都会以相同的方式影响两种回归算法，无论是在精度方面还是在计算成本方面。因此，我们认为假设5.2是正确的。OPT编程。通过伪回归15备注5.3（成本模型）停止。在计算成本的讨论中，所有估算都应理解为计算功能评估的数量。更准确地说，以下每项操作都会产生一个单位成本：o在Xj上生成一个Xj样品+1条件；o求一个基函数ψkat一个点x；o基本浮点数计算，如两个浮点数之间的乘积。当然，这些操作在实践中会产生非常不同的计算成本。然而，请注意，很难以任何方式实际限制真实的计算时间。这些可能在很大程度上取决于硬件特性（例如缓存未命中），尤其是实现细节。5.1. Tsitiklis–van Roy算法。通过假设5.2，我们已经可以描述标准回归算法的计算工作。命题5.4（标准回归的计算成本）。标准回归满意度的计算成本=OJ（M K+K）.证据当然，这个结果是众所周知的。计算成本的主导项是计算随机矩阵N>N以及通过LU或Cholesky分解计算系数β。对于每个练习时间j=0，…，必须重新计算两个操作，J-1.对于伪回归方法，我们将在假设5.5下操作。基函数ψ。

，ψKare的选择使得矩阵g显式给出。通过选择基函数为正交多项式w.r.t.u，最容易满足该假设。然后我们得到命题5.6（伪回归的计算成本）。假设5.2和5.5下伪回归的计算成本满足伪=OJM K+JK+K.此外，如果基函数是正交的w.r.t.u，则成本insteadsatis fiescpeudo=O（JMK）。证据首先，我们需要计算矩阵G的LU分解，其代价与J的K无关。我们还需要模拟随机变量su，并以O（MK）为代价建立矩阵M。在算法的每次迭代中，我们需要模拟向量Y，并按成本比例toMK乘以M>Y。最后，组合线性系统Gβ=MM>Y的解与K成正比。在正交情况下，我们得到G=G-1=IdK，设置和乘以M>Y的成本占主导地位。实际上，在假设5.7下，甚至可以更好地节约成本。马尔可夫过程X在时间上是同质的，即Xj+1given xjd的条件分布不依赖于j.16 CHRISTIAN BAYER、MARTIN REDMANN、JOHN Schoenmakers这一条件通常在金融模型中得到满足，它对伪回归算法（但不适用于标准回归）有重大影响。事实上，由于条件分布不依赖于j，并且我们总是从相同的分布u（而不是Xj的分布）中对起点（步骤j）进行采样，因此我们可以简单地使用相同的样本为（4.1）中的每个时间步设置Y。形式上，与命题5.6相比，渐近成本没有改变，但在实践中，我们确实观察到了递减常数的主要影响。备注5.8。