Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification

Multi-armed bandit (MAB) frameworks have evolved from simple reward maximization to structured models like linear bandits, enabling efficient algorithms such as LinUCB and Thompson Sampling. Pure exploration tasks, especially Top-m identification, focus on accurate arm subset detection within limited samples, crucial for applications like drug discovery and recommendation systems. While linear models offer computational and theoretical advantages, their assumption of perfect linearity often fails in practice, leading to model bias or misspecification. Recent research has addressed regret minimization under bias, but pure exploration remains less explored in this context. This paper situates itself at this intersection, aiming to develop algorithms that are both sample-efficient and robust to model deviations.

The core challenge is to identify the top-m arms with high confidence when the reward model deviates from linearity, characterized by an unknown bias ε. Existing algorithms like LinGapE perform poorly under bias, requiring excessive samples or failing to guarantee correctness. The difficulty lies in balancing exploration efficiency with robustness, especially when the bias magnitude is unknown or large. The problem becomes more complex as the bias affects the confidence bounds and the optimal sampling strategy, necessitating new theoretical tools and adaptive algorithms that can handle uncertainty in model fidelity.

The paper introduces three key innovations: 1) a problem-dependent lower bound on sample complexity that explicitly incorporates the bias level, revealing the fundamental limits of adaptive identification; 2) the MISLID algorithm, which combines an orthogonal projection estimator, KL divergence half-space optimization, and adaptive sampling via no-regret learners, enabling it to adapt to unknown bias levels; 3) a novel stopping rule based on structured concentration inequalities that guarantees δ-correctness across bias scenarios. These innovations collectively enable near-optimal, bias-robust pure exploration, filling a critical gap in the literature.

• �� Initialization: Pull a set of d arms spanning the feature space to ensure invertibility of the design matrix.
• �� Estimation: Compute empirical means, then project onto the model set M using a weighted norm, decomposing the mean into a linear part and residual bias.
• �� Bias Optimization: Use KL divergence half-space optimization to refine the bias estimate, constructing an optimistic proxy for the true mean.
• �� Sampling: Employ a no-regret online learner over the arm distribution, updating based on gain functions derived from the bias estimates.
• �� Stopping: Apply a threshold based on the structured concentration bounds, ensuring δ correctness.
• �� Adaptivity: The algorithm dynamically adjusts to the bias level, with theoretical guarantees matching the lower bound as δ→0.

Experiments involve synthetic data with controlled bias levels, drug repositioning datasets, and recommendation system logs. Baselines include LinGapE and LUCB. Metrics focus on sample complexity and error probability. Hyperparameters such as bias bound ε, confidence δ, and feature dimension d are varied to test robustness. Multiple repetitions ensure statistical significance. Ablation studies analyze the impact of bias estimation accuracy and the adaptive sampling strategy, demonstrating the algorithm’s ability to maintain efficiency across scenarios.

MISLID consistently achieves near-optimal sample complexity, matching the theoretical lower bound as δ→0. Under small bias, it reduces sample count by over 30% compared to baseline methods. With larger bias, it maintains robustness, reducing samples by 20% over traditional algorithms. In real datasets, it achieves high accuracy with fewer samples, confirming its practical advantage. The results highlight the importance of bias adaptation, with the algorithm outperforming fixed-structure methods especially when data deviates from linearity.

This approach is suitable for drug discovery, personalized recommendations, and adaptive testing where data bias is inevitable. It requires only an estimate of the bias bound and feature vectors, making it applicable in real-time decision systems. Its robustness reduces the need for extensive model validation, saving resources. Long-term, integrating bias estimation and nonlinear models could further broaden its impact, enabling more resilient AI systems in dynamic environments.

The method depends on a prior bias bound, which may be hard to estimate accurately. Excessively large actual bias can diminish the advantage of the structure-aware approach. Computational costs grow with the number of arms and feature dimensions, limiting scalability. Handling non-stationary biases or high-dimensional features remains an open challenge, requiring further algorithmic development.