Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning

By Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel Jaymin Mankowitz, Shie Mannor. 2018

218 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Is Reinforcement Learning (Not) for Natural Language Processing?: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization (2022, methodology): “To address this issue, we introduce NLPO (Natural Language Policy Optimization), which is inspired by work on action elimination/invalid-action masking (Zahavy et al., 2018; Huang & Ontañón, 2020; Ammanabrolu & Hausknecht, 2020).”
Keep CALM and Explore: Language Models for Action Generation in Text-based Games (2020, background): “Even with small actions spaces (e.g. < 200 actions), approaches to filter inadmissible actions (Zahavy et al., 2018; Jain et al., 2019) led to faster learning convergence.”
Interactive Fiction Games: A Colossal Adventure (2019, methodology): “Following this approach, (Zahavy et al. 2018) employ this strategy with their action-elimination network, a”
Graph Constrained Reinforcement Learning for Natural Language Action Spaces (2020, methodology): “Zahavy et al. (2018) reduce the combinatorially-sized action space into a discrete form using a walkthrough of the game and introduce the Action Elimination DQN, which learns to eliminate actions unlikely to cause a world change.”
Situated Dialogue Learning through Procedural Environment Generation (2021, background): “Text-based Game Playing and Generation LSTM-DQN (Narasimhan et al., 2015) and Action Elimination DQN (Zahavy et al., 2018) both train agents to produce Q-value estimates that maximize long term expected reward.”
An empirical investigation of the challenges of real-world reinforcement learning (2020, background): “ing this challenge. Dulac-Arnold et al. (2015) present an approach based on generating a vector for a candidate action and then doing nearest neighbor search to ﬁnd the closest real action available. Zahavy et al. (2018) propose an Action Elimination Deep Q Network (AE-DQN) that uses a contextual ba”
Challenges of real-world reinforcement learning: definitions, benchmarks and analysis (2021, background): “| | Zahavy et al. (2018) propose an Action Elimination Deep Q Network (AE-DQN) that uses a contextual bandit to eliminate irrelevant actions.”
How to Motivate Your Dragon: Teaching Goal-Driven Agents to Speak and Act in Fantasy Worlds (2020, background): “This resulted in agents developed by works such as (Zahavy et al., 2018; Ammanabrolu and Hausknecht, 2020), aiming to learn to execute contextually relevant actions.”
Learning Dynamic Belief Graphs to Generalize on Text-Based Games (2020, background): “Various deep learning agents have been explored [29, 17, 14, 51, 20, 3, 52, 47].”
Interactive Fiction Game Playing as Multi-Paragraph Reading Comprehension with Reinforcement Learning (2020, methodology): “Action-Elimination Deep Q-Network (AE-DQN) [15] learns to eliminate invalid action for efﬁcient policy learning via utilizing expert demonstration data.”
Behavior Cloned Transformers are Neurosymbolic Reasoners (2022, background): “Because text games require interactive multistep reasoning, agents have most commonly been modelled using reinforcement learning (e.g. He et al., 2016; Zahavy et al., 2018; Yao et al., 2020), though overall performance on most environments remains low (see Jansen, 2022; Osborne et al.”
Aligning to Social Norms and Values in Interactive Narratives (2022, background): “, 2020); (2) scaling RL algorithms to handle combinatorial natural language state-action spaces (Zahavy et al., 2018; Yao et al., 2020; Ammanabrolu et al., 2021; Jang et al., 2021); and (3) giving agents commonsense priors to better reason about the world (Murugesan et al.”
What can I do here? A Theory of Affordances in Reinforcement Learning (2020, background): “A related family of approaches involves learning when to prune actions (Even-Dar et al., 2003; Sherstov & Stone, 2005; Rosman & Ramamoorthy, 2012; Zahavy et al., 2018) in order to cope with large action-spaces.”
A Closer Look at Invalid Action Masking in Policy Gradient Algorithms (2020, unknown): “In the ﬁeld of games with natural language, others propose to train an Action Elimination Network (AEN) (Zahavy et al. 2018) to reduce the action set.”
Reinforcement Learning for Language Models (2023, background): “Since then, there have also been follow-up papers that attempt to eliminate actions [21] or generate small candidate action sets [22] for more efficient and stable exploration.”
Algorithmic Improvements for Deep Reinforcement Learning applied to Interactive Fiction (2019, methodology): “Our second contribution extends the work of Zahavy et al. (2018) on action elimination.”