Incentivized Learning in Principal-Agent Bandit Games
Antoine Scheid Daniil Tiapkin Etienne Boursier Aymeric Capitaine El Mahdi El Mhamdi Eric Moulines Michael I. Jordan Alain Durmus
This work considers a repeated principal-agent bandit game, where the
principal can only interact with her environment through the agent. The
principal and the agent have misaligned objectives and the choice of action is
only left to the agent. However, the principal can influence the agent's
decisions by offering incentives which add up to his rewards. The principal
aims to iteratively learn an incentive policy to maximize her own total
utility. This framework extends usual bandit problems and is motivated by
several practical applications, such as healthcare or ecological taxation,
where traditionally used mechanism design theories often overlook the learning
aspect of the problem. We present nearly optimal (with respect to a horizon
$T$) learning algorithms for the principal's regret in both multi-armed and
linear contextual settings. Finally, we support our theoretical guarantees
through numerical experiments.