Dec, 2019

使用单峰 Thompson 采样解决 Bernoulli 一阶臂赌博问题

HTML
PDF
TL;DR本研究介绍了随机Rank-One赌博机，在证明了该算法的对数后悔率的同时，通过将Rank-One赌博机作为单峰赌博机的一个特例进行分析，提出了一种新的Unimodal Thompson Sampling算法，并证明了其频率后悔率的渐近最优界，通过模拟实验和结果对比，证明了我们方法相对于现有技术的显著改进。
发现论文，激发创造
  • 多臂赌博问题中汤普森采样的分析

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

    Nov, 2011

  • 汤普森抽样：渐进最优的有限时间分析

    本文针对伯努利回报情况，首次提供匹配 Lai 和 Robbins 下限所给累积遗憾率的有限时间分析，证明了 Thompson Sampling 是解决随机多臂老虎机问题的最优策略，并通过数值比较和实验验证了这一结论。

    May, 2012

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

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

    Sep, 2012

  • 单模臂：遗憾下限和最优算法

    研究了随机多臂老虎机问题，通过一个单峰函数来表示不完全有序的臂的期望奖励。对于离散和连续臂的情况，分别提出了OSUB和UCB算法，并得到了渐进的上下界和提高性能的实验结果。

    May, 2014

  • 随机Rank-1赌博机

    本文基于stochastic rank-1 bandits提出了computationally-efficient算法Rank1Elim，该算法可解决在线学习问题，在rank-1矩阵中找到最大的条目，且在K + L，1 / Δ和log n方面的遗憾是线性的。

    Aug, 2016

  • 线性汤普森抽样再探

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

    Nov, 2016

  • 结构化随机赌臂问题中的最小探索

    介绍了一类广泛的随机赌博问题，其中将臂与相应的奖励映射的函数具有一些已知的结构特性。推导了这些问题的渐近特定情况下的遗憾下界，并且开发了OSSB算法，其遗憾匹配了这个基本极限。通过数值实验展示了OSSB的效率，并且证明OSSB优于包括汤普森取样在内的现有算法。

    Nov, 2017

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

    研究了在半盲反馈条件下，组合多臂赌博问题中，具有概率触发武器的组合汤普森抽样的遗憾，并在基准武器预期的连续Lipschitz情况下得出了CTS的遗憾界。

    Sep, 2018

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

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

    May, 2019

  • 多臂赌博机的宽容遗憾

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

    Aug, 2020