Prior-Agnostic Incentive-Compatible Exploration
This addresses incentive misalignment in online recommendation platforms, offering a prior-agnostic solution that is incremental over prior Bayesian approaches.
The paper tackles the problem of aligning incentives between a principal and agents in bandit settings where agents may not follow recommendations due to misaligned exploration benefits, showing that weighted swap regret bounds can induce agents to follow forecasts in an approximate Bayes Nash equilibrium, even with conflicting prior beliefs and no knowledge of agent beliefs.
In bandit settings, optimizing long-term regret metrics requires exploration, which corresponds to sometimes taking myopically sub-optimal actions. When a long-lived principal merely recommends actions to be executed by a sequence of different agents (as in an online recommendation platform) this provides an incentive misalignment: exploration is "worth it" for the principal but not for the agents. Prior work studies regret minimization under the constraint of Bayesian Incentive-Compatibility in a static stochastic setting with a fixed and common prior shared amongst the agents and the algorithm designer. We show that (weighted) swap regret bounds on their own suffice to cause agents to faithfully follow forecasts in an approximate Bayes Nash equilibrium, even in dynamic environments in which agents have conflicting prior beliefs and the mechanism designer has no knowledge of any agents beliefs. To obtain these bounds, it is necessary to assume that the agents have some degree of uncertainty not just about the rewards, but about their arrival time -- i.e. their relative position in the sequence of agents served by the algorithm. We instantiate our abstract bounds with concrete algorithms for guaranteeing adaptive and weighted regret in bandit settings.