Apr, 2013

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

PDF
TL;DR研究具有奖励分布先验分布的随机多臂赌博问题，证明 Thompson Sampling 算法在没有先验分布时具有最优的贝叶斯遗憾上界，并在 Bubeck 等人的先验设置下证明了算法的一致界限，并与 Audibert 和 Bubeck [2009] 和 Russo 和 Roy [2013] 的技术方法有关。
stochastic multi-armed banditprior distributionregret boundsthompson samplingbayesian regret
发现论文，激发创造
  • Thompson 采样的先验敏感性

    本文深入分析了 Thompson Sampling 算法中对先验分布选择的鲁棒性，发现在选择优先概率质量时，其遗憾上限与先验正判度呈 O (√T/p), 先验负判度呈 O (√(1-p) T), 并利用这些性质提出了一种基于鞅理论的新证明方法。

    Jun, 2015

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

    使用贝叶斯方法的随机算法 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

  • 高斯赌博机的 Thompson 抽样策略的最优性取决于先验知识

    探讨多参数模型中 normal distribution 模型下 Thompson sampling 算法的优化问题及其 prior 选择的影响

    Nov, 2013

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

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

    May, 2015

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

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

    Nov, 2011

  • Thompson 采样在逻辑回归老虎机问题中的表现

    本研究对 Logistic Bandit 问题进行了研究，确立了 Thompson sampling 算法的鲁棒性，提出了新的度量指标 —— 脆弱性维度，并使用该指标证明了现有算法的上限。

    May, 2019

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

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

    Nov, 2013

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

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

    May, 2019

  • 改进的贝叶斯后悔边界在强化学习中的应用

    本研究证明了在多种环境设置下，Thompson 采样在强化学习中的贝叶斯后悔限与性能上界，通过使用一组离散的替代环境简化学习问题，并使用后验一致性对信息比例进行了精细分析，从而导出了时间不均匀强化学习问题中的上界，其中 $H$ 是回合长度，$d_{l_1}$ 是环境空间的 Kolmogorov $l_1$ 维度。接着，我们在各种设置中找到了 $d_{l_1}$ 的具体限制，并讨论了我们的结果是首次出现还是改进了现有技术。

    Oct, 2023