Improved Path-length Regret Bounds for Bandits
Improved Path-length Regret Bounds for Bandits
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Sébastien Bubeck;Yuanzhi Li;Haipeng Luo;Chen-Yu Wei
中科院分区：
文献类型：
--
作者：
Sébastien Bubeck;Yuanzhi Li;Haipeng Luo;Chen-Yu Wei
我们研究了多臂匪徒和更普遍的线性匪徒的损失变化（所谓的路径长度界限）的自适应后悔界限。我们首先表明（Wei和Luo，2018年）看似次优的路径长度界面对于自适应对手来说是不可改进的。尽管取得了负面的结果，但我们随后开发了两种新算法，一种严格改善（Wei and Luo，2018），其路径长度较小，而另一种则改进了（Wei和Luo，2018），以供无知的对手路径长度很大。我们的算法基于研究精心的乐观镜下降框架，但重要的是使用几种新型技术，包括新的乐观预测，对最近选择的手臂有轻微的偏见以及使用类似于（Bubeck等人）的混合正规剂。 ，2018）。此外，我们通过显示出对全信息问题的动态遗憾的减少来将结果扩展到线性匪徒，然后进一步减少凸出身体追逐。我们提出了一种简单的贪婪追逐算法，以实现平方的2核，从而导致了新的动态遗憾结果，并因此也是通用线性匪徒的第一个长度遗憾。
We study adaptive regret bounds in terms of the variation of the losses (the so-called path-length bounds) for both multi-armed bandit and more generally linear bandit. We first show that the seemingly suboptimal path-length bound of (Wei and Luo, 2018) is in fact not improvable for adaptive adversary. Despite this negative result, we then develop two new algorithms, one that strictly improves over (Wei and Luo, 2018) with a smaller path-length measure, and the other which improves over (Wei and Luo, 2018) for oblivious adversary when the path-length is large. Our algorithms are based on the well-studied optimistic mirror descent framework, but importantly with several novel techniques, including new optimistic predictions, a slight bias towards recently selected arms, and the use of a hybrid regularizer similar to that of (Bubeck et al., 2018). Furthermore, we extend our results to linear bandit by showing a reduction to obtaining dynamic regret for a full-information problem, followed by a further reduction to convex body chasing. We propose a simple greedy chasing algorithm for squared 2-norm, leading to new dynamic regret results and as a consequence the first path-length regret for general linear bandit as well.