量子厚尾赌博机
本文提出了一种分布无关、数据驱动的上置信界(UCB)算法,结合最近发展的重新抽样中位数法(RMM)方法,对称奖励分布的研究中生成近乎最优的后悔边界,即使是重尾分布。
Jun, 2024
本文考察了当奖励分布具有 1+ε 阶矩时的多臂赌博问题,通过定义基于更精细的估计器的采样策略,如截断经验均值、Catoni 的 M - 估计和均值中位数估计器,证明了二阶矩(有限方差)足以获得与次高斯奖励分布同阶的悔恨界。
Sep, 2012
通过引入量子高斯过程 - 置信上界(Q-GP-UCB)算法,我们得到了第一个 BO 算法,可以在经典设置中将遗憾上界压缩为 O(对数多项式级别的 T),明显小于其遗憾下界 Omega(sqrt(T))。
Oct, 2023
本文提出了针对均值 - 方差 MAB 问题的 Thompson 抽样算法,并在更少的假设条件下提供了高斯和伯努利 bandit 的全面损失分析。我们的算法在各种参数配置下都达到了最好的已知损失边界。
Feb, 2020
本文研究了在风险厌恶的多臂老虎机问题中使用收益的均值和方差作为风险度量,并证明了 UCB 策略和 DSEE 策略可以实现收益方面的最优表现,且模型特定和模型无关的遗憾都有下界。
Apr, 2016
文章研究了一个量子计算版本的多臂老虎机问题,使用相干的 Oracle 访问状态,用 amplitudes 编码每个臂的奖励概率。特别地,作者提出了一种基于可变时间幅度放大和估计,用 Θ(| 根号 (n)| 乘以 | 根号 ∑_i=2^n Δ^(-2)_i|) 次量子查询可以找到最佳臂的算法。这个算法与经典算法相比,速度提升了一个平方级别。作者也证明了相匹配的量子下界(多项式对数因子)
Jul, 2020
该研究探讨具有随机延迟的随机多臂赌博问题,在考虑了奖励相关延迟和奖励无关延迟两种情况下,提出了接近最优的算法,并在延迟分布的分位数上增加了附加依赖性,而不需要假设延迟分布来自任何参数化的分布族,还允许无限延迟的情况。
Jun, 2021