Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
This provides a foundational theoretical result for sequential decision-making in applications like recommender systems and online advertising, though it is incremental in refining bounds.
The paper tackles the open problem of tight regret bounds for linear contextual bandits with infinite action sets, proving an upper bound of O(√(d²T log T)) × poly(log log T), which matches the known lower bound up to logarithmic terms.
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 $Ω(\sqrt{d^2 T\log T})$ in [Li et al., 2019] up to iterated logarithmic terms.