基于矩阵约束的多臂赌博纯探索
本文研究了随机多臂老虎机的组合纯探索问题,提出了一种新的样本复杂度的下界和一种新的抽样算法,并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外,我们还提出了更通用的问题,并针对其提供了样本复杂度的上下界。
Jun, 2017
本文提出了两种渐近最优的算法,基于 Track-and-Stop 方法和博弈论方法,用于寻找多臂赌博机环境中具有一定置信度的最优策略,特别考虑了带有线性约束的情况,并探讨了约束难度对问题的影响。
Jun, 2023
研究了 matroid semi-bandits 问题,提出了一个计算更便宜的算法 FasterCUCB,基于对内积权重的近似最大重量基的动态维护,能够保证与 CUCB 相匹配的遗憾上限,用来最大化期望累积线性回报。
May, 2024
本文提出了第一个完全自适应的算法用于求解线性赌博机中的最优选择问题,并且其采样复杂度与已有算法相当。此外,通过模拟实验表明,在合成和真实数据集上均远优于现有的方法。
Oct, 2017
本研究通过将实现优化为特定的子模最大化,并设计适应的近似程序,提供了首个可以依赖奖励结构来改善遗憾界限的有效算法。这一改进将状态 - of-the-art 的无间隙遗憾界限显著提高了 sqrt (m)/log m 倍。最后,我们证明了我们的改进如何转化为更普遍的预算组合半强盗。
Feb, 2019
通过结合 bandit 和 matroid 的思想,本篇论文提出了一种新型组合赌博算法 ——matroid bandits,它的目标是在 matroid 中最大化一个随机的初始未知的模块化函数,并提供了一种切实可行的算法 —— 乐观 matroid 最大化(OMM),证明了两个上界,gap-dependent 和 gap-free,时间复杂度均为亚线性,与其他相关量最多线性相关。同时在三个实际问题上测试,证明了该方法是有效的。
Mar, 2014
本文提出一种基于启发式算法的无参数算法,用于解决特定的组合纯探索随机赌博机问题,以寻找一组平均值高于给定阈值的摇臂,满足给定精度和一定的时间限制,并证明该算法是情况下的最优解决方案,并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题,并构建了最优策略。
May, 2016
本研究探讨了组合多臂赌博的后悔下界,并证明了在所有光滑奖励函数下,这种下界都是合理的,并且根据 Merlis 和 Mannor(2019)提出的 Gini 加权平滑度参数确定单调奖励函数的下界。
Feb, 2020