David Silver 强化学习 5 模型无关控制 Model-Free Control

2018-03-11

文章目录

1. 简介 Introduction
2. On-Policy Monte-Carlo Control
1. 2.1. 不基于模型控制的两个条件
3. On-Policy Temporal-Difference Control
1. 3.1. SARSA
2. 3.2. On-Policy的 SARSA 算法
4. Off-Policy Learning
1. 4.1. Off-Policy TD学习
5. 总结DP与TD关系

简介 Introduction

上一讲主要讲解了在模型未知的情况下如何进行预测。所谓的预测就是评估一个给定的策略，也就是确定一给定策略下的状态（或状态行为对）的价值函数。这一讲的内容主要是在模型未知的条件下如何优化价值函数，这一过程也称作模型无关的控制。

现实中有很多此类的例子，比如控制一个大厦内的多个电梯使得效率最高；控制直升机的特技飞行，机器人足球世界杯上控制机器人球员，围棋游戏等等。所有的这些问题要么我们对其模型运行机制未知，但是我们可以去经历、去试；要么是虽然问题模型是已知的，但问题的规模太大以至于计算机无法高效的计算，除非使用采样的办法。本节的内容就专注于解决这些问题。

根据优化控制过程中是否利用已有或他人的经验策略来改进我们自身的控制策略，我们可以将这种优化控制分为两类：

一类是遵循策略学习（On-policy Learning）: 其基本思想是个体已有一个策略，并且遵循这个策略进行采样，或者说采取一系列该策略下产生的行为，根据这一系列行为得到的奖励，更新状态函数，最后根据该更新的价值函数来优化策略得到较优的策略。由于要优化的策略就是当前遵循的策略，这里姑且将其翻译为“遵循策略”。

另一类是脱离策略学习（Off-policy Learning）: 其基本思想是，虽然个体有一个自己的策略，但是个体并不针对这个策略进行采样，而是基于另一个策略进行采样，这另一个策略可以是先前学习到的策略，也可以是人类的策略等一些较为优化成熟的策略，通过观察基于这类策略的行为，或者说通过对这类策略进行采样，得到这类策略下的各种行为，继而得到一些奖励，然后更新价值函数，即在自己的策略形成的价值函数的基础上观察别的策略产生的行为，以此达到学习的目的。这种学习方式类似于“站在别人的肩膀上可以看得更远”。由于这些策略是已有的策略，这里姑且翻译为“脱离策略”。

On-Policy Monte-Carlo Control

在本节中我们使用的主要思想仍然是动态规划的思想。先来回顾下动态规划是如何进行策略迭代的。

通用策略迭代（回顾）

p_1

通用策略迭代的核心是在两个交替的过程之间进行策略优化。一个过程是策略评估，另一个是改善策略。如上图的三角形区域所示，从一个策略π和一个价值函数Ｖ开始，每一次箭头向上代表着利用当前策略进行价值函数的更新，每一次箭头向下代表着根据更新的价值函数贪婪地选择新的策略，说它是贪婪的，是因为每次都采取转移到可能的、状态函数最高的新状态的行为。最终将收敛至最优策略和最优价值函数。

注意使用动态规划算法来改善策略是需要知道某一状态的所有后续状态及状态间转移概率：
$\pi ^{‘}(s)= \arg\max_{a\in A} R_s^a + P_{ss^{‘}}^a V(s^{‘})$

不基于模型控制的两个条件

那么这种方法是否适用于模型未知的蒙特卡洛学习呢？答案是否定的，这其中至少存在两个问题。其一是在模型未知的条件下无法知道当前状态的所有后续状态，进而无法确定在当前状态下采取怎样的行为更合适。解决这一问题的方法是，使用状态行为对下的价值Q(s,a)来代替状态价值：

$ \pi ^{‘}(s)= \arg\max_{a\in A} Q(s,a)$

这样做的目的是可以改善策略而不用知道整个模型，只需要知道在某个状态下采取什么什么样的行为价值最大即可。具体是这样：我们从一个初始的 Q 和策略 $\pi$ 开始，先根据这个策略更新每一个状态行为对的 Q 值，s 随后基于更新的 Q 确定改善的贪婪算法。

即使这样，至少还存在一个问题，即当我们每次都使用贪婪算法来改善策略的时候，将很有可能由于没有足够的采样经验而导致产生一个并不是最优的策略，我们需要不时的尝试一些新的行为，这就是探索（Exploration）。

$\epsilon$-贪婪探索 的目标使得某一状态下所有可能的行为都有一定非零几率被选中执行，也就保证了持续的探索，$1-\epsilon$ 的概率下选择当前认为最好的行为，而 $\epsilon$ 的概率在所有可能的行为中选择（也包括那个当前最好的行为）。数学表达式如下：

p_2

定理： 使用Ɛ-贪婪探索策略，对于任意一个给定的策略\pi，我们在评估这个策略的同时也总在改善它。

证明：
p_3

注：在证明上述定理过程中使用的不等式是在经过合理、精心设计的。

解决了上述两个问题，我们最终看到蒙特卡洛控制的全貌：使用Ｑ函数进行策略评估，使用Ɛ-贪婪探索来改善策略。该方法最终可以收敛至最优策略。如下图所示：

p_4

图中每一个向上或向下的箭头都对应着多个 Episode 。也就是说我们一般在经历了多个 Episode 之后才进行依次Ｑ函数更新或策略改善。实际上我们也可以在每经历一个 Episode 之后就更新Ｑ函数或改善策略。但不管使用那种方式，在Ɛ-贪婪探索算下我们始终只能得到基于某一策略下的近似Ｑ函数，且该算法没没有一个终止条件，因为它一直在进行探索。因此我们必须关注以下两个方面：一方面我们不想丢掉任何更好信息和状态，另一方面随着我们策略的改善我们最终希望能终止于某一个最优策略，因为事实上最优策略不应该包括一些随机行为选择。为此引入了另一个理论概念：GLIE。

GLIE
GLIE(Greedy in the Limit with Infinite Exploration)，直白的说是在有限的时间内进行无限可能的探索。具体表现为：所有已经经历的状态行为对（state-action pair）会被无限次探索；另外随着探索的无限延伸，贪婪算法中Ɛ值趋向于０。例如如果我们取 $\epsilon = 1/k$（ k 为探索的 Episode 数目），那么该Ɛ贪婪蒙特卡洛控制就具备 GLIE 特性。

基于GLIE的蒙特卡洛控制流程如下：

对于给定策略 $\pi$ ，采样第k个 Episode:
{ $S_{1}, A_{1}, R_{2}, …, S_{T} $} ～ $\pi$
对于该Episode里出现的每一个状态行为对S_t和A_t,更其计数和Ｑ函数：
$N(S_t, A_t) \leftarrow N(S_t, A_t) + 1 , Q(S_t, A_t) \leftarrow + \frac{1}{N(S_t, A_t)} (G_t - Q(S_t, A_t))$
基于新的Ｑ函数改善以如下方式改善策略：$\epsilon \leftarrow 1/k , \pi \leftarrow \epsilon-greedy(Q)$

定理：GLIE 蒙特卡洛控制能收敛至最优的状态行为价值函数。

On-Policy Temporal-Difference Control

上一讲提到TD相比MC有很多优点：低变异性，可以在线实时学习，可以学习不完整Episode等。因此很自然想到是否可以在控制问题上使用TD学习而不是MC学习？答案是肯定的，这就是下文要讲解的SARSA。

SARSA

SARSA 的名称来源于下图所示的序列描述：针对一个状态S，以及一个特定的行为A，进而产生一个状态行为对(S,A)，与环境交互，环境收到个体的行为后会告诉个体即时奖励R以及后续进入的状态S’；接下来个体遵循现有策略产生一个行为A’，根据当前的状态行为价值函数得到后一个状态行为对(S’,A’)的价值（Q），利用这个Q值更新前一个状态行为对(S,A)的价值。

p_5

更直观的解释是这样：一个Agent处在某一个状态S，在这个状态下它可尝试各种不同的行为，当遵循某一策略时，会根据当前策略选择一个行为A，个体实际执行这个行为，与环境发生实际交互，环境会根据其行为给出即时奖励R，并且进入下一个状态S’，在这个后续状态S’，再次遵循当前策略，产生一个行为A’，此时，个体并不执行该行为，而是通过自身当前的状态行为价值函数得到该S’A’状态行为对的价值，利用该价值同时结合个体S状态下采取行为A所获得的即时奖励来更新个体在S状态下采取A行为的（状态）行为价值。

与蒙特卡洛控制不同的时，每一个时间步，也就是在单个Episode内每一次个体在状态S_t采取一个行为后都要更新Q值，同样使用 $\epsilon$ -贪婪探索的形式来改善策略。

$Q(S,A) \gets Q(S,A) + \alpha(R+ \gamma Q(S^{‘},A^{‘})-Q(S,A))$

On-Policy的 SARSA 算法

p_6

定理：满足如下两个条件时，Sarsa算法将收敛至最优行为价值函数。

条件一：任何时候的策略 $\pi_t(a|s)$ 符合 GLIE 特性;

条件二：步长系数αt满足：$\sum_{t=1}^{\infty}{a_t} = \infty $ 且 $\sum_{t=1}^{\infty}{a_t^2} < \infty $

Sarsa(λ)算法：https://zhuanlan.zhihu.com/p/28108498

Off-Policy Learning

现时策略学习的特点就是当前遵循的策略就是个体学习改善的策略。Off-Policy学习（Off-Policy Learning）则指的是在遵循一个策略\mu(a|s)的同时评估另一个策略\pi(a|s)，也就是计算确定这另一个策略下的状态价值函数v_{\pi}(s)或状态行为价值函数q_{\pi}(s, a)。为什么要这么做呢？因为这样可以较容易的从人类经验或其他个体的经验中学习，也可以从一些旧的策略中学习，可以比较两个策略的优劣。其中可能也是最主要的原因就是遵循一个探索式策略的基础上优化现有的策略。同样根据是否经历完整的Episode可以将其分为基于蒙特卡洛的和基于TD的。基于蒙特卡洛的Off-Policy学习仅有理论上的研究价值，在实际中毫无用处。在解释这一结论时引入了“重要性采样（importance sampling）”这个概念，这里就不详述了，有兴趣的读者可以参考原讲义。这里主要讲解常用的TD下的Off-Policy学习。

Off-Policy TD学习

Off-PolicyTD学习的任务就是使用TD方法在遵循一个策略 $\mu(a|s)$ 的同时评估另一个策略 $\pi(a|s)$。具体数学表示为：

p_7

这个公式可以这样解释：个体处在状态S_t中，基于策略 $\mu$ 产生了一个行为 $A_t$ ，执行该行为后进入新的状态 $S_{t+1}$，那么在当前策略下如何根据新状态的价值调整原来状态的价值呢？Off-Policy的方法就是，在状态S_t时比较分别依据另一个策略 $\pi$ 和当前遵循的策略 $\mu$ 产生行为 $A_t$ 的概率大小，如果策略 $\pi$ 得到的概率值与遵循当前策略 $\mu$ 得到的概率值接近，说明根据状态 $S_{t+1}$ 价值来更新 $S_t$ 的价值同时得到两个策略的支持，这一更新操作比较有说服力。同时也说明在状态S_t时，两个策略有接近的概率选择行为 $A_t$。假如这一概率比值很小，则表明如果依照被评估的策略，选择 $A_t$ 的机会很小，这时候我们在更新 $S_t$ 价值的时候就不能过多的考虑基于当前策略得到的状态 $S_{t+1}$ 的价值。同样概率比值大于1时的道理也类似。这就相当于借鉴被评估策略的经验来更新我们自己的策略。

应用这种思想最好的方法是基于 TD(0) 的Q-学习（Q-learning）。它的要点在于，更新一个状态行为对的Q价值时，采用的不是当前遵循策略的下一个状态行为对的Q价值，而是采用的待评估策略产生的下一个状态行为对的Q价值。公式如下：

$Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha(R_{t+1}+ \gamma Q(S_{t+1},A^{‘})-Q(S_t,A_t))$

式中，TD目标是基于另一个估策略 $\pi$ 产生的行为A’得到的Q价值。Q学习最主要的表现形式是：个体遵循的策略是基于当前状态行为价值函数Q(s,a)的一个 $\epsilon-greedy$ 策略，而目标策略是基于当前状态行为价值函数Q(s,a)不包含 $\epsilon$ 的单纯greedy策略：

$ \pi (S_{t+1})= \arg\max_{a^{‘}} Q(S_{t+1},s^{‘})$

这样Q学习的TD目标值可以被大幅简化：

p_8

这样在状态 $S_t$ 依据Ɛ-greedy遵循策略得到的行为 $A_t$ 的 Q 价值将朝着 $S_{t+1}$ 状态所具有的最大Q价值的方向做一定比例的更新。这种算法能够使 greedy 策略 $\pi$ 最终收敛到最佳策略。由于个体实际与环境交互的时候遵循的是 $\epsilon-greedy$ 策略，它能保证经历足够丰富的新状态。

定理：Q学习控制将收敛至最优状态行为价值函数：$Q(s,a) \rightarrow q_*(s,a)$。

下图是Q学习具体的更新公式和图解：
p_9

下图是Q学习的算法流程：

p_10

总结DP与TD关系

下面两张图概括了各种DP算法和各种TD算法，同时也揭示了各种不同算法之间的区别和联系。总的来说TD是采样+有数据引导(bootstrap)，DP是全宽度+实际数据。如果从Bellman期望方程角度看：聚焦于状态本身价值的是迭代法策略评估（DP）和TD学习，聚焦于状态行为对价值函数的则是Q-策略迭代（DP）和SARSA；如果从针对状态行为价值函数的Bellman优化方程角度看，则是Q-价值迭代（DP）和Q学习。

p_11