SOLVING THE RUBIK'S CUBE WITH APPROXIMATE POLICY ITERATION
Recently, Approximate Policy Iteration (API) algorithms have achieved superhuman proficiency in two-player zero-sum games such as Go, Chess, and Shogi without human data. These API algorithms iterate between two policies: a slow policy (tree search), and a fast policy (a neural network). In these two-player games, a reward is always received at the end of the game. However, the Rubik's Cube has only a single solved state, and episodes are not guaranteed to terminate. This poses a major problem for these API algorithms since they rely on the reward received at the end of the game. We introduce Autodidactic Iteration: an API algorithm that overcomes the problem of sparse rewards by training on a distribution of states that allows the reward to propagate from the goal state to states farther away. Autodidactic Iteration is able to learn how to solve the Rubik's Cube without relying on human data. Our algorithm is able to solve 100% of randomly scrambled cubes while achieving a median solve length of 30 moves -less than or equal to solvers that employ human domain knowledge.
This paper introduces a deep RL algorithm to solve the Rubik's cube. The particularity of this algorithm is to handle the huge state space and very sparse reward of the Rubik's cube. To do so, a) it ensures each training batch contains states close to the reward by scrambling the solution; b) it computes an approximate value and policy for that state using the current model and c) it weights data points based by the inverse of the number of random moves from the solution used to generate that training point. The resulting model is compared to two non-ML algorithms and shown to be competitive either on computational speed or on the quality of the solution.  
This paper is well written and clear. To the best of my knowledge, this is the first RL-based approach to handle the Rubik's cube problem so well. The specificities of this problem make it interesting. While the idea of starting from the solution seemed straightforward at first, the paper describes more advanced tricks claimed to be necessary to make the algorithm work. The algorithm seems to be quite successful and competitive with expert algorithms, which I find very nice. Overall, I found the proposed approach interesting and sparsity of reward is an important problem so I would rather be in favor of accepting this paper. 
On the negative side, I am slightly disappointed that the paper does not link to a repository with the code. Is this something the authors are considering in the future? While it does not seem difficult to code, it is still nice to have the experimental setup.
There has been (unsuccessful) attempts to solve the Rubik's cube using deep RL before. I found some of them here: https://github.com/jasonrute/puzzle_cube . I am not sure whether these can be considered prior art as I could not find associated accepted papers but some are quite detailed. Some could also provide additional baselines for the proposed methods and highlight the challenges of the Rubik's cube.
I am also curious whether/how redundant positions are handled by the proposed approach and wished this would be discussed a bit. Considering the nature of the state space and the dynamics, I would have expected this to be a significant problem, unlike in Go or chess. Does the algorithm forbid the reverse of the last action? Is the learned value/policy function good enough that backwards moves are seldom explored? Since the paper mention that BFS is interesting to remove cycles, I assume identical states are not duplicated. Is this correct?