text: Contextual bandits with linear payoffs, which are also known as linear bandits, provide a powerful alternative for solving practical problems of sequential decisions, e.g., online advertisements. In the era of big data, contextual data usually tend to be high-dimensional, which leads to new challenges for traditional linear bandits mostly designed for the setting of low-dimensional contextual data. Due to the curse of dimensionality, there are two challenges in most of the current bandit algorithms: the first is high time-complexity; and the second is extreme large upper regret bounds with high-dimensional data. In this paper, in order to attack the above two challenges effectively, we develop an algorithm of Contextual Bandits via RAndom Projection ( CBRAP ) in the setting of linear payoffs, which works especially for high-dimensional contextual data. The proposed CBRAP algorithm is time-efficient and flexible, because it enables players to choose an arm in a low-dimensional space, and relaxes the sparsity assumption of constant number of non-zero components in previous work. Besides, we provide a linear upper regret bound for the proposed algorithm, which is associated with reduced dimensions.
  @cite_6: We consider a linear stochastic bandit problem where the dimension @math of the unknown parameter @math is larger than the sampling budget @math . In such cases, it is in general impossible to derive sub-linear regret bounds since usual linear bandit algorithms have a regret in @math . In this paper we assume that @math is @math sparse, i.e. has at most @math non-zero components, and that the space of arms is the unit ball for the @math norm. We combine ideas from Compressed Sensing and Bandit Theory and derive algorithms with regret bounds in @math .
summary: The total sequential rounds of playing bandits is @math . For each round @math with @math , a learner receives contextual information from the set of @math , where @math can be an extremely large integer representing a high-dimensional space. In this work, high-dimensional contextual data precisely mean that @math or even @math , which is the case mentioned in @cite_6 . Let @math be the number of arms and @math the reward of arm @math on round @math with @math and @math . We adopt @math to denote the @math norm of a vector @math , and @math to denote the identity matrix with dimensions of @math . For a positive definite matrix @math , the weighted norm of vector @math is defined as @math . The inner product is represented as @math , and the weighted inner product is @math .