Oct, 2023

强健性多臂赌博机算法对错误假设的鲁棒性研究

PDF
TL;DR对于参数化赌博机和上下文赌博机，我们确定了一些充分条件，取决于问题实例和模型类别，在这些条件下，经典算法（如 ϵ-greedy 和 LinUCB）在甚至严重错误的奖励设定下，也能够在时间范围内实现亚线性（sublinear）的后悔保证，这与现有针对错误设定赌博机的最坏情况结果形成对比，后者显示的后悔界限与时间成线性关系，这表明存在一组对错误设定具有鲁棒性的赌博机实例。
发现论文，激发创造
  • 上下文回馈中的误差适应

    在这篇论文中，我们介绍了一种新的 Oracle-efficient 算法，适用于无限行动设置下的线性情境强化学习问题，该算法实现了最优的拟合程度依赖性回归（square loss regression）的后悔上限，使得它能够在未知的模型错误情况下灵活适应。

    Jul, 2021

  • 利用离线回归预测器适应上下文 Bandit 中的错误规格化

    提出了一种简单的上下文 Bandit 算法族，该算法族可以通过当有证据表明错配错误导致遗憾增加时返回良好的安全策略来适应错配误差，而不需要像在线或约束回归神谕一样更健壮的神谕。

    Feb, 2021

  • 误设的高斯过程贝叶斯优化

    本文提出了两种基于高斯过程（GP）方法的算法：一种乐观的 EC-GP-UCB 算法，另一种是一种消除型算法 Phased GP Uncertainty Sampling。本文给出了算法的上界，其依赖于时间长度和核心参数，证明了我们的算法在不知道错误情况下实现了对 ε 的最优依赖性，并证明了 EC-GP-UCB 可以与后悔边界平衡策略相结合。

    Nov, 2021

  • 半参数情境赌博机

    该论文研究了半参数上下文赌博机问题，设计了新的算法来解决非线性混淆影响下的奖励估计问题，并通过实证评估证明了该算法的有效性。

    Mar, 2018

  • 线性赌博机误设

    本研究考虑了线性多臂老虎机问题中的在线学习问题，并提出了一种新的算法，该算法包括一个线性假设检验和 OFUL 或 UCB 算法的决策。该算法在完全线性情况下表现出 OFUL 的良好遗憾性能，在存在不稀疏偏差性质的错误规范模型上避免了线性遗憾现象，并且在综合数据实验中得到了一致的支持。

    Apr, 2017

  • 非参数随机情境臂机

    探讨 K-armed bandit 问题下的 noisy reward，提出了一种简单实用的算法（kNN-UCB），并得到了紧密的 top-arm identification 和 sublinear regret 边界，并讨论了该算法的全局 intrisinic dimension 和 ambient dimension 的 regret 边界，同时介绍了对于无限武装情境下 bandit 算法的扩展和实验证明了算法在多种任务上的优越性。

    Jan, 2018

  • 在线聚类误指定用户模型的赌博机

    提出了聚类多臂老虎机在用户模型未正确规定的情况下的问题，设计了两种鲁棒性算法，能适应不准确的用户偏好评估和模型错误导致的聚类问题，证明了我们算法的遗憾上限。实验证明我们对之前算法的优越性。

    Oct, 2023

  • 零膨胀臂

    对于稀疏非零奖励的赌博机实际应用，本文引入了零膨胀赌博机的研究，将奖励模型化为经典的半参数分布，设计了适用于各种奖励分布的 UCB 和 TS 算法，并利用理论和实验研究验证了其超出一般 sub-Gaussian 假设的性能表现能达到速率最优的遗憾界。

    Dec, 2023

  • 平滑上下文强化学习：连接参数化和不可微性遗憾模式

    该研究讨论了非参数上下文赌博问题，研究了函数的 Hölder 类和光滑度参数 β 之间的插值关系，提出了一种新算法，能够调整到各种光滑度设置，并通过确立匹配的上下限证明其遗憾是速率最优的，从而弥合了现有文献关于参数和非可区分性情境赌徒问题，以及仅使用全局或本地信息的赌徒算法之间的差距，同时也揭示了上下文赌徒问题中的复杂性和遗憾之间关键性的相互影响。

    Sep, 2019

  • 上下文臂选择模型

    介绍了在上下文密集应用中的模型选择问题及其解决方案，该方案适用于线性上下文密集应用，并在先验知识下达到了较低的后验概率。

    Jun, 2019