IJCAIApr, 2022

具有复合匿名延迟反馈的有界内存对抗性赌博机

PDF
TL;DR本研究探讨了具有复合匿名延迟反馈的对抗性赌徒问题，证明了非遗忘环境下会发生伪遗憾现象。但我们提出了一个包装器算法，在某些对抗赌徒问题上获得了 o (T) 策略遗憾。尤其对于 K-armed bandit 和 bandit 凸优化问题，我们的算法的策略遗憾边界为 Ο(T^(2/3))。 此外，我们还证明了 K-armed bandit 的匹配下界，即使在损失序列是遗忘的但延迟非遗忘的情况下也能实现。
adversarial bandit problemanonymous delayed feedbackpseudo regretpolicy regretloss sequence
发现论文，激发创造
  • 带有复合匿名反馈的非随机赌博机

    研究非随机赌博环境下的遗憾界，提出了基于 FTRL with Tsallis entropy 的算法转化方法。

    Dec, 2021

  • 具有延迟组合匿名赌徒反馈的随机次模赌徒算法

    本文研究了具有随机次模（期望上）奖励和完全 bandit 延迟反馈的组合多臂老虎机问题，其中假定延迟反馈是组合匿名的，同时研究了有界择逊、随机独立和随机条件独立三种延迟反馈模型，给出了每种延迟模型的后悔界限，忽略问题相关参数，证明所有延迟模型的后悔界限为 $ ilde {O}(T^{2/3} + T^{1/3} u)$，其中 $T$ 为时间跨度，$ u$ 根据三种情况有不同的定义，因此在所有三种延迟模型中表明了延迟对后悔的添加项，该算法被证明优于具有延迟复合匿名反馈的其他全 bandit 方法。

    Mar, 2023

  • 带有延迟、汇聚匿名反馈的赌博机

    研究了一种带有延迟的聚合匿名反馈的赌博机问题，表明在期望延迟已知的情况下，可以通过提供的算法，在硬的、延迟聚合匿名反馈设置中维持类似于非匿名问题的后悔成本，但在延迟不确定情况下，增加了对数因子或加性方差项的后悔成本。

    Sep, 2017

  • 对抗性多臂老虎机中的延迟和数据的适应

    本文考虑在延迟反馈下的敌对多臂老虎机问题，并分析了一些通过仅使用决策时可用的信息 (关于损失和延迟) 来调整步长的 Exp3 算法变体，从而获得适应观察到的 (而不是最坏情况下的) 延迟和 / 或损失序列的遗憾保证。最后，我们介绍了 AdaGrad 风格的版本的算法，该算法通过观察到的 (延迟的) 损失进行适应，而不仅仅是适应于累积延迟 (该算法要求先验上限）。

    Oct, 2020

  • 具有无限制延迟的非随机多臂赌博机

    本文研究带有延迟反馈的多臂老虎机问题，证明了先前的算法在延迟是变量但有上界的情况下具有较好的表现，提出了一种新算法通过一个跳过具有过度大延迟的步骤的 wrapper 来降低了对上界的要求，同时构造了一种新的加倍方案，从而放宽了对时间和延迟知识的要求。提出的算法解决了丰富的应用场景问题并达到了合理的预期表现。

    Jun, 2019

  • 带有延迟反馈的强化学习优化中的改进后悔度

    我们研究了具有延迟反馈的强凸波段优化问题，通过精细地利用延迟波段反馈的阻塞更新机制，我们的算法改进了损失边界并将其与延迟设置下的传统波段梯度下降（BGD）算法相匹配。

    Feb, 2024

  • 具有切换成本的对抗组合赌博机

    通过分析具有切换成本的对抗组合赌博问题，本论文推导了极小后悔的下界并设计了相应算法，同时考虑了赌博反馈和半赌博反馈两种情况。

    Apr, 2024

  • 延迟赌博机：何时中间观察有帮助？

    研究一种带有延迟反馈和中间观测的多臂老虎机模型，表明状态对损失的映射决定问题的复杂性，给出在不同映射下的后悔率上限，实验验证算法的有效性。

    May, 2023

  • 组合半弦臂算法的一阶遗憾上界

    本文研究了在线组合优化问题中的半盲反馈，提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率，在部分反馈方案中首次实现了此类保证，并在组合设置中首次实现了此类保证。

    Feb, 2015

  • 可证明高效的高维度分批反馈赌博学习

    我们研究具有批处理反馈的高维多臂上下文强化学习，其中在线交互的 T 步骤被分为 L 批次。针对稀疏或低秩结构的线性情况，我们设计了一种可证明的样本高效算法，使用仅 L = O (log T) 批次在稀疏情况下达到 O (s0^2 log^2 T) 遗憾，并在低秩情况下达到 O (r^2 log^2 T) 遗憾，此处 s0 和 r 分别为稀疏和低秩情况下奖励参数的稀疏度和秩，并省略涉及特征维度的对数因子。此外，我们还进行了合成和真实世界数据的实验证实。

    Nov, 2023