Shortest Path Learning in Non-Stationary Environments via Online Convex Optimization

In this paper, we study the online shortest path learning problem under semi-bandit feedback in adversarial environments. To this end, we use the online convex optimization framework. We introduce an optimal online shortest path algorithm that guarantees to learn the shortest path in an sequential manner. 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 network optimization problems that require exploration and exploitation at the same time.