贝尔曼公式

Bellman Equation

状态价值函数

考虑到单步策略：

$$S_t\stackrel{A_t}{\to }{S}_{t+1},R_{t+1}$$

其中：$S_t,S_{t+1}\in \mathcal{S}$，$A_t\in \mathcal{A}(S_t)$，$R_{t+1}\in \mathcal{R}(S_t,A_t)$，均为随机变量

从 $t$ 时刻开始，我们可以得到一个状态-动作-回报轨迹：

$$S_t\stackrel{A_t}{\to }{S}_{t+1},R_{t+1}\stackrel{A_{t+1}}{\to }{S}_{t+2},R_{t+2}\stackrel{A_{t+2}}{\to }{S}_{t+3},R_{t+3}\cdots$$

沿轨迹的折扣回报为：

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

显然 $G_t$ 也是一个随机变量。

定义状态价值函数（state-value function）：

$$v_{\pi }(s)=\mathbb{E}[G_t\mid S_t=s]$$

该函数能告诉我们当前的局势好不好。

举例：

$$v_{{\pi }_1}(s_1)=0+\gamma 1+{\gamma }^{2}1+\cdots =\frac{\gamma }{1-\gamma }$$$$v_{{\pi }_2}(s_1)=-1+\gamma 1+{\gamma }^{2}1+\cdots =-1+\frac{\gamma }{1-\gamma }$$$$v_{{\pi }_3}(s_1)=0.5(-1+\frac{\gamma }{1-\gamma })+0.5\left(\frac{\gamma }{1-\gamma }\right)=-0.5\left(\frac{\gamma }{1-\gamma }\right)$$

推导

$G_t$ 可以写为：

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

则：

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

有：

$$\begin{array}{rl}\mathbb{E}[R_{t+1}\mid S_t=s]=& \sum _a\pi (a\mid s)\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a]\\ =& \sum _a\pi (a\mid s)\sum _{r}p(r\mid s,a)r\end{array}$$$$\begin{array}{rl}\mathbb{E}[G_{t+1}\mid S_t=s]=& \sum _{s^{\prime }}\mathbb{E}[G_{t+1}\mid S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }\mid s)\\ =& \sum _{s^{\prime }}\mathbb{E}[G_{t+1}\mid S_{t+1}=s^{\prime }]p(s^{\prime }\mid s)\\ =& \sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }\mid s)\\ =& \sum _{s^{\prime }}{v}_{\pi }(s^{\prime })\sum _{a}p(s^{\prime }\mid s,a)\pi (a\mid s)\\ =& \sum _a\pi (a\mid s)\sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{\pi }\left(s^{\prime }\right)\end{array}$$

得到贝尔曼公式：

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

TIP

同样以上面的图片为例，对于策略 ${\pi }_1$：

$$\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}$$

得到：

$$v_{\pi }(s_4)=v_{\pi }(s_3)=v_{\pi }(s_2)=\frac{1}{1-\gamma }$$$$v_{\pi }(s_1)=\frac{\gamma }{1-\gamma }$$

同样以上面的图片为例，对于策略 ${\pi }_3$：

$$\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}$$

得到：

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

贝尔曼公式

定义：

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

有：

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

对于状态 $s_i$:

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

写成矩阵形式：

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

其中：

• $v_{\pi }=[v_{\pi }(s_1),\cdots ,v_{\pi }(s_n){]}^{\mathrm{\top }}\in {\mathbb{R}}^n$
• $r_{\pi }=[r_{\pi }(s_1),\cdots ,r_{\pi }(s_n){]}^{\mathrm{\top }}\in {\mathbb{R}}^n$
• ${\mathbf{P}}_{\pi }\in {\mathbb{R}}^{n\times n}$，$[{\mathbf{P}}_{\pi }{]}_{ij}=p_{\pi }(s_j\mid s_i)$

例子

$$\underset{v_{\pi }}{\underbrace{\left[\begin{array}{l}{v}_{\pi }\left(s_1\right)\\ v_{\pi }\left(s_2\right)\\ v_{\pi }\left(s_3\right)\\ v_{\pi }\left(s_4\right)\end{array}\right]}}=\underset{r_{\pi }}{\underbrace{\left[\begin{array}{l}{r}_{\pi }\left(s_1\right)\\ r_{\pi }\left(s_2\right)\\ r_{\pi }\left(s_3\right)\\ r_{\pi }\left(s_4\right)\end{array}\right]}}+\gamma \underset{P_{\pi }}{\underbrace{\left[\begin{array}{llll}{p}_{\pi }(s_1\mid s_1)& p_{\pi }(s_2\mid s_1)& p_{\pi }(s_3\mid s_1)& p_{\pi }(s_4\mid s_1)\\ p_{\pi }(s_1\mid s_2)& p_{\pi }(s_2\mid s_2)& p_{\pi }(s_3\mid s_2)& p_{\pi }(s_4\mid s_2)\\ p_{\pi }(s_1\mid s_3)& p_{\pi }(s_2\mid s_3)& p_{\pi }(s_3\mid s_3)& p_{\pi }(s_4\mid s_3)\\ p_{\pi }(s_1\mid s_4)& p_{\pi }(s_2\mid s_4)& p_{\pi }(s_3\mid s_4)& p_{\pi }(s_4\mid s_4)\end{array}\right]}}\underset{v_{\pi }}{\underbrace{\left[\begin{array}{l}{v}_{\pi }\left(s_1\right)\\ v_{\pi }\left(s_2\right)\\ v_{\pi }\left(s_3\right)\\ v_{\pi }\left(s_4\right)\end{array}\right]}}$$

以上面的图片为例，对于策略 ${\pi }_1$：

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

求解

直接求解：

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

采用迭代法：

$$v_{k+1}=r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k$$

有：

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

动作价值函数

定义动作价值函数（action-value function）：

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

有：

$$v_{\pi }(s)=\sum _a\pi (a\mid s)q_{\pi }(s,a)$$

对应贝尔曼公式：

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

即：

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

例子

以上面的图片为例，对于策略 ${\pi }_2$：

容易得出：

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

有：

$$\begin{array}{r}{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}$$