PaperlayerView exact revision on arXiv

Source-linked AI summary

MAVEN: Multi-Agent Variational Exploration

Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, Shimon Whiteson

arXiv:1910.07483v2cs.LGstat.ML

TL;DR

The paper studies how QMIX’s representational constraints affect exploration and optimality in decentralised MARL. It proposes MAVEN, which uses hierarchical latent-variable control and mutual-information training for committed exploration, and reports significant improvements on SMAC. A variational approximation can introduce a gap between the true mutual-information objective and its lower bound, particularly for continuous latent variables.

  • Problem

    QMIX and similar CTDE methods may combine decentralisation constraints with inefficient exploration, producing provably poor exploration and suboptimality.

  • Method

    MAVEN hybridises value- and policy-based methods through a shared latent variable controlled by a hierarchical policy, with mutual-information maximisation encouraging diverse behaviours.

  • Results

    MAVEN achieves significant performance improvements on the challenging SMAC domain, performing substantially better than alternatives on Super Hard maps.

  • Takeaways & Limitations

    Committed, temporally extended exploration provides MAVEN with a mechanism for discovering coordinated joint strategies while respecting decentralised value-factorisation constraints.

  • Takeaways & Limitations

    A poor variational approximation can reduce performance by widening the gap between the true objective and its lower bound, especially with continuous latent variables.

Abstract

from arXiv · show

Centralised training with decentralised execution is an important setting for cooperative deep multi-agent reinforcement learning due to communication constraints during execution and computational tractability in training. In this paper, we analyse value-based methods that are known to have superior performance in complex environments [43]. We specifically focus on QMIX [40], the current state-of-the-art in this domain. We show that the representational constraints on the joint action-values introduced by QMIX and similar methods lead to provably poor exploration and suboptimality. Furthermore, we propose a novel approach called MAVEN that hybridises value and policy-based methods by introducing a latent space for hierarchical control. The value-based agents condition their behaviour on the shared latent variable controlled by a hierarchical policy. This allows MAVEN to achieve committed, temporally extended exploration, which is key to solving complex multi-agent tasks. Our experimental results show that MAVEN achieves significant performance improvements on the challenging SMAC domain [43].

1 Introduction

Cooperative MARL under CTDE faces exponential joint-action spaces and decentralised execution constraints. The paper argues that QMIX’s monotonic factorisation creates exploration and suboptimality problems, motivating MAVEN’s committed-exploration approach.

  • Cooperative MARL must address exponentially growing joint action spaces and decentralised execution under partial observability and communication constraints.
  • QMIX factorises joint values into individual utilities and combines them monotonically, enabling tractable decentralised action selection but restricting value approximations.QTRAN instead uses linear constraints and L2 penalties, trading representational flexibility against tractability.
  • Decentralised MARL suffers from inefficient exploration that can interact with representational constraints, pushing learning toward suboptimal policies.The paper reports that standard single-agent remedies do not ensure the same outcome in decentralised MARL.
  • Committed exploration coordinates exploratory actions over extended time steps, which is important for discovering temporally extended joint strategies.Existing CTDE methods are described as lacking this capability.
  • MAVEN introduces a shared latent variable controlled by a hierarchical policy, allowing value-based agents to learn diverse, episode-long exploratory behaviours.The approach hybridises value- and policy-based methods and uses mutual-information maximisation to encourage behavioural diversity.

2 Background

The paper formalises cooperative partially observable tasks as Dec-POMDPs under CTDE, where centralised training precedes decentralised local-history action selection. QMIX achieves tractable decentralisation through monotonic value factorisation, while QTRAN pursues optimal decentralisation with an intractable constraint formulation.

  • Dec-POMDP formulation: A cooperative task is modelled as a Dec-POMDP with states, actions, transitions, shared rewards, observations, agents, and discounting.
  • Centralised training with decentralised execution: During centralised training, the learner accesses all agents’ histories and the full state, whereas execution restricts each agent to its local action-observation history.
  • Decentralisability: Decentralisability requires individual utilities whose separate argmax actions jointly recover the optimal decentralised action.
  • QMIX: QMIX combines individual utilities through a monotonic mixer, enabling decentralised argmax selection and joint-action maximisation in O(n|U|) time.Its nonnegative mixer weights enforce the monotonicity condition.
  • Related value-based methods: QMIX uses ϵ-greedy exploration over individual utilities, while VDN imposes the stricter additive factorisation.QTRAN seeks optimal decentralisation with O(|S||U|^n) linear constraints, which is computationally intractable in broad settings.

3 Analysis

The analysis identifies nonmonotonic value functions that QMIX cannot represent and establishes that this limitation can produce suboptimal policies. It further shows that ϵ-greedy exploration can worsen learning outcomes under a fixed time budget.

  • Nonmonotonicity: QMIX’s monotonicity implies that an agent’s optimal action cannot depend on other agents’ actions, motivating analysis of nonmonotonic Q-functions.
  • Matrix-game example: A two-player, three-action payoff matrix illustrates a nonmonotonic Q-function, with QMIX values examined under uniform visitation.
  • Uniform visitation: Theorem 1 establishes δ-suboptimal learning by QMIX under uniform visitation for n-player, k ≥3-action matrix games.The supplied passage states this result for any time horizon T and a specified payoff-matrix template.
  • ϵ-greedy visitation: Theorem 2 bounds the probability that ϵ-greedy visitation leads QMIX to learn a δ-suboptimal policy in n-player, k ≥3-action matrix games.The bound depends on the exploration schedule and its terminal value ϵ(T).
  • Exploration and suboptimality: For a fixed time budget T, increasing QMIX’s exploration rate lowers its probability of learning the optimal action under representational limitations.The paper attributes this to the network failing to retain the true value of an action it currently perceives as suboptimal.

4 Methodology

MAVEN trains value-based agents conditioned on a shared latent variable while a hierarchical policy learns the latent space and trajectory return. Mutual-information optimisation diversifies latent-conditioned behaviours, and training alternates updates for value, variational, and hierarchical-policy components.

  • Fixing the latent variable defines a joint action-value function and its corresponding greedy deterministic policy for low-level control.The coordinate-ascent scheme optimises the resulting Q-learning loss while holding the latent variable fixed.
  • The hierarchical policy is trained on cumulative trajectory reward while the value, feature, mixer, and variational parameters receive separate gradient updates.The training updates optimise the Q-learning and variational mutual-information objectives for the low-level components, and JRL for the latent-space policy.
  • Mutual information between trajectories and latent variables encourages diverse, identifiable exploration modes and prevents different latent values from collapsing to the same behaviour.Trajectories are represented through per-agent Boltzmann policies and encoded with an RNN so the objective remains differentiable.
  • A variational distribution qυ(z|σ(τ)) provides a tractable lower bound for the mutual-information objective when direct entropy calculations are infeasible.The bound equals the exact mutual information when the variational distribution matches the true posterior; a poor approximation creates a performance-relevant gap.
  • MAVEN samples a latent variable at episode start and uses it to condition decentralised greedy action selection throughout the episode.The latent variable is obtained from the hierarchical policy during training and sampled before decentralised execution at test time.

5 Experimental Results

MAVEN is evaluated on matrix games, SMAC maps, exploration-and-robustness tasks, latent-space representations, and component ablations. Across these experiments, MAVEN addresses difficult exploration and coordination settings while matching or exceeding alternatives as task difficulty increases.

  • 5.1 m-step matrix games: On the 10-step matrix game, QMIX reaches payoff 10 while MAVEN learns the optimal payoff 13.The game requires committed exploration because the optimal policy involves temporally extended coordination.
  • 5.2 StarCraft II: The SMAC evaluation reports median test win rates with quartiles, using decentralised greedy action selection during 32-episode evaluations every 100000 training steps.The benchmark includes Easy, Hard, and Super Hard maps, with hyperparameters tuned by grid search.
  • 5.2 StarCraft II: MAVEN performs substantially better than alternative approaches on Super Hard SMAC maps, with performance similar to QMIX on Hard and Easy maps.The reported pattern is that MAVEN performs better as difficulty increases.
  • 5.2 StarCraft II: In the 2-corridors task, QMIX fails to recover after the short corridor closes, whereas MAVEN adapts by using the long corridor.The task tests coordinated adaptation after the environment changes during training.
  • 5.2 StarCraft II: MAVEN’s latent space associates initial-state clusters with latent values, partitioning the state-action space into distinct joint behaviours.The t-SNE analysis compares latent assignments from initial to final training for 3s5z and micro_corridor.
  • 5.2 StarCraft II: A learned hierarchical policy outperforms a fixed uniform policy, while removing the variational MI loss causes a further performance drop on micro_corridor.The ablation results indicate that trajectory diversification and an explicit learned policy are important components in this setting.

6 Related Work

The related work situates MAVEN among approaches for scaling multi-agent reinforcement learning, exploring diverse behaviours, and enforcing decentralised execution. It connects MAVEN’s latent-variable and mutual-information design to prior single-agent and multi-agent exploration methods.

  • 6 Related Work: Coordination graphs factor large multi-agent problems to address the computational intractability caused by exponential state-action growth.This line of work also proposes inter-agent communication through message passing.
  • 6 Related Work: MAVEN without MI loss and with a uniform policy over z is equivalent to each agent using a Bootstrapped DQN.Bootstrapped DQN methods approximate a posterior over Q-values through statistical bootstrapping.
  • 6 Related Work: Related hierarchical reinforcement-learning methods learn diverse low-level behaviours using state features, behaviour mixtures, and mutual-information maximisation.These methods include approaches that subsequently tune higher-level policy components for specific tasks.

7 Conclusion and Future work

The paper analyses representational constraints on exploration under CTDE and introduces MAVEN to enable committed exploration while respecting decentralisation constraints. It identifies theoretical extensions, continuous-latent evaluation, variational inference, and communication-conditioned policies as future work.

  • 7 Conclusion and Future work: The paper’s conclusion is that MAVEN enables committed exploration while obeying CTDE representational constraints.The authors frame this as an extension of their analysis of representational constraints on exploration.
  • 7 Conclusion and Future work: Future work includes theoretical analysis of other CTDE algorithms and empirical evaluation of MAVEN with continuous latent variables.The authors also propose variational-inference methods to address continuous-latent intractability.
  • 7 Conclusion and Future work: Another proposed direction conditions the latent distribution on the joint state at each timestep and transmits it across agents for low communication cost.The proposed policy would be compared with existing centralised-execution approaches.

A QMIX Architecture

QMIX combines individual agent utilities through a mixing network whose structure is illustrated in the appendix. The figure shows the mixer, the overall architecture, and the agent network.

  • A QMIX Architecture: Figure 8 depicts the QMIX mixing network, overall QMIX architecture, and individual agent network structure.The caption identifies hypernetworks producing mixer weights and biases, with the mixer layers shown separately.

B Proofs

The analysis shows that QMIX can learn persistently suboptimal policies when its monotonic representation cannot express the optimal joint action-values, under both uniform and ϵ-greedy visitation.

  • Theorem 1 establishes that, for n-player, k ≥3-action matrix games under uniform visitation, QMIX learns a δ-suboptimal policy for any time horizon T.
  • The proof reduces QMIX fitting to a convex quadratic program over monotonic approximations, considering the cases x1 ≥x2 ≥x3 and x1 ≤x2 ≤x3.
  • QMIX’s monotonic projection can select the suboptimal action associated with payoff R instead of the optimal action with payoff R + δ.
  • Theorem 2 extends the result to ϵ-greedy visitation, giving a probabilistic bound under a decreasing exploration schedule.
  • The posterior and variational approximation over the latent variable are introduced as part of the variational analysis.

C.1 Architecture and Training

The experiments use recurrent, parameter-sharing agent networks with specified optimisation and exploration settings, alongside fixed MAVEN hyperparameters and SMAC evaluation protocols.

  • Architecture: Each agent is a Deep Recurrent Q-Network with a 64-dimensional hidden layer, GRU, and |U|-output layer, sharing parameters across agents and receiving an agent-id encoding.
  • Training: Target networks are updated every 200 episodes, with γ = 0.99 and RMSprop using a 5 × 10−4 learning rate and α = 0.99.
  • Exploration: QMIX uses per-agent ϵ-greedy exploration, annealing ϵ from 1.0 to 0.05 or 0.005 over 50k time steps before holding it constant.
  • MAVEN settings: MAVEN uses Z = 16, λMI = 0.001, λQL = 1, trajectory-based mutual-information loss, and hierarchical-policy entropy regularisation of 0.001.
  • Evaluation: All SMAC experiments use default benchmark rewards and observations, and methods run for 10 million environmental steps across 12 random initialisations.

C.2 Additional plots & ablations

The ablations examine how the number of latent-variable categories relates to performance and report median test returns across SMAC scenarios.

  • Latent categories: The number of latent-variable categories loosely correlates with performance, but this relationship is not consistent across settings.
  • Latent categories: For micro_corridor, category-count results are inconclusive because more latent variables and less training per variable offset each other under a fixed gradient-update budget.
  • Latent categories: Figure 9(b) reports returns from the corresponding policies learned for the latent-category ablation.
  • SMAC evaluation: Figure 10 presents median test returns on SMAC scenarios.
Loading 1910.07483v2…