Jul, 2023

具有多次游玩的对抗性睡眠强盗问题：算法与排名应用

PDF
TL;DR该论文提出了一种在在线推荐系统中解决多次玩睡眠盗贼问题的高效算法，该问题涉及有界的对抗性损失和未知的 i.i.d. 分布，所提出的算法扩展了单次选择臂的睡眠盗贼算法，能够保证理论性能，后悔上限为 O (kN^2√(TlogT))，其中 k 是每个时间步中选择的臂数，N 是总臂数，T 是时间界限。
发现论文，激发创造
  • 具有多次游戏和预算限制的多臂赌博机

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

    Nov, 2017

  • 具备随机行动集和对抗性奖励的改进型睡眠赌博机

    本文考虑了具有随机动作集和对抗回报的睡眠强盗问题，提出了一种新的受到 EXP3 启发的高效算法，并在每轮可用集合从一些未知的任意分布中产生的最普遍版本中提出了一个具有保证的高效算法。

    Apr, 2020

  • 对抗性贝叶斯强化学习的对抗攻击

    在对抗式多臂赌博机中，攻击者通过攻击策略干扰损失或奖励信号，以实现对受害者赌徒玩家的行为控制。我们向攻击者显示，攻击者能够引导任何无憾对抗性赌博算法，在每轮之外的几乎所有轮次中选择次优目标臂，而仅产生次线性的攻击成本。这个结果意味着在现实世界中，基于赌博机的系统中存在重要的安全问题，例如，在线推荐中，攻击者可能能够劫持推荐系统并推广所需的产品。我们提出的攻击算法只需要了解后悔率，因此对受害方使用的具体赌博算法没有任何限制。此外，我们还推导了任何受害者不可知攻击算法必须产生的理论下限，并与我们的攻击产生的上限匹配，这表明我们的攻击在渐近意义下是最优的。

    Jan, 2023

  • 更多适应性算法用于对抗式赌博机

    提出了一种新颖的算法，采用乐观性和适应性技术，结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题，并在提高先前工作的同时，取得了多种新的数据依赖性遗憾界。

    Jan, 2018

  • 阻断赌徒

    考虑到重复使用某些选项可能是不可取的或不可行的，本文提出了一种新颖的随机多臂赌博机设置，并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法，但它设计了一种贪婪算法和一种基于 UCB 的算法，具有一定的优异性。

    Jul, 2019

  • 多人赌博机：对抗情形

    设计了第一个能够在任意变化的环境中工作的多人赌博算法，其中武器的损失甚至可能是由对手选择的，同时解决了 Rosenski、Shamir 和 Szlak（2016 年）提出的一个悬而未决的问题。

    Feb, 2019

  • 休息和不休息赌博机的在线学习

    本文研究了涉及休息和不休息的多臂赌博机和多次游戏的在线学习问题，在每个时间步骤，用户可以玩 M 支手臂，其目标是决定每一步要播放哪些 K 支手臂，以在一系列试验中最大化其长期奖励，尤其与机会式频谱接入（OSA）的应用相关。

    Feb, 2011

  • 睡眠赌徒的近最佳每个动作的遗憾界

    我们使用广义版本的 EXP3、EXP3-IX 和 FTRL 与 Tsallis 熵直接最小化每次行动的遗憾，从而获得了接近最优的 $ O (√{TAln⁡K})$ 和 $ O (√{T√{AK}})$ 的界限，并将我们的结果推广到了从睡眠专家那里寻求建议的强盗情境，从而得到了一些现有自适应和跟踪遗憾上限的新证明，并通过推广我们的结果到专家报告信心的强盗版本，得到了主要依赖于专家信心之和的置信遗憾上限。

    Mar, 2024

  • 针对玩家武器平均值不同时的多人老虎机实用算法

    本论文针对多人随机多臂老虎机问题中，玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置，并提出了一种新的有效算法，结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析，证明了该算法的次线性极大遗憾界，解决了 NeurIPS2018 的一个开放性问题。

    Feb, 2019

  • 具有时延依赖收益的随机赌博机

    提出了一个非平稳随机 bandit 模型及其评估算法，对比了该算法和 UCB 方法的优越性，从而能够有效地解决音乐推荐中的问题。

    Oct, 2019