Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Julian Zimmert;Haipeng Luo;Chen-Yu Wei
中科院分区：
文献类型：
--
作者：
Julian Zimmert;Haipeng Luo;Chen-Yu Wei
我们开发了第一个同时实现$ \ Mathcal {o}（\ log t）$遗憾的$ \ mathcal {o}的通用半频算算法，以及$ \ mathcal {o}（\ sqrt {t}）$遗憾政权或回合$ t $的数量。我们边界的领先问题依赖性常数不仅在以前研究的一些最坏情况下是最佳的，而且对于两个半伴随问题的两个具体实例也是最佳的。我们的算法和分析扩展了（Zimmert＆Seldin，2019年）的最新工作，用于多武器匪徒的特殊情况，但重要的是需要专门为半搭接设计的新型混合规则剂。合成数据的实验结果表明，我们的算法确实在不同的环境中表现出色。最终，我们将结果的初步扩展为全面的强盗反馈。
We develop the first general semi-bandit algorithm that simultaneously achieves $\mathcal{O}(\log T)$ regret for stochastic environments and $\mathcal{O}(\sqrt{T})$ regret for adversarial environments without knowledge of the regime or the number of rounds $T$. The leading problem-dependent constants of our bounds are not only optimal in some worst-case sense studied previously, but also optimal for two concrete instances of semi-bandit problems. Our algorithm and analysis extend the recent work of (Zimmert & Seldin, 2019) for the special case of multi-armed bandit, but importantly requires a novel hybrid regularizer designed specifically for semi-bandit. Experimental results on synthetic data show that our algorithm indeed performs well uniformly over different environments. We finally provide a preliminary extension of our results to the full bandit feedback.