OSOM: A Simultaneously Optimal Algorithm for Multi-Armed and Linear Contextual Bandits
OSOM: A Simultaneously Optimal Algorithm for Multi-Armed and Linear Contextual Bandits
复制标题
OSOM：多臂和线性上下文强盗的同时最优算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Bartlett
中科院分区：
文献类型：
--
作者：
Niladri S. Chatterji;Vidya Muthukumar;P. Bartlett
考虑了随机线性（多臂）上下文强盗问题， extit{simple multi-armed bandit}结构，其中奖励独立于上下文信息。已知仅针对其中一个机制设计的算法对于其替代机制是次优的。我们设计了一个计算效率高的算法，同时获得问题相关的最优后悔率在简单的多臂土匪政权和最小最优后悔率在线性上下文土匪政权，而不知道先验的两个模型产生的奖励。在上下文信息多轮随机性的条件下证明了这些结果。我们的研究结果应被视为一个步骤，对有原则的数据依赖的政策类选择上下文土匪。
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden extit{simple multi-armed bandit} structure in which the rewards are independent of the contextual information. Algorithms that are designed solely for one of the regimes are known to be sub-optimal for their alternate regime. We design a single computationally efficient algorithm that simultaneously obtains problem-dependent optimal regret rates in the simple multi-armed bandit regime and minimax optimal regret rates in the linear contextual bandit regime, without knowing a priori which of the two models generates the rewards. These results are proved under the condition of stochasticity of contextual information over multiple rounds. Our results should be viewed as a step towards principled data-dependent policy class selection for contextual bandits.