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

Stefano V. Albrecht, Subramanian Ramamoorthy

Abstract

In multi-agent environments, agents often rely on models of others to optimize their own behavior. However, existing modeling techniques lack a formal mechanism to determine if a chosen model is fundamentally correct. This paper proposes a frequentist hypothesis testing framework to "criticize" agent models in real-time. By defining a score-based test statistic and modeling its distribution using a flexible skew-normal fit, the authors enable agents to calculate p-values for model correctness. Experimental results across various matrix games and agent architectures demonstrate high accuracy, scalability, and computational efficiency.

Introduction

Predicting the behavior of other agents is a cornerstone of multi-agent systems, from autonomous driving to algorithmic trading. While numerous methods exist for building these models—ranging from fictitious play to deep neural networks—a critical gap remains: how can an agent verify if its model is actually accurate? Traditional Bayesian approaches can identify the most likely model within a predefined set but fail when the entire set is poorly specified. This work introduces a formal "criticism" mechanism that allows an agent to statistically reject a model based on observed evidence, providing a specific level of confidence in the model's underlying logic.

Methodology

The proposed approach treats agent modeling as a frequentist hypothesis test. The agent maintains a hypothesis model of its opponent and observes their actions over time to calculate a p-value for model correctness.

The Test Statistic and Skew-Normal Fitting

The authors define a test statistic ($T$) based on "score functions" ($z$) that assign values to actions based on their likelihood under the model. $T$ measures the difference between the scores of actual observed actions and simulated actions generated by the hypothesis model.

While the Central Limit Theorem suggests that $T$ should follow a normal distribution asymptotically, early-stage interactions (the "shaping period") often exhibit significant skewness. To bridge this gap, the algorithm fits a skew-normal distribution to the data rather than assuming a standard Gaussian curve. This allows for accurate p-value calculation even with very little interaction data.

The empirical distribution of the test statistic often shows significant skewness, which is captured by the fitted skew-normal density (red line).

Experimental Setup

The framework was evaluated using a benchmark of 78 distinct 2x2 matrix games and three complex agent classes:

  • Leader-Follower-Trigger (LFT): Hybrid adaptive agents.
  • Co-Evolved Decision Trees (CDT): Deterministic, logic-based agents.
  • Co-Evolved Neural Networks (CNN): Stochastic, complex agents.

Key Results

The algorithm demonstrated exceptional performance in identifying model correctness. In scenarios with random behaviors, it achieved nearly 100% accuracy. Crucially, the method scales well; as the number of possible actions ($|A_j|$) increased from 2 to 20, the algorithm continued to effectively distinguish correct models from incorrect ones.

P-value convergence over time for different action space sizes. The correct model (red line) maintains a high p-value, while incorrect hypotheses quickly drop toward zero.

Efficiency and Robustness

Computationally, the method is highly efficient. A single cycle of sampling and p-value calculation takes less than 1ms, while fitting the skew-normal parameters takes less than 10ms on standard hardware. Furthermore, the skew-normal fit was shown to be significantly more accurate than standard Normal or Student-t distributions during the first 10-50 time steps of an interaction.

Conclusion and Future Work

This work provides a robust, "passive" mechanism for agent model criticism that does not require the agent to take risky actions to test its opponent. However, the passive nature means the algorithm can only criticize parts of a strategy that have been revealed through interaction. Future research will explore "active probing," where agents intentionally choose actions to interrogate and reveal hidden aspects of an opponent's strategy, as well as extending the model to handle noisy observations common in robotics.

Summary updated

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