Introduction
In the landscape of online machine learning, the Contextual Bandit problem serves as a foundational framework for decision-making under uncertainty. A learner must select an "arm" (an option) based on observed "features" (context) to maximize a cumulative reward. In modern high-dimensional settings, we often encounter the Sparse Linear Bandit problem, where only a small subset of features ($s_0$) actually influences the reward.
Traditionally, algorithms designed for these problems rely on "forced exploration"—randomly selecting suboptimal arms to ensure the model gathers sufficient information. However, optimal forced exploration requires prior knowledge of the sparsity level $s_0$, which is rarely available in practice. This has led researchers toward greedy algorithms. Greedy policies are "sparsity-agnostic"; they simply choose the best-looking option based on current data. While practically appealing, proving that greedy algorithms achieve sublinear regret has historically required a restrictive assumption known as relaxed symmetry, requiring arm features to be distributed almost symmetrically around the origin. This paper significantly expands the theoretical boundaries for greedy algorithms, proving their efficacy across a much wider and more realistic array of feature distributions.
The Compatibility Constant and Symmetry
The core challenge in proving the convergence of greedy algorithms lies in the compatibility constant ($\phi$). This mathematical value measures the diversity of the features selected by the greedy policy. If $\phi$ remains bounded away from zero, the Lasso estimator used by the algorithm can effectively learn the underlying reward structure.
Previous state-of-the-art research suggested that this diversity was only guaranteed if the feature distributions were origin-symmetric. In real-world scenarios—such as modeling user age, click-through rates, or purchase history—features are often strictly positive or highly asymmetric. This paper breaks this "symmetry barrier" by identifying new conditions under which the compatibility constant remains positive, even when data is "lopsided."
Theoretical Breakthroughs
1. The Mixture Theorem
One of the paper's most significant contributions is the Mixture Theorem. The authors prove that if a distribution is a mixture of a "greedy-applicable" component and any other distribution, the entire mixture remains greedy-applicable. This creates a "reverse-spoiled-apple" effect: a small subset of well-behaved, diverse data can provide enough exploration for the entire system to function effectively. For practitioners, this suggests that as long as a portion of the user base or environment provides diverse feature sets, the greedy algorithm's performance is theoretically protected.
2. New Distribution Classes
The authors identify and prove the applicability of several new distribution bases that do not require symmetry:
- Gaussian Mixtures: Sums of finite Gaussian distributions, which can model complex, multi-modal data.
- Discrete Distributions: Features that take on specific, fixed values, which is the standard for categorical data in recommendation systems.
- Radial Distributions: Distributions based on the distance from a central point, such as truncated Gaussians.
Performance and Empirical Validation
Theoretically, the authors demonstrate that for these new distribution classes, the greedy algorithm achieves an expected regret of $O(\sqrt{T})$ (ignoring logarithmic factors). This is a landmark result because it matches the performance of more complex algorithms that require advance knowledge of the problem's sparsity.
To validate these theoretical claims, the authors conducted numerical experiments using a synthetic dataset. They utilized a setup with 3 arms and 10-dimensional features generated from a uniform distribution between 0 and 1. This distribution is strictly positive and origin-asymmetric, explicitly violating the "relaxed symmetry" requirements of previous theories. Despite this, the greedy algorithm (specifically the SA LASSO Bandit) exhibited a clear $\sqrt{t}$ growth in cumulative regret, empirically confirming that the algorithm remains efficient in asymmetric environments.
Implications and Future Work
This research broadens the applicability of greedy algorithms to a variety of complex models, including Thresholded Lasso Bandits and Combinatorial Bandits. By removing the need for origin-symmetry, the authors have made sparsity-agnostic algorithms far more viable for real-world applications like personalized medicine and digital advertising.
However, some challenges remain. The current analysis relies on an independence assumption, requiring at least one arm's features to be independent of the others. Future research is needed to explore cases where all arms are highly correlated. Additionally, while the paper proves the compatibility constant $\phi$ is positive, quantifying exactly how its magnitude scales with the number of arms or feature dimensions remains an open question. A very small constant could still lead to high practical regret, even if the theoretical growth rate is optimal.
Summary updated