Linear bandits with limited adaptivity and learning distributional optimal design
Linear bandits with limited adaptivity and learning distributional optimal design
复制标题
具有有限适应性和学习分布优化设计的线性老虎机
DOI：
10.1145/3406325.3451004
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zhou, Yuan
中科院分区：
文献类型：
--
作者：
Ruan, Yufei;Yang, Jiaqi;Zhou, Yuan
出于实际需要，如大规模的学习，我们研究的影响，适应性约束的线性上下文土匪，在线学习和决策的中心问题。我们考虑两个流行的有限适应性模型在文献中：批量学习和罕见的政策开关。我们表明，当上下文向量是逆向选择的一维线性上下文强盗，学习者需要O（dlogdlogT）的政策开关，以实现最小最大最优的遗憾，这是最佳的topoly（logd，loglogT）的因素;随机上下文向量，即使在更严格的批量学习模型，只有O（loglogT）批次需要实现最优的遗憾。结合文献中已有的结果，我们的研究结果给出了线性语境强盗中适应性约束的完整描述。沿着的方式，我们提出了分布最优设计，最优实验设计的自然延伸，并提供了一个统计和计算效率的学习算法的问题，这可能是独立的利益。
Motivated by practical needs such as large-scale learning, we study the impact of adaptivity constraints to linear contextual bandits, a central problem in online learning and decision making. We consider two popular limited adaptivity models in literature: batch learning and rare policy switches. We show that, when the context vectors are adversarially chosen ind-dimensional linear contextual bandits, the learner needsO(dlogdlogT) policy switches to achieve the minimax-optimal regret, and this is optimal up topoly(logd, loglogT) factors; for stochastic context vectors, even in the more restricted batch learning model, onlyO(loglogT) batches are needed to achieve the optimal regret. Together with the known results in literature, our results present a complete picture about the adaptivity constraints in linear contextual bandits. Along the way, we propose the distributional optimal design, a natural extension of the optimal experiment design, and provide a both statistically and computationally efficient learning algorithm for the problem, which may be of independent interest.
登录
查看更多内容
关于测量约束回归模型中实验的计算可处理选择
影响因子：
6
作者：
Yining Wang;Adams Wei Yu;Aarti Singh
通讯作者：
Aarti Singh
通过批量手臂拉动进行多臂强盗中的上臂识别
DOI：
--
发表时间：
2016
期刊：
International Conference on Artificial Intelligence and Statistics
影响因子：
--
作者：
Kwang;Kevin G. Jamieson;R. Nowak;Xiaojin Zhu
通讯作者：
Xiaojin Zhu
D 最优设计的近似正相关分布和近似算法
DOI：
--
发表时间：
2018
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Mohit Singh;Weijun Xie
通讯作者：
Weijun Xie
具有切换约束的 Bandits 中的相变
DOI：
--
发表时间：
2019
期刊：
Neural Information Processing Systems
影响因子：
--
作者：
D. Simchi;Yunzong Xu
通讯作者：
Yunzong Xu
并发 PAC 强化学习
DOI：
--
发表时间：
2015
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Z. Guo;E. Brunskill
通讯作者：
E. Brunskill