Year: 2021

Abstract:
Multi-Agent Reinforcement Learning (MARL) has demonstrated significant success by virtue of collaboration across agents. Recent work, on the other hand, introduces surprise which quantifies the degree of change in an agent’s environment. Surprise-based learning has received significant attention in the case of single-agent entropic settings but remains an open problem for fast-paced dynamics in multi-agent scenarios. A potential alternative to address surprise may be realized through the lens of free-energy minimization. We explore surprise minimization in multi-agent learning by utilizing the free energy across all agents in a multiagent system. A temporal Energy-Based Model (EBM) represents an estimate of surprise which is minimized over the joint agent distribution. Our formulation of the EBM is theoretically akin to the minimum conjugate entropy objective and highlights suitable convergence towards minimum surprising states. We further validate our theoretical claims in an empirical study of multi-agent tasks demanding collaboration in the presence of fast-paced dynamics. sites.google.com/view/surprise-web/

text: sites.google.com/view/surprise-web/

heading: 1 INTRODUCTION
text: The rise of RL has led to an increasing interest in the study of multi-agent systems (Lowe et al., 2017; Vinyals et al., 2019), commonly known as Multi-Agent Reinforcement Learning (MARL). In the case of partially observable settings, MARL enables the learning of policies with centralised training and decentralised control (Kraemer & Banerjee, 2016). This has proven to be useful for exploiting value-based methods which motivate collaboration across large number of agents. But how do agents behave in the presence of sudden environmental changes?
Consider the problem of autonomous driving wherein a driver (agent) autonomously operates a vehicle in real-time. The driver learns to optimize the reward function by maintaining constant speed and covering more distance in different traffic conditions. Whenever the vehicle approaches an obstacle, the driver acts to avoid it by utilizing the brake and directional steering commands. However, due to the fast-paced dynamics of the environment, say fast-moving traffic, the agent may abruptly encounter an obstacle (a person running across the street) which may result in a collision. Irrespective of the optimal action (pushing of brakes) executed by the agent, the vehicle may fail to evade the collision as a result of the abrupt temporal change.
The above arises as a consequence of surprise, which is defined as a statistical measure of uncertainty. Surprise minimization (Berseth et al., 2019) is a recent phenomenon observed in the case of singleagent RL methods which deals with environments consisting of rapidly changing states. In the case of model-based RL (Kaiser et al., 2019), surprise minimization is used as an effective planning tool in the agent’s model (Berseth et al., 2019) whereas in the case of model-free RL, surprise minimization is witnessed as an intrinsic motivation (Achiam & Sastry, 2017; Macedo et al., 2004) or generalization problem (Chen, 2020). On the other hand, MARL does not account for surprise across agents as a result of which agents remain unaware of drastic changes in the environment (Macedo & Cardoso, 2005). Thus, surprise minimization in the case of multi-agent settings requires attention from a critical standpoint.
A potential pathway to treat surprising states may be realized in light of free-energy minimization. The free-energy principle depicts convergence to local niches and provides a general recipe for cognitive stability among agents. Through this lens, we unify surprise with free-energy in the multi-agent setting. We construct a temporal EBM which represents an estimate of surprise agents
may face in the environment. All agents jointly minimize this estimate utilizing temporal difference learning upon their value functions and the EBM. Our formulation of free-energy minimization is theoretically akin to minimizing the entropy in conjugate gradient space. This insight provides a suitable convergence result towards minimum surprising states (or niches) of the agent state distributions. In an empirical study of multi-agent tasks which present significant collaboration bottlenecks and fast-paced dynamics, we validate our theoretical claims and motivate the practical usage of EBMs in MARL.

heading: 2 RELATED WORK
text: Surprise Minimization: Despite the recent success of value-based methods (Mnih et al., 2016; Hessel et al., 2017) RL agents suffer from spurious state spaces and encounter sudden changes in trajectories. Quantitatively, surprise has been studied as a measure of deviation (Berseth et al., 2019; Chen, 2020) among states encountered by the agent during its interaction with the environment. While exploring (Burda et al., 2019; Thrun, 1992) the environment, agents tend to have higher deviation among states which is gradually reduced by gaining a significant understanding of state-action transitions. In the case of model-based RL, agents can leverage spurious experiences (Berseth et al., 2019) and plan effectively for future steps. On the other hand, in the case of model-free RL, surprise results in sample-inefficient learning (Achiam & Sastry, 2017). This is primarily addressed by making use of rigorous exploration strategies (Stadie et al., 2015; Lee et al., 2019). High-dimensional exploration further requires extrinsic feature engineering (Kulkarni et al., 2016) and meta models (Gupta et al., 2018). A suitable way to tackle high-dimensional dynamics is by utilizing surprise as a penalty on the reward (Chen, 2020). This leads to improved generalization for single-agent interactions (Ren et al., 2005). Our proposed approach is orthogonal to the aforesaid methods.
Energy-based Models: EBMs have been successfully implemented in single-agent RL methods (O’Donoghue et al., 2016; Haarnoja et al., 2017). These typically make use of Boltzmann distributions to approximate policies (Levine & Abbeel, 2014). Such a formulation results in the minimization of free energy within the agent. While policy approximation depicts promise in the case of unknown dynamics, inference methods (Toussaint, 2009) play a key role in optimizing goal-oriented behavior.
A second type of usage of EBMs follows the maximization of entropy (Ziebart et al., 2008). The maximum entropy framework (Haarnoja et al., 2018b) highlighted in Soft Q-Learning (SQL) (Haarnoja et al., 2017) allows the agent to obey a policy which maximizes its reward and entropy concurrently. Maximization of agent’s entropy results in diverse and adaptive behaviors (Ziebart, 2010) which may be difficult to accomplish using standard exploration techniques (Burda et al., 2019; Thrun, 1992). The maximum entropy framework is akin to approximate inference in the case of policy gradient methods (Schulman et al., 2017). Such a connection between likelihood ratio gradient techniques and energy-based formulations leads to diverse and robust policies (Haarnoja, 2018) and their hierarchical extensions (Haarnoja et al., 2018a) which preserve the lower levels of hierarchies. In the case of MARL, EBMs have witnessed limited applicability as a result of the increasing number of agents and complexity within each agent (Buşoniu et al., 2010). While the probabilistic framework is readily transferable to opponent-aware multi-agent systems (Wen et al., 2019), cooperative settings consisting of coordination between agents require a firm formulation of energy which is scalable in the number of agents (Grau-Moya et al., 2018) and accounts for environments consisting of spurious states (Wei et al., 2018). Our theoretical formulation is motivated by these methods in literature.

heading: 3 PRELIMINARIES

heading: 3.1 MULTI-AGENT LEARNING
text: We review the cooperative MARL setup. The problem is modeled as a Dec-Partially Observable Markov Decision Process (POMDP) (Oliehoek & Amato, 2016) defined by the tuple (S,A, r,N, P, Z,O, γ) where the state space S and action space A are discrete, r : S × A → [rmin, rmax] presents the reward observed by agents a ∈ N where N is the set of all agents, P : S × S ×A → [0,∞) presents the unknown transition model consisting of the transition probability to the next state s′ ∈ S given the current state s ∈ S and joint action u ∈ A (a combination of each agent’s action ua ∈ Aa) at time step t and γ is the discount factor. We consider a partially observable setting in which each agent n draws individual observations z ∈ Z according to the observation function O(s, u) : S × A → Z. We consider a joint policy πθ(u|s) as a function of
model parameters θ. Standard RL defines the agent’s objective to maximize the expected discounted reward Eπθ [ ∑T t=0 γ
tr(st, ut)] as a function of the parameters θ. The joint action-value function for agents is represented as Q(u, s; θ) = Eπθ [ ∑T t=1 γ
tr(s, u)|s = st, u = ut] which is the expected sum of payoffs obtained in state s upon performing action u by following the policy πθ. We denote the optimal policy πθ∗( shorthand π∗) such that Q(u, s; θ∗) ≥ Q(u, s; θ)∀s ∈ S, u ∈ A. In the case of multiple agents, the joint optimal policy can be expressed as the Nash Equilibrium (Nash, 1950) of the Stochastic Markov Game as π∗ = (π1,∗, π2,∗, ...πN,∗) such that Q(ua, s; θ∗) ≥ Q(ua, s; θ)∀s ∈ S, u ∈ A, a ∈ N . Q-Learning is an off-policy, model-free algorithm suitable for continuous and episodic tasks. The algorithm uses semi-gradient descent to minimize the Temporal Difference (TD) error in Equation 1.
L(θ) = E s,u,s′∼R
[( r + γmax
u′∈A Q(u′, s′; θ−)−Q(u, s; θ)
)2] (1)
where y = r + γmax u′∈A Q(u′, s′; θ−) is the TD target consisting of θ− as the target parameters andR denotes the replay buffer.

heading: 3.2 ENERGY-BASED MODELS
text: EBMs (LeCun et al., 2006; 2007) have been successfully applied in the field of machine learning (Teh et al., 2003) and probabilistic inference (MacKay, 2002). A typical EBM E formulates the equilibrium probabilities (Sallans & Hinton, 2004) P (v, h) = exp (−E(v,h))∑
v̂,ĥ[exp (−E(v̂,ĥ))] via a Boltzmann
distribution (Levine & Abbeel, 2014) where v and h are the values of the visible and hidden variables and v̂ and ĥ are all the possible configurations of the visible and hidden variables respectively. The probability distribution over all the visible variables can be obtained by summing over all possible configurations of the hidden variables. This is mathematically expressed in Equation 2.
P (v) = ∑ h exp (−E(v, h))∑ v̂,ĥ exp (−E(v̂, ĥ))
(2)
Here, E(v, h) is called the equilibrium free energy which is the minimum of the variational free energy and ∑ v̂,ĥ exp (−E(v̂, ĥ)) is the partition function.

heading: 4 ENERGY-BASED SURPRISE MINIMIZATION
text: We begin by constructing surprise minimization as an energy-based problem in the temporal setting. The motivation behind an energy-based formulation stems from rapidly changing states as an undesired niche among agents in the case of partially-observed settings. To steer agents away from this niche, we further construct a method which incorporates the theoretical aspect of the study.

heading: 4.1 THE SURPRISE MINIMIZATION OBJECTIVE
text: To make analysis tractable towards valid function spaces and surprising states, we take into account two assumptions which form the central basis of surprise minimization among multiple agents.
Assumption 1. (Completeness of value function space) The space Π : S ×A of all Q value functions Q(s, u) ∈ Π, ∀s ∈ S, ∀u ∈ A is a nonempty complete metric space.
Assumption 1 restricts the formulation of individual agent value functions Qa to the nonempty complete metric space. A nonempty space confirms the presence of candidate functions Qa upper bounded by the optimal function Q∗, i.e.- Qa ≤ Q∗, ∀a ∈ N (Bertsekas & Tsitsiklis, 1995). The completeness counterpart, on the other hand, provisions a fixed interior int Π for optimization (Boyd & Vandenberghe, 2004).
Assumption 2. (Constant surprise at Equilibrium) In the limit of convergence lim πa→π∗ to an optimal policy π∗, all agents a ∈ N incur a finite surprise ζ > 0 between consecutive states s and s′ until termination state sT .
Assumption 2 is directly based on the constant and continuous temporal aspect of surprise minimization (Schwartenbeck et al., 2013; Friston, 2010). Corresponding to the lifetime of each agent a ∈ N , a desired ecological niche bakes in the optimal distribution of actions which correspond to minimum yet finite instantaneous surprise.
We formulate the energy-based objective consisting of surprise as a function of states s, joint actions u and standard deviation σ of observations for each agent a. In the case of high-dimensional state spaces (such as multiple opponents), σ informs agents of the abrupt statistical change that would take place upon executing action u. We formulate surprise as T V asurp(s, u, σ) which serves as an uncertainty quantifier Unc(s,a) of the state-action distribution. Here V asurp(s, u, σ) denotes the surprise value function which serves as a mapping from agent and environment dynamics to surprise. Define an operator presented in Equation 3 which sums surprising configurations across all agents.
T V asurp(s, u, σ) = log N∑ a=1 exp ( V asurp(s, u, σ) ) (3)
Remark 1. T V asurp(s, u, σ) intuitively provides a global estimate of surprise. If all agents are equally likely to face a surprising state, then T V asurp(s, u, σ) captures their individual contributions. The formulation makes use of the soft-maximum operator (Asadi & Littman, 2017). The operator T V asurp(s, u, σ) is similar to prior energy formulations (Haarnoja et al., 2017) where the energy across different actions is evaluated. In our case, inference is carried out across all agents with actions as prior variables. However, in the special case of using an EBM as a Q-function, our approach suitable generalizes to the above methods (details in Appendix B).
Our choice of T V asurp(s, u, σ) is based on its unique mathematical properties which result in better convergence. Of these properties, the most useful result is that T forms a contraction on the surprise value function V asurp(s, u, σ) indicating a guaranteed minimization of surprise within agents. This is formally stated in Theorem 1 while utilizing the completeness criterion of Assumption 1 which provides a tractable value function space. All proofs are deferred to Appendix A.
Theorem 1. Given a surprise value function V asurp(s, u, σ) ∀a ∈ N , the energy operator T V asurp(s, u, σ) = log ∑N a=1 exp (V a surp(s, u, σ)) forms a contraction on V a surp(s, u, σ).
Theorem 1 provides a suitable guarantee of T V asurp(s, u, σ) converging to a fixed point niche. The contraction result is directly based on Banach’s fixed point property and suggests the generalization of convergence in any nonempty complete metric space (X, d) (Bertsekas & Tsitsiklis, 1995).
We now consider a weighted combination of Q(s, u) with T V asurp(s, u, σ) wherein we denote β as a temperature parameter,
Q̂(u, s; θ) = Q(u, s; θ) + β log N∑ a=1 exp (V asurp(s, u, σ))) (4)
Remark 2. Equation 4 is an instance of value function regularization wherein the Q values are subject to a joint penalty while observing surprising states.
Interestingly, upon considering the Legendre transform f∗(x) (Boyd & Vandenberghe, 2004; Gao & Pavel, 2017) (convex conjugate function corresponding to the conjugate space X of a differentiable function f(z)) of T V asurp(s, u, σ), we obtain the following,
f∗(x) = sup z∈dom f
( xTz− f(z) ) , f(z) = T V asurp(s, u, σ) (5)
f∗(x) = ∑ x x log(x) , x = ∇zf(z) ∈ X (6)
Remark 3. The Legendre Transform of T V asurp(s, u, σ) given by f∗(x) = ∑ x x log(x) when utilized as value function regularization Q̂ = Q− f∗(x) corresponds to the minimum entropy formulation in conjugate space Eπθ [∑T t=0 γ t(r(st, ut)− λH(x)) ] for x = ∇zf(z) ∈ X .
Based on the above insight, minimizing entropy to express ∇zf(z) in conjugate space is akin to minimizing uncertainty among all agents in the value function space Π. Intuitively, H(x) denotes the uncertainty for each agent a ∈ N in the multi-agent population which is directly related to its ability of efficaciously interpreting the environment. Minimizing H(x) leads to an increase in the expressiveness of value function. This in turn, induces an expressive state visitation distribution which steers the agent away from sudden changes in its environment. Note that the setting does not minimize entropy in value function space which would stand contrary to the maximum entropy formulation Haarnoja et al. (2018b) (see Appendix B).
Figure 1 presents an intuitive illustration of the objective. The joint agent population aims to minimize surprise corresponding to minimum energy configurations. Agents collaborate in partially-observed worlds to attain a joint niche. This local niche implicitly corresponds to a fixed point of T V asurp(s, u, σ) on the energy landscape. Note that agents act locally with actions conditioned on their own action observation histories. It is by virtue of preconditioned values estimations that the surprise minimization scheme informs agents of joint surprise. Upon population’s convergence to a suitable configuration, agents continue to experience minimum (yet finite) surprise arising from evironment dynamics.

heading: 4.2 SURPRISE MINIMIZATION WITH FUNCTION APPROXIMATION
text: We utilize the above insights as surprise-based regularization in the TD learning setting. Upon replacing Q(u, s; θ) with Q̂(u, s, ; θ) in the RL construction of Equation 1 one obtains the following,
L(θ) = E s,u,s′∼R 1 2 ( ŷ − (Q(u, s; θ) + β log N∑ a=1 exp (V asurp(s, u, σ))) )2 where ŷ = r + γmax
u′ Q(u′, s′; θ−) + β log
∑N a=1 exp (V a surp(s ′, u′, σ′)). Collecting the log terms
yields the following,
= E s,u,s′∼R 1 2 ( r + γmax u′ Q(u′, s′; θ−) + β log (∑N a=1 exp (V a surp(s ′, u′, σ′))∑N a=1 exp (V a surp(s, u, σ)) ) −Q(u, s; θ) )2
L(θ) = E s,u,s′∼R
[ 1
2
( r + γmax
u′ Q(u′, s′; θ−) + βE −Q(u, s; θ)
)2] (7)
Here, E is defined as the surprise ratio. The surprise value function V asurp(s ′, u′, σ′) is expressed as the negative free energy and ∑N a=1 exp (V a surp(s, u, σ)) as the partition function of a conventional EBM described in Equation 2. Alternatively, V asurp(s, u, σ) can be formulated as the negative free energy with ∑N a=1 exp (V a surp(s
′, u′, σ′)) as the partition function. The TD objective incorporates the minimization of surprise across all agents as minimizing the energy in spurious states.
Remark 4. The above formulation of βE can be realized as intrinsic motivation steering the agent towards subgoals with reduced surprise.
The energy formulation E provides a tractable distribution over all surprising configurations in the state space S . This guarantees convergence to minimum surprise at optimal policy π∗ and is formally expressed in Theorem 2 (see Appendix C for a detailed convergence analysis).
Theorem 2. Upon agent’s convergence to an optimal policy π∗, total energy of π∗, expressed by E∗ will reach a thermal equilibrium consisting of minimum surprise among consecutive states s and s′.
Theorem 2 demonstrates an intuitive convergence result of agent populations collaborating to reside in a mutual ecological niche (Friston, 2010). The multi-agent population with minimum surprise exhibits the optimal policy π∗ which results in minimum energy corresponding to each surprising state in the state distribution S . Orthogonally, agents may continue to experience finite and constant surprise in the long-horizon while acting optimally to visit non-surprising and rewarding states. This presents surprise minimization as a secondary surrogate objective in MARL.

heading: 4.3 ENERGY-BASED MIXER (EMIX)
text: Based on our theoretical analysis, we incorporate learning of surprise as global intrinsic motivation across all agents in the multi-agent system. A global estimate of surprise, following the energy operator T V asurp(s, u, σ), is befitting from a computational perspective as well. An individual estimate of surprise for each agent may be intractable to obtain due to the non-stationarity of the environment. Instead, we seek to minimize surprise jointly across all agents using an expressive Energy-based MIXer (EMIX) architecture which is compatible with any multi-agent RL algorithm. Figure 2 illustrates our learning scheme.
Learning of surprise in the high-dimensional value function space is cumbersome with the number of actions scaling linearly in the number of agents. This imposes an inherent restriction to learn global surprise efficaciously across all agents at a given timestep. Towards this goal, EMIX encodes individual value functions Q1, Q2, ... Qn corresponding to each agent using local value encoders. These encoders capture the local change in value functions arising over subsequent TD learning iterations (Wang et al., 2021). A global state encoder maps environment states s1, s2, ... sT to a low dimensional representation. Further, a state deviation encoder encodes deviations across all states s1, s2, ... sT within the given batch. Akin to a model-based method (Janner et al., 2019), the state deviation encoder accounts for uncertainty in an agent’s state visitation distribution. Note that the encoder does not construct an explicit model of states, but only represents their variation in the agent’s environment. This insight is essential to account for abrupt dynamics encountered by agents. Representations obtained from state and value function encoders are concatenated and compressed using a final surprise encoder which estimates a distribution of surprise values. The distribution implicitly represents the density of states wherein an agent may encounter most surprise. A value estimate V asurp(s, u, σ) sampled from the surprise distribution depicts the variational free energy configuration upon application of T which serves as global intrinsic motivation. Practical training of EMIX proceeds with backpropagation (Rumelhart et al., 1986) using gradient descent and the reparameterization trick (Kingma & Welling, 2014) for sampling of V asurp(s, u, σ).

heading: 4.4 PRACTICAL IMPLEMENTATION
text: Algorithm 1 Energy-based MIXer (EMIX)
1: Initialize φ, θ, θ−1 ..., θ − m, agent and hypernetwork parameters. 2: Initialize learning rate α, temperature β and replay bufferR. 3: for environment step do 4: u←− (u1, u2..., uN ) 5: R ←− R∪ {(s, u, r, s′)} 6: if |R| > batch-size then 7: for random batch do 8: Qθtot ←− Mixer-Network(Q1, Q2..., QN , s) 9: Qθ −
i ←− Target-Mixeri(Q1, Q2..., QN , s′), ∀i = 1, 2..,m 10: Calculate σ and σ′ using s and s′ 11: V asurp(s, u, σ)←− Surprise-Mixer(s, u, σ) 12: V asurp(s ′, u′, σ′)←− Target-Surprise-Mixer(s′, u′, σ′)
13: E ←− log (∑N a=1 exp (V a surp(s
′,u′,σ′))∑N a=1 exp (V a surp(s,u,σ)) ) 14: Calculate L(θ) using E in Equation 7 15: θ ←− θ − α∇θL(θ) 16: end for 17: end if 18: if update-interval steps have passed then 19: θ−i ←− θ,∀i = 1, 2..,m 20: end if 21: end for
Algorithm 1 presents the EMIX framework (in green) combined with QMIX Rashid et al. (2018), an off-the-shelf MARL algorithm. The total Q-value Qθtot is computed by the mixer network with its inputs as the Q-values of all the agents conditioned on s via the hypernetworks. Similarly, the target mixers approximate Qθ −
i conditioned on s ′. In order to evaluate surprise within agents, we
compute the standard deviations σ and σ′ across all observations z and z′ for each agent using s and s′ respectively. The surprise value function, called the Surprise-Mixer, estimates surprise V asurp(s, u, σ) conditioned on s, u and σ. The same computation is repeated using the Target-Surprise-Mixer for estimating surprise V asurp(s
′, u′, σ′) within next-states in the batch. Application of the energy operator along the non-singleton agent dimension for V asurp(s, u, σ) and V a surp(s
′, u′, σ′) yields the energy ratio E which is used in Equation 7 to evaluate L(θ). We then use batch gradient descent to update parameters of the mixer θ. Target parameters θ−i are updated every update− interval steps.

heading: 5 EXPERIMENTS
text: Our experiments aim to evaluate the theoretical claims presented by EMIX along with its performance to prior MARL methods. Specifically, we aim to answer the following questions- (1) How does the provision of an EBM for surprise minimization compare to current MARL methods?, and (2) Does the algorithm validate the theoretical claims corresponding to its components?

heading: 5.1 ENERGY-BASED SURPRISE MINIMIZATION
text: We assess the validity of EMIX, when combined with QMIX, on multi-agent StarCraft II micromanagement scenarios (Samvelyan et al., 2019) as these consist of a larger number of agents with different action spaces. This in turn motivates a greater deal of coordination. Additionally, micromanagement scenarios in StarCraft II consist of multiple opponents which introduce a greater degree of surprise within consecutive states.
We compare our method to prior methods namely; (1) QMIX (Rashid et al., 2018), constituting of nonlinear value function factorization with monotonicity constraints; (2) Value Decomposition Networks (VDN) (Sunehag et al., 2018), consisting of linear additive factorization of Q function; (3) Counterfactual Multi-Agent Policy Gradients (COMA) (Foerster et al., 2017), which consist of
counterfactual actor-critic updates in a centralized critic; and (4) Independent Q Learning (IQL) (Tan, 1993), wherein each agent acts independent of other agents. (5) In order to compare our surprise minimization scheme against pre-existing mechanisms, we compare EMIX additionally to a model-free implementation of SMiRL (Berseth et al., 2019) in QMIX. We use the generalized version of SMiRL as it demonstrates reduced variance across batches (Chen, 2020). This implementation is denoted as SMiRL-QMIX for comparisons. Details related to the implementation of EMIX are presented in Appendix D.
Table 1 presents the comparison of success rate percentages between EMIX and prior MARL algorithms on 12 StarCraft II micromanagement scenarios. Corresponding to each scenario, algorithms demonstrating higher success rate values in comparison to other methods have their entries highlighted in bold (see Appendix E.2 for a statistical analysis). Out of the 12 scenarios considered, EMIX presents higher success rates on 9 of these scenarios depicting the suitability of the proposed approach. In cases of so many baneling and 5m vs 6m having large number of opponents and a greater level of surprise, EMIX aptly improves over prior methods.
When compared to QMIX, EMIX depicts improved success rates on all of the 12 scenarios. On comparing EMIX with SMiRL-QMIX, we note that EMIX demonstrates a higher average success rate. This highlights the suitability of the energy-based scheme in the case of a larger number of agents and complex environment dynamics for surprise minimization.

heading: 5.2 ABLATION STUDY
text: We now present the ablation study for the various components of EMIX. Our experiments aim to determine the effectiveness of the energy-based surprise minimization method. Additionally, we also aim to evaluate the utility of dual approximators for surprise estimation in accordance with the precept from RL literature (Hasselt et al., 2016; Fujimoto et al., 2018; Haarnoja et al., 2018b).
5.2.1 EMIX OBJECTIVE
To weigh the effectiveness of energybased scheme, we ablate the energy operator T and only utilize V asurp. Since this implementation employs dual approximators V asurp,(i) i ∈ {1, 2} for stability, we call this implementation as TwinQMIX. Thus, we compare between QMIX, TwinQMIX and EMIX to assess the contributions of each of the proposed methods.
Figure 3 presents the comparison of average success rates for QMIX, TwinQMIX and EMIX on 3 different scenarios. Agents were evaluated for a total of 2 million timesteps with the lines in the plot indicating average success rates and the
shaded area as the deviation across 5 random seeds. In comparison to QMIX, TwinQMIX adds stability to the original objective by incorporating surprising estimates in the initial QMIX objective. On comparing TwinQMIX to EMIX we note that dual approximators play little role in improving convergence. Thus, the energy-based surprise minimization scheme is the main facet for significant performance improvement in the modified EMIX objective. This is demonstrated in the 5m vs 6m scenario wherein the EMIX implementation improves the performance of TwinQMIX in comparison to QMIX by utilizing a surprise-robust policy. In the case of so many baneling scenario which consists of a large number of opponents (27 banelings), EMIX tackles surprise effectively by preventing a significant drop in performance which is observed in cases of QMIX and TwinQMIX. We conjecture that this is a direct consequence of underestimations arising from V asurp,(i) estimates.

heading: 5.2.2 SURPRISE MINIMIZATION WITH TEMPERATURE
text: The importance of β can be validated by assessing its usage in surprise minimization. However, it is difficult to evaluate surprise minimization directly as surprise value function estimates V asurp(s, u, σ) vary from state-to-state across different agents and thus, they present high variance during agent’s learning. We instead observe the variation of E as it is a collection of surprise-based sample estimates across the batch. Additionally, E consists of prior samples V asurp(s, u, σ) for V a surp(s
′, u′, σ′) which makes inference across different agents tractable.
Figure 4 presents the variation of Energy ratio E with the temperature parameter β during learning. We compare two stable variations of E at β = 0.001 and β = 0.01. The objective minimizes E over the course of learning and attains thermal equilibrium with minimum energy. Intuitively, equilibrium corresponds to convergence to optimal policy π∗ which validates the claim in Theorem 2. With β = 0.01, EMIX presents improved convergence and surprise minimization for 5 out of the 6 considered scenarios, hence validating the suitable choice of β. On the other hand, a lower value of β = 0.001 does little to minimize surprise across agents.

heading: 6 DISCUSSION
text: In this paper, we presented an energy-based perspective towards surprise minimization in multiagent RL. Towards this goal we introduce EMIX, an energy-based intrinsic motivation framework for surprise minimization in MARL algorithms. EMIX utilizes a temporal EBM to estimate and minimize surprise jointly across all agents. Our theoretical claims on the formulation of minimization of temporal energy with surprise are corroborated upon utilizing EMIX on a suite of challenging MARL tasks requiring significant collaboration under fast-paced dynamics.
While EMIX serves as a practical example of EBMs in cooperative MARL, it presents several new avenues for future work. We shed light on 3 such aspects,
(1) Provision of an energy-based model naturally raises the question of how can we efficiently sample from the surprise distribution? Advances in sampling methods depict promise towards this aspect.
(2) Although suitable for lower dimensions, the scalability of EBMs towards high dimensional action spaces remains an open question. We conjecture that the utility of density-based methods and generative models can address the scalability gap.
(3) Lastly, the extension of an EBM framework to opponent-aware and competitive MARL settings presents a suitable tangent for learning multi-agent roles. Provision of an EBM for learning minimum energy role configurations would do away with the need for multi-stage training and complex exploration strategies. We leave the aforesaid as potential directions for future work.

heading: A PROOFS
text: Theorem 1. Given a surprise value function V asurp(s, u, σ)∀a ∈ N , the energy operator T V asurp(s, u, σ) = log ∑N a=1 exp (V a surp(s, u, σ)) forms a contraction on V a surp(s, u, σ).
Proof. We follow the process of (Asadi & Littman, 2017). Let us first define a norm on surprise values ||V1 − V2|| ≡ max
s,u,σ |V1(s, u, σ)− V2(s, u, σ)|. Suppose = ||V1 − V2||,
log N∑ a=1 exp (V1(s, u, σ)) ≤ log N∑ a=1 exp (V2(s, u, σ) + )
= log N∑ a=1 exp (V1(s, u, σ)) ≤ log exp ( ) N∑ a=1 exp (V2(s, u, σ))
= log N∑ a=1 exp (V1(s, u, σ)) ≤ + log N∑ a=1 exp (V2(s, u, σ))
= log N∑ a=1 exp (V1(s, u, σ))− log N∑ a=1 exp (V2(s, u, σ)) ≤ ||V1 − V2|| (8)
Similarly, using with log ∑N a=1 exp (V1(s, u, σ)),
log N∑ a=1 exp (V1(s, u, σ) + ) ≥ log N∑ a=1 exp (V2(s, u, σ))
= log exp ( ) N∑ a=1 exp (V1(s, u, σ)) ≥ log N∑ a=1 exp (V2(s, u, σ))
= + log N∑ a=1 exp (V1(s, u, σ)) ≥ log N∑ a=1 exp (V2(s, u, σ))
= ||V1 − V2|| ≥ log N∑ a=1 exp (V2(s, u, σ))− log N∑ a=1 exp (V1(s, u, σ)) (9)
Results in Equation 8 and Equation 9 prove that the energy operation is a contraction.
Theorem 2. Upon agent’s convergence to an optimal policy π∗, total energy of π∗, expressed by E∗ will reach a thermal equilibrium consisting of minimum surprise among consecutive states s and s′.
Proof. We begin by initializing a set of M policies {π1, π2..., πM} having energy ratios {E1, E2..., EM}. Consider a policy π1 with surprise value function V1. E1 can then be expressed as
E1 = log
[∑N a=1 exp (V
a 1 (s ′, u′, σ′))∑N
a=1 exp (V a 1 (s, u, σ)) ] Invoking Assumption 2 for s and s′, we can express V a1 (s
′, u′, σ′) = V a1 (s, u, σ) + ζ1 where ζ1 is a constant. Using this expression in E1 we get,
E1 = log
[∑N a=1 exp (V
a 1 (s, u, σ) + ζ1)∑N
a=1 exp (V a 1 (s, u, σ))
]
E1 = log
[ exp (ζ1) ∑N a=1 exp (V
a 1 (s, u, σ))∑N
a=1 exp (V a 1 (s, u, σ)) ] E1 = ζ1
Similarly, E2 = ζ2,E3 = ζ3...,EM = ζM . Thus, the energy residing in policy π is proportional to the surprise between consecutive states s and s′. Clearly, an optimal policy π∗ is the one with minimum surprise. Mathematically,
π∗ ≥ π1, π2..., πM =⇒ ζ∗ ≤ ζ1, ζ2..., ζM = π∗ ≥ π1, π2..., πM =⇒ E∗ ≤ E1, E2..., EM
Thus, proving that the optimal policy consists of minimum surprise at thermal equilibrium.

heading: B RELATION TO MAXIMUM ENTROPY FRAMEWORK
text: B.1 SIMILARITIES & DIFFERENCES
We conceptually compare EMIX to the maximum entropy framework.
Similarities: Both methods utilize an auxilary objective as intrinsic motivation to tackle uncertainty. While the maximum entropy formulation assigns low energy to uncertain actions, our method assigns low energy to uncertain encoded representations od states (as presented in Fig. 2).
Differences: Our method differs from maximum entropy in its optimization process and learning scheme. The maximum entropy formulation aims to maximize entropy in the value function space so as to motivate exploration. Our proposed scheme, on the other hand, aims to minimize surprise in the low-dimensional representation space to obtain dynamics-aware robust policies.
B.2 CONNECTION TO SOFT Q-LEARNING
The Soft Q-Learning objective with V θ − soft(s ′) and Qsoft(u, s; θ) as state and action value functions respectively is given by-
JQ(θ) = Es,u∼R [ 1
2
( r + γEs′∼R[V θ − soft(s ′)]−Qsoft(u, s; θ) )2]
= JQ(θ) = Es,u∼R 1 2 ( r + γEs′∼R [ log ∑ u∈A expQsoft(u ′, s′; θ−) ] −Qsoft(u, s; θ) )2 The gradient of this objective can be expressed as-
∇θJQ(θ) = Es,u∼R [( r + γEs′∼R [ log ∑ u∈A expQ(u′, s′; θ−) ] −Qsoft(u, s; θ) )] ∇θQsoft(u, s; θ)
(10)
And the gradient of the EMIX objective is obtained as-
L(θ) = Es,u,s′∼R 1 2 ( r + γmax u′ Q(u′, s′; θ−) + β log (∑N a=1 exp (V a surp(s ′, u′, σ′))∑N a=1 exp (V a surp(s, u, σ)) ) −Q(u, s; θ) )2
∇θL(θ) = Es,u,s′∼R [( r + γmax
u′ Q(u′, s′; θ−)
+ β log
(∑N a=1 exp (V a surp(s
′, u′, σ′))∑N a=1 exp (V a surp(s, u, σ))
) −Q(u, s; θ) )] ∇θQ(u, s; θ) (11)
Comparing Equation 10 to Equation 11 we notice that Soft Q-Learning and EMIX are related to each other as they utilize EBMs. Soft Q-Learning makes use of a discounted energy function which downweights the energy values over longer horizons. Actions consisting of lower energy configurations are given preference by making use of Qsoft(u, s; θ) as the negative energy. On the other hand, EMIX makes use of a constant energy function weighed by β which minimizes
surprise-based energy between consecutive states. Both the objectives can be thought of as energy minimizing models which search for an optimal energy configuration. Soft Q-Learning searches for an optimal configuration in the action space whereas EMIX favours optimal behavior on spurious states. In fact, EMIX can be realized as a special case of Soft Q-Learning if the mixer agent utilizes an energy-based policy and attains thermal equilibrium. This leads us to express Theorem 3. Theorem 3. Given an energy-based policy π with its target function V (s′) = log ∑ u∈A expQ(u
′, s′; θ−), the surprise minimization objective L(θ) reduces to the Soft QLearning objective L(θsoft) in the special case surprise absent between consecutive states,∑N
a=1 exp (V a surp(s ′, u′, σ′)) = ∑N a=1 exp (V a surp(s, u, σ)).
Proof. We know that the EMIX objective is given by-
L(θ) = Es,u,s′∼R 1 2 ( r + γmax u′ Q(u′; s′, θ−) + β log (∑N a=1 exp (V a surp(s ′, u′, σ′))∑N a=1 exp (V a surp(s, u, σ)) ) −Q(u, s; θ) )2 (12) Replacing the greedy policy term max u′ Q(u′, s′; θ−) with the energy-based value function V (s′) =
log ∑ u′∈A expQ(u ′, s′; θ−), we get,
L(θ) = Es,u,s′∼R 1 2 ( r + γEs′∼R[V (s′)] + β log (∑N a=1 exp (V a surp(s ′, u′, σ′))∑N a=1 exp (V a surp(s, u, σ)) ) −Q(u, s; θ) )2 (13)
= L(θ) = Es,u,s′∼R
[ 1
2
( r + γEs′∼R [ log
∑ u′∈A expQ(u′, s′; θ−)
]
+ β log
(∑N a=1 exp (V a surp(s
′, u′, σ′))∑N a=1 exp (V a surp(s, u, σ))
) −Q(u, s; θ) )2]
At thermal equilibrium, ∑N a=1 exp (V a surp(s, u, σ)) = ∑N a=1 exp (V a surp(s ′, u′, σ′)),
= L(θ) = Es,u,s′∼R
[ 1
2
( r + γEs′∼R [ log
∑ u′∈A expQ(u′, s′; θ−)
]
+ β log
(∑N a=1 exp (V a surp(s
′, u′, σ′))∑N a=1 exp (V a surp(s ′, u′, σ′))
) −Q(u, s; θ) )2]
= L(θ) = Es,u,s′∼R 1 2 ( r + γEs′∼R [ log ∑ u′∈A expQ(u′, s′; θ−) ] + β log(1)−Q(u, s; θ) )2 (14)
= L(θ) = Es,u,s′∼R 1 2 ( r + γEs′∼R [ log ∑ u′∈A expQ(u′, s′; θ−) ] −Q(u, s; θ) )2 (15) Equation 15 represents the Soft Q-Learning objective, hence proving the result.

heading: C CONVERGENCE ANALYSIS
text: We now analyze convergence of the surprise minimization scheme during policy optimization. For brevity, our notation denotes the modified Bellman operator as B obeying the standard assumptions of monotonicity and contraction (Bertsekas, 2018). Additionally, we consider the cumulative value V̂k = rk +Gk + β log ∑N a=1 exp(V a surp,(k)(s, u, σ)) as the sum of state values Vk = rk +Gk and
surprise energy values β log ∑N a=1 exp(V a surp,(k)(s, u, σ)) at k th Bellman update.
Consider ∥∥∥∥Vk − V ∗∥∥∥∥
2
with V ∗ being the optimal value at convergence,
∥∥∥∥V̂k − V ∗∥∥∥∥ 2 ≤ ∥∥∥∥BV̂k−1 + β log N∑
a=1
exp(V asurp,(k))− V ∗ ∥∥∥∥ 2
(16)
≤ ∥∥∥∥B2V̂k−2 + β log N∑
a=1
exp(V asurp,(k−1)) + β log N∑ a=1 exp(V asurp,(k))− V ∗ ∥∥∥∥ 2
(17)
≤ ∥∥∥∥B2V̂k−2 + β ( log N∑ a=1 exp(V asurp,(k−1)) + log N∑ a=1 exp(V asurp,(k)) ) − V ∗ ∥∥∥∥ 2
(18)
≤ ∥∥∥∥B2V̂k−2 + β ( log [ N∑ a=1 exp(V asurp,(k−1)) ][ N∑ a=1 exp(V asurp,(k)) ]) − V ∗ ∥∥∥∥ 2
(19)
Thus, for k iterations, we have, ≤ ∥∥∥∥BkV0 + β ( log k∏ i=1 [ N∑ a=1 exp(V asurp,(i)) ]) − V ∗ ∥∥∥∥ 2
(20)
= ∥∥∥∥BkV0 + β ( log N∑ a=1 [ k∏ i=1 exp(V asurp,(i)) ]) − V ∗ ∥∥∥∥ 2
(21)
= ∥∥∥∥BkV0 + β ( log N∑ a=1 [ exp( k∑ i=1 V asurp,(i)) ]) − V ∗ ∥∥∥∥ 2
(22)
We now absorb the sum of surprise values from time index i = 1, .., k in a single variable V atot. Thus, using V atot = ∑k i=1 V a surp,(i) and utilizing the Triangle Inequality, we get,
= ∥∥∥∥BkV0 − V ∗∥∥∥∥ 2 + ∥∥∥∥β ( log N∑ a=1 [exp(V atot)] )∥∥∥∥ 2
(23)
We now bound the two terms separately. Considering the first term and following the results of value iteration convergence (Bertsekas & Tsitsiklis, 1995),∥∥∥∥BkV − V ∗∥∥∥∥
2
≤ γk ∥∥∥∥V − V ∗∥∥∥∥
2
(24)
= γk ∥∥∥∥V + Vµ − Vµ − V ∗∥∥∥∥
2
(25)
wherein Vµ denotes an approximation to V . Utilizing the triangle inequality yields, ≤ γk ∥∥∥∥V − Vµ∥∥∥∥
2
+ γk ∥∥∥∥Vµ − V ∗∥∥∥∥
2
(26)
The two terms are bounded using the convergence result of (Bertsekas, 2018).
= γk √ rmax + γ k √ rmax|S| 1− γ
(27)
Now, considering the second term in Equation 23, ≤ β ∥∥∥∥ log N∑
a=1
exp(V atot) ∥∥∥∥ 2
(28)
= β ∥∥∥∥ log N∑ a=1 exp(V atot)− log N∑ a=1 exp(V ∗tot) + log N∑ a=1 exp(V ∗tot) ∥∥∥∥ 2
(29)
using the triangle inequality, ≤ β ∥∥∥∥ log N∑
a=1 exp(V atot)− log N∑ a=1 exp(V ∗tot) ∥∥∥∥ 2 + β ∥∥∥∥ log N∑ a=1 exp(V ∗tot) ∥∥∥∥ 2
(30)
Since T = log ∑N a=1 exp(V a tot) is a contraction following Theorem 1, for the first term we have,
≤ βγ ∥∥∥∥V atot − V ∗tot∥∥∥∥
2
+ β ∥∥∥∥ log N∑ a=1 exp(V ∗tot) ∥∥∥∥ 2
(31)
The second term in the above relation is bounded due to the completeness assumption,∥∥∥∥ log∑Na=1 exp(V ∗tot)∥∥∥∥ 2 .
≤ βγ ∥∥∥∥V atot − V ∗tot∥∥∥∥
2
+ βζ , ζ > 0 (32)
Finally, combining Equation 27 and Equation 32 in Equation 23, we obtain the desired convergence bound. ∥∥∥∥Vk − V ∗∥∥∥∥
2
≤ γk ( √ rmax + √ rmax|S| 1− γ ) + β ( γ ∥∥∥∥V atot − V ∗tot∥∥∥∥ 2 + ζ ) (33)
While the first term in Equation 33 denotes the convergence of policy optimization, the second term indicates the bounded convergence of surprise to ecological niches with finite (yet nonzero) surprising elements. The policy optimization process converges at a geometric rateO(γk) towards its stable fixed points. The surprise minimization process, on the other hand, demonstrates an annealing behavior which depends on the temperature parameter β. Furthermore, convergence to stable fixed point V atot is bounded in respect to each agents individual surprise values V a tot. This insight indicates that different agents converge towards different locally optimal values of surprise. Finally, the presence of constant ζ corroborates prior claims (Schwartenbeck et al., 2013; Friston, 2010) that agents continue to experience surprise irrespective of their convergence to minimum energy niches.
To further develop intuition for this claim, consider the special case wherein ∥∥∥∥V atot − V ∗tot∥∥∥∥
2
→ 0.
Irrespective of global convergence among all agents, a finite yet small ζ continues to contribute to the upper bound of ∥∥∥∥Vk − V ∗∥∥∥∥
2
.
Role of β: We further discuss the role of β which is of balancing the terms at successive iterations. While the first term geometrically decays with O(γk) rate, the second term approaches a finite constant βζ as V atot → V ∗tot. Irrespective of our choice of β, the LHS ‖Vk − V ∗‖2 is upper bounded by a constant which validates the claims of minimum yet finite surprise values. We do note that a small β is still desirable to remove any approximation errors in order to push Vk → V ∗. However, this comes at the cost of increased surprise if β is not selected appropriately.
D IMPLEMENTATION DETAILS
D.1 MODEL SPECIFICATIONS
Architecture: This section highlights model architecture for the surprise value function. At the lower level, the architecture consists of 3 independent networks called state net, q net and surp net. Each of these networks consist of a single layer of 256 units with ReLU non-linearity as activations. Similar to the mixer-network, we use the ReLU non-linearity in order to provide monotonicity constraints across agents. Using a modular architecture in combination with independent networks leads to a richer extraction of joint latent transition space. Outputs from each of the networks are concatenated and are provided as input to the main net consisting of 256 units with ReLU activations. The main net yields a single output as the surprise value V asurp(s, u, σ) which is reduced along the agent dimension by the energy operator. Alternatively, deeper versions of networks can be used in order to make the extracted embeddings increasingly expressive. However, increasing the number of layers does little in comparison to additional computational expense.
Computation of σ: The deviation σ corresponds to the standard deviation across each dimension of the state s. Considering the state as a tensor of size B ×A×M with B as the batch size, A as the number of agents and M as the observation dimension, we compute σ by calculating the standard deviation across the M dimension. This yields σ as a B ×A× 1 dimensional array. Computation of surprise estimates: Vsurp denotes the surprise value function which quantifies the amount of surprise experienced by agents. Analogous to a Q value function which provides estimates of returns, Vsurp provides estimate of surprise. Our framework learns Vsurp much like any other value function (using a neural network), but by additionally undergoing a log ∑ exp transformation to obey the fixed point property. This is achieved by realizing log-sum-exp as an energy operator T = log ∑ exp which can be computed using standard computation libraries. Since our code is implemented in PyTorch, we implement this as T_V = torch.logsumexp(V_surp, dim=1).
D.2 HYPERPARAMETERS
Table 2 presents hyperparameter values for EMIX. A total of 2 target Q-functions were used as the model is found to be robust to any greater values.
D.3 SELECTION & TUNING OF β
One can manually tune β using a fine-grained hyperparameter search. We tune β between 0.001 and 1 in intervals of 0.01 with best performance observed at β = 0.01. However, we find two additional methods helpful for obtaining more accurate values. These are described as follows-
Armijo’s Line Search: One can borrow from optimization theory and utilize Armijo’s line search Nocedal & Wright (2006) by setting a termination condition. The method starts with a constant value of β which is iteratively incremented/decremented until a termination criterion (example‖∇L(θ)‖ < with a constant) is reached. While line search is proven to converge towards globally optimal values, its O(n2) convergence may be computationally expensive that too in the MARL setting. Thus, we turn to the more efficient automatic tuning.
Algorithm 2 Armijo’s Line Search 1: Initialize β, δ ∈ (0, 1], EMIX & T V asurp; 2: while EMIX(Q+β∗T V asurp)> EMIX(Q)
+ α ∗ β ∗ ∇EMIX(Q)TT V asurp do 3: β = δ ∗ β 4: end while 5: return β
Algorithm 3 Automatic Tuning 1: Initialize β, δ ∈ (0, 1], EMIX & T V asurp; 2: EMIX(Q+ β ∗ T V asurp) 3: beta loss = β ∗ 0.5 ∗ (T V asurp − 0)2 4: beta loss.backward() 5: return β
Automatic Tuning: We choose to automatically tune β following single-agent RL literature Haarnoja et al. (2018b); Kumar et al. (2020). This is achieved by treating β as a parameter and adaptively
optimizing over it using Adam. We treat a surprise value of 0 as our target value. The method works well in practice and provides β values closer to 0.01 (our manual selection).

heading: E ADDITIONAL RESULTS
text: E.1 QUALITATIVE ANALYSIS
We visualize and compare behaviors learned by surprise minimizing agents to the prior method of QMIX. Fig. 5 presents the comparison of EMIX and QMIX agent trajectories (in yellow arrows) on the challenging so many baneling task. The task consists of 27 baneling opponents which rapidly attack the agent team on a bridge. QMIX agents naively move to the central alley of the bridge and start attacking enemies early on. While QMIX agents naively maximize returns, EMIX agents learn a different strategy. EMIX agents rearrange themselves first at the corners of the bridge. Note that these corners provide cover from enemy’s fire. Thus, EMIX agents learn to take cover before approaching the enemy head-on. This indicates that the surprise-robust policy is aware of the incoming fast-paced assault.
As another example, Fig. 6 presents behaviors on the 2s vs 1sc task wherein two agents must collaborate together to defeat a SpineCrawler enemy. The enemy, having a long tentacle pointing to the front, chooses to attack any one of the agents randomly in front of it. Additionally, the tentacle has a fixed length and cannot extend beyond this range. Random intermittent attacks indicate that the agents face a greater degree of surprise with no prior knowledge of the enemy’s movement. We observe that QMIX agents take turns to attack the enemy by moving back and forth to minimize damage. EMIX agents, on the other hand, learn a different strategy. One of the EMIX agents stands at a distance to attack th enemy while the other agent goes around to attack from behind. This indicates that the policy is aware of enemy’s limited movement.
E.2 STATISTICAL SIGNIFICANCE
We follow the recommendation of Lones (2021) and evaluate the statistical significance of our results by carrying out the Mann-Whitney U test Mann & Whitney (1947). All 5 seeds of an algorithm
(on each task) are compared to that of QMIX to yield the U statistic. U here denotes the statistical significance of performance with higher values being desirable.
Table 3 presents the comparison of U statistic on the StartCraft II benchmark. EMIX demonstrates consistently high values of U across a diverse set of tasks when compared to SMiRL and prior MARL agents. This highlights the consistent surprise-minimizing performance of EMIX across random seeds.
E.3 ADDITIONAL TASKS
This section compares EMIX and TwinQMIX to prior MARL methods on the Predator-Prey tasks. In addition to the difficulty of task, we vary the number of opponents. This helps quantify the variation in performance against increasing level of surprise under fixed dynamics. Table 4 presents average returns. While all agents present comparable performance on the easier tasks, EMIX improves over QMIX and TwinQMIX on the more challenging punish and hard tasks. In the case of punish, EMIX is the only method to achieve greater than 20 returns outperforming baselines by a significant margin.
We consider a simple toy task from the Predator-Prey benchmark to demonstrate the importance of surprise minimization. We select predator prey easy due to its simplicity and convenient dynamics. The task consists of 3 agents and 3 opponents. We increase the number of opponents while keeping the task fixed. This way the dynamics of the MDP remain unchanged and the only changing factor is opponent behaviors.
Fig. 7 presents the variation of average returns for EMIX and QMIX over 5 random seeds. While QMIX agents undergo a steady decrease in performance, EMIX agents are found robust to this fast degradation. Even after the addition of 20 opponents (against only 3 agents), EMIX is able to retain positive returns. The algorithm acquires a surprise robust-policy early on during training to tackle fast-paced changes introduced by the large number of agents.
E.4 ADDITIONAL ABLATIONS

Review summaries:
The authors present a method to regularise the learning of Q values within Decentralised partially observable markov decision processes, where the regulariser is one that minimises surprise in some way across the population of agents within the environment.  This it is argued allows the agents to avoid situations in which states are "rapidly changing", instead aiming to reach an equilibrium state where just enough surprise is being experienced as part of a reward maximising objective.  The authors present a series of results in which their method outperforms a number of SoTA alternatives on a reasonable looking set of benchmarks, as well as an ablation study showing the criticality of each proposed component. 

This paper introduced a suprise term in optimizing the policies (action-value functions in Q-learning) for solving the non-stationary challenge due to the rapid changes from the environment for MARL scenarios. This work not only proposed the concept of suprising value in the context of MARL, but also gave an operator (i.e. a contration) that can make the sequence of suprising values converges to a fixed point. The general sketch of the proofs is correct. Also, the authors showed that the convex conjugate of the suprising value operator is analogous to the minimization of the uncertainty among agents. By incorporating the suprising value into the Q-learning algorithm, the term led by the ratio between target and behaviour suprising value (suprising ratio) can also be interpreted as an intrinsic reward. Moreover, the authors also compare the proposed surprising minimization objective with the Soft Q-learning objective.