次线性时间下的拟阵半赌博问题
本研究通过将实现优化为特定的子模最大化,并设计适应的近似程序,提供了首个可以依赖奖励结构来改善遗憾界限的有效算法。这一改进将状态 - of-the-art 的无间隙遗憾界限显著提高了 sqrt (m)/log m 倍。最后,我们证明了我们的改进如何转化为更普遍的预算组合半强盗。
Feb, 2019
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
本研究探讨组合良带 (Bandits) 的算法,针对其大小批次 (K) 对后悔束缚的依赖性进行优化,发现一种可替代平滑性条件的新型触发概率和方差调节 (TPVM) 条件,进行后悔分析并提出基于置信区间和方差的 BCUCB-T 算法,将大小批次 (K) 的项降低至对数级别,并在非触发 CMAB 中将其完全去除。实验结果表明,我们的算法在不同领域具有优越的性能。
Aug, 2022
本研究利用 UCB-like 算法解决计算和采样高效的随机组合半贝叶斯在线学习问题,并分析了其 $n$ 步遗憾的上界,这里的遗憾是指最优解和次优解之间的预期回报差距。
Oct, 2014
本篇论文提出了 2 种线性 bandits 算法,并利用最大内积搜索问题求解臂的选择,从而解决了针对极大臂数和缓慢变化的应用困难,扩展了现有的近似最大内积搜索的求解算法并实现了子线性复杂度及减小了损失。应用于在线学习问题中,该算法时间复杂度良好且表现出与线性时间基线相似的遗憾值。
Mar, 2021
研究了分段不稳定组合半汉迪问题,提出了一种名为 GLR-CUCB 的算法,该算法将高效组合半汉迪算法 CUCB 与几乎无参数的变化点检测器 GLRT 相结合,其遗憾值具有渐近界,且比现有算法表现优异
Aug, 2019
本文研究了随机组合多臂赌博机框架,提出了一种名为 SDCB 的新算法,该算法估计底层随机变量的分布和它们的随机显著性置信区间,并证明了 SDCB 可以实现 O (logT) 的分布相关遗憾和 $ ilde {O}(√T)$ 的分布无关遗憾,并将所得结果应用于 $K$-MAX 问题。
Oct, 2016
通过结合 bandit 和 matroid 的思想,本篇论文提出了一种新型组合赌博算法 ——matroid bandits,它的目标是在 matroid 中最大化一个随机的初始未知的模块化函数,并提供了一种切实可行的算法 —— 乐观 matroid 最大化(OMM),证明了两个上界,gap-dependent 和 gap-free,时间复杂度均为亚线性,与其他相关量最多线性相关。同时在三个实际问题上测试,证明了该方法是有效的。
Mar, 2014
该研究提出了一种通用的组合多臂赌博问题框架,将未知分布的基础臂组成超级臂进行玩耍,进一步探讨了更多可能基于已激发臂的结果触发概率的扩展,旨在通过在线学习算法实现最小化(α,β)- 逼近遗憾。
Jul, 2014