Contracting with a Learning Agent
Guru Guruganesh Yoav Kolumbus Jon Schneider Inbal Talgam-Cohen Emmanouil-Vasileios Vlatakis-Gkaragkounis Joshua R. Wang S. Matthew Weinberg
Many real-life contractual relations differ completely from the clean, static
model at the heart of principal-agent theory. Typically, they involve repeated
strategic interactions of the principal and agent, taking place under
uncertainty and over time. While appealing in theory, players seldom use
complex dynamic strategies in practice, often preferring to circumvent
complexity and approach uncertainty through learning. We initiate the study of
repeated contracts with a learning agent, focusing on agents who achieve
no-regret outcomes.
  Optimizing against a no-regret agent is a known open problem in general
games; we achieve an optimal solution to this problem for a canonical contract
setting, in which the agent's choice among multiple actions leads to
success/failure. The solution has a surprisingly simple structure: for some
$\alpha > 0$, initially offer the agent a linear contract with scalar $\alpha$,
then switch to offering a linear contract with scalar $0$. This switch causes
the agent to ``free-fall'' through their action space and during this time
provides the principal with non-zero reward at zero cost. Despite apparent
exploitation of the agent, this dynamic contract can leave \emph{both} players
better off compared to the best static contract. Our results generalize beyond
success/failure, to arbitrary non-linear contracts which the principal rescales
dynamically.
  Finally, we quantify the dependence of our results on knowledge of the time
horizon, and are the first to address this consideration in the study of
strategizing against learning agents.