MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

Poster E: Wednesday -- 11:00 - 12:30

Xin Li, Zixin Zhong

Keywords: strategic linear bandits, best arm identification, mechanism design.

We design and analyze Mechanism-Enforced Sequential HAlving (MESHA), an algorithm for Best Arm Identification (BAI) in strategic linear bandits, where each arm may strategically misreport its feature vector to maximize the probability of being identified as the best arm, while rewards are generated from the arms' true but unobservable features. The design of MESHA applies the na\"ive uniform sampling rule and an epoch-wise Grim Trigger Condition (GTC): the former reduces the impact of arms' strategic behaviours and the latter eliminates arms whose reported features severely deviate from the ground truth. Considering an arbitrary Nash Equilibrium, we prove that any arm would attempt to pass the GTC check to maximize its identified probability and derive an upper bound on the failure probability of MESHA within a fixed budget $T$. We also show that state-of-the-art linear BAI algorithms with $G$-optimal design would fail in such strategic environment, as the optimal design (OD)-based sampling rule based on strategically reported features may starve the optimal arm of any sampling budget. Finally, extensive numerical experiments indicate that MESHA outperforms the OD-based and feature-ignostic baselines, corroborating the efficacy of MESHA as well as the tightness of our upper bound on its failure probability.