Bdq's blog

在上一篇文章强化学习的基本概念中，用大白话介绍了强化学习的一些基本概念，尤其是强化学习的基本过程。在了解了强化学习的基本概念之后，在本篇文章中，笔者将介绍一下马尔可夫决策过程，用马尔可夫决策过程来形式化的描述强化学习。

强化学习与马尔可夫决策过程

首先回顾一下Agent与Environment交互的过程。

在每一个时刻 $t$ ，Agent会观察到Environment的状态 $s$ 。根据状态 $s$ ，Agent通过决策产生一个动作 $a$ ，将动作 $a$ 作用在Environment上，Environment会反馈给Agent一个奖励 $R_{t+1}$ ，并进入一个新的状态 $s_{t+1}$ 。整个过程不断重复，最终产生一个交互序列：

$S_0,A_0,R_1,S_1,A_1,R_2,...$

从序列中可以看出，下一个状态不但与上一个状态有关，还与上上一个状态有关，甚至追溯到初始状态。这样的一个相关性特别强的序列，复杂到根本无法建模。

因此，有必要采取某些方式来简化这个状态转化过程，建立一个清晰的模型。于是，就引入了经典的马尔可夫决策过程。

马尔可夫假设

为了用马尔可夫决策过程对强化学习进行建模，对强化学习作了如下三个假设。

假设一

环境状态的转化的过程中，下一个状态 $s'$ ，仅仅与上一个状态 $s$ 有关，与之前的状态无关。用公式表示如下：

$P(S_{t+1}|S_t)=P(S_{t+1}|S_1,...,S_t)$

如此一来，环境状态转化的模型就简单多了，在状态 $s$ 下采取动作 $a$ ，转到下一个状态 $s'$ 的概率 $P^a_{ss'}$ ，可以表示为下面这个公式：

$P^a_{ss'}=P(S_{t+1}=s'|S_t=s,A_t=a)$

假设二

在状态 $s$ 时采取动作 $a$ 的概率仅与当前状态 $s$ 有关，与其他的要素无关。用公式表示如下：

$\pi(a|s)=P(A_t=a|S_t=s)$

这里的 $\pi$ 指的是一个全局的策略，针对的不是某一个状态或者动作。

假设三

状态价值函数仅仅依赖于当前状态 $s$ ，用公式表示如下：

$v_{\pi}(s)=E_{\pi}(G_t|S_t=s)=E_{\pi}(R_{t+1}+{\gamma}R_{t+2}+{\gamma}^2R_{t+3}+...|S_t=s)$

这里引入了一个衰减系数 $\gamma$ ，这是一个超参数，可以自定义。 $G_t$ 表示收获，是马尔可夫中从某一种状态 $S_t$ 开始采样，直到终止状态时所有奖励的有衰减的和。强化学习的最终目标就是最大化收获。

价值函数

在马尔可夫决策过程中，有两种价值函数。

状态价值函数 $v_{\pi}(s)$ ：表示已知当前状态 $s$ ，按照某种策略行动产生的长期回报期望。
动作价值函数 $q_{\pi}(s,a)$ ：表示已知当前状态 $s$ 和行动 $a$ ，按照某种策略行动产生的长期回报。可以理解为采取动作 $a$ 之后获得的奖励。

动作价值函数相对于状态价值函数的，它在状态价值函数的基础上，考虑了动作 $a$ 带来的价值影响。动作价值函数 $q_{\pi}(s,a)$ 表示如下：

$q_{\pi}(s,a)=E_{\pi}(G_t|S_t=s,A_t=a)=E_{\pi}(R_{t+1}+{\gamma}R_{t+2}+{\gamma}^2R_{t+3}+...|S_t=s,A_t=a)$

贝尔曼方程

基于状态价值函数进一步推导，可以得到如下公式：

$\begin{aligned} v_{\pi}(s)&=E_{\pi}(R_{t+1}+{\gamma}R_{t+2}+{\gamma}^2R_{t+3}+...|S_t=s)\\ &=E_{\pi}(R_{t+1}+{\gamma}(R_{t+2}+{\gamma}R_{t+3}+...)|S_t=s)\\ &=E_{\pi}(R_{t+1}+{\gamma}G_{t+1}|S_t=s)\\ &=E_{\pi}(R_{t+1}+{\gamma}v_{\pi}(S_{t+1})|S_t=s)\\ \end{aligned}$

这种递推式就是贝尔曼方程。这个式子表明一个状态的价值由当前状态的奖励和后续状态价值按一定的衰减比例联合组成。

同理，可得到动作价值函数的贝尔曼方程：

$q_{\pi}(s,a)=E_{\pi}(R_{t+1}+{\gamma}q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a)$

这两个方程很重要，后续的很多算法都基于这两个方程。

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

状态价值函数和动作价值函数之间是可以相互转化的。状态价值函数可以理解为在状态 $s$ 的情况下，未采取动作之前期望的回报值，即所有可能动作的奖励之和。如图所示，白点表示状态，黑点表示动作。

动作价值函数可以理解为在状态 $s$ 下，采取动作 $a$ 之后，转变到下一个状态 $s'$ 产生的奖励与下一个状态的期望奖励 $v_{\pi}(s')$ 之和。

将两个公式结合起来，可以得到下面两个公式：

$v_{\pi}(s)=\sum_{a \epsilon A}\pi(a|s)(R^a_s+\gamma\sum_{s' \epsilon S}P^a_{ss'}v_\pi(s'))$

$q_\pi(s,a)=R^a_s+\gamma\sum_{s' \epsilon S}P^a_{ss'}\sum_{a' \epsilon A}\pi(a'|s')q_\pi(s',a')$

最优价值函数与最优策略

强化学习的最终目的是通过不断的训练，找出一个最优的策略 $\pi_*$ ，通过这个 $\pi_*$ ，让智能体在目标环境中得到最大的收获。那么，如何评价一个策略是否比另一个策略优秀呢？只需要比较不同策略下产生的价值即可，最大的价值所对应的价值函数被称为最优价值函数。

价值函数有两种，所以对应的最优价值函数也有两种，即：

$v_*(s)=\max_{\pi}v_\pi(s)$

$q_*(s,a)=\max_{\pi}q_\pi(s,a)$

最优动作价值函数对应的最优策略可以定义为：

$\pi_*(a|s)=\begin{cases} 1 &\text{if } a = \arg\max_{a \epsilon A}q_*(s,a) \\ 0 &\text{else} \end{cases}$

由状态价值函数和动作价值函数之间的关系，可以得到：

$v_*(s)=\max_aq_*(s,a)$

$q_*(s,a)=R^a_s+\gamma\sum_{s' \epsilon S}p^a_{ss'}v_*(s')$

将上面两个式子结合可以得到下面的式子：

$v_*(s)=\max_a(R^a_s+\gamma\sum_{s' \epsilon S}P^a_{ss'}v*(s'))$

$q_*(s,a)=R^a_s+\gamma\sum_{s' \epsilon S}P^a_{ss'}\max_{a'}q_*(s',a')$

这两个式子是一个递推式，一般在实践中是通过迭代来求解，具体的算法如Q-learning，Sarsa等。通过不断迭代，一旦确定了最优的价值函数，对应的最优策略也就随之出现了。