Faster sorting algorithms discovered using deep reinforcement learning
Daniel J. Mankowitz, Andrea Michi, Anton Zhernov et al. · Nature · 2023
Abstract Fundamental algorithms such as sorting or hashing are used trillions of times on any given day1. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past2, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library3. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach.
Cited by 175 works. doi:10.1038/s41586-023-06004-9 Open-access PDF
Authors
- Daniel J. Mankowitz
- Andrea Michi
- Anton Zhernov
- Marco Gelmi
- Marco Selvi
- Cosmin Păduraru
- Edouard Leurent
- Shariq Iqbal
- Jean-Baptiste Lespiau
- Alex Ahern
- Thomas Köppe
- Kevin Millikin
- Sophie Elster
- Jackson Broshear
- Chris Gamble
- Kieran Milan
- Robert Tung
- Minjae Hwang
- Ali Taylan Cemgil
References
- Mastering the game of Go with deep neural networks and tree search
- Collision Free Hash Functions and Public Key Signature Schemes
- A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
- XXII. Programming a computer for playing chess
- Competition-level code generation with AlphaCode
- Mastering Atari, Go, chess and shogi by planning with a learned model
- Language to Logical Form with Neural Attention
- Mastering Atari, Go, chess and shogi by planning with a learned model
- Applied Mechanics and Materials Vol. 906
- Syntax-guided synthesis