研究了在随机多臂赌博游戏中受拟阵约束(Best-Basis)的纯勘探问题,提供了几乎最优样本复杂度的算法,以确定拟阵的基并达到最大总权重。
May, 2016
本文提出一种基于启发式算法的无参数算法,用于解决特定的组合纯探索随机赌博机问题,以寻找一组平均值高于给定阈值的摇臂,满足给定精度和一定的时间限制,并证明该算法是情况下的最优解决方案,并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题,并构建了最优策略。
本文研究了随机多臂老虎机的组合纯探索问题,提出了一种新的样本复杂度的下界和一种新的抽样算法,并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外,我们还提出了更通用的问题,并针对其提供了样本复杂度的上下界。
Jun, 2017
介绍了一类广泛的随机赌博问题,其中将臂与相应的奖励映射的函数具有一些已知的结构特性。推导了这些问题的渐近特定情况下的遗憾下界,并且开发了OSSB算法,其遗憾匹配了这个基本极限。通过数值实验展示了OSSB的效率,并且证明OSSB优于包括汤普森取样在内的现有算法。
Nov, 2017
提出了多项式时间适应性算法和多项式时间算法,以针对全带回馈和非线性奖励函数等多种情况进行组合纯探索问题的处理,对样本复杂度进行了分析。
Jun, 2020
本文研究了基于组合纯探索的对决党卫军(CPE-DB)问题,针对Borda获胜者和Condorcet获胜者情况,提出了多种算法,包括多臂匪徒问题(CPE-MAB)的算法和重要性采样算法。针对Condorcet获胜者问题,提出了一种全项式时间逼近法(FPTAS),并利用其作为Oracle设计了一种新的纯探索算法CAR-Cond,其每轮运行时间为多项式时间,从而实现了在CPE-DB中识别Condorcet获胜者的算法首次达到多项式时间复杂度。
本篇论文提出了一种用于解决真实行动类别的组合性纯探索算法,并通过引入广义宽度概念表明该算法在样本复杂度和 R-CPE-MAB 中的应用。
Jun, 2023
该论文考虑了纯探索问题回报序列的低秩结构,提出了一种分离设置的探索策略,并通过利用奖励向量的核信息,提供了高效算法,同时展示了多臂赌博机问题下纯探索的上下界。
我们研究了多臂赌博机问题的实值组合纯探索(R-CPE-MAB)问题。我们引入了一种名为广义汤普森采样探索(GenTS-Explore)算法,它是第一个能够在动作集的大小指数级增长时仍然有效的算法。我们还引入了一个新颖的问题相关样本复杂性下界,并证明GenTS-Explore算法实现了最优的样本复杂性,仅存在一个与问题相关的常数因子。
Aug, 2023
在固定预算环境下,我们研究了多臂赌博机的实值组合纯探索问题。我们提出了Combinatorial Successive Asign(CSA)算法,该算法可以在动作类别的大小与臂的数量成指数关系时,找到最佳动作。我们证明了CSA算法的错误概率上界与下界在指数的对数因子上匹配。然后,对于动作类别大小为多项式的情况,我们引入了另一个算法Minimax Combinatorial Successive Accepts and Rejects(Minimax-CombSAR),并证明该算法是最优的,与一个下界相匹配。最后,我们通过与先前方法的实验比较,证明了我们的算法表现更好。
Oct, 2023