上一节介绍了马尔可夫奖励过程中(Markov Reward Process,MRP) 出现的概念，本节引入贝尔曼期望方程，讲述马尔可夫决策过程(Markov Decision Process, MDP)的逻辑具体是如何实现的。

在介绍马尔可夫奖励过程(MRP)内容中，讲述了马尔可夫决策过程(MDP)的逻辑场景及相关概念，在这里做一个简单回顾：

在本节中，重新对各概念和条件进行设定；

状态(State) 设置为离散型随机变量，由 n n n种状态构成， S \mathcal S S表示状态集合， S ( k ) S^{(k)} S(k)表示状态集合 S \mathcal S S中编号为 k k k的状态， s , s ′ s,s' s,s′均表示某种具体状态； S = { S ( 1 ) , S ( 2 ) , . . . , S ( n ) } , s , s ′ ∈ S \mathcal S=\{S^{(1)},S^{(2)},...,S^{(n)}\},s,s' \in \mathcal S S={S(1),S(2),...,S(n)},s,s′∈S

动作(Action) 设置为离散型随机变量，由 m m m种动作构成， A \mathcal A A表示动作集合， A ( k ) A^{(k)} A(k)表示动作集合 A \mathcal A A中编号为 k k k的动作， a , a ′ a,a' a,a′表示某种具体动作； A = { A ( 1 ) , A ( 2 ) , . . . , A ( m ) } , a , a ′ ∈ A \mathcal A=\{A^{(1)},A^{(2)},...,A^{(m)}\},a,a' \in \mathcal A A={A(1),A(2),...,A(m)},a,a′∈A

奖励(Reward) 设置为离散型随机变量，由 s s s种奖励构成， R \mathcal R R表示奖励集合， R ( k ) R^{(k)} R(k)表示奖励集合 R \mathcal R R中编号为 k k k的奖励， r r r表示某种具体奖励； R = { R ( 1 ) , R ( 2 ) , . . . , R ( s ) } , r ∈ R \mathcal R=\{R^{(1)},R^{(2)},...,R^{(s)}\},r \in \mathcal R R={R(1),R(2),...,R(s)},r∈R

针对“状态转移过程中”转移到各状态的具体概率(当前状态转移到其他状态(含自身)的概率信息)：

马尔可夫决策过程(MDP)的核心在于执行过程中，找到最优的策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s); 策略是如何表示/描述的？ 我们从动作(Action)的角度解释策略； 上一节中，我们介绍了两种策略：

通过对确定性策略/随机性策略的描述，我们发现任意动作 a a a都不是独立存在并发生的，而是伴随着状态 s s s而产生的； 换句话说，是在状态 s s s的条件下 → \to →选择某种动作 a a a作为当前时刻的待执行动作。

示例： 前提条件：某决策过程中，动作集合 A \mathcal A A中包含3种动作；状态集合 S \mathcal S S中包含2种状态； A = { A ( 1 ) , A ( 2 ) , A ( 3 ) } , S = { S ( 1 ) , S ( 2 ) } \mathcal A = \{A^{(1)},A^{(2)},A^{(3)}\},\mathcal S = \{S^{(1)},S^{(2)}\} A={A(1),A(2),A(3)},S={S(1),S(2)} 假设一：确定性策略； 若当前状态是 S ( 1 ) S^{(1)} S(1),只能唯一确定地选择 A ( 3 ) A^{(3)} A(3); 基于上述假设，根据确定性策略， S ( 1 ) S^{(1)} S(1)状态下动作选择的概率分布如下表：

表格中描述的概率分布就是一种确定性策略(Deterministic Policy)。 假设二：随机性策略： 若当前状态是 S ( 2 ) S^{(2)} S(2),动作集合 A \mathcal A A中存在2种动作可以选择 → A ( 1 ) , A ( 3 ) \to A^{(1)},A^{(3)} →A(1),A(3),并且各动作被选择的概率分布如下：

同假设一，上述表格描述的也是一种策略 → \to → 随机性策略(Stochastic Policy)

在判定一个策略 π \pi π的优劣性时，假设状态转移矩阵 p ( s ′ , r ∣ s , a ) = 1 → p(s',r\mid s,a)=1 \to p(s′,r∣s,a)=1→此时是一种确定性环境(Deterministic Environment) → \to →只能唯一地选择下一个确定的状态； 基于上述条件下，可以直接使用回报(Return) G t G_t Gt​直接作为评价标准 → \to → 哪个状态的回报结果大，就选择该状态对应的策略； 但在实际情况中，由于状态转移概率的存在(下一时刻状态的选择存在概率分布)，智能体从当前状态到最终状态可能存在多种状态序列 → \to → 每个状态序列内有若干不同的回报 G t G_t Gt​，因而没有办法直接用 G t G_t Gt​比较的方式来确定策略。

换一种思路： 根据状态转移矩阵的定义 → \to →当前状态 S t S_t St​到下一时刻状态 S t + 1 S_{t+1} St+1​的可能性的分布；我们将这种可能性作为权重，使用回报的期望(回报与可能性的加权和)作为策略的评价指标： 期望值越大 → \to → 选择高回报状态的概率就越大 → \to → 引入价值函数(Value Function) 来改进策略。

价值函数表示当前时刻 t t t状态 S t S_t St​确定的情况下，对策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)的综合性考量。我们从2种角度对策略进行评判：

状态价值函数表示当前时刻 t t t状态 S t = s S_t=s St​=s开始，智能体采取策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)得到的期望回报。 V π ( s ) = E π [ G t ∣ S t = s ] V_\pi(s)=E_\pi[G_t \mid S_t=s] Vπ​(s)=Eπ​[Gt​∣St​=s] 我们称 V π ( s ) V_\pi(s) Vπ​(s)是策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)的状态价值函数。可以发现，状态价值函数只包含1个变量 s s s，因此状态价值函数是由状态 s s s所具有的价值决定的。

状态动作价值函数表示从当前时刻 t t t状态 S t = s S_t=s St​=s开始，智能体遵循策略 π ( a ∣ s ) → \pi(a \mid s) \to π(a∣s)→ 执行动作 a a a之后的期望回报。 q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] \begin{aligned} q_\pi(s,a) & =E_\pi[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ \end{aligned} qπ​(s,a)​=Eπ​[Gt​∣St​=s,At​=a]=s′,r∑​p(s′,r∣s,a)[Gt​∣St​=s,At​=a]​ 我们称 q π ( s , a ) q_\pi(s,a) qπ​(s,a)是策略 π \pi π的状态动作价值函数。可以发现该函数中包含两个变量 s s s、 a a a,因此状态动作价值函数是由当前状态 s s s和动作 a a a的共同价值决定的。

我们通过观察发现， q π ( s , a ) q_\pi(s,a) qπ​(s,a)就是在 V π ( s ) V_\pi(s) Vπ​(s)的基础上选择了某个具体动作 a a a产生的回报结果；换句话说， V π ( s ) V_\pi(s) Vπ​(s)是 s s s状态下的策略中所有可能发生的动作 a a a对应的 q π ( s , a ) q_\pi(s,a) qπ​(s,a)的加权平均。 通过上面的推演，我们获得 V π ( s ) V_\pi(s) Vπ​(s)和 q π ( s , a ) q_\pi(s,a) qπ​(s,a)之间的关系： V π ( s ) = ∑ a ∈ A π ( a ∣ s ) [ G t ∣ S t = s , A t = a ] = ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) \begin{aligned} V_\pi(s) & = \sum_{a \in \mathcal A} \pi(a \mid s) [G_t \mid S_t=s,A_t=a] \\ & = \sum_{a \in \mathcal A} \pi(a \mid s) q_\pi(s,a)\\ \end{aligned} Vπ​(s)​=a∈A∑​π(a∣s)[Gt​∣St​=s,At​=a]=a∈A∑​π(a∣s)qπ​(s,a)​ 此时， V π ( s ) V_\pi(s) Vπ​(s)可以使用 q π ( s , a ) q_\pi(s,a) qπ​(s,a)表示了，反过来， q π ( s , a ) q_\pi(s,a) qπ​(s,a)是否可以用 V π ( s ) V_\pi(s) Vπ​(s)表示呢？ 继续观察： 按照逻辑场景，在执行 a a a之后，系统必然将当前状态 S t = s S_{t}=s St​=s转移到下一时刻状态 S t + 1 S_{t+1} St+1​,假设下一时刻状态转移到 s ′ s' s′，我们观察 S t + 1 S_{t+1} St+1​的状态价值函数是如何表示的？ V π ( S t + 1 = s ′ ) = E π [ G t + 1 ∣ S t + 1 = s ′ ] V_\pi(S_{t+1}=s')=E_\pi[G_{t+1} \mid S_{t+1} =s'] Vπ​(St+1​=s′)=Eπ​[Gt+1​∣St+1​=s′] 从公式组成上和 V π ( s ) V_\pi(s) Vπ​(s)没什么区别，只是下标增加了1。我们将 G t + 1 G_{t+1} Gt+1​进行展开： G t + 1 = R t + 2 + γ R t + 3 + γ 2 R t + 4 + . . . G_{t+1} = R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + ... Gt+1​=Rt+2​+γRt+3​+γ2Rt+4​+... 再类比一下 G t G_{t} Gt​的展开式： G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . G_{t} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... Gt​=Rt+1​+γRt+2​+γ2Rt+3​+... 我们发现，实际上 G t G_t Gt​和 G t + 1 G_{t+1} Gt+1​之间存在如下关系： G t = R t + 1 + γ G t + 1 G_t = R_{t+1} + \gamma G_{t+1} Gt​=Rt+1​+γGt+1​ 得到如下关系，重新对 q π ( s , a ) q_\pi(s,a) qπ​(s,a)进行展开： q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ V π ( s ′ ) ) \begin{aligned} q_\pi(s,a) & =E_\pi[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[r + \gamma G_{t+1} \mid S_{t+1}=s',A_{t+1}=a'] \\ & = \sum_{s',r} p(s',r \mid s,a)(r + \gamma V_\pi(s'))\\ \end{aligned} qπ​(s,a)​=Eπ​[Gt​∣St​=s,At​=a]=s′,r∑​p(s′,r∣s,a)[Gt​∣St​=s,At​=a]=s′,r∑​p(s′,r∣s,a)[r+γGt+1​∣St+1​=s′,At+1​=a′]=s′,r∑​p(s′,r∣s,a)(r+γVπ​(s′))​ 其中 V π ( s ′ ) V_\pi(s') Vπ​(s′)表示下一时刻状态 S t + 1 = s ′ S_{t+1}=s' St+1​=s′的状态价值函数。 细心的朋友发现，

首先解答第一个问题： 当 G t → G t + 1 G_t \to G_{t+1} Gt​→Gt+1​时，公式中函数的后验部分不包含任何关于 t t t时刻的信息 → \to → 而是 t + 1 t+1 t+1时刻的信息；自然需要转换成 t + 1 t+1 t+1时刻的条件。 新的疑问： S t + 1 = s ′ , A t + 1 = a ′ S_{t+1}=s',A_{t+1}=a' St+1​=s′,At+1​=a′是随便说换就换的吗？

该问题和第二个问题一同解答： → \to → 我们需要回溯之前 G t G_t Gt​和 G t + 1 G_{t+1} Gt+1​之间关系的公式： 看起来 G t G_t Gt​和 G t + 1 G_{t+1} Gt+1​之间关系是很容易能够归纳出来，但内部的条件是很苛刻的。

我们知道， G t G_t Gt​是 t t t时刻 S t = s S_t=s St​=s状态下动作的回报；而 G t + 1 G_{t+1} Gt+1​是 t + 1 t+1 t+1时刻 S t + 1 = s ′ S_{t+1}=s' St+1​=s′状态下动作回报； → \to → 如何使2种相邻时刻并且状态确定的回报产生必然的联系？

总结起来就一句话：我们如何能够在 S t = s S_t=s St​=s的情况下使得 S t + 1 = s ′ S_{t+1}=s' St+1​=s′？

至少需要4个条件：

但凡这4个条件有1个不是确定的 → \to →必然不能满足 G t = R t + 1 + γ G t + 1 G_t = R_{t+1} + \gamma G_{t+1} Gt​=Rt+1​+γGt+1​ 换句话说，4个条件全部确定，才能保证 t → t + 1 t \to t+1 t→t+1时刻路径的唯一性。

回顾上式： = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] \begin{aligned} & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[r+ \gamma G_{t+1} \mid S_{t+1}=s',A_{t+1}=a'] \\ \end{aligned} ​=s′,r∑​p(s′,r∣s,a)[Gt​∣St​=s,At​=a]=s′,r∑​p(s′,r∣s,a)[r+γGt+1​∣St+1​=s′,At+1​=a′]​ 该式子中的 S t = s , A t = a , R t + 1 = r , S t + 1 = s ′ S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s' St​=s,At​=a,Rt+1​=r,St+1​=s′都是确定的，该步骤才能成立。 最后一步，根据期望的性质( C C C表示常数):

根据这2条性质，上式可以写成： = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ [ G t + 1 ∣ S t + 1 = s ′ , A t + 1 = a ′ ] ) = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ V π ( s ′ ) ) \begin{aligned} & = \sum_{s',r} p(s',r \mid s,a)[G_t \mid S_t=s,A_t=a] \\ & = \sum_{s',r} p(s',r \mid s,a)[r + \gamma G_{t+1} \mid S_{t+1}=s',A_{t+1}=a'] \\ & = \sum_{s',r} p(s',r \mid s,a)(r + \gamma[G_{t+1} \mid S_{t+1}=s',A_{t+1}=a']) \\ & = \sum_{s',r} p(s',r \mid s,a)(r + \gamma V_\pi(s'))\\ \end{aligned} ​=s′,r∑​p(s′,r∣s,a)[Gt​∣St​=s,At​=a]=s′,r∑​p(s′,r∣s,a)[r+γGt+1​∣St+1​=s′,At+1​=a′]=s′,r∑​p(s′,r∣s,a)(r+γ[Gt+1​∣St+1​=s′,At+1​=a′])=s′,r∑​p(s′,r∣s,a)(r+γVπ​(s′))​

根据上一节，我们获取了 V π ( s ) V_\pi(s) Vπ​(s)和 q π ( s , a ) q_\pi(s,a) qπ​(s,a)之间的关联关系： V π ( s ) = ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) V_\pi(s)= \sum_{a \in \mathcal A} \pi(a \mid s) q_\pi(s,a) Vπ​(s)=a∈A∑​π(a∣s)qπ​(s,a) q π ( s , a ) = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ V π ( s ′ ) ) q_\pi(s,a) = \sum_{s',r} p(s',r \mid s,a)(r + \gamma V_\pi(s')) qπ​(s,a)=s′,r∑​p(s′,r∣s,a)(r+γVπ​(s′)) 最终将上述2个关系式进行相互套娃，就得到了如下式子： V π ( s ) = ∑ a ∈ A π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ V π ( s ′ ) ) V_\pi(s) = \sum_{a \in \mathcal A}\pi(a \mid s)\sum_{s',r}p(s',r \mid s,a)(r + \gamma V_\pi(s')) Vπ​(s)=a∈A∑​π(a∣s)s′,r∑​p(s′,r∣s,a)(r+γVπ​(s′)) q π ( s , a ) = ∑ s ′ , r p ( s ′ , r ∣ s , a ) ( r + γ ( ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) ) ) q_\pi(s,a)=\sum_{s',r} p(s',r \mid s,a)(r + \gamma (\sum_{a' \in \mathcal A}\pi(a' \mid s') q_\pi(s',a'))) qπ​(s,a)=s′,r∑​p(s′,r∣s,a)(r+γ(a′∈A∑​π(a′∣s′)qπ​(s′,a′)))

这两个式子都是不动点方程，满足不动点定理，为后续的基于DP，MC的强化学习提供有效的理论支撑。

下一节继续介绍贝尔曼最优方程

相关参考： 【强化学习】马尔科夫决策过程【白板推导系列】 马尔科夫决策过程之Bellman Equation（贝尔曼方程） 深度强化学习原理、算法pytorch实战 - 刘全，黄志刚编著