Multi-task and meta-learning with sparse linear bandits

Leonardo Cella, Massimiliano PontilUAI 2021

Introduction

Linear contextual bandits are a cornerstone of personalized recommendation systems, where an algorithm must choose actions based on feature vectors to maximize a cumulative reward. However, in high-dimensional feature spaces, the "exploration" phase can be prohibitively long, as the algorithm struggles to estimate the underlying reward function. This paper introduces a novel framework that leverages joint sparsity across multiple tasks to accelerate learning. By extending the group-lasso estimator to handle the non-i.i.d. data typical of bandit policies, the authors achieve a theoretical regret reduction of $\sqrt{T}$ (where $T$ is the number of tasks) compared to learning tasks independently.

Problem Formulation: Joint Sparsity in Contextual Bandits

In many real-world scenarios, such as recommending content to thousands of users, we face many similar tasks. While each user is unique, their preferences often depend on the same small subset of features—a property known as joint sparsity. The primary challenge in exploiting this structure is that standard statistical tools for group-sparsity, like the group-lasso, assume data is independent and identically distributed (i.i.d.). In bandit settings, the data is inherently biased because the algorithm's past choices dictate future observations, creating a "martingale" noise structure that invalidates traditional i.i.d. proofs.

The Proposed Framework: DR-GroupLasso

The authors propose a three-step solution to bridge the gap between multi-task learning and bandit optimization:

  1. Novel Oracle Inequalities: They derive new theoretical guarantees for the group-lasso estimator specifically for data collected by a bandit policy, moving beyond the i.i.d. assumption to handle martingale difference sequences.
  2. Doubly Robust (DR) Group-Lasso Policy: Building on previous "doubly robust" techniques, they design a policy ($\pi_{DR}$) that uses a pseudo-reward estimator. This estimator corrects for the selection bias introduced by the bandit's sampling, allowing the group-lasso to function correctly.
  3. Task Reduction: For the multi-task setting, they "stack" multiple tasks into a single, massive group-sparse problem. This allows a single group-lasso policy to solve all tasks simultaneously, naturally sharing information about relevant features across the entire group.

Theoretical Contributions

The most significant theoretical insight is the $\sqrt{T}$ advantage. The multi-task regret is bounded by $\tilde{O}(s\sqrt{TN_0})$, where $s$ is the sparsity and $N_0$ is the number of rounds per task. This suggests that if you have 100 tasks, you could potentially learn 10 times more efficiently than an independent learner. Furthermore, the authors identify a flaw in previous state-of-the-art research, arguing that prior lower bounds were vacuous because they failed to account for the fundamental connection implied by joint sparsity.

Experimental Evaluation

The framework was evaluated using both synthetic and real-world data. The synthetic environment involved 40 parallel tasks in a 50-dimensional space with a sparsity constant of 5.

Cumulative rewards for various policies in a multi-tasking environment with 40 tasks.

As shown in the figure above, the DR-GroupLasso policy significantly outperforms the standard DR-Lasso and other baselines like MLinGreedy. The gap between the group-lasso approach and the "Oracle" (which knows the relevant features a priori) is substantially smaller than that of independent learners. These results were mirrored in tests on the Last.FM dataset (1892 users), where the proposed policy showed a clear cumulative reward advantage as the number of tasks increased, confirming that real-world user preferences often share a common underlying structure.

Conclusion and Future Work

While the DR-GroupLasso policy demonstrates clear advantages, its performance remains tied to the efficiency of the underlying Doubly Robust Lasso base. Future research may apply these group-lasso oracle inequalities to other bandit policies, such as those using forced exploration or different confidence intervals, to further improve practical results. Additionally, while the authors proposed a new lower bound, a formal proof of absolute minimax optimality remains an open question.

Summary updated

BibTeX
@inproceedings{cella2021multi,
  author = {Leonardo Cella and Massimiliano Pontil},
  title = {{Multi-task and meta-learning with sparse linear bandits}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
}
Figure