A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

2025/10/31 by Chase, Zachary, Ito, Shinji, Mehalel, Idan
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2511.00257

Abstract

We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be Θ( √(T K log (N/K) ) ), where K is the number of arms, N is the number of experts, and T is the time horizon.

Citations

• Improved Regret Bounds for Bandits with Expert Advice
• Multiclass Online Learnability under Bandit Feedback
• On Interpolating Experts and Multi-Armed Bandits
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
• Multiarmed Bandits With Limited Expert Advice
• The price of bandit information in multiclass online classification
• The Nonstochastic Multiarmed Bandit Problem

Related

• Multiarmed Bandits With Limited Expert Advice
• Improved Regret Bounds for Bandits with Expert Advice
• Bounded regret in stochastic multi-armed bandits
• Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice
• Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice