Paper deep dive
On Symmetry for Characterizing Agent Heterogeneity in Multi-Agent Systems
Jianhong Wang, Jonathan Lawry
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Understanding agent heterogeneity can inform the design of shared and agent-specific policy representations, however existing criteria provide no unified structural test. We study finite-horizon POSGs and define a type-compatible transformation as a policy-evaluation symmetry when complete policy evaluation commutes with it for every decentralized behavioral policy. Policy-evaluation symmetries form a group for which agent orbits define structural agent types. This classification does not depend on the particular policy chosen or the distribution of initial states. We prove that every componentwise environment automorphism is a policy-evaluation symmetry, but that the converse does not hold. Applying the framework to cooperative Dec-POMDPs shows that agents can belong to different structural types even when they share a common reward. For prescribed weighted reward aggregation, we derive an exact value identity and sufficient conditions for the resulting Dec-POMDP to inherit the policy-evaluation symmetries of the source POSG. Finally, we give sufficient conditions under which repeated model factorizations induce policy-evaluation symmetry, and show that preserving an optimal Boltzmann policy set neither implies nor follows from this symmetry in general.
Tags
Links
- Source: https://arxiv.org/abs/2610.18538v1
- Canonical: https://arxiv.org/abs/2610.18538v1
Trouble viewing inline? Open PDF directly →
Full Text
176,179 characters extracted from source content.
Expand or collapse full text
On Symmetry for Characterizing Agent Heterogeneity in Multi-Agent Systems Jianhong Wang†‡, Jonathan Lawry‡ Affiliation: †INFORMED-AI Hub, University of Bristol ‡School of Engineering Mathematics and Technology, University of Bristol , Bristol, United Kingdom email: jianhong.wang, J.Lawry@bristol.ac.uk © none Abstract. Understanding agent heterogeneity can inform the design of shared and agent-specific policy representations, however existing criteria provide no unified structural test. We study finite-horizon POSGs and define a type-compatible transformation as a policy-evaluation symmetry when complete policy evaluation commutes with it for every decentralized behavioral policy. Policy-evaluation symmetries form a group for which agent orbits define structural agent types. This classification does not depend on the particular policy chosen or the distribution of initial states. We prove that every componentwise environment automorphism is a policy-evaluation symmetry, but that the converse does not hold. Applying the framework to cooperative Dec-POMDPs shows that agents can belong to different structural types even when they share a common reward. For prescribed weighted reward aggregation, we derive an exact value identity and sufficient conditions for the resulting Dec-POMDP to inherit the policy-evaluation symmetries of the source POSG. Finally, we give sufficient conditions under which repeated model factorizations induce policy-evaluation symmetry, and show that preserving an optimal Boltzmann policy set neither implies nor follows from this symmetry in general. Keywords: multi-agent systems, agent heterogeneity, symmetry, POSGs, Dec-POMDPs 1. Introduction Multi-agent systems can describe interacting decision-makers in real-world problems, such as cooperative robot control (Bettini et al., 2023) and voltage regulation in power distribution networks (Wang et al., 2021), where agents’ capabilities, information, objectives, and behavior may differ. As a result, characterizing these differences is necessary, which can inform the design of policy to make decisions. Symmetry identifies transformations that preserve relevant system properties, a principle used across physical and computational sciences. In power-grid swing equations, exchanging generator labels preserves the dynamics when the corresponding generator parameters and network couplings are unchanged (Molnar et al., 2021). In molecular modeling, energy is invariant to rigid rotations, translations, and atom reindexing, properties incorporated into SchNet (Schüt et al., 2017). These examples inspires a possibility to identify corresponding structural regularities in multi-agent systems by symmetries. Multi-agent reinforcement learning (MARL), as a learning framework for multi-agent systems, already exploits symmetry. Distributed policy networks that encode global symmetries empirically improve data efficiency on symmetric cooperative tasks (van der Pol et al., 2022). Other-play uses environment symmetries to reduce dependence on arbitrary conventions in zero-shot coordination (Hu et al., 2020), while expected return symmetries extend the symmetry class used for this purpose (Muglich et al., 2025). However, their focus is task-specific (improving learning and coordination), leaving the connection to structural agent heterogeneity an open question. Broader formal accounts describe component-preserving model automorphisms (Kang and Kim, 2012; Treutlein et al., 2021). Braun et al. (Braun et al., 2022) use counting and isomorphic symmetries for compact partitioned Dec-POMDPs, with agent-number tractability relying on the stronger isomorphic factorization. Complementary work classifies physical and behavioral heterogeneity in multi-robot learning (Bettini et al., 2023), measures behavioral differences through system neural diversity (Bettini et al., 2025), and distinguishes observation, transition, objective, and policy heterogeneity (Hu et al., 2026). These perspectives identify particular model regularities or dimensions of difference, however, they are still with a gap to the chracteristics of multi-agent systems. We therefore ask: can we use symmetries to determine structural agent heterogeneity? Specifically, when can agents be exchanged through compatible transformations without changing how every decentralized policy is evaluated? To answer the above research questions, we ground our theoretical framework in finite-horizon partially observable stochastic games (POSGs). A transformation is a policy-evaluation symmetry if evaluating any transformed policy gives the correspondingly transformed value profile, at every state–joint-history pair. These symmetries form a group whose agent orbits define structural agent types: one orbit means structural homogeneity, and multiple orbits mean structural heterogeneity. For the specified game and admissible transformations, this classification is independent of the selected policy and initial-state distribution. Our contributions are as follows: (1) We establish the policy-evaluation symmetry group and its structural agent types, allowing compatible agent, state, action, and observation transformations. We distinguish policy-evaluation symmetry, which concerns every decentralized policy, from the equivariance of a selected policy. (2) We prove that preserving the transition, observation, and reward functions componentwise guarantees policy-evaluation symmetry, but the reverse is not necessary. A finite two-stage POSG yields a strictly finer componentwise agent partition to show the necessity of the policy-evaluation definition. (3) We show that Dec-POMDPs can remain structurally heterogeneous, although with a common reward. For a derived Dec-POMDP with a prescribed weighted common reward, we derive an exact weighted-value identity and sufficient conditions for inheriting the source game’s symmetries. We further compare the framework with existing heterogeneity categories, counting and isomorphic symmetry, and expected return symmetry, making the assumptions and limitations of each comparison explicit. 2. Related Work 2.1. Taxonomies of Agent Heterogeneity Bettini et al. (Bettini et al., 2023) distinguish physical from behavioral heterogeneity in multi-robot and multi-agent systems. They further separate behavioral heterogeneity according to whether agents share an objective, yielding five physical–behavioral subclasses. This taxonomy is a high-level classification rather than a measure of degree. Their later system neural diversity measure addresses the latter question for behavior by averaging pairwise behavioral distances (Bettini et al., 2025). Hu et al. (Hu et al., 2026) give a finer agent-level MARL taxonomy based on observation, response-transition, effect-transition, objective, and policy heterogeneity. Table 1 compares these prior categories and the system neural diversity measure with the closest concepts in our framework. For physical, observation, transition, and objective heterogeneity, the associations are conditional on the relevant agent property being represented in the POSG. Behavioral and policy heterogeneity are instead compared through equivariance of a selected policy relative to chosen policy-evaluation symmetries. Bettini et al.’s five subclasses combine physical and behavioral heterogeneity, with behavioral heterogeneity further distinguished by whether agents share an objective. The table therefore lists these underlying distinctions rather than repeating all five combinations. Table 1. Relation of prior heterogeneity categories and measures to our symmetry-based concepts. Note that these associations are not claims of formal equivalence. Prior category or measure Relation to our framework Physical heterogeneity (Bettini et al., 2023) Physical differences can be tested through a componentwise environment automorphism when their consequences are encoded in the POSG. Observation heterogeneity (Hu et al., 2026) Observation-preservation condition within a componentwise environment automorphism. Response- and effect-transition heterogeneity (Hu et al., 2026) Transition-preservation condition within a componentwise environment automorphism, provided that the required local transition factorization is specified. Objective heterogeneity (Bettini et al., 2023; Hu et al., 2026) Reward-preservation condition within a componentwise environment automorphism. Behavioral or policy heterogeneity (Bettini et al., 2023; Hu et al., 2026) Equivariance of a selected policy characterizes behavioral homogeneity among agents related by the chosen policy-evaluation symmetries, while failure relative to a specified symmetry expresses policy-relative behavioral differentiation. System neural diversity (Bettini et al., 2025) Graded comparison of selected policies that complements the exact classification into structural agent types. These associations locate earlier categories within the symmetry framework, but they do not identify those categories with structural agent types. A componentwise environment automorphism that exchanges two agents guarantees that they have the same structural agent type. However, failure of a componentwise preservation equation for a candidate transformation neither rules out that transformation as a policy-evaluation symmetry nor establishes that the agents have different structural agent types. Likewise, different behavior under one selected policy does not by itself establish different structural agent types. Graded behavioral measures such as system neural diversity (Bettini et al., 2025) are complementary to the structural agent-type partition. Appendix A explains the assumptions and direction of each association in Table 1. 2.2. Symmetry in Multi-Agent Systems Symmetry in normal-form games is commonly expressed through permutations of players and strategies that preserve payoff profiles. Cao and Yang (Cao and Yang, 2018) formalize player and strategy symmetry groups and distinguish ordinary, renaming, and name-irrelevant symmetric games. Koriche et al. (Koriche et al., 2017) distinguish structural symmetry from minimax symmetry in finite-horizon stochastic games. Their semantic notion preserves an optimal minimax value, whereas ours evaluates every decentralized policy in a partially observable game. Tewolde et al. (Tewolde et al., 2025) study the complexity of detecting player and action symmetries in normal-form games, deriving graph-automorphism and graph-isomorphism completeness results, and analyze Nash equilibria that respect given symmetries. These traditions motivate treating agent interchangeability as an orbit question but do not directly address our all-policy setting with type-compatible state, observation, and history transformations. For sequential models, Kang and Kim (Kang and Kim, 2012) study symmetries of POMDPs and POSGs through graph automorphisms that preserve the model components. In cooperative settings, Hu et al. (Hu et al., 2020) call component-preserving transformations equivalence mappings and use them to randomize conventions in other-play. Treutlein et al. (Treutlein et al., 2021) formulate Dec-POMDP isomorphisms and automorphisms using bijections of agents, states, actions, and observations that preserve transitions, observations, rewards, and the initial distribution. These definitions use different model conventions and admissible transformations. After translating them into our setting, their requirements to preserve the transition, observation, and reward functions become instances of the componentwise environment automorphisms studied in Section 5. By Theorem 5.2, these conditions are sufficient, but not necessary, for policy-evaluation symmetry. We instead define policy-evaluation symmetry directly by ℰℳ(g⋅π)=g⋅ℰℳ(π)E_M(g·π)=g·E_M(π) for every decentralized policy π: transforming a policy before evaluation must give the same value profile as evaluating it first and then transforming its values. Other work captures different consequences or representations of symmetry. At the policy-architecture level, van der Pol et al. (van der Pol et al., 2022) factor global cooperative-system symmetries into local transformations and agent permutations to construct distributed equivariant policy networks. This exploits a supplied symmetry in policy learning, whereas our structural agent types are defined before selecting a policy or architecture. At the representation level, Braun et al. (Braun et al., 2022) use counting and isomorphic symmetry to obtain compact lifted Dec-POMDP representations. Muglich et al. (Muglich et al., 2025) introduce expected return symmetries, which preserve self-play-optimal Boltzmann-exploratory policies at a fixed temperature for zero-shot coordination. Our structural agent types instead use the orbits of a solution-independent policy-evaluation symmetry group that holds for every decentralized policy. 3. Model and Type-Compatible Transformations We consider a finite-horizon partially observable stochastic game (POSG) (Hansen et al., 2004), as follows: ℳ=(N,,(i)i,(i)i,P,Z,(ri)i,ρ0,T,γ),M= (N,S,(A_i)_i,(O_i)_i,P,Z,(r_i)_i, _0,T,γ ), where N=1,…,nN=\1,…,n\ is the finite nonempty agent set, and S, iA_i, and iO_i are finite and nonempty for every i∈Ni∈ N. Moreover, the finite horizon is T<∞T<∞ and the discount factor is γ∈(0,1]γ∈(0,1]. The transition function is P(s′∣s,a)P(s s,a), the joint observation function is Z(o′∣s′,a)Z(o s ,a), and ri(s,a,s′)r_i(s,a,s ) is agent i’s reward function. At the initial time step t=0t=0, the state is drawn from the initial distribution ρ0 _0, so s0∼ρ0s_0 _0, and every agent has the empty history hi0=()h_i^0=(). For t≥1t≥ 1, the local history of agent i is defined as: hit=(ai0,oi1,…,ait−1,oit)∈ℋit=(i×i)t.h_i^t=(a_i^0,o_i^1,…,a_i^t-1,o_i^t) _i^t=(A_i×O_i)^t. The policy domain contains all decentralized behavioral product policies, such that: Πdec=∏i∈N∏t=0T−1∏hit∈ℋitΔ(i),πt(a∣ht)=∏iπit(ai∣hit). _dec= _i∈ N _t=0^T-1 _h_i^t _i^t (A_i), π^t(a h^t)= _i _i^t(a_i h_i^t). Agents may randomize independently at their local histories, but we exclude a common random signal, such as a shared seed or public correlation device (Aumann, 1974; Bernstein et al., 2009).11 1 Conditioning local policies on the same random draw can produce non-product joint action laws that the factorization above cannot represent, thereby enlarging the admissible policy domain. Because policy-evaluation symmetry quantifies over this domain, admitting correlated policies can change the symmetry group and its induced structural agent types. Let t=×∏iℋitX_t=S× _iH_i^t. Complete policy evaluation assigns a value to every valid state–joint-history pair, including pairs unreachable under a selected policy. With Vi,Tπ≡0V_i,T^π≡ 0, for t<Tt<T it is defined by the following Bellman recursion: Vi,tπ(s,ht)=∑a,s′,o′ V_i,t^π(s,h^t)= _a,s ,o πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) π^t(a h^t)P(s s,a)Z(o s ,a) (1) ⋅[ri(s,a,s′)+γVi,t+1π(s′,ht,a,o′)]. · [r_i(s,a,s )+γ V_i,t+1^π(s ,h^t,a,o ) ]. The final transition reward is therefore included at t=T−1t=T-1. Write ℰℳ:Πdec→,ℰℳ(π)=Vπ,E_M: _dec , _M(π)=V^π, for the operator returning all agents’ values at all time steps and pairs, where V is the space of all function profiles V=(Vi,t)V=(V_i,t), where Vi,t:t→ℝV_i,t:X_t for i∈Ni∈ N and 0≤t≤T0≤ t≤ T, with Vi,T≡0V_i,T≡ 0. Each policy π determines a particular profile Vπ∈V^π through Equation (1). The expected return under the initial distribution is as follows: (2) Ji(π)=s0∼ρ0[Vi,0π(s0,()N)],J_i(π)=E_s_0 _0 [V_i,0^π(s_0,()^N) ], where ()N()^N is the empty joint history. Type-compatible transformations. A type-compatible transformation is a complete tuple g=(σg,ϕg,(ϕg,i)i,(ϕg,i)i),g= ( _g, _g^S,( _g,i^A)_i,( _g,i^O)_i ), where σg _g permutes agents, ϕg _g^S bijects the state space, and ϕg,i:i→σg(i) _g,i^A:A_i _ _g(i) and ϕg,i:i→σg(i) _g,i^O:O_i _ _g(i) are bijections. It acts on joint actions by [g⋅a]σg(i)=ϕg,i(ai)[ g· a]_ _g(i)= _g,i^A(a_i), and analogously on joint observations. For t≥1t≥ 1, the induced local-history map Φg,iℋ,t:ℋit→ℋσg(i)t _g,i^H,t:H_i^t _ _g(i)^t is expressed as follows: Φg,iℋ,t(ai0,oi1,…,ait−1,oit) _g,i^H,t(a_i^0,o_i^1,…,a_i^t-1,o_i^t) =(ϕg,i(ai0),ϕg,i(oi1),…,ϕg,i(ait−1),ϕg,i(oit)), = ( _g,i^A(a_i^0), _g,i^O(o_i^1),…, _g,i^A(a_i^t-1), _g,i^O(o_i^t) ), and Φg,iℋ,0(())=() _g,i^H,0(())=(). For a joint history ht=(hit)i∈Nh^t=(h_i^t)_i∈ N, define [g⋅ht]σg(i)=Φg,iℋ,t(hit).[g· h^t]_ _g(i)= _g,i^H,t(h_i^t). Thus agent i’s transformed local history occupies coordinate σg(i) _g(i) in the joint history. The induced state–joint-history map is τgt:t→t,τgt(s,ht)=(ϕg(s),g⋅ht). _g^t:X_t _t, _g^t(s,h^t)= ( _g^S(s),g· h^t ). Thus τgt _g^t transforms the state and joint history. It preserves the time index22 2 The time sequence is not changed, e.g., a time sequence (t1,t2,t3)(t_1,t_2,t_3) would still be (t1,t2,t3)(t_1,t_2,t_3) after the transformation. and does not perform a state transition to generate the next state. In particular, for the empty joint history ()N()^N, τg0(s,()N)=(ϕg(s),()N) _g^0(s,()^N)=( _g^S(s),()^N). We fix an application-specified subgroup ℛadm(ℳ)R_adm(M) of complete type-compatible transformations arising from representation structure fixed for the application. Examples include permutations of an entity-factored multi-agent representation (Hao et al., 2023), node relabelings of a graph-structured representation (Keriven and Peyré, 2019), or geometric state–action transformations such as rotations and reflections (van der Pol et al., 2020). Membership in ℛadm(ℳ)R_adm(M) supplies a candidate transformation; an environment or policy-evaluation symmetry must also satisfy the corresponding preservation conditions. The induced transformations of policies and values are specified pointwise by the following equations: (3) (g⋅π)σg(i)t(ϕg,i(ai)∣Φg,iℋ,t(hit)) (g·π)_ _g(i)^t ( _g,i^A(a_i) _g,i^H,t(h_i^t) ) =πit(ai∣hit), = _i^t(a_i h_i^t), (4) (g⋅V)σg(i),t(τgtxt) (g· V)_ _g(i),t( _g^tx_t) =Vi,t(xt). =V_i,t(x_t). These transformations define left group actions. At each fixed joint history, the transformed joint action distribution equals the product of the transformed local distributions. Because the induced policy transformation only relabels and reindexes the local policies, g⋅πg·π remains a decentralized product policy in Πdec _dec. Appendix B proves these action properties together with the subgroup and orbit facts used in the following sections. 4. Policy-Evaluation Symmetry and Structural Agent Types Definition 4.1 (Policy-evaluation symmetry). An admissible transformation g∈ℛadm(ℳ)g _adm(M) is a policy-evaluation symmetry if ℰℳ(g⋅π)=g⋅ℰℳ(π)for every π∈Πdec.E_M(g·π)=g·E_M(π) every π∈ _dec. Equivalently, Vσg(i),tg⋅π(τgtxt)=Vi,tπ(xt)V_ _g(i),t^g·π( _g^tx_t)=V_i,t^π(x_t) for every policy, agent, time step, and xt∈tx_t _t. The set of all such transformations is denoted GℳevalG_M^eval. For a normal-form game embedded as a one-stage POSG, this definition reduces to payoff preservation under admissible player and action relabelings (see Proposition B.4). The requirement that the identity hold for every policy π∈Πdecπ∈ _dec is essential. The definition says that transforming any policy and then evaluating it gives the correspondingly transformed complete value profile. It does not require VπV^π to be invariant under g, because in general the comparison is between π and g⋅πg·π. The group-action laws imply that Gℳeval≤ℛadm(ℳ)G_M^eval _adm(M). Definition 4.2 (Structural agent type). Agents i,j∈Ni,j∈ N have the same structural agent type when i∼evalj⟺some g∈Gℳeval satisfies σg(i)=j.i _evalj g∈ G_M^eval satisfies _g(i)=j. The structural partition is the orbit partition eval(ℳ)=(Gℳeval)=σg(i):g∈Gℳeval:i∈N.P_eval(M)=P(G_M^eval)= \\ _g(i):g∈ G_M^eval\:i∈ N \. Writing eval(ℳ)=T1,…,TmP_eval(M)=\T_1,…,T_m\, each TkT_k is one structural agent type. The multi-agent system is structurally homogeneous if m=1m=1 and structurally heterogeneous if m>1m>1. Heterogeneity therefore describes the complete partition, rather than one particular type. Because GℳevalG_M^eval acts on N through the agent maps i↦σg(i)i _g(i), ∼eval _eval is the standard orbit equivalence relation (Judson and Beezer, 1994, Chap. 14.1).33 3 Specifically, e∈Gℳevale∈ G_M^eval satisfies σe(i)=i _e(i)=i, giving reflexivity. If g∈Gℳevalg∈ G_M^eval maps i to j, then g−1∈Gℳevalg^-1∈ G_M^eval maps j to i, giving symmetry. If g,k∈Gℳevalg,k∈ G_M^eval map i to j and j to ℓ , respectively, then kg∈Gℳevalkg∈ G_M^eval and σkg(i)=σk(σg(i))=ℓ _kg(i)= _k( _g(i))= , giving transitivity. Mathematically, the case m=1m=1 means that the action of GℳevalG_M^eval on N is transitive: for every pair of agents i,j∈Ni,j∈ N, some g∈Gℳevalg∈ G_M^eval satisfies σg(i)=j _g(i)=j. To obtain an equivariance relation for expected returns Ji(π)J_i(π) under the initial distribution, we additionally require the state transformation to preserve ρ0 _0. We therefore define the subgroup, as follows: Gℳeval,ρ0=g∈Gℳeval:ρ0(ϕg(s))=ρ0(s) for every s∈,G_M^eval, _0= \g∈ G_M^eval: _0 ( _g^S(s) )= _0(s) for every s \, where the state transformation must preserve the initial distribution. Therefore, every g∈Gℳeval,ρ0g∈ G_M^eval, _0 satisfies the following equation: Jσg(i)(g⋅π)=Ji(π).J_ _g(i)(g·π)=J_i(π). Policy equivariance is downstream. For an arbitrary subgroup H≤GℳevalH≤ G_M^eval, we call a selected joint policy H-equivariant when g⋅π=πg·π=π, for every g∈Hg∈ H. Pointwise, this is represented by the following equation: πσg(i)t(ϕg,i(ai)∣Φg,iℋ,t(hit))=πit(ai∣hit). _ _g(i)^t ( _g,i^A(a_i) _g,i^H,t(h_i^t) )= _i^t(a_i h_i^t). For every g∈Hg∈ H, policy-evaluation symmetry gives g⋅Vπ=Vg⋅πg· V^π=V^g·π. If the selected policy is H-equivariant, then g⋅π=πg·π=π, so its value profile is also unchanged: g⋅Vπ=Vg⋅π=Vπ.g· V^π=V^g·π=V^π. The reverse implication need not hold. The equality g⋅Vπ=Vπg· V^π=V^π for one selected policy does not imply that g⋅π=πg·π=π, nor does it establish the following identity for every policy: Vg⋅η=g⋅Vηfor every η∈Πdec,V^g·η=g· V^η every η∈ _dec, as required for g to be a policy-evaluation symmetry. 5. Componentwise Environment Automorphisms Componentwise primitive-preserving transformations,44 4 Agent-index conventions differ: the POSG automorphisms of Kang and Kim (2012) and Dec-POMDP automorphisms of Treutlein et al. (2021) include an agent bijection; the equivalence mappings of Hu et al. (2020) and transformation group of Muglich et al. (2025) fix agent indices. Our type-compatible transformations permit agent permutations, following the former convention. such as transformations that separately preserve the transition, observation, and reward functions, appear as POSG automorphisms or symmetries (Kang and Kim, 2012), Dec-POMDP equivalence mappings (Hu et al., 2020), Dec-POMDP automorphisms (Treutlein et al., 2021), and environment symmetries (Muglich et al., 2025). We use the name componentwise environment automorphism for this notion in POSGs, emphasizing its contrast with policy-evaluation symmetry. Unlike the Dec-POMDP automorphisms of Treutlein et al. (2021), preservation of the initial distribution is imposed separately in our framework, as we introduced in Section 4. Definition 5.1 (Componentwise environment automorphism (Kang and Kim, 2012)). An admissible transformation g is a componentwise environment automorphism when, for every well-typed s,s′,a,o′s,s ,a,o , and i, (5) P(ϕg(s′)∣ϕg(s),g⋅a) P( _g^S(s ) _g^S(s),g· a) =P(s′∣s,a), =P(s s,a), (6) Z(g⋅o′∣ϕg(s′),g⋅a) Z(g· o _g^S(s ),g· a) =Z(o′∣s′,a), =Z(o s ,a), (7) rσg(i)(ϕg(s),g⋅a,ϕg(s′)) r_ _g(i)( _g^S(s),g· a, _g^S(s )) =ri(s,a,s′). =r_i(s,a,s ). Write Autenv(ℳ)Aut_env(M) for the set of componentwise environment automorphisms. Theorem 5.2 (Componentwise environment automorphisms are sufficient). The componentwise environment automorphisms form a subgroup and Autenv(ℳ)≤Gℳeval,(Autenv(ℳ))⪯eval(ℳ),Aut_env(M)≤ G_M^eval, (Aut_env(M)) _eval(M), where ⪯ means finer than or equal to. Proof sketch. The identity transformation preserves all three environment components. If two transformations preserve them, applying the preservation equations successively shows that their composition also preserves them. Substituting inverse images into the same equations shows that each inverse preserves them. Hence Autenv(ℳ)Aut_env(M) is a subgroup. It remains to prove the inclusion in GℳevalG_M^eval. At t=Tt=T, both values in Definition 4.1 are zero. Assume their equality at time step t+1t+1, and expand the transformed Bellman recursion at time step t. Make the bijective substitutions b=g⋅a,s¯′=ϕg(s′),o¯′=g⋅o′.b=g· a, s = _g^S(s ), o =g· o . The policy-transformation rule in Equation (3) matches the transformed joint-action probability with the source probability. Equations (5)–(7) replace the transition, observation, and reward terms with their source counterparts. The history transformation identifies corresponding next state–joint-history pairs. The induction hypothesis then equates their values at time step t+1t+1 under the transformed and source policies. The transformed Bellman sum therefore reduces to Equation (1). Consequently, Vσg(i),tg⋅π(τgtxt)=Vi,tπ(xt)V_ _g(i),t^g·π( _g^tx_t)=V_i,t^π(x_t) for every g∈Autenv(ℳ)g _env(M), policy π, agent i, time step t, and xt∈tx_t _t. Thus, every componentwise environment automorphism is a policy-evaluation symmetry, proving Autenv(ℳ)≤GℳevalAut_env(M)≤ G_M^eval. The subgroup inclusion also gives the partition refinement, as follows: (Autenv(ℳ))⪯eval(ℳ),P(Aut_env(M)) _eval(M), because every orbit under Autenv(ℳ)Aut_env(M) is contained in an orbit under GℳevalG_M^eval. Appendix C gives the complete proof of Theorem 5.2. The inclusion can yield a strict refinement, as follows: Proposition 5.3 (Strictness of the componentwise sufficient condition). There exists a finite, full-support, two-agent, two-stage POSG for which Autenv(ℳ)⪇Gℳevaland(Autenv(ℳ))≺eval(ℳ).Aut_env(M) G_M^eval (Aut_env(M)) _eval(M). Here ≺ means strictly finer than. Proof sketch. Appendix B.2 constructs a full-support two-stage POSG in which exchanging the agents changes the transition distribution associated with some joint actions. The exchange is therefore not a componentwise environment automorphism. Nevertheless, the affected transition distributions produce the same expected successor-state reward and marginalized next-observation distribution. The Bellman recursion preserves complete policy evaluation under the exchange for every decentralized policy. The reward construction also rules out every alternative componentwise transformation that exchanges the agents. Hence, the componentwise partition separates the agents, whereas the policy-evaluation partition places them in one structural agent type. Componentwise environment automorphisms are a subgroup of policy-evaluation symmetries, which are a subgroup of admissible transformations. Agent orbits under policy-evaluation symmetry define structural types. A schematic example shows three componentwise parts and two structural types, with non-singleton parts in both partitions. The componentwise partition can be finer. Separate conditions on the initial distribution and selected policy yield expected-return equivariance and selected value-profile invariance, respectively. A full-width third panel summarizes the cooperative extensions. A common-reward model may still have several structural agent types. Weighted reward aggregation gives a weighted-value identity. Equal weights within each original structural type preserve all original policy-evaluation symmetries, so structural types are preserved or merged. Without this weight condition, no universal partition ordering is guaranteed. Figure 1. Hierarchy of key concepts and results. ≤ denotes subgroup inclusion. ⪯ means finer than or equal to. The schematic inset illustrates orbit refinement: each componentwise orbit lies within one structural agent type. Initial-distribution preservation and selected-policy equivariance impose separate conditions for expected-return equivariance and invariance of a selected value profile. Panel (c) shows that a common reward need not imply structural homogeneity. For the derived common-reward model, equal weights within each original structural type guarantee symmetry inheritance, so types are preserved or merged.Componentwise environment automorphisms are a subgroup of policy-evaluation symmetries, which are a subgroup of admissible transformations. Agent orbits under policy-evaluation symmetry define structural types. A schematic example shows three componentwise parts and two structural types, with non-singleton parts in both partitions. The componentwise partition can be finer. Separate conditions on the initial distribution and selected policy yield expected-return equivariance and selected value-profile invariance, respectively. A full-width third panel summarizes the cooperative extensions. A common-reward model may still have several structural agent types. Weighted reward aggregation gives a weighted-value identity. Equal weights within each original structural type preserve all original policy-evaluation symmetries, so structural types are preserved or merged. Without this weight condition, no universal partition ordering is guaranteed. 6. Extension to Dec-POMDPs We apply the policy-evaluation symmetry and orbit framework to two settings of Dec-POMDP (Bernstein et al., 2002). The first is a Dec-POMDP with a general common reward. The second is a derived Dec-POMDP formed by aggregating the individual rewards of a POSG. 6.1. General Common Rewards A finite-horizon POSG specializes to a Dec-POMDP when all agents share one reward function, ri=rcomr_i=r^com for every i∈Ni∈ N. The common terminal condition and Bellman recursion then imply that Vi,tπ(x)=Vj,tπ(x)for every i,j,π,t, and x∈t.V_i,t^π(x)=V_j,t^π(x) every i,j,π,t, and x _t. This equality compares the agents’ value coordinates under the same policy and at the same state–joint-history input. However, it does not show that their decision-making roles are interchangeable. By Definition 4.2, agents i and j have the same structural agent type only if some g∈Gℳevalg∈ G_M^eval maps i to j. Such a transformation must include compatible bijections between the agents’ action and observation spaces and must preserve complete policy evaluation for every decentralized policy after exchanging the agents. A common reward alone guarantees neither these bijections nor symmetry of the transition and observation distributions. For example, in a one-stage binary-action model with the common reward r(a1,a2)=a1r(a_1,a_2)=a_1, both agents receive the same payoff, but exchanging them changes which agent’s policy determines that payoff. The detailed proof of the above statement is given in Proposition D.1 in Appendix D. Hence, a Dec-POMDP may still have multiple structural agent types despite the common reward, and it is structurally homogeneous exactly when GℳevalG_M^eval acts transitively on the agent set N. 6.2. Aggregate Common Rewards Let ℳM be a POSG with agent-specific reward functions (ri)i∈N(r_i)_i∈ N. Fix nonnegative weights w∈ℝ≥0N∖0w _≥ 0^N \0\ and define the aggregate common reward, as follows: rw(s,a,s′)=∑i∈Nwiri(s,a,s′).r^w(s,a,s )= _i∈ Nw_ir_i(s,a,s ). Here rwr^w is only a scalar function constructed from the rewards of ℳM, so defining it does not replace the source reward functions in ℳM. We construct another Dec-POMDP ℳwM_w by retaining the agents, state, action, and observation spaces, transition and observation distributions, initial distribution, horizon, discount factor, and policy domain of ℳM, while assigning rwr^w to every agent: rjℳw=rwfor every j∈N.r_j^M_w=r^w every j∈ N. Thus, ℳM and ℳwM_w differ only in their reward specifications. We test both models using the same declared admissible transformations, so any difference between their symmetry groups comes from replacing the individual rewards with the common reward rwr^w, rather than from allowing different candidate transformations. Theorem 6.1 (Weighted aggregation and inherited symmetry). For every agent j, policy π, time step t, and x∈tx _t, Vj,tπ;ℳw(x)=∑i∈NwiVi,tπ;ℳ(x).V_j,t^π;M_w(x)= _i∈ Nw_iV_i,t^π;M(x). Moreover, g∈Gℳeval:wσg(i)=wifor all i≤Gℳweval. \g∈ G_M^eval:w_ _g(i)=w_i\ for all i \≤ G_M_w^eval. At the componentwise level, g∈Autenv(ℳ):wσg(i)=wifor all i≤Autenv(ℳw). \g _env(M):w_ _g(i)=w_i\ for all i \ _env(M_w). Proof sketch. At t=Tt=T, both sides of the value identity are zero. Suppose the identity holds at t+1t+1. For x=(s,ht)x=(s,h^t), write x′x for the successor state–joint-history input determined by s′,a,o′s ,a,o . Substituting the definition of rwr^w and the induction hypothesis into the Bellman recursion of ℳwM_w gives Vj,tπ;ℳw(x) V_j,t^π;M_w(x) =∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) = _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅∑i∈Nwi[ri(s,a,s′)+γVi,t+1π;ℳ(x′)]=∑i∈NwiVi,tπ;ℳ(x). · _i∈ Nw_i [r_i(s,a,s )+γ V_i,t+1^π;M(x ) ]= _i∈ Nw_iV_i,t^π;M(x). The last equality moves the finite weighted sum outside. Each remaining term is the Bellman recursion for agent i in ℳM. Backward induction therefore proves that Vj,tπ;ℳw(x)=∑i∈NwiVi,tπ;ℳ(x)V_j,t^π;M_w(x)= _i∈ Nw_iV_i,t^π;M(x). For the symmetry inclusion, let g∈Gℳevalg∈ G_M^eval and suppose wσg(i)=wiw_ _g(i)=w_i for every i. Apply the value identity above to policy g⋅πg·π and input τgtx _g^tx. Reindexing by k=σg(i)k= _g(i) and using weight preservation and policy-evaluation symmetry in ℳM then gives: Vσg(j),tg⋅π;ℳw(τgtx) V_ _g(j),t^g·π;M_w( _g^tx) =∑i∈Nwσg(i)Vσg(i),tg⋅π;ℳ(τgtx) = _i∈ Nw_ _g(i)V_ _g(i),t^g·π;M( _g^tx) =∑i∈NwiVi,tπ;ℳ(x)=Vj,tπ;ℳw(x). = _i∈ Nw_iV_i,t^π;M(x)=V_j,t^π;M_w(x). Because this holds for every policy, agent, time step, and evaluation input, we get g∈Gℳwevalg∈ G_M_w^eval. For the componentwise inclusion, let a weight-preserving g∈Autenv(ℳ)g _env(M) be given. It preserves the transition and observation distributions copied to ℳwM_w. Reindexing the aggregate reward and using reward preservation gives the equations, as follows: rw(ϕg(s),g⋅a,ϕg(s′)) r^w( _g^S(s),g· a, _g^S(s )) =∑i∈Nwσg(i)rσg(i)(ϕg(s),g⋅a,ϕg(s′)) = _i∈ Nw_ _g(i)r_ _g(i)( _g^S(s),g· a, _g^S(s )) =∑i∈Nwiri(s,a,s′)=rw(s,a,s′), = _i∈ Nw_ir_i(s,a,s )=r^w(s,a,s ), which proves g∈Autenv(ℳw)g _env(M_w). Appendix D gives the complete proof of Theorem 6.1. Equality of weights within structural agent types. Theorem 6.1 gives wσg(i)=wiw_ _g(i)=w_i for every i∈Ni∈ N as a sufficient condition for a policy-evaluation symmetry g of ℳM to be inherited by ℳwM_w. Requiring this condition for every g∈Gℳevalg∈ G_M^eval is equivalent to assigning equal weights to agents in the same structural agent type. It does not require equal weights across different types, so all agents must have equal weights only when ℳM is structurally homogeneous. If wi=wjw_i=w_j for agents i and j of the same structural type in ℳM, every policy-evaluation symmetry of ℳM is inherited by ℳwM_w, so Gℳeval≤GℳwevalG_M^eval≤ G_M_w^eval. Consequently, we get the following partition refinement: (Gℳeval)⪯(Gℳweval).P(G_M^eval) (G_M_w^eval). Because ⪯ means finer than or equal to, every structural agent type of ℳM is contained in a structural agent type of ℳwM_w. Thus, the aggregate common reward cannot separate agents that share a type in ℳM. Rather, it can only preserve that type or merge it with other types. Under this condition, ℳwM_w has no more structural agent types than ℳM. Thus, if ℳM is structurally homogeneous, then ℳwM_w remains structurally homogeneous. If some agents i and j belonging to the same structural agent type in ℳM receive different weights, Theorem 6.1 no longer guarantees that a policy-evaluation symmetry of ℳM mapping i to j remains for ℳwM_w. If no policy-evaluation symmetry of ℳwM_w maps i to j, then these agents belong to different structural agent types in ℳwM_w. Case 1 in the proof of Proposition D.3 in Appendix D provides a two-agent example of this splitting. Conversely, reward aggregation can turn a type-compatible transformation g that is not a policy-evaluation symmetry of ℳM into one of ℳwM_w. Its agent permutation σg _g may then map agents belonging to different structural agent types in ℳM into the same structural agent type in ℳwM_w. The two-agent examples in Cases 2 and 3 of the proof of Proposition D.3 demonstrate this merging with equal and unequal weights, respectively. Therefore, equality of weights within every structural agent type in ℳM guarantees that (Gℳeval)⪯(Gℳweval).P(G_M^eval) (G_M_w^eval). Across unrestricted weight assignments, however, there is no universal refinement relation between these two partitions. Consequences under the initial distribution. Because the two models share the same initial distribution, substituting the value identity from Theorem 6.1 into the definition of expected return under the initial distribution in Equation (2) gives the following identity without any symmetry assumption (see Proposition D.2): Jjℳw(π)=∑i∈NwiJiℳ(π).J_j^M_w(π)= _i∈ Nw_iJ_i^M(π). Let g∈Gℳevalg∈ G_M^eval preserve the weights. Theorem 6.1 ensures that g∈Gℳwevalg∈ G_M_w^eval. If g also preserves the initial distribution, Proposition D.2 gives the following expected-return identity: Jσg(j)ℳw(g⋅π)=Jjℳw(π)for every j∈N.J_ _g(j)^M_w(g·π)=J_j^M_w(π) every j∈ N. Figure 1 summarizes the hierarchy of key concepts and results introduced from Section 4 to Section 6. 7. Comparisons to Prior Symmetry Frameworks We compare two prior frameworks with policy-evaluation symmetry, the details of which are given in Appendix E. Counting and Isomorphic Symmetry. In Braun et al. (2022)’s partitioned Dec-POMDP framework, isomorphic symmetry uses identical factor templates for agents in each partition part. Under the grounding assumptions in Section E.1.1, exchanging agents within a part together with their action and observation assignments preserves the counts in that part and only reorders equal factor instances. The grounded transition, common-reward, and observation functions are therefore unchanged, which gives counting symmetry. When these exchanges are represented by the admissible typed embedding specified there, they are componentwise environment automorphisms and hence policy-evaluation symmetries. The lifted partition therefore refines the structural agent partition. However, the two-agent coordination example we showed in Appendix E.1.1 has counting and policy-evaluation symmetry but lacks the stated repeated additive reward factorization for the same partition with one part. Policy-evaluation symmetry alone does not guarantee this repeated additive factorization. Applying Braun et al. (2022)’s compact-representation and agent-number tractability results requires their additional factorization and computational assumptions. Expected Return Symmetry. An expected return symmetry (ERS) preserves the self-play-optimal Boltzmann policy set at a fixed positive temperature (Muglich et al., 2025), whereas policy-evaluation symmetry preserves complete evaluation for every decentralized policy. On the shared finite-horizon Dec-POMDP subclass and common admissible transformations, Proposition E.3 establishes that neither ERS nor initial-distribution-preserving policy-evaluation symmetry implies the other in general. The two non-implications are established using different models. For a particular model, the two symmetry sets may coincide or one may contain the other. Section E.2.1 presents the two counterexamples as evidence for these non-implications and states the additional local action-value condition linking the notions. ERS fixes agent indices, so it does not relate distinct agents or replace the structural agent types defined by our agent orbits. 8. Discussions and Framework Boundaries Why does the initial distribution matter? The initial distribution specifies how possible starting states are weighted when an episode begins. It is therefore part of standard POSG and Dec-POMDP formulations (Bernstein et al., 2002; Hansen et al., 2004). A related separation appears in PlaNet’s latent state-space model, which distinguishes an initial latent state from the transition, observation, and reward models used to generate a rollout (Hafner et al., 2019). Structural causal models offer a useful motivation: their structural equations describe transition functions, while a distribution over exogenous variables of structural equations represent background factors that imply substantive characteristics affecting behavior (Pearl, ). Here, the initial distribution is corresponding to the exogenous distribution. Our framework therefore separates policy evaluation conditioned on a state–joint-history input from the initial distribution. Policy-evaluation symmetry compares values at every corresponding state–joint-history pair and therefore does not necessarily require preservation of ρ0 _0. For any g∈Gℳevalg∈ G_M^eval, changing variables in the initial-state sum gives the following relation: Jσg(i)(g⋅π)=∑s∈ρ0(ϕg(s))Vi,0π(s,()N).J_ _g(i)(g·π)= _s _0 ( _g^S(s) )V_i,0^π(s,()^N). Thus, the return-equivariance identity under the initial distribution holds for the fixed ρ0 _0 when g∈Gℳeval,ρ0g∈ G_M^eval, _0. Why go beyond componentwise environment automorphisms? Componentwise symmetries have concrete uses. Graph automorphisms of POMDPs and POSGs support model reduction (Kang and Kim, 2012), Dec-POMDP equivalence mappings support other-play across conventions (Hu et al., 2020), and Dec-POMDP automorphisms formalize transformations relevant to zero-shot coordination (Treutlein et al., 2021). These approaches preserve the transition, observation, and reward functions separately. The resulting componentwise environment automorphisms provide directly checkable sufficient conditions for policy-evaluation symmetry, but these conditions need not be necessary. Proposition 5.3 gives the concrete separation. Its agent transformation changes some entries of the transition distribution, so it fails the componentwise test. The changed distributions nevertheless have the same expected successor-state reward and marginalized next-observation distribution, which are the quantities used by the Bellman evaluation in that construction. The policy-evaluation identity therefore holds for every decentralized policy. Two agents share a structural agent type if an admissible transformation connects them and preserves policy evaluation for every joint policy, even without preserving each model component. Conversely, componentwise preservation remains an additional, potentially finer diagnostic of where agents differ in the environment representation. Learning mechanisms concern behavioural policies, so it must be considered when talking about agent heterogeneity, which lets us introduce the policy equivariance. For example, exploration noise whose distribution does not respect the action transformation can violate the equivariance of an already equivariant policy. This will not change agent heterogeneity, because policy-evaluation symmetry requires the evaluation identity to hold for every decentralized policy. This makes the agent heterogeneity decided by the evaluation identity independent of the learning mechanism that is applied to obtain the target policies (that geniunely describes the agent heterogeneity). Thus, our policy-evaluation symmetry can capture intrinsic characteristics of an agent to categorize its agent type. Why extend the framework to Dec-POMDPs and aggregate common rewards? Dec-POMDPs are a long-standing model of cooperative sequential decision-making under partial observability, in which decentralized agents optimize a common reward (Bernstein et al., 2002). A common reward removes differences between the agents’ reward functions, but it does not guarantee interchangeable action or observation spaces, or symmetric roles in the transition and observation distributions. Section 6 therefore shows that shared objectives need not imply structural homogeneity. This extension helps connect the objective to physical and environmental perspectives, as deifned by prior work (Bettini et al., 2023), by assessing their structural significance through one policy-evaluation symmetry criterion. Social dilemmas (Dawes, 1980) illustrate how individually rational behavior can lead to collectively inferior outcomes, even when cooperation could benefit every player. This motivates mechanisms that support cooperation, with social welfare (Roughgarden and Tardos, 2002) providing a criterion for evaluating the resulting collective benefits. Social welfare is defined as the sum of individual payoffs, which well matches our definition of the aggregate common reward in Section 6. Theorem 6.1 and its examples show that replacing individual rewards by an aggregate common reward can preserve, remove, or create policy-evaluation symmetries. This provides a novel perspective from structural agent types, in contrast to previous work that identifies game structures (Leibo et al., 2017), to understand the effect of maximizing social welfare to social dilemmas. In cooperative MARL for solving Dec-POMDPs, the centralised training and decentralised execution (CTDE) paradigm (Oliehoek et al., 2011) is proposed to collectively optimize a global value function that approcimates the cumulative common rewards. There are a class of algorithms that proposed to represent the gloabl value function as aggregation of individual values, e.g., VDN uses additive decomposition (Sunehag et al., 2018); SQDDPG and SHAQ use Shapley-based value decompositions (Wang et al., 2020; Wang et al., 2022); and QTRAN learns an additive transformation of the joint action-value function that preserves its optimal actions (Son et al., 2019). As those formulations and the learning paradigm are well aligned with each agent j optimizing Vj,tπ;ℳw(x)=∑i∈NwiVi,tπ;ℳ(x)V_j,t^π;M_w(x)= _i∈ Nw_iV_i,t^π;M(x), Theorem 6.1 motivates a testable hypothesis: do these algorithms implicitly learn structural agent types, which could be an inductive bias for improving cooperation? Why is one connecting symmetry sufficient? We use every element of GℳevalG_M^eval to form orbits: two agents i and j belong to the same structural agent type when some g∈Gℳevalg∈ G_M^eval satisfies σg(i)=j _g(i)=j. For example, let N=1,2,3N=\1,2,3\ and consider the induced agent permutations σg _g that fulfil the cyclic permutation 1↦2↦3↦11 2 3 1. Repeated applications of these permutations can map any agent to any other, so the subgroup it generates acts transitively on N. This subgroup therefore induces the same single-part orbit partition N\N\ as Sym(N)Sym(N), although it contains only three of the six possible agent permutations, as contained in Sym(N)Sym(N). In contrast, a different and much stronger condition is that every agent permutation ξ∈Sym(N)ξ (N) be induced by some g∈Gℳevalg∈ G_M^eval satisfying σg=ξ _g=ξ. This full-permutation condition is the dynamic analogue of name-irrelevant symmetry in normal-form games (Cao and Yang, 2018). It is stronger than structural homogeneity, as we defined in Section 4. As explained after Definition 4.2, structural homogeneity requires only that, for every pair i,j∈Ni,j∈ N, some g∈Gℳevalg∈ G_M^eval satisfies σg(i)=j _g(i)=j. The induced agent-permutation group σg:g∈Gℳeval\ _g:g∈ G_M^eval\ may therefore be a proper subgroup of Sym(N)Sym(N). By the definition of stuctural partition, the structural agent types of Sym(N)Sym(N) may overclaim the exact structural agent types that can be obtained from GℳevalG_M^eval. The above conclusion is important in applications. Suppose the same stochastic model governs sensor disturbances or physical obstacles for symmetric agents. These factors can be described by symmetries not included in GℳevalG_M^eval, and different realized outcomes by those extra symmetries do not by themselves intrinsically change the agent structural types. However, separating stable structures from temporary perturbations, or equivalently, determine a proper subgroup of Sym(N)Sym(N), would require deeper investigation. Framework boundaries. The present framework assumes finite state, action, and observation spaces, a finite horizon, empty initial histories, exact expected-value evaluation, and the complete domain of decentralized behavioral product policies without shared randomness. Its structural types are relative to the specified POSG, the chosen evaluation semantics, and the declared admissible transformation group. Because ℛadm(ℳ)R_adm(M) is declared by the modeller, candidate transformations must be justified independently of the desired heterogeneity conclusion. Restricting this group can refine the structural partition, while enlarging it can coarsen the partition. We provide sufficient conditions and finite examples to clarify the policy-evaluation symmetry and the resulting agent heterogeneity, but no general symmetry-discovery or verification algorithm is introduced. Also, exact orbits given by policy-evaluation symmetries do not measure degrees of heterogeneity. Infinite-horizon models and nonlinear or learned reward aggregation require separate formulations. The weighted construction is a forward result for fixed linear weights. It does not recover individual rewards from a supplied common reward or cover nonlinear aggregation. Policy-evaluation symmetry compares expected values. It can therefore treat two transformations as symmetric even when they induce different distributions over trajectories or returns, provided those differences do not change the expected values. Distributional evaluation (Bellemare et al., 2017) or risk-sensitive evaluation (Chow et al., 2015) may further distinguish such transformations. Finally, our results do not prove the existence of an optimal equivariant policy, or establish representation, evaluation and sample-complexity improvements. All those above boundaries establishes clear routes for further research to improve our framework. Besides, with proper task formalizations, our framework may also inform research on multi-agent world models (Zhang et al., 2025) and large language models (LLMs) (Wu et al., 2023) by separating structural differences between agents. Acknowledgments Jianhong Wang and Jonathan Lawry are supported by the Engineering and Physical Sciences Research Council [Grant Ref: EP/Y028732/1]. References Aumann (1974) R. J. Aumann Subjectivity and correlation in randomized strategies. Journal of mathematical Economics 1 (1), p. 67–96. Cited by: §3. Bellemare et al. (2017) M. G. Bellemare, W. Dabney, and R. Munos A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, D. Precup and Y. W. Teh (Eds.), Proceedings of Machine Learning Research, Vol. 70, p. 449–458. Cited by: §8. Bernstein et al. (2009) D. S. Bernstein, C. Amato, E. A. Hansen, and S. Zilberstein Policy iteration for decentralized control of markov decision processes. J. Artif. Intell. Res. 34, p. 89–132. Cited by: §3. Bernstein et al. (2002) D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein The complexity of decentralized control of markov decision processes. Math. Oper. Res. 27 (4), p. 819–840. Cited by: §6, §8, §8. Bettini et al. (2023) M. Bettini, A. Shankar, and A. Prorok Heterogeneous multi-robot reinforcement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, N. Agmon, B. An, A. Ricci, and W. Yeoh (Eds.), p. 1485–1494. Cited by: §A.1, §A.4, §A.5, §1, §1, §2.1, Table 1, Table 1, Table 1, §8. Bettini et al. (2025) M. Bettini, A. Shankar, and A. Prorok System neural diversity: measuring behavioral heterogeneity in multi-agent learning. J. Mach. Learn. Res. 26, p. 163:1–163:27. Cited by: §A.6, §A.6, §1, §2.1, §2.1, Table 1. Braun et al. (2022) T. Braun, M. Gehrke, F. Lau, and R. Möller Lifting in multi-agent systems under uncertainty. In Uncertainty in Artificial Intelligence, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, UAI 2022, 1-5 August 2022, Eindhoven, The Netherlands, J. Cussens and K. Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 180, p. 233–243. Cited by: §E.1, §1, §2.2, §7. Cao and Yang (2018) Z. Cao and X. Yang Symmetric games revisited. Math. Soc. Sci. 95, p. 9–18. Cited by: §2.2, §8. Chow et al. (2015) Y. Chow, A. Tamar, S. Mannor, and M. Pavone Risk-sensitive and robust decision-making: a cvar optimization approach. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (Eds.), p. 1522–1530. Cited by: §8. Dawes (1980) R. M. Dawes Social dilemmas.. Annual review of psychology. Cited by: §8. Hafner et al. (2019) D. Hafner, T. P. Lillicrap, I. Fischer, R. Villegas, D. Ha, H. Lee, and J. Davidson Learning latent dynamics for planning from pixels. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 2555–2565. Cited by: §8. Hansen et al. (2004) E. A. Hansen, D. S. Bernstein, and S. Zilberstein Dynamic programming for partially observable stochastic games. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29, 2004, San Jose, California, USA, D. L. McGuinness and G. Ferguson (Eds.), p. 709–715. Cited by: §3, §8. Hao et al. (2023) J. Hao, X. Hao, H. Mao, W. Wang, Y. Yang, D. Li, Y. Zheng, and Z. Wang Boosting multiagent reinforcement learning via permutation invariant and permutation equivariant networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, Cited by: §3. Hu et al. (2020) H. Hu, A. Lerer, A. Peysakhovich, and J. N. Foerster "Other-play" for zero-shot coordination. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, Vol. 119, p. 4399–4410. Cited by: §1, §2.2, §5, §8, footnote 4. Hu et al. (2026) T. Hu, Z. Pu, Y. Wang, T. Qiu, M. Chen, and X. Yu Heterogeneity in multi-agent reinforcement learning. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2026, Paphos, Cyprus, May 25-29, 2026, V. Mascardi, J. Thangarajah, C. Amato, and L. A. Dennis (Eds.), p. 2754–2762. Cited by: §A.2, §A.3, §A.4, §A.5, §A.6, §1, §2.1, Table 1, Table 1, Table 1, Table 1. Judson and Beezer (1994) T. W. Judson and R. A. Beezer Abstract algebra: theory and applications. Vol. 20, PWS Publishing Company Boston. Cited by: §B.3, §4. Kang and Kim (2012) B. K. Kang and K. Kim Exploiting symmetries for single- and multi-agent partially observable stochastic domains. Artif. Intell. 182-183, p. 32–57. Cited by: §1, §2.2, Definition 5.1, §5, §8, footnote 4. Keriven and Peyré (2019) N. Keriven and G. Peyré Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, and R. Garnett (Eds.), p. 7090–7099. Cited by: §3. Koriche et al. (2017) F. Koriche, S. Lagrue, É. Piette, and S. Tabary Constraint-based symmetry detection in general game playing. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, C. Sierra (Ed.), p. 280–287. Cited by: §2.2. Leibo et al. (2017) J. Z. Leibo, V. F. Zambaldi, M. Lanctot, J. Marecki, and T. Graepel Multi-agent reinforcement learning in sequential social dilemmas. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, K. Larson, M. Winikoff, S. Das, and E. H. Durfee (Eds.), p. 464–473. Cited by: §8. Molnar et al. (2021) F. Molnar, T. Nishikawa, and A. E. Motter Asymmetry underlies stability in power grids. Nature communications 12 (1), p. 1457. Cited by: §1. Muglich et al. (2025) D. Muglich, J. Forkel, E. van der Pol, and J. N. Foerster Expected return symmetries. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025, Cited by: §E.2, §E.2, §E.2, §1, §2.2, §5, §7, footnote 4. Oliehoek et al. (2011) F. A. Oliehoek, M. T. J. Spaan, and N. Vlassis Optimal and approximate q-value functions for decentralized pomdps. CoRR abs/1111.0062. Cited by: §8. [24] J. Pearl Causal inference in statistics: An overview. Statistics Surveys 3 (none), p. 96 – 146. Cited by: §8. Roughgarden and Tardos (2002) T. Roughgarden and É. Tardos How bad is selfish routing?. J. ACM 49 (2), p. 236–259. Cited by: §8. Schüt et al. (2017) K. Schüt, P. Kindermans, H. E. S. Felix, S. Chmiela, A. Tkatchenko, and K. Müller SchNet: A continuous-filter convolutional neural network for modeling quantum interactions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett (Eds.), p. 991–1001. Cited by: §1. Son et al. (2019) K. Son, D. Kim, W. J. Kang, D. Hostallero, and Y. Yi QTRAN: learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 5887–5896. Cited by: §8. Sunehag et al. (2018) P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. F. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, and T. Graepel Value-decomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, E. André, S. Koenig, M. Dastani, and G. Sukthankar (Eds.), p. 2085–2087. Cited by: §8. Tewolde et al. (2025) E. Tewolde, B. H. Zhang, C. Oesterheld, T. Sandholm, and V. Conitzer Computing game symmetries and equilibria that respect them. In Thirty-Ninth AAAI Conference on Artificial Intelligence, Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence, Fifteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2025, Philadelphia, PA, USA, February 25 - March 4, 2025, T. Walsh, J. Shah, and Z. Kolter (Eds.), p. 14148–14157. Cited by: §2.2. Treutlein et al. (2021) J. Treutlein, M. Dennis, C. Oesterheld, and J. N. Foerster A new formalism, method and open issues for zero-shot coordination. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, M. Meila and T. Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, p. 10413–10423. Cited by: §1, §2.2, §5, §8, footnote 4. van der Pol et al. (2022) E. van der Pol, H. van Hoof, F. A. Oliehoek, and M. Welling Multi-agent MDP homomorphic networks. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, Cited by: §1, §2.2. van der Pol et al. (2020) E. van der Pol, D. E. Worrall, H. van Hoof, F. A. Oliehoek, and M. Welling MDP homomorphic networks: group symmetries in reinforcement learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (Eds.), Cited by: §3. Wang et al. (2021) J. Wang, W. Xu, Y. Gu, W. Song, and T. C. Green Multi-agent reinforcement learning for active voltage control on power distribution networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan (Eds.), p. 3271–3284. Cited by: §1. Wang et al. (2022) J. Wang, Y. Zhang, Y. Gu, and T. Kim SHAQ: incorporating shapley value theory into multi-agent q-learning. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Cited by: §8. Wang et al. (2020) J. Wang, Y. Zhang, T. Kim, and Y. Gu Shapley q-value: A local reward approach to solve global reward games. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, p. 7285–7292. Cited by: §8. Wu et al. (2023) Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, et al. Autogen: enabling next-gen llm applications via multi-agent conversation. arXiv preprint arXiv:2308.08155. Cited by: §8. Zhang et al. (2025) Y. Zhang, C. Bai, B. Zhao, J. Yan, X. Li, and X. Li Decentralized transformers with centralized aggregation are sample-efficient multi-agent world models. Trans. Mach. Learn. Res. 2025. Cited by: §8. Appendix A Detailed Comparison of Heterogeneity Categories Table 1 compares prior categories and measures of agent heterogeneity to different levels of our framework. The two approaches ask different questions. Existing taxonomies primarily identify where agents differ, such as in their physical capabilities, observations, dynamics, objectives, or selected policies. Our framework instead asks whether an admissible transformation can exchange the agents while preserving complete policy evaluation. The correspondences are therefore conditional interpretations rather than equivalences between definitions. The rows concerning physical properties, observations, transitions, and objectives share one logical direction. For agents i,j∈Ni,j∈ N, Theorem 5.2 gives [some g∈Autenv(ℳ) satisfies σg(i)=j]⟹i∼evalj. [some g _env(M) satisfies _g(i)=j ] i _evalj. The converse is false in general by Proposition 5.3. Consequently, componentwise preservation supplies a sufficient test for agents to share a structural agent type, but failure of a componentwise preservation equation for one candidate transformation does not establish that their structural types differ. Another admissible transformation may exchange the same agents. By contrast, if no admissible transformation maps i to j, then no policy-evaluation symmetry can map them, and they necessarily have different structural agent types. A.1. Physical Heterogeneity Bettini et al. (Bettini et al., 2023) describe physical heterogeneity through differences in hardware or physical constraints, such as sensors, actuators, and motion constraints. Our framework can classify such differences only through their representation in the POSG. Different sensors may appear in the observation spaces or observation distribution, different actuators may appear in the action spaces or transition distribution, and motion constraints may appear in the state and transition distribution. If action or observation spaces have different cardinalities, the required typed bijection does not exist. Equal cardinality permits a bijection between differently named spaces, but it does not by itself place the resulting complete transformation in the application-specified admissible group. Thus, the formal comparison concerns the modeled consequences of a physical difference rather than hardware identity itself. A physical property that is not represented in the POSG lies outside the structural classification. A.2. Observation Heterogeneity Hu et al. (Hu et al., 2026) define observation heterogeneity through differences in agents’ observation spaces or local observation functions. Our closest test combines the typed observation maps ϕg,i _g,i^O with the joint observation-preservation condition in Equation (6). The comparison is made after the state, action, and observation labels have been transformed. Hence differently named observations need not indicate different structural agent types. To compare directly with Hu et al.’s agent-local formulation, an application must also specify compatible timing and conditioning conventions and explain how its local observation functions induce the joint observation distribution Z. If Equation (6) fails, that particular componentwise environment automorphism is excluded, but a policy-evaluation symmetry may still relate the agents. A.3. Response- and Effect-Transition Heterogeneity Hu et al. (Hu et al., 2026) distinguish two locations at which agents may differ in the transition dynamics. Their agent-level model decomposes the global state as s^=(s1,…,s|N|,sE)∈(∏k∈Nk)×E, s=(s_1,…,s_|N|,s_E)∈ ( _k∈ NS_k )×S_E, where sks_k is agent k’s local state and sEs_E contains the remaining environmental state. Write a^=(a1,…,a|N|) a=(a_1,…,a_|N|) for the joint action. Response-transition heterogeneity concerns the local transition law Ti(⋅∣s^,a^)T^i(· s, a): under corresponding global states and joint actions, it asks whether agents have different distributions over their own next local states. Effect-transition heterogeneity instead concerns T−iT^-i, the collection of transition laws for the state components other than agent i, viewed as functions of (si,ai)(s_i,a_i) as well as the remaining state and action components. It asks whether different agents’ states or actions influence the rest of the system in different ways. The core POSG in Section 3 does not assume this agent-level decomposition. It specifies an undivided state space S and one global transition distribution P(s′∣s,a),P(s s,a), without canonically assigning coordinates of s to individual agents or attributing parts of the transition law to particular update mechanisms. Consequently, a difference in an agent’s own next-state distribution and a difference in its influence on other next-state components both appear as differences in the same global distribution. Equation (5) can test whether that entire distribution is preserved by a candidate type-compatible transformation. If the equation fails, however, the undivided representation does not reveal whether the failure arose from response dynamics, effect dynamics, or both. Thus, the two categories have the same closest counterpart in our core model only in this representational sense. They are not treated as equivalent concepts. To distinguish them, an application may additionally declare a decomposition =(∏k∈Nk)×ES=( _k∈ NS_k)×S_E, together with a complete collection of local transition factors and their dependency scopes. A candidate transformation must then map each local state component and transition factor to the corresponding component and factor for the target agent. A response-preservation test compares the factors that generate si′s_i and sσg(i)′s_ _g(i) . An effect-preservation test instead compares the factors for the remaining agents and environmental state insofar as those factors depend on (si,ai)(s_i,a_i) and (sσg(i),aσg(i))(s_ _g(i),a_ _g(i)), respectively. This additional structure is application-specific and, in general, cannot be recovered uniquely from P alone. For example, two robots exhibit a response difference if the same drive command under corresponding conditions produces different distributions over their own next velocities. They exhibit an effect difference if corresponding pushing actions produce different distributions over the next position of a shared object. Without declared velocity and object-state components, both differences appear only as changes in P(s′∣s,a)P(s s,a). These factor-level tests identify where a difference in the dynamics occurs. They do not provide a second definition of structural agent type. Structural agent types remain the agent orbits of GℳevalG_M^eval relative to the resulting admissible transformation group. Restricting that group to transformations that respect the declared factorization can refine the resulting orbit partition. Moreover, failure of a response- or effect-preservation test for one candidate transformation excludes that candidate componentwise symmetry, but it does not by itself prove that two agents have different structural agent types: another admissible policy-evaluation symmetry may still exchange them. A.4. Objective Heterogeneity Hu et al. (Hu et al., 2026) compare agents’ conditional reward distributions, while Bettini et al. (Bettini et al., 2023) distinguish behavior under a shared objective from behavior under different objectives. The closest componentwise test under our deterministic transition-reward convention is the exact reward-preservation condition in Equation (7). It compares the reward functions after the agent, state, and action labels have been transformed, rather than requiring the functions to be identical under their source labels. Failure of this condition excludes that particular componentwise environment automorphism but does not, by itself, establish different structural agent types. Section 6 also shows that a common reward function does not imply structural homogeneity. In a Dec-POMDP, all agents have equal value coordinates under the same policy and state–joint-history input, but they need not be exchangeable in their action spaces, observation spaces, or roles in the transition and observation distributions. Conversely, forming an aggregate common reward can preserve, remove, or create policy-evaluation symmetries, depending on the individual rewards and aggregation weights. Objective heterogeneity and structural heterogeneity are therefore related but distinct properties. A.5. Behavioral and Policy Heterogeneity The policy-output aspect of behavioral and policy heterogeneity concerns a selected policy rather than only the underlying game. Suppose H≤GℳevalH≤ G_M^eval. A selected policy π is H-equivariant exactly when, for every g∈Hg∈ H, agent i, decision time step t<Tt<T, local history hith_i^t, and action aia_i, πσg(i)t(ϕg,i(ai)∣Φg,iℋ,t(hit))=πit(ai∣hit). _ _g(i)^t ( _g,i^A(a_i) _g,i^H,t(h_i^t) )= _i^t(a_i h_i^t). After the prescribed history and action transformations, the two local rules therefore assign the same probabilities to corresponding actions. This is the symmetry-aware condition for behavioral homogeneity within each agent orbit of H. The policy tables may look different under their source labels and still satisfy it. For example, consider two agents in mirrored roles. One agent may turn right after observing an obstacle on its left, while the corresponding rule for the other agent is to turn left after observing an obstacle on its right. The rules are equivariant if the game symmetry exchanges the agents and the left–right labels. If a selected policy fails the displayed equality for this transformation, it breaks that particular game symmetry and expresses a policy-relative behavioral difference. This does not change the structural agent types, which are defined from complete policy evaluation for every policy. Nor does failure for one transformation prove that the agents are unrelated at the policy level, because another policy-evaluation symmetry may both preserve the selected policy and exchange them. The policy-heterogeneity definition of Hu et al. (Hu et al., 2026) covers more than differences between policy outputs: it also includes differences in action or observation spaces. In our framework, the existence of the necessary bijections is settled first by the type-compatibility and bijectivity requirements. Policy equivariance then compares the decision rules after those bijections have been applied. Bettini et al. (Bettini et al., 2023) use the possibility of distinct policy outputs on the same input to characterize agents with different behavioral models. They do not, however, restrict their analysis to identical inputs. Their behavioral-typing analysis also studies how one shared policy can produce apparently heterogeneous behavior when agent identifiers or other differences in observations provide different inputs. Our equivariance condition addresses another question: whether the selected local policies agree at histories and actions related by a policy-evaluation symmetry. Specifically, it compares the probability assigned to aia_i at hith_i^t with the probability assigned to ϕg,i(ai) _g,i^A(a_i) at Φg,iℋ,t(hit) _g,i^H,t(h_i^t) by agent σg(i) _g(i). When the history and action transformations are identities, this reduces to the same-input comparison. A.6. Exact Classes and Graded Differences The structural partition eval(ℳ)P_eval(M) is an exact classification: two agents share a structural agent type when some policy-evaluation symmetry exchanges them. The system neural diversity measure (Bettini et al., 2025) and the heterogeneity distances of Hu et al. (Hu et al., 2026) instead measure degrees of difference between behavioral or model components. Such measures can compare agents within one structural agent type or in different types when their required domains are comparable, but they do not replace the orbit partition. Conversely, orbit membership does not assign a numerical degree of similarity. The final row of Table 1 locates system neural diversity at the selected-policy level. Its pairwise distances compare agents’ action distributions on common observation inputs, assuming shared observation and action spaces (Bettini et al., 2025). This comparison does not test preservation of complete policy evaluation under agent permutations. A.7. Summary In summary, the transition, observation, and reward preservation conditions diagnose separately represented parts of the model. Policy-evaluation symmetries define structural agent types for the specified POSG and admissible transformation group. Given these symmetries, policy equivariance determines whether a selected policy is invariant under them. Table 1 classifies the prior categories according to the level of our framework that they describe. Structural agent types are instead defined by the agent orbits of the policy-evaluation symmetry group. Appendix B Proofs for the Core Framework In the following proofs, we define the product spaces for the joint action, joint observation, and joint history at time step t, as follows: =∏i∈Ni,=∏i∈Ni,ℋt=∏i∈Nℋit.A= _i∈ NA_i, = _i∈ NO_i, ^t= _i∈ NH_i^t. For transformations g,kg,k, the product gkgk means first applying k and then g. Thus, we have the following composition laws for the agent permutation and the state, action, and observation maps: σgk=σg∘σk,ϕgk=ϕg∘ϕk, _gk= _g _k, _gk^S= _g^S _k^S, ϕgk,i=ϕg,σk(i)∘ϕk,i,ϕgk,i=ϕg,σk(i)∘ϕk,i. _gk,i^A= _g, _k(i)^A _k,i^A, _gk,i^O= _g, _k(i)^O _k,i^O. We write (ht,a,o′)(h^t,a,o ) for the joint history obtained by appending (ai,oi′)(a_i,o_i ) to each local history hith_i^t. B.1. Induced actions Proposition B.1 (Induced group actions). The transformations in Equations (3) and (4) define left group actions of ℛadm(ℳ)R_adm(M) on Πdec _dec and V, respectively. Specifically: (i) Policies. For every g,k∈ℛadm(ℳ)g,k _adm(M) and π∈Πdecπ∈ _dec, the transformed policy belongs to Πdec _dec, and e⋅π=π,g⋅(k⋅π)=(gk)⋅π.e·π=π, g·(k·π)=(gk)·π. For every t<Tt<T, joint history hth^t, and joint action a, (g⋅π)t(g⋅a∣g⋅ht)=πt(a∣ht)=∏i∈Nπit(ai∣hit).(g·π)^t(g· a g· h^t)=π^t(a h^t)= _i∈ N _i^t(a_i h_i^t). Consequently, at every fixed joint history the transformed joint action distribution is still the product of one local distribution per agent. The deterministic transformation introduces no shared policy-randomization variable and no additional conditional correlation between agents’ actions. (i) Value profiles. For every g,k∈ℛadm(ℳ)g,k _adm(M) and V∈V , the transformed profile belongs to V, and e⋅V=V,g⋅(k⋅V)=(gk)⋅V.e· V=V, g·(k· V)=(gk)· V. The value-profile action laws ensure that successive transformations compose consistently. They are used in Proposition B.2 to establish that policy-evaluation symmetries form a subgroup. Proof. By the coordinatewise definition of the local-history maps and the composition laws for the action and observation maps, we obtain the following equation: Φgk,iℋ,t=Φg,σk(i)ℋ,t∘Φk,iℋ,t, _gk,i^H,t= _g, _k(i)^H,t _k,i^H,t, where σk(i) _k(i) identifies the agent whose coordinate contains the local history after applying k. At the initial time step t=0t=0, both sides fix the empty history. The joint-history transformation collects these local-history maps in the permuted agent coordinates. Using σgk=σg∘σk _gk= _g _k, for every i∈Ni∈ N we have that: [g⋅(k⋅ht)]σgk(i) [g·(k· h^t)]_ _gk(i) =Φg,σk(i)ℋ,t(Φk,iℋ,t(hit)) = _g, _k(i)^H,t ( _k,i^H,t(h_i^t) ) =Φgk,iℋ,t(hit)=[(gk)⋅ht]σgk(i). = _gk,i^H,t(h_i^t)=[(gk)· h^t]_ _gk(i). Since σgk _gk is a permutation, this proves that: (gk)⋅ht=g⋅(k⋅ht).(gk)· h^t=g·(k· h^t). Finally, combining this identity with ϕgk=ϕg∘ϕk _gk^S= _g^S _k^S and the definition τgt(s,ht)=(ϕg(s),g⋅ht) _g^t(s,h^t)=( _g^S(s),g· h^t) gives that: τgkt=τgt∘τkt. _gk^t= _g^t _k^t. The identity acts trivially, and the inverse coordinate maps undo each transformation. For policies, put a′=g⋅a =g· a and h′=g⋅hth =g· h^t. Then, we have that: (g⋅π)t(a′∣h′) (g·π)^t(a h ) =∏j∈N(g⋅π)jt(aj′∣hj′) = _j∈ N(g·π)_j^t(a _j h _j) =∏i∈N(g⋅π)σg(i)t(aσg(i)′∣hσg(i)′) = _i∈ N(g·π)_ _g(i)^t(a _ _g(i) h _ _g(i)) =∏i∈Nπit(ai∣hit)=πt(a∣ht). = _i∈ N _i^t(a_i h_i^t)=π^t(a h^t). Each transformed local rule depends only on the corresponding local history. It is normalized because its probabilities are obtained by bijectively reindexing the source agent’s actions. The pointwise policy definition and the coordinate composition laws give g⋅(k⋅π)=(gk)⋅πg·(k·π)=(gk)·π and e⋅π=πe·π=π. For the action on V, recall that this is the space of real-valued function profiles with zero terminal entries. Policy evaluation produces a particular profile VπV^π in this space. Fix an arbitrary V∈V . Since σg _g and τgt _g^t are bijective, Equation (4) assigns a unique real value to every transformed coordinate. The time index is unchanged, so terminal entries remain zero and g⋅V∈g· V . For any g,k∈ℛadm(ℳ)g,k _adm(M), i∈Ni∈ N, 0≤t≤T0≤ t≤ T, and xt∈tx_t _t, applying Equation (4) twice gives that: [g⋅(k⋅V)]σg(σk(i)),t(τgt(τktxt)) [g·(k· V)]_ _g( _k(i)),t ( _g^t( _k^tx_t) ) =(k⋅V)σk(i),t(τktxt) =(k· V)_ _k(i),t( _k^tx_t) =Vi,t(xt). =V_i,t(x_t). The first equality applies the definition to the profile k⋅Vk· V under g, at the coordinate (σk(i),t,τktxt)( _k(i),t, _k^tx_t). The second applies it to V under k. Applying the combined transformation gkgk once gives that: [(gk)⋅V]σgk(i),t(τgktxt)=Vi,t(xt).[(gk)· V]_ _gk(i),t( _gk^tx_t)=V_i,t(x_t). Because σgk=σg∘σk _gk= _g _k and τgkt=τgt∘τkt _gk^t= _g^t _k^t, the two calculations evaluate g⋅(k⋅V)g·(k· V) and (gk)⋅V(gk)· V at the same coordinate. Bijectivity ensures that these coordinates cover every agent and input at each time step, proving g⋅(k⋅V)=(gk)⋅Vg·(k· V)=(gk)· V. For the identity transformation, σe _e and τet _e^t are identity maps, so Equation (4) gives e⋅V=Ve· V=V. This proves the value-profile action laws and completes the proof. ∎ B.2. Complete proof for the strictness example Proof of Proposition 5.3. Let N=1,2N=\1,2\, set T=2T=2, choose any γ∈(0,1]γ∈(0,1], and let =L,M,HS=\L,M,H\. Both agents have action and observation sets 0,1\0,1\, and the initial state distribution is uniform. Take ℛadm(ℳ)R_adm(M) to be the full group of complete type-compatible transformations of these finite sets. Let g exchange the two agents while fixing the state, action, and observation labels. Thus, g⋅(a1,a2)=(a2,a1),g⋅(o1,o2)=(o2,o1).g·(a_1,a_2)=(a_2,a_1), g·(o_1,o_2)=(o_2,o_1). For a joint action a=(a1,a2)a=(a_1,a_2), abbreviated as a1a2a_1a_2, make the transition distribution independent of the current state by setting P(s′∣s,a)=pa(s′)for every s∈.P(s s,a)=p_a(s ) every s . In next-state order (L,M,H)(L,M,H), define apaapa00(1/2,1/3,1/6)01(1/3,1/3,1/3)10(5/12,1/6,5/12)11(1/6,1/3,1/2). array[]c@ c@ c@ ca&p_a&a&p_a\\ 00&(1/2,1/3,1/6)&01&(1/3,1/3,1/3)\\ 10&(5/12,1/6,5/12)&11&(1/6,1/3,1/2). array Make the observation distribution depend on the successor state but not on the joint action: Z(o′∣s′,a)=qs′(o′).Z(o s ,a)=q_s (o ). Abbreviating a joint observation (o1′,o2′)(o_1 ,o_2 ) as o1′o2′o_1 o_2 , use the joint-observation order (00,01,10,11)(00,01,10,11) and set qL=(3/8,1/4,1/4,1/8),qM=(1/4,1/4,1/4,1/4),q_L=(3/8,1/4,1/4,1/8), q_M=(1/4,1/4,1/4,1/4), qH=(1/8,1/4,1/4,3/8).q_H=(1/8,1/4,1/4,3/8). Finally, define c(L)=0,c(M)=1,c(H)=2,c(L)=0, c(M)=1, c(H)=2, and ri(s,a,s′)=c(s)+c(s′)+2ai+a1=a2.r_i(s,a,s )=c(s)+c(s )+2a_i+1\a_1=a_2\. Every initial, transition, and observation probability is positive. For each joint action a, define the expected successor-state reward component and the marginalized next-observation distribution by ma=∑s′pa(s′)c(s′),q¯a(o′)=∑s′pa(s′)qs′(o′).m_a= _s p_a(s )c(s ), q_a(o )= _s p_a(s )q_s (o ). For example, m01 m_01 =13c(L)+13c(M)+13c(H)=1, = 13c(L)+ 13c(M)+ 13c(H)=1, q¯01 q_01 =13(qL+qM+qH)=(1/4,1/4,1/4,1/4). = 13(q_L+q_M+q_H)=(1/4,1/4,1/4,1/4). The same calculations for the other joint actions give m00=23,m01=m10=1,m11=43,m_00= 23, m_01=m_10=1, m_11= 43, and q¯00 q_00 =(7/24,1/4,1/4,5/24), =(7/24,1/4,1/4,5/24), q¯01 q_01 =q¯10=(1/4,1/4,1/4,1/4), = q_10=(1/4,1/4,1/4,1/4), q¯11 q_11 =(5/24,1/4,1/4,7/24). =(5/24,1/4,1/4,7/24). Writing ui(a)=2ai+a1=a2u_i(a)=2a_i+1\a_1=a_2\, the transformation g, whose agent permutation swaps the two agents, therefore satisfies mg⋅a=ma,q¯g⋅a(g⋅o′)=q¯a(o′),uσg(i)(g⋅a)=ui(a).m_g· a=m_a, q_g· a(g· o )= q_a(o ), u_ _g(i)(g· a)=u_i(a). At t=1t=1, we separate the current-state contribution c(s)c(s) from the remaining expected reward by defining an expression, such that: Wiπ(h1)=∑a∈π1(a∣h1)[ui(a)+ma].W_i^π(h^1)= _a π^1(a h^1)[u_i(a)+m_a]. The Bellman recursion at t=1t=1 reduces to Vi,1π(s,h1)=c(s)+Wiπ(h1).V_i,1^π(s,h^1)=c(s)+W_i^π(h^1). The policy transformation and the three displayed identities give Wσg(i)g⋅π(g⋅h1)=Wiπ(h1).W_ _g(i)^g·π(g· h^1)=W_i^π(h^1). Indeed, changing variables by b=g⋅ab=g· a in the left-hand side matches the policy probability, uσg(i)(b)u_ _g(i)(b), and mbm_b with their three source terms on the right-hand side. At the initial time step t=0t=0, expanding Equation (1) yields the following equation: Vi,0π(s,h0)=∑a∈π0(a∣h0)[ V_i,0^π(s,h^0)= _a π^0(a h^0) [ c(s)+ui(a)+(1+γ)ma c(s)+u_i(a)+(1+γ)m_a +γ∑o′∈q¯a(o′)Wiπ(h0,a,o′)]. +γ _o q_a(o )W_i^π(h^0,a,o ) ]. The coefficient 1+γ1+γ appears because c(s′)c(s ) contributes once to the immediate reward and once, with discount γ, to the value at t=1t=1. In the transformed expression, use the bijections b=g⋅ab=g· a and o¯′=g⋅o′ o =g· o . The policy transformation matches the action probability. The identities for uiu_i and mam_a preserve the terms ui(a)u_i(a) and (1+γ)ma(1+γ)m_a, respectively. The identities for q¯a q_a and WiπW_i^π preserve the remaining term γ∑o′∈q¯a(o′)Wiπ(h0,a,o′)γ _o q_a(o )W_i^π(h^0,a,o ). Consequently, every term of the transformed sum equals its corresponding source term, which proves the value identity at the initial time step. Together with the identity at t=1t=1 and the zero values at t=2t=2, this gives that: Vσg(i),tg⋅π(τgtxt)=Vi,tπ(xt)V_ _g(i),t^g·π( _g^tx_t)=V_i,t^π(x_t) for every policy, agent, time step, and valid state–joint-history pair. Thus g∈Gℳevalg∈ G_M^eval. Its state map is the identity, so it also preserves the initial distribution. Nevertheless, for a=(0,1)a=(0,1) and s′=Ms =M, P(M∣s,g⋅a)=16≠13=P(M∣s,a),P(M s,g· a)= 16≠ 13=P(M s,a), so g∉Autenv(ℳ)g _env(M). It remains to rule out a different componentwise environment automorphism that exchanges the agents. Suppose, for a contradiction, that there exists a componentwise environment automorphism g~ g that exchanges the two agents. Let ψ denote its state permutation, and allow arbitrary binary action and observation relabelings. Substitute ri(s,a,s′)=c(s)+c(s′)+ui(a)r_i(s,a,s )=c(s)+c(s )+u_i(a) into the reward-preservation equation and move the source terms to the left. This gives the following equations: d(s)+d(s′)+uσg~(i)(g~⋅a)−ui(a)=0,d(s)=c(ψ(s))−c(s).d(s)+d(s )+u_ _ g(i)( g· a)-u_i(a)=0, d(s)=c(ψ(s))-c(s). Holding s′,a,is ,a,i fixed shows that d(s)d(s) is constant. Because ψ only permutes the three states, ∑sd(s)=∑sc(ψ(s))−∑sc(s)=0. _sd(s)= _sc(ψ(s))- _sc(s)=0. A constant function with zero sum is zero. Hence, d(s)=0d(s)=0 for every state, and injectivity of c gives ψ=idψ=id_S. Reward preservation reduces to an equation, such that: uσg~(i)(g~⋅a)=ui(a).u_ _ g(i)( g· a)=u_i(a). Write the two local action-label maps as f1f_1 and f2f_2. A bijection of the binary action set is either the identity or the label flip. Under the agent swap, [g~⋅a]2=f1(a1)[ g· a]_2=f_1(a_1) and [g~⋅a]1=f2(a2)[ g· a]_1=f_2(a_2). If f1f_1 flips labels, choose source agent 11 and a1=0a_1=0. Then, u2(g~⋅a)=2f1(0)+f2(a2)=f1(0)≥2,u_2( g· a)=2f_1(0)+1\f_2(a_2)=f_1(0)\≥ 2, whereas u1(a)≤1u_1(a)≤ 1, a contradiction. Thus f1f_1 is the identity. Repeating the same argument for source agent 22 shows that f2f_2 is also the identity. Observation relabeling cannot repair the transition mismatch because the transition equation does not contain an observation map. Therefore no componentwise environment automorphism exchanges the agents, while g∈Gℳevalg∈ G_M^eval does. Together with Theorem 5.2, which gives Autenv(ℳ)≤GℳevalAut_env(M)≤ G_M^eval, this proves Autenv(ℳ)⪇GℳevalAut_env(M) G_M^eval. The two orbit partitions are consequently (Autenv(ℳ))=1,2,eval(ℳ)=1,2.P(Aut_env(M))=\\1\,\2\\, _eval(M)=\\1,2\\. All transition, observation, and initial-state probabilities are positive, so the separation is not an artifact of histories that no policy can reach. ∎ B.3. Subgroup, orbit, and normal-form facts Proposition B.2 (Policy-evaluation symmetry subgroup and return equivariance under the initial distribution). The set GℳevalG_M^eval is a subgroup of ℛadm(ℳ)R_adm(M). Let Gℳeval,ρ0=g∈Gℳeval:ρ0(ϕg(s))=ρ0(s) for every s∈.G_M^eval, _0= \g∈ G_M^eval: _0 ( _g^S(s) )= _0(s) for every s \. Then Gℳeval,ρ0G_M^eval, _0 is a subgroup, and every g∈Gℳeval,ρ0g∈ G_M^eval, _0 satisfies Jσg(i)(g⋅π)=Ji(π)(i∈N,π∈Πdec).J_ _g(i)(g·π)=J_i(π) (i∈ N,\ π∈ _dec). Proof. We verify the three subgroup properties directly. The identity transformation satisfies the evaluation identity. If g,k∈Gℳevalg,k∈ G_M^eval, then ℰℳ((gk)⋅π) _M((gk)·π) =ℰℳ(g⋅(k⋅π)) =E_M(g·(k·π)) =g⋅ℰℳ(k⋅π)=(gk)⋅ℰℳ(π). =g·E_M(k·π)=(gk)·E_M(π). For inverses, fix g∈Gℳevalg∈ G_M^eval and any π∈Πdecπ∈ _dec. Since g−1∈ℛadm(ℳ)g^-1 _adm(M), Proposition B.1 ensures that g−1⋅π∈Πdecg^-1·π∈ _dec. Applying the defining evaluation identity for g to this policy and using g⋅(g−1⋅π)=πg·(g^-1·π)=π gives the following equation: ℰℳ(π)=g⋅ℰℳ(g−1⋅π).E_M(π)=g·E_M(g^-1·π). Apply g−1g^-1 to both value profiles. The value-profile action law g−1⋅(g⋅V)=Vg^-1·(g· V)=V then gives the following equation: ℰℳ(g−1⋅π)=g−1⋅ℰℳ(π).E_M(g^-1·π)=g^-1·E_M(π). Since π was arbitrary, this is the defining evaluation identity for g−1g^-1, so g−1∈Gℳevalg^-1∈ G_M^eval. The additional ρ0 _0-preservation condition is also closed under the group operations. The identity state map preserves ρ0 _0. If g and k preserve it, then we have that: ρ0(ϕgk(s))=ρ0(ϕg(ϕk(s)))=ρ0(ϕk(s))=ρ0(s). _0 ( _gk^S(s) )= _0 ( _g^S( _k^S(s)) )= _0( _k^S(s))= _0(s). If g preserves ρ0 _0, substituting u=(ϕg)−1(s)u=( _g^S)^-1(s) into ρ0(ϕg(u))=ρ0(u) _0( _g^S(u))= _0(u) shows that g−1g^-1 also preserves it. Hence Gℳeval,ρ0G_M^eval, _0 is a subgroup. Finally, let g∈Gℳeval,ρ0g∈ G_M^eval, _0. Preservation of the initial distribution means ρ0(ϕg(s))=ρ0(s) _0( _g^S(s))= _0(s). To apply evaluation equivariance, we reindex the initial-state sum using s′=ϕg(s)s = _g^S(s). Bijectivity ensures that every state is counted exactly once, and initial-distribution preservation ensures that its probability weight is unchanged. The empty initial joint history is fixed by the transformation, so we obtain the following identity: Jσg(i)(g⋅π) J_ _g(i)(g·π) =∑s′∈ρ0(s′)Vσg(i),0g⋅π(s′,()N) = _s _0(s )V_ _g(i),0^g·π(s ,()^N) =∑s∈ρ0(ϕg(s))Vσg(i),0g⋅π(ϕg(s),()N) = _s _0( _g^S(s))V_ _g(i),0^g·π( _g^S(s),()^N) =∑s∈ρ0(s)Vi,0π(s,()N)=Ji(π). = _s _0(s)V_i,0^π(s,()^N)=J_i(π). ∎ Proposition B.3 (Orbit facts). For every subgroup H≤ℛadm(ℳ),H _adm(M), define i∼Hji _Hj when some g∈Hg∈ H satisfies σg(i)=j _g(i)=j. Then ∼H _H is an equivalence relation. If H≤KH≤ K, then (H)⪯(K)P(H) (K). Proof. We first show that ∼H _H is an equivalence relation by verifying reflexivity, symmetry, and transitivity (Judson and Beezer, 1994, Chap. 1.2). For reflexivity, we must show that i∼Hii _Hi for every agent i. Because H is a subgroup, it contains the identity transformation e. This transformation leaves every agent label unchanged, so σe(i)=i _e(i)=i. Thus, e∈He∈ H satisfies the defining condition for i∼Hii _Hi. For symmetry, suppose that i∼Hji _Hj. By definition, some g∈Hg∈ H satisfies σg(i)=j _g(i)=j. Since H is a subgroup, the inverse transformation g−1g^-1 also belongs to H. Its agent permutation reverses that of g, giving σg−1(j)=σg−1(σg(i))=σg−1g(i)=σe(i)=i. _g^-1(j)= _g^-1 ( _g(i) )= _g^-1g(i)= _e(i)=i. Thus, g−1∈Hg^-1∈ H maps agent j back to agent i, which establishes j∼Hij _Hi. This proves symmetry of the relation. For transitivity, if σg(i)=j _g(i)=j and σk(j)=ℓ _k(j)= for g,k∈Hg,k∈ H, then kg∈Hkg∈ H and σkg(i)=ℓ _kg(i)= , giving i∼Hℓi _H . The equivalence classes are precisely the H-orbits, which form the partition (H)P(H). If H≤KH≤ K, then we have σg(i):g∈H⊆σg(i):g∈K,\ _g(i):g∈ H\ \ _g(i):g∈ K\, for every agent i. Thus, every H-orbit is contained in a K-orbit. Since these orbits are the parts of the corresponding partitions, every part of (H)P(H) is contained in a part of (K)P(K). By the definition of partition refinement, (H)⪯(K)P(H) (K). ∎ To check the definition in a static setting, we show that policy-evaluation symmetry reduces to payoff preservation for the following one-stage normal-form embedding. Proposition B.4 (Normal-form special case). Embed a finite normal-form game Γ=(N,(i)i,(ui)i) =(N,(A_i)_i,(u_i)_i) as a horizon-one POSG with one state, singleton observations, deterministic dynamics, and reward ri(s⋆,a,s⋆)=ui(a)r_i(s_ ,a,s_ )=u_i(a). For an admissible transformation g, evaluation equivariance for every mixed product policy is equivalent to uσg(i)(g⋅a)=ui(a)for every i and pure profile a.u_ _g(i)(g· a)=u_i(a) every i and pure profile a. Every admissible transformation automatically preserves the unique initial state–joint-history distribution. Proof. Let Ui(π)U_i(π) denote agent i’s expected payoff under the mixed product policy π. If the displayed payoff identity holds, reindexing joint actions and using the product-policy transformation gives Uσg(i)(g⋅π) U_ _g(i)(g·π) =∑a∈uσg(i)(g⋅a)∏j∈Nπj(aj) = _a u_ _g(i)(g· a) _j∈ N _j(a_j) =∑a∈ui(a)∏j∈Nπj(aj)=Ui(π). = _a u_i(a) _j∈ N _j(a_j)=U_i(π). Conversely, the policy domain contains every deterministic product policy δa _a, and g⋅δa=δg⋅ag· _a= _g· a. Evaluation equivariance gives uσg(i)(g⋅a)=Uσg(i)(δg⋅a)=Ui(δa)=ui(a).u_ _g(i)(g· a)=U_ _g(i)( _g· a)=U_i( _a)=u_i(a). Finally, let g∈ℛadm(ℳ)g _adm(M) be arbitrary. Since =s⋆S=\s_ \, its bijective state map must satisfy ϕg(s⋆)=s⋆ _g^S(s_ )=s_ . Every initial local history is empty, so there are no actions or observations to transform. Permuting the agents only rearranges identical empty histories, giving g⋅()N=()Ng·()^N=()^N. Consequently, τg0(s⋆,()N) _g^0(s_ ,()^N) =(ϕg(s⋆),g⋅()N) = ( _g^S(s_ ),g·()^N ) =(s⋆,()N). =(s_ ,()^N). The initial distribution assigns probability one to this single pair. Because the pair is fixed, its distribution is preserved by every admissible transformation. ∎ Appendix C Proofs for Componentwise Environment Automorphisms Proposition C.1 (Subgroup property of componentwise environment automorphisms). The set in Definition 5.1 satisfies Autenv(ℳ)≤ℛadm(ℳ).Aut_env(M) _adm(M). The componentwise environment automorphisms that preserve the initial distribution, such that: g∈Autenv(ℳ):ρ0(ϕg(s))=ρ0(s) for every s∈, \g _env(M): _0 ( _g^S(s) )= _0(s) for every s \, also form a subgroup. Proof. The identity preserves each component. Suppose g and k satisfy Equations (5)–(7). For transitions, P(ϕgk(s′)∣ϕgk(s),(gk)⋅a) P( _gk^S(s ) _gk^S(s),(gk)· a) =P(ϕg(ϕk(s′))∣ϕg(ϕk(s)),g⋅(k⋅a)) =P( _g^S( _k^S(s )) _g^S( _k^S(s)),g·(k· a)) =P(ϕk(s′)∣ϕk(s),k⋅a)=P(s′∣s,a). =P( _k^S(s ) _k^S(s),k· a)=P(s s,a). The first preservation equality removes the outer transformation g, and the second removes k. The observation and reward calculations have the same two-step procedure. For observations, Z((gk)⋅o′∣ϕgk(s′),(gk)⋅a) Z((gk)· o _gk^S(s ),(gk)· a) =Z(g⋅(k⋅o′)∣ϕg(ϕk(s′)),g⋅(k⋅a)) =Z(g·(k· o ) _g^S( _k^S(s )),g·(k· a)) =Z(k⋅o′∣ϕk(s′),k⋅a)=Z(o′∣s′,a). =Z(k· o _k^S(s ),k· a)=Z(o s ,a). For rewards, tracking the agent coordinate gives rσgk(i)(ϕgk(s),(gk)⋅a,ϕgk(s′)) r_ _gk(i)( _gk^S(s),(gk)· a, _gk^S(s )) =rσg(σk(i))(ϕg(ϕk(s)),g⋅(k⋅a),ϕg(ϕk(s′))) =r_ _g( _k(i))( _g^S( _k^S(s)),g·(k· a), _g^S( _k^S(s ))) =rσk(i)(ϕk(s),k⋅a,ϕk(s′))=ri(s,a,s′). =r_ _k(i)( _k^S(s),k· a, _k^S(s ))=r_i(s,a,s ). Thus the set is closed under composition. For inverse closure, fix g∈Autenv(ℳ)g _env(M). Since ℛadm(ℳ)R_adm(M) is a group, g−1g^-1 is an admissible transformation. We show that it also preserves the three model components by applying the identities already known for g to suitable inputs. For transitions, Equation (5) holds for every pair of states u,u′u,u and joint action b: P(ϕg(u′)∣ϕg(u),g⋅b)=P(u′∣u,b).P( _g^S(u ) _g^S(u),g· b)=P(u u,b). For arbitrary s,s′s,s , and a, choose u=ϕg−1(s),u′=ϕg−1(s′),b=g−1⋅a.u= _g^-1^S(s), u = _g^-1^S(s ), b=g^-1· a. Applying g cancels these inverse transformations, so ϕg(u)=s _g^S(u)=s, ϕg(u′)=s′ _g^S(u )=s , and g⋅b=ag· b=a. Substitution into the transition identity therefore gives P(s′∣s,a)=P(ϕg−1(s′)∣ϕg−1(s),g−1⋅a),P(s s,a)=P( _g^-1^S(s ) _g^-1^S(s),g^-1· a), which shows that the transition probabilities are preserved under g−1g^-1. For observations, Equation (6) gives Z(g⋅v′∣ϕg(u′),g⋅b)=Z(v′∣u′,b).Z(g· v _g^S(u ),g· b)=Z(v u ,b). Use the same u′u and b, and set v′=g−1⋅o′v =g^-1· o for an arbitrary joint observation o′o . Since g⋅v′=o′g· v =o , substitution gives Z(o′∣s′,a)=Z(g−1⋅o′∣ϕg−1(s′),g−1⋅a).Z(o s ,a)=Z(g^-1· o _g^-1^S(s ),g^-1· a). For rewards, Equation (7) holds for every agent j: rσg(j)(ϕg(u),g⋅b,ϕg(u′))=rj(u,b,u′).r_ _g(j)( _g^S(u),g· b, _g^S(u ))=r_j(u,b,u ). Use the same u,u′u,u , and b, and choose j=σg−1(i)j= _g^-1(i) for an arbitrary agent i. The agent permutations also cancel, giving σg(j)=i _g(j)=i. Thus, substitution into the reward identity gives ri(s,a,s′)=rσg−1(i)(ϕg−1(s),g−1⋅a,ϕg−1(s′)).r_i(s,a,s )=r_ _g^-1(i)( _g^-1^S(s),g^-1· a, _g^-1^S(s )). Because s,s′,a,o′s,s ,a,o , and i were arbitrary, these three identities show that g−1g^-1 preserves the transition probabilities, observation probabilities, and reward functions. Hence, g−1∈Autenv(ℳ)g^-1 _env(M). Together with the identity and composition properties proved above, this establishes that Autenv(ℳ)Aut_env(M) is a subgroup. It remains to impose preservation of the initial distribution. The identity state map preserves ρ0 _0. If g and k preserve ρ0 _0, then ρ0(ϕgk(s))=ρ0(ϕg(ϕk(s)))=ρ0(ϕk(s))=ρ0(s). _0 ( _gk^S(s) )= _0 ( _g^S( _k^S(s)) )= _0 ( _k^S(s) )= _0(s). For inverse closure, suppose g preserves ρ0 _0. This means that for every state u∈u , ρ0(ϕg(u))=ρ0(u). _0 ( _g^S(u) )= _0(u). For an arbitrary state s, choose u=ϕg−1(s)=(ϕg)−1(s)u= _g^-1^S(s)=( _g^S)^-1(s). Substituting this state into the preservation identity for g gives ρ0(ϕg(ϕg−1(s)))=ρ0(ϕg−1(s)). _0 ( _g^S( _g^-1^S(s)) )= _0 ( _g^-1^S(s) ). Since ϕg(ϕg−1(s))=s _g^S( _g^-1^S(s))=s, the left-hand side simplifies to ρ0(s) _0(s), yielding ρ0(s)=ρ0(ϕg−1(s)). _0(s)= _0 ( _g^-1^S(s) ). This holds for every s, so g−1g^-1 also preserves ρ0 _0. Together with the componentwise closure already proved, these calculations establish the second subgroup claim. ∎ Proof of Theorem 5.2. Proposition C.1 already establishes that Autenv(ℳ)Aut_env(M) is a subgroup of ℛadm(ℳ)R_adm(M). We now show that every element of this subgroup is a policy-evaluation symmetry. Fix g∈Autenv(ℳ)g _env(M). We prove by backward induction that Vσg(i),tg⋅π(τgtxt)=Vi,tπ(xt)V_ _g(i),t^g·π( _g^tx_t)=V_i,t^π(x_t) for every agent i, policy π, time step t, and xt∈tx_t _t. At t=Tt=T, both corresponding values are zero. Assume the identity holds at time step t+1t+1. For t<Tt<T, expand the transformed value: Vσg(i),tg⋅π(τgt(s,ht)) V_ _g(i),t^g·π( _g^t(s,h^t)) =∑b,s¯′,o¯′(g⋅π)t(b∣g⋅ht)P(s¯′∣ϕg(s),b)Z(o¯′∣s¯′,b) = _b, s , o (g·π)^t(b g· h^t)P( s _g^S(s),b)Z( o s ,b) ⋅[rσg(i)(ϕg(s),b,s¯′)+γVσg(i),t+1g⋅π(s¯′,g⋅ht,b,o¯′)]. · [r_ _g(i)( _g^S(s),b, s )+γ V_ _g(i),t+1^g·π( s ,g· h^t,b, o ) ]. Reindex the sum using b=g⋅a,s¯′=ϕg(s′),o¯′=g⋅o′.b=g· a, s = _g^S(s ), o =g· o . Each transformation is bijective, so every triple (b,s¯′,o¯′)(b, s , o ) corresponds to exactly one triple (a,s′,o′)(a,s ,o ). For the joint-action probability, the product-policy definition and the local policy-transformation rule in Equation (3) give (g⋅π)t(g⋅a∣g⋅ht) (g·π)^t(g· a g· h^t) =∏j∈N(g⋅π)σg(j)t(ϕg,j(aj)∣Φg,jℋ,t(hjt)) = _j∈ N(g·π)_ _g(j)^t ( _g,j^A(a_j) _g,j^H,t(h_j^t) ) =∏j∈Nπjt(aj∣hjt)=πt(a∣ht). = _j∈ N _j^t(a_j h_j^t)=π^t(a h^t). The first equality indexes the product by σg(j) _g(j), which visits each agent exactly once because σg _g is a permutation. Since g∈Autenv(ℳ)g _env(M), Definition 5.1 provides Equations (5)–(7). Applying these identities to the substituted transition, observation, and reward terms gives P(ϕg(s′)∣ϕg(s),g⋅a) P( _g^S(s ) _g^S(s),g· a) =P(s′∣s,a), =P(s s,a), Z(g⋅o′∣ϕg(s′),g⋅a) Z(g· o _g^S(s ),g· a) =Z(o′∣s′,a), =Z(o s ,a), rσg(i)(ϕg(s),g⋅a,ϕg(s′)) r_ _g(i)( _g^S(s),g· a, _g^S(s )) =ri(s,a,s′). =r_i(s,a,s ). To apply the induction hypothesis to the remaining value term, for each joint action a and next joint observation o′o , write ht+1:=(ht,a,o′).h^t+1:=(h^t,a,o ). This is the joint history of length t+1t+1 obtained by appending a and o′o to hth^t. The history transformation applies the same action and observation maps to every entry and preserves their order. Thus, transforming this extended history gives g⋅ht+1=(g⋅ht,g⋅a,g⋅o′).g· h^t+1=(g· h^t,g· a,g· o ). Recall from Section 3 that τgt(s,ht)=(ϕg(s),g⋅ht), _g^t(s,h^t)= ( _g^S(s),g· h^t ), so τgt _g^t transforms both the state and the joint history at time step t. Applying this definition at time step t+1t+1 and using the preceding history identity, the next state–joint-history pair in the substituted sum is therefore (ϕg(s′),(g⋅ht,g⋅a,g⋅o′)) ( _g^S(s ),(g· h^t,g· a,g· o ) ) =(ϕg(s′),g⋅ht+1) = ( _g^S(s ),g· h^t+1 ) =τgt+1(s′,ht+1). = _g^t+1 (s ,h^t+1 ). The induction hypothesis at time step t+1t+1, applied to (s′,ht+1)(s ,h^t+1), now gives Vσg(i),t+1g⋅π(ϕg(s′),g⋅ht+1) V_ _g(i),t+1^g·π ( _g^S(s ),g· h^t+1 ) =Vσg(i),t+1g⋅π(τgt+1(s′,ht+1)) =V_ _g(i),t+1^g·π ( _g^t+1(s ,h^t+1) ) =Vi,t+1π(s′,ht+1). =V_i,t+1^π (s ,h^t+1 ). Using the preceding identities in sequence, the Bellman expansion becomes Vσg(i),tg⋅π(τgt(s,ht)) V_ _g(i),t^g·π( _g^t(s,h^t)) =(1)∑a,s′,o′(g⋅π)t(g⋅a∣g⋅ht) (1)= _a,s ,o (g·π)^t(g· a g· h^t) ⋅P(ϕg(s′)∣ϕg(s),g⋅a) · P( _g^S(s ) _g^S(s),g· a) ⋅Z(g⋅o′∣ϕg(s′),g⋅a) · Z(g· o _g^S(s ),g· a) ⋅[rσg(i)(ϕg(s),g⋅a,ϕg(s′)) · [r_ _g(i)( _g^S(s),g· a, _g^S(s )) +γVσg(i),t+1g⋅π(τgt+1(s′,ht+1))] +γ V_ _g(i),t+1^g·π ( _g^t+1(s ,h^t+1) ) ] =(2)∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) (2)= _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[ri(s,a,s′)+γVσg(i),t+1g⋅π(τgt+1(s′,ht+1))] · [r_i(s,a,s )+γ V_ _g(i),t+1^g·π ( _g^t+1(s ,h^t+1) ) ] =(3)∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) (3)= _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[ri(s,a,s′)+γVi,t+1π(s′,ht+1)] · [r_i(s,a,s )+γ V_i,t+1^π (s ,h^t+1 ) ] =(4)Vi,tπ(s,ht). (4)=V_i,t^π(s,h^t). Step (1) uses the bijective substitutions and the identity for the next state–joint-history pair. Step (2) uses the joint-policy identity derived from Equation (3) and the componentwise identities in Equations (5)–(7) to replace the action, transition, and observation probabilities and the reward. Step (3) applies the induction hypothesis at time step t+1t+1 to the remaining transformed value. Step (4) is Equation (1), with ht+1=(ht,a,o′)h^t+1=(h^t,a,o ). This completes the induction. The equality holds for every agent, policy, time step, and valid state–joint-history pair, so Definition 4.1 gives g∈Gℳevalg∈ G_M^eval. Since g was arbitrary, Autenv(ℳ)⊆GℳevalAut_env(M) G_M^eval. The subgroup property from Proposition C.1 then gives Autenv(ℳ)≤GℳevalAut_env(M)≤ G_M^eval. Proposition B.3 yields the corresponding partition refinement: (Autenv(ℳ))⪯eval(ℳ),P(Aut_env(M)) _eval(M), as claimed. ∎ Appendix D Extension to Dec-POMDPs Proposition D.1 (Existing common reward). If ri=rcomr_i=r^com for every agent, then, for every policy π, time step t, valid x∈tx _t, and agents i,ji,j, Vi,tπ(x)=Vj,tπ(x).V_i,t^π(x)=V_j,t^π(x). The structural agent types nevertheless remain the orbits of GℳevalG_M^eval; in particular, equality of the value coordinates does not by itself imply that this group acts transitively on the agents. Proof. Fix an arbitrary policy π∈Πdecπ∈ _dec and agents i,j∈Ni,j∈ N. We prove equality of their values at every valid input by backward induction. At t=Tt=T, Vi,Tπ(x)=0=Vj,Tπ(x)for every x∈T.V_i,T^π(x)=0=V_j,T^π(x) every x _T. Suppose that Vi,t+1π(x′)=Vj,t+1π(x′)V_i,t+1^π(x )=V_j,t+1^π(x ) for every x′∈t+1x _t+1. Fix any (s,ht)∈t(s,h^t) _t, and write ht+1=(ht,a,o′)h^t+1=(h^t,a,o ) in each summand. Equation (1) and ri=rj=rcomr_i=r_j=r^com give Vi,tπ(s,ht) V_i,t^π(s,h^t) =∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) = _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[rcom(s,a,s′)+γVi,t+1π(s′,ht+1)] · [r^com(s,a,s )+γ V_i,t+1^π(s ,h^t+1) ] =∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) = _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[rcom(s,a,s′)+γVj,t+1π(s′,ht+1)] · [r^com(s,a,s )+γ V_j,t+1^π(s ,h^t+1) ] =Vj,tπ(s,ht). =V_j,t^π(s,h^t). The middle equality uses the induction hypothesis at the next input (s′,ht+1)(s ,h^t+1), which lies in t+1X_t+1. The first and last equalities use the Bellman recursion with the common reward. This proves the induction step. Since π,i,jπ,i,j, and the input were arbitrary, the value equality holds with all the stated quantifiers. The orbit characterization of structural agent types follows directly from Definition 4.2. To show that the value equality does not imply transitivity, consider the one-stage common-reward example from Section 6. Specify N=1,2N=\1,2\, T=1T=1, =s⋆S=\s_ \, 1=2=0,1A_1=A_2=\0,1\, and 1=2=o⋆O_1=O_2=\o_ \. The initial state is s⋆s_ with probability one, and the transition and observation distributions assign probability one to the unique next state and joint observation. Both agents receive r1(s⋆,a,s⋆)=r2(s⋆,a,s⋆)=a1.r_1(s_ ,a,s_ )=r_2(s_ ,a,s_ )=a_1. Take ℛadm(ℳ)R_adm(M) to be the full group of type-compatible transformations, so agent exchanges and arbitrary binary action relabelings are admissible. Suppose, for a contradiction, that some g∈Gℳevalg∈ G_M^eval exchanges the two agents. The first coordinate of g⋅ag· a is then ϕg,2(a2) _g,2^A(a_2). By Proposition B.4, g must preserve the payoffs at every pure joint action. The common reward therefore requires ϕg,2(a2)=a1for every a1,a2∈0,1. _g,2^A(a_2)=a_1 every a_1,a_2∈\0,1\. Taking (a1,a2)=(0,0)(a_1,a_2)=(0,0) and (1,0)(1,0) would give both ϕg,2(0)=0 _g,2^A(0)=0 and ϕg,2(0)=1 _g,2^A(0)=1, a contradiction. Hence no policy-evaluation symmetry exchanges the two agents, and eval(ℳ)=1,2.P_eval(M)= \\1\,\2\ \. The value coordinates are equal by the first part of this proof, but the policy-evaluation symmetry group is not transitive. This proves the final claim. ∎ Proof of Theorem 6.1. Fix an arbitrary policy π∈Πdecπ∈ _dec. We first prove the weighted-value identity for every derived agent j and every valid input by backward induction on the time step. At t=Tt=T, all values in both models are zero. Consequently, for every j∈Nj∈ N and x∈Tx _T, Vj,Tπ;ℳw(x)=0=∑i∈Nwi 0=∑i∈NwiVi,Tπ;ℳ(x).V_j,T^π;M_w(x)=0= _i∈ Nw_i\,0= _i∈ Nw_iV_i,T^π;M(x). This establishes the base case. For the induction step, let t<Tt<T and suppose that Vj,t+1π;ℳw(x′)=∑i∈NwiVi,t+1π;ℳ(x′)V_j,t+1^π;M_w(x )= _i∈ Nw_iV_i,t+1^π;M(x ) for every j∈Nj∈ N and every x′∈t+1x _t+1. We must establish the same identity at time step t. Fix any j∈Nj∈ N and x=(s,ht)∈tx=(s,h^t) _t. For each action a, next state s′s , and next observation o′o in the Bellman sum, write ht+1:=(ht,a,o′),x′:=(s′,ht+1)∈t+1.h^t+1:=(h^t,a,o ), x :=(s ,h^t+1) _t+1. Thus the induction hypothesis applies to every next input in that sum. The two models have the same policy domain, transition and observation distributions, and discount factor. Evaluating the fixed policy π therefore uses the same factors πt(a∣ht)π^t(a h^t), P(s′∣s,a)P(s s,a), and Z(o′∣s′,a)Z(o s ,a) in both models. The Bellman recursion gives the following sequence of equalities: Vj,tπ;ℳw(s,ht) V_j,t^π;M_w(s,h^t) =(1)∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) (1)= _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[rw(s,a,s′)+γVj,t+1π;ℳw(x′)] · [r^w(s,a,s )+γ V_j,t+1^π;M_w(x ) ] =(2)∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) (2)= _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[∑i∈Nwiri(s,a,s′)+γ∑i∈NwiVi,t+1π;ℳ(x′)] · [ _i∈ Nw_ir_i(s,a,s )+γ _i∈ Nw_iV_i,t+1^π;M(x ) ] =(3)∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) (3)= _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅∑i∈Nwi[ri(s,a,s′)+γVi,t+1π;ℳ(x′)] · _i∈ Nw_i [r_i(s,a,s )+γ V_i,t+1^π;M(x ) ] =(4)∑i∈Nwi∑a,s′,o′πt(a∣ht)P(s′∣s,a)Z(o′∣s′,a) (4)= _i∈ Nw_i _a,s ,o π^t(a h^t)P(s s,a)Z(o s ,a) ⋅[ri(s,a,s′)+γVi,t+1π;ℳ(x′)] · [r_i(s,a,s )+γ V_i,t+1^π;M(x ) ] =(5)∑i∈NwiVi,tπ;ℳ(s,ht). (5)= _i∈ Nw_iV_i,t^π;M(s,h^t). Step (1) is Equation (1) in ℳwM_w, where agent j’s reward is rwr^w. Step (2) replaces rwr^w by its defining weighted sum and applies the induction hypothesis to Vj,t+1π;ℳw(x′)V_j,t+1^π;M_w(x ). Step (3) combines the two sums over i by distributing each weight wiw_i over the reward and next value. Step (4) interchanges the finite sums over agents and over (a,s′,o′)(a,s ,o ). In this step, the weights are fixed, and the policy, transition, and observation factors are the same for every reward index i. Finally, in step (5), the inner sum for each i is Equation (1) in ℳM, so it equals Vi,tπ;ℳ(s,ht)V_i,t^π;M(s,h^t). Since j and (s,ht)(s,h^t) were arbitrary, this establishes the identity at time step t for every derived agent and valid input. Starting from t=Tt=T and repeating this induction step proves it at t=T−1,…,0t=T-1,…,0. The policy π was also arbitrary, so the identity holds for every decentralized policy as stated in the theorem. We next show that the weight-preserving elements of GℳevalG_M^eval form a subgroup of GℳevalG_M^eval. Since GℳevalG_M^eval is already a group, it suffices to verify three properties of the set of weight-preserving policy-evaluation symmetries: (i) the identity transformation belongs to this set; (i) composing any two transformations in this set gives another transformation in the set; and (i) the inverse of every transformation in this set also belongs to the set. The identity preserves w. If g and k preserve the weights, then wσgk(i)=wσg(σk(i))=wσk(i)=wi.w_ _gk(i)=w_ _g( _k(i))=w_ _k(i)=w_i. Finally, wσg(i)=wiw_ _g(i)=w_i implies the corresponding equality for g−1g^-1 after substituting i=σg−1(k)i= _g^-1(k). Now let g∈Gℳevalg∈ G_M^eval preserve the weights. For every derived agent j, Vσg(j),tg⋅π;ℳw(τgtx) V_ _g(j),t^g·π;M_w( _g^tx) =∑iwσg(i)Vσg(i),tg⋅π;ℳ(τgtx) = _iw_ _g(i)V_ _g(i),t^g·π;M( _g^tx) =∑iwiVi,tπ;ℳ(x)=Vj,tπ;ℳw(x). = _iw_iV_i,t^π;M(x)=V_j,t^π;M_w(x). The first equality applies the weighted-value identity and reindexes the agent sum by k=σg(i)k= _g(i). The second uses weight preservation and source policy-evaluation equivariance. Since this holds for every policy, agent, time step, and valid state–joint-history pair, g∈Gℳwevalg∈ G_M_w^eval, proving the asserted subgroup inclusion. At the componentwise level, let g∈Autenv(ℳ)g _env(M) preserve the weights. By construction, reward aggregation changes only the reward functions: the transition distribution P and observation distribution Z are unchanged in ℳwM_w. Consequently, the preservation identities in Equations (5) and (6), which g already satisfies in ℳM, also hold in ℳwM_w. It remains to check preservation of the aggregate reward rwr^w. Reindexing the defining reward sum by k=σg(i)k= _g(i) gives rw(ϕg(s),g⋅a,ϕg(s′)) r^w( _g^S(s),g· a, _g^S(s )) =∑iwσg(i)rσg(i)(ϕg(s),g⋅a,ϕg(s′)) = _iw_ _g(i)r_ _g(i)( _g^S(s),g· a, _g^S(s )) =∑iwiri(s,a,s′)=rw(s,a,s′). = _iw_ir_i(s,a,s )=r^w(s,a,s ). Thus it is also a componentwise environment automorphism of ℳwM_w. The weight-preserving componentwise environment automorphisms form a subgroup as well. The identity preserves the weights. Closure under composition follows from the displayed calculation for wσgk(i)w_ _gk(i), and the same substitution proves inverse closure. Proposition C.1 establishes that Autenv(ℳ)Aut_env(M) is a group. The checks above show that the set of its weight-preserving elements contains the identity and is closed under composition and inverses. These properties establish that this set is a subgroup of Autenv(ℳ)Aut_env(M). The preceding componentwise calculation shows that every element of this subgroup belongs to Autenv(ℳw)Aut_env(M_w). Therefore g∈Autenv(ℳ):wσg(i)=wifor every i≤Autenv(ℳw). \g _env(M):w_ _g(i)=w_i\ for every i \ _env(M_w). ∎ Proposition D.2 (Expected returns under weighted aggregation). Under the construction of Theorem 6.1, the models ℳM and ℳwM_w share the initial distribution ρ0 _0. For every policy π∈Πdecπ∈ _dec and every agent j∈Nj∈ N, Jjℳw(π)=∑i∈NwiJiℳ(π).J_j^M_w(π)= _i∈ Nw_iJ_i^M(π). This identity does not require any symmetry assumption. Moreover, let g∈Gℳevalg∈ G_M^eval satisfy wσg(i) w_ _g(i) =wi =w_i for every i∈N, every i∈ N, ρ0(ϕg(s)) _0( _g^S(s)) =ρ0(s) = _0(s) for every s∈. every s . Then, for every policy π∈Πdecπ∈ _dec and agent j∈Nj∈ N, Jσg(j)ℳw(g⋅π)=Jjℳw(π).J_ _g(j)^M_w(g·π)=J_j^M_w(π). Proof. Fix any policy π∈Πdecπ∈ _dec and agent j∈Nj∈ N. The expected-return definition in Equation (2) and the weighted-value identity in Theorem 6.1 give Jjℳw(π) J_j^M_w(π) =∑s∈ρ0(s)Vj,0π;ℳw(s,()N) = _s _0(s)V_j,0^π;M_w(s,()^N) =∑s∈ρ0(s)∑i∈NwiVi,0π;ℳ(s,()N) = _s _0(s) _i∈ Nw_iV_i,0^π;M(s,()^N) =∑i∈Nwi∑s∈ρ0(s)Vi,0π;ℳ(s,()N) = _i∈ Nw_i _s _0(s)V_i,0^π;M(s,()^N) =∑i∈NwiJiℳ(π). = _i∈ Nw_iJ_i^M(π). The second equality applies the theorem at the initial time step to each state and the empty joint history. The third interchanges the finite sums over states and agents. The first and last equalities use the expected-return definition with the same initial distribution ρ0 _0. For the second claim, weight preservation and Theorem 6.1 imply that g∈Gℳwevalg∈ G_M_w^eval. By assumption, g also preserves ρ0 _0, which is the initial distribution of ℳwM_w as well as ℳM. Thus Proposition B.2, applied to ℳwM_w, gives Jσg(j)ℳw(g⋅π)=Jjℳw(π)J_ _g(j)^M_w(g·π)=J_j^M_w(π) for every policy π and agent j, proving the second claim. ∎ Proposition D.3 (Aggregation can split or merge structural agent types). Under the construction of Theorem 6.1, each of the following outcomes can occur for a one-stage, two-agent source model ℳM and its derived common-reward model ℳwM_w: (1) With unequal weights w1≠w2w_1≠ w_2, one structural agent type in ℳM splits into two distinct structural agent types in ℳwM_w. (2) With equal weights w1=w2w_1=w_2, two distinct structural agent types in ℳM merge into one structural agent type in ℳwM_w. (3) With unequal weights w1≠w2w_1≠ w_2, two distinct structural agent types in ℳM merge into one structural agent type in ℳwM_w. Consequently, neither direction of refinement between (Gℳeval)P(G_M^eval) and (Gℳweval)P(G_M_w^eval) holds for all source models ℳM and weight vectors w. Proof. We construct one example for each of the three claims. All three use one-stage, two-agent models with singleton state and observation spaces, binary action sets, deterministic self-transition, and an admissible group containing only the identity and a transformation g whose agent permutation swaps the two agents and whose local action-label maps are identities. Case 1: Splitting a Structural Agent Type (Unequal Weights). Take r1(a1,a2)=a1,r2(a1,a2)=a2.r_1(a_1,a_2)=a_1, r_2(a_1,a_2)=a_2. g is a componentwise environment automorphism of ℳM, so its orbit partition is 1,2\\1,2\\. With w=(3/4,1/4)w=(3/4,1/4), the aggregate common reward is rw(a1,a2) r^w(a_1,a_2) =34r1(a1,a2)+14r2(a1,a2) = 34r_1(a_1,a_2)+ 14r_2(a_1,a_2) =34a1+14a2. = 34a_1+ 14a_2. Consequently, rw(1,0)=34,rw(0,1)=14.r^w(1,0)= 34, r^w(0,1)= 14. For the deterministic policy π selecting (1,0)(1,0), the transformed policy g⋅πg·π selects (0,1)(0,1). Hence, V2,0g⋅π;ℳw=14≠34=V1,0π;ℳw.V_2,0^g·π;M_w= 14≠ 34=V_1,0^π;M_w. Policy-evaluation symmetry requires this identity for every policy, so this single counterexample is enough to exclude g. The only nonidentity admissible transformation g therefore fails the defining evaluation identity in the derived model, whose partition is 1,2\\1\,\2\\. Aggregation has split a structural agent type of ℳM. Case 2: Merging Structural Agent Types (Equal Weights). Take r1(a1,a2)=a1,r2(a1,a2)=a2+1.r_1(a_1,a_2)=a_1, r_2(a_1,a_2)=a_2+1. Transforming the deterministic policy that selects (0,0)(0,0) by g leaves it unchanged but gives V1,0π;ℳ=0V_1,0^π;M=0 and V2,0g⋅π;ℳ=1V_2,0^g·π;M=1. Evaluation equivariance would require these values to be equal, so g is not a policy-evaluation symmetry of ℳM. Because the admissible group contains only the identity and g, the partition of ℳM is 1,2\\1\,\2\\. With w=(1,1)w=(1,1), however, the aggregate common reward is rw(a1,a2) r^w(a_1,a_2) =r1(a1,a2)+r2(a1,a2) =r_1(a_1,a_2)+r_2(a_1,a_2) =a1+(a2+1) =a_1+(a_2+1) =a1+a2+1, =a_1+a_2+1, which is invariant under g. The singleton dynamics and observations are invariant as well, so g is a componentwise environment automorphism, hence a policy-evaluation symmetry, in ℳwM_w. Its partition is 1,2\\1,2\\. Aggregation has merged the two source structural agent types. Case 3: Merging Structural Agent Types (Unequal Weights). Take r1(a1,a2)=a1,r2(a1,a2)=12a2.r_1(a_1,a_2)=a_1, r_2(a_1,a_2)= 12a_2. For the deterministic policy π selecting (1,0)(1,0), the transformed policy g⋅πg·π selects (0,1)(0,1), and V2,0g⋅π;ℳ=12≠1=V1,0π;ℳ.V_2,0^g·π;M= 12≠ 1=V_1,0^π;M. Thus g∉Gℳevalg∉ G_M^eval, and the source partition is 1,2\\1\,\2\\. With w=(1/3,2/3)w=(1/3,2/3), the aggregate common reward is rw(a1,a2)=13r1(a1,a2)+23r2(a1,a2)=13(a1+a2),r^w(a_1,a_2)= 13r_1(a_1,a_2)+ 23r_2(a_1,a_2)= 13(a_1+a_2), which is invariant under g. The singleton dynamics and observations are also invariant, so g is a componentwise environment automorphism and hence a policy-evaluation symmetry of ℳwM_w. Its partition is 1,2\\1,2\\. Therefore, aggregation can merge distinct source structural agent types even when their weights differ. Cases 1–3 establish the three claimed outcomes. Case 1 and either Case 2 or Case 3 establish the two opposite failures of refinement, proving the final claim. ∎ Appendix E Detailed Comparisons to Prior Symmetry Frameworks Sections 4–6 define agent heterogeneity through the agent orbits of GℳevalG_M^eval. The comparisons below do not introduce additional structural agent types. They instead state how two prior symmetry frameworks relate to the preservation conditions used in this paper. E.1. Counting and Isomorphic Symmetry Braun et al. (2022) formulate counting symmetry and isomorphic symmetry for partitioned Dec-POMDPs. Counting symmetry makes the transition, common-reward, and observation functions invariant to within-partition permutations of action and observation assignments. Equivalently, those functions depend on the assignments only through their per-partition histograms. Isomorphic symmetry additionally requires these functions to factor into repeated identical templates and therefore implies counting symmetry after grounding, whereas the converse need not hold. Thus, the two notions constrain the Dec-POMDP model functions and, for isomorphic symmetry, their factorization. By contrast, applying our more general POSG definition to the resulting grounded Dec-POMDP gives a condition on its complete policy-evaluation operator: it requires ℰℳ(g⋅π)=g⋅ℰℳ(π)E_M(g·π)=g·E_M(π) for every decentralized policy. Lifted-model implication. Within Braun et al.’s framework, the implication relates two properties of a lifted model: lifted isomorphic factorization⇓counting symmetry after grounding. gatheredlifted isomorphic factorization\\[-2.0pt] \\[-2.0pt] counting symmetry after grounding. gathered Here, grounding instantiates the lifted factor templates for the individual agents. Isomorphic factorization creates identical copies of the same factor structure for all agents in each part of the lifted partition. Permuting agents within a part therefore only reorders identical factors, so the grounded transition, common-reward, and observation functions can be represented using within-partition counts. This is counting symmetry. The arrow is one-way: counting symmetry can hold even when the grounded model does not arise from the same repeated isomorphic factorization. Consequence for admissible transformations. To translate counting symmetry into our language, let ℐ=I1,…,IKI=\I_1,…,I_K\ be the lifted agent partition and set Hℐ=∏k=1KSym(Ik),ι:Hℐ↪ℛadm(ℳ),H^ℐ:=ι(Hℐ).H_I= _k=1^KSym(I_k), :H_I _adm(M), H_I:= (H_I). The group HℐH_I contains exactly the agent permutations σ that permute agents only within each part IkI_k. The map ι assigns every σ∈Hℐσ∈ H_I a complete admissible transformation ι(σ)∈ℛadm(ℳ) (σ) _adm(M), whose agent permutation is σ. We assume that ι is an injective homomorphism. Thus distinct within-partition permutations produce distinct admissible transformations, and composition is preserved: ι(σ1σ2)=ι(σ1)ι(σ2) ( _1 _2)= ( _1) ( _2). Consequently, H^ℐ=ι(σ):σ∈Hℐ H_I=\ (σ):σ∈ H_I\ is a subgroup of ℛadm(ℳ)R_adm(M) that is isomorphic to HℐH_I. This embedding alone supplies only admissible transformations. To make them componentwise environment automorphisms, assume in addition that every ι(σ) (σ) has the identity state map and bijectively reindexes every grounded transition, observation, and additive common-reward factor into an equal instance of the same factor template, with no asymmetric extra factor. These assumptions give the componentwise preservation equations in Equations (5)–(7). Therefore, H^ℐ≤Autenv(ℳ)≤Gℳeval,ℐ=(H^ℐ)⪯eval(ℳ). H_I _env(M)≤ G_M^eval, =P( H_I) _eval(M). The first inclusion follows from the stated componentwise preservation assumptions, and the second follows from Theorem 5.2. Because the agent component of ι(σ) (σ) is σ, the orbits of H^ℐ H_I are exactly I1,…,IKI_1,…,I_K. Hence, each lifted partition part is contained in one structural agent type because H^ℐ≤Gℳeval H_I≤ G_M^eval. The containment may be strict because GℳevalG_M^eval may contain additional symmetries that connect agents from different lifted partition parts. Counting symmetry is thus a sufficient condition for this particular subgroup of componentwise environment automorphisms under the stated grounding assumptions. It is not a separate structural-type definition and does not claim to recover every componentwise environment automorphism. Since each lifted transformation has the identity state map, it automatically preserves ρ0 _0, without any additional restriction on the initial distribution. Because the initial joint history is ()N()^N, each initial state–joint-history pair (s0,()N)(s_0,()^N) in Equation (2) is preserved as well. These facts are needed when deriving identities for Ji(π)J_i(π), not for the subgroup relation H^ℐ≤Gℳeval H_I≤ G_M^eval. Counting symmetry does not imply the repeated additive factorization considered here for a partition with one part, even when both notions use the same lifted partition. Consider a one-stage, two-agent Dec-POMDP with state space =s⋆S=\s_ \, binary action spaces 1=2=0,1A_1=A_2=\0,1\, singleton observation spaces, deterministic self-transition, and common coordination reward rcom(s⋆,(a1,a2),s⋆)=a1=a2.r^com(s_ ,(a_1,a_2),s_ )=1\a_1=a_2\. For the lifted partition with one part, ℐ=1,2I=\\1,2\\, both agents belong to the same partition part. The reward equals 11 for the action histograms (2,0)(2,0) and (0,2)(0,2), and 00 for (1,1)(1,1). It therefore has counting symmetry. The admissible transformation whose agent permutation swaps the agents is also a componentwise environment automorphism and hence a policy-evaluation symmetry. However, because the model has only the fixed state s⋆s_ , abbreviate rcom(s⋆,(a1,a2),s⋆)r^com(s_ ,(a_1,a_2),s_ ) by rcom(a1,a2)r^com(a_1,a_2). For this same partition with one part, the repeated additive factorization considered here uses the same local factor template u for both agents: rcom(a1,a2)=c+u(a1)+u(a2)r^com(a_1,a_2)=c+u(a_1)+u(a_2). The shared function u is the repeated template associated with the only part 1,2\1,2\. This form would require rcom(0,0)+rcom(1,1)=rcom(0,1)+rcom(1,0),r^com(0,0)+r^com(1,1)=r^com(0,1)+r^com(1,0), because both sides would equal 2c+2u(0)+2u(1)2c+2u(0)+2u(1). Although the coordination reward satisfies counting symmetry, the left-hand side is 1+1=21+1=2, whereas the right-hand side is 0+0=00+0=0. Hence, no choices of c and u give this reward in the stated repeated additive form. Thus counting symmetry does not imply this repeated additive factorization for a partition with one part. More generally, policy-evaluation symmetry does not by itself provide the repeated lifted factor structure used to obtain the compact representation and tractability guarantees for lifted isomorphic models. Section E.1.1 gives the factor-reindexing proof and the proof that this example lacks the stated factorization for a partition with one part. E.1.1. Proofs of the lifted-model comparison The first proposition makes the grounding assumptions explicit; the second establishes the same-partition non-converse. Proposition E.1 (Lifted symmetry as a sufficient condition). Let ℐ=I1,…,IKI=\I_1,…,I_K\ be an agent partition and let Hℐ=∏k=1KSym(Ik).H_I= _k=1^KSym(I_k). Suppose a finite Dec-POMDP grounding admits an injective homomorphism ι:Hℐ⟶ℛadm(ℳ) :H_I _adm(M) whose image consists of transformations with the corresponding agent permutation, identity state map, and corresponding action and observation coordinate maps. Suppose also that every transformation in the image bijectively reindexes all grounded transition, observation, and additive common-reward factor instances into instances of the same templates, with no asymmetric extra factors. Writing H^ℐ=ι(Hℐ) H_I= (H_I), we then have H^ℐ≤Autenv(ℳ)≤Gℳeval,ℐ=(H^ℐ)⪯(Gℳeval). H_I _env(M)≤ G_M^eval, =P( H_I) (G_M^eval). Because the state map is the identity and the initial history is empty, the same transformations preserve the initial distribution. Proof. Fix a within-partition permutation σ∈Hℐσ∈ H_I and its complete transformation ι(σ) (σ). By assumption, it merely reorders the finitely many grounded factors within each factor product defining a transition or observation probability and within the factor sum defining the common reward. Every factor is matched with an equal instance of the same template. Reordering a finite product or sum does not change its value. Thus ι(σ) (σ) preserves the grounded transition distribution, observation distribution, and reward componentwise. Because this argument holds for every σ, H^ℐ≤Autenv(ℳ) H_I _env(M). Theorem 5.2 then gives Autenv(ℳ)≤GℳevalAut_env(M)≤ G_M^eval. We next show that the agent orbits of H^ℐ H_I are exactly the parts of ℐI. Fix a part IkI_k and an agent i∈Iki∈ I_k. Every g∈H^ℐg∈ H_I has the form g=ι(σ)g= (σ) for some σ∈Hℐσ∈ H_I, with agent permutation σg=σ _g=σ. Since σ permutes agents only within each part, σg(i)∈Ik _g(i)∈ I_k. Therefore, σg(i):g∈H^ℐ⊆Ik.\ _g(i):g∈ H_I\ I_k. Conversely, take any j∈Ikj∈ I_k. The permutation that exchanges i and j and fixes all other agents belongs to HℐH_I, because it acts only within IkI_k; if j=ij=i, use the identity permutation. For this permutation σ, its image ι(σ)∈H^ℐ (σ)∈ H_I satisfies σι(σ)(i)=σ(i)=j _ (σ)(i)=σ(i)=j. Thus every agent in IkI_k belongs to the orbit of i, proving the reverse containment. Hence, σg(i):g∈H^ℐ=Ik.\ _g(i):g∈ H_I\=I_k. Since this holds for every k and every i∈Iki∈ I_k, the orbit partition is (H^ℐ)=ℐP( H_I)=I. To establish the refinement, use the inclusion H^ℐ≤Gℳeval H_I≤ G_M^eval proved above. Every transformation used to connect two agents in IkI_k therefore also belongs to GℳevalG_M^eval. Consequently, each part IkI_k is contained in one GℳevalG_M^eval-orbit, which is one structural agent type. By the definition of partition refinement, as in Proposition B.3, this gives ℐ=(H^ℐ)⪯(Gℳeval).I=P( H_I) (G_M^eval). Finally, the identity state map fixes the initial state coordinate and every transformation fixes the empty initial history. Hence each transformation in the image preserves the initial distribution as claimed. ∎ Proposition E.2 (Same-partition non-converse). In the one-stage, two-agent common-reward model with binary actions and R(a1,a2)=a1=a2,R(a_1,a_2)=1\a_1=a_2\, the candidate partition with one part, 1,2\\1,2\\, has counting symmetry, and the transformation whose agent permutation swaps the two agents is a componentwise environment automorphism and therefore a policy-evaluation symmetry. However, there are no constant c and repeated local contribution u such that R(a1,a2)=c+u(a1)+u(a2).R(a_1,a_2)=c+u(a_1)+u(a_2). Proof. The reward is determined by the action histogram for the only partition part: it is 11 for (2,0)(2,0) and (0,2)(0,2), and 00 for (1,1)(1,1). Together with the singleton state and observation spaces and deterministic self-transition, this proves counting symmetry. The reward is therefore unchanged by exchanging the two action coordinates, while every other component is also unchanged. The corresponding transformation, whose agent permutation swaps the two agents, is a componentwise environment automorphism, and Theorem 5.2 shows that it is a policy-evaluation symmetry. If the repeated additive form held, then R(0,0)+R(1,1) R(0,0)+R(1,1) =[c+2u(0)]+[c+2u(1)] =[c+2u(0)]+[c+2u(1)] =2[c+u(0)+u(1)]=R(0,1)+R(1,0). =2[c+u(0)+u(1)]=R(0,1)+R(1,0). For the coordination reward, the left side is 22 and the right side is 00, a contradiction. This rules out the stated repeated additive reward factorization for a partition with one part. It does not rule out a partition into singleton parts, which separates the agents in the lifted representation. ∎ E.2. Expected Return Symmetry An expected return symmetry (ERS) is defined through self-play-optimal Boltzmann policies at a fixed temperature α>0α>0 (Muglich et al., 2025). We compare the two notions on their shared subclass of finite-horizon Dec-POMDPs: initial histories are empty, local action spaces are fixed, all agents have a common reward function, and the observation distribution factorizes as Z(o′∣s′,a)=∏iUi(oi′∣s′,a)Z(o s ,a)= _iU_i(o_i s ,a). Let Ψ denote the ambient transformation group used by ERS. We identify each of its elements with the type-compatible transformation g=(idN,ϕg,(ϕg,i)i∈N,(ϕg,i)i∈N),g= (id_N, _g^S,( _g,i^A)_i∈ N,( _g,i^O)_i∈ N ), where ϕg:→ _g^S:S , ϕg,i:i→i _g,i^A:A_i _i, and ϕg,i:i→i _g,i^O:O_i _i are bijections. The group Ψ contains all tuples of this form. Thus, Ψ fixes the agent indices. Under this identification, Ψ and ℛadm(ℳ)R_adm(M) are groups of type-compatible transformations on the same model, so their intersection is well defined. They act on decentralized policies by the policy-transformation rule in Equation (3). Let Πα(ℳ) ^α(M) be the policies satisfying the Boltzmann condition at every local history, stated explicitly in Section E.2.1, and let Π∗α(ℳ)=argmaxπ∈Πα(ℳ)Jℳ(π), _*^α(M)= *arg\,max_π∈ ^α(M)J^M(π), where Jℳ(π)J^M(π) is the common return under the initial distribution. We compare the two notions only on Ψ∩ℛadm(ℳ) _adm(M), whose elements are admissible in both formalisms. Throughout this subsection, the restricted ERS group is expressed, as follows: ΦERα(ℳ)≔g∈Ψ∩ℛadm(ℳ):g⋅π:π∈Π∗α(ℳ)=Π∗α(ℳ). _ER^α(M) \g∈ _adm(M):\;\g·π:π∈ _*^α(M)\= _*^α(M) \. Here, g⋅π:π∈Π∗α(ℳ)\g·π:π∈ _*^α(M)\ is the image of the entire self-play-optimal Boltzmann policy set under g. The equality therefore requires g to map this set onto itself, although it may map one member to a different member. Because the state, action, and observation spaces are finite, the common transformation domain is a finite group. The set equality is consequently equivalent to the pointwise condition used by Muglich et al. (2025), namely g⋅π∈Π∗α(ℳ)g·π∈ _*^α(M) for every π∈Π∗α(ℳ)π∈ _*^α(M). Thus, ERS concerns a selected optimal Boltzmann policy set and its local action-value conditions. By contrast, policy-evaluation symmetry preserves complete policy evaluation under a type-compatible transformation for every decentralized policy and may have a nonidentity agent permutation. Proposition E.3 (Class-level two-way non-implication). For every α>0α>0, there are finite Dec-POMDPs ℳa,ℳbM_a,M_b and transformations ga,gbg_a,g_b admitted by both formalisms such that ga∈ΦERα(ℳa)∖Gℳaeval,ρ0,gb∈Gℳbeval,ρ0∖ΦERα(ℳb).g_a∈ _ER^α(M_a) G_M_a^eval, _0, g_b∈ G_M_b^eval, _0 _ER^α(M_b). Hence neither condition implies the other across the common model class. Proof sketch. The proposition gives two counterexamples over the common model class. It does not claim that both set differences are nonempty for every fixed Dec-POMDP. In ℳaM_a, the uniform policy is the unique self-play-optimal Boltzmann policy. A within-agent action relabeling fixes this singleton set but changes the return of a deterministic policy outside Πα ^α. It is therefore an ERS transformation but not a policy-evaluation symmetry. In ℳbM_b, a within-agent observation relabeling satisfies the value-transformation identity in Definition 4.1 for every decentralized policy after transforming the policy and local histories. However, it exchanges observations with different conditional local action-value gaps, so it maps the unique Boltzmann policy to a policy that violates Boltzmann consistency. Both transformations have the identity state map and therefore preserve the corresponding initial distribution. Section E.2.1 gives both constructions. To state the exact additional condition, let Qiπ(hit,ai)Q_i^π(h_i^t,a_i) be the conditional expected return-to-go when agent i’s current action is fixed to aia_i, while the other agents’ current actions and all later actions follow π. Consider g∈Gℳeval,ρ0∩Ψg∈ G_M^eval, _0∩ . Assume that Φg,iℋ,t(hit) _g,i^H,t(h_i^t) lies in the paired local-history domain, ϕg,i _g,i^A bijects the corresponding legal-action sets, and both local action-value vectors are defined. Proposition E.4 shows that g∈ΦERα(ℳ)g∈ _ER^α(M) if and only if, for every π∈Π∗α(ℳ)π∈ _*^α(M), agent i, time step t, and local history hith_i^t, there is a constant cg,π,i,hitc_g,π,i,h_i^t, independent of aia_i, such that: Qig⋅π(Φg,iℋ,t(hit),ϕg,i(ai))=Qiπ(hit,ai)+cg,π,i,hitQ_i^g·π ( _g,i^H,t(h_i^t), _g,i^A(a_i) )=Q_i^π(h_i^t,a_i)+c_g,π,i,h_i^t for every legal aia_i. The constant is exactly the freedom that leaves a softmax distribution unchanged. If, more strongly, such a g is also a componentwise environment automorphism, the constant is zero at histories having positive probability under the paired policies. At an off-path history, meaning a history with zero probability under the relevant policy, the same conclusion requires one globally fixed belief and local-Q convention that is equivariant under the transformations being compared. Because ERS as defined by Muglich et al. (2025) fixes agent indices, it does not relate distinct agents and therefore cannot replace the structural agent types defined in this paper. Those types remain the agent orbits of the policy-evaluation symmetry group GℳevalG_M^eval, as in Definition 4.2. E.2.1. Boltzmann condition and comparison proofs For the proofs below, fix a temperature α>0α>0 and use the common admissible transformation domain defined above. We abbreviate Πα(ℳ) ^α(M), Π∗α(ℳ) _*^α(M), and Jℳ(π)J^M(π) by Πα ^α, Π∗α _*^α, and J(π)J(π), respectively. Recall that Πα ^α contains the policies satisfying the Boltzmann condition πit(ai∣hit)=exp(Qiπ(hit,ai)/α)∑bi∈iexp(Qiπ(hit,bi)/α). _i^t(a_i h_i^t)= (Q_i^π(h_i^t,a_i)/α) _b_i _i (Q_i^π(h_i^t,b_i)/α). The local action value Qiπ(hit,ai)Q_i^π(h_i^t,a_i) is the conditional expected return-to-go after local history hith_i^t when agent i’s current action is fixed to aia_i, while the other current actions and all later actions follow π. At a zero-probability history it uses the single declared off-path belief and local-Q convention discussed below. Proof of Proposition E.3. ERS without policy-evaluation symmetry. Choose 0<ε<2α0< <2α. Let ℳaM_a be a one-stage, two-agent Dec-POMDP with one state, singleton observations, binary actions, deterministic dynamics, and common reward R(a)=ε 1a1=a2.R(a)= \,1\a_1=a_2\. If agent i selects action 11 with probability pip_i, then against an agent selecting action 11 with probability q, Qiπ((),1)=εq,Qiπ((),0)=ε(1−q).Q_i^π((),1)= q, Q_i^π((),0)= (1-q). Boltzmann self-consistency is therefore p1=F(p2),p2=F(p1),F(q)=11+exp[−ε(2q−1)/α].p_1=F(p_2), p_2=F(p_1), F(q)= 11+ [- (2q-1)/α]. Since |F′(q)|≤ε2α<1,|F (q)|≤ 2α<1, the joint response map (p1,p2)↦(F(p2),F(p1))(p_1,p_2) (F(p_2),F(p_1)) is a contraction in the sup norm. Moreover, F(1/2)=1/2F(1/2)=1/2, so (1/2,1/2)(1/2,1/2) is a fixed point. To see directly that it is the only one, let p be any other fixed point and let L=ε/(2α)<1L= /(2α)<1. The contraction bound gives ∥p−(1/2,1/2)∥∞≤L∥p−(1/2,1/2)∥∞, p-(1/2,1/2) _∞≤ L p-(1/2,1/2) _∞, which forces the norm to be zero. Therefore Πα=Π∗α=πu, ^α= _*^α=\π^u\, where πuπ^u is the uniform product policy. Let gag_a swap the two action labels of agent 11 and fix all other coordinates. Declare e,ga\e,g_a\ admissible. This within-agent action relabeling lies in Ψ and fixes πuπ^u, hence ga∈ΦERα(ℳa).g_a∈ _ER^α(M_a). For the deterministic policy π00π^00, however, Jℳa(π00)=ε,Jℳa(ga⋅π00)=0.J^M_a(π^00)= , J^M_a(g_a·π^00)=0. The transformation fixes the agent indices and the unique initial pair, so return equivariance would require these two returns to be equal. Their inequality therefore violates policy-evaluation symmetry, and ga∉Gℳaeval,ρ0.g_a∉ G_M_a^eval, _0. Policy-evaluation symmetry without ERS. Let ℳbM_b be a two-stage, two-agent Dec-POMDP. Use states u,z\u,z\. Agent 11 has actions 0,1\0,1\ and observations c,x,y\c,x,y\. Agent 22 has singleton action and observation sets ⋆\ \ and ⊥\ \. Set γ=1γ=1, let the initial distribution be δu _u, and abbreviate joint action (a,⋆)(a, ) by a. For either action, take P(u∣u,a)=P(z∣u,a)=12,P(z∣z,a)=1.P(u u,a)=P(z u,a)= 12, P(z z,a)=1. Agent 22 always observes ⊥ , while agent 11’s action-independent observation probabilities are cxyu1/52/52/5z1/51/53/5 array[]c|c&c&x&y\\ u&1/5&2/5&2/5\\ z&1/5&1/5&3/5 array Give both agents the common successor-state reward R(s′,(a,⋆))=2 1a=0,s′=u.R(s ,(a, ))=2\,1\a=0,\ s =u\. Let gbg_b exchange agent 11’s observation labels x and y and fix every other coordinate. Declare e,gb\e,g_b\ admissible. This within-agent observation relabeling lies in Ψ . For a0∈0,1a^0∈\0,1\, o∈c,x,yo∈\c,x,y\, and either common-reward coordinate k, write h1(a0,o)=((a0,o),(⋆,⊥)),pa0,o=π11(0∣(a0,o)).h^1(a^0,o)= ((a^0,o),( , ) ), p_a^0,o= _1^1(0 (a^0,o)). At t=1t=1, Vk,1π(u,h1(a0,o))=pa0,o,Vk,1π(z,h1(a0,o))=0.V_k,1^π (u,h^1(a^0,o) )=p_a^0,o, V_k,1^π (z,h^1(a^0,o) )=0. Indeed, from u, choosing action 00 gives reward 22 when the next state is u, which occurs with probability 1/21/2, and choosing action 11 gives zero. From z, both actions give zero. The policy transformation exchanges pa0,xp_a^0,x and pa0,yp_a^0,y. For example, Vk,1gb⋅π(u,gb⋅h1(a0,x))=pa0,x=Vk,1π(u,h1(a0,x)).V_k,1^g_b·π (u,g_b· h^1(a^0,x) )=p_a^0,x=V_k,1^π (u,h^1(a^0,x) ). The same calculation applies to histories ending in y, while c is fixed and both values from z are zero. Hence the defining value-transformation identity holds at every state–joint-history pair at t=1t=1. At the initial time step t=0t=0, putting q=π10(0∣())q= _1^0(0 ()) gives Vk,0π(u,()N)=q+12∑a0∈0,1π10(a0∣())[15pa0,c+25pa0,x+25pa0,y].V_k,0^π(u,()^N)=q+ 12 _a^0∈\0,1\ _1^0(a^0 ()) [ 15p_a^0,c+ 25p_a^0,x+ 25p_a^0,y ]. Exchanging x and y leaves this expression unchanged. From state z, every present and future reward is zero. Together with the zero values at t=2t=2, these calculations cover all time steps and valid state–joint-history pairs. The transformation gbg_b also fixes the state, so it preserves the initial distribution δu _u. Therefore gb∈Gℳbeval,ρ0.g_b∈ G_M_b^eval, _0. The local action values used by the Boltzmann condition instead condition on agent 11’s observation. For example, after either initial action a0a^0, Pr(u∣a0,x)=(1/2)(2/5)(1/2)(2/5)+(1/2)(1/5)=23. (u a^0,x)= (1/2)(2/5)(1/2)(2/5)+(1/2)(1/5)= 23. The same Bayes calculation gives Pr(u∣a0,y)=25,Pr(u∣a0,c)=12. (u a^0,y)= 25, (u a^0,c)= 12. These posterior probabilities are also the action-value gaps at t=1t=1: conditioned on a belief assigning probability p to u, action 00 has expected reward 2p(1/2)=p2p(1/2)=p, whereas action 11 has value zero. Thus the required Boltzmann probabilities of action 00 after x and y are bx=e2/(3α)1+e2/(3α),by=e2/(5α)1+e2/(5α).b_x= e^2/(3α)1+e^2/(3α), b_y= e^2/(5α)1+e^2/(5α). Every initial action and every resulting observation at t=1t=1 have positive probability under a Boltzmann policy, so the displayed probabilities uniquely fix every rule at t=1t=1. The posterior calculation, and hence each of these fixed rules, is independent of the initial action. Since the transition and observation distributions and the decision rules at t=1t=1 are independent of the initial action, the expected reward at t=1t=1 is the same after initial actions 00 and 11. Their immediate expected rewards differ by 2(1/2)=12(1/2)=1, which uniquely fixes the Boltzmann rule at the initial time step as well. Hence Πα=Π∗α ^α= _*^α is a singleton. Since the logistic function is strictly increasing, bx>byb_x>b_y. At a history ending in x, the transformed policy uses byb_y, although Boltzmann self-consistency requires bxb_x. Therefore gb∉ΦERα(ℳb),g_b∉ _ER^α(M_b), which proves the reverse non-implication. ∎ Proposition E.4 (Local action-value bridge). Let g be a transformation such that g∈Gℳeval,ρ0∩Ψ.g∈ G_M^eval, _0∩ . Assume that g preserves the paired local-history domain, matches the legal-action sets bijectively, and that both local action-value vectors are defined. Then g∈ΦERα(ℳ)g∈ _ER^α(M) if and only if, for every π∈Π∗απ∈ _*^α, i,t,hiti,t,h_i^t, there is an action-independent constant cg,π,i,hitc_g,π,i,h_i^t such that Qig⋅π(Φg,iℋ,t(hit),ϕg,i(ai))=Qiπ(hit,ai)+cg,π,i,hitQ_i^g·π ( _g,i^H,t(h_i^t), _g,i^A(a_i) )=Q_i^π(h_i^t,a_i)+c_g,π,i,h_i^t for every legal aia_i. If, in addition, g∈Autenv(ℳ)g _env(M), then the identity holds with constant zero at positive-probability paired histories. The same conclusion at off-path histories requires a globally fixed belief and local-Q convention that is equivariant under the relevant group. Proof. Because g is an initial-distribution-preserving policy-evaluation symmetry and g∈Ψg∈ fixes agent indices, J(g⋅π)=J(π)J(g·π)=J(π) for every policy. Thus, for π∈Π∗απ∈ _*^α, the transformed policy is again optimal within Πα ^α exactly when it remains in Πα ^α. The policy transformation preserves the action-probability vector after reindexing its action coordinates. Two finite Boltzmann vectors agree exactly when their action values differ by one action-independent constant. Write the corresponding action-value vectors as q and q′q , indexed by corresponding legal actions. For a singleton action set the claim is immediate. Otherwise, equality of the probability ratios for any two actions a,ba,b gives e(qa′−qb′)/α=e(qa−qb)/α,e^(q _a-q _b)/α=e^(q_a-q_b)/α, and hence qa′−qa=qb′−qbq _a-q_a=q _b-q_b. Thus the difference is the same for every action. Conversely, if qa′=qa+cq _a=q_a+c for every action a, then eqa′/α∑beqb′/α e^q _a/α _be^q _b/α =ec/αeqa/αec/α∑beqb/α = e^c/αe^q_a/αe^c/α _be^q_b/α =eqa/α∑beqb/α. = e^q_a/α _be^q_b/α. The common factor therefore cancels, giving the same action probabilities. To prove necessity, suppose that g∈ΦERα(ℳ)g∈ _ER^α(M). For every π∈Π∗απ∈ _*^α, its image g⋅πg·π also belongs to Π∗α _*^α, so both policies satisfy the Boltzmann condition. Their action probabilities agree after reindexing the action coordinates. Applying the probability-ratio argument at each paired local history gives the stated action-independent difference between their local action values. To prove sufficiency, assume the stated local action-value identity for every π∈Π∗απ∈ _*^α and every paired local history. Fix such a policy π. At each paired history, the constant-shift calculation shows that its reindexed action probabilities are the Boltzmann probabilities determined by Qig⋅πQ_i^g·π. These are precisely the probabilities assigned by g⋅πg·π, so the transformed policy satisfies the Boltzmann condition at every local history. Thus g⋅π∈Παg·π∈ ^α. Since J(g⋅π)=J(π)J(g·π)=J(π), it attains the same maximum return within Πα ^α as π, and hence belongs to Π∗α _*^α. Since π was arbitrary, this proves g⋅π:π∈Π∗α⊆Π∗α.\g·π:π∈ _*^α\ _*^α. To prove the reverse inclusion, we must show that every policy in Π∗α _*^α is the image of another policy in that set. Because g belongs to the finite group Ψ , there is an integer m≥1m≥ 1 such that gm=eg^m=e, where e is the identity transformation. Take any π∈Π∗απ∈ _*^α and define π~=gm−1⋅π. π=g^m-1·π. The inclusion already proved means that each application of g keeps a policy in Π∗α _*^α. Applying it m−1m-1 times therefore gives π~∈Π∗α π∈ _*^α; when m=1m=1, this simply means π~=π π=π. Moreover, the policy action law gives g⋅π~=g⋅(gm−1⋅π)=gm⋅π=π.g· π=g·(g^m-1·π)=g^m·π=π. Thus every π∈Π∗απ∈ _*^α has a preimage in Π∗α _*^α, which establishes the reverse inclusion. Combining the two inclusions gives g⋅π:π∈Π∗α=Π∗α.\g·π:π∈ _*^α\= _*^α. This is exactly the set-preservation requirement in the definition of ΦERα(ℳ) _ER^α(M), completing the equivalence proof. For the zero-constant statement, pair each trajectory under π with its transformed counterpart under g⋅πg·π. Componentwise preservation, the policy transformation, and preservation of the initial distribution give the paired trajectories the same probability and reward. Conditioning at a positive-probability paired history preserves this correspondence. It also persists when the current local action is fixed and all other current and later actions follow the respective policies. The two conditional expected returns-to-go are therefore equall, such that: Qig⋅π(Φg,iℋ,t(hit),ϕg,i(ai))=Qiπ(hit,ai).Q_i^g·π ( _g,i^H,t(h_i^t), _g,i^A(a_i) )=Q_i^π(h_i^t,a_i). Positive reachability makes the Bayesian conditional law unambiguous. At a zero-probability history, this reasoning applies only when the single off-path belief and local-Q convention is itself equivariant. A convention may assign well-defined beliefs and local action values at every zero-probability history without making these assignments consistent with the transformation g (see the below explanation for details). Therefore, well-definedness alone does not establish the local action-value equality at those histories. ∎ Clarification on Off-Path Histories. An off-path history can occur even when every action has positive probability. For example, consider a two-stage, two-agent Dec-POMDP with states L,R\L,R\, a uniform initial distribution, and transitions that leave the state unchanged. Agent 11 has actions 0,1\0,1\ and observations x,y\x,y\, but always observes x in either state; agent 22 has singleton action and observation sets. The common reward is 11 when the state and agent 11’s action are (L,0)(L,0) or (R,1)(R,1), and 00 otherwise. At t=1t=1, the history h11=(0,y)h_1^1=(0,y) has probability zero under every policy, because y is impossible. To evaluate an action after this history, agent 11 needs a conditional belief about the state. However, the usual conditional-probability formula would require the undefined ratio, such that: Prπ(s1=L,a10=0,o11=y)Prπ(a10=0,o11=y)=00. _π(s_1=L,\,a_1^0=0,\,o_1^1=y) _π(a_1^0=0,\,o_1^1=y)= 00. Thus, the model and policy do not determine which belief to use at this history. To define the local action values and impose the Boltzmann condition at every local history, we must declare a convention that assigns a belief at such zero-probability histories. For example, at t=1t=1, assigning probability one to L gives values 11 and 00 for actions 00 and 11, while assigning probability one to R reverses these values. These are alternative extensions to an impossible history, and neither assignment is determined by Bayes’ rule. Let g exchange L with R and agent 11’s actions 00 with 11, while fixing all other coordinates, and take e,g\e,g\ as the admissible group. This transformation preserves the transition, observation, and common-reward functions and the initial distribution, and maps (0,y)(0,y) to (1,y)(1,y). Suppose a fixed convention assigns probability one to L at every zero-probability local history of agent 11, under every policy. Since t=1t=1 is the final decision time, the resulting local action values satisfy Q1π((0,y),0)=1,Q1g⋅π((1,y),1)=0.Q_1^π((0,y),0)=1, Q_1^g·π((1,y),1)=0. Thus, this well-defined convention does not preserve the local action-value equality. An equivariant convention must instead assign probability one to R at the transformed history under g⋅πg·π whenever it assigns probability one to L at the source history under π. This issue concerns the conditional local action values used in the ERS comparison. The complete values Vi,tπ(s,ht)V_i,t^π(s,h^t) used to define our symmetry group are specified directly by Equation (1), including at unreachable state–joint-history pairs, and require no such belief convention.