PaperlayerView exact revision on arXiv

Source-linked AI summary

On Symmetry for Characterizing Agent Heterogeneity in Multi-Agent Systems

Jianhong Wang, Jonathan Lawry

arXiv:2610.18538v1cs.MAcs.AI

TL;DR

Existing criteria do not provide a unified structural test for agent heterogeneity, despite its relevance to policy representation design. The paper defines policy-evaluation symmetries for finite-horizon POSGs and uses their group orbits to classify structural agent types. It shows that componentwise automorphisms suffice but are not necessary, and that agents can remain structurally heterogeneous under a common reward.

  • Problem

    Existing criteria provide no unified structural test for agent heterogeneity, which can inform the design of shared and agent-specific policy representations.

    Source: §1 · p. 1

  • Method

    For finite-horizon POSGs, the paper defines symmetry by whether complete evaluation commutes with an admissible transformation for every decentralized policy, then classifies agents by group orbits.

    Source: §1 · p. 1, §4 · p. 3

  • Results

    Componentwise environment automorphisms guarantee policy-evaluation symmetry but are not necessary, and cooperative Dec-POMDP agents can have different structural types despite a common reward.

    Source: §1 · p. 1, §8 · p. 8

  • Takeaways & Limitations

    Structural types are determined by all-policy evaluation rather than a selected policy or initial-state distribution, while shared objectives alone do not guarantee structural homogeneity.

    Source: §1 · p. 1, §8 · p. 8

    Expected-value symmetry can equate transformations that induce different trajectory or return distributions, and the framework does not establish optimal equivariant policies or learning improvements.

    Source: §8 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether symmetry can provide a unified structural test for agent heterogeneity, then defines transformations by whether they preserve complete policy evaluation. The resulting agent types are policy-independent, and the framework distinguishes sufficient componentwise preservation from the broader policy-evaluation criterion.

1 Introduction

  • The paper asks when compatible transformations can exchange agents without changing how every decentralized policy is evaluated.Characterizing differences among agents can inform the design of shared and agent-specific policies.Source: §1 · p. 1
  • Policy-evaluation symmetries form a group whose agent orbits define structural types, independent of the selected policy and initial-state distribution.One orbit corresponds to structural homogeneity; multiple orbits indicate heterogeneity.Source: §1 · p. 1
  • Componentwise preservation of transition, observation, and reward functions guarantees policy-evaluation symmetry, but the converse does not hold.The paper uses a finite two-stage POSG to show the policy-evaluation partition can be finer than the componentwise partition.Source: §1 · p. 1
  • Cooperative Dec-POMDP agents can have different structural types despite a common reward, and prescribed weighted aggregation has an exact value identity and symmetry-inheritance conditions.The framework also compares its criterion with existing heterogeneity categories and symmetry notions.Source: §1 · pp. 1–2

2 Related Work

Prior work classifies heterogeneity by agent properties and studies several notions of symmetry, but these approaches ask different questions from the paper’s all-policy evaluation criterion. The paper relates those approaches conditionally rather than treating them as equivalent definitions.

2.1 Taxonomies of Agent Heterogeneity

  • Bettini et al. [5] distinguish physical and behavioral heterogeneity, while system neural diversity measures behavior through average pairwise distances.Hu et al. [15] classify observation, response-transition, effect-transition, objective, and policy heterogeneity.Source: §2.1 · p. 2
  • The taxonomy-to-framework associations are conditional on the relevant property being represented in the POSG, and do not identify prior categories with structural agent types.Componentwise automorphisms guarantee a shared structural type, but their failure neither rules out policy-evaluation symmetry nor proves different types.Source: §2.1 · p. 2

2.2 Symmetry in Multi-Agent Systems

  • Normal-form and stochastic-game symmetry work studies payoff, structural, or minimax preservation, whereas this framework evaluates every decentralized policy in a partially observable game.These traditions motivate agent interchangeability as an orbit question without directly addressing the paper’s all-policy setting.Source: §2.2 · p. 2
  • Component-preserving model automorphisms are sufficient but not necessary for policy-evaluation symmetry; related work also uses symmetry for policy architectures, compact representations, or optimal Boltzmann policy sets.Those aims differ from defining solution-independent agent types through a group that preserves evaluation for every decentralized policy.Source: §2.2 · pp. 2–3

3 Model and Type-Compatible Transformations

The framework is set in a finite-horizon POSG with decentralized behavioral policies and complete value profiles over state–joint-history pairs. Type-compatible transformations relabel agents and their associated state, action, observation, and history coordinates while preserving the time index.

3 Model and Type-Compatible Transformations

  • The model is a finite-horizon POSG with finite nonempty agents, states, actions, and observations, transition and observation functions, individual rewards, and an initial-state distribution.The initial state is drawn from ρ0, and each agent begins with an empty local history.Source: §3 · p. 3
  • The policy domain consists of decentralized behavioral product policies with independent local randomization, excluding a common random signal.Complete policy evaluation assigns values even to valid state–joint-history pairs unreachable under a selected policy, using a Bellman recursion that includes the final transition reward.Source: §3 · p. 3
  • A type-compatible transformation is a complete tuple of compatible agent and component maps that relabels joint actions and moves each agent’s local history to its transformed coordinate.The induced state–joint-history map preserves the time index and does not itself perform a state transition.Source: §3 · p. 3
  • An application specifies an admissible subgroup of candidate transformations, but membership alone does not establish environment or policy-evaluation symmetry.The induced transformation relabels and reindexes local policies, preserving decentralized product form; allowing correlated policies could change the symmetry group and agent types.Source: §3 · p. 3

4 Policy-Evaluation Symmetry and Structural Agent Types

A policy-evaluation symmetry is an admissible transformation under which transforming any decentralized policy and then evaluating it agrees with transforming its complete value profile. These symmetries form a group, and its agent orbits define structural types.

4 Policy-Evaluation Symmetry and Structural Agent Types

  • A policy-evaluation symmetry satisfies the evaluation identity for every policy, agent, time step, and valid state–joint-history input.The comparison is between a policy and its transformed policy; it does not require the original value profile to be invariant.Source: §4 · pp. 3–4
  • The orbits of the policy-evaluation symmetry group partition agents into structural types; one orbit is homogeneity, while multiple orbits are heterogeneity.This is a complete partition of the agents, not a label for just one type.Source: §4 · p. 4
  • Policy-evaluation symmetry does not require preserving the initial-state distribution, whereas expected-return equivariance under that distribution requires an additional preservation condition.The definition compares values at corresponding state–joint-history pairs.Source: §4 · p. 4
  • Equivariance of a selected policy is downstream of the symmetry group, and an equivariant policy has a correspondingly unchanged value profile.Value invariance for one selected policy does not establish the all-policy identity required for policy-evaluation symmetry.Source: §4 · p. 4

5 Componentwise Environment Automorphisms

Componentwise environment automorphisms preserve transition, observation, and reward functions separately, and every such automorphism is a policy-evaluation symmetry. The inclusion is strict in general, so componentwise tests can yield finer agent partitions.

5 Componentwise Environment Automorphisms

  • Componentwise environment automorphisms preserve the transition, observation, and reward functions separately.Source: §5 · p. 4
  • These automorphisms form a subgroup, and every one is a policy-evaluation symmetry whose agent orbits refine the structural agent partition.Source: §5 · pp. 4–5
  • A finite two-agent, two-stage POSG shows the inclusion can be strict: componentwise tests separate agents that policy evaluation groups together.The exchange changes some transition probabilities but preserves expected successor-state rewards and marginalized next-observation distributions, maintaining evaluation for every decentralized policy.Source: §5 · p. 5

6 Extension to Dec-POMDPs

The Dec-POMDP extension shows that a shared reward need not make agents structurally interchangeable. For weighted reward aggregation, the paper derives a value identity and conditions under which source symmetries are inherited, preserved, or merged.

6 Extension to Dec-POMDPs

  • A finite-horizon POSG with a shared reward is a Dec-POMDP, to which the policy-evaluation symmetry and agent-orbit framework applies.Source: §6 · p. 5, §6.1 · p. 5

6.1 General Common Rewards

  • A common reward does not guarantee interchangeable roles: agents can have multiple structural types, and homogeneity requires G_eval to act transitively on agents.Compatible action and observation bijections and symmetry of transition and observation distributions are not guaranteed by a common reward.Source: §6.1 · p. 5

6.2 Aggregate Common Rewards

  • The derived model retains the source POSG’s other components and assigns every agent the prescribed weighted aggregate of its individual rewards.Source: §6.2 · p. 5
  • Theorem 6.1 gives an exact weighted-value identity for the derived common-reward model.The proof uses backward induction on the Bellman recursion.Source: §6.2 · p. 5
  • Equal weights within each original structural type suffice for every source policy-evaluation symmetry to be inherited by the aggregated model.Source: §6.2 · p. 6
  • Under that condition, aggregation can preserve or merge original types but cannot split them; the derived model has no more types than the source.A structurally homogeneous source remains structurally homogeneous.Source: §6.2 · p. 6
  • Unequal weights within a type remove the inheritance guarantee, while aggregation can also merge source types, so unrestricted weights yield no universal partition refinement.Source: §6.2 · pp. 6–7
  • Because the source and derived models share the initial distribution, the value identity also yields an expected-return identity; preserving that distribution gives a further equivariance identity.Source: §6.2 · p. 7

7 Comparisons to Prior Symmetry Frameworks

The comparisons distinguish policy-evaluation symmetry from counting and isomorphic symmetry and from expected return symmetry. The frameworks have conditional relationships, but neither of the latter symmetry notions generally implies the other.

7 Comparisons to Prior Symmetry Frameworks

  • Under stated grounding assumptions, Braun et al.’s isomorphic symmetry yields counting symmetry and policy-evaluation symmetry, with the lifted partition refining structural agent types.Source: §7 · p. 7
  • Policy-evaluation symmetry alone does not guarantee the repeated additive factorization needed for Braun et al.’s compact representation and tractability results.Source: §7 · p. 7
  • On the shared finite-horizon Dec-POMDP subclass, neither expected return symmetry nor initial-distribution-preserving policy-evaluation symmetry implies the other in general.For a particular model, their symmetry sets may coincide or one may contain the other; expected return symmetry fixes agent indices and does not define structural agent types.Source: §7 · p. 7

8 Discussions and Framework Boundaries

The discussion separates policy-evaluation symmetry from initial-distribution-dependent returns, selected-policy behavior, and componentwise model preservation. It also states scope boundaries and identifies limits of what the framework establishes.

8 Discussions and Framework Boundaries

  • Policy-evaluation symmetry compares values at corresponding state–joint-history inputs, while expected-return equivariance additionally requires preservation of the initial distribution.Source: §8 · p. 7
  • Componentwise automorphisms are directly checkable sufficient conditions, but policy evaluation can remain symmetric even when transition distributions change.In the construction described, changed distributions preserve expected successor-state rewards and marginalized next-observation distributions.Source: §8 · p. 7
  • Policy-evaluation symmetry is independent of the learning mechanism because its evaluation identity must hold for every decentralized policy.Exploration noise that violates action-transformation compatibility can break equivariance of an already equivariant policy without changing the structural types.Source: §8 · pp. 7–8
  • The framework connects aggregate common rewards to social welfare, defined as the sum of individual payoffs, while motivating study of whether value-decomposition algorithms learn structural types.Source: §8 · p. 8
  • Structural homogeneity requires a transitive induced agent-permutation group, not every possible agent permutation; full permutation symmetry is stronger.Source: §8 · p. 8
  • The framework assumes finite spaces and horizon, exact expected-value evaluation, and decentralized behavioral product policies without shared randomness; no general symmetry-discovery or verification algorithm is introduced.Source: §8 · p. 8
  • Weighted aggregation is limited to fixed linear weights; infinite-horizon models and nonlinear or learned reward aggregation require separate formulations.Source: §8 · p. 8
  • Expected-value symmetry may identify transformations with different trajectory or return distributions, and the results do not establish an optimal equivariant policy or performance improvements.Source: §8 · p. 8

A Detailed Comparison of Heterogeneity Categories

The section distinguishes structural agent types, defined by transformations preserving complete policy evaluation, from taxonomies of particular differences and selected-policy behavior. It then relates componentwise tests, policy equivariance, and orbit-based classification, while noting what the core POSG representation can and cannot distinguish.

A Detailed Comparison of Heterogeneity Categories

  • Existing heterogeneity categories identify where agents differ, whereas this framework asks whether an admissible transformation preserves complete policy evaluation; these are conditional interpretations, not equivalent definitions.Componentwise preservation is sufficient for shared types, but its failure for one candidate transformation does not prove distinct types; absence of any admissible map does.Source: A Detailed Comparison of Heterogeneity… · p. 11

A.1 Physical Heterogeneity

  • Physical differences enter the classification only through their representation in the POSG; unequal action- or observation-space cardinalities preclude the required typed bijection.Equal cardinality permits a bijection but does not guarantee that the complete transformation is admissible.Source: §A.1 · p. 11

A.2 Observation Heterogeneity

  • Observation comparisons require transformed labels and compatible timing and conditioning conventions; failure of the componentwise observation test does not rule out a policy-evaluation symmetry.The application must explain how agent-local observation functions induce the joint observation distribution.Source: §A.2 · p. 11

A.3 Response- and Effect-Transition Heterogeneity

  • The core POSG’s undivided state and global transition distribution cannot identify whether a transition difference concerns an agent’s own updates, its effects on others, or both.An application-specific factorization can enable separate response- and effect-preservation tests, but that structure is not uniquely recoverable from the global transition distribution; restricting admissible transformations to respect it can refine orbit partitions.Source: §A.3 · pp. 11–12

A.4 Objective Heterogeneity

  • Objective heterogeneity is distinct from structural heterogeneity: a common reward does not ensure exchangeability, and aggregation can preserve, remove, or create symmetries depending on rewards and weights.The componentwise reward test compares functions after transforming agent, state, and action labels.Source: §A.4 · p. 12

A.5 Behavioral and Policy Heterogeneity

  • Policy equivariance compares local policies at histories and actions related by the chosen transformations; a selected policy can break a game symmetry without changing structural agent types.Different-looking policy tables can still be equivariant after agent, history, and action labels are transformed.Source: §A.5 · p. 12

A.6 Exact Classes and Graded Differences

  • Structural types are exact agent orbits, unlike graded behavioral or model distances, which can compare agents within or across types but do not replace the orbit partition.Orbit membership itself assigns no numerical degree of similarity; the framework separately classifies prior categories by the level they describe.Source: §A.6 · p. 12, §A.7 · p. 12

B.1 Induced actions

  • The proof establishes group actions on decentralized policies and value profiles, with transformed policies remaining decentralized and successive transformations composing consistently.These action laws support the subgroup result for policy-evaluation symmetries.Source: §B.1 · p. 13

B.2 Complete proof for the strictness example

The proof constructs a two-agent, two-stage POSG in which an agent swap preserves complete policy evaluation but no componentwise environment automorphism exchanges the agents. It also establishes subgroup and orbit facts and the reduction to payoff preservation in a one-stage normal-form game.

B.2 Complete proof for the strictness example

  • The example uses two agents, two stages, three states, binary action and observation sets, and the full group of type-compatible transformations.Its agent swap fixes state, action, and observation labels.Source: §B.2 · p. 13
  • The constructed agent swap preserves policy evaluation for every policy but is not a componentwise environment automorphism, establishing that the converse to the componentwise sufficiency result fails.The proof rules out other componentwise exchanges as well; all initial, transition, and observation probabilities are positive, so the separation is not due to unreachable histories.Source: §B.2 · p. 14

B.3 Subgroup, orbit, and normal-form facts

  • The policy-evaluation symmetry set is a subgroup, so it is closed under inverses; the proof also establishes subgroup closure with initial-distribution preservation.The inverse property is used to show that an evaluation-preserving transformation has an evaluation-preserving inverse.Source: §B.3 · p. 15
  • For any subgroup of admissible transformations, agents related by its permutations form equivalence classes, and enlarging the subgroup yields a coarser orbit partition.The classes are precisely the subgroup’s agent orbits.Source: §B.3 · p. 15
  • In a horizon-one embedding of a finite normal-form game, evaluation equivariance for every mixed product policy is equivalent to the corresponding payoff-preservation identity.The embedding uses one state, singleton observations, deterministic dynamics, and rewards equal to the game payoffs.Source: §B.3 · p. 15

C Proofs for Componentwise Environment Automorphisms

Componentwise environment automorphisms form a subgroup, and each is a policy-evaluation symmetry. The proof verifies inverse preservation of model components and uses backward induction to establish evaluation equivariance.

C Proofs for Componentwise Environment Automorphisms

  • Among componentwise automorphisms, those preserving the initial distribution also form a subgroup.The proof checks identity, composition, and inverse preservation of the initial distribution.Source: C Proofs for Componentwise Environment… · p. 16
  • Componentwise environment automorphisms are closed under composition, with the observation and reward calculations following the transition calculation.The identity preserves each component, and closure under composition establishes the subgroup property together with inverse closure.Source: C Proofs for Componentwise Environment… · p. 16
  • The inverse of a componentwise environment automorphism preserves transition, observation, and reward functions, completing the subgroup proof.The proof uses suitable inputs in the known preservation identities; the three identities hold for arbitrary states, actions, observations, and agents.Source: C Proofs for Componentwise Environment… · p. 16
  • Every componentwise environment automorphism is a policy-evaluation symmetry, so Autenv(M) is a subgroup of Geval(M).Backward induction establishes evaluation equivariance for every agent, policy, time step, and valid state–joint-history pair.Source: C Proofs for Componentwise Environment… · p. 17

D Extension to Dec-POMDPs

The Dec-POMDP extension relates common and weighted rewards to policy-evaluation symmetry and structural agent types. The comparisons show how counting symmetry and repeated factorization relate to this framework.

D Extension to Dec-POMDPs

  • A common reward does not ensure that agents share a structural type: value coordinates can be equal while the policy-evaluation symmetry group is not transitive.The common-reward example establishes equal values, but no policy-evaluation symmetry exchanges the agents.Source: D Extension to Dec-POMDPs · pp. 17–18
  • For every decentralized policy, each derived agent’s value equals the prescribed weighted sum of source-agent values.The identity follows by backward induction; the expected-return identity also holds without any symmetry assumption.Source: D Extension to Dec-POMDPs · pp. 18–19
  • Weight-preserving source symmetries transfer to the weighted-reward model under the stated conditions, including for componentwise environment automorphisms.The componentwise result uses unchanged transition and observation distributions and preservation of the aggregate reward.Source: D Extension to Dec-POMDPs · p. 19
  • Weighted reward aggregation can split or merge structural agent types, including merging distinct types when the weights differ.The one-stage examples establish splitting with unequal weights and merging with either equal or unequal weights.Source: D Extension to Dec-POMDPs · pp. 19–20

E.1 Counting and Isomorphic Symmetry

  • Isomorphic factorization implies counting symmetry after grounding, but counting symmetry need not imply repeated additive factorization.A one-part coordination-reward example has counting symmetry but cannot be represented in the stated repeated additive form.Source: §E.1 · pp. 20–21
  • Under the stated grounding assumptions, counting symmetry supplies a subgroup of componentwise automorphisms whose orbits refine structural agent types.The lifted transformations preserve the initial distribution because their state map is the identity and the initial history is empty.Source: §E.1 · p. 21

E.1.1 Proofs of the lifted-model comparison.

The lifted-model comparison gives conditions under which repeated factor templates induce policy-evaluation symmetry, while the expected-return comparison establishes that neither symmetry notion implies the other across the shared model class.

E.1.1 Proofs of the lifted-model comparison.

  • An injective lifted-partition embedding that reindexes equal grounded factors, with no asymmetric extra factors, makes the lifted subgroup a subgroup of policy-evaluation symmetries.The identity state map also preserves the initial distribution, and the lifted subgroup’s agent orbits are exactly the partition parts.Source: §E.1.1 · p. 21
  • The same-partition coordination example has counting symmetry and policy-evaluation symmetry but lacks the stated repeated additive reward factorization.The result rules out that factorization for a partition with one part, not for a singleton partition.Source: §E.1.1 · p. 22

E.2 Expected Return Symmetry

  • Across the shared finite Dec-POMDP class, neither expected return symmetry nor policy-evaluation symmetry implies the other.The two non-implications use different models; the result does not claim both failures occur in every fixed model.Source: §E.2 · p. 22
  • The counterexamples separate preserving the optimal Boltzmann policy set from preserving evaluation for every decentralized policy.An ERS transformation can change a nonoptimal policy’s return, while an evaluation symmetry can map the unique Boltzmann policy to one violating Boltzmann consistency.Source: §E.2 · p. 22

E.2.1 Boltzmann condition and comparison proofs.

The comparison proofs show that preserving an optimal Boltzmann policy set and being a policy-evaluation symmetry are distinct properties. A local action-value criterion characterizes the set-preservation property, with off-path histories requiring an equivariant convention for that criterion.

E.2.1 Boltzmann condition and comparison proofs.

  • For 0 < ε < 2α, this one-stage two-agent Dec-POMDP has common reward R(a)=ε1{a₁=a₂}; swapping agent 1’s action labels is admissible, lies in Ψ, fixes the uniform product policy, and exemplifies ERS without policy-evaluation symmetry.Source: §E.2.1 · p. 23
  • In Mᵦ, exchanging observations x and y is a policy-evaluation symmetry, but the transformed policy violates Boltzmann self-consistency, so it is not ERS.The fixed Boltzmann probabilities satisfy bₓ > bᵧ, whereas the transformed policy uses bᵧ at an x-history.Source: §E.2.1 · pp. 23–24
  • Under paired-history and legal-action assumptions, a transformation preserves the optimal Boltzmann policy set exactly when paired local action-value vectors differ by an action-independent constant for every policy in Πα.For an environment automorphism, the constant is zero at positive-probability paired histories.Source: §E.2.1 · p. 24
  • At zero-probability histories, well-defined local action values alone do not ensure the local action-value identity; the fixed belief and local-Q convention must be equivariant.The L/R and action-swap example shows that a convention assigning probability one to L at every impossible history fails this condition.Source: §E.2.1 · p. 25
  • The complete values defining the policy-evaluation symmetry group are specified directly, including at unreachable state–joint-history pairs, and need no belief convention..Source: §E.2.1 · p. 25

Related papers

Loading 2610.18538v1…