Title: POLICY GRADIENT FOR MULTIDIMENSIONAL ACTION SPACES: ACTION SAMPLING AND ENTROPY BONUS Anonymous authors Paper under double-blind review

Abstract: In recent years deep reinforcement learning has been shown to be adept at solving sequential decision processes with high-dimensional state spaces such as in the Atari games. Many reinforcement learning problems, however, involve highdimensional discrete action spaces as well as high-dimensional state spaces. In this paper, we develop a novel policy gradient methodology for the case of large multidimensional discrete action spaces. We propose two approaches for creating parameterized policies: LSTM parameterization and a Modified MDP (MMDP) giving rise to Feed-Forward Network (FFN) parameterization. Both of these approaches provide expressive models to which backpropagation can be applied for training. We then consider entropy bonus, which is typically added to the reward function to enhance exploration. In the case of high-dimensional action spaces, calculating the entropy and the gradient of the entropy requires enumerating all the actions in the action space and running forward and backpropagation for each action, which may be computationally infeasible. We develop several novel unbiased estimators for the entropy bonus and its gradient. Finally, we test our algorithms on two environments: a multi-hunter multi-rabbit grid game and a multi-agent multi-arm bandit problem.

1. INTRODUCTION:

In recent years deep reinforcement learning has been shown to be adept at solving sequential decision processes with high-dimensional state spaces such as in the Go game (Silver et al. (2016) ) and Atari games (Mnih et al. (2013) , Mnih et al. (2015) , Mujika (2016) , O'Donoghue et al. (2016) , Parisotto et al. (2015) , Wang et al. (2016 ), Czarnecki et al. (2017) ). In all of these success stories, the size of the action space was relatively small. Many reinforcement learning problems, however, involve high-dimensional action spaces as well as high-dimensional state spaces. Examples include StarCraft (Vinyals et al. (2017) , Lin et al. (2017) ), where there are many agents each of which can take a finite number of actions; and coordinating self-driving cars at an intersection, where each car can take a finite set of actions (Sukhbaatar et al. (2016) ).

In this paper, we develop a novel policy gradient methodology for the case of large multidimensional action spaces. There are two major challenges in developing such a methodology:

• For large multidimensional action spaces, how can we design expressive and differentiable parameterized policies which can be efficiently sampled?

• In policy gradient, in order to encourage sufficient exploration, an entropy bonus term is typically added to the objective function. However, in the case of high-dimensional action spaces, calculating the entropy and its gradient requires enumerating all the actions in the action space and running forward and backpropagation for each action, which may be computationally infeasible. How can we efficiently approximate the entropy and its gradient while maintaining desirable exploration?

In this paper, we first propose two approaches for parameterizing the policy: a LSTM model and a Modified MDP (MMDP) giving rise to Feed-Forward Network (FFN) model. For both of these parameterizations, actions can be efficiently sampled from the policy distribution, and backpropagation can be employed for training. We then develop several novel unbiased estimators for the entropy bonus and its gradient. These estimators can be combined with stochastic gradient descent giving a new a class of policy gradient algorithms with desirable exploration. Finally, we test our algorithms on two environments: a multi-agent multi-arm bandit problem and a multi-agent hunter-rabbit grid game.

2. POLICY GRADIENT FOR MULTIDIMENSIONAL ACTION SPACES:

Consider an MDP with a d-dimensional action space

A = A 1 × A 2 × • • • × A d . Denote a = (a 1 , .

. . , a d ) for an action in A. A policy π(•|s) specifies for each state s a distribution over the action space A. In the standard RL setting, an agent interacts with an environment over a number of discrete timesteps (Sutton & Barto (1998) , Silver (2015) ). At timestep t, the agent is in state s t and samples an action a t from the policy distribution π(•|s t ). The agent then receives a scalar reward r t and the environment enters the next state s t+1 . The agent then samples a t+1 from π(•|s t+1 ) and so on. The process continues until the end of the episode, denoted by T . The return R t = T -t k=0 γ k r t+k is the discounted accumulated return from time step t until the end of the episode.

In the policy gradient formulation, we consider a set of parameterized policies π θ (•|s), θ ∈ Θ, and attempt to find a good θ within a parameter set Θ. Typically the policy π θ (•|s) is generated by a neural network with θ denoting the weights and biases in the network. The parameters θ are updated by performing stochastic gradient ascent on the expected reward. One example of such an algorithm is REINFORCE, proposed by Williams & Peng (1991) , where in a given episode at timestep t the parameters θ are updated as follows:

∆θ = α T t=0 ∇ θ log π θ (a t |s t )(R t -b t (s t ))

where b t (s t ) is a baseline. It is well known that the policy gradient algorithm often converges to a local optimum. To discourage convergence to a highly suboptimal policy, the policy entropy is typically added to the update rule:

EQUATION

where

EQUATION

This approach is often referred to as adding entropy bonus or entropy regularization (Williams & Peng (1991) ) and is widely used in different applications of neural networks, such as optimal control in Atari games (Mnih et al. (2016) ), multi-agent games (Lowe et al. (2017) ) and optimizer search for supervised machine learning with RL (Bello et al. (2017) ). β is referred to as the entropy weight.

In applying policy gradient to MDP with large multidimensional action spaces, there are two challenges. First, how do we design an expressive and differentiable parameterized policy which can be efficiently sampled? Second, for the case of large multidimensional action spaces, calculating the entropy and its gradient requires enumerating all the actions in the action space, which may be infeasible. How do we then enhance exploration in a principled way?

3. POLICY PARAMETERIZATION FOR EFFICIENT SAMPLING:

To abbreviate the notation, we write p θ (a) for π θ (a|s t ), with the conditioning on s t being implicit. We consider schemes whereby the sample components a i , i = 1, . . . , d, are sequentially generated.

In particular, after obtaining a 1 , a 2 , . . . , a i-1 , we will generate a i ∈ A i from some parameterized distribution p θ (•|a 1 , a 2 , . . . , a i-1 ) defined over the one-dimensional set A i . After generating the distribution p θ (•|a 1 , a 2 , . . . , a i-1 ), i = 1, . . . , d and the action components a 1 , . . . , a d sequentially, we can then define p θ (a) as p θ (a) = d i=1 p θ (a i |a 1 , a 2 , . . . , a i-1 ). We now propose two methods for creating the parameterized distributions p θ (a|a 1 , a 2 , . . . , a i-1 ), a ∈ A i . To our knowledge, these models are novel and have not been studied in multidimensional action space literature. We assume that the size of the one-dimensional action sets are equal, that is,

|A 1 | = |A 2 | = ... = |A d | = K.

To handle action sets of different sizes, we include inconsequential actions if needed.

3.1. USING RNNS TO GENERATE THE PARAMETERIZED POLICY:

The policy p θ (a) can be learned with a recurrent neural network (RNN). Long Short-Term Memory (LSTM), a special flavor of RNN, has recently been used with great success to represent conditional probabilities in language translation tasks (Sutskever et al. (2014) ). Here, as shown in Figure 1 (a), we use an LSTM to generate a parameterized multidimensional distribution p θ (•) and to sample a = (a 1 , . . . , a d ) from that distribution. Specifically, p θ (a|a 1 , a 2 , . . . , a i-1 ), a ∈ A i is given by the output of the LSTM. To generate a i , we run a forward pass through the LSTM with the input being a i-1 and the current state s t (and implicitly on a 1 , . . . , a i-1 which influences h i-1 ). This produces a hidden state h i , which is then passed through a linear layer, producing a K dimensional vector. The softmax of this vector is taken to produce the one-dimensional conditional distribution p θ (a|a 1 , a 2 , ..., a i-1 ), a ∈ A i . Finally, a i is sampled from this one-dimensional distribution, and is then fed into the next stage of the LSTM to produce a i+1 .

After generating the action a = (a 1 , . . . , a d ), and the conditional probabilities p θ (•|a 1 , a 2 , . . . , a i-1 ), i = 1, . . . , d, we can evaluate p θ (a) as the product of the conditional probabilities. During training, we can also use backpropagation to efficiently calculate the first term on the RHS of the update rule in (1).

3.2. USING MMDP TO GENERATE PARAMETERIZED POLICY:

As an alternative to using a LSTM to create parameterized multidimensional policies, we can modify the underlying MDP to create an equivalent MDP for which the action space is one dimensional at each time step. We refer to this MDP as the Modified MDP (MMDP). In the original MDP, we have state space S and action space

A = A 1 × A 2 × • • • × A d where A i = {1, 2, . . . , K}.

In MMDP, the state is modified to encapsulate the original state and all the action dimensions selected for state s so far, i.e., (s, a 1 , a 2 , . . . , a i , 0, . . . , 0) with a 1 , . . . , a i being selected values for action dimensions 1 to i, and 0 being the placeholder for d -i -1 dimensions. The new action space is A = {0, 1, . . . , K} and the new state space is S × {0, 1, . . . , K} d-1 . The state transition probabilities for the MMDP are given by P ((s, a 1 , 0, . . . , 0)|(s, 0, . . . , 0), a 1 ) = 1 P ((s, a 1 , a 2 , 0, . . . , 0)|(s, a 1 , 0, . . . , 0), a 2 ) = 1 . . .

P ((s, a 1 , . . . , a d-1 )|(s, a 1 , . . . , a d-2 , 0), a d-1 ) = 1 P ((s , 0, . . . , 0)|(s, a 1 , . . . , a d-1 ), a d ) = P (s |s, a 1 , . . . , a d )

where P (s |s, a 1 , . . . , a d ) is the transition probabiliy of the original MDP. The reward is only generated after all d component actions are taken. It is easily seen that the MMDP is equivalent to the original MDP.

Since the MMDP has an one-dimensional action space, we can use a feed-forward network (FFN) to generate each action component as shown in (Figure 1(b) ). Note that the FFN input layer size is always |S| + K -1 and the output layer size is K.

4. ENTROPY BONUS APPROXIMATION FOR LARGE ACTION SPACE:

As shown in (1), an entropy bonus is typically included to enhance exploration. However, for large multidimensional action spaces, calculating the entropy and the gradient of the entropy requires enumerating all the actions in the action space and running forward and backpropagation for each action. In this section we develop computationally efficient unbiased estimates for the entropy and its gradient.

Let A = (A 1 , . . . , A d ) denote a random variable with distribution p θ (•). Let H θ denote the exact entropy of the distribution p θ (a):

H θ = - a p θ (a) log p θ (a) = -E A∼p θ [log p θ (A)] = - d i=1 E A∼p θ [log p θ (A i |A i-1 )] RNN 0 s t Linear + Softmax a 1 a 1 h 1 RNN s t Linear + Softmax a 2 h 2 ... RNN a t s t h d Linear + Softmax a d (a)

The RNN architecture. To generate ai, we input st and ai-1 into the RNN and then pass the resulting hidden state hi through a linear layer and a softmax to generate a distribution, from which we sample ai.

FFN:

s t [0,...,0] length d Softmax a 1 FFN s t [0,...,0] length d -1 Softmax a 2 ... a3, a4 . . . a d-1 FFN s t Softmax a d (b)

The MMDP architecture. To generate ai, we input st and a1, a2, . . . , ai-1 into a FFN. The output is passed through a softmax layer, providing a distribution from which we sample ai. Since the input size of the FFN is fixed, when generating ai, constants 0 serve as placeholders for ai+1, . . . , a d-1 in the input to the FFN.

Figure 1 : The RNN and MMDP architectures for generating parameterized policies.

4.1. CRUDE UNBIASED ESTIMATOR:

During training within an episode, for each state s t , the policy (using, for example, LSTM or MMDP) generates an action a = (a 1 , a 2 , . . . , a d ). A crude approximation of the entropy bonus is:

H crude θ (a) = -log p θ (a) = - d i=1 log p θ (a i |a i-1 )

This approximation is an unbiased estimate of H θ but its variance is likely to be large. To reduce the variance, we can generate M action samples a (1) , a (2) , . . . , a (M ) when in s t and average the log action probabilities over the samples. However, generating a large number of samples is costly, especially when each sample is generated from a neural network, since each sample requires one additional forward pass.

4.2. SMOOTHED ESTIMATOR:

In this section, we develop an alternative unbiased estimator for entropy which only requires the one episodic sample. In the course of an episode, an action a = (a 1 , a 2 , . . . , a d ) is generated for each s t . The alternative estimator accounts for the entropy along each dimension of the action space.

H θ (a) := - d i=1 a∈Ai p θ (a|a i-1 ) log p θ (a|a i-1 ) = d i=1 H (i) θ (a i-1 )

where

H (i) θ (a i-1 ) := - a∈Ai p θ (a|a i-1 ) log p θ (a|a i-1 )

which is the entropy of A i conditioned on a i-1 . This approximation of entropy bonus is computationally efficient since for each dimension i, we need to obtain p θ (•|a i-1 ), its log and gradient anyway during training. We refer to this approximation as the smoothed entropy.

The smoothed entropy H θ (A) has several appealing properties. The proofs of Theorem 1 and Theorem 3 are straightforward and omitted.

Theorem 1. H θ (A) is an unbiased estimator of the exact entropy H θ .

Theorem 2. If p θ (a) has a multivariable normal distribution with mean and variance depending on θ, then:

H θ (a) = H θ ∀a ∈ A

Thus, the smoothed entropy equals the exact entropy for a multi-variate normal parameterization of the policy (Proof in Appendix B). Theorem 3. (i) If there is a sequence of weights θ 1 , θ 2 , . . . such that p θn (•) converges to the uniform distribution over A, then

sup θ H θ (a) = d log K (ii)

If there is a sequence of weights θ 1 , θ 2 , . . . such that p θn (a * ) → 1 for some a * , then

inf θ H θ (a) = 0

Thus, the smoothed entropy H θ (a) mimics the exact entropy in that it has the same supremum and infinum values as the exact entropy.

The above theorems indicate that H θ (a) may serve as a good proxy for H θ : it is an unbiased estimator for H θ , it has the same minimum and maximum values when varying θ; and in the special case when p θ (a) has a multivariate normal distribution, it is actually equal to H θ for all a ∈ A. Our numerical experiments have shown that the smoothed estimator H θ (a) typically has lower variance than the crude estimator H crude θ (a). However, it is not generally true that the smoothed estimator always has lower variance as counterexamples can be found.

4.3. GRADIENT OF ENTROPY:

So far we have been looking at estimates of entropy. But the policy gradient algorithm (1) uses the gradient of the entropy rather than just simply the entropy. As it turns out, the gradient of estimators H crude θ (a) and H θ (a) are not unbiased estimates of the gradient of the entropy. In this subsection, we provide unbiased estimators for the gradient of the entropy. For simplicity, in this section, we assume an one-step decision setting, such as in a multi-armed bandit problem. A straightforward calculation shows:

∇ θ H θ = E A∼p θ [-log p θ (A)∇ θ log p θ (A)]

(3) Suppose a is one sample from p θ (•). A crude unbiased estimator for the gradient of the entropy therefore is: -log p θ (a)∇ θ log p θ (a) = log p θ (a)∇ θ H crude θ (a). Note that this estimator is equal to the gradient of the crude estimator multiplied by a correction factor.

Analogous to the smoothed estimator for entropy, we can also derive a smoothed estimator for the gradient of the entropy. Theorem 4. If a is a sample from p θ (•), then

∇ θ H θ (a) + d i=1 H (i) θ (a i-1 )∇ θ i-1 j=1 log p θ (a j |a j-1 )

is an unbiased estimator for the gradient of the entropy (Proof in Appendix C).

Note that this estimate for the gradient of the entropy is equal to the gradient of the smoothed estimate H θ (a) plus a correction term. We refer to this estimate of the entropy gradient as the unbiased gradient estimate.

5. EXPERIMENTAL RESULTS:

We designed experiments to compare the LSTM and MMDP models, and to also compare how the different entropy approximations perform for both. For each entropy approximation, the entropy weight as described in (1) was tuned to give the highest episode reward. For MMDP, the number of hidden layers was also tuned from 1 to 7. The rest of the hyperparameters are listed in Appendix A.

5.1. HUNTERS AND RABBITS:

In this environment, there is a n × n grid. At the beginning of each episode d hunters and d rabbits are randomly placed in the grid. The rabbits remain fixed in the episode, and each hunter can move to a neighboring square (including diagonal neighbors) or stay at the current square. So each hunter has nine possible actions, and altogether there are |A| = 9 d actions at each time step. When a hunter enters a square with a rabbit, the hunter captures the rabbit and remains there until the end of the game. In each episode, the goal is for the hunters to capture the rabbits as quickly as possible. Each episode is allowed to run for at most 10,000 time steps.

To provide a dense reward signal, we formalize the goal with the following modification: capturing a rabbit gives a reward of 1, which is discounted by the number of time steps taken since the beginning of the episode. The discount factor is 0.8. The goal is to maximize the episode's total discounted reward. After a hunter captures a rabbit, they both become inactive. The representation of an active hunter or rabbit is (1, y position, x position). The representation of an inactive hunter or rabbit is (0, -1, -1).

Comparison of different entropy estimates for LSTM and MMDP:

Table 1 shows the performance of the LSTM and MMDP models with different entropy estimates. (smoothed mode entropy is explained in Appendix D). The evaluation was performed in a square grid of 5 by 5 with 5 hunters and 5 rabbits. Training was run for 1 million episodes for each of the seeds. All evaluations are averaged over 1,000 episodes per seed for a total of 5,000 episodes.

First, we observe that the LSTM model always does better than the MMDP model, particularly for the episode length. Second, we note that policies obtained with the entropy approximations all perform better than policies obtained without entropy or with crude entropy. For the LSTM model, the best performing approximation is smoothed entropy, reducing the mean episode length by 45% and increasing the mean episode reward by 10% compared to without entropy. We also note that there is not a significant difference in performance between the smoothed entropy estimate, smoothed mode estimate, and the unbiased gradient estimate. As shown in Table 2 , smoothed entropy is also more robust to the initial seed than without entropy. For example, for the LSTM model, in the case of without entropy, seed 0 leads to significantly worse results than the seeds 1-4. This does not happen to smoothed entropy.

Entropy approximations versus exact entropy:

We now consider how policies trained with entropy approximations compare with polices trained with exact entropy. In order to calculate exact entropy in an acceptable amount of time, we reduced the number of hunters and rabbits to 4 hunters and 4 rabbits. Training was run for 50,000 episodes. Table 3 shows the performance differences between policies trained with entropy approximations and exact entropy. We see that the best entropy approximations perform only slightly worse than exact entropy for both LSTM and MMDP. Once again we see that the LSTM model performs better than the MMDP model. 

5.2. MULTI-AGENT MULTI-ARM BANDITS:

We examine a multi-agent version of the standard multi-armed bandit problem, where there are d agents each pulling one of K arms, with d ≤ K. The k th arm generates a reward r k . The total reward in a round is generated as follows. In each round, each agent chooses an arm. All of the chosen arms are then pulled, with each pulled arm generating a reward. Note that the total number of arms chosen, c, may be less than d since some agents may choose the same arm. The total reward is the sum of rewards from the c chosen arms. The optimal policy is for the d agents to collectively pull the d arms with the highest rewards. Additionally, among all the optimal assignments of d agents to the d arms that yield the highest reward, we add a bonus reward with probability p * if one particular agent-to-arms assignment is chosen.

We performed experiments with 4 agents and 10 arms, with the k th arm providing a reward of k.

The exceptional assignment gets a bonus of 200 with probability 0.01, and no bonus with probability 0.99. Thus the maximum expected reward is 36. Training was run for 100,000 rounds for each of the seeds. Table 4 shows average results for the last 500 of the 100,000 rounds. The results for the multi-agent bandit problem are consistent with those for the hunter-rabbit problem. Policies obtained with the entropy approximations all perform better than policies obtained without entropy or with crude entropy, particularly for the percentage of optimal arms pulled. We again note that using the unbiased gradient estimate does not perform significantly better than using the smoothed entropy estimate.

6. RELATED WORK:

There has been limited attention in the RL literature with regards to large discrete action spaces. Pazis & Parr (2011) proposes generalized value functions in the form of H-value functions, and also propose approximate linear programming as a solution technique. Their methodology is not suited for deep RL, and approximate linear programming may lead to highly sub-optimal solutions. Dulac-Arnold et al. (2015) embeds discrete actions in a continuous space, picks actions in the continuous space and map these actions back into the discrete space. However, their algorithm introduces a new hyper-parameter that requires tuning for every new task. Our approach involves no new hyper-parameter other than those normally used in deep learning.

In Sukhbaatar et al. (2016) , each action dimension is treated as an agent and backpropagation is used to learn coordination between the agents. The approach is particularly adept for problems where agents leave and enter the system. However, the approach requires homogenous agents, and has not been shown to solve large-scale problems. Furthermore, the decentralized approach will potentially lead to highly suboptimal polices even though communication is optimized among the agents.

To our knowledge, we are the first to propose using LSTMs and a modified MDP to create policies for RL problems with large multidimensional action spaces. Although this leads to algorithms that are straightforward, the approaches are natural and well-suited to multidimensional action spaces.

We also propose novel estimators for the entropy regularization term that is often used in policy gradient. To the best of our knowledge, no prior work has dealt with approximating the policy entropy for MDP with large multidimensional discrete action space. On the other hand, there has been many attempts to devise methods to encourage beneficial exploration for policy gradient. Nachum et al. (2016) modifies the entropy term by adding weights to the log action probabilities, leading to a new optimization objective termed under-appreciated reward exploration.

While entropy regularization has been mostly used in algorithms that explicitly parameterize the policies, Schulman et al. (2017) applies entropy regularization to Q-learning methods. They make an important observation about the equivalence between policy gradient and entropy regularized Q-learning, which they term soft Q-learning.

7. CONCLUSION:

In this paper, we developed a novel policy gradient methodology for the case of large multidimensional discrete action spaces. We proposed two approaches for creating parameterized policies: LSTM parameterization and a Modified MDP (MMDP) giving rise to Feed-Forward Network (FFN) parameterization. Both of these approaches provide expressive models to which backpropagation can be applied for training. We then developed several novel unbiased estimators for entropy bonus and its gradient. We did experimental work for two environments with large multidimensional action space. For these environments, we found that both the LSTM and MMDP approach could successfully solve large multidimensional action space problems, with the LSTM approach generally performing better. We also found that the smoothed estimates of the entropy and the unbiased gradient estimate of the entropy gradient can help reduce computational cost while not sacrificing significant loss in performance.

Also note that for X ∼ N (µ, Σ), the entropy of X takes the form

H(X) = k 2 (log 2π + 1) + 1 2 |Σ|

where k is the dimension of X and | • | denotes the determinant. Therefore, the entropy of a multivariate normal random variable depends only on the variance and not on the mean.

Because A is multivariate normal, the distribution of A i given A 1 = a 1 , . . . , A i-1 = a i-1 has a normal distribution with a variance σ 2 i that does not depend on a 1 , . . . , a i-1 . Therefore

H θ (A i |a 1 , . . . , a i-1 ) = 1 2 (log 2π + 1 + σ 2 i )

does not depend on a 1 , . . . , a i-1 and hence H θ (a) does not depend on a. Combining this with the fact that H θ (a) is an unbiased estimator for H θ gives H θ (a) = H θ for all a ∈ A.

C PROOF OF THEOREM 4:

From (3), we have:

EQUATION

We will now use conditional expectation to calculate the terms in the double sum.

For i < j:

E A∼p θ [log p θ (A i |A i-1 )∇ θ log p θ (A j |A j-1 )|A j-1 ] = log p θ (A i |A i-1 )E A∼p θ [∇ θ log p θ (A j |A j-1 )|A j-1 ] = 0

For i > j:

E A∼p θ [log p θ (A i |A i-1 )∇ θ log p θ (A j |A j-1 )|A i-1 ] =∇ θ log p θ (A j |A j-1 )E A∼p θ [log p θ (A i |A i-1 )] = -∇ θ log p θ (A j |A j-1 )H (i) θ (A i-1 ) For i = j: E A∼p θ [log p θ (A i |A i-1 )∇ θ log p θ (A i |A i-1 )|A i-1 ] = -∇ θ H (i) θ (A i-1 )

Combining these three conditional expectations with (4), we obtain:

∇ θ H θ = E A∼p θ [∇ θ H θ (A) + d i=1 H (i) θ (A i-1 )∇ θ i-1 j=1 log p θ (A j |A j-1 )]

D APPROXIMATING ENTROPY USING THE MODE OF THE DISTRIBUTION:

Depending on the episodic action a at a given time step in the episode, the smoothed entropy H θ (a) may give unsatisfactory results. For example, suppose for a particular episodic action a, H θ (a)

H θ . In this case, the policy gradient may ignore the entropy bonus term, thinking that the policy already has enough entropy when it perhaps does not. We therefore consider alternative approximations which may improve performance at modest additional computational cost.

First consider Thus in this case, instead of calculating the entropy over a sample action a, we calculate it over the most likely action a * . The problem here is that it is not easy to find a * when the given conditional probabilities p θ (a|a 1 , . . . , a i-1 ) are not in closed form but only available algorithmically as outputs of neural networks.

E * = -

A more computationally efficient approach would be to choose the action greedily: â1 = argmax The action â is an approximation for the mode of the distribution p θ (•). As often done in NLP, we can use beam search to determine an action a that is a better approximation, that is, p θ (a ) ≥ p θ (â). Indeed, the above H θ definition is beam search with beam size equal to 1. We refer to H θ as smoothed mode entropy.

H θ with an appropriate beam size may be a better approximation for the entropy H θ than H θ (a). However, calculating H θ and its gradient comes with some computational cost. For example, with a beam size equal to one, we would have to make two passes through the neural network at each time step: one to obtain the episodic sample a and the other to obtain the greedy action â. For beam size n we would need to make n + 1 passes.

We note that H θ is a biased estimator for H θ but with no variance. Thus there is a bias-variance tradeoff between H θ (a) and H θ . Note that H θ also satisfies Theorems 2 and 3 in subsection 4.2.

:



Figures and Tables:

p θ (a|a * 1 , . . . , a * i-1 ) log p θ (a|a * 1 , . . . , a * i-1 ) where a * = (a * 1 , . . . , a * d ) = argmax a∈A p θ (a)

p θ (a|â 1 , . . . , âi-1 ) log p θ (a|â 1 , . . . , âi-1 )

Performance of LSTM and MMDP across different entropy approximations.

Table content: <table><tr><td>Without</td><td>Crude</td><td>Smoothed</td><td>Smoothed</td><td>Unbiased Gradient</td></tr><tr><td>Entropy</td><td>Entropy</td><td>Entropy</td><td>Mode Entropy</td><td>Estimate</td></tr><tr><td>LSTM Mean Episode Length 10.1 ± 1.9</td><td>19 ± 8.7</td><td>5.6 ± 0.2</td><td>6.0 ± 0.2</td><td>6.0 ± 0.1</td></tr><tr><td colspan="3">MMDP Mean Episode Length 21.5 ± 3.7 37.3 ± 29.6 10.6 ± 0.7</td><td>10.6 ± 0.7</td><td>9.8 ± 0.6</td></tr><tr><td>LSTM Mean Episode Reward 3.0 ± 0.06</td><td>3.0 ± 0.03</td><td>3.3 ± 0.04</td><td>3.2 ± 0.04</td><td>3.2 ± 0.02</td></tr><tr><td>MMDP Mean Episode Reward 2.8 ± 0.03</td><td>2.7 ± 0.03</td><td>2.9 ± 0.03</td><td>2.8 ± 0.04</td><td>2.9 ± 0.02</td></tr></table>

LSTM and MMDP results across seeds.

Table content: <table><tr><td/><td/><td/><td>Without</td><td/><td/><td/><td/><td>Crude</td><td/><td/><td/><td/><td>Smoothed</td><td/><td/></tr><tr><td/><td/><td/><td>Entropy</td><td/><td/><td/><td/><td>Entropy</td><td/><td/><td/><td/><td>Entropy</td><td/><td/></tr><tr><td>Seed</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td></tr><tr><td colspan="5">LSTM Mean Episode Length 14 9 11 9</td><td colspan="7">8 40 12 17 11 14 5</td><td>6</td><td>6</td><td>5</td><td>6</td></tr><tr><td colspan="16">MMDP Mean Episode Length 15 19 27 27 20 17 30 14 109 18 10 10 11 11 12</td></tr></table>

LSTM and MMDP results for entropy approximation versus exact entropy.

Table content: <table><tr><td/><td>LSTM</td><td>LSTM</td><td>MMDP Unbiased</td><td>MMDP</td></tr><tr><td/><td>Smoothed Entropy</td><td>Exact Entropy</td><td>Gradient Estimate</td><td>Exact Entropy</td></tr><tr><td>Mean Episode Length</td><td>9.0 ± 0.3</td><td>8.9 ± 0.2</td><td>11.5 ± 0.3</td><td>10.7 ± 0.4</td></tr><tr><td>Mean Episode Reward</td><td>2.14 ± 0.02</td><td>2.19 ± 0.02</td><td>2.01 ± 0.01</td><td>2.1 ± 0.01</td></tr></table>

Performance of LSTM policy parameterization.

Table content: <table><tr><td/><td>Without</td><td>Crude</td><td>Smoothed</td><td>Unbiased</td></tr><tr><td/><td>Entropy</td><td>Entropy</td><td>Entropy</td><td>Gradient Estimate</td></tr><tr><td>Mean Reward</td><td>34.9 ± 0.8</td><td colspan="2">35.5 ± 1.1 35.9 ± 0.8</td><td>35.9 ± 0.3</td></tr><tr><td colspan="4">Percentage Optimal Arms Pulled 39.8 ± 35.9 59.4 ± 35.7 95.0 ± 1.9</td><td>95.7 ± 2.7</td></tr></table>

Peer review (iclr2018):
 In this paper, the authors suggest introducing dependencies between actions in RL settings with multi-dimensional action spaces by way of two mechanisms (using an RNN and making partial action specification as part of the state); they then introduce entropy pseudo-rewards whose maximization corresponding to joint entropy maximization. In general, the multidimensional action methods either seem incremental or non novel to me. The combined use of the chain rule and RNNs (LSTM or not) to induce correlations in multi-dimensional outputs is well know (sequence-to-sequence networks, pixelRNN, etc.) and the extension to RL presents no difficulties, if it is not already known. Note very related work in https://arxiv.org/pdf/1607.07086.pdf and https://www.media.mit.edu/projects/improving-rnn-sequence-generation-with-rl/overview/ . As for the MMDP technique, I believe it is folklore (it can for instance be found as a problem in a problem set - http://stellar.mit.edu/S/course/2/sp04/2.997/courseMaterial/topics/topic2/readings/problemset4/problemset4.pdf). Note that both approaches could be combined; the first idea is essentially a policy method, the second, a value method. The second method could be used to provide stronger, partial action-conditional baselines (or even critics) to the first method. The entropy derivation are more interesting - and the smoothed entropy technique is as far as I know, novel. The experiments are well done, though on simple toy environments. Minor: - In section 3.2, one should in principle tweak the discount factor of the modified MDP to recover behavior identical to the original one with large action space. This should be noted (alternatively, the discount between non-environment transitions should be set to 1). - From the description at the end of 3.2, and figure 1.b, it seems actions fed to the MMDP feed-forward network are not one- hot; I thought this was pretty surprising as it would almost certainly affect performance? Note also that the collection of feed-forward network which collectively output the joint vector can be thought of as an RNN with non-learned state transition. - Since the function optimized can be written as an expectation of reward+pseudo-reward, the proof of theorem 4 can be simplified by using generic score-function optimization arguments (see Stochastic Computation Graphs, Schulman et al).