Multi-armed bandits with multiple best options get sharper regret bounds

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivit

Artificial IntelligenceMachine Learning

Summary

This paper looks at decision-making problems where there can be several equally good choices instead of just one. The authors study a type of problem called multi-armed bandits, where you repeatedly pick options and learn their rewards. They improve how we understand the best possible performance for these problems when multiple best arms exist, showing tighter limits on how much worse you can do compared to the best choices. They also find that knowing roughly how many best options exist is important for performing well. This helps clarify how to balance exploring different choices versus focusing on the best ones when there are multiple good answers.

What this means in practice

  • For online marketing teams: Optimize choices among multiple equally effective campaign actions to improve ad performance with theoretical regret guarantees.
  • For robotics control engineers: Improve decision algorithms in robotics where several actions yield similar outcomes, using tighter performance limits for adaptive control.

A theory result. No direct application yet.

Authors

Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu

Abstract

We study multi-armed bandits (MAB) 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, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$ minimax regret, where $T$ is the total number of interactions and $\tilde O(\cdot)$ drops all constant and logarithmic factors, improving the previous $\tilde{O}(\sqrt{KT/A})$ regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of $A$ up to $\tilde{O}(1)$ factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of $K$-armed bandits with $A$ over the entire range of $1 \leq A \leq K-1$.
View PDFOpen arXiv