# Combining a Meta-Policy and Monte-Carlo Planning for Scalable Type-Based Reasoning in Partially Observable Environments

arXiv: https://arxiv.org/abs/2306.06067 · HTML: https://mlsanity.com/paper/2306.06067/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 47 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 19 of 19)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems](https://mlsanity.com/paper/1709.08071/) (2017)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [A Game-Theoretic Model and Best-Response Learning Method for Ad Hoc Coordination in Multiagent Systems](https://mlsanity.com/paper/1506.01170/) (2015)
- [Improving Policies via Search in Cooperative Partially Observable Games](https://mlsanity.com/paper/1912.02318/) (2019)
- [K-level Reasoning for Zero-Shot Coordination in Hanabi](https://mlsanity.com/paper/2207.07166/) (2022)
- [Reasoning about Hypothetical Agent Behaviours and their Parameters](https://mlsanity.com/paper/1906.11064/) (2019)
- [Approximate exploitability: Learning a best response in large games](https://mlsanity.com/paper/2004.09677/) (2020)
- [Belief and Truth in Hypothesised Behaviours](https://mlsanity.com/paper/1507.07688/) (2015)
- [Learning in POMDPs with Monte Carlo Tree Search](https://mlsanity.com/paper/1806.05631/) (2018)
- [Scalable Planning and Learning for Multiagent POMDPs: Extended Version](https://mlsanity.com/paper/1404.1140/) (2014)
- [Nested Reasoning About Autonomous Agents Using Probabilistic Programs](https://mlsanity.com/paper/1812.01569/) (2018)
- [Scalable Decision-Theoretic Planning in Open and Typed Multiagent Systems](https://mlsanity.com/paper/1911.08642/) (2019)
- [Decentralized MCTS via Learned Teammate Models](https://mlsanity.com/paper/2003.08727/) (2020)
- [Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning](https://mlsanity.com/paper/2302.00797/) (2023)
- [On Convergence and Optimality of Best-Response Learning with Policy Types in Multiagent Systems](https://mlsanity.com/paper/1907.06995/) (2019)

## Abstract (arXiv)

The design of autonomous agents that can interact effectively with other agents without prior coordination is a core 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 state and actions of the other agent or do not scale efficiently to larger problems with longer planning horizons. Addressing these limitations, we propose Partially Observable Type-based Meta Monte-Carlo Planning (POTMMCP) - an online Monte-Carlo Tree Search based planning method for type-based reasoning in large partially observable environments. POTMMCP incorporates a novel meta-policy for guiding search and evaluating beliefs, allowing it to search more effectively to longer horizons using less planning time. We show that our method converges to the optimal solution in the limit and empirically demonstrate that it effectively adapts online to diverse sets of other agents across a range of environments. Comparisons with the state-of-the art method on problems with up to 1014 states and 108 observations indicate that POTMMCP is able to compute better solutions significantly faster.