2-贝尔曼公式

第2课-贝尔曼公式（例子说明Return的重要性）_哔哩哔哩_bilibili

---

摘要

本节将重点介绍一个核心概念和一个重要工具，它们都是强化学习重要的基础内容.

• 核心概念: state value (状态值). 用于衡量一个policy的好坏，越好的policy对应的state value相对越大.
• 基本工具: the Bellman equation (贝尔曼方程). 用于分析state value，描述所有的state value间的关系。解贝尔曼方程就可以获得这些state values，这一过程也被称为policy evaluation (策略评估).

目录:

1. ⋆State value (状态值)
2. ⋆Bellman equation (贝尔曼方程): Derivation (推导) → Matrix-vector form (矩阵-向量形式) → Solve the state values (求解状态值)
3. Action value (动作值)

回顾: return (回报)

关于回报 (return)

在介绍state value前，我们首先回顾一个相似的概念：return (回报)。因为return也可以用以衡量一个policy的好坏.

Q1: 为什么回报 (return) 很重要? A1: 回报可以评估一个策略。这是将我们对一个策略好坏的直觉 (intuition) 进行数学化的重要定量工具。只有量化了一个policy我们才能不断改进策略。

Q2: 如何计算回报 (return)? A2:

1. 根据定义: 不断累和，即将此policy实施过程中所有 (discounted) reward加和.
2. 自举法 (Bootstrapping) ¹: 当前state的return依赖于其他state的return，最后循环回到自身。这样将所有的state组合起来就可以通过矩阵形式求解 (也就可以得到一般的 Bellman equation)。

图 1: 一个计算奖励的说明性示例

如图1所示，如果根据定义，就会得到：

$$\begin{array}{rl}{v}_1& =r_1+\gamma r_2+{\gamma }^2{r}_3+\cdots ,\\ v_2& =r_2+\gamma r_3+{\gamma }^2{r}_4+\cdots ,\\ v_3& =r_3+\gamma r_4+{\gamma }^2{r}_1+\cdots ,\\ v_4& =r_4+\gamma r_1+{\gamma }^2{r}_2+\cdots .\end{array}$$

其中$\gamma$为discounted rate (折扣率)。

但是可以发现，实际上$v_1$会依赖于下一个state的reward $v_2$，依此类推，就可以得到如下系统：

$$\begin{array}{rl}{v}_1& =r_1+\gamma (r_2+\gamma r_3+\dots )=r_1+\gamma v_2,\\ v_2& =r_2+\gamma (r_3+\gamma r_4+\dots )=r_2+\gamma v_3,\\ v_3& =r_3+\gamma (r_4+\gamma r_1+\dots )=r_3+\gamma v_4,\\ v_4& =r_4+\gamma (r_1+\gamma r_2+\dots )=r_4+\gamma v_1.\end{array}$$

虽然看似每个量间都相互关联构成循环，因此不可解，但是实际上如果写成如下线性的矩阵-向量方程 (linear matrix-vector equation) 就可以看出只需求逆矩阵即可：

$$\underset{v}{\underbrace{\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}=\underset{r}{\underbrace{\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]}}+\left[\begin{array}{c}\gamma v_2\\ \gamma v_3\\ \gamma v_4\\ \gamma v_1\end{array}\right]=\underset{r}{\underbrace{\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]}}+\gamma \underset{P}{\underbrace{\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]}}\underset{v}{\underbrace{\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}$$ $$v=r+\gamma Pv\Rightarrow v=(I-\gamma P{)}^{-1}r$$

状态值 (State Value)

从上述关于return的回顾中可以看到return已经可以度量一个policy的好坏了，那么为什么还需要再提出state value的概念呢？–原因在于return只能计算确定的trajectory，无法融入随机性 (stochastic)。例如下图2的例子，在初始点 $s_1$，此policy有 $p_1$ 概率向右，有 $p_2$ 概率向下 ($p_1+p_2=1$)，因此一个简单的想法就是取均值（期望）：

$$\begin{array}{rl}{v}_1& =p_1(r_{11}+\gamma r_2+{\gamma }^2{r}_3+{\gamma }^3{r}_3+\cdots )\\ & +p_2(r_{12}+\gamma r_4+{\gamma }^2{r}_3+{\gamma }^3{r}_3+\cdots ),p_1+p_2=1\\ & =p_1(r_{11}+\gamma r_2)+p_2(r_{22}+\gamma r_4)+r_3({\gamma }^2+{\gamma }^3+\cdots )\end{array}$$

图 2: 一个计算状态值的说明性示例

下面我们形式化地将随机性引入计算过程中，进而介绍state value.

在agent每执行一次动作时，都会相应地到达下一个state并获得一个 (只与当前state和action有关的) reward，也就得到了如下 单步过程:

$$S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}$$

其中t是为引入时序性，大写字母是表示随机变量 (random variables)，引入随机性.

• $A_t$ 由 $\pi (A_t=a|S_t=s)$ 决定，即某state采取某action的概率
• $S_t\stackrel{A_t}{\to }{R}_{t+1}$ 由 $p(R_{t+1}=r|S_t=s,A_t=a)$ 决定，表示第t-state采取某action后获得某reward的概率
• $S_t\stackrel{A_t}{\to }{S}_{t+1}$ 由 $p(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$ 决定，表示第t-state采取某action后获得变成某state的概率

自然地就可以延伸至如下多步/状态-动作-奖励 (随机) 轨迹:

$$S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}\stackrel{A_{t+1}}{\to }{R}_{t+2},S_{t+2}\stackrel{A_{t+2}}{\to }{R}_{t+3},\dots$$

如此可以计算随机折扣回报 (random discounted return):

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$$

⋆状态值 (State value): 定义为 $G_t$ 的期望 (expectation / expected value / mean)，全称状态-值函数 (state-value function):

$$v_{\pi }(s)\triangleq E[G_t|S_t=s]$$

注 1.1:

1. state value是states的函数，并且依赖于policy $\pi$
2. 如果 $v_{\pi }(s)$ 更大，那么说明对于该state此policy较好
3. state value不依赖于时间步t，当policy给定后，各个state的state value也就确定了

状态值 vs. 回报

Q: 回报 (return) 和状态值 (state value) 之间有什么关系？ A:

1. state value是所有情况下的return求和后 $G_t$ 的期望；return仅针对一个单独的trajectory，而state value需要考虑全部可能的trajectory.
2. 当没有随机性时，即只有一条确定性的trajectory时，return的累和 $G_t$ 就与state value相同.
3. 可以看出使用state value作为评判policy好坏较使用return是更好的.

---

贝尔曼方程 (Bellman Equation)

下面开始介绍重要工具Bellman equation。总的来说，Bellman equation是一组描述所有state values之间关系的方程。解出了Bellman equation也就可以得到相应policy的各state values，进而可以评价该policy。

对于一个state-action-reward trajectory: $S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}\stackrel{A_{t+1}}{\to }{R}_{t+2},S_{t+2}\stackrel{A_{t+2}}{\to }{R}_{t+3},\dots$

Discounted return可以写为:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\underset{\text{immediate reward}}{\underbrace{R_{t+1}}}+\gamma \cdot \underset{\text{future reward}}{\underbrace{G_{t+1}}}$$

进而根据定义，states的state value可以写为：

$$v_{\pi }(s)=E[G_t|S_t=s]=E[R_{t+1}+\gamma G_{t+1}|S_t=s]=E[R_{t+1}|S_t=s]+\gamma E[G_{t+1}|S_t=s]$$

其中第一项为立即奖励的均值 (mean of immediate rewards)，为：

$$E[R_{t+1}|S_t=s]=\sum _{a\in A(s)}\pi (a|s)E[R_{t+1}|S_t=s,A_t=a]=\sum _{a\in A(s)}\pi (a|s)\sum _{r\in R(s,a)}p(r|s,a)\cdot r$$

其中第一个等号使用了双重期望定理 (law of total expectation)，第二个等式是期望的定义。

第二项为未来奖励的均值 (mean of future rewards)，为：

$$\begin{array}{rl}E[G_{t+1}|S_t=s]& \stackrel{\text{law of total expectation}}{\to }\sum _{s^{\prime }\in S}E[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }|s)\\ & \stackrel{\text{Markov decision process property}}{\to }\sum _{s^{\prime }\in S}E[G_{t+1}|S_{t+1}=s^{\prime }]p(s^{\prime }|s)\\ & =\sum _{s^{\prime }\in S}{v}_{\pi }(s^{\prime })p(s^{\prime }|s)\\ & \stackrel{\text{law of total expectation}}{\to }\sum _{s^{\prime }\in S}{v}_{\pi }(s^{\prime })\sum _{a\in A(s)}p(s^{\prime }|s,a)\pi (a|s)\end{array}$$

将分解式(11)(12)代回式(10)中就可以得到如下的Bellman Equation²:

$$\begin{array}{rl}{v}_{\pi }(s)& =E[R_{t+1}|S_t=s]+\gamma E[G_{t+1}|S_t=s]\\ & =\underset{\text{mean of immediate rewards}}{\underbrace{\sum _{a\in A(s)}\pi (a|s)\sum _{r\in R(s,a)}p(r|s,a)r}}+\gamma \underset{\text{mean of future rewards}}{\underbrace{\sum _{a\in A(s)}\pi (a|s)\sum _{s^{\prime }\in S}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })}}\\ & =\sum _{a\in A(s)}\pi (a|s)\left[\sum _{r\in R(s,a)}p(r|s,a)r+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\right],\forall s\in S\end{array}$$

小结

• Bellman equation描述了不同state的state-value function间的关系
• Bellman equation看似陷入循环、不可解，但其是一族方程，其包含了状态空间$S$中全部state，共$|S|$个方程，求解方法就是前面介绍的Bootstrapping
• $\pi (a|s)$是一个给定的policy，求解Bellman equation可以得到相应的state value。因此求解Bellman equation也被称为policy evalution (策略评估)，即评价一个policy的好坏
• $p(r|s,a)$和$p(s^{\prime }|s,a)$表示系统的模型，称为dynamic model / environment model (动态模型/环境模型)，这个model有时已知有时未知，后续会介绍未知情形下如何进行policy evaluation.
• 根据全概率公式 (law of total probability) $$p(s^{\prime }|s,a)=\sum _{r\in R}p(s^{\prime },r|s,a),p(r|s,a)=\sum _{s^{\prime }\in S}p(s^{\prime },r|s,a).$$ Bellman equation (13)也等价地可以写为： $$v_{\pi }(s)=\sum _{a\in A(s)}\pi (a|s)\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$$
• 如果在某些问题中reward只与$s^{\prime }$相关，那么上述bellman equation又可以进一步写为 $$v_{\pi }(s)=\sum _{a\in A}\pi (a|s)\sum _{s^{\prime }\in S}p(s^{\prime }|s,a)[r(s^{\prime })+\gamma v_{\pi }(s^{\prime })]$$

贝尔曼方程 – 矩阵-向量形式

之前介绍的Bellman equation (13)实际上是其elementwise form，共有$|S|$个公式，无法单独求解，但是将他们组合起来就可以得到一组线性方程，即求解一个线性方程组，也就是matrix-vector form。

首先为书写方便，将式(13)改写为：

$$v_{\pi }(s)=r_{\pi }(s)+\gamma \sum _{s^{\prime }}{p}_{\pi }(s^{\prime }|s)v_{\pi }(s^{\prime })$$

其中$r_{\pi }(s)$为average of immediate reward (立即回报的平均值)，$p_{\pi }(s^{\prime }|s)$为在policy $\pi$下state由$s$转变为$s^{\prime }$的概率：

$$r_{\pi }(s)\triangleq \sum _a\pi (a|s)\sum _{r}p(r|s,a)r$$ $$p_{\pi }(s^{\prime }|s)\triangleq \sum _a\pi (a|s)p(s^{\prime }|s,a)$$

对于n个状态的状态空间$S=\{s_1,s_2,\cdots ,s_n\}$，n个Bellman equation可写为：

$$v_{\pi }(s_i)=r_{\pi }(s_i)+\gamma \sum _{s_j}{p}_{\pi }(s_j|s_i)v_{\pi }(s_j),i=1,2,...,n$$

写成matrix-vector form就是：

$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

其中

• $v_{\pi }=[v_{\pi }(s_1),\dots ,v_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• $r_{\pi }=[r_{\pi }(s_1),\dots ,r_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• $P_{\pi }\in {\mathbb{R}}^{n\times n}$，其中 $[P_{\pi }{]}_{ij}=p_{\pi }(s_j|s_i)$，为状态转移矩阵 (state transition matrix)

写成矩阵形式就是

$$\underset{v_{\pi }}{\underbrace{\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ ⋮\\ v_{\pi }(s_n)\end{array}\right]}}=\underset{r_{\pi }}{\underbrace{\left[\begin{array}{c}{r}_{\pi }(s_1)\\ r_{\pi }(s_2)\\ ⋮\\ r_{\pi }(s_n)\end{array}\right]}}+\gamma \underset{P_{\pi }}{\underbrace{\left[\begin{array}{cccc}{p}_{\pi }(s_1|s_1)& \cdots & p_{\pi }(s_{n-1}|s_1)& p_{\pi }(s_n|s_1)\\ p_{\pi }(s_1|s_2)& \cdots & p_{\pi }(s_{n-1}|s_2)& p_{\pi }(s_n|s_2)\\ ⋮& \ddots & ⋮& ⋮\\ p_{\pi }(s_1|s_n)& \cdots & p_{\pi }(s_{n-1}|s_n)& p_{\pi }(s_n|s_n)\end{array}\right]}}\underset{v_{\pi }}{\underbrace{\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ ⋮\\ v_{\pi }(s_n)\end{array}\right]}}$$

矩阵$P_{\pi }$有如下两个特点：

1. 所有元素非负。因为显然概率$0\le [P_{\pi }{]}_{ij}=p_{\pi }(s_j|s_i)\le 1$
2. 行和为1，即$P_{\pi }1=1$，其中$1=[1,1,\cdots ,1{]}^T$。因为 ${\sum }_j{p}_{\pi }(s_j|s_i)=1$

贝尔曼方程: 求解状态值

1. 第一种求解方式就是直接求其闭式解 (closed-form solution)，为

   $$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

   虽然此解数学形式直接，但是实际中大规模矩阵求逆矩阵很困难，仍然需要使用特殊的数值方法（且仍然难以求解）。

   矩阵 $I-\gamma P_{\pi }$ 实际上有如下性质：

   1. $I-\gamma P_{\pi }$ 可逆。证明需要使用Gershgorin circle theorem，详见附录A。
   2. $(I-\gamma P_{\pi }{)}^{-1}\ge I$。因为 $(I-\gamma P_{\pi }{)}^{-1}=I+\gamma P_{\pi }+{\gamma }^2{P}_{\pi }^2+\cdots \ge I\ge 0$.
   3. $(I-\gamma P_{\pi }{)}^{-1}r\ge r\ge 0,\forall r\ge 0$。因为直接利用性质2即可.

2. 第二种方法是迭代法找其迭代解 (iterative solution)：

   $$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k,k=0,1,2,\cdots$$

   最终可以证明³ (证明过程详见附录A)

   $$v_k\stackrel{k\to \infty }{\to }{v}_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

注 2.1:

1. 计算state value可以评价一个policy好不好
2. 不同的policy也可以得到相同的state value

---

动作值 (Action Value)

Action value也是强化学习中的一个重要概念，放在这里才提出是因为其定义需要和state value相联系。Action value是指在某state下采取相应的某action后能够获得的平均回报 (average return)，即

$$q_{\pi }(s,a)\triangleq E[G_t|S_t=s,A_t=a]$$

• $q_{\pi }(s,a)$ 是state-action pair $(s,a)$的函数，而不仅依赖于action
• $q_{\pi }(s,a)$ 依赖于policy $\pi$

State value与Action value辨析

• state value 是指一个agent从一个state出发能得到的average return，定义为 $$v_{\pi }(s)=E[G_t|S_t=s]$$
• action value 是指一个agent从一个state出发并且做出一个action后能得到的average return，定义为 $$q_{\pi }(s,a)\triangleq E[G_t|S_t=s,A_t=a]$$

由于

$$\underset{v_{\pi }(s)}{\underbrace{E[G_t|S_t=s]}}=\sum _a\underset{q_{\pi }(s,a)}{\underbrace{E[G_t|S_t=s,A_t=a]}}\pi (a|s)=\sum _a\pi (a|s)\underset{q_{\pi }(s,a)}{\underbrace{\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\right]}}$$

因此

$$v_{\pi }(s)=\sum _a\pi (a|s)q_{\pi }(s,a)$$ $$q_{\pi }(s,a)=\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })$$

式(21a)和(21b)就像一个硬币的两面，式(21a)说明可以从action value获得state value，式(21b)说明可以从state value获得action value。

注 3: 当一个确定性的policy中在某个state只有一个action时，其他的action产生的action value并不是0，而是也可以计算，此时的immediate reward一般为0，但是仍然有future reward。这样就可以与这个确定的action比较看是否这个action是好的.

---

附录A. 证明

贝尔曼方程迭代解的收敛性

$v_k\stackrel{k\to \infty }{\to }{v}_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$

证明: 首先定义残差 ${\delta }_k=v_k-v_{\pi }$，我们只需要证明 ${\delta }_k\to 0$ 即可。 将 $v_{k+1}={\delta }_{k+1}+v_{\pi }$, ${\delta }_k=v_k-v_{\pi }$ 代入 $v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$ 中得到

$$\begin{array}{rl}{\delta }_{k+1}+v_{\pi }& =r_{\pi }+\gamma P_{\pi }({\delta }_k+v_{\pi })\\ {\delta }_{k+1}& =-v_{\pi }+r_{\pi }+\gamma P_{\pi }{\delta }_k+\gamma P_{\pi }{v}_{\pi }\\ & =\gamma P_{\pi }{\delta }_k-v_{\pi }+(r_{\pi }+\gamma P_{\pi }{v}_{\pi })\end{array}$$

因为 $v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$，所以

$${\delta }_{k+1}=\gamma P_{\pi }{\delta }_k$$

因此有

$${\delta }_{k+1}=\gamma P_{\pi }{\delta }_k={\gamma }^2{P}_{\pi }^2{\delta }_{k-1}=\cdots ={\gamma }^{k+1}{P}_{\pi }^{k+1}{\delta }_0.$$

已知 $0\le [P_{\pi }{]}_{ij}=p_{\pi }(s_j|s_i)\le 1$，因此 $0\le [P_{\pi }^k{]}_{ij}\le 1$，且 $\gamma <1\Rightarrow {\gamma }^k\to 0$，从而有

$${\delta }_{k+1}={\gamma }^{k+1}{P}_{\pi }^{k+1}{\delta }_0\stackrel{k\to \infty }{\to }0$$

闭式解的可逆性

$I-\gamma P_{\pi }$ 可逆

证明: 根据格尔什戈林圆盘定理，矩阵 $I-\gamma P_{\pi }$ 的所有特征值至少落在一个格尔什戈林圆盘中，其中第i个格尔什戈林圆盘中心为 $[I-\gamma P_{\pi }{]}_{ii}=1-\gamma p_{\pi }(s_i|s_i)$，半径为 $R_i={\sum }_{j\ne i}|[I-\gamma P_{\pi }{]}_{ij}|={\sum }_{j\ne i}\gamma p_{\pi }(s_j|s_i)$。

由于 $0<[I-\gamma P_{\pi }{]}_{ii}=1-\gamma p_{\pi }(s_i|s_i)<1$，$0<\gamma <1$，故

$$[I-\gamma P_{\pi }{]}_{ii}-R_i=1-\gamma p_{\pi }(s_i|s_i)-\sum _{j\ne i}\gamma p_{\pi }(s_j|s_i)=1-\gamma \sum _j{p}_{\pi }(s_j|s_i)=1-\gamma >0$$

因此所有的格尔什戈林圆盘都在复平面的右半边，不包含原点。自然地，所有的特征值都严格大于0，因此矩阵可逆。

定理 1 (格尔什戈林圆盘定理). 令 $A=[a_{ij}]$ 为 $n\times n$ 的复矩阵， $R_i$ 为第 $i$ 行除对角元外所有元素绝对值之和：

$$R_i\triangleq \sum _{j\ne i}|a_{ij}|$$

令 $D(a_{ii},R_i)\subseteq \mathbb{C}$ 表示中心为 $a_{ii}$，半径为 $R_i$ 的闭圆盘 (disc)，称之为格尔什戈林圆盘 (Gershgorin disc)。 那么，A的所有特征值至少落在一个格尔什戈林圆盘 $D(a_{ii},R_i)$ 中。

Footnotes

1. Bootstrapping来源于统计抽样，其思想是通过一些方法作用于一个系统就可以只利用该系统本身来获取其自身信息 ↩

2. 这是elementwise form (元素形式)的Bellman equation，下面会讲解matrix-vector form (矩阵-向量形式)的Bellman equation ↩

3. 如果熟悉的话这其实就是一个不动点迭代的证明，使用Banach不动点定理 ↩