PaperlayerView exact revision on arXiv

Source-linked AI summary

Value Iteration Networks

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

arXiv:1602.02867v4cs.AIcs.LGcs.NEstat.ML

TL;DR

Reactive policies often lack explicit planning and may generalize poorly to unseen task instances. The paper introduces VIN, which embeds a differentiable approximation of value iteration as a CNN and trains it end-to-end. Across grid-world, continuous-control, and natural-language tasks, VIN policies generalize better to new unseen instances.

  • Problem

    Deep RL policy architectures rarely investigate explicit planning or the generalization of trained policies beyond their training domains.

  • Method

    VIN embeds a differentiable approximation of value iteration within a neural-network policy, learning an auxiliary planning computation jointly with the policy.

  • Results

    VIN policies generalize better to new, unseen task instances across visual, continuous-control, and natural-language decision tasks.

  • Takeaways & Limitations

    Learning an explicit planning computation provides a policy representation that improves generalization across diverse task settings.

  • Takeaways & Limitations

    VIN requires designing an auxiliary MDP whose optimal plan contains useful information about the original task’s optimal policy, without assuming that auxiliary MDP is known in advance.

Abstract

from arXiv · show

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.

1 Introduction

Deep RL policies often rely on reactive CNN architectures that lack explicit planning and generalize poorly beyond training domains. VIN addresses this gap by embedding a differentiable planning computation, enabling policies that generalize better to unseen task instances.

  • Reactive CNN policies can solve training-domain sequential tasks but lack explicit planning computation.Their apparent long-term reasoning comes from learning action choices with good consequences in the training domain.
  • Standard CNN policies trained on obstacle maps do not generalize well to unseen grid-world configurations.The authors attribute this limitation to their failure to understand the goal-directed nature of behavior.
  • A reactive policy could represent optimal behavior with enough coverage and capacity, but this may require too much training data in practice.The proposed alternative exploits a flexible prior about the planning computation underlying behavior.
  • VIN is a neural-network policy with a differentiable planning program embedded within its architecture.The model is introduced specifically to learn to plan.
  • Value iteration can be represented as a CNN module that is trained end-to-end with standard backpropagation.Embedding the module in a feed-forward network supports integration with perception and control.
  • Across visual, continuous-control, and natural-language decision tasks, VIN policies generalize better to new, unseen task instances.The paper evaluates VIN within standard reinforcement-learning and imitation-learning algorithms.

2 Background

The paper frames sequential decision making through MDPs, value functions, and value iteration, then contrasts these planning concepts with differentiable CNN and policy-learning foundations. RL and IL differ in supervision, but both can use differentiable policy representations.

  • An MDP specifies states, actions, rewards, and transition probabilities for sequential decision making.A policy maps states to actions, while transitions describe the next-state distribution.
  • The optimal value function is the greatest expected discounted return achievable from a state.An optimal policy attains this value for every state.
  • Value iteration repeatedly computes action values from rewards and successor-state values, then takes the maximum over actions.As iterations increase, the value function converges to the optimal value function.
  • CNNs apply stacked convolution and max-pooling operations to multidimensional inputs such as images.They are commonly trained with stochastic gradient descent and backpropagation.
  • RL learns from interaction-generated rewards and transitions, whereas IL learns from expert supervision.Both settings can use differentiable policy representations optimized by gradient-based algorithms.

3 The Value Iteration Network Model

VIN embeds an explicit planning module into a policy by learning an auxiliary MDP and implementing approximate value iteration as a differentiable CNN. The resulting value features guide a reactive policy and can be trained end-to-end.

  • Planning-based policy representation: VIN learns an auxiliary MDP whose reward and transition functions depend on the original state observation.The auxiliary MDP need not be known in advance; its parameters are learned as part of policy training.
  • Planning-based policy representation: In grid worlds, learned auxiliary rewards can favor goals and penalize obstacles even when they do not equal the task’s true rewards and transitions.An optimal plan in the auxiliary MDP can still produce a useful obstacle-avoiding route to the goal.
  • Planning-based policy representation: Local connectivity lets the policy attend only to the subset of value-function states relevant to each action.This reduces the effective number of features used for a given action prediction.
  • Planning-based policy representation: The planning-based policy representation combines a planner’s value-function features with a reactive policy.An attention module selects relevant value features before they are supplied to the reactive policy.
  • The VI module: The VI module implements each value-iteration step as convolution over rewards and values followed by max-pooling across action channels.Each convolution channel represents an action-specific Q-function, and recurrent application performs K iterations.
  • The VI module: The differentiable VI module allows auxiliary MDP parameters and reward functions to be learned through backpropagation.It can also be composed hierarchically by using one module’s value as input to another.
  • VIN design: A VIN consists of the VI module together with specified planning state and action spaces, reward and transition functions, and an attention function.These components may be parameterized and trained jointly with the policy.
  • VIN design: VINs are implemented as CNNs and are evaluated for improved generalization after learning to plan.The paper reports that the experimental implementations required only several lines of Theano code.

4 Experiments

The experiments test whether VINs can learn planning computations with standard learning algorithms and generalize beyond training domains across discrete, visual, continuous, and language-based tasks.

  • The experiments ask whether VINs learn planning with standard RL and IL algorithms and whether this improves generalization over reactive policies.
  • 4.1 Grid-World Domain: Synthetic grid-world policies are trained from optimal-policy demonstrations, with a planning MDP whose reward map is learned from image input.The supplementary material reports similar findings for additional RL experiments.
  • 4.1 Grid-World Domain: VIN policies significantly outperform reactive networks across grid-world sizes, with the performance gap increasing dramatically as problem size grows.Prediction loss is comparable between reactive policies and VINs, while reactive success rates are significantly worse.
  • 4.2 Mars Rover Navigation: 84.8% success was achieved by VIN on Mars terrain images, compared with 90.3% for a planner using obstacle classifications from a separately trained image classifier.The VIN did not receive elevation data or ground-truth obstacle labels during training or testing.
  • 4.3 Continuous Control: Continuous control uses high-level planning on a coarse discrete grid combined with low-level control over continuous states and actions.The task requires planning trajectories around or using obstacles while controlling a particle with mass and inertia.
  • 4.4 WebNav Challenge: WebNav evaluates navigation through website links toward a queried goal, contrasting a reactive word-embedding policy with a VIN-based planning approach.The experiments use the Wikipedia for Schools website, which contains over 6000 pages and at most 292 links per page.

5 Conclusion and Outlook

VIN policies learn approximate planning computations relevant to tasks ranging from gridworld navigation to continuous control and Wikipedia-link navigation, and these computations lead to better generalization.

  • VIN policies learn approximate task-relevant planning computations that lead to better generalization across gridworlds, continuous control, and Wikipedia-link navigation.The authors propose future planning computations based on simulation or optimal linear control.

A Visualization of Learned Reward and Value

The visualization shows how the VIN represents obstacles, goals, and intermediate locations in learned reward and value functions.

  • The learned reward is strongly negative at obstacles, strongly positive at the goal, and slightly negative elsewhere.
  • The resulting value function peaks at the goal and forms a gradient pointing toward it around obstacles.This pattern is presented as evidence that the VI block learned a useful planning computation.

B Weight Sharing

VINs use shared weights across recurrent value-iteration layers, and untying those weights reduces performance, especially with less training data.

  • B Weight Sharing: Untying weights in the VIN’s K recurrent layers degrades performance relative to shared weights.The comparison evaluates the effect of shared VI-module weights on the 16 × 16 grid-world domain.
  • B Weight Sharing: The degradation from untying weights is stronger when the training set is smaller.

C Gridworld with Reinforcement Learning

The grid-world experiment compares VIN and CNN policies trained on the same randomly generated maps and evaluated on held-out test maps using success rate.

  • C Gridworld with Reinforcement Learning: VIN and CNN policies are trained on the same randomly generated grid-world maps and then evaluated on a held-out test set.
  • C Gridworld with Reinforcement Learning: K is set to 10 for 8 × 8 maps and 20 for 16 × 16 maps.The convolutional-network structure is adapted to the map size.
  • C Gridworld with Reinforcement Learning: Testing reports the proportion of successful trials for each network, where success means reaching the goal on a test map.Exact rewards are ignored during testing.

D Technical Details for Experiments

The experiments use grid-world trajectories, map-processing networks, recurrent VIN settings, and CNN or FCN baselines, with performance tracked across training and test-map difficulty.

  • D Technical Details for Experiments: Figure 6 reports VIN and CNN performance on 16 × 16 test maps as training increases and map difficulty rises.
  • D Technical Details for Experiments: The grid-world training set contains 5,000 random instances and 7 optimal shortest-path trajectories per instance.Each state observation encodes the agent state, obstacle map, and goal position, with an optimal action label.
  • D Technical Details for Experiments: The VIN reward-mapping network uses obstacle-and-goal images to produce a reward image through two convolutional layers.The first layer has 150 3 × 3 kernels, followed by one 3 × 3 output filter.
  • D Technical Details for Experiments: VIN recurrence depth is K = 10, 20, or 36 for 8 × 8, 16 × 16, or 28 × 28 domains, respectively.These values keep the network small while allowing goal information to flow across the map.
  • D Technical Details for Experiments: The CNN baseline uses map-size-specific convolutional and fully connected layers, while the FCN baseline assigns an action label to each image location.

D.2 Mars Domain

The Mars-domain experiment models rover navigation over terrain while avoiding grid cells containing slopes of 10 degrees or more.

  • D.2 Mars Domain: The experiment uses HiRISE terrain imagery and elevation data to plan long-distance rover trajectories that avoid steep slopes.A 33.3 km by 6.3 km Mars area is divided into 128 × 128 image patches and a 16 × 16 grid-world.

D.3 Continuous Control

The continuous-control evaluation uses guided policy search with unknown dynamics and compares VINs under matched training conditions. The Mars results indicate that VINs approach a planner trained with labeled obstacle data without using obstacle labels.

  • Training setup: Guided policy search with unknown dynamics trains time-varying iLQG controllers and fits them to a single neural-network policy.The experiments use publicly available GPS code and MuJoCo simulation.
  • Mars evaluation: VIN performance on Mars is compared with a planner using obstacle predictions trained from labeled obstacle data.That planner is presented as an upper bound because identifying obstacles from raw images is difficult.
  • Mars evaluation: VINs achieve close performance to the labeled-obstacle planner without access to labeled obstacle data.
  • Training setup: 10 iLQG iterations followed by one neural-network fitting iteration provide a comparison without GPS-specific effects.The cost is quadratic distance to the goal.

D.4 WebNav

The WebNav setup treats website navigation as goal-directed movement through a directed graph, using page and query features to choose links. VIN planning is combined with a baseline policy, while runtime is notably higher for the language task in the reported implementation.

  • Task setup: WebNav asks an agent to reach a target page from a starting page by clicking at most four links per page.The query contains four sentences, the target is at most four hops away, and reward is given for a path no longer than 10 hops.
  • Task setup: The agent represents each page and query with bag-of-words features and pretrained word embeddings, then selects valid outgoing links.The action set consists of linked successor pages from the current page.
  • Model: The baseline uses a single tanh-layer neural network, and the VIN model combines the VI module and baseline by adding their outputs.
  • Model: The WebNav VIN performs value iteration on a smaller approximate website graph, with learned rewards, fixed graph transitions, attention over the value function, and a query- and state-dependent coefficient.
  • Reported evaluations: The supplied materials identify performance tables for the full Wikipedia dataset and HVIN grid-world evaluation but provide no numerical results.
  • Runtime: VINs are considerably slower than baselines on the language task because the implementation lacks GPU support for graph convolutions and sparse operations.In contrast, shared VI computations make VINs not much slower than baselines in the 2D domains.
  • Planning depth: The required number of VI iterations depends on problem size: at least L iterations are needed to propagate a goal L steps away.With fewer iterations, the action prediction at the state has not received the goal information.
  • Hierarchical planning: A hierarchical VI network forms a coarse value function at an upper level and feeds its up-sampled output into a lower-level reward layer.
Loading 1602.02867v4…