Jun, 2023

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

PDF
TL;DR本文研究了随机预算多臂赌博问题，并提出了一种名为 ω-UCB 的新的上置信界（UCB）采样策略，该策略使用了不对称置信区间，并表明该方法具有对数遗憾且在合成和真实设置中始终优于现有策略。
stochasticbudgeted multi-armed banditupper confidence boundreward-cost ratiologarithmic regret
发现论文，激发创造
  • 具有多次游戏和预算限制的多臂赌博机

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

    Nov, 2017

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

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

    Jun, 2024

  • 基于背包的预算受限多臂赌博机最优策略

    对于受预算限制的多臂赌博机问题，本论文提出了两种拉动策略 KUBE 和分数 KUBE，并证明了两种策略的遗憾具有对数上限，且这个上限是渐近最优的。

    Apr, 2012

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

    本文研究了随机组合多臂赌博机框架，提出了一种名为 SDCB 的新算法，该算法估计底层随机变量的分布和它们的随机显著性置信区间，并证明了 SDCB 可以实现 O (logT) 的分布相关遗憾和 $ ilde {O}(√T)$ 的分布无关遗憾，并将所得结果应用于 $K$-MAX 问题。

    Oct, 2016

  • 基于图的赌博机学习

    本论文研究了一种称为图赌博机的多臂赌博机扩展问题，提出了一种能够利用乐观原则平衡长期探索与开发的学习算法 G-UCB，并证明其能够达到理论最优的遗憾界，数值实验结果表明该算法优于其他基准算法。

    Sep, 2022

  • 拜占庭弹性的分散式多臂赌博机

    该研究通过开发一种完全分散的鲁棒上置信界算法，将信息混合步骤与不一致和极端值的截断步骤结合起来，以恢复分散合作多臂赌博中的有效行为，提高正常代理的表现。该算法在遗憾方面不劣于单代理 UCB1 算法，并且所有正常代理的累积遗憾严格优于非合作情况。实验证实了这一框架的优点。

    Oct, 2023

  • 非平稳赌博机问题的置信上限策略

    本文考虑了分布保持不变，但在未知时间发生改变的非稳态赌徒问题，研究了两种算法：折扣上限置信区间和滑动窗口上限置信区间，并通过 Hoeffding 不等式得到了后者的上界，对不优的赌博机被玩的次数期望进行了上界估计并证明了存在性突然性改变时的遗憾下界，证明了折扣上限置信区间和滑动窗口上限置信区间的匹配下界一致性。

    May, 2008

  • 多保真度多臂赌博机

    本文研究了一种多保真度赌博机的变体，提出了一种名为 MF-UCB 的新型上置信区间过程，并证明了它在序列逐渐的逼近中适应性更好，并且达到了比忽略近似的策略更好的遗憾最小化效果。

    Oct, 2016

  • 组合多臂老虎机及其对概率触发臂的扩展

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

    Jul, 2014

  • 针对分段平稳赌博机的变化检测近乎最优自适应程序

    通过结合经典的 UCB 算法和简单的变化检测组件，我们提出了一种称为 M-UCB 的算法，可以在未知时间步骤中检测和适应变化，并在多臂赌博机问题中实现近乎最优的风险界。通过在公共数据集上进行数值实验，我们还展示了该算法的卓越性能。

    Feb, 2018