Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit

Ke Li, Yun Yang, Naveen N. Narisetty

In this paper, we consider the multi-armed bandit problem with high-dimensional features. First, we prove a minimax lower bound, $\mathcal{O}\big((\log d)^{\frac{α+1}{2}}T^{\frac{1…