ICMLJan, 2023

平滑的非平稳赌博机

PDF
TL;DR本文研究应用于在线决策中的两臂赌博机问题，其中臂的平均奖励是绝对阶数小于等于 β 的 Hölder 函数。我们展示了该问题平滑和非平滑情况的首个分离，提出了一种策略以 T^（3/5）遗憾为代价。同时，我们为任何整数 β≥1 证明了一个 T^（β+1）/2β+1 的下限，与 β=2 的上限相匹配。
online decision makingbandit algorithmsnon-stationalityhölder functionregret
发现论文，激发创造
  • 非平稳线性赌臂问题的简单解法

    本文研究了非平稳线性臂问题，提出了一种基于重启策略的算法以平衡利用和探索，并证明了该算法的动态遗憾值，同时还解决了现有算法中的严重技术缺陷问题。

    Mar, 2021

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

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

    Sep, 2019

  • 非平稳环境下高效应对背景干扰的 Bandit 算法

    本研究开发了多种高效的上下文推断算法，为非平稳环境提供了有效的解决方案，具有动态适应分布变化的能力，同时通过对各种标准回归进行分析，证明了在时间和空间成本上都能达到最优的效果。

    Aug, 2017

  • 用一种新的平滑度对抗强盗

    定义了一种新的算法家族，用于对抗性多臂赌博问题，并提供基于凸平滑的简单分析技术。通过使用 Tsallis 熵进行正则化，证明了它的最小极大后悔度为 Θ(√TN)；同时，对于具有有界危害率的微扰分布，广泛类的扰动方法可获得近乎最优的后悔率，低至 O (√TN log N)，例如 Gumbel、Weibull、Frechet、Pareto 和 Gamma 分布都满足此特性。

    Dec, 2015

  • 非平稳环境下的组合半赌博算法

    该研究探讨了非静态组合半强盗问题，研究了在动态和切换的情况下，算法所能达到的最佳后悔上限以及需要提前了解的参数，并提供了无需先知参数的算法。

    Feb, 2020

  • 非平稳对决多臂老虎机的最优高效动态遗憾算法

    本文研究了 $K$- 武斗器下在非固态或时变偏好情况下动态遗憾最小化问题，设计了能够有效解决此问题的算法，证明了算法的最优性，并进行了大量模拟和与其他算法对比的实验。

    Nov, 2021

  • 非平稳潜在自回归赌博算法

    我们考虑具有非平稳收益的随机多臂赌博问题，提出了一个称为潜在 AR 赌博的新环境，在这个环境中，臂的平均收益随时间变化是由未知的、潜在的、自回归（AR）阶数为 k 的状态引起的。针对已知的 AR 阶数 k，我们提出了一个算法，在这种情况下实现了 O (k√T) 的遗憾。在多个非平稳环境中，我们的算法在实证上优于标准 UCB，即使 k 被错误估计。

    Feb, 2024

  • 无范数偏见的线性赌博机

    本文提出了两种不需要先验知识的新算法，一种针对较小的变动武器集，另一种针对固定武器集，其悔恨界仅仅受到次要影响。

    May, 2022

  • 学习在非稳态下进行优化

    介绍了一种新的非平稳线性随机赌博算法，应用于动态定价和广告分配领域，并使用滑动窗口 UCB 算法实现了最优动态后悔上界。

    Oct, 2018

  • 非平稳环境下的 MNL-Bandit

    本文研究在非稳态环境下的 MNL-Bandit 问题，提出一种算法，其最坏动态遗憾为 $\tilde {O}(\min \left\{ \sqrt {NTL}\;;\; N^{\frac {1}{3}}(\Delta_{\infty}^{K})^{\frac {1}{3}} T^{\frac {2}{3}} + \sqrt {NT}\right\} )$，并基于 2016 年 Agrawal 等人提出的周期算法，引入了新的技术和思想来解决非稳态问题中的挑战，特别是针对非稳态引入的偏差，得出了紧密的表征以及新的浓度界限。

    Mar, 2023