AAAIDec, 2023

稀疏超图上多智能体汤普森采样的有限时间频率后悔界

PDF
TL;DR研究了多智能体多抽臂赌博机问题，针对联动臂的回报进行了探索，提出了一种高效的变体算法 epsilon-MATS，并证明了其在频率意义下的遗憾上界是次线性的，同时通过实验验证了其在相同情景下相比现有算法的卓越性能和改进的计算效率。
multi-agent multi-armed bandithypergraphthompson samplingregret boundcomputational efficiency
发现论文，激发创造
  • 多组玩法随机多臂赌博问题中 Thompson 抽样的最优遗憾分析

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

    Jun, 2015

  • 多臂赌博机的宽容遗憾

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

    Aug, 2020

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

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

    Sep, 2012

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

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

    Mar, 2018

  • 智能和适应后验采样算法用于二元选择

    我们研究了基于 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

  • 具有时间性的多臂赌博机问题中汤普森抽样的遗憾界

    本文从学习的角度分析了未知参数情况下的时序不息不静赌博机问题，在采用泰普斯抽样的情况下考虑了一个通用策略映射作为竞争者，证明了贝叶斯遗憾的 k 倍增长上限。本文的竞争对手足够灵活，可以表示各种基准，包括最佳固定操作策略，最优策略，惠特尔指数策略或近视策略。同时，还提供了支持理论发现的实证结果。

    May, 2019

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

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

    Nov, 2011

  • 使用分数后验信息的汤普森抽样泛化遗憾分析

    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

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

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

    May, 2015

  • 连续风险厌恶赌博机汤普森抽样的统一理论

    本文提供了一种连续、优势风险函数 $ ho$ 的风险厌恶型 Thompson 抽样算法设计和分析方法，并证明了多项分布下基于连续优势风险函数的算法 $ ho$-MTS 的渐近最优遗憾界以及 Bernoulli 分布下基于经验分布性能度量的风险测度的渐近最优性，包括了广泛应用的风险测度如 CVaR、比例风险等；数值模拟验证了算法与基线遗憾界的接近度。

    Aug, 2021