贝尔曼方程 · aiwiki.page

贝尔曼方程是一种递归关系，用即时奖励或成本以及剩余问题的价值来表示序贯决策问题的价值。它以理查德·贝尔曼的名字命名，是动态规划和强化学习的基础。它并不一次性优化整个决策序列，而是通过价值函数描述当前选择如何与未来结果相联系。贝尔曼在20世纪50年代建立了这一框架，并在1957年出版的《动态规划》中加以阐述。(incompleteideas.net)

最优性原理

该方程将贝尔曼的最优性原理形式化：在作出初始决策并到达相应状态之后，最优策略中剩余的决策，对于从该状态开始的问题而言，也必须是最优的。这体现了最优子结构，使递归求解成为可能。评价准则通常可以分解为各阶段的奖励或成本，并在适用时包含终端价值。(mit.edu)

状态必须包含足以确定未来可能情况的信息。在马尔可夫决策过程（MDP）中，马尔可夫性质意味着：给定当前状态和动作后，下一状态的分布不再额外依赖此前的历史。如果缺少必要信息，就可能需要扩充状态表示，才能使递归关系成立。(mit.edu)

策略评估

考虑一个有限MDP，其状态为 $s$ ，可选动作为 $a$ ，转移概率为 $P(s' \mid s,a)$ ，即时奖励的期望为 $r(s,a)$ 。平稳策略（强化学习） $\pi(a\mid s)$ 指定了选择各个动作的概率。对于折扣因子 $0\leq\gamma<1$ ，该策略的价值是折扣奖励序列之和的期望值：

V^\pi(s)= \mathbb E_\pi\!\left[ \sum_{k=0}^{\infty}\gamma^k R_{t+k+1} \;\middle|\;S_t=s \right].

将第一个奖励与剩余回报分开，就得到贝尔曼期望方程：

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

它用于评估给定策略，而不在不同动作之间进行优化。式中的期望同时考虑了动作选择和状态转移的不确定性。(incompleteideas.net)

对于有限状态空间，定义由策略诱导的转移矩阵 $P^\pi$ 和奖励向量 $r^\pi$ ，则有

V^\pi=r^\pi+\gamma P^\pi V^\pi, \qquad (I-\gamma P^\pi)V^\pi=r^\pi.

因此，策略评估归结为求解一个线性方程组，可以使用线性代数方法或迭代更新求解。这里的 $I$ 是单位矩阵。(mit.edu)

最优性方程

最优价值 $V^*(s)$ 是从状态 $s$ 出发所能获得的最大期望回报。其贝尔曼最优性方程为

V^*(s)= \max_a \left[ r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^*(s') \right].

与策略评估不同，由于存在最大化运算，该方程通常是非线性的。它将序贯数学优化问题归结为一个纳入后续最优价值的单步选择。在有限的折扣MDP中，在每个状态选择使上述表达式最大的动作，就能得到一个最优的确定性平稳策略。不同动作可能取得相同的最大值，因此最优价值唯一并不意味着最优策略也唯一。(gradml.mit.edu)

对于成本最小化问题，相应方程将奖励替换为成本，将 $\max$ 替换为 $\min$ 。在确定性系统中，对下一状态取期望简化为直接计算后继状态的价值。因此，该方程的适用范围并不限于随机决策问题。(underactuated.csail.mit.edu)

时间范围与边界条件

对于在时刻 $T$ 结束的问题，设 $g(s)$ 为终端奖励。有限时域的递归关系为

V_t^*(s)= \max_a\left[ r_t(s,a)+ \gamma\sum_{s'}P_t(s'\mid s,a)V_{t+1}^*(s') \right], \qquad V_T^*(s)=g(s).

价值和最优策略都可能随时间变化。计算从终端条件出发向前逐步回推，这是逆向归纳法的一种应用。与无限时域问题不同，有限时域问题可以取 $\gamma=1$ ，而无须要求无穷奖励之和收敛。边界条件在有终点的最短路径问题中同样重要，其中目的地的剩余成本通常为零。(mit.edu)

不动点与求解方法

最优性方程的右侧定义了一个贝尔曼算子 $T$ 。因此，该方程也是一个不动点条件，即 $V^*=TV^*$ 。对于奖励有界的有限折扣MDP，该算子在最大范数下是一个压缩映射：

\|TV-TW\|_\infty \leq\gamma\|V-W\|_\infty.

因此，它存在唯一的有界不动点。如果不采用折扣，或奖励无界，则存在性和唯一性需要额外假设；仅凭该方程本身无法保证其中任何一项。(stuff.mit.edu)

价值迭代反复应用算子 $T$ 。策略迭代则交替进行策略评估和策略改进，改进时选择使单步表达式最大的动作。两者都利用了同一递归结构，但贝尔曼方程本身刻画的是价值，而不是某一种具体的算法。(gradml.mit.edu)

学习、应用与局限

当转移概率未知时，时序差分学习利用观测到的状态转移，构造基于样本的贝尔曼更新。Q学习将最优性关系应用于动作价值，使用形如 $R+\gamma\max_{a'}Q(s',a')$ 的目标值。这些方法将动态规划与从经验中学习相结合，而不要求具备完整的状态转移模型。(web.mit.edu)

在控制理论中，连续时间下的对应形式是哈密顿–雅可比–贝尔曼方程，它是描述最优价值的微分方程。基于贝尔曼方程的方法可用于机器人学及其他序贯控制问题，但庞大的状态空间会使精确计算的代价高昂。函数逼近可以替代显式的价值表；不过，它也会改变数值求解问题，因此精确折扣更新的收敛保证不会自动适用于函数逼近。(underactuated.csail.mit.edu)