多臂老虎机中的期望样本复杂度

研究针对随机多臂老虎机问题提出期望样本复杂度这一性能度量，并在名为“近似正确期望（ACE）”的新框架下进行分析。ACE 保证可推出几乎必然收敛到最优期望奖励，并可转化为显式期望遗憾界。研究还给出 explore-then-ε-greedy 算法与 Thompson sampling 的分析及近乎匹配的上下界，证明两种情形在 ε 上紧致且存在性能分离。