专栏首页arxiv.org翻译专栏异步 Q-Learning 的样本复杂度:更敏锐的分析和方差减少技术(CS LG)
原创

异步 Q-Learning 的样本复杂度:更敏锐的分析和方差减少技术(CS LG)

异步 Q-learning 的目的是基于行为策略诱导的马尔科夫样本的单一轨迹,学习马尔科夫决策过程(MDP)的最优行动值函数(或Q-function)。专注于一个具有状态空间 \mathcal{S} 和行动空间 \mathcal{A}γ 折现 MDP,我们证明了经典异步 Q-learning 的基于 \ell_{\infty} 的样本复杂度--即产生Q-function 的入口 \varepsilon 精确估计所需的样本数--最多只在 \begin{equation*} \frac{1}{μ_{\mathsf{min}}(1-γ)^5\varepsilon^2}+ \frac{t_{\mathsf{mix}}}{μ_{\mathsf{min}}(1-γ)} \end{equation*} 的数量上。在采用适当的恒定学习率的前提下,即 可达某个对数系数。这里,t_{\mathsf{mix}}μ_{\mathsf{min}} 分别表示混合时间和样本轨迹的最小状态动作占用概率。该约束的第一项与从轨迹的固定分布中抽取独立样本的情况下的复杂性相匹配。第二项反映了马尔科夫轨迹的经验分布达到稳定状态所需的费用,它在一开始就产生,并随着算法的运行而摊销。令人振奋的是,上述边界比最先进的结果至少提高了 |\mathcal{S}|||\mathcal{A}| 的系数。此外,贴现复杂度的缩放可以通过减少方差的方法来改善。

原文题目:Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction

原文:Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a γ-discounted MDP with state space \mathcal{S} and action space \mathcal{A}, we demonstrate that the \ell_{\infty}-based sample complexity of classical asynchronous Q-learning -- namely, the number of samples needed to yield an entrywise \varepsilon-accurate estimate of the Q-function -- is at most on the order of \begin{equation*} \frac{1}{μ_{\mathsf{min}}(1-γ)^5\varepsilon^2}+ \frac{t_{\mathsf{mix}}}{μ_{\mathsf{min}}(1-γ)} \end{equation*} up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, t_{\mathsf{mix}} and μ_{\mathsf{min}} denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the complexity in the case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the expense taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result by a factor of at least |\mathcal{S}||\mathcal{A}|. Further, the scaling on the discount complexity can be improved by means of variance reduction.

原文作者:Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen

原文地址:https://arxiv.org/abs/2006.03041

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深度学习在医学影像上的应用(二)——图像重建及后处理,标注,回归,配准,图像超分辨率

    上一篇给大家介绍了深度学习在医学影像上分类的应用案例,这一篇我将分享深度学习在医学影像上关于图像重建及后处理,图像标注,图像配准,图像超分辨率和回归的应用。

    医学处理分析专家
  • 【干货】ICML2018:63篇强化学习论文精华解读!

    【新智元导读】机器学习顶会ICML 2018从2473份提交论文中接收了621篇,其中有63余篇强化学习相关论文,作者将这些论文分成了多个类别,并对每篇文章的核...

    新智元
  • 【ICML2018】63篇强化学习论文全解读

    【导读】一年一度的国际机器学习会议( ICML ),于7月15日在瑞典斯德哥尔摩闭幕,ICML 的会议日程之紧凑,会议内容之丰富,令人目不暇接。今年从2,473...

    AI科技大本营
  • PPO(Proximal Policy Optimization)近端策略优化算法

    强化学习可以按照方法学习策略来划分成基于值和基于策略两种。而在深度强化学习领域将深度学习与基于值的Q-Learning算法相结合产生了DQN算法,通过经验回放池...

    狼啸风云
  • 测量误差对聚类算法的影响(CS LG)

    聚类由一组流行的技术组成,这些技术用于将数据分成兴趣小组以进行进一步分析。许多进行聚类的数据源都存在随机的或系统的测量误差,这些错误可能会对集群产生不利影响。虽...

    Elva
  • 经典回顾!Github 上打星超过 1 万的可复现顶会论文项目

    AI 科技评论按:Zaur Fataliyev 是在 LG 电子的一名机器学习工程师,为了方便大家对带有复现代码的经典顶会论文进行查询,他在 GitHub 上将...

    AI研习社
  • 经典回顾!Github 上打星超过 1 万的可复现顶会论文项目

    AI 科技评论按:Zaur Fataliyev 是在 LG 电子的一名机器学习工程师,为了方便大家对带有复现代码的经典顶会论文进行查询,他在 GitHub 上将...

    abs_zero
  • 经典回顾!Github 上打星超过 1 万的可复现顶会论文项目

    AI 科技评论按:Zaur Fataliyev 是在 LG 电子的一名机器学习工程师,为了方便大家对带有复现代码的经典顶会论文进行查询,他在 GitHub 上将...

    AI科技评论
  • DeepMind和剑桥、普朗克研究所共同论文:基于模型加速的连续深度Q-learning方法

    摘要 模型无关的强化学习被成功应用于许多难题,最近还被用于处理大型神经网络策略和价值函数。然而,模型无关的算法的样本复杂度往往限制了它们在硬件系统中的应用,尤其...

    AI科技评论
  • 8比特数值也能训练模型?商汤提训练加速新算法丨CVPR 2020

    在CVPR 2020上,商汤研究院链接与编译团队、高性能计算团队和北航刘祥龙老师团队合作提出了用于加速卷积神经网络训练过程的INT8训练技术。该工作通过将网络的...

    AI科技大本营
  • 莫凡《机器学习》笔记

    机器学习方法 1.1 机器学习 通常来说, 机器学习的方法包括: 监督学习 supervised learning:(有数据有标签)在学习过程中,不断的向计算...

    闪电gogogo
  • 深度学习盛会 ICLR-17 最佳论文出炉!机器自主编程 NPI 再称雄

    1 新智元编译 来源:iclr.cc、openreview.net 编译:闻菲、张易、刘小芹 【新智元导读】深度学习盛会 ICLR 2017 日程及最佳论文...

    新智元
  • ICLR 2019 |一文尽览 ICLR 2019 Facebook & Google 入选论文

    AI 科技评论按,近日,ICLR 2019 论文入选结果公布,各大公司和研究院纷纷在博客上公布了今年入选的论文。

    AI科技评论
  • 图片相似性匹配中的特征提取方法综述

    stevenmiao(苗捷),2016年7月博士毕业于华南理工大学,应届毕业加入TEG信息安全部。八年计算机视觉算法经验,博士期间主要研究面向视频的特征提取和内...

    TEG云端专业号
  • ICML 2016 谷歌 DeepMind 论文上辑(大咖点评附下载)

    【新智元导读】ICLR2016 最佳论文获奖团队、谷歌 DeepMind 有9篇论文被即将于19日召开的深度学习重要会议 ICML2016 接收。新智元系统整理...

    新智元
  • 无参考质量评估在视频增强的进展与应用

    大家可能对有参考质量评估有一定了解,某些有参考评价在应用上会有所限制,甚至在视频增强领域会存在不适应性,因此在第一阶段内容里会提到腾讯在无参考质量评估方面投入的...

    LiveVideoStack
  • 开源 | OpenAI基准DQN及其三个变体:通过最佳实践确保DQN正确性

    选自Open AI Blog 机器之心编译 参与:黄小天、微胖 我们开源了 OpenAI 基准(https://github.com/openai/baseli...

    机器之心
  • 谷歌分享注视点渲染技术的新研究成果

    显示器分辨率在不断提高,但图形处理能力并没有以同样的速度提升。注视点渲染技术通常被认为是下一代头显必备的能力,该技术能够让头显降低对显卡渲染的要求,显卡会集中渲...

    企鹅号小编
  • 丽影 - 质量评估,让你知道视频有多美!

    ? 不知道你会不会跟小编一样,照镜子的时候自我感觉良好,一拍照的时候总觉得哪里不对劲?如果说相机记录了你的容颜,那么自己照镜子的时候,多少脑补了一些王力宏、胡...

    腾讯多媒体实验室

扫码关注云+社区

领取腾讯云代金券