# Principal-Agent Reward Shaping in MDPs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 30 Dec 2023.

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

- [A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress](https://mlsanity.com/paper/1806.06877/) (2018)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Learning to Utilize Shaping Rewards: A New Approach of Reward Shaping](https://mlsanity.com/paper/2011.02669/) (2020)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [Consequences of Misaligned AI](https://mlsanity.com/paper/2102.03896/) (2021)
- [Incomplete Contracting and AI Alignment](https://mlsanity.com/paper/1804.04268/) (2018)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [The Complexity of Contracts](https://mlsanity.com/paper/2002.12034/) (2020)
- [Model-based Constrained MDP for Budget Allocation in Sequential Incentive Marketing](https://mlsanity.com/paper/2303.01049/) (2023)
- [Admissible Policy Teaching through Reward Design](https://mlsanity.com/paper/2201.02185/) (2022)
- [Automated Dynamic Mechanism Design](https://mlsanity.com/paper/2105.06008/) (2021)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [Efficient Algorithms for Planning with Participation Constraints](https://mlsanity.com/paper/2205.07767/) (2022)
- [Optimal Common Contract with Heterogeneous Agents](https://mlsanity.com/paper/1911.04146/) (2019)

## Built on by (most cited first, 13 of 13)

- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024)
- [Extracting Heuristics from Large Language Models for Reward Shaping in Reinforcement Learning](https://mlsanity.com/paper/2405.15194/) (2024)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents](https://mlsanity.com/paper/2412.16318/) (2024)
- [Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals](https://mlsanity.com/paper/2505.23124/) (2025)
- [Reward Shaping for (Inference-Time) Alignment: A Stackelberg Game Perspective](https://mlsanity.com/paper/2602.02572/) (2026)
- [Robust Reward Design for Markov Decision Processes](https://mlsanity.com/paper/2406.05086/) (2024)
- [Contracting With a Reinforcement Learning Agent by Playing Trick or Treat](https://mlsanity.com/paper/2410.13520/) (2024)
- [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025)
- [Quantum-Inspired Reinforcement Learning for Secure and Sustainable AIoT-Driven Supply Chain Systems](https://mlsanity.com/paper/2601.22339/) (2026)

## Abstract (arXiv)

Principal-agent problems arise when one party acts on behalf of another, leading to conflicts of interest. The economic literature has extensively studied principal-agent problems, and recent work has extended this to more complex scenarios such as Markov Decision Processes (MDPs). In this paper, we further explore this line of research by investigating how reward shaping under budget constraints can improve the principal's utility. We study a two-player Stackelberg game where the principal and the agent have different reward functions, and the agent chooses an MDP policy for both players. The principal offers an additional reward to the agent, and the agent picks their policy selfishly to maximize their reward, which is the sum of the original and the offered reward. Our results establish the NP-hardness of the problem and offer polynomial approximation algorithms for two classes of instances: Stochastic trees and deterministic decision processes with a finite horizon.