Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning
Learning how to act when there are many available actions in each state is a challenging task for Reinforcement Learning (RL) agents, especially when many of the actions are redundant or irrelevant. In such cases, it is sometimes easier to learn which actions not to take. In this work, we propose the Action-Elimination Deep Q-Network (AE-DQN) architecture that combines a Deep RL algorithm with an Action Elimination Network (AEN) that eliminates sub-optimal actions. The AEN is trained to predict invalid actions, supervised by an external elimination signal provided by the environment. Simulations demonstrate a considerable speedup and added robustness over vanilla DQN in text-based games with over a thousand discrete actions.
This paper addresses the issue of having a very large action space when solving a Reinforcement Learning (RL) problem. The authors propose the Action-Elimination Deep Q-Network (AE-DQN) which is a model that eliminates sub-optimal actions. The training process requires an external supervised signal to learn which actions should be eliminated given the current state. The authors validate their approach by conducting experiments on text-based games where the number of discrete actions is over a thousand. They show a considerable speedup and added robustness over vanilla DQN.  More precisely, in the model being proposed, the elimination signal is not used to simply shape the environment reward. Instead, it is decoupled from the MDP by using contextual multi-armed bandits. An Action Elimination Network learns a mapping from states to elimination signal, and given a state provides the subset of actions that should be used by the DQN (trained using standard Q-Learning). In addition, the authors show that their Action Elimination Q-Learning converges to find an optimal policy and a minimal valid action space in the contextual bandits setting.  Main contributions: 1) Action-Elimination Deep Q-Network (AE-DQN) which is a model that eliminates sub-optimal actions in very large actions space using an external action elimination signal. 2) Convergence proof of the proposed Action Elimination Q-learning. 3) State of the art results on the text-based game Zork1.  Pros: - A technique that deals with large action space is of great interest to the community; - Text-based games offer interesting challenges for RL algorithms (stochastic dynamics, delayed reward, long-term memory, language understanding) and have been little explored. - Overall, the paper is well written, and the authors communicate clearly the motivation and main ideas of the proposed method.  Cons: - Extracting an elimination signal from most environments is not trivial. To be fair, the authors do address this concern in their conclusion. - It is unclear how the elimination signal is obtained for Zork1. Usually, in text-based games, that signal comes in the form of text which would need to be understood first (maybe some sort of sentiment analysis model?). - It is unclear to me what is the target of the NLP CNN classification. How does one determine the actions' relevance in each state? Is it by using the elimination signal?  Minor issues: - I was not able to open the 'run_cpu' file in the anonymized code repo. From footnote #2, it seems the implementation of the elimination signal for Zork1 can be found there. I would still like to see it detailed in the paper (or at least in the Appendix). - The definition of the three action spaces is hard to follow. Maybe a table would be clearer if space allows it. - Figure 5(b)'s caption mentions 209 actions whereas in the text (Section 5.2) it says 215 actions. - It is unclear if the step penalty was used for the Open Zork domain? I would assume it isn't to make the results comparable to previous work. I would briefly mention it.  EDIT: In light of the authors' answers, I'm raising my rating.