Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

强化学习及其常见算法介绍

scsn_dango 2019-01-25 15:50:00 阅读数:188 评论数:0 点赞数:0 收藏数:0

目录

强化学习算法

scsn_dango

第一部分: RL 基本概念介绍

RL 定义

​ 在中文维基百科中,强化学习被定义为机器学习中的一个领域,强调如何基于环境而行动,以取得最大化的预期收益 wikipedia。Richard S. Sutton and Andrew G. Barto 最新的强化学习书籍《Reinforcement Learning: An Introduction II》中对强化学习的定义为: Reinforcement learning is learning what to do—how to map situations to actions——so as to maximize a numerical reward signal.

RL基本元素

​ 可以看出强化学习至少有这样几个基本概念: 环境(Environment)、主体(Agent)、状态(State)、行动(Action)和收益(Reward)

RL
图1

环境是一个外部系统,主体处于这个系统中,能够感知到这个系统并且能够基于感知到的状态做出一定的行动。比如在 MR(Montezuma's Revenge) 中,环境就是80x80像素大小的游戏界面。

主体是一个嵌入到环境中的系统,能够通过采取行动来改变环境的状态。比如在MR中,主体就是玩家操控的小人,小人能够根据当前环境的状态做出一个动作(上下左右移动或者跳跃),从而改变环境的状态。

状态是指当前环境的一个时间切片。在MR中就是一张特定时间的80x80大小的图片。

行动是指主体做出的行为。在MR中指上下左右、跳跃的操作。

收益是一个标量,指的是环境对当前动作或者状态的一个奖励。在MR中指的是系统定义的一个收益,既可以是在游戏回合结束的时候给的 Game Over 或者 Win 这样的全局收益,也可以是一个局部收益,比如拿到 钥匙 或者去到另一个 房间

RL与其他机器学习的关系

​ RL和传统的机器学习(监督学习 Supervised Learning,非监督学习 Unsupervised Learning,半监督学习 Semi-Supervised Learning)既有一定的联系,也存在很大的区别。大致的包含关系如图2所示。

RL and ML
图2

​ 强化学习主要有以下几个特点:

1. 试错学习:强化学习一般没有直接的指导信息,Agent 要以不断与 Environment 进行交互,通过试错的方式来获得最佳策略(Policy)。

2. 延迟回报:强化学习的指导信息很少,而且往往是在事后(最后一个状态(State))才给出的。比如 MR 中可能只有在每一次游戏结束以后才有一个 Game Over 或者 Win 的回报。

​ 总的来说,RL与其他机器学习算法不同的地方在于:

 1. 没有监督者,只有一个Reward信号;
2. 反馈是延迟的,不是立即生成的;
3. 强化学习是序列学习,时间在强化学习中具有重要的意义;
4. Agent的行为会影响以后所有的决策。

​ RL可以被抽象为一个序列预测的问题,只不过序列是通过类似图灵机一样的原理产生的,后一个State只有在前一个Action做出以后才可以得到。

\[ S_0\stackrel{a_0}{\longrightarrow}S_1\stackrel{a_1}{\longrightarrow}...\stackrel{a_{n-1}}{\longrightarrow}S_n \]

​ 其中\(S_i\)表示i时刻的State,\(a_i\)表示i时刻的Action。RL学习的目标就是学习一个根据当前State选择一个能够最大化全局收益的Action,我们把Agent根据State选择Action的方法叫做策略(Policy)。

第二部分:RL 算法

​ 强化学习的算法主要分为两大类: 基于值的算法(Value-Based)基于策略的算法(Policy-Based)。我首先分别介绍一下基于值和基于策略的经典算法,然后介绍一个将基于值和基于策略的算法的优点结合起来的框架——Actor-Critic(AC)框架。在AC框架下进一步介绍目前学术界用得最多的几种强化学习算法,也包括《RND》这篇论文中使用的PPO算法。

基于值的算法

​ 在介绍基于值的算法之前首先介绍两个概念 状态价值函数(State Value Function)-V(s)行为价值函数(Quality of State-Action function)-Q(s,a)

状态价值函数:状态价值函数V(s),输入是一个状态,输出是该状态的预期Reward。

\[ V_{\pi}(s) = E_{\pi}[G_0 | S_0 = s] \]

​ 其中\(\pi\)表示Agent选择Action的策略的概率分布, \(G_0|S_0=s\)表示从状态s开始到\(G_0\)状态整个序列。所以\(V_{\pi}(s)\)表示从当前状态开始到达\(G_0\)状态的预期收益。

​ 特别地,如果我们用\(R_t\)表示t时刻的预期收益,那么有

\[ V_{\pi}(s) = E_{\pi}[G_0 | S_0 = s] = E_{\pi}[\sum_{t=0}^{\infty}{\gamma^{t}R_{t+1}|S_0=s}] \]

​ 其中\(\gamma\)表示折扣因子,体现与当前状态更近的状态对与当前状态的预期期望贡献更大。

行为价值函数:行为价值函数Q(s,a),输入是一个状态和一个行动,输出是在该状态下采取该行动的预期收益,那么有

\[ Q_{\pi}(s, a) = E_{\pi}[G_0 | S_0 = s, A_0 = a] = E_{\pi}[\sum_{t=0}^{\infty}{\gamma^{t}R_{t+1}|S_0 = s, A_0 = a}] \]

​ 易知,V(s)和Q(s,a)之间有这样的关系

\[ V_{\pi}(s) = \sum_{a \in A}{Q_{\pi}(s, a)} \]

Q-learning

​ 下面我们给出经典的Q-learning的算法,伪代码如下所示

Q-learning pseudocode

​ Q-learning 算法通过构建和维护一个Q表,Q表中的每一项表示Q(s,a),来找到一个最优策略,这个策略能够最大化从当前状态开始所有的后继行动的期望收益。

​ Q-learning最重要的部分在于对于Q值的更新,从伪代码中我们可以看到,对于Q值的更新\(\Delta Q\)是两部分的差值乘以系数\(\alpha\)。一部分是\(r+\gamma max_{a^{\prime}}Q(s^{\prime}, a^{\prime})\)表示当前环境给出的即时回报,r表示当前环境给出的即时回报,\(\gamma max_{a^{\prime}}Q(s^{\prime}, a^{\prime})\)是对是对\(Q(s^{\prime}, a^{\prime})\)的最大估计(折扣因子为的最大估计(折扣因子为\(\gamma\)),所以第一部分总的表示对于当前(s,a)的Q值的现实值;另一部分为Q(s,a)表示Q(s,a)的估计值。

​ 除了Q-learning以外,还有Deep Q-learning、Double Q-learning 和 SARSA等基于值的算法。一般来说基于值的算法都是先评估每个(s, a) 元组的Q值-Q(s,a),再根据Q值求最优策略,基于值的方法适用于比较简单(状态空间比较小,或者Action数目较小)的问题,它有较高的数据利用率并且能稳定收敛。

​ 对于Q-learning来说,因为需要构建一个Q表,每一个(s,a)元组都需要对应一个Q值,所以只能解决State和Action均可数并且数目较小的问题。Deep Q-learning通过深度神经网络(Deep Neural Network, DNN)来估计一个函数\(g: S{\rightarrow}R^{|A|}\)用于对每一个State s,计算一个\(|A|\)维的向量,向量的每一维表示Q(s,a)对应的值,这样就能够应对State数目无穷的情况,但是仍然没办法解决\(|A|{\rightarrow}{\infty}\)的情况。

基于策略的算法

​ 我们已经知道Q-learning、DQN等基于价值的方法通过计算每一个状态动作的价值,选择价值最大的动作执行。这是一种间接选择策略的做法,并且几乎没办法处理Action数目无穷的情况。那么我们能不能直接对策略进行建模呢?

​ 一种比较直观的想法是我们可以构建这样一个策略网络(Policy Network) \(PN: S {\rightarrow} A\),输入一个状态直接输出对应的Action,而不是得到一个状态价值V(s)或者每个Action对应的Q值Q(s, a),然后直接对这个策略网络进行更新,从而直接对策略选择建模。如果我们用神经网络来模拟\(PN\),那么可以形式化的表示为:

\[ a = \pi(s, \theta)\ or\ a = \pi(a|s, \theta) \]

​ 可以直接输出确定的Action,也可以输出Action的一个概率分布。在输出概率分布的时候,虽然形式上和DQN类似都是\(S{\rightarrow}R^{|A|}\),但是DQN输出的是Q值,并且是基于Q值做Action的决策,而\(PN\)直接得到的是Action的概率分布,并且对于\(|A|{\rightarrow} {\infty}\)\(PN\)能够直接预测出Action。

Policy Gradient

\(Policy\ Gradient\)是基于策略的算法中最基础的一种算法。通过对收益期望求梯度,从而对Policy Network的参数进行更新。

​ 定义收益期望\(J(\theta)\)如下:

\[ J(\theta) = E_{\tau{\sim}\pi_{\theta}(\tau)}[r(\tau)] = \int_{\tau\sim\pi(\tau)}r(\tau)\pi_{\theta}(\tau)d\tau \]

\[ \theta^{*} = \mathop{argmax}_{\theta}(J(\theta)) \]

​ 对\(J(\theta)\)求导有

\[ \bigtriangledown_{\theta}J(\theta) = \bigtriangledown_{\theta}\int_{\tau\sim\pi(\tau)}r(\tau)\pi_{\theta}(\tau)d\tau=\int_{\tau\sim\pi(\tau)}r(\tau)\bigtriangledown_{\theta}\pi_{\theta}(\tau)d\tau \]

​ 又因为

\[ \bigtriangledown_{\theta}\pi_{\theta}(\tau) = \pi_{\theta}(\tau) \frac{\bigtriangledown_{\theta}\pi_{\theta}(\tau)}{\pi_{\theta}(\tau)} = \pi_{\theta}(\tau)\bigtriangledown_{\theta}log\pi_{\theta}(\tau) \]

\[ \begin{align} \bigtriangledown_{\theta}J(\theta) &= \int_{\tau\sim\pi(\tau)}\pi_{\theta}(\tau)r(\tau)\bigtriangledown_{\theta}log\pi_{\theta}(\tau)d\tau \\&= E_{\tau{\sim}\pi_{\theta}(\tau)}[r(\tau)\bigtriangledown_{\theta}log\pi_{\theta}(\tau)] \end{align} \]

\[ \begin{align} log\pi_{\theta}(\tau) & = log\pi_{\theta}(s_1, a_1, s_2, a_2, ...s_T, a_T) \\&= log\{p(s_1)\prod_{t=1}^{T}[\pi_{\theta}(a_t|s_t)p(s_{t+1}|s_t, a_t)]\} \\&= logp(s_1)+\sum_{t=1}^{T}log\pi_{\theta}(a_t|s_t)+\sum_{t=1}^{T}logp(s_{t+1}|s_t, a_t) \\&= logp(s_T)+\sum_{t=1}^{T}log\pi_{\theta}(a_t|s_t) = \sum_{t=1}^{T}log\pi_{\theta}(a_t|s_t) \end{align} \]

\[ r(\tau) = \sum_{t=1}^{T}r(s_t, a_t) \]

\[ \bigtriangledown_{\theta}J(\theta) = E_{\tau{\sim}\pi_{\theta}(\tau)}[\sum_{t=1}^{T}\bigtriangledown_{\theta} log\pi_{\theta}(a_t|s_t)\sum_{t=1}^{T}r(s_t, a_t)] \]

​ 最终我们得到了一个漂亮的\(\bigtriangledown_{\theta}J(\theta)\)的表达式,期望里面包括两个部分\(\sum_{t=1}^{T}\bigtriangledown_{\theta} log\pi_{\theta}(a_t|s_t)\)表示的是获取当前Trace的概率的梯度,\(\sum_{t=1}^{T}r(s_t, a_t)\)表示的是当前路径的总的回报。因为回报是一个总的回报,只能在一个轮次之后才能得到,所以Policy Gradient算法只能针对每一轮次更新,无法针对每个step更新。

​ 一个Policy Gradient算法REINFORCE的伪代码如下:
\(1.\ sample \{\tau^i\} \ from\ \pi_{\theta}(a_t|s_t)\ (run\ the\ policy)\)
\(2.\ \bigtriangledown_{\theta}J(\theta) \approx \sum_i(\sum_{t=1}^{T}\bigtriangledown_{\theta} log\pi_{\theta}(a_t^i|s_t^i)\sum_{t=1}^{T}r(s_t^i, a_t^i))\)
\(3.\ \theta \leftarrow \theta + \alpha \bigtriangledown_{\theta}J(\theta)​\)

Actor-Critic 框架

Based Actor-Critic

​ 由于最基础的Policy Gradient算法只能实现每轮次更新,很难准确地把Reward反馈回去,训练效率很差,并且很容易不收敛。所以想要将\(\sum_{t=1}^{T}r(s_t^i, a_t^i)\) 替换为\(Q(s_t^i, a_t^i)\)使用价值函数对当前的\((s_t^i, a_t^i)\)二元组的期望收益做一个评估,这样就能在每一步获取\(\bigtriangledown_{\theta} log\pi_{\theta}(a_t^i|s_t^i)Q(s_t^i, a_t^i)\)从而更新参数。

​ 所以最基础的AC框架的期望收益函数\(J(\theta)\)的梯度有如下的形式:

\[ \bigtriangledown_{\theta}J(\theta) = E_{\tau{\sim}\pi_{\theta}(\tau)}[\sum_{t=1}^{T}\bigtriangledown_{\theta} log\pi_{\theta}(a_t|s_t)Q(s_t, a_t)] \]

Advantage Actor Critic(A2C)

​ 后来研究表明这样的形式计算\(Q(s_t, a_t)\)有很大的方差。为了减小方差,将\(Q(s_t, a_t)\)替换为\(Q(s_t, a_t) - V(s_t)\),又结合\(Q(s,a)\)\(V(s)\)之间的关系(前文有过相关讨论),得到了一个Advantage函数,形式如下:

\[ A^{\pi}(s_t, a_t) = r(s_t, a_t) + V^{\pi}(s_{t+1}) - V^{\pi}(s_t) \]

​ 所以想要求得\(A^{\pi}(s_t, a_t)\)的值,我们只需要用一个神经网络对\(V(s_t)\)建模就好了。伪代码如下:

\(batch\ actor\ critic\ algorithm\)
\(1.\ sample\ \{s_i, a_i\}\ from\ \pi_{\theta}(a|s)\ (run\ it\ on\ the\ robot)\)
\(2.\ fit\ \hat{V}_{\Phi}^{\pi}(s)\ to\ sampled\ reward\ sums\)
\(3.\ evaluate\ \hat{A}^{\pi}(s_i, a_i) =r(s_i, a_i) + \hat{V}_{\Phi}^{\pi}(s_{i}^{\prime}) - \hat{V}_{\Phi}^{\pi}(s_i)\)
\(4.\ \bigtriangledown_{\theta}J(\theta) = \sum_i \bigtriangledown_{\theta} log\pi_{\theta}(a_i|s_i)\hat{A}^{\pi}(s_i, a_i)\)
\(5.\ \theta \leftarrow \theta + \alpha \bigtriangledown_{\theta}J(\theta)\)

Trust Region Policy Optimization (TRPO)

​ 虽然A2C很好的把Policy-Based和Value-Based两种方法结合了起来,并且能够做到step级别的更新,但是A2C没有考虑这样的问题:每一次的更新是否能够保证新的策略的\(J_{new}(\theta)\)大于\(J_{old}(\theta)\)

​ Schulman 2015年发表在ICML的论文《Trust Region Policy Optimization》讨论了这个问题,并且提出了TRPO算法,从理论上能够证明\(J_{new}(\theta) \ge J_{old}(\theta)\) 。Schulman把最终的优化问题转换成了

\[ \theta_{k+1} = \mathop{argmax}_\theta L(\theta_{k}, \theta) \\ s.t.\ \bar{D}_{KL}(\theta || \theta_{k}) \le \delta \\ where\ L(\theta_{k}, \theta) = \mathop{E}_{s,a\sim \pi_{\theta_{k}}}[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_{k}}(a|s)}A^{\pi_{\theta_k}}(s,a)] \]

​ 利用\(KL\)距离来限制old policy和new policy之间的距离,并且修改了目标函数,使得在满足\(KL\)限制下,\(J_{new}(\theta) \ge J_{old}(\theta)\)

​ TRPO在理论上和实践中都有很好的效果。

Proximal Policy Optimization(PPO)

​ TRPO虽然在理论上和实践中都有很好的效果,但是因为最后求解的问题过于复杂,导致训练时间复杂度很高。为了减少时间上的开销,OpenAI又提出了一个TRPO的改进方法PPO,通过一个Clip函数来截断\(r_t(\theta)\),从而用很小的代价实现了和\(KL\)距离的限制条件类似的功能。新的目标函数为:

\[ L^{CLIP}(\theta) = \hat{E}_t[\min(r_t(\theta)\hat{A}_t), \mathop{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon)\hat{A}_t] \\ r_t(\theta) = \frac{\pi_{\theta}(a_t|s_t)}{\pi_{\theta_{k}}(a_t|s_t)} \]

Reference

[1] Burda Y, Edwards H, Storkey A, et al. Exploration by Random Network Distillation[J]. arXiv preprint arXiv:1810.12894, 2018.

[2] Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms[J]. arXiv preprint arXiv:1707.06347, 2017.

[3] Schulman J, Levine S, Abbeel P, et al. Trust region policy optimization[C]//International Conference on Machine Learning. 2015: 1889-1897.

[4] Sutton R S, McAllester D A, Singh S P, et al. Policy gradient methods for reinforcement learning with function approximation[C]//Advances in neural information processing systems. 2000: 1057-1063.

[5] Sutton R S, Barto A G. Reinforcement learning: An introduction[M]. MIT press, 2018.

[6] Watkins C J C H, Dayan P. Q-learning[J]. Machine learning, 1992, 8(3-4): 279-292.

版权声明
本文为[scsn_dango]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/yeyuan111/p/10320050.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;