Sep, 2021

在线决策问题中关于对抗性破坏的最佳鲁棒性

PDF
TL;DR论文研究了预测问题和多臂老虎机问题两个具有序列决策的基本问题。特别地，我们关注当对手可能篡改损失时的随机机制，并研究能够实现的鲁棒性水平。本文的主要贡献在于表明，最佳鲁棒性可以通过对所涉及的污染量的平方根依赖来表达。此外，我们还提供了下限，表明上述遗憾边界是紧的。最后，对于多臂老虎机问题，我们还提供了一个近似紧密的下限。
predictionexpert advicemulti-armed bandit problemrobustnessregret bounds
发现论文，激发创造
  • 更好的随机赌博机算法与对抗性干扰

    研究了存在对抗性污染的随机多臂赌博机问题，在此问题上提出了一种新算法，其遗憾几乎是最优的，相对于以前的工作有显著的改进。我们的算法对对抗污染的程度是不可知的，并且可以承受相当大的污染，几乎不会降低性能。

    Feb, 2019

  • 对抗性污染下的随机赌博机鲁棒性

    本文介绍了一种基于随机波段的新型随机抽样模型，该模型可以适应在受到敌对冲击的情况下仍然保持准确性，并且对于包含作弊行为的数据的性能逐渐降低，但依旧维持在一个线性水平。

    Mar, 2018

  • 具对抗性破坏的随机线性优化

    将随机赌徒模型扩展到对抗性破坏模型，并应用于随机线性优化问题，采用 L"owner-John 椭球进行探索，并将时间分割成指数递增的时代以限制破坏的影响，使得算法对于适应性对手所选择的破坏的数量不可知，其遗憾只会在破坏数量线性增加时增加。

    Sep, 2019

  • 抗对抗攻击的随机线性臂机算法

    研究了随机线性赌博机问题，考虑了对抗攻击，提出了两种 Robust Phased Elimination 算法，证明了在非污染情况下可以获得近似最优的收益，并得出针对这些算法的相对近似最优的加性项。同时，在具有多样化情境的情况下，表明一种简单的贪婪算法是稳健的，近似最优的加性遗憾项，尽管不进行明确的探索并且不知道 C。

    Jul, 2020

  • 随机和对抗多臂赌博问题中扰动的最优性

    本研究探讨了在随机和对抗多臂老虎机问题中，基于扰动的算法的最优性。我们提供了对于子 Weibull 和有界扰动的统一遗憾分析，当收益是次高斯分布时。我们的界限对于具有参数 2 的子 Weibull 扰动是实例最优的，并且具有匹配的下支界。对于对于在支持的极端点处有足够概率质量的所有有界扰动，我们都提供了实例最优边界。在对抗设置中，我们使用离散选择理论和极值理论的工具，证明了两种自然解决方法的严格障碍。我们的结果表明，如果最优扰动存在，则将是 Frechet 类型的。

    Feb, 2019

  • 鲁棒利普希茨贝叶斯在对抗扰动下的决策

    本文提出了第一行对抗下的强、弱 Lipschitz bandit 算法，能在无总损坏预算的情况下，在两种类型的对手下实现次线性后悔，但强对手情况下表现最优，并通过对两种经典攻击的试验证明了该算法的有效性。

    May, 2023

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

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

    Jan, 2023

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

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

    Jan, 2018

  • 在线和分布自由鲁棒性：带 Huber 污染的回归和上下文臂

    本文从对抗鲁棒性的角度重新审视了两个经典的高维在线学习问题，即线性回归和情境地图，并探究了无需假设数据分布，直接从全局角度保证它们对抗鲁棒的可行性。具体方法是通过交替最小化策略将普通最小二乘法嵌入到简单的凸约束计算不完整数据下的最优加权分布，并证明该方法在污染程度方面具有最佳的可重复性和完整性。

    Oct, 2020

  • 强化学习中具有防腐能力的探索策略

    我们提出了一个框架，结合 “不确定性中的乐观主义” 和 “动作消除” 这两个策略，以解决领域中的非随机腐败问题，从而有效地实现了多阶段情节强化学习。

    Nov, 2019