EFXPLORER: Cooperative Multi-Agent Reinforcement Learning via Epigraph-Form Guided Exploration

How can a multi-agent team discover new strategies
while preserving its existing coordination capabilities?

Baseline: MAPPO-Linear

Coordination collapse. Naively adding exploration bonus distorts the objective.

\(r = r^{\mathrm{ext}} + \beta\, r^{\mathrm{int}}\)

EFXPLORER

Emergent coordination. Exploration is allowed only while the budget lasts and task progress is preserved.

\(\min\{ A^{\mathrm{ext}},\, V^{\mathrm{int}} - z \}\)

TL;DR: EFXPLORER promotes individual exploration while preserving team performance using an epigraph reformulation with adaptive exploration budgets.

Method

Epigraph-form constrained exploration

\[ \begin{aligned} &\max_{\textcolor{#5b21b6}{z}}\; \textcolor{#5b21b6}{z} := \sum_{i\in\mathcal{N}} z^i \\[0.35em] \text{s.t.}\quad &\max_{\boldsymbol{\pi}}\;\min\Big\{\, \textcolor{#b91c1c}{J_{\mathrm{ext}}(\boldsymbol{\pi}) - J_{\mathrm{ext}}(\hat{\boldsymbol{\pi}})}\,,\; \textcolor{#1d4ed8}{J_{i,\mathrm{int}}(\pi^i) - z^i} \Big\} \ge 0,\quad \forall i \in \mathcal{N} \end{aligned} \]

\[ \begin{aligned} &\max_{\textcolor{#5b21b6}{z}}\; \textcolor{#5b21b6}{z} := \sum_{i\in\mathcal{N}} z^i \\[0.35em] \text{s.t.}\;\; &\max_{\boldsymbol{\pi}}\;\min\Big\{\, \textcolor{#b91c1c}{J_{\mathrm{ext}}(\boldsymbol{\pi}) - J_{\mathrm{ext}}(\hat{\boldsymbol{\pi}})}\,, \\[0.2em] &\qquad\qquad\;\; \textcolor{#1d4ed8}{J_{i,\mathrm{int}}(\pi^i) - z^i} \Big\} \ge 0,\;\; \forall i \in \mathcal{N} \end{aligned} \]

Overview of EFXPLORER: (a) conservative exploration framework with exploration budgets and an epigraph min objective; (b) successor distance-based intrinsic reward from factorized per-agent episodic novelty.

EFXPLORER overview with the adaptive exploration budgets highlighted.

Overview

EFXPLORER maximizes each agent's intrinsic return while ensuring the team's extrinsic return does not degrade. Using an epigraph reformulation, it alternates between policy updates under a stepwise min-bottleneck and updates of the exploration budgets.

Adaptive exploration budgets

\(m^\ast = \arg\max_{m\in\mathcal{F}_k} \sum_i \hat{z}^{\,i,k,m}_0,\qquad z^{i,k+1}_0 \leftarrow \alpha_z\, \hat{z}^{\,i,k,m^\ast}_0 + (1-\alpha_z)\, z^{i,k}_0\)

The outer loop grows the intrinsic return budgets \(z^i\) only from rollouts whose task return beats a running reference, moving them toward the one with the largest collective intrinsic return at rate \(\alpha_z\).

Stepwise epigraph bottleneck

\(\mathcal{B}^{\mathrm{epi}}_{i}(\tilde{s}^i_t,\mathbf{a}_t) \triangleq \min\{\textcolor{#b91c1c}{A^{\mathrm{ext}}_{\hat{\boldsymbol{\pi}}}(s_t,\mathbf{a}_t)},\; \textcolor{#1d4ed8}{S^{\mathrm{int}}_{i}(\tilde{s}^i_t,\mathbf{a}_t)}\},\qquad S^{\mathrm{int}}_{i}(\tilde{s}^i_t,\mathbf{a}_t) \triangleq \mathbb{E}_{\tau\sim\boldsymbol{\pi}}\Big[\sum_{k=t}^{\infty}\gamma^{k-t} r^{\mathrm{int}}_{i,k} - z^i_t \,\Big|\, \tilde{s}^i_t,\mathbf{a}_t\Big]\)

The episode-level constraint is turned into a per-step signal by augmenting the state with the remaining budget. Each agent's update is driven by the smaller of the reference task advantage and its intrinsic surplus, so exploration proceeds only while it does not hurt task progress.

Long-horizon novelty via successor distance

\(\textcolor{#1d4ed8}{r^{\mathrm{int}}_{i,t}(s^i_t)} = \min_{k \in [0,t)} d_{\phi_i}(s^i_k, s^i_t)\)

Each agent learns a quasimetric successor distance on its own state space. The intrinsic reward is the minimum learned temporal distance to the states already visited in the episode, pushing agents toward temporally distant states rather than locally surprising ones.

Results

VMAS-balance

VMAS-give way

VMAS-transport

VMAS-wheel

MPE-corridor

MPE-tag

SMAX 3s5z_vs_3s6z

SMAX 5m_vs_6m

Comparison to Cooperative MARL Baselines

Comparison to Alternative Formulations

Normalized average return on MPE-corridor, VMAS-balance, VMAS-give way, and SMAX-3s5z_vs_3s6z for EFXPLORER versus MAPPO-Linear with beta 0.02, 0.1, 1 and MAPPO-Lagrangian with lambda0 0.2 and 1.

Ablation Study

Sensitivity analysis on VMAS-transport comparing MAPPO-Linear across beta values with EFXPLORER across budget update rates alpha_z.

\[ \underbrace{r = r^{\mathrm{ext}} + \beta\, r^{\mathrm{int}}}_{\text{MAPPO-Linear}} \quad\text{vs.}\quad \underbrace{z^{i} \leftarrow \alpha_z\,\hat{z}^{i} + (1-\alpha_z)\,z^{i}}_{\text{EFXPLORER}} \]

In MAPPO-Linear, a poor choice of the mixing coefficient \(\beta\) can lead to coordination collapse, whereas in EFXPLORER, varying the budget update rate \(\alpha_z\) only changes how quickly exploration expands.

State factorization ablation across VMAS-balance, VMAS-give way, and VMAS-transport comparing EFX-MA, EFX-MA-Joint, EFX-MA-Obs, EFX-I, EFX-I-Joint, and EFX-I-Obs.

\[ r^{\mathrm{int}}_{i,t} = \min_{k \lt t} d_{\phi_i}(x_k, x_t),\qquad x = \underbrace{s^i}_{\text{Ours}} \;\big|\; \underbrace{s}_{\text{Joint}} \;\big|\; \underbrace{o^i}_{\text{Obs}} \]

Measuring successor distance on joint states suffers from high dimensionality, while measuring it on observations inherits teammate-induced non-stationarity.

Intrinsic reward ablation on VMAS-balance and MPE-corridor comparing EFX-MA with successor distance against Pseudo-counts, Entropy, and Network distillation.

\[ r^{\mathrm{int}}_{i,t} = \underbrace{\min_{k \lt t} d_{\phi_i}(s^i_k, s^i_t)}_{\text{Ours}} \;\big|\; \underbrace{\big(N(s^i_t)+1\big)^{-1/2}}_{\text{Pseudo-counts}} \;\big|\; \underbrace{-\log d(s^i_t)}_{\text{Entropy}} \;\big|\; \underbrace{\big\lVert \hat{f}_{\theta}(s^i_t) - f(s^i_t) \big\rVert^2}_{\text{Network distillation}} \]

Long-horizon successor distance outperforms short-term novelty bonuses (Pseudo-counts, Entropy, Network distillation), especially on MPE-corridor.

Feasibility set ablation across VMAS-balance, VMAS-give way, and VMAS-transport comparing running reference EFX-MA and EFX-I against strict best-return EFX-MA-Strict and EFX-I-Strict.

\[ \begin{gathered} \mathcal{F}_k = \{\, m : \hat{J}^{\mathrm{ext}}_{k,m} > \bar{J}^{\mathrm{ext}}_k \,\} \\[0.4em] \bar{J}^{\mathrm{ext}}_k = \underbrace{(1-\alpha_{\mathrm{ref}})\,\bar{J}^{\mathrm{ext}}_{k-1} + \alpha_{\mathrm{ref}}\,\hat{J}^{\mathrm{ext}}_{k-1,m^\ast}}_{\text{Ours}} \;\big|\; \underbrace{\max_{k'\le k} \hat{J}^{\mathrm{ext}}_{k'}}_{\text{Strict}} \end{gathered} \]

A strict best-return threshold is vulnerable to noisy return spikes, which stalls budget growth.

Cooperative Multi-Agent Reinforcement Learning via Epigraph-Form Guided Exploration

How can a multi-agent team discover new strategies
while preserving its existing coordination capabilities?

SMAX 5m_vs_6m: five allied marines (blue) vs. six enemy marines (green)

TL;DR: EFXPLORER promotes individual exploration while preserving team performance using an epigraph reformulation with adaptive exploration budgets.