Reinforcement learning in environments with large state-action spaces is challenging, as exploration can be highly inefficient. Even if the dynamics are simple, the optimal policy can be combinatorially hard to discover. In this work, we propose a hierarchical approach to structured exploration to improve the sample efficiency of on-policy exploration in large state-action spaces. The key idea is to model a stochastic policy as a hierarchical latent variable model, which can learn low-dimensional structure in the state-action space, and to define exploration by sampling from the low-dimensional latent space. This approach enables lower sample complexity, while preserving policy expressivity. In order to make learning tractable, we derive a joint learning and exploration strategy by combining hierarchical variational inference with actor-critic learning. The benefits of our learning approach are that 1) it is principled, 2) simple to implement, 3) easily scalable to settings with many actions and 4) easily composable with existing deep learning approaches. We demonstrate the effectiveness of our approach on learning a deep centralized multi-agent policy, as multi-agent environments naturally have an exponentially large state-action space. In this setting, the latent hierarchy implements a form of multi-agent coordination during exploration and execution (MACE). We demonstrate empirically that MACE can more efficiently learn optimal policies in challenging multi-agent games with a large number (~20) of agents, compared to conventional baselines. Moreover, we show that our hierarchical structure leads to meaningful agent coordination. Reinforcement learning in environments with large state-action spaces is challenging, as exploration can be highly inefficient in high-dimensional spaces. Hence, even if the environment dynamics are simple, the optimal policy can be combinatorially hard to discover. However, for many large-scale environments, the high-dimensional state-action space has (often hidden or implicit) low-dimensional structure which can be exploited. Many natural examples are in collaborative multi-agent problems, whose state-action space is exponentially large in the number of agents, but have a low-dimensional coordination structure. Consider a simple variant of the Hare-Hunters problem (see FIG0 . In this game, N = 2 identical hunters need to capture M = 2 identical static prey within T time-steps, and exactly H = 1 hunter is needed to capture each prey. T is set such that no hunter can capture both preys. There are two equivalent solutions: hunter 1 captures prey 1 and hunter 2 captures prey 2, or vice versa. There are also two suboptimal choices: both hunters choose the same prey. Hence, the hunters must coordinate over a (large) number of time-steps to maximize their reward. This implies the solution space has low-dimensional structure that can be used to accelerate training.In this work, we propose a principled approach to structured exploration to improve sample complexity in large state-action spaces, by learning deep hierarchical policies with a latent structure. As a highlevel intuition, consider a tabular multi-agent policy, which maps discrete (joint) states to action probabilities. For N agents with S states and A actions each, this policy has O((S · A) N ) weights. However, the low-dimensional coordination structure can be captured by a factorized, low-rank matrix, where the factorization can be learned and, for instance, only has O(N K(S + A)) weights. Similarly, our approach both 1) learns a low-dimensional factorization of the policy distribution and 2) defines exploration by also sampling from the low-dimensional latent space. For instance, in the multi-agent setting, we can learn a centralized multi-agent policy with a latent structure that encodes coordination between agents and biases exploration towards policies that encode "good" coordination.The key ideas of our approach are: 1) to utilize a shared stochastic latent variable model that defines the structured exploration policy, and 2) to employ a principled variational method to learn the posterior distribution over the latents jointly with the optimal policy. Our approach has several desirable properties. First we do not incorporate any form of prior domain knowledge, but rather discover the coordination structure purely from empirical experience during learning. Second, our variational learning method enables fully differentiable end-to-end training of the entire policy class. Finally, by utilizing a hierarchical policy class, our approach can easily scale to large action spaces (e.g. a large number of coordinating agents). Our approach can also be seen as a deep hierarchical generalization of Thompson sampling, which is a historically popular way to capture correlations between actions (e.g. in the bandit setting BID2 ).To summarize, our contributions in this work are as follows:• We introduce a structured probabilistic policy class that uses a hierarchy of stochastic latent variables.• We propose an efficient and principled algorithm using variational methods to train the policy end-to-end.• To validate our learning framework, we introduce several synthetic multi-agent environments that explicitly require team coordination, and feature competitive pressures that are characteristic of many coordinated decision problems.• We empirically verify that our approach improves sample complexity on coordination games with a large number (N ∼ 20) of agents.• We show that learned latent structures correlate with meaningful coordination patterns. In a sense, we studied the simplest setting that can benefit from structured exploration, in order to isolate the contribution of our work. Our hierarchical model and variational approach are a simple way to implement multi-agent coordination, and easily combine with existing actor-critic methods. Moving forward, there are many ways to expand on our work. Firstly, for complex (partial-information) environments, instead of using reactive policies with simple priors P ∼ N (0, 1), memoryfull policies with flexible priors ) may be needed. Secondly, our approach is complementary to richer forms of communication between agents. Our hierarchical structure can be interpreted as a broadcast channel, where agents are passive receivers of the message λ. Richer communication protocols could be encoded by policies with more complex inter-agent structure. It would be interesting to investigate how to learn these richer structures. We show details on how to derive a tractable learning method to the multi-agent reinforcement learning problem with a centralized controller: DISPLAYFORM0 Instead of directly optimizing (16), we cast it as a probabilistic inference problem, as in BID17 Vlassis et al. (2009) , and optimize a lower bound.To do so, we assume that the total reward R i for each i to be non-negative and bounded. Hence, we can view the total reward R(τ ) as a random variable, whose unnormalized distribution is defined as DISPLAYFORM1 We can then rewrite (16) as a maximum likelihood problem: DISPLAYFORM2 Hence, the RL objective is equivalent to a maximal likelihood problem: DISPLAYFORM3 where the probability of a rollout τ features a marginalization over the latent variables λ t : DISPLAYFORM4 DISPLAYFORM5 Here, we used the hierarchical decomposition for the policy: DISPLAYFORM6 DISPLAYFORM7 This policy distribution is intractable to learn exactly, as it involves margalization over λ t and an unknown flexible distribution P (a i t |λ t , s t ). Hence the maximization in Equation FORMULA17 is hard. Hence, we follow the variational approach and get a lower bound on the log-likelihood log P (R, τ ; θ) in Equation (19) . For this, we use an approximate variational distribution Q R (λ 0:T |τ ; φ) and Jensen's inequality BID12 : DISPLAYFORM8 DISPLAYFORM9 where in the last line we used (20) . By inspecting the quotient in (26), we see that the optimal Q R is a factorized distribution weighted by the total reward R: DISPLAYFORM10 P (s t+1 |s t , a t )Q(λ t |s t ; φ).We see that (26) simplifies to:dλ 0:T Q R (λ 0:T |τ ; φ) log P (R|τ )P (s 0 ) T t=0 P (s t+1 |s t , a t )P (a t , λ t |s t ; θ) P (R|τ )P (s 0 ) T t=0 P (s t+1 |s t , a t )Q(λ t |s t ; φ) (28) = dλ 0:T Q R (λ 0:T |τ ; φ) log T t=0 P (a t , λ t |s t ; θ) Q(λ t |s t , φ)= dλ 0:T Q R (λ 0:T |τ ; φ) T t=0 log P (a t , λ t |s t ; θ) Q(λ t |s t , φ)= dλ 0:T Q R (λ 0:T |τ ; φ) T t=0 log P (a t |λ t , s t ; θ)P (λ t |s t ) Q(λ t |s t , φ)= dλ 0:T Q R (λ 0:T |τ ; φ) DISPLAYFORM11 log P (a t |λ t , s t ; θ) + log P (λ t |s t ) Q(λ t |s t , φ)ELBO(Q R ,θ,φ).The right-hand side in Equation FORMULA30 is called the evidence lower bound (ELBO), which we can maximize as a proxy for (16). The standard choice is to use maximum-entropy standard-normal priors: P (λ t |s t ) = N (0, 1). We can then optimize (32) using e.g. stochastic gradient ascent.
Make deep reinforcement learning in large state-action spaces more efficient using structured exploration with deep hierarchical policies. A method to coordinate agent behaviour by using policies that have shared latent structure, a variational policy optimization method to optimize the coordinated policies, and a derivation of the authors' variational, hierarchical update. This paper suggests an algorithmic innovation consisting of hierarchical latent variables for coordinated exploration in multi-agent settings