一种用于PAC组合纯探索的快速算法
通过系统的约束求解器的黑盒方案,结合搜索空间的统一探索,我们提出了一种新的采样技术,可以克服采样过程中的诸多困难,形成了自然的近似模型计数技术。
Oct, 2012
本文研究了随机多臂老虎机的组合纯探索问题,提出了一种新的样本复杂度的下界和一种新的抽样算法,并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外,我们还提出了更通用的问题,并针对其提供了样本复杂度的上下界。
Jun, 2017
研究使用尽可能少的臂样本来确定具有最大奖励决策的自适应学习算法,解决具有连续可分离奖励函数的组合纯探索问题, 并分析了其样本复杂度, 并且给出了可以处理非线性奖励函数的示例。
May, 2018
在研究中,我们将n个武器的随机多臂强盗问题与PAC设定结合起来,提出了一种有效的方法来解决从最佳m个武器中准确识别k个武器的问题,其中1≤k≤m,同时给出了一些相关算法和下界。
Jan, 2019
本文研究了基于组合纯探索的对决党卫军(CPE-DB)问题,针对Borda获胜者和Condorcet获胜者情况,提出了多种算法,包括多臂匪徒问题(CPE-MAB)的算法和重要性采样算法。针对Condorcet获胜者问题,提出了一种全项式时间逼近法(FPTAS),并利用其作为Oracle设计了一种新的纯探索算法CAR-Cond,其每轮运行时间为多项式时间,从而实现了在CPE-DB中识别Condorcet获胜者的算法首次达到多项式时间复杂度。
Jun, 2020
本文研究了纯探索问题中具有无限多臂的赌博机问题,针对固定置信和固定预算两种情形,提出了两种算法,分别以最小的期望和固定样本复杂度为目标,最终准确选择一个高质量臂,使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$,并给出了理论证明。
Jun, 2023
本篇论文提出了一种用于解决真实行动类别的组合性纯探索算法,并通过引入广义宽度概念表明该算法在样本复杂度和 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