带虚拟协助代理的汤普森抽样
该论文介绍了 Thompson 采样算法在处理在线决策问题,尤其是在平衡当前性能和收集信息提高未来性能之间的探索与利用上的应用。该算法适用于各种问题并具有高效的计算能力,具体例子包括伯努利老虎机问题,最短路径问题,推荐系统,主动学习等。此外,本文还讨论了 Thompson 采样算法何时有效、何时无效以及与其他算法的关系。
Jul, 2017
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
基于观测数据的贝叶斯泰普森抽样策略成功地平衡了探索和利用,通过引入新的鞅技术和浓厚不等式解决了部分观测相关随机变量的问题,为研究其他具有上下文信息和部分观测的决策问题铺平了道路。
Feb, 2024
本文提出一种名为广义 Thompson Sampling 的新算法,将其作为专家学习框架下的一种启发式算法,其包括 Thompson Sampling 作为其特殊情况,并派生了一般性遗憾界,将其应用到广泛的情境性算法中,量化 “先验” 分布对遗憾界的影响。
Oct, 2013
本文将 Thompson sampling 算法扩展到预算限制的 MAB 中,通过从后验分布中采样两个数字并比较选择具有最大比值的手臂进行更新,证明此算法在伯努利臂或普通分布下的分布相关遗憾界都是在预算上对数复杂度,通过我们的仿真实验验证了该算法的有效性。
May, 2015
本文采用一种简单的后验抽样算法来平衡探索和利用学习优化操作,称为 Thompson Sampling,理论上提出了后验抽样与 UCB 算法的联系,并提供了一个广泛适用且可以专门针对许多模型类进行特化的后验抽样贝叶斯遗憾界。
Jan, 2013
本文设计和分析了一种基于贝叶斯思想的 Thompson Sampling 算法泛化版本,用于解决带有线性收益函数的随机上下文多臂老虎机问题,同时提供了该算法的第一理论保证,得到了最佳遗憾保证。
Sep, 2012
本文介绍了一种基于深度神经网络和贝叶斯推断的新型算法 —— 神经 Thompson Sampling (Neural Thompson Sampling),并证明该算法的性能能够和同类算法相匹配,实验结果证实了该理论。
Oct, 2020
使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的 contestual bandits 设置。
Sep, 2012
我们研究了基于 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