The stochastic multi-arm bandit problem has been extensively studied under standard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many real-world problems but sometimes they require knowledge (on tails for instance) that may not be precisely accessible to the practitioner, raising the question of the robustness of bandit algorithms to model misspecification. In this paper we study a generic Dirichlet Sampling (DS) algorithm, based on pairwise comparisons of empirical indices computed with re-sampling of the arms' observations and a data-dependent exploration bonus. We show that different variants of this strategy achieve provably optimal regret guarantees when the distributions are bounded and logarithmic regret for semi-bounded distributions with a mild quantile condition. We also show that a simple tuning achieve robustness with respect to a large class of unbounded distributions, at the cost of slightly worse than logarithmic asymptotic regret. We finally provide numerical experiments showing the merits of DS in a decision-making problem on synthetic agriculture data.


翻译:根据对手臂分布的标准假设(例如有已知支持、指数式家庭等),对多臂强盗问题进行了广泛研究。这些假设适用于许多现实世界问题,但有时需要知识(例如尾巴),而实践者可能无法准确获得这种知识,这就提出了强盗算法的稳健性问题,以模型错误区分。在本文中,我们研究了一种通用的Drichlet抽样算法,这种算法基于对经验性指数的对比,这种指数是用重新采集手臂观察结果和数据依据的勘探奖金来计算的。我们表明,当分布被捆绑和对准的半边际分布有轻微微小的微度条件时,这一战略的不同变式都取得了可想象的最佳遗憾保证。我们还表明,简单调整对于大类无限制的分布取得了稳健性,其代价略小于对正数的误差。我们最后提供了数字实验,表明DS在合成农业数据的决策问题上的优点。

0
下载
关闭预览

相关内容

专知会员服务
27+阅读 · 2021年7月20日
专知会员服务
50+阅读 · 2020年12月14日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2022年1月21日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员