A General (sqrt T gamma T) Lower Bound for Kernel Bandits
The paper establishes a general minimax regret lower bound of $\Omega(pT \gamma T / \log T)$ for non-constant continuous kernels on compact domains, showing this scaling is generally unavoidable. However, it demonstrates that this logarithmic factor can be removed under specific conditions related to the information gain rate $\gamma_T$, achieving an optimal $\Theta(\sqrt{T} \gamma_T)$ regret for certain kernels.