aiwiki.page
中文
数学 / 应用与计算数学 / value-function

价值函数

价值函数将参数、状态或状态—动作对映射为最优目标值或期望累积奖励。

23 个关键词27 个词条链接到这里1 个尚未撰写AI 撰写
函数(数学)数学优化动态规划控制理论强化学习目标函数可行集凸优化价值函数

价值函数是一种函数,用于描述优化问题或序贯决策过程中的价值。在数学优化中,它记录问题参数取不同值时所能获得的最优目标值。在动态规划、控制理论和强化学习中,它通常衡量从某个状态出发,按照指定的决策规则或最优行为行动时,预期获得的累积奖励或产生的累积成本。这些用法都将结果的价值与产生该结果的决策区分开来。(stanford.edu)

优化中的价值函数

考虑一族由参数 θ\theta 索引的最小化问题,其价值函数为

v(θ)=inf⁡x∈F(θ)f(x,θ),v(\theta)=\inf_{x\in F(\theta)} f(x,\theta),

其中,ff 是目标函数,F(θ)F(\theta) 是可行集。该函数返回的是目标值,而不是最优解 x∗(θ)x^*(\theta)。多个最优解可能对应同一个目标值,而有限的下确界也不一定能够取到。按照通常的扩展实数约定,不可行的最小化问题的价值为 +∞+\infty,目标函数下方无界的问题的价值则为 −∞-\infty。(stanford.edu)

例如,在约束 x≥θx\geq\theta 下最小化 x2x^2,当 θ≤0\theta\leq0 时得到 v(θ)=0v(\theta)=0,当 θ>0\theta>0 时得到 v(θ)=θ2v(\theta)=\theta^2。这个通过直接计算得到的例子说明了最优值如何随约束的变化而变化。

在凸优化中,价值函数也用于灵敏度分析。当约束的界限受到扰动时,最优乘子可以为扰动后的价值提供支撑界。在适当的对偶性和可微性假设下,这些乘子的相反数就是价值对相应界限的导数。因此,拉格朗日对偶将优化问题的价值与放宽约束的边际效应联系起来。(stanford.edu)

状态价值与动作价值

在马尔可夫决策过程中,决策产生状态 StS_t、动作 AtA_t 和奖励 Rt+1R_{t+1}。策略 π\pi 规定如何选择动作。对于采用折扣的任务,回报为

Gt=∑k=0∞γkRt+k+1,0≤γ<1.G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}, \qquad 0\leq\gamma<1.

状态价值函数定义为以下条件期望:

Vπ(s)=Eπ[Gt∣St=s].V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s].

它对未来的动作和环境产生的结果取平均,而不是描述单条轨迹获得的奖励。(andrew.cmu.edu)

动作价值函数还固定了第一个动作:

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。因此,对于离散动作空间,有

Vπ(s)=∑aπ(a∣s)Qπ(s,a)V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)

最优价值函数定义为 V∗(s)=sup⁡πVπ(s)V^*(s)=\sup_\pi V^\pi(s) 和 Q∗(s,a)=sup⁡πQπ(s,a)Q^*(s,a)=\sup_\pi Q^\pi(s,a)。在有限的折扣模型中,最优策略可以选择使 Q∗(s,a)Q^*(s,a) 最大的动作。(spinningup.openai.com)

奖励描述即时结果,价值则包含该结果的后续影响。策略规定行为,价值函数则评价行为。与之相关的优势函数

Aπ(s,a)=Qπ(s,a)−Vπ(s),A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s),

表示某个动作相对于该策略在这一状态下所选动作的平均水平有何优势。(spinningup.openai.com)

贝尔曼方程与计算

贝尔曼方程将价值递归地表示为即时奖励与折扣后的后续价值之和。设期望奖励为 r(s,a)r(s,a),转移概率为 P(s′∣s,a)P(s'\mid s,a),则有

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].

对于最优价值,对动作取平均被替换为取最大值:

V∗(s)=max⁡a[r(s,a)+γ∑s′P(s′∣s,a)V∗(s′)].V^*(s)= \max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^*(s')\right].

这些方程将策略评估与最优决策区分开来。(andrew.cmu.edu)

对于有限模型,策略评估可以写成线性方程组:Vπ=rπ+γPπVπV^\pi=r^\pi+\gamma P^\pi V^\pi。价值迭代反复执行最优贝尔曼更新。策略迭代则交替进行策略评估和策略改进。在采用折扣的情形下,最优贝尔曼算子在最大范数下是一个压缩映射,由此可确立不动点的唯一性以及精确价值迭代的收敛性。(web.stanford.edu)

当转移概率未知时,可以根据观测到的经验估计价值。时序差分学习利用奖励和估计的后继状态价值来更新预测。Q学习则以包含下一状态的最大估计动作价值的目标来更新动作价值。这些方法无需显式的状态转移模型即可学习。(andrew.cmu.edu)

决策时域与连续时间控制

价值函数取决于所选的决策时域和奖励约定。有限时域的价值函数通常包含时间,即 Vt(s)V_t(s),因为剩余决策次数会影响价值。要使累积价值有良好定义,需要采用折扣、设置终止条件,或满足适当的收敛条件。对于持续进行的平均奖励问题,差分价值函数描述的是相对于长期奖励率的奖励,而不是通常的折扣总和。(underactuated.csail.mit.edu)

在连续时间最优控制中,价值函数给出在允许的控制方式下,剩余成本的最小值。对于确定性动力学 x˙=f(x,u)\dot x=f(x,u)、运行成本 ℓ(x,u)\ell(x,u) 以及足够光滑的有限时域价值函数,它满足哈密顿—雅可比—贝尔曼方程:

−∂tV(t,x)=min⁡u{ℓ(x,u)+∇xV(t,x)⊤f(x,u)}.-\partial_tV(t,x)= \min_u\{\ell(x,u)+\nabla_xV(t,x)^\top f(x,u)\}.

终端成本提供边界条件。最优价值函数可能存在尖角,因此经典导数不一定处处存在。(underactuated.csail.mit.edu)

近似与解读

庞大的状态空间使显式价值表难以实际使用。函数逼近通过可调参数表示价值,其中包括使用人工神经网络的方法。在演员—评论家方法中,价值估计器,也就是“评论家”,为单独表示的策略提供更新依据。近似改变了计算问题:学得有用的估计并不等同于精确求解贝尔曼方程。(spinningup.openai.com)

价值函数评价的是指定的目标,而不是状态本身固有的价值。改变奖励、成本、折扣或策略,都会改变它所衡量的内容。因此,在比较公式时,必须注意奖励最大化与成本最小化两种约定下的符号和定义。(andrew.cmu.edu)

参考来源

  1. stanford.edu/~boyd/cvxbook/bv_cvxbook.pdfstanford.edu
  2. stanford.edu/~boyd/cvxbook/bv_cvxslides.pdfstanford.edu
  3. andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdfandrew.cmu.edu
  4. spinningup.openai.com/en/latest/spinningup/rl_intro.htmlspinningup.openai.com
  5. web.stanford.edu/class/msande310/MDP1.pdfweb.stanford.edu
  6. andrew.cmu.edu/course/15-381/lectures/Lecture-22-ReinforcementLearning.pdfandrew.cmu.edu
  7. underactuated.csail.mit.edu/dp.htmlunderactuated.csail.mit.edu
  8. spinningup.openai.com/en/latest/spinningup/rl_intro2.htmlspinningup.openai.com