Value Iteration Networks
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.
The paper presents a view of value iteration that links it to a convolutional layer in a neural network. This observation is exploited in a NN architecture that has multiple layers that effectively perform depth-limited VI, the parameters of which specify the MDP on which the planning will occur. In this way, the network learns to construct MDPs for short-term planning based on the current state of the real system. Experiments demonstrate that this approach allows the agent to generalize more effectively over many instances of navigation problems.
***After Author Response***  I was literally just complaining about reviewers that say "Add the kitchen sink" without regard for the research cost or for the impact on clarity in the paper, and here I am being that reviewer! The authors are right to call me on that. I agree that the paper has plenty going on as it is (and said as much in my original review). At the time I was erroneously thinking one could simply take the same architecture as the VIN, but train the model using prediction error rather than the policy gradient. I see now that I hadn't thought it all the way through -- the VIN model does not have the same state space as the world, so it's not clear what the error signal would even be. Rather than suggesting an additional impractical empirical comparison, I should have instead suggested that the paper back off a bit from its dismissal of model-based RL. In general, I agree that MBRL is a challenge, but it may be that the domains that are ideal for VIN are also viable for MBRL. I think that's an open question, and could be presented as such.  I have to admit that I did not follow the "constant domain observation" explanation. I might have missed something. In any case, I think runtime bears at least a little bit of discussion. If there's really no room for it, maybe it can go in the appendix.  I'm genuinely surprised that VIN helps early in learning, but that's really cool, and worth reporting.  ---Technical Quality---  The claims of the paper seemed to be technically sound and the experiments were well-designed.  I will say that I am not sure I am totally on board with the phrase "learns to plan." I think one could argue that the actual planning process is still fixed (it is the VI-like process, defined by the K convolution+max layers). What the network learns are model parameters for which the planning process yields useful results. "Learns to plan" almost implies that it has to learn about value iteration itself, which is not the case.  There was also a claim that I felt was a little under-supported. The paper waves off model-based learning because it can be hard to learn accurate dynamics. I think this is fair to say. *However*, in the particular domains the paper considers, I'm not convinced that a model would be harder to learn than the VIN. The navigation tasks all have the same flavor where the local dynamics are very simple. Presumably this is why the VIN gets any traction at all. I would imagine that a conv-net would be ideally suited to learning in these problems. I recognize that space is limited and I think there is plenty in this paper to chew on. Still, I did wish that this approach had been compared to the clear alternative approach of simply training a convolutional dynamics model and performing value iteration on that to obtain a policy. This would answer the question of whether a VIN is actually easier to learn than a dynamics model. If this approach could be demonstrated to perform robustly in domains where the more traditional model-based approach fails, that would significantly strengthen this case.  I have one other small technical quibble, and it only seems to be directly relevant to the supplementary material. When describing the grid world experiment, the text seems to suggest that the VIN statespace \bar{S} and the real statespace S are similar. The implication seems to be that S is a 2D grid (i.e. only the agent's position). Actually, of course, a state in S contains *both* the agent's position *and* the arrangement of the obstacles. \bar{S} is actually far simpler than S, which is important for the success of the VIN, I suspect.   ---Novelty---  I found the idea of the VIN to be highly novel and interesting. The idea that a planner might generate a temporary, locally useful model is not in itself new, but I don't believe I have seen an approach that learns *how* to construct such a model from experience. I also found the link between convolution and value iteration on a locally connected MDP to be a fresh view of familiar constructs.  The paper did connect to some earlier work that the authors might consider mentioning. Both pieces of work I'm thinking of use policy gradient to directly adapt model parameters rather than trying to learn the most accurate model. Sorg et al. (NIPS 2010) does this with the reward model and Joseph et al. (ICRA 2013) does it with the dynamics model. There's been follow-up at least to the Sorg work (Guo et al., IJCAI 2016). Like this work, they treat the model-based architecture as just a complicated parameterization of the policy and adapt the whole thing with model-free learning. This work is definitely distinct in several ways, but I think there is a kinship with these existing ideas.  ---Impact---  I think this paper has substantial potential for impact. I can easily see this particular algorithm being further explored/applied in other domains. I also believe that the core idea of *learning* to map complicated observations into simple models for the sake of short-horizon planning is potentially very insightful, and one that seems likely to inspire follow-up work.  I will say that I wish the paper had a little more room to discuss the weaknesses/challenges of this approach. For instance... - The paper does not discuss runtime, but I assume that the VIN module adds a *lot* of computational expense. - Though f_R and f_P can be adapted over time, the experiments performed here did incorporate a great deal of domain knowledge into their structure. A less informed f_R/f_P might require an impractical amount of data to learn. - The results are only reported after a bunch of training has occurred, but in RL we are often also interested in how the agent behaves *while* learning. I presume that early in training the model parameters are essentially garbage and the planning component of the network might actually *hurt* more than it helps. This is pure speculation, but I wonder if the CNN is able to perform reasonably well with less data. - I wonder whether more could be said about when this approach is likely to be most effective. The navigation domains all have a similar property where the *dynamics* follow relatively simple, locally comprehensible rules, and the state is only complicated due to the combinatorial number of arrangements of those local dynamics. WebNav is less clear, but then the benefit of this approach is also more modest. In what kinds of problems would this approach be inappropriate to apply?  ---Clarity---  I found the paper to be clear and highly readable. I thought it did a good job of motivating the approach and also clearly explaining the work at both a high level and a technical level.  I thought the results presented in the main text were sufficient to make the paper's case, and the additional details and results presented in the supplementary materials were a good compliment. This is a small point, but as a reader I personally don't like the supplementary appendix to be an entire long version of the paper; it makes it harder to simply flip to the information I want to look up. I would suggest simply taking the appendices from that document and putting them up on their own.  ---Summary of Review---  I think this paper presents a clever, thought-provoking idea that has the potential for practical impact. I think it would be of significant interest to a substantial portion of the NIPS audience and I recommend that it be accepted.