RL的原理-2-贝尔曼公式 • Linxii's Blog

1.return的重要性#

在强化学习中，智能体的目标是最大化其在环境中获得的累积奖励（return 或者 discounted return）。

四宫格循环走的情况：

$v_{1}=r_{1}+\gamma r_{2}+\gamma^{2} r_{3}+...=r_{1}+\gamma v_{2}$

$v_{2}=r_{2}+\gamma r_{3}+\gamma^{2} r_{4}+...=r_{2}+\gamma v_{3}$

$v_{3}=r_{3}+\gamma r_{4}+\gamma^{2} r_{1}+...=r_{3}+\gamma v_{4}$

$v_{4}=r_{4}+\gamma r_{1}+\gamma^{2} r_{2}+...=r_{4}+\gamma v_{1}$

上面的公式展示了return的递归性质，可以写成矩阵的形式

\begin{bmatrix} v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \end{bmatrix} = \begin{bmatrix} r_{1} \\ r_{2} \\ r_{3} \\ r_{4} \end{bmatrix} + \gamma \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \end{bmatrix}

上面的矩阵形式可以写成简化的形式，通过下面这种简化的形式可以很方便的求解

\mathbf{v} = \mathbf{r} + \gamma \mathbf{P} \mathbf{v}

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

G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...

状态值函数（State Value Function）表示在给定状态下，智能体在未来能够获得的累积奖励的期望值。状态值函数通常表示为 $v_{\pi}(s)$ ，其中 $s$ 表示状态， $\pi$ 表示策略。

v_{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s]

return 与 state value的关系

return是针对单个trajestory而言的，而state value是对所有trajestory而言的。state value表示在给定状态下，智能体在未来能够获得的累积奖励的期望值。

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

$=\mathbb{E} [R_{t+1} | S_t = s]+ \gamma \mathbb{E}_{\pi}[G_{t+1} | S_t = 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) [\sum_{r}p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v_{\pi}(s') ]$

（1）s状态的state value是当前状态的所有return的期望值：

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

（2）首先看第一项，第一项就是当前状态下，所有可能动作下的奖励（reward）的期望值：

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

其中， $\pi(a|s)$ 表示在状态 $s$ 下选择动作 $a$ 的概率， $p(r|s,a)$ 表示在状态 $s$ 下选择动作 $a$ 后获得奖励 $r$ 的概率。

(3)再看第二项，第二项是当前状态下，所有可能动作下，所有可能转移到的下一个状态的state value的期望值：

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

首先把第一项中的部分组合一下，这部分就是当前状态下执行不同的Action得到的reward的期望值：

r_{\pi}(s) = \sum_{a} \pi(a|s) \sum_{r} p(r|s,a)r

然后把第二项中的部分组合一下，这部分就是从 $s$ 到 $s'$ 的概率：

P_{\pi}(s,s') = \sum_{a} \pi(a|s) p(s'|s,a)

于是贝尔曼公式可以写成下面的形式：

v_{\pi}(s) = r_{\pi}(s) + \gamma \sum_{s'} P_{\pi}(s'|s) v_{\pi}(s')

上面的公式可以写成矩阵与向量的形式：

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

求解

根据矩阵的形式，可以使用逆矩阵进行求解，不过实际应用中并不使用这种解法，因为状态空间通常非常大，计算逆矩阵的开销很大。通常使用迭代方法来近似求解。

v_{k+1} \rightarrow r_{\pi} + \gamma P_{\pi} v_{k}

当 $k \rightarrow \infty$ 时， $v_{k}$ 会收敛到 $v_{\pi}$ 。

$q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$ $= \sum_{r} p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v_{\pi}(s')$

Action Value 与 State Value的关系：

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