This paper considers two fundamental sequential decision-making problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus on stochastic regimes in which an adversary may corrupt losses, and we investigate what level of robustness can be achieved against adversarial corruptions. The main contribution of this paper is to show that optimal robustness can be expressed by a square-root dependency on the amount of corruption. More precisely, we show that two classes of algorithms, anytime Hedge with decreasing learning rate and algorithms with second-order regret bounds, achieve $O( \frac{\log N}{\Delta} + \sqrt{ \frac{C \log N }{\Delta} } )$-regret, where $N, \Delta$, and $C$ represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide a matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi-armed bandit problem, we also provide a nearly tight lower bound up to a logarithmic factor.


翻译:本文探讨了两个基本的先后决策问题:用专家意见预测的问题和多臂匪盗问题。 我们侧重于对手可能腐败损失的随机制度,我们调查在对抗敌对腐败方面能够达到的稳健程度。 本文的主要贡献是表明最佳的稳健性可以表现为对腐败程度的平底依赖。 更确切地说, 我们展示了两类算法, 即随着学习率下降而随时与第二阶差错的学习率和算法相冲突, 达到O( \ frac) nunDelta} +\ sqrt{\ sqrt{ \ frac{ C\log N un Delta}} 和 $- regret, 分别代表专家人数、 差距参数和腐败程度。 我们还提供了相应的较低约束, 这就意味着这种遗憾的束缚将紧到一个不变的因素。 对于多臂匪盗问题, 我们还提供了近乎更窄的下限到一个对数系数。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2021年8月8日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Sequential Community Mode Estimation
Arxiv
0+阅读 · 2021年11月16日
Arxiv
0+阅读 · 2021年11月15日
Arxiv
0+阅读 · 2021年11月14日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员