{'fraction_non_alphanumeric': 0.03875922118756803, 'fraction_numerical': 0.015781835772161083, 'mean_word_length': 4.171669793621013, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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.


Introduction
The problem of identifying bottlenecks is a crucial task in network analysis, especially in the analysis of traffic flow in road networks. In a road network, the road segment with the highest cost is described as a path-specific bottleneck on a path between a source node and a destination node. The cost or weight can be defined according to certain criteria such as travel time. The aim is to find a path that minimizes the bottleneck among all paths connecting the source and destination nodes.
Bottleneck identification can thus be modeled as the task of computing the minimax edge in a given road network to find an edge with the smallest maximum edge over the paths connecting the source node and the destination node. By negating the edge weights, bottleneck identification can also be viewed as the widest path problem or the maximum capacity path problem [1].
Getting from one point of the network to another point via a path with the smallest bottleneck can be considered as a sequential decision making problem. In a classical minimax problem, we assume that the network parameters such as the edge weights are given. However, in some real-world cases, the edge weights are unknown from the beginning and have to be learned while solving the minimax problem. In this paper, we formulate the bottleneck identification task as a contextual combinatorial semi-bandit problem and propose an online learning approach to solve it. Then we evaluate our approach on a real-world application, road networks. We think of road navigation as playing bandit arms while the road segments are paired with a cost defined as inverse of speed. We associate the bottleneck of a path with the most costly edge of the path and aim to find the path with the smallest bottleneck.
The Multi-Armed Bandit (MAB) model is a classic approach to online decision-making. An MAB agent repeatedly plays an arm and receives a stochastic reward drawn from an unknown reward distribution. In each iteration, the agent chooses an arm to play based on the observed reward of the previously played arms. The goal is to maximize the cumulative reward over a time horizon by making a trade-off between exploration and exploitation. The greedy algorithm is based on pure exploitation. Towards more exploration, the ǫ t -greedy algorithm [2], chooses uniformly * Corresponding author random actions with probability ǫ decaying by time, and otherwise exploits them greedily. If the horizon goes to infinity, the ǫ-greedy algorithm guarantees that the actual value of the learnable parameter will be reached, since the agent plays each arm many times. However, there are other algorithms that make better use of the reward history for more efficient exploration.
The Upper Confidence Bound (UCB) [3] algorithm is based on the idea of optimism in the face of uncertainty. It calculates an Upper Confidence Bound for each arm where the value is an overestimate of the learnable parameter with probability close to one. Later, [4] introduced BayesUCB which uses upper quantiles of the posterior distribution to compute the UCB. Thompson Sampling (TS) [5] is a classical approach to the trade-off between exploration and exploitation, assuming the existence of a prior distribution for the learnable parameter. Several studies, e.g., [6,7,8], demonstrate the performance of TS in different problems, including TS in combinatorial semi-bandit setting with the objective of finding the shortest path [9] and bottleneck [10] in a network (though these two works do not consider contextual information). A Contextual bandit model is an extension of the standard MAB, in which the agent receives additional information, called context, for each arm, which determines the distribution of the reward. Assuming that the expected reward is linear with the arm's context, [3] proposed the contextual bandit algorithm LinRel. Later, [11] improved LinRel by using different form of regularization and proposed LinUCB. Studies in [12,13] proposed a combinatorial MAB based on LinUCB, with application-specific objectives. [14] analyzes TS algorithm with linear reward.
In this paper, we propose a Contextual Combinatorial Semi-Bandit framework to identify bottlenecks in a network. Within this framework, we study ǫ t -greedy, LinUCB, BayesUCB and TS under Contextual Combinatorial Semi-Bandit conditions. We adapt these algorithms for a minimax path problem. We then demonstrate their performance on a realworld road network.

Problem Formulation
In this section, we first introduce the problem of identifying bottlenecks in a road network. Then, assuming the network is not fully specified, we define the probabilistic model of the problem.

Road Network Formulation
Consider a road network given as a graph G(V, E, w), where the nodes V represent intersections in the road network, and the edges E represent road segments. G is a directed graph, where each edge e = (u, v) ∈ E is the edge leading from node u ∈ V to v ∈ V. A weight function w : E → R + maps edge e ∈ E to its corresponding weight value w(e).
In our road network, we define w(e) as the cost in terms of travel time divided by the length (second per meter) of the edge e. We let the bottleneck of a single path refer to the edge on the path with the highest weight value. Consequently, given an arbitrary pair of sources node v ∈ V and target node u ∈ V, the bottleneck of all possible paths connecting v and u, is the smallest bottleneck among all possible paths connecting v to u. In other words, the bottleneck of v and u, denoted by M (v, u, G), can be defined as the edge with the minimax distance between these two points, as obtained by Eq. 1 where p v,u is a path connecting the source v and the target node u and P v,u is the set of all paths between v and u. Note that to use minimax distance, the weight function w is required to respect semi-metric constraints.
We apply a modification of Dijkstra's algorithm [15] to find the path including the bottleneck edge, M (v, u, G), in the directed setting.

Probabilistic Model of the Road Network
In our problem setting, the edge weights of the network are uncertain and stochastic. Thus, we adopt a Bayesian approach to model the edge weights and make use of prior knowledge. Given a time horizon T , for each edge e ∈ E and time step t ∈ [T ], we assume access to a d-dimensional feature vector c t,e representing contextual information related to the edge at that point in time. We further assume that the expected value of the weight is linear in c t,e , for some unknown parameter θ * e ∈ R d . More specifically, we assume that, at time t, the weight w t (e), given c t,e , for ∀e ∈ E to be sampled independently from a Gaussian distribution N (c ⊤ t,e · θ * e , ς 2 e ) where the mean θ * e is itself sampled from a prior distribution N (µ 0,e , Σ 0,e ). For simplicity of explanation, like other works [6,14], we assume ς 2 e is known. With a Gaussian prior and likelihood, for e ∈ E do 3: Observe the edge context c t,e 4: Assign algorithm-specific edge weightŵ t (e) based onθ t,e and c t,e 5: end for 6: for e ∈ p v,u do 8: Observe w t (e) by traversing edge e 9: Update the parameter estimateθ t,e 10: end for 11: end for the posterior has the same parametric form as the prior and the update of the parameters of the Gaussian posterior is derived in a closed form.

The Contextual Combinatorial Semi-bandit Framework
We formulate the network bottleneck identification task as a contextual combinatorial semi-bandit problem. We have a set of base arms A = {1, . . . , K}, each of which corresponds to an edge in the graph. Furthermore, we consider a set of super-arms I ⊆ 2 A , corresponding to the set of all paths between a specified source node and target node. In each time step t ∈ [T ], for each base arm a ∈ A, the environment reveals a contextual feature vector c t,a to the agent. Subsequently, the agent selects a super-arm S t ∈ I. For each base arm a ∈ S t , the environment reveals a loss sampled from N (c ⊤ t,a · θ * a , ς 2 a ) to the agent, i.e., semi-bandit feedback. The objective of the agent, in each time step t, is to find a super-arm S t ∈ I minimizing the maximum expected base arm loss, conditioned on the contextual information. This can be formalized as a regret minimization task, over the horizon T , where we define the expected cumulative regret as: where S * t = arg min S∈I max a∈S c ⊤ t,a · θ * a .

Algorithm 2 Thompson Sampling for bottleneck identification
for e ∈ E do p v,u ← Obtain a path that contains M (v, u, G(V, E,ŵ t )) 8: for e ∈ p v,u do 9: Observe w t (e) by traversing edge e

The Framework
We adapt and investigate several contextual combinatorial semi-bandit methods for the bottleneck identification problem. Algorithm 1 describes our general framework for this task. Given a graph G(V, E), a source node v ∈ V and a target node u ∈ V, the agent in each time step t ∈ [T ], for each edge e ∈ E, observes the context vector c t,e . Each agent keeps and updates an internal representation of the graph G, with weightsŵ t (e) assigned using the context c t,e and the stochastic weights w t (e) to induce exploration. Having observed c t,e , the agent subsequently updates the internal edge weightŵ t (e) according to c t,a and algorithm-specific parameter estimateθ t,e . Different algorithms have different approaches to updateŵ t (e), which we discuss later in this section. In line 6 the agent finds a path p v,u containing the bottleneck M (v, u, G(V, E,ŵ t )) based on the modification of Dijkstra's algorithm. In lines lines 7 to 9 the agent for each played edge e in the path, observes the stochastic edge weight (arm loss) w t (e) and then updates the parametersθ t,e , and internal weightsŵ t (e) accordingly.

Adapted Algorithms
We adapt several methods to our contextual combinatorial semi-bandit framework.
-Thompson Sampling: In Thompson Sampling, we have a prior distribution N (µ 0,e , Σ 0,e ) for θ * e where µ 0,e is a d-dimensional column vector and Σ 2 0,e is a scalar matrix λI d with a positive constant λ. Algorithm 2 describes the TS agent. In line 4, the agent samplesθ t,e from the posterior distribution N (µ t−1,e , Σ t−1,e ). Then, it updatesŵ t (e) with the expected weight given the sampledθ t,e . The TS agent updates the posterior parameters by UPDATE-PARAMS procedure shown in Algorithm 3.
-BayesUCB: We adapt the combinatorial BayesUCB in [16] for contextual setting, where the agent uses the upper quantiles of the posterior distributions over expected arm rewards to determine the level of exploration. The quantile function of a distribution ρ, denoted by Q(ν, ρ), is defined so that P ρ (X ≤ Q(ν, ρ)) = ν. In Algorithm 4, describing BayesUCB, lower quantiles of the expected edge weights given the context is used in line 4. The BayesUCB agent makes use of UPDATE-PARAMS procedure.
-LinUCB: The LinUCB agent, described in Algorithm 5, introduces A t,e ∈ R d×d and b t,e ∈ R d×1 with initialization of b 0,e = 0 d×1 and A 0,e = I d for each edge e ∈ E. To find the UCB value for each edge first it obtains the ridge regression estimateθ t,e ← A −1 t−1,e b t−1,e . Then, having the exploration factor α, the agent calculates the current edge

Algorithm 4 BayesUCB for bottleneck identification
for e ∈ E do p v,u ← Obtain a path that contains M (v, u, G(V, E,ŵ t (e)) 9: for e ∈ p v,u do 10: Observe w t (e) by traversing edge e end for 14: end for weight values. Since our problem is formulated as a loss minimization, we negate the α term. Updating the parameter in LinUCB follows lines lines 11 and 12.
ǫ t -greedy: We adapt the ǫ t -greedy in [2] to our problem setting, with ǫ t = t −1/2 . The Greedy agent estimatesθ t,e as the mode of the posterior distribution N (µ t,e , Σ t,e ), and then updates the edge by c ⊤ t,eθt,e . Then, with probability 1 − ǫ t , the agent applies the modification of Dijkstra's algorithm, and with probability ǫ t it chooses an arbitrary path containing a uniformly random edge. The update of the parameters follows Algorithm 3.

Experiments
Here, we evaluate our framework in a real-world road network dataset. We use the simulation framework in [17], adapt it to the road networks and extend it to contextual combinatorial setting.

Road Network Dataset
To evaluate our method, we used road network data provided by Turin SUMO Traffic (TuST) Scenario [18]. SUMO is a tool to simulate road network traffic data for a given scenario [19]. TuST describes the traffic of Turin during one day. It contains 14, 226 intersections and 18, 741 road segments. For each segment, we are provided with information such as the IDs of two intersections connected by the road segment, the length of the intersection, the speed limit, and the mean and variance of the speed of vehicles passing the segment at different hours of the day. Two peak traffic hours are defined in the scenario, the morning rush hour at 8:15 am and the evening rush hour at 6:30 pm. Since the simulation results for 24 hours are extensive, we use segments speed information of 5 hours as the contextual information for the   3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  0   500   1000   1500   2000   2500 Cumulative Regret (a) Thompson Sampling   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  0   500   1000   1500   2000   2500 Cumulative Regret (b) BayesUCB

Experimental Results
For the agents that make use of prior, for each edge e ∈ E with edge length l e , we initialize µ 0,e with a d−dimensional all-ones vector multiplied by λ e where λ e = l e · 10 −2 and Σ 0,e is λ e · 5 · I d . We set ς = 1. We fix the horizon to T = 5000. For LinUCB we set the exploration factor α = 4. We repeat all experiments for 10 runs. Figure 1a shows the average cumulative regrets of the agents over 10 runs. The LinUCB agent has the lowest cumulative regret, which stabilises faster compared to the others. Then, the BayesUCB and TS agents perform almost equally, and the ǫ t -greedy agent has the highest cumulative regret. Figure 1b illustrates the average instant regrets of the LinUCB and TS agents, which decrease as we progress in time. The LinUCB achieves the lowest regrets compared to TS. Figure 1c shows Turin road network, where the explored paths by the LinUCB agent are colored red, and the opacity illustrates the amount of exploration of each of the road segments. Figure 2 shows the boxplot of the cumulative regrets for the mentioned four agents in 10 runs. The y-axes show the cumulative regrets and x-axes show the horizon. We plotted a box for every 200 time steps. So, the labels of x-axes times 200 show the actual time step t. The red lines show the median and the boxes mark the upper and lower quantiles, with outliers shown as points. LinUCB has the smallest quantile boxes, suggesting that LinUCB behaves almost the same in different iterations. It also has the lowest median. ǫ t -greedy has relatively small quantile boxes with outlier points that show the uniformly random behavior of this agent occasionally. BayesUCB and TS behave almost the same regarding the sizes of the quantile boxes. The BayesUCB and TS agents compete closely with each other, and the ǫ t -greedy agent follows other agents.

Conclusion
We developed a unified contextual combinatorial bandit framework for network bottleneck identification which takes into account the available side information. We used a minimax concept to find the path with the bottleneck edge. We adapted Thompson Sampling, BayesUCB, LinUCB and ǫ t -greedy to our framework. We evaluated its performance on a real-world road network application, and demonstrated that LinUCB outperforms the other agents.