Adaptive Routing with End-to-End feedback Distributed….pdfVIP

Adaptive Routing with End-to-End feedback: Distributed Learning and Geometric Approaches Baruch Awerbuch ∗ Robert D. Kleinberg † ABSTRACT Categories and Subject Descriptors Minimal delay routing is a fundamental task in networks. Since F.2.2 [Analysis of Algorithms and Problem Complex- delays depend on the (potentially unpredictable) traffic distribu- ity]: Nonnumerical Algorithms and Problems—Routing and tion, online delay optimization can be quite challenging. While layout uncertainty about the current network delays may make the cur- rent routing choices sub-optimal, the algorithm can nevertheless try to learn the traffic patterns and keep adapting its choice of General Terms routing paths so as to perform nearly as well as the best static path. Algorithms, Theory This online shortest path problem is a special case of online linear optimization, a problem in which an online algorithm must Keywords choose, in each round, a strategy from some compact set S ⊆ Rd so as to try to minimize a linear cost function which is only Routing, online decision problem, multi-armed bandit prob- revealed at the end of the round. Kalai and Vempala [4] gave an lem, online linear optimization 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 1. INTRODUCTION more challenging opaque feedback model, in which only the co