Oct, 2019

任意延迟下对抗性赌博机的最优算法

PDF
TL;DR提出一个新的算法，针对有无限延迟的对抗多臂老虎机问题，该算法是基于一种新型的混合规则制定的，采用 Follow the Regularized Leader (FTRL) 框架，可实现 $O (\sqrt {kn}+\sqrt {D\log (k)})$ 的遗憾保证，并且不需要预先了解 $n$ 或 $D$, 还提出了一种新的调优算法，遗憾保证可达到 $O (\sqrt {kn}+\min_{S}|S|+\sqrt {D_{\bar S}\log (k)})$，用于解决了 Thune 等人 (2019) 提出的未解决问题。
adversarial multi-armed banditsdelayalgorithmregretftrl
发现论文，激发创造
  • 对抗性多臂老虎机中的延迟和数据的适应

    本文考虑在延迟反馈下的敌对多臂老虎机问题，并分析了一些通过仅使用决策时可用的信息 (关于损失和延迟) 来调整步长的 Exp3 算法变体，从而获得适应观察到的 (而不是最坏情况下的) 延迟和 / 或损失序列的遗憾保证。最后，我们介绍了 AdaGrad 风格的版本的算法，该算法通过观察到的 (延迟的) 损失进行适应，而不仅仅是适应于累积延迟 (该算法要求先验上限）。

    Oct, 2020

  • 具有无限制延迟的非随机多臂赌博机

    本文研究带有延迟反馈的多臂老虎机问题，证明了先前的算法在延迟是变量但有上界的情况下具有较好的表现，提出了一种新算法通过一个跳过具有过度大延迟的步骤的 wrapper 来降低了对上界的要求，同时构造了一种新的加倍方案，从而放宽了对时间和延迟知识的要求。提出的算法解决了丰富的应用场景问题并达到了合理的预期表现。

    Jun, 2019

  • 组合半匪谷、线性匪谷和 MDP 的非随机延迟反馈的统一分析

    本文提出了 Follow The Regularized Leader (FTRL) 算法并应用于在线学习中，通过分离延迟反馈成本和赌博反馈成本，得出了在三种不同的情况下的新结果，包括组合半赌博、带延迟的对抗 Markov 决策过程以及带权值的线性赌博。我们的新型遗憾分解显示 FTRL 在正则化程序的 Hessian 矩阵上的温和假设下，可在多轮中保持稳定，并为线性赌徒提供了一种有效算法和接近最优的遗憾限制。

    May, 2023

  • 带有复合匿名反馈的非随机赌博机

    研究非随机赌博环境下的遗憾界，提出了基于 FTRL with Tsallis entropy 的算法转化方法。

    Dec, 2021

  • 更多适应性算法用于对抗式赌博机

    提出了一种新颖的算法，采用乐观性和适应性技术，结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题，并在提高先前工作的同时，取得了多种新的数据依赖性遗憾界。

    Jan, 2018

  • 线性上下文强化学习的最佳算法

    我们研究了针对 K 臂线性情境赌博机的最佳算法，无需先前对环境有所了解，在敌对和随机的情境下都能够提供接近最优的后悔边界。

    Dec, 2023

  • 面向具有悔恨的对抗性线性马尔可夫决策过程的最优化

    在线强化学习是研究的主题之一，尤其在线性 Markov 决策过程中使用了对抗性损失和强盗反馈，提出了两个算法以改善后悔性能。

    Oct, 2023

  • 具有不受限制的延迟分布的随机多臂赌博机

    该研究探讨具有随机延迟的随机多臂赌博问题，在考虑了奖励相关延迟和奖励无关延迟两种情况下，提出了接近最优的算法，并在延迟分布的分位数上增加了附加依赖性，而不需要假设延迟分布来自任何参数化的分布族，还允许无限延迟的情况。

    Jun, 2021

  • 对抗性贝叶斯强化学习的对抗攻击

    在对抗式多臂赌博机中，攻击者通过攻击策略干扰损失或奖励信号，以实现对受害者赌徒玩家的行为控制。我们向攻击者显示，攻击者能够引导任何无憾对抗性赌博算法，在每轮之外的几乎所有轮次中选择次优目标臂，而仅产生次线性的攻击成本。这个结果意味着在现实世界中，基于赌博机的系统中存在重要的安全问题，例如，在线推荐中，攻击者可能能够劫持推荐系统并推广所需的产品。我们提出的攻击算法只需要了解后悔率，因此对受害方使用的具体赌博算法没有任何限制。此外，我们还推导了任何受害者不可知攻击算法必须产生的理论下限，并与我们的攻击产生的上限匹配，这表明我们的攻击在渐近意义下是最优的。

    Jan, 2023

  • 具有复合匿名延迟反馈的有界内存对抗性赌博机

    本研究探讨了具有复合匿名延迟反馈的对抗性赌徒问题，证明了非遗忘环境下会发生伪遗憾现象。但我们提出了一个包装器算法，在某些对抗赌徒问题上获得了 o (T) 策略遗憾。尤其对于 K-armed bandit 和 bandit 凸优化问题，我们的算法的策略遗憾边界为 Ο(T^(2/3))。 此外，我们还证明了 K-armed bandit 的匹配下界，即使在损失序列是遗忘的但延迟非遗忘的情况下也能实现。

    Apr, 2022