🤖 AI

Partner Capability Estimation for Task-Agnostic Adaptation in Ad-Hoc Teamwork

This paper introduces CE-CM and its diversity-aware extension CE-CM-Div, an approximate Bayesian framework that enables autonomous agents to rapidly estimate hidden, task-invariant partner capabilities and adapt their joint planning in ad-hoc teamwork scenarios without requiring pre-training or prior knowledge of the task.

Original authors: Peter Tisnikar, Maja Swieczkowska, Benteng Ma, Gerard Canal, Matteo Leonetti

Published 2026-07-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Peter Tisnikar, Maja Swieczkowska, Benteng Ma, Gerard Canal, Matteo Leonetti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking into a brand-new video game with a stranger. You don't know if they are a speed-runner who skips levels, a cautious explorer who checks every corner, or someone who just really hates jumping. In the world of artificial intelligence, this is called Ad-Hoc Teamwork. It's the challenge of getting a robot (or an AI agent) to cooperate with a partner it has never met before, without any prior practice or a shared rulebook. Usually, AI researchers try to train robots to be "super-robust," meaning they learn to play well against anyone by practicing against thousands of different computer opponents. But this paper asks a different question: What if, instead of just memorizing how to react, the robot could actually figure out what its partner is capable of doing? Think of it like a dance partner. Instead of just guessing the next step, the robot tries to learn the partner's "moveset"—can they jump high? Can they lift heavy things? Once it knows the limits of the partner's abilities, it can plan a dance routine that works perfectly for both of them, even if they are dancing to a completely new song.

The paper, titled "Partner Capability Estimation for Task-Agnostic Adaptation in Ad-Hoc Teamwork," introduces a clever new method called CE-CM (Capability Estimation via Contextual Models). The core idea is that the robot shouldn't just guess what the partner wants to do; it should figure out what the partner can do. The authors treat a partner's abilities as a hidden list of "superpowers" (or lack thereof) that stays the same no matter what game they are playing.

Here is how the robot learns: It watches the partner play a few rounds of a game. Then, the robot runs a mental simulation. It says, "Okay, if my partner had this specific set of superpowers, how would they have played that last round?" It compares its simulation to what actually happened. If the simulation matches the reality, the robot keeps that set of superpowers as a possibility. If it doesn't match, it throws that idea away. By doing this over and over, the robot narrows down the list until it has a very good guess about the partner's true capabilities. Once it knows the partner's limits, it can plan the next game together, making sure it never asks the partner to do something impossible, like lifting a piano if the partner can only lift a mouse.

The researchers tested this idea in two very different digital worlds. The first was a tidy-up game called TidyUP, where the rules were strict and clear (like a logic puzzle). In this world, the robot was amazing. It quickly figured out exactly what the partner could and couldn't do. After just a few games, the robot stopped making mistakes, like asking the partner to clean a room they couldn't enter. The results showed that the robot's ability to coordinate improved drastically, with the number of "corrections" (where the robot had to fix a bad plan) dropping from about 75% down to less than 5% for some partners.

However, the second world, Overcooked (a chaotic cooking simulator), was much trickier. In a kitchen, there are often many ways to make a salad. You can chop tomatoes first, or onions first; both work. The robot's original method, CE-CM, assumed that if the partner could do something, they would do it in the most perfect, logical way. But real people (and even some computer partners) are messy. They might choose a weird path just because they like it, or they might make a mistake. In this messy environment, the robot got stuck. It knew what the partner could do, but it couldn't predict what they would actually do because there were too many valid options.

To fix this, the authors created an upgrade called CE-CM-Div. Instead of asking, "What is the one perfect way my partner would act?", this new method asks, "What are all the different ways my partner might act?" It generates a whole bunch of different possible scenarios for each set of superpowers. When the partner does something, the robot checks if it matches any of those scenarios. This turned out to be a game-changer when they tested it with real humans. They gathered 225 cooking sessions from 15 different people. The original method struggled, often failing to guess the human's abilities correctly because humans are unpredictable. But CE-CM-Div, with its "many-possibilities" approach, successfully learned the humans' capabilities much faster and more accurately.

The paper suggests that while knowing a partner's limits is a huge step forward, it's not a magic bullet for every situation. If a partner has many ways to solve a problem, knowing their limits isn't enough to know which path they will choose. But by accounting for this diversity and uncertainty, robots can become much better teammates. The authors conclude that this approach—learning a reusable model of what a partner can do, rather than just memorizing how they act in one specific game—is a promising way to build AI that can work with anyone, anywhere, on any task.

Technical Summary: Partner Capability Estimation for Task-Agnostic Adaptation in Ad-Hoc Teamwork

1. Problem Formulation

The paper addresses a critical limitation in current Ad-Hoc Teamwork (AHT) research: the assumption that agents collaborate on a single, fixed task with known partner capabilities. In realistic open-world settings, particularly those involving human collaborators, partners possess hidden, task-invariant constraints on their abilities (capabilities) and may act sub-optimally or with diverse strategies.

The authors formalize the problem as joint planning with decentralized execution under hidden partner capabilities. The core challenge is to learn a reusable, task-agnostic model of a specific partner's capabilities from observed joint trajectories. Unlike previous approaches that learn robust policies for a fixed task or infer preferences (what a partner wants to do), this work focuses on inferring capabilities (what a partner is fundamentally able to do). The goal is to enable an autonomous agent ( $Ag_1$ ) to estimate the hidden capability vector ( $c$ ) of an uncontrollable partner ( $Ag_2$ ) and use this estimate to plan future joint tasks without pre-training on a population of partners.

2. Methodology

2.1. Modeling Framework

The authors extend the Contextual Multi-agent Markov Decision Process (CMMDP) framework.

State & Action: Defined over a finite set of joint states ( $S$ ) and joint actions ( $A$ ).
Capabilities ( $C$ ): Modeled as $D$ -dimensional binary vectors where each bit represents a specific capability (e.g., ability to lift a heavy object, ability to use a specific tool).
Transition Function ( $T$ ): Capabilities modulate the transition function. If a capability required for a transition is missing ( $c_i=0$ ), the transition results in a self-loop (the state does not change), effectively rendering the action infeasible in that context.
Objective: The agent seeks to find the capability vector $c^*$ that minimizes the difference between the joint trajectory planned under $c^*$ and the observed trajectory $\tau_{obs}$ across multiple tasks.

2.2. CE-CM: Capability Estimation via Contextual Models

The primary method, CE-CM, is an approximate Bayesian inference approach that operates via a "simulate-and-compare" loop:

Sampling: The agent samples candidate capability vectors ( $\hat{c}$ ) from a prior distribution.
Simulation: For each candidate, the agent uses a joint planner to simulate the trajectory ( $\tau_{\hat{c}}$ ) that would result if the partner possessed those capabilities.
Comparison: The simulated trajectory is compared to the observed trajectory ( $\tau_{obs}$ ) using a similarity metric (Jaccard distance for propositional states, cosine similarity for real-valued vectors).
Belief Update: Candidates that fall within a similarity threshold $\epsilon$ are accepted. The agent maintains a set of accepted samples to approximate the posterior distribution.
Estimation: A point estimate $\hat{c}^*$ is derived (e.g., via Maximum A Posteriori estimation) by thresholding the empirical mean of the accepted samples.
Planning: The estimated capabilities induce a specific CMMDP instance, which the agent uses to compute a new joint plan for the next task.

2.3. CE-CM-Div: Handling Behavioral Diversity

The authors identify that standard CE-CM is brittle when human partners exhibit diverse or suboptimal behaviors, as a single capability vector might induce multiple valid trajectories. To address this, they propose CE-CM-Div:

Instead of comparing the observation to a single optimal trajectory, CE-CM-Div generates a diverse set of trajectories ( $\Delta_{\hat{c}}$ ) for each candidate capability hypothesis using a diversity-aware planner (based on Monte Carlo Tree Search).
A hypothesis is accepted if at least one trajectory in the diverse set is sufficiently similar to the observation.
This approach prevents the rejection of valid capability hypotheses due to unmodeled behavioral variations or suboptimality.

3. Key Contributions

Capability-Based Formulation: A formalization of multi-task AHT as joint planning under hidden, task-invariant capability constraints, providing an interpretable and reusable partner representation.
CE-CM Algorithm: An online, task-agnostic adaptation method that infers discrete capability vectors from few interactions without requiring population pre-training or demonstration data.
CE-CM-Div Extension: A robustness mechanism that accounts for behavioral diversity by evaluating hypotheses against sets of diverse planner rollouts rather than single optimal trajectories.
Empirical Validation: Comprehensive evaluation across two domains (TidyUP and Overcooked) and a human-subject study demonstrating the efficacy and limitations of capability-based modeling.

4. Experimental Results

4.1. TidyUP (PDDL Domain)

In a symbolic household domain with fully specified rewards and deterministic transitions:

Inference: CE-CM rapidly recovered ground-truth capability vectors, reducing Hamming distance to near-zero within five tasks.
Coordination: The method significantly reduced the ratio of "corrected actions" (conflicts between agent and partner plans) and increased plan overlap (IoU) compared to optimistic and pessimistic baselines.
Conclusion: In well-specified environments where feasibility strictly dictates behavior, capability inference is highly effective.

4.2. Overcooked (Simulated Partners)

In a dynamic coordination domain with underspecified rewards (multiple valid strategies):

Inference: CE-CM successfully recovered capability constraints, reducing the proportion of infeasible (unproductive) actions assigned to the partner.
Coordination Limitation: Despite accurate capability estimates, CE-CM did not fully resolve coordination errors (plan overlap remained low). This is because capabilities constrain feasibility but do not determine which feasible strategy a partner chooses when multiple exist.
Conclusion: Capabilities alone are insufficient to predict behavior in domains with high strategy ambiguity.

4.3. Overcooked (Human Subjects)

A study with 15 participants (225 trajectories) revealed significant behavioral variability:

CE-CM Failure: The standard CE-CM frequently failed to update beliefs because human trajectories rarely matched the single optimal trajectory generated by the planner, leading to very few accepted samples.
CE-CM-Div Success: The diversity-aware extension substantially improved inference accuracy (lower Hamming distance) and posterior size by accepting hypotheses that matched any of the diverse plausible behaviors.
Conclusion: Accounting for behavioral diversity is essential for robust capability inference in realistic human-AI teaming.

5. Significance and Claims

The paper claims that capability-based modeling offers a promising, interpretable, and task-agnostic approach to adaptation in ad-hoc teamwork. By distinguishing between what a partner can do (capabilities) and what they choose to do (preferences/strategies), agents can accumulate reusable knowledge about an individual across different tasks.

However, the authors are modest about the scope of this solution. They explicitly state that:

Capabilities are necessary but not sufficient: In domains with multiple valid strategies (like Overcooked), knowing a partner's capabilities does not uniquely predict their behavior.
Diversity is critical: Robust adaptation in human-AI teams requires mechanisms (like CE-CM-Div) that account for behavioral variability and suboptimality, rather than assuming optimal planning.
Scalability: The current approach relies on joint planning, which scales exponentially with the number of agents, limiting immediate application to large teams without further approximations.

The work positions capability estimation as a foundational step toward generalizable human-AI teaming, while highlighting the need to jointly model capabilities and preferences to fully resolve behavioral ambiguity.