通过后验抽样学习优化
文章提出了一种基于多臂赌博框架的在线顺序决策支持方法,利用 Thompson 抽样来平衡探索与利用的权衡,提出了两种算法用以解决多臂赌博问题,并在理论上给出了广义下界,通过实验证明了该方法在现实世界的数据集上表现的有效性。
Sep, 2022
我们研究了基于 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
本文提出了一种新的模型无关后验采样的公式,适用于更广泛的周期性强化学习问题,并通过新颖的证明技术,展示了在适当条件下,我们的后验采样方法的最坏后果可以与基于优化的方法的最优结果相匹配,尤其是在线性 MDP 设置中,我们的算法产生的遗憾与现有基于后验采样的探索算法相比,随着维度线性增长而非二次依赖。
Aug, 2022
本文将 Thompson sampling 算法扩展到预算限制的 MAB 中,通过从后验分布中采样两个数字并比较选择具有最大比值的手臂进行更新,证明此算法在伯努利臂或普通分布下的分布相关遗憾界都是在预算上对数复杂度,通过我们的仿真实验验证了该算法的有效性。
May, 2015
该文提出了一种新颖的基于后验采样算法的马尔可夫博弈的可证明有效性算法,其中实现了对广义函数逼近的解决方案,并证明了该算法在满足一定条件的问题中具有 sqrt (T) 的后悔上限,丰富了 MGs 的工具箱并促进了后验采样的广泛应用。
Oct, 2022
研究具有奖励分布先验分布的随机多臂赌博问题,证明 Thompson Sampling 算法在没有先验分布时具有最优的贝叶斯遗憾上界,并在 Bubeck 等人的先验设置下证明了算法的一致界限,并与 Audibert 和 Bubeck [2009] 和 Russo 和 Roy [2013] 的技术方法有关。
Apr, 2013
该研究提出了一种用于强化学习的后验采样方法(PSRL),通过对一个先验分布进行贝叶斯更新来在已知的一系列时段内实现对 Markov 决策过程的优化,从而达到高效的探索。该算法在时间,状态和行动空间上有明显的性能优势,并具有一定的先验知识编码能力。
Jun, 2013
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