New Algorithm Improves Best Arm Identification in Strategic Bandits

This paper introduces MESHA, a novel algorithm designed for the Best Arm Identification (BAI) problem within strategic linear bandit environments. In such settings, individual "arms" or options may strategically manipulate their reported characteristics to increase their chances of being chosen, even if their true underlying features would not warrant it. MESHA counters this by employing a dual strategy: uniform sampling to dilute the impact of strategic misreporting, and an epoch-wise Grim Trigger Condition that identifies and eliminates arms whose reported features significantly deviate from reality. The theoretical analysis demonstrates that under any Nash Equilibrium, arms are incentivized to pass the Grim Trigger Condition check to maximize their selection probability. The algorithm provides an upper bound on failure probability within a fixed budget. Furthermore, the study highlights that conventional linear BAI algorithms, particularly those relying on G-optimal design, are vulnerable in strategic environments because their optimal design-based sampling rules can inadvertently neglect the truly optimal arm due to misreported features. Extensive numerical experiments confirm MESHA's effectiveness, showing superior performance compared to both optimal design-based sampling rules and feature-agnostic baselines. This suggests a robust solution for decision-making in competitive or deceptive environments.