Rate-Optimal Bayesian Simple Regret in Best Arm Identification
研究了多臂老虎机问题中的最优臂识别，在给定先验连续性条件下刻画了贝叶斯简单遗憾的收敛速率，并提出了一个简单易算的算法，其主导项与下界仅差常数因子。
We consider best arm identification in the multiarmed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret derives from the region in which the gap between optimal and suboptimal arms is smaller than [Formula: see text]. We propose a simple and easy-to-compute algorithm with its leading term matching with the lower bound up to a constant factor; simulation results support our theoretical findings.