May, 2019

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

PDF
TL;DR本文从学习的角度分析了未知参数情况下的时序不息不静赌博机问题，在采用泰普斯抽样的情况下考虑了一个通用策略映射作为竞争者，证明了贝叶斯遗憾的 k 倍增长上限。本文的竞争对手足够灵活，可以表示各种基准，包括最佳固定操作策略，最优策略，惠特尔指数策略或近视策略。同时，还提供了支持理论发现的实证结果。
restless bandit problemsnon-stationary multi-armed banditslearning perspectivethompson samplingbayesian regret bound
发现论文，激发创造
  • 非周期性不安定赌博机中的汤普森抽样

    本文研究了在未知奖励分布下使用 Thompson 采样算法来解决不断变化的赌博机问题，证明了一种子线性的，O (sqrt (T) log T) 的遗憾上限，并将算法测试在了一个动态信道接入问题的模拟中，实证结果与理论上限一致。

    Oct, 2019

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

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

    Sep, 2012

  • 关于不安分马尔科夫赌博机的遗憾界限

    本文介绍了一种算法来解决不安分的马尔科夫赌臂问题，并证明了基于指数的策略在这个问题中一定是次优的。该算法可以在不需要假设马尔可夫链除了不可约的任何情况下，经过 T 步后实现相对于知道所有赌臂分布的最佳策略的 O (√T) 的悔恨。

    Sep, 2012

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

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

    Apr, 2013

  • 不静态赌博机问题的近似算法

    讨论了一种无法使用贪心指数算法求解的 Feedback MAB 问题，开发出了一种新颖并且通用的双重算法技术，可为不少于 1+epsilon 的解提供 2+epsilon 的近似值，这个技术同样适用于其他不特定的喧闹强盗问题和 POMDP。

    Nov, 2007

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

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

    Jun, 2015

  • 基于置信区间和不安定多臂赌博模型的感知策略

    在认知无线电中，提出了一种对于具有不同但未知奖励分布的多臂赌博问题的感知策略。该策略是一个集中协调的索引策略，其中频带的索引由一个样本均值项和一个置信项组成，使得子优频段之间连续感知的时间间隔成指数增长，导致弱后悔值对数增长。仿真结果表明，该策略优于文献中的其他类似方法。

    Nov, 2012

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

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

    Nov, 2013

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

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

    Nov, 2011

  • 线性强化学习问题的信息论界限和紧凑遗憾率

    该论文研究了贝叶斯后悔和汤普森抽样算法在赌博问题中的变体。它建立在信息论框架的基础上，通过率失真分析提供了关于线性赌博问题的后悔率上界。使用链接论证，我们针对度量动作空间的赌博问题建立了新的界限。在奖励的适当连续性假设下，我们的界限为 d 维线性赌博问题提供了紧凑的速率。

    Mar, 2024