Mar, 2023

非平稳环境下的 MNL-Bandit

PDF
TL;DR本文研究在非稳态环境下的 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 等人提出的周期算法，引入了新的技术和思想来解决非稳态问题中的挑战，特别是针对非稳态引入的偏差，得出了紧密的表征以及新的浓度界限。
mnl-banditnon-stationarydynamic regretepoch-based algorithmconcentration bounds
发现论文，激发创造
  • 使用少量最优臂进行非平稳赌博与元学习

    研究了一种基于子模最大化的算法，该算法可以优化 K 个老虎机任务中最佳 M 个机器臂的最佳子集，表现出比标准算法更小的代价，同时解决了未知和已知任务边界的问题。

    Feb, 2022

  • 非平稳线性赌臂问题的简单解法

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

    Mar, 2021

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

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

    Nov, 2021

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

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

    Feb, 2020

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

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

    Aug, 2017

  • 平滑的非平稳赌博机

    本文研究应用于在线决策中的两臂赌博机问题，其中臂的平均奖励是绝对阶数小于等于 β 的 Hölder 函数。我们展示了该问题平滑和非平滑情况的首个分离，提出了一种策略以 T^（3/5）遗憾为代价。同时，我们为任何整数 β≥1 证明了一个 T^（β+1）/2β+1 的下限，与 β=2 的上限相匹配。

    Jan, 2023

  • 一种新的非平稳情境赌博算法：高效、最优和免参数

    提出了首个无需参数的、高效的、动态遗憾最优的上下文赌博算法，通过引入回放阶段来保持对非平稳的探索，并在探索和开发之间保持良好的平衡。

    Feb, 2019

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

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

    Feb, 2024

  • 关于 MNL-Bandit 组合选择模型的紧密下限的说明

    考虑多项式对数式组合 (MNL) 赌博模型下的动态组合规划问题，证明了关于累计遗憾的严格下界和现有遗憾上界相匹配，适用于所有参数（时间范围 T，物品数量 N 和最大组合容量 K），并减小了现有研究中上下限遗憾之间的 O (√K) 间隙。

    Sep, 2017

  • 对漂移进行对冲：在非稳态环境下学习优化

    介绍针对非静态赌博机环境的最新数据驱动决策算法，采用了随机和对手式学习算法的非传统结合方法，通过滑动窗口 - 置信界算法，针对各种非静态赌博机问题实现了最优动态遗憾边界，并通过数字实验验证了算法的超越性能。

    Mar, 2019