量子赌徒
文章研究了一个量子计算版本的多臂老虎机问题,使用相干的 Oracle 访问状态,用 amplitudes 编码每个臂的奖励概率。特别地,作者提出了一种基于可变时间幅度放大和估计,用 Θ(| 根号 (n)| 乘以 | 根号 ∑_i=2^n Δ^(-2)_i|) 次量子查询可以找到最佳臂的算法。这个算法与经典算法相比,速度提升了一个平方级别。作者也证明了相匹配的量子下界(多项式对数因子)
Jul, 2020
我们研究了基于线性奖励的鲁棒最佳臂识别问题(RBAI)。选择近乎最佳的鲁棒臂是我们的主要目标,该过程涉及每轮选择臂并通过探索潜在对手行动来评估其鲁棒性,尤其适用于使用模拟器并寻找实际转移问题中的鲁棒解。我们提出了基于实例的线性奖励的鲁棒最佳臂识别问题的下界,并提出了静态和自适应赌博算法,其样本复杂度与下界相匹配。在合成实验中,我们的算法有效地识别出最佳的鲁棒臂,并与 “预言家” 策略表现相似。作为应用,我们研究了糖尿病护理以及学习对标准计算器不准确的胰岛素剂量建议的过程。我们的算法在识别不同年龄段患者的鲁棒剂量值方面证明了其有效性。
Nov, 2023
在贝叶斯设置下,我们研究了固定置信度最佳臂识别问题。我们证明了传统的 FC-BAI 算法在贝叶斯设置下会导致任意次优的性能,并且介绍了一种连续淘汰的变体,其性能与下界匹配,仅有一个对数因子的差距。模拟实验验证了理论结果。
Feb, 2024
该研究提出了一种严格推广的最佳臂标识问题,即在中介者反馈下的最佳臂标识问题,首先推导并分析了与该中介者反馈场景相关的样本复杂度的统计下界,然后提出了一种顺序决策策略,用于根据学习者已知的中介者策略发现最佳臂,最终将这些结果扩展到学习者不知道中介者策略的情况,获得可比较的结果。
Aug, 2023
提出了一种新的随机多臂老虎机问题称为好臂识别,在解决好臂识别过程中面临独特的置信度的探索 - 利用困境并为此提出了一种算法以最小化每个过程的样本数量,该算法在样本复杂度上达到了理论下限并已通过实验得到验证。
Oct, 2017
在差分隐私约束下,研究固定预算探索期的线性赌臂问题,通过最大绝对确定性原则构建满足差分隐私约束的策略,得到其错误概率的上限和下限,并展示其与赌臂问题复杂性、亚最优的臂差异和差分隐私参数相关的指数级衰减特性。此外,该研究还提供了独立感兴趣且对其他赌臂问题的错误概率下限证明具有重要作用的一些辅助结果,填补了先前文献中固定预算探索期下差分隐私约束情况下最优臂识别的研究空白。
Jan, 2024
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020