基于强化回归的最优停车

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Optimal stopping via reinforced regression》
---
作者：
Denis Belomestny, John Schoenmakers, Vladimir Spokoiny and Bakhyt
  Zharkynbay
---
最新提交年份：
2019
---
英文摘要：
  In this note we propose a new approach towards solving numerically optimal stopping problems via reinforced regression based Monte Carlo algorithms. The main idea of the method is to reinforce standard linear regression algorithms in each backward induction step by adding new basis functions based on previously estimated continuation values. The proposed methodology is illustrated by a numerical example from mathematical finance.
---
中文摘要：
在本文中，我们提出了一种通过基于强化回归的蒙特卡罗算法来解决数值最优停止问题的新方法。该方法的主要思想是，通过基于先前估计的连续值添加新的基函数，在每个反向归纳步骤中加强标准线性回归算法。数学金融学的一个数值例子说明了所提出的方法。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Numerical Analysis        数值分析
分类描述：Numerical algorithms for problems in analysis and algebra, scientific computation
分析和代数问题的数值算法，科学计算
--
一级分类：Computer Science        计算机科学
二级分类：Numerical Analysis        数值分析
分类描述：cs.NA is an alias for math.NA. Roughly includes material in ACM Subject Class G.1.
cs.na是Math.na的别名。大致包括ACM学科类G.1的材料。
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
PDF下载：
--> Optimal_stopping_via_reinforced_regression.pdf (188.6 KB)

2022-6-10 09:20:18 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Continuation Applications Quantitative Mathematical Computation

通过强化回归D实现最佳停车。贝洛梅斯特尼亚，b，*, J、 Schoenmakersc，V.Spokoinyb，c，B.ZharkynbaybaDuisburg Essen University，EssenbNational University Higher School of Economics，MoscowcWIAS，Berlina摘要本文提出了一种通过基于强化回归的蒙特卡罗算法来解决数值最优停止问题的新方法。该方法的主要思想是在每个反向归纳步骤中，通过基于先前估计的连续值添加新的基函数来加强标准线性回归算法。mathematica l-Finance的几个数值例子说明了所提出的方法。关键词：蒙特卡罗、最优停止、回归、加固2010 MSC:65C05、60H35、62P051。简介圆盘停留时间最优停车问题可以在低维情况下，通过树方法或对相应的偏微分方程使用确定性数值方法有效地解决。然而，应用程序中出现的许多最佳停止问题（参见例[1]）涉及高维底层过程，因此有必要开发蒙特卡罗方法来解决此类问题。通过蒙特卡罗方法解决最佳停车问题是一项具有挑战性的任务，因为这通常需要逆向动态编程，长期以来，人们认为逆向动态编程与蒙特卡罗方法的正向结构不兼容。近年来，许多研究集中于开发有效的方法来计算价值函数或最优运动策略的近似值。著名的例子包括[2]的函数优化方法、[3]的mes h方法、[4]、[5]、[6]、[7]和[8]的基于回归的方法。最流行的算法类型无疑是回归算法。

事实上，在许多实际的PricingProblem中，低阶多项式通常用于回归（见[1]）。由此产生的最小二乘问题有相对较少的未知数量这项工作得到了RSF拨款19-71-30020的支持*对应的authorEmail地址：denis。belomestny@uni-到期日。de（D.Belomestny）URL：www.uni-due。de/~ hm0124（D.Belomestny）预印本提交给乳胶模板杂志2019年7月2日参数。然而，这种方法有一个重要的缺点，即对于运动边界的高度非线性行为建模而言，其灵活性可能太小。可以使用高次多项式，但它们可能包含太多的参数，因此，要么超过蒙特卡罗样本，要么由于参数数量太多而无法进行参数估计。本文提出了一种基于回归的蒙特卡罗方法，用于在动态规划算法的每个后退步骤建立解析回归模型。这使得估计值函数的成本几乎与基于低阶多项式但精度更高的标准回归算法相同。额外的基函数是为手头的最优停止问题构造的，无需使用固定的预先定义的单位。具体而言，新的基函数是在后向诱导过程中通过合并前一个后向诱导步骤中的信息来学习的。我们的算法可以被视为构造基本值函数的稀疏非线性近似（根据其在蒙特卡罗路径上的依赖性）的方法，从这个意义上讲，它扩展了关于最优存储问题的非线性学习型算法的文献，例如，见最近的论文[9]和其中的参考文献。本文的结构如下。

在回顾了美式期权的基本事实并在第2节中解决了主要设置后，第3节中介绍了强化流程。第5.2节研究了数值性能。主要设置分别是一类一般的最优停止问题，可以针对基础Rd值马尔可夫过程（Xt，0≤ t型≤ T）在过滤概率空间上定义(Ohm, F、 （英尺）0≤t型≤T、 P）。流程（Xt）假设适用于过滤（Ft）0≤t型≤感觉每个X都是可测量的。回想一下，每个FTI都是Ohm 这样的话 英尺: F代表s≤ t、 此后，我们将自己限制在只有有限数量的停止机会0<t<t<…<tJ=允许的T区域。我们现在根据马尔可夫链Zj考虑预先规定的奖励过程gj（Zj）：=Xtj，j=1，J，对于某些给定的函数g，gJmapping Rdinto[0，∞). 设Tjdenote取{j，j+1，…，j}中的值的停止时间集，并考虑公式vj（x）=supτ的最优停止问题∈TjE[gτ（Zτ）| Zj=x]，x∈ Rd，（1）在（1）中，我们必须读取T：=tf或j=0。许多用于最优停止问题的近似算法的一个共同特征是，它们提供估计值CN，1（x），中国，J-1（x）对于所谓的连续函数：Cj（x）：=E[Vj+1（Zj+1）| Zj=x]，j=1，J- 1.（2）这里的指数N表示，上述估计是基于一组九个独立的“训练”轨迹（Z（i），Z（i）J），i=1，N、 （3）从一点开始的全明星赛。

对于所谓的回归方法，通过应用动态规划原理获得（1）和（2）的估计值：Cj（x）=E[Vj+1（Zj+1）| Zj=x]，Vj（x）=max（gj（x），Cj（x）），1≤ j≤ J- 1，VJ（x）=gJ（x），CJ（x）=0，结合非参数回归。在Tsitiklis van Roy【6】的设置中，这种回归算法可以描述如下。首先初始化CN，J（x）≡ 0.假设对于某些1≤j<j，已经构建了Cj+1（x）的估计值CN，j+1（x）。然后，在第j步中，需要估计条件期望值nE[VN，j+1（Zj+1））；Zj=x]，（4），其中VN，j+1（x）=max（gj+1（x），CN，j+1（x））。这可以通过在路径集（Z（i）j，VN，j+1（Z（i）j+1）），i=1，…，上执行非参数回归（线性或非线性）来实现，N、 （5）由于一系列bas is函数，导致估算值CN，j（x）。在Longstaff-Schwartz[5]的方法中，我们通过使用交错的“虚拟现金流”bV（i）jin集合进行回归来构建估计值CLSN、jsay。首先初始化，除了CLSJ≡ 0，bV（i）J：=gJ（Z（i）J），i=1。。。，N、 一旦为j+1建造了CLSN、j+1和BV（i）j+1≤ J，用VN，J+1（Z（i）J+1）替换为bv（i）J+1，通过（5）计算关于某一组基函数的回归估计CLSN，J。下一次更新bV（i）j=（gj（Z（i）j），gj（Z（i）j）≥ CLSN，j（Z（i）j）；bV（i）N，j+1，gj（Z（i）j）<CLSN，j（Z（i）j），对于i=1。。。，N（另见[1]）。考虑到估计值CN，1（x），中国，J-1（x）（Tsitiklis van Roy或Longstaff Schwartz），我们接下来可以构建一个较低的边界（低偏差估计），用于验证（通常次优）停止规则：τN=min1.≤ j≤ J:gj（Zj）≥ CN，j（Zj）,有CN，J≡ 定义为0。事实上，fix一个自然数可以模拟过程Z的最新独立轨迹。

然后可以将vc的低偏差估计构造为vntest，N=NtestNtestXr=1gτ（r）NZ（r）τ（r）k（6） τ（r）N=minn1≤ j≤ J:gj（Z（r）J）≥ CN，j（Z（r）j）o.（7）3。强化回归算法在本节中，我们概述了基于一组训练轨迹（3）在t=0时估计（1）解的方法。在这方面，作为一种新的成分，我们将通过学习并在后向层上合并新的基函数来加强标准回归程序。作为一个典型示例，可以考虑在估计Cj的回归步骤中合并VN，jas基函数-1、其他可能性，例如，Vj的某些（空间）导数，或与时间j的基本运动边界密切相关的函数，例如1{gj-CN，j}。通常，可以在每个步骤中选择（通常很小）数量的合适的增强基函数。3.1. 回归基础的后向强化假设我们手头有一些固定的和计算上的基函数奶酪系统（ψ（x），ψK（x））。现在，我们在每个反向回归步骤j中扩展此基础-1具有一组额外且稀疏的新函数vn，j-1.vN，j-1在给定的训练路径上，在前面的后退步骤j中构造的。其主要思想是，这样构造的基可以提供更精确的回归估计CN，j-1连续函数Cj-1、与原来的基础相比，同时保持便宜。3.2. 后向增强回归算法基于训练样本（3），我们提出了一种增强后向算法，其伪算法工作如下。在时间J，我们初始化CN，J（x）=0。

假设对于j<j，CN，jis已经在FORMCN中构造，对于某些γN，j（x）=KXk=1γN，jkψk（x）+bXk=1γN，jk+kνN，jk（x）∈ RK+b。用于从j>0下降到j- 1，定义新的强化回归基础iaψN，j-1（x）：=ψ（x），ψK（x），νN，j-1（x），νN，j-1b（x）（8） （作为行向量）由于函数集（νN，j）的选择-1.νN，j-1b）基于之前估计的连续值CN，j。例如，我们可以取b=1并考虑函数νn，j-1（x）=最大值（gj（x），CN，j（x））。（9） 然后考虑N×（K+b）设计矩阵Mj-1带有条目。Mj公司-1mk：=ψN，j-1k（Z（m）j-1） ，m=1，N、 k=1，K+b，（10）和（列）向量vj=VN，j（Z（1）j），VN，j（Z（N）j）(11)=最大值（gj（Z（1）j），CN，j（Z（1）j）），最大值（gj（Z（N）j），CN，j（Z（N）j））.下一步计算并存储γN，j-1:=Mj公司-1.Mj公司-1.-1.Mj公司-1.Vj，（12），然后setCN，j-1（x）=ψN，j-1（x）γN，j-1（13）=KXk=1γN，j-1kψk（x）+bXk=1γN，j-1k+KνN，j-1k（x）。备注1。为了确定回归步骤（11）-（12），根据西西里斯·范罗伊（TV）方法重新选择了回归步骤[6]。通过一些微小而明显的变化，强化回归方法也可以应用于Longstaff-Schwartz（LS）方法[5]。由于细节和复杂性分析非常相似，我们将自己局限于本文中的电视方法。3.3. 详细说明算法让我们在选择（9）加强函数的情况下详细说明上述伪算法（一般情况可以用类似的方法研究）。在预计算步骤中，我们首先生成并保存m=1，N、 值ψk（Z（m）j），gi（Z（m）j），1≤ j≤ 我≤ J，1≤ k≤ K、 （14）反向程序。在初始时间j=j时，我们设置CN，j：=0。

对于一般的后退步骤j<j，我们假设q数量cn，j（Z（m）l），0≤ l≤ j、 m=1。。。，N、 （15）以及系数γN，j∈ RK+1已经计算并存储，其中形式上CN，j（x）satifiescn，j（x）=KXk=1γN，jkψk（x）+γN，jk+1νN，j（x）（16）与νN，j=max（gj+1，CN，j+1）。现在让我们假设0<j≤ J，并继续到时间J- 1、我们首先计算（10）和（1 1）。对于l=j和预先计算的值（14），后者Vj由（15）直接获得。要计算（10），我们需要ψN，j-1K+1（Z（m）j-1） =νN，j-1（Z（m）j-1） ，m=1，N、 因此，我们设置νN，j-1（Z（m）j-1） =最大（gj（Z（m）j-1） ，CN，j（Z（m）j-1） ）对于m=1，N、 使用（15）表示l=j- 接下来，我们可以计算（并存储）系数向量（12），即γN，j-1，使用（10）和（11），并正式建立（16）。为了完成一般的后退步骤，我们现在需要评估cn，j-1（Z（m）l）=KXk=1γN，j-1kψk（Z（m）l）（17）+γN，j-1K+1νN，j-1（Z（m）l），（18）对于m=1。。。，N、 0个≤ l≤ j- 第一部分（17）直接从预计算（14）和在此步骤中计算的系数（12）中获得。对于第二部分（18），我们有νN，j-1（Z（m）l）=最大（gj（Z（m）l），CN，j（Z（m）l）），对于m=1，N、 和0≤ l≤ j- 因此，项（18）直接从（14）系数（12）和（15）中获得。备注2。（i） 跟踪整个集合（15）（而不是某些子集，例如j-1.≤ l≤ j） 在上述过程中，由于反向生成的附加基函数的所需结构，因此该过程是微妙而必要的。从更正式的编程角度来看，当从j到j时，这是逻辑递归不变量的一个自然要素- 1.（ii）可以看出，每个近似值CN，j-1非线性依赖于所有先前估计的连续函数CN，j，中国，J-因此，在所有“特征”（gl（Z（m）l），ψk（Z（m）l），k=1，K、 m=1，N、 l=j，j+1。

，J）。从这个意义上说，我们的程序基于模拟的“特征”为连续函数找到了稀疏非线性类型近似。与其他非线性学习型算法（参见，例如，[9]）相比，我们的过程不需要在高维参数空间上进行非线性优化。成本估算执行预计算所需的总成本（14）为bo utNJcf+NJ Kcf，其中CF表示评估每个函数的最大成本gj，j=0，J和ψk，k=1，K、 在给定点。从j到j的一个后退步骤的成本- 1可由上述byNKc估算*由于（12）NKjc的计算*由于（17）+（18）的构造，其中c*表示由于两个实数的加法和乘法而产生的成本之和。因此，上述算法的总代价可以是njcf+njkcf+njkc的上界*+NJKc公司*（19） 包括预计算。3.4. 基于新实现的较低估计假设第3.2节的反向算法已经实现，并且我们现在有一组独立的实现（eZ（m）j，j=0，J）EZ（m）=X，m=1，Ntest。鉴于（6）和（7），让我们介绍一下停止规则τN=minj：1≤ j≤ J，gj（Zj）≥ CN，j（Zj）. （20） 然后通过V获得Vis的较低估计：=NtestNtestXm=1gτ（m）NeZ（m）τ（m）N. （21）这里CN中的索引N，jin表示这些对象是使用（3.2）中使用的模拟样本构建的。因此，（20）是次优的停止时间，（21）是较低的有偏估计。让我们考虑（20）的计算。系数向量γN，j，1≤ j≤ 已经在上面的反向算法中进行了计算。我们现在必须考虑任意点Z的cn，j（Z）的计算∈ {eZ（m）j，m=1，…，Ntest}在特定时间j，对于1≤ j≤ J

为此，我们提出以下反向过程。计算任意状态Z1的CN，j（Z）的过程。我们首先（预先）计算1的ψk（Z）≤ k≤ K、 对于j<l，和gl（Z）≤ J，导致订单成本（K+（J- j） ）参见第2节。接下来递归计算CN，j（Z），如下所示：（a）初始化CN，j（Z）：=0。一次CN，l（Z），j<l≤ 计算并保存J，计算νN，l-1（Z）使用（9）。（b） 计算机，l-1（Z）=KXk=1γN，l-1kψk（Z）+γN，l-1K+1νN，l-1（Z）以订单成本Kc*. 通过这种方式，我们以（K+（j）的总成本一直向下到n，j（Z- j） ）cf+K（j）- j） c类*包括预计算步骤。根据上述程序，基于最差计算成本（20），评估（21）的成本将为NTestj Kcf+JNtestcf+NtestKJc*. （22）显然，（对于Ntest=N），这与第3.2.3.5节中描述的基于回归的反向诱导程序的顺序相同。成本比较标准与强化回归从强化回归算法的成本分析可以明显推断，标准回归程序，即基于固定基ψ的回归程序，ψk无需加固，将需要NJ Kcf+N J Kc订单的计算成本*（23）用于计算回归系数。作为加固方法的最终目标，我们将努力实现与标准化方法相当的精度，同时大大降低固定基础的基数。