Value Iteration Networks

Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, Pieter Abbeel

Seminal February 2016

TL;DR VIN builds value iteration into a policy network as a recurrent convolution, so the policy learns a model to plan on and is trained end-to-end with ordinary imitation learning or RL. On unseen 28x28 grid-worlds it reaches the goal 97% of the time, against 74% for a CNN policy.

What they do

Deep RL policies are usually reactive: CNN features map straight to actions, with no planning step. A value iteration network (VIN) puts a differentiable form of value iteration inside the policy. It learns a planning MDP from the observation, solves it, and uses the values to act. The question is whether this generalizes to unseen maps better than reactive networks.

How it works

Learned planning MDP. The reward R̄ = f_R(φ(s)) and the transitions P̄ = f_P(φ(s)) are trainable. They need not match the true task.
VI module. One VI iteration is a convolution over the reward and value maps, with one Q channel per action, followed by a max over actions. It repeats K times with shared weights (K = 10, 20, 36 for 8x8, 16x16, 28x28 grids).
Attention. Only the values near the agent reach the reactive policy: its own cell’s Q-values, or a 5x5 value patch in continuous control.
Coarse plans. The VIN plans on a 16x16 grid for continuous control and on a category graph (under 3% of the site) for WebNav.

Results

Grid-world, imitation learning. On 8x8, 16x16 and 28x28 maps, VIN succeeds 99.6%, 99.3% and 97% of the time. A CNN gets 97.9%, 87.6% and 74.2%. With untied recurrent weights, 16x16 success drops to 91.9–95.6%.
Grid-world, RL with TRPO. VIN 90.9% vs CNN 86.9% at 8x8, and 82.5% vs 33.1% at 16x16.
Mars terrain images. VIN reaches 84.8% with no obstacle labels. A planner on a label-trained obstacle classifier reaches 90.3%.
Continuous control and WebNav. Test distance to goal is 0.35 for VIN vs 0.59 for the CNN. On WebNav from random start pages, VIN succeeds on 346 of 4000 queries vs 304 for the baseline. From the root it is 1030 vs 1025 of 2000.

Limitations

The planning space, reward and transition maps, and attention are designed by hand for each task. K must grow with map size. On the language task VINs were considerably slower than the baseline. Starting from the WebNav root, VIN barely beats the reactive baseline.

Figures

From Figure 2: A general policy representation that adds value-function features from a planner to a reactive policy.

From Figure 3: A random 28x28 synthetic grid-world, with the VIN-predicted trajectory and the ground-truth shortest p... — From Figure 3: A random 28x28 synthetic grid-world, with the VIN-predicted trajectory and the ground-truth shortest path between random start and goal positions.

From Figure 3: A Mars terrain image with the VIN-predicted trajectory (purple line with cross markers) and the ground... — From Figure 3: A Mars terrain image with the VIN-predicted trajectory (purple line with cross markers) and the ground-truth shortest path (blue line).

From Figure 4: Trajectories predicted by VIN and CNN on a test domain of the continuous control task.

Abstract

We introduce the value iteration network (VIN): a fully differentiable neural network with a `planning module' embedded within. VINs can learn to plan, and are suitable for predicting outcomes that involve planning-based reasoning, such as policies for reinforcement learning. Key to our approach is a novel differentiable approximation of the value-iteration algorithm, which can be represented as a convolutional neural network, and trained end-to-end using standard backpropagation. We evaluate VIN based policies on discrete and continuous path-planning domains, and on a natural-language based search task. We show that by learning an explicit planning computation, VIN policies generalize better to new, unseen domains.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.

Matt Strong