Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
  Linear contextual bandit is an important class of sequential decision making
problems with a wide range of applications to recommender systems, online
advertising, healthcare, and many other machine learning related tasks. While
there is a lot of prior research, tight regret bounds of linear contextual
bandit with infinite action sets remain open. In this paper, we address this
open problem by considering the linear contextual bandit with (changing)
infinite action sets. We prove a regret upper bound on the order of
$O(\sqrt{d^2T\log T})\times \text{poly}(\log\log T)$ where $d$ is the domain
dimension and $T$ is the time horizon. Our upper bound matches the previous
lower bound of $\Omega(\sqrt{d^2 T\log T})$ in [Li et al., 2019] up to iterated
logarithmic terms.
