Online Shortest Path Learning via Convex Optimization

In this paper, we study the online shortest path learning problem under semi-bandit feedback in adversarial and non-stationary environments. To develop an efficient algorithm, we use the online convex optimization framework. We introduce an optimal online shortest path algorithm that guarantees to obtain the performance of the shortest path sequence. Since we do not have any statistical assumptions on the path delays, the results in the paper are guaranteed to hold in an individual sequence manner. Hence, our algorithm can be used for a wide range of practical network optimization problems that require exploration and exploitation at the same time.