We consider the classical stochastic multi-armed bandit problem with a constraint that limits the total cost incurred by switching between actions to be no larger than a given switching budget. For this problem, we prove matching upper and lower bounds on the optimal (i.e., minimax) regret, and provide efficient rate-optimal algorithms. Surprisingly, the optimal regret of this problem exhibits a non-conventional growth rate in terms of the time horizon and the number of arms. Consequently, we discover surprising "phase transitions" regarding how the optimal regret rate changes with respect to the switching budget: when the number of arms is fixed, there are equal-length phases, where the optimal regret rate remains (almost) the same within each phase and exhibits abrupt changes between phases; when the number of arms grows with the time horizon, such abrupt changes become subtler and may disappear, but a generalized notion of phase transitions involving certain new measurements still exists. The results enable us to fully characterize the trade-off between the regret rate and the incurred switching cost in the stochastic multi-armed bandit problem, contributing new insights to this fundamental problem. Under the general switching cost structure, the results reveal interesting connections between bandit problems and graph traversal problems, such as the shortest Hamiltonian path problem.


翻译:我们认为古老的多武装匪盗问题具有制约性,限制了在行动之间转换的总成本,因此限制了在行动之间转换的总成本。 对于这一问题,我们证明在最佳(即迷你)遗憾上匹配上下界限,并提供了高效的速率最佳算法。令人惊讶的是,这一问题的最佳遗憾在时间范围和武器数量方面表现出非常规的增长率。因此,我们发现在转换预算方面的最佳遗憾率变化是如何发生的令人惊讶的“阶段过渡 ” : 当武器数量固定下来时,有同等长的阶段,每个阶段内的最佳遗憾率保持相同(几乎),并显示两个阶段之间的突变变化;当武器数量随着时间跨度的增长而变化时,这种突然的变化变得微妙,可能会消失,但涉及某些新计量的阶段过渡的普遍概念仍然存在。结果使我们能够充分说明在选择的遗憾率和多武装暴徒问题中发生的转折价,从而导致对这个基本阶段问题产生新的洞察力。在总体成本结构下,这种轮廓将揭示出这种根本性问题,作为最短的轮廓问题。

0
下载
关闭预览

相关内容

【TAMU】最新《时间序列分析》课程笔记,527页pdf
专知会员服务
179+阅读 · 2020年9月12日
【IJCAI2020】TransOMCS: 从语言图谱到常识图谱
专知会员服务
34+阅读 · 2020年5月4日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
TensorFlow神经网络教程
Python程序员
4+阅读 · 2017年12月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
VIP会员
相关VIP内容
【TAMU】最新《时间序列分析》课程笔记,527页pdf
专知会员服务
179+阅读 · 2020年9月12日
【IJCAI2020】TransOMCS: 从语言图谱到常识图谱
专知会员服务
34+阅读 · 2020年5月4日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
相关资讯
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
TensorFlow神经网络教程
Python程序员
4+阅读 · 2017年12月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员