AISTATS 2021poster27 citations
Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
Yingkai Li, Yining Wang, Xi Chen, Yuan Zhou
Abstract
Linear contextual bandit is a class of sequential decision-making problems with important applications in recommendation systems, online advertising, healthcare, and other machine learning-related tasks. While there is much prior research, tight regret bounds of linear contextual bandit with infinite action sets remain open. In this paper, we consider the linear contextual bandit problem with (changing) infinite action sets. We prove a regret upper bound on the order of O(\sqrt{d^2T\log T}) \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.
BibTeX
@InProceedings{pmlr-v130-li21b,
title = { Tight Regret Bounds for Infinite-armed Linear Contextual Bandits },
author = {Li, Yingkai and Wang, Yining and Chen, Xi and Zhou, Yuan},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {370--378},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/li21b/li21b.pdf},
url = {https://proceedings.mlr.press/v130/li21b.html},
abstract = { Linear contextual bandit is a class of sequential decision-making problems with important applications in recommendation systems, online advertising, healthcare, and other machine learning-related tasks. While there is much prior research, tight regret bounds of linear contextual bandit with infinite action sets remain open. In this paper, we consider the linear contextual bandit problem with (changing) infinite action sets. We prove a regret upper bound on the order of O(\sqrt{d^2T\log T}) \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. }
}