多臂赌博机的组合纯探索问题以及实数动作类的解决方法
该研究提出了一种通用的组合多臂赌博问题框架,将未知分布的基础臂组成超级臂进行玩耍,进一步探讨了更多可能基于已激发臂的结果触发概率的扩展,旨在通过在线学习算法实现最小化(α,β)-逼近遗憾。
Jul, 2014
本文提出一种基于启发式算法的无参数算法,用于解决特定的组合纯探索随机赌博机问题,以寻找一组平均值高于给定阈值的摇臂,满足给定精度和一定的时间限制,并证明该算法是情况下的最优解决方案,并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题,并构建了最优策略。
May, 2016
本文研究了随机多臂老虎机的组合纯探索问题,提出了一种新的样本复杂度的下界和一种新的抽样算法,并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外,我们还提出了更通用的问题,并针对其提供了样本复杂度的上下界。
Jun, 2017
研究使用尽可能少的臂样本来确定具有最大奖励决策的自适应学习算法,解决具有连续可分离奖励函数的组合纯探索问题, 并分析了其样本复杂度, 并且给出了可以处理非线性奖励函数的示例。
May, 2018
本文研究了基于组合纯探索的对决党卫军(CPE-DB)问题,针对Borda获胜者和Condorcet获胜者情况,提出了多种算法,包括多臂匪徒问题(CPE-MAB)的算法和重要性采样算法。针对Condorcet获胜者问题,提出了一种全项式时间逼近法(FPTAS),并利用其作为Oracle设计了一种新的纯探索算法CAR-Cond,其每轮运行时间为多项式时间,从而实现了在CPE-DB中识别Condorcet获胜者的算法首次达到多项式时间复杂度。
Jun, 2020
我们研究了多臂赌博机问题的实值组合纯探索(R-CPE-MAB)问题。我们引入了一种名为广义汤普森采样探索(GenTS-Explore)算法,它是第一个能够在动作集的大小指数级增长时仍然有效的算法。我们还引入了一个新颖的问题相关样本复杂性下界,并证明GenTS-Explore算法实现了最优的样本复杂性,仅存在一个与问题相关的常数因子。
Aug, 2023
在固定预算环境下,我们研究了多臂赌博机的实值组合纯探索问题。我们提出了Combinatorial Successive Asign(CSA)算法,该算法可以在动作类别的大小与臂的数量成指数关系时,找到最佳动作。我们证明了CSA算法的错误概率上界与下界在指数的对数因子上匹配。然后,对于动作类别大小为多项式的情况,我们引入了另一个算法Minimax Combinatorial Successive Accepts and Rejects(Minimax-CombSAR),并证明该算法是最优的,与一个下界相匹配。最后,我们通过与先前方法的实验比较,证明了我们的算法表现更好。
Oct, 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