Deriving the Bellman Equation

考虑以下 Trajectory ：

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

回报为：

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

则 State Value 可以写作：

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

先来看 $\mathbb{E}^\pi \left[R_{t+1}\mid S_t = s \right]$ ：

$$\begin{aligned} \mathbb{E}^\pi \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|s,a)\cdot r \end{aligned}$$

关于 $\mathbb{E}\left[R_{t+1}\mid S_t=s,A_t=a\right]$ 到 $\sum_r p(r|s,a)\cdot r$ 的变换，其实就是当前策略和状态确定时，可以获得的奖励集合也是确定的，所以期望就是所有可能收益加权求和。

可以说，它的含义就是在第 $t$ 步采取动作之后、环境返回的立即奖励（immediate reward）的期望值。

再来看 $\mathbb{E}^\pi \left[G_{t+1}\mid S_t = s \right]$ ：

$$\begin{aligned} \mathbb{E}^\pi \left[G_{t+1}\mid S_t = s \right] &= \sum_{s^\prime}\mathbb{E}\left[G_{t+1}\mid S_t=s,S_{t+1}=s^\prime\right]p(s^\prime\mid s)\\ &= \sum_{s^\prime}\mathbb{E}\left[G_{t+1}\mid S_{t+1}=s^\prime\right]p(s^\prime\mid s)\quad\text{(Markov property)}\\ &= \sum_{s^\prime}v^\pi(s^\prime)\sum_a \pi(a|s)p(s^\prime|s,a) \end{aligned}$$

它的物理含义就是第 $t$ 步采取动作之后，下一步带来的所有未来奖励（future reward）的期望值。

贝尔曼公式（Bellman Equation） 就是：

$$\begin{aligned} v^\pi(s) &= \mathbb{E}^\pi \left[R_{t+1}\mid S_t = s \right]+\gamma\mathbb{E}^\pi \left[G_{t+1}\mid S_t = s \right]\\ &=\sum_a\pi(a\mid s)\sum_r p(r|s,a)\cdot r + \gamma\sum_{s^\prime}v^\pi(s^\prime)\sum_a \pi(a|s)p(s^\prime|s,a)\\ &=\underbrace{\sum_a\pi(a\mid s)\sum_r p(r|s,a)\cdot r}_{\text{mean of immediate rewards}} + \underbrace{\gamma\sum_a\pi(a|s)\sum_{s^\prime} p(s^\prime|s,a)v^\pi(s^\prime)}_\text{mean of future rewards}\\ &= \sum_a\pi(a\mid s)\left[\sum_r p(r|s,a)\cdot r + \sum_{s^\prime} p(s^\prime|s,a)v^\pi(s^\prime)\right],\forall s\in \mathbb{S} \end{aligned}$$

其中：

• $\pi(a\mid s)$ 由策略决定；
• $p(r\mid s,a)$ 和 $p(s^\prime\mid s,a)$ 由 model 决定；（对于 model-free 的情况则需要采用另外的算法）
• 虽然 $v^\pi(s)$ 依赖于 $v^\pi(s^\prime)$ ，但事实上可以写出一组形如上面的式子，再求解线性方程组（不难看成其是满秩的）

为求解方便，还可以进一步将其写为矩阵形式：

$$\begin{aligned} v^\pi(s) &= \mathbb{E}^\pi \left[R_{t+1}\mid S_t = s \right]+\gamma\mathbb{E}^\pi \left[G_{t+1}\mid S_t = s \right]\\ &=\sum_a\pi(a\mid s)\sum_r p(r|s,a)\cdot r + \gamma\sum_{s^\prime}v^\pi(s^\prime)\sum_a \pi(a|s)p(s^\prime|s,a)\\ &= r^\pi(s) + \gamma \sum_{s^\prime}v^\pi(s^\prime)p(s^\prime\mid s),\forall s\in \mathbb{S} \end{aligned}$$

对于 $s_i\in \mathbb{S}=\{s_1,s_2,\cdots,s_n\}$ ：

$$v^\pi(s_i) = r^\pi(s_i) + \gamma \sum_{s_j}v^\pi(s_j)p(s_j\mid s_i)$$

令：

• $v^\pi=\begin{bmatrix}v^\pi(s_1),v^\pi(s_2),\cdots,v^\pi(s_n)\end{bmatrix}^T\in\mathbb{R}^n$ ；
• $r^\pi=\begin{bmatrix}r^\pi(s_1),r^\pi(s_2),\cdots,r^\pi(s_n)\end{bmatrix}^T\in \mathbb{R}^n$ ；
• $P^\pi\in \mathbb{R}^{n\times n},\text{where }P^\pi_{i,j} = p(s_j\mid s_i)$ ，即状态转移矩阵；

则 Bellman Equation 可以写作：

$$v^\pi = r^\pi + \gamma P^\pi v^\pi$$