Sep, 2018

组合多臂赌博机中 Thompson Sampling 的分析与概率触发武器

PDF
TL;DR研究了在半盲反馈条件下，组合多臂赌博问题中，具有概率触发武器的组合汤普森抽样的遗憾，并在基准武器预期的连续 Lipschitz 情况下得出了 CTS 的遗憾界。
combinatorial thompson samplingmulti-armed banditsemi-bandit feedbackregretlipschitz
发现论文，激发创造
  • 组合半臂老虎机的汤普森抽样

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

    Mar, 2018

  • 组合半臂老虎机的汤普森抽样的统计效率

    本文研究了采用半智能反馈的随机组合多臂赌博机问题。研究中提出了解决对于两种不同分布情况下是否存在效率最优、渐进遗憾最小算法的问题。通过分别采用 Beta 先验和高斯先验对 Combinatorial Thompson Sampling 策略进行了分析，进而找到了这两种分布情况下的算法解决方案，从而得出计算效率上优于 Efficient Sampling for Combinatorial Bandit 策略的结论。

    Jun, 2020

  • 多臂赌博问题中汤普森采样的分析

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

    Nov, 2011

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

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

    Sep, 2012

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

    本文提出了多次试验下的 Thompson sampling 方法（MP-TS）并对其进行了后效分析，证明了其具有与 Anantharam 等人提供的最佳后悔下界相匹配的最优后悔上界，并通过计算机模拟进行了验证。我们还提出了 MP-TS 的改进版本，并表明其具有更好的实际效果。

    Jun, 2015

  • 概率触发手臂组合半赌博算法的遗憾上界优化及应用

    该论文研究具有概率触发臂的组合多臂赌博机 (CMAB-T) 和半弱馈反的问题，将触发概率调制 (TPM) 条件引入 CMAB-T 框架中以达到更好的遗憾界限，并发现许多应用程序如影响最大化赌博机和组合级联赌博机满足 TPM 条件。此外，本文提供了下限结果，表明这种条件对于消除 $1/p^*$ 因子是至关重要的。

    Mar, 2017

  • 组合半匪难度分析及 Thompson 抽样策略与贪心算法的应用

    本文研究了在贪心算法下 Thompson sampling（TS）在组合多臂赌博问题（CMAB）中的行为，证明了 TS 可以在近似算法的预测下解决 CMAB 问题，并提供了渐近匹配的后悔上限。

    Nov, 2021

  • Thompson 采样用于复杂的赌博机问题

    考虑了具有复杂操作的随机多臂赌博问题，其中决策者在每轮中进行复杂操作而不仅仅是基本臂。复杂操作的奖励是基本臂奖励的某些函数，并且观察到的反馈可能不是每个臂的奖励。作者在一般情况下证明了一种频率后悔上限和 Thompson 抽样算法的 相容性，并应用于包括选择臂子集的一类复杂赌博问题中。

    Nov, 2013

  • 组合神经赌博机

    本文提出了两个基于深度神经网络的组合赌博算法：CN-UCB 和 CN-TS，它们是首个在组合赌博问题中实现遗憾性能保证的算法。通过数值实验，证明了我们的算法有更好的性能。

    May, 2023

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

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

    Sep, 2021