高斯过程优化中汤普森采样自适应收敛速率
本文提出了一种基于稀疏高斯过程模型实现的可扩展 Thompson 抽样算法,通过理论证明和实验验证表明该算法不会损失标准 Thompson 抽样算法的遗憾性能,并成功地应用于高通量分子设计任务等实际问题。
Jun, 2020
本文提出了两种基于高斯过程的算法 - 改进的 GP-UCB(IGP-UCB)和 GP-Thomson 采样(GP-TS),并给出了相应的遗憾边界,在连续的臂集上解决了随机赌徒问题。当期望奖励函数属于复制核希尔伯特空间(RKHS)时,边界成立。在实验评估和对合成和真实世界环境中现有算法的比较中,突出了所提出策略的优势。
Apr, 2017
本文提供了一种连续、优势风险函数 $ ho$ 的风险厌恶型 Thompson 抽样算法设计和分析方法,并证明了多项分布下基于连续优势风险函数的算法 $ ho$-MTS 的渐近最优遗憾界以及 Bernoulli 分布下基于经验分布性能度量的风险测度的渐近最优性,包括了广泛应用的风险测度如 CVaR、比例风险等;数值模拟验证了算法与基线遗憾界的接近度。
Aug, 2021
本文提出一种名为广义 Thompson Sampling 的新算法,将其作为专家学习框架下的一种启发式算法,其包括 Thompson Sampling 作为其特殊情况,并派生了一般性遗憾界,将其应用到广泛的情境性算法中,量化 “先验” 分布对遗憾界的影响。
Oct, 2013
通过选取最优的高斯过程先验,构建相应函数空间,提出的多个方法可以最小化某个函数的未知性,包括连续自适应边界算法和高斯过程基本概念,最优化方法如期望改进和随机搜索算法等。
Jan, 2011
使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的 contestual bandits 设置。
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
该论文研究了如何在贝叶斯全局优化中利用并行算法解决多臂赌博问题,提出了基于高斯过程的 GP-BUCB 算法,证明了与串行方法相比,该算法的累积遗憾仅增加一个独立于批量的常数因子,并在两个真实世界应用中展示了其有效性。
Jun, 2012
探讨多参数模型中 normal distribution 模型下 Thompson sampling 算法的优化问题及其 prior 选择的影响
Nov, 2013
我们通过建立一个马尔可夫决策过程模型,研究一种名为汤普森采样的采样算法的渐近行为。我们展示了标准(期望)遗憾可能呈超线性增长,并且不能很好地捕捉到在具有非平凡状态演进的现实情况下的学习概念。通过分解标准(期望)遗憾,我们提出了一种新的指标,称为期望剩余遗憾,它忽略了过去动作的不可变后果,而是测量了当前时期后的最优奖励的遗憾。我们表明,汤普森采样算法的期望剩余遗憾上界由一个指数级快速收敛于 0 的项给定。我们给出了汤普森采样的后验采样误差收敛于 0 的条件,并且引入了期望剩余遗憾的概率版本并给出了其收敛于 0 的条件。因此,我们提供了一个适用于采样算法的学习概念,在比以前考虑的更广泛的情况下将非常有用。
May, 2024