Jun, 2024

随机线性赌博机中的近似推断贝叶斯赌博算法

PDF
TL;DR提出了一个通用的理论框架来分析具体推断存在时的随机线性赌博带中的贝叶斯赌博算法，得到了 Linear Thompson Sampling 和 Linear Bayesian Upper Confidence Bound 在近似推断时保持原有遗憾上界但需要更大的常数项的结论，引入一种新的定义来展示 Linear Bayesian Upper Confidence Bound 改进了 Linear Thompson Sampling 的遗憾速率，从而与极小的理论最优速率相匹配，这是首次在具有有界近似推断误差的随机线性赌博带设置中给出的遗憾界。
bayesian bandit algorithmsapproximate bayesian inferencecontextual bandit problemsregret analysisstochastic linear bandits
发现论文，激发创造
  • 广义线性情境赌博机的可证明最优算法

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

    Feb, 2017

  • 带线性约束的随机赌博机

    本文研究了一个约束的上下文线性赌博机问题，提出了一种算法 OPLB 并证明了其 T 轮后悔度的上限，针对多臂赌博机情况提出了高效算法，同时给出了问题的下限和模拟结果。

    Jun, 2020

  • 具有重尾收益的线性随机赌博机的几乎最优算法

    本研究提出一种创新的算法来解决具有重尾收益的线性随机赌博机问题，并证明了算法的最优性。

    Oct, 2018

  • 安全约束下的线性随机赌博机

    本文提出了一种基于 UCB 策略的新算法 Safe-LUCB，用于解决多臂赌博问题中考虑安全限制的约束，该算法具有探索和利用两个阶段，并控制遗憾值增长，提供了一般遗憾上界及与最佳行动位置有关的问题相关遗憾上界。

    Aug, 2019

  • 非平稳环境下的加权线性赌博机

    该研究利用 D-LinUCB 算法解决了随机线性 bandit 模型中的非平稳线性回归模型，通过使用加权最小二乘估计器进行序列预测，同时提供了理论保证和实验表现。

    Sep, 2019

  • 具有对数或次线性遗憾的约束上下文臂机算法

    本文对具有预算和时间限制的约束情境赌博问题展开了研究，提出了一种高效算法 UCB-ALP 以实现对其进行近似求解并达到对数遗憾。

    Apr, 2015

  • 截断 LinUCB 算法用于随机线性赌臂问题

    研究此论文中的上下文臂带，其中上下文是独立且恒定分布的 d 维随机向量，期望回报在臂参数和上下文中都是线性的；提出了一种截断版的 LinUCB 算法，称为 Tr-LinUCB，其在截断时间 S 之前遵循 LinUCB，在之后进行纯粹的开发，S=Cd log（T）时达到 O（d log（T））的遗憾，如果 S = d log（T）的某个升幂，则相对于最优解的损失是费用为 loglog（T）的乘法，这种对超调敏感的 Tr-LinUCB 算法的实用重要性。

    Feb, 2022

  • 具有随机延迟反馈的线性赌博机

    该文提出了基于延迟反馈的随机线性赌博机及其算法 OTFLinUCB 和 OTFLinTS，并通过实验验证了其性能，其中 OTFLinUCB 算法的遗憾上界为 O (d√T)。

    Jul, 2018

  • 针对随机情境对决赌徒的方差感知后悔界限

    本研究提出了一种基于广义线性模型的上下文对决算法，该算法在计算效率和方差感知遗憾边界方面有优势，并通过实验验证了其优于以往无方差算法的优点。

    Oct, 2023

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

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

    Mar, 2024