Doubly-Robust Lasso Bandit

Gi-Soo Kim, Myunghee Cho Paik

Overview

Contextual multi-armed bandit (MAB) algorithms are foundational to modern sequential decision-making tasks, powering everything from news article recommendations to mobile health interventions. However, as the number of features (the context dimension, $d$) grows into the thousands, standard bandit algorithms struggle. Researchers from Seoul National University have introduced the Doubly-Robust (DR) Lasso Bandit, a novel algorithm that thrives in these high-dimensional settings. By treating unobserved rewards as a "missing data" problem and applying a doubly-robust estimator, the algorithm achieves a regret bound that scales logarithmically with $d$, making it significantly more efficient for large-scale personalization tasks.

The Challenge of High-Dimensional Bandits

In the Contextual MAB framework, a learner chooses an "arm" (e.g., a specific news article) based on "context" (e.g., user demographics and browsing history) to maximize a reward (e.g., a click).

Standard algorithms face a critical bottleneck when the context dimension $d$ is large: their "regret"—the difference in reward between the optimal choice and the learner's choice—typically grows polynomially with $d$. In many modern applications, while $d$ can be massive, only a small, sparse subset of features ($s_0 \ll d$) actually influences the reward.

While the Lasso method is the gold standard for sparse linear regression, it fundamentally fails in the standard bandit setting. Lasso requires data to be independent and identically distributed (i.i.d.). In a bandit problem, the learner’s policy inherently biases the data; we only observe rewards for the arms we actively choose, which focuses the data collection on a narrow region of the feature space. This "non-compatibility" prevents standard Lasso from converging efficiently.

The Doubly-Robust Lasso Approach

To bridge the gap between sparse regression and online decision-making, the authors propose the Doubly-Robust Lasso Bandit. The methodology relies on three core pillars:

  1. The Missing Data Perspective: The bandit problem is reframed as a missing data problem. The rewards for the arms the learner did not choose are simply treated as missing observations.
  2. Doubly-Robust (DR) Pseudo-Rewards: To correct the sampling bias, the algorithm constructs a "pseudo-reward" for the average context of all available arms. This estimator elegantly combines two techniques:
  3. A model-based prediction utilizing the current estimate of the regression parameters.
  4. An importance-weighted correction based on the probability that a specific arm was selected.
  5. Algorithm Flow: The algorithm alternates between uniform exploration and greedy exploitation. It uses the DR pseudo-rewards to update its internal model via Lasso. Because the DR estimator targets the average context—which remains i.i.d. over time—it satisfies the strict technical conditions Lasso requires to converge rapidly, effectively tricking the Lasso into operating on unbiased data.

Key Insights and Innovations

  • Independence from Arm Count ($N$): Unlike many previous sparse bandit algorithms, the regret of the DR Lasso Bandit does not depend on the number of arms. This makes it highly scalable for systems with massive, expanding catalogs.
  • Logarithmic Scaling: The regret scales with $\log(d)$ instead of $\sqrt{d}$ or $d$. This is a massive theoretical and practical breakthrough for processing high-dimensional feature vectors.
  • Cross-Disciplinary Synergy: The core innovation lies in applying the doubly-robust technique—a staple in causal inference and missing data literature—to "unbias" the context distribution in a bandit setting.
  • Simpler Tuning: The proposed method requires only three tuning parameters. Previous state-of-the-art sparse bandits required four, making the DR Lasso Bandit easier to deploy and maintain in production environments.

Results and Performance

The authors evaluated the algorithm through rigorous theoretical proofs and synthetic simulation studies, varying the number of arms ($N = 10$ to $100$), context dimension ($d = 100$), and sparsity ($s_0 = 5$).

  • Theoretical Bound: The paper establishes a high-probability regret upper bound of $O(s_0 \log(dT) \sqrt{T})$. This confirms mathematically that the cost of learning grows only logarithmically with the dimension.
  • Simulation Dominance: When compared against the standard Lasso Bandit (Bastani and Bayati, 2015), the DR Lasso Bandit significantly outperforms the baseline, especially as the number of arms $N$ increases. While the standard Lasso Bandit's regret increases with $N$, the DR Lasso Bandit remains remarkably stable.
  • Robustness to Correlation: The algorithm performs exceptionally well when contexts between different arms are highly correlated—a frequent scenario in real-world recommendation systems where multiple items share similar tags or categories.

Limitations and Future Directions

While a significant step forward, the DR Lasso Bandit has a few limitations that pave the way for future research:

  • I.I.D. Context Assumption: The current theoretical guarantees rely on the assumption that the distribution of context variables is i.i.d. over time. In dynamic real-world scenarios (like trending news or shifting user preferences), the context distribution is often non-stationary.
  • Linearity Constraints: The model assumes a linear relationship between context and reward. Extending this doubly-robust approach to non-linear or neural-network-based reward models is a natural and highly anticipated next step.
  • Parameter Sensitivity: Although it reduces the number of tuning parameters, performance still relies on the careful selection of exploration schedules ($\lambda_1, \lambda_2$), necessitating offline simulation before live deployment.

Summary updated

Abstract

Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, $d$. In many applications however, it is often the case that contexts are high-dimensional with only a sparse subset of size $s_0 (\ll d)$ being correlated with the reward. We consider the stochastic linear contextual bandit problem and propose a novel algorithm, namely the Doubly-Robust Lasso Bandit algorithm, which exploits the sparse structure of the regression parameter as in Lasso, while blending the doubly-robust technique used in missing data literature. The high-probability upper bound of the regret incurred by the proposed algorithm does not depend on the number of arms and scales with $\mathrm{log}(d)$ instead of a polynomial function of $d$. The proposed algorithm shows good performance when contexts of different arms are correlated and requires less tuning parameters than existing methods.
BibTeX
@inproceedings{kim2019doubly,
  author = {Gi-Soo Kim and Myunghee Cho Paik},
  title = {{Doubly-Robust Lasso Bandit}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=22uEa534Kq7v},
}
Figure