针对最佳臂识别问题,本文提出了一种基于阈值的最优排名算法,通过对强度的函数分配进行采样来识别最佳臂,分析表明该算法在极限情况下是最优的。
Mar, 2024
研究了多臂赌博机中的最佳臂辨识问题,提出了一个基于顺序淘汰算法的通用框架,并基于采样机制和每轮淘汰臂数量提出了性能评估指标,设计了一种按剩余臂数的非线性函数划分预算的算法,能够在纯探索场景下获得改进的理论保证和实验性能。
Sep, 2016
在贝叶斯设置下,我们研究了固定置信度最佳臂识别问题。我们证明了传统的 FC-BAI 算法在贝叶斯设置下会导致任意次优的性能,并且介绍了一种连续淘汰的变体,其性能与下界匹配,仅有一个对数因子的差距。模拟实验验证了理论结果。
Feb, 2024
本文介绍了一种基于贝叶斯方法的多臂赌博机最佳臂识别优化方法,其着重于建模与多臂之间的相关性,相比已有的方法在允许的函数评估数目较小时能够取得更优的效果,在自动机器学习工具箱等实际应用中表现良好。对多种方法进行对比分析,阐明了它们不同特征之间的相对优劣。
Mar, 2013
研究最优臂辨识问题,发现新算法和上下限优化,并提出一个新的关于最优样本复杂度的猜想。
Nov, 2015
本文介绍了使用贝叶斯算法的 Thompson Sampling 原则,旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优,并展现了一些理想的特性,但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。
Nov, 2011
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
最近在许多实际场景中出现了多臂赌博问题,其中由于代理人等待反馈的时间有限,必须对臂进行批量抽样。这些应用包括生物实验和在线营销。当臂的数量很大而批次的数量很小时,问题进一步复杂化。我们考虑了批量多臂赌博问题中的纯探索。我们引入了一个通用的线性规划框架,可以将不同理论设置中的目标纳入其中,以便在最佳臂识别中使用。线性规划导致了一个两阶段算法,可以实现良好的理论性能。通过数值研究,我们证明了该算法与某些 UCB 型或 Thompson 抽样方法相比也具有良好的性能。
Dec, 2023
在具有有限个臂的不安定多臂赌博问题中,通过分析某个马尔可夫决策过程及其状态 - 行动访问比例,确定最佳臂的策略和相应的期望停止时间,从而在有限的样本数、有限错误概率的条件下达到最佳臂的识别。
Oct, 2023
我们研究了基于线性奖励的鲁棒最佳臂识别问题(RBAI)。选择近乎最佳的鲁棒臂是我们的主要目标,该过程涉及每轮选择臂并通过探索潜在对手行动来评估其鲁棒性,尤其适用于使用模拟器并寻找实际转移问题中的鲁棒解。我们提出了基于实例的线性奖励的鲁棒最佳臂识别问题的下界,并提出了静态和自适应赌博算法,其样本复杂度与下界相匹配。在合成实验中,我们的算法有效地识别出最佳的鲁棒臂,并与 “预言家” 策略表现相似。作为应用,我们研究了糖尿病护理以及学习对标准计算器不准确的胰岛素剂量建议的过程。我们的算法在识别不同年龄段患者的鲁棒剂量值方面证明了其有效性。
Nov, 2023