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.
One common technique for dimensionality reduction is to perform linear random projection @cite_22 @cite_28 . In this paper, we consider projecting the contextual data of @math onto a low-dimensional space of @math . Without loss of generality, we denote the random projection matrix by @math . Then, we have where @math and @math .
@cite_28 @cite_22
1571401318 2061375390
This paper discusses the topic of dimensionality reduction for @math -means clustering. We prove that any set of @math points in @math dimensions (rows in a matrix @math ) can be projected into @math dimensions, for any @math , in @math time, such that with constant probability the optimal @math -partition of the point set is preserved within a factor of @math . The projection is done by post-multiplying @math with a @math random matrix @math having entries @math or @math with equal probability. A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results. We show how to approximate a data matrix @math with a much smaller sketch @math that can be used to solve a general class of constrained k-rank approximation problems to within @math error. Importantly, this class of problems includes @math -means clustering and unconstrained low rank approximation (i.e. principal component analysis). By reducing data points to just @math dimensions, our methods generically accelerate any exact, approximate, or heuristic algorithm for these ubiquitous problems. For @math -means dimensionality reduction, we provide @math relative error results for many common sketching techniques, including random row projection, column selection, and approximate SVD. For approximate principal component analysis, we give a simple alternative to known algorithms that has applications in the streaming setting. Additionally, we extend recent work on column-based matrix reconstruction, giving column subsets that not only cover' a good subspace for @math , but can be used directly to compute this subspace. Finally, for @math -means clustering, we show how to achieve a @math approximation by Johnson-Lindenstrauss projecting data points to just @math dimensions. This gives the first result that leverages the specific structure of @math -means to achieve dimension independent of input size and sublinear in @math .