David Silver 强化学习 第五讲

Model-Free 的控制

Posted by Pelhans on January 17, 2018

本讲基于前一讲及更早的内容,是本课程的核心内容,其基本思想是对于无模型情况下的控制问题,即对策略和状态价值函数进行优化,其中再根据优化控制过程中利用的时自己或他人的经验策略又分为现时策略学习和离线策略学习两种。

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

现时策略学习(On-Policy Learning)

现时策略学习其基本思想时个体有一个策略并遵循该策略进行采样,根据采样得到的奖励取更新状态函数,最后根据该更新的价值函数来优化策略得到较优的策略。简单来说就是根据自身的策略进行采样来进行更新。

现时蒙特卡罗控制(On-Policy MOnte-Carlo Control)

在之前的学习中我们学习了动态规划算法,通过动态规划算法来改善策略需要知道某一个状态的所有后续状态及状态间的转移概率:

\[\pi^{'}(s) = \arg\max\limits_{a\in A} R_{s}^{a} + P_{ss^{'}}^{a}V(s^{'})\]

很明显该方法不能用于模型未知的情况。因为我们不知道当前状态的所有后续状态,也就无从判断采取怎样的行为更好。为此使用当前的状态行为对下的价值\(Q(s, a)\)来代替状态价值,即:

\[\pi^{'}(s) = \arg\max\limits_{a\in A}Q(s, a)\]

这样做的目的时可以改善策略而不用知道整个模型。即只要在某个状态下的行为价值最大。具体流程为:从一个初始的Q和策略\(\pi\)开始,现根据这个策略更新每一个状态行为对的q,s。随后基于更新的Q确定改善的贪婪算法。

但此时又带来了新的问题,即我们使用贪婪算法后,可能由于没有足够的采样而导致产生一个并不是最优的策略。为此我们需要引入探索来尝试新的行为。该探索采用随机机制,以一定的概率选择当前最好的策略,同时它又能给其他的行为带来一定的几率,这就是\(\epsilon\)-贪婪探索。

\(\epsilon\)-贪婪搜索

\(\epsilon\)-贪婪搜索的目标是使得某一个状态下所有可能的行为都有一定的几率被选择到以此来保证足够的探索,其中\(1-\epsilon\)的概率选择当前认为最好的行为,而\(\epsilon\)的概率在所有可能的行为中选择(需要注意此处包含最好的行为)。即:

\[\pi(a | s) = \left\{ \begin{aligned} \epsilon / m + 1 - \epsilon & & if a^{*} = \arg\max\limits_{a\in A}Q(s, a) \\ \epsilon / m & & otherwise \end{aligned} \right.\]

通过定理可以证明,使用\(\epsilon\)-贪婪策略,对于任意一个给定的策略\(\pi\),我们在评估这个策略的 同时也在改进它。

至此我们得到蒙特卡罗控制的全貌,即使用Q函数进行策略评估,使用\(\epsilon\)-贪婪探索来改善策略直至收敛到最优策略。

此处需要强调的是,由于时蒙特卡罗控制,因此是在经历一个Episode之后才会对Q函数进行更新。但这样随机的探索看起来没有一个终止条件,但我们一方面不想丢掉任何更好的信息和状态,另一方面我们希望它能终止于某一个最优策略。为此引入另一个理论概念:GLIE(Greedy in the Limit with Infinite Exploration)。

GLIE

GLIE是指在有限时间内的无限可能探索。简单来说就是所有已经经历的状态行为对会被无限次探索;同时随着探索的无限延伸,贪婪算法中的$\epsilon$$值趋向于0.相关定理证明,GLIE蒙特卡罗控制能够收敛到最优的状态行为价值函数。基于GLIE的蒙特卡罗控制流程如下:

1) 对于给定的策略\(\pi\),采样第k个Episode:\({S_{1},A_{1},R_{2},\ldots, S_{T}}\~ \pi\)

2) 对于该Episode里出现的每一个状态行为对\(S_{t}\)和\(A_{t}\),更新其计数和Q函数:

\[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}))\]

3) 基于新的Q函数改善如下方式改善策略:\(\epsilon \leftarrow \frac{1}{k}, \pi \leftarrow \epsilon - greedy(Q)\)

现时策略时序差分控制( On-Policy Temporal-Difference Control )

上面是基于蒙特卡罗的控制方法,在前一讲我们知道TD相比于MC有很多优点,因此我们上面的方法应用到TF学习中,即SARSA。

SARSA不是什么名词的缩写而是下述序列关系的总结:

针对一个状态S,以及一个特定的行为A,进而产生一个状态行为对(SA),与环境交互,环境收到个体的行为后会告诉个体即时奖励R以及后续进入的状态S’;接下来个体遵循现有策略产生一个行为A’,根据当前的状态行为价值函数得到后一个状态行为对(S’A’)的价值(Q),利用这个Q值更新前一个状态行为对(SA)的价值。

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

\[Q(S, A) \leftarrow Q(S, A) + \alpha(R + \gamma Q(S^{'}, A^{'}) - Q(S, A))\]

需 要注意的是,在状态S‘,个体并不真正的执行动作A’,而是将行为A‘留到下一个循环执行。当满足如下两个条件时,SARSA算法将收敛到最优行为价值函数:

条件1: 任何时候的策略 \(\pi_{t}(a|s)\)符合GLIE特性;

条件2: 步长系数\(\alpha_{t}\)满足: \(\sum\limits_{t=1}^{\infty}\alpha_{t} = \infty and \sum\limits_{t=1}^{\infty}\alpha_{t}^{2} < \infty\)

n-step SARSA

对应于前一讲的TD学习,我们引入类似的n-step SARSA概念,定义n-step Q收获:

\[q_{t}^{n} = R_{t+1} + \gamma R_{t+2} + \ldots +\gamma^{n-1}R_{t+n} + \gamma^{n}Q(S_{t+n})\]

这里的公式看起来和前一讲的n-step G收获很像,但实际上\(Q(s_{t+1}, a_{t+1})\)时基于行为状态对的。而价值V(S_{t})则基于状态。

讲上式带入有SARSA更新算法有:

\[Q(S_{t}, A_{t}) \leftarrow Q(S_{t}, A_{t}) \alpha (q_{t}^{n} - Q(S_{t}, A_{t}))\]

对应于前面的\(\lambda\)-收获,我们在这也引入参数\(\lambda\)和对应权重:

\[q_{t}^{\lambda} = (1-\lambda)\sum\limits_{n=1}^{\infty}\lambda^{n-1}q_{t}^{n}\]

和TD学习类似,我们也可以有SARASA(\(\lambda\))前向认识和反向认识。前向认识即用某一个状态\(q^{\lambda}\)收获来更新状态行为对的Q值:

\[Q(S_{t}, A_{t}) \leftarrow Q(S_{t}, A_{t}) + \alpha(a_{t}^{\lambda} - Q(S_{t}, A_{t}))\]

同样,对于反向认识,我们引入效用追踪(ES)的概念,不同的时此时E值针对的是一个状态行为对:

\[E_{0}(s, a) = 0\] \[E_{t}(s, a) = \gamma\lambda E_{t-1}(s,a) + 1(S_{t} = s, A_{t} = a)\]

它可以体现一个结果与某一个状态行为对的因果关系,表示接近结果时的状态行为对和在得到结果之前频繁出现的状态行为对对于结果的影响大小。通常应用在在线学习算法中。

引入ET概念后SARSA(\(\lambda\))的Q值更新:

\[\delta_{t} = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_{t}, A_{t})\] \[Q(s, a) \leftarrow Q(s,a) + \alpha\delta_{t}E_{t}(s, a)\]

下图给出具体的SARSA(\(\lambda\))算法:

SARSA(\(\lambda\))

该算法同时还针对每一次Episode维护一个关于状态行为对<S,A>的E表,初始时E表值均为0。当个体首次在起点\(S_{0}\)决定移动一步\(A_{0}\)(向右)时,它被环境告知新位置为\(S_{1}\),此时发生如下事情:首先个体会做一个标记,使E<\(S_{0}\), \(A_{0}\)>的值增加1,表明个体刚刚经历过这个事件<\(S_{0}\), \(A_{0}\)>;其次它要估计这个事件的对于解决整个问题的价值,也就是估计TD误差,此时依据公式结果为0,说明个体认为在起点处向右走没什么价值,这个“没有什么价值”有两层含义:不仅说明在 \(S_{0}\)处往右目前对解决问题没有积极帮助,同时表明个体认为所有能够到达 \(S_{0}\)状态的状态行为对的价值没有任何积极或消极的变化。随后个体将要更新该Episode中所有已经经历的Q<S,A>值,由于存在E值,那些在<\(S_{0}\),\(A_{0}\)> 之前近期发生或频繁发生的<S,A>的Q值将改变得比其他Q值明显些,此外个体还要更新其E值,以备下次使用。对于刚从起点出发的个体,这次更新没有使得任何Q值发生变化,仅仅在E<\(S_{0}\), \(A_{0}\)>处有了一个实质的变化。随后的过程类似,个体有意义的发现就是对路径有一个记忆,体现在E里,具体的Q值没发生变化。这一情况直到个体到达终点位置时发生改变。此时个体得到了一个即时奖励1,它会发现这一次变化(从S_H采取向上行为A_H到达\(S_{G}\))价值明显,它会计算这个TD误差为1,同时告诉整个经历过程中所有<s,a>,根据其与<\(S_{H}\),\(A_{H}\)>的密切关系更新这些状态行为对的价值Q(上图右所示),个体在这个Episode中经历的所有状态行为对的Q值都将得到一个非0的更新,但是那些在个体到达\(S_{H}\)之前就近发生以及频繁发生的状态行为对的价值提升得更加明显。

在图示的例子中没有显示某一状态行为频发的情况,如果个体在寻路的过程中绕过一些弯,多次到达同一个位置,并在该位置采取的相同的动作,最终个体到达终止状态时,就产生了多次发生的<s,a>,这时的<s,a>的价值也会得到提升。也就是说,个体每得到一个即时奖励,同时会对所有历史事件的价值进行依次更新,当然那些与该事件关系紧密的事件价值改变的较为明显。这里的事件指的就是状态行为对。在同一状态采取不同行为是不同的事件。

当个体重新从起点第二次出发时,它会发现起点处向右走的价值不再是0。如果采用greedy策略更新,个体将根据上次经验得到的新策略直接选择右走,并且一直按照原路找到终点。如果采用\(\epsilon\)-greedy策略更新,那么个体还会尝试新的路线。

由于为了解释方便,做了一些约定,这会导致问题并不要求个体找到最短一条路径,如果需要找最短路径,需要在每一次状态转移时给个体一个负的奖励。

离线策略学习 (Off-Policy Learning)

现时策略学习就是根据当前遵循的策略进行学习改善,而离线策略学习则是指在遵循自身的策略 \(\mu(a | s)\)的同时评估好的外界策 略\(\pi(a | s)\),通过这样的设计,个体可以较容易的从人类经验或其他个体经验中学习,也可以从旧的策略中学习,也可以在遵循一个探索式策略的基础上优化现有的策略。对于该学习我们同样可以分为蒙特卡罗学习和TD学习。

离线蒙特卡罗学习

离线策略TD学习

离线策略TD学习的任务就是使用TD方法在遵循自身策略 \(\mu(a|s)\)的同时评估外界策略 \(\pi(a|s)\)。具体数学表示为:

\[V(S_{t}) \leftarrow V(S_{t}) + \alpha(\frac{\pi(A_{t} | S_{t})}{\mu(A_{t} | S_{t})}(R_{t+1} + \gamma V(S_{t+1})) -V(S_{t}))\]

可以看到,个体对外界策略时学习通过一个比值的形式发生,若外界策略和自身策略作出的决定相似时,比值接近于1,此时可以使用近似于自身策略进行更新,若外界策略和自身策略作出的决定相差较大时,则倾向于采用外界策略来改善而压制自身策略。

Q-learning

应用这种方法最好的时基于TD(0)的Q学习(Q-learning).主要思想是在更新状态行为对Q价值时,采用的时外界策略产生的下一个状态行为对Q价值而不是当前策略的Q。公式对应为:

\[Q(S_{t}, A_{t}) \leftarrow Q(S_{t}, A_{t}) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, A^{'}) - Q(S_{t}, A_{t}))\]

其中\(\alpha\)后的括号部分为外界策略\(\pi\)产生的行为\(A^{'}\)的Q价值。个体遵循的策略时基于当前状态行为对价值函数\(Q(s, a)\)的一个\(\epsilon\)-greedy策略,而目标策略(外界策略)时基于当前状态行为价值函数Q(s, a)不包含\(\epsilon\)的纯greedy策略:

\[\pi(S_{t+1}) = \arg\max\limits_{a^{'}}Q(S_{t+1}, a^{'})\]

因此Q学习的TD目标之可以被大幅简化:

\[R_{t+1} + \gamma Q(S_{t+1}, A^{'}) = R_{t+1} + \gamma Q(S_{t+1}, \arg\max\limits_{a^{'}}Q(S_{t+1}, a^{'}))\]

也就是:

\[R_{t+1} + \gamma Q(S_{t+1}, A^{'}) = R_{t+1} + \max\limits_{a^{'}}\gamma Q(S_{t+1}, a^{'})\]

这样在状态\(S_{t}\)依据\(\epsilon\)贪婪遵循策略得到的行为\(A_{t}\)的Q价值将朝着\(S_{t+1}\)状态所具有的最大Q价值方向做一定比例的更新。这种算法能够使得贪婪策略\(\pi\)最终收敛到最佳策略。由于个体与实际环境交互中遵守的时\(\epsilon\)贪婪策略,它能保证经历足够丰富的新状态。(这块我没想懂)下图给出Q学习算法的流程: