  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.
