Apr, 2024

改进的多臂赌博机问题的近乎紧密逼近保证

PDF
TL;DR我们对改进的多臂赌博机问题给出了近似最优的上下界。我们证明了对于任何随机在线算法，存在一个实例使其相对于最优收益至少有一个 Ω(√k) 的近似因子。然后，我们提供了一个随机在线算法，在事先告知最优臂可达到的最大收益的情况下，保证了一个 O (√k) 的近似因子。我们接下来展示了如何消除这一假设，以增加 O (log k) 的近似因子，从而实现了相对于最优的 O (√k log k) 的整体近似。
multi-armed banditsapproximation factorreward functiononline algorithmconcave function
发现论文，激发创造
  • 针对 Top-k 臂选择的近乎最佳样本复杂度界限

    本文探讨了 Best-$k$-Arm 问题的样本复杂性边界，提出了一种新颖的复杂度度量方法和基于消除的算法，并展示了该算法的实例 - 边界下限和状态 - 界限的严格支配能力。

    Feb, 2017

  • 线性参数化赌博机

    本文研究基于多维随机向量臂收益的赌博机问题，证明了在解决特定问题时使用相应的相位策略可以达到最优的累计遗憾和贝叶斯风险，并提出了针对通用问题的近似最优解。

    Dec, 2008

  • 高维线性少参数随机连续武装匪徒问题

    考虑了随机连续武装机器人问题，对其低秩矩阵恢复文献的结果进行了研究，导出实现遗憾度上界的高效随机算法。

    Dec, 2013

  • K 臂对决赌徒问题的相关上限置信界

    本文介绍了一种新的解决 K-armed dueling bandit 问题的方法，其扩展了 Upper Confidence Bound 算法并证明了有限时间的遗憾度为 O（log t）。 经实验结果证实，与现有技术相比，该方法在信息检索中取得了显着的优势。

    Dec, 2013

  • 具有多次游戏和预算限制的多臂赌博机

    研究多臂赌博问题下的多次试验和预算约束的拓展，提出上置信区间和 Exp3 算法的具体实现及其性能分析。

    Nov, 2017

  • 多种最佳臂的遗憾问题

    本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题，通过提出自适应算法来自动适应问题的难度，并在理论和实验方面展现了该算法的优越性。

    Jun, 2020

  • 流式赌博问题的紧凑内存遗憾下界

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

    Jun, 2023

  • 使用少量最优臂进行非平稳赌博与元学习

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

    Feb, 2022

  • 具有武器层次结构的 Top-k 极端情境强化学习

    研究了上下文臂问题，其中臂的总数可以巨大，并允许学习者选择 k 个臂并观察所选臂的所有或某些收益。我们为非极端现实设置提出了一个算法，并提出了一种实用的臂层次结构模型来处理极端情况，这种层次结构允许每个上下文的相关臂数指数减少，从而获得了有关遗憾的保证。

    Feb, 2021

  • 具有次线性时间复杂度的线性赌博机算法

    本篇论文提出了 2 种线性 bandits 算法，并利用最大内积搜索问题求解臂的选择，从而解决了针对极大臂数和缓慢变化的应用困难，扩展了现有的近似最大内积搜索的求解算法并实现了子线性复杂度及减小了损失。应用于在线学习问题中，该算法时间复杂度良好且表现出与线性时间基线相似的遗憾值。

    Mar, 2021