Methods, systems, and apparatus, including computer programs encoded on computer storage media, for training a neural network using a priority queue. One of the methods includes maintaining data identifying a set of K output sequences that were previously generated; selecting at least one of the output sequences from the set of output sequences; for each selected output sequence, determining a respective score; determining, for each selected sequence, a respective first update to the current values of the controller parameters; generating a batch of new output sequences using the controller neural network; obtaining a respective reward for each of the new output sequences; determining, from the new output sequences and the output sequences in the maintained data, the K output sequences that have the highest rewards; and modifying the maintained data.