Tight Regret Bounds for Infinite-armed Linear Contextual Bandits

Abstract

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^{2}T\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.

arXiv comment10 pages, accepted for presentation at AISTATS 2021

References in corpus (1)

• Provably Optimal Algorithms for Generalized Linear Contextual Bandits

Cited by in corpus (6)

• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Stochastic Linear Optimization with Adversarial Corruption
• Stochastic Bandits with Context Distributions
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Impact of Representation Learning in Linear Bandits
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP