AlphaDev：通过深度强化学习发现更快的排序算法.
本文提出了AlphaDev，这是一种使用强化学习来发现增强的计算机科学算法。AlphaDev建立在AlphaZero的基础上，发现了一种更快的排序算法，并将其开源在主C++库中，这是十多年来对排序库这一部分的首次更改。
AlphaDev并不是直接改进现有算法，而是从计算机的汇编指令(assembly instruction)出发进行优化。汇编指令用于创建二进制代码，供计算机执行。C++等高级语言必须通过编译器(compiler)翻译为汇编指令才能被计算机理解，汇编器(assembler)进一步将汇编指令转换为计算机可以运行的可执行机器代码。
在汇编指令这个较低级别上计算机存储和操作更加灵活，这意味着有更多潜在的改进，而在更高级别的编码语言中可能很难发现这些改进，这些改进可能会对速度和能源使用产生更大的影响。
AlphaDev把排序算法转换为单人的汇编游戏(assembly game)。在每一轮中，AlphaDev接收系统状态$s_t$作为输入，观察它已经生成的算法和CPU中包含的信息；然后通过选择一条指令添加到算法中来进行移动。每次移动后，生成的算法都会被输入一个测试输入序列，并生成一个输出序列，并与排序序列的预期输出进行比较。基于算法的正确性和延迟来给与奖励。
AlphaDev专注于改进包含三到五个元素的较短序列的排序算法。这些算法是使用最广泛的算法之一，因为它们经常作为较大排序函数的一部分被多次调用。为了让新的排序算法更容易被使用，通过逆向工程把发现的结果翻译成C++语言，并改进了LLVM libc++排序库，对于较短的序列，其速度提高了$70\%$；对于超过$250000$个元素的序列，速度提高了$1.7\%$。
AlphaDev发现的排序算法包含新的指令序列，每次应用它们时都会保存一条指令，称之为“交换和复制移动”（swap and copy moves）。通过交换和复制移动，AlphaDev跳过了一个步骤，以一种看似错误但实际上更快捷方式的方式连接元素。比如排序三个元素的汇编程序中，把$\min(A,B,C)$替换成了$\min(A,B)$：
