Fooling Algorithms in Non-Stationary Bandits using Belief Inertia
Gal Mendelson, Eyal Tadmor
我们研究在零碎的固定式多武装匪徒中最糟糕的情况后悔的问题。 虽然固定匪徒的minimax理论已经确立,但在时间变化的设置中理解类似的限制是具有挑战性的。 现有的下限依赖于我们所说的不常见的抽样参数,在没有探索的情况下,长时间的间隔允许对抗性奖励变化,从而引起巨大的遗憾。 在本文中,我们引入了一种基于信念惯性论证的完全不同的方法。 我们的分析捕获了算法的经验信念,通过历史奖励平均值编码,创造了在变化后抵抗新证据的动力。 我们展示了如何利用这种惯性来构建误导经典算法的对抗性实例,如Explore Then Commit,epsilon greedy和UCB,导致他们遭受与T线性增长的遗憾,并且具有实质性的恒定因子,无论它们的参数如何调整,即使只有一个变化点。 我们将分析扩展到定期重新启动以处理非静止性的算法,并证明即使在那时,最糟糕的情况后悔仍然是T中的线性。 我们的结果表明,利用信念惯性可以在非静止土匪中推导出尖锐的下界。
We study the problem of worst case regret in piecewise stationary multi armed bandits. While the minimax theory for stationary bandits is well established, understanding analogous limits in time-varying settings is challenging. Existing lower bounds rely on what we refer to as infrequent sampling arguments, where long intervals without exploration allow adversarial reward changes that induce large regret. In this paper, we introduce a fundamentally different approach based on a belief inertia ar...
