Learning Transferable Graph Exploration
Hanjun Dai · Yujia Li · Chenglong Wang · Rishabh Singh · Po-Sen Huang · Pushmeet Kohli

Thu Dec 12th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #166

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 theexploration' 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