In modern recommendation systems and personalized medicine, we often face a "curse of dimensionality." To make a good decision, an algorithm might look at thousands of features—user demographics, browsing history, or genetic markers. However, standard contextual bandit algorithms like LinUCB or Thompson Sampling struggle here: their "regret" (the cost of learning) typically scales linearly with the number of features $d$. When $d$ is in the thousands, the algorithm spends so much time exploring every possible dimension that it never gets around to actually helping the user.
The core insight of recent research is that while the feature space is massive, the actual reward signal is usually governed by a much smaller, hidden structure. By identifying and exploiting this low-dimensional manifold, we can reduce the complexity of the problem from the ambient dimension $d$ to an "effective dimension" $k$, where $k \ll d$.
The Geometry of Uncertainty
To understand why high dimensionality is a problem, imagine the agent’s knowledge as an "uncertainty ellipsoid" in feature space. Every time the agent pulls an arm, it flattens this ellipsoid along one direction. In a 10,000-dimensional space, the agent must pull arms in 10,000 different "directions" just to get a basic sense of the reward landscape.
Early work like the Banditron, introduced by Sham M. Kakade, Ambuj Tewari, and Shai Shalev‐Shwartz in Efficient bandit algorithms for online multiclass prediction, sought to bring the efficiency of simple linear classifiers to the bandit setting. However, as datasets grew, researchers realized that simply being "efficient" wasn't enough; the algorithms needed to ignore the noise entirely.
Exploiting Sparsity
The most common structural assumption is sparsity: the idea that out of 1,000 features, only 10 actually influence the reward.
Algorithms like Lasso-OD, developed by Recep Can Yavas and Vincent Y. F. Tan in Fixed-Budget Best-Arm Identification in Sparse Linear Bandits, use a two-phase approach. They first use a thresholded Lasso estimator to identify the "active" features and then focus all subsequent exploration on that tiny subset. Similarly, Sunrit Chakraborty and Ambuj Tewari showed in Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits that using "spike-and-slab" priors allows Thompson Sampling to naturally gravitate toward sparse solutions, making it both mathematically optimal and computationally faster.
Learning the Shared Representation
Often, the structure isn't just a few active features, but a low-rank representation—a specific combination of features that matters across many different tasks.
In Provable Benefits of Representation Learning in Linear Bandits, Jason D. Lee, Simon S. Du, and colleagues proved that if an agent learns a shared low-dimensional representation across multiple tasks, the sample complexity drops from the ambient dimension $d$ to the latent dimension $k$. This "meta-learning" approach allows the agent to use data from Task A to narrow down the search space for Task B.
For single-task settings, Kamyar Azizzadenesheli and Anima Anandkumar proposed the Projected Stochastic Linear Bandit (PSLB) in Stochastic Linear Bandits with Hidden Low Rank Structure. PSLB uses Principal Component Analysis (PCA) to continuously project high-dimensional action features into a lower-dimensional subspace, effectively "denoising" the context before the bandit even sees it.
Human-in-the-Loop and Hierarchies
If the algorithm can't find the structure on its own, it can ask for help or use a "coarse-to-fine" strategy.
- Feature Feedback: Urvashi Oswal and Robert D Nowak introduced FF-OFUL in Linear Bandits with Feature Feedback. In this framework, users provide "hints" (e.g., highlighting a keyword in a recommended article). This feedback allows the algorithm to grow its feature space dynamically, focusing only on the dimensions the user has flagged as relevant.
- Hierarchical Exploration: In Hierarchical Exploration for Accelerating Contextual Bandits, Yisong Yue and Carlos Guestrin developed CoFineUCB. This algorithm prioritizes exploration in a low-dimensional subspace of "typical" preferences first, only moving to the full, high-dimensional feature space once it has mastered the basics.
A Unified View: Explore-the-Structure-Then-Commit
To tie these ideas together, Wenjie Li, Adarsh Barik, and Jean Honorio proposed a unified framework called ESTC in A Simple Unified Framework for High Dimensional Bandit Problems.
The intuition is simple: instead of trying to learn the reward and the structure simultaneously (which is hard), the agent spends a small, initial "exploration" phase specifically to identify the underlying structure (be it sparsity, low-rank, or group-sparsity). Once the structure is identified, the agent "commits" to that low-dimensional subspace for the rest of time. This two-stage approach yields regret bounds that scale only logarithmically with the high dimension $d$, proving that in the world of bandits, the "curse" of dimensionality can be broken if you know where to look for the "blessing" of structure.