走近流行强化学习算法:最优Q-Learning

Q-Learning 是最著名的强化学习算法之一。我们将在本文中讨论该算法的一个重要部分:探索策略。但是在开始具体讨论之前,让我们从一些入门概念开始吧。

强化学习(RL)

强化学习是机器学习的一个重要领域,其中智能体通过对状态的感知、对行动的选择以及接受奖励和环境相连接。在每一步,智能体都要观察状态、选择并执行一个行动,这会改变它的状态并产生一个奖励。

马尔科夫决策过程(MDP)

在绝大多数传统的设置中,RL 解决 MDP。即使在 RL 的核心部分,我们也不会在本文中涉及 MDP 理论。维基百科上有关于 MDP 很好的简介。

我们将要解决「forest fire」的马尔科夫决策问题,这个在 python 的 MDP 工具箱(http://pymdptoolbox.readthedocs.io/en/latest/api/example.html)中是可以看到的。

森林由两种行动来管理:「等待」和「砍伐」。我们每年做出一个行动,首要目标是为野生动物维护一片古老的森林,次要目标是伐木赚钱。每年都会以 p 的概率发生森林火灾(森林正常生长的概率就是 1-p)。

我们将马尔科夫决策过程记为 (S, A, P, R, γ),其中:

S 是有限状态空间:按照树龄分为三类:0—20 年,21—40 年,大于 40 年

A 是有限行动空间:「等待」和「砍伐」

P 和 R 是转换矩阵和奖励矩阵,它们的闭合形式容易表达出来

γ是表示长期奖励和短期奖励之间的区别的折扣因子

策略π是在给定的当前状态下动作的平稳分布(马尔可夫性)

目标就是找到在不了解任何马尔科夫动态特性的情况下来寻找马尔科夫决策过程的最优策略π*。需要注意的是,如果我们具有这种知识,像最有价值迭代这种算法就可以找到最优策略。

这里的最优策略是相当符合直觉的,就是等到森林达到最老的树龄再砍伐,因为我们把树龄最老的时候的砍伐奖励设置成了其成长过程中的 5 倍(r1=10,r2=50)。

Q-LEARNING

Q-Learning 中策略(π)的质量函数,它将任何一个状态动作组合(s,a)和在观察状态 s 下通过选择行动 a 而得到的期望积累折扣未来奖励映射在一起。

Q-Leraning 被称为「没有模型」,这意味着它不会尝试为马尔科夫决策过程的动态特性建模,它直接估计每个状态下每个动作的 Q 值。然后可以通过选择每个状态具有最高 Q 值的动作来绘制策略。

如果智能体能够以无限多的次数访问状态—行动对,那么 Q-Learning 将会收敛到最优的 Q 函数 [1]。

同样,我们也不会深入讨论 Q-Learning 的细节。如果你对它不太熟悉,这里有 Siraj Raval 的解释视频。

下面我们将展示 Q-Learning 的 Python 实现。请注意,这里所拥的学习率(alpha)遵循 [3] 的结果,使用 w=0.8 的多项式。

这里用到的探索策略(ε-greedy)在后面会有细节介绍。

Exploration/Exploitation 权衡

连续学习算法会涉及到一个基本的选择:

Exploitation: 在目前已经给定的信息下做出最佳选择

Exploration: 通过做出其他选择收集更多的信息

成功的平衡 exploration 和 exploitation 对智能体的学习性能有着重要的影响。太多的 exploration 会阻止智能体最大化短期奖励,因为所选的 exploration 行动可能导致来自环境的不良奖励。另一方面,在不完全的知识中 exploiting 会阻止智能体最大化长期奖励,因为所选的 exploiting 行动可能一直不是最优的。

ε-greedy exploration 策略

这是一个很朴素的 exploration 策略:在每一步都以概率 ε选择随机的动作。

这也许是最常用的、也是最简单的 exploration 策略。在很多实现中,ε都被设置为随时间衰减,但是在一些例子中,ε也被设置为定值。

「乐观面对不确定性」的 exploration 策略

这个概念首次在随机多臂赌博机(SMAB)环境中被首次提出,这是一个古老的决策过程,为了最大化机器给出的期望折扣奖励,赌徒在每一步都要决定摇动哪一个机器。

赌徒面临着一个 exploration/exploitation 权衡,使用具有最高平均奖励的机器或者探索其他表现并不是很好的机器以得到更高的奖励。

SMAB 和 Q-Learning 中的 exploration 问题很相似。

Exploitation: 在给定的状态下选择具有最高 Q 值的动作

Exploration: 探索更多的动作(选择没有被足够得访问或者从未被访问的动作)

图片来自微软研究院

「面对不确定性的乐观」(OFU)状态:无论什么时候,我们都对老虎机的输出结果是不确定的,所以我们预计环境是最好的,然后选择最好的老虎机。

OFU 背后的直觉是:

如果我们处于最好的处境:OFU 会选择最佳的老虎机(没有遗憾)

如果我么不在最好的处境中:不确定性会减少(最佳)

最著名的 OFU 算法之一是 UCB(置信区上界)[2]。我们按照下面的方法将它用在 Q-learning 中。

定义:

Q(s, a): 状态 s 下采用动作 a 的 Q 值

N(t, s, a):在时间 t,动作 a 在状态 s 被选择的次数

智能体的目标是:Argmax 。代表在状态 s 下选择具有最大 Q 值的动作。但是时间 t 的实际 Q(s, a) 是未知的。

我们有:Q(s,a) = + (Q(s,a) �6�1 ),是时间 t 估计的 Q 值。(Q(s,a) �6�1 ) 对应的是误差项,我们可以形成边界并使用 OFU。

Hoeffding 不等式是限制这个误差的一种方式,我们可以证明:

最优策略可以被写成:

Argmax

其中β ≥ 0 调节 exploration。当β=0 的时候,该策略仅仅利用过去的估计(遵循 leader 策略)。

这个范围是该领域最常用的。还有很多其他改进这个范围的工作(UCB-V、UCB、KL-UCB、Bayes-UCB、BESA 等)。

这里是我们对经典 UCB exploration 策略的实现,以及它在 Q-Learning 中使用的结果。

UCB exploration 似乎能够快速地达到很高的奖励,然而训练过程还是受到早期 exploration 的干扰,对于更复杂的马尔科夫决策过程而言,这是有优势的,因为智能体可以免于非最优的解决方案。

我们来更加仔细地比较这两种策略。

总结及展望

Q-learning 是最常用的强化学习算法之一。在这篇文章中,我们讨论了 exploration 策略的重要性以及 UCB exploration 策略的使用,而并非最出名的ε-greedy exploration 策略。为了平衡 exploration 和 exploitation,更多的改进乐观策略可能会被用到。

参考文献

[1] T. Jaakkola, M. I. Jordan, and S. P. Singh,「On the convergence of stochastic iterative dynamic programming algorithms」Neural computation, vol. 6, no. 6, pp. 1185–1201, 1994.

[2] P. Auer,「Using Confidence Bounds for Exploitation-Exploration Trade-offs」, Journal of Machine Learning Research 3 397–422, 2002.

[3] E. Even-Dar, Y. Mansour,「Learning Rates for Q-learning」, Journal of Machine Learning Research 5 1–25, 2003.

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王照彬的专栏

【 SPA大赛 】腾讯社交广告大赛初赛阶段小结

总结了腾讯高校算法大赛初赛的数据分析与处理心得, 主要包括了时序分析, 训练集选取与处理, 基于树关系的贝叶斯平滑方法等.

95400
来自专栏AI研习社

测量神经网络真的难吗?Uber 说未必

过去十年来,神经网络彻底改变了机器学习。机器学习从一个相对晦涩的学术研究领域崛起成为工业支柱,在大量数据可用的地方为众多应用提供支持。Uber 将神经网络用于多...

13130
来自专栏人工智能头条

机器学习安全不容忽视

10740
来自专栏简书专栏

深度学习图像方向学习线索

深度学习框架选择:tensorflow、pytorch 文章《TensorFlow和PyTorch谁更好》链接:https://mp.weixin.qq.co...

17330
来自专栏ATYUN订阅号

谷歌开源AI新模型,区分语音准确度达到92%

Speaker diarization即根据谁说什么,以及什么时候说,将语音样本划分为独特的,同质的片段的过程,对机器来说不像人类那么容易,并且训练机器学习算法...

8720
来自专栏IT派

什么是深度学习?

什么是深度学习 深度学习,顾名思义,需要从“深度”和“学习”两方面来谈。 01 深度 深度学习的前身是人工神经网络(artificial neural netw...

36880
来自专栏PPV课数据科学社区

多模型融合推荐算法——从原理到实践

1 研发背景 互联网时代也是信息爆炸的时代,内容太多,而用户的时间太少,如何选择成了难题。电商平台里的商品、媒体网站里的新闻、小说网站里的作品、招聘网站里的职位...

49170
来自专栏量子位

强化学习如何入门?看这篇文章就够了

对于大脑的工作原理,我们知之甚少,但是我们知道大脑能通过反复尝试来学习知识。我们做出合适选择时会得到奖励,做出不切当选择时会受到惩罚,这也是我们来适应环境的方式...

17430
来自专栏AI科技评论

学界 | MIT周博磊团队:时序关系网络帮助计算机填补视频帧之间的空白

AI 科技评论按:如果你向一个人仅仅展示一段视频中的几帧,他通常可以推测出视频里发生的是什么事件以及屏幕上会显示出什么。例如,如果我们在视频开始时的帧中看到了一...

16430
来自专栏PPV课数据科学社区

收藏 | 27个机器学习小抄(附学习资源)

本文多资源,建议收藏。 本文针对机器学习基本概念及编程和数学基础,为你列出相应的学习资源。

17610

扫码关注云+社区

领取腾讯云代金券