Warning: session_start() expects parameter 1 to be array, string given in /www/wwwroot/blog/wp-includes/class-wp-hook.php on line 288
强化学习——从Q-Learning到DQN到底发生了什么? | 野风
  • 欢迎访问我的个人博客,如遇博客图片无法显示,请用IE浏览器访问。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧!

强化学习——从Q-Learning到DQN到底发生了什么?

强化学习 野风同学 1年前 (2020-06-22) 1816次浏览 0个评论 扫描二维码

学习目标

  1. 复习Q-Learning;
  2. 理解什么是值函数近似(Function Approximation);
  3. 理解什么是DQN,弄清它和Q-Learning的区别是什么。

用Q-Learning解决经典迷宫问题

现有一个5房间的房子,如图1所示,房间与房间之间通过门连接,编号0到4,5号是房子外边,即我们的终点。我们将agent随机放在任一房间内,每打开一个房门返回一个reward。图2为房间之间的抽象关系图,箭头表示agent可以从该房间转移到与之相连的房间,箭头上的数字代表reward值。



根据此关系,可以得到reward矩阵为

Q-Learning是一种off-policy TD方法,伪代码如图所示

我们首先会初始化一个Q表,用于记录状态-动作对的值,每个episode中的每一步都会根据下列公式更新一次Q表

Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]

这里的迷宫问题,每一次episode的结束指的是到达终点状态5。为了简单起见,这里将学习率 \alpha 设为1,更新公式变为

Q\left(S_{t}, A_{t}\right) \leftarrow R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)

另外,将衰减系数 \gamma设为0.8。Q表初始化为一个5×5的全0矩阵。下面这个小视频展示了一个episode中一步的更新过程,每次这样更新,最终Q表会收敛到一个矩阵。

最终Q表收敛为

因此,也可以得到最优路径如下红色箭头所示

Python代码:

import numpy as np
GAMMA = 0.8
Q = np.zeros((6,6))
R=np.asarray([[-1,-1,-1,-1,0,-1],
   [-1,-1,-1,0,-1,100],
   [-1,-1,-1,0,-1,-1],
   [-1,0, 0, -1,0,-1],
   [0,-1,-1,0,-1,100],
   [-1,0,-1,-1,0,100]])
def getMaxQ(state):
    return max(Q[state, :])
def QLearning(state):
    curAction = None
    for action in range(6):
        if(R[state][action] == -1):
            Q[state, action]=0
        else:
            curAction = action
            Q[state,action]=R[state][action]+GAMMA * getMaxQ(curAction)
count=0
while count<1000:
    for i in range(6):
        QLearning(i)
    count+=1
print(Q/5)

Q-Learning方法很好的解决了这个迷宫问题,但是这终究只是一个小问题(状态空间和动作空间都很小),实际情况下,大部分问题都是有巨大的状态空间或者动作空间,想建立一个Q表,内存是绝对不允许的,而且数据量和时间开销也是个问题

值函数近似与DQN

值函数近似(Function Approximation)的方法就是为了解决状态空间过大,也称为“维度灾难”的问题。通过用函数而不是Q表来表示 Q(s, a) ,这个函数可以是线性的也可以使非线性的。
\hat{v}(s, \boldsymbol{w}) \approx v_{\pi}(s) \text { or } \hat{q}(s, a, \boldsymbol{w}) \approx q_{\pi}(s, a)
其中 \boldsymbol{w} 称为“权重”。那怎么把这个权重求出来,即拟合出这样一个合适的函数呢?这里就要结合机器学习算法里的一些有监督学习算法,对输入的状态提取特征作为输入,通过MC/TD计算出值函数作为输出,然后对函数参数 \boldsymbol{w} 进行训练,直到收敛。这里主要说的是回归算法,比如线性回归、决策树、神经网络等。

这里,就可以引入DQN(Deep Q-Network)了,实际上它就是Q-Learning和神经网络的结合,将Q-Learning的Q表变成了Q-Network

好,现在关键问题来了。这么去训练这个网络呢?换句话说,怎么去确定网络参数 \boldsymbol{w} 呢?第一,我们需要一个Loss Function;第二,我们需要足够的训练样本

训练样本好说,通过 \varepsilon-greedy策略去生成就好。回忆一下Q-Learning,我们更新Q表是利用每步的reward和当前Q表来迭代的。那么我们可以用这个计算出来的Q值作为监督学习的“标签”来设计Loss Function,我们采用如下形式,即近似值和真实值的均方差

J(\boldsymbol{w})=\mathbb{E}_{\boldsymbol{\pi}}\left[\left(q_{\pi}(s, a)-\hat{q}(s, a, \boldsymbol{w})\right)^{2}\right]

采用随机梯度下降法(SGD)来迭代求解,得到我们想要的 \boldsymbol{w} ,具体公式和过程还请看参考资料,这里不展开了,其实就是求导啦。值得一提的是,上述公式中的q_{\pi}(s, a) 根据不同方法算出来,其形式不一样,比如利用MC,则为G_{t} (回报);利用TD(0),则为 R_{t+1}+\gamma \hat{q}\left(s_{t+1}, a_{t+1}, \boldsymbol{w}\right) ;Q-Learning呢,就是R_{t+1}+\gamma \max \hat{q}\left(s_{t+1}, a_{t+1}, \boldsymbol{w}\right)

在David Silver的课里,他根据每次更新所参与样本量的不同把更新方法分为增量法(Incremental Methods)和批处理法(Batch Methods)。前者是来一个数据就更新一次,后者是先攒一堆样本,再从中采样一部分拿来更新Q网络,称之为“经验回放”,实际上DeepMind提出的DQN就是采用了经验回放的方法。为什么要采用经验回放的方法?因为对神经网络进行训练时,假设样本是独立同分布的。而通过强化学习采集到的数据之间存在着关联性,利用这些数据进行顺序训练,神经网络当然不稳定。经验回放可以打破数据间的关联。

最后附上DQN的伪代码

学到这里,其实可以做一个阶段性总结了,强化学习算法的基本框架可以用下图概括

本专辑文章介绍了这个图里的大部分内容,但最重要、应用最为广泛的policy-based方法还没有介绍,这也是后面要着重去学习的。

学习资料

[1]Reinforcement Learning: An Introduction - Chapter 9: On-policy Prediction with Approximation
[2]Reinforcement Learning: An Introduction - Chapter 10: On-policy Control with Approximation
[3]David Silver's RL Course Lecture 6 - Value Function Approximation (video, slides)
[4]DQN从入门到放弃5 深度解读DQN算法
[5]一条咸鱼的强化学习之路6之值函数近似(Value Function Approximation)和DQN


《Reinforcement Learning: An Introduction 第二版》PDF书籍与David Silver课程,欢迎关注我的公众号“野风同学”,回复“RL”即可获取。
一个程序员的自我成长之路,持续分享机器学习基础与应用、LeetCode面试算法和Python基础与应用等技术干货文章,同时也经常推荐高质量软件工具、网站和书籍。


本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。如有侵权请邮件与我们联系处理。敬请谅解!
喜欢 (0)
[打赏赞助]
分享 (0)
野风同学
关于作者:
我是野风同学,这是我的主页。
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址