“AI 技术+人才”如何成为企业增长新引擎?戳此了解>>> 了解详情
写点什么

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

  • 2017-11-19
  • 本文字数:4428 字

    阅读完需:约 15 分钟

系列导读:《无痛的增强学习入门》系列文章旨在为大家介绍增强学习相关的入门知识,为大家后续的深入学习打下基础。其中包括增强学习的基本思想,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 年起在知乎开设了自己的专栏:《无痛的机器学习》,发表机器学习与深度学习相关文章,收到了不错的反响,并被多家媒体转载。曾多次参与社区技术分享活动。

公众号推荐:

2024 年 1 月,InfoQ 研究中心重磅发布《大语言模型综合能力测评报告 2024》,揭示了 10 个大模型在语义理解、文学创作、知识问答等领域的卓越表现。ChatGPT-4、文心一言等领先模型在编程、逻辑推理等方面展现出惊人的进步,预示着大模型将在 2024 年迎来更广泛的应用和创新。关注公众号「AI 前线」,回复「大模型报告」免费获取电子版研究报告。

AI 前线公众号
2017-11-19 17:083547

评论

发布
暂无评论
发现更多内容

专访|OpenTiny 社区 Mr 栋:结合兴趣,明确定位,在开源中给自己一些技术性挑战

OpenTiny社区

开源 前端 React UI组件库

币安进军 Web3 钱包领域预示着几个重要的趋势和发展

区块链软件开发推广运营

dapp开发 区块链开发 链游开发 NFT开发 公链开发

GPTs数据泄露大语言模型安全刻不容缓,如何用AI Agent提升LLM应用安全系数?

王吉伟频道

数据安全 大语言模型 AI Agent AI智能体 RPA Agent

Mac电脑矢量绘图软件:llustrator 2023 for mac最新激活版

iMac小白

区块链链游合约系统开发项目模式技术方案

西安链酷科技

区块链 设计 方案 链游 合约

区块链拆分

西安链酷科技

区块链 dapp 去中心化 拆分

如何使用Python调用API接口获取淘宝商品数据

Noah

App Cleaner & Uninstaller for Mac 完美激活 mac清理卸载工具

iMac小白

犀牛8 建模软件Rhinoceros 8 for Mac 完美激活版下载

iMac小白

Proxyman 4.14.0 for Mac - HTTP 调试代理应用程序

晴雯哥

DBeaverUltimate for Mac激活版下载(数据库管理软件)

iMac小白

挖掘外贸网站产品核心词,提高购物旺季的订单转化

九凌网络

Linux内核安全子系统简介(上)

nn-30

Linux Linux Kenel 内核 linux security 内核安全

Fig Player for Mac(多媒体播放器) 1.3.7激活版

影影绰绰一往直前

Fig Player Fig Player破解下载 Fig Player激活版

清华-用友数智化领导力项目正式开课!

用友BIP

数智化领导力

3大方面升级华为云CCE集群体验,助力集群高效运维管理

华为云开发者联盟

云原生 后端 华为云 华为云开发者联盟 华为云CCE容器服

Downie 4 for Mac(最好用的视频下载软件)

iMac小白

Axure RP 8 for Mac(交互式原型设计工具) 中文版

iMac小白

Acrobat Pro DC 2023 for mac 完美激活版下载

iMac小白

pycharm pro for mac破解版下载(Python编辑开发)

iMac小白

什么样的LED显示屏适合用在车站

Dylan

信息化 应用 LED显示屏 led显示屏厂家

Premiere Pro 2023 for Mac(pr 2023)完美激活版下载

iMac小白

哈希竞猜游戏开发源码部署方案

西安链酷科技

去中心化 交易所 链游 哈希竞猜

.NET Core中一些优秀的项目和框架

互联网工科生

.net core

从GPT定制到Turbo升级再到Assistants API,未来AI世界,你准备好了吗?

EquatorCoco

人工智能 AI GPT ChatGPT

Spring高手之路16——解析XML配置映射为BeanDefinition的源码

砖业洋__

spring源码 BeanDefinition分析 Spring框架内部工作 XML配置文件

网络安全专用产品有哪些?能一一列举出来吗?

行云管家

网络安全 防火墙 等保 安全运维

「智造」第6期:浅谈智能工厂

用友BIP

智能制造

WeChatTweak for Mac(多开和防撤回工具) macOS微信多开插件

影影绰绰一往直前

数字货币swap交易所逻辑系统开发分析方案

西安链酷科技

区块链 数字货币 去中心化

“ChatGPT 之父”暗讽马斯克;传安卓版本与鸿蒙将不再兼容;PICO 裁撤游戏工作室团队丨 RTE 开发者日报 Vol.83

声网

无痛的增强学习入门:Q-Learning_语言 & 开发_冯超_InfoQ精选文章