Dec, 2023

组合随机贪心赌博机

PDF
TL;DR我们提出了一种新颖的组合性随机贪婪的赌博算法 (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 的增长，性能差距也增大。
combinatorial stochastic-greedy banditcombinatorial multi-armed banditstochastic-explore-then-commit approachregret boundonline constrained social influence maximization
发现论文，激发创造
  • 基于随机贪心学习的非单调随机次模最大化全博弈反馈

    本文研究具有完全机器人反馈和随机奖励的无限制组合多臂武器匪徒问题，提出随机贪心学习算法 (RGL)，证明其对于时间区间 T 和武器数 n，达到 1/2 遗憾上限 Õ(T^(2/3))，并在实验中展示了其对于非次模和次模设置都优于其他全机器人变体。

    Feb, 2023

  • 阻断赌徒

    考虑到重复使用某些选项可能是不可取的或不可行的，本文提出了一种新颖的随机多臂赌博机设置，并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法，但它设计了一种贪婪算法和一种基于 UCB 的算法，具有一定的优异性。

    Jul, 2019

  • 组合赌博机再审

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

    Feb, 2015

  • 贪心算法在多臂老虎机问题中的不合理有效性

    研究了贝叶斯多臂赌博问题的多臂区间，证明了对于設計最优策略子采样至关重要，提出了一种新型的无偿探索方法，即对奖励分布的尾事件进行无偿探索，使用模拟数据和真实数据测试后发现贪婪算法表现更佳。

    Feb, 2020

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

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

    Feb, 2020

  • 安全线性随机赌博机

    本文介绍了一个安全的线性随机挑战模型，其中学习器在每一阶段都需要选择一个预期奖励不小于预先确定的（安全）阈值的臂，以高概率。我们假设学习器最初掌握的是一个已知为安全但不一定最优的臂的知识。基于此假设，介绍了一种学习算法，它将已知的安全臂与探索性臂系统地结合起来，以便随时间安全地扩展安全臂集，同时促进后续阶段的安全贪婪利用。除了确保在每个播放阶段满足安全约束之外，所提出的算法还表现出一种预期的遗憾，在播放 T 个阶段后不超过 O（sqrt（T）log（T））

    Nov, 2019

  • 随机组合半赌博机的紧急遗憾上限

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

    Oct, 2014

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

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

    Oct, 2018

  • 非平稳环境下的组合半赌博算法

    该研究探讨了非静态组合半强盗问题，研究了在动态和切换的情况下，算法所能达到的最佳后悔上限以及需要提前了解的参数，并提供了无需先知参数的算法。

    Feb, 2020

  • 基于贝叶斯设置的组合高斯过程赌臂问题：理论与能效导航应用

    研究探究了具有时间变化的臂可用性的组合高斯过程半 - 算法问题，提出了三种基于高斯过程的算法 (即 GP-UCB、Bayes-GP-UCB 和 GP-TS) 的贝叶斯遗憾界，对综合合成和实际路网进行了实验研究，并发现上下文高斯过程模型在先验信息的信息度量上的遗憾值较低。

    Dec, 2023