UCB 赌博机上的近最优对抗攻击
在对抗式多臂赌博机中,攻击者通过攻击策略干扰损失或奖励信号,以实现对受害者赌徒玩家的行为控制。我们向攻击者显示,攻击者能够引导任何无憾对抗性赌博算法,在每轮之外的几乎所有轮次中选择次优目标臂,而仅产生次线性的攻击成本。这个结果意味着在现实世界中,基于赌博机的系统中存在重要的安全问题,例如,在线推荐中,攻击者可能能够劫持推荐系统并推广所需的产品。我们提出的攻击算法只需要了解后悔率,因此对受害方使用的具体赌博算法没有任何限制。此外,我们还推导了任何受害者不可知攻击算法必须产生的理论下限,并与我们的攻击产生的上限匹配,这表明我们的攻击在渐近意义下是最优的。
Jan, 2023
该论文研究了对多臂赌博算法进行的对抗攻击,以操纵奖励信号以控制算法选择的行动,并提出了针对常见的两种多臂赌博算法 epsilon-greedy 和 UCB 的攻击方案。这种攻击是在不知道平均奖励的情况下进行的,并且攻击者所需的努力是对问题特定参数取对数,这个参数随着赌博问题变得越来越容易攻击而变小。结果表明,攻击者可以轻松地劫持多臂赌博算法的行为,以推广或阻止某些行动。由于多臂赌博算法在实践中的使用越来越广泛,因此我们的研究揭示了一个重大的安全威胁。
Oct, 2018
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
提出抵御恶意攻击的新型样本中位数算法和探索辅助上限置信区间算法,并通过多个仿真和实验表明它们能够在多臂赌博机问题中实现 sublinear regret。
Feb, 2020
研究多臂赌博机中 UCB 类型最佳臂识别策略的对手扰动攻击,探讨其对模型选择目标臂的影响,证明了在总臂数和伪中心极限定理参数已知的情况下,可以在 T 轮内找到目标臂作为最佳臂。
Sep, 2022
该论文提出了一种新的多臂赌博机框架,在该框架下将 K-armed bandit 问题转化为 C+1-armed 问题。通过利用该框架下的广义上限置信区间算法可以降低算法的遗憾量,以实现一定的算法性能优势。
Aug, 2018
研究了在自利的情况下,三种常见的赌博算法 UCB, ε-Greedy 和 Thompson Sampling 对策略行为的适应性,为应用于经济学中的推荐系统提供了鲁棒的工具。
Jun, 2019
针对多臂赌博机框架中奖励之间相互关联的情况,我们提出了一种统一的方法来优化这种关联并基于这种情况推广经典赌博算法,其中 C-UCB 是上置信边界算法的相关版本。我们证明了算法的正确性,并通过 MovieLens 和 Goodreads 数据集的实验验证了该算法与经典的赌博算法相比的显著改进。
Nov, 2019
提出了基于一种不精确预算方法的智能多臂赌博机构建 UCB 型算法的新方法;推导出了相应于最优化方法的收敛速度的遗憾界;提出了一种新的算法 Clipped-SGD-UCB,并从理论和实证角度展示了在奖励中存在对称噪声的情况下,我们可以达到 O (logT√KTlogT) 的遗憾界,而不是当奖励分布满足 E [X∈D][|X|^(1+α)]≤σ^(1+α)(α∈(0,1]) 时,即表现得比普遍的重尾赌博机下界所假设的要好。此外,即使奖励分布没有期望,也能保持相同的界限,即当 α<0 时。
Feb, 2024