Jun, 2024

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

PDF
TL;DR本文提出了一种分布无关、数据驱动的上置信界（UCB）算法，结合最近发展的重新抽样中位数法（RMM）方法，对称奖励分布的研究中生成近乎最优的后悔边界，即使是重尾分布。
stochastic multi-armed banditsupper confidence boundsregret ratesdistribution-free ucb algorithmheavy-tailed distributions
发现论文，激发创造
  • 自举式上置信域界限算法

    本文提出了一种基于乘数 bootstrap 的非参数和数据相关的 UCB 算法，并进一步将二阶校正融入该算法，在理论上，我们推导出了在比标准次高斯性更弱的尾部假设下的多臂老虎机的问题相关和问题无关的后悔边界，数值结果表明 UCB 算法相比其他基线在一系列多臂和线性老虎机问题中都有显著的降低后悔

    Jun, 2019

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

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

    May, 2008

  • 优化置信区间上界算法：改进有限臂赌博机的遗憾

    提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法，同时具有最优问题依赖性遗憾和最坏情况遗憾。

    Jul, 2015

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

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

    Jun, 2023

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

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

    Oct, 2023

  • 量子厚尾赌博机

    本文研究了具有重尾分布的奖励和量子奖励谷歌的多臂黑客（MAB）和随机线性黑客（SLB）。

    Jan, 2023

  • 用于带有重和超重对称噪声的随机赌博机的快速 UCB 类型算法

    提出了基于一种不精确预算方法的智能多臂赌博机构建 UCB 型算法的新方法；推导出了相应于最优化方法的收敛速度的遗憾界；提出了一种新的算法 Clipped-SGD-UCB，并从理论和实证角度展示了在奖励中存在对称噪声的情况下，我们可以达到 O (logT√KTlogT) 的遗憾界，而不是当奖励分布满足 E [X∈D][|X|^(1+α)]≤σ^(1+α)(α∈(0,1]) 时，即表现得比普遍的重尾赌博机下界所假设的要好。此外，即使奖励分布没有期望，也能保持相同的界限，即当 α<0 时。

    Feb, 2024

  • 重尾臂赌博机中实现全自适应遗憾最小化

    学习重尾分布下的遗憾最小化问题，引入自适应算法并提供适应性鲁棒 UCB 方法，以最小化重尾 MAB 问题的遗憾。

    Oct, 2023

  • 概率无界对抗下的稳健随机赌博算法

    提出抵御恶意攻击的新型样本中位数算法和探索辅助上限置信区间算法，并通过多个仿真和实验表明它们能够在多臂赌博机问题中实现 sublinear regret。

    Feb, 2020

  • 多智能体多臂赌博决策分布式一致性算法

    研究多智能体多臂赌博问题中的决策制定策略，利用贝叶斯变点检测和重启决策协作优化多智能体 UCB 算法的期望组后悔率的理论上限，并在合成数据集和真实数据集上进行数值实验，表明所提出的方法优于现有的算法。

    Jun, 2023