Contracting With a Reinforcement Learning Agent by Playing Trick or Treat

We study *principal-agent* problems where a *farsighted* agent takes costly actions in an MDP. The core challenge in these settings is that agent's actions are *hidden* to the principal, who can only observe their outcomes, namely state transitions and their associated rewards. Thus, the principal's goal is to devise a policy that incentives the agent to take actions leading to desirable outcomes, by committing to a payment scheme (a.k.a. *contract*) at each step. Interestingly, we show that Markovian policies are unfit in these settings, as they do not allow to achieve the optimal principal's utility and are constitutionally intractable. Thus, accounting for history in unavoidable, and this begets considerable additional challenges compared to standard MDPs. Nevertheless, we design an efficient algorithm to compute an approximately optimal policy, leveraging a compact way of representing histories for this purpose. Unfortunately, this policy incentivizes the agent to take the desired actions only approximately. To fix this, we design an efficient method to make such a policy incentive compatible, by only introducing a negligible loss in principal's utility, generalizing an existing technique for classical principal-agent problems.