Expected Return Symmetries
Authors: Darius Muglich
Johannes Forkel
Elise van der Pol
Jakob Nicolaus Foerster
Venue: ICLR 2025 Poster (2025)
Keywords: multi-agent reinforcement learning
zero-shot coordination
Primary area: reinforcement learning
TL;DR: Discovering a symmetry class over policies that improves coordination between agents

Abstract: Symmetry is an important inductive bias that can improve model robustness and generalization across many deep learning domains. In multi-agent settings, a priori known symmetries have been shown to address a fundamental coordination failure mode known as mutually incompatible symmetry breaking; e.g. in a game where two independent agents can choose to move "left" or "right", and where a reward of +1 or -1 is received when the agents choose the same action or different actions, respectively. However, the efficient and automatic discovery of environment symmetries, in particular for decentralized partially observable Markov decision processes, remains an open problem. Furthermore, environmental symmetry breaking constitutes only one type of coordination failure, which motivates the search for a more accessible and broader symmetry class. In this paper, we introduce such a broader group of previously unexplored symmetries, which we call expected return symmetries, which contains environment symmetries as a subgroup. We show that agents trained to be compatible under the group of expected return symmetries achieve better zero-shot coordination results than those using environment symmetries. As an additional benefit, our method makes minimal a priori assumptions about the structure of their environment and does not require access to ground truth symmetries.

Published as a conference paper at ICLR 2025
EXPECTED RETURN STRENSSSMEEER SYMMETRIES
Darius Muglich University of Oxford
Johannes Forkel"
University of Oxford
darius@robots. ox ac. uk
johannes forkel@eng ox ac
Elise van der Pol
Jakob Foerster
Microsoft Research Al for Science evanderpol crosoft.. com
University of Oxford
jakob. foerstereeng ox ac uk
ABSTRACT
Symmetry is an important inductive bias that can improve model robustness and generalization across many deep learning domains. In multi-agent settings, pri- ori known symmetries have been shown address fundamental coordination failure mode known as mutually incompatible symmetry breaking: e.g. in game where two independent agents can choose move "left" or "right", and where a reward of +1 or -1 is received when the agents choose the same action or differ- ent actions, respectively. However, the efficient and automatic discovery of envi- ronment symmetries, in particular for decentralized partially observable Markov decision processes, remains an open problem. Furthermore, environmental sym- metry breaking constitutes only one type of coordination failure, which motivates the search for a more accessible and broader symmetry class. In this paper, we introduce such broader group of previously unexplored symmetries, which we call expected return symmetries, which contains environment symmetries as a sub- group. We show that agents trained to be compatible under the group of expected return symmetries achieve better zero-shot coordination results than those using environment symmetries. As an additional benefit, our method makes minimal a priori assumptions about the structure of their environment and does not require access to ground truth symmetries.
INTRODUCTION
Incorporating the symmetries of underlying problem into models has had demonstrable success in improving generalization and accuracy across many different machine learning domains (Bronstein
ct al. 2021 Krizhevsky et al. 2017 Cohen et al. 2019 Finzi et al. 2020 Van der Pol et al. 20200) As an important example, using data augmentations and equivariant networks has been shown to improve zero-shot coordination (ZSC), the ability of independently trained agents to coordinate in cooperative multi-agent settings at test time (Hu et al.] 2020;; Muglich et al. (002a)). Without accounting for symmetries, independently trained agents can converge onto equivalent yet mutually incompatible policies during training, leading to coordination failure at test time. For example, one team of agents might use the color "blue" to signal "play" in cooperative card game like Hanabi, while a different team might use the equivalent color "red". This issue, known as mutually incompatible symmetry breaking, can be mitigated by incorporating symmetries like color into the training process, as is done in other-play (OP) (Hu et al. 2020). OP addresses this by applying an independently sampled symmetry transformation to each agent during every training episode, ensuring compatibility amongst equivalent policies.
Environmental symmetry breaking form of over-coordination, where agents adopt arbitrary conventions that hinder new partners' adaptation within episode. Yet, this is only one failure mode; even without non-trivial symmetries, agents may over-coordinate by forming overly specific conventions (see Example 2). Moreover, current symmetry-based methods assume a priori access to these symmetries, but automatically discovering them cenee-clllllly in large-scale Dec-POMDPs OOliehoek et al. 2007 can be computationally infeasible (Narayanamurthy & Ravindran 2008
"qqual contribution

---

Published as a conference paper at ICLR 2025
2?
Figure I: Mutually incompatible symmetry breaking between chess players is shown in the left side panels (Chess.com 202T). Let Nı, m2 represent the joint policies under which both play- ers choose handshake, fist bump. respectively. and let the reward he 11, depending whether they match
2021
00:00
of both joint policies 1, the cross-play score between them is -1. Thus, policies incompatibly break the symmetry between handshake and fist bump.
The self-play
To address these two issues, in this paper, we define the group of expected return symmetries (ER symmetries), relatively underexplored symmetry group that contains the environment symmetries of Dec-POMDP as a subgroup. Since in most cases ER symmetries are a strict superset of the envi- ronment symmetries, using them the symmetry group for OP enforces training time compatibility with a greater number of policies.
We also introduce scalable method for discovering approximate ER symmetries, which lever- ages gradient-based optimization to search for transformations that preserve expected returns across optimal policies. Furthermore, we show that ER symmetries better improve zero-shot coordination amongst independently trained agents than Dec-POMDD symmetries, while maintaining completely model-free assumptions. To summarize, our main contributions are:
We define the group of expected return symmetries and introduce novel algorithms for learning them.
2. We demonstrate that, when combined with the OP learning rule, expected return sym- metries are significantly more effective preventing wer-coordination than Dec-POMDP symmetries. Furthermore, we demonstrate that our method is applicable in settings where both off-belief learning Hu et al.] (202T) and cognitive hierarchies Cui al. (202T) fail.
3. To the best of our knowledge, our method is the first symmetry- method im- prove zero-shot coordination without priori/privileged environment information, such as of symmetries dynamics.
BACKGROUND
2.1 DECENTRALIZED PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES
We model cooperative multi-agent tasks as a Decentralized POMDP (Dec-POMDP) Olichoek al. 2007), defined by the 9-tuple
(S, n. ; (4 H.
Here, S is the state space, n the number of agents, and for each agent i, A' and Oi denote the local action and observation spaces (with joint action and observation spaces A " and O = x O*). The dynamics are given by
8t+1 T(st+1 (1, az), of-1~ ~11101 (5)11,0))
with rewards f1+1 = R(8++1 0t), horizon H (with terminal state 8H), and discount factor Each agent i follows local policy T², which chooses local actions based on the local action-observatiin history (AOH) 7/ = (a), .j...., a.-1. of), while the joint policy = (Tr,...,, ,T) selects joint actions (a...... af') based on the joint AOH T, (Tt,.., ..... T²"), with probability
x (a)lm) = II x (afT)))
The self-play objective is defined by the expected discounted return:
F -1
( = Ex
Σ
t=0
2

---

Published as a conference paper at ICLR 2025
2.2
ZERO- SHOT COORDINATION
The self-play objective is widely used in multi-agent reinforcement learning (MARL) (Samuel
1959
Tesauro al. 1995), where agents train together under joint policy. While effective for coordination, it often results in arbitrary conventions that only work among agents trained together.
However, many real-world tasks require coordination with unknown partners (Mariani et al. 2021 Kakish et al. 2019), making this limitation problematic.
Resnick et al. 2018
To address this, Hu al. 2020) introduced zero-shot coordination (ZSC). In ZSC, agents first agree on learning rule, which they each implement independently (e.g. cannot agree on seeds). Each agent then trains a joint policy a Dec-POMDP environment, without communication or coordination between agents during training. Finally, agents participate in cross-play (XP), where joint policies trained by different agents are combined to evaluate the XP objective (defined here only for = 2, but it can be extended to n > 2):
1
XT T2) := (J(T). m2) JJ (Tb).
for independently learned joint policies and 'T. ZSC aims for learning rules that optimize cross- play with other rational partners using the same minimal set of assumptions (e-g., no access to be- havioral data or coordination experience with specific groups of agents). 7SC presents a promising approach to addressing real-world coordination challenges where relying on arbitrary conventions impractical. ZSC has become key benchmark for human- coordination and is important
step towards more generalized coordination capabilities (Ji et al. 2023 Hu et al. 2021)
2.3 SYMMETRY GROUPS AND OTHER PLAY IN DEC-POMDRS
We consider symmetries that can be expressed as maps Φ = (Øs. SA 0o), consisting of bijective maps 6s S + S, Cs A - A', and do O' O¹, Am (a")), (o = (ooi (o'),.... Po- (o")), for all a A and o O. The set of all such maps forms a group, which we denote by V. Given & E V, we slightly abuse notation and define ((s) == ds(s), ø(a') := (a:(a') and ø(o')= (oi()"), for S, and o² E O². Given joint AOH TO = (T()...,TT") we define d(T)) == (O(T)), ((T")) with ((T/)) == (é(a)), p(of).... ((.)_)), Furthermore, we let symmetry @ v act joint
1, l,... n, the sense that
(a) (a )... .....
A'
policies through the formula
((T)(((())) (((()) = n' (a (T).
(2)
Any subgroup & C v partitions the space of joint policies into disjoint equivalence classes: given joint policy ग, define its equivalence class [ = {Ø(TT): Definition 1 (Dec-POMDP Symmetries). A map 6 v is called a Dec-POMDP symmetry if for all (St, Ge, 8t+1, 0c+1) E S x A S x O it holds that
$).
T(s+11 8t, 8t)aa) = (()(s+11) U(o++1 8441,aa) ((b(o++1) ((((4)1) R($441,a,) = R(6(54+1) o(a,)).
o(a)),
(3)
We denote the set of all the Dec-POMDP symmetries of given Dec-POMDP by MDP
Dec-POMDP symmetries form subgroup of V which corresponds to relabelings of the state, action, and observation spaces that leave all the transition and reward functions of the Dec-POMDP unchanged (see Example 2). We note that Dec- Pec-POMDP symmetries can be extended to also include permutations between players (Treutlein et al. 202I).
Hu et al. (2020) demonstrate that policies equivalent under MDP are prone to mutually incompat- ible symmetry breaking: without biases like initialization or reward shaping, the learning rule may converge to either its equivalent Φ(T), the learning process cannot distinguish between them due to the Dec-POMDP symmetries. Although J(T) = (()())) the cross- play score may suffer, Le.. (mT) > XP(T, ((T)), meaning æ and Φ(T) were not trained to be compatible. See Figure |
To constrain policies to be compatible with policies that are equivalent with respect to the symmetry group MDP, Hu et al. 2020) introduced the other-play objective (can be extended
2):
3

---

Published as a conference paper at ICLR 2025
Definition 2 (Other-Play (OP) Objective), Given Dec-POMDP and symmetry group + V, define the other-plat play (OP) objective OP" :II + R w.r.t & by
OP ( := [P(T,, +)]
Σ [T [
(J(m - ,
(4)
Hu et al. (2020) proposed the OP learning rule म. = sug OP* (m). for + = $ MDP Agents
trained using the OP objective take into account modes of symmetry breaking resulting from the fact that a test-time partner is unbiased in their choice between ((T) and n, Vń E $
METHOD
In Section 3.1 we generalize the OP objective (Equation 4) to defined over general symmetry
group & and highlight desirable properties that symmetry group for OP should satisfy. In Section
3.2
we define the group of expected return symmetries, which we argue is better suited for OP than Dec-POMDP symmetries by way of the aforementioned desirable properties. In Section 3.3 propose a method for learning expected return symmetries.
3.1
OTHER-PLAR OVER GENERAL SYMMETRY GROUPS
While Hu al. (020) introduced symmetry breaking w.r.t. @DDPP we extend the definition for general symmetry group T:
Definition 3 (Symmetry Breaking). Given a symmetry group 4, joint policy is said to incom- patibly break symmetry w.r.t. @ E 4 if J(T) > XP(T, ((T)), and w.r.t. 4 if ((T) > OP" (T).
The OP objective (Equation 4 evaluates the expected return when an agent from one policy is matched in a team with members of randomly chosen policies from the same equivalence class induced by 4. Thus OP optimal policies are maximally compatible with policies within their equiv- alence class, as they best avoid incompatible symmetry breaking w.r.t. ②. We note that different OP ooptimiimal policies are not necessarily in the same equivalence class and can therefore be incom- patible; for example, when & Id. OP reduces SP, and each OP*-optimal policy forms its own one-element equivalence class. We denote IT the set of all optimal policies under Op*.
Rational and independent ZSC agents would therefore choose a symmetry group + such that:
1. (Diversity within Equivalence Classes) The choice of & should ensure that for all π e TT the equivalence class using OP to enforce and [T] to be compatible makes π broadly compatible with policies it could encounter at test-time, assuming other agents also adopt OP as their learning rule.
meaningfully diverse. This diversity should be such that
2. (Optimality within Equivalence Classes) & should separate poor policies from good poli- cies, i.e. OP (T') Rs OP*(T)) (T), for any II and n' E [Tr). since otherwise there is no reason to constrain oneself to be compatible with T' (a rational test-time partner would not use TT).
Example 1. For + [Id], OP* SP, which corresponds to perfectly preserving optimality, but not introducing any diversity to the equivalence class; i.e. perfect satisfaction of Item 2ommbbu but extremely poor satisfaction of Item [ On the other extreme, we can consider on II, which enforces compatibility with every possible test-time partner (i.e., rational partners), but also with other possible policies (which are mostly poor), thus converging to the best response to random player; i.c., perfect satisfaction of Item I but extremely poor satisfaction of Item 2
be the
all bijections
The goal of 7SC is to find learning rule that maximizes the expected XP score between indepen- dently trained test-time partners. For the learning rule OP* the expected XP score is:
XP(OP!) EE - XP(TI, =2)]
(5)
Thus interpret max+en "P (x) estimating XP(OP"), but only through the cross-play scores within a given equivalence class [T]] induced by Φ:
max OP (Tt) E5-15 [OP (T)) EI [Emssmm [XP(TI T2)]] #EIl
(6)
4

---

Published as a conference paper at ICLR 2025
Since optimal OP" policies are not trained to be compatible across different equivalence classes, can always assume w.L.ogg. that OP (Λ) >> [x"E(T]] [XP(x, for any x' II, for which & [T]] (else just merges [T]] and [x'] by adding the transposition between ι and n' to Φ).
Thus if Item is satisfied perfectly, it follows that
max OP (Tt) 2 XP(OP"), #Ell
with equality if and only if [+]= = IT. for any and thus all E IT. This means that if one finds symmetry group & which satisfies both of Items | and 2 perfectly, then [r] = 11.T for any π E 11. and OP (T) = XP(OP"). ). In other words, with such a choice of Q, agents during training account for any potential test-time partner produced by OP", and only for such partners. Items 1 and are thus desirable criteria for choosing a group d that makes OP" a suitable learning rule for ZSC. However, these criteria alone are not sufficient for & to be optimal for ZSC, because agents in ZSC cannot choose a symmetry group & that is tailored to a specific Rec-POMDP. For example, suppose agents select & the set of all bijections In this case, except for trivially simple Dec-POMDPs, we have TT = [^] = {-}- This choice of Φ would trivially satisfy Item (since { } is entirely representative of test-time policies) and Item 2 (since π E _1 and Φ(π) = ग, Vé E ②). However, such symmetry group is not permissible in ZSC because is specifically constructed for particular policy specific Dec-POMDP, violating the are desirable properties, they are not sufficient on their own for choosing an appropriate symmetry group for ZSC.
II that leave particular SP optimal policy x unchanged.
requirement for generality in ZSC. Therefore, while Items] | and 2
3.2 EXPECTED RETURN SYMMETRIES
We propose that the group ER of expected return (ER) symmetries, which be learned with completely model-free assumptions, handles the above trade-off given by Items [ favorably:
Definition 4 (Expected Return Symmetries). For a fixed temperature a > 0, define the set of Boltzmann exploratory policies as
(+(r/aa)) a
exp
IT
π
E
(a)
x
T/)
Va E A'(T), Vol. Vi 1,...
ExTEA(TT)) exp
where Q', (ri ai) is the action-value function of T' when assuming that all other agents also follow т. The set of self-play optimal Boltzmann exploratory policies is then defined as
TT == arg max (T=)
rell>
Finally, define the group of expected return symmetries as
S ER ==
v
VT E ((T) =
ie., the subset of transformations preserving self-play optimality of Bolzzmann-xxplorttryy policies.
We will suppress the dependence of FR on a, but is important to define tR over self-play op- timal Doltzmann-exploratoon
policies: if one were to allow self-play optimal policies that do not explore the entire space of AOHs in this structured way, then expected return symmetries would not be properly restricted in their effect on policies at suboptimal AOHs, and ER could contain symme- tries that inhibit coordination (see Appendix C). For small a, policies learned via Q-learning can be aonverted-albeit approximately, due to the algorithm being off-policy -ino policies belonging to II by using Boltzmann sampling on the learned local action values. As well, entropy- regularrzee policy gradient methods yield policies whose actor networks produce logits proportional the cor- responding Q-values, thereby resulting in policies in IIe (see Appendix B.2 for details).
FR is a group under function composition (see Appendix B.1p. Furthermore, since for any Dec- POMDP symmetry & E &DDP and any joint policy π it holds that J (Tr [()()), and also that ((T) is Boltzmann exploratory, it follows that &ER contains &DDP as subgroup (see Appendix
B.I.
transposition is permutation that swaps exactly two elements.
5

---

Published as a conference paper at ICLR 2025
At high level, MDP captures coordination differences based only on relabeling actions and obser- vations, offering limited diversity. In contrast, calf--pla-otimmll policies can differ significantly in coordination strategies, beyond mere label permutations. By grouping such diverse policies into the same equivalence class, 6ER better addresses Item than &DDP While &ER may not fully satisfy Item 2 (as &ER is only required preserve the expected return of peff-play-optimal policies), show in Section 4.4 that learned symmetries in oER approximately meet this criterion. Overall, this
suggests ZSC agents using Op* will coordinate better at test time than those using Op Section confirms that dER significantly improves (zero-shot) coordination across various environments.
The following example illustrates the advantage of ER symmetries over Dec-POMDP symmetries.
Example 2. Consider a cooperative communication game based on Hu et al. 2021), p. Alice observes a binary variable (pet) representing either "cat" "dog". Her actions include turning a light bulb on for a reward of 0.01, light bulb off for a reward of O, bailing for a reward of 1 which ends the game, or removing a barrier at a cost of let Bob directly observe the pet. Bob can bail for 0.5 or guess the pet, receiving 10 for a correct "cat" guess, 11 for a correct "dog" guess, and losing 10 for an incorrect guess.
In this game, there are two ways for Alice to communicate with Bob: a "cheap-talk" channel (turning the light on or off) and "grounded" channel (removing the barrier). There are exactly two self- play optimal (Boltzmann exploratory) joint policies, and both use the cheap-talk talk channel with high probability: one policy associates "light on dog, light off = cat," while the other assigns the reverse. These two policies are incompatible in cross-play however, where coordination fails if each agent follows a different encoding.
Due to the different rewards for cat/dog, this game contains no non-trivial Dec- symmetries, which means that OP with MDD reduces to self-play, which, as just discussed, leads to coordination failure since independently trained agents will converge on either of the two self-play peff-play-optimal but waassslla-inccoopee
policies. Indeed, permuting "on/off" and "cat/dog" not a Rec-POMDP symmetry because these environmental features have different reward dynamics.
However, these pairings are ER symmetries, as they transform the two self self-play-ore play-optimal policies into one another and thus preserve their expected return. Therefore, these two policies are symmetric to each other w.r.t. &ER are put into the same equivalence class, and OP with $BR able to anticipate their coordination failure. OP with I then chooses the optimal grounded policy, leading to the best possible cross-play score in this game for independent rational agents. This is demonstrated empirically in Section 4.2
3.3 ALGORITTMICC APPROACHES
In practice, if dER is large, we find that it can be effectively approximated by limited number of learned ER symmetries, that are sufficiently diverse (see Section 3.J]ffo for the importance of diversity). We therefore develop an algorithm to learn such subset of ER symmetries, which we find in Section is sufficient to significantly enhance zero-shot coordination across various environments.
Based on Equation
4
we formulate the following objective for learning ER symmetries:
②gg- where 0* = arg inf E.--- [T) (()(()))]
where (Øv A E }} a parameterization, and II' C II is a fixed pool of SP optimal Boltzmann exploratory policies. The broader the set II' is. the more representative it will be of II; and hence the less likely the learned ςv- will overfit to a specific policy (i.e. not able to preserve expected return for other optimal policies outside the training set).
Since the policies in Equation are approximately SP optimal, we can use the equivalent objective
dgg where 0* -arg sup Ex-IT [J())
oge
Importantly, the optimization in Equation 9 focuses only on the ER symmetry dee In this process, we train the transformation Φe within a reinforcement learning loop, but we keep the weights of the policies in II' fixed. See Algorithm I in Appendix for details. The Boltzmann exploration of the policies in II' enforces that de takes into account all possible AOHs during training, not just optimal ones. Furthermore, when training é using policy gradient methods, we use entropy- searop-rrgularizztion to ensure ((T) yields self-play optimal Boltzmann exploratory policy (see Appendix B.2 B.2 for details).

---

Published as a conference paper at ICLR 2025
Recall that 09 { 00,0, (A..). Since we interested in expected return symmetries insofar as they act on the policy space rather than the Dec-POMDP itself. we fix Φs.0 = Id. Furthermore, since typically |AA] << [O], rather than learning both {6o, s, $A.03 } in a reinforcement learning loop, we can consider learning Φ1,40 through search over tuples of permutations on the local action spaces; i.e. we initialize fixed tuple of local action permutations 9.A.0 and learn $0.0 per Equation See Algorithm I in Appendix [ for an outline of this procedure.
Each local action space A allows for (1-")) distinct transpositions, representing the number of unique ways two actions can be permuted. Consequently, learning one observation transformation $0,8 corresponding every possible tuple of local action transpositions requires OQ | optimizations of Equation 9 to perform an exhaustive search (i.e. O [AAl2) iterations of the outer for loop in Algorithm]]] D. However, in Section [4.4 we show that non-exhaustive search that undersamples the space of tuples of transpositions still sufficient for learning symmetries that significantly improve coordination amongst agents.
Note that the objective in Sqquation99does not enforce closure under composition (i.e. Φ1 01022 E o for all Φ1, の2 E TFR) or invertibility (i.e. for all & E ΦER there exists 6- E oER such that 6-1 Id), both necessary for & to form a group. To learn ER symmetries which are compositional and invertible, we use the following regularized objective:
Φg- where 0* = arg max E EE
(1 {1)J((o(T=) > E Riddy [J do -6 (T)]]
A2EoOO [d(o, (8)))
(10)
where d 0² 10, ou) is a metric, SRR is a fixed pool of unregularized ER symmetries learned
through Equation Algorithh [ and Å 10, X2 E o0) control the regularization towards compositionality and invertibility, respectively. Since 6A.9 is a fixed transposition, 024.0 = Id by
design, so we can easily enforce 22.0 = Id. The objective can be optimized stochastically, to avoid computing multiple policy gradients per update. This is detailed in Algorithm 2 in Appendix F Note that in the term EDeo [d(o, og (o))²] we abuse notation, and let de map into continuous extension of O, otherwise this term would be locally constant with a gradient of zero almost everywhere.
We also propose an alternative objective for learning ER symmetries through XP maximization:
Φg. s.t. 0" = sup XP(TT, (o(TT)))
(11)
OE@
where Ty. E II' are a pair of SP optimal policies chosen from the fixed training pool. If Ta and ny belong to the same equivalence class induced by कER, then by definition there exists an ER
symmetry & that maximizes Equation I1 to the self-play optimum value of J(TT)). Therefore, for each pair of optimal policies Ty F E II. we optimize Equation II over da. and save the de that optimize Equation I1 the highest value. We outline this approach in Algorithm 3 Appendix E We highlight a trade-off between the objectives of Equation [1] and Equation [T] while the former more directly optimizes for an ER symmetry, it assumes A. to be of certain form, while the latter assumes no such form but tacitly assumes some pair II' belong to the same equivalence class.
4 EXPERIMENTS
We evaluate our method in four different environments. focusing on how ER symmetries impact zero-shot coordination (ZSC) compared to self-play and other-play with Dec-POMDP symmetries. Specifically, we train independent agent populations that take advantage of ER symmetries and compare their cross-play performance within the population to baseline populations. The goal is to assess whether the use of ER symmetries leads to better coordination between agents than self-play or Pec-POMMD--symeetry
training.
Populations of agents using ER symmetries for ZSC are formed as follows: each agent chooses seeds at random to train k different optimal policies, IT, Agent i then independently performs ER symmetry discovery with their specific 11; by optimizing Equation 9 Equation 10 or Equation [1 and among their learned transformations uses the / that best preserve expected return as their ER symmetries. Agent then chooses m seeds at random and uses their learned symmetries to train m policies { 1== with reinforcement learning constrained by the learning rule in Equation 4 multiple policies (m > 1) are trained to mitigate the effect of seed that sub-optimally explores the space. Agent& then selects n; arg max k=1....... ( and deploys m, for cross-play.
7

---

Published as a conference paper at ICLR 2025
Aside from the environments in Sections 4.1 and 4.2 parameterize 60,8 , feed-forward neural
network with two hidden layers. The experiments mn Sections 4.3 and 4.4 use the JaxMARL environ- ment and implementations (Ruthertord et al. (023). For details our setup and hyperparameters, refer to Appendix A See Appendix[Fjton plots of interpretability of agent play. If accepted, we will release full working code for all four environments.
4.1 ITERATED THREE-LEVER GAME
We consider a Dec-POMDP inspired by Treutlein et al. (2021) where two agents choose one of three levers simultaneously, earning +1 for match and -1 otherwise over 2 rounds, with each
agent observing the other's 's previous action. Thus, |S] = 1, A = O = (1,2,3) x (1,2.3), r++1 =a and 01+1 a. of =a.
There are 6 Dec-POMIP symmetries (the 6 permutations of levers). The optimal Op policy chooses a lever uniformly in round one; if the agents match, they repeat that choice, otherwise they switch to the unique unused lever. This yields an expected return of 4/3 (optimal for ZSC given
1/3 chance of first-round success). Since & = MDP,, learning all of &J and applying Op* aR approximates the optimal ZSC policy.
Each ER symmetry agent first trains k: = 20 SP optimal policies using IQL with shared Q-values, and then makes them Boltzmann exploratory with a 1. For each tuple of local action permutations, we select the tuple of local observation permutations that maximizes the objective in Equation ( (averaged over 2000 episodes). The ERS agent then picks the / = 6 best ER symmetries. Each ERS agents learns exactly the 6 Dec-POMDP symmetries.
This game illustrates a setting where OP outperforms OBL (Hu et al. 2021 OBL fails (in its turn- based form) as agents assuming uniform randomness converge to uniform distribution. However, in the two-lever variant Op*"" (and hence Op**) fails due the lack of unique second-round choice, leaving repeat and switch policies in distinct, incompatible equivalence classes. This under- scores a limitation in the symmetry group's 's expressivity.
4.2 CAT/DoG ENVIRONMENT
We take the cat/dog game from Example 2 We build population of 5 independent Q-learning (IQL) [Tan] 1993) agents as self-play baseline. We build a population of 5 ER symmetry agents, for which each agent trains & 10 optimal self-play policies II', and then optimizes Equation 9 with vanilla policy gradient (Sutton et al. 1999). where dooe parameterized as probability distribution over all possible permutations of the observations (there being 2! for Alice and 4! for Bob). Equation / Algorithm suffices because permutations already satisfy compositionality and invertibility. Each ER symmetry agent uses = 3 ER symmetries to then train
3 OP& policy.
We find ER symmetries can prevent over-coordination in settings where non non-trivial Rec-POMDP symmetries do not even exist. It is worth mentioning that approaches based on cognitive hierarchies fail to find the optimal grounded communication protocol in this setting (Hu et al.) 2021 Cui et al.,
2021 Camerer al., 2004), since they assume other agents follow random lower-level strategies, and instead consistently converge onto "bailing" for a return of 1.
4.3 OVERCOOKED V2
Overcooked V2 is a recent Al benchmark for 7SC (Gessler et al., 2025). which improves on the cooperative multi-agent benchmark Overcooked (Carroll et al. 2219)) by introducing asymmetric information and increased stochasticity, creating more nuanced coordination challenges. In this work, we concentrate on the "Grounded Coordination Simple" layout, leaving the exploration of additional layouts to future work.
For ZSC, we train a population of 5 IPPO (Yu et al. 2022) policies as a SP baseline, where each policy uses RNN coupled with a CNN process the observations. The population of ER sym- metry agents each train = 12 IPPO SP policies, to then use Equation TT Algorithm 3 to obtain
I 1= 16 ER symmetries. Each agent trains 3 Op policies using their learned symmetries.
The IPPO baseline shows a bimodal XP score distribution, with agents either highly compatible or incompatible. In Figure? 2 the SP-optimal baseline scores mean XP of 6.74, compared 15.8
8

---

Published as a conference paper at ICLR 2025
Cross-play score distribution of the IPPO self-play play baseline population and the ER symmetry agent popula- tion Overcooked V2. The baseline population achieves mean SP scores of 162.33 + 0.14, and the ER symmetry popu- lation achieves mean SP scores of 27.81 + 0.3.
Figure 2:
Crosselay Seildhyy by Baselite
Cross-Flay Scores of
Hestgram Goundan InC
Gaundan KDC
Modes
Vodax
Mediarc 10.22
Media:: 2007
04.39
01212
0220
-00
354
-30
for the Op -optimal population. The ER symmetry population thus significantly reduces the SP- XP gap, leading to more consistent coordination. Overcooked V2's simultaneous moves further underscore the effectiveness of ER symmetries for ZSC.
4.4
HANABI
Hanabi (see Appendix G for details) a challenging Al benchmark, and has served as the primary test bed for many algorithms designed for zero-shot coordination, ad-hoc teamplay, and other coop-
erative tasks (Bard et al. 2020 Cui et al. 2021 Nekoei et al. 2021 2023 Muglich et al., 2022a
Preserves OP Optimality
Since ER symmetries contain Dec-POMDP symmetries, and capture equivalences beyond just rela- belling, they clearly more diverse than Dec-POMIP symmetries, and hence better satisfy Item from Section 3.1 We verify the ER symmetries also approximately satisfy Item 2
We take the 11 learned regularized ER symmetries from above, denoting this set as HER We find
6pp4' (T) = 23.59 0.04 and E
E Pooje [Op& (+())) = 23.34 + 0.05,
that E ---II
where we train 5 Op4 policies. Thus, Item is approximately satisfied by L
Zero-Shot Coordination
For ZSC we two baselines: (1) population of 5 IPPO agents, and (2) 5 IPPO agents with access to all Dec-POMDD symmetries constrained by the OP objective (Equation 4.. We also train population of ER symmetry agents that independently discover ER symmetries for the OP objective. Each ER agent uses k = 6 seeds to learn symmetries and saves the top 1 = 11 that best preserve expected return. Every population consists of 5 agents, where each agent trains m and deploys the one with the highest return. Symmetries selecting 64 fixed transpositions on the local action space, with the same transpositions fixed for both local policies to simplify the search in the symmetric game Hanabi.
policies
trained via Equation 10 by randomly
Inspired by the symmetrizer in Treutlein et al. (202I); Muglich et al. (2022a); Van der Pol et al. 2020), define the symmetrizer S II - II by S(T)) (a: Te) [Ti [x'e(s] (o, Tt), where can be taken to be either &ER or MDDP Agents from any population can thus transform their policy with S before deploying for cross-play, ensuring invariance the deployed policy w.n.t. & (since ((S())) ((T), Vo E Φ). As per the empirical results below, the symmetrizer functions as a policy improvement operator for cross-play across multiple policy populations.
Table I shows that the agents using ER symmetries improve in ZSC over both baselines; this is even spite of the Dec-POMMP agent population assuming access to environment symmetries. As well, even with just using subset of transformations from FR the return symmetry agents are able to converge on policies that generalize well in cross-play. We also notice that symmetrization with respect to EER or &DDP improves coordination amongst agents of all populations considered; we can see that ER better improves the optimal self-play policy population, and a MDP better improves the other two, which aligns with expectation since EER is only explicitly enforced to maintain invariance over optimal self-play policies, whereas MDP maintains invariance over any policy type.

---

Published as a conference paper at ICLR 2025
Table 1: Self-play, within-population mean cross-play (XP) and median cross-play (XP(*)) scores are reported. The Op Mur population used all 120 Dec-POMDP symmetries, whereas the Op*
population used 11 ER symmetries. "MDP" indicates the population was symmetrized with Dec- POMDP symmetries at test time, and "ER" analogously indicates symmetrization with expected return symmetries. The ER symmetrizer uses 11 expected return symmetries.
Model
Self-Play
XP
XP(*)
XP(*)+MD
XP(*)+ER
IPPO
24.04 : 0.02
4.02 0.17
0.12 0.03
0.14 0.03
0.10 0.03
IPPO + Ope XBP
23.81 + 0.03
8.61 0.17
0.14
8.70 0.16
9.91 + 0.14
IPPO + Op
23.74 + 0.03
21.64 + 0.07
22.03 0.05
0.00
25.25
5 RELATED WORK
Extensive research exists on coordination in multi-agent systems, particularly in zero-shot coordi- nation. Methods like Hu et al. (2020); Muglich et al. (2022a) use Dec-POMDP symmetries to avoid incompatible policies, while Hu et al. (2021) rely on environment dynamics for grounded policies. Diversity- -baeed approaches also leverage known symmetries and simulator access (Cui et al. 2023 Lupu et al. 202T). In contrast, ER symmetries can be learned from agent-environment interactions without privileged information, enabling grounded signaling and effective coordination in concur- rent environments (see Sections 4.2 and
In agegle settings, symmetry has been shown to reduce sample complexity in RL (Van der Pol et al. 2020; Zhu et al. 2022 Nguyen al. 2024). In multi-agent systems, symmetries reduce policy space complexity and help agents identify equivalent strategies (van der Pol et al., 2021 Muglich al., 2022a). However, many methods require explicit knowledge of symmetries, or rely on predefined groups (Abreu et al. 2023; Yu et al. 2024 Nguyen et al. 22024). Our work generalizes these approaches by introducing ER symmetries, which do not require prior symmetry knowledge or equivariant networks, and can be learned directly through environment interactions.
Our work relates to value-based abstraction, which groups states or observations with similar value functions. Rezaci-Shoshtar et al. (2022) use lax- max-bisimulation to learn MDP homomorphisms, while Grimm et al. (2021) learn a model of the underlying MDP for value-based planning. In contrast, we Tocus on symmetries in the policy space that preserve expected return. ER symmetries are concep- tually related to Q- -irrelevance abstractions (Li al.) 2006) in that both aim to preserve the optimal value function of an MDP. However, whereas Q -r-irreleevacc abstractions reduce complexity by ag- gregating states, ER symmetries form a group that acts bijectively on the policy space, transforming optimal policies into other policies with the same expected return.
CONCLUSION
This paper defined expected return symmetries a group whose action preserves policy expected return. We demonstrated that the symmetries in this group can be learned purely from interactions with the environment and without requiring privileged environment information. We demonstrated that this symmetry class significantly enhances zero-shot coordination, significantly outperforming traditional Pec-POMPPPor symmetries, which are subset of this group. Importantly, showed that expected return symmetries are effective in challenging settings where state-of-the- ZSC methods, such off-belicf learning (Hu et al. (22T)) in Hanabi approaches based cognitive hierarchies, either fail completely (e.g., in the lever game and cat/dog environments) or face difficulties in their application (e.g., Overcooked V2).
One major limitation of our approach is that we constrain the search for symmetries to bijections over the action and observation spaces. While this works well in many settings, as shown in our experiments, there are environments, e.g. the two-lever game, in which this limited expressivity cannot provide enough diversity within the equivalence classes of policies that are optimal w.r.t. OP with ERR, to prevent coordination failure in ZSC. Another limitation is that the success of our method is heavily dependent on the type of policies which are used to learn the ER symmetries.
Our work opens several avenues for future research. One direction is to explore the use of expected return symmetries in ad-hoc teamwork or single-agen settings. Another is investigate broader classes of symmetries, beyond the ones that arise from bijections on the actions and observations.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Darius Muglich is supported by Toshiba Research, well the EPSRC centre for Doctoral Train- ing in Autonomous and Intelligent Machines and Systems (EP/S0240501)). Johannes Forkel is funded by the UKI grant EP/Y028481/1 (originally selected for funding by the ERC). Jakob Foer- ster is partially funded by the UKI grant EP/Y028481/1. Jakob Foerster is also supported by the JPMC Research Award and the Amazon Research Award. EP/Y028481/1
REFERENCES
Miguel Abreu, Luis Paulo Reis, and Nuno Lau. Addressing Imperfect Symmetry: Novel Symmetry-Leaming Actor-Critic Extension. arXiv preprint arXiv:2309.02711, 2023.
Nolan Bard, Jakob N Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The Hanabi Challenge: A New Frontier for AI Research. Artificial Intelligence, 280:103216, 2020.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv preprint arXiv:2104.13478 2021.
Colin Camerer, Teck-Hua Ho, and Juin-Kuan Chong. A Cognitive Hicrarchy Model of Games. The Quarterly Journal of Economics, 119())8611888, 2004.
Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the Utility of Learning about Humans for Human-Al Coordination. Advances in Neural Information Processing Systems, 32, 2019.
Chess.com. The Worst And The Best Chess Handshakes Of World Cup 2021. https::/www 7bDyNYHI 2021. Accessed: 2024-09-30.
yout com
wtw.tuubee.oomttttccheeeeeeee http://ttccchtvtt
Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge Equivariant Convolu- tional Networks and the Icosahedral CNN. In International Conference on Machine learning, pp- 1321-1330. PMLR, 2019.
Brandon Cui, Hengyuan Hu, Luis Pineda, and Jakob Foerster. K-level Reasoning for Zero-Shot Coordination in Hanabi. Advances Neural Information Processing Systems, 34:8215-8228, 2021.
Brandon Cui, Andrei Lupu, Samuel Sokota, Hengyuan Hu, David J Wu, and Jakob Foerster. Adver- sarial Diversity in Hanabi. In International Conference on Learning Representations, 2023.
Marc Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing Convolu- tional Neural Networks for Equivariance to Lie Groups on Arbitrary Continuous Data. In Inter- national Conference on Machine Learning, pp. 3165-3176. PMLR, 2020.
Tobias Gessler, Tin Dizdarevic, Ani Calinescu, Benjamin Ellis, Andrei Lupu, and Jakob Foerster. OvercookedV2: Rethinking Overcooked for Zero-Shot Coordination. In International Confer- ence on Learning Representations, 2025.
Christopher Grimm, André Barreto, Greg Farquhar, David Silver, and Satinder Singh. Proper Value Equivalence. Advances in Neural Information Processing Systems, 34:7773-7786, 2021.
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "Other-Play" for Zero-Shot Coordination. In International Conference on Machine Learning, pp. 4399-4410. PMLR, 2020.
Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, Noam Brown, and Jakob Foerster. Off-Belief Learning. International Conference on Machine Learning, pp. 4369-4379. PMLR, 2021.
Jiaming Ji, Tianyi Qiu, Boyuan Chen, Borong Zhang, Hantao Lou, Kaile Wang. Yawen Duan, Zhonghao He, Jiayi Zhou, Zhaowei Zhang, et al. Al Alignment: A Comprehensive Survey, arXiv preprint arXiv:2310. 19852, 2023.
11

---

Published as a conference paper at ICLR 2025
Zahi M Kakish, F RodrAguez--era, D Bischel, A Mosquera, R Boumghar, S Kaczmarek, Seabrook, P Metzger, and JL Galanche. Open-source Al Assistant for Cooperative Multi-agent Systems for Lunar Prospecting Missions. In 8th European Conference for Aeronautics and Space Sciences (EUCASS), 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. ImageNet Classification with Deep Con- volutional Neural Networks. Communications of the ACM, (0(6):84-90, 2017.
Lihong Li, Thomas Walsh, and Michael L Littman. Towards a Unified Theory of State Abstraction for MDPs. AI&M, 1(2)3, 2006.
Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory Diversity for Zero-Shot Coordination. In International Conference on Machine Learning, pp. 7204-7213, PMLR, 2021.
Stefano Mariani, Giacomo Cabri, and Franco Zambonelli. Coordination of Autonomous Vehicles: Taxonomy and Survey. ACM Computing Surveys (CSUR), 54(1): 2021.
Darius Muglich, Christian Schroeder de Witt, Elise der Pol, Shimon Whiteson, and Jakob Fo- erster. Equivariant Networks for Zero-Shot Coordination. Advances in Neural Information Pro- cessing Systems, 35:64 10-6433, 2022a.
Darius Muglich, Luisa M Zintgraf, Christian A Schroeder De Witt, Shimon Whiteson, and Jakob Foerster. Generalized Beliefs for Cooperative AI. In International Conference on Machine Learn- ing, pp. 16062-16082. PMLR, 2022b.
Shravan Matthur Narayanamurthy and Balaraman Ravindran. On the hardness of finding symmetries in Markov decision processes. In International Conference on Machine learning, pp. 688-695, 2008
Hadi Nekoei, Akilesh Badrinaaraayanan, Aaron Courville, and Sarath Chandar. Continuous Coor- dination As a Realistic Scenario for Lifelong Learning. In International Conference on Machine Learning, pp.
PMLR, 2021.
Hadi Nekoei, Xutong Zhao, Janarthanan Rajendran, Miao Liu, and Sarath Chandar. Towards Few- shot Coordination: Revisiting Ad-hoe Teamplay Challenge In the Game of Hanabi. In Conference on Lifelong Learning Agents, pp. 861-877, PMLR, 2023.
Hai Nguyen, Tadashi Kozuno, Cristian C Herrrndez, and Masashi Hamaya. Symmetry- aware Reinforcement Learning for Robotic Assembly under Partial Observability with a Soft Wrist. arXiv preprint arXiv:2402. 18002, 2024.
Frans A Olichoek, Matthijs TJ Spaan, Nikos Vlassis, et al. Dec-POMDPs with delayed communi- cation. In The 2nd Workshop on Multi agent Sequential Decision-Making in Uncertain Domains. Citeseer, 2007.
Cinjon Resnick, Ilya Kulikov, Kyunghyun Cho, and Jason Weston. Vehicle Communication Strate- gies for Simulated Highway Driving. arXiv preprint arXiv: arXiv:/804.00 1804.0717, 2018
Sahand Shraaiiihosttari, Rosie Zhao, Prakash Panangaden, David Meger, and Doina Precup. Con- tinuous MDP Homomorphisms and Homomorphic Policy Gradient. Advances in Neural Infor- mation Processing Systems, 35:20189 092044 2022.
Alexander Rutherford, Benjamin Ellis, Matteo Gallici, Jonathan Cook, Andrei Lupu, Gardar Ingvarsson, Timon Willi, Akbir Khan, Christian Schroeder de Witt, Alexandra Souly, Sap- tarashmi Bandyopadhyay, Mikayel Samvelyan, Minqi Jiang, Robert Tjarko Lange, Shimon Whiteson, Bruno Lacerda, Nick Hawes, Tim Rocktaschel, Chris Lu, and Jakob Nicolaus Fo- erster. JaxMARL: Multi-Agent RL. Environments and Algorithms in JAX. arXiv preprint arXiv:2311.10090 2023.
Arthur L Samuel. Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of research and development, 3(3):210-229, 1959.
12

---

Published as a conference paper at ICLR 2025
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy Gradient Meth- ods for Reinforcement Learning with Function Approximation. Advances in Neural Information Processing Systems, 12, 1999.
Ming Tan. Multi-Agent Reinforcement Learning: Independent vs. Cooperative Agents. In Interna- tional Conference on Machine Mearning, pp. 330-337, 1993.
Gerald Tesauro et al. Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3):58668 68, 1995.
Johannes Treutlein, Michael Dennis, Caspar Oesterheld, and Jakob Foerster. A New Formalism, Method and Open Issues for Zero-Shot Coordination. In International Conference Machine Learning, pp. 10413-10423. PMLR, 2021.
Elise Van der Pol, Daniel Worrall, Herke van Hoof, Frans Olichock, and Max Welling, MDP Ho- momorphic Networks: Group Symmetries in Reinforcement Learning, Advances Neural In- formation Processing Systems, 33:4199-4210, 2020.
Elise van der Pol, Herke van Hoof, Frans A Oliehoek, and Max Welling, Multi-Agent MDP Homo- morphic Networks. In International Conference on Learning Representations, 2021.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang. Alexandre Bayen, and Yi Wu. The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games. Advances in Neural Information Processing Systems, 35:2461 1-24624, 2022.
Xin Yu, Rongye Shi, Pu Feng, Yongkai Tian, Simin Li, Shuhao Liao, and Wenjun Wu. Lever- aging Partial Symmetry for Multi-Agent Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17583-17590 2024.
Xupeng Zhu, Dian Wang, Ondrej Biza, Guanang Su, Robin Walters, and Robert Platt. Sample Efficient Grasp Learning Using Equivariant Models. arXiv preprint arXiv:2202.09468, 2022.
13

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL SETUP
For expected return symmetry discovery in the three-lever game, each ERS agent trains 20 self-play optimal policies using IQL over 10000 episodes, with an 0.1 e-greedy behaviour policy and learning rate of 0.1. The computed Q-values Then for each pair of local action permutations, the ERS agent maximizes the objective [ by searching over each pair of local observation permutations. The best quadruples of two local action permuations and two local observation permuations are kept as learned expected return symmetries. Each of ERS agents exactly finds the 6 Dec-POMDP symmetries.
then used to construct Boltzmann exploratory
policies, with temperature a
For expected return symmetry discovery in cat/dog, we use temperature of a 1/2.667 for Boltzmann exploration to promote sufficient exploration of different actions. We use constant baseline function with value 9.5 for the policy gradient. We use learning rate of 0.01 and 2000 episodes for each inner loop of Algorithm
For expected return symmetry discovery in Overcooked V2 and Hanabi, we parameterize èo, o as two hidden layer, feedforward neural network, with each linear layer intialized as (O'I-dimensione identity matrix; this choice of initialization necessary as the symmetry discovery is highly initial- ization sensitive. We apply ReL.U to the final output of the network to promote sparsity in the repre- sentation. We build on top of the environment implementation and baseline algorithms in JAXMARI. (Rutherford al. 2023).
For Hanabi, we run each inner loop of Algorithm 2 for 2.25e9 timesteps across vectorized Han- abi environments. As per Equation I0 we use λι 0.65, X 2.5e-9. 0.A.0 is fixed action transposition for each learned symmetry. We use a temperature of a = for Boltzmann exploration.
For Overcooked V2, affine map. We use a temperature of a = 1.1 for Boltzmann exploration.
each inner loop of Algorithm for 1.5e8 timesteps. 6A.0 is learned
For both Hanabi and Overcooked V2, we use PPO and Generalized Advantage Estimation. For Han- abi, we use epochs, 1024 environments per pretrained policy, 128 environment steps per update, minibatches, = 0.99, GAE Lambda 0.95, CLIP EPS 0.2, VF COFFF 0.5, MAX GRAD NORM 0.5, a learning rate of le-5 and a linear learning rate annealing schedule. For Over- cooked V2, we
epochs, 256 environments, 256 environment steps per update, 64 minibatches, 0.99, GAE Lambda = 0.95, CLIP EPS = 0.2, VF COEFF = 0.5, MAX GRAD NORM = 0.25, a learning rate of 1e-5 with no annealing.
Methods for Hanabi and Overcooked V2 were ran on A40 and L40 GPUs.
Code for Cat/Dog:
ab. httpop//...aeaeerr...ooooo/////t 19NDhh?? usp=sharing
Code for Iterated Three-Lever Game:
Code for Hamab//Oveeorroooee V2:
14

---

Published as a conference paper at ICLR 2025
B PROOFS
B. GROUP PROPERTIES
Theorem. F = { f v (II))- _ forms group under function composition.
Proof. To show that ERR forms group under function composition, we verify the group axioms: closure, associativity, identity, and inverses.
Closure: For any 1i, 62 E hER we need to show that Φi o tb E & For the composition Φi $2. we see that
(0r o o2) = 01 (12 01 (I II."
which shows that o1 Φ2 E D Associativity: Function composition is associative, so for any Φ1, 22, da dbR,
(0r o (2) c d3 = Φ1 o (d2 o 63).
Thus, associativity holds.
Identity: The identity function Id v satisfies Id(r) for all II, and thus Id 4 and acts as the identity element.
Inverses: We let d E LER Since V is finite group, there exists positive integer k such that df Id, and thus Φ ok-1, Since @ E &ER due to closure, we see that & E DER
Since &ER satisfies closure, associativity, identity, and inverses, it forms group under function composition.
Theorem (Dec-POMDP Symmetry Expected Return Invariance). For any Dec-POMDP symmetry MDP, and any joint policy n, it holds that
( (((TT).
Proof. We prove by induction the time step t 0,1..... H that for every obbsevnttsrvationn history (AOH) Tt.
(T) (o(=))
Since the initial AOH is the empty history (i.e., To = ((To)), this immediately implies
J(T) = V7o Vo(o)(((TT)) J(r(T))
Base Case (l H):
At time H the game terminates, by definition,
Va V=(TH) and (o(m)(((TH) 0.
Inductive Hypothesis:
Assume that for some with t < H, the equality
(=(T(+1) = (((r)(((TT=1))
holds for every AOH T+-1-
Inductive Step (t): for π is
Consider arbitrary AOH T.. By the Bellman equation, the value function
(T.) = Σ
(st Te)
Σ
x(a T()
Σ
T(s++1 St, az)
S.ES
atEA
S1+1ES
R(st+1,0)+ Σ
U(or+1
15

---

Published as a conference paper at ICLR 2025
Similarly, the value function for the transformed policy d(T) on the transformed history Φ(T)) is (o(T)(((TT))
Σ B (0(+))
((T:))
Σ ((T)(((a)) d(Tx))
a.EA
Σ T(6(#)+1) (+tt),
x
Rt-1ES
((())) +y E u(ő(ou+1) (la
x
P-160
By the symmetry properties (e.g.. Equations 2 and 3) we have
(6(8)) ((T))) (st Te), ((T)(((()) I ((T)) T(at)) Tt).
and the invariance of T, R, and UI under @. Thus,
= Σ (8 TT) Σ x(at (T)
Σ T(8+11 (1)
#:E8
atEA
#++1E8
x a((+41,,))+ +7 +?
Σ
U(ou+1 S141, (o)
01100
By the inductive hypothesis Vo(T) (d(T((1)) = (T(+))),, so it follows that
(o(x)(((TT)) = (T(T))
This completes the inductive step.
By mathematical induction, the equality (T(T)) (o(T)) holds for all / 0,1, .... H, and hence
( VT) (o(=)(((T))) ((((T))
Theorem (Dec-POMDP Symmetry Boltzmann Exploratory Invariance). Let Φ E MDP be Dec- POMDP symmetry and let E 11 be Boltzmann exploratory joint policy with temperature >> 0. Then, the transformed policy ((x) is also Boltzmann exploratory, i.e.,
Qates (o((())))))
exp
)()) (o(at) ((T)))
a
Loce (o(r))
Enred (4(101721)) exp
Moreover, holds that
Quian (D(Ti), o(a))) (tt,
for all agents i, times AOHs T/J and local actions af.
Proof. We first prove by induction the time step that for every agent i,
(
Q (T).
Base Case (t H): At terminal time H, the episode ends. Hence, by definition we have
Q¹ (gg) 0 and Qsta (6(Th). 0.
Thus, the base case holds.
Inductive Hypothesis:
Assume that for some t H. and for all agents i, all local histories T/ and actions of the following holds:
((ata)) of (f
16

---

Published as a conference paper at ICLR 2025
Inductive Step (t): For a given local AOH 7/ and local action a;, the Bellman equation gives
(T Σ
(st,,, re r/) Σ n (a," (a=t1(t))
Σ
T(s++1 st,
(12)
86+1
x R(s++1,0) +
Ut (842,
E
T'(441 1441) (F (2tm))
11
of (E
Here x-1 0g T, denote the parts of the joint policy æ, joint action ae, and joint AOH Tr, which do not belong to agent i. Similarly, under the transformed policy Φ(x), the Q-function for agent is given by
Co(n) (é(T)))
Σ
Ba(r) (o(s.))) o(T))) Σ ((T) (((a5) o((T))) Σ
T(((se+1) ( ((()))
#E.TEES
act1
x
((0((41))0(a1)) + Σ (d(o0(())) ((s4+)).
(13)
Σ
(( ( ( (ol
x
oti1 E0 1 (Ai(0())4))))
Since @ is a Dec-POMDP symmetry, Equation 3 states that
T(6(s)11) ((s))) T(se+1 18,, (t, U(blo++1) (((41)) U(0e+1 (841,
R(0(9+11) = R(s++1,)))
Hence, for the belief B, it holds that
Borz) (o(s)), d(T)) o(+;)) = B, To T().
By definition of (()) we that
(()) ((aT") ((T=T)) (
- "(a;") Tt)))
Moreover, by the inductive hypothesis,
Co (o(T())))) (((44))))))))) = (f
Finally, it holds that
(A'(((()) A'(T))
as this a necessary condition on Φ. such that (T)) is well-defined for all n.
Substituting all of the above equations into Equation we obtain:
( (1(r/
This completes the induction step.
17

---

Published as a conference paper at ICLR 2025
Therefore, for any agent local history r/. and action oj. the transformed policy satisfies
(riaa))
exp
((x)) (d(a)) ((())) = =x' (a/(l//)) = E
EetEA exp
Doir (o(T)))))) exp
a
Tore (ocm (a(r)))0a))))
EalEo-1(A exp
a
which shows that ((T) E 11%.
B.2 COLICY-GRADIENT BASED BOLTZMANN- EOLPRRAAN POLICIES
Recall that for a decentralized partially observable setting, each agent i acts based on its local ac- tion-observation history (AOH) T/. The value Ti. when assuming that all agents follow their respective local policies in is given by
(a(r))
Σ ('EA((F))
<' T/) Q2(
where Q (Ti, af) the local action-value function for agent when assuming that all agents follow their respective local policies in
In practice, actor critic methods update the critic and actor on different timescales. With appropriate learning rate schedules, the local value estimates Q' (T). of) converge and approximately satisfy the Bellman equations. this regime, we may treat Q+ a;) as fixed when optimizing the policy. Then, for agent i, the entropy darropy-regllriieer objective becomes
J=z(a')
Σ (FE))
n'a Q2(t. + a (T))),
with the entropy given by
((T'(-11))) = Σ
a'aa 78) log T/).
a'EA'(F))
Because (T/ af) is treated as fixed and the entropy function is strictly concave, the local ob- jective J (T') is strictly concave in x'(- 7f). Hence, its unique maximizer can be computed independently for each agent and each local history by solving Lagrangian optimization problem.
The following theorem formalizes that the unique maximizer of Jrę (TT*) ) the Boltzmann (softmax)
policy.
Theorem (Local Boltzmann Policy from Marropy-Regularizee Objective). For a fixed local AOH Ti of agent i, the optimal local policy that maximizes
(x')
Σ ('EA((())
<aat rL) (t a + (f))
subject to
Σ
x'(af T²) =
a'EAA(TT))
is given by
(ri.a))
exp
+ ra T/)
EneeA exp (ri.a)))
18

---

Published as a conference paper at ICLR 2025
Proof. Assume that for the fixed local AOH r/. the value estimates (T, aj) treated stant. Define the Lagrangian
((T Σ a'EA'(T))
(a 7/) (1),,
Σ
(aa r/) log (a) T/)) + a
Σ
a'a 73) 1;)-
d'EAA(T)
('EA)(T)))
Taking the derivative with respect to xO (a r/) for each a' E AA((Ti)) yields
JC
Q of) a (log (a) 7/) + 1) + =
(a) r/)
Rearrange this equation to obtain
log n (at Tz)) Qt (T( a
Exponentiating both sides gives
x (a T.) = exp ai(
A- a
exp
Since the term exp( )=ي is independent of a', it is determined by the normalization constraint: (+)
n' (at r/) exp (~-=))))
Σ
Σ
exp
a
a
o a'EA((+))
a'EAi(T()
Defining
Q (Tt
z11²)) =
Σ exp
a'E
we have
exp
a
(T()
Thus, the unique maximizer is given by
(1(1aa)
exp
exp
<aaa (/)
2T(Ti)
Emted'(T)) exp
Q (1(riee))
Note the Q-functions above can be provided by a critic network or be estimated via empirical returns. When the local (T) a estimates have converged, the local objective decouples over 7. and its unique maximizer is the Boltzmann (softmax) policy. This motivates our definition of the set of Boltzmann exploratory policies,
exp
II
n/ (af
T!)
Val, VT Vi 1
E EMEA:(+))) exp
Qh(riaa))
and, correspondingly, our definition of the set of self-play optimal Boltzmann-exploratory policies
II = arg max ((x.
=EnT
Finally, we define expected return symmetries,
ER
Φ E
VT E I. ((T) E mma.
the subset of transformations preserving self-play optimality of Bolzzmam--explorttory policies.
19

---

Published as a conference paper at ICLR 2025
C WHY BOLTZMANN--XPPORAADO POLICIES ARE NECESSARY
Defining expected return symmetries in terms of Boltemann-cxplorator policies, rather than just e-soft policies, necessary. If defined via e-soft policies, permuting any set of actions which are suboptimal in self-play would be expected return symmetry, since all suboptimal actions would be taken with the same probability. The following example illustrates this:
Consider the cat/dog game from Example 2 Boltzmann exploration is necessary to disambiguate for Alice the actions of removing the barrier and bailing: simple e-greedy exploration does not suffice, since we would then still use both these suboptimal actions with equal probability, and so the expected return remains the same under the relabeling of these actions. Thus, under e-greedy exploration, permuting the labels of the actions for removing the barrier and bailing is an expected
return symmetry. This, however, undesirable because we want Op -optimal policies to be able to disambiguate these very different actions. Under Boltzmann exploration, Alice takes the reveal action more often than the bail action, and so relabeling these actions lowers expected return and thus not an expected return symmetry.
D LEARNED TRANSFORMATIONS SATISFY GROUP PROPERTIES
This section analyzes the learned ER symmetries for their group properties.
We first train six (near-)optimal IPPO policies with independent seeds II', obtaining mean expected return of [E<-i([((<))) = 24.04 + 0.02. Next, we randomly select 64 local-action-space transpositions, and learn the corresponding { 164 via optimizing Equation / Algorithm [ That is, we fix the same action transposition for each local policy, significantly constraining the search. This space, yet as we show below we still learn effective ER symmetries for coordination. We then save the 11 best transformations (those that maximize Equation 9 as unregularized ER symmetries. These are used to maximize Equation TO Algorithm [ on another set of 64 random transpositions, now enforcing compositional closure and invertibility. The 11 best are saved as regularized ER symmetries.
significant undersampling of the 190 possible transpositions on each local action
Table 2: Comparison of 11 unregularized and 11 regularized ER symmetries applied to 6 unseen optimal policies ([Hunsenn = 6). Regularization enforces compositionality and invertibility. For k = 2, 3, let Ju gg [J[(2] randomly sampled transformations. We report Single Transform.
o...o (x)(T)) denote the expected return after composing
(J1), Double Comp. (J2). and Triple Comp. (Jz). Relative Reconstruction Loss measures approximate invertibility (lower is
better): En Brsx| ( using the & norm for AOH vectors. Recall Em~ (T))
24.04 + 0.02.
Single Transform.
Double Comp.
Triple Comp.
Rel. Rec. Loss
Unreg.
22.88 0.07
21.10 0.09
20.36 0.11
31.4% 1.8%
Reg.
23.32 0.05
22.16 = 0.07
20.94 0.12 16.7% 0.18%
Table 2 shows that up to minor deviations in expected return preservation, the learned ER symme- tries still approximately satisfy closure under composition. addition, when invertibility is en- forced, the relative reconstruction loss decreases substantially (a lower relative reconstruction loss tells us applying the transformation twice brings us closer to the original AOH, suggesting approx- imate invertibility). We conclude that the learned ER symmetries, especially the regularized ones, approximately satisfy the desired group-theoreti properties.
20

---

Published as a conference paper at ICLR 2025
E ALGORITHMS
Algorithm Learning Expected Return Symmetries with Policy Gradients (without enforcing com- positionality invertibility). ... Optimization of Equation 9
Input: A Dec-POMDP, set II' of joint policies in it, parameterization óo, do,e. 0 O learning
rate > 0, for the number of top transformations to save
2: Initialize list of top / average expected returns: Jup --...... -o (length 7)
3: Initialize list of top I transformations: @up = [ (length /)
4: for each tuple of local action transpositions Φ E I[ Transpositions(44) do
5: Initialize $ with random parameters 0 θ
6: while not converged do
7: for each policy и E TT' do Sample batch B of joint AOHs, and the corresponding sequences of returns, using the transformed policy ( = (ΦA, (z)
8:
9:
Compute advantage ( (T,,a,) a,) for f = O,.... H 1, using any advantage
function (e.g., TD, GAE)
10:
Compute policy gradient:
H
VoJ(Co(TT)
=
Vo (og)o(T)((a) (
B
THEB
t=
Update parameters: 0 + 1/ (do(())
12:
end for
end while
14:
Compute average expected return Jøs where for every E II' the expected return ((os( (m)) is approximated by the average return over number of episodes:
Joe
[(b((T)
JETP
15:
Find the index the lowest return in Jrop say imin
16:
if Jop [mi] then
17:
Replace the lowest return: Jop[imini +- Jop
18:
Replace the corresponding transformation: drop [imin] (0o.0, d.A.)):
19:
end
20:
end for
21:
Output: Set Shop of the best learned transformations
21

---

Published as a conference paper at ICLR 2025
Algorithm Learning Expected Return Symmetries (enforcing compositionality and invertibility) Optimization of Equation TO
Input: A Dec-POMDP, a set II' joint policies in it, a parameterization do.e. 0 O, learning rate > O, transformations { pm obtained from Algorithm [ 1 for the number of top
transformations to save, regularization weights λ1, A2
2: Initialize list of top / average expected returns: Jrop [-000000 .....,. co] (length ()
3: Initialize list of top transformations: drop = = [...... (length /)
4: for each tuple of local action transpositions AA E II. Transpositions(44) do
5: Initialize Φo, e with random 0 E θ
6: while not converged do
7: for each policy
I1' do
8:
With probability 1
A1 set 60 Φg. and with probability A1 sample di Φj
{Φr
Om and set Φu o, o Φy o oj
9:
Sample batch B of joint AOHs, and the corresponding sequences of returns, using
the transformed policy (TT)
Compute advantage A A az), for all O, H 1, using any advantage
function (e.g., TD, GAE)
1 Compute the invertibility regularization term L(D) = [o Eoco [d(o, oo. (0))
11:
and its gradient (()
12:
Compute policy gradient:
Ø-1
VoJ(Ōo(TT) ~
Vo log ( T1)A0(())
THEB
1=U
13:
Update 0 0 n (VoJ A2 VoL())
14:
end for
15:
Compute average expected return Jay. where for every TT' the expected return [ós (T)) is approximated by the average return over number of episodes
J
1
Σ [()((T))
JETP
16:
end while
17:
Find the index of the lowest return in Jusp say imin
18: if JØs Jeppp [min]] then
19:
Replace the lowest return: Jup [[min +- Jáv
Replace the corresponding transformation: drop [minl +- (60.0,
21: end if
22:
end for
23: Output: Set @up of the best learned transformations
22

---

Published as a conference paper at ICLR 2025
Algorithm 3 Learning Expected Return Symmetries through cross-play maximization between pairs of Policies.... Optimization of Equation 1I
1: Input: A Dec-POMDDR a set IT' of joint policies in it, a parameterization do,0, 0 E O learning
rate 77 > 0, for the number of top transformations to save
2: Initialize list of top / average expected returns: -op = [-o0.... -oo (length ()
Initialize list of top transformations:
Sup [0. ..... 0] (length /)
4: for each pair of joint policies (I;; TT) IT' IT' {(T, x)) x E IT') do
5: Initialize Φo,8 and d.A. with random parameters
6: while not converged do
7: Sample a batch of joint AOHs, and the corresponding sequences of returns, using
transformed pair (T: Øe (xz))
8: Compute advantage (T.. (Tr, az), for all t = 0, H 1, using any advantage
function (e.g.. TD, GAB)
9:
Compute policy gradient:
Ve log de (T)) ())())) (Te, ae)
(TJ
TH
10:
Update parameters: - VoJ (0
11:
Compute average return J(m ((mt)o((77)) J [ Se (T3)) over number of episodes
end while
13:
Find the index of the lowest return in Jrop say imin
14:
if ((n;)oo(())) (oo(x))) > Fmin] then
15:
Replace the lowest return: Jup (mmnl + (m(])))(33)))
16:
17: end Replace the corresponding transformation: drop [
(2.,0)
18: end for
19: Output: Set Shop of the best learned transformations
23

---

Published as a conference paper at ICLR 2025
F INTERPRETABILITY OF HANABI OP AGENTS
OF with Expected Return Symmetries
OP with Dec-POMDP symmetries
octont 64
81
Figure 3: Conditional action matrices of Opd -optimal and Op** -optimal policies; i.e., P(a d)-1). We select the agent from both respective populations achieving the highest cross-play scores. We can see the Op optimal policy more consistently uses a rank hint to signal playing the fifth card, whereas the Op -optimal policy similar convention but less consistently.
HDP
G HANABI
Hanabi a cooperative card game that can be played with 2 to 5 people. Hanabi is popular game, having been crowned the 2013 "Spiel des Jahres" award, German industry award given to the best board game of the year. Hanabi has been proposed as an AI benchmark task to test models of cooperative play that act under partial information [Brdd al. (2020). To date, Hanabi has one the largest state spaces of all Dec-POMDP benchmarks.
The deck of cards in Hanabi is comprised five colors (white, yellow, green, blue and red), and five ranks (1 through 5), where for each color there are three I's, two each of 2's, 3's and 4's, and one for a total deck size of fifty cards. Each player dealt five cards (or four cards if there are players). At the start, the players collectively have eight information tokens and three fuse tokens, the uses of which shall be explained presently.
In Hanabi, players can see all other players' hands but their own. The goal of the game is to play cards collectively form five consecutively ordered stacks, one for each color, beginning with card of rank and ending with card of rank 5. These stacks referred to fireworks, playing the cards in order is meant to draw analogy to setting up a firework display.
We call the player whose turn it is the active agent. The active agent must conduct one of three actions:
Hint The active agent chooses another player to grant hint to. A hint involves the active agent choosing color rank, and revealing their chosen partner all cards in the partner's 'ss hand that satisfy the chosen color rank. Performing a hint exhausts an information token. If the players have no information tokens, a hint may not be conducted and the active agent must either conduct a discard or play.
Discard The active agent chooses one of the cards in their hand to discard. The iden- tity of the discarded card is revealed to the active agent and becomes public information. Discarding card replenishes an information token should the players have less than eight.
Play The active agent attempts play one of the cards in their hand. The identity of the played card revealed to the active agent and becomes public information. The active agent has played successfully if their played card is the next in the firework of its color to played, and the played card is then added to the sequence. If firework is completed, the players receive new information token should they have less than eight. If the player
24

---

Published as a conference paper at ICLR 2025
is unsuccessful, the card is discarded, without replenishment of information token, and the players lose fuse token.
The game ends when all three fuse tokens are spent, when the players successfully complete all five fireworks, when the last card in the deck is drawn and all players take one last turn. If the game finishes by depletion of all fuse tokens (i.e. by "bombing out"), the players receive score of O. Otherwise, the score of the finished game is the of the highest card ranks in each firework, for a highest possible score of 25.
More facts about Hanabi:
1. The Dec-POMDP symmetries correspond permutations of the five card colors (5! 120).
2. two-player Hanabi, there are 20 possible actions per turn, organized into four types: Play, Discard, Color Hint, and Rank Hint. These yield 190 distinct action transpositions.
3. A perfect score is 25, though some deck permutations make this score unreachable, so no policy can guarantee an expected return of 25.
25


Reviews:
[{"review_id": "3cijobAvQ6", "reviewer": "Reviewer_8d16", "summary": "This paper addresses the zero-shot coordination problem in multi-agent systems within the context of decentralized partially observable Markov decision processes. It introduces a new symmetric class, which is a class containing the previously proposed environment symmetries. The paper also presents an algorithm to find these symmetries and demonstrates that agents within this symmetric class can achieve better zero-shot coordination in decentralized partially observable Markov decision processes.", "questions": "As my understanding of this paper is limited, I hope the authors can provide an intuitive example to illustrate why their proposed symmetry class is better than the Other-Play algorithm [1].\n\n[1] Hu, Hengyuan, et al. \"“other-play” for zero-shot coordination.\" International Conference on Machine Learning. PMLR, 2020.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The organization of this paper is well-structured.\n2. The paper conducts experiments in several zero-shot coordination tasks and gives comprehensive analysis.", "weaknesses": "As I'm not familiar with this field, it is hard for me to give constructive suggestions to the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Sbx4YzYjxP", "reviewer": "Reviewer_zi1H", "summary": "This work explores *symmetry in expected returns* as an inductive bias for training agents that are more capable of zero-shot coordination.", "questions": "- What are the key limitations of this approach?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The writing is clear, concise, and detailed.\n- The approach is well-motivated theoretically, and seemingly well-grounded in prior literature.\n- Discussion of prior work appears complete. \n- The experiments are compelling, and validate the claims made in the paper.\n- Future directions are compelling. \n- Work is likely to be of interest to the broader field.", "weaknesses": "- Limitations are not adequately addressed. I would suggested addressing this explicitly in the conclusion, between the summary and discussion of future directions. \n- Readability:\n\t- Figure 2 graph text is far too small.\n\t- What purpose do the black horizontal bars at the top and bottom of Figure 1's image serve? Seems the text would fit much better without these.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TappktCUKD", "reviewer": "Reviewer_GMBG", "summary": "This paper extends the concept of Dec-POMDP symmetry to Expected Return (ER) symmetry for the Other-Play (OP) objective. ER symmetry captures broader classes of symmetry-breaking by preserving the expected return of self-play optimal policies instead of the state, action, and observation spaces, thus increasing diversity within equivalence classes at the cost of some optimality. The authors introduce novel algorithms to discover ER symmetries and validate their effectiveness across three MARL environments with independent agents, demonstrating improvement in terms of zero-shot coordination compared to existing symmetry discovery methods.", "questions": "1. Please address the questions raised in the weakness section, regarding experiments on more complex environments and comparison with SOTA MARL baselines.\n2. In the caption of Figure 2, the mean SP score for the baseline population is listed as “162.33 ± 0.14,” while the graph displays a mean of 6.74. Is this a typo? I'd suggest the authors to thoroughly check all results presented in the paper.\n3. The evaluation of group properties reveals a high relative reconstruction loss (18.4%), does this violation of a group's property of closure under composition impact the performance of symmetry discovery and MARL performance greatly?\n4. For real-world applications, could you elaborate on the interpretability of ER symmetries? Would it be feasible to construct more intuitive symmetry structures based on those discovered by your model, and how does this compare to the interpretability of Dec-POMDP symmetry?\n5. Regarding Equation 9, how large is the deviation from optimality in practice? Specifically, what is the gap between Equation 9 and Equation 10 in your experimental results? Are these deviations minor enough to be negligible?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The introduction of ER symmetry seems to be a new contribution, extending the symmetry-breaking methods beyond simple action and observation relabeling.\n+ The use of various toy examples throughout the paper makes the key definitions and concepts easy to understand. \n+ The proposed approach is solid, and its effectiveness is underpinned by the with well-defined constructions of equivalence classes.", "weaknesses": "- Despite the use of the toy examples and the effort by the authors, I feel the writing could be further improved for readability. Some sections are still a bit challenging to follow. \n- The experiments largely focus on the Hanabi environment, while the results on overcook and cat/dog environments are very brief. More  complex environments, especially those with continuous action and state spaces, should be used to demonstrate the effectiveness and scalability of the ER symmetry method, which unfortunately remain unclear.\n- For Hanabi, the comparisons are limited to self-play and cross-play using IPPO. How do the proposed methods compare with (i) self- or cross-play using other RL algorithms, (ii) SOTA MARL baselines in Hanabi that do not necessarily employ self- or cross-play? I'm mostly interested in seeing how the proposed algorithms compare with SOTA MARL algorithms out there.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KDAQI412Wx", "reviewer": "Reviewer_4GFs", "summary": "The paper generalizes the existing OP method to a more general symmetry group. They further define the group of expected return symmetries, and propose a novel method to learn expected return symmetries. The performance of the propose method significantly outperforms Dec-POMDP symmetries.", "questions": "See the weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The introduction of expected return symmetries is novel, which is better suited for OP than Dec-POMDP symmetries. The proposed method greatly improves zero-shot coordination, significantly outperforming traditional Dec-POMDP symmetries. Moreover, expected return symmetries can be effectively applied in environments where agents act simultaneously.", "weaknesses": "1. The structure of the proposed expected return symmetries is quite similar to the state value funtion that evaluates the future expexted returns. It can be easily affected by the policies of other agents. In multi-agent settings, how the proposed method deals with non-stationary issue during self-play and cross play.\n2. The authors argue that the optimal policies learned independently by an agent may not be compatible with other agents' policies during test time. It is not very clear that how the proposed method enhances the compatibility. How self-play optimal policies can differ significantly in coordination strategies.\n3. The limitations of the proposed expected return symmetries should be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)