Jun, 2020

广义线性赌臂问题的高效算法：在线随机梯度下降和汤普森抽样

PDF
TL;DR本研究提出了一种基于在线随机梯度下降的广义线性赌博机算法，它使用单步 SGD 更新来利用过去的信息并使用汤普森抽样实现探索，能够在探索与利用之间取得平衡，在合成和实际数据集上始终优于现有算法，其总时间复杂度为 T 和 d 的线性比例，其中 T 是总轮次数，d 是特征数量，并实现了 O（T）的遗憾，其中 T 是回合数。
发现论文，激发创造
  • 基于线性回报的情境型贝叶斯 - 汤普森抽样算法

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

    Sep, 2012

  • 广义线性情境赌博机的可证明最优算法

    本文提出了针对广义线性情境臂的上界置信度算法，实现了与众不同的性能，同时我们还分析了更简单的上界置信度算法，在特定情况下证明了该算法具有最优的后悔。

    Feb, 2017

  • PG-TS：逻辑上下文多臂赌博机的改进汤普森抽样

    本文提出了改进的 Polya-Gamma 配分的 Thompson Sampling 算法（PG-TS），通过使用一种快速推理程序，它可以解决逻辑上下文 bandits 的遗憾最小化问题，通过对环境特征协方差的后验分布的明确估计，能够使得 PG-TS 在类似情形下较传统算法快速收敛。

    May, 2018

  • 上下文广告带中的广义汤普森采样

    本文提出一种名为广义 Thompson Sampling 的新算法，将其作为专家学习框架下的一种启发式算法，其包括 Thompson Sampling 作为其特殊情况，并派生了一般性遗憾界，将其应用到广泛的情境性算法中，量化 “先验” 分布对遗憾界的影响。

    Oct, 2013

  • 神经汤普森抽样

    本文介绍了一种基于深度神经网络和贝叶斯推断的新型算法 —— 神经 Thompson Sampling (Neural Thompson Sampling)，并证明该算法的性能能够和同类算法相匹配，实验结果证实了该理论。

    Oct, 2020

  • 广义线性背景下双重双重稳健汤普森抽样

    提出了一种新颖的上下文强化学习算法，使用 double doubly-robust estimator 实现对所有上下文的独立性考虑，并在概率保证条件下证明了广义线性模型赌博机的后悔上限。

    Sep, 2022

  • 非平稳广义线性赌博机算法

    本文提出了两个基于上限置信度算法的广义线性模型及其应用的方法，以解决在非静态环境下的上下文在线学习和塞德利反馈问题，这些结果表明这些算法在一般的情境序列下，并且存在突然变化时具有高概率的上限置信度边界，证明结果的形式为时间 T 内的 d^2/3 G^1/3 T^2/3 阶动态后悔。

    Mar, 2020

  • 线性汤普森抽样再探

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

    Nov, 2016

  • 广义线性 Bandit 算法及其重尾奖励的高效计算

    本文研究了具有重尾回报的广义线性赌博问题，提出了基于截断和中值平均的两种新算法，其在时间上界和上下文信息维度的情况下，几乎达到了最优的减悔界限。通过数值实验结果验证了我们算法的优点。

    Oct, 2023

  • 在线持续上下文推荐系统超参数优化

    本文提出了第一个在线连续超参数调整框架，即 CDT 框架，用于学习最佳超参数配置，可以在不预设候选超参数组合的情况下调整上下文 bandit 算法，其中使用 Zooming TS 算法进行探索和重启技术来避免环境切换，并提供更好的实验结果。

    Feb, 2023