双掷硬币汤普森抽样在对决式多臂老虎机算法中的应用
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索/开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
提出了减少德杰斯特拉竞标者问题(Dueling Bandits)到传统(随机)多臂赌博机问题(Multi-Armed Bandits)的算法,我们的算法有着广泛的应用性以及在有限和无限的情况下证明了较优的回报上限。
May, 2014
本文提出了多次试验下的Thompson sampling方法(MP-TS)并对其进行了后效分析,证明了其具有与Anantharam等人提供的最佳后悔下界相匹配的最优后悔上界,并通过计算机模拟进行了验证。我们还提出了MP-TS的改进版本,并表明其具有更好的实际效果。
Jun, 2015
本文研究了K-armed dueling bandit问题,提出了一种受Deterministic Minimum Empirical Divergence算法启发的算法,并得到了匹配下界的后悔上界,实验结果表明该算法明显优于现有算法。
Jun, 2015
研究了K-armed dueling bandit问题,提出了CW-RMED和ECW-RMED算法来解决Copeland winners的推荐问题,并通过实验比较证明ECW-RMED算法的有效性优于现有算法。
May, 2016
本文研究具有相关性的多股臂的多对打算法,在推荐系统等领域可以更高效地学习和优化用户的基于偏好的关键特征,使用自对抗算法,结合高斯过程统计方法可以更准确地捕捉相关性,提升算法的效果。
Apr, 2017
通过研究三向反馈的对决问题,我们确定了一个学习算法的样本复杂度下限,提出了POCOWISTA算法,并证明了在特定条件下偏好概率的情况下,我们可以得到一个改进的样本复杂度。
Oct, 2023
我们研究了基于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