TL;DR
This paper introduces a novel method for AI agents to learn social norms by observing others, moving beyond systems that require pre-defined norms. By adapting Markov Chain Monte Carlo (MCMC) sampling to a probabilistic grammar that defines norms, the approach can identify complex, recursive norms from observed behavior, even in open multi-agent systems.
What Problem Does This Paper Address?
In multi-agent systems (MAS), social norms are crucial for predictable and efficient interactions, much like in human societies. While some MAS assume norms are explicitly programmed, this paper tackles the challenge of norm identification: how can an agent learn the prevalent norms of a society through observation, especially in open systems where norms aren't centrally dictated? Existing methods often struggle with the complexity and recursive nature of norms, requiring either pre-defined norm sets or domain-specific representations. This work aims to overcome these limitations by enabling agents to discover norms from a rich, generative language.
Methods
The core of this paper is an adaptation of the Metropolis-Hastings Markov Chain Monte Carlo (MCMC) algorithm for sampling from a space of symbolic expressions (norms) defined by a probabilistic context-free grammar (PCFG).
- Probabilistic Grammar for Norms: They use a "Tagged Probabilistic Context-Free Grammar" (PCFG) where each production rule is tagged, and probabilities are assigned to rules and terminal symbols. This allows for the generation of complex, nested norm expressions.
- MCMC for Symbolic Expressions: The standard MCMC algorithm is adapted to sample from the space of these grammar-generated expressions. The grammar's probabilities define the prior distribution, and the likelihood function is domain-specific, measuring how well an observed task execution conforms to a candidate norm.
- Favored Norm Identification: A key modification is introduced to the acceptance rate calculation in the MCMC algorithm. This modification down-scales the prior probabilities of "irrelevant" norm expressions (those that don't explain the observed behavior well), thereby favoring norms that are more relevant to the observed task.
- Convergence Testing: To address the lack of convergence analysis in prior symbolic MCMC work, they propose using a vector representation of expression trees (based on tree kernels) to define a distance metric. This allows the application of the Gelman-Rubin convergence diagnostic (R statistic) to assess if the MCMC chains have converged to a stationary distribution.
Datasets
Not discussed in the paper. The experiments use a simulated robot manipulation task.
Key Insights and Ideas
- Generative Norm Language: The use of a probabilistic grammar to define norms is powerful because it allows for the representation of arbitrarily complex and recursive norms, overcoming the limitations of finite, pre-defined norm sets.
- MCMC as a General Tool: Adapting MCMC, a well-established technique for numerical data, to sample from symbolic expression spaces (like norms) is a significant methodological contribution.
- Task Relevance Matters: Explicitly favoring norms relevant to the observed task, rather than just any norm, is crucial for effective norm identification in practical scenarios.
- Convergence is Key (and Tricky): While MCMC can explore complex spaces, ensuring convergence is vital for reliable posterior distributions. The proposed tree-based vector representation and diagnostic are important steps towards this.
- Behavioral Equivalence: The paper highlights that norms can be behaviorally equivalent even if their symbolic representations differ. This necessitates behavioral interpretations of precision and recall for evaluation.
Key Results
- The proposed MCMC-based norm identification method successfully identified the true norm in a simulated robot manipulation task.
- When the probability of non-normative behavior ($p_{nn}$) was low (≤ 0.25), the method identified the true norm or an equivalent norm with high probability.
- Behavioral precision and recall were high (often > 0.8) for norms identified by frequency rank, even when the identified norm wasn't the exact true norm, suggesting the approach enables compliant behavior.
- The convergence diagnostic (R statistic) showed some indication of lack of convergence for shorter chain lengths, suggesting the need for longer chains or further refinement of the MCMC process for full posterior analysis.
Limitations and Future Work
- Convergence: The paper notes that the R statistic did not consistently decrease towards 1, suggesting potential issues with convergence and the need for longer MCMC chains or improved sampling strategies.
- Efficiency: Improving the efficiency of MCMC search for norms is identified as a future research direction.
- Grammar Design: Investigating more expressive probabilistic grammars for encoding norms is suggested.
- Incremental Learning: Adapting the approach for incremental learning, where norms are learned and updated over time as new observations become available, is another promising avenue.
Summary updated