Technical Summary: Batched Single-Index Global Multi-Armed Bandits with Covariates

1. Problem Formulation

The paper addresses the Global Multi-Armed Bandit with Covariates (GMABC) problem in a batched setting. This framework extends standard contextual bandits by incorporating two critical real-world constraints often found in applications like clinical trials and personalized recommendations:

1. Shared Information (Global Structure): Arms are not independent; they share a global parameter that links their reward functions. Playing one arm provides information about others, particularly when covariates are similar.
2. Batched Feedback: Decisions are made in batches rather than sequentially. A policy can only be updated at predetermined batch boundaries after observing all rewards within a batch.
3. Unknown Reward Functions: Unlike standard Global MAB models that assume known reward functions, this work assumes the link between covariates and rewards is unknown and potentially non-linear.

The reward for arm $k$ at time $t$ with covariate $X_t$ is modeled as:
$$Y_t^{(k)} = g^{(k)}(X_t) + \epsilon_t = f^{(k)}(X_t^\top \beta_0) + \epsilon_t$$
where $f^{(k)}$ are unknown 1-dimensional link functions specific to each arm, and $\beta_0 \in \mathbb{R}^d$ is a shared unknown index parameter (direction) across all arms. The goal is to minimize cumulative regret $R_T(\pi)$, defined as the gap between the optimal expected reward and the reward obtained by the policy.

2. Methodology: The BIDS Algorithm

The authors propose BIDS (Batched single-Index Dynamic binning and Successive arm elimination), a semi-parametric algorithm designed to leverage the shared single-index structure while handling batch constraints.

Core Mechanism

BIDS adapts the Adaptive Binning and Successive Elimination (ABSE) strategy (originally for fully nonparametric bandits) but modifies it to operate in a projected space rather than the full $d$-dimensional covariate space.

1. Dimension Reduction: Instead of partitioning the full covariate space $\mathbb{R}^d$, BIDS projects covariates onto a 1-dimensional axis defined by an estimated index vector $\hat{\beta}$. This mitigates the curse of dimensionality.
2. Hierarchical Partitioning: The algorithm constructs a tree of partitions based on the projected values $X_t^\top \hat{\beta}$.
   • Dynamic Binning: Bins are split adaptively. If a bin contains multiple active arms and the data is insufficient to distinguish the best arm, the bin is split into child bins in the next batch.
   • Successive Elimination: Within each bin, arms are eliminated if their empirical mean reward is statistically significantly lower than the current best arm in that bin, based on a confidence threshold dependent on the bin width and batch size.
3. Two Scenarios:
   • With Pilot Direction: If a reasonably accurate pilot estimate $\beta$ is available (e.g., from prior studies), BIDS uses it directly to guide binning.
   • Without Pilot Direction: If no pilot is available, the first batch is used as an initialization phase. Samples are collected cyclically from all arms to estimate $\beta_0$ using a Single-Index Regression (SIR) method (e.g., Sliced Average Derivative Estimation - SADE). The estimated direction is then used for the remaining $M-1$ batches.

3. Key Contributions

The paper makes four primary contributions:

1. GMABC Framework: Introduction of a novel semi-parametric framework that generalizes Global MABs by allowing unknown, covariate-dependent reward functions linked via a shared single-index parameter.
2. BIDS Algorithm: Proposal of the first systematic algorithm for contextual batched bandits under a sufficient-dimension reduction paradigm using a single-index structure.
3. Regret Guarantees:
   • Lower Bound: Derivation of a minimax lower bound for the batched semi-parametric GMABC problem, quantifying the fundamental difficulty involving the number of batches $M$, arms $K$, and margin parameter $\alpha$.
   • Upper Bounds:
     • With Pilot: When a pilot direction is available with sufficient accuracy ($\rho_{pilot} \approx O((T/K)^{-1/3})$), the algorithm achieves a regret bound of $O((K \log T)^{1-\beta_M} T^{\beta_M})$ (for fixed $K$, this matches the minimax rate for nonparametric bandits with $d=1$).
     • Without Pilot: When the index must be estimated, the regret includes an additional term $O(K^{1/3} T^{2/3})$ from the initialization phase, but still achieves sub-linear regret.
4. Practical Insights: Analysis of the trade-offs between estimation error of the index direction and the learning rate, highlighting the role of batch constraints and covariate dimensionality.

4. Results

Theoretical Results

• Minimax Optimality: For a fixed number of arms $K$ and a sufficiently accurate pilot direction, BIDS achieves the minimax-optimal rate for nonparametric batched bandits but with effective dimension $d=1$, effectively circumventing the curse of dimensionality associated with high-dimensional covariates.
• Dependence on $K$: The upper bound exhibits polynomial dependence on $K$ ($K^{1-\beta_M}$), which is typical for multi-parameter bandit models, while the lower bound shows logarithmic dependence. The gap is attributed to the need to collect sufficient samples to compare all arms within bins.
• Margin Condition: The performance depends on the margin parameter $\alpha$. When $\alpha$ is small (harder to distinguish arms), the regret rate is slower.

Empirical Results

Experiments were conducted on simulated data and three real-world datasets (Rice Classification, Occupancy Detection, EEG Eye State).

• Comparison: BIDS consistently outperformed the nonparametric batched bandit baseline (BaSEDB) across all settings.
• Pilot Accuracy: BIDS remained robust to moderate perturbations in the pilot direction but performance degraded as the angle between the pilot and true direction increased.
• Noise Sensitivity: In the absence of a pilot, BIDS performed better than BaSEDB even under varying noise levels, though the gap narrowed as noise increased (reducing the accuracy of the initial SIR estimate).
• Interpretability: The estimated index vectors $\hat{\beta}$ aligned with domain knowledge (e.g., identifying temperature and humidity as key features for occupancy detection), demonstrating the interpretability advantage of the semi-parametric approach over black-box nonparametric methods.

5. Significance and Claims

The paper claims to be the first systematic study of contextual bandits under a sufficient-dimension reduction paradigm using a single-index model structure.

• Bridging Flexibility and Interpretability: The work bridges the gap between fully parametric models (which are interpretable but rigid) and fully nonparametric models (which are flexible but suffer from the curse of dimensionality and lack interpretability). By assuming a single-index structure, the authors retain the flexibility to model complex non-linear reward functions while reducing the effective dimension to 1.
• Computational Efficiency: The method offers significant computational advantages over nonparametric counterparts, as the number of bins does not grow exponentially with the covariate dimension $d$.
• Real-World Applicability: The framework is specifically motivated by scenarios like clinical trials where data is collected in batches, treatments share chemical compositions (global structure), and patient profiles (covariates) influence outcomes non-linearly.

The authors acknowledge limitations, noting that the current algorithm requires prior knowledge of the margin parameter $\alpha$ for tuning and that the polynomial dependence on $K$ in the upper bound could potentially be improved. They suggest future work could explore adaptive estimation of the index direction across batches or leveraging transfer learning to estimate the pilot direction.