mlsanityData to 14 Oct 2026

Principal-Agent Reward Shaping in MDPs

arXiv 2401.00298 ↗First posted 30 Dec 2023cs.AIcited by 13

Not on the map. Why?

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.

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

14 of 45 references.

References · 14

  1. 2018A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progresscited by 298
  2. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
  3. 2020Learning to Utilize Shaping Rewards: A New Approach of Reward Shapingcited by 114
  4. 2020Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learningcited by 81
  5. 2021Consequences of Misaligned AIcited by 80
  6. 2018Incomplete Contracting and AI Alignmentcited by 62
  7. 2014Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problemscited by 46
  8. 2020The Complexity of Contractscited by 16
  9. 2023Model-based Constrained MDP for Budget Allocation in Sequential Incentive Marketingcited by 15
  10. 2022Admissible Policy Teaching through Reward Designcited by 12
  11. 2021Automated Dynamic Mechanism Designcited by 8
  12. 2023Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Modelcited by 7
2 more
  1. 2022Efficient Algorithms for Planning with Participation Constraintscited by 6
  2. 2019Optimal Common Contract with Heterogeneous Agentscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 9; 2025: 2; 2026: 2.

13 papers.

Sort:

By area:

  1. 2024Contracting with a Learning Agentcited by 23
  2. 2024Incentivized Learning in Principal-Agent Bandit Gamescited by 13
  3. 2024Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contractscited by 9
  4. 2024Extracting Heuristics from Large Language Models for Reward Shaping in Reinforcement Learningcited by 8
  5. 2024Games with Payments between Learning Agentscited by 3
  6. 2024Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationalitycited by 3
  7. 2024Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agentscited by 2
  8. 2025Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivalscited by 2
  9. 2026Reward Shaping for (Inference-Time) Alignment: A Stackelberg Game Perspectivecited by 2
  10. 2024Robust Reward Design for Markov Decision Processescited by 1
  11. 2024Contracting With a Reinforcement Learning Agent by Playing Trick or Treatcited by 0
  12. 2025Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisitioncited by 0
1 more
  1. 2026Quantum-Inspired Reinforcement Learning for Secure and Sustainable AIoT-Driven Supply Chain Systemscited by 0