ICMLJun, 2023

单次遍历流式多臂赌博机的严格遗憾界

PDF
TL;DR本文解决了多臂赌博机模型 (single-pass MABs) 中的 regret minimization 问题，并设计出一些具有不同 memory 复杂度的算法分别达到了不同的最优 regret 上界，并且通过实验取得了较好的效果。
发现论文，激发创造
  • 流式赌博问题的紧凑内存遗憾下界

    这篇论文研究了流式赌博机问题，建立了时间上界、臂数、游戏轮数的算法紧确的最劣后悔下限，并证明了与分析算法复杂度上限的样本复杂性分析问题的关系。

    Jun, 2023

  • 流式随机多臂赌博机中的记忆 - 遗憾权衡理解

    在 $P$ 次流式模型中研究随机多臂赌博机问题，通过设计一种算法，给出了关于 $m，n$ 和 $P$ 的最优遗憾度量的完整刻画，同时提出了一个上界和下界，结果在 $n$ 和 $P$ 方面具有紧密性。

    May, 2024

  • 最佳选择躲避：关于多臂老虎机的纯探索的近最优多遍流式下限

    纯探索、多臂赌博机、多次传递流算法、样本通过折衷、奖励差距

    Sep, 2023

  • 睡眠赌徒的近最佳每个动作的遗憾界

    我们使用广义版本的 EXP3、EXP3-IX 和 FTRL 与 Tsallis 熵直接最小化每次行动的遗憾，从而获得了接近最优的 $ O (√{TAln⁡K})$ 和 $ O (√{T√{AK}})$ 的界限，并将我们的结果推广到了从睡眠专家那里寻求建议的强盗情境，从而得到了一些现有自适应和跟踪遗憾上限的新证明，并通过推广我们的结果到专家报告信心的强盗版本，得到了主要依赖于专家信心之和的置信遗憾上限。

    Mar, 2024

  • 混洗模型下的差分隐私多臂老虎机

    本文提出了一种在随机模型下割臀膜机制下的多臂老虎机问题的差分隐私算法，其分别对应具体分布相关和分布无关两种后悔下界，并给出最优算法上界和良好的本地模型表现。

    Jun, 2021

  • 多智能体多臂赌博机中的遗憾下界

    在多臂赌博机领域，多智能体多臂赌博机方法已经受到了广泛关注，但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界，并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时，我们证明了实例相关上界的 O（log T）下界和平均差值独立上界的 sqrt（T）下界。在对抗奖励的假设下，我们建立了连接图的 O（T^（2/3））下界，从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时，我们还展示了线性的遗憾下界。与以前的研究相比，本文全面研究了这些情景下的紧密下界。

    Aug, 2023

  • 多臂赌博机的宽容遗憾

    本文提出了一种忽略一定程度下最优性差距的 Bandit 算法，并以其为基础，设计优化算法 Thompson Sampling (ε-TS)。研究结果表明，该算法能够在一定程度上避免过度探索问题，并在保证性能的前提下，提高计算效率。

    Aug, 2020

  • 探索不再：非随机赌博机的改进高概率遗憾界限

    本文提出了基于 Implicit eXploration 的损失估计策略，可以在不需要不必要的探索成分的情况下，实现高概率遗憾界，取得了多臂赌博问题方面的改进结果。

    Jun, 2015

  • 多保真度多臂赌博机再访

    研究了多精度多臂赌博机（MF-MAB）及其最优臂识别和后悔最小化目标，为 BAI 提出了成本复杂度下限，推荐两种替代忠诚度选择程序的算法框架，并确定了两种程序的成本复杂度上限，并提出了新的后悔定义，以及解决了该问题的消除算法。

    Jun, 2023

  • 随机多臂赌博机的有限遗憾

    研究解决在已知最优的选择和最小间隔值时如何制定随机化策略，以解决随机多臂赌博问题中可能发生的后悔问题，并探讨了其下界和最优解等问题。

    Feb, 2013