Improved decisions for unknown behaviours in interactive dynamic influence diagrams

Yinghui Pan, Mengen Zhou, Biyang Ma, Yifeng Zeng, Yew-Soon Ong, Guoquan LiuArtif. Intell. Rev 2025 · OpenReview

TL;DR

This paper tackles the challenge of agents making optimal decisions in dynamic environments when other agents exhibit unpredictable behaviors. They introduce two novel swarm intelligence-based approaches, Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO), to generate a diverse set of potential behaviors for these unknown agents, significantly improving the subject agent's decision-making capabilities.

What Problem Does This Paper Address?

In multi-agent systems operating under uncertainty, a "subject agent" needs to optimize its strategy while other agents adapt their behaviors. A major hurdle arises when these other agents display behaviors that the subject agent hasn't anticipated. Traditional Interactive Dynamic Influence Diagrams (I-DIDs) struggle with this because they assume the subject agent can model all possible behaviors of others. This paper addresses the limitation of I-DIDs in handling "unknown behaviors" by proposing methods to generate a richer, more diverse set of potential behaviors for the other agents, thereby equipping the subject agent to better adapt.

Methods

The core of this work lies in adapting two Swarm Intelligence (SI) techniques to generate new behaviors for the "other agents" within an I-DID framework.

  • Particle Swarm Optimization (PSO)-Enabled Behaviors (PSB): Inspired by bird flocking, PSO is used to evolve a population of candidate behaviors. Each behavior is represented as a particle with a position (sequence of actions) and velocity. Novel arithmetic rules are introduced to update these particles, allowing them to explore a wider range of behaviors. The fitness of each behavior is determined by its expected reward.
  • Ant Colony Optimization (ACO)-Enabled Behaviors (ACB): Mimicking ant foraging, ACO is employed to discover optimal action sequences. Ants deposit "pheromone" on paths (action sequences) that lead to higher expected rewards. This pheromone guides subsequent ants, encouraging exploration of promising behaviors.
  • Behavioral Diversity: A key aspect of both methods is their ability to generate diverse behaviors. The paper introduces a metric to quantify this diversity, aiming to ensure that the generated behaviors cover a broad spectrum of possibilities, including less probable ones.
  • Theoretical Analysis: The authors provide theoretical analysis to understand how the generated behaviors impact the subject agent's decision quality, particularly concerning the convergence rate of the generated behaviors towards true behaviors.

Datasets

The paper evaluates its proposed methods on two standard multiagent planning problems:

  • Multiagent Tiger Problem: A classic problem where two agents must navigate doors to find gold while avoiding a tiger.
  • Multiagent Unmanned Aerial Vehicle (UAV) Problem: A more complex scenario involving a predator UAV hunting a prey UAV in a partially observable environment.

No new datasets were introduced; existing benchmarks were used to demonstrate the effectiveness of the proposed algorithms.

Key Insights and Ideas

  • Swarm Intelligence for Behavioral Diversity: SI algorithms like PSO and ACO are well-suited for generating a diverse set of behaviors, which is crucial for handling unexpected actions from other agents. This is a significant departure from methods that rely on pre-defined or manually crafted behavior sets.
  • Bridging the Gap in I-DIDs: The proposed PSB and ACB methods effectively address the long-standing challenge in I-DIDs of modeling unknown agent behaviors, making the framework more robust and applicable to real-world scenarios.
  • Diversity Enhances Robustness: The empirical results show that increased behavioral diversity (generated by PSB and ACB) leads to better average rewards for the subject agent, especially when the true behavior of the other agent is not among the initially considered models. This suggests that a broader exploration of possibilities makes the subject agent less susceptible to surprises.
  • PSB's Advantage: The PSB algorithm, in particular, demonstrated consistent superior performance, likely due to its balance between exploring individual behaviors and leveraging collective intelligence, effectively mitigating mode collapse.

Key Results

  • Improved Decision Quality: Both PSB and ACB algorithms significantly outperformed the baseline "Exact" method and the Genetic Algorithm (GA) in terms of average rewards, especially in more complex scenarios and longer planning horizons.
  • Enhanced Diversity: PSB and ACB generated models with demonstrably higher diversity compared to GA, leading to better performance for the subject agent.
  • Robustness to Unknown Behaviors: When the true behavior of the other agent was not included in the initial candidate models, PSB and ACB still achieved better results than Exact and GA, highlighting their ability to cope with novel situations.
  • Parameter Sensitivity: The performance of PSB and ACB is influenced by their parameters (e.g., inertia weight 'w' in PSO, exploration rate 'ε' in ACO), and optimal settings were identified through sensitivity analysis.

Limitations and Future Work

  • Parameter Tuning: The effectiveness of SI-based I-DID solutions is sensitive to parameter settings, which can be challenging to optimize. The authors suggest more systematic parameter analysis techniques and visualization tools.
  • Scalability for Long Horizons: While SI is used for behavior generation, solving I-DIDs with many agents and long planning horizons can still be computationally intensive. The authors note that the explicit structural nature of I-DIDs might limit scalability for very long-term planning.
  • Exploring More Complex Interactions: The current work focuses on pairwise interactions or a limited number of agents. Future work could explore more complex multiagent settings, including mixed cooperative and competitive scenarios, and investigate how agents' local structures influence collective behavior.
  • Alternative Approaches: The authors suggest exploring deep reinforcement learning or other generative methods as potential complements or alternatives for improving I-DID scalability and handling complex interactions.
  • Real-time Decision Making: The challenge of enabling the subject agent to timely update its own decisions in real-time based on the evolving behavior models of other agents remains an area for further research.

Summary updated

Abstract

Interactive dynamic influence diagrams (I-DIDs) are a general decision framework for a subject agent who interacts with other agents (of either collaborative or competitive) in a common environment with partial observability. The subject agent aims to optimize its decision-making (response strategy) while other agents concurrently adapt their behaviors over time. The I-DID model has faced a long-term challenge when other agents exhibit unknown behaviors that go beyond what the subject agent has planned for prior to their interactions. This is because the subject agent does not hold the capability of modeling unknown behaviours of other agents in traditional I-DID techniques. In this article, we adapt two different swarm intelligence (SI) techniques to develop new behaviours for other agents in I-DIDs. The SI-based algorithms have the strength of generating a collective set of behaviours that could potentially contain various types of agents’ behaviours. We theoretically analyze how the two algorithms impact the subject agent’s decision quality, and empirically demonstrate the algorithm performance in two commonly used problem domains.
BibTeX
@inproceedings{pan2025improved,
  author = {Yinghui Pan and Mengen Zhou and Biyang Ma and Yifeng Zeng and Yew-Soon Ong and Guoquan Liu},
  title = {{Improved decisions for unknown behaviours in interactive dynamic influence diagrams}},
  booktitle = {Artif. Intell. Rev},
  year = {2025},
  url = {https://openreview.net/forum?id=N3uazymC0q},
}
Figure