Doubly-Robust Lasso Bandit

Gi-Soo Kim, Myunghee Cho Paik

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 existing algorithms have regret proportional to a polynomial function of the context dimension, $d$. In many applications, however, 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, 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 $\log(d)$ instead of a polynomial function of $d$. The proposed algorithm shows good performance when contexts of different arms are correlated and requires fewer tuning parameters than existing methods.

Introduction

In the Contextual Multi-Armed Bandit (MAB) framework, a learner must repeatedly choose an action (an "arm") based on observed side information (the "context"). The goal is to maximize cumulative rewards over time, a task that requires balancing the exploration of new actions with the exploitation of known high-performing ones.

Modern applications, such as personalized news feeds or digital health interventions, often involve massive context dimensions ($d$). However, it is frequently the case that only a small subset of these features ($s_0$) actually influences the reward—a property known as sparsity. Traditional bandit algorithms often suffer from the "curse of dimensionality," where the regret (the difference between the learner's performance and the optimal strategy) grows polynomially with $d$. While the Lasso is a standard tool for high-dimensional sparse regression, applying it to bandit settings is non-trivial because the data collected by a bandit policy is inherently biased and non-i.i.d., often violating the technical conditions required for Lasso to converge.

The Challenge of High-Dimensional Bandits

The primary difficulty in high-dimensional bandit learning is that as the learner identifies better arms, it stops sampling "bad" arms. This selective sampling creates a biased data distribution. In statistical terms, this often leads to a violation of the "compatibility condition" or "restricted eigenvalue condition" necessary for Lasso-based estimators to remain accurate. Previous attempts to solve this, such as the original Lasso Bandit, often required separate models for every arm or forced exploration in ways that could be inefficient as the number of arms ($N$) increased.

The Doubly-Robust Lasso Bandit

The Doubly-Robust (DR) Lasso Bandit algorithm bridges the gap between bandit learning and high-dimensional statistics by reframing the bandit problem as a missing data problem. For any given time step, the rewards for the arms not chosen are essentially "missing."

1. Doubly-Robust Pseudo-Rewards

The core innovation is the construction of a doubly-robust pseudo-reward. This estimator combines two components:

  • A Direct Method: A reward prediction based on the current model parameters.
  • Inverse Probability Weighting (IPW): The actual observed reward, weighted by the inverse of the probability that the specific arm was chosen.

By combining these, the algorithm creates an unbiased estimate of the reward for every arm, regardless of whether it was pulled. This "pseudo-data" helps satisfy the compatibility conditions required for Lasso, even when the underlying data distribution is biased by the learner's policy.

2. Information Sharing and Sparsity

Unlike earlier methods that trained independent models for each arm, the DR Lasso Bandit shares information across all arms to estimate a single global parameter $\beta$. This global approach allows the algorithm to be insensitive to the number of arms ($N$), a critical feature for systems with large action spaces.

3. Two-Stage Randomization

The algorithm employs a randomized policy to ensure sufficient exploration. In each step, it either explores (pulling an arm at random) or exploits (pulling the arm with the highest predicted reward), ensuring that the probability of choosing any arm remains bounded away from zero, which is necessary for the stability of the doubly-robust estimator.

Empirical and Theoretical Results

The authors provide a rigorous theoretical analysis, proving a high-probability regret upper bound of $O(s_0 \log(dT) \sqrt{T})$. This result is significant because the regret scales only with the logarithm of the dimension ($\log d$), allowing the algorithm to handle thousands of features with minimal performance loss.

Simulation Findings

Through synthetic simulation studies (varying $N$ from 10 to 100, with $d=100$ and $s_0=5$), the researchers demonstrated several key advantages:

  • Insensitivity to Arm Count: While standard Lasso Bandit regret increases as more arms are added, the DR Lasso Bandit's performance remains stable.
  • Robustness to Correlation: The algorithm performs exceptionally well when the contexts of different arms are strongly correlated, a common occurrence in real-world datasets where features often overlap.
  • Ease of Use: The algorithm requires only three tuning parameters, compared to the four required by previous state-of-the-art sparse bandit methods.

Conclusion and Future Directions

The Doubly-Robust Lasso Bandit offers a robust solution for sequential decision-making in high-dimensional environments. By treating unobserved rewards as missing data and applying doubly-robust estimation, it enables the use of Lasso in non-i.i.d. settings.

While the current framework assumes a linear relationship between context and reward, future work could extend this doubly-robust approach to non-linear models, such as neural networks or forest-based estimators. Additionally, addressing the computational cost of running Lasso optimizations at every time step remains an important area for practical optimization in large-scale production environments.

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