2.Bellman Equation

课程笔记

Return

Return 的简单例子

这三个相同环境下，给定三种策略，计算三种 return

$retur{n}_1=0+\gamma 1+{\gamma }^{2}1+...=\gamma (1+\gamma +{\gamma }^2+...)=\frac{\gamma }{1-\gamma }.$

$retur{n}_2=-1+\gamma 1+{\gamma }^{2}1+...=-1+\gamma (1+\gamma +{\gamma }^2+...)=-1+\frac{\gamma }{1-\gamma }.$

$retur{n}_3=0.5(-1+\frac{\gamma }{1-\gamma })+0.5(\frac{\gamma }{1-\gamma })=-0.5+\frac{\gamma }{1-\gamma }.$

实际上 return 3 是两个 return 的平均，return 能够判断哪个 trajectory 是比较好的

return 一般计算方法

注意

以下是在确定性策略 $\pi$ 下的计算

若每此行动都会得到相应的当步收益 $r_i$，则 return 使用 boostrapping 方法计算（核心是状态之间是有关系的）

从 $s_1$ 出发 $v_1=r_1+\gamma r_2+{\gamma }^2{r}_3+...=r_1+\gamma (r_2+\gamma r_3+...)=r_1+\gamma v_2$

从 $s_2$ 出发 $v_2=r_2+\gamma r_3+{\gamma }^2{r}_4+...=r_2+\gamma (r_3+\gamma r_4+...)=r_2+\gamma v_3$

从 $s_3$ 出发 $v_3=r_3+\gamma r_4+{\gamma }^2{r}_1+...=r_3+\gamma (r_4+\gamma r_1+...)=r_3+\gamma v_4$

从 $s_4$ 出发 $v_4=r_4+\gamma r_1+{\gamma }^2{r}_2+...=r_4+\gamma (r_1+\gamma r_2+...)=r_4+\gamma v_1$

写成矩阵形式（矩阵形式很有用）：

$\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]=\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]+\gamma \left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]$

有矩阵形式可化简为 bellman 公式 $v=r+\gamma Pv$ ，通过方程求解 return $v$

State value

Definition

State value function 概念非常重要，是强化学习中策略的评估标准，以下逐步引出 state value 的公式表达

考虑单步过程: $S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}$

• $t,t+1$: 离散时间
• $S_t$: 在 $t$ 时刻的状态
• $A_t$: 在 $S_t$ 状态时采取的行动
• $R_{t+1}$: 采取 $A_t$ 行动后获得的奖励
• $S_{t+1}$: 采取 $A_t$ 行动后转移的状态

其中，大写字母 $S_t,A_t,R_{t+1}$ 是随机变量，且单步过程中取决于概率分布：

• $S_t\to A_t$ 由策略 $\pi (A_t=a|S_t=s)$ 决定（采取行动又策略决定）
• $S_t,A_t\to R_{t+1}$ 由奖励概率 $p(R_{t+1}=r|S_t=s,A_t=a)$ 决定（获得奖励由奖励分布决定）
• $S_t,A_t\to S_{t+1}$ 由转移概率 $p(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$ 决定（状态转移由转移概率决定）

考虑多步轨迹 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},...$

Discount return 是 $G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...$

• $\gamma \in [0,1)$ 是折扣率。
• $G_t$ 同样是一个随机变量，因为 $R_{t+1},R_{t+2},...$ 是随机变量。

状态价值函数

其中 $G_t$ 的期望被定义为 state-value-function

$$v_{\pi }=\mathbb{E}(G_t|S_t=s)$$

Remarks:

• 这是状态 $s$ 的函数，是从状态 $s$ 开始的条件下的条件 return 期望
• 该函数基于策略 $\pi$，不同策略 → 不同的轨迹 → 不同的 return → 会有不同的 state value
• 该函数表示状态 $s$ 下的价值，价值函数越大，则该策略越好，因为能得到更多的累计奖励
• Return 和 state value 有什么区别？
  • Return 是对单个 trajectory 计算的
  • 而一般状态下，一个状态出发可能会有多个 trajectory ，求他们的期望 return
  • 但如果策略是确定性的，那么 return 与 state value 是一致的
  • 回到标题 Return 的简单例子，每种策略下只有一条 trajectory，因此 return 就是 state value，可以比较 state value 的大小来选择策略

State value 计算

State value 的计算工具：bellman 公式

从 return 一般计算方法 可知，bellman 公式描述了状态之间的联系

考虑 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},...$

则 return 利用 boostrap 化简：

$$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...\\ & =R_{t+1}+\gamma (R_{t+1}+\gamma R_{t+3}+...)\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$

根据 state value 定义，利用上述技巧可化简：

$$\begin{array}{rl}{v}_{\pi }& =\mathbb{E}(G_t|S_t=s)\\ & =\mathbb{E}(R_{t+1}+\gamma G_{t+1}|S_t=s)\\ & =\mathbb{E}(R_{t+1}|S_t=s)+\gamma \mathbb{E}(G_{t+1}|S_t=s)\end{array}$$

首先计算 state value 的第一项（实际上是 rewward的期望），使用两次全概率公式：

$$\begin{array}{rl}\mathbb{E}[R_{t+1}|S_t=s]& =\sum _a\pi (a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r\end{array}$$

然后计算 state value 的第二项（实际上是未来 reward的期望），同样多次使用全概率公式

$$\begin{array}{rl}\mathbb{E}[G_{t+1}|S_t=s]& =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }|s)(t+1时刻有不同的状态转移)\\ & =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime }]p(s^{\prime }|s)(Markov的无记忆性)\\ & =\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }|s)\\ & =\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })\sum _{a}p(s^{\prime }|s,a)\pi (a|s)(s状态到s^{\prime }状态有不同的行动)\\ & =\sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })(写成未来statevalue的期望)\end{array}$$

通过上述两项的计算，state value 计算式为：

$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}(R_{t+1}|S_t=s)+\gamma \mathbb{E}(G_{t+1}|S_t=s)\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r+\gamma \sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\\ & =\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\forall s\in \mathcal{S}\end{array}$$

highlights

• 上述方程就是传说中的 Bellman 方程，描述了不同状态下的 state value函数的关系

• 该方程包含了两部分：当前 reward 的期望和未来 reward 的期望

• 对所有状态下都存在该等式关系

• $v_{\pi }(s)$ 和 $v_{\pi }^{\prime }(s)$ 是能够计算的 state value，但他们依赖于各种概率分布

• 给定策略 $\pi (a|s)$ 情况下，求方程解的过程被称为策略评估（方程解 $v_{\pi }(s)$ 能评价策略的好坏）

• 奖励概率分布 $p(r|s,a)$ 和转移概率 $p(s^{\prime }|s,a)$ 表示动态模型，一般是知道的(不知道也可以)

State value 计算例子

Example 1

给出如下环境、状态集合 $\mathcal{S}$、确定性策略 $\pi$，其中行动分为上 ($a_1$)、右 ($a_2$)、下 ($a_3$)、左 ($a_4$)、不动 ($a_5$)

根据 Bellman 公式一般表达式，求解该环境下策略 $\pi$ 的 state value 值 $v_{\pi }(s)$、$v_{\pi }(s^{\prime })$，需要知道 $\pi (a|s)、p(r|s,a)、p(s^{\prime }|s,a)$

$$v_{\pi }(s)=\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\forall s\in \mathcal{S}$$

首先考虑在 $s_1$ 状态下的 state value 值 $v_{\pi }(s_1)$

• 策略 $\pi (a=a_3|s)=1and\pi (a\ne a_3|s)=0$
• 奖励概率分布 $p(r=0|s,a)=1andp(r\ne 0|s,a)=0$
• 状态转移概率 $p(s=s_3|s_1,a_3)=1andp(s\ne s_3|s_1,a_3)=0$

因此 $s_1$ 状态下 Bellman 公式化简为 $v_{\pi }(s_1)=0+v_{\pi }(s_3)$，（本质上等于即时奖励+未来的 statevalue）

同理得到其他状态下的 Bellman 公式

$$\begin{array}{r}{v}_{\pi }(s_1)=0+\gamma v_{\pi }(s_3),\\ v_{\pi }(s_2)=1+\gamma v_{\pi }(s_4),\\ v_{\pi }(s_3)=1+\gamma v_{\pi }(s_4),\\ v_{\pi }(s_4)=1+\gamma v_{\pi }(s_4).\end{array}$$

求解所有状态构成的 bellman 方程组，若 $\gamma =0.9$ 则：

$$\begin{array}{rl}{v}_{\pi }(s_1)& =\frac{\gamma }{1-\gamma }=\frac{0.9}{1-0.9}=9,\\ v_{\pi }(s_2)& =\frac{1}{1-\gamma }=\frac{1}{1-0.9}=10,\\ v_{\pi }(s_3)& =\frac{1}{1-\gamma }=\frac{1}{1-0.9}=10,\\ v_{\pi }(s_4)& =\frac{1}{1-\gamma }=\frac{1}{1-0.9}=10.\end{array}$$

可以观察到不同状态的 state value，$s_1$ 是最小的，因为离目标最远，而其他状态距离目标最近

Example 2

现在策略改变了，在 $s_1$ 处是随机方向。

同上计算相似,，只在状态 $s_1$ 不同

$$\begin{array}{rl}{v}_{\pi }(s_1)& =0.5[0+\gamma v_{\pi }(s_3)]+0.5[-1+\gamma v_{\pi }(s_2)]],\\ v_{\pi }(s_2)& =1+\gamma v_{\pi }(s_4),\\ v_{\pi }(s_3)& =1+\gamma v_{\pi }(s_4),\\ v_{\pi }(s_4)& =1+\gamma v_{\pi }(s_4).\end{array}$$

同理解方程组：

$$\begin{array}{rl}{v}_{\pi }(s_1)& =-0.5+\frac{\gamma }{1-\gamma }=\frac{0.9}{1-0.9}-0.5=8.5,\\ v_{\pi }(s_2)& =\frac{1}{1-\gamma }=\frac{1}{1-0.9}=10,\\ v_{\pi }(s_3)& =\frac{1}{1-\gamma }=\frac{1}{1-0.9}=10,\\ v_{\pi }(s_4)& =\frac{1}{1-\gamma }=\frac{1}{1-0.9}=10.\end{array}$$

state value 的作用

比较 example 1 与 example 2 两种策略可知

在 $s_1$ 下，$v_{{\pi }_1}(s_1)>v_{{\pi }_2}(s_1)$，显然第一种策略更好。

Bellman equation

Bellman 公式的矩阵形式

因为每一个状态都会存在一个 Bellman 公式，因此具有矩阵形式。，Bellman 公式如下：

$$v_{\pi }(s)=\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\forall s\in \mathcal{S}$$

将 Bellman 公式使用符号简化，得到：

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

其中

$$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)$$

因此若状态表示为 $s_i(i=1,...,n)$，则对于状态 $s_i$ 的 Bellman 方程为

$$v_{\pi }(s_i)=r_{\pi }(s_i)+\gamma \sum _{s_j}{p}_{\pi }(s_j|s_i)v_{\pi }(s_j)$$

将所有状态的 Bellman 方程写在一起，并重写称矩阵形式如下：

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

其中

• $v_{\pi }=[v_{\pi }(s_1),...,v_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• $r_{\pi }=[r_{\pi }(s_1),...,r_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• $[P_{\pi }{]}_{ij}=p_{\pi }(s_j|s_i)$ ，则 $P_{\pi }\in {\mathbb{R}}^{n\times n}$是转移概率矩阵

Bellman 公式的矩阵形式例子

Example 1

若环境中只有四个状态，则 Bellman 公式的一般矩阵形式如下：

$$\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ v_{\pi }(s_3)\\ v_{\pi }(s_4)\end{array}\right]=\left[\begin{array}{c}{r}_{\pi }(s_1)\\ r_{\pi }(s_2)\\ r_{\pi }(s_3)\\ r_{\pi }(s_4)\end{array}\right]+\gamma \left[\begin{array}{cccc}{p}_{\pi }(s_1|s_1)& p_{\pi }(s_2|s_1)& p_{\pi }(s_3|s_1)& p_{\pi }(s_4|s_1)\\ p_{\pi }(s_1|s_2)& p_{\pi }(s_2|s_2)& p_{\pi }(s_3|s_2)& p_{\pi }(s_4|s_2)\\ p_{\pi }(s_1|s_3)& p_{\pi }(s_2|s_3)& p_{\pi }(s_3|s_3)& p_{\pi }(s_4|s_3)\\ p_{\pi }(s_1|s_4)& p_{\pi }(s_2|s_4)& p_{\pi }(s_3|s_4)& p_{\pi }(s_4|s_4)\end{array}\right]\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ v_{\pi }(s_3)\\ v_{\pi }(s_4)\end{array}\right].$$

Example 2

若四个状态的环境中，给出如下策略：

$$\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ v_{\pi }(s_3)\\ v_{\pi }(s_4)\end{array}\right]=\left[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}\right]+\gamma \left[\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ v_{\pi }(s_3)\\ v_{\pi }(s_4)\end{array}\right].$$

Example 3

$$\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ v_{\pi }(s_3)\\ v_{\pi }(s_4)\end{array}\right]=\left[\begin{array}{c}0.5(0)+0.5(-1)\\ 0.5+1(-1)\\ 1\\ 1\end{array}\right]+\gamma \left[\begin{array}{cccc}0& 0.5& 0.5& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ v_{\pi }(s_3)\\ v_{\pi }(s_4)\end{array}\right].$$

Bellman 公式的求解

解析解

$$\begin{array}{rl}{v}_{\pi }& =r_{\pi }+\gamma P_{\pi }{v}_{\pi }\\ v_{\pi }& =(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }\end{array}$$

数值求解

迭代算法如下：

$$v_k=r_{\pi }+\gamma P_{\pi }{v}_{k+1}$$

算法中会产生一组序列 $\{v_0,v_1,v_2,...\}$，并有数值分析中的收敛结论：

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

相关数学证明过程

Action value

Definition

定义如下，表示在给定 state 和 action 下可以看出哪些 action 更好

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

State value 与 action value 关系 1：从定义和全概率公式推 state value 具体表达

$$\begin{array}{rl}\mathbb{E}[G_t|S_t=s]& =\sum _a\mathbb{E}[G_t|S_t=s,A_t=a]\pi (a|s)\\ v_{\pi }(s)& =\sum _a\pi (a|s)q_{\pi }(s,a)(actionvalue的平均)\end{array}$$

State value 与 action value 关系 2：从 Bellman 公式出发反推 action value 具体表达

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _a\pi (a|s)\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\right]\\ q_{\pi }(s,a)& =\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\end{array}$$

Action value 计算例子

Example

给定收益 $p(r|s,a)$、转移概率 $p(s^{\prime }|s,a)$ 则在 $s_1$ 处的

• 收益是 $p(r=-1|s_1,a_2)=1andp(r\ne -1|s_1,a_2)=0$
• 状态转移是 $p(s=s_2|s_1,a_2)=1andp(s\ne s_2|s_1,a_2)=0$

则由关系 2 计算在 $s_2$ 状态下的 action value

$$q_{\pi }(s_1,a_2)=-1+\gamma v_{\pi }(s_2)$$

注意

虽然这里是确定性的策略，但不代表该策略是最优的策略，因此 $q_{\pi }(s_1,a_1)$ 、$q_{\pi }(s_1,a_3)$、$q_{\pi }(s_1,a_4)$、$q_{\pi }(s_1,a_5)$ 不一定为 0

$$\begin{array}{rl}{q}_{\pi }(s_1,a_1)& =-1+\gamma v_{\pi }(s_1)\\ q_{\pi }(s_1,a_3)& =0+\gamma v_{\pi }(s_3)\\ q_{\pi }(s_1,a_4)& =-1+\gamma v_{\pi }(s_1)\\ q_{\pi }(s_1,a_5)& =0+\gamma v_{\pi }(s_1)\end{array}$$

Summury

• State value $v_{\pi }=\mathbb{E}(G_t|S_t=s)$
• Action value $q_{\pi }(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$
• Bellman equation (elementwise form)
  • $v_{\pi }(s)={\sum }_a\pi (a|s)[{\sum }_{r}p(r|s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\forall s\in \mathcal{S}$
• Bellman equation (matrix-vector form)
  • $v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$
• How to solve Bellman equation
  • Closed-form solution
  • Iterative solution