Tight Regret Bounds for Infinite-armed Linear Contextual Bandits

Yingkai Li, Yining Wang, Xi Chen, Yuan Zhou
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:370-378, 2021.

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.

Cite this Paper

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. } }
Endnote
%0 Conference Paper %T Tight Regret Bounds for Infinite-armed Linear Contextual Bandits %A Yingkai Li %A Yining Wang %A Xi Chen %A Yuan Zhou %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-li21b %I PMLR %P 370--378 %U https://proceedings.mlr.press/v130/li21b.html %V 130 %X 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.
APA
Li, Y., Wang, Y., Chen, X. & Zhou, Y.. (2021). Tight Regret Bounds for Infinite-armed Linear Contextual Bandits . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:370-378 Available from https://proceedings.mlr.press/v130/li21b.html.

Related Material