2.贝尔曼公式 • CoderXL's Blog

课程笔记 →

Bellman Equation

文中大量使用 $\pi$ 表示 policy 策略，因为 $\pi$ 是希腊字母中与 p 对应的字母。

Evaluating Policy#

Policy 会生成 trajectory，而 trajectory 对应一个 return. 因此可以通过 return 评估一个 policy 的好坏。

Policy 和 reward 往往都不是确定性的，因此需要计算 return 的期望。

Calculating Return#

一、定义法#

计算 reward （贴现之后的）加和。

二、自举法（Bootstrapping）#

184

考察这个 policy，发现 agent 会进入循环。

设 $v_i$ 为 agent 位于 $s_i$ 时，未来的 reward 之和（贴现后）： $\sum_{k=i}^\infty \gamma^{k-i} r_{(k-1) \% 4 + 1}$

那么可以列出方程组

\begin{equation*} \begin{cases} v_1 = r_1 + \gamma v_2 \\ v_2 = r_2 + \gamma v_3 \\ v_3 = r_3 + \gamma v_4 \\ v_4 = r_4 + \gamma v_1 \end{cases} \end{equation*}

这个方程组是一个非齐次线性方程组，有唯一解。

写成矩阵向量形式，即 $\boldsymbol{v} = \boldsymbol{r} + \gamma \boldsymbol{P} \boldsymbol{v}$ .

其中

\boldsymbol{P} = \begin{bmatrix*} 0 &1 &0 &0\\ 0 &0 &1 &0\\ 0 &0 &0 &1\\ 1 &0 &0 &0 \end{bmatrix*}

这就是贝尔曼公式，或者说在这种特殊的确定性情况下的实例。

实际上， $\boldsymbol{P}$ 就是一步可达的状态转移矩阵。

State Value#

在继续之前，有必要严谨化符号。

考察单步过程

S_t \overset{A_t}{\to} R_{t+1}, S_{t+1}

其中：

$t, t+1$ 表示离散的时间步
$S_t$ 表示时刻 $t$ 时的状态
$A_t$ 表示 $S_t$ 处所采取的动作
$R_{t+1}$ 表示在采取动作 $A_t$ 后得到的奖励
$S_{t+1}$ 表示在采取动作 $A_t$ 后转移到的状态

当然， $R_{t+1}$ 的下标有时也记成 $R_t$ ，数学结构不变。

注意， $S_t, A_t, R_{t+1}$ 均为随机变量，并服从以下分布：

$S_t \to A_t$ 服从策略分布 $\pi(A_t=a \mid S_t=s)$
$S_t, A_t \to R_{t+1}$ 服从奖励分布 $p(R_{t+1}=r \mid S_t=s, A_t=a)$
$S_t, A_t \to S_{t+1}$ 服从状态转移分布 $p(S_{t+1}=s' \mid S_t=s, A_t=a)$

考察多步过程

S_t \overset{A_t}{\to} R_{t+1}, S_{t+1} \overset{A_{t+1}}{\to} R_{t+2}, S_{t+2} \overset{A_{t+2}}{\to} \cdots

记 $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$ ，其中 $\gamma\in[0,1)$ 是贴现系数。

则 $G_t$ 也是随机变量。

由上述定义知， $G_t$ 就是一个 trajectory 的 discounted return，而 state value 就是 $G_t$ 的期望值。

state-value function (or simply state value) 定义：

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

含义：从某个状态 $s$ 出发，在给定策略 $\pi$ 下，期望得到的 discounted return. 这个量可以评估状态 $s$ 的“价值”。

确定性的情况下，state value 和 discounted return 是相同的。

在一般的情况下，对于 trajectory 的一个采样，仍然有 $G_t = R_{t+1} + \gamma G_{t+1}$

因此，

\begin{align*} 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] \end{align*}

运用全期望公式化简第一项，得：

\begin{align*} \mathbb{E}[R_{t+1} \mid S_t = s] &= \mathbb{E}[\mathbb{E}[R_{t+1} \mid S_t=s, A_t = a] \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{align*}

这一项表示，从 $s$ 出发，按照 policy 走一步能得到的奖励的期望。

再处理第二项：

\begin{align*} \mathbb{E}[G_{t+1} \mid S_t = s] &= \mathbb{E}[\mathbb{E}[G_{t+1} \mid S_{t+1}=s',S_t=s] \mid S_t=s]\\ &= \mathbb{E}[\mathbb{E}[G_{t+1} \mid S_{t+1}=s'] \mid S_t=s]\\ &= \mathbb{E}[v_\pi (s') \mid S_t=s]\\ &=\sum_{s'}v_\pi (s') \sum_a p(s' \mid s,a)\pi(a \mid s) \end{align*}

这一项表示，从 $s$ 出发，到达的新状态的 state value 的期望。

最终，可整理出：

v_\pi (s)=\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),\ s\in S

此即贝尔曼公式。

它刻画了状态空间中，不同状态之间的 state-value function 的关系。

分析一下：

等号两侧都有 $v_\pi$ ，意味着这是一个 bootstrap 形式的公式。
对于有限的 $S$ ，可以对所有 $s$ 列出贝尔曼公式，形成方程组，然后求解出 $v_\pi(s)$ .
贝尔曼公式依赖于 policy $\pi$ ，因此对于给定 policy，求解贝尔曼公式被称为 policy evaluation.
$p(r \mid s,a)$ 和 $p(s' \mid s,a)$ 反映了对世界的建模，在此处我们需要它已知。

Bellman Equation#

贝尔曼公式可以写成矩阵-向量形式以便理解和求解。

先定义两个量，对应第一项和第二项：

r_\pi (s) \triangleq \sum_a \pi(a \mid s) \sum_r p(r \mid s,a)r

p_\pi (s' \mid s) \triangleq \sum_a \pi(a \mid s) p(s' \mid s,a)

然后，可将贝尔曼公式整理成：

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

记 $n = \lvert S \rvert$ .

将 $p_\pi(s_j \mid s_i)$ 写成一个 $n \times n$ 的矩阵 $\boldsymbol{P}_\pi$ ，其中 $[\boldsymbol{P}_\pi]_{i,j} = p_\pi(s_j \mid s_i)$ ；
将 $v_\pi(s_i)$ 写成列向量 $\boldsymbol{v}_\pi = [v_\pi(s_1), \dots, v_\pi(s_n)]^T \in \mathbb{R}^n$ ；
将 $r_\pi(s_i)$ 写成列向量 $\boldsymbol{r}_\pi = [r_\pi(s_1), \dots, r_\pi(s_n)]^T \in \mathbb{R}^n$ ；

那么原式可化为：

矩阵-向量形式

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

求解贝尔曼公式#

求解贝尔曼公式的过程称为 policy evaluation，是 RL 中的基本问题，是优化 policy 的关键。

闭式解#

根据线性代数理论，可以直接得到 $\boldsymbol{v}_\pi = (\boldsymbol{I} - \gamma \boldsymbol{P}_\pi)^{-1} \boldsymbol{r}_\pi$ .

迭代法#

实践中通常不会使用闭式解求解：求逆在状态空间 $n$ 较大时计算过于复杂。

\boldsymbol{v}_{k+1} = \boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi \boldsymbol{v}_k

由不动点理论保证， $\boldsymbol{v}_{k} \to \boldsymbol{v}_\pi = (\boldsymbol{I} - \gamma \boldsymbol{P}_\pi)^{-1} \boldsymbol{r}_\pi,\quad k \to \infty$ .

证明

v_k \to v_\pi

设 $\delta_k = v_k - v_\pi$ ，我们只需证明 $\delta_k \to 0,\quad k \to \infty$ .

代入迭代公式，得：

\boldsymbol{v}_\pi + \boldsymbol{\delta}_{k+1} = \boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi(\boldsymbol{v}_\pi + \boldsymbol{\delta}_k)

使用贝尔曼公式的矩阵-向量形式，可消去 $\boldsymbol{v}_\pi$ 化简，得：

\boldsymbol{\delta}_{k+1} = \gamma \boldsymbol{P}_\pi\boldsymbol{\delta}_k

由于 $\gamma \in [0,1)$ ， $[\boldsymbol{P}_\pi]_{i,j} \in [0,1]$ ，且 $\boldsymbol{P}_\pi \boldsymbol{1} = \boldsymbol{1}$ ，因此 $\delta_k \to 0,\quad k \to \infty$ .

由这个例子可知，state value 可以反映一个 policy 的好坏，好的 policy 总体得分更高。

Action Value#

对比 state value 和 action value：

state value 表示 agent 从某个 state 开始，期望可以得到的 (discounted) return.
action value 表示 agent 从某个 state 开始并采取某个 action，期望可以得到的 (discounted) return.

action value 定义：

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

state value 可以理解为对 action value 再取一次期望：

$v_\pi(s) = \mathbb{E}[q_\pi(s,a) \mid S_t = s]$
或者写成
$v_\pi(s) = \sum_a \pi(a \mid s) q_\pi(s,a)$

比较上式与

v_\pi (s)=\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],\ s\in S

可得 action value 表达式为：

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

重要

即便 policy 中没有包含某个 action，这个 action 的 action value 仍然存在。

Action Value 的计算#

有若干方法：

先通过 Bellman 公式算出 state value，再计算 action value
直接采样计算（model-free）