Low-Regret Learning in Strategic Bandits via Incentive Design

Online platforms often recommend products based on information reported by providers, who are self-interested and may misreport information to maximize their own profits. To help platforms make decisions, we study how the learner can minimize its regret against arms' misreporting features in strategic bandits. We propose the PALinUCB algorithm whose efficacy roots from a delicately designed contract utility. We show that, under PALinUCB, the regret is largely determined by the deviation incentive of the optimal arm. In particular, when the optimal arm behaves appropriately, the resulting joint strategy profile forms a $\mathrm{poly}(\log T)$-approximate Nash equilibrium, where each suboptimal arm is selected only $\mathrm{poly}(\log T)$ times. Moreover, under Nash equilibrium, PALinUCB achieves a $\mathrm{poly}(\log T)$ regret. Further, numerical results corroborate our theoretical findings and indicate that our contract design can substantially shape arms' strategic behavior for the interest of the learner, and PALinUCB remains robust under strategic reporting.