阈值型赌博机带有最优聚合遗憾
本文提出一种基于阈值套索算法的 regret minimization 解决方案,能够更好地应对稀疏随机上下文线性赌博机问题,且不需要对稀疏度等参数有先验知识,理论上的性能约束也有所提高。
Oct, 2020
本文提出了一种忽略一定程度下最优性差距的 Bandit 算法,并以其为基础,设计优化算法 Thompson Sampling (ε-TS)。研究结果表明,该算法能够在一定程度上避免过度探索问题,并在保证性能的前提下,提高计算效率。
Aug, 2020
探讨了在多臂赌博机中最小化遗憾的问题,其中臂的好坏度量不是平均回报率,而是平均值和方差的某个通用函数,特征化了学习可能的条件,并展示了对于某些情况自然算法无法实现亚线性遗憾的例子。
May, 2014
本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题,通过提出自适应算法来自动适应问题的难度,并在理论和实验方面展现了该算法的优越性。
Jun, 2020
本文提出一种基于启发式算法的无参数算法,用于解决特定的组合纯探索随机赌博机问题,以寻找一组平均值高于给定阈值的摇臂,满足给定精度和一定的时间限制,并证明该算法是情况下的最优解决方案,并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题,并构建了最优策略。
May, 2016
本文介绍了一个安全的线性随机挑战模型,其中学习器在每一阶段都需要选择一个预期奖励不小于预先确定的(安全)阈值的臂,以高概率。我们假设学习器最初掌握的是一个已知为安全但不一定最优的臂的知识。基于此假设,介绍了一种学习算法,它将已知的安全臂与探索性臂系统地结合起来,以便随时间安全地扩展安全臂集,同时促进后续阶段的安全贪婪利用。除了确保在每个播放阶段满足安全约束之外,所提出的算法还表现出一种预期的遗憾,在播放 T 个阶段后不超过 O(sqrt(T)log(T))
Nov, 2019
在对抗式多臂赌博机中,攻击者通过攻击策略干扰损失或奖励信号,以实现对受害者赌徒玩家的行为控制。我们向攻击者显示,攻击者能够引导任何无憾对抗性赌博算法,在每轮之外的几乎所有轮次中选择次优目标臂,而仅产生次线性的攻击成本。这个结果意味着在现实世界中,基于赌博机的系统中存在重要的安全问题,例如,在线推荐中,攻击者可能能够劫持推荐系统并推广所需的产品。我们提出的攻击算法只需要了解后悔率,因此对受害方使用的具体赌博算法没有任何限制。此外,我们还推导了任何受害者不可知攻击算法必须产生的理论下限,并与我们的攻击产生的上限匹配,这表明我们的攻击在渐近意义下是最优的。
Jan, 2023