Title: STRUCTURED EXPLORATION VIA HIERARCHICAL VARIATIONAL POLICY NETWORKS

Abstract: 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.

1. INTRODUCTION:

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.

Figure 1 : Equivalent solutions in a 2-hunter 2prey game.

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 Figure 1 ). 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 (Agrawal & Goyal, 2012) ).

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.

2. COOPERATIVE MULTI-AGENT REINFORCEMENT LEARNING:

We use multi-agent environments to show the efficacy of our approach to structured exploration, as they naturally exhibit exponentially large state-action spaces. In this work we focus on efficiently learning a centralized policy: a joint policy model for all agents, in the full-information setting. More generally, multi-agent problems can be generalized along many dimensions, e.g. one can learn decentralized policies in partial-information settings. For an overview, see Busoniu et al. (2008) .

In multi-agent RL, agents sequentially interact within an environment defined by the tuple: E ≡ (S, A, r, f P ). Each agent i starts in an initial state s i 0 , and at each time t observes a state s t ∈ S and executes an action a i t chosen by a (stochastic) policy a i t ∼ P a i t |s t . Each agent then receives a reward r i (s t , a t ), and the environment transitions to a new state s t+1 with probability f P (s t+1 |s t , a t ). We define the joint state and actions as s t = {s i t ∈ S} and a t = {a i t ∈ A}, where i ∈ I indexes the agents. Note that the rewards for each agent r i can depend on the full joint state and actions.

In this work, we restrict to fully cooperative MDPs that are fully observable, deterministic and episodic. Each agent can see the full state s, f P is deterministic and each episode τ = (s t , a t ) 0≤t≤T ends when the agent encounters a terminal state and the MDP resets.

In the fully cooperative case, the goal for each agent is to learn its optimal policy P * a i t |s t , θ that maximizes the total reward R(τ

EQUATION

To optimize, we can apply gradient descent with policy gradient estimators ĝθ (Williams (1992))

EQUATION

Figure 2 : Structured latent variable model of the multi-agent policy (actor, left) and instance of the multi-agent actor-critic interacting in the environment E (right). The joint policy contains two stacked layers of stochastic latent variables (red), and deterministically receives states and computes actions (green). Global variables λ are shared across agents. On the right, a neural network instance of the actor-critic uses the reparametrization trick and receives the environment state, samples actions from the policy for all agents and computes value functions V • .

where we sample M rollouts τ k by sampling actions from the policy that is being learned.

A central issue in reinforcement learning is the exploration-exploitation trade-off: how can agents sample rollouts and learn efficiently? In particular, when the state-action space is exponentially large, discovering good (coordinated) policies when each agent samples independently becomes combinatorially intractable as N grows. Hence, exploration in large state-action spaces poses a significant challenge.

2.1. MACE: JOINT COORDINATION AND EXPLORATION:

We now formulate our multi-agent objective (1) using a hierarchical policy class that enables structured exploration. Our approach, MACE ("Multi-Agent Coordinated Exploration"), builds upon two complementary approaches:

• Encode structured exploration by sampling actions that are correlated between agents. The correlation between actions encodes coordination. • Use a variational approach to derive and optimize a lower bound on the objective (1).

Hierarchical Latent Model. To encode coordination between agents, we assume the individual policies have shared structure, encoded by a latent variable λ t ∈ R n for all t, where n is the dimension of the latent space. This leads to a hierarchical policy model P (a t , λ t |s t ), as shown in Figure 2 . We first write the joint policy for a single time-step as:

EQUATION

where we introduced the conditional priors P (λ t |s t ). The latent variables λ t introduce dependencies among the a t , hence this policy is more flexible compared to standard fully factorized policies (Ranganath et al. (2015) ). Note that this approach supports centralized learning and decentralized execution, by sharing a random seed amongst agents to sample λ t and actions a t during execution.

Computing the integral in the optimal policy (3) is hard, because the unknown distribution P (a i t |λ t , s t ) can be highly complex. Hence, to make learning (3) tractable, we will use a variational approach.

Hierarchical Variational Lower Bound. We next derive a tractable learning algorithm using variational methods. Instead of directly optimizing (1), we cast it as a probabilistic inference problem, as in Levine & Koltun (2013); Vlassis et al. (2009) , and instead 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 P (R|τ ) = R. We can then rewrite (1) as a maximum likelihood problem:

EQUATION

Hence, the RL objective is equivalent to a maximal likelihood problem:

EQUATION

In MACE we introduce a latent variable λ t in the probability of a rollout τ , using (3):

EQUATION

where computing the policy distribution P (a t , λ t |s t ; θ) is intractable, which makes the maximization in Equation ( 5) hard. Hence, we derive a lower bound on the log-likelihood log P (R|τ )P (τ ; θ) in Equation ( 5), using a variational approach. Specifically, we use an approximate factorized variational distribution Q R that is weighted by the total reward R:

EQUATION

where φ are the parameters for the variational distribution Q R . Using Jensen's inequality (Hoffman et al., 2013) and ( 3) to factorize P (a t , λ t |s t ; θ), we can derive:

EQUATION

where the right-hand side is called the evidence lower bound (ELBO), which we can maximize as a proxy for (4). For more details on the derivation, see the Appendix.

The standard choice for the prior P (λ t |s t ) is to use maximum-entropy standard-normal priors: P (λ t |s t ) = N (0, 1). We can then optimize (8) using e.g. stochastic gradient ascent. Formally, the MACE policy gradient is:

EQUATION

which is an approximation of the true policy gradient (2). This gradient can be estimated using sampled roll-outs τ k of the policy P π :

EQUATION

During a rollout τ k , we sample λ ∼ Q, observe rewards R ∼ P (R|τ ) and transitions s t+1 ∼ P (s t+1 |.), and use these to compute (10). We can similarly compute

g φ,Q = ∇ φ ELBO(Q R , θ, φ),

the gradient for the variational posterior Q R .

Actor-Critic and Bias-Variance. Estimating policy gradients g θ using empirical rewards can suffer from high variance and instabilities. It is thus useful to consider more general objectives F i :

EQUATION

such that the variance in ĝ is reduced. 1 In practice, we find that using (10) with more general F , such as generalized advantages (Schulman et al. (2015) ), performs quite well.

3. EXPERIMENTAL VALIDATION:



3.1. MULTI-AGENT ENVIRONMENTS:

To validate our approach, we created two grid-world games, depicted in Figure 2 , inspired by the classic Predator-Prey and Stag-Hunt games (Shoham & Leyton-Brown (2008) ). In both games, the world is periodic and the initial positions of the hunters and prey are randomized. Also, we consider two instances for both games: either the prey are moving or fixed.

Hare-Hunters. Predator-Prey is a classic test environment for multi-agent learning, where 4 predators try to capture a prey by boxing it in. We consider a variation defined by the settings (N, M, H, T ): N hunters and M prey. Each prey can be captured by exactly H hunters: to capture the prey, a hunter gets next to it, after which the hunter is frozen. Once a prey has had H hunters next to it, it is frozen and cannot be captured by another hunter. The terminal rewards used are:

R i = 1, if all prey are captured H times before the time limit T 0, otherwise

The challenge of the game is for the agents to inactivate all prey within a finite time T . Due to the time limit, the optimal strategy is for the agents to distribute targets efficiently, which can be challenging due to the combinatorially large number of possible hunter-to-prey assignments.

Stag-Hunters. The Stag-Hunt is another classic multi-agent game designed to study coordination. In this game, hunters have a choice: either they capture a hare for low reward, or, together with another hunter, capture a stag for a high reward. We extend this to the multi-agent (N, M, H, T )-setting:

N hunters hunt M prey (M/2 stags and M/2 hares). Each stag has H hit-points, while hares and hunters have 1 hit-point. Capturing is as in Hare-Hunters. The spatial domain is similar to the Hare-Hunters game and we also use a time limit T . The terminal reward is now defined as:

R i =    1,

if i captured a live stag that became inactive before the time limit T 0.1, if i captured a live hare before the time limit T 0, otherwise

The challenge for the agents here is to discover that choosing to capture the same prey can yield substantially higher reward, but this requires coordinating with another hunter.

3.2. NEURAL COORDINATION MODEL:

For experiments, we instantiated our multi-agent policy class (as in Figure 2 ) with deep neural networks. For simplicity, we only used reactive policies without memory, although it is straightforward to apply MACE to policies with memory (e.g. LSTMs). The model takes a joint state s t as input and computes features φ(s) using a 2-layer convolutional neural network. To compute the latent variable λ ∈ R d , we use the reparametrization trick (Kingma & Welling, 2013) to learn the variational distribution (e.g. Q(λ|s)), sampling λ via ∼ N (0, 1) and distribution parameters µ, σ (omitting t):

EQUATION

)

Given λ, the model then computes the policies P (a i |λ, s) and value functions V i (s) as (omitting t):

EQUATION

where softmax(x) = exp x/ j exp x j . In this way, the model can be trained end-to-end.

Training. We used A3C (Mnih et al. (2016) ) with KL-controlled policy gradients (10), generalized advantage as F (Schulman et al. (2015) ). and policy-entropy regularization. For all experiments, we performed a hyper-parameter search and report the best 5 runs seen (see the Appendix for details).

Baselines. We compared MACE against two natural baselines:

• Shared (shared actor-critic): agents share a deterministic hidden layer, but maintain individual weights θ i for their (stochastic) policy P (a|λ, s; θ i ) and value function V i (s; θ).

The key difference is that this model does not sample from the shared hidden layer.

• Cloned (actor-critic): a model where each agent uses an identical policy and value function with shared weights. There is shared information between the agents, and actions are sampled according to the agents' own policies. or 20-vs-20 agents; randomly moving or fixed preys. Average, minimal and maximal rewards for the best 5 runs for each model are shown. MACE accumulates increasingly higher rewards compared to the baselines, by 1) achieving higher terminal reward per episode and 2) finishing episodes faster (see Figure 4 ). For 10-10 Stag-Hunters with frozen prey, average reward per-episode is 4.64 (Cloned), 6.22 (Shared), 6.61 (MACE) after 1 million samples. For more, see the Appendix.

w Figure 4 : Train-time episode lengths during 1 million steps for 10-vs-10 Hare-Hunters (left) and Stag-Hunters (right), with fixed preys. MACE (orange) finishes an episode successfully before the time limit more often than the baselines (Cloned (blue) and Shared (yellow)).

4. QUANTITATIVE ANALYSIS:

Above, we defined a variational approach to train hierarchical multi-agent policies using structured exploration. We now validate the efficacy of our approach by showing our method scales to environments with a large number of agents. We ran experiments for both Hare-Hunters and Stag-Hunters for N = M = 10, 20 in a spatial domain of 50 × 50 grid cells.

Sample complexity.:

In Table 1 we show the achieved rewards after a fixed number of training samples, and Figure 3 showcases the corresponding learning curves. We see that MACE achieves up to 10× reward compared to the baselines. Figure 4 shows the corresponding distribution of training episode lengths. We see that MACE solves game instances more than 20% faster than baselines in 50% (10%) of Hare-Hunters (Stag-Hunters) episodes. In particular, MACE learns to coordinate for higher reward more often: it achieves the highest average reward per-episode (e.g. for 10-10 Stag-Hunters with frozen prey, average rewards are 4.64 (Cloned), 6.22 (Shared), 6.61 (MACE)). Hence, MACE coordinates successfully more often to capture the stags. Together, these results show MACE enables more efficient learning.

Using the ELBO. A salient difference between (10) and ( 2) is the KL-regularization, which stems from the derivation of the ELBO. Since we use a more general objective F , c.f. ( 11), we also investigated the impact of using the KL-regularized policy gradient (10) versus the standard (2). To Arrows show where agents move to in the next frame. Top: at the start, predators explore via λ, but do not succeed before the time limit T (red dot). Bottom: after convergence agents succeed consistently (green dot) before the time limit (purple dot) and λ encodes the two strategies from Figure 1 . Highlighted λ-components correlate with rollout under a 2-sided t-test at α = 0.1 significance.

this end, we ran several instances of the above experiments both with and without KL-regularization. We found that without KL-regularization, training is unstable and prone to mode collapse: the variance σ of the variational distribution can go to 0. This reflects in essentially 0 achieved reward: the model does not solve the game for any reasonable hyperparameter settings.

Impact of dynamics and T . Inspecting training performance, we see the relative difficulty of capturing moving or randomly moving prey. Capturing moving prey is easier to learn than capturing fixed preys, as comparing rewards in Table 1 shows. This shows a feature of the game dynamics: the expected distance between a hunter and an uncaptured prey are lower when the preys are randomly moving, resulting in an easier game. Comparing Hare-Hunters and Stag-Hunters, we also see the impact of the time limit T . Since we use terminal rewards only, as T gets larger, the reward becomes very sparse and models need more samples to discover good policies.

5. MODEL INSPECTION:

Beyond training benefits, we now demonstrate empirical evidence that suggest efficacy and meaningfulness of our approach to structured exploration. We start by inspecting the behavior of the latent variable λ for a simple N = M = 2 Hare-Hunters game, which enables semantic inspection of the learned policies, as in Figure 5 . We make a number of observations. First, λ is relevant: many components are statistically significantly correlated with the agents' actions. This suggests the model Left: components of the latent code λ that significantly correlate with sampled actions (computed as in Figure 5 ). Right: Three episode snapshots: at the start, middle and end. Red: predators; green: prey. Arrows indicate where agents move to in the next snapshot. The hunters solve the game (green dot) before the time limit T = 1000 (purple dot), by distributing targets amongst themselves.

does indeed use the latent λ: it (partly) controls the coordination between agents.2 Second, the latent λ shows strong correlation during all phases of training. This suggests that the model indeed is performing a form of structured exploration. Third, the components of λ are correlated with semantic meaningful behavior. We show a salient example in the bottom 2 rows in Figure 5 : the correlated components of λ are disjoint and each component correlates with both agents. The executed policies are exactly the two equivalent ways to assign 2 hunters to 2 preys, as illustrated in Figure 1 .

Coordination with a large N . In the large N = M = 10 case, the dynamics of the agent collective are a generalization of the N = M = 2 case. There are now redundancies in multi-agent hunter-prey assignments that are analogous to the N = M = 2 case that are prohibitively complex to analyze due to combinatorial complexity. However our experiments strongly suggest (see e.g. Figure 6 ) the latent code is again correlated with the agents' behavior during all phases of training, showing that λ induces meaningful multi-agent coordination.

6. RELATED WORK:

Deep Structured Inference. Recent works have focused on learning structured representations using expressive distributions, which enable more powerful probabilistic inference. For instance, Johnson et al. (2016) has proposed combining neural networks with graphical models, while Ranganath et al. (2015) learn hierarchical latent distributions. Our work builds upon these approaches to learn structured policies in the reinforcement learning setting. In the multi-agent setting, the RL problem has also been considered as an inference problem in e.g. (Liu et al., 2015; Wu et al., 2013; Liu et al., 2016) .

Variational methods in RL. Neumann (2011); Furmston & Barber (2010) discuss variational approaches for RL problems, but did not consider end-to-end trainable models. Levine & Koltun (2013) used variational methods for guided policy search. Houthooft et al. (2016) learned exploration policies via information gain using variational methods. However, these only consider 1 agent.

Coordination in RL. Multi-agent coordination has been studied in the RL community (e.g. Guestrin et al. (2002) ; Kapetanakis & Kudenko (2002) ; Chalkiadakis & Boutilier (2003) ), for instance, as a method to reduce the instability of multiple agents learning simultaneously using RL. The benefit of coordination was already demonstrated in simple multi-agent settings in e.g. Tan (1993) . The shared latent variable λ of our structured policy can also be interpreted as a learned correlation device (see Bernstein (2005) for an example in the decentralized setting), which can be used to e.g. break ties between alternatives or induce coordination between agents. More generally, they can be used to achieve correlated equilibria (Greenwald & Hall, 2003) , a more general solution concept than Nash equilibria. However, previous methods learned hand-crafted models and do not scale well to complex state spaces and many agents. In contrast, our method learns coordination end-to-end via on-policy methods, learns the multi-agent exploration policy and scales well to many agents via its simple hierarchical structure.

Communication Models. Recently, end-to-end learning of communication models has been studied for shared broadcast channels (Sukhbaatar et al. (2016) ), sequential communication (Peng et al. (2017) ), heuristic multi-agent exploration Usunier et al. (2016) and bit-channels (Foerster et al. (2016) ). These works show that non-trivial communication protocols can be learned through backpropagation or heuristic stabilization methods, but often do not scale well to a large number of agents. Our hierarchical approach is complementary, learns via variational methods, and can scale to large N .

Multi-task learning. Hierarchical models have been studied for multi-task learning, e.g. Daume III (2014) learns latent hierarchies via EM in a supervised learning setting. Instead, we study flexible end-to-end trainable latent hierarchies in the reinforcement learning setting.

7. DISCUSSION:

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 (Chen et al., 2016) We show details on how to derive a tractable learning method to the multi-agent reinforcement learning problem with a centralized controller:

EQUATION

Instead of directly optimizing ( 16), we cast it as a probabilistic inference problem, as in Levine & Koltun (2013) ; 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

EQUATION

We can then rewrite ( 16) as a maximum likelihood problem:

EQUATION

Hence, the RL objective is equivalent to a maximal likelihood problem: 

max θ E π

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 ( 19) 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 (Hoffman et al., 2013) :

EQUATION

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:

Q R (λ 0:T |τ ; φ) = P (R|τ )P (s 0 ) .

(32)

The right-hand side in Equation ( 32) 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.

8.2. TRAINING:

Training method. We used the A3C method with 5-20 threads for all our experiments. Each thread performed SGD with (??). The loss for the value function at each state s t is the standard L 2 -loss between the observed total rewards for each agent i and its value estimate:

EQUATION

)

In addition, in line with other work using actor-critic methods, we found that adding a small entropy regularization on the policy can sometimes positively influence performance, but this does not seem to be always required for our testbeds. The entropy regularization is: 

H(P ) = -

:

Note that if the total reward R is bounded, we can define R-weighted probabilities by shifting and normalizing R. In general, the derivation applies if F is similarly bounded.

This is parallel to the discussion inChen et al. (2016), which investigates the effectiveness of latent codes λ.

Figures and Tables:

Figure 3: Train-time cumulative terminal reward for N agents in (N, M, 1, T ) Hare-Hunters (upper, T = 2000) and Stag-Hunters (lower, T = 1000) on a 50 × 50 gridworld, for 10-vs-10or 20-vs-20 agents; randomly moving or fixed preys. Average, minimal and maximal rewards for the best 5 runs for each model are shown. MACE accumulates increasingly higher rewards compared to the baselines, by 1) achieving higher terminal reward per episode and 2) finishing episodes faster (see Figure4). For 10-10 Stag-Hunters with frozen prey, average reward per-episode is 4.64 (Cloned), 6.22 (Shared), 6.61 (MACE) after 1 million samples. For more, see the Appendix.

Figure 5: Predators (red) and prey (green) during training for 2v2 Hare-Hunters for 100 episodes.Arrows show where agents move to in the next frame. Top: at the start, predators explore via λ, but do not succeed before the time limit T (red dot). Bottom: after convergence agents succeed consistently (green dot) before the time limit (purple dot) and λ encodes the two strategies from Figure1. Highlighted λ-components correlate with rollout under a 2-sided t-test at α = 0.1 significance.

Figure 6: Visualization of MACE for a (10, 10, 1, 1000) Hare-Hunters game in a 30 × 30 world.Left: components of the latent code λ that significantly correlate with sampled actions (computed as in Figure5). Right: Three episode snapshots: at the start, middle and end. Red: predators; green: prey. Arrows indicate where agents move to in the next snapshot. The hunters solve the game (green dot) before the time limit T = 1000 (purple dot), by distributing targets amongst themselves.

Figure 7: Train-time cumulative terminal reward in (N, M, 1, 1000) Hare-Hunters (upper) and Stag-Hunters (lower) on a 50×50 gridworld, for 10-vs-10 or 20-vs-20 agents; randomly moving or fixed preys. Average, minimal and maximal rewards for the best 5 runs for each model are shown. MACE accumulates increasingly higher rewards compared to the baselines.

Total terminal reward (averaged over 5 best runs) for N agents for set # of training samples.

Table content: <table><tr><td>Preys are</td><td colspan="2">Frozen</td><td colspan="2">Moving</td><td colspan="2">Frozen</td><td colspan="2">Moving</td></tr><tr><td>Samples (x100k)</td><td>5</td><td>10</td><td>5</td><td>10</td><td>5</td><td>10</td><td>5</td><td>10</td></tr><tr><td>Hare-Hunters</td><td/><td colspan="2">10-vs-10</td><td/><td/><td colspan="2">20-vs-20</td><td/></tr><tr><td>Cloned</td><td>85.0</td><td>178.3</td><td>465.0</td><td>912.5</td><td>20.0</td><td>70.0</td><td>706.7</td><td>1401.7</td></tr><tr><td>Shared</td><td>65.0</td><td>155.0</td><td>457.5</td><td>923.8</td><td>65.0</td><td>105.0</td><td>491.4</td><td>962.9</td></tr><tr><td>MACE</td><td>240.0</td><td>580.0</td><td>662.7</td><td>1381.8</td><td>200.0</td><td>393.3</td><td>1260.0</td><td>2344.0</td></tr><tr><td>Stag-Hunters</td><td/><td colspan="2">10-vs-10</td><td/><td/><td colspan="2">20-vs-20</td><td/></tr><tr><td>Cloned</td><td colspan="8">1229.2 2482.9 2079.4 4171.2 3224.5 6219.9 5934.5 11429.2</td></tr><tr><td>Shared</td><td colspan="8">1214.5 2423.7 2005.7 4144.3 3150.7 6379.8 6344.4 12196.8</td></tr><tr><td>MACE</td><td colspan="8">1515.2 3047.3 2275.7 4610.7 3799.3 7158.1 6880.7 13358.6</td></tr></table>

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. Nikos Vlassis, Marc Toussaint, Georgios Kontes, and Savas Piperidis. Learning model-free robot control by a Monte Carlo EM algorithm. Autonomous Robots, 27(2):123-130, August 2009. ISSN 0929-5593, 1573-7527.

Table content: <table><tr><td>8.1 HIERARCHICAL VARIATIONAL LOWER BOUND.</td></tr><tr><td>Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement</td></tr><tr><td>learning. Machine learning, 8(3-4):229-256, 1992.</td></tr><tr><td>Feng Wu, Shlomo Zilberstein, and Nicholas R Jennings. Monte-carlo expectation maximization</td></tr><tr><td>for decentralized pomdps. In Proceedings of the Twenty-Third international joint conference on</td></tr><tr><td>Artificial Intelligence, pp. 397-403. AAAI Press, 2013.</td></tr></table>

t+1 |s t , a t )Q(λ t |s t ; φ). (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 ; φ) = dλ 0:T Q R (λ 0:T |τ ; φ) log (a t , λ t |s t ; θ) Q(λ t |s t , φ) (29) = dλ 0:T Q R (λ 0:T |τ ; φ) , λ t |s t ; θ) Q(λ t |s t , φ)(30)= dλ 0:T Q R (λ 0:T |τ ; φ) (a t |λ t , s t ; θ)P (λ t |s t ) Q(λ t |s t , φ)(31)= dλ 0:T Q R (λ 0:T |τ ; φ)

Table content: <table><tr><td/><td>T</td><td/></tr><tr><td/><td/><td>P (s (27)</td></tr><tr><td/><td>t=0</td><td/></tr><tr><td>We see that (26) simplifies to:</td><td/><td/></tr><tr><td>dλ 0:T Q R (λ 0:T |τ ; φ) log</td><td>P (R|τ )P (s 0 )</td><td>T t=0 P (28)</td></tr><tr><td colspan="2">T t=0 P T t=0 log P (a t T log P</td><td/></tr><tr><td>t=0</td><td/><td/></tr></table>

A3C additionally defines training minibatches in terms of a fixed number of environment steps L: a smaller L gives faster training with higher variance and a higher L vice versa.Hyperparameter search. For experiments, we performed a random search over hyperparameters: Search range of hyper-parameters.

Table content: <table><tr><td>(34)</td></tr></table>

Peer review (iclr2018):
 This paper proposes an approach to improve exploration in multiagent reinforcement learning by allowing the policies of the individual agents to be conditioned on an external coordination signal .lambda. In order to find such parametrized policies, the approach combines deep RL with a variational inference approach (ELBO optimization). The paper presents an empirical evaluation, which seems encouraging, but that is also somewhat difficult to interpret given the lack of comparison to other state-of-the-art methods. Overall, the paper seems interesting, but (in addition to the not completely convincing empirical evaluation), it has two main weaknesses: lack of clarity and grounding in related literature. =Issues with clarity= -"This problem has two equivalent solutions". This is not so clear; depending on the movement of the preys it might well be that the optimal solution will switch to the other prey in certain cases? -It is not clear what is really meant with the term "structured exploration". It just seems to mean *improved*? -It is not clear that the improvements are due to exploration; my feeling is that is is due to improved statistical strength on a more abstract state feature (which is learned), not unlike: Geramifard, Alborz, et al. "Online discovery of feature dependencies." Proceedings of the 28th International Conference on Machine Learning (ICML-11). 2011. However, there is no clear indication that there is an improved exploration policy. -The problem setting is not quite clear: The paper first introduces "multi-agent RL", which seems to correspond to a "stochastic game" (also "Markov game"), but then moves on to restrict to the "fully cooperative setting" (which would make it a "Multiagent MDP", Boutilier *96). It subsequently says it deals only with deterministic problems (which would reduce the problem further to a learning version of a multiagent classical planning problem), but in the experiments do consider stochastically moving preys. -The paper says the problem is fully observable, but fails to make explicit if this is *individually* fully observable, or jointly. I am assuming the former, but is it not clear how the agents observe this full state in the experimental evaluation. This is actually a crucial confusion, as it completely changes the interpretation of what the approach does: in the individually observable case, the approach is adding a redundant source of information which is more abstract and thus seems to facilitate faster learning. In the latter case, where agents would have individual observations, it is actually providing the agents with more information. As such, I would really encourage the authors to better define the task they are considering. E.g., by building on the taxonomies of problems that researchers have developed in the community focusing on decentralized POMDPs, such as: Goldman, Claudia V., and Shlomo Zilberstein. "Decentralized control of cooperative systems: Categorization and complexity analysis." (2004). -"Compared to the single-agent RL setting, multi-agent RL poses unique difficulties. A central issue is the exploration-exploitation trade-off" That now in particular happens to be a central issue in single agent RL too. -"Finding the true posteriors P (λ t |s t ) ∝ P (s t |λ t )P (λ t ) is intractable in general" The paper did not explain how this inference task is required to solve the RL problem. -In general, I found the technical description impossible to follow, even after carefully looking at the appending. For instance, (also) there the term P (λ |s ) is suddenly introduced without explaining what the term exactly is? Why is the term P(a|λ) not popping up here? That also needs to be optimized, right? I suppose .phi is the parameter vector of the variational approximation, but it is never really stated. The various shorthand notations introduced for clarity do not help at all, but only make the formulas very cryptic. -The main text is not readable since definitions, e.g., L(Q_r,.tehta,.phi), that are in the appendix are now missing. -It is not clear to me how the second term of (10) is now estimated? -"Shared (shared actor-critic): agents share a deterministic hidden layer," What kind of layer is this exactly? How does it relate to .lambda ? -"The key difference is that this model does not sample from the shared hidden layer" Why would sampling help? Given that we are dealing with a fully observable multiagent MDP, there is no inherent need to randomize at all? (there should be a optimal deterministic joint policy?) -"There is shared information between the agents" What information is referred to exactly? Also: It is not quite clear if for these domains cloned would be better than completely independent learners (without shared weights)? -I can*t seem to find anywhere what is the actual shape (or type? I am assuming a vector of reals) of the used .lambda. -in figure 5, rhs, what is being shown exactly? What do the colors mean? Why does there seem to be a .lambda *per* agent now? =Related work= I think the paper could/should be hugely improved in this respect. The idea of casting MARL as inference has also been considered by: Learning for Decentralized Control of Multiagent Systems in Large, Partially-Observable Stochastic Environments. M Liu, C Amato, EP Anesta, JD Griffith, JP How - AAAI, 2016 Stick-breaking policy learning in Dec-POMDPs M Liu, C Amato, X Liao, L Carin, JP How International Joint Conference on Artificial Intelligence (IJCAI) 2015 Wu, F.; Zilberstein, S.; and Jennings, N. R. 2013. Monte-carlo expectation maximization for decentralized POMDPs. In Proc. of the 23rd Int’l Joint Conf. on Artificial Intelligence (IJCAI- 13). I do not think that these explicitly make use of a mechanism to coordinate the policies, since they address to true Dec-POMDP setting where each agent only gets its own observations, but in the Dec-POMDP literature, there also is the notion of *correlation device*, which is an additional controller (say corresponding to a dummy agent), which of which the states can be observed by other agents and used to condition their actions on: Bernstein DS, Hansen EA, Zilberstein S. Bounded policy iteration for decentralized POMDPs. InProceedings of the nineteenth international joint conference on artificial intelligence (IJCAI) 2005 Jun 6 (pp. 52-57). (and clearly this could be directly included in the aforementioned learning approaches). This notion of a correlation device also highlights to potential relation to methods to learn/compute correlated equilibria. E.g.,: Greenwald A, Hall K, Serrano R. Correlated Q-learning. In ICML 2003 Aug 21 (Vol. 3, pp. 242-249). A different connection between MARL and inference can be found in: Zhang, Xinhua and Aberdeen, Douglas and Vishwanathan, S. V. N., "Conditional Random Fields for Multi-agent Reinforcement Learning", in (New York, NY, USA: ACM, 2007), pp. 1143--1150. The idea of doing something hierarchical of course makes sense, but also here there are a number of related papers: -putting "hierarchical multiagent" in google scholar finds works by Ghavamzadeh et al., Saira & Mahadevan, etc. -Victor Lesser has pursued coordination for better exploration with a number of students. I suppose that Guestrin et al.*s classical paper: Guestrin, Carlos, Michail Lagoudakis, and Ronald Parr. "Coordinated reinforcement learning." ICML. Vol. 2. 2002. would deserve a citation, and the MARL field is moving ahead fast, an explanation of the differences with COMA: Counterfactual Multi-Agent Policy Gradients J Foerster, G Farquhar, T Afouras, N Nardelli, S Whiteson AAAI 2018 is probably also warranted.