Ad Hoc Teamwork

Definition

Ad hoc teamwork is the problem of cooperating effectively with teammates that were not known, trained with, or pre-coordinated with before deployment. A compact formal view is that the ad hoc agent acts under uncertainty over teammate type or policy z, updating a belief such as

$$P(z\mid H_{0:T})\propto P(z)\prod _{t=0}^{T}P(a_t^{-i}\mid s_t,z),$$

then choosing actions that work well with the inferred or robustly possible teammates.

Why It Matters

Many real deployments cannot assume fixed partners. Robots, assistants, warehouse agents, traffic agents, and human-AI teams may encounter new teammates, open populations, or partners that adapt over time. Safety claims based only on fixed self-play populations can fail when the agent meets a teammate with different conventions, capabilities, or goals.

Formalism / Key Objects

• Unknown teammates: the ad hoc agent has no shared training history or fixed policy model for other agents.
• Open teams: agents may enter or leave the environment, changing both team composition and role requirements.
• Teammate modelling: the agent estimates partner goals, policies, capabilities, or task assignments from observed behavior.
• Communication value: a message or signal is useful when its expected coordination benefit exceeds its cost and when it is interpretable to the teammate.
• Inverse-planning approaches such as Bayesian Delegation infer high-level subtask allocation from low-level actions.

Connections

• Multi-Agent Coordination is the broader problem class; ad hoc teamwork adds teammate uncertainty and missing prior coordination.
• Emergent Communication becomes harder in ad hoc settings because a signal protocol may not transfer to new partners.
• Multi-Agent Non-Stationarity appears when teammates adapt during interaction rather than remaining fixed.
• Cooperative MARL Benchmarking should include partner diversity and held-out teammate tests if it wants to measure ad hoc competence.
• Safe Multi-Agent Reinforcement Learning needs ad hoc robustness because unsafe behavior can come from mismatch between individually reasonable policies.

Common Confusions

• Ad hoc teamwork is not the same as ordinary cooperative self-play; the teammate distribution at deployment is the point.
• Generalization to new maps is weaker than generalization to new teammates.
• Communication does not automatically solve ad hoc teamwork if there is no shared protocol or trusted interpretation.

Key Sources

• Ahmed2022 - Deep Reinforcement Learning for Multi-Agent Interaction
• Wang2020 - Too Many Cooks: Coordinating Multi-agent Collaboration Through Inverse Planning
• Rother2023 - Disentangling Interaction using Maximum Entropy Reinforcement Learning in Multi-Agent Systems