倒向随机微分方程的多级逼近

我们相信较弱的诺曼假设（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。