Principal-Agent Reward Shaping in MDPs
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.
Code (1)
Similar Papers 제목 키워드 기반
BAMDP Shaping: a Unified Theoretical Framework for Intrinsic Motivation and Reward Shaping
Intrinsic motivation (IM) and reward shaping are common methods for guiding the exploration of reinforcement learning (RL) agents by adding pseudo-rewards. Designing these rewards is challenging, however, and they can co…
Reinforcement Learning (RL)Accelerating lifelong reinforcement learning via reshaping rewards
The reinforcement learning (RL) problem is typically formalized as the Markov Decision Process (MDP), where an agent interacts with the environment to maximize the long-term expected reward. As an important branch of RL,…
Lifelong learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards
We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward struct…
InformativenessMaximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards
We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward struct…
InformativenessCalculus on MDPs: Potential Shaping as a Gradient
In reinforcement learning, different reward functions can be equivalent in terms of the optimal policies they induce. A particularly well-known and important example is potential shaping, a class of functions that can be…
Math