Jul, 2023

比例响应：用于简单和累积遗憾最小化的情境赌博机算法

PDF
TL;DR提出了一种新的基于上下文 Bandit 算法的族群，利用 “保序手臂集” 提供每个上下文的一组手臂，覆盖了上下文特定的最优手臂，在简单遗憾最小化和累积遗憾最小化方面都有优异表现。
发现论文，激发创造
  • 具有平滑遗憾的情境臂控算法：连续行动空间高效学习

    提出了一种平滑遗憾函数的背景自适应算法，可用于大量或连续动作空间下的通用背景自适应问题，并能适应各种光滑度级别的问题，取得了先前优化遗憾函数的最优性保证。

    Jul, 2022

  • 上下文连续型强化学习：静态对动态遗憾的比较

    我们研究了上下文连续性强化学习问题，证明了任何达到次线性静态遗憾的算法都可以扩展到达到次线性动态遗憾，我们提出了一种算法，通过自协调屏障和内点法实现了次线性动态遗憾，并且得出两个关键事实：首先，对于上下文不连续的函数，没有算法可以达到次线性动态遗憾；其次，对于强凸和光滑函数，我们提出的算法达到了最小极大动态遗憾速率的最优值，仅相差对数因子。

    Jun, 2024

  • 无限臂老虎机的简单遗憾

    本文针对无穷臂随机赌博机问题，提出一种算法用以最小化简单损失，并扩展到多种情况下，如未知时间跨度等。

    May, 2015

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

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

    Feb, 2017

  • 多臂赌博问题的纯探索

    研究随机多臂老虎机问题的性质和限制，探讨具有在线探索特性的预测器的表现，其中简单后悔被评估，讨论简单后悔与累计后悔的关系，在有限臂数的情况下展示了一种性能下限和预测器的上限后悔，并针对连续老虎臂问题进行了研究。

    Feb, 2008

  • $α$- 公平上下文强化学习

    设计了一种高效算法，确保在全信息和强盗反馈设置中几乎达到次线性的遗憾，以解决 alpha-fair contextual bandits 问题。

    Oct, 2023

  • 具有自适应上下文的因果情境助推

    我们研究了一种因果背景下的情境式赌博问题，学习者基于由其选择的初始干预进行上下文选择。在每一轮开始时，学习者根据其选择的初始行动选择一个随机上下文并获得奖励。通过引入一个与实例相关的因果参数 λ 来实现上界，并且通过使用凸优化来解决赌博探索问题。我们的实验结果验证了我们的理论，并在项目的 GitHub 存储库上发布了我们的代码。

    May, 2024

  • 可上下文化的随机臂赌博机

    介绍了一个在上下文赌博问题中近似最优样本复杂度，并且是这个问题的 PAC 设置和在线设置中的最小化遗憾。

    Jun, 2023

  • 上下文臂针对高效优化学习

    本文介绍了一种在线学习算法，它使用了一种基于代价敏感分类器的方法，并实现了最优遗憾率，与之前的算法相比，具有指数级别的运行速度优势，并且在反馈延迟方面实现了加性遗憾而非乘性遗憾。

    Jun, 2011

  • 一种高效的含背包限制多臂赌博算法，以及对凹目标问题的扩展

    研究了具有全局背包限制条件下的上下文多臂赌博问题，提出了一种计算效率更高、后悔更低的算法，复杂度与策略空间的大小成对数关系，并将结果推广到一种没有背包限制但目标是任意 Lipschitz 凹函数的变体。

    Jun, 2015