带附加信息的安全线性汤普森抽样
在随机线性赌博机问题中,我们为 Thompson 采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关,并且选取与乐观参数相关的最优臂可以控制后悔,在具有固定概率为乐观的采样分布下来看,Thompson 采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。
Nov, 2016
本文介绍了一个安全的线性随机挑战模型,其中学习器在每一阶段都需要选择一个预期奖励不小于预先确定的(安全)阈值的臂,以高概率。我们假设学习器最初掌握的是一个已知为安全但不一定最优的臂的知识。基于此假设,介绍了一种学习算法,它将已知的安全臂与探索性臂系统地结合起来,以便随时间安全地扩展安全臂集,同时促进后续阶段的安全贪婪利用。除了确保在每个播放阶段满足安全约束之外,所提出的算法还表现出一种预期的遗憾,在播放 T 个阶段后不超过 O(sqrt(T)log(T))
Nov, 2019
本文提出了一种称为批量 Langevin Thompson Sampling 算法的方法,用于学习未知奖励分布和转移动力学,在批处理模式下,算法仅需要对数通信成本。 通过在随机多臂老虎机和无限时间域强化学习中应用此算法,保持与标准汤普森采样算法相同的次优遗憾保证。
Jun, 2023
本文设计和分析了一种基于贝叶斯思想的 Thompson Sampling 算法泛化版本,用于解决带有线性收益函数的随机上下文多臂老虎机问题,同时提供了该算法的第一理论保证,得到了最佳遗憾保证。
Sep, 2012
本研究针对具有相似但不完全相同的多臂赌博机环境中的在线多任务学习问题,研究了如何通过知识的健壮传递从而提高学习器在多个相关任务上的整体性能。我们提出了一种 TS 类型算法,对其进行了经验分析,并证明了它是几乎最优的。最后,我们将算法在合成数据上进行了评估,证明了 TS 类型算法在与基准算法和 UCB 算法的比较中具有卓越的经验性能。
Jun, 2022
该论文研究了贝叶斯后悔和汤普森抽样算法在赌博问题中的变体。它建立在信息论框架的基础上,通过率失真分析提供了关于线性赌博问题的后悔率上界。使用链接论证,我们针对度量动作空间的赌博问题建立了新的界限。在奖励的适当连续性假设下,我们的界限为 d 维线性赌博问题提供了紧凑的速率。
Mar, 2024
本文研究了在未知奖励分布下使用 Thompson 采样算法来解决不断变化的赌博机问题,证明了一种子线性的,O (sqrt (T) log T) 的遗憾上限,并将算法测试在了一个动态信道接入问题的模拟中,实证结果与理论上限一致。
Oct, 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
本文提出了一种基于 UCB 策略的新算法 Safe-LUCB,用于解决多臂赌博问题中考虑安全限制的约束,该算法具有探索和利用两个阶段,并控制遗憾值增长,提供了一般遗憾上界及与最佳行动位置有关的问题相关遗憾上界。
Aug, 2019