Oct, 2023

多臂赌博机的固定预算真值组合纯探索

HTML
PDF
TL;DR在固定预算环境下，我们研究了多臂赌博机的实值组合纯探索问题。我们提出了Combinatorial Successive Asign（CSA）算法，该算法可以在动作类别的大小与臂的数量成指数关系时，找到最佳动作。我们证明了CSA算法的错误概率上界与下界在指数的对数因子上匹配。然后，对于动作类别大小为多项式的情况，我们引入了另一个算法Minimax Combinatorial Successive Accepts and Rejects（Minimax-CombSAR），并证明该算法是最优的，与一个下界相匹配。最后，我们通过与先前方法的实验比较，证明了我们的算法表现更好。
发现论文，激发创造
  • 组合多臂老虎机及其对概率触发臂的扩展

    该研究提出了一种通用的组合多臂赌博问题框架，将未知分布的基础臂组成超级臂进行玩耍，进一步探讨了更多可能基于已激发臂的结果触发概率的扩展，旨在通过在线学习算法实现最小化（α，β）-逼近遗憾。

    Jul, 2014

  • 基于矩阵约束的多臂赌博纯探索

    研究了在随机多臂赌博游戏中受拟阵约束（Best-Basis）的纯勘探问题，提供了几乎最优样本复杂度的算法，以确定拟阵的基并达到最大总权重。

    May, 2016

  • 阈值赌博机问题的最优算法

    本文提出一种基于启发式算法的无参数算法，用于解决特定的组合纯探索随机赌博机问题，以寻找一组平均值高于给定阈值的摇臂，满足给定精度和一定的时间限制，并证明该算法是情况下的最优解决方案，并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题，并构建了最优策略。

    May, 2016

  • 组合型纯探索的近最优采样算法

    本文研究了随机多臂老虎机的组合纯探索问题，提出了一种新的样本复杂度的下界和一种新的抽样算法，并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外，我们还提出了更通用的问题，并针对其提供了样本复杂度的上下界。

    Jun, 2017

  • 具有连续可分离奖励函数的组合纯探索及其应用（扩展版）

    研究使用尽可能少的臂样本来确定具有最大奖励决策的自适应学习算法，解决具有连续可分离奖励函数的组合纯探索问题, 并分析了其样本复杂度, 并且给出了可以处理非线性奖励函数的示例。

    May, 2018

  • 带有完全赌博反馈的Top-k组合赌博

    本研究通过引入Hadamard矩阵，提出了一种通用的CSAR算法用于解决top-k组合赌博问题，针对完全赌博反馈，该算法仅观察奖励总和，在两个变体的算法中，第一个最小化样本复杂性，第二个最小化遗憾，并证明了样本复杂度的下限，该复杂度对于$k=O(1)$来说是紧的。最后，通过实验证明该算法优于其他方法。

    May, 2019

  • 全赌臂或部分线性反馈下的组合纯探索

    提出了多项式时间适应性算法和多项式时间算法，以针对全带回馈和非线性奖励函数等多种情况进行组合纯探索问题的处理，对样本复杂度进行了分析。

    Jun, 2020

  • 多臂赌博机的组合纯探索问题以及实数动作类的解决方法

    本篇论文提出了一种用于解决真实行动类别的组合性纯探索算法，并通过引入广义宽度概念表明该算法在样本复杂度和 R-CPE-MAB 中的应用。

    Jun, 2023

  • 用于多臂赌博机的实值组合纯探索的汤普森抽样

    我们研究了多臂赌博机问题的实值组合纯探索（R-CPE-MAB）问题。我们引入了一种名为广义汤普森采样探索（GenTS-Explore）算法，它是第一个能够在动作集的大小指数级增长时仍然有效的算法。我们还引入了一个新颖的问题相关样本复杂性下界，并证明GenTS-Explore算法实现了最优的样本复杂性，仅存在一个与问题相关的常数因子。

    Aug, 2023

  • 组合随机贪心赌博机

    我们提出了一种新颖的组合性随机贪婪的赌博算法 (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