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.
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).