MOTS:极小极大化优化的汤普森采样
使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的 contestual bandits 设置。
Sep, 2012
本文提出了多次试验下的 Thompson sampling 方法(MP-TS)并对其进行了后效分析,证明了其具有与 Anantharam 等人提供的最佳后悔下界相匹配的最优后悔上界,并通过计算机模拟进行了验证。我们还提出了 MP-TS 的改进版本,并表明其具有更好的实际效果。
Jun, 2015
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
我们研究了基于 Thompson Sampling 的有界奖励随机赌博算法。为了解决现有的与高斯先验的 Thompson Sampling 相关的问题相关后悔界限在 T≤288e^64 时是虚无的问题,我们导出了一个更实用的界限,将主要项的系数从 288e^64 缩小到 1270。此外,我们提出了两种参数化的 Thompson Sampling 算法:带有模型聚合的 TS-MA-α 和带有时间战斗的 TS-TD-α,其中 α∈[0,1] 控制效用与计算之间的权衡。这两种算法都可以实现 O (Kln^(α+1)(T)/Δ) 的后悔界限,其中 K 是臂数量,T 是有限学习时段,Δ 表示拉动次优臂时的单轮性能损失。
May, 2024
本文将 Thompson sampling 算法扩展到预算限制的 MAB 中,通过从后验分布中采样两个数字并比较选择具有最大比值的手臂进行更新,证明此算法在伯努利臂或普通分布下的分布相关遗憾界都是在预算上对数复杂度,通过我们的仿真实验验证了该算法的有效性。
May, 2015
研究了在半盲反馈条件下,组合多臂赌博问题中,具有概率触发武器的组合汤普森抽样的遗憾,并在基准武器预期的连续 Lipschitz 情况下得出了 CTS 的遗憾界。
Sep, 2018
本文针对伯努利回报情况,首次提供匹配 Lai 和 Robbins 下限所给累积遗憾率的有限时间分析,证明了 Thompson Sampling 是解决随机多臂老虎机问题的最优策略,并通过数值比较和实验验证了这一结论。
May, 2012
研究了多智能体多抽臂赌博机问题,针对联动臂的回报进行了探索,提出了一种高效的变体算法 epsilon-MATS,并证明了其在频率意义下的遗憾上界是次线性的,同时通过实验验证了其在相同情景下相比现有算法的卓越性能和改进的计算效率。
Dec, 2023
本文研究了一种序贯子集选择问题,并提出了一种基于 Thompson Sampling 算法的适用于多项式逻辑模型选择模型的求解方法,能够在绝大多数情况下获得接近最优水平的收益,并在数字实验中取得有趣的实验结果。
Jun, 2017