Contextual Bandits with Linear Payoﬀ Functions - Chu, Wei; Li, Lihong; Reyzin, Lev; Schapire, Robert E. (AISTATS 2011, 2011)
In this paper we study the contextual bandit problem (also known as the multi-armed bandit problem with expert advice) for linear payoﬀ functions. For T rounds, K actions, and d dimensional feature vectors, we prove an OqTdln3(KT ln(T)/δ)regret bound that holds with probability 1−δ for the simplest known (both conceptually and computationally) eﬃcient upper conﬁdence bound algorithm for this problem. We also prove a lower bound of Ω(√Td) for this setting, matching the upper bound up to logarithmic factors.