Towards Principled Unsupervised Multi-Agent Reinforcement Learning

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper provides the first principled theoretical treatment of unsupervised pre-training in multi-agent RL (MARL) via state entropy maximization. It characterizes three competing objectives (joint, disjoint, mixture entropy), proves mixture entropy offers the best tractability-performance trade-off, and introduces TRPE, a decentralized trust-region algorithm that directly optimizes single-trial objectives in convex Markov Games.

Problem

Unsupervised pre-training via state entropy maximization is well-understood in single-agent RL, but no principled multi-agent counterpart existed. Prior MARL work using entropic objectives was empirical, reward-shaping-based, and lacked: (1) formal problem formulation as convex Markov Games, (2) theoretical comparison of alternative objectives, and (3) algorithms that directly optimize finite-trial objectives rather than infinite-trial surrogates that fail at deployment.

Method

The paper frames multi-agent unsupervised pre-training as solving a convex Markov Game (cMG) equipped with an entropy functional. Three objectives are formalized: - Joint entropy: maximize H(d^π) over the joint state distribution — optimal in theory but exponentially hard in practice due to |S| scaling exponentially with N agents. - Disjoint entropy: each agent independently maximizes its own marginal entropy H(d^π_i) — tractable but breaks coordination incentives. - Mixture entropy: maximize H(d̃^π) where d̃^π = (1/N)Σ d^π_i — a uniform mixture of marginals over a shared state space; decomposes as average disjoint entropy plus sum of KL divergences, encouraging agent diversity (clustering).

TRPE (Trust Region Pure Exploration): A decentralized algorithm targeting the single-trial (K=1) objective. Each agent optimizes a per-agent surrogate function via importance sampling (IS) estimators of the empirical entropy, subject to a KL-divergence trust-region constraint (DKL(π̃^i || π^i) ≤ δ). Agents operate concurrently using only decentralized-information policies; no centralized critic is required.

Key Contributions

• First principled formulation of multi-agent state entropy maximization as a convex Markov Game (cMG), with three distinct objective families (joint, disjoint, mixture) in both infinite- and finite-trial variants.
• Lemma 4.1 (Entropy Mismatch): Proves ordering H(d^π)/N ≤ (1/N)ΣH(d^π_i) ≤ H(d̃^π) ≤ sup H(d^π_i) + log|N| ≤ H(d^π) + log|N|, showing mixture is a tight lower bound to joint entropy.
• Theorem 4.2 (Finite-Trials Mismatch): Shows that for mixture objectives the infinite/finite-trial performance gap scales as O(√(|S̃|/(N·K))), i.e., sub-linearly in N — more agents reduce deployment mismatch, unlike joint objectives where |S| grows exponentially with N.
• Demonstrates that independent policy gradient over infinite-trial non-disjoint objectives converges (Fact 4.1), but optimizing these leads to poor single-trial performance.
• TRPE: first decentralized algorithm explicitly addressing single-trial cMG objectives.
• Empirical extension of single-agent unsupervised RL findings to multi-agent settings, including zero-shot transfer results.

Results

• State entropy optimization (secret room, T=50): Mixture objectives optimize both joint and mixture entropy effectively; joint/disjoint objectives fail to coordinate and either over- or under-explore.
• Downstream sparse-reward learning (secret room, T=150): TRPE with mixture pre-training converges faster than uniform initialization; joint pre-training yields no improvement.
• Short-horizon pre-training (secret room, T=50): Mixture pre-training leads to substantially higher returns; disjoint pre-training is actively harmful (deterministic policies, no coordination).
• Zero-shot generalization (2-agent MaMuJoCo Reacher, T=100): Joint and mixture pre-training both achieve zero-shot performance matching MA-TRPO after 2×10⁴ samples; disjoint fails. Mixture shows lower variance than joint, with no worst-case initializations below random baseline.
• All results reported as average and 95% CI over 4 runs.

Limitations

• Monte Carlo estimation of single-trial objectives is sample-inefficient in high-dimensional tasks; more efficient estimators for convex RL remain an open problem.
• Plug-in entropy estimator requires discrete state spaces; extension to continuous domains requires separate contributions.
• Mixture objective assumes a shared per-agent state space (Assumption 3.1, Uniformity); applicable in homogeneous agent settings but requires padding for heterogeneous state spaces.
• Experiments use small-scale environments (2-agent secret room, 2-agent Reacher) for interpretability; large-scale validation is left as future work.
• Convergence guarantees for decentralized-information policies in finite-trial cMGs remain open.

Relevance to Agentic AI / LLM Agents

State entropy maximization as unsupervised pre-training is directly relevant to reward-free skill discovery and environment exploration in multi-agent systems — a foundational challenge for deploying autonomous agent teams without dense reward specification. The theoretical result that mixture objectives scale favorably with agent count has practical implications for designing pre-training curricula in collaborative LLM-agent pipelines (e.g., role-diverse agent pools), where each agent should cover distinct behavioral modes. TRPE's decentralized design aligns with the architectural constraint in most real LLM-agent deployments, where a shared global policy is impractical. This work also provides a rigorous bridge between single-agent unsupervised RL theory and multi-agent settings, establishing foundations for task-agnostic capability pre-training in agentic AI systems.