The On-Line Shortest Path Problem Under Partial Monitoring

By Pál Benkö, Géza Kós, T. Várady, L. Andor, Ralph Robert Martin. Journal of machine learning research, 2007

363 citations recorded by the source corpus.

The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change 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 (defined 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 weights of those edges that belong to the chosen path. For this problem, an algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire 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 complexity that is linear in the number of rounds n (i.e., the average complexity per round is constant) and in the number of edges. An extension to the so-called label efficient setting is also given, in which the decision maker is informed about the weights 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 path, a generalization of the problem of tracking the best expert. A version of the multi-armed bandit 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.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/65b6827d2415770a5f30cf3bd65a2946c3de4b0b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

The Price of Bandit Information for Online Optimization (2007, neutral): “There is only one (non-trivial) special case [Gyorgy et al., 2007] in the literature where an O * (poly(n) √ T ) regret has been established, and this case assumes significantly more feedback than in the partial information case — their result is for Path Planning (where D is the set of paths on a…”
Bandit Algorithms (2020, methodology): “Hazan and Kale [2011] gave an algorithm for which Rn = O(k2 √ Qn), which can be better than the worst-case bound of Exp3 or Exp3-IX when the quadratic variation is very small.”
Minimax Policies for Combinatorial Prediction Games (2011, methodology): “Up to the numerical constant, the result concerning ( EXP 2, L ∞ ) appeared in Gy¨orgy et al. (2007) in the context of the online shortest path problem.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The problem of playing a game repeatedly, now a classical topic in game theory, was initiated by the groundbreaking work of James Hannan and David Blackwell.”
High-Probability Regret Bounds for Bandit Online Linear Optimization (2008, methodology): “The algorithm with the best regret guarantee so far is by Gy¨orgy et al. [11].”
Combinatorial Bandits (2012, background): “There has been a flurry of activity to address versions of the adversarial bandit problem for large and structured classes of experts, see Awerbuch and Kleinberg [3], McMahan and Blum [16], Dani and Hayes [8], György, Linder, Lugosi, and Ottucsák [10], Dani, Hayes, and Kakade [7], Abernethy, Hazan, ”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “…we can view a single coordinate of the loss vector, but doesn’t apply as-is when we can view more than one coordinate (as in semi-bandit feedback [35, 6], bandits with side observations [42], or prediction with limited advice [50]), receive a linear projection (as in bandit linear optimization),…”
Non-Stochastic Bandit Slate Problems (2010, result): “1 This setting is similar to that of Gy¨orgy, Linder, Lugosi and Ottucs´ak [10] in that the cost of all actions in the chosen slate are revealed, rather than just the total cost of the slate.”