Jun, 2020

对抗式多臂老虎机的组合纯探索

HTML
PDF
TL;DR本文研究了基于组合纯探索的对决党卫军（CPE-DB）问题，针对Borda获胜者和Condorcet获胜者情况，提出了多种算法，包括多臂匪徒问题（CPE-MAB）的算法和重要性采样算法。针对Condorcet获胜者问题，提出了一种全项式时间逼近法（FPTAS），并利用其作为Oracle设计了一种新的纯探索算法CAR-Cond，其每轮运行时间为多项式时间，从而实现了在CPE-DB中识别Condorcet获胜者的算法首次达到多项式时间复杂度。
发现论文，激发创造
  • 稀疏对决波段

    本文提出一种新的基于Borda准则的方法，解决了在多臂赌博机中的对抗赌博问题。通过压缩样本量和利用比较稀疏性的结构限制，我们提出了一种新的叫做Successive Elimination with Comparison Sparsity (SECS) 的算法，并在实验中对其进行了评估。结果表明，这种基于稀疏模型的新方法相对于标准方法能够获得显著的改进。

    Jan, 2015

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

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

    May, 2016

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

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

    Jun, 2017

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

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

    May, 2018

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

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

    Jun, 2020

  • 一种用于PAC组合纯探索的快速算法

    本文提出了一种新的在PAC设置下求解组合型纯探索问题的算法，其计算负担较小，可适用于拥有成千上万个手臂的问题，通过逐步准许手臂并基于问题的组合结构进行消除，以及少量的组合预言调用，提供了样本复杂性保证，并在实验中证明了在大型问题上的实用性。

    Dec, 2021

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

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

    Jun, 2023

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

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

    Aug, 2023

  • 在带有不确定关系的决斗伴侣竞争中识别科普兰得胜者

    通过研究三向反馈的对决问题，我们确定了一个学习算法的样本复杂度下限，提出了POCOWISTA算法，并证明了在特定条件下偏好概率的情况下，我们可以得到一个改进的样本复杂度。

    Oct, 2023

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

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

    Oct, 2023