Tight Regret Bounds for Infinite-armed Linear Contextual Bandits

05/04/2019
by   Yingkai Li, et al.
0

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 prove regret upper bound of O(√(d^2T T))×poly( T) where d is the domain dimension and T is the time horizon. Our upper bound matches the previous lower bound of Ω(√(d^2 T T)) up to iterated logarithmic terms.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset