The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
复制标题
乐观主义的终结？
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Csaba Szepesvari
中科院分区：
文献类型：
--
作者：
Tor Lattimore;Csaba Szepesvari
随机线性老虎机是有限臂老虎机的自然而简单的推广，具有许多实际应用。当前的方法侧重于推广有限武装老虎机的现有技术，特别是乐观原则和汤普森采样。虽然之前的工作大多是在最坏的情况下进行的，但我们分析了渐进的依赖于实例的后悔，并显示了可实现的匹配的上限和下限。令人惊讶的是，我们的结果表明，没有一种基于乐观或汤普森采样的算法能够达到最佳速率，而且实际上，即使在非常简单的情况下，也可能与最佳速率相距甚远。这是一个令人不安的结果，因为这些技术是广泛用于顺序优化的标准工具。例如，对于广义线性老虎机和强化学习。
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case setting, we analyse the asymptotic instance-dependent regret and show matching upper and lower bounds on what is achievable. Surprisingly, our results show that no algorithm based on optimism or Thompson sampling will ever achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even in very simple cases. This is a disturbing result because these techniques are standard tools that are widely used for sequential optimisation. For example, for generalised linear bandits and reinforcement learning.