  As deep learning continues to make progress for challenging perception tasks,
there is increased interest in combining vision, language, and decision-making.
Specifically, the Vision and Language Navigation (VLN) task involves navigating
to a goal purely from language instructions and visual information without
explicit knowledge of the goal. Recent successful approaches have made in-roads
in achieving good success rates for this task but rely on beam search, which
thoroughly explores a large number of trajectories and is unrealistic for
applications such as robotics. In this paper, inspired by the intuition of
viewing the problem as search on a navigation graph, we propose to use a
progress monitor developed in prior work as a learnable heuristic for search.
We then propose two modules incorporated into an end-to-end architecture: 1) A
learned mechanism to perform backtracking, which decides whether to continue
moving forward or roll back to a previous state (Regret Module) and 2) A
mechanism to help the agent decide which direction to go next by showing
directions that are visited and their associated progress estimate (Progress
Marker). Combined, the proposed approach significantly outperforms current
state-of-the-art methods using greedy action selection, with 5% absolute
improvement on the test server in success rates, and more importantly 8% on
success rates normalized by the path length. Our code is available at
https://github.com/chihyaoma/regretful-agent .
