In recent years we have seen fast progress on a number of benchmark problems in AI, with modern methods achieving near or super human performance in Go, Poker and Dota. One common aspect of all of these challenges is that they are by design adversarial or, technically speaking, zero-sum. In contrast to these settings, success in the real world commonly requires humans to collaborate and communicate with others, in settings that are, at least partially, cooperative. In the last year, the card game Hanabi has been established as a new benchmark environment for AI to fill this gap. In particular, Hanabi is interesting to humans since it is entirely focused on theory of mind, i.e. the ability to effectively reason over the intentions, beliefs and point of view of other agents when observing their actions. Learning to be informative when observed by others is an interesting challenge for Reinforcement Learning (RL): Fundamentally, RL requires agents to explore in order to discover good policies. However, when done naively, this randomness will inherently make their actions less informative to others during training. We present a new deep multi-agent RL method, the Simplified Action Decoder (SAD), which resolves this contradiction exploiting the centralized training phase. During training SAD allows other agents to not only observe the (exploratory) action chosen, but agents instead also observe the greedy action of their team mates. By combining this simple intuition with an auxiliary task for state prediction and best practices for multi-agent learning, SAD establishes a new state of the art for 2-5 players on the self-play part of the Hanabi challenge. Humans are highly social creatures and spend vast amounts of time coordinating, collaborating and communicating with others. In contrast to these, at least partially, most progress on AI in games has been in zero-sum games where agents compete against each other, typically rendering communication futile. This includes examples such as Go 2018) , poker (Brown & Sandholm, 2017; Moravčík et al., 2017; Brown & Sandholm, 2019) and chess (Campbell et al., 2002) . This narrow focus is unfortunate, since communication and coordination require unique abilities. In order to enable smooth and efficient social interactions of groups of people, it is commonly required to reason over the intents, points of views and beliefs of other agents from observing their actions. For example, a driver can reasonably infer that if a truck in front of them is slowing down when approaching an intersection, then there is likely an obstacle ahead. Furthermore, humans are both able to interpret the actions of others and can act in a way that is informative when their actions are being observed by others, capabilities that are commonly called theory of Mind (ToM), . Importantly, in order to carry out this kind of reasoning, an agent needs to consider why a given action is taken and what this decision indicates about the state of the world. Simply observing what other agents are doing is not sufficient. While these abilities are particularly relevant in partially observable fully cooperative multi-agent settings, ToM reasoning clearly matters in a variety of real world scenarios. For example, autonomous cars will likely need to understand the point of view, intents and beliefs of other traffic participants in order to deal with highly interactive settings such as 4-way crossing or dense traffic in cities. Hanabi is a fully cooperative partially-observable card game that has recently been proposed as a new benchmark challenge problem for AI research (Bard et al., 2019) to fill the gap around ToM. In Hanabi, players need to find conventions that allow them to effectively exchange information from their local observations through their actions, taking advantage of the fact that actions are observed by all team mates. Most prior state-of-the-art agents for Hanabi were developed using handcrafted algorithms, which beat off-the-shelf deep multi-agent RL methods by a large margin. This makes intuitive sense: Beyond the "standard" multi-agent challenges of credit assignment, non-stationarity and joint exploration, learning an informative policy presents an additional fundamentally new conflict. On the one hand, an RL agent needs to explore in order to discover good policies through trial and error. On the other hand, when carried out naively, this exploration will add noise to the policy of the agent during the training process, making their actions strictly less informative to their team mates. One possible solution to this is to explore in the space of deterministic partial policies, rather than actions, and sample these policies from a distribution that conditions on a common knowledge Bayesian belief. This is successfully carried out in the Bayesian Action Decoder (BAD) , the only previous Deep RL method to achieve a state of the art in Hanabi. While this is a notable accomplishment, it comes at the cost of simplicity and generality. For a start, BAD requires an explicit common knowledge Bayesian belief to be tracked, which not only adds computational burden due to the required sampling steps, but also uses expert knowledge regarding the game dynamics. Furthermore, BAD, as presented, is trained using actor-critic methods which are sample inefficient and suffer from local optima. In order to get around this, BAD uses population based training, further increasing the number of samples required. Lastly, BAD's explicit reliance on common knowledge limits the generality of the method. In this paper we propose the Simplified Action Decoder (SAD), a method that achieves a similar goal to BAD, but addresses all of the issues mentioned above. At the core of SAD is a different approach towards resolving the conflict between exploration and being interpretable, which, like BAD, relies on the centralized training with decentralized control (CT/DC) regime. Under CT/DC information can be exchanged freely amongst all agents during centralized training, as long as the final policies are compatible with decentralized execution. The key insight is that, during training we do not have to chose between being informative, by taking greedy actions, and exploring, by taking random actions. To be informative, the greedy actions do not need to be executed by the environment, but only need to be observed by the team mates. Thus in SAD each agent takes two different actions at each time step: One greedy action, which is not presented to the environment but observed by the team mates at the next time step as an additional input, and the "standard" (exploratory) action that gets executed by the environment and is observed by the team mates as part of the environment dynamics. Importantly, during greedy execution the observed environment action can be used instead of centralized information for the additional input, since now the agent has stopped exploring. Furthermore, to ensure that these greedy actions and observations get decoded into a meaningful representation, we can optionally train an auxiliary task that predicts key hidden game properties from the action-observation trajectories. While we note that this idea is in principle compatible with any kind of model-free deep RL method with minimal modifications to the core algorithm, we use a distributed version of recurrent DQN in order to improve sample efficiency, account for partial observability and reduce the risk of local optima. We also train a joint-action Q-function that consists of the sum of per-agent Q-values to allow for off-policy learning in this multi-agent setting using Value Decomposition Networks (VDN) (Sunehag et al., 2017) . Using SAD we establish a new SOTA for 2-5 players in Hanabi, with a method that not only requires less expert knowledge and compute, but is also more general than previous approaches. In order to ensure that our results can be easily verified and extended, we also evaluate our method on a proof-of-principle matrix game and plan to open-source our training code and agents. Beyond enabling more research into the self-play aspect of Hanabi, we believe these resources will provide a much needed starting point for the ad-hoc teamwork part of the Hanabi challenge. In this paper we presented the Simplified Action Decoder (SAD), a novel deep multi-agent RL algorithm that allows agents to learn communication protocols in settings where no cheap-talk channel is available. On the challenging benchmark Hanabi our work substantially improves the SOTA for an RL method for all numbers of players. For two players SAD establishes a new high-score across any method. Furthermore we accomplish all of this with a method that is both simpler and requires less compute than previous advances. While these are encouraging steps, there is clearly more work to do. In particular, there remains a large performance gap between the numbers achieved by SAD and the known performance of hat-coding strategies (Wu, 2018) for 3-5 players. One possible reason is that SAD does not undertake any explicit exploration in the space of possible conventions. Another promising route for future work is to integrate search with RL, since this has produced SOTA results in a number of different domains including Poker, Go and backgammon. A NETWORK ARCHITECTURE AND HYPER-PAMAMETERS FOR HANABI Our Hanabi agent uses dueling network architecture (Wang et al., 2015) . The main body of the network consists of 1 fully connected layer of 512 units and 2 LSTM (Hochreiter & Schmidhuber, 1997) layers of 512 units, followed by two output heads for value and advantages respectively. The same network configuration is used across all Hanabi experiments. We take the default featurization of HLE and replace the card knowledge section with the V0-Belief proposed by . The maximum length of an episode is capped at 80 steps and the entire episode is stored in the replay buffer as one training sample. This avoids the "slate hidden states" problem as described in Kapturowski et al. (2019) so that we can simply initialize the hidden states of LSTM as zero during training. For exploration and experience prioritization, we follow the simple strategy as in Horgan et al. (2018) and Kapturowski et al. (2019) . Each actor executes an i -greedy policy where .., N − 1} but with a smaller = 0.1 and α = 7. For simplicity, all players of a game use the same epsilon. The per time-step priority δ t is the TD error and per episode priority is computed following δ e = η max t δ i + (1 − η)δ where η = 0.9. Priority exponent is set to 0.9 and importance sampling exponent is set to 0.6. We use n-step return (Sutton, 1988) and double Q-learning (van Hasselt et al., 2015) for target computation during training. The discount factor γ is set to 0.999. The network is updated using Adam optimizer (Kingma & Ba, 2014) with learning rate = 6.25 × 10 −5 and = 1.5 × 10 −5 . Trainer sends its network weights to all actors every 10 updates and target network is synchronized with online network every 2500 updates. These hyper-parameters are fixed across all experiments. In the baseline, we use Independent Q-Learning where each player estimates the Q value and selects action independently at each time-step. Note that all players need to operate on the observations in order to update their recurrent hidden states while only the current player has non-trivial legal moves and other players can only select 'pass'. Each player then writes its own version of the episode into the prioritized replay buffer and they are sampled independently during training. The prioritized replay buffer contains 2 17 (131072) episodes. We warm up the replay buffer with 10,000 episodes before training starts. Batch size during training is 128 for games of different numbers of players. As mentioned in Section 4, the SAD agent is built on top of joint Q-function where the Q value is the sum of the individual Q value of all players given their own actions. One episode produces only one training sample with an extra dimension for the number of players. The replay buffer size is reduced to 2 16 for 2-player and 3-player games and 2 15 for 4-player and 5-player games. The batch sizes for 2-, 3-, 4-, 5-players are 64, 43, 32, 26 respectively to account for the fact that each sample contains more data. Auxiliary task can be added to the agent to help it decode the greedy action more effectively. In Hanabi, the natural choice is the predict the card of player's own hand. In our experiments, the auxiliary task is to predict the status of a card, which can be playable, discardable, or unknown. The loss is the average cross entropy loss per card and is simply added to the TD-error of reinforcement learning during training. Figure 3 shows learning curves of different algorithms averaged over 13 seeds per algorithm per player setting. Shading is error of the mean.
We develop Simplified Action Decoder, a simple MARL algorithm that beats previous SOTA on Hanabi by a big margin across 2- to 5-player games.
{"src": "scitldr-AIC_train", "paper_id": "B1xm3RVtwB"}