aiwiki.page
中文
计算机 / 人工智能 / policy-evaluation

策略评估

策略评估利用环境模型、采样经验或两者结合,估计固定决策策略的期望累积奖励。

19 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
策略(强化学习)强化学习马尔可夫决策过程期望值价值函数贝尔曼方程动态规划时间复杂度策略评估

策略评估是确定某个固定策略在序贯决策环境中表现如何的任务。在强化学习中,它通常指计算或估计遵循该策略所获得的期望累积奖励,既可以从特定状态和动作出发,也可以从指定的初始状态分布出发。与旨在寻找更优策略的策略优化不同,策略评估将策略视为给定条件。它是许多学习与规划算法的核心组成部分,也是部署前比较不同决策系统的一种手段。

数学表述

标准设定是马尔可夫决策过程(MDP),它由状态、可用动作、转移概率、奖励以及奖励累积准则构成。平稳随机策略 π(a∣s)\pi(a\mid s) 指定了在状态 ss 下选择动作 aa 的概率。

对于折扣任务,从时刻 tt 开始的回报为

Gt=∑k=0∞γkRt+k+1,G_t=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1},

其中,Rt+k+1R_{t+k+1} 是后续获得的奖励,0≤γ<10\leq\gamma<1 是折扣因子。当奖励有界时,折扣可确保这一无穷和具有良好定义。

状态价值函数是以从特定状态出发、随后遵循该策略为条件的回报期望值:

vπ(s)=Eπ[Gt∣St=s].v_\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s].

动作价值函数还将第一个动作作为条件:

qπ(s,a)=Eπ[Gt∣St=s,At=a].q_\pi(s,a) = \mathbb{E}_\pi[G_t\mid S_t=s,A_t=a].

在第一个动作之后,后续动作均按 π\pi 选择。这是价值函数的两种形式:前者评估状态,后者评估状态—动作对。

评估也可以针对单一性能指标:

J(π)=ES0∼d0[vπ(S0)],J(\pi)=\mathbb{E}_{S_0\sim d_0}[v_\pi(S_0)],

其中,d0d_0 是初始状态分布。这一区别很重要:估计从典型初始状态出发的平均表现,可能比准确估计整个状态空间中的价值更容易。

其他回报准则

折扣回报并不是唯一的评估目标:

  • 有限时域回报对固定步数内的奖励求和。价值通常同时取决于状态和剩余时间。
  • 不折扣的回合回报对终止之前的奖励求和。需要对终止和奖励施加相应条件,才能确保期望回报有限。
  • 平均奖励衡量长期来看每个时间步获得的奖励。根据环境和策略的不同,这一数值可能取决于初始状态。其评估所用的方程与折扣评估不同,往往涉及相对价值函数或差分价值函数。

因此,只有先明确评估准则,才能对策略表现进行有意义的比较。

贝尔曼期望方程

策略评估利用了一种递归性质:一个状态的价值等于其即时奖励的期望值,加上后继状态价值期望值的折扣值。这一关系由贝尔曼方程中的期望形式表达:

vπ(s)=∑aπ(a∣s)[r(s,a)+γ∑s′P(s′∣s,a)vπ(s′)],v_\pi(s) = \sum_a \pi(a\mid s) \left[ r(s,a) + \gamma\sum_{s'}P(s'\mid s,a)v_\pi(s') \right],

其中,r(s,a)r(s,a) 是期望即时奖励,P(s′∣s,a)P(s'\mid s,a) 是转移概率。

对于有限状态空间,将策略诱导的奖励向量 rπr_\pi 和转移矩阵 PπP_\pi 定义为

rπ(s)=∑aπ(a∣s)r(s,a),r_\pi(s)=\sum_a\pi(a\mid s)r(s,a),
Pπ(s,s′)=∑aπ(a∣s)P(s′∣s,a).P_\pi(s,s')=\sum_a\pi(a\mid s)P(s'\mid s,a).

价值方程于是变为

vπ=rπ+γPπvπ.v_\pi=r_\pi+\gamma P_\pi v_\pi.

当 0≤γ<10\leq\gamma<1 时,它具有唯一解

vπ=(I−γPπ)−1rπ.v_\pi=(I-\gamma P_\pi)^{-1}r_\pi.

这一表达式表明,在表格表示下,固定策略的折扣评估是一个线性问题。实际实现通常直接求解线性方程组,而不是显式计算逆矩阵。

相应的动作价值方程为

qπ(s,a)=r(s,a)+γ∑s′P(s′∣s,a)∑a′π(a′∣s′)qπ(s′,a′).q_\pi(s,a) = r(s,a) + \gamma\sum_{s'}P(s'\mid s,a) \sum_{a'}\pi(a'\mid s')q_\pi(s',a').

这些是期望方程,而不是最优性方程:对未来动作的处理是在指定策略下取平均,而非选取使价值最大的动作。

模型已知时的评估

当转移概率和期望奖励已知时,策略评估可以采用动态规划或数值线性代数方法。

直接求解

对于有限 MDP,求解贝尔曼线性方程组即可得到价值,误差仅来自数值计算。通用的稠密矩阵直接求解器,其时间复杂度为状态数量的三次方,不过,稀疏性、问题结构和迭代式线性求解器都可能显著改变实际计算开销。

直接求解适用于中小规模模型,但在大型环境中,仅存储转移模型就可能超出可承受范围。

迭代策略评估

另一种方法是反复应用贝尔曼期望算子:

vk+1=Tπvk=rπ+γPπvk.v_{k+1}=T_\pi v_k = r_\pi+\gamma P_\pi v_k.

在有限状态的折扣设定下,该算子在最大范数下是压缩映射:

∥Tπu−Tπv∥∞≤γ∥u−v∥∞.\|T_\pi u-T_\pi v\|_\infty \leq \gamma\|u-v\|_\infty.

因此,从任意分量取值有限的初始价值向量出发,反复更新都会收敛到 vπv_\pi。更新既可以同步进行,即使用完整的上一轮向量;也可以异步进行,即对选定状态就地更新。异步收敛需要满足适当的更新条件,包括持续更新每个相关状态。

贝尔曼残差提供了一种衡量精度的方法:

∥v−vπ∥∞≤∥Tπv−v∥∞1−γ.\|v-v_\pi\|_\infty \leq \frac{\|T_\pi v-v\|_\infty}{1-\gamma}.

随着 γ\gamma 接近 1,这一界会变得更宽松,而奖励信息沿较长轨迹传播也可能需要更多轮迭代。

对于有限时域问题,后向归纳法从最后一个时间步向前推算,以评估策略,无须进行无限次迭代。

基于采样经验的评估

当无法获得环境模型时,可以根据观测到的状态转移或完整轨迹来估计价值。

蒙特卡洛评估

蒙特卡洛方法通过对观测回报取平均来估计价值。例如,首次访问评估对每个回合中某状态首次出现之后的回报取平均。

这种方法不需要转移概率,也不依赖已有的价值估计进行自举。不过,它通常需要完整结束的回合,或有合理依据的截断流程。过长或变动很大的轨迹可能使估计具有较高的方差。

在适当的采样条件和期望有限的条件下,样本均值会收敛到相应的期望回报。然而,策略很少访问的状态仍可能得不到准确估计。

时序差分评估

时序差分学习利用即时奖励和后继状态的估计价值来更新价值估计。单步 TD(0) 更新为

V(St)←V(St)+αt[Rt+1+γV(St+1)−V(St)],V(S_t)\leftarrow V(S_t) + \alpha_t \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right],

其中,αt\alpha_t 是步长。

方括号中的量称为时序差分误差。由于目标中包含 V(St+1)V(S_{t+1}),该方法采用了自举:它的学习部分依赖于自身当前的预测。

TD 方法可以在回合结束前更新,也适用于持续型任务。在标准的访问、奖励和步长条件下,表格型同策略 TD 会收敛。但这一保证并不能无条件地推广到函数逼近与离策略学习的任意组合。

多步方法和资格迹介于短程自举目标与较长程采样回报之间。它们的表现取决于采样噪声、自举误差和数据可用性之间的相互作用。

同策略评估与离策略评估

同策略评估使用由待评估策略生成的经验。离策略评估则使用由另一个行为策略生成的数据,估计目标策略的表现。

当收集新的交互数据代价高昂、受到限制,或可能产生重大后果时,离策略评估尤为重要。它在统计上也更具挑战,因为观测到的动作和状态分布与目标策略所诱导的分布不同。

重要性采样

重要性采样通过对观测数据重新加权,校正动作概率的差异。对于动作序列为 A0,…,AT−1A_0,\ldots,A_{T-1} 的有限轨迹,其轨迹权重为

ρ=∏t=0T−1π(At∣St)b(At∣St),\rho = \prod_{t=0}^{T-1} \frac{\pi(A_t\mid S_t)} {b(A_t\mid S_t)},

其中,bb 是行为策略。

在适当假设下,包括环境动态和初始状态分布相同,这一比值可将行为策略下的期望转换为目标策略下的期望。一个关键的覆盖条件是:对于相关轨迹中目标策略所需的动作,行为策略必须赋予其正概率。

概率比值的乘积可能具有极高的方差,在时域较长时尤其如此。逐决策加权、权重归一化和裁剪可以改善统计性质,但其中一些改动会引入偏差。

基于模型的评估与拟合评估

另一种思路是学习环境模型,并在该模型中评估策略。这种方法可以高效复用数据,但模型误差可能沿较长的模拟轨迹不断累积。

拟合 Q 评估则通过反复拟合以下形式的目标来学习动作价值函数:

y=r+γEa′∼π(⋅∣s′)[Qprevious(s′,a′)].y = r+\gamma\mathbb{E}_{a'\sim\pi(\cdot\mid s')} [Q_{\text{previous}}(s',a')].

它避免了显式学习转移概率。不过,对于覆盖不足的状态或动作,其预测可能不可靠;数据集上的拟合误差较低,也不意味着对目标策略表现的估计就准确。

双重稳健估计量将价值模型的预测与重要性加权修正相结合。在特定估计量所要求的假设下,只要相关价值模型或加权模型中有一个设定正确,就可能保证一致性。这类保证并不能免除覆盖要求,也不会自动确保有限样本误差较低。

函数逼近与规模扩展

在庞大或连续的状态空间中,分别用表格存储每个状态的价值并不现实。因此,评估会采用参数化近似,例如

vθ(s)≈vπ(s).v_\theta(s)\approx v_\pi(s).

可用的表示方式包括线性特征、树以及人工神经网络。函数逼近使跨状态泛化成为可能,但也改变了统计问题和收敛性质。

采用线性特征时,有些方法求解的是投影贝尔曼方程,而不是精确求解原方程。采用非线性模型时,优化问题可能是非凸的,预测误差也可能影响后续的自举目标。

函数逼近、自举和离策略学习的组合常被称为致命三要素,因为它可能导致不稳定或发散。这是对一类相互作用的警示,并不意味着所有结合这些要素的方法都会失败。

在学习与控制中的作用

策略评估源于动态规划和序贯决策理论。它是策略迭代的两个主要阶段之一:

  1. 评估当前策略。
  2. 利用所得价值改进策略。

精确策略迭代将这两个阶段分开进行,而许多实用算法则将不完全评估与策略改进交替进行。

在行动者—评论者方法中,评论者评估行动者的策略或相关价值量,行动者则调整策略。策略梯度方法常利用这些估计来降低梯度方差或估计优势。由于行动者在训练过程中不断变化,评论者可能始终在跟踪一个变化的目标,而不是完成对某个固定策略的评估。

策略评估还应与Q学习区分开来。后者的标准更新以最大化的动作价值为目标,旨在实现最优控制,而非评估任意给定的固定策略。

可靠性与局限性

评估结果以其奖励定义、时域、折扣因子、初始状态分布和环境为前提。即便针对同一个策略,采用不同设定的两次评估也可能回答不同的问题。

重要的局限性包括:

  • **覆盖不足:**日志数据中可能很少甚至完全没有关于目标策略倾向选择的决策的证据。
  • **分布变化:**数据收集与部署之间的分布偏移,可能使原本准确的估计失效。
  • **部分可观测性:**观测到的状态表示可能遗漏满足基于马尔可夫性质的评估假设所需的信息。
  • **未观测混杂:**在观测性日志中,动作选择可能依赖于评估者无法获得的信息,从而破坏常规离策略识别所需的条件。
  • **奖励设定不当:**即使回报估计准确,也未必衡量了所有值得关注的结果。
  • **选择效应:**从许多带噪声的估计中挑选表面上最优的策略,可能使报告的表现过于乐观。

单一的期望回报数值也无法描述结果的完整分布。期望回报相同的策略,在波动程度、罕见失败事件或不同初始状态下的表现方面,可能存在显著差异。因此,在数据和假设足以支持的情况下,统计报告还可以包含置信区间、结果分布,以及针对特定子群或状态的估计。