Timezone: »
This paper considers the problem of efficient exploration of unseen environments, a key challenge in AI. We propose a learning to explore' framework where we learn a policy from a distribution of environments. At test time, presented with an unseen environment from the same distribution, the policy aims to generalize the exploration strategy to visit the maximum number of unique states in a limited number of steps. We particularly focus on environments with graph-structured state-spaces that are encountered in many important real-world applications like software testing and map building.
We formulate this task as a reinforcement learning problem where the
exploration' agent is rewarded for transitioning to previously unseen environment states and employ a graph-structured memory to encode the agent's past trajectory. Experimental results demonstrate that our approach is extremely effective for exploration of spatial maps; and when applied on the challenging problems of coverage-guided software-testing of domain-specific programs and real-world mobile applications, it outperforms methods that have been hand-engineered by human experts.
Author Information
Hanjun Dai (Georgia Tech)
Yujia Li (DeepMind)
Chenglong Wang (University of Washington)
Rishabh Singh (Google Brain)
Po-Sen Huang (DeepMind)
Pushmeet Kohli (DeepMind)
More from the Same Authors
-
2021 : Inferring a Continuous Distribution of Atom Coordinates from Cryo-EM Images using VAEs »
Dan Rosenbaum · Marta Garnelo · Michal Zielinski · Charles Beattie · Ellen Clancy · Andrea Huber · Pushmeet Kohli · Andrew Senior · John Jumper · Carl Doersch · S. M. Ali Eslami · Olaf Ronneberger · Jonas Adler -
2022 Spotlight: Fault-Aware Neural Code Rankers »
Jeevana Priya Inala · Chenglong Wang · Mei Yang · Andres Codas · Mark Encarnación · Shuvendu Lahiri · Madanlal Musuvathi · Jianfeng Gao -
2022 : Panel »
Jeevana Priya Inala · Pushmeet Kohli · Ann Kennedy · Sriram Rajamani · Yisong Yue -
2022 Poster: Fault-Aware Neural Code Rankers »
Jeevana Priya Inala · Chenglong Wang · Mei Yang · Andres Codas · Mark Encarnación · Shuvendu Lahiri · Madanlal Musuvathi · Jianfeng Gao -
2021 : Inferring a Continuous Distribution of Atom Coordinates from Cryo-EM Images using VAEs »
Dan Rosenbaum · Marta Garnelo · Michal Zielinski · Charles Beattie · Ellen Clancy · Andrea Huber · Pushmeet Kohli · Andrew Senior · John Jumper · Carl Doersch · S. M. Ali Eslami · Olaf Ronneberger · Jonas Adler -
2021 : Live Panel »
Max Welling · Bharath Ramsundar · Irina Rish · Karianne J Bergen · Pushmeet Kohli -
2021 Poster: Learning Semantic Representations to Verify Hardware Designs »
Shobha Vasudevan · Wenjie (Joe) Jiang · David Bieber · Rishabh Singh · hamid shojaei · C. Richard Ho · Charles Sutton -
2020 Poster: Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration »
Hanjun Dai · Rishabh Singh · Bo Dai · Charles Sutton · Dale Schuurmans -
2020 Poster: Training Generative Adversarial Networks by Solving Ordinary Differential Equations »
Chongli Qin · Yan Wu · Jost Tobias Springenberg · Andy Brock · Jeff Donahue · Timothy Lillicrap · Pushmeet Kohli -
2020 Poster: Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming »
Sumanth Dathathri · Krishnamurthy Dvijotham · Alexey Kurakin · Aditi Raghunathan · Jonathan Uesato · Rudy Bunel · Shreya Shankar · Jacob Steinhardt · Ian Goodfellow · Percy Liang · Pushmeet Kohli -
2020 Spotlight: Training Generative Adversarial Networks by Solving Ordinary Differential Equations »
Chongli Qin · Yan Wu · Jost Tobias Springenberg · Andy Brock · Jeff Donahue · Timothy Lillicrap · Pushmeet Kohli -
2020 Poster: The Autoencoding Variational Autoencoder »
Taylan Cemgil · Sumedh Ghaisas · Krishnamurthy Dvijotham · Sven Gowal · Pushmeet Kohli -
2020 Spotlight: The Autoencoding Variational Autoencoder »
Taylan Cemgil · Sumedh Ghaisas · Krishnamurthy Dvijotham · Sven Gowal · Pushmeet Kohli -
2019 : Contributed Talk: Neural-Guided Symbolic Regression with Asymptotic Constraints »
Rishabh Singh -
2019 Poster: Are Labels Required for Improving Adversarial Robustness? »
Jean-Baptiste Alayrac · Jonathan Uesato · Po-Sen Huang · Alhussein Fawzi · Robert Stanforth · Pushmeet Kohli -
2019 Poster: Adversarial Robustness through Local Linearization »
Chongli Qin · James Martens · Sven Gowal · Dilip Krishnan · Krishnamurthy Dvijotham · Alhussein Fawzi · Soham De · Robert Stanforth · Pushmeet Kohli -
2019 Poster: Retrosynthesis Prediction with Conditional Graph Logic Network »
Hanjun Dai · Chengtao Li · Connor Coley · Bo Dai · Le Song -
2019 Poster: Efficient Graph Generation with Graph Recurrent Attention Networks »
Renjie Liao · Yujia Li · Yang Song · Shenlong Wang · Will Hamilton · David Duvenaud · Raquel Urtasun · Richard Zemel -
2018 Poster: A Unified View of Piecewise Linear Neural Network Verification »
Rudy Bunel · Ilker Turkaslan · Philip Torr · Pushmeet Kohli · Pawan K Mudigonda -
2018 Poster: Learning Loop Invariants for Program Verification »
Xujie Si · Hanjun Dai · Mukund Raghothaman · Mayur Naik · Le Song -
2018 Spotlight: Learning Loop Invariants for Program Verification »
Xujie Si · Hanjun Dai · Mukund Raghothaman · Mayur Naik · Le Song -
2018 Poster: Cooperative neural networks (CoNN): Exploiting prior independence structure for improved classification »
Harsh Shrivastava · Eugene Bart · Bob Price · Hanjun Dai · Bo Dai · Srinivas Aluru -
2018 Poster: Coupled Variational Bayes via Optimization Embedding »
Bo Dai · Hanjun Dai · Niao He · Weiyang Liu · Zhen Liu · Jianshu Chen · Lin Xiao · Le Song -
2018 Poster: M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search »
Yelong Shen · Jianshu Chen · Po-Sen Huang · Yuqing Guo · Jianfeng Gao -
2018 Poster: Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding »
Kexin Yi · Jiajun Wu · Chuang Gan · Antonio Torralba · Pushmeet Kohli · Josh Tenenbaum -
2018 Spotlight: Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding »
Kexin Yi · Jiajun Wu · Chuang Gan · Antonio Torralba · Pushmeet Kohli · Josh Tenenbaum -
2018 Poster: Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections »
Xin Zhang · Armando Solar-Lezama · Rishabh Singh -
2017 Poster: Imagination-Augmented Agents for Deep Reinforcement Learning »
Sébastien Racanière · Theophane Weber · David Reichert · Lars Buesing · Arthur Guez · Danilo Jimenez Rezende · Adrià Puigdomènech Badia · Oriol Vinyals · Nicolas Heess · Yujia Li · Razvan Pascanu · Peter Battaglia · Demis Hassabis · David Silver · Daan Wierstra -
2017 Poster: Learning Combinatorial Optimization Algorithms over Graphs »
Elias Khalil · Hanjun Dai · Yuyu Zhang · Bistra Dilkina · Le Song -
2017 Spotlight: Learning Combinatorial Optimization Algorithms over Graphs »
Elias Khalil · Hanjun Dai · Yuyu Zhang · Bistra Dilkina · Le Song -
2017 Oral: Imagination-Augmented Agents for Deep Reinforcement Learning »
Sébastien Racanière · Theophane Weber · David Reichert · Lars Buesing · Arthur Guez · Danilo Jimenez Rezende · Adrià Puigdomènech Badia · Oriol Vinyals · Nicolas Heess · Yujia Li · Razvan Pascanu · Peter Battaglia · Demis Hassabis · David Silver · Daan Wierstra -
2015 Poster: M-Statistic for Kernel Change-Point Detection »
Shuang Li · Yao Xie · Hanjun Dai · Le Song