Google DeepMind recently published a new paper which describes how they used a reinforcement learning to discover faster sorting algorithms. A summary of the paper is here and the paper is here.
It appears the reinforcement learning model is trying to write list sorting functions in assembler which are correct and efficient. For example, Figures 3b and 3c in the paper show that the reinforcement learning model managed to find a list sorting algorithm which consists of only 16 assembler instructions, whereas the previously known (and human written) solution consisted of 17 assembler instructions.
My question is: How did the reinforcement model employed by the paper's authors manage to reduce the search space compared to a brute force "Superoptimisation" approach?
For a given line of code in the list sorting algorithm, I assume there are lots and lots of valid assembler instructions that the reinforcement learnign model could choose from. For simplicity and to be conservative, let's assume there are only 100 valid assembler instructions. Even in this case, for 16 lines of code (as is the solution found by DeepMind) there would be 100^16 possible list sorting algorithms. Each of these would consist of valid assembler instructions, but only a tiny proportion of them would return the correct result and only one of them is both correct and optimal. Due to the huge search space for 16 lines of code, a brute force search seems impractical.
My (very elementary) understanding of reinforcement learning is that the agent gets rewards for correct behaviour. But in this use case, is there any way to score some interim results, e.g. to score whether the first line of assembler written by reinforcement learning is any good, before moving on to writing the second line? I would have thought that only the entire function, i.e. the 16 lines of code, can be "graded" for correctness by the reinforcement learning model.
It would be great if someone could explain in very simple terms how the reinforcement learning model managed to identify early on which search paths to discard and which ones to pursue without exhausting the entire search space. Thanks!
