贝尔曼公式（Bellman Equation）

对于单过程：

$$S_t \xrightarrow{A_t} R_{t+1},\, S_{t+1}$$

• $S_t$ 状态； $A_t$ 动作； $R_{t+1}$ 奖励

• 均为随机变量

• $S_t \rightarrow A_t$ is governed by $\pi(A_t = a \mid S_t = s)$

• $S_t, A_t \rightarrow R_{t+1}$ is governed by $p(R_{t+1} = r \mid S_t = s, A_t = a)$

• $S_t, A_t \rightarrow S_{t+1}$ is governed by $p(S_{t+1} = s' \mid S_t = s, A_t = a)$

对于多过程：

$$S_t \xrightarrow{A_t} R_{t+1},\, S_{t+1} \xrightarrow{A_{t+1}} R_{t+2},\, S_{t+2} \xrightarrow{A_{t+2}} R_{t+3},\, \ldots$$

$$\text{discounted return}=G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$$

状态价值 State value

The expectation of $G_t$

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

• 是 s 的函数，从 s 开始的状态价值

• 基于策略 $\pi$

• 是多个Trajectory的return的均值

---

公式推导 Deriving the Bellman equation

1.提取 $G_t$ 中的 $\gamma$ 得到递推公式

$$\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \cdots \right) \\ &= R_{t+1} + \gamma G_{t+1}. \end{aligned}$$

2.  应用到状态价值公式

$$\begin{aligned} v_\pi(s) &= \mathbb{E}\!\left[ G_t \mid S_t = s \right] \\ &= \mathbb{E}\!\left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s \right] \\ &= \mathbb{E}\!\left[ R_{t+1} \mid S_t = s \right] + \gamma \mathbb{E}\!\left[ G_{t+1} \mid S_t = s \right]. \end{aligned}$$

对于第一部分 $\mathbb{E}\!\left[ R_{t+1} \mid S_t = s \right]$ ，相当于 the mean of immediate rewards 当前奖励的均值

$$\begin{aligned} \mathbb{E}\!\left[ R_{t+1} \mid S_t = s \right] &= \sum_a \pi(a \mid s)\, \mathbb{E}\!\left[ R_{t+1} \mid S_t = s, A_t = a \right] \\ &= \sum_a \pi(a \mid s)\, \sum_r p(r \mid s, a)\, r . \end{aligned}$$

对于第二部分 $\mathbb{E}\!\left[ G_{t+1} \mid S_t = s \right]$ ，相当于 the mean of future rewards 未来奖励的均值

$$\begin{aligned} \mathbb{E}\!\left[ G_{t+1} \mid S_t = s \right] &= \sum_{s'} \mathbb{E}\!\left[ G_{t+1} \mid S_t = s, S_{t+1} = s' \right] p(s' \mid s) \\ &= \sum_{s'} \mathbb{E}\!\left[ G_{t+1} \mid S_{t+1} = s' \right] p(s' \mid s) \\ &= \sum_{s'} v_\pi(s')\, p(s' \mid s) \\ &= \sum_{s'} v_\pi(s') \sum_a p(s' \mid s, a)\, \pi(a \mid s). \end{aligned}$$

相关信息

$\mathbb{E}\left[ G_{t+1} \mid S_t = s, S_{t+1} = s' \right] = \mathbb{E}\left[ G_{t+1} \mid S_{t+1} = s'\right]$ 是根据，马尔可夫无记忆性

因此，贝尔曼公式如下

$$\begin{aligned} v_\pi(s) &= \mathbb{E}\!\left[ R_{t+1} \mid S_t = s \right] + \gamma \, \mathbb{E}\!\left[ G_{t+1} \mid S_t = s \right] \\[6pt] &= \underbrace{\sum_a \pi(a \mid s) \sum_r p(r \mid s, a)\, r}_{\text{mean of immediate rewards}} + \gamma \, \underbrace{\sum_a \pi(a \mid s) \sum_{s'} p(s' \mid s, a)\, v_\pi(s')}_{\text{mean of future rewards}} \\[6pt] &= \sum_a \pi(a \mid s) \left[ \sum_r p(r \mid s, a)\, r + \gamma \sum_{s'} p(s' \mid s, a)\, v_\pi(s') \right], \qquad \forall s \in \mathcal{S}. \end{aligned}$$

相关信息

对于未来奖励的均值 交换了求和次序

• 贝尔曼公式是不同状态的状态价值的关系的函数
• 是公式集合，每个状态都有想这样的公式

公式变量含义

• $v_\pi(s)$ 和 $v_\pi(s')$ 是需要计算的状态价值（state values），这体现了自举（Bootstrapping）的思想。

• $\pi(a \mid s)$ 是给定的策略（policy），求解该方程的过程称为策略评估（policy evaluation）。

• $p(r \mid s, a)$ 和 $p(s' \mid s, a)$ 表示环境的动态模型（dynamic model）。

---

矩阵-向量形式

对于状态集合的每个状态都有一个贝尔曼公式，共 $|\mathcal{S}|$ 个公式。将这些公式放在一起得到一组线性方程，可以写成矩阵-向量形式。

将贝尔曼方程改写为：

$$v_{\pi}(s)=r_{\pi}(s)+\gamma\sum_{s'}p_{\pi}(s'\mid s)\,v_{\pi}(s') \tag{1}$$

其中，

$$r_{\pi}(s):=\sum_{a}\pi(a\mid s)\sum_{r}p(r\mid s,a)\,r,\qquad p_{\pi}(s'\mid s):=\sum_{a}\pi(a\mid s)\,p(s'\mid s,a).$$

假设状态可以编号为 $s_i\ (i=1,\ldots,n)$ 。

对于状态 $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).$$

将所有状态对应的方程合在一起，并改写为矩阵-向量形式：

$$\mathbf{v}_{\pi}=\mathbf{r}_{\pi}+\gamma \mathbf{P}_{\pi}\mathbf{v}_{\pi}.$$

其中

• $\mathbf{v}_{\pi}:=\bigl[v_{\pi}(s_1),\ldots,v_{\pi}(s_n)\bigr]^{\mathsf T}\in\mathbb{R}^n$

• $\mathbf{r}_{\pi}:=\bigl[r_{\pi}(s_1),\ldots,r_{\pi}(s_n)\bigr]^{\mathsf T}\in\mathbb{R}^n$

• $\mathbf{P}_{\pi}\in\mathbb{R}^{n\times n}$ ，其中 $[\mathbf{P}{\pi}]{ij}:=p_{\pi}(s_j\mid s_i)$ ，是状态转移矩阵。

如果有四个状态

$$\underbrace{ \begin{bmatrix} v_{\pi}(s_1)\\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix}}_{\mathbf{v}_{\pi}} = \underbrace{ \begin{bmatrix} r_{\pi}(s_1)\\ r_{\pi}(s_2)\\ r_{\pi}(s_3)\\ r_{\pi}(s_4) \end{bmatrix}}_{\mathbf{r}_{\pi}} +\gamma\, \underbrace{ \begin{bmatrix} 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{bmatrix}}_{\mathbf{P}_{\pi}} \underbrace{ \begin{bmatrix} v_{\pi}(s_1)\\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix}}_{\mathbf{v}_{\pi}}.$$

---

例子

$$\begin{bmatrix} v_{\pi}(s_1)\\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} = \begin{bmatrix} 0.5(0)+0.5(-1)\\ 1\\ 1\\ 1 \end{bmatrix} +\gamma \begin{bmatrix} 0 & 0.5 & 0.5 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} v_{\pi}(s_1)\\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix}.$$

---

求解

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

• 封闭解：

  • $$\mathbf{v}_{\pi} = (\mathbf{I} - \gamma \mathbf{P}_{\pi})^{-1} \mathbf{r}_{\pi}$$

• 数值迭代解：

  • $$\mathbf{v}_{k+1} = \mathbf{r}_{\pi} + \gamma \mathbf{P}_{\pi} \mathbf{v}_{k}$$

---

动作价值 Action value

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

• 是状态动作对 $(s,a)$ 的函数

• 依赖于策略 $\pi$

根据条件期望的性质可得：

$$\underbrace{\mathbb{E}\left[ G_t \mid S_t = s \right]}_{v_{\pi}(s)} = \sum_{a} \underbrace{\mathbb{E}\left[ G_t \mid S_t = s, A_t = a \right]}_{q_{\pi}(s,a)} \pi(a \mid s)$$

因此，

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

比较状态价值公式，得到动作价值公式

$$q_{\pi}(s,a) = \sum_{r} p(r \mid s,a) r + \gamma \sum_{s'} p(s' \mid s,a) v_{\pi}(s')$$

• 两个价值可以互相转化

注意：

• 动作价值很重要，可以决定选择哪个动作
• 可以通过状态价值而计算动作价值
• 也可以直接计算动作价值，通过数据，可以依赖模型或不依赖模型