May, 2024

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

HTML
PDF
TL;DR我们研究了基于Thompson Sampling的有界奖励随机赌博算法。为了解决现有的与高斯先验的Thompson Sampling相关的问题相关后悔界限在T≤288e^64时是虚无的问题，我们导出了一个更实用的界限，将主要项的系数从288e^64缩小到1270。此外，我们提出了两种参数化的Thompson Sampling算法：带有模型聚合的TS-MA-α和带有时间战斗的TS-TD-α，其中α∈[0,1]控制效用与计算之间的权衡。这两种算法都可以实现O(Kln^(α+1)(T)/Δ)的后悔界限，其中K是臂数量，T是有限学习时段，Δ表示拉动次优臂时的单轮性能损失。
发现论文，激发创造
  • 基于线性回报的情境型贝叶斯-汤普森抽样算法

    本文设计和分析了一种基于贝叶斯思想的Thompson Sampling算法泛化版本，用于解决带有线性收益函数的随机上下文多臂老虎机问题，同时提供了该算法的第一理论保证，得到了最佳遗憾保证。

    Sep, 2012

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

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

    Sep, 2012

  • 通过后验抽样学习优化

    本文采用一种简单的后验抽样算法来平衡探索和利用学习优化操作，称为 Thompson Sampling，理论上提出了后验抽样与 UCB 算法的联系，并提供了一个广泛适用且可以专门针对许多模型类进行特化的后验抽样贝叶斯遗憾界。

    Jan, 2013

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

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

    Apr, 2013

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

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

    Nov, 2013

  • Thompson采样的先验敏感性

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

    Jun, 2015

  • 线性汤普森抽样再探

    在随机线性赌博机问题中，我们为Thompson采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关，并且选取与乐观参数相关的最优臂可以控制后悔，在具有固定概率为乐观的采样分布下来看，Thompson采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。

    Nov, 2016

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

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

    Sep, 2021

  • 感性良好的汤普森取样在上下文臂和强化学习中的应用

    本文提出了一种改进的 Thompson Sampling 策略，在 frequentist 问题的设置下，通过理论分析及感性解释说明了如何缓解 TS 策略中探索不够的缺陷，并提供了 Bayesian Regret Bounds for TS 和 frequentist regret bounds for Feel-Good TS 的理论证明。基于在线最小二乘回归估计，使用在线聚合技术可以直接获得频率分析中的在线最小二乘回归估计回归界限，得到了与最小值下限的匹配，同时，该分析可以推广到一类线性嵌入式上下文匹配问题。

    Oct, 2021

  • 基于信息论的噪声上下文随机赌博机的汤普森抽样算法的遗憾分析

    我们研究了一种随机情境线性赌博机问题，代理人通过一个未知噪声参数的噪声信道观察到真实情境的有噪声、损坏的版本。我们的目标是设计一种行动策略，可以近似一个能够获取奖励模型、信道参数以及根据观察到的有噪声情境从真实情境得到预测分布的神谕的行动策略。我们在贝叶斯框架下引入了一种基于高斯情境噪声的汤普森采样算法。采用信息论分析，对于神谕的行动策略，我们证明了该算法的贝叶斯遗憾。我们还将这个问题扩展到当代理人在接收到奖励之后，以一定延迟观察到真实情境的情景，并展示了延迟真实情境会导致更低的贝叶斯遗憾。最后，我们通过与基准算法进行实证研究，展示了所提出算法的性能。

    Jan, 2024