Online Learning of Network Bottlenecks via Minimax Paths

The path-specific Another commonly used method for these problems is bottleneck on a path between a source and a target node in a Upper Confidence Bound (UCB) (Auer 2002), which utilizes network is defined as the edge with a maximal cost or weight optimism to balance exploration and exploitation. UCB according to some criterion such as transfer time, load, commute has been adapted to combinatorial settings (Chen, Wang, and time, distance, etc. Then, the goal of bottleneck identification Yuan 2013), and also exists in Bayesian variants (Kaufmann, and avoidance is to find a path whose bottleneck is Cappé, and Garivier 2012). Recently, a variant of UCB has minimal. Thus, one may model bottleneck identification as been studied for bottleneck avoidance problems in a combinatorial the problem of computing the minimax edge over the given pure exploration setting (Du, Kuroki, and Chen network/graph, to obtain an edge with a minimal largest gap 2021). They consider a different problem setting and method between the source and target nodes. Equivalently, it can be than ours, though their bottleneck reward function is similar formulated as a widest path problem or maximum capacity to the one we use in our approximation method.