  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.
