我们相信较弱的诺曼假设（AX）中的估计可能适用于（AK）之外的一类基函数。后来的计算实例确实表明，多层次的好处超过了假设，在这种假设下，复杂性增益随后得到了证明。比较定理3.7和定理3.9的误差范围，可以看出范数|·|∞在前者中，定理已被后者中较弱范数E（·）中的等价项所取代。根据定理3.9，k级多级模式的全局误差（23）的上界表示为时间步数、时间增量、基函数数、基函数偏差、模拟次数和前一个k级的全局误差（23）-1（即术语“e（Z，k-1，j）。在本节剩下的部分中，我们将使用顺序符号O（·）：如果存在常数C，我们将g（y）写在O（y）中，而不依赖于k级，这样lim supy↓0g（y）/y≤ C.我们设置了多级算法的数值参数——基函数和模拟次数——以便当ε>0时，全局误差E（k）达到精度水平O（ε）。与备注3.8相比，我们使用此校准来计算复杂性，并将多级算法与LSMDP方案进行更精确的比较。备注3.10。我们下面的理论复杂性分析应用了定理3.9中的误差估计，因此要求其假设成立；特别是，基础是满足（AK）。此外，要求基的近似误差T（Y，k）1，i和T（Z，k）1，i为基维数k（k）Y的阶数o（ε），iresp。K（K）Z，国际会计准则在下文的选择基础中规定。结合起来，这些假设似乎有局限性，但稍后的计算示例将显示超出这些假设的经验多层次效益。

另一方面，有一类例子满足了所需的假设，我们在本评论的其余部分展示了这一类。假设解是x7→ （y（k）i（x），z（k）i（x））是周期性的，即存在λ：=（λ，…，λd）∈ Rd+suchJuly 320018年14时28分19（y（k）i（x），z（k）i（x））=（y（k）i（x+nλ），z（k）i（x+nλ））∈ Z和x∈ Rd.作为一个例子，X（k）i=Wt（k）i和Φ（X）=sin（β·X），其中λi=2π/βi。更一般地，我们可以考虑任何周期终端条件Φ，并且X（k）是随机微分方程解的边缘，其系数函数具有与Φ相同的周期性。每一个t∈ （0，T]和κ≤ k、 我们假设边缘X（κ）J在域D中有一个密度，其下限为c（t）>0（独立于κ）：di=1[-λi，λi]对于所有j，使得t（κ）j>t。如果X（k）i是一个随机微分方程的解的边缘，则该性质满足，该随机微分方程的生成元是一致椭圆的；因此，边缘密度从下方以高斯密度为界[30]。设{Bk，i，1，…，Bk，i，K（K）i}为D的超立方体划分，并定义基函数pη，K，i，j（x）（j=1，…，K（K）i，η=Y，Z）作为集Ak，i，j:=n上的指示函数1Ak，i，j（x）∈Z{x+nλ：x∈ Bi，j}。然后，P（Ak，i，j）≥P（Bk，i，j）≥ c（t）u（D）/K（K）i，其中u是勒贝格度量；因此，条件（AK）满足δ=1/（c（t）u（D））。因此，只要考虑区间[t，t]上的整体误差，δ就可以被视为k级和精度级的常数。评论

作为备注3.10中概述的周期性过程的替代情况，我们也可以考虑一个正向过程X，它是一个在某个紧凑域内的扩散，例如确保其密度远离零，因此我们可以像上面的周期性过程一样进行论证。然而，为了使ansatz严格，需要像（Aπ）（ii）这样的L正则性性质来保持反射差X。我们还不知道这样的结果是否可用。定理3.9的误差范围（28–29）表明，实现全局误差O（ε）的有效标准是确保（28–29）中的和中的每个项都以O（ε）为界，我们使用该标准制定校准程序。此外，假设Mark3.10的假设成立，即基函数满足（AK）和周期性。我选择的依据。我们首先选择一个满足（AK）的基，使T（Y，k）1，i和T（Z，k）1，i由O（ε）上界。让k（k）Y，i=k（k）Z，i和集合{Bk，i，j:j=1，…，k（k）·，i}是集合D上的统一超循环。由于（aπ）（iv），（AX），它对T（Y，k）1，i，T（Z，k）1的有界性是足够的，以确保最大值为0≤我≤2k-1minφ∈K（K）Y，iE[|u（t（K）i，X（K）i）-φ（X（k）i）|]+k-1Xi=0minφ∈K（K）Z，iE[|v（t（K）i，X（K）i）-φ（X（k）i）|]≤ O（ε）。为了简单起见，我们假设θ=1。由于（AX）（iv），v（t，·）的李普希茨常数等于O（（t）- （t）-1/2），因此必须在时间t（k）等于qt时设置超立方体直径- t（k）iO(√ε） ，其中基的维数为K（K）Z，i=（T- t（k）i）-d/2O（ε）-d/2）。由于u（t（k）i，·）的Lipschitz常数是O（1），因此t（Y，k）1，i≤ O（ε）具有相同的基。我有很多模拟。

基函数的选择决定了基函数的个数K（K）·i=K（K）·i（ε）。我们选择Mk=maxiO（ε-1kK（k）Z，i（ε））=O（kε-1.-d/2maxi（T- t（k）i）-d/2）≤O（k2kd/2ε-1.-d/2）确保（28-29）中的所有条款——除了那些依赖于“E（Z，k）”的条款-1，·）-并且在命题3.5中的修正项中，以O（ε）为界；注意，我们不需要担心术语1/（T）- t（k）i）1-θ、 因为sumPk-1i=0（k） 我不能- t（k）i）1-θ在k中均匀有界。2018年7月3日14:28，20I迭代至水平j<k。在上述计算中，只需设置参数，使k-1.-1Xl=α（i）+1′E（Z，k）- 1.1）（k）-1） j≤ O(（k） i）对于所有i.这通过设置全局误差E（k）的精度来满足-1） 在k层-1小于或等于O（最小值（k） （一）≤ O（2）-k） 代替O（ε）。随后，在每个级别上≤ K- 1此后，我们将全局误差E（j）的精度设置为小于或等于O（mini）（j+1）i）≤ O（2）-j） 并重复上述程序的前两个步骤。为了简单起见，我们为每个级别选择相同的基础，尽管这可能不是最优的。时间t（j）的基维数为K（j，i，ε）：=（t- t（j）i）-d/2O（ε）-d/2）和水平j<k的模拟次数为Mj=maxiO（j2jd/2K（j，2j-1，ε））=O（j2j+jd/2ε-d/2）。我喜欢复杂性分析。We fixε=O（2-k） ，因为这通常是（yk，zk）和连续时间解之间的离散误差（见（Aπ）（iv））。对计算成本有两个贡献：马尔可夫链X（k）的模拟成本和布朗增量W（k）和回归的成本。在算法的第j级上，计算模拟的成本为O（2jMj），因此整体模拟成本pkj=0O（2jMj）。

为了计算回归的成本，首先必须注意，指标回归有一个封闭式公式（见[26]中的分割估计）：对于响应（ψm）1≤M≤m对应于观测值（φm）1≤M≤M、 用H表示的指示函数的精度由αH=PMm=1ψmH（φM）PMm=1H（φM）给出；因此，每个时间点的回归成本与将模拟排序到指标中的成本成正比，这与维度d乘以模拟次数成正比。这意味着l级回归的成本也等于O（2lMl）。因此，回想一下ε=O（2-k） ，算法的总成本为kxj=0O（2jMj）≤ O（k）kXj=0O（2j（1+d））=O（ln（ε）-1+ 1)ε-2.-d） 。为了进行比较，我们用（27）代替（28-29）校准了备注3.8中描述的LSMDP算法的基函数和模拟次数。我们选择相同的基本函数，Mk=O（ε-1kK（k，2k- 1, ε)). 然后，设置ε=O（2-k） ，总体复杂度isk×Mk=O（ε-3.-d） 。我们观察到，与多级方案的复杂性相比，ln（ε）中的一个因子-1+1）已被系数ε取代-1，它要大得多。这意味着，与MDP相比，多级方案可能有效率增益因子ε（忽略对数项）。在我们的设置中，等于时间步数，这是实质性的。3.4定理3.7和3.9的证明我们在下面的命题3.11中陈述了OLS的基本性质（定义3.1）。这一命题事实上与[24，命题4.12]相同，我们建议对证明感兴趣的读者参考2018年7月3日14:28 21的论文。

我们知道这个命题的第（三）部分和第（四）部分具有高度的概括性，因此我们提供了一些明确的σ-代数和函数，以便于读者在陈述命题后的直觉。提案3.11。使用定义3.1的符号，假设K是有限维的，由函数{p（.），pK（.）}。我们走吧？根据（18）（和（19））求解OLS（S，K，ν）（和OLS（S，K，νM））。满足以下特性：（i）线性：映射S 7→ s是线性的。（ii）收缩性能：kS？kL（B（Rl），u）≤ kSkL（B（Rl），u），其中u=ν（分别为u=νM）。（iii）条件期望解：在离散概率测度νM的情况下，另外假设子σ-代数Q~F是这样的：pj（X（1）），pj（X（M））对于每个j，Q是可测量的吗∈ {1，…，K}。设SQ（·）为任意F B（Rl）-可测量的、Rl值函数，使得每m的SQ（X（m））：=E[S（X（m））|Q]∈ {1，…，M}P-几乎可以肯定。然后，E[S？|Q]（ω，x）解OLSSQ，K，νM.（iv）有界条件方差：在离散概率测度νM的情况下，假设s（ω，x）是G B（Rl）-可测量，例如G~F独立于σ（X（1:M）），存在一个钻孔可测量函数h:Rl→ E、 对于一些欧几里德空间E，随机变量{pj（X（m））：m=1，…，m，j=1，…，K}是H:=σ（H（X（m））：m=1，M）-可测量，且存在一个有限常数σ≥ 统一限定条件方差E的0|S（X（m））-| E（S（X（m））|G∨ H） | | G∨ H≤ σP-a.s.和所有m∈ {1，…，M}。然后呢？(·) -~E[S.（·）|G∨ H] kL（B（Rl），νM）G∨ 你好≤ σK/M.命题3.11的直觉。上面的观测X（m）和响应S将分别是X（k，m）和（k）i（X，w），而线性空间k将是k（k）i，度量值ν（分别是νm）将是νk（分别是ν（k）m）。

对于第（三）部分，我们将Q作为σ-代数F（M）k，定义为3.4；然后，函数q[S（X（m））]（·）将等于y（k）i（分别为z（k）i），见下文。对于第（iv）部分，wetake E=Rd和Borel函数h:Rl→ E是h（X（m））=X（k，m）i，其中σ-代数h是σ（X（k，m）i:m=1，Mk）。我们选择F(*)K-1对于G，G从哪里来∨ H=F（M）k，i.我们现在开始证明这两个定理。回顾定义3.4中的σ-代数和第1.1节中的软截断函数Tr（·）。函数Tr（·）的Lipschitz连续性（对于所有r）意味着e[ky（k）i- y（k，M）ikk，i，M]=E[kTCy（y（k）i）-TCy（ψ（k，M）Y，i）kk，i，M]≤ E[ky（k）i- ψ（k，M）Y，ikk，i，M]（30）E[kz（k）i- z（k，M）ikk，i，M]=E[kTCz，k，i（z（k）i）-TCz，k，i（ψ（k，M）Z，i）kk，i，M]≤ E[kz（k）i- ψ（k，M）Z，ikk，i，M]（31）我们引入了“有效”函数ψ（k）Y，i:Rd→ R和ψ（k）Z，i:Rd→ （Rq）>由ψ（k）Y定义，i（·）解OLS（S（k）Y，i（x，w），k（k）Y，i，ν（k）M），ψ（k）Z，i（·）解OLS（S（k）Z，i（x，w），k（k）Z，i，ν（k）M），对于算法1（20）中给出的函数S（k）Y，i（·）和S（k）Z，i（·）；ψ（k）Y，i（·）和ψ（k）Z，i（·）的实际性质来自函数S（k）Y，i（·）和S（k）Z，i（·），它们是在2018年8月3日14:28 22y（k）（·）和Z（k）（·）时使用未知函数july 3构造的，因此无法明确计算。我们将分别使用（随机）函数E（M）k，i[ψ（k）Y，i]（·）和E（M）k，i[ψ（k）Z，i]（·）分解（30）和（31），但首先我们使用命题3。11（iii）确定E（M）k，i[ψ（k）Y，i]（·）和E（M）k，i[ψ（k）Z，i]（·）解OLS。将Q设为σ-代数F（M）k，i.p（X（k，M）i）对任何p都是Q-可测的∈ KY，k，我∪现在，因为-1） j（X（k）-1，m）j）是F（m）k，2j对于所有j>α（i）都是可测量的，应用塔性质和马尔可夫性质（AX）得到E（m）k，i[S（k）Y，i（Xm）]=E（m）k，i[Φ（X（k，m）k）]=Y（k）i（X（k，m）i），（32）E（m）k，i[S（k）Z，i（Xm]=E（m）k，i[Φ（X（k，m）k）W（k，m）i（k） i]=z（k）i（X（k，m）i）。（33）对所有人来说∈ {1, . . .

，Mk}，我们最终从中获得表达式x∈ Rd7→ E（M）k，i[ψ（k）Y，i]（x）解OLS（Y（k）i（xi），k（k）Y，i，ν（k）M,十、∈ Rd7→ E（M）k，i[ψ（k）Z，i]（·）解OLS（Z（k）i（xi），k（k）Z，i，ν（k）M.因此，在（30）和（31）的右边分别引入随机函数E（M）k，i[ψ（k）Y，i]（·）和E（M）k，i[ψ（k）Y，i]（·），并应用毕达哥拉斯定理，得出E[ky（k）i- y（k，M）ikk，i，M]≤ E[ky（k）i- E（M）k，i[ψ（k）Y，i]kk，i，M]+E[k（E（M）k，i[ψ（k）Y，i]-ψ（k，M）Y，i）kk，i，M]，（34）E[kz（k）i- z（k，M）ikk，i，M]≤ E[kz（k）i- E（M）k，i[ψ（k）Z，i]kk，i，M]+E[k（E（M）k，i[ψ（k）Z，i]-ψ（k，M）Z，i）kk，i，M]。（35）此外，E[kz（k）i-E（M）k，i[ψ（k）Z，i]kk，i，M]≤ T（k）Z，i和E[ky（k）i-E（M）k，i[ψ（k）Y，i]kk，i，M]≤ T（k）Y，i，并将其注入不等式（34）和（35）yieldsE[ky（k）i- y（k，M）ikk，i，M]≤ T（k）Y，i+E[kE（M）k，i[ψ（k）Y，i]-ψ（k，M）Y，ikk，i，M]，（36）E[kz（k）i- z（k，M）ikk，i，M]≤ T（k）Z，i+E[kE（M）k，i[ψ（k）Z，i]-ψ（k，M）Z，ikk，i，M]。（37）为了处理（36）（和（37））右侧的第二项，我们分解[kE（M）k，i[ψ（k）Y，i]-ψ（k，M）Y，ikk，i，M]≤ 2E[kψ（k）Y，i- ψ（k，M）Y，ikk，i，M]+2E[kE（M）k，i[ψ（k）Y，i]-ψ（k）Y，ikk，i，M]，（38）E[kE（M）k，i[ψ（k）Z，i]-ψ（k，M）Z，ikk，i，M]≤ 2E[kψ（k）Z，i- ψ（k，M）Z，ikk，i，M]+2E[kE（M）k，i[ψ（k）Z，i]-ψ（k）Z，ikk，i，M]。（39）我们首先处理术语E[kψ（k）Z，i- ψ（k，M）Z，ikk，i，M]和E[kψ（k）Z，i]- ψ（k，M）Z，ikk，i，M]；对于状态和上限，我们只关注前者的结果。我们采用类似于命题3.11（iv）证明的方法；参见[24，附录A]进行比较。首先，用命题3.11（i）观察ψ（k）Z，i- ψ（k，M）Z，i（·）解OLS（S（k）Z，i（x，w）- S（k，M）Z，i（x，w），k（k）Z，i，ν（k）M）。然后，由于KZ，k，是有限维的，它有一个正交的（关于范数k·kk，i，M）基{p，{p}k}≤ KZ，k，i。

使用p的正交性，设置α？：=R~p（x）>{S（k）Z，i（x）-2018年7月3日14时28分23S（k，M）Z，i（x）}dν（k）M，并扩展|α|作为对样本yieldskψ（k）Z的求和，i- ψ（k，M）Z，ikk，i，M=|α|=mkxm，m=1Tr~p（X（m））~p>（X（m））（S（k）Z，i（X（m））-S（k，M）Z，i（X（M））（S（k）Z，i（X（M））-S（k，M）Z，i（X（M））>.随机变量{X（1），…，X（Mk）}是独立的，这意味着{S（k）Z，i（X（m））- S（k，M）Z，i（X（M））：M=1，Mk}在条件上独立于F（M）k，i。因此，取条件期望E（M）k，i意味着对于m6=M，（M，M）-项变为0。矩阵∑（M）：=E（M）k，i（S（k）Z，i（X（m））-S（k，M）Z，i（X（M））（S（k）Z，i（X（M））-S（k，M）Z，i（X（M））>, 接下来就是e（M）k，ikψ（k）Z，i- ψ（k，M）Z，ikk，i，M=mkxm=1Tr[~p ~p>]（X（m））∑（m）≤mkxm=1Tr[~p ~p>]（X（m））Tr（∑（m）），（40），其中我们使用了Tr（AB）≤ Tr（A）Tr（B）对于任何对称的非负有限矩阵A和B。为了继续，我们需要E[Tr]上的上界[~p ~p>]（X（m））Tr（∑（m））]。根据基的选择，有两种方法可用：对于一般基（如定理3.7），我们找到几乎确定的在m中一致的Tr（σ（m））上界；另一方面，对于定理3.9中基的特殊选择，利用基的内在性质来获得定义的界。引理3.12。对于任何k≥ 0，我∈ {0，…，2k- 1} ，以及定义3.2中选择的基函数，kψ（k）Z，i- ψ（k，M）Z，ikk，i，M≤K（K）Z，我（k） iMkn | y（k）i（·）-y（k，M）i（·）|∞+K-1.-1Xj=α（i）+1 | z（k）-1） j（·）-z（k）-1，M）j（·）|∞（k）-1） jo，kψ（k）Y，i- ψ（k，M）Y，ikk，i，M≤K（K）Z，iMkk-1.-1Xj=α（i）+1 | z（k）-1） j（·）-z（k）-1，M）j（·）|∞（k）-1） j.证据。我们处理术语kψ（k）Z，i- ψ（k，M）Z，ikk，i，M；关于kψ（k）Y，i项的证明- ψ（k，M）Y，ikk，i，Misthe相同，我们排除它。回想一下估算（40）。

由于布朗增量的独立性，我们得到了等式tr（∑（m））=E（m）k，i[|S（k）Z，i（X（m））-S（k，M）Z，i（X（M））|]=E（M）k，i（y（k）i（X（k，m）i）-y（k，M）i（X（k，M）i））E[|W（k，m）i |](（k） 我知道-1.-1Xj=α（i）+1E（M）k，i|W（k，m）i | | z（k）-1） j（X（k）-1，m）j）-z（k）-1，M）j（X（k）-1，m）j）|E[|W（k）-1，m）j](（k） i）2018年7月3日14:28 24≤（k） in | y（k）i（·）-y（k，M）i（·）|∞+K-1.-1Xj=α（i）+1 | z（k）-1） j（·）-z（k）-1，M）j（·）|∞（k）-1） jo（41）现在，使用mpmm=1[~p~p>]（X（m））=IdR)和)K≤ KZ，k，i，将（41）的边界代入（40）以得到结果。事实上，如果在基函数的基础上假设额外的结构，就可以改进引理3.12。引理3.13。除一般假设外，假设（AK）来自定理3.9。给anyk≥ 0，我∈ {0，…，2k- 1} ，E[kψ（k）Z，i- ψ（k，M）Z，ikk，i，M]≤K（K）Z，iδ（k） iMknE[ky（k）i（·）-y（k，M）i（·）kk，i，∞] + 8qCX-kTθ-1+2kq ln（2）k-1.-1Xj=α（i）+1E[kz（k）-1） j（·）-z（k）-1，M）j（·）kk-1，j，∞]（k）-1） jo，（42）E[kψ（k）Y，i- ψ（k，M）Y，ikk，i，M]≤K（K）Z，iδMkk-1.-1Xj=α（i）+1E[kz（k）-1） j（·）-z（k）-1，M）j（·）kk-1，j，∞]（k）-1） j.（43）证据。我们给出了（42）的证明；（43）的证明是类似的（而且更简单）。从（40）开始，我们应用[5]的方法。为了方便读者，我们将[5]的符号转换为我们的设置：函数fjare相当于向量p的第j分量pj，whenceTr[~p ~p>]（X（m））=PK（k）Z，ij=1（fj）；Hα？mis等价于我们的S（k）Z，i（X（m））；X等于X，X等于X（m）。假设PX（k）i（AZ，k，i，j）≥ δ/K（K）Z，ifor all j。

利用第14页[5，情形（b）的条件论证，得出如下结论：e[kψ（k）Z，i- ψ（k，M）Z，ikk，i，M]≤ ehmkxm=1Tr[~p ~p>]（X（m））E（M）k，i[Tr（∑（M））]i≤MkE[Var（Hα？（X）|X）K（K）Z，iXj=1（fj）]（在[5]的等效符号中）≤K（K）Z，iXj=1E[|S（K）Z，i（X）- S（k，M）Z，i（X）|X（k）i∈AZ，k，i，j]MkP（X（k）i∈ AZ，k，i，j）≤K（K）Z，iδMkE[|S（K）Z，i（X）- S（k，M）Z，i（X）|]。为了完成证明，我们得到了E[|S（k）Z，i（X）的上界- S（k，M）Z，i（X）|]:E[|S（k）Z，i（X）- |=i（X，k）][（y（k）i（X（k）i）-y（k，M）i（X（k）i））E[|W（k）i |](（k） 我知道-1.-1Xj=α（i）+1E[|W（k）i | | z（k）-1） j（X（k）-1） j）-z（k）-1，M）j（X（k）-1） j）|]E[|W（k）-1） j](（k） i）。2018年7月3日14时28分，两人之间存在相互依赖问题W（k）土地| z（k）-1） j（X（k）-1） j）-z（k）-1） j（X（k）-1） j）我们现在对待的；注意，在处理E[|S（k）Y，i（X）时，这种相互依赖性不会出现-S（k，M）Y，i（X）|]。自从W（k）ihas q独立分量，每个分量都具有均值为0且方差为0的高斯分布（k） i，这些分量在定律上都等于q（k） 式中，N具有均值为0、方差为1的高斯分布。通过部分积分计算期望值，然后使用密尔不等式，对于任何R>0，这意味着[|N | N |>√R] =2P（N>√R） （R+1）-√重新-R/2√2π≤ 2P（N>√R） （R+1）-R）≤ 2e-R/2。现在，使用分解W（k）i=Tq（k） 红外光谱(W（k）i+(W（k）i- Tq（k） 红外光谱(W（k）i）和推论2.3和算法2中z项的最确定界，它遵循[|W（k）i | | z（k）-1） j（X（k）-1） j）-z（k）-1，M）j（X（k）-1） j）|]≤ qR（k） iE[|z（k）-1） j（X（k）-1） j）-z（k）-1，M）j（X（k）-1） j）|]+4qCX（k） i（T）- t（k）-1） j）1-θE[|N |N |>R]≤ qR（k） iE[kz（k-1） j（·）-z（k）-1，M）j（·）kk-1，j，∞] +8qe-R/2CX（k） i（T）- t（k）-1） j）1-θ≤ qR（k） iE[kz（k-1） j（·）-z（k）-1，M）j（·）kk-1，j，∞] +8qe-R/2CX（k） i（T）- t（k）-1） j）1-θ.通过选择R=ln（22k）完成证明。

为了完成（38）和（39）的估计，它只剩下界E[kE（M）k，i[ψ（k）Y，i]- ψ（k）Y，ikk，i，M]和E[kE（M）k，i[ψ（k）Z，i]-ψ（k）Z，ikk，i，M]。提案3.14。除一般假设外，假设（AX）（来自定理3.7）或（AK）（来自定理3.9）有效。那么，无论如何≥ 0和我∈ {0，…，2k- 1} ，E[kE（M）k，i[ψ（k）Y，i]-ψ（k）Y，ikk，i，M]≤ C2×2-kK（k）Y，iMk3CX+（2+q）andE[kE（M）k，i[ψ（k）Z，i]-ψ（k）Z，ikk，i，M]≤ C6K（k）Z，i（2+5T1）-θ） CxMk（T- t（k）i）1-θ+2C（2+q）K（K）Z，iCXcXMk。式中，如果（AK）成立，C=δ；如果（AX）成立，C=1。证据我们将使用提案3.11（iv）。对于x=（x，…，xk）∈ R（2k+1）×d，\'x=（\'x，…，\'xk）-1) ∈R（2k）-1+1）×d，w=（w，…，wk-1) ∈ Rk×q，定义h（x，’x，w）：=xi；h是一个Borel可测函数，h（X（m））=X（k，m）i。用h表示σ-代数σ嗨（Xm）：m=1，Mk, 等于σ（X（k，m）i:m=1，Mk），并由G表示σ-代数F(*)K-1.∨ σ（X（k，m）j:j<i，m=1，Mk）；那么S（k）Y，i（·）和S（k）Z，i（·）是G B（Rl）-可测量，和G∨ H等于F（M）k，i。由于ψ（k，M）Y，i（resp.ψ（k，M）Z，i）解OLS（S（k）Y，i（·），k（k）Y，i，ν（k）M）（resp.OLS（S（k）Z，i（·），k（k）Z，i，ν（k）M）），它只剩下为期望ψY，k，i:=E（M）k，i[|S（k）Y，i（X（M））找到合适的（确定性）上界- E（M）k，i[S（k）Y，i（X（M））]|]2018年7月3日14:28 26（分别为ψZ，k，i:=E（M）k，i[|S（k）Z，i（X（M））- E（M）k，i[S（k）Z，i（X（M））]|]）允许我们应用命题3.11（iv）。这项技术对于ψY，k，i和ψZ，k，i都是相似的，所以我们只包括后者的证明。

策略如下：首先，我们假设马尔可夫链X（k，m）和X（k-1，m）是t（k）处的确定值x和t（k）处的¨x-1） α（i）；然后通过引入扩散过程X（t（k）i，X，m）和X（t（k），分解ψZ，k，ib的上界-1） α（i），\'x，m）；最终，我们得到了x=x（k，m）和x=x（k-1，m）α（i）（由于自始至终使用条件期望E（m）k，i[·]而不会造成困难）来获得最终界限。IStep 1（定义t（k）和t（k）处马尔可夫链的初始值-1） α（i））：观察随机变量S（k）Z，i（X（m））仅通过值（X（k，m）i，X（k，m）k，X（k）-1，m）α（i）+1，X（k）-1，m）k-1.i（k），W，W（k，m）k-1） 也就是说，它不依赖于路径X（k，m），X（k-1.m）和时间t（k）i.Lettingx，`x之前的W（k，m）∈ 我们定义（m，i）（x，\'x）：=（x（k，m，i，x）i，X（k，m，i，X）k，X（k-1，m，α（i），\'x）α（i）+1，X（k）-1，m，α（i），\'x）k-1.W（k，m）i，W（k，m）k-1).然后可以写出ψZ，k，i=ψZ，k，i（X（k，m）i，X（k-其中ψZ，k，i（x，\'x）：=E（m）k，i[|S（k）Z，i（x（m，i）（x，\'x））- E（M）k，i[S（k）Z，i（X（M，i）（X，\'X））]。IStep 2（中间离散BSDE分解）：设X（t，X，m）（m）∈ {1，…，Mk}）是从时间t开始的扩散模拟，其值x与增量的布朗运动路径相同W（k，m）i.回顾第2.2节中的离散BSDE（~y（k），~z（k））和定义y（k，m）j:=Ekj[Φ（X（t（k）i，X，m）t）]，以及（k） j~z（k，m）j:=Eki[(W（k，m）i）>j的Φ（X（t（k）i，X，m）t）]∈ {0，…，2k- 1}. 对于粗网格π（k-1） ，定义y（k-1，m）j:=Ek-1j[Φ（X（t）k-1） α（i），\'x，m）T]和（k）-1） j~z（k）-1，m）j:=Ek-1j[W（k）-1，m）jΦ（X（t）k-1） j的α（i），\'x，m）T]∈ {0，…，2k-1.-1}.

我们使用这些过程将S（k）Z，i（X（m）（X，\'X））分解为两个表达式：S（k）Z，i（X（m，i）（X，\'X））=W（k，m）i（k） inΦ（X（k，m，i，X）N）-Φ（X（t（k）i，X，m）t）-（y（k）i（X（k，m，i，X）i）- ~y（k，m）i）-主键-1.-1j=α（i）+1（z（k）-1） j（X（k）-1，m，α（i），\'x）j）- ~z（k）-1，m）j）W（k）-1.m）乔+W（k，m）i（k） 我Φ（X（t（k）i，X，m）t）- ~y（k，m）i-K-1.-1Xj=α（i）+1~z（k）-1，m）jW（k）-1，m）j=: A（x，\'x）+A（x，\'x）。2018年7月3日14:28 27微不足道的不平等（x+y）≤ 2x+2y对于所有实x和y，则产生ψZ，k，i（x，\'\'x）≤ 2E（M）k，i[A（x，\'x）]+2E（M）k，i[A（x，\'x）]。I步骤3（绑定在E（M）k上，I[A（x，\'\'x）]）。利用柯西-施瓦兹不等式，我们得到了e（M）k，i[|z（k）-1） j（X（k）-1，m，α（i），\'x）j）- ~z（k）-1，m）j |]=(（k）-1） j）E（M）k-1，i[|E（M）k，j[(W（k）-1，m）j）>（y（k）-1） j+1（X（k）-1，m，α（i），\'x）j+1）- ~y（k）-1，m）j+1）]≤Q（k）-1） jnE（M）k，i[|y（k）-1） j+1（X（k）-1，m，α（i），\'x）j+1）- ~y（k）-1，m）j+1 |]-E（M）k，i[|E（M）k-1，j[y（k）-1） j+1（X（k）-1，m，α（i），\'x）j+1）- ~y（k）-1，m）j+1]|]o.观察E（m）k-1，j[y（k）-1） j+1（X（k）-1，α（i），\'x，m）j+1）- ~y（k）-1，m）j+1]=y（k-1） j（X（k）-1，α（i），\'x，m）j）- y（k-1，m）j。

然后，求和符号的ashift表示givesk-1.-1Xj=α（i）+1E（M）k，i[|z（k）-1） j（X（k）-1，m，α（i），\'x）j）- ~z（k）-1，m）j |]（k）-1） j≤K-1.-1Xj=α（i）+1qnE（M）k，i[|y（k）-1） j+1（X（k）-1，m，i，`x）j+1）- ~y（k）-1） |j+1241]-E（M）k，i[|E（M）k-1，j[y（k）-1） j+1（X（k）-1，m，i，`x）j+1）- ~y（k）-1） j+1]|]o≤K-1.-1Xj=α（i）+1qnE（M）k，i[|y（k）-1） j（X（k）-1，m，i，`x）j）- ~y（k）-1，m）j |]-E（M）k，i[|E（M）k-1，j[y（k）-1） j+1（X（k）-1，m，i，`x）j+1）- ~y（k）-1，m）j+1]|]|{z}=0o+qE（m）k，i[|Φ（X（k-1，m，α（i），\'x）N）-Φ（X（t）k-1） α（i），\'x，m）T）|]。因此，利用布朗增量的独立性，可以得到上界（M）k，i[A（x，\'x）]=（k） inE（M）k，i[|Φ（X（k，M，i，X）N）-Φ（X（t（k）i，X，m）t）|]+E（m）k，i[|y（k）i（X（k，m，i，X）i）- ~y（k）i |]+k-1.-1Xj=α（i）+1E（M）k，i[|z（k）-1） j（X（k）-1，m，i，`x）j）- ~z（k）-1，m）j |]（k）-1） 乔≤（k） in2E（M）k，i[|Φ（X（k，M，i，X）N）-Φ（X（t（k）i，X，m）t）|]+qE（m）k，i[|Φ（X（k）]-1，m，α（i），\'x）N）-Φ（X（m，t（k）-1） α（i），|x）T）|]o（44）根据马尔可夫链（AX）（i）和时间网格（Aπ）（iii）的假设（44）中括号中的项可以由CXmaxi{2限定-k+q2-（k）-1)}. 因此，E（M）k，i[A（x，\'x）]≤（2+q）CX-K（k） 我≤（2+q）CXcX。2018年7月3日14:28 28I第4步（在E（M）k，i[A（x，\'\'x]上绑定）。使用等式（9）和引理2.1，我们得到-1.-1Xj=α（i）+1~z（k，m）jW（k）-1，m）j=Φ（X（t）k-1） α（i），\'x，m）T）- ~y（k）-1，m）α（i）+1-K-1.-1Xj=α（i）+1L（k）-1，m）jwhereL（k）-1，m）j:=Rt（k）-1） j+1t（k）-1） j（z（t）k-1） α（i），\'x，m）t- ~z（k）-1，m）j）>dW（m）和z（t（k）-1） α（i），\'x，m）是（AX）（iii）中给出的过程，其中x（t）（k-1） α（i），\'x，m）代替x（t（k）-1） α（i），\'x）。

将其代入A（x，\'\'x）的定义中，则表示A（x，\'\'x）=(W（k）i）>（k） inΦ（X（t（k）i，X，m）t）-Φ（X（t）k-1） α（i），\'x，m）T）-（~y（k，m）i- ~y（k）-1，m）α（i）+1）+k-1.-1Xj=α（i）+1L（k）-1.m）乔。现在，我们确定并接受期望值，并以正确的方式对待条款五十、 Φ和y分别为。在…中处理术语五十、 我们应用性质（Aπ）（iv）来获得该pk-1j=α（i）+1E（M）k，i[|L（k）-1，m）j |]以2CX为界-K该上界与x（t（k）的起始值x无关-1） α（i），\'x，m）。为了处理涉及Φ的术语，我们将假设（AX）（ii）应用于obtainE（M）k，i[|Φ（X（t（k）i，X，M）t）-Φ（X（t）k-1） α（i），\'x，m）T）|]≤ CX | x-X（t（k）-1） α（i），\'x，m）t（k）i |。（45）备注3.15。在（45）中，可以看到条件（AX）（ii）的影响；需要求出O（2）的上界-k） 对于Φ中的项，一旦我们把x=x（k，m）i，\'x=x（k-1，m）α（i），并取期望值。最后，为了处理y中的术语，我们使用y（k，m）i- ~y（k）-1，m）α（i）+1等于y（k，m）i±y（k，m）2（α（i）+1）- ~y（k）-1，m）α（i）+1=（~y（k，m）i）- y（k，m）2（α（i）+1））+E（m）k，2（α（i）+1）[Φ（X（t（k）i，X，m）t）-Φ（X（t）k-1） α（i），\'x，m）T）]。Φ中的术语按（45）处理。我们进一步扩展（~y（k）i- ~y（k）2（α（i）+1））使用（9）~y（k，m）i- ~y（k，m）2（α（i）+1）=2（α（i）+1）Xj=i{z（k）jW（k，m）j+L（k，m）j}。通过平方和条件期望，我们得到了（Aπ）（iv）和推论2.3，即e（M）k，i[|y（k，M）i- y（k，m）2（α（i）+1）|]=2（α（i）+1）Xj=iE（m）k，i[|z（k）j||W（k）j |+|L（k）j |]≤2CX-k（T）- t（k）i）1-θ+CX-k、 为了结束第4步，我们结合上述上界来获得（k） iE（M）k，i[A（x，\'x）]≤ 3×（3CX | x-X（t（k-1） α（i），\'x，m）t（k）i |+2CX-k（T）- t（k）i）1-θ+2CX-k） 。2018年7月3日14:28 29因此，堵塞x=x（k，m）和¨x=x（k-1，m）α（i），我们得到（k） iE（M）k，i[A（X（k，M）i，X（k-1，m）α（i））]≤ 9CX | X（k，m）i- X（k）-1，m）α（i）|+6CX-k（T）- t（k）i）1-θ+6CX-k（46）总结证据。

（AX）下命题的证明现在通过观察|X（k，m）i来完成- X（k）-1，m）α（i）|=0 in（46），将步骤1-4中获得的估计值拼合为一（m）k，i[|S（k）Z，i（X（m））- E（M）k，i[S（k）Z，i（X（M））]|]发现存在确定性界，并应用命题3.11（iv）。另一方面，如果（AK）有效，我们再次（在引理3.13的证明中）使用[5，第14页的情况（b）]的条件参数来获得[kE（M）k，i[ψ（k）Z，i]-ψ（k）Z，ikk，i，M]≤δK（K）Z，即E（M）k，i[|S（k）Z，i（X（1））-E（M）k，i[S（k）Z，i（X（1））]Mk.通过组合步骤1-4中获得的E（M）k，i[|S（k）Z，i（X（1））的估计值-E（M）k，i[S（k）Z，i（X（1））]|]代入上述不等式，我们可以看到期望E[kE（M）k，i[ψ（k）Z，i]-ψ（k）Z，ikk，i，M]以6δk（k）Z为界3CXE[|X（k）i- X（k）-1） α（i）|]（k） i+（2+2T1）-θ） CXcX（T- t（k）i）1-θ+ 2δ（2+q）K（K）Z，iCXcXMk≤6δK（K）Z，i（2+5T1）-θ） CxMk（T- t（k）i）1-θ+2δ（2+q）K（K）Z，iCXcXMk（47），其中我们在上一个不等式中使用了（AX）（iii），并且（Aπ）（iii）用于界（k） 我≥ cX-K备注3.16。我们在等式（47）中看到了假设（AX）（iii）的影响；假设收敛速度较低，则理论3中关于上界k的整体收敛速度。9会更低。通过使用引理3.12（分别为引理3.13）和命题3.14估计（38–39）中的项，完成证明，并将估计值代入（36–37）。3.5计算示例本节中的计算示例说明并比较不同模拟方案与带零生成器的BSDE的实际误差和效率（3），以支持基于误差估计的理论分析结果。我们考虑具有解析解的BSDE情况，以便研究各个近似方案的近似解的实际全局均方误差（MSE）。

MSE由蒙特卡罗在一个固定时间网格上计算，计算方式与（23）中的全局误差相同。总MSE是相对于Y和Z分量的MSE之和，分别对应于第一个（最大加班时间的平方）和第二个（时间加权）和。2018年7月3日14:28 303.5.1正弦支付首先让我们考虑一个q=1维的例子，其中T=1，X=W，终端条件Φ（X）=sin（X）。在回归基础上，我们采用了高达7次的埃尔米特多项式，对{1，p（t，Wt），…，p（t，Wt）}在所有时间t>0的情况下都是正交的，即K=8。我们在最终水平K运行多水平（ML）方案，Mk=40×K×2k模拟，而在任何较低水平j<j+1≤ k模拟次数Mj=2Mj+1倍。在k级之前，ML的总体复杂度为ML=O（k×22k）。为了进行比较，我们运行了MDP方案的两个实例：第一个（MDP1）和1 2 3 4 5 6 7 8 9-16-14-12-10-8.-6.-4时间步长（log2）误差（log2）全局均方误差多级复杂度为O（k22k）MDP2复杂度为O（23k）MDP1复杂度为O（22k）图1：正弦支付：对数均方误差与对数（N）对ML和MDP1，2Mk=40×K×2K模拟，然后（MDP2）具有更高的数值Mk=40×K×22k模拟。第一种情况下的复杂性为CMDP，1=O（22k），第二种情况下的复杂性为CMDP，2=O（23k）。图1显示了MDP1、MDP2和theML方案的全局均方误差（MSE）与时间步数k=logN的对数。各回归线为（ML）-0.88倍-5.0（MDP1）-0.05倍-分别为5.7（MDP2）-0.97-6.5. 本例支持定理3.7和3.9的结果，以及第3.3节中随后的复杂性分析；事实上，我们可以看到，MDP的模拟量是多级模拟量的2k倍，才能达到大约2倍的收敛速度-1.

此外，我们可以看到计算结果表明，在定理的假设之外，对于比（AK）允许的更广泛的基函数类，可以获得定理3.9中所述的效率增益，因为本例中使用的基函数不满足此条件。3.5.2一个多维例子假设正向过程是一个布朗运动X=W，维度q=3，考虑终端条件Φ（XT）=qqxit，T=1。这超出了第3.3节复杂性分析中使用的假设、有界性假设（AΦ）和利普希茨假设（AX）（iv）。本例将分别比较2018年7月3日14:28（ML）和MDP计划的Y部分和Z部分的MSE贡献。此外，我们还比较了两组不同的回归基础。第一个回归基础（“指标”）由Rinto K=8=512集的等概率超立方体上的指标函数组成。第二个回归基（“线性”）由函数组成，每个函数都位于Rinto K=5集划分的一个超立方体内，并在外部消失。线性基包含4×5=500个回归函数，因此两个基的大小大致相同。两种方案的模拟次数均为M=2×10。

对于ML，每个级别使用相同数量的模拟。（N）2 3 4 4 5 5 5 5 6 6 6 6 6 0.1253 0 0.1236 0.1231 0 0.1222 2 2 2 2 2 2 2 2 2 0 0 0.12 12 5 5 0 0 0.1194 0 0 0.1194 0 0 0.1183 0 0.1183 0 0 0.0 0 0 0 0 0.5 5 5 5 5 5 5 5 0.0 0 0 0 0.0 0 0 0.1193 3 0 0 0 0 0 0 0.1193 0 0 0 0 0 0 0 0 0 0 0 0 0.1193 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.1190升升（线性）线性（线性）线性）0（线性）0（线性）0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.0 0 0 0 0 0 0 0 0 0 0.0358 0.0 0 0 0.0 0 0 0 0 0 0 0 0 0 0.58 0.0 0.0 0 0 0.0.1154 0.1210MDPY（指标）0.5865 0.5465 0.5351 0.5318 0.5297 0.5297MDP Z（指标）0.1514 0.1253 0.1230 0.1330 0.1550 0.2044全局均方误差表（表1）显示，对于内时间网格，多级方案的Z部分误差较低，而Y部分的误差相似。多级方案显示，对于线性基，Z的误差降低得更高。对于k=logN，误差减少系数超过1/2≥ 4是重要的，即使注意到在最终水平k时，N=2k+1时间步长的MDP的计算成本基本上等于N=2k步长的ML的计算成本。与MDP相比，多级方案的误差（Z）在后期k=logN开始增加，并以更温和的速度增加，无论选择的基础是什么；通过比较图2和图3可以看出这一点。这一影响与定理3.7和3.9的结果相吻合，定理3.7和3.9指出，与MDP方案相比，多级方案的误差受时间点数量的影响较小（27）；多级方案的误差应仅随N的对数增加。图2显示了误差曲线在较大k时仅轻微增加。请注意，对于固定数量的模拟，如此处所示，统计误差不可避免地会在某个阶段增加和接管；这仅仅意味着更大的k=logN需要更多的模拟。

在这个例子中，基于该基础的函数空间上的线性投影的偏差较小，而基于指标的函数空间则需要一个更好的划分来实现这一点，从这个意义上可以理解线性模型相对于指标模型的优势。这个例子表明，通过实际计算可以实现多层次的效率增益；此外，还表明，除了第3.3.4节完成拆分算法Fix k>0所要求的特定假设外，在更一般的情况下，效率的提高可能是预期的。在本节中，大致描述拆分系统（4）的第二部分，即函数“y（k）i:Rd”→ R和z（k）i:Rd→ （Rq）>引理2.2。在2018年6月3日14:28 321 2 3 4 6 7省略上标（k）以简化注释-2.-1.5-1.-蒙特卡罗法的0.5log2（N）log10（MSE）BSDE近似- Z-ML方案中的均方误差（MSE）（线性基础）ML方案（指示剂基础）图2:3维中的多水平的Z中的均方误差（MSE）如下所示，我们记得这些函数满足¨yi（Xi）：=Eihk-1Xj=i+1fjXj，y（k）j+1（X（k）j+1）+yj+1（X（k）j+1），z（k）j（X（k）j）+zj（X（k）j）吉，i×(R)zi（Xi）：=EihW（k）iK-1Xj=i+1fjX（k）j，yj+1（X（k）j+1）+yj+1（X（k）j+1），zj（X（k）j）+zj（X（k）j）Ji、 设函数（yj（·），zj（·））为0≤J≤N-1b使用多级算法进行近似，π表示多级算法最高级别的时间网格π（k）。我们使用[24]中的最小二乘多步动态规划（LSMDP）对具有零终端条件的离散BSDE和随机驱动Rf（M）j（y，z）：=fjX（k）j，y（k，M）j+1（X（k）j+1）+y，z（k，M）j+1（X（k）j+1）+z（48）近似为“易（·）”和“子（·）”。我们在符号X（k）中保留上标k，W（k）和t（k）提醒使用的时间网格是π（k），尽管LSMDP没有使用更早（更粗糙）的时间网格。

驱动程序有两个随机性来源：依赖于多级算法中使用的样本的随机函数（y（k，M），z（k，M））和马尔可夫链X（k）。符号f（M）j（x，x，y，z）：=fjx、 y（k，M）j+1（x）+y，z（k，M）j（x）+z,将在续集中有所帮助。为了方便读者，我们简要回顾了LSMDP算法。与第3节中的算法一样，LSMDP是一种最小二乘蒙特卡罗算法；2018年6月3日14时28分的差异331 2 3 4 6 7-2.-1.5-1.-蒙特卡罗法的0.50log2（N）log10（MSE）BSDE近似- Z MDP方案中的均方误差（MSE）（线性基础）MDP方案（指标基础）图3:3维MDP的Z中的均方误差（MSE）与第3节的多级算法相比，基函数的选择和模拟的生成有三个方面：首先，由于没有使用多个级别，只生成Markovchain X（k）的模拟；其次，为每个时间点生成独立的模拟云，这意味着每个时间点的经验度量独立于在任何其他时间点使用的经验度量；第三，基函数的选择与多级方案不同。我们通过以下定义将其正式化。定义4.1（有限维近似空间）。因为我∈ {0，…，2k-1} 我们定义了函数线性空间KY，iand KZ，iof维KY，iand KZ，i，由KY，i:=span{p（1）Y，i，…，p（KY，i）Y，i}，对于p（l）Y，i:Rd→ R s.t.E[|p（l）Y，i（Xi）|]+∞,KZ，i:=span{p（1）Z，i，…，p（KZ，i）Z，i}，对于p（l）Z，i:Rd→ （Rq）>s.t.E[|p（l）Z，i（Xi）|]+∞.我们在基函数和线性空间的表示法中抑制下标k，以区别于定义3.2中的下标k。函数“yi（·）”和“zi（·）”将分别在线性空间KY、i和KZ、i中进行近似。将以KZ，i近似。

我们定义1，i:=infφ∈KY，iEh |φ（Xi）- \'yi（Xi）| i:=infφ∈KZ，iEh |φ（Xi）- \"子(十一)一;；与定义3.2一样，这些是choosen基函数可能存在的最佳近似误差。定义4.2（模拟和经验测量）。因为我∈ {0，…，2k- 1} ，生成Mi≥ 1独立副本Ck，i:={(W（k，i，m）i，X（k，i，m））：m=1，米}of(W（k）i，X（k））：Ck，i时间i时用于回归的模拟云。我们假设模拟云（Ck，i:0≤ i<N）是独立生成的，并且也是从云{Ck:0]独立生成的≤ K≤ k} 用于多级算法的定义4.2。让ν（k）i，Mdenote于2018年7月3日14:28测量Ck，i-模拟，即ν（k）i，M=MiMiXm=1δ(W（k，i，m）i，X（k，i，m）i，。。。，X（k，i，m）k）。我们使用符号中的附加下标i表示模拟云Ck，i，以及LSMDP算法的经验测量ν（k）i，m，来区分它们与多级算法中使用的下标i，并指定时间点。正如在第3节中，我们扩大了概率空间，同时继续通过(Ohm, F、 P），还包含用于LSMDP和多级算法的模拟；回想一下，原型过程W（k）和X（k）独立于所有模拟云。算法3。回想一下线性空间KY，iand KZ，ifrom定义4.1，经验测度{ν（k）i，M:i=0，…，2k- 1} 根据定义4.2，（Af）（iii）中的几乎确定界限，第1.1节中截断函数TL（·）的定义，以及定义3.1中的OLS。设置y（M）k（·）：=0。对于每个i=2k- 1，2k- 2.

，0，递归设置随机函数y（M）i（·）和z（M）i（·）如下：定义y（M）i（·）：=TCy，iψ（M）Y，i（·）和¨z（M）i（·）=TCz，iψ（M）Z，i（·）, 式中，Cy，i:=CX（T）- t（k）i）（θL+θ）/2，Cz，i:=CX（t）- t（k）i）（θL+θ）/2/（k） 土地ψ（M）Y，i（·）OLSS（M）Y，i（x），KY，i，ν（k）i，M对于S（M）Y，i（x）：=k-1Xj=if（M）kxj，xj+1，\'y（M）j+1（xj+1），\'z（M）j（xj）（k） j和ψ（M）Z，i（·）解OLSS（M）Z，i（w，x），KZ，i，ν（k）i，M对于S（M）Z，i（w，x）：=（k） 是（M）Y，i+1（x）w>，代表w∈ Rq，x=（x，…，xk）∈ （Rd）k+1。（49）我们现在来看本节的主要结果，即LSMDP算法的误差分析。定理4.3（LSMDP方案的误差）。回想一下常数Cy，iand Cz，ifrom算法3。每j∈ {0，…，2k- 1} ，定义（j）：=TY1，j+TZ1，j+CS3KY，jMj+2qKZ，j（k） jMj+ 800Cy，j（KY，j+1）+Cz，j（KZ，j+1）q对数（3Mj）Mj。式中cs:=k-1Xi=0nCf+Lf（Cy，i+Cy+Cz，i+Cz，k，i）（T）- t（k）i）（1-θL）/2o（k） i.从（Aπ）中回忆Cπ（k），并假设k足够大，因此Cπ（k）Lf（Rπ）∨ 1) ≤ （384（2q+（1+T）eT/2）（1+T））-1，并且多级算法的参数是这样的，即全局误差由¨E（k）估计≤ ε对于某些ε>0（关于¨E（k）的定义，见等式（23）和随后的2018年7月3日14:28）。那么，对于所有0≤ 我≤ 2k- 1，EhMiMiXm=1 | y（M）i（X（k，i，M）i）- \'yi（X（k，i，m）i）|i≤ TY1，i+3CSKY，iMi+CΓ（1+T）ε+CΓk-1Xj=iE（j）（k） j，（50）k-1Xj=iEhMjMjXm=1 | z（M）j（X（k，j，M）j）- \'zj（X（k，j，m）j）|i（k） j≤ CΓ（1+T）ε+CΓk-1Xj=iE（j）（k） j，（51）式中CΓ=8 exp384（Rπ）∨ 1） （2q+（1+T）eT/2）（1+T）TθLLf/θL.上述定理的证明类似于[24，定理4.11]的证明。

事实上，[24，定理4.11]的证明仅依赖于条件论元、先验估计、可测性集中和普通最小二乘回归的基本性质（命题3.11）；apriori估计[24，命题3.2]承认驱动因素的随机性，并且有序最小二乘回归的性质是通用的，因此这些参数不需要对我们的设置进行更改。下面的命题5.1提供了测量结果的浓度。分析中有三个最小值，为了方便读者，我们现在对其进行详细说明。首先，我们必须通过添加σ（C，…，Ck）来扩充条件参数中使用的σ-代数，σ（C，…，Ck）是分裂系统第一部分的多级算法中使用的模拟的σ-代数。其次，在应用先验估计后，必须估计[|fj（y（k）j+1（X（k）j+1）+yj+1（X（k）j+1），z（k）j（X（k）j）+zj（X（k）j））-f（M）j（\'y（M）j+1（X（k）j+1），\'z（M）j（X（k）j））|]（52），而在[24，等式（33）]中的相应计算中，只需要估计E[|fj（yj+1（X（k）j+1），zj（X（k）j））-fj（y（M）j+1（X（k）j+1），z（M）j（X（k）j））|]。

回顾一下f（M）j（y，z）：=fj（X（k）j，y（k，M）j+1（X（k）j+1）+y，z（k，M）j+1（X（k）j+1）+z，我们使用fj（y，z）的Lipschitz连续性以及（y（k），z（k））的近似（y（k，M），z（k））会产生小于或等于ε的全局误差来估计由于多电平效应而产生的误差。最后，将[24，定理4.11]中的常数C（4.7）替换为CS；CSis的显式值与[24，引理4.7]中C（4.7）的显式值完全相同，仅使用‘y（M）i（·）和‘z（M）i（·）的几乎绝对边界。5结论：使用第3节和第4节的结果，比较有无外裂和多级方案，我们现在可以将我们的算法（拆分结合多级）与最小二乘多步动态规划（LSMDP）方案进行比较，两者都没有。为了简单起见，我们将假设θ=θL=1，这意味着终端条件Φ（·）是Lipschitz连续的（但不一定是可微分的），并且驱动器在（y，z）中是一致Lipschitz连续的。对于本节的剩余部分，如果存在一个独立于k和y的常数，我们写g（y）=O（y），使得g（y）/y→ C为y→ 0.对于给定的精度水平ε>0，我们的目标是在2018年7月3日14:28 36设置基函数和（\'yi，\'zi）近似值的每个时间点的模拟次数，以便全局误差满足E（M）：=max0≤我≤2k-1E[| y（M）i（X（k）i）- |X（k）i=124i（k）- “\'zi（X（k）i）|]（k） 我≤ O（ε）。（53）为了应用定理4.3，我们首先提供测量结果的集中度。提议5.1。每k∈ {0，…，κ}和i∈ {0, . . .

，2k- 1} ，我们有[y（M）i（X（k）i）- “\'yi（X（k）i）|]≤ 2HMIMIXM=1|y（M）i（X（k，i，M）i）- \'yi（X（k，i，m）i）|i+2028（KY，i+1）Cy，ilog（3Mi）Mi，E[| z（m）i（X（k）i）- “\'zi（X（k）i）|]≤ OX（hmiz）i=124m- \'zi（X（k，i，m）i）|i+2028（KZ，i+1）qCz，ilog（3Mi）Mi；我们记得Cy，i=CX（T- t（k）i）（1+θ）/2和Cz，i=CX（t- t（k）i）θ/2。正如命题3.5一样，命题5.1类似于[24，命题4.10]。不等式右边的第二项是修正项，可以解释为由于内部测度的变化而产生的相互依赖误差。我们看到，互依误差与定理4.3中E（i）中的最后一项K·，i和Mi具有相同的依赖性。因此，为了确保（53），有必要设置数值参数，使局部误差项满足E（i）≤ O（ε）为everyi∈ {0，…，2k- 1}. 使用（AX）（ii），我们可以替换TY1，i和TZ1，ibyTY2，i:=infφ∈KY，iE[|φ（Xt（k）i）-U（t（k）i，Xt（k）i）|]和TZ2，i:=infφ∈KZ，iE[|φ（Xt（k）i）-V（t（k）i，Xt（k）i）|]分别在局部误差项E（i）中，并选择基函数，使TY2，i和TZ2，i在每个i中由O（ε）控制。由于（Af）（iii）中的Lipschitz连续性，在直径为O的不相交超立方体的划分上使用（每个时间点以及Y和Z）函数的基是有效的(√ε). 这个基础是有限维的，但我们可以做一个简单的截断来绕过这个问题。我们还假设（如[24，第4.4节]）对于每一个∈ {0，…，2k-1} ，X（k）i为指数矩，因此我们可以在外部区域中设置基础[-R、 R=ln（ε）时R]dto为零-1+ 1); 这种截断会导致误差O（ε），这是允许的。因此，超立方体基Kl，iI的维数在l中是一致的∈ {Y，Z}和我∈ {0，…，2k- 1} ，也相等（ε-d/2ln（ε）-1+1）d）。

因此，我们必须选择模拟的数量，使其在i中均匀地等于O（2kε）-1.-d/2ln（ε）-1+1）d）。它只剩下计算方案的复杂性。对计算成本有两个贡献：马尔可夫链X（k）的模拟成本和布朗增量W（k），以及回归的成本。模拟成本等于O（23kε）-1.-d/2ln（ε）-1+1）d）；额外因子2k来自于在每个时间步重新模拟马尔可夫链X（k）的路径。由于我们使用分区估计来计算回归系数，回归成本等于toPk-1j=0O（Mi）=O（22kε-1.-d/2ln（ε）-1+1）d）；有关分区估计的详细信息，请参见第3.3节。因此，回顾2k=ε-1，整体复杂度等于O（ε）-4.-d/2ln（ε）-1+1）d）。因此，利用第3.3节中的假设和计算，可以得出，在2018年7月3日14:28 37时，采用多级算法（即算法3和算法2）的拆分方案的总体复杂性为isO（ε-2.-dln（ε）-1+1））+O（ε-4.-d/2ln（ε）-1+1）d）。（54）我们现在校准了LSMDP算法，该算法没有分裂，也没有多级，下面我们回顾一下算法4中的完整性。然后，我们计算该算法的复杂度，以便与已建立的算法进行适当的比较，并确定多级分割算法的可能增益。算法4。回想一下线性空间KY，iand KZ，ifrom定义4.1，经验测度{ν（k）i，M:i=0，…，2k- 1} 根据定义4.2，（Af）（iii）中的边界，以及第1.1节中的截断函数tl（·）。集合y（M）k（·）：=Φ（·）。对于每个i=2k- 1，2k- 2.

，0，将随机函数y（M）i（·）和z（M）i（·）递归设置如下：定义y（M）i（·）：=TCyψ（M）Y，i（·）z（M）i（·）=TCz，iψ（M）Z，i（·）, 式中，Cy:=CX，Cz，i:=Cz，k，iandψ（M）Y，i（·）解S（M）Y，i（x），KY，i，ν（k）i，M）的OLS（S（M）Y，i（x）：=Φ（xN）+k-1Xj=ifkxj，y（M）j+1（xj+1），z（M）j（xj）（k） j和ψ（M）Z，i（·）为S（M）Z，i（w，x）解OLS（S（M）Z，i（w，x），KZ，i，ν（k）i，M）：=（k） 是（M）Y，i+1（x）w>，代表w∈ Rq，x=（x，…，xk）∈ （Rd）k+1。[24，定理4.11]研究了该算法的误差。利用该算法，我们直接逼近连续时间函数v（t，·）+v（t，·）。算法4的复杂度分析与上述算法3的复杂度分析相同，但我们必须考虑到由于Lipschitz系数的时间依赖性而产生的额外权重：v（t，·）+v（t，·）的Lipschitz常数等于- （t）-1/2）对于所有t∈ [0，T）-参见假设（AX）（iv）和（Af）（iii）。因此，我们为每个时间点i选择一个超循环基础∈ {0，…，2k- 1} 谁的立方体有直径- t（k）iO(√ε).因此，算法4的总体复杂度为isO（ε-3.-d/2ln（ε）-1+1）d）k-1Xi=0（T- t（k）i）d/2≤ O（ε）-4.-dln（ε）-1+1）d）。与（54）中的两项相比，算法4的复杂度占主导地位：如果d<4，（54）以O（ε）为主导-4.-d/2ln（ε）-1+1）d），而对于d≥ 4，（54）以O（ε）为主-2.-dln（ε）-1+ 1)).因此，在高维d中，ε的一阶等于二阶≥ 4.由于使用了多级分割算法。如果我们在零驱动部分使用分裂法，但不使用多级（即注释3.8中的LSMDP），与纯LSMDP相比，增益仍然很大，在ε中为一阶，但是通过多级（对于d≥ 4） ，参见第3.3节。最后，我们通过一个金融示例的计算结果来支持非线性发生器的理论。

为此，考虑一个d=2维正向过程X=（S，H），用于相关几何布朗运动dS=Sσsdww，其中S=1，dh=Hγdt+σH（ρdW+p1）-ρdW）, H=1，（55）2018年7月3日14:28 38，参数σS=σH=0.5，ρ=0.6和γ=0.1。将S和H视为流动可交易风险资产和非流动资产的（贴现）价格过程，期权Φ（XT）=（HT）的所谓不好交易估值界Y- ST）+到期时交易T一项交易资产Tinto一项非交易资产Ht由非线性BSDEdYt描述=-h | Z（2）t | dt+ZtdW=-|Z（2）t | dt+Z（1）tdW（1）t+Z（2）tdW（2）t，YT=Φ（XT），（56），其中Z=（Z（1），Z（2））；对于我们认为h=0.2的大量约束，请参见[2,3]。BSDEH是Margrabe型公式的显式解，见[3]，相应的良好交易对冲策略可以从Z中获得。ML和MDP的回归基础由Rinto K=50集的a部分超立方体上的指标函数给出。模拟次数为M=2* 两个方案各10个；对于多层（ML），每个层使用相同数量的模拟。均方误差的结果见表2。它们显示了多级（ML）与分裂方案相结合的大幅误差减少，尤其是对于时间网格（更大的k=logN）的Z中的MSE，与之前一样，也证实了使用非零生成器的本例的见解。表2：Y和Z方向非零发生器对数（N）1 2 3 4 5MDP Y 0.1372 0.0795 0.0515 0.0379 0.0322MDP Z 0.0161 0.0089 0.0092 0.0143 0.0253 Ml Y 0.1371 0.0791 0.0510 0.0373 0.0314 Ml Z 0.0156 0.0068 0.0039 0.0032 0.0031确认：我们感谢Emmanuel Gobet对本文和论文[38]的建议，其中首次引入了多级方案，特别是为了指出定理3.9中使用的特殊基础。