2.2　贝尔曼方程

马尔可夫决策过程为强化学习问题提供了基本的理论框架，几乎所有的强化学习问题都可以用马尔可夫决策过程（MDP）进行建模。2.1.3节介绍了马尔可夫决策过程的基本概念，本节介绍在求解马尔可夫决策过程问题时用到的最基础的方程——贝尔曼方程。可以说贝尔曼方程是强化学习算法的基石，因为后续章节介绍的几乎所有的算法，如动态规划、蒙特卡罗、时序差分等强化学习方法，都是基于贝尔曼方程来求解最优策略的。

贝尔曼方程（Bellman Equation），也称为动态规划方程，由理查·贝尔曼（Richard Bellman）发现。贝尔曼方程可以求解具有某种最优性质的问题，其基本思想是将待求解问题分解成若干个子问题，从这些子问题的解得到原问题的解。

本节介绍两类贝尔曼方程，分别为贝尔曼期望方程和贝尔曼最优方程。贝尔曼期望方程表达了当前值函数（或行为值函数）和它后继值函数（或行为值函数）的关系，以及值函数和行为值函数之间的关系。贝尔曼最优方程表达了当前最优值函数（或最优行为值函数）和它后继最优值函数（或最优行为值函数）的关系，以及最优值函数和最优行为值函数之间的关系。贝尔曼方程为后续各类以迭代方式求解值函数的方法打开了大门，如果知道下一个状态的值，就能很容易求解当前状态的值。

2.2.1　贝尔曼期望方程

1．贝尔曼方程推导

在介绍贝尔曼期望方程之前，先回顾值函数的定义。状态值函数V_π（s）表示从状态s开始，遵循当前策略π时所获得的期望回报，数学表示如下：

V_π（s）=E_π[G_t|S_t=s]=E_π[R_t+1+γ R_t+2+…|S_t=s]

对V_π（s）的定义公式进行推导：

最后一行将G_t+1变成了V（S_t+1），因为回报的期望等于回报期望的期望。经过推导将V_π（s）分解为两部分，第一项是该状态下立即回报的期望，该项是常数项，因此立即回报期望等于立即回报R_t+1本身；第二项是下一时刻状态值函数的折扣期望。

同样地，Q_π（s，a）的贝尔曼期望方程为

以上就是贝尔曼方程的最初形式。

2．贝尔曼期望方程

本节通过图形化的方式推导出贝尔曼期望方程的其他四种表达形式，这四种方程分别给出了状态值函数、行为值函数之间存在的关系。如图2-4所示，空心圆圈表示状态，实心圆点表示动作，状态指向动作表示在该状态下采取某种动作。动作指向状态表示在某动作下发生了状态转变。

（1）基于状态s，采取动作a，求取V_π（s）。

由图2-4可见，在遵循策略π时，状态s的值函数体现为在该状态下采取所有可能行为的价值Q_π（s，a）（行为值函数）与行为发生概率π（a|s）的乘积的和。数学表达式描述如下：

（2）采取行为a，状态转变至s'，求取Q_π（s，a）。

类似地，行为值函数也可以表示成状态值函数的形式。

在遵循策略π时，行为状态价值Q_π（s，a）体现为两项之和，如图2-5所示。第一项是采取行为a后，获得的立即回报，第二项是所有可能的状态值V_π（s'）乘以状态转移概率带衰减求和。

（3）基于状态s，采取行为a，状态转变至s'，求取V_π（s）。

如图2-6所示，将（1）和（2）的结果组合起来，可以得到V_π的第二种表示方法。

（4）采取行为a，状态转变至s'，采取行为a'，求取Q_π（s，a）。

如图2-7所示，同样将（1）和（2）的结果组合，得到Q_π（s，a）的第二种表示方法。

可通过求职马尔可夫决策过程例子对上述四种贝尔曼期望方程进行验证。如图2-8所示，圈内状态下面的数字表示状态对应的值函数，线条上Q_××表示状态行为对对应的行为值函数。策略为随机策略，折扣因子γ为1，状态转移概率如未特殊说明，为1。

（1）验证V_π（s）和V_π（s'）关系公式：

假设选择状态“强化学习”为研究对象，则此状态对应值函数V₄表示当前状态值函数V_π（s），V₄的下继状态值函数V₁、V₂、V₅表示下一步状态值函数V_π（s'）。

已知V₄=6.562 5，V₁=14.281 25，V₂=0，V₅=9.406 25，状态转换概率均为1/3。

根据公式，有

则公式得以验证。

（2）验证Q_π（s，a）和Q_π（s'，a'）关系公式：

假设选择状态“本职工作”为研究对象，则继续本职工作对应的状态行为对为（1，1），行为值函数为Q₁₁。令Q₁₁表示当前行为值函数Q_π（s，a），则Q₁₁的下继行为值函数Q₁₁、Q₁₂表示下一步的行为值函数Q（s'，a'）。已知Q₁₁=14.281 25，=0，Q₁₂=14.281 25，分别将各个取值代入公式，有

则公式得以验证。

（3）验证V_π（s）和Q_π（s，a）关系公式：

继续选择状态“强化学习”为研究对象，则此状态对应值函数V₄表示当前状态值函数V_π（s），下继行为值函数Q₄₁、Q₄₂、Q₄₃表示Q_π（s，a）。已知V₄=6.5625，Q₄₁=4.2812，Q₄₂=8，Q₄₃=7.406 25。根据公式，有：

则公式得以验证。

（4）验证Q_π（s，a）和V_π（s'）关系公式：

假设选择状态“本职工作”为研究对象，则继续本职工作对应的状态行为对为（1，1），行为值函数为Q₁₁。令Q₁₁表示当前行为值函数Q_π（s，a）。下继值函数V₁表示V_π（s'）。已知Q₁₁=14.281 25，V₁=14.281 25。根据公式，有：

Q₁₁=0+1*1*V₁=0+1*1*14.281 25=14.281 25

则公式得以验证。

3．贝尔曼期望方程矩阵形式

贝尔曼期望方程的矩阵形式表示为：

V_π=R_π+γ P_πV_π

其中，V_π为状态值矩阵；R_π为回报矩阵；P_π为状态转移矩阵；γ为折算因子，是一个常数。

结合矩阵的具体表达形式，可表示为：

对上述矩阵直接求解：

V_π=R_π+γ P_πV_π

（I-γ P_π）V_π=R_π

V_π=（I-γ P_π）-1R_π

注意　在进行矩阵求解时，要求（I-γ P_π）可逆。

也可以针对式（V（s）和V（s'）关系式，Q（s，a）和Q（s'，a'）关系式）列线性方程组，方程组中唯一的未知数是值函数（或行为值函数），其未知数的个数与方程组的个数一致，可求解。

下面以求职马尔可夫决策过程模型为例列线性方程组进行求解。设：[V₁，V₂，V₃，V₄，V₅]=[本职工作，人工智能工作，机器学习，强化学习，深度强化]

使用公式：

根据公式可以列出方程组：

求解方程组可得

直接求解仅适用于小规模的MDP。大规模求解通常使用迭代法，常用的迭代方法有动态规划、蒙特卡罗、时序差分，后面会逐步讲解这些方法。

2.2.2　贝尔曼最优方程

贝尔曼最优方程表达的是当前最优值函数（或最优行为值函数）和它后继最优值函数（或最优行为值函数）的关系，以及最优值函数和最优行为值函数之间的关系。

其中，最优值函数V*（s）是指在所有策略中最大的值函数，即

相应地，最优行为值函数Q*（s，a）是指所有策略中最大的行为值函数，即

接下来本节继续通过图形化的方式推导贝尔曼最优方程的四种表达形式，这四种表达形式分别给出了最优状态值函数、行为值函数之间的关系。同样地，空心圆圈表示状态，实心圆点表示动作，状态指向动作表示在该状态下采取某种行为。动作指向状态表示在某动作下，发生了状态转变。

（1）基于状态s，采取动作a，求取V*（s）。

如图2-9所示，当前状态的最优值函数V*（s）等于从该状态s出发，采取的所有行为中对应的那个最大的行为值函数。

（2）采取行为a，状态转变至s'，求取Q*（s，a）。

如图2-10所示，在某个状态s下，采取某个行为的最优价值Q*（s，a）由两部分组成，一部分是离开状态s的立即回报，另一部分则是所有能到达的状态s'的最优状态价值V*（s'）按出现概率求和：

（3）基于状态s，采取行为a，状态转变至s'，求取V*（s）。

如图2-11所示，将（1）和（2）的结果组合起来，得到V*（s）。

（4）采取行为a，状态转变至s'，采取行为a'，求取Q*（s，a）。

如图2-12所示，将（1）和（2）的结果组合起来，得到Q*（s，a）。

同样可以用求职马尔可夫决策过程的例子来验证上述四个公式。假设已经求得最优值函数和最优行为值函数，如图2-13和图2-14所示。

（1）验证V*（s）和V*（s'）关系公式：

假设以状态“本职工作”作为研究状态，表示最优值函数V*（s），的下继状态值函数表示后继最优值函数V*（s'）。已知，根据公式，有

则公式得以验证。

（2）验证Q*（s，a）和Q*（s'，a'）关系公式

继续选择状态“本职工作”为研究对象，则继续本职工作对应的状态行为对为（1，1），行为值函数为Q₁₁。令表示当前最优行为值函数Q*（s，a），的下继行为值函数、表示后继最优行为值函数Q*（s'，a'）。

根据公式，有

则公式得以验证。

（3）验证Q*（s）和Q*（s，a）关系公式：

继续以状态“本职工作”作为研究状态，表示最优值函数V*（s），的下继行为值函数表示Q*（s，a）。

根据公式，有：

则公式得以验证。

（4）验证Q*（s，a）和V*（s'）关系公式：

继续选择状态“本职工作”为研究对象，令表示当前最优行为值函数Q*（s，a），的下继值函数表示V*（s'）。

根据公式，有

则公式得以验证。

贝尔曼最优方程是非线性的，没有固定的解决方案，只能通过一些迭代方法来解决，如价值迭代、策略迭代、Q学习、Sarsa等，后续会逐步展开讲解。