Learning Compositional Neural Programs with Recursive Tree Search and Planning

Abstract

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

References in corpus (22)

• Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation
• FeUdal Networks for Hierarchical Reinforcement Learning
• Data-Efficient Hierarchical Reinforcement Learning
• DeepCoder: Learning to Write Programs
• Neural Programmer-Interpreters
• Neural GPUs Learn Algorithms
• Modular Multitask Reinforcement Learning with Policy Sketches
• Fast Context Adaptation via Meta-Learning
• A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms
• RobustFill: Neural Program Learning under Noisy I/O
• Sample Efficient Adaptive Text-to-Speech
• Making Neural Programming Architectures Generalize via Recursion
• Programming with a Differentiable Forth Interpreter
• Learning Independent Causal Mechanisms
• TerpreT: A Probabilistic Programming Language for Program Induction
• Near-Optimal Representation Learning for Hierarchical Reinforcement Learning
• Hierarchical Reinforcement Learning with Hindsight
• Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization
• Towards Synthesizing Complex Programs from Input-Output Examples
• Adaptive Neural Compilation
• Hierarchical Reinforcement Learning via Advantage-Weighted Information Maximization
• Forward-Backward Reinforcement Learning

Cited by in corpus (9)

• Evaluating Large Language Models Trained on Code
• Strong Generalization and Efficiency in Neural Programs
• Evolving Reinforcement Learning Algorithms
• Meta-learning curiosity algorithms
• Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis
• Compositional Generalization via Neural-Symbolic Stack Machines
• Learning Compositional Neural Programs for Continuous Control
• Learning compositional programs with arguments and sampling
• On the Parallel Tower of Hanoi Puzzle: Acyclicity and a Conditional Triangle Inequality