Inter-Agent Relative Representations for Multi-Agent Option Discovery
Authors: Raul D. Steleac
Mohan Sridharan
David Abel
Venue: ICLR 2026 Poster (2026)
Keywords: Option Discovery
Multi-agent Reinforcement Learning
Primary area: reinforcement learning
TL;DR: We aim to address the challenges of multi-agent option discovery methods through a novel inter-agent relative state representation.

Abstract: Temporally extended actions improve the ability to explore and plan in single-agent settings. In multi-agent settings, the exponential growth of the joint state space with the number of agents makes coordinated behaviours even more valuable. Yet, this same exponential growth renders the design of multi-agent options particularly challenging. Existing multi-agent option discovery methods often sacrifice coordination by producing loosely coupled or fully independent behaviours. Toward addressing these limitations, we describe a novel approach for multi-agent option discovery. Specifically, we propose a joint-state abstraction that compresses the state space while preserving the information necessary to discover strongly coordinated behaviours. Our approach builds on the inductive bias that synchronisation over agent states provides a natural foundation for coordination in the absence of explicit objectives. We first approximate a fictitious state of maximal alignment with the team, the Fermat state, and use it to define a measure of spreadness, capturing team-level misalignment on each individual state dimension. Building on this representation, we then employ a neural graph Laplacian estimator to derive options that capture state synchronisation patterns between agents. We evaluate the resulting options across multiple scenarios in two simulated multi-agent domains, showing that they yield stronger downstream coordination capabilities compared to alternative option discovery methods.

Published as a conference paper at ICLR 2026
INTER-AGENT RELATIVE REPRESENTATIONS FOR MULTI-AGENT OPTION DISCOVERY
Raul D. Steleac
Mohan Sridharan
David Abel
School Informatics
School of Informatics
School of Informatics
University of Edinburgh
University of Edinburgh
University of Edinhurgh
raul. stell eacêed. ac. uk
m. sr.ii www.raaareeeeeeeee ac. uk
david. abel Bed. ac uk
ABSTRACT
Temporally extended actions improve the ability explore and plan single- agent settings. In multi-agent settings, the exponential growth of the joint state space with the number of agents makes coordinated behaviours even more valu- able. Yet, this same exponential growth renders the design of multi-agent op- tions particularly challenging. Existing multi-agent option discovery methods often sacrifice coordination by producing loosely coupled fully independent behaviours. Toward addressing these limitations, we describe a novel approach for multi-agent option discovery. Specifically, we propose joint-state abstrac- tion that compresses the state space while preserving the information necessary to discover strongly coordinated behaviours. Our approach builds on the inductive bias that synchronisation over agent states provides a natural foundation for co- ordination in the absence of explicit objectives. We first approximate a fictitious state of maximal alignment with the team, the Fermat state, and use it to define a measure of spreadingness, capturing team-level misalignment on each individual state dimension. Building on this representation, we then employ a neural graph Laplacian estimator to derive options that capture state synchronisation patterns between agents. We evaluate the resulting options across multiple scenarios in two simulated multi-agent domains, showing that they yield stronger downstream coordination capabilities compared to alternative option discovery methods.
INTRODUCTION
Effective cooperation in complex domains requires agents to distribute the tasks, synchronise ac- tions, and make decisions under partial observability. Humans seeking to cooperate often invent novel strategies for new tasks by adapting cooperation patterns previously learned for related tasks, and reasoning about the requirements the new tasks (see Appendix A. for additional discussion). For example, when learning to play a new ball game, basic cooperation patterns like passing or po- sitioning relative to teammates or opponents surface instinctively and are then adapted to the new setting. This ability to identify and reuse cooperation patterns enables skills and instead focus on discovering more abstract (high-level) strategies. In this work, we study how to enable AI agents discover such basic cooperation patterns, and use them to explore and identify more useful cooperation strategies at a higher level than that allowed by primitive actions.
bypass relearning basic
In single-agent reinforcement learning (RL), the options framework (Sutton al., 1999) a widely used mechanism for formulating temporally extended actions. Options can act as shortcuts be- tween distant regions of the state space during exploration (McGovern & Barto, 2001). Yet, as noted in prior work (Jong et al., 2008), the effectiveness of options is sensitive to many factors, and poorly designed options or a large set of options can hinder learning. This makes option dis- covery, i.e., the automated design of useful options, challenging problem. Methods based on the cigen-decomposition of the graph Laplacian, such as Eigenoptions (Machado et al., 2017a), have gained traction due to their task-agnostic discovery of options and exploration guarantees (Jinnai et al., 2019a). However, relying on the eigenvectors of the state-transition graph Laplacian leads to excessive number of options being discovered (twice the state count), problem that is more pronounced in multi-agon systems because the state space grows exponentially with the number of agents. Moreover, current Laplacian eigenvector approximators most effective in estimating

---

Published as a conference paper at ICLR 2026
small number of cigenvectors (Wang al., 2021; Gomez et al., 2024), risking not identifying useful options, particularly those that facilitate exploration at various timescales.
We address option discovery for multi-agent systems through novel inter-agent relative state ab- straction. This new state abstraction compresses the joint state space of group of agents into a compact latent representation centred around the state of maximal alignment among agents, which we call the Fermat state. Through this abstraction of the joint state, we drastically reduce the number of discovered options while also focusing the discovery process on how the relationships between the agents change. We then empirically show how this abstraction encourages the emergence of highly coordinated behaviours. Our approach builds on the intuition that in the absence of an ex- plicit objective, synchronisation over state features represents a natural basis for coordination. Re- turning to the ball game example, both passing and positioning skills can be understood as forms of multi-agent state synchronisation; they determine who holds the ball and how the players align relative to one another along each spatial dimension. This intuition is consistent with insights into position alignment in animal collective movement (Herbert-Read Read, 2016) and emergent coordination in human psychology (Knoblich et al., 2011). The key contributions of our paper are:
A novel abstract joint state representation that maps the relationships between the agents to multi-dimensional N-metric space;
The use of the abstract state representation, and its ability to compress and reorient eigenoptions toward inter-agent relations, for the discovery of highly coordinated joint options; and Adapting the MacDec-POMDDD framework (Amato et al., 2019) to support joint-option execution.
We illustrate and experimentally evaluate the capabilities of our approach in two benchmark multi- agent collaboration domains: Level-Based Foraging (Papoudakis et al., 2021) and Overcooked (Ruh- dorfer et al., 2024). We demonstrate the benefits of incorporating, joint options over baselines that do include such options, and show that the coordination behaviours discovered using our proposed state abstraction lead to better performance than the behaviours obtained using other multi-agent option discovery methods.
BACKGROUND
We begin by describing the basic concepts of Dec-POMDPs, the options framework, and n-metries.
2.1 DECENTRALISED BOBTAALL-OOBSRVABLE MARKOV DECISION PROCESSES
A Dec-POMDP (Bernstein et al., 2009) is defined as a tuple (I, (A') T, R., (2'), O, where = {I...., _N is a finite set agents' indices, S the state space and A = A x ... A the joint action space. At every time-step f, agent receives its local observation of Ω2 where Ω Q' x.x.... x is the joint set of observations that was generated according to the observation function S x A x Ω + [0, 1]. Agent i then selects action of E A' according to a policy x' (a/ that is conditioned on the history of its local observations and actions h; (of of...., of of Given the joint set of actions at t, 8141 S according to the state transition function T S A x S [0, 1] and induces global reward received by all agents r, = R(s, a), where R S A RR The goal is to learn joint policy ( N) that maximises the expected cumulative discounted return G = ΣT 7t
{a} a; J. the environment transitions to new state
Amato et al. (2019) extended Dec-POMDPs by integrating single-agent macro-actions (options) within an asynchronous execution scheme. They defined MacDec-POMDP as the tuple (I, A, (M') T. R, ( {2*), {('), 1, O), where SI A, T. R, {2*), O) are the same as in a Dec-POMDP. The primitive action of each agent I, A', is replaced with finite of macro- actions M', and M = M x ... x M is the joint macro-action set. They also introduced a joint set of macro-obseervatinn <= x -.. x NN with z x S Ç² + [0, 1] specifying the macro- observation probability function for each agent i. To formalise macro-actions, separate histories are maintained for the two execution levels: H' is the primitive action observation history, and Hi, is the and the joint macro history is HM - H
history. The joint primitive history is HA (H))..., H
2

---

Published as a conference paper at ICLR 2026
2.2 OPTIONS
Sutton et al. (1999) define an option as a tuple w = (Iw, Tw,, Bw), where I. C S is the initiation where the option be invoked, Fa is the option poliey, and B - [0, 1] is the termination condition. these components depend only on the current state, the option is referred to as a Markov option. This notion is generalised condition may depend on additional information (c.g., state-action rewaard histories), or termination may be triggered by external factors such as fixed k-step horizon.
gemi-Markov options, in which the policy and termination
Eigenoption discovery (Machado et al., 2017b) 7b) estimates the eigenvectors of the combinatorial graph Laplacian corresponding
state transition graph, typically via random walks. The eigenvectors of the graph Laplacian, L = D A (where D and A are the degree and adjacency matrices, re- spectively), captures long-term temporal relationships between states and the overall geometry of an MDP (Mahadevan & Maggioni, 2007). Given eigenvector e, the intrinsic reward function for transitioning from discrete state to s' can be computed as (e s') = e(s') e(s). Subsequent work (Wu et al., 2018; Jinnai et al., 2020; Wang et al., 2021) extends this framework non-tabular domains by approximating the eigenvectors through neural networks trained to minimise objectives derived from graph-drawing theory (Koren, 2005). The ALLO method introduced by Gomez et al. (2024) further improves robustness to hyperparameters and eigenvector rotations.
2.3 M-METRICS AND n n-DISTANCES
n-metric. Given set X and an integer 2, n-(heei)metrre (Deza & Rosenberg, 2000; Deza & Deza, 2009) is a function d X + R, that respects the following conditions:
(MI) (Non-negativity) d(z1,..... Fn) N 0 for all 21.... In E X.
(M2) (Total symmetry) d(x),...... Fnn) ((z. .....
for all , En X and for any
permutation x of {1..... n).
(M3) (Definiteness) d(r1,...,, nn) 0, if and only if 21 ........ Fn not pairwise distinct.
(M4) (Simplex inequality) d(z), ................................ n..) Σ d(x), ............... )n for all ,n,, E X.
This definition uses n to replace m + 1 the original definition of an m-hemimetric (Deza & Deza, 2009) and uses d(x1,.... )n, denote the function evaluated on elements where the i-th element r, is replaced by 2 drawn from the same set X.
n-distance. n-distances (Martín & Mayor, 2011; Kiss al., 2018) relax (M3) by setting d(z xx,) = only when I1 = =... In. providing a direct way of comparing the dissim- ilarity separateness for sets with more than two elements.
Fermat n-distance. Given metric space (X.d) and an integer n 2 2, a Fermat set F. for a Fn) ) is set that minimises the sum of distances to each element in the
list of n elements (I)....,,,))
list (Boltianski et al., 1998):
72
Fx
1 M Σ ((z;,)) S E a'), Va' E E
The elements of F, then named the Fermat points for the respective list. Based on these defini- tions, Kiss et al. (2018) introduce Fermat n-distances as functions dy X - R of the form:
de df(r1,.... 2n) min Σ d(z,,
(2)
MULTI-AGENT OPTION-DISCOVEN
We next describe our framework for multi-agent option discovery, starting with the method for approximating the spread of group of agents through n-distance estimation.
3.1 n-DISTANCES FOR MULTI-AGENT DISSIMILARITY ESTIMATION
In the absence of a reward signal, one key strategy for coordination among a group of agents is through the alignment of their states. An important step generate such collaborative behaviours
3

---

Published as a conference paper at ICLR 2026
is to define a measure of spreadingness for the group of agents at any given time. We begin by introducing a notion of distance between the state of two agents. To this end, we assume that the joint state-space, S, can be factored into N single-agent state spaces 8', with N = [ and i I, by ignoring the presence of others and including information corresponding solely to each individual agent We denote s S to be single agent-state, and d(s", s²) as a distance metric capable of comparing the similarity between the state of two agents, i.j E I. For simplicity, we focus our notation and definitions on homogeneous agent state spaces, i.e., S = S _... S However, Appendix A.8 describes how this model can be extended to heterogeneous settings, and presents empirical evaluation in two toy scenarios.
Inspired by Fermat n n-distances (Equation 2), we define an n-distance metric for a group of agents.
Definition 1. For a metric space (S*, d), where St is a single-agent state space, is a state distance metric and N 2 2, we define the Fermat inter-agent state distance as a map dy S - RR such that:
N
dr(st
min SES
d(s s).
(3)
Computing the minimization operation from Definition I becomes intractable in large or continuous state spaces. To alleviate this problem, we propose approximating the Fermat state, the state of minimum summed distance to each agent, through parameterised function, ø S - S*, which we call the Fermat encoder and train by minimizing the following objective:
N
Lr(d,
=
E Pm
1 N
Σ
alsh. ((s)))
(4)
where 7 ... ST-I.. ~ Pa is history of states under the trajectory distribution Pr of joint policy т, T is the time horizon of an episode, 8; is the joint state, and sj is the ith element of the factorised joint state, corresponding to agent i. This objective depends on a pre-defined state distance metric d. While any valid state distance metric would suffice, we employ temporal distances due to their invariance feature semantics and close alignment with environmental dynamics (see Section 5). Temporal distances are typically formulated as quasimetrics that are obtained by relaxing the symmetry requirement to account for the arrow of time (e.g., ascending mountain takes more time than descending it). Although a quasimetric function can be symmetrised, e.g. dm (I, y) = (z, y) + (y, 2)), such transformations remove key advantage of temporal distances and reduce the expressivity of the resulting measure. Thus, we enforce consistent input order by fixing the Fermat state as the second input in Equation 4, yielding a directed function that can be interpreted as the expected number of steps needed for the agents to achieve full alignment.
We adopt the successor distances method (Myers al., 2024) for approximating temporal distances and denote the parameterised state distance as dg S* x S - I. The Fermat encoder & and the distance approximator do are trained concomitantly by enforcing stop-gradient operator on the distance estimator's 's parameters (0) when integrating it in the Fermat encoder objective (Equation 4).
3.2 MULTI-AGENT OPTION DISCOVERY ON RELATIVE STATES
Eigenoption discovery, introduced in Section 2.2, consists of two main steps: (i) estimating the state- transition graph and (ii) performing the eigen-decompositton of the graph Laplacian to generate set of eigenvectors for option training. An important observation is that this process is completely dependent on the state representation used to construct the transition graph. We propose inten- tionally leverage this observation by embedding the joint state space into an inter-agent relative representation prior to performing the graph Laplacian iigen-decomposition.
Intuitively, one could replace each joint state in the transition graph with the corresponding n- distance estimation. However, such a compression may limit the behavioural expressivity captured in the eigenvectors. Using a singular scalar value to describe the dissimilarity on all feature dimen- sions can obscure their individual effect. For instance, two agents reported as being k units apart may differ primarily along one dimension defining the space, or along multiple dimensions, but the
Single agent states can contain general environmental information. Because it is shared by all agents, it will be naturally ignored by the state distance measure.
4

---

Published as a conference paper at ICLR 2026
Σ
dg
d
Φ s,)
Joint state
Fermat state
R-distance
eigenvector
Option discovery on inter-agent relative representations for state factorisation function g. Fermat encoder @, state distance encoder de and graph Laplacian eigenvector approximator j..
Figure 1:
scalar provides no insight into which dimension drives the misalignment. Furthermore, mapping joint states to scalar values has drastic effects on the topology of the state-transition graph, further limiting the diversity of the alignment behaviour discovered. To address this issue, we compute the n-distance along each feature dimension of the single-agent state space and encode the nodes the state-transition graph as their concatenation. The distance module thus modified to predict F outputs d' S* X S RR,, where F = dim(S*). We then use a linear projection layer to approximate the overall state-distance when training de Figure provides an overview of our joint option discovery framework, which uses multi cealii-dmmesionall n-distances state representations.
In practice, however, this unconstrained decomposition can lead to degenerate solutions, as dī can output identical distance estimates all dimensions revert to only using of the output dimen- sions. To mitigate this issue, we impose a Mutual Information (MI) objective that encourages each state feature dominate the information flow leading its corresponding distance prediction. For- mally, let S = (S), be the random pair of single-agent states corresponding to agents i, E I, with i + j. obtained by factorizing states of joint trajectories from Pr. For each feature index {I....,F}, we denote S Sy) as the pair of their f-th feature dimension. Given that d= : S* x S + R is deterministic map, we define random vector Z d= (S" SS) E R and its f-th component 2 We require that the MI between each feature distance Z and the rest of the state-feature pairs 5". i.e. T( 7i")). does not exceed the MI between the feature pairs themselves, T(S".) St."). This implies that each distance prediction should not carry more information about the value of other features than already captured the correlations between the inherent features. We next establish that through simple manipulations of the chain rule of informa- tion, we can upper bound the information between Zidd and the rest of the state features S' by the information already explained by feature s/ about S"t; plus a residual conditional term.
Proposition 1. For any two agent indexes i,j E I, with i + j. and feature index f E (I,..., F}:
I(S Zi 1
(5)
proof this proposition in Appendix A.2. To reduce information overflow in the distance predictions, thus minimise the following Conditional Mutual Information (CMI), measuring the excess information that Z conveys about S beyond what is already captured in St..
1 s/ Dkulp(stH, shi. S 2 p(S s Jo(z) أهب
(6)
Minimizing CMI. We adopt the approach of Dunion et al. (2023) and introduce discrimina- tor network Dg trained to directly detect the information excess. Specifically, the discriminator is trained to distinguishing between real triplets {s-) 8
i. iij f.6: 2f,t obtained by pairing factorised
single-agent states from a history of joint states T A (8o. .......,7 87) ~ Pr, and fake triplets obtained J.j
f f fixed. As in Dunion et al. (2023), we use the discrim- inator's predictions define disentanglement penalty when training df. We defer description of the CMI minimization algorithm to Appendix A.3, A visual comparison of scalar and the multi- dimensional n-distances is in Appendix A.5.
by permuting (.) while keeping (5)
5

---

Published as a conference paper at ICLR 2026
Single
Joint
Relative
(1.7.
(7.7).78))
(1.7
(7.7) (7.8)
Figure 2:
The first three non-trivial cigenvectors of the graph Laplacian for an 15x15 grid environ-
ment with three agents, the only entities in the grid, under varying state representations: single agent state spaces (left), raw joint state spaces (centre) and inter-agent relative state representations (right). For visibility, fix the position of two agents for the multi-agent scenarios (at ((1,4), (1,7)) and ((7,7), (7,8))), and display the values when varying the position of the remaining agent.
We follow the representation-drivel option discovery (ROD) cycle from Machado et al. (2023) 2 to generate the of options, but precede the eigenvector estimation by first representing joint states as their disentangled multi-dimensional n-distance representation. Both the n-distance encoder train- ing and joint option discovery are done prior the generic training. By converting raw joint states into relative representations, we produce options that reflect a range of complex multi-agent align- ment behaviours, enabling agents to synchronise along various subsets of their state features. Fig- ure 2 (right) illustrates the resulting eigenvectors in grid-world setting with coordinate- Appendix A.6 extends this analysis to prior multi-agent eigenoption methods (Chen et al., 2022). For ease of understanding, we fix the positions of N - agents and visualise the eigenvectors from the remaining agent's s perspective. We emphasise that these relative eigenvectors are highly respon- sive changes in the joint state due to the re-centring effect around the Fermat state, property that much less evident in the cigenvectors discovered on raw joint states. this simple domain, the first eigenvector aligns agents along coordinate axis, while its negation (also valid eigenvec- tor) aligns them along the other. The subsequent eigenvector promotes alignment across both axes simuitaneously, followed by eigenvectors that capture more complex synchronisation patterns.
states;
Following the procedure introduced in Section 2.2, we use these eigenvectors as intrinsic reward signals for option-policy training. Figure 3 shows visualisation of the multi-agent options trained to follow the positive and negative versions of the first two eigenvectors for team of four agents. With each grid, we report the feature-wise distance values for the corresponding final states, highlighting the distinct alignment patterns achieved by the learned option policies. Furthermore, the first two eigenvectors induce the same behaviours for four agents as they did for three in Figure illustrating the consistency of the alignment patterns with respect to team size.
3.3 ADDING JOINT OPTIONS DEC-POMPDS
We adapt the MacDec-POMDD framework (Amato al., 2019) described in Section 2. to support multi-agent macro-actions (joint options). To ensure the correct selection, execution, and termina- tion of joint options in decentralised settings, we impose the following two modeling assumptions: Assumption 1. There is information-ssuring mechunism between all agents.
This assumption yields a more permissive model than the standard MacDec-POMMP framework. However, it still withholds access to the true underlying state. The information sharing mechanism
We use the ALLO method from Gomez et al. (2024) to approximate the eigenvectors of the graph Laplacian and follow the original eigenoptions approach from Machado al. (2017h), where we single ROD cycle generate the whole of eigenvectors. motivation for these design choices in Appendix A.9.

---

Published as a conference paper at ICLR 2026
Option1
Option 2
Option
Opton
Figure 3: Policy roll-outs visualisation of the first four relative options in the 15x15 grid environment with four agents. Arrows indicate the actions taken by each agent's 's policy, coloured circles mark the final states (before the termination action triggered), and the white circle denotes the estimated Fermat state corresponding these final states. The bars the right of each figure show the Fermat n-distance estimates for each feature. Please see Appendix A.7 for other state initializations.
motivated by the collective nature of the options discovered, where effective option selection often depends on team-level information. In scenario where agents must search for resources in an environment, a good strategy might be to spread out, locate resource, and then trigger an option to gather around it. Without knowing if teammate has found the resource, however, triggering the option prematurely can hinder performance and destabilise exploration.
Assumption 2. There is a synchronisation mechanism that ensures the minimum number of agents required for the correct execution of joint options.
In the same way that passing in a ball game cannot be defined without a receiving partner, this design choice synchronises joint option selection, asserting that enough agents agrec on following an option at a given time for that option to be activated and executed correctly.
Inspired by local options (Amato al., 2019), we define joint options via hierarchical agent his- tories. A joint option a tuple W = (Iw: xw, Sw), where Iw S H and 3w : HM - [o. 1] defined over joint macro-level histories, and Rw (T....., m is joint policy mapping joint primitive-level histories HA to actions. We define joint options as collective behaviours in- volving the entire team, and therefore require full team consensus for initiation. Joint options can be viewed as direct extension of local options to multi-agent behaviours. Although global consensus restricts the expressivity of representable behaviours, we adopt it for simplicity. Therefore, despite our discovery method supporting behaviours over arbitrary agent subsets, we restrict ourselves to team-level options and leave the integration of options involving subsets of agents to future work.
To integrate joint options into the MlaDeec-POMDD framework, we redefine the macro-action set M, to include both joint and local options, treating primitive actions as local options with immediate termination. When agent i selects option M, at time step I, this selection is interpreted toward option initiation; a threshold of N votes is required for joint options, and 1 vote for local options. If this value is reached, the option is executed and control is transferred to the option policy until termination, otherwise control is returned at + 1. Next, we redefine macro-observations G to incorporate information shared by teammates. Dec-POMDP-Com (Oliehoek & Amato, 2016) extends the standard framework with an explicit communication protocol. Since communication is focus, we mimic this step by allowing agents share their observations directly and leave more general treatment of communication to future work.
vote
4 EMPIRICAL EVALUATION
We structured our empirical evaluation around three hypotheses: (H1) Joint options provide ad- vantages in downstream tasks compared with not using them. (H2) Joint options discovered via inter-agent relative representations (IARO) yield better downstream performance than those derived from other methods. (H3) The multi-dimensional n-distance representation enables a more robust option discovery process that its scalar-value variant in domains with more complex state spaces. Additionally, we investigate how increasing or decreasing the number of relative options discovered by framework affects overall performance in our experimental domains.
Experimental Setup. We evaluated our approach two multi-agent domains: Level- -asee For- aging (Papoudakis al., 2021) and Overcooked (Ruhdorfer al., 2024), using their JAX

---

Published as a conference paper at ICLR 2026
implementations from jum (2024) and Rutherford et al. (2024), respectively. We focused on two scenarios in each domain: for LBF, these are 15x15-4p-3t and 15x15-4p-5f and for Overcooked, they are Forced Coordination and Counter Circuit. In LBF, requirements by setting each apple's level equal to the sum of all agents' levels, the forced coopera- tion configuration from Papoudakis et al. (2021). Our choice of domains reflects trade-off between interpretability and feature diversity. LBF enables straightforward visualisation of eigenvectors and relative representations through its X, -coordinnaee state space. Overcooked involves richer feature semantics, combining X, Y -oordiinass,s, orientations, and a categorical variable for item inventory. While information sharing is implicit in the Overcooked task, in LBF, we allowed agents to always observe the relative distances to their teammates (rather than only when they enter their field of view) and add a flag to their observations indicating when each teammate is the vicinity of an apple. Our approach and all baselines operated under the same level of observability in our analysis.
introduced stronger coordination
To train the n-distance encoder and the graph Laplacian eigenvector approximator ALLO (Gomez et al., 2024), we used dataset of 500,000 transitions sampled from a random joint policy in each domain. In LBF, we approximated the first 10 eigenvectors, yielding 20 options, while in Over- cooked we approximated 20 eigenvectors, yielding 40 options. Once estimated, option policies based on these eigenvectors for one million steps, equivalent to 5% and 10% of the total training time in each task. We employed IQL. train the option policies and incorporated an action, Ai = AA U (1). }. as the termination condition (Machado et al., 2017b). All agents involved had all choose this action for an option to be terminated. In addition, we enforced hard stop after 50 steps. The initiation set was defined as the entire joint state space, allowing options to be started anywhere, provided that the required number of agents, Ry = N, was met.
trained joint
against generic baselines. To evaluate HI, we compared the performance of IQL equipped with inter-agent relative options (IQL+IARO) against four option-free free baselines: MAPPO (Yu et al.. 2022), IPPO, IQL, and VDN (Sunehag et al., 2018). Following Rutherford et al. (2024), we left MAPPO out of our analysis for Overcooked. Figure presents IQM scores with 95% confidence intervals (CI) computed across 10 seeds. The addition of joint options (IQL+IARO) led to consistent performance gains over the vanilla IQL, achieving higher percentages of apples caten per episode in LBF and more successful deliveries per episode in Overcooked; see top row of Fig- ure 4. This improvement was especially visible in Overcooked, where IQL tends to remain stuck in suboptimal solutions. The joint options equipped agents with coordination skills that systematically explored the state space and enabled them to swiftly parse through various coordination patterns in search of better strategies. Additionally, IQL+IARO outperformed the other baselines across the set of experiments, except the Forced Coordination scenario where VDN is known to perform well (Rutherford et al., 2024). These results highlight the benefits of joint options in overcoming the limitations of independent policy learning in multi-agent tasks by encouraging cooperation through the set of pre-computed coordination behaviours; note that our method does not rely on central- ization (MAPPO) or value decomposition ( (VDN) to support it. However, we did observe a slower convergence at the start of training, which we attribute to known challenges of training with options under global initiation sets (Jong et al., 2008; Machado et al., 2023).
Evaluation
equipped
Evaluation against other option frameworks. Next, to evaluate hypothesis H2, we compared the downstream benefits of the options discovered with our framework against those discovered through an existing Kronecker graph product method from Chen et al. (2022) (IQL+Kron), and an ablation where discovery was performed directly on raw joint states (IQL+RJS). For IQL+Kron, followed the original implementation, apart from two main adaptations to match our framework: approximate both eigenvectors and eigenvalues
closely
(i) we employed ALLO (Gomez et al., 2024) directly; and (ii) we used single ROD cycle to estimate multiple eigenvectors. Figure 4 compares the resulting options across both domains and shows that the options discovered by our method better equip teams of agents with the cooperative skills necessary to solve these downstream tasks. We noticed that, particularly in LBF, options discovered via raw joint states and Kronecker products can degrade performance. We believe that this is due to their first non-trivial eigenvectors mainly capturing behaviours that drive agents to the edges of the state space (also see Appendix A.6), which is counterproductive for the apple-picking task.
We then explored H3 by evaluating the utility of the multi-dimensional n-distance representation (IQL=IARO-MultiDmm against its scalar-value variant (IQL+IARO-Scalar), While in LBF, the do- main with simpler state definitions, both methods performed similarly, in Overcooked, the multi- distance method proved more effective, as agent states consist of multiple features of diverse
8

---

Published as a conference paper at ICLR 2026
3041% 4p-37
LOP: 38x38-4p.39
Overcoseed -wr.oo ceero
Overcooked -ounber CIreae
PATSUIT 4.7CM
15
Sence Seccedda
020
15
1.5
00
02
02.
Stresteps
83
02
24
Threstess
21
10638-pp-r
L07 18xth-4p-11
Overceobed Aeved
Overceoked coeedar dreat
Parrent S.TE
Sanon Orthwote
30
70
32
1.0
53
5:2
2-1 2.5
RQ5+
QL-
Figure 4: Downstream task performance analysis for both environments (LBF on the left, Over- cooked the right). The top row compares IQL+IARO against option-free baseline algorithms, while the bottom row compares it against IQL augmented with other option discovery methods.
15x15-4p-77 Sr
Overcooked counter circult
15
Surcesste Deliverrees
80
-3
10
83
Options
Options
Figure 5: Downstream task performance for the most complex scenario in LBF and Overcooked, evaluated using different numbers of options. We report IQM scores over 15 seeds and 64 evaluation episodes the end of training for each configuration, with standard deviations shown error bars.
mantics, highlighting the benefits of the disentangled n-distance representation. By decomposing n-distance estimation across features, agents can align on specific subsets of state dimensions, yield- ing a richer set of cooperative behaviours. is then up to the acting policy to decide, via exploration, which alignment strategies are beneficial for the task at hand.
complementary episodic reward analysis for a larger set of domains is provided Appendix A.4, while other implementation details and the list of hyperparameters can be found in Appendix A.
Option count analysis. We examined how the number of joint options used during training influ- ences downstream task performance. Our goal was to identify the threshold at which subset of options yields substantial performance gains, as well as to understand how further increasing the number of options affects results. Figure 5 reports the aggregated scores for the most complex sce- nario in both environments. We observed that both tasks benefit even from a relatively small option set. In LBF, the largest boost in apples collected appears with as few as two options, while no- table improvements in successful deliveries emerge with the first ten options in Overcooked. This is consistent with eigenoption theory, which suggests that the first eigenvectors connect distant nodes in the state-transition graph, yielding powerful exploration behaviours. Later cigenvectors encode shorter time-scale behaviours, whose usefulness may vary in each task. We also note that more complex state spaces generally imply a larger threshold, reflecting the greater diversity of long- horizon alignment patterns that emerge through different feature combinations. Finally, although larger option sets can sometimes further improve performance (e.g., six options for LBF and twenty for Overcooked), these gains eventually saturate. Larger option sets can introduce increased train- ing instability, resulting in reduced performance higher variance. In previous evaluations utilised the maximum number of options for both environments to enable a fair comparison with the other option discovery methods.

---

Published as a conference paper at ICLR 2026
5 RELATED WORK
We discuss related work on similar metrics, state representations, and cumporally-extendee actions.
State similarity metrics. Estimating state similarity measures is fundamental challenge in RL. Even in simple domains, standard distances such as Euclidean, fail to capture true state proxim- ity in the presence of obstacles, as they ignore environmental dynamics. In contrast, bisimulation metrics (Ferns et al., 2004) measure state similarity through differences in rewards and transition dy- namics, and have been widely applied in optimality preserving state aggregation methods (Li al., 2006). However, these approaches struggle in sparse-rewards settings, leaving them susceptible to representation collapse (Kemertas & Aumentado-Amsttrnn successor distances define state similarity as the expected number of actions required by policy to travel between two states Venkaataaammnnjjm et al., 2019). This class of state distances is invariant to state representations and closely reflects environmental dynamics, making it popular solution for goal-conditioned RI. (Hartikainen et al., 2020; Durugkar et al., 2021; Myers et al., 2024), in- trinsic reward composition (Bac et al., 2024; Jiang et al., 2025) and unsupervised skill discovery (Park et al., 2024). Notably, METRA (Park et al., 2024) is particularly relevant to our work, as aims to learn skills that explore latent space connected to the ground state space via temporal metric. Besides performing skill discovery in single-agent settings, a main distinction is that we leverage temporal distances approximate a latent representation for the eigenoption discovery of joint options that achieve exploration at different time-scales, rather than only at its extremes.
2021; Chen et al., 2024). Temporal or
State representations in MARL.. State representations in MARL have been mostly used for the aggregation of agents' local observations into a compact global representation, often through graph neural networks (GNNs). GNNs are invariant the number of entities, here agent observation em- beddings, and can weight the information passed between vertices differently through edge features (Jiang et al., 2020; Liu et al., 2019; 2021: Nayak et al., 2023). Utke et al. (2025) emphasise the importance of relative information for estimating inter-agent relations, and embed this inductive bias into GNN edge features based on hand-crafted spatial relations. In contrast, our method learns inter-agent relations automatically, without any restrictions on feature semantics.
Temporally extended actions for multi-agent systems. Makar et al. (2001) extend semi-Markov decision processes to cooperative multi-agent settings, introducing two execution schemes: syn- chronous (macro-actions terminate simultaneously) and asynchronous (macro-actions terminate in- dependently). Asynchronous schemes gained recent popularity due to their innate generality (Amato et al., 2019; Xiao et al., 2021; 2022), but typically rely on single-agent (local) options that do not ex- press cooperative behaviours. Therefore, coordination occurs only at the option selection level, but not within the option policies themselves. This approach drastically limits the expressiveness of the options used in multi-agent scenarios. To address this, Chen et al. (2022) integrates option discov- ery techniques based on covering options (Jinnai et al., 2019b) that construct joint behaviours via Kronecker products of single-agent transition graphs. However, the resulting joint options mainly synchronise independent behaviours, failing to capture strong inter-agent dependencies or correla- tions, a limitation noted by the authors. This leaves the problem of discovering strongly coordinated behaviours still open, which is precisely what we aim to address with our method.
6 CONCLUSION
In this work, we introduced a novel inter-agent relative representation for joint states, designed to address the key challenges of multi-agent option discovery. This representation compresses the joint state space and re-centres it around the point of maximum alignment for the team. We define this point as the Fermat state and propose a method that estimates it explicitly. Using the relative rep- resentation, we then produce joint options that are strongly coordinated and well-suited to capture inter-agent relational dynamics. Moreover, by disentangling the representation across individual state features, our approach further enriches the behavioural diversity expressed in the discovered joint options. We demonstrated the effectiveness of the proposed method across multiple benchmark domains and scenarios, confirming its ability to support agent teams in achieving stronger solutions on downstream tasks. Our work opens up multiple directions for further research in the discov- ery and use of options for multi-agent collaboration. In particular, richer topologies of coordinated behaviours, relax the assumption of sharing observations in lieu of a communication protocol, and the restriction that joint option initiation requires full team consensus.
will study the discovery of
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Jumanji: a diverse suite of scalable reinforcement learning environments in jax, 2024. http:: //arxiv. www.:/rrgg.a/...e.............ae 223/ 2306...0 09884.
Christopher Amato, George Konidaris, Leslie P. Kaelbling, and Jonathan P. How. Modeling and planning with macro-actions decentralized pomdps. J. Artif. Int. Res., 64(())817-885) January
2019. ISSN 1076-9757. doi: 10. 1.613//air...114133 URL jair. 1.11418.
Junik Bac, Kwanyoung Park, and Youngwoon Lee. Tldr: Unsupervised goal-conditioned rl via temporal distance-aware representations, 2024. URL http:://aaxxv..ogg////// 08464.
Daniel Bernstein, Christopher Amato, Eric Hansen, and Shlomo Zilberstein. Policy iteration for decentralized control of markov decision processes. Journal of Artificial Intelligence Research, 34:89-132, 2009.
V. G. Boltianski, Horst Martini, and Valeriu Soltan. Geometric methods and optimization problems. 1998. URL i www.aaannicsccoooooooooooooceeee
semant
1177766778..
Jianda Chen, Wen Zheng Terence Ng. Zichen Chen, Sinno Jialin Pan, and Tianwei Zhang. State chrono representation for enhancing generalization in reinforcement learning, 2024. URL
httpp:://araa
org/ abs 2411.
Jiayu Chen, Jingdi Chen, Tian Lan, and Vaneet Aggarwal. Scalable multi-agent covering option discovery based on kronecker graphs. Proceedings of the 36th International Conference on Neural Information P Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.
M.-M. Deza and LG. Rosenberg, n-semimetrics. Eur. J. Comb., 21(6))797-806, August 2000. ISSN 0195-6698. doi: 10.1006//ujc..1999.0333. URL https: wttpo//.........///..........//. 1999.0384
Michel Marie Deza and Elena Deza. Encyclopedia of Distances, pp. 1-583, Springer Berlin Heidel- berg, Berlin, Heidelberg, 2009. ISBN 978-3-442-00234222 doi: URL httphhtt:///// //op::///ol.. .rg /10 1007
Mhairi Dunion, Trevor McInroe, Kevin Luck, Josiah Hanna, and Stefano Albrecht. Conditional mu- tual information for disentangled representations in reinforcement learning. Advances in neural information processing Systems, 36:80111-801221 2023.
Ishan Durugkar, Mauricio Tec, Scott Nickum, and Peter Stone. Adversarial intrinsic motivation for reinforcement learning, 2021. URL httph:tp/////c..t htt.pp::/aax...oo/////o/// http://///w.......o///////////// 13345.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, pp- 162-169, Arlington, Virginia, USA, 2004. AUAI Press. ISBN 0974903906.
Diego Gomez, Michael Bowling, and Marlos C. Machado. Proper laplacian representation learning, 2024. URL https: arxiv. org/ abs htwp//31..............t..abttt.t /2..3..1...........1.11111133331
Kristian Hartikainen, Xinyang Geng, Tuomas Haarnoja, and Sergey Levine. Dynamical distance
learning for semi-supervised and unsupervised skill discovery, 2020. URL bxg/abs// 1907. 08225.
J. E. Herbert-Reed Understanding how animal groups achieve coordinated movement. Journal of Experimental Biology, 219(19)22711-29) 129229 10 2016. ISSN 0022-0949, doi: 10.1242/jeb.11 129411. URL hwt.tttpp///o /ww. .org/ wtt.o///........./.... / 129411.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning, 2020. URL https: /ttttpp:://axi.oor/////a/ee
0. 09202.
11

---

Published as a conference paper at ICLR 2026
Yuhua Jiang, Qihan Liu, Yiqin Yang, Xiaoteng Ma, Dianyu Zhong, Hao Hu, Jun Yang, Bin Liang, Bo Xu, Chongjie Zhang, and Qianchuan Zhao. Episodic novelty through temporal distance, 2025. URL https::/aaxxi...tt////
abs/ /bs//2000 2010/551.... 15418.
Yuu Jinnai, Jee Won Park, David Abel, and George Konidaris. Discovering options for exploration by minimizing cover time. In Proceedings of the International Conference Machine Learning, 2019a.
Yuu Jinnai, Jee Won Park, David Abel, and George Konidaris. Discovering options for exploration by minimizing cover time, 2019b. URL https: /ttp:///aaivvvvoo
www./////////////eeeeee /
00606.
Yuu Jinnai, Jee Won Park. Marlos C. Machado, and George Dimitri Konidaris. Exploration in
reinforcement learning with deep covering options. International Conference on Learn- ing Reprexentations, 2020. URL 211266513.
semanticscholes www.aar.rrrroooooreeeeeeeeeeeeee
Nicholas K. Jong, Todd Hester, and Peter Stone. The utility of temporal abstraction in re- inforcement learning. Adaptive Agents and Multi-Agent Systems, 2008. URL https: / //api. semant cascholrr aallar.orrr wwr.orrg/ooo
597393355.
Mete Kemertas and Tristan Aumentado-Armstronn In Proceedings of the 35th International Conference on Neural Information P Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
Towards robust bisimulation metric learning.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017. URL https: / arxiv. org/ abs / 1412. 6980.
Gergely Kiss, Jean-Luc Marichal, and Bruno Teheux. A generalization of the concept of dis- tance based on the simplex inequality. Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, 59(2)2477-266, January 2018. ISSN 2191-0383, doi: 10.1007/
13336-018-0379--1 URL http::ttt//// /dx doi. pooi.orge org/r0ggg//ooooo /0. 10t.11101111331
Günther Knoblich, Stephen Butterfill, and Natalie Sebanz. Psychological research on joint action. theory and data. Psychology of Learning and Motivation PSYCH LEARN MOTIV-ADV RES TH, 54:59-101, 12 2011. doi: 10. 10.1016/B978-0- 12- 12-77800--1--5552--500000---
Y. Koren. Drawing graphs by eigenvectors: theory and practice. Comput. Math. Appl., 49(11-122) 1867-1888, June 2005. ISSN 0898-1221. doi: 10.
URL https:
///oii.org//l 10. 1016 camwa 2004. 08.08..88 015.
Lihong Li, Thomas J. Walsh, and Michael L. Littman. Towards a unified theory of state abstraction for mdps. In AI&M, 2006. URL ht //api. sew.//tta.........aee///mmmaaa.. 245037.
semant cscchlar. org Corpus
Bo Liu, Yihao Feng, Qiang Liu, and Peter Stone. Metrie residual networks for sample ef- ficient goal-conditioned reinforcement learning. In Proceedings of the Thirty-Sventth AAAI Conference Artificial Intelligence and Thirty-Fitth Conference of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial In- telligence, AAAAT23/AAAT23/AAATTA AAAI Press, 2023. ISBN 978-1-57735-880- doi: 10. 10.16099/aaii.v3777.26033 URL https: doi www.oo/g///o.. 1ee.16669/6 1t1.://.a...333772255555555
Innovative Applications
Iou-Jen Liu, Zhongzheng Ren, Raymond A. Yeh, and Alexander G. Schwing. Semantic tracklets: An object-centric representation for visual multi-agent reinforcement learning, 2021. URL https:
/ //arxiv..rg/aab//222
03319.
Yong Liu, Weixun Wang, Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network, 2019. URL https: httss///xxivvoorr abs/191 10715.
Marlos C. Machado, Mare G. Bellemare, and Michael Bowling. A laplacian framework for option discovery in reinforcement learning. Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. 2295-2304 JMI..org, 2017a.
12

---

Published as a conference paper at ICLR 2026
Marlos C. Machado, Marc G. Bellemare, and Michael Bowling. A laplacian framework for option discovery reinforcement learning. Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. 2295-2304, JMLR.org, 2017b.
Marlos C. Machado, André Barreto, Doina Precup, and Michael Bowling. Temporal abstraction in reinforcement learning with the successor representation. J. Mach. Learn. Res., 24(1), January 2023. ISSN 1532-4435.
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learn- ing representation and control in markov decision processes. Journal of Machine Learning Re- search, 8(74):2169-222 2007. URL http: / /mmll httggpppprs////e/g / htt///////maaaaaaa mahadevan07a 7a html.
Rajbala Makar, Sridhar Mahadevan, and Mohammad Ghavamzadeh. Hierarchical multi-agent rein- forcement learning. In Proceedings of the Fifth International Conference on Autonomous Agents, AGENTS '01, pp. 246-253, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 13322X.. 375735. 376302.
doi: 10.1145/375735.376600 URL https: /ttppp://ddci http://......1111111/1111
Martín and G. Mayor. Multi-argument distances. Fuzzy Sets Syst., 167(1):92-100, March 2011. URL
ISSN 14. doi:
Ess 2010.10.0100
Amy McGovern and Andrew G. Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. Proceedings of the Eighteenth International Conference on Machine Learning, ICML '01, pp. 361-368, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558607781.
Vivek Myers, Chongyi Zheng, Anca Dragan, Sergey Levine, and Benjamin Eysenbach. Learning temporal distances: contrastive successor features can provide metric structure for decision- making. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMgR.org, 2024.
Siddharth Nayak, Kenneth Choi, Wenqi Ding, Sydney Dolan, Karthik Gopalakrishnan, and Hamsa Balakrishnan. Scalable multi-agent reinforcement learning through intelligent information aggre- gation. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR. 2023.
Frans A. Oliehoek and Christopher Amato. A Concise Introduction to Decentralized POMDPs. Springer Publishing Company, Incorporated, 1st edition, 2016. ISBN 3319289276.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Proceedings of the Neurul Information Processing Systems Truck on Datasets and Benchmarks (NeurIPS), 2021.
Seohong Park, Oleh Rybkin, and Sergey Levine. Metra: Scalable unsupervised rl with metric-aware abstraction, 2024. URL ptttt:::/arxite org/ abs 2310. 08887.
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, S. M. Ali Eslami, and Matthew Botvinick. Machine theory of mind. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4218-4227. PMLR, 10-15 Jul 2018.
Constantin Ruhdorfer, Matteo Bortoletto, Anna Penzkofer, and Andreas Bulling. The overcooked generalisation challenge. arXiv preprint arXiv:2406. 2ww.224446.799.... 2024.
Alexander Rutherford, Benjamin Ellis, Matteo Gallici. Jonathan Cook, Andrei Lupu, Garar Ingvars- son, Timon Willi, Ravi Hammond, Akbir Khan, Christian Schroeder de Witt, Alexandra Souly, Saptarashmi Bandyopadhyay, Mikayel Samvelyan, Minqi Jiang. Robert Tjarko Lange, Shimon Whiteson, Bruno Lacerda, Nick Hawes, Tim Rocktäschel, Chris Lu, and Jakob Nicolaus Foerster. Jaxmarl: Multi-agent rl environments and algorithms in jax. In The Thirty-eir eight Conference on Neural Information Processing Systems Datasets and Benchmarky Track, 2024.
13

---

Published as a conference paper at ICLR 2026
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Proceed- ings of the 17th International Conference on Autonomous Agents and MuliiAgent Systems, AA- MAS 18, pp. 2085-2087, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: a frame- work for temporal abstraction reinforcement learning. Artif. Intell., 111111))181-211, August 1999. ISSN 0004-3702. doi: 10. 1..10166900443370229900000033330 10.1016 00000 3---7772222 (99) 00052-1.
URL https: /dof org//
Sutton and A.G. Barto. Reinforcement learning: An introduction. IEEE Transactions on Neural Networks, 155:1054-1 1998. doi: 10.1 N..100//NN.19988.711999999 1998.712192.
Sharlin Utke, Jeremie Houssineau, and Giovanni Montana. Investigating relational state ab- straction in collaborative marl. In Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artifi- cial Intelligence and Fifteenth Symposium
Educational Advances in Artificial Intelligence, doi: 10.1609/aaai.
AAAI25/AAAT2//FAATTTS AAAI Press, 2025. ISBN v39:20.35390. URL https: / doi. org / 0 . 1699 aaai v39120. 35390.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding, 2019. URL /tttp:://rxxi......./// http://wwwv.......e..../. alos / 807.03748.
Srinivas Venkattaramanujam, Eric Crawford, Thang Doan, and Doina Precup. Self-supervised learning of distance functions for goal-conditioned reinforcement learning. arXiv preprint arXiv:1907.02998 2019.
Kaixin Wang, Kuangqi Zhou, Qixin Zhang, Jie Shao, Bryan Hooi, and Jiashi Feng. Towards better laplacian representation in reinforcement learning with generalized graph drawing, 2021. URL 05545.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with
efficient approximations, 2018. URL httstt/s:// http///xxvv..o www.:iii..ro/aaaaooo haapg//ab////a/ 1810011110000 04586.
Yuchen Xiao, Joshua Hoffmaan, and Christopher Amato. Macro-action--aased deep multi-agent rein- forcement learning, 2021. URL attps://arxitt wttp://bbbbb/0.006666...
Yuchen Xiao, Weihao Tan, and Christopher Amato. Asynchronous actor-critic for multi-agent re- inforcement learning. In Proceedings of the 36th International Conference Neural Informa- tion Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022, Curran Associates Inc ISBN 9781713871085 1088.
14

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 PRACTICAL EXAMPLES IN REALISTIC SCENARIOS
We present two example scenarios where identifying coordination strategies can drastically acceler- ate the computation of effective solutions in downstream tasks: search-and-rescue team operation and the dynamics of a professional restaurant kitchen.
As the first example, consider a team of Al agents assisting humans in a search and rescue operation. The appropriate strategy for the team depends on multiple factors, such the type of terrain to be explored (e.g.. open fields versus dense forest), the capabilities of the agents involved (e.g.. bipedal robots or drones), and the level of effort required to assist each individual in need (e.g., assist in extracting the human from rubble, or arranging for an ambulance). In dense forests, teams may need to form tight lines or sweep formations to ensure perfect coverage, whereas open fields can often be searched more efficiently by dispersion. Moreover, when victims require substantial assistance, teams may need to alternate between broad search patterns and swift regrouping around targets to deliver help quickly and effectively.
As another example of multi-agent agent collaboration, consider a professional kitchen with multiple AI agents coordinating their activities, operating with maximum efficiency and precision to prepare and serve high-quality dishes as quickly as possible. The complex dynamics of the scenario require both division of labour and synchronisation, with different subsets of the agents pursuing coordinating patterns for preparing ingredients and cooking the dishes while synchronising their activities at specific steps in the recipe, and delivering the dishes to provide good experience for the customers.
Humans often draw on their rich contextual understanding to identify and apply the correct strategy for these (and other such) tasks, although even humans will undergo specialised training to acquire this contextual understanding. On the other hand. learning complex, ied coordination strategies from scratch is extremely challenging for teams of AI agents. Sparse reward (i.e., feedback) signals, non non-stationarities in the dynamics of the domain and the agents, and credit assignment are among multiple reasons that make this learning particularly challenging. The discovery of intermediate coordination patterns (options) that aid in the reliable and efficient com- pletion such tasks by Al agents is central to our efforts; our objective (in this paper) is to develop method capable of identifying these patterns from limited number of interactions with the envi- ronment. Such a method enables the team of agents to focus solely on learning when and where to deploy each strategy, a substantially casier task in complex downstream scenarios. The domains use for experimental evaluation are simplified versions of the complex scenarios described above.
cemporally-xtendde
and var-
A.2 MUTUAL INFORMATION OBJECTIVE PROOF
Next, we provide the proof of Proposition 1 introduced in Section 3.2.
Proposition 1. For any two agent indexes i,j E Z, with i * j. and feature index f E (1,.... F): IS 2)") S I(S"// + [(S zi St'))
Proof. Let A, B, and C' be three random variables such that A, B, C' ~ p(a,,, where p(a, b, c) is the joint distribution, and let T(A B, C) be the Multivariate Mutual Information (MI) estimate for these variables. Then, from the chain rule of MI:
I(A; C) I(A: + B(C
I(A; = +I
and therefore:
I(A;C) T(A;) I(A:; B) + B(A:C]
Given that an MI estimate is always positive. i.c. I(A, 20:
-T(A; BJC) 5
I[A:C) - I(A;)) - IIB;C 50
I(A:C) 1(A; B) B))::))+(AACC
I(A:C| -(AAC))
Replacing A A= Sd. B = B and C ==7²,, obtain the inequality in Proposition 1 (Equation 5).
15

---

Published as a conference paper at ICLR 2026
A.3 CMI MINIMISATION ALGORITHM
Algorithm follows the framework of Dunion et al. (2023) to minimise the CMI estimator defined in Equation 6. The algorithm first samples batch of state pairs from the same time step in trajectory and encodes their dineti-dimenioonll distance. For each pair, it iterates over state features and forms a conditioning term by concatenating the feature value with its corresponding distance component. It then selects the most similar neighbours in the batch (based on this concatenated representation) and constructs negative samples by shuffling the remaining feature values, while the original state pair serves as the positive example. The n-distance estimator is trained adversarially to minimize a discriminator's ability to distinguish positive from negative pairs, thereby reducing correlations between feature values belonging to the same state.
Algorithm CMI minimisation step
Require:
Transitions {50..... S Pai joint-state factorisation function g: S I1 St Parameters for the distance estimator and the discriminator t 1: Factorise each joint state into N single-agent states sf,,...,,.
Require:
g(x), with t (0..... T}.
2: Create single agent state pairs 1 [(s.. st), (sl s²),... (s) (sh-1) -1 x())
3: Concatenate the single agent state pairs into the final batch for CMI minimisation:
Bi. [( sb),.... (v0 . 0)) (. (1), (oT N- )}
4: Initialise LD < and LA + O.
5: Forward pass through multi-feature distance encoder 2n dh (s)2), where st is the n-th pair in the single agent dataset BiJ.
6: for n E (1,..., B do
7: for f E f (I,..., F) do
8:
Create conditioning set cj. (5 zf,a).
Find k nearest neighbours (kNN) of Cfn in the batch: V E, ((ega)² - (cf,e))) )²
9:
10:
Create _e { ..... 1-1, /+1 /+1.....
perm
pemm } by shuffling the kNNs.
11: Calculate discriminator loss:
Ln - Ln + log ol (D = + log (1 (D perm in s.n o fine zz,n)
12:
end for 13: end for
14: Update discriminator parameters to minimise Lp-
15: for n E (1, (1....,N) do
16: for f f do
17:
Calculate adversarial loss: LA +- LA + log (1 - o (DD ,f.()))=ff.)))
18:
end for
19:
end for
20:
Update encoder parameters to minimise CA.
A.4 EPISODIC REWARD ANALYSIS & ADDITIONAL RESULTS
Figure presents an extended analysis our method using episodic returns as the evaluation mea- sure. Beyond the four scenarios discussed in Section 4, we add one additional setting for each domain: 15x15-3p-5f in Level-Based Foraging (LBF) and Asymmetric Advantages in Overcooked. These scenarios, together with the original four, were selected because the IQL baseline finds difficult to compute solutions for these scenarios (Papoudakis et al., 2021; Rutherford et al., 2024), thereby highlighting the improvements achieved by our approach. Similar Figure4, we report the IQM scores with 95% CI for 10 seeds.
A.5 R-DISTANCE REPRESENTATION COMPARISON
Figure 7 compares the outputs the trained n-distance estimator, conditioning on the positions of two agents, for the scalar and multi-dimennsonnl variants. Since the two state features, X and
16

---

Published as a conference paper at ICLR 2026
Nerm
Figure 6: Episodic reward IQM results for the entire suite of environments (including 15x15-3p-5f for LBF and Asymmetric Advantages for Overcooked).
Relative Scalar
Relative MultiDim
(1,4).(1.7)
(7.7). (7.8)
(7,13), (13.7)
Figure/ 7: A visualisation of the n-distance approximator outputs for the scalar and multi- dimensional disentangled variants in 15x15 grid environment with three agents, where we fix positions of two agents and show the n-distance values as the position the third agent varies.
coordinates, are independent and no obstacles are present, the multi-agent temporal distance approximates measure similar standard spatial distance. The sealar estimator computes the n-distance jointly across both axes, whereas the multi-dimensional variant disentangles them by applying the proposed MI penalty. At the centre of these representations lies the Fermat state, point of minimal distance from the fixed coordinates of the teammates.
A.6 EIGENVECTOR COMPARISON
In this section, we offer a more detailed explanation of the differences between eigenvectors com- puted on the inter-agent relative representation of the joint state space, and those obtained by apply- ing eigenoption discovery directly on the raw states. We also extend the visualisation in Figure 2 to incorporate the Kronecker eigenvector (Chen et al., 2022) approximations, and the eigenvectors ob- tained from both the scalar and multi-dimensional n-distance representations presented in Figure 7, not just the latter.
17

---

Published as a conference paper at ICLR 2026
Joint
Kmoecker Product
Relative Scalar
Relative MuRliDm
(1,4), (1,7)
Figure 8: The first five non-trivial eigenvectors resulted from eigenoption discovery on raw joint states, through the Kronecker product of single agent eigenvectors, and the two proposed inter-agent relative representation--asee methods. The conditioning states for the first two agents in the team the coordinates (1,4) and (1,7).
To this end, we fix two agents at specific positions and examine the values of each eigenvector from the perspective of the remaining agent. Under the assumption of agent homogeneity, agents are inter- changeable, and examining the perspective of one agent yields meaningful insight into the team-level subgoals captured by the eigenvectors. We discuss the heterogenous case in detail in Section A.8. This statement holds in particular for cigenvectors that encode coordinated behaviours, whereas the choice of conditioning order can lead different results for more independent behaviours. We found this to be evident in the Kronecker product approximation, where joint eigenvectors are formed as products of multiple single-agent eigenvectors.
Figures 8-10 provide more extensive analysis of the first five non-trivial eigenvectors for each of the four frameworks: Eigenoption discovery on raw joint states (Joint), Kronecker product-based joint option discovery (Kronecker Product), and the two proposed inter-agent relative options (Relative- Scalar and Relative-MultiDimm. We also extend the analysis to three distinct conditioning pairs for the positions of the first two agents: (11,)) ((7,7). and (13,1), Please note the negated version of each eigenvector, as the eigenvectors produce two options with opposite effects.
The key difference between eigenvectors derived from the non-relative and relative representations the lack of responsiveness of the Joint and Kronecker product eigenvectors to different condi- tioning pairs. This effect is pronounced for the Kronecker product eigenvectors, which remain
18

---

Published as a conference paper at ICLR 2026
Joint
Kroeeker Product
Relative - Scalar
Relative MultiDim
(7.7), (7,8)
Figure 9: The first five non-trivial eigenvectors resulted from eigenoption discovery on raw joint states, through the Kronecker product of single agent eigenvectors, and the two proposed inter-agent relative representation-based methods. The conditioning states for the first two agents in the team the coordinates (7,7) and (7,8).
completely unaffected by teammate positions, further validating the absence of interdependence or coupling in the behaviours captured by this method. This effect arises because both the raw joint state and Kronecker product methods emphasise exploration of the state space rather than inter-agent relations. In contrast, by centring the representation around the Fermat state, the relative represen- tation yields behaviours that adapt to diverse team configurations and produce various patterns of agent alignment. While the scalar representation yields behaviours that align the agents at differ- ent distances to each other (on both axes), the multi-dimennional representation enables various in-phase and off- off-phase behaviours to be discovered with different combinations of features. In addi- tion, as we proceed through the set of estimated graph Laplacian eigenvectors, individual elements capture progressively shorter time scales. This is consequence of the orthogonality constraint im- posed by estimating multiple eigenvectors per cycle while using graph-drawing-bant based objectives, ALLO (Gomez et al., 2024).
19

---

Published as a conference paper at ICLR 2026
Joint
Krnneckkr Product
Relative Scalar
Relative MultiDim
Levee
(7.13), (13,7)
Figure 10: The first five non-trivial eigenvectors resulted from eigenoption discovery on raw joint states, through the Kronecker product of single agent eigenvectors, and the two proposed inter-agent relative representation-based methods. The conditioning states for the first two agents in the team the coordinates (7,13) and (13,7).
A.7 OPTION POLICY VISUALISATION
Figure presents rollouts for the first four options, corresponding to the first two relative multi- dimensional eigenvectors described in Section A.6. Each row depicts different agent initialization, illustrating how behaviours dynamically adapt to changes in the coordinates of the Fermat state. The bars on the right of each rollout indicate the n-distance of the final joint state, highlighting the ability of the learned options to selectively align agents along specific state features.
A.8 HETEROGENEOUS STATE SPACES
In this section, we present our extension of the homogeneous state space framework (Section 3) to heterogeneous state spaces. Due to the need for meaningful state-space alignment, we focus on sce- narios in which each agent shares subset of its state features with one or more teammates. Without such shared features, state synchronisation is not a valid strategy for coordination. Furthermore, expect each agent to be able to infer its teammates' types from its observations, either explic- itly, when the observations contain type information, or implicitly, for example by enforcing a clear ordering of features or by using fixed positions in the observation vector. We believe these expecta-
20

---

Published as a conference paper at ICLR 2026
Option
Option 2
Option
Option
Figure 11: Visualisation of the policy roll-outs for the first four learned options in the 15x15 grid environment with four agents, illustrating four distinct state-alignment patterns for multiple initial states. Arrows indicate the actions taken by each agent's policy, colored circles mark the final states (before termination action is triggered), and the white circle denotes the estimated Fermat state corresponding to these final states. The bars the right of each figure show the Fermat n-distance estimates for each feature.
tions are representative of practical multi- collaboration domains, and point to agent modelling techniques (Rabinowitz et al., 2018) as a potential way to relax the latter requirement.
Note that only two modules in our approach operate directly on state information, the pairwise state- distance function d= S* x S R and the Fermat encoder á S S" the homogeneous setting, we had S* = S thereby invalidating the original formulations of these two modules. address this issue, we intro- duce the unified feature space F - Fi, where F denotes the feature set underlying agent i's individual state space Si, indicating which components of the factorised joint state space it includes. For each feature f F let F, denote its domain, defined as the union of all values that feature take across the state spaces of all agents. We then redefine the shared state space as the Cartesian product over all feature domains in the unified feature space, i.e., S* xer- Fy- This definition
NN but this assumption does not hold in heterogeneous domains,
21

---

Published as a conference paper at ICLR 2026
of S" can represent each individual state space Si by padding the features that appear in F but not in F with default values, c.g. zeros. Given the unified single agent state-space S we can retain our original definition of d and Ø; long as d can identify the common features between two heterogeneous agent states and compute their similarity while ignoring any padded values, the rest of our proposed framework distance metries is beyond the scope of this work, we outline (below) a set of guidelines for adapting the temporal state distance approach used throughout this paper to heterogeneous state spaces.
remain unchanged. While full treatment of heterogeneous state
In Section 3, we rely on the temporal successor distance method of Myers et al. (2024) for computing pairwise state distances. We now outline how this method can be extended to heterogeneous state spaces through two main changes:
1. The MRN distance module is provided the source agent's type as an additional input.
2. We modify the sampling of goal states to include randomly shuffled values from states of other agent types, therefore achieving conditional independence to these features, given the source agent's type.
In the original MRN architecture (Liu et al., 2023), the distance encoder is computed as a sum of symmetric and asymmetric parts: do y) (sho(z) ho(y)) + (z)) ho(9))+(l9o0(>) max"_ [max (0, ær:]] and hg and go represent the two halves of the outputs of a encoder network parameterised by 0. In our adaptation, Let st and of be the source and goal state for agent i at time step 1, and 1e the indexed type of this agent. Then, we modify the above expression for heterogeneous states as: da (s), gi. (*) go (gi. [-) When si and of correspond to the same state
(o)ll.. where Azz)
extend this expression to include the agent type as follows.
A (hho(s), type, 1 is redundant. However, as stated in our second proposed change, the padded features of gi, {flf E F* A & FiJ, are randomly sampled from the goal states of agents of different types to i, resulting in the conditional invariance discussed above.
ho(gi, 1²)) + [90(s),
Empirical analysis. To demonstrate the effectiveness of this extension, we constructed two het- erogeneous toy scenarios by adapting the LBF environment to include two agent types: Type (X axis only) agents and Type 2 (X & Y axes) agents. Type 1 agents' states only contain the X-axis coordinate, and their action space no longer includes the "Left" and "Right" horizontal movement actions. Type 2 agents have full (z; y) state representations and can move along both axes, akin to the agents the original environment.
Our experiments use two domain configurations. The first is a 10x10 grid containing one Type and one Type agent. The second is a 15x15 grid with three agents, where one agent is Type I and the remaining two are Type 2. The first configuration aims to analyse whether agents of different types can successfully identify and synchronise solely on their common features, while the second configuration examines whether selective alignment can be achieved between multiple agents that share different numbers of features.
Figure 12 illustrates the eigenvectors learned using our proposed heterogeneous extension for the two distinct agent types in the first configuration (10x10 10 grid). Since the two agents share only single feature, the eigenvectors are identical from both perspectives, resulting in behaviours that align the agents solely along that feature. The lower part of the figure shows roll-outs from the first three option policies derived from the eigenvectors. The first option perfectly aligns the agents along the shared X-axis coordinate while completely disregarding the Y-axis. The second option aligns them along the Y-axis, ignoring the X-axis. The third policy positions the agents a specific distance along the same axis, demonstrating behaviours at different time scales.
Figure 13 presents a similar analysis for the second configuration (15x15 grid). With the addition of another agent of Type 2, the eigenvectors enable these two agents to align along both axes of move- ment, while considering the third agent only with respect to the shared feature. This demonstrates the ability of the state alignment to occur selectively based on agent types. Specifically, the second eigenvector aligns an agent precisely with the Y-axis coordinate of its same-type teammate, while the third eigenvector captures behaviours that align all agents along the X-axis but only the corre- sponding ones (Type 2) along the Y-axis. We further support this observation by showing roll-outs from the trained option policies, which clearly exhibit these behaviours.
22

---

Published as a conference paper at ICLR 2026
Type 1
Type 2
(1,7)
(4.13)
(7,4)
(1.0)
(4.0)
(7,0)
Option
Option
Option 3
The first three eigenvectors, along with the first three options obtained using the proposed heterogencous approach for 10x10 grid with two agents of distinctive types: Type and Type 2. The top part the figure illustrates the eigenvectors, conditioned on the teammate's position at different coordinates, while the bottom part shows the roll-outs for the first three options generated. With padding, the Y-coordinate of the Type 1 agent is replaced with the value 0. We use diagonal stripes to identify the Type-1 agent in the grid.
Figure 12:
A.9 ROD CYCLE DISCUSSION
We adopt the original ROD cycle of Machado et al. (2017a) to approximate eigenoptions, estimating multiple eigenvectors within a single cycle. This design ensures orthogonality among eigenvectors, property that enables options to function at different time scales. By contrast, other frameworks extract only one eigenvector per cycle, requiring multiple cycles to generate a full set of options, as in covering options (Jinnai et al., 2019h; Chen al., 2022) and covering eigenoptions (CHO) (Machado et al., 2023). Covering options provide exploration guarantees by leveraging the Fiedler eigenvector produce policies that connect the farthest points in the faaeettransiionn graph, objective where orthogonality plays little role (Jinnai et al., 2019b). Our focus, however, is on discovering sets of cooperative behaviours that express diverse alignment patterns. In our experiments with CEO, the most recent framework, we found the resulting eigenvectors to exhibit limited diversity, see Figure 14, reinforeing our decision return to the original approach.
23

---

Published as a conference paper at ICLR 2026
Type
Type 2
(1.4). (1.7)
(7.7). (7.8)
(4.7). (7.1)
(1.0). (1.7)
(7.0), (7,8)
(4.0). (7.1)
Option
Option 2
Option
Figure 13: The first three eigenvectors, along with the first three options obtained using the proposed heterogeneous approach for a 15x15 grid with three agents distinctive types: one agent of Type 1 and two agents Type 2. The top part of the figure illustrates the eigenvectors, conditioned on the teammate's ' position at different coordinates, while the bottom part shows the roll-outs for the first three options generated. With padding, the Y-coordinate of the Type agent is replaced with the value O. We use diagonal stripes to identify the Type-1 agent in the grid.
A.10 IMPLEMENTATION DETAILS HYPERPARAMETERS
Our implementations for the proposed discovery methods, baselines, and visualisations can be found at: https: :ttp::///iitie /tttthggttbtttt//// com/ homm/ruu Maulsteeeecc/ARe.
n-distance training. We followed the publicly available implementation of successor distances from Myers et al. (2024) when integrating the CMD-1 architecture into our codebase. The temporal distance encoder dg is trained using the symmetrised InfoNCE contrastive loss (without resubstitu- tion) (van den Oord et al., 2019), suggested in the original work. We jointly train this encoder with the Fermat encoder Φ using joint states sampled from random joint policy and factorised as described in Section 3. Positive pairs for the InfoNCE loss are constructed by pairing current and future states from each agent's s trajectory individually, without cross-agent mixing, while negatives generated through in-batch shuffling, allowing combinations of states from different agents. To train the Fermat encoder, we incorporate d, into the objective Equation 4 using a stop- cop-gradient operator. When using multi-dimensional n-distance df. insert lightweight linear projection to
24

---

Published as a conference paper at ICLR 2026
Cycle:1
Cycle: 2
Cycle:
Cycle:
Cycle:
(1.7)
(7,8)
Figure 14: The eigenvectors generated by five consecutive CEO cycles, where once discovered, the option is introduced in the action space of the agents for exploration in the next phase.
map outputs scalar for contrastive loss computation. This projection is discarded after training, restoring the full multi-dimensional relative states. For Fermat encoder training, we instead sum the distance dimensions, since errors on each dimension are weighted equally for this step.
In some scenarios, e.g., Overcooked Forced-coord and Asymmetric Advantages, agents cannot ac- cess the same states, as they are separated by walls. This causes the temporal distance estimator to encounter single-agent state combinations not present in training, resulting in noisy predictions. To mitigate this, we omit the feature causing the heterogeneity (the coordinate) during state fac- torization. We note that this issue is tied to the temporal distance model itself, and our framework would operate successfully with any distance function not affected by this problem. We present the full list of hyperparameters for n-distance estimation training in Table 1.
Hyperparameter
LBF
Overcooked
Distance encoder learning rate
0.001
0.00005
Fermat encoder learning rate
0.001
0.00005
Optimizer
Adam (Kingma & Ba, 2017)
Adam (Kingma & Ba, 2017)
Distance encoder hidden layers
[256, 256]
[256, 256]
Distance encoder dimension (per feature)
12
Fermat encoder hidden layers
[256, 256]
[256, 256]
Minibatch size
100
100
# of epochs
10
10
Discriminator (CMI) learning rate
0.0003
0.0001
Discriminator hidden layers
[256, 256]
[256, 256]
# kNNs
15
15
Penalty weight
0.003
0.0003
Table I: Hyperparameters for training the n-distance estimator, for the scalar variant (up to the horizontal line) and multi-dimensional variant (the entire set).
25

---

Published as a conference paper at ICLR 2026
ALLO training (Eigenvector approximator). We used the same dataset train the eigenvec- tor encoder ALLO as for n-distance training. We followed the publicly available implementation referenced in Gomez et al. (2024), with similar hyperparameter configurations: two layers of 256 dimensions and barrier coefficient initiation value 2.
Joint option policy training. For joint option policy training, used separate IQL architec- tures for each eigenvector sign (positive and negative), without parameter sharing, to accom- modate potentially distinct agent behaviours. The environmental reward is thus replaced with & = els']= e(s]. for each eigenvector e and two subsequent states s, Table 2 lists the hyperparameters used for option policy training.
Hyperparameter
LBF
Overcooked
Learning rate
0.001
0.001
Anneal learning rate
False
False
Optimizer
Adam (Kingma & Ba, 2017) [64, 64]
Adam (Kingma Ba, 2017)
Hidden layers
[32,32]
CNN features
[16,16,16]
CNN Kerne dims
[[5.5]. [3,3], [3,3]]
Parallel environments
32
16
Rollout steps
10
10
0.99
0.99
Buffer size
5000
10
Buffer batch size
32
128
Target update interval
10
10
Maximum gradient norm
10
start
1.0
1.0
decay
0.1
0.1
finish
0.05
0.05
evaluation
0.05
0.05
Learning starts at timestep
5000
1000
# of epochs
4
4
training steps
106
106
Table 2: Hyperparameters used for training the joint opinion policies.
MacDec-POMin training. We integrated the discovered set of options additional actions in the original action space of each individual agent. For the backbone IQL implementation, we used an RNN decentralised architecture, trained with the set of hyperparameters presented in Table 3. We used the same list of hyperparameters when training IQL enhanced with options generated from each option discovery framework. To support the training of the decentralised policy additionally integrated previous SMDP training techniques like training primitive actions on option policy steps, intra-option learning and option interruption (Sutton al., 1999). When integrating intra-option learning, we only reused the experiences of the executing joint option to train others when there was an exact match for the actions of each individual agent. For option interruption, we follow the be interrupted if (H W) < (HH ), for any agent currently following that option.
options,
improvement theorem from Sutton & Barto (1998) and enable option w to
A.11 LLM USAGE DECLARATION
In this work, the of LLMs kept to minimum, providing limited support in writing tasks such as grammar correction and synonym search.
26

---

Published as a conference paper at ICLR 2026
Hyperparameter
LBF
Overcooked
Learning rate
0.0005
0.0005
Anneal learning rate
True
True
Optimizer
Adam (Kingma & Ba, 2017)
Adam (Kingma Ba, 2017)
Hidden layers
[128, 128]
[128, 128]
CNN features
[32,32,32]
CNN Kernel dims
[[5,5], [3,3], [3,3]]
Parallel environments
32
16
Rollout steps
20
10
Y
0.99
0.99
Buffer size
5000
10a
Buffer batch size
128
128
Target update interval
10
100
Maximum gradient norm
10
c start
1.0
1.0
decay
0.1
0.1
e finish
0.05
0.05
evaluation
0.05
0
Learning starts at timestep
5000
1000
# of epochs
4
4
# training steps
2 x 107
107
step limit for option execution
50
50
Table Hyperparameters used for Mac-DePPOMDP training.
27


Reviews:
[{"review_id": "zWNLqw1qVs", "reviewer": "Reviewer_Sm3d", "summary": "This paper presents a framework for discovering temporally extended actions (options) in MARL settings. The authors propose a method that compresses the joint state space into a latent representation centered around a \"Fermat state\". This abstraction enables the discovery of coordinated behaviors by focusing on inter-agent relational dynamics rather than raw joint states. Empirical evaluations in Level-Based Foraging and Overcooked domains demonstrate that the proposed method outperforms existing option discovery techniques and baseline MARL algorithms, particularly in tasks requiring strong coordination.", "questions": "Is the proposed option learning generalizable to different environments? \n\nWhat is the difficult part of extending beyond 2 agents?", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "By introducing the Fermat state and leveraging n-distance metrics, the authors effectively re-center the representation space to emphasize coordination. The use of multi-dimensional disentangled representations allows for richer behavioral diversity, and the mutual information constraint ensures that each feature contributes meaningfully to the learned options. \n\nThe empirical results are thorough, covering multiple domains and scenarios, and the visualizations of eigenvectors provide intuitive insights into the discovered coordination patterns. The integration of the framework into the MacDec-POMDP model and the use of decentralized training further enhance its practical relevance.", "weaknesses": "I am not familiar with this area, so hard to understand the motivation. It is expected to show more background and examples about the problem. \n\nThe reliance on homogeneity among agent state spaces limits its applicability to more diverse multi-agent systems. The assumption of full observability and shared information among agents, while practical for evaluation, may not hold in real-world scenarios. \n\nThe computational overhead introduced by multi-dimensional distance estimation and mutual information regularization might be significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r5iHXOnZ1v", "reviewer": "Reviewer_gMWz", "summary": "This paper tackles multi-agent option discovery by proposing an inter-agent relative state abstraction that centers the joint state around a “Fermat state” of maximal alignment, measures team “spreadness” per feature dimension via learned temporal distances, then discovers options by estimating Laplacian eigenvectors on this relative representation rather than on the raw joint state. The key idea is that synchronisation patterns between agents are a natural substrate for coordination, so compressing the joint state into a feature-wise, alignment-centric embedding both reduces option count and biases discovery toward genuinely joint behaviours. The method trains a Fermat encoder together with a temporal distance model, adds a conditional mutual information regularizer to keep each feature’s distance prediction focused on its own signal, and adapts MacDec-POMDPs to execute joint options under simple team-level synchronisation assumptions. Experiments on Level-Based Foraging and Overcooked show that options learned on the relative representation improve IQL downstream performance and often beat options produced by raw joint state or Kronecker-product constructions.", "questions": "Can you report sensitivity to the number of eigenvectors and to the size and policy used to collect the 500k transition dataset for distance and Laplacian estimation, in particular, how do option quality and downstream performance vary when the dataset is smaller or when trajectories come from a partially coordinated policy rather than random, can you quantify how the accuracy of the temporal distance model affects discovered options, for example by adding noise or using a weaker successor-distance estimator, can you provide a diagnostic of the synchronisation motifs your eigenoptions encode, for instance by plotting controlled rollouts that show which feature subsets a given option aligns, can you stress test the joint option initiation and information sharing assumptions, for example by injecting delays or dropouts into the shared signals and reporting how often options fail to trigger, can you add a small heterogeneous-agents study, even synthetic, to illustrate how the approach might extend beyond identical S* spaces.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper isolates a real bottleneck in multi-agent option discovery, the exponential blow-up of joint state spaces and the tendency to produce loosely coupled skills, then proposes an elegant fix, compress the joint state via a Fermat-state-centred, feature-wise temporal distance representation that foregrounds coordination structure. The learning objective for the Fermat encoder and temporal distances is straightforward, the use of successor-style temporal distances fits the coordination intuition and is representation agnostic, the conditional mutual information penalty is a thoughtful touch to keep features disentangled and to avoid degenerate solutions, the adaptation of MacDec-POMDPs to joint options with simple voting and synchronisation assumptions is clearly described and easy to implement. On the empirical side, the method improves IQL on LBF and Overcooked, it outperforms Kronecker-product options and raw joint-state options, the multi-dimensional variant is especially helpful in the richer Overcooked feature space, and the ablations align with the story the paper tells.", "weaknesses": "The empirical scope is still moderate for ICLR standards, two domains and a few scenarios, the evaluation would benefit from additional environments with heterogeneous agent state spaces where the homogeneity assumption breaks, and from tasks with explicit communication limits to stress the information sharing assumption used during joint option selection. Sensitivity to key choices is only partially explored, for example the number of eigenvectors retained, the dataset size for pretraining the distance and Laplacian estimators, the effect of temporal distance quality on option quality, and the robustness of the CMI regularizer. The assumptions for joint option initiation and information sharing are reasonable for a first pass, yet the paper could better characterise failure modes when the “enough agents agree” condition is not met, or when shared observations are stale. Finally, while Figure 2 is very helpful, a more systematic probe into what kinds of synchronisation patterns each discovered option encodes would make the contribution crisper, for example, controlled grid tests that manipulate only one relational factor at a time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UfqoQXCzv9", "reviewer": "Reviewer_TBjq", "summary": "This work tackles the problem of option discovery in multi-agent reinforcement learning (MARL), where existing methods (like Eigenoptions) are impractical because they discover too many options, scaling with the massive joint state space. The authors introduce a novel inter-agent relative state abstraction that compresses this joint state space into a compact latent representation. This abstraction is centered around the \"Fermat state,\" which represents the point of maximal alignment among agents, thereby focusing the discovery process on inter-agent relational dynamics rather than the full state space. By discovering options within this compressed, relation-focused space, the method drastically reduces the number of options and encourages the emergence of highly coordinated joint behaviors.", "questions": "Please see the Weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Novel State Abstraction: The core contribution is a new inter-agent relative state abstraction centered around the \"Fermat state.\" This is a new technique for compressing the massive state space. A direct, practical benefit of this abstraction is that it drastically reduces the number of options that need to be discovered, making the problem computationally tractable. The abstraction is not just a random compression; it's designed to focus the discovery process on inter-agent relational dynamics and synchronization. This is highly relevant for cooperative tasks.\n\n2. The method is empirically shown to discover options that represent highly coordinated joint behaviors, which is the goal of many MARL tasks. The paper demonstrates that its method discovers a more diverse and generalizable set of coordination skills that can better support agents in various downstream tasks compared to other methods.", "weaknesses": "1. The authors define the distances between agents' states using the Fermat inter-agent state distance and further approximate this distance by learning a parameterized function. The training process for this function seems to map the joint state space to a single-agent state space by minimizing a temporal distance. The authors claim that this distance metric is capable of comparing the similarity between the states of two agents. However, it is unclear whether this temporal distance can distinguish between the states of two agents, since agents may have different states at the same time step. Moreover, what are the differences between an agent's observations and its 'single state'?\n\n2. The proposed method requires that the MI between each feature distance and the remaining state-feature pairs does not exceed the MI between the feature pairs themselves. Why not directly maximize the MI objective between the state-feature pair and the random vector $Z$? This would also seem to distinguish different features.\n\n3. More evaluations on some commonly used benchmarks, such as SMAC and GRF, should be included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qjRgOWI0tE", "reviewer": "Reviewer_KghA", "summary": "This paper targets at multi-agent option discovery. Specifically, they propose a joint-state abstraction that compresses the state space while preserving the information necessary to discover strongly coordinated behaviors.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Multi-agent option is an important and challenging research problem.\n- This paper is tecnically solid and theretically grouned.\n- The comparison with related work is comprehensive.", "weaknesses": "- MAPPO results are not provided for overcooked tasks.\n- Please provide a discussion on the computation cost compared to other methods.\n- Please provide a discussion on the compatibility with mainstream MARL methods, such as. VDN and MAPPO. Can they be integrated together?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)