# Contextual Bandits with Random Projection

Source: [Contextual Bandits with Random Projection](<https://www.sota2.com/research/paper/68fa65801e209131cea0a935>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:38.288Z

Authors: Xiaotian Yu

Published: 2019-03-20T16:34:11.000Z

## Abstract

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 (\\texttt{CBRAP}) in the setting of linear payoffs, which works especially for high-dimensional contextual data. The proposed \\texttt{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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Bandit Recommendation on MovieLens 1M (top-1500 subset)](<https://www.sota2.com/research/sota/bandit-recommendation-on-movielens-1m-top-1500-subset.md>): Bandit Recommendation; MovieLens 1M top-1500 most-rated items; Cumulative Regret R(T): 660.

- [Contextual Bandits on MovieLens 100k](<https://www.sota2.com/research/sota/contextual-bandits-on-movielens-100k.md>): Contextual Bandits; MovieLens 100k; Cumulative Regret: 653.4.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1903.08600>)

[PDF](<https://arxiv.org/pdf/1903.08600.pdf>)
