Thompson 采样在逻辑回归老虎机问题中的表现
使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的 contestual bandits 设置。
Sep, 2012
在随机线性赌博机问题中,我们为 Thompson 采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关,并且选取与乐观参数相关的最优臂可以控制后悔,在具有固定概率为乐观的采样分布下来看,Thompson 采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。
Nov, 2016
该论文研究了贝叶斯后悔和汤普森抽样算法在赌博问题中的变体。它建立在信息论框架的基础上,通过率失真分析提供了关于线性赌博问题的后悔率上界。使用链接论证,我们针对度量动作空间的赌博问题建立了新的界限。在奖励的适当连续性假设下,我们的界限为 d 维线性赌博问题提供了紧凑的速率。
Mar, 2024
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
研究具有奖励分布先验分布的随机多臂赌博问题,证明 Thompson Sampling 算法在没有先验分布时具有最优的贝叶斯遗憾上界,并在 Bubeck 等人的先验设置下证明了算法的一致界限,并与 Audibert 和 Bubeck [2009] 和 Russo 和 Roy [2013] 的技术方法有关。
Apr, 2013
本文深入分析了 Thompson Sampling 算法中对先验分布选择的鲁棒性,发现在选择优先概率质量时,其遗憾上限与先验正判度呈 O (√T/p), 先验负判度呈 O (√(1-p) T), 并利用这些性质提出了一种基于鞅理论的新证明方法。
Jun, 2015
本篇论文研究了带有图反馈的多臂赌博问题,其中可以观察所选行动的相邻行动,在图可能随时间变化且不向决策者完全显露的情况下。该文提出了一种算法, 并证明了在无向图情况下它达到了最优(在对数因子内)失误收敛速率。同时,论文还提出了在有向图情况下该算法略微较弱的失误收敛速率, 并提出了一种改进算法,在有向情况下,达到了最优失误收敛速率(对数因子内)。这两种算法都能有效实现,且不需要在任何时候了解反馈图。
May, 2018
本研究证明了在多种环境设置下,Thompson 采样在强化学习中的贝叶斯后悔限与性能上界,通过使用一组离散的替代环境简化学习问题,并使用后验一致性对信息比例进行了精细分析,从而导出了时间不均匀强化学习问题中的上界,其中 $H$ 是回合长度,$d_{l_1}$ 是环境空间的 Kolmogorov $l_1$ 维度。接着,我们在各种设置中找到了 $d_{l_1}$ 的具体限制,并讨论了我们的结果是首次出现还是改进了现有技术。
Oct, 2023
考虑了具有复杂操作的随机多臂赌博问题,其中决策者在每轮中进行复杂操作而不仅仅是基本臂。复杂操作的奖励是基本臂奖励的某些函数,并且观察到的反馈可能不是每个臂的奖励。作者在一般情况下证明了一种频率后悔上限和 Thompson 抽样算法的 相容性,并应用于包括选择臂子集的一类复杂赌博问题中。
Nov, 2013