Improving Policies via Search in Cooperative Partially Observable Games

Introduction

Real-world situations such as driving require humans to coordinate with others in a partially-observable environment with limited communication. In such environments, humans have a mental model of how other agents will behave in different situations (theory of mind). This model allows them to change their beliefs about the world based on why they think an agent acted as they did, as well as predict how their own actions will affect others’ future behavior. Together, these capabilities allow humans to search for a good action to take while accounting for the behavior of others.

Despite the importance of these cooperative settings to real-world applications, most recent progress on AI in large-scale games has been restricted to zero-sum settings where agents compete against each other, typically rendering communication useless. Search has been a key component in reaching professional-level performance in zero-sum games, including backgammon (?), chess (?), Go (?; ?; ?), and poker (?; ?; ?).

Inspired by the success of search techniques in these zero-sum settings, in this paper we propose methods for agents to conduct search given an agreed-upon ‘convention’ policy (which we call the blueprint policy) in cooperative partially observable games. We refer to these techniques collectively as Search for Partially Observing Teams of Agents (SPARTA). In the first method, a single agent performs search assuming all other agents play according to the blueprint policy. This allows the search agent to treat the known policy of other agents as part of the environment and maintain beliefs about the hidden information based on others’ actions.

In the second method, multiple agents can perform search simultaneously but must simulate the search procedure of other agents in order to understand why they took the actions they did. We propose a modification to the multi-agent search procedure - retrospective belief updates - that allows agents to fall back to the blueprint policy when it is too expensive to compute their beliefs, which can drastically reduce the amount of computation while allowing for multi-agent search in most situations.

Going from just the blueprint policy, to single-agent search, to multi-agent search each empirically improves performance at the cost of increased computation. Additionally, we prove that SPARTA cannot result in a lower expected value than the blueprint policy except for an error term that decays in the number of Monte Carlo (MC) rollouts.

We test these techniques in Hanabi, which has been proposed as a new benchmark challenge problem for AI research (?). Hanabi is a popular fully cooperative, partially observable card game with limited communication. Most prior agents for Hanabi have been developed using handcrafted algorithms or deep reinforcement learning (RL). However, the Hanabi challenge paper itself remarks that “humans approach Hanabi differently than current learning algorithms” because while RL algorithms perform exploration to find a good joint policy (convention), humans instead typically start with a convention and then individually search for the best action assuming that their partners will play the convention (?).

Applying SPARTA to an RL blueprint (that we train in self-play) establishes a new state-of-the-art score of 24.61 / 25 on 2-player Hanabi, compared to a previous-best of 24.08 / 25. Our search methods also achieve state-of-the-art scores in 3, 4, and 5-player Hanabi (Table 1). To our knowledge, this is the first application of theoretically sound search in a large partially observable cooperative game.

We provide code for single- and multi-agent search in Hanabi as well as a link to supplementary material at https://github.com/facebookresearch/Hanabi_SPARTA

Related Work

Search has been necessary to achieve superhuman performance in almost every benchmark game. For fully observable games, examples include two-ply search in backgammon (?), alpha-beta pruning in chess (?), and Monte Carlo tree search in Go (?; ?; ?). The most prominent partially observable benchmark game is poker, where search based on beliefs was key to achieving professional-level performance (?; ?; ?). Our search technique most closely resembles the one used in the superhuman multi-player poker bot Pluribus, which conducts search given each agents’ presumed beliefs and conducts MC rollouts beyond the depth limit of the search space assuming all agents play one of a small number of blueprint policies.

Cooperative multi-agent settings have been studied extensively under the DEC-POMDP formalism (?). Finding optimal policies in DEC-POMDPs is known to be NEXP-hard (?), so much prior work studies environments with structure such as factorized local interactions (?), hierarchical policies (?), or settings with explicit costs of communication (?).

There has been a good deal of prior work developing agents in Hanabi. Notable examples of hand-crafted bots that incorporate human conventions include SmartBot (?) and Fireflower (?). Alternatively, so called ‘hat-coding’ strategies (?), which are particularly successful for N $>$ 2 players, instead use information theory by communicating instructions to all players via hints using modulo-coding, as is commonly employed to solve ‘hat-puzzles’. More recent work has focused on tackling Hanabi as a learning problem (?; ?). In this domain, the Bayesian Action Decoder learning method uses a public belief over private features and explores in the space of deterministic partial policies using deep RL (?), which can be regarded as a scalable instantiation of the general ideas presented in (?). The Simplified Action Decoder algorithm established the most recent state of the art in Hanabi (?).

Lastly, there is recent work on ad-hoc team play in Hanabi, in which agents get evaluated against a pool of different teammates (?; ?).

Background

In order to represent variable sequence lengths trajectories, $\tau^{i}_{t}$, Deep RL in partially observable settings typically uses recurrent networks (RNNs) (?). These RNNs can learn implicit representations of the sufficient statistics over the Markov state given $\tau^{i}_{t}$. In contrast, in our work we will use explicit beliefs to represent the probability distribution over possible trajectoriesMaintaining exact beliefs in large POMDPs is typically considered intractable. However we find that even in an environment with large state spaces such as card games, the number of states that have non-zero probability conditional on a player’s observations is often much smaller; in the case of Hanabi, this set of possible states can be stored and updated explicitly.. The private belief of agent $i$ that they are in trajectory $\tau_{t}$ at time step $t$ is $B^{i}(\tau_{t})=P(\tau_{t}|\tau^{i}_{t})$. We also define $B(\tau_{t})=P(\tau_{t}|\tau_{t}^{\mathcal{G}})$ and $B(\tau^{i}_{t})=P(\tau^{i}_{t}|\tau_{t}^{\mathcal{G}})=\sum_{\tau_{t}\in\tau_{t}^{i}}B(\tau_{t})$, which is the probability that agent $i$ is in AOH $\tau^{i}_{t}$ conditional only on the common knowledge (CK) of the entire group of agents $\tau^{\mathcal{G}}_{t}$. Here CK are things that all agents know that all agents know ad infinitum. Please see (?) for a formal definition of CK and (?; ?) for examples of how CK can arise and be used in multi-agent learning. Practically it can be computationally challenging to exactly compute common-knowledge beliefs due a large number of possible states and trajectories. However, in many settings, e.g., poker (?), the CK-belief can be factorized across public features and a set of private features associated with the different agents. In these settings the CK trajectory is simply the history of public features.

In our methods we will commonly need to carry out computations over each of the possible trajectories that have non-zero probability given an agent’s AOH or all agents’ common knowledge. We refer to these as the trajectory range $\beta^{i}_{t}=\{\tau_{t}|B^{i}(\tau_{t})>0\}$ and $\beta_{t}=\{\tau_{t}|B(\tau_{t})>0\}$. We refer to the vector of probabilities in the trajectory range on timestep $t$ by ${\bf B}_{t}^{i}$ and ${\bf B_{t}}$. We also commonly need to carry out computations over each of an agent’s AOHs that have non-zero probability given the common knowledge of the entire group of agents, which we refer to as the AOH range $\chi^{i}_{t}=\{\tau^{i}_{t}|B(\tau^{i}_{t})>0\}$. We refer to the entire vector of probabilities in the AOH range of agent $i$ on timestep $t$ by ${\bf C}^{i}_{t}$.

We further define the typical conditional expectations (‘value functions’),

Given the range defined above we also introduce expectations conditioned on the AOHs, $\tau^{i}_{t}$:

Even though the optimal policies in the fully cooperative setting are deterministic, we consider stochastic policies for the purpose of reinforcement learning.

We further assume that a deterministic blueprint policy $\pi_{b}$, defining what each player should do for all possible trajectories, is common knowledge amongst all players. Player $i$’s portion of the blueprint policy is denoted $\pi^{i}_{b}$ and the portion of all players other than $i$ as $\pi_{b}^{-i}$. In some settings, when actually playing, players may choose to not play according to the blueprint and instead choose a different action determined via online search. In that case $\pi_{b}$ differs from $\pi$, which denotes the policy that is actually played.

In our setting all of the past actions taken by all agents and the observation functions of all players are common knowledge to all agents. As such, if an agent is known to be playing according to a given policy, each action taken by this agent introduces a belief update across all other agents and the public belief. Suppose agent $i$ has a current belief $B_{t-1}^{i}$ and next observes $(a_{t}^{j},o_{t}^{i})$, where we have broken up the observation to separate out the observed partner action. Then,

In other words, the belief update given $(a_{t}^{j},o_{t}^{i})$ consists of two updates: one based on the partner’s known policy $\pi^{j}$, and the other based on the dynamics of the environment. The common knowledge belief $B$ is updated in the same way, using the common-knowledge observation $\tau^{\mathcal{G}}$ rather than $\tau^{i}$.

Method

In this section we describe SPARTA, our online search algorithm for cooperative partially-observable games.

We first consider the case in which only one agent conducts online search. We denote the searching agent as agent $i$. Every other agent simply plays according to the blueprint policy (and we assume agent $i$ knows all other agents play according to the blueprint).

Since agent $i$ is the only agent determining her policy online while all other agents play a fixed common-knowledge policy, this is effectively a single-agent POMDP for agent $i$. Specifically, agent $i$ maintains a belief distribution ${\bf B}_{t}^{i}$ over trajectories she might be in based on her AOH $\tau_{t}^{i}$ and the known blueprint policy of the other agents. Each time she receives an observation or another agent acts, agent $i$ updates her belief distribution according to (6) (see Figure 1, left). Each time $i$ must act, she estimates via Monte Carlo rollouts the expected value $Q_{\pi_{b}}(\tau_{t}^{i},a^{i})$ of each action assuming all agents (including agent $i$) play according to the joint blueprint policy $\pi_{b}$ for the remainder of the game following the action (Figure 1, right). A precise description of the single-agent search algorithm is provided in the appendix.

As described, agent $i$ calculates the expected value of only the next action. This is referred to as 1-ply search. One could achieve even better performance by searching further ahead, or by having the agent choose between multiple blueprint policies for the remainder of the game. However, the computational cost of the search would also increase, especially in a game like Hanabi that has a large branching factor due to chance. In this paper all the experiments use 1-ply search.

Since this search procedure uses exact knowledge of all other agents’ policies, it cannot be conducted correctly by multiple agents independently. That is, if agent $j$ conducts search on a turn after agent $i$ conducted search on a previous turn, then agent $j$’s beliefs are incorrect because they assume agent $i$ played $\pi^{i}_{b}$ while agent $i$ actually played the modified policy $\pi^{i}$. If more than one agent independently performs search assuming that others follow the blueprint, policy improvement cannot be guaranteed, and empirical performance is poor (Table 4, Appendix).

Multi-Agent Search

In order for an agent to conduct search effectively, her belief distribution must be accurate. In the case of single-agent search, this was achieved by all agents agreeing beforehand on a blueprint policy, and then also agreeing that only one agent would ever conduct search and deviate from the blueprint. In this section we instead assume that all agents agree beforehand on both a blueprint policy and on what search procedure will be used. When agent $i$ acts and conducts search, the other agents exactly replicate the search procedure conducted by agent $i$ (including the random seed) and compute agent $i$’s resulting policy accordingly. In this way, the policy played so far is always common knowledge.

Since the other agents do not know agent $i$’s private observations, we have all agents (including agent $i$) conduct search and compute agent $i$’s policy for every possible AOH that agent $i$ might be in based on the common-knowledge observations. Specifically, all agents conduct search for every AOH $\tau^{\prime i}_{t}\in\chi^{i}_{t}$. When conducting search for a particular $\tau^{\prime i}_{t}$ as part of this loop, the agents also compute what ${\bf B}_{i}^{t}$ would be assuming agent $i$’s AOH is $\tau^{\prime i}_{t}$ and compute $Q_{\pi_{b}}(\tau^{\prime i}_{t},a^{i})$ for every action $a^{i}$ based on this ${\bf B}_{i}^{t}$. We refer to this loop of search over all $\tau^{\prime i}_{t}\in\chi_{t}^{i}$ as range-search.

Agent $i$ must also compute her policy via search for every $\tau^{\prime i}_{t}\in\chi^{i}_{t}$ (that is, conduct range-search) even though she knows $\tau^{i}_{t}$, because the search procedure of other agents on future timesteps may be based on agent $i$’s policy for $\tau^{\prime i}_{t}\neq\tau^{i}_{t}$ where $\tau^{\prime i}_{t}\in\chi^{i}_{t}$ and it is necessary for all agents to be consistent on what that policy is to ensure that future search procedures are replicated identically by all agents.

In a game like two-player Hanabi, $|\chi^{i}_{t}|$ could be nearly 10 million, which means the range-search operation of multi-agent search could be 10 million times more expensive than single-agent search in some situations and therefore infeasible. Fortunately, the actual number of positive-probability AOHs will usually not be this large. We therefore have all agents agree beforehand on a budget for range-search, which we refer to as a max range (abbreviated MR). If $|\chi^{i}_{t}|>\textit{MR}$ on timestep $t$ where agent $i$ is the acting agent, then agent $i$ does not conduct search and instead simply plays according to the blueprint policy $\pi_{b}$. Since $\chi^{i}_{t}$ and the max range are common knowledge, it is also common knowledge when an agent does not search on a timestep and instead plays according to the blueprint.

Using a max range makes multi-agent search feasible on certain timesteps, but the fraction of timesteps in which search can be conducted may be less than single-agent search (which in a balanced two-player game is 50%). The next section describes a way to use a max range while guaranteeing that there’s always at least one agent who can perform search.

Retrospective Belief Updates

As discussed in the previous section, $\chi^{i}_{t}$ on some timesteps may be too large to conduct search on. Using a max range mitigates this problem, but may result in search only rarely being conducted. Fortunately, in many domains more common knowledge information is revealed as the game progresses, which reduces the number of positive-probability AOHs on previous timesteps.

For example, at the start of a two-player game of Hanabi in which agent $i$ acts first (and then agent $j$), $|\chi^{i}_{0}|$ might be nearly 10 million. If agent $i$ were to use search to choose an action at this point, it would be too expensive for the agents to run range-search given the magnitude of $|\chi^{i}_{0}|$, so the other agents would not be able to conduct search on future timesteps.

However, suppose the action chosen from agent $i$’s search results in agent $i$ giving a hint to agent $j$. Given this new common-knowledge information, it might now be known that only 100,000 of the 10 million seemingly possible AOHs at the first timestep were actually possible. It may now be feasible for the agents to run range-search on this reduced set of 100,000 possible AOHs. In this way, agent $i$ is able to conduct search on a timestep $t$ where the max range is exceeded, and the agents can execute range-search at some later timestep $t^{\prime}$ once further observations have reduced the size of $\chi^{i}_{t}$ below the max range.

We now introduce additional notation to generalize this idea. Agent $i$’s belief at timestep $t^{\prime}$ that the trajectory at some earlier timestep $t$ was (or is) $\tau_{t}$ is $B^{i}_{t^{\prime}}(\tau_{t})=P(\tau_{t}|\tau_{t^{\prime}}^{i})$. The public belief at timestep $t^{\prime}$, which conditions only on the common knowledge of the entire group of agents at timestep $t^{\prime}$, that the trajectory at timestep $t$ was (or is) $\tau_{t}$ is $B_{t^{\prime}}(\tau_{t})=P(\tau_{t}|\tau_{t^{\prime}}^{\mathcal{G}})$ and $B_{t^{\prime}}(\tau^{i}_{t})=P(\tau^{i}_{t}|\tau_{t^{\prime}}^{\mathcal{G}})=\sum_{\tau_{t}\in\tau_{t}^{i}}B_{t^{\prime}}(\tau_{t})$. The trajectory range at timestep $t^{\prime}$ of the trajectories at timestep $t$ is $\beta_{t,t^{\prime}}=\{\tau_{t}|B_{t^{\prime}}(\tau_{t})>0\}$ and $\beta^{i}_{t,t^{\prime}}=\{\tau_{t}|B_{t^{\prime}}^{i}(\tau_{t})>0\}$. The AOH range at timestep $t^{\prime}$ of the agent $i$ AOHs at timestep $t$ is $\chi^{i}_{t,t^{\prime}}=\{\tau^{i}_{t}|B_{t^{\prime}}(\tau^{i}_{t})>0\}$.

Again, the key idea behind retropective updates is that an agent can delay running range-search on a timestep until that range shrinks based on subsequent observations. When it is an agent’s turn to act, she conducts search if and only if she has run range-search for each previous timestep $t$ where one of the other agents played search (because this means she knows her belief distribution). Otherwise, she plays according to the blueprint policy.

Specifically, all agents track the oldest timestep on which search was conducted but range-search was not conducted. This is denoted $t^{*}$. Assume the agent acting at $t^{*}$ was agent $i$. If at any point $|\chi^{i}_{t^{*},t}|\leq\textit{MR}$ then all agents conduct range-search for timestep $t^{*}$ and $t^{*}$ is incremented up to the next timestep on which search was conducted but range-search was not conducted (but obviously not incremented past the current timestep $t$). If $|\chi^{i}_{t^{*},t}|\leq\textit{MR}$ for this new $t^{*}$ then all agents again conduct range-search and the process repeats. Since $\chi^{i}_{t^{*},t}$ depends only on common knowledge, all agents conduct range-search at the same time and therefore $t^{*}$ is always consistent across all agents. When it is an agent’s turn to act on timestep $t$, she conducts search if and only if she was the agent to act on timestep $t^{*}$ or if $t=t^{*}$. An important upshot of this method is that it’s always possible for at least one agent to use search when acting.

If MR is set to zero then multi-agent search with retrospective updates is identical to single-agent search, because the first agent to act in the game will conduct search and she will continue to be the only agent able to conduct search on future timesteps. As MR is increased, agents are able to conduct search on an increasing fraction of timesteps. In two-player Hanabi, setting $\textit{MR}=$ 10,000 makes it possible to conduct search on 86.0% of timesteps even though in the worst case $|\chi^{i}_{t}|\approx$ 10,000,000.

Soundness and Convergence Bound for Search

We now prove a theorem that applies to all three SPARTA variants described in this section. Loosely, it states that applying search on top of a blueprint policy cannot reduce the expected reward relative to the blueprint, except for an error term that decays as $O(1/\sqrt{N})$, where $N$ is the number of Monte Carlo rollouts.

Consider a Dec-POMDP with N agents, actions $\mathcal{A}$, reward bounded by $r_{\textit{min}}\leq R(\tau)<r_{\textit{max}}$ where $r_{\textit{max}}-r_{\textit{min}}\leq\Delta$, game length bounded by $T$, and a set of blueprint policies $\pi_{b}\equiv\{\pi_{b}^{0},\ldots,\pi_{b}^{N}\}$. If a Monte Carlo search policy $\pi_{s}$ is applied using $N$ rollouts per step, then

Experimental Setup

We evaluate our methods in the partially observable, fully cooperative game Hanabi, which at a high level resembles a cooperative extension of solitaire. Hanabi has recently been proposed as a new frontier for AI research (?) with a unique focus on theory of mind and communication.

The main goal of the team of agents is to complete 5 stacks of cards, one for each color, in a legal sequence, starting with a $\mathbf{1}$ and finishing with a $\mathbf{5}$. The defining twist in Hanabi is that while players can observe the cards held by their teammates, they cannot observe their own cards. As such, players need to exchange information with their teammates in order to decide which cards to play. Hanabi offers two different means for doing so. First, players can take costly hint actions that reveal part of the state to their teammates. Second, since all actions are observed by all players, each action (such as playing a card or discarding a card) can itself be used to convey information, in particular if players agree on a set of conventions before the game. For further details on the state and action space in Hanabi please see (?).

In this work we are focused on the self-play part of the challenge, in which the goal is to find a set of policies that achieve a high score when playing together as a team.

For the blueprint strategy used in the experiments, we experimented with open-sourced handcrafted bots WTFWThat (?) and SmartBot (?). We also created two of our own blueprint strategies. One was generated from scratch using deep reinforcement learning, which we call RLBot. The other, which we call CloneBot, was generated by conducting imitation learning using deep neural networks on the policy produced by single-agent search on top of SmartBot. The details for the generation of both bots are given in the appendix.

All experiments except the imitation learning of CloneBot and the reinforcement learning of RLBot were conducted on CPU using machines with Intel® Xeon® E5-2698 CPUs containing 40 cores each. A game of Hanabi requires about 2 core-hours for single-agent search and 90 core-hours for retrospective multi-agent search using the SmartBot blueprint policy with a max range of 10,000. We parallelize the search procedure over multiple cores on a single machine.

The public and private observations in Hanabi are factorizable into public and private features.The class of games of this form has recently been formalized as ‘Factorized Observation Games’ in (?). Specifically, each player’s hidden information consists of the cards held by other agents, so the beliefs for each player can be represented as a distribution over possible hands that player may be holding. The initial private beliefs can be constructed based on the card counts. In addition to updates based on the actions of other agents, updates based on observations amount to (a) adjusting the probabilities of each hand based on the modified card count as cards are revealed, and (b) setting the probability of hands inconsistent with hints to 0.

The public beliefs for 2-player Hanabi can be factored into independent probability distributions over each player’s hand (conditional on the common knowledge observations). These public beliefs are identical to the private beliefs except that the card counts are not adjusted for the cards in the partner’s hand. Given one player’s hand, the private beliefs over the other player’s hand (which is of course no longer independent of the other player’s hand) can be computed from the public beliefs by adjusting the card counts for the privately-observed cards.This conversion from public to private beliefs is what we call ConditionOnAOH() in the algorithm listing in the Appendix.

Estimating Action Expected Values via UCB

In order to reduce the number of MC rollouts that must be performed during search, we use a UCB-like procedure that skips MC rollouts for actions that are presumed not to be the highest-value action with high confidence. After a minimum of 100 rollouts per action is performed, the reward sample mean and its standard deviation is computed for each action. If the expected value for an action is not within 2 standard deviations of the expected value of the best action, its future MC rollouts are skipped.

Furthermore, we use a configurable threshold for deviating from the blueprint action. If the expected value of the action chosen by search does not exceed the value of the blueprint action by more than this threshold, the agent plays the blueprint action. We use a threshold of $0.05$ in our experiments.

The combination of UCB and the blueprint deviation threshold reduces the number of rollouts required per timestep by 10$\times$, as shown in Figure 3 in the appendix.

Bootstrapping Search-Based Policies via Imitation Learning

Search can be thought of as a policy improvement operator, i.e. an algorithm that takes in a joint policy and outputs samples from an improved joint policy. These samples can be used as training data to learn a new policy via imitation learning. This improved policy approximates the effect of search on the blueprint policy while being cheaper to execute, and search can be run on this learned policy, in effect bootstrapping the search procedure. In principle, repeated application of search and learning could allow the effect of single-agent search to be applied on multiple agents, and could allow the benefits of search to extend beyond the depth limit of the search procedure. However, there is no guarantee that this process would eventually converge to an optimal policy, even in the case of perfect function approximation.

We refer to the policy learned in this manner as CloneBot. We provide details of the training procedure in the Appendix and evaluate its performance in Table 1.

Results

Table 1 shows that adding SPARTA leads to a large improvement in performance for all blueprint policies tested in two-player Hanabi (the most challenging variant of Hanabi for computers) and achieves a new state-of-the-art score of 24.61 / 25 compared to the previous-best of 24.08 / 25.It is impossible to achieve a perfect score for some shuffles of the deck. However, the highest possible average score is unknown. Much of this improvement comes from adding single-agent search, though adding multi-agent search leads to an additional substantial improvement.

Unfortunately there are no reliable statistics on top human performance in Hanabi. Discussions with highly experienced human players has suggested that top players might achieve perfect scores in 2-player Hanabi somewhere in the range of 60% to 70% of the time when optimizing for perfect scores. Our strongest agent optimizes for expected value rather than perfect scores and still achieves perfect scores 75.5% of the time in 2-player Hanabi.

Table 2 shows the benefits of single-agent search also extend to the 3, 4, and 5-player variants of Hanabi as well. For these variants, the SAD agent (?) was state-of-the-art among learned policies, while an information-theoretic hat-coding policy (WTFWThat) achieves close to perfect scores for 4 and 5 players (?). Applying single-agent search to either SAD or WTFWThat improves the state-of-the-art scores for 3, 4, and 5-player variants (Table 2, Table 5 in Appendix). Applying multi-agent search in Hanabi becomes much more expensive as the number of players grows because the number of cards each player observes becomes larger.

Table 3 examines the performance and cost in number of rollouts for single-agent search and multi-agent search with different values of the max range (MR) parameter, using SmartBot as the blueprint agent. When MR is set to zero, we are performing single-agent search, so search is conducted on 50% of timesteps, which requires about $10^{5}$ rollouts per gameSPARTA also performs counterfactual belief updates using the blueprint, using about $2\times 10^{6}$ policy evaluations per game, which corresponds to about $4\times 10^{4}$ games worth of policy evaluations. This cost is dominated by search rollouts for all SPARTA variants.. As the max range is increased, search is conducted more often. At a max range of 10,000, search is conducted on 86% of timesteps even though the maximum possible range for a timestep in two-player Hanabi is nearly 10 million. However, this still requires about 1,000$\times$ as many rollouts as single-agent search.

Figure 2 plots the average MC search prediction of the expected payoff of the best move ($Q_{\pi_{b}}(\tau^{i},a^{*})$) at different points in the game, for two blueprint policies. As predicted by the theory, the expected score starts at the blueprint expected score and increases monotonically as search is applied at each move of the game.

Conclusions

In this paper we described approaches to search in partially observable cooperative games that improves upon an arbitrary blueprint policy. Our algorithms ensure that any agent conducting search always has an accurate belief distribution over the possible trajectories they may be in, and provide an alternative in case the search procedure is intractable at certain timesteps. We showed that in the benchmark domain of Hanabi, both search techniques lead to large improvements in performance to all the policies we tested on, and achieves a new state of the art score of 24.61 / 25 compared to a previous-best of 24.08 / 25. We also proved that applying our search procedure cannot hurt the expected reward relative to the blueprint policy, except for an error term that shrinks with more Monte Carlo rollouts. This result fits a theme, also shown in other games such as Chess, Go, and Poker, that search leads to dramatically improved performance compared to learning or heuristics alone.

The performance improvements from search come at a computational cost. Our search procedure involves tracking the belief probability of each AOH that a player may be in given the public information, which for Hanabi is no more than 10 million probabilities. Search also requires computing a large number of MC rollouts of the policy, especially for multi-agent search where the number of rollouts scales with the size of the belief space. Conducting search in partially observable games, whether cooperative or competitive, with many more AOHs per instance of public information remains an interesting challenge for future work and may be applicable to settings like Bridge and environments with visual inputs like driving.

This work currently assumes perfect knowledge of other agents’ policies. This is a reasonable assumption in settings involving centralized planning but decentralized execution, such as self-driving cars that are created by a single company or robots working together as a team in a factory. In general however, an agent’s model of others may not be perfect. Investigating how search performs in the presence of an imperfect model of the partner, and how to make search more robust to errors in that model, are important directions for future work as well.

Acknowledgments

We would like to thank Pratik Ringshia for developing user interfaces used to interact with Hanabi agents.

References

Appendix A Search Algorithm Listing

Appendix B Experimental Details for Reinforcement Learning

We train the reinforcement learning baseline with our own implementation of Ape-X DQN (?) on the Hanabi Learning Environment (HLE) (?). Essentially, Ape-X DQN is a distributed Q-learning framework with a large number of asynchronous actors feeding transitions into a shared prioritized replay buffer (?) in parallel, and a centralized learner that samples from the replay buffer to update the agent. It also incorporates several techniques for improved performance such as $n$-step return targets (?), double Q-learning (?) and dueling network architecture (?). There are two notable differences between our implementation and the one proposed in the original paper. First, instead of having 360 actors each running on a single environment on a CPU, we use 80 actors while each of them running on a vector of 20 environments. We loop over 20 environments and batch their observations together. Then the actor acts on the batch data using GPU. With this modification, our implementation can run under moderate computation resources with 20 CPU cores (40 Hyper-Threads) and 2 GPUs where one GPUs is used for training and the other is shared by all 80 asynchronous actors. Second, we synchronize all actors with learner every 10 mini-batches while in the original paper each actor independently synchronize with the learner every 400 environment steps.

We modify the input features of HLE by replacing card knowledge section with the V0-Belief proposed in (?). To avoid the agent being overly cautious, we do not zero out reward for games in which all life tokens are exhausted during training, even though we report numbers according to the counting scheme at test time. The agent uses a 3 layer fully connected network with 512 neurons each layer, followed by two-stream output layers for value and advantage respectively. Similar to the original Ape-X paper, each actor executes an $\epsilon_{i}$-greedy policy where $\epsilon_{i}=\epsilon^{1+\frac{1}{N-1}\alpha}$ for $i\in\{0,...,N-1\}$ but with a smaller $\epsilon=0.1$ and $\alpha=7$. The discount factor $\gamma$ is set to $0.999$. The agent is trained using Adam optimizer (?) with learning rate $=6.25\times 10^{-5}$ and $\epsilon=1.5\times 10^{-5}$. Each mini-batch contains $512$ transitions sampled from the prioritized replay buffer with priority exponent of $0.6$ and importance sampling exponent equal to $0.4$.

Appendix C Experimental Details for Imitation Learning Applied to Search

We train a supervised policy for one agent using sampled AOH-action pairs from 1.3 million games where single-agent search was applied to the SmartBot blueprint policy. The model is a 2-layer, 128-unit LSTM, which takes as input a representation of the AOH as described in the previous section, as well as the action the blueprint agent plays at this AOH. This latter input is available at inference time and is crucial to achieve good performance, presumably because the neural model can “fall back” to the blueprint policy, which may be hard to approximate in some situations (as it’s not a neural policy).

The model outputs a softmax policy $\pi_{clone}$ and is optimized using the objective function is the expected reward $\sum_{a}{\pi_{clone}(\tau^{i},a)Q(\tau^{i},a)}$ . At test time we execute the action with the highest probability under the policy. We found that this objective led to a stronger agent than either predicting $Q(\tau^{i},a)$ directly with an MSE loss - which wastes model capacity predicting $Q$ for unplayed actions - or predicting $a$ directly with a cross-entropy loss - which forces the model to select between actions with nearly identical value.

We train the model for 100,000 SGD steps, a batch size of 256, using the RMSprop optimizer with a learning rate of $5\times 10^{-4}$.

Appendix D Additional Results

Figure 3 shows the effect of the blueprint deviation threshold and UCB-like search pruning on average score. Interestingly, a threshold of 0.05 improves the total score even for a large number of rollouts; perhaps this is because the move chosen by SmartBot is more useful for future search optimizations later in the game. UCB reduces the number of rollouts per turn without affecting the average score.

Table 4 lists average scores in 2-player Hanabi using independent multi-agent search. In this variant, both players independently perform search (incorrectly) assuming that the partner is playing the blueprint. Without modification, this approach leads to undefined situations where the partner’s beliefs contain no states. To solve this, we add some uncertainty to the model of the partner’s strategy.

In the table, we sweep two parameters: the uncertainty about the partner’s strategy in the belief update, and the threshold minimum difference in expected reward at which the agent will deviate from the blueprint. The rationale for the threshold is that any time a player deviates from the blueprint, they are corrupting their partner’s beliefs, so this should only be done when it is substantially beneficial. Under some settings, independent joint search performs better than the blueprint (22.99) but never outperforms single-agent search.

Table 5 shows new state-of-the-art results in 3, 4, and 5 player Hanabi by applying search on top of the information-theoretic ‘WTFWThat‘ hat-coding policy. This hat-coding policy achieves near-perfect scores but is not learned and considered somewhat against the spirit of the game, since it does not use grounded information at all. Nevertheless, we show here that even these policies can be improved with single-agent search.

Appendix E Proof of Main Theorem

Consider a Dec-POMDP with N agents, actions $\mathcal{A}$, reward bounded by $r_{\textit{min}}\leq R(\tau)<r_{\textit{max}}$ where $r_{\textit{max}}-r_{\textit{min}}\leq\Delta$, game length bounded by $T$, and a set of blueprint policies $\pi_{b}\equiv\{\pi_{b}^{0}\ldots\pi_{b}^{N}\}$. If a MC search policy $\pi_{s}$ is applied using $N$ rollouts per step, then

Consider agent $i$ at some (true) trajectory $\tau$. This agent has an exact set of beliefs $B^{i}(\tau^{i})$, i.e. the exact probability distribution over trajectories it could be in given its action-observation history $\tau^{i}$.

Suppose that an agent at some point $\tau$ acts according to the search procedure described in Section Method (it is not relevant whether single-agent or joint search is performed). For each action $a\in\mathcal{A}$, the agent collects $N/|\mathcal{A}|$ i.i.d. samples of the reward $R$, sampling trajectories from $\tau\sim B^{i}(\tau^{i})$ and assuming that agent $i$ plays some action $a$ at $\tau^{i}$ and all agents play according to ${\pi_{b}}$ thereafter. We denote a single MC rollout (which is an MC estimate of $Q_{\pi_{b}}(\tau^{i},a)$) as $\hat{Q}_{\pi_{b}}^{k}(\tau^{i},a)$, and the mean of the rollouts for $a$ as $\hat{Q}_{\pi_{b}}(\tau^{i},a)$. The agent then plays $\hat{a}^{*}\equiv\operatorname*{argmax}\limits_{a\in\mathcal{A}}{\hat{Q}_{\pi_{b}}(\tau^{i},a)}$. We denote the true optimal action as $a^{*}\equiv\operatorname*{argmax}\limits_{a\in\mathcal{A}}{Q_{\pi_{b}}(\tau^{i},a)}$.

Line (10) adds canceling terms and line (11) simplifies the expression using the definition of $\hat{a}^{*}$.

We will now use a concentration inequality to bound (12). To do so we will need refer to some facts about subgaussian random variables, which loosely means those whose tails die off at least as fast as a Gaussian.

Let $X$ be a random variable with mean and $X\in[a,b]$, $\Delta=b-a$. Then $X$ is $\Delta/2$-subgaussian.

Suppose that $X_{1},\ldots,X_{n}$ are independent and $\sigma$-subgaussian. Then their mean is $\frac{\sigma}{\sqrt{n}}$-subgaussian.

Suppose that $X_{1},\ldots,X_{n}$ are each $\sigma$-subgaussian. Then

Now we can apply these results to our setting. $\hat{Q}_{\pi_{b}}^{k}(\tau^{i},a)-Q_{\pi_{b}}(\tau^{i},a)$ has mean 0 and bounded width $\Delta$, therefore by Lemma 1 it is $\Delta/2$-subgaussian. The search procedure performs $N/|\mathcal{A}|$ rollouts per action, so from Lemma 2 the mean $\hat{Q}_{\pi_{b}}(\tau^{i},a)-Q_{\pi_{b}}(\tau^{i},a)$ is $\left(\frac{\Delta}{2}\sqrt{\frac{|\mathcal{A}|}{N}}\right)$-subgaussian. Finally, applying Lemma 3 to the bound in (12), we have

We can simplify this a bit using the fact that $\log(X)\leq X$ for $X\geq 1$:

We can now prove the main theorem. We denote the policy that follows the MC search procedure up to time $t$ and the blueprint ${\pi_{b}}$ thereafter as $\pi_{s\to t}$. We will prove by induction on $t$ that

The base case is satisfied by definition, since $\pi_{s\to 0}\equiv{\pi_{b}}$.

Suppose that at some time $t$, Equation 16 is satisfied.

This completes the proof by induction. Since the game length is bounded by $T$, $V_{\pi_{s\to T}}\equiv V_{\pi_{s}}$ and the proof is complete.