Stochastic Online Shortest Path Routing: The Value of Feedback

DOI10.1109/TAC.2017.2747409zbMATH Open1390.90142arXiv1309.7367OpenAlexW2963554715MaRDI QIDQ4567151FDOQ4567151

Richard Combes, Alexandre Proutiere, Mikael Johansson, Zhenhua Zou, Mohammad Talebi

Publication date: 27 June 2018

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: This paper studies online shortest path routing over multi-hop networks. Link costs or delays are time-varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. These bounds help us to understand the performance improvements we can expect when (i) taking routing decisions at each hop rather than at the source only, and (ii) observing per-link delays rather than end-to-end path delays. In particular, we show that (i) is of no use while (ii) can have a spectacular impact. Three algorithms, with a trade-off between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms, and they significantly outperform state-of-the-art algorithms in numerical experiments.

Full work available at URL: https://arxiv.org/abs/1309.7367

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Stochastic programming (90C15) Stochastic network models in operations research (90B15)

Cited In (6)

• A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
• Online learning for route planning with on-time arrival reliability
• A combinatorial multi-armed bandit approach to correlation clustering
• A Lyapunov analysis of the continuous-time adaptive Bellman-Ford algorithm
• Differentially Private and Budget-Limited Bandit Learning over Matroids
• Optimal decisions in stochastic graphs with uncorrelated and correlated edge weights

This page was built for publication: Stochastic Online Shortest Path Routing: The Value of Feedback

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4567151)