Feb, 2024

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

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

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

    Jun, 2024

  • UCBoost: 对随机赌博机的复杂性和最优性进行增强的提升方法

    这篇论文提出了一种名为 UCBoost 的方法，用于解决多臂赌博算法在序贯决策问题中低复杂度且最优问题，该方法提供了一种可以在计算复杂度和最优性之间互相交换的方式。

    Apr, 2018

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

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

    Jul, 2015

  • 有界随机赌博机及其扩展的 KL-UCB 算法

    本文针对随机赌博问题，提出了一种在线动态索引策略 KL-UCB 算法，并通过有界回报和伯努利回报两个方面的研究证明了其优越性和适用性，同时展示了比较实验结果，在时间短的情况下依然表现良好，且优于其他算法。

    Feb, 2011

  • 一种极小极大算法及渐进最优算法用于随机赌博机

    本文提出了 kl-UCB ++ 算法，用于在具有指数分布族的随机赌博机模型中实现遗憾最小化，并证明了其同时渐近最优（按 Lai 和 Robbins 的下限界定）和极小化最优。这是第一种证明同时具有这两个性质的算法，因此将两种不同的研究方向合并在一起，并提供了简单明了的证明。

    Feb, 2017

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

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

    Feb, 2020

  • 随机多臂赌博问题的遗憾下界和拓展上置信界策略

    通过对经典多臂赌博机（Stochastic Multi-Armed Bandit）的研究，探讨了两种不同的准则下存在的遗憾下界。同时，研究了 UCB 等算法的变体，证明了这种情况下不可能设计一种自适应的策略来选择最优算法。

    Dec, 2011

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

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

    Oct, 2023

  • 合作多智体图形赌博机：UCB 算法和遗憾分析

    在这篇论文中，我们将多智能体图赌博问题定义为由 Zhang、Johansson 和 Li [CISS 57，1-6（2023）] 引入的图赌博问题的多智能体扩展。我们提出了一种基于上限置信界（UCB）的学习算法 Multi-G-UCB，并证明其在 T 步内的期望遗憾通过 O (Nlog (T)[sqrt (KT) + DK]) 被界定，其中 D 是图 G 的直径。最后，我们通过与其他方法的比较对算法进行了数值测试。

    Jan, 2024

  • 量子厚尾赌博机

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

    Jan, 2023