In many modern applications, from clinical trials to digital marketing, decision-makers must select optimal treatments for users based on high-dimensional data. Traditional multi-armed bandit (MAB) algorithms often assume a sequential, one-at-a-time update process. However, real-world constraints frequently require processing users in batches. This paper introduces the Teamwork LASSO Bandit algorithm, designed to handle batch arrivals and high-dimensional covariates where only a few features are truly predictive.
The Batch Decision-Making Challenge
The core difficulty in this setting is "limited adaptivity." When users arrive in batches, the agent cannot update its model until the entire batch is processed. This delay can lead to inefficient exploration. Furthermore, high-dimensional covariates—where the number of features $d$ may exceed the sample size—require sophisticated regularization techniques like LASSO to identify relevant features without being overwhelmed by noise.
The Teamwork LASSO Bandit Algorithm
The proposed solution uses a "Teamwork-Selfish" policy to manage the exploration-exploitation trade-off. The algorithm alternates between two distinct modes:
- Teamwork Stage (Exploration): During specific decision epochs (specifically those at indices that are powers of 2), the agent enters "teamwork mode." It forces exploration across all treatments to build a "Teamwork sample"—a clean, unbiased dataset used for screening.
- Selfish Stage (Exploitation): In all other epochs, the agent aims to maximize rewards. It first uses the Teamwork sample to screen out sub-optimal treatments and then applies a second LASSO regression on the entire historical dataset ("All LASSO") to select the best candidate.
The algorithmic flow is detailed in the following flowchart, illustrating the logic used at each decision epoch:
Theoretical and Experimental Insights
A major theoretical contribution is the "rate of optimal allocation condition," which ensures the algorithm collects enough high-quality data for the LASSO estimator to remain consistent. The authors prove an expected cumulative regret bound of $O(NKs_0^2 [\log T + \log d]^2)$, where $N$ is batch size, $K$ is the number of treatments, and $s_0$ is the sparsity of the feature set.
Simulations validate these findings, showing that the Teamwork LASSO Bandit achieves performance comparable to high-frequency update models while significantly reducing computational overhead. By separating the exploration data, the algorithm avoids the bias typically introduced by past decisions.
Conclusion and Future Directions
The Teamwork LASSO Bandit provides a robust framework for batch decision-making in high-dimensional settings. While currently based on linear assumptions and constant batch sizes, future work could extend this to non-linear models or fluctuating traffic patterns, potentially using alternative penalties like Minimax Concave Penalized (MCP) to further tighten regret bounds.
Summary updated