关于折扣强化学习中优化确定性等价的样本复杂度

## 关于折扣强化学习中优化确定性等价量的样本复杂度 来源：https://arxiv.org/html/2605.21763 Mohammad Sadegh Talebi²²哥本哈根大学计算机科学系。电子邮件：[email protected]。 ###### 摘要 我们研究有限折扣MDP中的风险敏感强化学习，假设MDP的生成模型可用。我们考虑一类称为优化确定性等价量（OCE）的风险度量，其中包括重要风险度量如熵风险、CVaR和均值-方差。我们关注在递归OCE下学习最优状态-动作价值函数（价值学习）和最优策略（策略学习）的样本复杂度。我们精确刻画了相应的OCE定义PAC可学习目标所需的效用函数uu的特征。我们分析了一种简单的基于模型的方法，并推导出PAC样本复杂度界。我们证明，只要uu的定义域不是完整的（dom(u)≠R\text{dom}(u)\neq\mathbb{R}），相应的问题就不是PAC可学习的。最后，我们为价值学习和策略学习建立了相应的下界，证明在状态-动作空间大小SASA上的紧性，并且对于更受限的效用函数类，我们导出了显式依赖有效视界11−γ\frac{1}{1-\gamma}的下界。特别地，对于CVaRτ\text{CVaR}_{\tau}，我们表明对τ−1\tau^{-1}的正确依赖是1τ2\frac{1}{\tau^{2}}，相比现有最优结果提升了1τ\frac{1}{\tau}倍，尽管我们的界在11−γ\frac{1}{1-\gamma}上的依赖是次优的。

## 1 引言

在强化学习（RL）中，标准目标是最大化期望回报，定义为（可能折扣的）奖励总和[64 (https://arxiv.org/html/2605.21763#bib.bib22)]。然而，由于该目标本质上是*风险中性的*，在许多高风险应用领域可能不适用，例如治疗[20 (https://arxiv.org/html/2605.21763#bib.bib46)]、金融[58 (https://arxiv.org/html/2605.21763#bib.bib49), 9 (https://arxiv.org/html/2605.21763#bib.bib48)]、运筹学[16 (https://arxiv.org/html/2605.21763#bib.bib47)]和交通运输[35 (https://arxiv.org/html/2605.21763#bib.bib102)]。这些应用需要考虑回报的变异性及其风险。解决此局限的一种原则性方法是优化回报分布的风险度量。使用凹风险度量会导致良好定义的优化问题。值得注意的风险度量包括均值-方差[42 (https://arxiv.org/html/2605.21763#bib.bib2)]、风险价值（VaR）[17 (https://arxiv.org/html/2605.21763#bib.bib5)]、条件风险价值（CVaR）[59 (https://arxiv.org/html/2605.21763#bib.bib37)]、熵风险[29 (https://arxiv.org/html/2605.21763#bib.bib50)]和熵风险价值（EVaR）[2 (https://arxiv.org/html/2605.21763#bib.bib38)]，所有这些都已应用于广泛场景。其中，CVaR在MDP中建模风险敏感性方面变得特别流行[15 (https://arxiv.org/html/2605.21763#bib.bib51), 10 (https://arxiv.org/html/2605.21763#bib.bib52), 13 (https://arxiv.org/html/2605.21763#bib.bib53), 6 (https://arxiv.org/html/2605.21763#bib.bib54)]，主要因为它对回报的不良尾部提供了精细控制。ERM作为另一个流行概念，早就被考虑用于MDP和RL中的风险敏感控制[29 (https://arxiv.org/html/2605.21763#bib.bib50), 11 (https://arxiv.org/html/2605.21763#bib.bib32), 28 (https://arxiv.org/html/2605.21763#bib.bib31), 30 (https://arxiv.org/html/2605.21763#bib.bib23), 21 (https://arxiv.org/html/2605.21763#bib.bib25)]。然而，现有文献大多关注无折扣设置，尽管折扣MDP很普遍；例如，参见[7 (https://arxiv.org/html/2605.21763#bib.bib18), 28 (https://arxiv.org/html/2605.21763#bib.bib31), 50 (https://arxiv.org/html/2605.21763#bib.bib65)]作为显著例外。在本文中，我们研究折扣MDP的风险敏感RL，假设可以访问MDP的生成模型，该模型是一个模拟器，能够为任意状态-动作对生成真实MDP的样本。我们考虑一类广泛且重要的风险度量，包括那些可以表示为优化确定性等价量（OCE）的风险度量[8 (https://arxiv.org/html/2605.21763#bib.bib89)]。我们参考第2节 (https://arxiv.org/html/2605.21763#S2) 的定义，并参考附录A (https://arxiv.org/html/2605.21763#A1) 以获取关于风险度量的更详细入门。OCE度量类捕获了许多重要风险，如CVaR、ERM和均值-方差，作为特殊情况（这些情况在合适的效用函数选择下导出）。在风险敏感RL中，目标可以以两种方式表述：在*非递归*（也称为非迭代或静态）表述中，风险度量直接应用于总回报[12 (https://arxiv.org/html/2605.21763#bib.bib34), 11 (https://arxiv.org/html/2605.21763#bib.bib32), 27 (https://arxiv.org/html/2605.21763#bib.bib96)]；而在*递归*表述（也称为迭代、嵌套或动态）中，风险度量在每一步tt应用于剩余奖励[3 (https://arxiv.org/html/2605.21763#bib.bib16), 4 (https://arxiv.org/html/2605.21763#bib.bib10), 18 (https://arxiv.org/html/2605.21763#bib.bib69)]。非递归方法可能允许智能体访问高风险状态，尽管整个轨迹的风险仍受控制，但在许多安全关键应用中这可能不可接受。相反，递归方法通过在每一步控制风险可能导致更谨慎的行为，这根据应用可能要么是可取的，要么过于保守[18 (https://arxiv.org/html/2605.21763#bib.bib69), 68 (https://arxiv.org/html/2605.21763#bib.bib87), 66 (https://arxiv.org/html/2605.21763#bib.bib86)]。由于这些定性差异，两者被认为是正交的建模选择。从技术角度来看，一个关键区别是非递归表述通常不满足Bellman型最优性方程，并可能导致时间不一致的最优策略（参见[32 (https://arxiv.org/html/2605.21763#bib.bib44)]），而递归表述保留了Bellman型最优性结构。基于这些考虑，我们研究通过递归OCE定义目标的风险敏感折扣RL。

### 1.1 主要贡献

我们考虑生成设置中表格折扣MDP下递归OCE的风险敏感RL。学习性能以样本复杂度衡量，定义为给定(ε,δ)(\varepsilon,\delta)时，以超过1−δ1-\delta的概率获得ε\varepsilon-最优策略（*策略学习*问题）或ε\varepsilon-接近的最优Q值（在最大范数下，*价值学习*问题）所需的总样本数TT。我们做出以下贡献。我们提出一种基于模型的算法，称为基于模型的OCE值迭代（MB-OCE-VI），并在假设定义OCE的效用函数uu属于U1\mathbb{U}_1（本质上是具有全定义域的效用函数集合——关于更精确定义和背景，见2.1节 (https://arxiv.org/html/2605.21763#S2.SS1)）下，为其在价值学习和策略学习上的样本复杂度建立了PAC型界限（定理1 (https://arxiv.org/html/2605.21763#Thmtheorem1)）。这些界限在状态-动作空间大小SASA上的依赖是最优的（达到对数因子），并且对使用U1\mathbb{U}_1中效用函数定义的所有OCE目标同时成立。我们进一步表明，限制在关联于u∈U1u\in\mathbb{U}_1的OCE是必要的。我们通过建立当OCE由效用函数u∉U1u\notin\mathbb{U}_1定义时PAC样本复杂度界限的不可行性结果来证明这一主张。因此，我们提供了OCE度量的精确刻画，这些度量在价值学习和策略学习下是PAC可学习的。最后，我们建立了OCE下样本复杂度的最坏情况下界。对于每个问题，我们给出两个下界。第一个（定理6.1 (https://arxiv.org/html/2605.21763#S6.SS1) 和 6.2 (https://arxiv.org/html/2605.21763#S6.SS2)）是一个通用下界，适用于任何由u∈U1u\in\mathbb{U}_1定义的OCE。这些下界对S,A,1δ,εS,A,\frac{1}{\delta},\varepsilon的依赖是最优的（达到对数因子），但对1/(1−γ)1/(1-\gamma)的依赖复杂。第二个下界（定理6.1 (https://arxiv.org/html/2605.21763#S6.SS1) 和 6.2 (https://arxiv.org/html/2605.21763#S6.SS2)）显式依赖于1/(1−γ)1/(1-\gamma)，但仅对U1\mathbb{U}_1中的子类效用函数成立。然而，我们表明该子类包括所有强风险厌恶的相干OCE风险度量，其中显著包括CVaR。我们证明后一个下界在τ\tau非常小的机制下可以优于CVaRτ\text{CVaR}_{\tau}的最佳现有下界。据我们所知，这些结果构成了折扣MDP中递归OCE样本复杂度的首批上界和下界，也是RL中OCE下的首批不可行性结果。

### 1.2 相关工作

##### 风险中性折扣RL。 关于表格折扣MDP中可证明样本有效的学习算法有丰富的文献，涵盖多种设置，如生成设置[34 (https://arxiv.org/html/2605.21763#bib.bib41), 26 (https://arxiv.org/html/2605.21763#bib.bib30), 1 (https://arxiv.org/html/2605.21763#bib.bib15), 60 (https://arxiv.org/html/2605.21763#bib.bib56), 45 (https://arxiv.org/html/2605.21763#bib.bib28), 33 (https://arxiv.org/html/2605.21763#bib.bib82)]、离线（或批量）设置[55 (https://arxiv.org/html/2605.21763#bib.bib39), 43 (https://arxiv.org/html/2605.21763#bib.bib61)]和在线设置[63 (https://arxiv.org/html/2605.21763#bib.bib8), 40 (https://arxiv.org/html/2605.21763#bib.bib6)]。在我们也考虑的生成设置中，早期工作包括[34 (https://arxiv.org/html/2605.21763#bib.bib41), 36 (https://arxiv.org/html/2605.21763#bib.bib55)]，随后被一系列工作改进和跟进，特别是[26 (https://arxiv.org/html/2605.21763#bib.bib30), 60 (https://arxiv.org/html/2605.21763#bib.bib56), 67 (https://arxiv.org/html/2605.21763#bib.bib57), 44 (https://arxiv.org/html/2605.21763#bib.bib29), 33 (https://arxiv.org/html/2605.21763#bib.bib82)]。Azar等人[26 (https://arxiv.org/html/2605.21763#bib.bib30)]首次提供了价值学习和策略学习的极小化最优样本复杂度界O~(SAε2(1−γ)3)\widetilde{\cal O}\big(\frac{SA}{\varepsilon^{2}(1-\gamma)^{3}}\big)，尽管是针对相当受限的ε\varepsilon范围，这是由简单的基于模型方法达到的。此外，他们为价值学习建立了下界Ω~(SAε2(1−γ)3)\widetilde{\Omega}\big(\frac{SA}{\varepsilon^{2}(1-\gamma)^{3}}\big)。在更近期的后续工作中提出了无模型方法，如[60 (https://arxiv.org/html/2605.21763#bib.bib56), 67 (https://arxiv.org/html/2605.21763#bib.bib57), 33 (https://arxiv.org/html/2605.21763#bib.bib82)]。值得注意的是，[44 (https://arxiv.org/html/2605.21763#bib.bib29)]最近建立了适用于整个ε\varepsilon范围的最优界，使用了基于经验MDP但带有奖励扰动或保守规划的基于模型方法。我们注意到，现有最优样本复杂度依赖于充分利用回报相对于奖励的可加性的技术；这种结构性质通常对风险敏感目标不成立，相应的技术也不适用。

##### 风险敏感RL。 在赌博机和RL设置中，关于基于风险度量决策的文献很丰富。在赌博机中，风险敏感目标通常通过遗憾最小化来研究；例如，参见[57 (https://arxiv.org/html/2605.21763#bib.bib62), 47 (https://arxiv.org/html/2605.21763#bib.bib63), 37 (https://arxiv.org/html/2605.21763#bib.bib64)]。扩展到MDP引入了更丰富的结构和算法挑战。关于风险度量下RL的文献可以大致按风险度量的应用方式（递归 vs. 非递归）以及所研究的风险度量类型进行分类。代表性例子包括CVaR[18 (https://arxiv.org/html/2605.21763#bib.bib69), 19 (https://arxiv.org/html/2605.21763#bib.bib70), 14 (https://arxiv.org/html/2605.21763#bib.bib71), 39 (https://arxiv.org/html/2605.21763#bib.bib74)]、ERM[11 (https://arxiv.org/html/2605.21763#bib.bib32), 51 (https://arxiv.org/html/2605.21763#bib.bib95), 49 (https://arxiv.org/html/2605.21763#bib.bib66), 48 (https://arxiv.org/html/2605.21763#bib.bib67), 28 (https://arxiv.org/html/2605.21763#bib.bib31)]、均值-方差风险[62 (https://arxiv.org/html/2605.21763#bib.bib100), 31 (https://arxiv.org/html/2605.21763#bib.bib101), 38 (https://arxiv.org/html/2605.21763#bib.bib73)]和EVaR[53 (https://arxiv.org/html/2605.21763#bib.bib92), 25 (https://arxiv.org/html/2605.21763#bib.bib103)]。其中，CVaR是研究最广泛的。在递归CVaR下，[18 (https://arxiv.org/html/2605.21763#bib.bib69)]分析了生成设置中的样本复杂度并给出了下界。在递归ERM下，最近的如[21 (https://arxiv.org/html/2605.21763#bib.bib25), 22 (https://arxiv.org/html/2605.21763#bib.bib27), 23 (https://arxiv.org/html/2605.21763#bib.bib26), 30 (https://arxiv.org/html/2605.21763#bib.bib23), 46 (https://arxiv.org/html/2605.21763#bib.bib24)]在遗憾设置中研究了在线情节RL。据我们所知，现有关于递归ERM下折扣MDP的工作仅限于规划；一个显著例子是[4 (https://arxiv.org/html/2605.21763#bib.bib10)]，它提供了彻底的理论处理但没有提出学习算法。存在一系列风险敏感RL和控制方面的工作，为整个风险度量族开发算法。在此背景下研究的两类重要家族是相干风险度量和OCE。虽然熵风险不是相干的，但它属于OCE；附录A (https://arxiv.org/html/2605.21763#A1)提供了风险度量的简要概述。现有关于OCE风险的结果[66 (https://arxiv.org/html/2605.21763#bib.bib86), 68 (https://arxiv.org/html/2605.21763#bib.bib87), 56 (https://arxiv.org/html/2605.21763#bib.bib97), 41 (https://arxiv.org/html/2605.21763#bib.bib4)]没有解决折扣MDP中递归熵风险下可证明样本高效的学习问题。此外，针对相干风险的结果[54 (https://arxiv.org/html/2605.21763#bib.bib77), 65 (https://arxiv.org/html/2605.21763#bib.bib72), 39 (https://arxiv.org/html/2605.21763#bib.bib74), 69 (https://arxiv.org/html/2605.21763#bib.bib93)]不适用于熵风险。特别地，[56 (https://arxiv.org/html/2605.21763#bib.bib97)]考虑了递归OCE下折扣MDP的离线RL，但没有提供样本复杂度保证。我们还注意到，递归相干风险MDP与分布鲁棒MDP之间的关联已在[4 (https://arxiv.org/html/2605.21763#bib.bib10)]中建立。

## 2 设置：递归OCE下的RL

##### 符号。 对于n∈Nn\in\mathbb{N}，令[n]:={1,...,n}[n]:=\{1,\ldots,n\}。1A\mathbbmss{1}