（详细）强化学习--贝尔曼方程

原文链接：https://zhuanlan.zhihu.com/p/86525700

我有一个疑问，就是在推导过程中，状态s不是变量，st 是t阶段的状态相当于是一个常数，那么为什么st=s，常数在等号的左边，变量在等号的右边？

这里的st表示的是t时刻对应的状态，状态可能有多种，但是这里设t时刻的状态为s，所以st=s。比如说放学回家，你一共有三种状态，写作业、看电视、打游戏，在某一时刻（这里可以对应t）你的状态是什么，即st得状态。st得状态可以是写作业（状态s1）、看电视（状态s2）、打游戏（状态s3）。st=s1表示t时刻你的状态是你正在写作业

Bellman方程

Bellman方程是强化学习的基础和核心，在介绍强化学习的概念及应用时我们必须对贝尔曼方程有个全面的了解，不然后面的只是将很难理解和掌握，所以在这里我们首先介绍Bellman方程的基础知识。

首先我们需要弄清楚贝尔曼方程的三个主要概念，策略函数、状态价值函数、状态-动作价值函数（简称为动作价值函数）^[1]。

策略函数（Policy Function）：策略函数是一个输入为s输出为a的函数表示为 ${\pi(s)}$ ，其中s表示状态，a表示动作，策略函数的含义就是在状态s下应该选择的动作a。强化学习的核心问题就是最优化策略函数从而最大化后面介绍的价值函数。

状态价值函数（State Value Function）：前面说过强化学习的核心问题是最优化策略函数，那么如何评价策略函数是最优的呢？状态价值函数是评价策略函数 ${\pi(s)}$ 优劣的标准之一，在每个状态s下（ $s\in{S}$ , $S$ 为所有状态的集合），可以有多个动作a选择( $a\in{A}$ , $A$ 为所有动作的集合)，每执行一次动作，系统就会转移到另一个状态（状态有时有多个可能，每种状态都有一个概率转移到就是下文的 $\sum_{s'}{P_{ss'}^a}$ ），如何保证所有的动作能使系统全局最优则要定义价值函数，系统的状态价值函数的含义是从当前状态开始到最终状态时系统所获得的累加回报的期望，下一状态的选取依据策略函数（不同的动作a将导致系统转移到不同的状态）。所以系统的状态价值函数和两个因素有关，一个是当前的状态s，另一个是策略 ${\pi(s)}$ 。从不同的状态出发，得到的值可能不一样，从同一状态出发使用不同的策略，最后的值也可能不一样。所以建立的状态价值函数一定是建立在不同的策略和起始状态条件下的。状态价值函数的具体形式如下：

$\begin{equation} V^{\pi}(s)=E_{\pi}\left[R_{t} | s_{t}=s\right] \end{equation}$

其中 ${R_{t}=\sum_{k=0}^{\infty}{\gamma^{k}r_{t+k+1}}}$ ，其中 ${r_{t+1}}$ 表示从 ${s_{t}}$ 转移到 ${s_{t+1}}$ 时获得的回报， $\gamma$ 是折损因子，取值为 $0\sim1$ 。可以将上面的状态价值函数的形式表示为递归的形式：

$\begin{equation} \begin{array}{l}{V^{\pi}(s)=E_{\pi}\left[R_{t} | s_{t}=s\right]}\\{=E_{\pi}\left\{\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} | s_{t}=s\right\}} \\ {=E_{\pi}\left\{r_{t+1}+\gamma \sum_{k=0}^{\infty} \gamma^{k} r_{t+k+2} | s_{t}=s\right\}} \\ {=\sum_{a} \pi(s, a) \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left[R_{s s^{\prime}}^{a}+\gamma E_{\pi}\left\{\sum_{k=0}^{\infty}{\gamma^{k}r_{t+k+2}|s_{t+1}=s^{\prime}}\right)\right]} \\ {=\sum_{a} \pi(s, a) \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left[R_{s s^{\prime}}^{a}+\gamma V^{\pi}\left(s^{\prime}\right)\right]}\end{array} \end{equation}$

其中 ${P_{s s^{\prime}}^{a}}$ 表示在选择动作a时，状态由s转移到 ${s^{\prime}}$ 的概率，这里要注意，选定了动作之后不代表后面的状态就确定了，根据概率可能有好几种状态可以转移到，如后面的赌徒问题。但是也存在动作确定后，后面只有一种转移可能，这个时候 ${P_{s s^{\prime}}^{a}=1}$ 。下面用赌徒问题和方格世界的例子来说明这个概念。

例1：赌徒问题^[2]

一个赌徒利用硬币投掷的反正面结果来赌博。假如投掷结果是硬币的正面朝上，那么他就赢得他所压的赌注，如果是反面朝上，那么他输掉他的赌注。当这个赌徒赢满100美元或者他输掉他所有的钱时，赌博结束。每一轮投掷，赌徒必须取出他资金的一部分作为赌注，赌注金额必须是整数。这个问题可以表述为一个无折扣的、情节式的有穷马尔可夫决策过程。状态就是赌徒所拥有的资金， ${s\in[{1,2,\cdots,99}]}$ ，动作就是下赌注， ${a\in[{1,2,\cdots,\min{(s,100-s)}}]}$ 。

这里的每个动作a就对应2各状态，如当前状态 ${s=50}$ ， ${a=20}$ ,设赌徒每局输赢的概率都为0.5，则下一状态为 ${s=70}$ 的概率为0.5，下一状态为 ${s=30}$ 的概率也为0.5。

例2：方格世界

如图有个 ${4\times{4}}$ 的方格，每个方格都对应一个状态，共有16个状态，每个状态下对应4个动作

A={上，下，左，右 }，当当前状态确定，动作确定之后对应的下一个状态也就确定了。

状态动作价值函数（State-action Value Function）：动作价值函数也称为Q函数，相比于Value Function是对状态的评估，Q Function是对（状态-动作对）的评估，Q值的定义是，给定一个状态 ${s_{t}}$ ，采取动作 ${a_{t}}$ 后，按照某一策略 ${\pi_{s}}$ 与环境继续进行交互，得到的累计汇报的期望值。其数学表达形式是：

$\begin{equation} Q^{\pi}(s, a)=E_{\pi}\left[R_{t} | s_{t}=s, a_{t}=a\right] \end{equation}$

$\begin{equation} Q^{\pi}(s, a)=E_{\pi}\left\{R_{t} | s_{t}=s, a_{t}=a\right\}=E_{\pi}\left\{\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} | s_{t}=s, a_{t}=a\right\} \end{equation}$

对于状态价值函数和动作价值函数的区别，可以简单的认为，状态函数中，当前状态下选取哪个动作是未知数，需要求出一系列的动作集合（各不同状态下），形成一个完整的策略，然后使状态方程的值最大化，而动作价值函数是当前状态下的动作已知，求余下状态下的动作集合使动作方程的值最大化，具体数学形式如下：

$\begin{equation} \begin{aligned} V^{*}(s) &=\max _{a} E\left\{r_{t+1}+\gamma V^{*}\left(s_{t+1}\right) | s_{t}=s, a_{t}=a\right\} \\ &=\max _{a} \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left[R_{s s^{\prime}}^{a}+\gamma V^{*}\left(s^{\prime}\right)\right] \end{aligned} \end{equation}$

$\begin{equation} \begin{aligned} Q^{*}(s, a) &=E\left\{r_{t+1}+\gamma \max _{a^{\prime}} Q^{*}\left(s_{t+1}, a^{\prime}\right) | s_{t}=s, a_{t}=a\right\} \\ &=\sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left[R_{s s^{\prime}}^{a}+\gamma \max _{a^{\prime}} Q^{*}\left(s^{\prime}, a^{\prime}\right)\right] \end{aligned} \end{equation}$

动作和状态价值函数的关系

前面我们简单的将状态价值函数和状态-动作价值函数的关系描述为状态价值函数在当前状态的动作是不确定的，所以它必须考虑到所用动作的情况然后取其期望，而状态-动作价值函数只是考虑特定的动作下的价值。最大化状态价值函数就是求当前状态的最大期望值，而最大化状态-动作价值函数就是求当前状态下一动作能带来的最大回报值，用数学的形式表示如下：

$\begin{equation} V^{\pi}(s)=\sum_{a\in{A}}{\pi(a|s)}*Q^{\pi}(s,a) \end{equation}$

$\begin{equation} Q^{\pi}(s,a)=R_{s}^{a}+\gamma*\sum_{s^{'}}{P_{ss^{'}}V^{\pi}(s)} \end{equation}$

将公式(1-2)进一步化简可得：

$\begin{equation} V^{\pi}(s)=\sum_{a\in{A}}{\pi(a|s)*R_{s}^{a}}+\gamma*\sum_{a\in{A}}{\pi(a|s)}\sum_{s^{'}}{P_{ss^{'}}V^{\pi}(s)} \end{equation}$

从上式可以看出状态方程比动作方程考虑了所有动作的情况。

注意：

这里需要注意几个表示价值的符号的意义， $R_{s}^a、R_{ss'}^a、R_s^\pi$ 。

$R_{ss'}^a：R_{ss'}^a$ 表示的是在状态s下，执行动作a的情况下状态转移到s'时得到的即时奖励。

$R_{s}^a：R_{s}^a=\sum_{s'}{P_{ss'}^a*R_{ss'}^a}$

$R_{s}^\pi：R_{s}^\pi=\sum_{a}{\pi(a|s)*R_{s}^a}$

下面举个例子说明状态价值函数和状态动作价值函数的含义^[3]：

如图2所示，是计算各状态价值的过程，其中设每一个状态下执行某个动作的概率都为0.5，即 $\pi(a|s)=0.5$ ，折损因子 $\gamma=1$ ,根据公式 $V^{\pi}(s)=\sum_{a\in{A}}{\pi(a|s)*[R_{s}^{a}}+\gamma*\sum_{s^{'}}{P_{ss^{'}}V^{\pi}(s)} ]$

进行迭代求解，这里箭头从一个圆直接连接到另一个圆表示执行某动作之后，其能到达的状态只有一种， ${P_{ss'}^a}=1$ ，而箭头连接点的分出去三个箭头，表示执行该动作，将有可能到达三种状态，且概率分别为0.2，0.4，0.4。图中， $R$ 表示的是 $R_{s}^a$ ，以图中7.4值计算为例：