非平稳环境下的滑动窗口汤普森采样
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索/开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
针对非平稳环境下的多臂赌博问题,提出了一种基于贝叶斯方法的 Thompson Sampling 变体,对其进行了系统性降低先前观测效果的描述,通过增加贝叶斯采样的功利值提供了最优化算法的乐观版本,并进行了广泛的实证分析和与各种算法的比较研究。
Jul, 2017
本文从学习的角度分析了未知参数情况下的时序不息不静赌博机问题,在采用泰普斯抽样的情况下考虑了一个通用策略映射作为竞争者,证明了贝叶斯遗憾的k倍增长上限。本文的竞争对手足够灵活,可以表示各种基准,包括最佳固定操作策略,最优策略,惠特尔指数策略或近视策略。同时,还提供了支持理论发现的实证结果。
May, 2019
本文研究了在未知奖励分布下使用Thompson采样算法来解决不断变化的赌博机问题,证明了一种子线性的,O(sqrt(T)log T)的遗憾上限,并将算法测试在了一个动态信道接入问题的模拟中,实证结果与理论上限一致。
Oct, 2019
本文提出了一种新的算法 Discounted Thompson Sampling (DS-TS) with Gaussian priors,用于解决非平稳多臂赌博机问题,并分析了算法在不同情况下的表现和 upper bound of regret。
May, 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
我们通过建立一个马尔可夫决策过程模型,研究一种名为汤普森采样的采样算法的渐近行为。我们展示了标准(期望)遗憾可能呈超线性增长,并且不能很好地捕捉到在具有非平凡状态演进的现实情况下的学习概念。通过分解标准(期望)遗憾,我们提出了一种新的指标,称为期望剩余遗憾,它忽略了过去动作的不可变后果,而是测量了当前时期后的最优奖励的遗憾。我们表明,汤普森采样算法的期望剩余遗憾上界由一个指数级快速收敛于0的项给定。我们给出了汤普森采样的后验采样误差收敛于0的条件,并且引入了期望剩余遗憾的概率版本并给出了其收敛于0的条件。因此,我们提供了一个适用于采样算法的学习概念,在比以前考虑的更广泛的情况下将非常有用。
May, 2024
本研究针对传统算法在动态环境中失效的问题,提出了两种基于汤普森采样的新算法:BETA-SWTS和$\gamma$-SWGTS,以适应非平稳设定的复杂性。通过推导一般化的遗憾公式,我们提供了对不同奖励环境下算法误差的深入分析,强调了此研究在处理突变和平滑变化环境中的潜在影响。
Sep, 2024