NIPSFeb, 2015

组合赌博机再审

PDF
TL;DR本文研究了随机和对抗性组合多臂赌博问题。在随机情况下，我们提出了一种特定问题的遗憾下限，并讨论了其与决策空间维数的比例关系。我们提出了 ESCB 算法，该算法能有效地利用问题的结构，并对其遗憾进行了有限时间分析。ESCB 具有比现有算法更好的性能保证，并在实践中显着优于这些算法。在对抗性情况下，我们提出了 CombEXP 算法，其遗憾比比现有最先进算法相同，但对于某些组合问题具有较低的计算复杂度。
stochasticadversarialmulti-armed banditregretalgorithm
发现论文，激发创造
  • 随机组合半赌博机的紧急遗憾上限

    本研究利用 UCB-like 算法解决计算和采样高效的随机组合半贝叶斯在线学习问题，并分析了其 $n$ 步遗憾的上界，这里的遗憾是指最优解和次优解之间的预期回报差距。

    Oct, 2014

  • 组合多臂赌博机的紧密下界

    本研究探讨了组合多臂赌博的后悔下界，并证明了在所有光滑奖励函数下，这种下界都是合理的，并且根据 Merlis 和 Mannor（2019）提出的 Gini 加权平滑度参数确定单调奖励函数的下界。

    Feb, 2020

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

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

    Jan, 2018

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

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

    Apr, 2024

  • 组合随机贪心赌博机

    我们提出了一种新颖的组合性随机贪婪的赌博算法 (SGB)，用于组合多臂赌博问题。该算法在没有额外信息的情况下，仅观察到每个时间步 t∈[T] 时选择的一组 n 个臂的联合奖励。SGB 采用了一种优化的随机探索再确认的方法，并且专门设计用于具有大量基本臂的情景。与现有方法在每个选择步骤中都会探索整个未选择基本臂集不同，我们的 SGB 算法仅对未选择的臂进行优化比例的抽样，并从该子集中选择行动。我们证明了对于单调随机次模性奖励，我们的算法实现了 (1-1/e) 的遗憾边界，其复杂度为 O (n^(1/3) k^(2/3) T^(2/3) log (T)^(2/3))，在基数约束 k 方面优于最先进的方法。此外，我们在在线受限社交影响最大化的背景下对我们的算法进行实证评估。我们的结果表明，我们提出的方法始终优于其他算法，并且随着 k 的增长，性能差距也增大。

    Dec, 2023

  • 适应离线算法来解决带有固定反馈的组合多臂赌博问题的框架

    该研究针对随机、组合式多臂老虎机问题，提出了一种将离线算法转化为基于有限老虎机反馈的子线性 α 遗憾策略的框架，并将其应用于离散优化问题中的基数问题和背包约束问题中获得了良好的表现。

    Jan, 2023

  • 去中心化协作随机赌博机

    本文研究了多臂赌博机问题在网络上的去中心化协作，采用加速一致性过程来计算所有智能体对每个臂的平均奖励，该算法采用上置信区间来决策，能够达到更好的回归界，同时不需要过多的底层网络信息。

    Oct, 2018

  • 优化置信区间上界算法：改进有限臂赌博机的遗憾

    提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法，同时具有最优问题依赖性遗憾和最坏情况遗憾。

    Jul, 2015

  • 随机和非随机多臂赌博机问题的遗憾分析

    本调查报告主要关注于多臂赌博问题中两个极端情况的分析，即独立同分布回报和对抗性回报，并对有限行为、情境赌博模型等进行了分析。

    Apr, 2012

  • 已知协方差的组合半赌博算法

    介绍了一个基于线性回归的优化算法，用于解决组合随机半汉带问题中的依赖关系，分析证明其是最优的，并且推出了一个与被拉动手臂数的对数因子成比例的新的下界。

    Dec, 2016