Abstract
A generally intelligent agent must be able to teach itself how to solveproblems in complex domains with minimal human supervision. Recently, deepreinforcement learning algorithms combined with self-play have achievedsuperhuman proficiency in Go, Chess, and Shogi without human data or domainknowledge. In these environments, a reward is always received at the end of thegame, however, for many combinatorial optimization environments, rewards aresparse and episodes are not guaranteed to terminate. We introduce AutodidacticIteration: a novel reinforcement learning algorithm that is able to teachitself how to solve the Rubik's Cube with no human assistance. Our algorithm isable to solve 100% of randomly scrambled cubes while achieving a median solvelength of 30 moves -- less than or equal to solvers that employ human domainknowledge.