线性汤普森抽样再探
本文针对线性随机赌博机问题提出一种基于线性 Thompson 抽样的新型安全算法,通过引入线性安全约束,在与没有安全约束的情况下,展示了使得机器人有更好的性能表现的结果,并将其与基于 UCB 算法的安全算法进行了比较。
Nov, 2019
使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的 contestual bandits 设置。
Sep, 2012
本研究对 Logistic Bandit 问题进行了研究,确立了 Thompson sampling 算法的鲁棒性,提出了新的度量指标 —— 脆弱性维度,并使用该指标证明了现有算法的上限。
May, 2019
本文研究了在未知奖励分布下使用 Thompson 采样算法来解决不断变化的赌博机问题,证明了一种子线性的,O (sqrt (T) log T) 的遗憾上限,并将算法测试在了一个动态信道接入问题的模拟中,实证结果与理论上限一致。
Oct, 2019
本文提出一种名为 DR Thompson Sampling 的多臂上下文赌博算法,并利用缺失数据文献中使用的双重稳健估计器提供先验概率在最坏情况下的保证率和次均方误差,具体表现为对因变量和全部或几个自变量进行回归的误差。他们发现该方法在实践中的表现优于 LinTS。
Feb, 2021
该论文研究了贝叶斯后悔和汤普森抽样算法在赌博问题中的变体。它建立在信息论框架的基础上,通过率失真分析提供了关于线性赌博问题的后悔率上界。使用链接论证,我们针对度量动作空间的赌博问题建立了新的界限。在奖励的适当连续性假设下,我们的界限为 d 维线性赌博问题提供了紧凑的速率。
Mar, 2024
Thompson sampling (TS) is a popular algorithm for solving multi-armed bandit problems; this paper introduces a variant called $\alpha$-TS with tempered likelihoods in the posterior distribution, and provides regret bounds for both instance-dependent and instance-independent scenarios.
Sep, 2023
本研究证明了在多种环境设置下,Thompson 采样在强化学习中的贝叶斯后悔限与性能上界,通过使用一组离散的替代环境简化学习问题,并使用后验一致性对信息比例进行了精细分析,从而导出了时间不均匀强化学习问题中的上界,其中 $H$ 是回合长度,$d_{l_1}$ 是环境空间的 Kolmogorov $l_1$ 维度。接着,我们在各种设置中找到了 $d_{l_1}$ 的具体限制,并讨论了我们的结果是首次出现还是改进了现有技术。
Oct, 2023
本文设计和分析了一种基于贝叶斯思想的 Thompson Sampling 算法泛化版本,用于解决带有线性收益函数的随机上下文多臂老虎机问题,同时提供了该算法的第一理论保证,得到了最佳遗憾保证。
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