专栏首页机器之心AAAI 2018 | 阿尔伯塔大学提出新型多步强化学习方法,结合已有TD算法实现更好性能

AAAI 2018 | 阿尔伯塔大学提出新型多步强化学习方法,结合已有TD算法实现更好性能

选自arXiv

作者:Kristopher De Asis等

机器之心编译

在 AAAI 2018 接收论文列表中,来自阿尔伯塔大学强化学习和人工智能实验室 Richard S. Sutton 等研究者的一篇论文提出一种新的多步动作价值算法 Q(σ),该算法结合已有的时序差分算法,可带来更好性能。机器之心对此论文做了简要介绍,更多详细内容请查看原文。

时序差分(TD, Sutton, 1988)法是强化学习中的一个重要概念,结合了蒙特卡洛和动态规划法。TD 允许在缺少环境动态模型的情况下从原始经验中直接进行学习,这一点与蒙特卡洛方法类似;同时也允许在最终结果未出来时基于其他学得的评估更新评估结果,与动态规划法类似。TD 法的核心概念提供一个构建多种强大算法的灵活框架,这些算法可用于预测和控制。

TD(λ) 算法结合一步 TD 学习(one-step TD learning)和蒙特卡洛方法(Sutton, 1988)。通过使用 eligibility trace 和 trace-decay 参数,λ ∈ [0, 1],创建了一系列算法。当λ = 1 时,就是蒙特卡洛方法,λ = 0 时,就是一步 TD 学习。

人们通常认为多步 TD 方法是多个不同长度步长的收益平均值,通常与 eligibility trace 有关,和 TD(λ) 一样。但是,也可以认为它们是相关的 n 步备份的第 n 步收益(Sutton & Barto, 1998)。

Q(σ) 是 Sutton 和 Barto 2017 年提出的算法,该算法结合和推广了现有的多步 TD 控制方法。该算法执行的采样程度由采样参数 σ 控制。当 σ = 1 时出现 Sarsa(全采样),当 σ = 0 时出现树备份(Tree-backup,纯粹预期)。σ 的中间值构建的算法既有采样也有预期。这篇论文展示了 σ 的中间值构建的算法优于 σ 等于 0 或 1 时的算法。此外,研究者还展示了 σ 可以进行动态调整,以输出更好的性能。研究者将对 Q(σ) 的讨论限制在没有 eligibility trace 的 atomic 多步情况,但是使用复合备份(compound backup)是其自然扩展,也是未来研究的方向。Q(σ) 通常可用于在策略和离策略学习,但是该论文中的初始实验仅研究在策略预测和控制问题。

论文:Multi-step Reinforcement Learning: A Unifying Algorithm

论文链接:https://arxiv.org/abs/1703.01327

摘要:结合看似完全不同的算法来生成性能更好的算法是强化学习的长久以来的目标。作为主要示例,TD(λ) 使用 eligibility trace 和 trace-decay 参数 λ 将一步 TD 预测和蒙特卡洛方法结合起来。目前,有大量算法可用于执行 TD 控制,包括 Sarsa、Q-learning 和 Expected Sarsa。这些方法通常用于一步的情况中,但是它们可以扩展到多步以达到更好的性能。其中每一个算法都是针对不同任务的特定算法,没有一个在所有问题上优于其他算法。本论文研究一种新的多步动作价值算法 Q(σ),该算法结合和推广了这些已有算法,并对它们进行子求和(subsuming)作为特殊案例。新参数 σ 被引入作为算法每一步执行的采样程度,其备份不断改变,当 σ = 1 时出现 Sarsa(全采样),当 σ = 0 时出现 Expected Sarsa(纯粹预期)。Q(σ) 通常可用于在策略(on-policy)和离策略(off-policy)学习,但是本论文主要关注在策略的情况。实验结果显示 σ 的中间值会带来现有算法的混合,性能优于 σ 在两级的情况。该混合可以动态调整,带来更好的性能。

可视化备份操作的常见方式是使用备份图示,如图 1 所示。

图 1. atomic 4 步 Sarsa、Expected Sarsa、Tree-backup 和 Q(σ) 的备份图示。我们可以看到 Q(σ) 基于 σ 的设置包含其他三种算法。

算法 1 展示了在策略 Q(σ) 的伪代码:

图 3. 带有 19 个状态的随机游走结果。上图从价值函数的 RMS 误差的角度展示了 Q(σ) 的性能。结果是 100 次运行的平均值,标准误差全部小于 0.006。Q(1) 具备最优初始性能,Q(0) 具备最优渐近性能,动态 σ 优于所有的固定 σ 值。

图 5. Stochastic windy gridworld 结果。上图通过对于不同 σ 值和α值的函数运行 100 episode 的平均收益展示了 Q(σ) 的性能。结果首先是选定 α 值的结果,然后是直线,之后是 1000 次运行的平均值。标准误差低于 0.05,差不多是线的宽度。4 步算法的性能优于 1 步算法,σ 为动态值的 Q(σ) 性能最好。

图 6. 山崖环境。智能体的目标是在不掉下山崖的前提下驶过小旗。该智能体每一个时间步收到的奖励为 -1,而掉下山崖就会在山谷的随机初始位置得到 -100 的奖励。

图 7:山崖结果。上图通过每个 episode 的平均回报展示了每个 atomic 多步算法的性能。为了平滑结果,采用了适当均值的移动平均数,其带有 100 个连续 episode 的窗口。σ 为动态值的 Q(σ) 性能最好。

本文分享自微信公众号 - 机器之心(almosthuman2014)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-12-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Hacker News热议:封装包那么多,程序员还用学习算法吗?

    如果你是几十年前的程序员,那你一定精通于算法,并经常需要自己编写算法。但在今天,算法已经变成了一种「商品」,从业者都在使用现成的软件包和购买的算法。甚至有人提出...

    机器之心
  • NeurIPS 2018提前看:生物学与学习算法

    Joni 目前是日本国立产业综合研究所的研究员。在中国大陆本科本行是自动化,后来对机器人研究有兴趣,在香港就读了电机工程的 Mphil 学位。博士时开始着迷生物...

    机器之心
  • 深度 | 谷歌和OpenAI新研究:如何使用达尔文进化论辅助设计人工智能算法?

    选自QZ 作者:Dave Gershgorn 机器之心编译 参与:吴攀、黄小天、李亚洲 现代机器智能建立在模仿自然的基础之上——这一领域的主要目的是在计算机中复...

    机器之心
  • 阿里算法工程师面经

    牛客网
  • 算法系列1 初识算法 算法复杂性模型 算法复杂度的计算

    定义:由若干条指令组成的有穷序列,且满足:输出输入,确定性,有限性 输入:有零个或多个由外部提供的量作为算法的输入 输出:算法产生至少一个量作为算法的输出 ...

    一只胡说八道的猴子
  • 极客算法训练笔记(一),算法学习方法篇

    付完款那一刻我忍不住吐槽“哇塞,我可真有钱”,一看余额“我去,伤心的人那么多~我变成了其中一个~”(这首歌叫啥来着,好像有点应景)。

    阿甘的码路
  • 了解一下“算法”,每个人都要掌握的编程知识

    假设我们有一个难题需要解决,那怎么解决呢?解决的步骤怎样呢?如果有一样东西能把这个解决这个难题的步骤描述出来,那就叫做这个问题的算法。

    讲编程的高老师
  • 这 3 个学数据结构和算法的网站,相信你也会喜欢的!

    而我比较特殊,我的第一印象、第二印象以至第 N 印象都觉得很难,所以为了更好的学习和理解算法,我千金一掷一下买了一堆的算法书,有图为证:

    五分钟学算法
  • 机器学习入门基础(二)

    1)线性回归:进行直线或曲线拟合,一般使用“最小二乘法”来求解。最小二乘法将最优问题转化为求函数极值问题。函数极值在数学上我们一般会采用求导数...

    长风破浪
  • Hacker News热议:封装包那么多,程序员还用学习算法吗?

    如果你是几十年前的程序员,那你一定精通于算法,并经常需要自己编写算法。但在今天,算法已经变成了一种「商品」,从业者都在使用现成的软件包和购买的算法。甚至有人提出...

    机器之心

扫码关注云+社区

领取腾讯云代金券