Confidence intervals are a crucial building block in the analysis of various online learning problems. The analysis of kernel based bandit and reinforcement learning problems utilize confidence intervals applicable to the elements of a reproducing kernel Hilbert space (RKHS). However, the existing confidence bounds do not appear to be tight, resulting in suboptimal regret bounds. In fact, the existing regret bounds for several kernelized bandit algorithms (e.g., GP-UCB, GP-TS, and their variants) may fail to even be sublinear. It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof, and the main challenge seems to stem from the online (sequential) nature of the observation points. We formalize the question of online confidence intervals in the RKHS setting and overview the existing results.


翻译:信任间隔是分析各种在线学习问题的关键基石。对内核土土匪和强化学习问题的分析利用适用于复制核心Hilbert空间(RKHS)元素的信任间隔。然而,现有的信任界限似乎并不紧凑,导致不尽人意的遗憾界限。事实上,若干内核强盗算法(如GP-UCB、GP-TS及其变种)的现有遗憾界限甚至可能无法成为亚线性。尚不清楚亚最佳遗憾界限是这些算法的基本缺陷还是证据的文物,主要挑战似乎来自观察点的在线(顺序)性质。我们在RKHS设定和概述现有结果时将在线信任间隔问题正式化。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
22+阅读 · 2021年12月19日
A Modern Introduction to Online Learning
Arxiv
20+阅读 · 2019年12月31日
VIP会员
相关VIP内容
专知会员服务
42+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员