Potential-Based Shaping and Q-Value Initialization are Equivalent

By Eric Wiewiora. 2003

217 citations recorded by the source corpus.

Shaping has proven to be a powerful but precarious means of improving reinforcement learning performance. Ng, Harada, and Russell (1999) proposed the potential-based shaping algorithm for adding shaping rewards in a way that guarantees the learner will learn optimal behavior. In this note, we prove certain similarities between this shaping algorithm and the initialization step required for several reinforcement learning algorithms. More specifically, we prove that a reinforcement learner with initial Q-values based on the shaping algorithm's potential function make the same updates throughout learning as a learner receiving potential-based shaping rewards. We further prove that under a broad category of policies, the behavior of these two learners are indistinguishable. The comparison provides intuition on the theoretical properties of the shaping algorithm as well as a suggestion for a simpler method for capturing the algorithm's benefit. In addition, the equivalence raises previously unaddressed issues concerning the efficiency of learning with potential-based shaping.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “ T+1 = R T+1 v0, can also be derived via reward shaping; however, the offset has to be added at the beginning: R 1 = R1 +v0. Reward shaping requires for the shaping reward Fand a potential function [76,122]: F(s t;a t;s t+1) = ( s t+1) ( s t) : (A200) For introducing a reward of cat time t= kand rem”
Potential-based difference rewards for multiagent reinforcement learning (2014, background): “Wiewiora [18] later proved that an agent learning with potential-based reward shaping and no knowledge-based Qtable initialisation will behave identically to an agent without reward shaping when the latter agent’s value function is initialised with the same potential function.”
Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Tasks (2020, background): “Potential-based look-ahead advice (Wiewiora 2003) further extends PBRS such that the potential function also depends on actions: F (s, a, s, a) = γΦ(s, a)− Φ(s, a), where a is chosen by the current policy.”
Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning (2015, methodology): “There are multiple interpretations of the multitask pretraining. From a reinforcement learning perspective, instantiating the state-action value function approximator is equivalent to reward shaping (Wiewiora, 2003), a method of augmenting the reward signal of an MDP so as to make it more informativ”
Social reward shaping in the prisoner's dilemma (2008, background): “In the context of Q-learning, adding potentialbased shaping rewards via potential function Φ(s) has the same effect as initializing the Q function to Φ(s) [9].”
Shaping Rewards for Reinforcement Learning with Imperfect Demonstrations using Generative Models (2020, background): “[38] demonstrated potential functions for discrete state and action spaces, that were constrained to lowdimensional discrete planning problems, which are not applicable to robotics.”
Autonomous Agents and Multi-agent Systems Manuscript No. Learning Potential Functions and Their Representations for Multi-task Reinforcement Learning (unknown): “[87,88] introduced shaping functions of the form Fxa x′a′ = γΦ(x′, a′)−Φ(x, a), where a′ is defined as in the learning rule.”
Policy Transfer using Reward Shaping (2015, background): “static potential-based reward shaping is shown to be equivalent, given the same experiences, to Q-value initialization [24], which is exactly what many transfer learning techniques do [19, 21].”
Transfer in Reinforcement Learning via Shared Features (2012, methodology): “Wiewiora (2003) showed that this is equivalent to using the same reward function as a non-uniform initial state valu function, or with 2.”
Theoretical considerations of potential-based reward shaping for multi-agent systems (2011, background): “In single-agent problem domains the equivalence of Q-table initialisation and potential-based reward shaping can be proven also in SARSA and other temporal difference algorithms [33].”
Intrinsically Motivated Reinforcement Learning: An Evolutionary Perspective (2010, background): “Wiewiora [54] showed that adding shaping rewards is equivalent to initializing the agent’s -function to nonzero values.”
Integrating reinforcement learning with human demonstrations of varying ability (2011, background): “This is effectively changing the initialization of the Q-value function, or, equivalently [33], providing a shaping reward to the state-action pairs that are selected by the rules.”
Reward (Mis)design for Autonomous Driving (2021, background): “There is a small canon of reward-shaping research that focuses on how to perform reward shaping with certain safety guarantees [34, 54, 4, 11, 17].”