Deep Reinforcement Learning in Large Discrete Action Spaces

By Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy P. Lillicrap, Jonathan J. Hunt, Timothy A. Mann, Theophane Weber, Thomas Degris, Ben Coppin. 2015

640 citations recorded by the source corpus.

Being able to reason in an environment with a large number of discrete actions is essential to bringing reinforcement learning to a larger class of problems. Recommender systems, industrial plants and language models are only some of the many real-world tasks involving large numbers of discrete actions for which current methods are difficult or even often impossible to apply. An ability to generalize over the set of actions as well as sub-linear complexity relative to the size of the set are both necessary to handle such tasks. Current approaches are not able to provide both of these, which motivates the work in this paper. Our proposed approach leverages prior information about the actions to embed them in a continuous space upon which it can generalize. Additionally, approximate nearest-neighbor methods allow for logarithmic-time lookup complexity relative to the number of actions, which is necessary for time-wise tractable training. This combined approach allows reinforcement learning methods to be applied to large-scale learning problems previously intractable with current methods. We demonstrate our algorithm’s abilities on a series of tasks having up to one million actions.

Subfields: Artificial Intelligence

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

Citations in the corpus

Stratospheric Aerosol Injection as a Deep Reinforcement Learning Problem (2019, methodology): “This could either be achieved using low-dimensional embeddings (Dulac-Arnold, 2015) or, more robustly, by factorising the joint value function using techniques originally developed for cooperative multi-agent settings (Sunehag, 2018; Rashid, 2018).”
Challenges of Real-World Reinforcement Learning (2019, background): “These large state and action spaces can present serious issues for traditional RL algorithms, as identiﬁed in (Dulac-Arnold et al., 2015).”
Discrete Sequential Prediction of Continuous Actions for Deep RL (2017, methodology): “[11] Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin.”
Horizon: Facebook's Open Source Applied Reinforcement Learning Platform (2018, background): “One alternative is to combine policy gradients with a K-NN search (Dulac-Arnold et al., 2015), but when the number of available actions for any given state is sufﬁciently small, this approach is heavy-handed.”
Toybox: A Suite of Environments for Experimental Evaluation of Deep Reinforcement Learning (2019, background): “• Action Space Complexity Increasing the size of the action space can quickly lead to intractable computation for Q-value or policy function approximation, especially when that approximation is computationally expensive as in deep RL (Dulac-Arnold et al., 2015).”
I love your chain mail! Making knights smile in a fantasy game world: Open-domain goal-oriented dialogue agents (2019, methodology): “The Top-K model, related to (Dulac-Arnold et al., 2015), is another approach to keeping the number of trainable parameters small.”
Learning Action Representations for Reinforcement Learning (2019, methodology): “If additional information is known about the actions, as assumed in prior work (Dulac-Arnold et al., 2015), it can also be considered when initializing the action representations.”
Convergence of Edge Computing and Deep Learning: A Comprehensive Survey (2019, methodology): “In addition, Wolpertinger architecture [242] is utilized to cope with the challenge of large action space.”
A Closer Look at Invalid Action Masking in Policy Gradient Algorithms (2020, neutral): “Although a well-shaped action space could help the agent efficiently explore and learn a useful policy, action space shaping is shown to be potentially difficult to tune and some times detrimental in helping the agent solve the desired tasks [5].”
Graph Classification using Structural Attention (2018, background): “Using more complex node typing strategies [1] may, however, increase the number of node types substantially and one may have to look into reinforcement learning strategies that work well when the discrete action space is large [10].”
Hierarchical visuomotor control of humanoids (2018, methodology): “Our method was based on the Wolpertinger approach introduced in (Dulac-Arnold et al., 2015).”
Deep reinforcement learning for page-wise recommendations (2018, methodology): “Following [7], we build a simulated online environment (adapted to our case) for online test.”
Learning Action-Transferable Policy with Action Embedding (2019, positive): “In this paper, we adopt the architecture proposed by (Dulac-Arnold et al. 2015), in which the policy outputs over actions within a continuous space Rd and maps the output to discrete action space, since the output may not exist in discrete action space.”
Bao: Making Learned Query Optimization Practical (2020, background): “Since the size of the action space is an important factor for determining the convergence time of reinforcement learning algorithms [16], we opted for the smaller action space in hopes of achieving quick convergence.”
Strong mixed-integer programming formulations for trained neural networks (2018, methodology): “isesin deepreinforcementlearningproblemswith high dimensional action spaces and where any of the cost-to-go function, immediate cost, or the state transition functions are learned by a neural network [6,23,56,62,64,80]. More generally, this approach may be used to approximately optimize learned func”
Dynamics-aware Embeddings (2019, background): “Also related are methods which attempt to learn embeddings of single actions to enable efficient learning in very large action spaces (Dulac-Arnold et al., 2015; Chandak et al., 2019).”