The on-line shortest path problem under partial monitoring

The on-line shortest path problem is considered under various mode ls of partial monitoring. Given a weighted directed acyclic graph whose edge weights can c hange in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defin ed as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the w eights of those edges that belong to the chosen path. For this problem, an algorithm is given who se average cumulative loss in n rounds exceeds that of the best path, matched off-line to the ent ire sequence of the edge weights, by a quantity that is proportional to 1 / n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with linear complexity in the number of rounds n and in the number of edges. An extension to the so-called label efficie nt setting is also given, in which the decision maker is informed about the w eights of the edges corresponding to the chosen path at a total of m n time instances. Another extension is shown where the decision maker competes against a time-varying pa th, a generalization of the problem of tracking the best expert. A version of the multi-armed b andit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented.