BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

无痛的增强学习入门:Q-Learning

| 作者 冯超 关注 7 他的粉丝 发布于 2017年11月20日. 估计阅读时间: 17 分钟 | Google、Facebook、Pinterest、阿里、腾讯 等顶尖技术团队的上百个可供参考的架构实例!

系列导读:《无痛的增强学习入门》系列文章旨在为大家介绍增强学习相关的入门知识,为大家后续的深入学习打下基础。其中包括增强学习的基本思想,MDP框架,几种基本的学习算法介绍,以及一些简单的实际案例。

作为机器学习中十分重要的一支,增强学习在这些年取得了十分令人惊喜的成绩,这也使得越来越多的人加入到学习增强学习的队伍当中。增强学习的知识和内容与经典监督学习、非监督学习相比并不容易,而且可解释的小例子比较少,本系列将向各位读者简单介绍其中的基本知识,并以一个小例子贯穿其中。

8 Q-Learning

8.1 Q-Learning

上一节我们介绍了TD的SARSA算法,它的核心公式为:

\(q_t(s,a)=q_{t-1}(s,a)+\frac{1}{N}[R(s')+q(s',a')-q_{t-1}(s,a)]\)

接下来我们要看的另一种TD的算法叫做Q-Learning,它的基本公式为:

\(q_t(s,a)=q_{t-1}(s,a)+\frac{1}{N}[R(s')+max_{a'} q(s',a')-q_{t-1}(s,a)]\)

两个算法的差别只在其中的一个项目,一个使用了当前episode中的状态-行动序列,另一个并没有,而是选择了数值最大的那个。这就涉及到两种不同的思路了。我们先暂时不管这个思路,来看看这个算法的效果。

首先还是实现代码:

def q_learning(self):
    iteration = 0
    while True:
        iteration += 1
        self.q_learn_eval()
        ret = self.policy_improve()
        if not ret:
            break

对应的策略评估代码为:

def q_learn_eval(self):
    episode_num = 1000
    env = self.snake
    for i in range(episode_num):
        env.start()
        state = env.pos
        prev_act = -1
        while True:
            act = self.policy_act(state)
            reward, state = env.action(act)
            if prev_act != -1:
                return_val = reward + (0 if state == -1 else np.max(self.value_q[state,:]))
                self.value_n[prev_state][prev_act] += 1
                self.value_q[prev_state][prev_act] += (return_val - \
                    self.value_q[prev_state][prev_act]) / \
                    self.value_n[prev_state][prev_act]
            prev_act = act
            prev_state = state
            if state == -1:
                break

实际的运行代码省略,最终的结果为:

Timer Temporal Difference Iter COST:4.24033594131
return_pi=81
[0 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0]
policy evaluation proceed 94 iters.
policy evaluation proceed 62 iters.
policy evaluation proceed 46 iters.
Iter 3 rounds converge
Timer PolicyIter COST:0.318824052811
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

可以看出,Q-Learning的方法和策略迭代比还是有点差距,当然通过一些方法是可以把数字提高的,但是这不是本文的重点了。不过从结果来看,Q-Learning比SARSA要好一些。

8.2 On-Policy与Off-Policy

实际上这两种算法代表了两种思考问题的方式,分别是On-Policy和Off-Policy。On-Policy的代表是SARSA,它的价值函数更新是完全根据episode的进展进行的,相当于在之前的基础上不断计算做改进;Off-Policy的代表是Q-Learning,它的价值函数中包含了之前的精华,所以可以算是战得更高,看得更远。当然也不能说Off-Policy就绝对好,Off-Policy还会带来一些自己的问题,总之我们需要具体问题具体分析。

这里最后再做一点对两大类算法的总结。其实如果游戏有终点,模型不复杂(像我们的蛇棋),蒙特卡罗法还是有绝对的优势,但是蒙特卡罗的软肋也比较明显,它需要完整的episode,产生的结果方差大,这对于一些大型游戏并不适合,所以在真正的产品级规模的增强学习上,TD的身影还是更多一些。

8.3 展望

由于篇幅的限制,到这里我们实际上就完成了对增强学习的一些基础内容的介绍,但是了解了这些内容,还不足以完成更加复杂的任务,下面就让我们简单了解一些更为高级的内容。

8.3.1 Function Approximation

前面我们提到的所有的增强学习算法都是基于表格的,表格的好处在于我们可以独立地考虑每一个状态、每一个行动的价值,不需要把很多状态汇集在一起考虑,然而在很多实际问题中,状态的数目非常多,甚至状态本身就不是连续的,那么采用表格来进行计算就显得不太现实,于是研究人员就开始研究一些更为合适的表达方式,这时候,我们的机器学习就登场了,我们可以建立一些模型,并用一个模型来表示状态、行动到价值函数的关系。

我们令状态为\(s \in S\),行动为\(a \in A\),最终的价值函数为\(v \in R\),那么我们要建立这样一个映射:

\(S \times A \rightarrow R\)

这样我们就把增强学习中的一个子问题转换成了监督学习,而监督学习是大家熟悉的套路,所以做起来就更加的得心应手了。实际上这就是一个回归问题,于是所有可以用于回归问题的模型都可以被我们用上。比方说线性回归,支持向量回归,决策树,神经网络。因为现在深度学习十分火,于是我们可以用一个深层的神经网络完成这个映射。

模型函数和监督学习使我们又了从另一个角度观察增强学习的可能。此时的模型要考虑bias和variance的权衡,要考虑模型的泛化性,这些问题最终都会映射到增强学习上。模型的表示形式也有很多种,前面给出的\(S \times A \rightarrow R\)只是模型表示的一种形式,我们还可以表示成\(S \rightarrow A,R\)这样的形式。对于第一种表示形式,由于不同的行动将作用在同一个状态下(或者不同的行动被同一种行动操纵),模型中的参数表示必然会存在重复,那么为了更好地共享参数,我们可以使用后面一种形式来表示。

说完了模型的形式,那么接下来就来看看模型的目标函数。最简单的目标函数自然是平方损失函数:

\(obj=\frac{1}{2}\sum_i^N(v'_i(s,a;w) - v_i)^2\)

其中的\(v_i'\)表示模型估计的价值,而\(v_i\)表示当前的真实价值,定义了目标函数,下面我们就可以利用机器学习经典的梯度下降法求解了:

\(\frac{\partial obj}{\partial w}=\sum_i^N (v_i' -v_i) \frac{\partial v_i'}{\partial w}\)

这个公式是不是看上去很眼熟?实际上如果

\(\frac{\partial v_i'}{\partial w}=1\)

,那么模型的最优解就等于

\(v_i'=\frac{1}{N}\sum_i^N v_i\)

也就是所有训练数据的平均值,这个结果和表格版的计算公式是一致的,也就是说表格版的算法实际上也是一种模型,只不过它的梯度处处为1。

关于模型更多的讨论,我们也可以取阅读各种论文,论文中对这里面的各个问题都有深入的讨论。

8.3.2 Policy Gradient

另外一个方向则是跳出已有的思维框架,朝着另一种运算方式前进。这种方法被称为Policy Gradient。在这种方法中,我们不再采用先求价值函数,后更新策略的方式,而是直接针对策略进行建模,也就是\(\pi(a|s)\)建模。

我们回到增强学习问题的源头,最初我们希望找到一种策略使得Agent的长期回报最大化,也就是:

\(max E_{\pi}[v_{\pi}(s_0)]\)

这个公式求解梯度可以展开为:

\(\nabla v_{\pi}(s_0)=E_{\pi}[\gamma^t G_t \nabla log \pi(a_t|s_t;w)]\)

更新公式为:

\(\theta_{t+1}=\theta_t + \alpha G_t \nabla log\pi(a_t|s_t;w)\)

这其中的推导过程就省略不谈了。得到了目标函数的梯度,那么我们就可以直接根据梯度去求极值了。我们真正关心的部分实际上是里面的那个求梯度的部分,所以当整体目标达到最大时,策略也就达到了最大值,因此目标函数的梯度可以回传给模型以供使用。由于log函数不改变函数的单调性,对最终的最优策略步影响,于是我们可以直接对\(log \pi(a|s;w)\)进行建模。这个方法被称为REINFORCE。

当然,这个算法里面还存在着一些问题。比方说里面的\(G_t\)同样是用蒙特卡罗的方法得到的。它和蒙特卡罗方法一样,存在着高方差的问题,为了解决高方差的问题,有人提出构建一个BaseLine模型,让每一个\(G_t\)减掉BaseLine数字,从而降低了模型的方差。更新公式为:

\(\theta_{t+1}=\theta_t + \alpha (G_t-b(S_t)) \nabla log\pi(a_t|s_t;w)\)

8.3.3 Actor-Critic

既然有基于Policy-Gradient的蒙特卡罗方法,那么就应该有TD的方法。这种方法被称为Actor-Critic方法。这个方法由两个模型组成,其中Actor负责Policy的建模,Critic负责价值函数的建模,于是上面基于BaseLine的REINFORCE算法的公式就变成了:

\(\theta_{t+1}=\theta_t + \alpha (R_{t+1}+\gamma \hat{v}(s_{t+1};w)-\hat{v}(S_t;w)) \nabla log\pi(a_t|s_t;w)\)

这样每一轮的优化也就变成了先根据模拟的episode信息优化价值函数,然后再优化策略的过程。

一般来说,上面公式中的\((R_{t+1}+\gamma \hat{v}(s_{t+1};w)-\hat{v}(S_t;w))\)表示向前看一步的价值和就在当前分析的价值的差。下棋的人们都知道“下棋看三步”的道理,也就是说有时面对一些游戏的状态,我们在有条件的情况下可以多向前看看,再做出决定,所以一般认为多看一步的价值函数的值会更高更好一些,所以上面的那一项通常被称为优势项(Advantage)。

在前面的实验中我们也发现,对于无模型的问题,我们要进行大量的采样才能获得比较精确的结果,对于更大的问题来说,需要的采样模拟也就更多。因此,对于大量的计算量,如何更快地完成计算也成为了一个问题。有一个比较知名且效果不错的算法,被称为A3C(Asynchronous Advantage Actor-Critic)的方法,主要是采用了异步的方式进行并行采样,更新参数,这个方法也得到了比较好的效果。

以上就是《无痛的增强学习》入门篇,我们以蛇棋为例介绍了增强学习基础框架MDP,介绍了模型已知的几种方法——策略迭代、价值迭代、泛化迭代法,介绍了模型未知的几种方法——蒙特卡罗、SARSA、Q-Learning,还简单介绍了一些更高级的计算方法,希望大家能从中有所收获。由于作者才疏学浅,行文中难免有疏漏之处,还请各位谅解。

作者介绍

冯超,毕业于中国科学院大学,猿辅导研究团队视觉研究负责人,小猿搜题拍照搜题负责人之一。2017年独立撰写《深度学习轻松学:核心算法与视觉实践》一书,以轻松幽默的语言深入详细地介绍了深度学习的基本结构,模型优化和参数设置细节,视觉领域应用等内容。自2016年起在知乎开设了自己的专栏:《无痛的机器学习》,发表机器学习与深度学习相关文章,收到了不错的反响,并被多家媒体转载。曾多次参与社区技术分享活动。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT