Calculus on MDPs: Potential Shaping as a Gradient
This work provides a theoretical foundation for reward shaping in reinforcement learning, offering incremental insights into policy invariance and reward selection.
The paper tackles the problem of reward function equivalence in reinforcement learning by formally connecting potential shaping to gradients using discrete calculus on MDP graphs, strengthening existing results and providing a method to select unique rewards from equivalence classes.
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 added to any reward function without changing the optimal policy set under arbitrary transition dynamics. Potential shaping is conceptually similar to potentials, conservative vector fields and gauge transformations in math and physics, but this connection has not previously been formally explored. We develop a formalism for discrete calculus on graphs that abstract a Markov Decision Process, and show how potential shaping can be formally interpreted as a gradient within this framework. This allows us to strengthen results from Ng et al. (1999) describing conditions under which potential shaping is the only additive reward transformation to always preserve optimal policies. As an additional application of our formalism, we define a rule for picking a single unique reward function from each potential shaping equivalence class.