Oct, 2016
乐观主义的终结?有限臂线性赌博机的渐近分析
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Tor Lattimore, Csaba Szepesvari
TL;DR这篇研究分析了随机线性赌博机在实例依赖性遗憾方面的异步情况,并得出了最优性的上下界匹配结果,表明基于乐观主义或汤普森抽样的算法将永远无法达到最优速度,甚至在非常简单的情况下也可能与最优解相差无几。
Abstract
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
→
stochastic linear banditsoptimism principlethompson samplinginstance-dependent regretasymptotic analysis
发现论文,激发创造
汤普森抽样:渐进最优的有限时间分析
本文针对伯努利回报情况,首次提供匹配 Lai 和 Robbins 下限所给累积遗憾率的有限时间分析,证明了 Thompson Sampling 是解决随机多臂老虎机问题的最优策略,并通过数值比较和实验验证了这一结论。
May, 2012
带线性约束的随机赌博机
本文研究了一个约束的上下文线性赌博机问题,提出了一种算法 OPLB 并证明了其 T 轮后悔度的上限,针对多臂赌博机情况提出了高效算法,同时给出了问题的下限和模拟结果。
Jun, 2020
安全线性随机赌博机
本文介绍了一个安全的线性随机挑战模型,其中学习器在每一阶段都需要选择一个预期奖励不小于预先确定的(安全)阈值的臂,以高概率。我们假设学习器最初掌握的是一个已知为安全但不一定最优的臂的知识。基于此假设,介绍了一种学习算法,它将已知的安全臂与探索性臂系统地结合起来,以便随时间安全地扩展安全臂集,同时促进后续阶段的安全贪婪利用。除了确保在每个播放阶段满足安全约束之外,所提出的算法还表现出一种预期的遗憾,在播放 T 个阶段后不超过 O(sqrt(T)log(T))
Nov, 2019
有限臂结构赌博机的有界遗憾
研究了一种新型的 K 武装强盗问题,介绍了一种针对这一问题的新算法,并展示了在特定条件下可以实现有限的预期累计遗憾,同时提供了依赖于问题的累计遗憾下限,显示出至少在某些特殊情况下,新算法是近乎最优的。
Nov, 2014
线性上下文臂优化中的自适应探索
我们设计了一种渐近上限最优算法,并充分利用线性结构和精确探索,从而减少了在多种合理情境下的失算,数值结果表明,与其他基准算法相比,我们的方法大大减少了失算。
Oct, 2019