We study the stochastic Multi-Armed Bandit (MAB) problem with random delays in the feedback received by the algorithm. We consider two settings: the reward-dependent delay setting, where realized delays may depend on the stochastic rewards, and the reward-independent delay setting. Our main contribution is algorithms that achieve near-optimal regret in each of the settings, with an additional additive dependence on the quantiles of the delay distribution. Our results do not make any assumptions on the delay distributions: in particular, we do not assume they come from any parametric family of distributions and allow for unbounded support and expectation; we further allow for infinite delays where the algorithm might occasionally not observe any feedback.


翻译:我们研究的是随机拖延算法收到的反馈的多武装盗匪(MAB)问题。我们考虑了两个环境:取决于报酬的延迟设定,因为实际的延迟可能取决于随机的奖励,以及取决于报酬的延迟设定。我们的主要贡献是在每个环境中实现近于最佳的遗憾的算法,对延迟分布的四分位数还有额外的添加剂依赖。我们的结果对延迟分布不作任何假设:特别是,我们不认为它们来自任何分布的参数式组合,允许不受限制的支持和期待;我们进一步允许在算法偶尔可能看不到任何反馈的情况下出现无限的延迟。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Yoshua Bengio,使算法知道“为什么”
专知会员服务
7+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
LibRec 每周算法:parameter-free contextual bandits (SIGIR'15)
LibRec智能推荐
5+阅读 · 2017年6月12日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
专知会员服务
76+阅读 · 2021年3月16日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Yoshua Bengio,使算法知道“为什么”
专知会员服务
7+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
LibRec 每周算法:parameter-free contextual bandits (SIGIR'15)
LibRec智能推荐
5+阅读 · 2017年6月12日
Top
微信扫码咨询专知VIP会员