Lecture2: Bellman Equation

State value

考虑grid-world的单步过程：
$$S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}$$

• $t$, $t+1$：时间戳
• $S_t$：时间$t$时所处的state
• $A_t$：在state $S_t$时采取的action
• $R_{t+1}$：在采取 action $A_t$ 之后获得的reward
• $S_{t+1}$：在采取 action $A_t$ 之后，state $S_t$转移后的state

通过概率分布对以上变量的动作进行描述：

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

考虑grid-world的多步（multi-step）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}...$$
其discounted return为：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...$$

• $\gamma \in [0,1)$是折扣率（discount rate）
• 当$R_{t+1},R_{t+2},...$是随机变量时，$G_t$也是随机变量

$G_t$的期望（expectation; expected value; mean）被定义为state-value function或state value。
$$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$

• $v_{\pi }(s)$是state $s$的函数，是state从 $s$ 起始的条件期望。
• $v_{\pi }(s)$基于policy $\pi$，对于不同的policy，state value可能会不同
• 其代表了一个state的“价值”。 如果state value越大，代表policy就越好，因为可以获得更大的累积奖励（cumulative rewards）。

注意区分state value和return： state value是从某个state开始可以获得的所有可能return的平均值。如果每一个 $\pi (a|s),p(r|s,a),p(s^{\prime }|s,a)$是确定的，那么state value和return是相等的。

例：

计算三个样例的state value：
$$v_{{\pi }_1}(s_1)=0+\gamma 1+{\gamma }^{2}1+\cdots =\gamma (1+\gamma +{\gamma }^2+\cdots )=\frac{\gamma }{1-\gamma }$$

$$v_{{\pi }_2}(s_1)=-1+\gamma 1+{\gamma }^{2}1+\cdots =-1+\gamma (1+\gamma +{\gamma }^2+\cdots )=-1+\frac{\gamma }{1-\gamma }$$

$$v_{{\pi }_3}(s_1)=0.5(-1+\frac{\gamma }{1-\gamma })+0.5(\frac{\gamma }{1-\gamma })=-0.5+\frac{\gamma }{1-\gamma }$$

Bellman equation: Derivation

贝尔曼方程描述了所有state值之间的关系。

考虑一个随机的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$$
其return $G_t$可以被计算为：
$$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \\ & =R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\dots )\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$
其state value可以计算为：
$$\begin{array}{rl}{v}_{\pi }(s)& =\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}$$
对于第一项：
$$\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}$$
这是瞬时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)\\ & =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime }]p(s^{\prime }|s)\\ & =\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)\end{array}$$
这是未来reward的期望

因此，可以得到：
$$\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 _{s^{\prime }}{v}_{\pi }(s^{\prime })\sum _{a}p(s^{\prime }|s,a)\pi (a|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],\forall s\in S\end{array}$$

• $v_{\pi }(s)$和$\pi (s^{\prime })$是需要被计算的state value，可以采用bootstrapping。
• $\pi (a|s)$是给定的policy，可以通过策略评估（policy evaluation）进行求解。
• $p(r|s,a)$和$p(s^{\prime }|s,a)$代表动态模型，分为known和unknown。
• 上式叫做贝尔曼等式（Bellman equation），其描述了不同state之间state-value function的关系。
• Bellman equation包含两个部分，瞬时奖励（immediate reward）和未来奖励（future reward）。

例：

对于action:

若policy为：

首先写Bellman equation：
$$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]$$
计算上式各项：

• $\pi (a=a_3|s_1)=1$, $\pi (a\ne a_3|s_1)=0$
• $p(s^{\prime }=s_3|s_1,a_3)=1$, $p(s^{\prime }\ne s_3|s_1,a_3)=0$
• $p(r=0|s_1,a_3=1)$, $p(r\ne 0|s_1,a_3)=0$

替换进Bellman equation得：
$$v_{\pi }(s_1)=0+\gamma v_{\pi }(s_3)$$
同样的，可以计算：
$$\begin{gathered} 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{gathered}$$
对于上式，可以从后往前计算：
$$\begin{gathered} v_{\pi }(s_4)=\frac{1}{1-\gamma } \\ {v}_{\pi }(s_3)=\frac{1}{1-\gamma } \\ {v}_{\pi }(s_2)=\frac{1}{1-\gamma } \\ {v}_{\pi }(s_1)=\frac{\gamma }{1-\gamma } \end{gathered}$$
若policy为：

则：
$$\begin{gathered} 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{gathered}$$
从后往前算：
$$\begin{gathered} v_{\pi }(s_4)=\frac{1}{1-\gamma } \\ {v}_{\pi }(s_3)=\frac{1}{1-\gamma } \\ {v}_{\pi }(s_2)=\frac{1}{1-\gamma } \\ \begin{array}{rl}{v}_{\pi }(s_1)& =0.5[0+\gamma v_{\pi }(s_3)]+0.5[-1+\gamma v_{\pi }(s_2)]\\ & =-0.5+\frac{\gamma }{1-\gamma }\end{array} \end{gathered}$$

Bellman equation: Matrix-vector form

对于Bellman equation:
$$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]$$
通常是未知的$v_{\pi }(s)$伴随着未知的$v_{\pi }(s^{\prime })$，这对于每一个$s\in \mathcal{S}$都成立。因此，意味着共有$|\mathcal{S}|$个这样的等式。如果将所有的等式，放到一起进行计算，这就构成了Bellman equation的矩阵形式。

将上式展开，写为：
$$v_{\pi }(s)=r_{\pi }(s)+\gamma \sum _{s^{\prime }}{p}_{\pi }(s^{\prime }|s)v_{\pi }(s^{\prime })(1)$$
其中：
$$\begin{gathered} r_{\pi }(s):=\sum _a\pi (a|s)\sum _{r}p(r|s,a)r \\ {p}_{\pi }(s^{\prime }|s):=\sum _a\pi (a|s)p(s^{\prime }|s,a) \end{gathered}$$
为state $s$添加索引$s_i,i=1,...,n$

对于$s_i$，其Bellman equation为：
$$v_{\pi }(s_i)=r_{\pi }(s_i)+\gamma \sum _{s_j}{p}_{\pi }(s_j|s_i)v_{\pi }(s_j)$$
将所有的state写为矩阵形式：
$${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }$$
其中：

• ${\mathbf{v}}_{\pi }=[v_{\pi }(s_1),v_{\pi }(s_2),...,v_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• ${\mathbf{r}}_{\pi }=[r_{\pi }(s_1),r_{\pi }(s_2),...,r_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• ${\mathbf{P}}_{\pi }\in {\mathbb{R}}^{n\times n}$，其中，$[P_{\pi }]=p_{\pi }(s_j|s_i)$是state转移矩阵。

假设有四个state，则上式矩阵形式可以写为：
$$\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]$$
例，对policy1：

对其求解，得：
$$\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]$$
对policy2:

对其求解，得：
$$\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)\\ 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 equation: Solve the state values

对于矩阵形式的Bellman equation：
$${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }$$
其closed-form的解为：
$${\mathbf{v}}_{\pi }=(\mathbf{I}-\gamma {\mathbf{P}}_{\pi }{)}^{-1}{\mathbf{r}}_{\pi }$$
为了避免求矩阵的逆，可以采用迭代法：
$$\begin{gathered} {\mathbf{v}}_{k+1}=\mathbf{r}+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_k \\ {\mathbf{v}}_k\to {\mathbf{v}}_{\pi }=(\mathbf{I}-\gamma {\mathbf{P}}_{\pi }{)}^{-1}{\mathbf{r}}_{\pi },k\to \infty \end{gathered}$$
以下是对于一个grid-world，在给定policy下，各个state的state value。

可以看到，不同的policy其产生的state value可能是相同的。

可以看到，大多数情况下，不同的policy对state value的影响是比较大的，因此，state value是有效评估policy的一个指标。

Action value

state value: agent从某个state开始可以获得的平均return

action value: agent从某个state开始并采取action可以获得的平均return。

通过action value可以知道当前state下，哪个action是更好的。

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

• $q_{\pi }(s,a)$是state、action对的函数
• $q_{\pi }(s,a)$依赖于$\pi$

根据条件期望公式：
$$\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)(2)$$
对于state 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]\\ & =\sum _a\pi (a|s)\cdot q_{\pi }(s,a)\end{array}(3)$$
比较公式（2）与公式（3），可以得到action-value function：
$$q_{\pi }(s,a)=\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })(4)$$
通过公式（2）和公式（4）可以发现state value和action value可以相互转化。

例：

求解，得：
$$\begin{array}{rl}& q_{\pi }(s_1,a_1)=-1+\gamma v_{\pi }(s_1)\\ & q_{\pi }(s_1,a_2)=-1+\gamma v_{\pi }(s_2)\\ & 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}$$

Summary

• state value: $v_{\pi }(s)=\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
  $$\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]\\ & =\sum _a\pi (a|s)\cdot q_{\pi }(s,a)\end{array}$$
  matrix-vector form
  $${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma \mathbf{P}{\mathbf{v}}_{\pi }$$

• 可以通过闭合形式解和迭代法求Bellman equation

以上内容为B站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。