Are You Doing What I Think You Are Doing? Criticising Uncertain Agent Models

Stefano V. Albrecht, Subramanian Ramamoorthy

Abstract

In multiagent systems, agents frequently employ opponent modeling to predict the actions of others. However, a model that fits historical data may still fail to capture the underlying logic of an agent, leading to poor performance in novel scenarios. We propose a novel frequentist hypothesis testing framework for "model criticism"—a statistically grounded method to evaluate the correctness of a behavioral model during live interaction. By utilizing a skew-normal distribution to model the test statistic, our algorithm provides reliable p-values even in the early stages of interaction. Experimental results demonstrate near 100% accuracy in structured environments with minimal computational overhead, offering a robust tool for real-time multiagent coordination.

Introduction

Opponent modeling is a cornerstone of effective interaction in multiagent systems (MAS). While techniques like fictitious play or case-based reasoning are adept at building these models, they often lack a mechanism for self-criticism. A model might achieve high "goodness-of-fit" on past observations while being fundamentally flawed. This paper addresses the critical challenge of "model criticism": providing a formal, online method to decide whether to keep or reject a behavioral hypothesis based on ongoing interaction history.

Methodology: Frequentist Model Criticism

The authors frame model criticism as a frequentist hypothesis test. The null hypothesis ($H_0$) posits that the observed agent is behaving according to the hypothesized model $\pi^*$.

Test Statistic and Distribution

The core of the test is a score function $z$ that compares observed actions against the hypothesized probability distribution. The test statistic $T$ measures the discrepancy between the score of observed actions and the expected score under the hypothesis.

While $T$ is asymptotically normal, the authors observe that it can be highly skewed during the initial stages of an interaction. To address this, the algorithm fits a skew-normal distribution to $N$ synthetic action sequences generated from the hypothesis. This allows for accurate p-value approximation much earlier than standard normal tests would permit.

p-value evolution over time for action spaces of size 2, 10, and 20. The correct hypothesis (red) remains stable while incorrect ones are rejected.

Experimental Evaluation

The algorithm was evaluated in two distinct environments:

  1. Random Behaviors: A synthetic baseline where agents follow sequences of random probability distributions, testing the algorithm's ability to distinguish structure-free behaviors.
  2. Adaptive Behaviors: A complex benchmark involving 78 matrix games with three classes of adaptive agents: Leader-Follower-Trigger (LFT), Co-Evolved Decision Trees (CDT), and Co-Evolved Neural Networks (CNN).

Key Results

The proposed method demonstrates exceptional performance across several metrics:

  • Accuracy and Scalability: In random behavior tests, the algorithm achieved nearly 100% accuracy in identifying correct and incorrect models. This performance remained consistent as the action space size increased from 2 to 20.
  • Real-Time Efficiency: The computational cost is negligible, with a single cycle taking less than 10ms even with skew-normal fitting, making it ideal for real-time MAS applications.
  • Sample Efficiency: Only $N=50$ synthetic samples are required to effectively learn the test distribution, ensuring low overhead.
Percentage of correct model identifications. Blue bars show correct acceptance ($\pi_j^* = \pi_j$), and red bars show correct rejection ($\pi_j^* \neq \pi_j$).

Discussion: The Probing Problem

A significant insight from this work is the "probing problem." Because the algorithm is passive, it can only reject a model if the observed interaction history exposes a disagreement between the hypothesis and reality. If the observer does not take actions that "probe" the other agent's logic—forcing it into states where its true behavior diverges from the model—incorrect hypotheses may persist.

Conclusion and Future Work

This paper provides a formal, efficient framework for criticizing agent models, moving beyond simple goodness-of-fit. Future research will explore integrating this critic into active exploration strategies, where the observer intentionally probes the environment to accelerate model validation. Additionally, extending the framework to handle hidden variables and private information remains a promising direction.

Summary updated

Abstract

The key for effective interaction in many multiagent applications is to reason explicitly about the behaviour of other agents, in the form of a hypothesised behaviour. While there exist several methods for the construction of a behavioural hypothesis, there is currently no universal theory which would allow an agent to contemplate the correctness of a hypothesis. In this work, we present a novel algorithm which decides this question in the form of a frequentist hypothesis test. The algorithm allows for multiple metrics in the construction of the test statistic and learns its distribution during the interaction process, with asymptotic correctness guarantees. We present results from a comprehensive set of experiments, demonstrating that the algorithm achieves high accuracy and scalability at low computational costs.
BibTeX
@inproceedings{albrecht2015are,
  author = {Stefano V. Albrecht and Subramanian Ramamoorthy},
  title = {{Are You Doing What I Think You Are Doing? Criticising Uncertain Agent Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
}
Figure