Thompson 采样的先验敏感性
研究具有奖励分布先验分布的随机多臂赌博问题,证明 Thompson Sampling 算法在没有先验分布时具有最优的贝叶斯遗憾上界,并在 Bubeck 等人的先验设置下证明了算法的一致界限,并与 Audibert 和 Bubeck [2009] 和 Russo 和 Roy [2013] 的技术方法有关。
Apr, 2013
使用贝叶斯方法的随机算法 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
探讨多参数模型中 normal distribution 模型下 Thompson sampling 算法的优化问题及其 prior 选择的影响
Nov, 2013
本研究对 Logistic Bandit 问题进行了研究,确立了 Thompson sampling 算法的鲁棒性,提出了新的度量指标 —— 脆弱性维度,并使用该指标证明了现有算法的上限。
May, 2019
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
该文章重新考虑了 Thompson Sampling 算法在来自对称 α- 稳定分布的奖励下的应用,提出了一个有效的后验推断框架,证明了两种算法的有限时间遗憾界,并通过一系列的实验展示了 Thompson Sampling 在此环境中更强的性能。
Jul, 2019
在随机线性赌博机问题中,我们为 Thompson 采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关,并且选取与乐观参数相关的最优臂可以控制后悔,在具有固定概率为乐观的采样分布下来看,Thompson 采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。
Nov, 2016
本文提出了一种新的模型无关后验采样的公式,适用于更广泛的周期性强化学习问题,并通过新颖的证明技术,展示了在适当条件下,我们的后验采样方法的最坏后果可以与基于优化的方法的最优结果相匹配,尤其是在线性 MDP 设置中,我们的算法产生的遗憾与现有基于后验采样的探索算法相比,随着维度线性增长而非二次依赖。
Aug, 2022
本文提出一种名为广义 Thompson Sampling 的新算法,将其作为专家学习框架下的一种启发式算法,其包括 Thompson Sampling 作为其特殊情况,并派生了一般性遗憾界,将其应用到广泛的情境性算法中,量化 “先验” 分布对遗憾界的影响。
Oct, 2013