Thompson采样的先验敏感性

Jun, 2015

On the Prior Sensitivity of Thompson Sampling

Che-Yu Liu, Lihong Li

TL;DR本文深入分析了Thompson Sampling算法中对先验分布选择的鲁棒性, 发现在选择优先概率质量时, 其遗憾上限与先验正判度呈O(√T/p), 先验负判度呈O(√(1-p)T), 并利用这些性质提出了一种基于鞅理论的新证明方法。

Abstract

The empirically successful thompson sampling algorithm for stochastic bandits has drawn much interest in understanding its theoretical properties. One important benefit of the algorithm is that it allows domain k

发现论文，激发创造

基于线性回报的情境型贝叶斯-汤普森抽样算法

本文设计和分析了一种基于贝叶斯思想的Thompson Sampling算法泛化版本，用于解决带有线性收益函数的随机上下文多臂老虎机问题，同时提供了该算法的第一理论保证，得到了最佳遗憾保证。

Sep, 2012

进一步优化 Thompson Sampling 算法的后悔上界

使用贝叶斯方法的随机算法Thompson Sampling在多臂赌博问题中表现显著，本文提供了一种新的悔恨分析方法，同时证明了该算法在期望后悔上的问题特定界限和问题独立界限，方法简单且可适用于更广泛的contestual bandits设置。

Sep, 2012

Thompson抽样的无先验和有先验依赖的遗憾界

研究具有奖励分布先验分布的随机多臂赌博问题，证明Thompson Sampling算法在没有先验分布时具有最优的贝叶斯遗憾上界，并在Bubeck等人的先验设置下证明了算法的一致界限，并与Audibert和Bubeck [2009]和Russo和Roy [2013]的技术方法有关。

Apr, 2013

线性汤普森抽样再探

在随机线性赌博机问题中，我们为Thompson采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关，并且选取与乐观参数相关的最优臂可以控制后悔，在具有固定概率为乐观的采样分布下来看，Thompson采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。

Nov, 2016

时间敏感型贝叶斯优化多臂赌博机学习

该文研究了在具有时间偏好的情况下的强化学习中，使用折扣累计损失代替累计损失，使用改进的 Thompson 抽样算法得到较强的解决方案。

Apr, 2017

Thompson采样在逻辑回归老虎机问题中的表现

本研究对Logistic Bandit问题进行了研究，确立了Thompson sampling算法的鲁棒性，提出了新的度量指标——脆弱性维度，并使用该指标证明了现有算法的上限。

May, 2019

Bandits问题中学习先验知识无悔

提出 AdaTS，一种适用于与其交互的赌博任务的 Thompson 抽样算法，该算法通过在参数上维护分布来适应未知任务先验分布，并在解决赌博任务时对不确定性进行较为准确的处理。AdaTS 是一种全贝叶斯算法，适用于多种赌博问题的高效实现，其 Bayes 遗憾的上界可以量化由于不知道任务先验而产生的损失，实验证明 AdaTS 在挑战性的实际应用问题中表现出色，优于之前的算法。

Jul, 2021

具有正态伽马先验的线性赌博机问题的汤普森取样算法

本文介绍了在正态分布奖励模型下使用贝叶斯推断方法的 Thompson 抽样算法在多臂赌博问题中的应用，通过使用多元正态分布-伽玛先验来表示所有相关参数的环境不确定性，并得出了关于 Thompson 抽样算法的贝叶斯遗憾界，其前提条件为方差分布的 5/2 阶矩存在。

Mar, 2023

基于信息论的噪声上下文随机赌博机的汤普森抽样算法的遗憾分析

我们研究了一种随机情境线性赌博机问题，代理人通过一个未知噪声参数的噪声信道观察到真实情境的有噪声、损坏的版本。我们的目标是设计一种行动策略，可以近似一个能够获取奖励模型、信道参数以及根据观察到的有噪声情境从真实情境得到预测分布的神谕的行动策略。我们在贝叶斯框架下引入了一种基于高斯情境噪声的汤普森采样算法。采用信息论分析，对于神谕的行动策略，我们证明了该算法的贝叶斯遗憾。我们还将这个问题扩展到当代理人在接收到奖励之后，以一定延迟观察到真实情境的情景，并展示了延迟真实情境会导致更低的贝叶斯遗憾。最后，我们通过与基准算法进行实证研究，展示了所提出算法的性能。

Jan, 2024

智能和适应后验采样算法用于二元选择

我们研究了基于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