【强化学习】2-贝尔曼公式
Categories: RL
目录
一、例子：为什么return很重要
1. 例子1
以下面的情况为例，考虑三种policy：
从状态 $s_1$ 开始，对于第1种策略，其折扣回报discounted return为：
\[\begin{equation} \begin{aligned} \text{return}_1 &= 0 + \gamma 1 + \gamma^2 1 + \ldots \\ &= \gamma (1 + \gamma + \gamma^2 + \ldots) \\ &= \frac{\gamma}{1 - \gamma} \end{aligned} \end{equation}\]该return是按照上一节中将回合任务（episodic tasks）转换为持续任务（continuing tasks）来计算的。
对于第2种策略，在状态 $s_1$ 下，其折扣回报为：
\[\begin{equation} \begin{aligned} \text{return}_2 &= -1 + \gamma 1 + \gamma^2 1 + \ldots \\ &= -1 + \gamma (1 + \gamma + \gamma^2 + \ldots) \\ &= -1 + \frac{\gamma}{1 - \gamma} \end{aligned} \end{equation}\]前两种策略是确定性的，而第3种策略是随机性的，在状态 $s_1$ 下，其折扣回报为：
\[\begin{equation} \begin{aligned} \text{return}_3 &= 0.5 \left( -1 + \frac{\gamma}{1 - \gamma} \right) + 0.5 \left( \frac{\gamma}{1 - \gamma} \right) \\ &= -0.5 + \frac{\gamma}{1 - \gamma} \end{aligned} \end{equation}\]综上 $\text{return}_1 > \text{return}_3 > \text{return}_2$ ，与直观上一致，第一种策略更好。因此，return之所以重要就是因为可以用来评估策略的好坏。
2. 例子2
考虑下面的例子来计算不同状态的return：
令 $v_i$ 表示由状态 $s_i$ 计算得到的return值，有：
\[\begin{align} v_1 &= r_1 + \gamma r_2 + \gamma^2 r_3 + \ldots \\ v_2 &= r_2 + \gamma r_3 + \gamma^2 r_4 + \ldots \\ v_3 &= r_3 + \gamma r_4 + \gamma^2 r_1 + \ldots \\ v_4 &= r_4 + \gamma r_1 + \gamma^2 r_2 + \ldots \end{align}\]进一步，将第二项之后的 $\gamma$ 提取出来，有：
\[\begin{align} v_1 &= r_1 + \gamma (r_2 + \gamma r_3 + \ldots) = r_1 + \gamma v_2, \\ v_2 &= r_2 + \gamma (r_3 + \gamma r_4 + \ldots) = r_2 + \gamma v_3, \\ v_3 &= r_3 + \gamma (r_4 + \gamma r_1 + \ldots) = r_3 + \gamma v_4, \\ v_4 &= r_4 + \gamma (r_1 + \gamma r_2 + \ldots) = r_4 + \gamma v_1. \end{align}\]以 $v_1$ 为例，它等于状态 $s_1$ 当前的奖励 $r_1$ 加上状态 $s_2$ 所得到的 $v_2$ 。可见return的value互相依赖，$v_1$ 依赖于 $v_2$ ，$v_2$ 依赖于 $v_3$ …，这种现象称为Bootstrapping，即求解这些值，却首先要知道这些值本身。可以通过矩阵向量的形式，将上面的式子写为：
\[\begin{equation} \underbrace{\begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix} }_{\mathbf{v} } = \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} + \begin{bmatrix} \gamma v_2 \\ \gamma v_3 \\ \gamma v_4 \\ \gamma v_1 \end{bmatrix} = \underbrace{\begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} }_{\mathbf{r} } + \gamma \underbrace{\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} }_{\mathbf{P} } \underbrace{\begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix} }_{\mathbf{v} } \end{equation}\]即：
\[\begin{equation} \mathbf{v} = \mathbf{r} + \gamma \mathbf{P} \mathbf{v} \end{equation}\]上式就是本例在确定性情况下得到的贝尔曼公式（Bellman Equation），其解为 $\mathbf{v} = (\mathbf{I} - \gamma \mathbf{P})^{-1} \mathbf{r}$ ，这里的 $\mathbf{P}$ 实际上跟policy和state transition有关。
二、State Value
1. 符号定义
考虑单步过程：$S_t \xrightarrow{A_t} R_{t+1}, S_{t+1}$
其中：
- $t$ ：时间步
- $S_t$ ：$t$ 时刻的状态
- $A_t$ ：在状态 $S_t$ 执行的动作
- $R_{t+1}$ ：执行动作 $A_t$ 后得到的奖励（有时候也写作 $R_t$ ，含义是一致的，即immediate reward）
- $S_{t+1}$ ：执行动作 $A_t$ 后得到的状态
这里 $S_t,A_t,R_{t+1}$ 都是大写字母，代表随机变量，$S_t, S_{t+1} \in \mathcal{S}; ~ A_t \in \mathcal{A}(S_t); ~ R_{t+1} \in \mathcal{R}(S_t,A_t)$ 。它们由以下概率分布获得：
- $S_t \rightarrow A_t$ 由 $\pi(A_t = a | S_t = s)$ 得到
- $S_t, A_t \rightarrow R_{t+1}$ 由 $p(R_{t+1} = r | S_t = s, A_t = a)$ 得到
- $S_t, A_t \rightarrow S_{t+1}$ 由 $p(S_{t+1} = s’ | S_t = s, A_t = a)$ 得到
对于一个 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}, \ldots$ ，折扣回报是：
2. ⭐️ State Value 定义
State Value定义为在一个状态 $s$ 下，折扣回报 $G_t$ 的期望：
\[\begin{equation} v_\pi(s) = \mathbb{E}[G_t \mid S_t = s] \end{equation}\]注意以下几点：
- state value是 $s$ 的函数，从不同的状态出发，得到的折扣回报的期望也不同。
- state value也和策略 $\pi$ 有关，不同策略可能会得到不同的trajectory。
- $G_t$ 是对一个
trajectory而言的，State Value则是 $G_t$ 的期望。在随机性的情况下，一个state可能会有多个trajectory，因此state value是多个trajectory的return的期望。如果是在确定性的情况下，state value和return是相等的。 - 当state value较大时，说明这个状态很有价值，因为从它出发能够获得更多的return。
在第一小节的例1中，我们计算的 $return_3$ 实际上就是state value。
三、⭐️ 贝尔曼公式推导
对于一个随机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}, \ldots$ ，折扣回报 $G_t$ 可以写为：
\[\begin{equation} \begin{aligned} 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}, \end{aligned} \end{equation}\]根据state value的定义，有：
\[\begin{equation} \begin{aligned} v_\pi(s) &= \mathbb{E}[G_t \mid S_t = s] \\ &= \mathbb{E}[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= {\color{green}{\mathbb{E}[R_{t+1} \mid S_t = s]} } + \gamma {\color{blue}{\mathbb{E}[G_{t+1} \mid S_t = s]} } \end{aligned} \end{equation}\]其中，第一项 $\color{green}{\mathbb{E}[R_{t+1} \mid S_t = s]}$ ，即状态 $s$ 的即时奖励（immediate rewards）的期望:
\[\begin{equation} \begin{aligned} \mathbb{E}[R_{t+1} \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{aligned} \end{equation}\]第二项 $\color{blue}{\mathbb{E}[G_{t+1} \mid S_t = s]}$ ，即未来奖励（future rewards）的期望：
\[\begin{equation} \begin{aligned} \mathbb{E}[G_{t+1} \mid S_t = s] &= \sum_{s'} \mathbb{E}[G_{t+1} \mid S_t = s, S_{t+1} = s'] p(s' \mid s) \\ &= \sum_{s'} \mathbb{E}[G_{t+1} \mid S_{t+1} = s'] 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} \label{eq:1} \end{equation}\]其中：
- $p(s’ \mid s)$ 是指由状态 $s$ 跳转到状态 $s’$ 的概率
- 基于马尔科夫无记忆属性，$\mathbb{E}[G_{t+1} \mid S_t = s, S_{t+1} = s’]$ 可以写为 $\mathbb{E}[G_{t+1} \mid S_{t+1} = s’]$
综上，得到⭐️贝尔曼公式：
\[\begin{equation} \begin{aligned} \color{red}{v_\pi(s)} &= \mathbb{E}[R_{t+1} \mid S_t = s] + \gamma \mathbb{E}[G_{t+1} \mid S_t = s], \\ &= \underbrace{\sum_a \pi(a \mid s) \sum_r p(r \mid s, a) r}_{\color{green}{\text{mean of immediate rewards of all action} }} + \underbrace{\gamma \sum_a \pi(a \mid s) \sum_{s'} p(s' \mid s, a) \color{red}{v_\pi(s')} }_{\color{blue}{\text{mean of future rewards of all action} }}, \\ &= \sum_a \pi(a \mid s) \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) {\color{red}{v_\pi(s')} } \right], \quad \forall s \in \mathcal{S}. \end{aligned} \label{eq:2} \end{equation}\]公式 $\eqref{eq:1}$ 中最后一行： \(①：\sum_{s'} v_\pi(s') \sum_a p(s' \mid s, a) \pi(a \mid s)\) 到公式 $\eqref{eq:2}$ 中第二行的第二项： \(②：\sum_a \pi(a \mid s) \sum_{s'} p(s' \mid s, a) v_\pi(s')\) 它们是如何变换的？ 首先，可以将①写为双重求和的形式：\(\sum_{s'} \sum_a v_\pi(s') p(s' \mid s, a) \pi(a \mid s)\) 根据非负项的双重求和可交换性，因而可以将上式写为②的形式。
因此，贝尔曼公式描述了不同状态的state value之间的关系，需要注意的几个点：
- $v_\pi(s)$ 和 $v_\pi(s’)$ 是需要计算得到的（Bootstrapping）
- 公式 $\eqref{eq:2}$ 对状态空间 $\mathcal{S}$ 中所有的状态 $s$ 都成立，有 $n$ 个状态，就有 $n$ 个这样的式子。
- 公式包括两个部分：
immediate rewards和future rewards - $\pi(a \mid s)$ 是给定的策略，求解贝尔曼公式，知道State Value后，进而可以对当前策略进行评估
- $p(r \mid s, a),p(s’ \mid s, a)$ 称为系统模型（System Model），它们可能是已知的也可能是未知的，如果是未知，则可以用model-free算法来求解
除了公式 $\eqref{eq:2}$中的表达式，在文献中还可能遇到贝尔曼方程的其他表达式形式。接下来，介绍两个等价的表达式。 第一种，由全概率法则可知： \(\begin{align} p(s' \mid s, a) = \sum_{r \in \mathcal{R} } p(s', r \mid s, a) \\ p(r \mid s, a) = \sum_{s' \in \mathcal{S} } p(s', r \mid s, a) \end{align}\) 因此公式 $\eqref{eq:2}$ 可以写为： \(\begin{equation} v_\pi(s) = \sum_{a \in \mathcal{A} } \pi(a \mid s) \sum_{s' \in \mathcal{S} } \sum_{r \in \mathcal{R} } p(s', r \mid s, a) [r + \gamma v_\pi(s')] \end{equation}\) 第二种，奖励 $r$ 在某些问题中可能仅依赖于下一个状态 $s’$。因此，我们可以将奖励写为 $r(s’)$，从而得到 $p(r(s’) \mid s, a) = p(s’ \mid s, a)$，将其代入公式 $\eqref{eq:2}$ 中得到： \(\begin{equation} v_\pi(s) = \sum_{a \in \mathcal{A} } \pi(a \mid s) \sum_{s' \in \mathcal{S} } p(s' \mid s, a) [r(s') + \gamma v_\pi(s')] \end{equation}\)
四、贝尔曼公式的向量形式与求解
1. 向量形式
将公式 $\eqref{eq:2}$ 写为：
\[\begin{equation} v_\pi(s) = r_\pi(s) + \gamma \sum_{s'} p_\pi(s' \mid s) v_\pi(s') \end{equation}\]这在概念上更为直观，即状态 $s$ 的State Value等于其即时奖励加上折扣因子乘以其余状态的State Value的加权求和。其中：
\[\begin{align} 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) \end{align}\]假设状态 $s$ 由下标标识 $s_i(i=1,2,\dots,n)$ ，便能得到 $n$ 个方程：
\[\begin{equation} v_\pi(s_i) = r_\pi(s_i) + \gamma \sum_{s_j} p_\pi(s_j \mid s_i) v_\pi(s_j) \end{equation}\]写成向量形式为：
\[\begin{equation} \boxed{v_\pi = r_\pi + \gamma P_\pi v_\pi} \label{eq:3} \end{equation}\]其中：
- $ v_\pi = [v_\pi(s_1), \ldots, v_\pi(s_n)]^T \in \mathbb{R}^n $
- $ r_\pi = [r_\pi(s_1), \ldots, r_\pi(s_n)]^T \in \mathbb{R}^n $
- $ P_\pi \in \mathbb{R}^{n \times n} $，且 $[P_\pi]_{ij} = p_\pi(s_j \mid s_i)$，是状态转移矩阵
例如，当 $n=4$ 时，$v_\pi = r_\pi + \gamma P_\pi v_\pi$ 实际上是：
\[\begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix} = \begin{bmatrix} r_\pi(s_1) \\ r_\pi(s_2) \\ r_\pi(s_3) \\ r_\pi(s_4) \end{bmatrix} + \gamma \begin{bmatrix} p_\pi(s_1|s_1) & p_\pi(s_2|s_1) & p_\pi(s_3|s_1) & p_\pi(s_4|s_1) \\ p_\pi(s_1|s_2) & p_\pi(s_2|s_2) & p_\pi(s_3|s_2) & p_\pi(s_4|s_2) \\ p_\pi(s_1|s_3) & p_\pi(s_2|s_3) & p_\pi(s_3|s_3) & p_\pi(s_4|s_3) \\ p_\pi(s_1|s_4) & p_\pi(s_2|s_4) & p_\pi(s_3|s_4) & p_\pi(s_4|s_4) \end{bmatrix} \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix}\]2. 求解State Value
公式 $\eqref{eq:3}$ 的解析表达式为：
\[\begin{equation} v_\pi = (I - \gamma P_\pi)^{-1} r_\pi \end{equation}\]在实际过程中，通常使用迭代的方式来求解：
\[\begin{equation} v_{k+1} = r_\pi + \gamma P_\pi v_k, \quad k=0,1,2,\dots \end{equation}\]通过初始化 $v_0 \in \mathbb{R}^n$ ，不断代入计算新的 $v_{k+1}$ ，可以证明：$v_k \to v_\pi = (I - \gamma P_\pi)^{-1} r_\pi, k \to \infty$
证明： 定义误差为 $\delta_k = v_k - v_\pi$。我们只需要证明 $\delta_k \to 0$。将 $v_{k+1} = \delta_{k+1} + v_\pi$ 和 $v_k = \delta_k + v_\pi$ 代入 $v_{k+1} = r_\pi + \gamma P_\pi v_k$ 得到
\[\delta_{k+1} + v_\pi = r_\pi + \gamma P_\pi (\delta_k + v_\pi)\]这可以重写为
\[\begin{aligned} \delta_{k+1} &= -v_\pi + r_\pi + \gamma P_\pi \delta_k + \gamma P_\pi v_\pi \\ &= \gamma P_\pi \delta_k - v_\pi + (r_\pi + \gamma P_\pi v_\pi) \\ &= \gamma P_\pi \delta_k \end{aligned}\]因此，
\[\delta_{k+1} = \gamma P_\pi \delta_k = \gamma^2 P_\pi^2 \delta_{k-1} = \cdots = \gamma^{k+1} P_\pi^{k+1} \delta_0\]由于 $P_\pi$ 的每个元素都是非负的且不大于1，因此对于任何 $k$，$P_\pi^k$ 的每个元素都不大于1。另一方面，由于 $\gamma < 1$，有 $\gamma^k \to 0$，因此当 $k \to \infty$ 时，$\delta_{k+1} = \gamma^{k+1} P_\pi^{k+1} \delta_0 \to 0$。
五、Action Value
Action Value定义为在一个状态 $s$ 和动作 $a$ 下，折扣回报 $G_t$ 的期望： \(\begin{equation} q_\pi(s, a) = \mathbb{E}[G_t \mid S_t = s, A_t = a] \end{equation}\)
对比State Value定义：$v_\pi(s) = \mathbb{E}[G_t \mid S_t = s]$
State Value和Action Value的关系可以表达为：
\(\begin{equation}
\underbrace{\mathbb{E}[G_t \mid S_t = s]}_{v_\pi(s)} = \sum_a \underbrace{\mathbb{E}[G_t \mid S_t = s, A_t = a]}_{q_\pi(s, a)} \pi(a \mid s)
\end{equation}\)
即：
\(\begin{equation}
{\color{red}{v_\pi(s)} } = \sum_a \pi(a \mid s) {\color{red}{q_\pi(s, a)} }
\end{equation}\)
与贝尔曼公式相比较，可见 $q_\pi(s, a)$ 就是中括号中的部分：
\(\begin{equation}
{\color{red}{v_\pi(s)} } = \sum_a \pi(a \mid s) \underbrace{\left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_\pi(s') \right]}_{ {\color{red}{q_\pi(s, a)} }} \label{eq:4}
\end{equation}\)
即⭐️Action Value的表达式为：
\(\begin{equation}
{\color{red}{q_\pi(s, a)} } = \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) {\color{red}{v_\pi(s')} } \label{eq:5}
\end{equation}\)
从公式 $\eqref{eq:4}$ 和公式 $\eqref{eq:5}$ 可以看出：
- 公式 $\eqref{eq:4}$ 展示了如何从Action Value计算得到State Value（Action Value的期望就得到State Value）
- 公式 $\eqref{eq:5}$ 展示了如何从State Value计算得到Action Value（Action Value等于该action的即时奖励加上该action所得到的状态 $s’$ 的State Value的期望）
注意：
- Action Value很重要，因为我们需要关注采取哪个action。
- 我们可以先计算所有State Value，然后再计算Action Value。
- 我们也可以根据有或没有model【即 $p(r \mid s, a),p(s’ \mid s, a)$】来直接计算Action Value。