多臂老虎机问题中引入期望样本复杂度 ACE 新框架
Expected Sample Complexity in Multi-Armed Bandits
一篇多臂老虎机理论论文，提出 ACE 框架把样本复杂度从高概率保证换成期望保证，还证明了 Thompson 采样在 ε 未知时的紧界。
论文研究随机多臂老虎机问题的样本复杂度，提出期望样本复杂度指标和 approximately correct in expectation（ACE）分析框架。ACE 保证可推出最优期望奖励的几乎必然收敛，区别于其他框架中的高概率保证，并可转化为显式的期望遗憾界。论文证明确定性算法无法获得有利的 ACE 界，进而在 ε 已知场景设计了 explore-then-ε-greedy 算法，在 ε 未知场景分析了 Thompson 采样。两个场景均给出近乎匹配的下界，证明算法在 ε 上的紧性及两种场景间的性能分离。
Expected Sample Complexity in Multi-Armed Bandits
Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level $ε$ is known to the algorithm and when it is unknown. In the former, we devise an explore-then-$ε$-greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in $ε$ and proving a performance separation between the two regimes.