本文介绍了多臂老虎机模型的性能表现,并提供了特定情况下的下限和匹配算法。此外,还提供了改进的序贯停止规则以及两个独立的技术结果。
Jul, 2014
本研究提出了一种GOB模型的GMRF扩展方法,结合Thompson采样算法,解决了通过传递信息来实现推荐系统等中大规模难题,能够在不需要聚类假设的情况下扩展到更大的图形,并提出了一个学习图形的启发式方法。
Mar, 2017
本研究提出了一种在线聚类的赌博算法,通过允许用户频率的非统一分布,并使用简单的集合结构来表示聚类,提出了一种更有效的算法,并证明了该算法的遗憾界可以不考虑用户的最小频率。在合成和真实数据集的实验中,新算法相对于现有方法具有一定的优势。
Feb, 2019
本研究通过引入Hadamard矩阵,提出了一种通用的CSAR算法用于解决top-k组合赌博问题,针对完全赌博反馈,该算法仅观察奖励总和,在两个变体的算法中,第一个最小化样本复杂性,第二个最小化遗憾,并证明了样本复杂度的下限,该复杂度对于$k=O(1)$来说是紧的。最后,通过实验证明该算法优于其他方法。
May, 2019
该论文提出了基于多级 Thompson 抽样方案的算法,用于解决具有线性预期收益的上下文相关多臂赌博机及其聚类武器的问题。同时,理论和实证表明,利用特定的集群结构可以显著改善遗憾并降低计算成本。
Sep, 2021
本文研究了带有错误预言机的聚类问题,利用多臂赌博机算法解决该问题的上下界。
Jul, 2022
提出了聚类多臂老虎机在用户模型未正确规定的情况下的问题,设计了两种鲁棒性算法,能适应不准确的用户偏好评估和模型错误导致的聚类问题,证明了我们算法的遗憾上限。实验证明我们对之前算法的优越性。
Oct, 2023
在这篇论文中,我们考虑了稀疏背景下的上下文强化学习问题,其中臂特征通过稀疏参数的内积影响奖励。我们证明了贪心算法适用于更广泛的臂特征分布,提出了与高斯混合、离散和径向分布相关的新分布类,确保样本的多样性,从而为贪心策略在非常广泛的臂特征分布上提供了理论保证。
Dec, 2023
在本文中,我们研究了主动聚类问题(ACP)。一个学习者与具有d维亚高斯反馈的N臂随机赌博机交互。存在一致维向量的K个组将臂分为隐藏分区,同一组中的臂共享相同的均值向量。学习者的任务是以最小的预算发现这个隐藏分区,并且误差概率小于一个预定的常数δ。在本文中,我们(i)推导了预算的非渐近下界,(ii)提出了计算高效的ACB算法,其预算与大多数情况下的下界相匹配。我们改进了统一采样策略的性能。重要的是,与批处理设置不同,我们证明主动设置中不存在计算信息差距。
Jun, 2024
本文研究了多臂赌博机框架中的代表臂识别问题,旨在在已知臂的聚类的情况下尽可能少地抽取臂来可靠识别每个聚类中的指定数量的臂。提出了两种基于置信区间的算法,并通过实证比较证明了其在合成数据和真实数据集上的优越性能,这为解决代表臂识别问题提供了新的方法和理论支持。
Aug, 2024