非周期性不安定赌博机中的汤普森抽样
本文从学习的角度分析了未知参数情况下的时序不息不静赌博机问题,在采用泰普斯抽样的情况下考虑了一个通用策略映射作为竞争者,证明了贝叶斯遗憾的 k 倍增长上限。本文的竞争对手足够灵活,可以表示各种基准,包括最佳固定操作策略,最优策略,惠特尔指数策略或近视策略。同时,还提供了支持理论发现的实证结果。
May, 2019
我们研究了基于 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 在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的 contestual bandits 设置。
Sep, 2012
本文提出了一种新的算法 Discounted Thompson Sampling (DS-TS) with Gaussian priors,用于解决非平稳多臂赌博机问题,并分析了算法在不同情况下的表现和 upper bound of regret。
May, 2023
在随机线性赌博机问题中,我们为 Thompson 采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关,并且选取与乐观参数相关的最优臂可以控制后悔,在具有固定概率为乐观的采样分布下来看,Thompson 采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。
Nov, 2016
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
本文介绍了一种基于深度神经网络和贝叶斯推断的新型算法 —— 神经 Thompson Sampling (Neural Thompson Sampling),并证明该算法的性能能够和同类算法相匹配,实验结果证实了该理论。
Oct, 2020
本文提出了多次试验下的 Thompson sampling 方法(MP-TS)并对其进行了后效分析,证明了其具有与 Anantharam 等人提供的最佳后悔下界相匹配的最优后悔上界,并通过计算机模拟进行了验证。我们还提出了 MP-TS 的改进版本,并表明其具有更好的实际效果。
Jun, 2015
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