Various algorithms in reinforcement learning exhibit dramatic variability in their convergence rates and ultimate accuracy as a function of the problem structure. Such instance-specific behavior is not captured by existing global minimax bounds, which are worst-case in nature. We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions and identify an instance-dependent functional that controls the difficulty of estimation in the $\ell_\infty$-norm. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning. Our theory provides a precise way of distinguishing "easy" problems from "hard" ones in the context of $Q$-learning, as illustrated by an ensemble with a continuum of difficulty.


翻译:强化学习中的各种算法在汇合率和最终准确性上都表现出巨大的差异,这是问题结构的一个函数。这种具体实例的行为没有被现有全球迷你最大边框所捕捉,这些边框在性质上是最坏的。我们用离散的状态和行动来分析为贴现的Markov决策程序估计最佳美元价值功能的问题,并找出一个能控制$@ ⁇ infty-norm 估算难度的基于实例的功能。我们使用一个本地的迷你框框架来显示,这种功能是在任何估算程序的准确性的较低界限中产生的。在另一个方向上,我们通过分析差异化的美元学习版本,确定我们较低的边框的清晰度,到州和行动空间的对数值。我们的理论提供了一种精确的方法,将“容易”的问题与“硬”问题区别在$Q-norm的范畴内。我们用一个具有连续困难的组合来说明。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
强化学习扫盲贴:从Q-learning到DQN
夕小瑶的卖萌屋
52+阅读 · 2019年10月13日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年8月30日
Arxiv
0+阅读 · 2021年8月27日
Arxiv
11+阅读 · 2020年12月2日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
强化学习扫盲贴:从Q-learning到DQN
夕小瑶的卖萌屋
52+阅读 · 2019年10月13日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员