We study the adversarial multi-armed bandit problem and create a completely online algorithmic framework that is invariant under arbitrary translations and scales of the arm losses. We study the expected performance of our algorithm against a generic competition class, which makes it applicable for a wide variety of problem scenarios. Our algorithm works from a universal prediction perspective and the performance measure used is the expected regret against arbitrary arm selection sequences, which is the difference between our losses and a competing loss sequence. The competition class can be designed to include fixed arm selections, switching bandits, contextual bandits, or any other competition of interest. The sequences in the competition class are generally determined by the specific application at hand and should be designed accordingly. Our algorithm neither uses nor needs any preliminary information about the loss sequences and is completely online. Its performance bounds are the second order bounds in terms of sum of the squared losses, where any affine transform of the losses has no effect on the normalized regret.


翻译:我们研究对抗性多武装土匪问题,并创建一个完全在线的算法框架,这种框架在任意翻译和武器损失的尺度下是无差别的。我们研究我们的算法对通用竞争等级的预期性能,这使它适用于各种各样的问题。我们的算法从普遍预测的角度和所使用的业绩计量是预期对任意选择武器序列的遗憾,即我们的损失和竞争性损失顺序之间的差别。竞争等级可以设计成包括固定的手臂选择、换换手、背景强盗或任何其他利益竞争。竞争等级的顺序一般由手头的具体应用程序决定,因此应当据此设计。我们的算法既不使用也不需要关于损失顺序的任何初步信息,而是完全在线的。其性能界限是平方损失总和的第二顺序,即损失的任何折叠式转换都不会对归正的遗憾产生影响。

0
下载
关闭预览

相关内容

专知会员服务
31+阅读 · 2021年7月15日
专知会员服务
91+阅读 · 2021年6月3日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
【课程】纽约大学 DS-GA 1003 Machine Learning
专知会员服务
45+阅读 · 2019年10月29日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Generative Adversarial Text to Image Synthesis论文解读
统计学习与视觉计算组
13+阅读 · 2017年6月9日
Arxiv
0+阅读 · 2021年11月5日
A Modern Introduction to Online Learning
Arxiv
20+阅读 · 2019年12月31日
Risk-Aware Active Inverse Reinforcement Learning
Arxiv
7+阅读 · 2019年1月8日
VIP会员
相关VIP内容
专知会员服务
31+阅读 · 2021年7月15日
专知会员服务
91+阅读 · 2021年6月3日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
【课程】纽约大学 DS-GA 1003 Machine Learning
专知会员服务
45+阅读 · 2019年10月29日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Generative Adversarial Text to Image Synthesis论文解读
统计学习与视觉计算组
13+阅读 · 2017年6月9日
Top
微信扫码咨询专知VIP会员