EM算法与经济学中的随机控制

，cT-1，以最大化他或她的效用最大值（c，θ，…，θT-（1）∈ΘE“T-1Xt=0ut+1（st+1，st，ct）c、 θ，θT-1#（4）s.t.ct=c（t，st，θt），t=0，1，T- 1，（5）st+1=ψt+1（st，ct，zt+1），t=0，1，T- 1，其中Θ是RN的子集，其中n=nc+（T-1） d；ut+1（·）是决策者在（t+1）时期的效用函数。值得注意的是，第一阶段的效用函数可以包括第0阶段的效用。一个比问题（4）更一般的控制问题由max（c，θ，…，θT）给出-（1）∈ΘE[u（s，c，s，c，…，sT-1，cT-1，sT）| c，θ，θT-1] （6）s.t.ct=c（t，st，θt），t=0，1，T- 1，st+1=ψt+1（st，ct，zt+1），t=0，1，T- 1，其中u（s，c，s，c，…，sT-1，cT-1，sT）是一个通用的效用函数，它可能不会像（4）中的函数那样在时间上是可分离的。为了便于说明，我们将给出问题（4）的ourEM-C算法；然而，EM-C算法也适用于一般问题（6）；详见附录D。为便于记法，我们表示x=（c，θ，θ，…，θT-1） 用U（x）表示问题（4）的目标函数：=U（c，θ，θ，…，θt-1） ：=E“T-1Xt=0ut+1（st+1，st，ct）c、 θ，θT-1#。（7） 一般来说，（7）中的期望值不能以闭合形式计算，因此U（x）没有解析形式。2.3 EM控制（EM-C）算法的描述在本小节中，我们概括了EM算法的思想，提出了用于求解（4）的EM控制（EM-C）算法。EM-C算法是一种迭代算法，涉及多轮前后更新。

EM-C算法继承了EM算法的精神，通过优化目标函数来更新给定时间段的控制策略，该目标函数仅针对该时间段的控制策略，并且所有其他时间段的控制策略固定在算法迭代中的最新状态。更准确地说，假设在（k）之后-1）第h次迭代，控制策略参数为xk-1： =（ck-1，θk-1，θk-1.θk-1吨-1） 。在第k次迭代中，EM-C算法更新xk-1为xk：=（ck，θk，θk，…，θkT-1） 根据更新规则：xk∈ M（xk-1） ，（8）其中M（·）是将映射设置在表示更新规则的Θ上的点（即，M（·）将Θ中的点映射到Θ的子集）。EM-C算法更新ck-1，θk-1，θk-1.θk-1吨-1及时后退；在每个时间段t=t- 1，T- 2.1，算法更新θk-1t为θkt，然后向后移动以更新θk-1吨-1.最后，算法更新ck-1确认。接下来，我们在（8）中指定精确的更新规则。在第k次迭代中，在周期t更新控制参数之前∈ {T-1，T-2.1} ，控制参数为（ck-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkt+2，θkT-1） 。然后，在周期t，em-C算法更新θk-1t为θkt，使得u（ck-1，θk-1，θk-1.θk-1吨-1，θkt，θkt+1，θkT-（1）≥ U（ck-1，θk-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1） ，（9）可以很容易地显示为等效toE“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θkt，θkt+1，θkT-1个#≥ E“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1#；（10） 详见附录A。因此，可以通过找到问题maxθt的次优（o最优）解决方案来获得满足（9）的θkt∈ΘtE“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θt，θkt+1。

，θkT-1#，其中Θt={θ∈ Rd |（ck-1，θk-1.θk-1吨-1，θ，θkt+1，θkT-（1）∈ Θ}。θk之后-1更新为θkt，控制策略参数更新自（ck-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1） 至（ck-1，θk-1，θk-1吨-1，θkt，θkt+1，θkT-1） 。类似地，在周期0，ck之前-1已更新，控制策略参数为（ck-1，θk，θkT-1） 。然后，EM-C算法更新ck-1使u（ck，θk，θk，…，θkT-（1）≥ U（ck-1，θk，θk，θkT-1） 。（11） 然后，从（ck）更新控制参数-1，θk，θkT-1） to（ck，θk，…，θkT-1） 。简而言之，算法1总结了用于解决问题（4）的EM-C算法。有两条注释：（i）在EM-C算法中，当我们更新θk时-1ttoθktor更新ck-1要检查，如果目标函数没有改进，我们只需设置θkt=θk-1或设置ck=ck-1.（ii）EM-C算法不使用动态规划原理（即Bellman方程）。相比之下，文献中的ADP算法是基于Bellman方程的。此外，由于EM-C算法不使用Bellman方程，因此它可以应用于效用函数不可时间分离的一般控制问题（6）。详见附录D。inNeal和Hinton（1999）对EM算法的直觉以及我们的EM-C算法的直觉也与块坐标下降（BCD）算法有关，在该算法中，坐标被划分为块，并且在迭代的每个子步中，仅以循环顺序更新一个坐标块。然而，算法的细节差别很大：（i）本质上，EM-C算法试图更新控制策略，就像EM算法一样，它可以被视为在函数空间（即（1）中的分布空间q）而不是实数空间中的广义BCD搜索。

这就是为什么EM-C算法的收敛性证明类似于EM算法的收敛性证明（如Wu（1983））。（ii）BCD方法用于最大化确定性目标函数，但算法1用于解决问题（4）1的EM-C算法。初始化k=1和x=（c，θ，θ，…，θT-1） 。2、迭代k，直到满足某些停止条件。在第k次迭代中，updatexk-1=（ck-1，θk-1，θk-1.θk-1吨-1） 至xk=（ck，θk，θk，…，θkT-1） 从t=t向后移动- 1到t=0，如下所示：（a）从t=t向后移动- 1至t=1。在每个周期t，更新θk-1t为θkt，使e“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θkt，θkt+1，θkT-1个#≥ E“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1#。这样的θkt可以设置为问题maxθt的次优（最优）解∈ΘtE“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θt，θkt+1，θkT-1#。（12） （b）在时段0，更新e ck-1确保-1Xj=0uj+1（sj+1，sj，cj）ck，θk，θkT-1个#≥ E“T-1Xj=0uj+1（sj+1，sj，cj）ck公司-1，θk，θkT-1#。这种CKC可以设置为问题MaxC的次优（最优）解∈ΘE“T-1Xj=0uj+1（sj+1，sj，cj）c、 θk，θkT-1#，（13）式中Θ={c∈ Rnc |（c，θk，…，θkT-（1）∈ Θ}。EM-C算法用于最大化随机效用函数的期望值（即（7）），通常无法对其进行分析评估。这就是为什么我们必须采用模拟和随机优化来实现EM-C算法（见第4节）。

（iii）EM-C算法在优化要求方面更加灵活。与BCD算法不同，EM-C算法不需要将控制参数更新为子问题（12）或（13）的精确最小值，也不需要根据目标函数的梯度更新控制参数，部分原因是，在EM-C算法可解的问题中，通常没有目标函数（即（7）），也没有目标函数的梯度可以通过分析来计算。（iv）EM-C算法的收敛性满足underweaker条件。BCD算法的收敛性是基于对目标函数的各种假设获得的，例如目标函数是凸的或是光滑函数和凸可分函数的和，或满足一定的可分性和正则性条件；相反，EM-C算法的收敛性证明类似于EM算法的收敛性证明，如Wu（1983）所述，该算法不需要对目标函数进行此类假设。详见第3节。3收敛性分析EM-C算法的收敛性与EM算法相似。首先，EM-C算法在每次迭代中都具有单调性。其次，在温和的假设下，迭代EM-C算法生成的目标函数值序列收敛到一个平稳值（即，在平稳点评估的目标函数值）或局部最大值。第三，EM-C算法迭代生成的控制参数序列在一些额外的正则性条件下收敛到一个平稳点或一个局部极大点。Luo和Tseng（1992）证明了当目标函数是两次连续可微的严格凸时，坐标下降（CD）算法的收敛性。Bertsekas（1999年，第二章。

2.7）显示了当每个子问题的精确最小值唯一且用于更新坐标块时，CD a算法的收敛性。Tsung（2001）研究了当目标函数具有一定的可分性和正则性，并且当每个子问题的精确极小值用于更新坐标块时，块CD方法的收敛性。Wright（2015）讨论了当目标函数为凸函数时，以及当坐标根据目标函数的梯度更新时，CD算法的收敛性。3.1单调性定理1。（7）中定义的目标函数U（·）在EM-C算法的每次迭代中单调递增，即U（xk）=U（ck，θk，θk，…，θkT-（1）≥ U（xk-1） =U（ck-1，θk-1，θk-1.θk-1吨-1） ，则，k、 （14）证明。见附录B。1.3.2{U（xk）}k的收敛性≥0到固定值或本地最大值let{xk}k≥0be由EM-C算法生成的控制参数序列。在本小节中，我们考虑U（xk）收敛到平稳值或局部最大值的问题。我们对（7）中定义的目标函数U（·）做出以下温和假设：对于任何x，U（x）>-∞, {x∈ Θ| U（x）≥ U（x）}是紧的。（15） U（·）在Θ中是连续的，在Θ内部是可区分的。（16） 需要假设（16），因为我们需要确定U（·）的固定点。假设目标函数U（·）满足（15）和（16）。那么，我们有{U（xk）}k≥对于U（x）>-∞. （17） 通过（14）和（17），U（xk）单调收敛于某个U*. 我们不能保证*是U onΘ的glo ba l最大值。

一般来说，如果目标函数uh有几个局部极大值和平稳点，则EM-C算法生成的序列收敛到哪种类型的点取决于起始点x的选择；EM算法也是如此。从X的点到X的子集的映射ρ称为在X上设置映射的点（Wu（1983））。设M为（8）中定义的EM-C算法的点对集映射。定义：=U（·）inΘ的局部极大值集，S：=U（·）inΘ的固定点集，M（a）：={x∈ M | U（x）=a}，（18）S（a）：={x∈ S | U（x）=a}。（19） 关于{U（xk）}k的收敛性，我们有以下定理≥0表示EM-C算法。定理2。提供满足条件（15）和（16）的目标函数。设{xk}k≥0be由xk生成的序列∈ M（xk-1） 在EM-C算法中。（1） 假设U（xk）>U（xk-1） 对于任何xk-1个/∈ S（分别为xk-1个/∈ M） 。（20） 然后，所有{xk}k的极限点≥0是U的平稳点（对应于局部极大值），U（xk）单调收敛于U*= U（x*) 对于s ome x*∈ S（分别为x*∈ M） 。（2） 假设在EM-C算法的每次迭代中，k和所有t，θkt和ck分别是问题（12）和（13）的最优解。然后，{xk}的所有极限点都是U的平稳点，U（xk）单调收敛于*= U（x*) 对于s ome x*∈ S、 证明。见附录B。2.3.3{xk}k的收敛性≥0到一个固定点或局部最大小点M（a）和S（a）分别在（18）和（19）中定义。在ORM2条件下，U（xk）→ U*{xk}的所有极限点都在S（U）中*) （分别为M（U*)).然而，这并不自动意味着{xk}k的收敛≥0到a点X*. 但是，如果S（U*) （分别为M（U*)) 由单个点x组成*, i、 e.，t此处不能是两个不同的固定点（分别为局部极大值），具有相同的U*, 然后下面的定理说xk→ x个*.

下面的定理还提供了xk→ x个*.定理3。设{xk}k≥0是满足定理2条件的EM-C算法的一个实例，并让U*是{U（xk）}k的极限≥0.（1）如果S（U*) = {x*} （分别为M（U*) = {x*}), 然后是xk→ x个*作为k→ ∞.（2） 如果kxk+1-xkk公司→ 0 a s k→ ∞, 然后，在S（U）的连通紧致子集中，xkare的所有极限点*) （分别为M（U*)). 特别是，如果S（U*) （分别为M（U*))是Discrete，即其唯一连接的组件是Singleton，然后XkConverge到一些x*以S（U）为单位*) （分别为M（U*)).证据见附录B。当然，从实用的角度来看，值函数{U（xk）}k的收敛性≥0到平稳值或局部最大值比{xk}k的收敛性更重要≥0.4 EM-C算法的实现4.1通过模拟EM-C算法来实现EM-C算法，我们需要找到问题（12）和（13）的次优（最优）解决方案。在实践中，这些问题的目标函数中的期望值可能无法以封闭形式进行评估，这使得解决这些问题变得困难。我们建议使用一种基于模拟的方法来解决这些问题，称为随机近似（SA）算法。SA是一种经典的迭代随机优化算法，它试图找到无法直接计算的期望值的零或极值。更准确地说，在EM-C算法的每次迭代中，使用currentpolicy模拟样本路径，然后应用SA在每个时间段查找控制策略的更新，以改进目标函数。在第k次迭代开始时，我们首先模拟N i.i.d.状态的样本路径（s、s、…、sT-1） 根据控制参数（ck-1，θk-1.θk-1吨-1） ，在（k）末尾获得- 1） 第次迭代。我们将这些采样路径表示为（s，sk1，l，sk2，l。

，skT-1，l），l=1，N、 SA算法由Robbins和Monro（1951）以及Kiefer和Wolfowitz（1952）提出。它已广泛用于强化学习，以改进时间差异方法中的政策（参见Chang、Fu、Hu和Marcus（2007））。有大量关于SA算法的文献；例如，参见Gu和Li（19 98）、Lai（2003）的调查论文以及Kushner和Yin（2003）和Spall（2003）的著作。Broadie、Cice k和Zeevi（2011）提出了一种SA算法，改进了k iefer-Wolfowitz算法的实时性能。然而，不必使用SA算法来实现我们的EM-C算法。其中一条渠道还使用了其他随机优化算法，如cro ss熵算法（Rubinsteinand Kroese（2004））。在算法1的步骤2（a）o中，我们应用SA算法来解决问题（12）。（12）目标函数中的期望值等于T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θt，θkt+1，θkT-1#=E（NNXl=1“ut+1（skt+1，l（θt），skt，l，ckt，l（θt））+t-1Xj=t+1uj+1（skj+1，l（θt），skj，l（θt），ckj，l（θt））），（21）其中ckt，l（θt）=c（t，skt，l，θt）（见（5））和（skt+1，l（θt），ckt+1，l（θt），skT公司-1，l（θt），ckT-1，l（θt），skT，l（θt））是一个模拟样本，从skT开始，然后遵循控制参数θt，θkt+1，θkT-1、SA算法使用▄f（θt）：=NNXl=1“ut+1（skt+1，l（θt），skt，l，ckt，l（θt））+t-1Xj=t+1uj+1（skj+1，l（θt），skj，l（θt），ckj，l（θt））#（22）作为解决问题时目标函数的近似值。因此，在SA算法的每次迭代中（在对应于该迭代的参数θt处），我们只需要模拟周期t+1到周期t期间的N个状态样本路径，即（skt+1，l（θt），skT公司-1，l（θt），skT，l（θt）），l=1，N、 样品skt，l，l=1。

，N对于SA算法的所有迭代都是相同的。在算法1的步骤2（b）中，我们应用SA算法来解决问题（13）。（13）中的期望值等于t oE“t-1Xj=0uj+1（sj+1，sj，cj）c、 θk，θkT-1#=E（NNXl=1“u（sk1，l（c），s，c）+T-1Xj=1uj+1（skj+1，l（c），skj，l（c），ckj，l（c）），（23），其中{（sk1，l（c），ck1，l（c），…，skT-1，l（c），ckT-1，l（c），skT，l（c））}Nl=1是N i.i.d.样本路径（s，c，…，sT-1，cT-1，sT），从砂开始模拟，然后遵循控制参数（c，θk，…，θkT-1） 。SA算法使用▄f（c）：=NNXl=1“u（sk1，l（c），s，c）+T-1Xj=1uj+1（skj+1，l（c），skj，l（c），ckj，l（c））#（24），作为解决问题时目标函数的近似值（13）。附录XC中描述了用于解决问题（12）和（13）的SA算法的详细信息。假设我们在SA算法中使用固定数量的m次迭代。然后，解决问题（12）和（13）的计算成本分别为O（m（T-t+1）和O（mT）。因此，EM-Calgorithm每次迭代的计算成本为O（mT）。4.2数值示例：一个简单的随机增长模型我们考虑一个简单的随机增长问题，如下所示Maxcte“Xt=0ut+1（st+1，st，ct）#=E”Xt=0log ct+log s#（25）s.t.st+1=st公司-st1+exp（ct）exp（a+bzt+1），t=0，1，2，s=1，ct∈ R、 t=0，1，2，其中a是常数，b>0是波动率，a和zt+1，t=0，1，2是具有标准正态分布的i.i.d.随机噪声。在第tth个时间段，amountst1+exp（ct）从资本st中消耗，剩余资本按倍数exp（a+bzt+1）增长。所有可用资本将在年底消耗掉（t=3）。该问题可以用以下最优控制和最优值函数解析求解C*t=对数（3- t） ，t=0，1，2，（26）V（s）=6a- 4对数4+4对数s。