The value of information in shortest path optimization/

[摘要] (cont.) Specifically, we consider an agent that seeks to traverse the shortest path of a graph subject to some side information it receives about the edge weights in advance of and during its travel. In this setting, decision quality is determined by the average length of the paths the agent chooses, not how often the agent decodes the optimal path. For this application, we define and quantify a notion of information that is compatible with this problem, bound the performance of the agent subject to a bound on the amount of information available to it, study the impact of spreading information sequentially over partial decisions, and provide algorithms for information optimization. Meaningful, analytic performance bounds and practical algorithms for information optimization are obtained by leveraging a new type of geometric graph reduction for shortest path optimization as well as an abstraction of the geometry of sequential decision making.

[发布机构] Massachusetts Institute of Technology