Phase Transitions in Bandits with Switching Constraints
Phase Transitions in Bandits with Switching Constraints
复制标题
具有切换约束的 Bandits 中的相变
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yunzong Xu
中科院分区：
文献类型：
--
作者：
D. Simchi;Yunzong Xu
我们考虑了经典的随机多臂强盗问题的约束的总成本之间的切换行动。我们证明了匹配的上限和下限遗憾，并提供了近最优算法解决这个问题。令人惊讶的是，我们发现相变和循环现象的最佳遗憾。也就是说，我们表明，与多臂强盗问题，有阶段定义的武器和开关成本，在每个阶段的遗憾的上限和下限保持不变，并显着下降阶段之间的数量。研究结果使我们能够充分刻画在随机多臂强盗问题中后悔和转换成本之间的权衡，为这一基本问题提供了新的见解。在一般的转换成本结构下，结果揭示了强盗问题和图遍历问题之间的深层联系，如最短哈密尔顿路径问题。
We consider the classical stochastic multi-armed bandit problem with a constraint on the total cost incurred by switching between actions. We prove matching upper and lower bounds on regret and provide near-optimal algorithms for this problem. Surprisingly, we discover phase transitions and cyclic phenomena of the optimal regret. That is, we show that associated with the multi-armed bandit problem, there are phases defined by the number of arms and switching costs, where the regret upper and lower bounds in each phase remain the same and drop significantly between phases. The results enable us to fully characterize the trade-off between regret and 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 a deep connection between bandit problems and graph traversal problems, such as the shortest Hamiltonian path problem.