Faster sorting algorithms discovered using deep reinforcement learning

Fundamental algorithms such as sorting or hashing are used trillions of times on any given day. 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 past, 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 library. This represents a significant advancement in the development of a combinatorial algorithm that has been automatically optimized through the learning process, showcasing the generality of the approach. Human intuition and know-how have been crucial in improving algorithms. However, many algorithms have reached a stage whereby human experts have not been able to optimize them further, leading to an ever-growing performance bottleneck. The work in classical program synthesis literature, spanning many decades, aims to generalize existing programs and/or optimize programs to provide for latency. These include enumerative search techniques and stochastic search as well as the more recent trend of using deep learning in program synthesis for generating correct programs. Using deep reinforcement learning (DRL), we can take this a step further by generating correct and performant algorithms by optimizing for actual measures and latency at the CPU instruction level, by more efficiently searching and considering the space of correct and fast programs compared to previous work.

Daniel J. Mankowitz, Andrea Michi, Anton Zhernnov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Laurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Minjae Hwang, Taylan Cemgil, Mohammadinam Barekatain, Yuji Li, Amol Mandhane, Thomas Hubert, Julian Schriftweiser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals, David Silver