Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds
Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds
复制标题
具有变化的动作集的对抗性在线学习：具有近似遗憾界限的高效算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
D. Kempe
中科院分区：
文献类型：
--
作者：
E. Emamjomeh;Chen;Haipeng Luo;D. Kempe
我们重温了有睡眠专家/团伙的在线学习问题：在每个时间步中，只有一个行动子集可供算法选择（和学习）。Kleinberg 等人[2010]的研究表明，存在一种无遗憾算法，其渐近表现不会比最佳行动排序差。遗憾的是，实现这种无遗憾约束在计算上似乎很难：Kanade 和 Steinke [2014] 的研究表明，实现这种无遗憾性能至少与 PAC 学习 DNF 一样困难，而 DNF 是一个臭名昭著的难题。在本研究中，我们放宽了原始问题，并研究了计算高效的无近似遗憾算法：除了加法遗憾之外，这种算法还可能以乘法常数超出最优成本。我们给出了一种算法，它能为一般的睡眠专家/bandit 问题提供无近似遗憾保证。对于该问题的几种典型特例，我们给出了近似率明显更高的算法；这些算法还说明了实现无近似遗憾保证的不同技术。
We revisit the problem of online learning with sleeping experts/bandits: in each time step, only a subset of the actions are available for the algorithm to choose from (and learn about). The work of Kleinberg et al. [2010] showed that there exist no-regret algorithms which perform no worse than the best ranking of actions asymptotically. Unfortunately, achieving this regret bound appears computationally hard: Kanade and Steinke [2014] showed that achieving this no-regret performance is at least as hard as PAC-learning DNFs, a notoriously difficult problem. In the present work, we relax the original problem and study computationally efficient no-approximate-regret algorithms: such algorithms may exceed the optimal cost by a multiplicative constant in addition to the additive regret. We give an algorithm that provides a no-approximate-regret guarantee for the general sleeping expert/bandit problems. For several canonical special cases of the problem, we give algorithms with significantly better approximation ratios; these algorithms also illustrate different techniques for achieving no-approximate-regret guarantees.