强化学习（5）贝尔曼公式的推导-拓冰建站

Bellman equation describes the relationship among the values of all states

推导

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

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots \\ = R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \ldots) \\ = R_{t+1} + \gamma G_{t+1}$

即：当前时刻得到的return=立即能得到的reward＋下一个时刻的return

因此，由条件期望的线性性：

对状态s下的state value有： $v_\pi(s) = \mathbb{E}[G_t \mid S_t = s] \\ = \mathbb{E}[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ = \mathbb{E}[R_{t+1} \mid S_t = s] + \gamma \mathbb{E}[G_{t+1} \mid S_t = s]$

接下来只需分别计算两个条件期望

第一项

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

第一项是状态s下的immediate reward的均值

第二项

$\mathbb{E}[G_{t+1} | S_t = s] \\ = \sum_{s'} \mathbb{E}[G_{t+1} | S_t = s, S_{t+1} = s'] p(s' | s) \\ = \sum_{s'} \mathbb{E}[G_{t+1} | S_{t+1} = s'] p(s' | s) \\ = \sum_{s'} v_\pi(s') p(s' | s) \\ = \sum_{s'} v_\pi(s') \sum_a p(s' | s, a) \pi(a | s)$

对于当前状态s，下一个状态可能有好多种s'，到每一种s'的概率为 $p(s' | s)$

$\mathbb{E}[G_{t+1} | S_{t+1} = s']$ 表示从状态s'出发得到的return的均值，也就是s'的state value： $v_\pi(s')$

第二项是future reward的均值

加和

$v_\pi(s) = \sum_a \pi(a|s) \sum_r p(r|s,a) r + \gamma \sum_a \pi(a|s) \sum_{s'} p(s'|s,a) v_\pi(s')$

$= \sum_a \pi(a|s) \left[ \sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v_\pi(s') \right] \quad \forall s \in \mathcal{S}$

以上就是贝尔曼公式，它描述了不同状态的state value的关系，包含两项：immediate reward和future reward。由于 $\forall s \in \mathcal{S}$ ，所以贝尔曼公式对于state space里的所有state都成立

Solving the equation is called policy evaluation.

grid-world example

$v_\pi(s) = \sum_a \pi(a|s) \left[ \sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v_\pi(s') \right]$

可得： $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).$

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