Technical Summary: MESHA for Strategic Linear Bandits

Problem Formulation

This paper addresses the Fixed-Budget Best Arm Identification (BAI) problem within the setting of Strategic Linear Bandits. In this environment, a learner seeks to identify the optimal arm (candidate) from a pool of $K$ arms within a fixed budget of $T$ rounds. Each arm $i$ possesses a true, unobservable feature vector $x_i \in \mathbb{R}^d$ and a true quality score $\mu_i = \langle \theta^*, x_i \rangle$, where $\theta^*$ is an unknown latent vector.

The critical challenge is that arms act as self-interested agents. Their primary objective is to maximize the probability of being identified as the best arm. To achieve this, arms may strategically misreport their feature vectors ($x_{t,i} \neq x_i$) to manipulate the learner's sampling decisions. While the learner observes the reported features and selects an arm, the actual reward received is generated based on the arm's true feature vector plus noise. The goal is to design an algorithm that identifies the optimal arm with high probability despite these strategic manipulations, assuming the arms reach a Nash Equilibrium (NE).

Methodology: MESHA Algorithm

The authors propose MESHA (Mechanism-Enforced Sequential Halving), an algorithm that integrates a uniform sampling rule with a mechanism-based elimination strategy. MESHA operates over $R = \lceil \log_2 K \rceil$ epochs.

1. Uniform Sampling Rule

Unlike state-of-the-art (SOTA) linear BAI algorithms that rely on G-optimal design (OD) to allocate sampling budgets based on feature geometry, MESHA employs naïve uniform sampling. Within each epoch, every active arm is pulled an equal number of times.

• Rationale: This decouples the sampling allocation from the arms' reported features. It prevents strategic arms from manipulating the geometry of the feature space to starve the optimal arm of samples (a vulnerability identified in OD-based methods).

2. Epoch-wise Grim Trigger Condition (GTC)

At the end of each epoch, MESHA applies a Grim Trigger Condition (GTC) to eliminate arms exhibiting severe strategic deviations.

• Mechanism: For each active arm $i$, the algorithm computes two bounds based on the history of the current epoch:
  • Lower Confidence Bound (RLCB): The predicted cumulative reward based on the arm's reported features and the learner's estimator.
  • Upper Confidence Bound (AUCB): The upper bound on the actual observed cumulative rewards.
• Elimination: If $RLCB_{r,i} > AUCB_{r,i}$, the arm is eliminated. This condition detects a fundamental inconsistency: if an arm inflates its reported features to appear more attractive, its predicted rewards (based on reported features) will exceed its actual rewards (based on true features).
• Incentive Structure: Under a Nash Equilibrium, rational arms are incentivized to pass this check to avoid permanent elimination (which yields zero utility). Thus, the GTC forces arms to constrain their strategic deviations.

3. Sequential Halving

Arms that pass the GTC check are retained. The algorithm then eliminates the bottom half of the remaining arms based on their estimated mean rewards, proceeding to the next epoch with a reduced active set until a single arm remains.

Key Contributions

1. The MESHA Algorithm and Theoretical Guarantees

The paper proposes MESHA and proves that under an arbitrary Nash Equilibrium, any arm attempting to maximize its identification probability must pass the GTC check.

• Failure Probability Bound: The authors derive an upper bound on the failure probability of MESHA:
  $$P(\Delta_{i_{out}} \geq \zeta) \leq \lceil \log_2 K \rceil^2 \frac{1}{T} \exp\left( - \frac{T \zeta^2}{18 K d^2 \log^2(1 + T/\lceil \log_2 K \rceil)} \right)$$
• Convergence: The failure probability exhibits exponential decay with respect to the budget $T$, preserving the convergence guarantees of non-strategic SOTA baselines, albeit with an additional statistical overhead of $O(d^2 \log T)$ due to the need to disincentivize strategic deviations.

2. Failure of State-of-the-Art Linear BAI Algorithms

The paper demonstrates that current SOTA algorithms (specifically OD-LinBAI and OptGTM) are fundamentally vulnerable in strategic settings:

• Vulnerability of G-Optimal Design: OD-based algorithms rely on feature geometry to allocate samples. Strategic arms can coordinate to report features such that the optimal arm's feature vector lies within the cone spanned by suboptimal arms. This causes the G-optimal design to allocate zero samples to the optimal arm (a "starvation attack"), leading to identification failure.
• Limitations of Existing Mechanisms: The paper critiques OptGTM (designed for Regret Minimization) for relying on a strong assumption (Lemma E.1 in [4]) that arms' reported means perfectly align with true means. This assumption effectively sidesteps equilibrium analysis. In contrast, MESHA's epoch-wise GTC actively constrains behavior under weaker, more practical assumptions without requiring perfect alignment.

3. Numerical Validation

Extensive experiments compare MESHA against baselines including Sequential Halving (SH), Successive Rejects (SR), OD-LinBAI, OD-LinBAI-GTC, and OptGTM.

• Robustness: OD-LinBAI and OD-LinBAI-GTC fail completely (failure probability $\to 1$) under strategic manipulation due to the starvation attack.
• Performance: MESHA consistently achieves low failure probabilities across varying budgets ($T$), dimensions ($d$), and arm counts ($K$).
• Scalability: As $K$ increases, MESHA's advantage over feature-agnostic baselines (SH, SR) widens, demonstrating the value of utilizing feature information even in strategic environments. As $d$ increases, MESHA's performance approaches that of an oracle baseline (OD-LinBAI with true features).

Significance and Claims

The paper claims to be the first to comprehensively explore the BAI task in the presence of strategic arms. Its significance lies in:

1. Bridging Mechanism Design and BAI: It successfully adapts mechanism design principles (GTC) to the Best Arm Identification setting, moving beyond the Regret Minimization focus of prior work.
2. Structural Insight: It identifies that the failure of G-optimal design in strategic settings is structural (unavoidable by reward-level consistency checks alone) and necessitates a decoupling of sampling from reported features.
3. Practical Efficacy: The results suggest that MESHA provides a robust solution for scenarios like hiring platforms or clinical trials where candidates or treatments may misrepresent their attributes to increase selection chances.

The authors modestly note that their theoretical guarantees rely on the assumption of Nash Equilibrium (fully rational agents) and that the $O(d^2 \log T)$ overhead may warrant further investigation to determine if it is a fundamental limitation of the problem or an artifact of the current mechanism design.