PaperlayerView exact revision on arXiv

Source-linked AI summary

Coordinated Multi-Agent Imitation Learning

Hoang M. Le, Yisong Yue, Peter Carr, Patrick Lucey

arXiv:1703.03121v2cs.LG

TL;DR

The paper tackles imitation learning when multiple agents coordinate through roles and assignments that are implicit in demonstrations. It jointly learns individual policies with a latent coordination structure, using role-based assignment and integrated structure learning. Across predator-prey and professional soccer settings, the method achieves significantly superior imitation performance compared with conventional baselines.

  • Problem

    Imitation learning for coordinating agents must infer unobserved roles and role assignments, which may change across sequences and complicate consistent policy learning.

  • Method

    The method jointly learns individual policies and a latent coordination model by integrating conventional imitation learning with unsupervised structure learning.

  • Results

    The method achieves significantly superior imitation performance compared with conventional baselines in synthetic predator-prey and professional soccer team-defense settings.

  • Takeaways & Limitations

    Learning latent structure to encode implicit coordination improves imitation performance in the evaluated multi-agent settings.

  • Takeaways & Limitations

    The framework’s training and inference procedures vary with the graphical-model structure, and broader graphical models remain an open direction.

Abstract

from arXiv · show

We study the problem of imitation learning from demonstrations of multiple coordinating agents. One key challenge in this setting is that learning a good model of coordination can be difficult, since coordination is often implicit in the demonstrations and must be inferred as a latent variable. We propose a joint approach that simultaneously learns a latent coordination model along with the individual policies. In particular, our method integrates unsupervised structure learning with conventional imitation learning. We illustrate the power of our approach on a difficult problem of learning multiple policies for fine-grained behavior modeling in team sports, where different players occupy different roles in the coordinated team strategy. We show that having a coordination model to infer the roles of players yields substantially improved imitation loss compared to conventional baselines.

1. Introduction

The paper addresses imitation learning for coordinating agents, where coordination is implicit and multi-agent learning faces high-dimensional spaces and limited data. It jointly learns individual policies and a latent coordination structure, demonstrating improved imitation performance in synthetic predator-prey and professional soccer settings.

  • Motivation: Multi-agent learning remains relatively modest compared with conventional supervised learning and single-agent reinforcement learning.The paper attributes this to extremely high-dimensional state and action spaces, along with limited data sources and experimental testbeds.
  • Motivation: Sports tracking data enables learning coordinated multi-agent policies from demonstrations.Team sports require players to assume different roles, while those roles and their assignments are unobserved and may change during a play sequence.
  • Problem: The paper studies imitation learning for multiple coordinating agents in collaborative settings such as team sports, game AI, robot teams, and collective animal behavior.The coordination mechanism is not explicitly observed in the demonstrations.
  • Approach: The proposed semi-supervised framework integrates conventional imitation learning with unsupervised, or latent, structure learning.The latent structure model represents the implicit coordination mechanism in demonstration data.
  • Approach: Alternating optimization jointly trains individual policies and the latent structure model.The method extends reduction-based single-agent imitation learning to the multi-agent setting and uses stochastic variational inference for latent structure learning.
  • Evaluation: The method is evaluated on synthetic predator-prey coordination and large-scale professional soccer team-defense imitation.Learning a latent structure that encodes implicit coordination yields significantly superior imitation performance compared with conventional baselines.

2. Problem Formulation

The formulation handles demonstrations whose agent identities may change across sequences by learning role-based indexing for consistent policy inputs. It combines latent role assignment with multi-agent policy learning and entropy-regularized structure learning.

  • Problem Setting: Training data contains multiple demonstrations of K coordinating agents whose identities or indexing may change between demonstrations.Each demonstration is represented as an unstructured set of agent trajectories, potentially with varying sequence lengths and associated context.
  • Policy Learning: The joint policy maps the joint state of K agents to K actions, with imitation loss measured under the state distribution induced by that policy.The loss may use squared loss for deterministic policies or cross entropy for stochastic policies.
  • Problem Setting: Consistent indexing is required so the same policy input position corresponds to the same functional role across demonstrations.Without this consistency, black-box policy learning receives inconsistent state representations and may become difficult or impossible.
  • Role-Based Indexing: Role-based indexing learns one policy per role rather than identity-specific policies.This is more natural and data-efficient when demonstrations contain heterogeneous agent identities and teams.
  • Structured Learning: Figure 2 motivates graphical models because role transitions should obey structural regularity induced by coordination.Roles are learned in an unsupervised fashion without attaching semantic labels to them.
  • Role-Based Indexing: The assignment function A maps an unstructured trajectory set U and latent structured model q to an ordered trajectory set A.The model q infers role assignments, allowing state vectors to be consistently constructed for imitation-loss optimization.
  • Structured Learning: The objective augments imitation loss with a low-entropy penalty and can be viewed as maximizing mutual information between latent structure and observed trajectories.The formulation also allows multiple agents to occupy a role and permits roles to be unoccupied in some sequences.

3. Learning Approach

The approach alternates between assigning latent roles, learning jointly indexed multi-agent policies, rolling them out, and updating the latent structure model. This addresses the circular dependence between policy learning and role assignment while supporting black-box supervised learners.

  • Approach Outline: The method alternates policy optimization with latent structure learning to address the circular dependence between policies and role assignments.It fixes the structured model while minimizing imitation loss, then fixes policies while retraining the latent model and reassigning roles.
  • Approach Outline: Role assignment converts unstructured demonstrations into ordered trajectories so each trajectory corresponds consistently to a policy.This indexing is required for reduction-based policy learning with centralized or decentralized black-box policy classes.
  • Approach Outline: The optional mixing step replaces training trajectories with roll-outs at an increasing probability and may stabilize early learning, but yielded no observed performance gain in the main experiment.The authors relate this option to scheduled sampling.
  • Joint Multi-Agent Imitation Learning: Joint multi-agent training rolls out all policies, cross-updates each agent’s state using other agents’ predictions, and updates policies against expert actions.The procedure increases the prediction horizon across trajectory segments and uses freshly updated policies for subsequent roll-outs.
  • Coordination Structure Learning: The latent structure model is trained as a graphical model using role assignment inference and stochastic variational updates.The framework updates local latent variables and global model parameters while leveraging graphical-model training and inference.

4. Experiments

The experiments evaluate coordinated multi-agent imitation learning in predator-prey and professional soccer, comparing structured coordination with unstructured and centralized alternatives. Across both settings, latent coordination improves imitation performance, while decentralized policies can remain comparable to centralized ones.

  • Experimental settings: The experiments use predator-prey and professional soccer settings to evaluate imitation of coordinating multi-agent behavior.The soccer task uses professional tracking data to learn up to 10 defensive policies.
  • Predator-Prey Domain: In predator-prey, coordinated training learns latent roles, whereas unstructured training assigns arbitrary roles independently across games.The coordinated version uses a discrete HMM and maximizes role consistency across dynamic oracles.
  • Predator-Prey Domain: 22 steps with 8% failure rate were achieved by the proposed method in the last predator-prey iteration, versus 42 steps with 70% failure for unstructured imitation.The comparison gives the unstructured baseline an advantage by letting the prey move after all predators.
  • Multi-agent Imitation Learning for Soccer: Coordinated soccer learning substantially outperforms imitation learning without structured coordination, while decentralized and centralized policies have comparable performance.The imitation loss measures average distance between roll-outs and ground truth in meters.
  • Multi-agent Imitation Learning for Soccer: Soccer imitation loss increases with longer horizons because of cascading errors, but the error scales sub-linearly with horizon length.The policies were trained on sequences of length 50.
  • Multi-agent Imitation Learning for Soccer: Visualized soccer policies are qualitatively similar to demonstrations and may support counterfactual replay analysis.Role distributions show dominant modes, and roles can switch during play.

5. Other Related Work

Related work situates multi-agent imitation learning alongside earlier work on learning joint tasks and permutation-invariant policy representations. The cited prior imitation-learning approach used direct interaction with human teachers and addressed different technical challenges.

  • Prior multi-agent imitation learning: Multi-agent imitation learning has received limited prior attention, with Chernova and Veloso addressing a substantially different application and technical setting.Their learner collected samples through direct interaction with teleoperating human teachers.
  • Index-free policy learning: Index-free policy learning is difficult for black-box machine-learning techniques when agent inputs or outputs are unordered sets.Related work studies ordering and permutation-invariant approaches for set-based learning problems.

6. Limitations and Future Work

The framework can potentially extend beyond the graphical models and demonstration-learning setting studied here, but broader model classes and end-to-end training remain future directions. The authors also identify a possible tension between end-to-end methods and learning-reductions approaches.

  • Future graphical models: The latent structure model can in principle use different graphical-model families, but the exact training and inference procedure depends on the graph structure.The authors suggest finding domains that benefit from more general graphical models.
  • Future training methods: End-to-end differentiable training could provide computational speed-up, but may require departing from a learning-reductions style approach.The authors identify this departure as a potential issue for end-to-end methods.
  • Broader applications: The proposed framework could also be used for generative modeling or more efficient structured exploration in multi-agent reinforcement learning.The paper presents these as possible applications beyond imitation learning from demonstrations.

A. Variational Inference Derivation for Hidden Markov Models

The appendix derives structured variational inference for a Bayesian Hidden Markov Model. It formulates latent roles over featurized trajectories and approximates the intractable role posterior with a simpler variational distribution.

  • Variational inference derivation: The derivation focuses on the Forward-Backward procedure for training a Bayesian Hidden Markov Model.Other graphical-model derivations depend on the chosen model family.
  • Model formulation: Each trajectory is represented by features x_t, while the latent role sequence is z_1:T under an unknown coordination model.The model includes global parameters and local role-related parameters.
  • Model formulation: At each time t, an agent acts according to a categorical latent role z_t.The categorical distribution is parameterized by the local parameters of the structured model.
  • Posterior approximation: Because the posterior p(z|x, θ) is often intractable, the method approximates it with a simpler distribution q using Bayesian variational inference.The paper uses this approach instead of typically slower sampling-based MCMC methods.

Structured Variational Inference for Unsupervised Role

The section formulates unsupervised role inference as structured mean-field variational inference for a graphical model, optimized through alternating local and global updates. For role transitions, the model uses an HMM whose local inference is performed by message passing.

  • Variational objective: The variational objective maximizes the ELBO, equivalently minimizing the KL divergence between the approximating and true posterior distributions.The structured mean-field family factorizes q(z, θ) into q(z)q(θ), separating global parameters from latent sequences while preserving dependencies among z_t states.
  • Variational objective: Structured mean-field inference factorizes q(z, θ) as q(z)q(θ), breaking dependence between global parameters and latent states but retaining temporal dependence among latent states.This differs from fully factorized inference for independent observations because the latent sequence remains structured.
  • HMM role model: The role-transition model is an HMM with global parameters for the initial distribution, transition matrix, and emission parameters, and local variables for hidden state assignments.The transition matrix models first-order dependencies between consecutive role states, while emissions relate hidden states to observations.
  • Alternating optimization: Local variational updates use HMM message passing, specifically forward-backward recursion, while global parameters are updated through stochastic natural-gradient optimization.The local update computes latent-state marginals using current transition and emission estimates; global updates use mini-batches and expected sufficient statistics.
  • Computational cost: For an HMM chain with T observations and K hidden states, the forward-backward local update takes O(K^2T) time.This complexity applies to the message-passing step for a chain of length T and K hidden states.
  • Alternating optimization: Training alternates local inference over latent role sequences with global parameter updates, producing an updated variational model q(θ)q(z).The coordinated structure-learning algorithm computes local factors by forward-backward message passing and then updates global parameters using the prescribed stochastic rules.

B.2. Visualizing Role Assignment for Soccer

The soccer visualization examines how often each learned policy is assigned different latent roles. Policies with more consistent dominant roles tend to correspond to players whose action trajectories have lower variance, while other policies switch roles more often.

  • Role consistency: Policies indexed 0–3 tend to remain most consistent with their prescribed latent roles in the professional-soccer demonstrations.These policies have fewer assignments outside their dominant role than policies that switch or swap roles more frequently.
  • Role consistency: The players associated with the most consistent policies also have the least variance in their action trajectories.This connects role-assignment consistency with observed trajectory variability in the soccer data.
  • Policy training: The multi-agent imitation-learning procedure aggregates expert actions encountered during policy rollouts and retrains each policy on its expanded dataset.At each step, policies produce actions, states are cross-updated using all agents’ actions and context, and expert actions are collected for aggregation.
  • Role consistency: Policies indexed 8–9 receive higher frequencies for less consistent roles according to the maximum-likelihood estimate of the latent structured model.The figure caption highlights these policies as examples of assignments outside a single dominant role.
  • Role decomposition: Entropy regularization encourages a role decomposition that makes learned policies as decoupled as possible to minimize imitation loss.The caption presents this as the intuition behind the observed role-frequency pattern.
Loading 1703.03121v2…