带有复合匿名反馈的非随机赌博机
本研究探讨了具有复合匿名延迟反馈的对抗性赌徒问题,证明了非遗忘环境下会发生伪遗憾现象。但我们提出了一个包装器算法,在某些对抗赌徒问题上获得了 o (T) 策略遗憾。尤其对于 K-armed bandit 和 bandit 凸优化问题,我们的算法的策略遗憾边界为 Ο(T^(2/3))。 此外,我们还证明了 K-armed bandit 的匹配下界,即使在损失序列是遗忘的但延迟非遗忘的情况下也能实现。
Apr, 2022
本文研究了具有随机次模(期望上)奖励和完全 bandit 延迟反馈的组合多臂老虎机问题,其中假定延迟反馈是组合匿名的,同时研究了有界择逊、随机独立和随机条件独立三种延迟反馈模型,给出了每种延迟模型的后悔界限,忽略问题相关参数,证明所有延迟模型的后悔界限为 $ ilde {O}(T^{2/3} + T^{1/3} u)$,其中 $T$ 为时间跨度,$ u$ 根据三种情况有不同的定义,因此在所有三种延迟模型中表明了延迟对后悔的添加项,该算法被证明优于具有延迟复合匿名反馈的其他全 bandit 方法。
Mar, 2023
研究了一种带有延迟的聚合匿名反馈的赌博机问题,表明在期望延迟已知的情况下,可以通过提供的算法,在硬的、延迟聚合匿名反馈设置中维持类似于非匿名问题的后悔成本,但在延迟不确定情况下,增加了对数因子或加性方差项的后悔成本。
Sep, 2017
本文研究了在线组合优化问题中的半盲反馈,提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率,在部分反馈方案中首次实现了此类保证,并在组合设置中首次实现了此类保证。
Feb, 2015
本文研究带有延迟反馈的多臂老虎机问题,证明了先前的算法在延迟是变量但有上界的情况下具有较好的表现,提出了一种新算法通过一个跳过具有过度大延迟的步骤的 wrapper 来降低了对上界的要求,同时构造了一种新的加倍方案,从而放宽了对时间和延迟知识的要求。提出的算法解决了丰富的应用场景问题并达到了合理的预期表现。
Jun, 2019
本文考虑在延迟反馈下的敌对多臂老虎机问题,并分析了一些通过仅使用决策时可用的信息 (关于损失和延迟) 来调整步长的 Exp3 算法变体,从而获得适应观察到的 (而不是最坏情况下的) 延迟和 / 或损失序列的遗憾保证。最后,我们介绍了 AdaGrad 风格的版本的算法,该算法通过观察到的 (延迟的) 损失进行适应,而不仅仅是适应于累积延迟 (该算法要求先验上限)。
Oct, 2020
本文提出了 Follow The Regularized Leader (FTRL) 算法并应用于在线学习中,通过分离延迟反馈成本和赌博反馈成本,得出了在三种不同的情况下的新结果,包括组合半赌博、带延迟的对抗 Markov 决策过程以及带权值的线性赌博。我们的新型遗憾分解显示 FTRL 在正则化程序的 Hessian 矩阵上的温和假设下,可在多轮中保持稳定,并为线性赌徒提供了一种有效算法和接近最优的遗憾限制。
May, 2023
研究了拥有部分信息反馈的对抗 (非随机) 在线学习问题,在黑盒模型下能够获得如上小损失的概率,而其独特的设计使它在更多应用如半强盗问题和上下文强盗问题中得到有效的应用,并且能够提供一些之前无法获得的最优保证。
Nov, 2017