The value of sequential information in shortest path optimization
Michael Rinehart, Munther A. Dahleh · 2010
Consider an agent who seeks to traverse the shortest path in a graph having random edge weights. If the agent has no side information about the realizations of the edge weights, it should simply take the path of least average length, a deterministic optimization. We consider a generalization of this framework whereby the agent has access to a limited amount of side information about the edge weights as it traverses the graph. Specifically, we define a notion of side information and capacity, and we provide bounds on the agent's performance relative to the total amount of side information it receives. The results are based in a graph reduction for shortest path optimization and an abstraction of sequential decision-making.