Learning Compositional Neural Programs with Recursive Tree Search and Planning
This work addresses the challenge of reducing supervision in program learning for AI systems, though it is incremental as it builds on existing NPI and AlphaZero methods.
The paper tackles the problem of training Neural Programmer-Interpreters (NPI) without strong supervision by proposing AlphaNPI, a reinforcement learning algorithm that combines NPI's structural biases with AlphaZero's search, resulting in effective training using only sparse rewards and achieving performance comparable to supervised variants in tasks like sorting.
We propose a novel reinforcement learning algorithm, AlphaNPI, that incorporates the strengths of Neural Programmer-Interpreters (NPI) and AlphaZero. NPI contributes structural biases in the form of modularity, hierarchy and recursion, which are helpful to reduce sample complexity, improve generalization and increase interpretability. AlphaZero contributes powerful neural network guided search algorithms, which we augment with recursion. AlphaNPI only assumes a hierarchical program specification with sparse rewards: 1 when the program execution satisfies the specification, and 0 otherwise. Using this specification, AlphaNPI is able to train NPI models effectively with RL for the first time, completely eliminating the need for strong supervision in the form of execution traces. The experiments show that AlphaNPI can sort as well as previous strongly supervised NPI variants. The AlphaNPI agent is also trained on a Tower of Hanoi puzzle with two disks and is shown to generalize to puzzles with an arbitrary number of disk