Adaptive routing with end-to-end feedback: distributed learning and geometric approaches

ABSTRACT

Minimal delay routing is a fundamental task in networks. Since delays depend on the (potentially unpredictable) traffic distribution, online delay optimization can be quite challenging. While uncertainty about the current network delays may make the current routing choices sub-optimal, the algorithm can nevertheless try to learn the traffic patterns and keep adapting its choice of routing paths so as to perform nearly as well as the best static path. This online shortest path problem is a special case of online linear optimization, a problem in which an online algorithm must choose, in each round, a strategy from some compact set S ⊆ R^d so as to try to minimize a linear cost function which is only revealed at the end of the round. Kalai and Vempala[4] gave an algorithm for such problems in the transparent feedback model, where the entire cost function is revealed at the end of the round. Here we present an algorithm for online linear optimization in the more challenging opaque feedback model, in which only the cost of the chosen strategy is revealed at the end of the round. In the special case of shortest paths, opaque feedback corresponds to the notion that in each round the algorithm learns only the end-to-end cost of the chosen path, not the cost of every edge in the network.We also present a second algorithm for online shortest paths, which solves the shortest-path problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs better than the first, as measured by their additive regret.

REFERENCES

• 1: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.322, October 23-25, 1995
• 2: Baruch Awerbuch and Yishay Mansour. Online learning of reliable network paths. In PODC, 2003. to appear.
• 3: Avrim Blum, Geoff Gordon, and Brendan McMahan. Bandit version of the shortest paths problem. Unpublished manuscript, July 2003.
• 4: Adam Kalai and Santosh Vempala. Geometric algorithms for online optimization, 2003. unpublished manuscript.
• 5: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 6: Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. In IEEE Symposium on Foundations of Computer Science, pages 256--261, 1989.
• 7: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 8: Eiji Takimoto , Manfred K. Warmuth, Path Kernels and Multiplicative Updates, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.74-89, July 08-10, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

General Terms:
Algorithms, Theory

Keywords:
multi-armed bandit problem, online decision problem, online linear optimization, routing