On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice

This paper examines two extensions of multi-armed bandit problems: multi-armed bandits with expert advice and contextual linear bandits. For the former problem, multi-armed bandits with expert advice, the previously known best upper and lower bounds have been O( KT log N K ) and Ω( KT log N log K ), respectively. Here, K, N , and T represent the numbers of arms, experts, and rounds, respectively. We provide a lower bound of Ω( KT log N K ) for the setup in which the player chooses an expert before observing the advices in each round. For the latter problem, contextual linear bandits, we provide an algorithm that achieves O( dT log(K min1, S d )) together with a matching lower bound, where d and S represent the dimensionality of feature vectors and the size of the context space, respectively. O KT log + N K , 1 where we denote log + x := max log x, 1. This is minimax optimal for the case of N = O(K). However, the minimax optimal bound for arbitrary settings of K and N has been an open question. The best known lower bound Ω KT log N log K is shown by Seldin and Lugosi [2016], who conjectured that this lower bound is minimax optimal. This paper provides a solution to this open question by providing a lower bound of Ω KT log + N K , which, together with the upper 1 Kale [2014] deals with more general settings of the multi-armed bandit with expert advice in which only a limited number of expert advice are accessible in each round. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).