Jun, 2017

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

PDF
TL;DR本文研究了随机多臂老虎机的组合纯探索问题，提出了一种新的样本复杂度的下界和一种新的抽样算法，并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外，我们还提出了更通用的问题，并针对其提供了样本复杂度的上下界。
stochastic multi-armed banditscombinatorial pure explorationsampling algorithmlower boundsoptimization
发现论文，激发创造
  • 针对 Top-k 臂选择的近乎最佳样本复杂度界限

    本文探讨了 Best-$k$-Arm 问题的样本复杂性边界，提出了一种新颖的复杂度度量方法和基于消除的算法，并展示了该算法的实例 - 边界下限和状态 - 界限的严格支配能力。

    Feb, 2017

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

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

    May, 2016

  • 关于最佳臂识别的最优样本复杂度

    研究最优臂辨识问题，发现新算法和上下限优化，并提出一个新的关于最优样本复杂度的猜想。

    Nov, 2015

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

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

    May, 2016

  • 最优探索与汤普森抽样同等难度

    该论文提出了一种利用采样和 argmax oracle 来实现指数收敛率的算法，以解决纯探索线性赌博问题，并证明了该算法在实践中与现有的渐近最优方法相当。

    Oct, 2023

  • 无限臂老虎机渐进最优纯探索

    本文研究了纯探索问题中具有无限多臂的赌博机问题，针对固定置信和固定预算两种情形，提出了两种算法，分别以最小的期望和固定样本复杂度为目标，最终准确选择一个高质量臂，使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$，并给出了理论证明。

    Jun, 2023

  • 通过解游戏进行非渐近纯探索

    本文提出了一种适用于纯探索问题和赌博机结构的不需完全解决优化问题的优化算法，并获得了对指数族的适应性和有限信心保证。

    Jun, 2019

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

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

    Oct, 2023

  • 多臂赌博机中最优臂选取的顺序消除算法

    研究了多臂赌博机中的最佳臂辨识问题，提出了一个基于顺序淘汰算法的通用框架，并基于采样机制和每轮淘汰臂数量提出了性能评估指标，设计了一种按剩余臂数的非线性函数划分预算的算法，能够在纯探索场景下获得改进的理论保证和实验性能。

    Sep, 2016

  • 线性赌博机探索的游戏化

    研究了线性随机机器人中的最佳臂标识，在标准多胳臂机器人中存在渐近最优算法，但是对于线性机器人中的最佳臂识别还没有出现这样的算法，本文提出了一种渐近最优算法。

    Jul, 2020