面向风险规避马尔可夫决策过程的半光滑牛顿方法

《Automatica》：Semismooth newton methods for risk-averse Markov decision processes

　　

受半光滑牛顿方法启发，研究人员提出了一种通用框架，用于设计具有收敛性保证的风险规避马尔可夫决策过程（Markov Decision Processes, MDPs）求解方法。该框架利用马尔可夫相干风险测度（Markovian coherent risk measures）的假设，能够适应多种风险测度。为展示该框架的通用性和有效性，研究人员设计了三种具有收敛性保证的不同求解方法，且这些方法不限于特定的风险测度。此外，研究人员证明了风险规避策略迭代可以被解释为半光滑牛顿方法的一个实例，这一结果解释了其相较于风险规避值迭代的优越收敛性质。数值实验验证了该算法框架的有效性。本工作的核心贡献在于开发了一个受半光滑牛顿方法启发的算法框架，用于求解风险规避马尔可夫决策问题。马尔可夫决策过程是一种强大的数学工具，可用于建模来自金融到流行病学等不同领域的现实问题。马尔可夫决策过程框架中的最优决策通常通过动态规划（Dynamic Programming, DP）来解决，该方法由R. Bellman于20世纪50年代提出。经典动态规划仅处理期望性能准则，这些准则往往不适合作为性能度量，因为它们未考虑成本围绕均值的潜在波动及其对建模误差的敏感性。在许多应用中，与期望值的偏差会对系统性能产生不利影响，例如在金融和某些机器人应用中。风险规避动态规划用更一般的风险测度替代期望值，提供了一种量化风险和确保对建模误差鲁棒性的方法。这一变体带来了一些技术挑战：例如问题可能失去马尔可夫结构，破坏贝尔曼方程的递归形式，这造成了理论和计算上的障碍，需要针对特定风险测度专门设计求解方法。由于时间不一致性问题，构造动态规划公式和推导相应的贝尔曼算子可能很困难或不可能。Ruszczyński引入了马尔可夫相干风险测度的概念，并推导了折扣无限时域马尔可夫决策过程的风险规避贝尔曼方程扩展，从而定义了风险规避值迭代和策略迭代，它们与其风险中性对应物具有相似的收敛性质。许多研究者采用了这一框架，将马尔可夫相干风险测度作为满足风险规避马尔可夫决策过程贝尔曼最优性原理的时间一致替代物，使得能够以统一框架处理风险规避马尔可夫决策过程，并部署与风险中性动态规划相同的技术和逻辑。

本研究中，研究人员提出采用新视角来处理Ruszczyński提出的风险规避贝尔曼方程扩展的求解。特别是在风险中性情形下，策略迭代与半光滑牛顿方法之间的联系已带来重要的理论和算法洞见，并促进了求解大规模马尔可夫决策过程的新方法设计。受这些结果启发，研究人员研究了具有马尔可夫相干风险测度的风险规避马尔可夫决策过程的半光滑牛顿方法的部署。研究人员从Ruszczyński提出的框架出发，关注具有有限状态和动作空间的折扣无限时域马尔可夫决策过程这一类别。

研究人员的主要贡献包括：提出基于半光滑牛顿方法的新框架，用于设计具有马尔可夫风险测度的风险规避马尔可夫决策过程的新求解方法；部署该框架设计了三种不同的风险规避动态规划问题求解方法，并提供了其收敛性质的数学刻画；证明了Ruszczyński设计的193ms蜜芽吊的风险规避策略迭代方法本身是半光滑牛顿方法的一个实例，这一联系有助于解释该方法相对于风险规避值迭代的优越收敛性质；受风险中性动态规划方法启发，提出了所提方法的不精确变体并证明了其全局收敛性，该变体是乐观策略迭代的风险规避类比；定义了保证框架内方法快速二次局部收敛的充分局部结构性质。研究人员通过考虑条件风险价值（Conditional Value at Risk, CVaR）马尔可夫决策过程来展示框架的实用性，并研究了所提方法在此类风险规避马尔可夫决策过程上的经验性能。

符号说明方面，Sⁿ和S^n×n分别表示n维单纯形和n×n行随机矩阵集合。对于算子O:?ⁿ→?ⁿ、整数m>0和向量v∈?ⁿ，O^mv表示算子O对v应用m次。v⁽ⁱ⁾表示v的第i个分量。对于矩阵A∈?^n×m，[A]_i,:表示第i行。e表示?ⁿ中的全1向量，(t)₊=max{0,t}，其中t∈?ⁿ，max按元素理解。⊙表示元素级乘积，〈·,·〉:?ⁿ×?ⁿ→?表示内积。U_x表示x∈?ⁿ的邻域。

在问题设置方面，研究人员考虑具有有限状态和动作空间的折扣平稳马尔可夫决策过程，由五元组S, A, γ, P, g描述，其中S={1,…,n}和A={1,…,m}分别是状态和动作空间，γ∈(0,1)是折扣因子，P:S×A→Sⁿ是受控核，g:S×A→[-R,R]是阶段成本函数。允许在状态x∈X中采取的动作子集记为A(x)?A。可接受平稳确定性策略是映射π:X→A的函数。经典动态规划的目标是找到策略π∈Π，最小化目标函数。由于期望准则在许多实际问题中不适合度量性能，研究人员考虑用更一般的风险测度替代期望算子来建模风险规避。

研究人员考虑μ为Ruszczyński意义下的平稳马尔可夫风险测度。 consequently，对于由五元组定义的马尔可夫决策过程，存在风险转移映射χ:?ⁿ×Sⁿ→?，使得对于所有v∈?ⁿ和a_t∈A(x_t)，有μ(v(s_t+1))=χ(v,P(s_t,a_t))。马尔可夫假设对于公式化至关重要，没有这一假设，无法期望获得问题(3)的马尔可夫最优策略，因为一般风险测度可能依赖于过程的整个历史。

利用受控核P和对于任意(i,a)∈S×A，研究人员设定中存在闭且有界的凸分布集P^χ(P(i,a))?Sⁿ，使得对于所有v∈?ⁿ，有χ(v,P(i,a))=max_{p?∈P^χ(P(i,a))}〈v,p?〉=max_{p?∈P^χ(P(i,a))}??v，其中期望关于概率测度p?取值。这一重构具有引人注目的分布鲁棒解释：χ(v,P(i,a))可被视为在扰动分布集合中最坏分布下随机变量v(s_t+1)的期望，该集合由风险测度和马尔可夫决策过程的受控转移核共同塑造。

类似于风险中性情形，研究人员定义两个称为风险规避贝尔曼算子的算子。给定策略π:S→A，定义D_π:?ⁿ→?ⁿ为(D_πv)(i)=g(i,π(i))+γχ(v,P(i,π(i)))，i∈S，称为与π关联的风险规避贝尔曼算子。还定义最优性风险规避贝尔曼算子D:?ⁿ→?ⁿ为(Dv)(i)=min_a∈A(i){g(i,a)+γχ(v,P(i,a))}，i∈S。与风险中性情形不同，由于χ的潜在非线性和非光滑性，(7)不一定是线性或光滑的。

风险规避贝尔曼算子(7)、(8)是单调的且在无穷范数下是γ-压缩的。此外，问题(3)有唯一最小值v^*，它也是D算子的唯一不动点。给定策略π∈Π，(3)是D_π算子的唯一不动点。这些性质在引理1中总结。研究人员还在引理2中证明了风险规避贝尔曼算子具有常数平移性质。

利用(8)和Ruszczyński的结果，研究人员将(3)在策略集上的最小化等价地重写为v=Dv，当且仅当v=v^*时成立。动态规划包含(12)的求解方法。根据Banach定理，v的相应Picard-Banach迭代从任意v⁰∈?ⁿ线性收敛到v^*。该方法称为风险规避值迭代，其(k+1)次迭代为v_k+1=Dv_k。

求解(12)的替代方法是所谓的风险规避策略迭代方法，它将风险中性策略迭代算法推广到风险规避设置。该方案由Ruszczyński提出，通过用风险规避扩展替代风险中性贝尔曼算子。从v⁰∈?ⁿ开始，算法交替进行策略改进步骤和策略评估步骤。与风险中性策略迭代不同，策略评估步骤(15)需要求解潜在非光滑非线性方程组。假设每次迭代(15)精确求解，Ruszczyński证明生成的迭代序列非增且全局收敛到v^*，在无穷范数下速率为γ。

在第三章中，研究人员将(8)重写为求根问题v-Dv=0，其中r:?ⁿ→?ⁿ由于D算子的非线性和非光滑性而是非光滑非线性的。研究人员将r称为风险规避贝尔曼残差函数。由于(3)中风险测度的基本假设，风险规避贝尔曼残差函数以v^*为唯一根。

半光滑牛顿方法及其变体是数学分析中处理一般非光滑求根问题的主要工具。这些迭代方法用依赖于当前迭代的近似替代残差函数，得到更容易求解的近似问题以产生下一次迭代。将半光滑牛顿逻辑应用于求解(16)，给定迭代v_k，形成局部近似r(v_k)+ξ(v_k,d)，其中ξ(v_k,d)属于近似族Ξ(v_k)。

给定迭代v_k，存在d_k使得r(v_k)+ξ(v_k,d_k)=0，新的牛顿迭代设为v_k+1=v_k+d_k，其中v⁰∈?ⁿ。与Gargiani等人的讨论不同，研究人员不仅考虑线性近似，(17)也可能是非线性的。当可以计算其至少某些元素时，Ξ(v_k)的常见选择是集合{J_kd | J_k∈?r(v_k)}，其中?r(v_k)是r在v_k处的Clarke广义雅可比。

选择Ξ(v)的一般要求包括：对于所有v∈?ⁿ和所有ξ(v,·)∈Ξ(v)，有ξ(v,0)=0，且ξ(v,·)可逆且d(v)=ξ^-1(v,-r(v))是r(v)+ξ(v,d)=0的唯一解。这些条件通常不足以保证迭代(19)的收敛性，需要Ξ的额外更强条件和r固有的结构性质。

在定理3中，研究人员证明如果Ξ验证某些结构性质，则一般半光滑牛顿方法生成的序列在解的邻域内具有快速二次收敛速率。具体而言，假设对于每个ξ(v,·)∈Ξ(v)，ξ(v,·)是一致Lipschitz双射且具有一致Lipschitz逆，L_Ξ≥0是逆的Lipschitz模；且存在邻域U'_v*??ⁿ和常数C_Ξ≥0使得对于所有v∈U'_v*，有‖r(v)+ξ(v,v^*-v)-r(v^*)‖≤C_Ξ‖v-v^*‖²。那么，如果v⁰∈U''_v*，则序列{v_k}_k=0^∞Q-二次收敛到v^*。

研究人员随后介绍了风险规避贝尔曼残差函数(16)的三种不同近似族。首先引入两个辅助算子，然后用于定义近似。对于v?∈?ⁿ，定义T_v?:?ⁿ→?ⁿ为T_v?v=min_π∈Π{g_π+γP^π_v?v}，其中对于每个π∈Π，P^π_v?∈S^n×n是其第i行由P^π_v?i,:∈argmax_{p∈P^χ(P(i,π(i)))}〈p,v?〉定义的行随机矩阵。类似地，对于π?∈Π，引入算子T^π?_v?:?ⁿ→?ⁿ将v∈?ⁿ映射为T^π?_v?v=g_π?+γP^π?_v?v。这些算子可解释为具有(27)作为转移概率映射的马尔可夫决策过程的风险中性贝尔曼算子。

研究人员定义了以下三种风险规避贝尔曼残差函数的近似族：Ξ₁: ξ₁(v,d)=d+Dv-T_v(v+d)；Ξ₂: ξ₂(v,d)=d+Dv-D_π(v+d)，其中D_πv=Dv；Ξ₃: ξ₃(v,d)=d+Dv-T^π_v(v+d)，其中D_πv=Dv。引理5证明了所有三种近似都验证牛顿近似的基本要求。

在第四章中，研究人员考虑Ξ<1作为近似族。利用引理5的结果，得到r(v_k)+ξ₁(v_k,d_k)=v_k+1-T_vkv_k+1，因此该局部模型导致牛顿迭代v_k+1=T_vkv_k+1。每次成本更新需要求解一个风险中性马尔可夫决策过程，其中转移矩阵根据(27)计算。对于有限状态-动作马尔可夫决策过程，可以用风险中性策略迭代在有限次迭代内求解。该方法称为半光滑牛顿方法I（SNMI），通过求解具有不同转移概率矩阵的风险中性马尔可夫决策过程序列来求解原始风险规避马尔可夫决策过程。定理6证明了SNMI生成非递减迭代序列且全局收敛到(3)的最小化器。

在第五章中，研究人员考虑第二类函数Ξ<2，得到局部模型r(v_k)+ξ₂(v_k,d_k)=v_k+1-D^π_k+1v_k+1，其中D^π_k+1v_k=Dv_k。这导致牛顿迭代v_k+1=D^π_k+1v_k+1。由于(7)的潜在非线性和非光滑性，(43)需要求解依赖于风险转移映射具体选择的非平凡非光滑非线性方程组。该方法称为半光滑牛顿方法II（SNMII）。

研究人员指出，(43)可视为所考虑风险规避马尔可夫决策过程策略π_k+1的成本评估。后者是关于当前迭代v_k的风险规避贪婪策略。因此，该半光滑牛顿实例在风险规避场景中模仿风险中性策略迭代方法，交替进行策略改进步骤和策略评估步骤。迭代(43)与Ruszczyński提出的迭代相同。与标准策略迭代方案不同，策略评估步骤需要求解非线性非光滑方程组。Ruszczyński提出部署半光滑牛顿方法来完成此任务，产生内迭代。可以证明该内迭代全局收敛到(43)的唯一解。

进一步探索与策略迭代的并行性，研究人员模仿乐观策略迭代，不精确求解(43)，而是通过从当前迭代v_k开始用D^π_k+1算子执行有限次数的风险规避值迭代步骤来产生v^π_k+1的估计。这导致迭代v_k+1=(D^π_k+1)^w_kv_k，其中π_k+1是关于v_k的风险规避贪婪策略，w_k>0是使用的风险规避值迭代步骤数。定理7表征了所得序列的收敛性质，证明对于任意v⁰∈?ⁿ，序列收敛到v^*。

在第六章中，研究人员部署第三类函数，得到vk+1=Tπk+1vkvk+1，其中πk+1是关于vk的风险规避贪婪策略，满足Dπk+1vk=Dvk。与(34)、(43)需要求解非线性非光滑方程组不同，(58)是线性的。该方法称为半光滑牛顿方法III（SNMIII），其更新对应于具有(27)定义的转移矩阵的风险中性马尔可夫决策过程中策略πk+1相关成本的评估。SNMIII试图通过求解线性系统序列来找到(8)的根，每个系统对应于具有扰动转移映射的马尔可夫决策过程的策略评估，该映射基于当前成本向量在每次迭代时重新计算。

对于SNMIII，定理3的条件2归结为要求存在邻域和常数使得特定不等式成立，当算子为分段仿射时平凡成立，因为分段仿射函数是强半光滑的。为建立收敛性，定理6和定理7的论据不适用，因为若无额外假设，局部线性化会破坏单调性结构。尽管SNMIII的全局收敛仍是开放问题，定理8通过建立与分段光滑牛顿的联系表征了其局部收敛性质。对于任意v⁰∈?ⁿ，存在唯一序列满足算法4的迭代。此外，若χ:?ⁿ×Sⁿ→?关于第一个参数是1阶分段连续可微的，则存在v^*的邻域使得对于所有该邻域内的v⁰，序列Q-超线性收敛到v^*。命题9证明了CVaR关于其第一个参数是分段仿射函数，这允许研究人员得出所提SN方法在部署CVaR作为风险测度时满足局部Q-二次收缩的结论。

在计算考虑方面，算法1-4的每次迭代需要求解|S|×|A|个凸程序用于评估定义方法迭代的算子。虽然这些程序的目标函数总是线性的，可行域总是凸的，但其具体结构取决于风险测度的选择。除了这些凸程序外，每种方法每次迭代需要不同量的计算。这些凸程序相互独立，可以并行求解。具体而言，SNMI需要求解风险中性马尔可夫决策过程，可用风险中性策略迭代在少于mⁿ次迭代内完成。SNMII的内半光滑牛顿方法的每次迭代需要求解|S|维线性系统和重新评估转移映射。SNMIII每次迭代仅需求解|S|维线性系统。

在数值评估方面，研究人员以CVaR unemployed风险测度评估算法的数值性能。CVaR是风险管理中流行的数学工具，与VaR不同，它是相干风险测度，使优化更稳定高效。为评估算法，研究人员考虑状态和动作空间大小不同的马尔可夫决策过程，以及高(γ=0.9)和低(γ=0.1)折扣因子。基准测试表明所提SN方法在收敛速率和CPU时间方面具有可比性能。实验中发现SNMII及其热启动变体倾向于遭受数值不稳定性，特别是当内公差水平设得较低时迭代(44)无法实现收敛而导致振荡。另一方面，SNMI和SNMIII的收敛不受公差水平参数选择的影响，这使其对参数设置更鲁棒。

关于风险规避乐观策略迭代，如理论预期，执行的内迭代次数越多，以外迭代次数衡量的收敛速率越快。执行更多内迭代带来更高计算成本，最优内迭代次数代表收敛速率和计算成本之间的权衡。实验中风险规避乐观策略迭代以常数w_k=20是所研究设置中最佳的。然而，总体而言风险规避乐观策略迭代在总计算时间方面不具竞争力，即使对于低折扣因子也是如此。风险规避值迭代在两种设置中都有慢收敛速率，但在风险中性情况下其迭代计算廉价使方法具有竞争力，而在风险规避情况下额外计算成本破坏了这种权衡。

最后，研究人员指出对于所考虑的具有有限状态和动作空间的风险规避马尔可夫决策过程类别，半光滑牛顿方法具有快速收敛性质，而风险规避值迭代需要大量迭代才能达到相同收敛水平。与风险中性情形不同，慢收敛速率被廉价迭代所补偿，风险规避贝尔曼算子评估产生的额外计算成本对风险规避值迭代不利。

马尔可夫决策过程作为建模序贯决策问题的核心数学工具，在机器人、金融、流行病学等领域具有广泛应用。经典动态规划基于期望性能准则进行最优决策，然而该准则未能刻画成本围绕均值的波动以及对建模误差的敏感程度，导致在许多实际场景中可能出现性能劣化。风险规避动态规划通过引入风险测度替代期望算子以量化风险并确保鲁棒性，但时间不一致性等固有问题使得构造动态规划公式和贝尔曼算子面临理论及计算挑战，且现有方法多为针对特定风险测度的专门设计，缺乏统一框架。

针对上述问题，Gargiani、Micheli、Tsiamis和Lygeros在发表于《Automatica》的研究中提出了基于半光滑牛顿方法的风险规避马尔可夫决策过程统一求解框架。该框架利用马尔可夫相干风险测度假设，能够适应多种风险测度，克服了既有方法局限于特定风险测度的缺陷。

研究人员开展了以下主要工作并得出结论：首先，提出基于半光滑牛顿方法的新框架，用于设计具有马尔可夫风险测度的风险规避马尔可夫决策过程求解方法，该框架具有广泛的适用性。其次，基于该框架设计了三种不同的求解方法——半光滑牛顿方法I（SNMI）、半光滑牛顿方法II（SNMII）和半光滑牛顿方法III（SNMIII），并为每种方法提供了收敛性质的数学刻画。第三，证明了Ruszczyński提出的风险规避策略迭代方法本身是半光滑牛顿方法的一个实例，这一理论联系解释了其相对于风险规避值迭代的优越收敛性质。第四，受风险中性动态规划方法启发，提出了所提方法的不精确变体——风险规避乐观策略迭代，并证明了其全局收敛性。第五，定义了保证框架内方法快速二次局部收敛的充分局部结构性质。

该研究的重要意义在于：从半光滑牛顿方法的全新视角统一处理风险规避马尔可夫决策过程的求解问题，不仅深化了对现有方法收敛性质的理论理解，还为设计高效求解算法提供了系统性的方法论基础，有望促进风险敏感决策领域的大规模问题求解。

研究所用的主要关键技术方法包括：半光滑牛顿方法作为核心算法框架；马尔可夫相干风险测度作为时间一致的数学基础；Clarke广义雅可比和CD-正则性用于处理非光滑性；牛顿近似方案用于局部模型构造；分段光滑牛顿理论用于分析局部收敛性；以及条件风险价值作为具体的风险测度实例进行数值验证。

研究结果部分按以下结构展开：

关于SNMI的收敛性，通过构造辅助算子T_v?并建立其与风险中性贝尔曼算子的等价关系，利用单调性和压缩性证明SNMI生成非递减且有上界的迭代序列，从而全局收敛到最优成本v^*。

关于SNMII与策略迭代的关系，通过选择Ξ<2>近似族，证明所得迭代与Ruszczyński风险规避策略迭代的等价性，将风险规避策略迭代重新诠释为半光滑牛顿方法，从而利用牛顿方法的理论工具分析其收敛性质。

关于风险规避乐观策略迭代的全局收敛性，通过引入常数平移技巧和单调性论证，证明对于任意初始值，不精确求解策略评估步骤的算法仍能保证全局收敛，建立了风险中性乐观策略迭代向风险规避设置的自然推广。

关于SNMIII的局部超线性收敛性，在风险转移映射关于第一个参数为1阶分段连续可微的假设下，建立与分段光滑牛顿方法的联系，证明其作为后者实例的局部Q-超线性收敛，并以CVaR为具体情形验证了该条件的可满足性。

关于计算实现与数值性能，详细讨论了各方法每次迭代涉及的凸优化问题求解及并行化潜力，并通过人工生成的马尔可夫决策过程基准测试比较了各方法的CPU时间和迭代效率，验证了理论分析的正确性和框架的实用性。

在讨论与结论部分，研究人员总结指出：所提出的半光滑牛顿方法框架为风险规避马尔可夫决策过程提供了一套统一的算法设计方法论，三种具体实例——SNMI、SNMII和SNMIII——分别对应不同的计算效率与实现复杂度的权衡。特别是，将Ruszczyński的风险规避策略迭代识别为半光滑牛顿方法的实例，不仅从理论上解释了其优于值迭代的收敛表现，也为进一步优化该方法提供了思路。风险规避乐观策略迭代作为不精确变体，在保持全局收敛的同时提供了实施灵活性。数值实验在CVaR马尔可夫决策过程上的验证表明，所提方法在实际计算中具有可行性和效率，其中SNMI和SNMIII表现出对参数设置的较好鲁棒性。未来工作将致力于把所提方法整合至高性能分布式求解器中，以利用并行/分布式计算高效求解大规模风险规避马尔可夫决策问题。