Universal Policies for Software-Defined MDPs
arXiv:2012.11401
Abstract
We introduce a new programming paradigm called oracle-guided decision programming in which a program specifies a Markov Decision Process (MDP) and the language provides a universal policy. We prototype a new programming language, Dodona, that manifests this paradigm using a primitive 'choose' representing nondeterministic choice. The Dodona interpreter returns either a value or a choicepoint that includes a lossless encoding of all information necessary in principle to make an optimal decision. Meta-interpreters query Dodona's (neural) oracle on these choicepoints to get policy and value estimates, which they can use to perform heuristic search on the underlying MDP. We demonstrate Dodona's potential for zero-shot heuristic guidance by meta-learning over hundreds of synthetic tasks that simulate basic operations over lists, trees, Church datastructures, polynomials, first-order terms and higher-order terms.
References in corpus (15)
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- Language Models are Few-Shot Learners
- Scaling Laws for Neural Language Models
- Theoretical Models of Learning to Learn
- A Survey on Multi-Task Learning
- Learning a SAT Solver from Single-Bit Supervision
- Learning and Evaluating Contextual Embedding of Source Code
- Scaling Laws for Autoregressive Generative Modeling
- Neural Code Comprehension: A Learnable Representation of Code Semantics
- A Literature Study of Embeddings on Source Code
- Dynamic Neural Program Embedding for Program Repair
- A Theory of Universal Artificial Intelligence based on Algorithmic Complexity
- Neurally-Guided Procedural Models: Amortized Inference for Procedural Graphics Programs using Neural Networks
- Inference Compilation and Universal Probabilistic Programming
- ProGraML: Graph-based Deep Learning for Program Optimization and Analysis