Motivated by the phenomenon of strategic agents gaming a recommender system to maximize the number of times users are recommended, we study a strategic variant of the linear contextual bandit problem, where arms strategically misinform the learner about observed contexts. privately. % under manipulation of the strategic context. We treat the algorithm design problem as one of \emph{mechanism design} under uncertainty and propose the Optimistic Gloom Triggering Mechanism (OptGTM) that minimizes regret while incentivizing agents to be approximately truthful. We show that OptGTM achieves sublinear regret even though agents have no constraints on their ability to fool the learning algorithm by misreporting contexts. We then also show that not taking into account the strategic nature of agents results in linear regret. However, striking a balance between incentive compatibility and regret minimization has been shown to be inevitable. More generally, this work provides insights into the intersection of online learning and mechanism design.
