Jun, 2015

多组玩法随机多臂赌博问题中 Thompson 抽样的最优遗憾分析

HTML
PDF
TL;DR本文提出了多次试验下的Thompson sampling方法（MP-TS）并对其进行了后效分析，证明了其具有与Anantharam等人提供的最佳后悔下界相匹配的最优后悔上界，并通过计算机模拟进行了验证。我们还提出了MP-TS的改进版本，并表明其具有更好的实际效果。
发现论文，激发创造
  • 多臂赌博问题中汤普森采样的分析

    本文介绍了使用贝叶斯算法的 Thompson Sampling 原则，旨在在序贯决策问题中研究探索/开发权衡。该算法在实验证明接近最优，并展现了一些理想的特性，但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。

    Nov, 2011

  • 进一步优化 Thompson Sampling 算法的后悔上界

    使用贝叶斯方法的随机算法Thompson Sampling在多臂赌博问题中表现显著，本文提供了一种新的悔恨分析方法，同时证明了该算法在期望后悔上的问题特定界限和问题独立界限，方法简单且可适用于更广泛的contestual bandits设置。

    Sep, 2012

  • Thompson抽样的无先验和有先验依赖的遗憾界

    研究具有奖励分布先验分布的随机多臂赌博问题，证明Thompson Sampling算法在没有先验分布时具有最优的贝叶斯遗憾上界，并在Bubeck等人的先验设置下证明了算法的一致界限，并与Audibert和Bubeck [2009]和Russo和Roy [2013]的技术方法有关。

    Apr, 2013

  • 预算多臂老虎机的汤普森抽样

    本文将 Thompson sampling 算法扩展到预算限制的 MAB 中，通过从后验分布中采样两个数字并比较选择具有最大比值的手臂进行更新，证明此算法在伯努利臂或普通分布下的分布相关遗憾界都是在预算上对数复杂度，通过我们的仿真实验验证了该算法的有效性。

    May, 2015

  • 组合半臂老虎机的汤普森抽样

    本文研究了Thompson采样方法在随机组合多臂赌博机框架中的应用，分析了多种算法的累积遗憾，并给出了上限界以及其他算法之间的比较结果。

    Mar, 2018

  • 均值方差赌博机的汤普森采样算法

    本文提出了针对均值-方差MAB问题的Thompson抽样算法，并在更少的假设条件下提供了高斯和伯努利bandit的全面损失分析。我们的算法在各种参数配置下都达到了最好的已知损失边界。

    Feb, 2020

  • 多臂赌博机的宽容遗憾

    本文提出了一种忽略一定程度下最优性差距的Bandit算法，并以其为基础，设计优化算法Thompson Sampling(ε-TS)。研究结果表明，该算法能够在一定程度上避免过度探索问题，并在保证性能的前提下，提高计算效率。

    Aug, 2020

  • 基于集群武器的汤普森抽样算法

    该论文提出了基于多级 Thompson 抽样方案的算法，用于解决具有线性预期收益的上下文相关多臂赌博机及其聚类武器的问题。同时，理论和实证表明，利用特定的集群结构可以显著改善遗憾并降低计算成本。

    Sep, 2021

  • 匹配市场中的赌博学习的汤普森抽样

    本文针对未知偏好的两侧市场匹配问题，提出了首个Thompson Sampling算法的回报分析，证明TS算法在实践中优于ETC和UCB算法。

    Apr, 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