Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces MESHA, an algorithm designed for Best Arm Identification (BAI) in strategic linear bandits where arms can misreport their features to appear optimal. By employing a naive uniform sampling rule alongside an epoch-wise Grim Trigger Condition (GTC), MESHA effectively mitigates the impact of strategic misreporting and ensures that only arms with consistent feature reporting are considered. The results demonstrate that MESHA significantly outperforms existing state-of-the-art algorithms in this context, highlighting the limitations of optimal design-based approaches in strategic environments.
MESHA outperforms traditional optimal design methods in strategic linear bandits, revealing their vulnerability to misreporting tactics.
We design and analyze \underline{M}echanism-\underline{E}nforced \underline{S}equential \underline{HA}lving (MESHA), an algorithm for Best Arm Identification (BAI) in strategic linear bandits. In this setting, each arm may strategically misreport its feature vector to maximize the probability of being identified as the best arm, when 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 {\it starve} the optimal arm of any sampling budget. Finally, extensive numerical experiments indicate that MESHA outperforms baselines that rely on OD-based sampling rules as well as the feature-agnostic baselines, corroborating the efficacy of MESHA.