summaries: The paper approaches reinforcement learning from a program synthesis perspective and proposes a new method - LEAPS - that is capable of learning programmatic policies just from weak reward signals. This is achieved in two steps: i) learning a smooth latent manifold where similar programs are encoded close to each other; ii) searching the latent space efficiently via the Cross Entropy Method. LEAPS is applied to several tasks in the Karel domain where it successfully can learn programmatic policies that are even transferable to larger state spaces for zero-shot learning. This paper suggests representing policies for MDPs as programs, and shows how to learn programmatic policies effectively from a mix of trial-and-error experience on specific tasks and a pre-training phase to create an embedding that maps programs producing similar behaviors into similar points in the embedding. The authors compare their method to a variety of baselines, including both ablations of their own model as well as more traditional approaches from hierarchical RL, deep RL, and a standard program synthesizer on the KAREL domain. The authors find that the programmatic policy representations perform better overall for many of the KAREL tasks, and generalize better to larger problems than they were trained on. This paper presents a two-stage method for reinforcement learning via program synthesis, and shows that is is effective compared to baselines for a number of simple gridworld tasks, deminstrating a degree of out-of-distribution generalisation. The first stage of the process learns a latent space for encoding programs, and the second stage searches that latent space for programs that maximise reward in  the task. Overall a very nice paper that deserves publication. - Authors use a two-stage method for program synthesis: (1) They   create an embedding space capturing the semantics of the program   space; (2) They search through the embedding space for a program   that solves the task in hand. - They use variational autoencoder to encode programs, where an   encoder maps a sequence of program tokens into a latent space, while   a decoder maps from the latent space into the original program. They   use a combination of loss functions to ensure that not only   syntactically similar programs are close to each other in the latent   space but also semantically close programs. Loss function consists   of a composition of 3 losses. (A) Classical beta VAE loss which   helps that syntactically close programs are close to each other. (B)   Program behavior reconstruction loss which helps that semantically   similar programs are close to each other in the embedding space. For   example, two syntactically different programs can make same actions   under same situations. This loss is defined by difference between   execution traces of original and reconstructed program. (C) Latent   behavior reconstruction loss. This loss is constructed by learning a   policy to predict correct action based on the latent program   embedding. This allows for backpropagating gradient through the   policy and the encoder to ensure better quality of the embeddings. - After training the variational autoencoder, authors use a cross   entropy method to find a program with maximal performance using the   latent space. They sample the latent space distribution of programs,   decode the latent program into an actual program, execute the   program to obtain corresponding rewards, and repeat the process. - Authors did a nice ablation study where they measured effectiveness   of their individual design decisions: evaluating each of the loss   function components, as well as the effectiveness of the latent   space search method for finding the best performing program. They   compared they method to other methods, deep reinforcement learning   (DRL) based as well as Viper which is a decision tree policy   obtained by mimicking a DRL agent.
abstractText: Recently, deep reinforcement learning (DRL) methods have achieved impressive performance on tasks in a variety of domains. However, neural network policies produced with DRL methods are not human-interpretable and often have difficulty generalizing to novel scenarios. To address these issues, prior works explore learning programmatic policies that are more interpretable and structured for generalization. Yet, these works either employ limited policy representations (e.g. decision trees, state machines, or predefined program templates) or require stronger supervision (e.g. input/output state pairs or expert demonstrations). We present a framework that instead learns to synthesize a program, which details the procedure to solve a task in a flexible and expressive manner, solely from reward signals. To alleviate the difficulty of learning to compose programs to induce the desired agent behavior from scratch, we propose to first learn a program embedding space that continuously parameterizes diverse behaviors in an unsupervised manner and then search over the learned program embedding space to yield a program that maximizes the return for a given task. Experimental results demonstrate that the proposed framework not only learns to reliably synthesize task-solving programs but also outperforms DRL and program synthesis baselines while producing interpretable and more generalizable policies. We also justify the necessity of the proposed two-stage learning scheme as well as analyze various methods for learning the program embedding. Website at https://clvrai.com/leaps.
authors.name: Dweep Trivedi
authors.name: Jesse Zhang
authors.name: Shao-Hua Sun
authors.name: Joseph J. Lim
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A. Rusu Joel Veness Marc G. Bellemare Alex Graves Martin Riedmiller Andreas K. Fidjeland Georg Ostrovski Stig Petersen Charles Beattie Amir Sadik Ioannis Antonoglou Helen King Dharshan Kumaran Daan Wierstra Shane Legg Demis Hassabis
references.title: Human level control through deep reinforcement learning
references.venue: Nature,
references.authors: David Silver Aja Huang Chris J Maddison Arthur Guez Laurent Sifre George Van Den Driessche Julian Schrittwieser Ioannis Antonoglou Veda Panneershelvam Marc Lanctot
references.title: Mastering the game of go with deep neural networks and tree search
references.authors: David Silver Thomas Hubert Julian Schrittwieser Ioannis Antonoglou Matthew Lai Arthur Guez Marc Lanctot Laurent Sifre Dharshan Kumaran Thore Graepel
references.title: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play
references.venue: Science,
references.authors: Oriol Vinyals Igor Babuschkin Wojciech M Czarnecki Michaël Mathieu Andrew Dudzik Junyoung Chung David H Choi Richard Powell Timo Ewalds Petko Georgiev
references.title: Grandmaster level in starcraft ii using multi-agent reinforcement learning
references.authors: Alexandre Campeau-Lecours Hugo Lamontagne Simon Latour Philippe Fauteux Véronique Maheu François Boucher Charles Deguire Louis-Joseph Caron L’Ecuyer
references.title: Kinova modular robot arms for service robotics applications
references.authors: Shixiang Gu Ethan Holly Timothy Lillicrap Sergey Levine
references.title: Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates
references.venue: In International Conference on Robotics and Automation,
references.authors: OpenAI: Marcin Andrychowicz Bowen Baker Maciek Chociej Rafal Jozefowicz Bob McGrew Jakub Pachocki Arthur Petron Matthias Plappert Glenn Powell Alex Ray
references.title: Learning dexterous in-hand manipulation
references.venue: The International Journal of Robotics Research,
references.authors: Danijar Hafner Timothy Lillicrap Jimmy Ba Mohammad Norouzi
references.title: Dream to control: Learning behaviors by latent imagination
references.venue: In International Conference on Learning Representations,
references.authors: Jun Yamada Youngwoon Lee Gautam Salhotra Karl Pertsch Max Pflueger Gaurav S Sukhatme Joseph J Lim Peter Englert
references.title: Motion planner augmented reinforcement learning for robot manipulation in obstructed environments
references.venue: In Conference on Robot Learning,
references.authors: Grace Zhang Linghan Zhong Youngwoon Lee Joseph J Lim
references.title: Policy transfer across visual and dynamics domain gaps via iterative grounding
references.venue: In Robotics: Science and Systems,
references.authors: Youngwoon Lee Edward S Hu Zhengyu Yang Joseph J Lim
references.title: To follow or not to follow: Selective imitation learning from observations
references.venue: In Conference on Robot Learning,
references.authors: Osbert Bastani Yewen Pu Armando Solar-Lezama
references.title: Verifiable reinforcement learning via policy extraction
references.venue: In Neural Information Processing Systems,
references.authors: Jeevana Priya Inala Osbert Bastani Zenna Tavares Armando Solar-Lezama
references.title: Synthesizing programmatic policies that inductively generalize
references.venue: In International Conference on Learning Representations,
references.authors: Abhinav Verma Vijayaraghavan Murali Rishabh Singh Pushmeet Kohli Swarat Chaudhuri
references.title: Programmatically interpretable reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Abhinav Verma Hoang Le Yisong Yue Swarat Chaudhuri
references.title: Imitation-projected programmatic reinforcement learning
references.venue: In Neural Information Processing Systems,
references.authors: Jacob Devlin Jonathan Uesato Surya Bhupatiraju Rishabh Singh Abdel-rahman Mohamed Pushmeet Kohli
references.title: Robustfill: Neural program learning under noisy i/o
references.venue: In International Conference on Machine Learning,
references.authors: Rudy R Bunel Matthew Hausknecht Jacob Devlin Rishabh Singh Pushmeet Kohli
references.title: Leveraging grammar and reinforcement learning for neural program synthesis
references.venue: In International Conference on Learning Representations,
references.authors: Xinyun Chen Chang Liu Dawn Song
references.title: Execution-guided neural program synthesis
references.venue: In International Conference on Learning Representations,
references.authors: Eui Chul Shin Illia Polosukhin Dawn Song
references.title: Improving neural program synthesis with inferred execution traces
references.venue: In Neural Information Processing Systems,
references.authors: Miguel Lázaro-Gredilla Dianhuan Lin J Swaroop Guntupalli Dileep George
references.title: Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs
references.venue: Science Robotics,
references.authors: Shao-Hua Sun Hyeonwoo Noh Sriram Somasundaram Joseph Lim
references.title: Neural program synthesis from diverse demonstration videos
references.venue: In International Conference on Machine Learning,
references.authors: Raphaël Dang-Nhu
references.title: Plans: Neuro-symbolic program learning from videos
references.venue: Neural Information Processing Systems,
references.authors: Richard E Pattis
references.title: Karel the robot: a gentle introduction to the art of programming
references.authors: Danfei Xu Suraj Nair Yuke Zhu Julian Gao Animesh Garg Li Fei-Fei Silvio Savarese
references.title: Neural task programming: Learning to generalize across hierarchical tasks
references.venue: In International Conference on Robotics and Automation,
references.authors: Jacob Devlin Rudy R Bunel Rishabh Singh Matthew Hausknecht Pushmeet Kohli
references.title: Neural program meta-induction
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Arvind Neelakantan Quoc V Le Ilya Sutskever
references.title: Neural programmer: Inducing latent programs with gradient descent
references.venue: In International Conference on Learning Representations,
references.authors: Alex Graves Greg Wayne Ivo Danihelka
references.title: Neural turing machines
references.venue: arXiv preprint arXiv:1410.5401,
references.authors: Łukasz Kaiser Ilya Sutskever
references.title: Neural gpus learn algorithms
references.venue: In International Conference on Learning Representations,
references.authors: Alexander L. Gaunt Marc Brockschmidt Nate Kushman Daniel Tarlow
references.title: Differentiable programs with neural libraries
references.venue: In International Conference on Machine Learning,
references.authors: Scott Reed Nando De Freitas
references.title: Neural programmer-interpreters
references.venue: In International Conference on Learning Representations,
references.authors: Jonathon Cai Richard Shin Dawn Song
references.title: Making neural programming architectures generalize via recursion
references.venue: In International Conference on Learning Representations,
references.authors: Da Xiao Jo-Yu Liao Xingyuan Yuan
references.title: Improving the universality and learnability of neural programmer-interpreters with combinator abstraction
references.venue: In International Conference on Learning Representations,
references.authors: Michael Burke Svetlin Penkov Subramanian Ramamoorthy
references.title: From explanation to synthesis: Compositional program induction for learning from demonstration
references.authors: Yujun Yan Kevin Swersky Danai Koutra Parthasarathy Ranganathan Milad Hashemi
references.title: Neural execution engines: Learning to execute subroutines
references.venue: In Neural Information Processing Systems,
references.authors: Yujia Li Felix Gimeno Pushmeet Kohli Oriol Vinyals
references.title: Strong generalization and efficiency in neural programs
references.venue: arXiv preprint arXiv:2007.03629,
references.authors: De-An Huang Suraj Nair Danfei Xu Yuke Zhu Animesh Garg Li Fei-Fei Silvio Savarese Juan Carlos Niebles
references.title: Neural task graphs: Generalizing to unseen tasks from a single video demonstration
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Matko Bošnjak Tim Rocktäschel Jason Naradowsky Sebastian Riedel
references.title: Programming with a differentiable forth interpreter
references.venue: In International Conference on Machine Learning,
references.authors: Emilio Parisotto Abdel-rahman Mohamed Rishabh Singh Lihong Li Dengyong Zhou Pushmeet Kohli
references.title: Neuro-symbolic program synthesis
references.venue: In International Conference on Learning Representations,
references.authors: Richard Shin Illia Polosukhin Dawn Song
references.title: Improving neural program synthesis with inferred execution traces
references.venue: In Neural Information Processing Systems,
references.authors: Yunchao Liu Jiajun Wu Zheng Wu Daniel Ritchie William T. Freeman Joshua B. Tenenbaum
references.title: Learning to describe scenes with programs
references.venue: In International Conference on Learning Representations,
references.authors: Xi Victoria Lin Chenglong Wang Luke Zettlemoyer Michael D Ernst
references.title: Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system
references.venue: In International Conference on Language Resources and Evaluation,
references.authors: Yuan-Hong Liao Xavier Puig Marko Boben Antonio Torralba Sanja Fidler
references.title: Synthesizing environment-aware activities via activity sketches
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Kevin Ellis Maxwell Nye Yewen Pu Felix Sosa Josh Tenenbaum Armando Solar- Lezama
references.title: Write, execute, assess: Program synthesis with a repl
references.venue: In Neural Information Processing Systems,
references.authors: Kevin Ellis Catherine Wong Maxwell Nye Mathias Sable-Meyer Luc Cary Lucas Morales Luke Hewitt Armando Solar-Lezama Joshua B Tenenbaum
references.title: Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning
references.venue: arXiv preprint arXiv:2006.08381,
references.authors: Matej Balog Alexander L Gaunt Marc Brockschmidt Sebastian Nowozin Daniel Tarlow
references.title: Deepcoder: Learning to write programs
references.venue: In International Conference on Learning Representations,
references.authors: Paweł Liskowski Krzysztof Krawiec Nihat Engin Toklu Jerry Swan
references.title: Program synthesis as latent continuous optimization: Evolutionary search in neural embeddings
references.venue: In Genetic and Evolutionary Computation Conference,
references.authors: Daniel A Abolafia Mohammad Norouzi Jonathan Shen Rui Zhao Quoc V Le
references.title: Neural program synthesis with priority queue training
references.venue: arXiv preprint arXiv:1801.03526,
references.authors: Joey Hong David Dohan Rishabh Singh Charles Sutton Manzil Zaheer
references.title: Latent programmer: Discrete latent codes for program synthesis
references.venue: In International Conference on Machine Learning,
references.authors: Tom Silver Kelsey R Allen Alex K Lew Leslie Pack Kaelbling Josh Tenenbaum
references.title: Few-shot bayesian imitation learning with logical program policies
references.venue: In Association for the Advancement of Artificial Intelligence,
references.authors: Jiajun Wu Joshua B Tenenbaum Pushmeet Kohli
references.title: Neural scene de-rendering
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Mark Chen Jerry Tworek Heewoo Jun Qiming Yuan Henrique Ponde Jared Kaplan Harri Edwards Yura Burda Nicholas Joseph Greg Brockman
references.title: Evaluating large language models trained on code
references.venue: arXiv preprint arXiv:2107.03374,
references.authors: Ferran Alet Javier Lopez-Contreras James Koppel Maxwell Nye Armando Solar-Lezama Tomas Lozano-Perez Leslie Kaelbling Joshua Tenenbaum
references.title: A large-scale benchmark for few-shot program induction and synthesis
references.venue: In International Conference on Machine Learning,
references.authors: Xinyun Chen Dawn Song Yuandong Tian
references.title: Latent execution for neural program synthesis beyond domain-specific languages
references.venue: arXiv preprint arXiv:2107.00101,
references.authors: Jacob Austin Augustus Odena Maxwell Nye Maarten Bosma Henryk Michalewski David Dohan Ellen Jiang Carrie Cai Michael Terry Quoc Le
references.title: Program synthesis with large language models
references.venue: arXiv preprint arXiv:2108.07732,
references.authors: Joey Hong David Dohan Rishabh Singh Charles Sutton Manzil Zaheer
references.title: Latent programmer: Discrete latent codes for program synthesis
references.venue: In International Conference on Machine Learning,
references.authors: Catherine Wong Kevin Ellis Joshua B Tenenbaum Jacob Andreas
references.title: Leveraging language to learn program abstractions and search heuristics
references.venue: In International Conference on Machine Learning,
references.authors: Xinyun Chen Petros Maniatis Rishabh Singh Charles Sutton Hanjun Dai Max Lin Denny Zhou
references.title: Spreadsheetcoder: Formula prediction from semi-structured context
references.venue: In International Conference on Machine Learning,
references.authors: Maxwell Nye Yewen Pu Matthew Bowers Jacob Andreas Joshua B. Tenenbaum Armando Solar-Lezama
references.title: Representing partial programs with blended abstract semantics
references.venue: In International Conference on Learning Representations,
references.authors: Dongkyu Choi Pat Langley
references.title: Learning teleoreactive logic programs from problem solving
references.venue: In International Conference on Inductive Logic Programming,
references.authors: Elly Winner Manuela Veloso
references.title: Distill: Learning domain-specific planners by example
references.venue: In International Conference on Machine Learning,
references.authors: Mikel Landajuela Brenden K Petersen Sookyung Kim Claudio P Santiago Ruben Glatt Nathan Mundhenk Jacob F Pettit Daniel Faissol
references.title: Discovering symbolic policies with deep reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Diederik P Kingma Max Welling
references.title: Auto-encoding variational bayes
references.venue: In International Conference on Learning Representations,
references.authors: Irina Higgins Loic Matthey Arka Pal Christopher Burgess Xavier Glorot Matthew Botvinick Shakir Mohamed Alexander Lerchner
references.title: beta-vae: Learning basic visual concepts with a constrained variational framework
references.venue: In International Conference on Learning Representations,
references.authors: Ronald J Williams
references.title: Simple statistical gradient-following algorithms for connectionist reinforcement learning
references.venue: Machine learning,
references.authors: Reuven Y Rubinstein
references.title: Optimization of computer simulation models with rare events
references.venue: European Journal of Operational Research,
references.authors: Stéphane Ross Geoffrey Gordon Drew Bagnell
references.title: A reduction of imitation learning and structured prediction to no-regret online learning
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: John Schulman Filip Wolski Prafulla Dhariwal Alec Radford Oleg Klimov
references.title: Proximal policy optimization algorithms
references.venue: arXiv preprint arXiv:1707.06347,
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: In International Conference on Machine Learning,
references.authors: Zachary C Lipton
references.title: The mythos of model interpretability
references.venue: In ICML Workshop on Human Interpretability in Machine Learning,
references.authors: Owen Shen
references.title: Interpretability in ml: A broad overview, 2020
references.venue: URL https://mlu.red/ muse/52906366310
references.authors: Jesse Zhang Brian Cheung Chelsea Finn Sergey Levine Dinesh Jayaraman
references.title: Cautious adaptation for reinforcement learning in safety-critical settings
references.venue: In International Conference on Machine Learning,
references.authors: Lukas Hewing Juraj Kabzan Melanie N. Zeilinger
references.title: Cautious model predictive control using gaussian process regression
references.venue: IEEE Transactions on Control Systems Technology,
references.authors: Jaime F Fisac Anayo K Akametalu Melanie N Zeilinger Shahab Kaynama Jeremy Gillula Claire J Tomlin
references.title: A general safety framework for learning-based control in uncertain robotic systems
references.venue: IEEE Transactions on Automatic Control,
references.authors: A. Hakobyan G.C. Kim I. Yang
references.title: Risk-aware motion planning and control using cvarconstrained optimization
references.venue: IEEE Robotics and Automation Letters,
references.authors: Dorsa Sadigh Ashish Kapoor
references.title: Safe control under uncertainty with probabilistic signal temporal logic
references.venue: In Proceedings of Robotics: Science and Systems,
references.authors: Felix Berkenkamp Matteo Turchetta Angela P. Schoellig Andreas Krause
references.title: Safe modelbased reinforcement learning with stability guarantees
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Brijen Thananjeyan Ashwin Balakrishna Ugo Rosolia Felix Li Rowan McAllister Joseph E. Gonzalez Sergey Levine Francesco Borrelli Ken Goldberg
references.title: Safety augmented value estimation from demonstrations (saved): Safe deep model-based rl for sparse cost robotic tasks
references.venue: IEEE Robotics and Automation Letters,
references.authors: Anil Aswani Humberto Gonzalez S Shankar Sastry Claire Tomlin
references.title: Provably safe and robust learning-based model predictive control
references.authors: Jacob Andreas Dan Klein Sergey Levine
references.title: Modular multitask reinforcement learning with policy sketches
references.venue: In International Conference on Machine Learning,
references.authors: Junhyuk Oh Satinder Singh Honglak Lee Pushmeet Kohli
references.title: Zero-shot task generalization with multi-task deep reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Shao-Hua Sun Te-Lin Wu Joseph J. Lim
references.title: Program guided agent
references.venue: In International Conference on Learning Representations,
references.authors: Yichen Yang Jeevana Priya Inala Osbert Bastani Yewen Pu Armando Solar-Lezama Martin Rinard
references.title: Program synthesis guided reinforcement learning
references.venue: arXiv preprint arXiv:2102.11137,
references.authors: Youngwoon Lee Shao-Hua Sun Sriram Somasundaram Edward Hu Joseph J. Lim
references.title: Composing complex skills by learning transition policies
references.venue: In International Conference on Learning Representations,
references.authors: Zelin Zhao Karan Samel Binghong Chen Le Song
references.title: Proto: Program-guided transformer for program-guided tasks
references.venue: arXiv preprint arXiv:2110.00804,
references.authors: Yee Whye Teh Victor Bapst Wojciech Marian Czarnecki John Quan James Kirkpatrick Raia Hadsell Nicolas Heess Razvan Pascanu
references.title: Distral: Robust multitask reinforcement learning
references.venue: arXiv preprint arXiv:1707.04175,
references.authors: Richard Socher Tianmin Shu Caiming Xiong
references.title: Hierarchical and interpretable skill acquisition in multi-task reinforcement learning
references.venue: International Conference on Learning Representations,
references.authors: Sungryull Sohn Junhyuk Oh Honglak Lee
references.title: Hierarchical reinforcement learning for zeroshot generalization with subtask dependencies
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ayush Jain Andrew Szot Joseph Lim
references.title: Generalization to new actions in reinforcement learning
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: Karl Pertsch Youngwoon Lee Joseph J. Lim
references.title: Accelerating reinforcement learning with learned skill priors
references.venue: In Conference on Robot Learning,
references.authors: Jake Snell Kevin Swersky Richard Zemel
references.title: Prototypical networks for few-shot learning
references.venue: In Advances in Neural Information Processing Systems
references.authors: Risto Vuorio Shao-Hua Sun Hexiang Hu Joseph J Lim
references.title: Multimodal model-agnostic meta-learning via task-aware modulation
references.venue: In Neural Information Processing Systems,
references.authors: Oriol Vinyals Charles Blundell Tim Lillicrap Daan Wierstra
references.title: Matching networks for one shot learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Chelsea Finn Pieter Abbeel Sergey Levine
references.title: Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
references.venue: In International Conference on Machine Learning,
references.authors: Risto Vuorio Shao-Hua Sun Hexiang Hu Joseph J Lim
references.title: Toward multimodal modelagnostic meta-learning
references.venue: arXiv preprint arXiv:1812.07172,
references.authors: Wei-Yu Chen Yen-Cheng Liu Zsolt Kira Yu-Chiang Frank Wang Jia-Bin Huang
references.title: A closer look at few-shot classification
references.venue: In International Conference on Learning Representations,
references.authors: Yoonho Lee Seungjin Choi
references.title: Gradient-Based Meta-Learning with Learned Layerwise Metric and Subspace
references.venue: In International Conference on Machine Learning,
references.authors: Alex Nichol John Schulman
references.title: Reptile: a scalable metalearning algorithm
references.venue: arXiv preprint arXiv:1803.02999,
references.authors: Garima Pruthi Frederick Liu Satyen Kale Mukund Sundararajan
references.title: Estimating training data influence by tracing gradient descent
references.venue: In Neural Information Processing Systems,
references.authors: Yun-Chun Chen Chao-Te Chou Yu-Chiang Frank Wang
references.title: Learning to learn in a semisupervised fashion
references.venue: In European Conference on Computer Vision,
references.authors: I.T. Jolliffe
references.title: Principal Component Analysis
references.authors: Mihalj Bakator Dragica Radosav
references.title: Deep learning and medical diagnosis: A review of literature
references.venue: Multimodal Technologies and Interaction,
references.authors: Dinggang Shen Guorong Wu Heung-Il Suk
references.title: Deep learning in medical image analysis
references.venue: Annual review of biomedical engineering,
references.authors: Biraja Ghoshal Allan Tucker
references.title: Estimating uncertainty and interpretability in deep learning for coronavirus (covid-19) detection
references.venue: arXiv preprint arXiv:2003.10769,
references.authors: Chia-Jung Chang Wei Guo Jie Zhang Jon Newman Shao-Hua Sun Matt Wilson
references.title: Behavioral clusters revealed by end-to-end decoding from microendoscopic imaging
references.venue: bioRxiv,
references.authors: Amitojdeep Singh Sourya Sengupta Vasudevan Lakshminarayanan
references.title: Explainable deep learning models in medical image analysis
references.venue: Journal of Imaging,
references.authors: Vladimir Iosifovich Levenshtein
references.title: Binary codes capable of correcting deletions, insertions and reversals
references.venue: Soviet Physics Doklady,
references.authors: Michihiro Yasunaga Percy Liang
references.title: Graph-based, self-supervised program repair from diagnostic feedback
references.venue: In International Conference on Machine Learning,
references.authors: Hoang Duong Thien Nguyen Dawei Qi Abhik Roychoudhury Satish Chandra
references.title: Semfix: Program repair via semantic analysis
references.venue: In Conference on Software Engineering,
references.authors: Jiajun Jiang Yingfei Xiong Hongyu Zhang Qing Gao Xiangqun Chen
references.title: Shaping program repair space with existing patches and similar code
references.venue: In ACM SIGSOFT International Symposium on Software Testing and Analysis,
references.authors: Qi Xin Steven P Reiss
references.title: Leveraging syntax-related code for automated program repair
references.venue: In International Conference on Automated Software Engineering,
references.authors: Claire Le Goues Michael Pradel Abhik Roychoudhury
references.title: Automated program repair
references.venue: Communications of the ACM,
references.authors: Eric Schulte Stephanie Forrest Westley Weimer
references.title: Automated program repair through the evolution of assembly code
references.venue: In International Conference on Automated Software Engineering,
references.authors: Anil Koyuncu Kui Liu Tegawendé F Bissyandé Dongsun Kim Jacques Klein Martin Monperrus Yves Le Traon
references.title: Fixminer: Mining relevant fix patterns for automated program repair
references.venue: Empirical Software Engineering,
references.authors: Thomas Durieux Martin Monperrus
references.title: Dynamoth: dynamic code synthesis for automatic program repair
references.venue: In International Workshop on Automation of Software Test,
references.authors: Yi Li Shaohua Wang Tien N Nguyen
references.title: Dlfix: Context-based code transformation learning for automated program repair
references.venue: In International Conference on Software Engineering,
references.authors: Liushan Chen Yu Pei Carlo A Furia
references.title: Contract-based program repair without the contracts
references.venue: In International Conference on Automated Software Engineering,
references.authors: Martin White Michele Tufano Matias Martinez Martin Monperrus Denys Poshyvanyk
references.title: Sorting and transforming program repair ingredients via deep learning code similarities
references.venue: In IEEE International Conference on Software Analysis, Evolution and Reengineering,
references.authors: Rahul Gupta Soham Pal Aditya Kanade Shirish Shevade
references.title: Deepfix: Fixing common c language errors by deep learning
references.venue: In Association for the Advancement of Artificial Intelligence,
references.authors: Ke Wang Rishabh Singh Zhendong Su
references.title: Dynamic neural program embedding for program repair
references.venue: arXiv preprint arXiv:1711.07163,
references.authors: Ali Mesbah Andrew Rice Emily Johnston Nick Glorioso Edward Aftandilian
references.title: Deepdelta: learning to repair compilation errors
references.venue: In ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering,
references.authors: He Zhu Zikang Xiong Stephen Magill Suresh Jagannathan
references.title: An inductive synthesis framework for verifiable reinforcement learning
references.venue: In ACM SIGPLAN Conference on Programming Language Design and Implementation,
references.authors: Jonathan Long Evan Shelhamer Trevor Darrell
references.title: Fully convolutional networks for semantic segmentation
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Karol Hausman Jost Tobias Springenberg Ziyu Wang Nicolas Heess Martin Riedmiller
references.title: Learning an embedding space for transferable robot skills
references.venue: In International Conference on Learning Representations,
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A Rusu Joel Veness Marc G Bellemare Alex Graves Martin Riedmiller Andreas K Fidjeland Georg Ostrovski
references.title: Human-level control through deep reinforcement learning
sections.heading: 1 Introduction
sections.text: Recently, deep reinforcement learning (DRL) methods have demonstrated encouraging performance on a variety of domains such as outperforming humans in complex games [1–4] or controlling robots [5–11]. Despite the recent progress in the field, acquiring complex skills through trial and error still remains challenging and these neural network policies often have difficulty generalizing to novel scenarios. Moreover, such policies are not interpretable to humans and therefore are difficult to debug when these challenges arise.
  To address these issues, a growing body of work aims to learn programmatic policies that are structured in more interpretable and generalizable representations such as decision trees [12], statemachines [13], and programs described by domain-specific programming languages [14, 15]. Yet, the programmatic representations employed in these works are often limited in expressiveness due to constraints on the policy spaces. For example, decision tree policies are incapable of naïvely generating repetitive behaviors, state machine policies used in [13] are computationally complex to ∗Contributed equally. †Work partially done as a visiting scholar at USC. ‡AI Advisor at NAVER AI Lab.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  scale to policies representing diverse behaviors, and the programs of [14, 15] are constrained to a set of predefined program templates. On the other hand, program synthesis works that aim to represent desired behaviors using flexible domain-specific programs often require extra supervision such as input/output pairs [16–20] or expert demonstrations [21, 22], which can be difficult to obtain.
  In this paper, we present a framework to instead synthesize human-readable programs in an expressive representation, solely from rewards, to solve tasks described by Markov Decision Processes (MDPs). Specifically, we represent a policy using a program composed of control flows (e.g. if/else and loops) and an agent’s perceptions and actions. Our programs can flexibly compose behaviors through perception-conditioned loops and nested conditional statements. However, composing individual program tokens (e.g. if, while, move()) in a trial-and-error fashion to synthesize programs that can solve given MDPs can be extremely difficult and inefficient.
  To address this problem, we propose to first learn a latent program embedding space where nearby latent programs correspond to similar behaviors and allows for smooth interpolation, together with a program decoder that can decode a latent program to a program consisting of a sequence of program tokens. Then, when a task is given, this embedding space allows us to iteratively search over candidate latent programs to find a program that induces desired behavior to maximize the reward. Specifically, this embedding space is learned through reconstruction of randomly generated programs and the behaviors they induce in the environment in an unsupervised manner. Once learned, the embedding space can be reused to solve different tasks without retraining.
  To evaluate the proposed framework, we consider the Karel domain [23], featuring an agent navigating through a gridworld and interacting with objects to solve tasks such as stacking and navigation. The experimental results demonstrate that the proposed framework not only learns to reliably synthesize task-solving programs but also outperforms program synthesis and deep RL baselines. In addition, we justify the necessity of the proposed two-stage learning scheme as well as conduct an extensive analysis comparing various approaches for learning the latent program embedding spaces. Finally, we perform experiments which highlight that the programs produced by our proposed framework can both generalize to larger state spaces and unseen state configurations as well as be interpreted and edited by humans to improve their task performance.
sections.heading: 2 Related Work
sections.text: Neural program induction and synthesis. Program induction methods [20, 24–36] aim to implicitly induce the underlying programs to mimic the behaviors demonstrated in given task specifications such as input/output pairs or expert demonstrations. On the other hand, program synthesis methods [16– 19, 21, 37–58] explicitly synthesize the underlying programs and execute the programs to perform the tasks from task specifications such input/output pairs, demonstrations, language instructions. In contrast, we aim to learn to synthesize programs solely from reward described by an MDP without other task specifications. Similarly to us, a two-stage synthesis method is proposed in [46]. Yet, the task is to match truth tables for given test programs rather than solve MDPs. Their first stage requires the entire ground-truth table for each program synthesized during training, which is infeasible to apply to our problem setup (i.e. synthesizing imperative programs for solving MDPs).
  Learning programmatic policies. Prior works have also addressed the problem of learning programmatic policies [59–61]. Bastani et al. [12] learns a decision tree as a programmatic policy for pong and cartpole environments by imitating an oracle neural policy. However, decision trees are incapable of representing repeating behaviors on their own. Silver et al. [49] addresses this by including a loop-style token for their decision tree policy, though it is still not as expressive as synthesized loops. Inala et al. [13] learns programmatic policies as finite state machines by imitating a teacher policy, although finite state machine complexity can scale quadratically with the number of states, making them difficult to scale to more complex behaviors.
  Another line of work instead synthesizes programs structured in Domain Specific Languages (DSLs), allowing humans to design tokens (e.g. conditions and operations) and control flows (e.g. while loops, if statements, reusable functions) to induce desired behaviors and can produce human interpretable programs. Verma et al. [14, 15] distill neural network policies into programmatic policies. Yet, the initial programs are constrained to a set of predefined program templates. This significantly limits the scope of synthesizable programs and requires designing such templates for each task. In contrast,
  our method can synthesize diverse programs, without templates, which can flexibly represent the complex behaviors required to solve various tasks.
  3 Problem Formulation
  We are interested in learning to synthesize a program structured in a given DSL that can be executed to solve a given task described by an MDP, purely from reward. In this section, we formally define our definition of a program and DSL, tasks described by MDPs, and the problem formulation.
  Program and Domain Specific Language. The programs, or programmatic policies, considered in this work are defined based on a DSL as shown in Figure 1. The DSL consists of control flows and an agent’s perceptions and actions. A perception indi-
  cates circumstances in the environment (e.g. frontIsClear()) that can be perceived by an agent, while an action defines a certain behavior that can be performed by an agent (e.g. move(), turnLeft()). Control flow includes if/else statements, loops, and boolean/logical operators to compose more sophisticated conditions. A policy considered in this work is described by a program ρ which is executed to produce a sequence of actions given perceptions from the environment.
  MDP. We consider finite-horizon discounted MDPs with initial state distribution µ(so) and discount factor γ. For a fixed sequence {(s0, a0), ..., (st, at)} of states and actions obtained from a rollout of a given policy, the performance of the policy is evaluated based on a discounted return ∑T t=0 γ
  trt, where T is the horizon of the episode and rt = R(st, at) the reward function. Objective. Our objective is maxρ Ea∼EXEC(ρ),s0∼µ[ ∑T t=0 γ
  trt], where EXEC returns the actions induced by executing a program policy ρ in the environment. Note that one can view this objective as a special case of the standard RL objective, where the policy is represented as a program which follows the grammar of the DSL and the policy rollout is obtained by executing the program.
sections.heading: 4 Approach
sections.text: Our goal is to develop a framework that can synthesize a program (i.e. a programmatic policy) structured in a given DSL that can be executed to solve a task of interest. This requires the ability to synthesize a program that is not only valid for execution (e.g. grammatically correct) but also describes desired behaviors for solving the task from only the reward. Yet, learning to synthesize such a program from scratch for every new task can be difficult and inefficient.
  To this end, we propose our Learning Embeddings for lAtent Program Synthesis framework, dubbed LEAPS, as illustrated in Figure 2. LEAPS first learns a latent program embedding space that continuously parameterizes diverse behaviors and a program decoder that decodes a latent program to a program consisting of a sequence of program tokens. Then, when a task is given, we iteratively search over this embedding space and decode each candidate latent program using the decoder to find a program that maximizes the reward. This two-stage learning scheme not only enables learning to synthesize programs to acquire desired behaviors described by MDPs solely from reward, but also allows reusing the learned embedding space to solve different tasks without retraining.
  In the rest of this section, we describe how we construct the model and our learning objectives for the latent program embedding space in Section 4.1. Then, we present how a program that describes desired behaviors for a given task can be found through a search algorithm in Section 4.2.
sections.heading: 4.1 Learning a Program Embedding Space
sections.text: To learn a latent program embedding space, we propose to train a variational autoencoder (VAE) [62] that consists of a program encoder qφ which encodes a program ρ to a latent program z and a program decoder pθ which reconstructs the program from the latent. Specifically, the VAE is trained through
  reconstruction of randomly generated programs and the behaviors they induce in the environment in an unsupervised manner. Architectural details are listed in Section L.6.
  Since we aim to iteratively search over the learned embedding space to achieve certain behaviors when a task is given, we want this embedding space to allow for smooth behavior interpolation (i.e. programs that exhibit similar behaviors are encoded closer in the embedding space). To this end, we propose to train the model by optimizing the following three objectives.
sections.heading: 4.1.1 Program Reconstruction
sections.text: To learn a program embedding space, we train a program encoder qφ and a program decoder pθ to reconstruct programs composed of sequences of program tokens. Given an input program ρ consisting of a sequence of program tokens, the encoder processes the input program one token at a time and produces a latent program embedding z. Then, the decoder outputs program tokens one by one from the latent program embedding z to synthesize a reconstructed program ρ̂. Both the encoder and the decoder are recurrent neural networks and are trained to optimize the β-VAE [63] loss:
  LPθ,φ(ρ) = −Ez∼qφ(z|ρ)[log pθ(ρ|z)] + βDKL(qφ(z|ρ)‖pθ(z)). (1)
sections.heading: 4.1.2 Program Behavior Reconstruction
sections.text: While the loss in Eq. 1 enforces that the model encodes syntactically similar programs close to each other in the embedding space, we also want to encourage programs with the same semantics to have similar program embeddings. An example that demonstrates the importance of this is the program aliasing issue, where different programs have identical program semantics (e.g. repeat(2): move() and move() move()). Thus, we introduce an objective that compares the execution traces of the input program and the reconstructed program. Since the program execution process is not differentiable, we optimize the model via REINFORCE [64]:
  LRθ,φ(ρ) = −Ez∼qφ(z|ρ)[Rmat(pθ(ρ|z), ρ)], (2)
  where Rmat(ρ̂, ρ), the reward for matching the input program’s behavior, is defined as
  Rmat(ρ̂, ρ) = Eµ[ 1
  N N∑ t=1 1{EXECi(ρ̂) == EXECi(ρ) ∀i = 1, 2, ...t}︸ ︷︷ ︸ stays 0 after the first t where EXECt(ρ̂) != EXECt(ρ) ], (3)
  where N is the maximum of the lengths of the execution traces of both programs, and EXECi(ρ) represents the action taken by program ρ at time i. Thus this objective encourages the model to embed behaviorally similar yet possibly syntactically different programs to similar latent programs.
sections.heading: 4.1.3 Latent Behavior Reconstruction
sections.text: To further encourage learning a program embedding space that allows for smooth behavior interpolation, we devise another source of supervision by learning a program embedding-conditioned policy. Denoted π(a|z, st), this recurrent policy takes the program embedding z produced by the program encoder and learns to predict corresponding agent actions. One can view this policy as a neural program executor that allows gradient propagation through the policy and the program encoder by optimizing the cross entropy between the actions obtained by executing the input program ρ and the actions predicted by the policy:
  LLπ(ρ, π) = −Eµ[ M∑ t=1 |A|∑ i=1 1{EXECi(ρ̂) == EXECi(ρ)} log π(ai|z, st)], (4)
  where M denotes the length of the execution of ρ. Optimizing this objective directly encourages the program embeddings, through supervised learning instead of RL as in LR, to be useful for action reconstruction, thus further ensuring that similar behaviors are encoded together and allowing for smooth interpolation. Note that this policy is only used for improving learning the program embedding space not for solving the tasks of interest in the later stage.
  In summary, we propose to optimize three sources of supervision to learn the program embedding space that allows for smooth interpolation and can be used to search for desired agent behaviors: (1) LP (Eq. 1), the β-VAE objective for program reconstruction, (2) LR (Eq. 2), an RL environmentstate matching loss for the reconstructed program, and (3) LL (Eq. 4), a supervised learning loss to encourage predicting the ground-truth agent action sequences. Thus our combined objective is:
  min θ,φ,π
  λ1LPθ,φ(ρ) + λ2LRθ,φ(ρ) + λ3LLπ(ρ, π), (5)
  where λ1, λ2, and λ3 are hyperparameters controlling the importance of each loss. Optimizing the combination of these losses encourages the program embedding to be both semantically and syntactically informative. More training details can be found in Section L.6.
sections.heading: 4.2 Latent Program Search: Synthesizing a Task-Solving Program
sections.text: Once the program embedding space is learned, our goal becomes searching for a latent program that maximizes the reward described by a given task MDP. To this end, we adapt the Cross Entropy Method (CEM) [65], a gradient-free continuous search algorithm, to iteratively search over the program embedding space. Specifically, we (1) sample a distribution of latent programs, (2) decode the sampled latent programs into programs using the learned program decoder pθ, (3) execute the programs in the task environment and obtain the corresponding rewards, and (4) update the CEM sampling distribution based on the rewards. This process is repeated until either convergence or the maximum number of sampling steps has been reached.
sections.heading: 5 Experiments
sections.text: We first introduce the environment and the tasks in Section 5.1 and describe the experimental setup in Section 5.2. Then, we justify the design of LEAPS by conducting extensive ablation studies in Section 5.3. We describe the baselines used for comparison in Section 5.4, followed by the experimental results presented in Section 5.5. In Section 5.6, we conduct experiments to evaluate the ability of our method to generalize to a larger state space without further learning. Finally, we investigate how LEAPS’ interpretability can be leveraged by conducting experiments that allow humans to debug and improve the programs synthesized by LEAPS in Section 5.7
sections.heading: 5.1 Karel domain
sections.text: To evaluate the proposed framework, we consider the Karel domain [23], as featured in [17, 19, 21], which features an agent navigating through a gridworld with walls and interacting with markers. The agent has 5 actions for moving and interacting with marker and 5 perceptions for detecting obstacles and markers. The tasks of interest are shown in Figure 3. Note that most tasks have randomly sampled agent, wall, marker, and/or goal configurations. When either training or evaluating, we randomly sample initial configurations upon every episode reset. More details can be found in Section K.
sections.heading: 5.2 Programs
sections.text: To produce programs for learning the program embedding space, we randomly generated a dataset of 50,000 unique programs. Note that the programs are generated independently of any Karel tasks; each program is created only by sampling tokens from the DSL, similar to the procedures used in [16–19, 21, 22]. This dataset is split into a training set with 35,000 programs a validation set with 7,500 programs, and a testing set with 7,500 programs. The validation set is used to select the learned program embedding space to use for the program synthesis stage.
  For each program, we sample random Karel states and execute the program on them from different starting states to obtain 10 environment rollouts to compute the program behavior reconstruction loss LR and the latent behavior reconstruction loss LL when learning the program embedding space. We perform checks to ensure rollouts cover all execution branches in the program so that they are representative of all aspects of the program’s behavior. The maximum length of the programs is 44 tokens and the average length is 17.9. We plot a histogram of their lengths in Figure 14 (in Appendix). More dataset generation details can be found in Section J.
sections.heading: 5.3 Ablation Study
sections.text: We first ablate various components of our proposed framework in order to (1) justify the necessity of the proposed two-stage learning scheme and (2) identify the effects of the proposed objectives. We consider the following baselines and ablations of our method (illustrated Section I).
  • Naïve: a program synthesis baseline that learns to directly synthesize a program from scratch by recurrently predicting a sequence of program tokens. This baseline investigates if an end-to-end learning method can solve the problem. More details can be found in Section L.4. • LEAPS-P: the simplest ablation of LEAPS, in which the program embedding space is learned by
  only optimizing the program reconstruction loss LP (Eq. 1). • LEAPS-P+R: an ablation of LEAPS which optimizes both the program reconstruction loss LP
  (Eq. 1) and the program behavior reconstruction loss LR (Eq. 2). • LEAPS-P+L: an ablation of LEAPS which optimizes both the program reconstruction loss LP
  (Eq. 1) and the latent behavior reconstruction loss LL (Eq. 4). • LEAPS (LEAPS-P+R+L): LEAPS with all the losses, optimizing our full objective in Eq. 5. • LEAPS-rand-{8/64}: similar to LEAPS, this ablation also optimizes the full objective (Eq. 5) for
  learning the program embedding space. Yet, when searching latent programs, instead of CEM, it simply randomly samples 8/64 candidate latent programs and chooses the best performing one. These baselines justify the effectiveness of using CEM for searching latent programs.
  Program Behavior Reconstruction. To determine the effectiveness of the proposed two-stage learning scheme and the learning objectives, we measure how effective each ablation is at reconstructing the behaviors of input programs. We use programs from the test set (shown in Figure 9 in Appendix), and utilize the environment state matching reward Rmat(ρ̂, ρ) (Eq. 3), with a 0.1 bonus for synthesizing a syntactically correct program. Thus the return ranges between [0, 1.1]. We report the mean cumulative return, over 5 random seeds, of the final programs after convergence.
  The results are reported in Table 1. Each test is named after its control flows (e.g. IFELSE+WHILE has an if-else statement and a while loop). The naïve program synthesis baseline fails on the complex WHILE+2IF+IFELSE program, as it rarely synthesizes conditional and loop statements, instead generating long sequences of action tokens that attempt to replicate the desired behavior of those statements (see synthesized programs in Figure 10). We believe that this is because it is incentivized to initially predict action tokens to gain more immediate reward, making it less likely to synthesize other tokens. LEAPS and its variations perform better and synthesize more complex programs, demonstrating the importance of the proposed two-stage learning scheme in biasing program search. We also note that LEAPS-P achieves the worst performance out of the CEM search LEAPS ablations, indicating that optimizing the program reconstruction loss LP (the VAE loss) alone does not yield satisfactory results. Jointly optimizing LP with either the program behavior reconstruction loss LR or the latent behavior reconstruction loss LL improves the performance, and optimizing our full objective with all three achieves the best performance across all tasks, indicating the effectiveness of the proposed losses. Finally, LEAPS outperforms LEAPS-rand-8/64, suggesting the necessity of adopting better search algorithms such as CEM.
  Program Embedding Space Smoothness. We investigate if the program and latent behavior reconstruction losses encourage learning a behaviorially smooth embedding space. To quantify behavioral smoothness, we measure how much a change in the embedding space corresponds to a change in behavior by comparing execution traces. For all programs we compute the pairwise Euclidean distance between their embeddings
  in each model. We then calculate the environment state matching distance Rmat between the decoded programs by executing them from the same initial state.
  The results are reported in Table 2. LEAPS and LEAPS-P+L perform the best, suggesting that optimizing the latent behavior reconstruction objective LL, in Eq. 4, is essential for improving the smoothness of the latent space in terms of execution behavior. We further analyze and visualize the learned program embedding space in Section A and Figure 4 (in Appendix).
sections.heading: 5.4 Baselines
sections.text: We evaluate LEAPS against the following baselines (illustrated in Figure 13 in Appendix Section I).
  • DRL: a neural network policy trained on each task and taking raw states (Karel grids) as input. • DRL-abs: a recurrent neural network policy directly trained on each Karel task but taking abstract
  states as input (i.e. it sees the same perceptions as LEAPS, e.g. frontIsClear()==true). • DRL-abs-t: a DRL transfer learning baseline in which for each task, we train DRL-abs policies
  on all other tasks, then fine-tune them on the current task. Thus it acquires a prior by learning to
  All the baselines are trained with PPO [67] or SAC [68], including the VIPER teacher policy. More training details can be found in Section L.
sections.heading: 5.5 Results
sections.text: We present the results of the baselines and our method evaluated on the Karel task set based on the environment rewards in Table 3. The reward functions are sparse for all tasks, and are normalized such that the final cumulative return is within [−1, 1] for tasks with penalties and [0, 1] for tasks without; reward functions for each task are detailed in Section K.
  Overall Task Performance. Across all but one task, LEAPS yields the best performance. The LEAPS-rand baselines perform significantly worse than LEAPS on all Karel tasks, demonstrating the need for using a search algorithm like CEM during synthesis. The performance of VIPER is bounded by its RL teacher policy, and therefore is outperformed by the DRL baselines on most of the tasks. Meanwhile, DRL-abs-t is generally unable to improve upon DRL-abs across the board, suggesting that transferring Karel behaviors with RL from one task to another is ineffective. Furthermore, both the HRL baselines achieve poor performance, likely because agent actions alone provide insufficient supervision for a VAE to encode useful action trajectories on unseen tasks—unlike programs. Finally, the poor performance of the naïve program synthesis baseline highlights the difficulty and inefficiency of learning to synthesize programs from scratch using only rewards. In the appendix, we present programs synthesized by LEAPS in Figure 11, example optimal programs for each task in Section F (Figure 9), rollout visualizations in Figure 16, and additional results analysis in Section H.
  Repetitive Behaviors. Solving STAIRCLIMBER and FOURCORNER requires acquiring repetitive (or looping) behaviors. STAIRCLIMBER, which can be solved by repeating a short, 4-step stair-climbing behavior until the goal marker is reached, is not solved by DRL-abs. LEAPS fully solves the task given the same perceptions, as this behavior can be simply represented with a while loop that repeats the stair-climbing skill. However VIPER performs poorly as its decision tree cannot represent such loops. Similarly, the baselines are unable to perform as well on FOURCORNER, a task in which the agent must pickup a marker located in each corner of the grid. This behavior takes at least 14 timesteps to complete, but can be represented by two nested loops. Similar to STAIRCLIMBER, the bias introduced by the DSL and our generated dataset (which includes nested loops), results in LEAPS being able to perform much better.
  Exploration. TOPOFF rewards the agent for adding markers to locations with existing markers. However, there are no restrictions for the agent to wander elsewhere around the environment, thus making exploration a problem for the RL baselines, and thereby also constraining VIPER. LEAPS performs best on this task, as the ground-truth program can be represented by a simple loop that just moves forward and places markers when a marker is detected. MAZE also involves exploration, however its small size (8× 8) results in many methods, including LEAPS, solving the task. Complexity. Solving HARVESTER and CLEANHOUSE requires acquiring complex behaviors, resulting in poor performance from all methods. CLEANHOUSE requires an agent to navigate through a house and pick up all markers along the walls on the way. This requires repeated execution of a skill, of varied length, which navigates around the house, turns into rooms, and picks up markers. As such, all baselines perform very poorly. However, LEAPS is able to perform substantially better because these behaviors can be represented by a program of medium complexity with a while loop and some nested conditional statements. On the other hand, HARVESTER involves simply navigating to and picking up a marker on every spot on the grid. However, this is a difficult program to synthesize given our random dataset generation process; the program we manually derive to solve HARVESTER is long and more syntactically complex than most training programs. As a result, DRL and VIPER outperform LEAPS on this task.
  Learned Program Embedding Space. More analysis on our learned program embedding space can be found in the appendix. We present CEM search trajectory visualizations in Section B, demonstrating how the search population’s rewards change over time. To qualitatively investigate the smoothness of the learned program embedding space, we linearly interpolate between pairs of latent programs and display their corresponding decoded programs in Section C. In Section D, we illustrate how predicted programs evolve over the course of CEM search.
  5.6 Generalization
  We are also interested in learning whether the baselines and the programs synthesized by LEAPS can generalize to novel scenarios without further learning. Specifically, we investigate how well they can generalize to larger state spaces. We expand both STAIRCLIMBER and MAZE to 100× 100 grid sizes (from 12 × 12 and 8 × 8, respectively). We directly evaluate the
  policies or programs obtained from the original tasks with smaller state spaces for all methods except DRL (its observation space changes), which we retrain from scratch. The results are shown in Table 4. All baselines perform significantly worse than before on both tasks. On the contrary, the programs synthesized by LEAPS for the smaller task instances achieve zero-shot generalization to larger task instances without losing any performance. Larger grid size experiments for the other Karel tasks and additional unseen configuration experiments can be found in Section G.
sections.heading: 5.7 Interpretability
sections.text: Interpretability in machine learning [69, 70] is particularly crucial when it comes to learning a policy that interacts with the environment [71–78]. The proposed framework produces programmatic policies that are interpretable from the following aspects as outlined in [70].
  • Trust: interpretable machine learning methods and models may more easily be trusted since humans tend to be reluctant to trust systems that they do not understand. Programs synthesized by LEAPS can naturally be better trusted since one can simply read and interpret them. • Contestability: the program execution traces produce a chain of reasoning for each action,
  providing insights on the induced behaviors and thus allowing for contesting improper decisions. • Safety: synthesizing readable programs allows for diagnosing issues earlier (i.e. before execution)
  and provides opportunities to intervene, which is especially critical for safety-critical tasks.
  In the rest of this section, we investigate how the proposed framework enjoys interpretability from the three aforementioned aspects. Specifically, synthesized programs are not only readable to human users but also interactive, allowing non-expert users with a basic understanding of programming to diagnose and make edits to improve their performance. To demonstrate this, we asked non-expert
  humans to read, interpret, and edit suboptimal LEAPS policies to improve their performance. Participants edited LEAPS programs on 3 Karel tasks with suboptimal reward: TOPOFF, FOURCORNER, and HARVESTER. With just 3 edits, participants obtained a mean reward improvement of 97.1%, and with 5 edits, participants improved it by 125%. This justifies how our synthesized policies can be manually diagnosed and improved, a property which DRL methods lack. More details and discussion can be found in Section E.
sections.heading: 6 Discussion
sections.text: We propose a framework for solving tasks described by MDPs by producing programmatic policies that are more interpretable and generalizable than neural network policies learned by deep reinforcement learning methods. Our proposed framework adopts a flexible program representation and requires only minimal supervision compared to prior programmatic reinforcement learning and program synthesis works. Our proposed two-stage learning scheme not only alleviates the difficulty of learning to synthesize programs from scratch but also enables reusing its learned program embedding space for various tasks. The experiments demonstrate that our proposed framework outperforms DRL and programmatic baselines on a set of Karel tasks by producing expressive and generalizable programs that can consistently solve the tasks. Ablation studies justify the necessity of the proposed two-stage learning scheme as well as the effectiveness of the proposed learning objectives.
  While the proposed framework achieves promising results, we would like to acknowledge two assumptions that are implicitly made in this work. First, we assume the existence of a program executor that can produce execution traces of programs. This program executor needs to be able to return perceptions from the environment state as well as apply actions to the environment. While this assumption is widely made in program synthesis works, a program executor can still be difficult to obtain when it comes to real-world robotic tasks. Fortunately, in research fields such as computer vision or robotics, a great amount of effort has been put into satisfying this assumption such as designing modules that can return high-level abstraction of raw sensory input (e.g. with object detection networks, proximity/tactile sensors, etc.).
  Secondly, we assume that it is possible to generate a distribution of programs whose behaviors are at least remotely related to the desired behaviors for solving the tasks of interest. It can be difficult to synthesize programs which represent behaviors that are more complex than ones in the training program distribution, although one possible solution is to employ a better program generation process to generate programs that induce more complex behaviors. Also, the choice of DSL plays an important role in how complex the programs can be. Ideally, employing a more complex DSL would allow our proposed framework to synthesize more advanced agent behaviors.
  In the future, we hope to extend the proposed framework to more challenging domains such realworld robotics. We believe this framework would allow for deploying robust, interpretable policies for safety-critical tasks such as robotic surgeries. One way to make LEAPS applicable to robotics domains would be to simultaneously learn perception modules and action controllers. Other possible solutions include incorporating program execution methods [79–84] that are designed to allow program execution or designing DSLs that allow pre-training of perception modules and action controllers. Also, the proposed framework shares some characteristics with works in multi-task RL [79, 80, 85–89] and meta-learning [90–99]. Specifically, it learns a program embedding space from a distribution of tasks/programs. Once the program embedding space is learned, it can be be reused to solve different tasks without retraining.
  Yet, extending LEAPS to such domains can potentially lead to some negative societal impacts. For example, our framework can still capture unintended bias during learning or suffer from adversarial attacks. Furthermore, policies deployed in the real world can create great economic impact by causing job losses in some sectors. Therefore, we would encourage further work to investigate the biases, safety issues, and potential economic impacts to ensure that the deployment in the field does not cause far-reaching, negative societal impacts.
sections.heading: Acknowledgments
sections.text: The authors appreciate the fruitful discussions with Karl Pertsch, Youngwoon Lee, Ayush Jain, and Grace Zhang. The authors would like to thank Ting-Yu S. Su for contributing to the learned
  program embedding spaces visualizations. The authors are grateful to Sidhant Kaushik, Laura Smith, and Siddharth Verma for offering their time to participate in the human debugging interpretability experiment.
  Funding Transparency Statement
  This project was partially supported by USC startup funding and by NAVER AI Lab.
title: Learning to Synthesize Programs as Interpretable and Generalizable Policies