ICMLJun, 2012

面向自适应对手的在线强盗学习：从遗憾到策略遗憾

PDF
TL;DR该论文提出了当对手可以适应在线算法的动作时，标准遗憾定义变得不再有效，定义了替代的政策遗憾概念，用于测量在线算法在适应性对手下的性能，并研究了在线赌徒问题的情况，表明任何赌徒算法都无法针对带有无界内存的适应性对手保证次线性的政策遗憾，但同时提出了将标准遗憾限制在次线性边界以下的任何赌徒算法转换为政策遗憾限制在次线性边界以下的算法的一般技术， 并将这一结果扩展到其他遗憾变体。
online learning algorithmsadversarial inputregretpolicy regretonline bandit setting
发现论文，激发创造
  • BanditQ -- 在对抗环境中具有保证的每个用户收益的无懊悔学习

    本文提出一种在线学习算法 BanditQ，基于队列理论和在线学习相结合，实现公平在线预测，并在信息完整的情况下，达到目标约束，同时实现 $O (T^{3/4})$ 的损失率。

    Apr, 2023

  • 重复博弈中的政策后悔

    本文重新审视了在线学习中的策略后悔问题，表明在某些情况下，外部后悔和策略后悔是不兼容的，而在自利智能体领域，如果使用某些算法，则可以保证外部后悔和策略后悔都是有利的。本文还介绍了一个新的均衡概念 —— 策略均衡，并表明粗略相关均衡是策略均衡的一个真子集。

    Nov, 2018

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

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

    Jan, 2018

  • 具有切换成本和其他自适应对手的在线学习

    本文研究了预测中的不同类型自适应（非固定的）对手的强度，使用新概念的策略遗憾去衡量玩家的表现，特别关注记忆和切换成本的自适应对手，具有均摊 2/3 次幂的速率且强度显著较弱。

    Feb, 2013

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

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

    Jan, 2023

  • 在线组合优化中的遗憾

    本文研究使用二进制向量表示决策者可能的选择时的在线线性优化问题及其反悔，探讨了决策者在不同反馈条件下的最优反悔幅度，并提出了一种使用镜像下降算法和隐式归一化预测策略的解决方案，获得了半强盗情形的最优界限，同时也证明了在线组合优化基准算法的次优性。

    Apr, 2012

  • 计数型赌博机的完整策略遗憾界

    研究了限制对手策略的措施，旨在实现最强版本的策略后悔，即完全策略后悔。提出概念式为 “计票老虎机” 的在线学习算法，并针对该算法提供了一种具有可接受保证的算法，证明了算法的近似最优性。

    Apr, 2022

  • 同时最小化动态遗憾和适应性遗憾

    本文提出了一种在线学习算法，能同时最小化动态遗憾和自适应遗憾，具有更强的理论保证。

    Feb, 2020

  • 关于连续时间在线学习的一点备注

    连续时间模型中，我们提出了在线学习问题的连续时间算法，并给出了最优遗憾界的简明证明。

    May, 2024

  • 自适应遗憾在可能的情况下：只需两个查询

    在线优化中，给出了强适应遗憾的准确查询和遗憾最优的贪心算法，同时给出了多臂赌博机和赌博凸优化的最优算法，并通过实证研究表明了在不稳定环境和下游任务中的卓越表现。

    Jan, 2024