Improving Policies via Search in Cooperative Partially Observable Games

Free

Search techniques to improve policies in cooperative partially observable games

FreeFree tier

Type

Open Source

Visit Website GitHub (40 stars)

About Improving Policies via Search in Cooperative Partially Observable Games

This paper introduces two search-based techniques for improving arbitrary policies in cooperative partially observable games, focusing on the challenge of coordination and communication between agents. The first technique, single-agent search, converts the multi-agent problem into a single-agent setting by freezing all but one agent's policy. The second, multi-agent search, allows all agents to perform the same common-knowledge search procedure when computationally feasible, falling back to the original policy otherwise. Both methods are theoretically guaranteed to at least maintain the original policy's performance up to a bounded approximation error. Applied to the Hanabi benchmark, the search technique achieves a state-of-the-art score of 24.61/25, significantly improving over the previous best of 24.08/25. The work is published at AAAI 2020.

Key Features

Single-agent search that converts the multi-agent problem into a single-agent setting

Multi-agent search with common-knowledge search procedure

Theoretical guarantee of at least maintaining original policy performance (up to bounded approximation error)

Application to Hanabi achieves state-of-the-art score of 24.61/25

Improves performance of any agreed-upon policy without requiring retraining

Pros & Cons

Pros

Theoretically guaranteed to not degrade performance of the base policy
Achieves significant improvement in Hanabi, a challenging cooperative game
Applicable to any arbitrary policy, including RL-trained policies
Provides two complementary search approaches for different computational budgets

Cons

Multi-agent search requires computational feasibility to be applied simultaneously by all agents
Results are demonstrated only in the Hanabi benchmark, generalizability to other domains not fully validated
Approach assumes a common-knowledge search procedure, which may limit applicability

Best For

Improving policies in cooperative multi-agent games such as HanabiEnhancing coordination and communication in AI systems with theory of mindResearch in multiagent systems and partially observable environmentsBenchmarking search-based improvements for cooperative AI

FAQ

What is the main contribution of this paper?

The paper proposes two search techniques (single-agent and multi-agent) that can improve any agreed-upon policy in cooperative partially observable games, with theoretical guarantees and state-of-the-art results on Hanabi.

How does single-agent search work?

Single-agent search converts the multi-agent problem into a single-agent setting by making all but one agent play according to the agreed-upon policy, allowing the remaining agent to search for improvements.

What is the difference between single-agent and multi-agent search?

In single-agent search, only one agent performs search while others follow the base policy. In multi-agent search, all agents carry out the same common-knowledge search procedure when computationally feasible, falling back to the base policy otherwise.