arXiv (Cornell University) · 2015 · 289 citations · 15 references
Open access
ComputingComputer ScienceAlgorithmsMachine LearningRecommender SystemsAction RepresentationApproximation AlgorithmsLanguage ModelingPolicy LearningReinforcement LearningContinuous Space RepresentationEmbedding LearningHigh-dimensional State SpacesLinear ComplexityLogarithmic Space Complexity
Reinforcement learning in environments with large discrete action sets is critical for many real‑world problems, yet existing methods lack the ability to generalize over actions and achieve sub‑linear complexity, motivating the present work. The authors propose to embed actions in a continuous space using prior information to enable generalization. They combine this embedding with approximate nearest‑neighbor lookup, achieving logarithmic‑time complexity in the number of actions. The resulting approach enables reinforcement learning on previously intractable problems and is validated on tasks with up to one million actions.
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.
15
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver et al. · Nature · 2015 · 30K citations
Continuous control with deep reinforcement learning
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel et al. · arXiv (Cornell University) · 2015 · 5.4K citations · Full text
Computing, Computer Science, Physics +17
MuJoCo: A physics engine for model-based control
Emanuel Todorov, Tom Erez, Yuval Tassa · 2012 · 4.4K citations
Engineering, Mechanical Engineering, Robotics Engineering +17
Deterministic policy gradient algorithms
David Silver, Guy Lever, Nicolas Heess et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2014 · 1.7K citations · Full text