AAAIJul, 2020

多臂赌博机的量子探索算法

PDF
TL;DR文章研究了一个量子计算版本的多臂老虎机问题，使用相干的 Oracle 访问状态，用 amplitudes 编码每个臂的奖励概率。特别地，作者提出了一种基于可变时间幅度放大和估计，用 Θ(| 根号 (n)| 乘以 | 根号 ∑_i=2^n Δ^(-2)_i|) 次量子查询可以找到最佳臂的算法。这个算法与经典算法相比，速度提升了一个平方级别。作者也证明了相匹配的量子下界（多项式对数因子）
multi-armed banditquantum computationamplitude amplificationreward probabilitiesquantum queries
发现论文，激发创造
  • 量子赌徒

    提出一种基于量子振幅放大的算法解决了量子版本的最优臂识别问题，并在所有情况下证明了它比经典算法快两次达到最优解。

    Feb, 2020

  • 量子厚尾赌博机

    本文研究了具有重尾分布的奖励和量子奖励谷歌的多臂黑客（MAB）和随机线性黑客（SLB）。

    Jan, 2023

  • 多臂赌博机中最优臂选取的顺序消除算法

    研究了多臂赌博机中的最佳臂辨识问题，提出了一个基于顺序淘汰算法的通用框架，并基于采样机制和每轮淘汰臂数量提出了性能评估指标，设计了一种按剩余臂数的非线性函数划分预算的算法，能够在纯探索场景下获得改进的理论保证和实验性能。

    Sep, 2016

  • 具有马尔可夫回报的多臂赌博机问题的在线算法

    考虑带 Markov 奖励的经典多臂赌博机问题，玩一只手臂时，其状态会按 Markov 方式更改，不玩时保持冻结。玩一只手臂时，玩家会获得与状态相关的奖励，每只手臂的状态转移概率未知。我们证明在手臂的状态转移概率满足一定条件下，基于样本均值的指数策略能够在总试验次数上实现对数遗憾，同时也证明了在具有休息的 Markov 赌博机模型下，样本均值指数策略不会降低最优性。此外，对比 Anantharam 的指数策略和 UCB，我们发现通过选择一个小的探索参数 UCB 可以比 Anantharam 的指数策略拥有更小的遗憾。

    Jul, 2010

  • 多层次最优臂识别

    在本文中，我们研究多信度最佳臂识别问题，通过提出一种以梯度为基础的方法，我们找到了具有渐近最优成本复杂度的解决方案，并针对每个臂还提出了最优保真度的概念。

    Jun, 2024

  • 线性赌博机中的最优臂识别

    本文研究线性贝叶斯最优化模型中的最优臂选择问题，提出样本分配策略来识别具有固定置信度的最优臂，并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值，并将其与最优实验设计中使用的 G - 最优准则进行比较。

    Sep, 2014

  • 具有固定置信度的不安定赌博机中的最佳臂标识

    在具有有限个臂的不安定多臂赌博问题中，通过分析某个马尔可夫决策过程及其状态 - 行动访问比例，确定最佳臂的策略和相应的期望停止时间，从而在有限的样本数、有限错误概率的条件下达到最佳臂的识别。

    Oct, 2023

  • 线性赌博机中的最优臂识别

    本文研究了随机线性武装的固定置信度下的最佳武器识别问题，目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法，其采样复杂度与已知的特定实例下界匹配，在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则，而且可以很少更新而不影响其理论保证。此外，与现有的最佳武器识别策略不同，我们的算法使用的停止规则不依赖于武器数量。实验结果表明，我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。

    Jun, 2020

  • 线性赌臂机中纯探索的完全自适应算法

    本文提出了第一个完全自适应的算法用于求解线性赌博机中的最优选择问题，并且其采样复杂度与已有算法相当。此外，通过模拟实验表明，在合成和真实数据集上均远优于现有的方法。

    Oct, 2017

  • 关于最佳臂识别的最优样本复杂度

    研究最优臂辨识问题，发现新算法和上下限优化，并提出一个新的关于最优样本复杂度的猜想。

    Nov, 2015