Sorting algorithm is one of the most popular foundation algorithms that are used trillions of times on almost every day. But like many algorithms, it has reached a stage whereby human are struggling to improve them further, especially when the demand for computation continue to grow.
In a new paper Faster sorting algorithms discovered using deep reinforcement learning, a DeepMind research team introduces AlphaDev, a deep reinforcement learning (DRL) agent which is capable to automatically discover correct and efficient sorting algorithms that achieves superior performance then previously known human benchmarks.
In this work, the team focus on two type of sorting algorithms: 1) the fixed sort and 2) the variable sort. They formulate the problem as a single-player game, which they refer as Assembly Game for an agent to discover new, efficient sorting algorithms. The challenge of this game is players need to consider combinatorial space of the given assembly instructions to search a provably correct and fast sorting algorithm.
To this end, the proposed AlphaDev consists of two core components: 1) A learning algorithm that incorporates both DRL and tochastic search optimization algorithms to play the Assembly Game; and 2) a representation function to capture the underlying structure of assembly programs.
More specifically, the AlphaDev representation networks consist of 1) a Transformer Encoder network that encodes one-hot program instructions to generate the corresponding algorithm embeddings; and 2) a CPU State Encoder network to receive the current state of memory and registers to generate memory/register embeddings. The final state representation is the combination of the generated algorithm embedding and memory/register embeddings. As a result, AlphaDev is able to represent complex algorithmic structures and predict how the algorithm affects the dynamics of memory and registers.
In their empirical study, the team trained the AlphaDev to discover novel fixed and variable sort algorithms from scratch, which are both correct while achieving state-of-the-art performance. And they also integrated the founded algorithms into the standard sort function in the LLVM standard C++ library, used by millions of developers and real-world applications.
Overall, this work showcases the potential of AlphaDev for automatically discovers state-of-the-art sorting algorithms. The team hopes their work can provide insights and encourage more new approaches in Artificial Intelligence and program
synthesis communities.
The paper Faster sorting algorithms discovered using deep reinforcement learning on Nature.
Author: Hecate He | Editor: Chain Zhang
We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.
A very interesting topic that I have been looking at, I think this is one of the most important information for me. And I’m glad to read your post. Thanks for sharing!