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.
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 .
@cite_6
2949469249
We study exploration in Multi-Armed Bandits in a setting where @math players collaborate in order to identify an @math -optimal arm. Our motivation comes from recent employment of bandit algorithms in computationally intensive, large-scale applications. Our results demonstrate a non-trivial tradeoff between the number of arm pulls required by each of the players, and the amount of communication between them. In particular, our main result shows that by allowing the @math players to communicate only once, they are able to learn @math times faster than a single player. That is, distributing learning to @math players gives rise to a factor @math parallel speed-up. We complement this result with a lower bound showing this is in general the best possible. On the other extreme, we present an algorithm that achieves the ideal factor @math speed-up in learning performance, with communication only logarithmic in @math .