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

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 Õ((K−A)/√(KA)√T ) minimax regret, where T is the total number of interactions and Õ(·) drops all constant and logarithmic factors, improving the previous Õ(√(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 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 ≤ A ≤ K−1.

Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
Qiwei Di, Quanquan Gu
arXiv28 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
Jingyang Li, Jian‐Feng Cai, Yang Chen +1
The Annals of Statistics1 Jun 2026Peer-reviewedLicence not statedFull text16 citedNumerical analysis & scientific computingOpenAlex
Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Shion Takeno, Shogo Iwazaki, Ichiro Takeuchi
arXiv20 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
Mengxiao Zhang
arXiv11 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
Near-Optimal First-Order Regret for Bandits with Feedback Graphs
Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1
arXiv29 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{ji2026bandits,
  title = {{Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity}},
  author = {Kaixuan Ji and Qiwei Di and Qingyue Zhao and Heyang Zhao and Quanquan Gu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.38659},
  eprint = {2609.38659},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38659},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
AU  - Kaixuan Ji
AU  - Qiwei Di
AU  - Qingyue Zhao
AU  - Heyang Zhao
AU  - Quanquan Gu
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.38659
UR  - https://arxiv.org/abs/2609.38659
AB  - 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 Õ((K−A)/√(KA)√T ) minimax regret, where T is the total number of interactions and Õ(·) drops all constant and logarithmic factors, improving the previous Õ(√(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 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 ≤ A ≤ K−1.
ER  -

Abstract

Related

Cite