NIPSOct, 2016

具有一般奖励函数的组合多臂赌博机

PDF
TL;DR本文研究了随机组合多臂赌博机框架，提出了一种名为 SDCB 的新算法，该算法估计底层随机变量的分布和它们的随机显著性置信区间，并证明了 SDCB 可以实现 O (logT) 的分布相关遗憾和 $ ilde {O}(√T)$ 的分布无关遗憾，并将所得结果应用于 $K$-MAX 问题。
stochastic combinatorial multi-armed banditreward functionupper confidence boundsdcb algorithm$k$-max problem
发现论文，激发创造
  • 组合多臂老虎机及其对概率触发臂的扩展

    该研究提出了一种通用的组合多臂赌博问题框架，将未知分布的基础臂组成超级臂进行玩耍，进一步探讨了更多可能基于已激发臂的结果触发概率的扩展，旨在通过在线学习算法实现最小化（α，β）- 逼近遗憾。

    Jul, 2014

  • 具有不对称置信区间的预算多臂赌博机

    本文研究了随机预算多臂赌博问题，并提出了一种名为 ω-UCB 的新的上置信界（UCB）采样策略，该策略使用了不对称置信区间，并表明该方法具有对数遗憾且在合成和真实设置中始终优于现有策略。

    Jun, 2023

  • 应用于逐步强化学习和其他领域的组合多元多臂赌博机

    引入一种新的组合多臂赌博梳理 (CMAB) 框架，具有多维和概率触发的臂 (CMAB-MT)，其中每个臂的结果是一个 d 维多维随机变量，反馈遵循普通臂触发过程。

    Jun, 2024

  • 组合多臂老虎机问题的批量独立遗憾界

    针对组合多臂赌博机问题中的非线性奖励函数和批处理选择，引入一种新的平滑度标准 —— 基尼加权平滑度，证明了现有算法中的线性后悔量与批大小的关系可以被该平滑度参数取代，并在概率最大覆盖问题中获得了明显的精度提高。

    May, 2019

  • 基于数据驱动的上界置信度在重尾赌博机上的近优遗憾

    本文提出了一种分布无关、数据驱动的上置信界（UCB）算法，结合最近发展的重新抽样中位数法（RMM）方法，对称奖励分布的研究中生成近乎最优的后悔边界，即使是重尾分布。

    Jun, 2024

  • 具公平约束的组合式睡眠赌博机

    提出针对多臂赌博机模型（MAB）的新型组合睡眠 MAB 模型。通过扩展在线学习算法 UCB 以处理利用和探索之间的权衡，同时采用虚拟队列技术来正确处理公平性约束。最终提出一种名为 LFG 的新算法，可保证可行性最优，具有受时间平均后悔上限约束的时间复杂度，并进行了广泛的模拟以证明其有效性。

    Jan, 2019

  • 具上下文的组合赌博机、概率挑战的手臂

    本文针对情境组合赌博问题，提出了一种具有触发概率和方差自适应的算法，并给出了相应的遗憾界。在合成和真实世界数据集上的实验结果表明算法的优越性。

    Mar, 2023

  • 带有主导目标的多目标上下文多臂赌博机

    本文提出了一种新的具有两个目标的多目标情境多臂赌博问题，并通过引入奖励向量及其依赖于上下文的分配来解决问题；提出了基于 Pareto 的指标的 MOC-MAB 算法，证明了其对于二维和 Pareto 的悔恨度都是次线性的，并在合成和实际数据集上与其他最先进的方法进行了比较。

    Aug, 2017

  • 概率触发臂或独立臂组合半匪徒问题的无关批量大小的后悔界限

    本研究探讨组合良带 (Bandits) 的算法，针对其大小批次 (K) 对后悔束缚的依赖性进行优化，发现一种可替代平滑性条件的新型触发概率和方差调节 (TPVM) 条件，进行后悔分析并提出基于置信区间和方差的 BCUCB-T 算法，将大小批次 (K) 的项降低至对数级别，并在非触发 CMAB 中将其完全去除。实验结果表明，我们的算法在不同领域具有优越的性能。

    Aug, 2022

  • 适应离线算法来解决带有固定反馈的组合多臂赌博问题的框架

    该研究针对随机、组合式多臂老虎机问题，提出了一种将离线算法转化为基于有限老虎机反馈的子线性 α 遗憾策略的框架，并将其应用于离散优化问题中的基数问题和背包约束问题中获得了良好的表现。

    Jan, 2023