AI Picks Better When It Knows Several Answers Are Right

Researchers have sharpened the math behind a classic problem: choosing among options when several are equally good. In a new arXiv paper, Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, and Quanquan Gu study multi-armed bandits with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For K-armed bandits with A optimal arms, they provide a sharper analysis of previous sub-sampling algorithms, establishing a minimax regret that improves on the previous bound. They then provide a matching lower bound up to logarithmic factors, indicating their established rate is nearly minimax-optimal. They further show that knowledge of A up to small factors is necessary to achieve near-optimal regret, since near-optimal algorithms for one number of optimal arms must incur substantially larger regret than the optimal regret for a smaller number. Overall, the results provide a comprehensive minimax characterization of K-armed bandits with A over the entire range of 1 ≤ A ≤ K−1.