We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. While the setting in which delays only depend on time has been extensively studied, the arm-dependent delay setting better captures real-world applications at the cost of introducing new technical challenges. In the full information (experts) setting, we design an algorithm with a first-order regret bound that reveals an interesting trade-off between delays and losses. We prove a similar first-order regret bound also for the bandit setting, when the learner is allowed to observe how many losses are missing. These are the first bounds in the delayed setting that depend on the losses and delays of the best arm only. When in the bandit setting no information other than the losses is observed, we still manage to prove a regret bound through a modification to the algorithm of Zimmert and Seldin (2020). Our analyses hinge on a novel bound on the drift, measuring how much better an algorithm can perform when given a look-ahead of one round.


翻译:在拖延取决于时间和武器的情况下,我们研究非随机强盗和专家。虽然已经对拖延仅取决于时间的环境进行了广泛研究,但依靠手臂的拖延会以新的技术挑战为代价,更好地捕捉现实世界应用。在完整的信息(专家)环境下,我们设计了一种带有第一级遗憾的算法,它揭示了拖延和损失之间的一个有趣的权衡。我们证明,对于强盗环境来说,我们也有类似的第一级遗憾,它允许学习者观察损失了多少。这是延后环境的第一个界限,它仅取决于最佳手臂的损失和延误。在强盗中,除了观察损失之外,没有任何信息,我们仍然设法通过修改Zimmert和Seldin的算法(202020年)来证明遗憾。我们的分析取决于关于漂移的一小说,衡量在给一回合前看时算法能做得更好得多。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
推荐|Andrew Ng计算机视觉教程总结
全球人工智能
3+阅读 · 2017年11月23日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
4+阅读 · 2021年7月1日
Meta-Learning with Implicit Gradients
Arxiv
13+阅读 · 2019年9月10日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关VIP内容
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
推荐|Andrew Ng计算机视觉教程总结
全球人工智能
3+阅读 · 2017年11月23日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员