Minimax Optimal Algorithms for Adversarial Bandit Problem With Multiple Plays
Minimax Optimal Algorithms for Adversarial Bandit Problem With Multiple Plays
复制标题
多次游戏对抗性强盗问题的最小最大最优算法
DOI：
10.1109/tsp.2019.2928952
复制
发表时间：
2019
影响因子：
5.4
通讯作者：
S. Kozat
中科院分区：
文献类型：
--
作者：
Nuri Mert Vural;Hakan Gokcesu;Kaan Gokcesu;S. Kozat
研究了半强盗反馈下的多对策对抗强盗问题。我们引入了一个高效的算法，渐近实现最佳的开关<inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula>-手臂策略的性能与最小最大最优遗憾界。为了构造我们的算法，我们引入了一个新的专家意见算法的多播放设置。通过使用我们的专家建议算法，我们还提高了<inline-formula><tex-math notation="LaTeX">$O（\sqrt{m}）$</tex-math></inline-formula>的多播放设置的最知名的高概率界。我们的结果是保证持有在一个单独的序列方式，因为我们没有统计假设的强盗臂增益。通过一组广泛的实验，涉及合成和真实的数据，我们证明了显着的性能增益所提出的算法相对于国家的最先进的算法。
We investigate the adversarial bandit problem with multiple plays under semi-bandit feedback. We introduce a highly efficient algorithm that asymptotically achieves the performance of the best switching <inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula>-arm strategy with minimax optimal regret bounds. To construct our algorithm, we introduce a new expert advice algorithm for the multiple-play setting. By using our expert advice algorithm, we additionally improve the best-known high-probability bound for the multi-play setting by <inline-formula><tex-math notation="LaTeX">$O(\sqrt{m})$</tex-math></inline-formula>. Our results are guaranteed to hold in an individual sequence manner since we have no statistical assumption on the bandit arm gains. Through an extensive set of experiments involving synthetic and real data, we demonstrate significant performance gains achieved by the proposed algorithm with respect to the state-of-the-art algorithms.