Theoretical considerations of potential-based reward shaping for multi-agent systems

By Sam Devlin, Daniel Kudenko. 2011

139 citations recorded by the source corpus.

Potential-based reward shaping has previously been proven to both be equivalent to Q-table initialisation and guarantee policy invariance in single-agent reinforcement learning. The method has since been used in multi-agent reinforcement learning without consideration of whether the theoretical equivalence and guarantees hold. This paper extends the existing proofs to similar results in multi-agent systems, providing the theoretical background to explain the success of previous empirical studies. Specifically, it is proven that the equivalence to Q-table initialisation remains and the Nash Equilibria of the underlying stochastic game are not modified. Furthermore, we demonstrate empirically that potential-based reward shaping affects exploration and, consequentially, can alter the joint policy converged upon.

How researchers see this paper

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

Citations in the corpus

Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “In RL, reward shaping is popular for learning desired behavior in various domains (Ng et al., 1999; Babes et al., 2008; Devlin & Kudenko, 2011), which inspires our idea for ﬁnding diverse strategic behavior.”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “This approach is also extended for online POMDP settings [33] and multi-agent setting [30], though deﬁning the potential function is challenging and usually needs speciﬁc domain knowledge.”
Reinforcement Learning with Multiple Experts: A Bayesian Model Combination Approach (2018, background): “More recently, policy invariance has been extended for non-stationary time-dependent potential functions of the form F (s, a, t, s′, t′) = γΦ(s′, t′)− Φ(s, t) (6) (Devlin and Kudenko [2012]), for action-dependence (Wiewiora et al. [2003]), as well as for partiallyobserved (Eck et al.”
Potential-based reward shaping for finite horizon online POMDP planning (2016, methodology): “In particular we consider a popular technique for implicitly guiding agents towards large future rewards from the related field of reinforcement learning called potential-based reward shaping (PBRS) [2,6,7,14] and apply this technique to online POMDP planning.”
Policy invariance under reward transformations for multi-objective reinforcement learning (2017, methodology): “In MARL, work by Devlin and Kudenko [6] proved that PBRS does not alter the set of Nash equilibria of an SG.”
Combining reward shaping and hierarchies for scaling to large multiagent systems (2016, unknown): “In Q-learning, reward shaping can be represented by the following formula (Ng et al ., 1999; Devlin & Kudenko, 2011):”
Autonomous Agents and Multi-agent Systems Manuscript No. Learning Potential Functions and Their Representations for Multi-task Reinforcement Learning (unknown): “In multiagent RL, potential-based shaping provably preserves the Nash equilibrium in stochastic games [11,44].”
Prosocial learning agents solve generalized Stag Hunts better than selfish ones (2017, background): “cross many ﬁelds. Existing work in RL has proposed modiﬁcations to independent MARL to increase the probability of the system converging to a preferred equilibrium (Littman, 2001; Babes et al., 2008; Devlin and Kudenko, 2011; Devlin et al., 2011; Kapetanakis and Kudenko, 2002; Yoshida et al., 2008; ”
Context-sensitive reward shaping for sparse interaction multi-agent systems (2016, background): “Moreover, it is also proven that PBRS in MAS does not change the Nash equilibria of the underlying stochastic game the agents are playing (Devlin & Kudenko, 2011).”
Potential-based difference rewards for multiagent reinforcement learning (2014, background): “Potential-based reward shaping has also recently been used to improve multiagent reinforcement learning solutions [3, 5, 6].”
A Theoretical and Empirical Analysis of Reward Transformations in Multi-Objective Stochastic Games (2017, background): “Potential-Based Reward Shaping (PBRS) is a form of reward shaping which has been proven to preserve the Nash equilibria of a SG [6].”