Bayes-Adaptive Monte-Carlo Planning for Type-Based Reasoning in Large Partially Observable, Multi-Agent Environments

Designing autonomous agents that can interact effectively with other agents without prior coordination is an important problem in multi-agent systems. Type-based reasoning methods achieve this by maintaining a belief over a set of potential behaviours for the other agents. However, current methods are limited in that they assume full observability of the environment or do not scale efficiently to larger problems with longer planning horizons. Addressing these limitations, we propose Bayes-Adaptive Partially Observable Stochastic Game Monte-Carlo Planning (BAPOSGMCP)-a scalable online planner for Type-based reasoning in partially observable environments-which combines Monte-Carlo Tree Search with a novel meta-policy for selecting the best policy to guide search during planning. Through comprehensive evaluations we demonstrate that BAPOSGMCP is able to effectively adapt online to diverse sets of agents in large cooperative, competitive and mixed environments with up to 10 14 states and 10 8 observations.