增强学习的数学表达形式

在了解了增强学习的大致框架之后，我们继续深入探讨增强学习的数学形态。一个增强学习系统可以抽象成马尔可夫决策过程（Markov Decision Process，MDP）的模式，其中还包括策略函数（Policy Function）、奖励（Reward）与回报（Return）、价值函数（Value Function）这几个核心部分。前面我们已经介绍了增强学习的概念，如果希望采用数学的方式来描述这个交互过程，则需要解决下面的问题：

• Agent的动作是根据什么做出的？

• 这个部分是否可以通过模型表达出来？环境是如何随Agent的动作变化的？

• 这里面是不是包含着某种规律？如果有规律，那么能不能用模型把它表达出来？

MDP

对于大多数的增强学习问题，我们都可以用马尔可夫决策过程（MDP）来描述。MDP这个概念可以分两个方面进行介绍。这里假设Agent在每一个状态下的动作是有限的，同时环境的状态的数量也是有限的。首先是交互过程的马尔可夫特征。我们知道增强学习的过程是Agent和Environment交互的过程，当Agent的Action产生后，Environment会切换到下一个状态，那么这个新状态的产生会和哪些因素有关呢？直觉上看，新状态 $S_{t+1}$ 会与 $S_t$ 和 $A_t$ 相关。那么除此之外，会不会和 $S_{t-1}$ 和 $A_{t-1}$ 相关呢？拥有马尔可夫特性的问题告诉我们，不会。马尔可夫特性将状态转移限定在只和前一个状态相关，也就是说：

$P\{R_{t+1}=r,S_{t+1}=s'|S_0,A_0,R_1,\cdots,S_{t-1},A_{t-1},R_t,S_t,A_t\}$

相当于：

$P\{R_{t+1}=r,S_{t+1}=s'|S_t,A_t\}$

这个特性极大地简化了问题的复杂度，使得整个问题变得更加清晰。同时，状态间相互依赖的特性依然保留，使得这个特性仍然可以保留问题本身最核心的一些特点。

其次是决策过程。当Agent接收到某一时刻 $t$ 的 $S_t$ 和 $R_t$ 之后，它将根据自身的策略做出相应的 $A_t$ ，Environment接收到Action后，会根据 $S_t$ 和 $A_t$ 转换到下一个状态 $S_{t+1}$ ，转换的方式依赖于 $p(s_{t+1}|s_t,a_t)$ 概率，同时给出相对应的奖励 $R_{t+1}=r(s_t,a_t,s_{t+1})$ 。之后Agent再做出选择。如此不断进行的状态转换构成了环境状态和Agent动作的序列，这个序列就可以描述过程。

策略函数

策略描述了Agent的行为方式。具体来说，就是描述了针对Environment的某个状态，Agent将采取什么样的动作，而这个动作也是我们心目中最好的。所谓最好的动作，就是能让Agent获得最多奖励的动作。对于一些比较简单的问题，策略是一个简单函数或者一个“状态-动作”的查找表，某一种特定的状态都可以从查找表中找出对应的最优动作。而对于一些复杂的问题，采用查找表的方式就比较困难了。比如环境的状态空间非常大，对应Agent的动作也非常多，查找表很难存储所有的最后方案，这个时候策略函数也需要有更加复杂的表示方式，例如建立一个从环境到动作的函数。同时，对于Environment的某个状态，Agent既可以给出确定的动作，也可以给出随机的动作。前面提到了增强学习中的一个挑战——探索与利用。在一些场景下，我们对当前“计算”得到的策略函数并没有百分之百的信心，也许对于某个状态，存在一个比策略函数更好的动作。在实际中，一些策略函数会以一个比较小的概率采取“探索”的策略，尝试最优策略之外的策略。这种方式往往能获得更好的效果。对于俄罗斯方块这个游戏，每个人的策略可能都有所不同，有的人会采用“尽可能得更多分”的策略，在“竖条”出现前，尽可能不去消除方块，而是积攒起来，等到“竖条”出现时再一并清除，以获得更多的分数；也有人为了稳妥起见，尽可能早地消除方块，保证自己立于不败之地，这都是策略的体现。

奖励与回报

奖励函数（Reward Function）描述了在某种环境状态下执行了某个动作之后能够获得的奖励的数目，数目的多少决定了当前行为在当前状态下的价值。这个函数一般可以被Agent直接使用。奖励函数一般具有时间不变性，也就是说，对于同一个状态或者同一个状态-动作对，其奖励不会因为它出现时间的不同而不同，其确定性也使得它可以更好地帮助Agent调整合适的策略。在增强学习中，奖励一般以数值的形式表示。这样的表示方式也非常常见，比如在大量的电子游戏中都有得分这样的机制，玩家采取一定的动作之后，游戏系统都会根据玩家的行为改变其分数，有的是增加有的是减少。这些得分很好地反映了玩家当前的表现，和奖励的定义非常相近。前面提到Agent的目标是尽可能多地获得奖励，这里将“尽可能多地获得奖励”换成“最大化长期奖励”，也就是最大化从当前状态到某种结束状态能获得的所有奖励。由于Agent的目标是长期获得最多的奖励，这和在当前状态下获得最大化奖励的目标不太一样。对于长期奖励这个目标，这里用回报（Return）来区别。那么Agent的目标就是最大化回报的数量。

根据“长期”的期限不同，增强学习可以分为两类：有明确结束状态和没有明确结束状态的。

有明确结束状态

有明确结束状态的问题是比较常见的，比如电子游戏，一般都会有明确的结束状态（游戏通关或者角色死亡），那么对于这样的问题，Agent和Environment的交互流程会有一个终点。

对于有明确结束状态的问题，回报相当于从当前状态到结束状态的奖励的加和，可以写作：

$G_t=R_{t+1}+R_{t+2}+\cdots+R_T$

没有明确结束状态

对于没有明确结束状态的问题，对于Agent和Environment的交互不会看到一个明显的终点，两者的交互会无限延伸下去。下面以守林人问题为例进行说明。在世界的某个角落，有一片森林，这片森林一直以来有一批守林人，他们的主要任务就是守护这片森林。假设这片森林种着的全是 $N$ 年生的树木，也就是说，这批树木在生长 $N$ 年后会完全长成。每一年的开始，这些守林人都要做出一个决策：是继续让这批树木生长，还是砍掉所有树木卖钱？假设这片森林土地永远存在，守林人也更新换代，那么这就是个在理想状态下没有明确结束状态的问题。

对于无明确结束状态的问题，回报相当于从当前状态到无穷尽的未来所有奖励的和，可以写作：

$G_t=\sum\limits_t^\infty R_t$

相对而言，对于有明确结束状态的问题，回报的数字是可以计算的（当然可能也会比较大）；而对于无结束状态的问题，由于交互可能是无限的，如果按照上面的公式进行计算，这个数字可能是无穷大的。如果所有的回报值都是无穷大的，那么他们将无法进行比较，显然我们需要解决回报值无穷大的问题。解决这个问题的办法是引入一个变量：折现率。折现率的概念其实对我们来说并不陌生，可以用储蓄问题来解释这个概念。假设我们现在有100元钱，把这100元钱存到某个银行里，银行给出的年化率是5%，那么一年后这100元钱将变成105元。也就是说，在利率一定的情况下，一年后的105元等于现在手里的100元。所以如果要把未来的钱换算到当前时间下，则钱的数量需要减少。同理，如果站在当前时间段取计算未来的奖励，则未来的奖励同样需要折现到现在的时间下。我们用 $\gamma$ 表示折现率，这个变量是小于 $1$ 的，这样和上面描述的概率是符合的。此时，对于回报的计算公式可以变成：

$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots=\sum\limits_{k=0}^\infty\gamma^k R_{t+k+1}$

可以看出，现在无明确结束状态问题的回报也变得有界了。我们可以做如下证明。假设每一个动作反馈的奖励是有界的，那么必然存在一个上界 $R_{\max}$ ，于是有：

$G_t \leq R_{\max}+\gamma R_{\max} +\gamma^2 R_{\max}+\cdots = R_{\max}\sum\limits_{k=0}^\infty\gamma^k = \frac{R_{\max}}{1-\gamma}<\infty$

那 $\gamma$ 的数值该如何设置呢？这和实际问题相关。对于一些需要有长远眼光的问题来说， $\gamma$ 应该靠近 $1$ ；而对于一些不需要长远眼光的问题来说， $\gamma$ 应该靠近 $0$ ；对于一些极限状况， $\gamma$ 等于 $0$ 。那么这个问题就完全变成“走一步，看一步”的问题，回报和奖励也就相等了。

价值函数

前面提到了奖励和回报两个概念，对于奖励，Agent可以通过和环境进行交互来获得；而回报则无法直接获得。价值函数（Value Function）的作用就是计算回报这个数值，将当前环境所处的状态、状态-动作对与回报关联起来。一般来说，价值函数会以两种形式展现出来。

（1）状态价值函数（State-Value Function） $v_\pi(s)$ ，表示当环境处于 $s$ 状态时的期望回报：

$v_\pi(s)=E_\pi[G_t|S_t=s]=E_\pi[\sum\limits_{k=0}^\infty\gamma^kR_{t+k+1}|S_t=s]$

（2）动作价值函数（Action-Value Function） $q_\pi(s,a)$ ，表示当环境处于 $s$ 状态且Agent采用了动作 $a$ 后的期望回报：

$q_\pi(s,a)=E_\pi[G_t|S_t=s,A_t=a]=E_\pi[\sum\limits_{k=0}^\infty\gamma^kR_{t+k+1}|S_t=s,A_t=a]$

贝尔曼方程

上面的状态价值函数是通过从当前状态开始无限延伸下去的奖励加和得到的，而实际上我们是无法得到未来所有状态的，但是可以对其进行变换使价值函数变得可解：

$v_\pi=E_\pi[G_t|S_t=s]=E_\pi[\sum\limits_{k=0}^\infty\gamma^kR_{t+k+1}|S_t=s]$

$=E_\pi[R_{t+1}+\gamma\sum\limits_{k=0}^\infty\gamma^kR_{t+k+2}|S_t=s]$

$=\sum\limits_a\pi(a|s)\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma E_\pi[\sum\limits_{k=0}^\infty\gamma^k R_{t+k+2}|S_{t+1}=s']]$

$=\sum\limits_a\pi(a|s)\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma v_\pi(s')]$

由此可见，对于当状态为 $s$ 时，价值函数的取值可以通过其他状态的值求出，这个公式也别成为贝尔曼方程（Bellman Equation），是增强学习中十分重要的一个公式。同时，两个价值函数之间也可以建立起联系

$q_\pi(s,a)=\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma _\pi(s')]$

$v_\pi=\sum\limits_a\pi(a|s)q_\pi(s,a)$

最优策略性质

在Agent与环境的交互过程中，Agent当然希望自己能够获得最多的回报，那么就需要自己有用最优的动作策略。我们可以给出最优策略的定义：对于一个策略函数 $\pi$ ，如果它和其他的 $\pi'$ 相比，对于任意一个 $s$ ，都有 $v_\pi(s)\geq v_{\pi'}(s)$ ，那么就称这个策略 $\pi$ 是最优的。对于最优策略的价值函数，我们定义它的状态价值函数为 $v^*(s)$ ，状态-动作价值函数为 $q^*(s,a)$ 。与前面的推导过程类似，我们可以用贝尔曼方程对其进行推导：

$v_*(s)=\max\limits_{a\in A(s)}q_{\pi^*}(s,a)$

$= \max\limits_aE_{\pi^*}[G_t|S_t=s,A_t=a]$

$=\max\limits_aE_{\pi^*}[\sum\limits_{k=0}^\infty\gamma^k R_{t+k+1}|S_t=s,A_t=a]$

$=\max\limits_aE_{\pi^*}[R_{t+1}+\gamma\sum\limits_{k=0}^\infty\gamma^kR_{t+k+2}|S_t=s,A_t=a]$

$=\max\limits_aE[R_{t+1}+\gamma v_*(S_{t+1}|S_t=s,A_t=a)]$

$= \max\limits_{a\in A(s)}\sum\limits_{s',r}p(s',r|s,a)[r+\gamma v_*(s')]$

从上面的公式可以看出，当知道了最优价值函数后，就可以推导出最优策略来。由于 $v^*(s)$ 是由最优的动作得到的，那么在公式中只要计算出所有 $A_t$ 对应的状态价值，找出其中价值最大的那个，就是当前状态的最优的策略。想要求出完整的策略，就需要把所有的状态遍历一遍。当然，对于那些状态很多的问题，求解最优价值函数已经十分困难，更别说遍历所有状态求解最优策略这种计算量很大的问题了。