Online Batch Decision-Making with High-Dimensional Covariates

Chi-Hua Wang, Guang Cheng

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:

  1. 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.
  2. 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.
Figure 1: The Teamwork-Selfish policy structure, showing how exploration (blue Teamwork stages) and exploitation (orange Selfish stages) are interleaved across batches.

The algorithmic flow is detailed in the following flowchart, illustrating the logic used at each decision epoch:

Figure 2: Flowchart of the Teamwork LASSO Bandit algorithm, illustrating the decision logic at each epoch $t$.

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

Abstract

We propose and investigate a class of new algorithms for sequential decision making that interacts with \textit{a batch of users} simultaneously instead of \textit{a user} at each decision epoch. This type of batch models is motivated by interactive marketing and clinical trial, where a group of people are treated simultaneously and the outcomes of the whole group are collected before the next stage of decision. In such a scenario, our goal is to allocate a batch of treatments to maximize treatment efficacy based on observed high-dimensional user covariates. We deliver a solution, named \textit{Teamwork LASSO Bandit algorithm}, that resolves a batch version of explore-exploit dilemma via switching between teamwork stage and selfish stage during the whole decision process. This is made possible based on statistical properties of LASSO estimate of treatment efficacy that adapts to a sequence of batch observations. In general, a rate of optimal allocation condition is proposed to delineate the exploration and exploitation trade-off on the data collection scheme, which is sufficient for LASSO to identify the optimal treatment for observed user covariates. An upper bound on expected cumulative regret of the proposed algorithm is provided.
BibTeX
@inproceedings{wang2020online,
  author = {Chi-Hua Wang and Guang Cheng},
  title = {{Online Batch Decision-Making with High-Dimensional Covariates}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure