通过结合Exp3 和 UCB1两个先前算法的优点,我们提出了一种新的、在对抗性奖励和随机奖励两种情况下表现最优的bandit算法SAO。
Feb, 2012
该论文提出了当对手可以适应在线算法的动作时,标准遗憾定义变得不再有效, 定义了替代的政策遗憾概念,用于测量在线算法在适应性对手下的性能,并研究了在线赌徒问题的情况,表明任何赌徒算法都无法针对带有无界内存的适应性对手保证次线性的政策遗憾,但同时提出了将标准遗憾限制在次线性边界以下的任何赌徒算法转换为政策遗憾限制在次线性边界以下的算法的一般技术, 并将这一结果扩展到其他遗憾变体。
Jun, 2012
本研究提出了一种算法,能够在对抗式和随机式赌徒问题中实现几乎最优的伪后悔界限,并表明任何在随机式赌徒问题中具有O(log n)伪后悔界限的算法都无法对自适应对抗式赌徒问题实现O(sqrt(n))的期望后悔。
May, 2016
研究多臂赌博问题下的多次试验和预算约束的拓展,提出上置信区间和Exp3算法的具体实现及其性能分析。
Nov, 2017
提出了一种新颖的算法,采用乐观性和适应性技术,结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题,并在提高先前工作的同时,取得了多种新的数据依赖性遗憾界。
Jan, 2018
探究了一种带背包的 Bandits 模型,旨在在限制供应/预算情况下求解多臂赌博机问题。提出了一种新的算法,采用重复博弈中遗憾最小化的框架,相对于最佳固定动作分布具有 O(log T) 的竞争比率。
Nov, 2018
发展了一种新的方法,使用标准无偏估计量,并依赖于简单的递增的学习速率表和对数单调自协调障碍以及加强的弗里德曼不等式,以获取高概率遗憾边界。
Jun, 2020
该研究提出了一种BwK框架的一般化模型,允许非单调资源利用,并提出了一个灵活的双重模板以处理任何具有再生性问题的在线学习问题,包括对抗和随机输入,同时可用于解决一些实际相关的经济问题。
Jun, 2023
通过要求原始算法和对偶算法是弱自适应的,我们证明了在「背包带劫匪」框架中,能够保证子线性的对违规约束的罚值,并同时在随机和对抗的情况下提供最佳性能,并为具有线性约束的上下文劫匪问题提供了首个无α-遗憾的保证。
May, 2024
本文研究了对抗攻击具有鲁棒性的随机多臂赌博机算法,解决了攻击者在观察学习者行动后篡改奖励观测的问题。提出的算法在已知和未知攻击预算情况下均有效,显著降低了算法的遗憾界限,为提升算法在对抗环境中的稳定性提供了新思路。
Aug, 2024