A Contextual Combinatorial Semi-Bandit Approach to Network Bottleneck Identification
Bottleneck identification is a challenging task in network analysis,
especially when the network is not fully specified. To address this task, we
develop a unified online learning framework based on combinatorial semi-bandits
that performs bottleneck identification alongside learning the specifications
of the underlying network. Within this framework, we adapt and investigate
several combinatorial semi-bandit methods such as epsilon-greedy, LinUCB,
BayesUCB, and Thompson Sampling. Our framework is able to employ contextual
information in the form of contextual bandits. We evaluate our framework on the
real-world application of road networks and demonstrate its effectiveness in
different settings.