Wan et al., 2023

为量子老虎机算法建立了新的下界

研究人员为量子多臂老虎机（QMAB）和量子线性老虎机（QLB）建立了新的极小极大下界，改进了先前的工作。该研究证明了具有 $K$ 个臂、时间范围为 $T$ 的 QMAB 的下界为 $\Omega(K\log(T/K))$，以及 $d$ 维 QLB 的下界为 $\Omega(d\log(T/d))$。这些发现解决了关于实现与 $T$ 无关的遗憾以及降低 QLB 中的维度依赖性的问题。作为对这些理论结果的补充，提出了一种用于有限动作 QL…