# Contracting With a Reinforcement Learning Agent by Playing Trick or Treat

arXiv: https://arxiv.org/abs/2410.13520 · HTML: https://mlsanity.com/paper/2410.13520/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 8 of its 31 references that are in the map.
- First posted on arXiv 17 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 8 of 8)

- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Generalized Principal-Agency: Contracts, Information, Games and Beyond](https://mlsanity.com/paper/2209.01146/) (2022)
- [Persuading Farsighted Receivers in MDPs: the Power of Honesty](https://mlsanity.com/paper/2306.12221/) (2023)
- [Regret-Minimizing Contracts: Agency Under Uncertainty](https://mlsanity.com/paper/2402.13156/) (2024)

## Abstract (arXiv)

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. This is accomplished by committing to a payment scheme (a.k.a. contract) at each step, specifying a monetary transfer from the principal to the agent for every possible outcome. 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 optimal policy, leveraging a compact way of representing histories for this purpose. Unfortunately, the policy produced by such an algorithm cannot be readily implemented, as it is only approximately incentive compatible, meaning that the agent is incentivized 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. This method can be generally applied to any approximately-incentive-compatible policy, and it generalized a related approach that has already been discovered for classical principal-agent problems to more general settings in MDPs.