线性最佳臂识别中的安全性价格
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
本文研究线性贝叶斯最优化模型中的最优臂选择问题,提出样本分配策略来识别具有固定置信度的最优臂,并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值,并将其与最优实验设计中使用的 G - 最优准则进行比较。
Sep, 2014
本文介绍了一个安全的线性随机挑战模型,其中学习器在每一阶段都需要选择一个预期奖励不小于预先确定的(安全)阈值的臂,以高概率。我们假设学习器最初掌握的是一个已知为安全但不一定最优的臂的知识。基于此假设,介绍了一种学习算法,它将已知的安全臂与探索性臂系统地结合起来,以便随时间安全地扩展安全臂集,同时促进后续阶段的安全贪婪利用。除了确保在每个播放阶段满足安全约束之外,所提出的算法还表现出一种预期的遗憾,在播放 T 个阶段后不超过 O(sqrt(T)log(T))
Nov, 2019
本文提出了两种渐近最优的算法,基于 Track-and-Stop 方法和博弈论方法,用于寻找多臂赌博机环境中具有一定置信度的最优策略,特别考虑了带有线性约束的情况,并探讨了约束难度对问题的影响。
Jun, 2023
最近在许多实际场景中出现了多臂赌博问题,其中由于代理人等待反馈的时间有限,必须对臂进行批量抽样。这些应用包括生物实验和在线营销。当臂的数量很大而批次的数量很小时,问题进一步复杂化。我们考虑了批量多臂赌博问题中的纯探索。我们引入了一个通用的线性规划框架,可以将不同理论设置中的目标纳入其中,以便在最佳臂识别中使用。线性规划导致了一个两阶段算法,可以实现良好的理论性能。通过数值研究,我们证明了该算法与某些 UCB 型或 Thompson 抽样方法相比也具有良好的性能。
Dec, 2023
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作 “Track-and-Stop” 的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
我们研究了基于线性奖励的鲁棒最佳臂识别问题(RBAI)。选择近乎最佳的鲁棒臂是我们的主要目标,该过程涉及每轮选择臂并通过探索潜在对手行动来评估其鲁棒性,尤其适用于使用模拟器并寻找实际转移问题中的鲁棒解。我们提出了基于实例的线性奖励的鲁棒最佳臂识别问题的下界,并提出了静态和自适应赌博算法,其样本复杂度与下界相匹配。在合成实验中,我们的算法有效地识别出最佳的鲁棒臂,并与 “预言家” 策略表现相似。作为应用,我们研究了糖尿病护理以及学习对标准计算器不准确的胰岛素剂量建议的过程。我们的算法在识别不同年龄段患者的鲁棒剂量值方面证明了其有效性。
Nov, 2023
本文提出了一种基于 UCB 策略的新算法 Safe-LUCB,用于解决多臂赌博问题中考虑安全限制的约束,该算法具有探索和利用两个阶段,并控制遗憾值增长,提供了一般遗憾上界及与最佳行动位置有关的问题相关遗憾上界。
Aug, 2019
探讨了利用 Adaptive Constraint Learning 算法解决具有昂贵人类偏好未知约束的序列决策问题,特别是在驾驶行为中体现的安全和舒适性约束的识别,该算法在驾驶模拟中比其他算法更加高效
Jun, 2022