Distributed Value Iteration: A New Approach for Optimization?
Professor Ben Van Roy
Stanford University
Consider an optimization problem in which decision variables are associated with vertices of an undirected graph and the objective function is a sum of “clique functions,” each depending only on the subset of variables associated with a clique. So-called nonserial dynamic programs offer a useful formulation that complements mainstream areas of optimization such as linear, convex, and dynamic programming. However, nonserial dynamic programming is intractable, even when clique sizes are at most two.
This talk will be about distributed value iteration, a heuristic that has demonstrated promise as an efficient algorithm for a number of nonserial dynamic programs. I will present existing general results along with a recent study of the algorithm applied in a specific context involving distributed averaging. I will also speculate on the role that distributed value iteration might play in the future of optimization.