Research map / Reinforcement learning / MDPs and planning
Principal-Agent Reward Shaping in MDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies principal-agent reward shaping in MDPs under a bonus budget, proving NP-hardness and giving an FPTAS for stochastic trees and a pseudo-polynomial exact algorithm (Pareto frontier) for finite-horizon deterministic decision processes.
Problem
Principal must choose a bounded-budget bonus reward to shape a self-interested agent's reward so the agent's optimal MDP policy maximizes the principal's utility; the problem is NP-hard in general.
Approach
Uses minimal bonus implementations and an indifference observation to decouple bonus allocation across subtrees, enabling bottom-up dynamic programming with discretized budgets for stochastic trees; for deterministic finite-horizon DDPs, propagates Pareto frontiers of (agent, principal) utility vectors and filters by the budget-implementability condition.
Key results
- Stochastic tree algorithm STUM is an FPTAS: uses budget B(1+alpha) and runs in O(|A||S|k(|S|/alpha)^3) time with utility at least the optimum under budget B.
- Pareto-frontier algorithm MDPPF is exact for epsilon-discrete rewards, running in O(|S||A|H^2/epsilon log(|A|H/epsilon)) time, and gives an additive H*epsilon approximation with budget B+H*epsilon for general rewards.
- Simulations on 10,000 random instances show MDPPF's utility lies between the Corollary lower bound and the brute-force optimum, converging as epsilon decreases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use STUM on stochastic-tree MDPs with budget B + ε|S| | Principal-agent reward shaping · Stochastic trees | Principal utility | Helped |
| Use MDPPF with ε-discrete reward functions | Principal-agent reward shaping · Acyclic deterministic decision processes | Principal utility | Helped |
| Use MDPPF with discretized rewards and budget B + Hε | Principal-agent reward shaping · Acyclic deterministic decision processes with general rewards | Principal utility | Helped |
| Decrease the discretization factor ε | MDPPF · Generated finite-horizon DDPs | Principal utility | Helped |
| Use MDPPF instead of its Corollary lower-bound guarantee | MDPPF · Generated finite-horizon DDPs | Principal utility | Helped |
| Increase the budget B | MDPPF · Generated finite-horizon DDPs | Principal utility approximation accuracy | Helped |
| Use ε-discretized rewards rather than exact rewards | MDPPF · Generated finite-horizon DDPPs | Principal utility | Hurt |
Surprising findings
- Principal's utility as a function of budget can be discontinuous, since the agent's indifference requires an exact bonus equal to the loss.
Limitations
- Tree-structured stochastic MDP algorithm runtime depends on budget discretization; DDP algorithm is only approximate for general (non-discrete) rewards.
- Assumes agent breaks ties in favor of principal; relaxing this requires extra tiny bonuses.
- Evaluation limited to small synthetic instances with brute-force comparison.
Experimental setup
Benchmarks: randomly generated layered DDP instances (5 layers, 10 states, 10 actions)
Metrics: principal utility approximation vs. discretization factor epsilon principal utility vs. budget
Baselines: brute force algorithm
Builds on: policy teaching environment design money burning
Closest papers by meaning
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.87)
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.87)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.85)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.85)
- Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.84)
- Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.