\section{Introduction}
Bottleneck identification constitutes an important task in network analysis, with applications including transportation planning and management \citep{berman1987optimal}, routing in computer networks \citep{shacham1992multicast} and various bicriterion path problems \citep{hansen80}.
The path-specific bottleneck, on a path between a source and a target node in a network, is defined as the edge with a maximal cost or weight according to some criterion such as transfer time, load, commute time, distance, etc.
The goal of bottleneck identification and avoidance is then to find a path whose bottleneck is minimal. Thus, one may model bottleneck identification as the problem of computing the minimax edge over the given network/graph, to obtain an edge with a minimal largest gap between the source and target nodes. Equivalently, it can be formulated as a widest path problem or maximum capacity path problem \citep{pollack1960letter} where the edge weights have been negated.

The aforementioned formulations assume that the network or the graph is fully specified, i.e., that all the edge weights are fully known. However, in practice, the edge weights might not be known in advance or they might include some inherent uncertainty. In this paper, we tackle such situations by developing an online learning framework to learn the edge weight distributions of the underlying network, while solving the bottleneck identification problem for different problem instances.
For this purpose, we view this as a multi-armed bandit (MAB) problem and focus on Thompson Sampling (TS) \citep{thompson1933}, a method that suits probabilistic online learning well.

Thompson Sampling is an early Bayesian method for addressing the trade-off between exploration and exploitation in sequential decision making problems. It has only recently been thoroughly evaluated through experimental studies \citep{ChapelleL11, GraepelCBH10} and theoretical analyses \citep{KaufmannKM12, agrawal2012analysis, russo2014learning}, where it has been shown to be asymptotically optimal in the sense that it matches well-known lower bounds of these types of problems \citep{lai1985asymptotically}.

Among many other problem settings, Thompson Sampling has been adapted to online versions of combinatorial optimization problems with retained theoretical guarantees \citep{wang2018thompson}, where one application is to find shortest paths in graphs \citep{liu2012adaptive, gai2012combinatorial, zou2014online, ijcai2020-0284}.

Another commonly used method for these problems is Upper Confidence Bound (UCB) \citep{Auer02}, which utilizes optimism to balance exploration and exploitation. UCB has been adapted to combinatorial settings \citep{chen2013combinatorial}, and also exists in Bayesian variants \citep{kaufmann2012bayesian}. Recently, a variant of UCB has been studied for bottleneck avoidance problems in a combinatorial pure exploration setting \citep{du2021combinatorial}. They consider a different problem setting and method than those we present in this paper, though their bottleneck reward function is similar to the one we use in our approximation method.

In this paper, we model the online bottleneck identification task as a stochastic combinatorial semi-bandit problem, for which we develop a combinatorial variant of Thompson Sampling. We then derive an upper bound on the corresponding Bayesian regret that is tight up to a polylogarithmic factor, which is consistent with the existing lower bounds for combinatorial semi-bandit problems. We face the issue of computational intractability with the \emph{exact} problem formulation. We thus propose an \emph{approximation} scheme, along with a theoretical analysis of its properties.
Finally, we experimentally investigate the performance of the proposed method on directed and undirected real-world networks from transport and collaboration domains.

\section{Bottleneck Identification Model}
In this section, we first introduce the bottleneck identification problem over a fixed network and then describe a probabilistic model to be used in stochastic and uncertain situations.

\subsection{Bottleneck identification over a network}
We model a network by a graph $ G( V, E, w )$, where $V$ denotes the set of vertices (nodes) and each $e = (u,v) \in E$ indicates an edge between vertices $u$ and $v$ where $u,v \in V$ and $u \neq v$.
Moreover, $w: E\rightarrow \mathbb{R}$ is a weight function defined for each edge of the graph, where for convenience, we use $w_e$ to denote the weight of edge $e$.
If $G$ is directed, the pair $(u,v)$ is ordered, otherwise, it is not (i.e., $(u,v)\equiv (v,u)$ for undirected graphs).
A path $p$ from vertex $u$ (source) to vertex $v$ (target) over $G$ is a sequence of vertices $<v_1, v_2, \dots,v_{k-1}, v_k >$ where $v_1=u$, $v_k=v$ and $(v_i,v_{i+1}) \in E, \forall i \in [1, k-1]$.
It can also be seen as a sequence of edges $< (v_1, v_2),(v_2,v_3), \dots,(v_{k-1}, v_k) >$.

As previously mentioned, a bottleneck on a path $p$ can be described as an edge with a maximal weight on that path.
To find the smallest feasible bottleneck between the source node $u$ and the target node $v$, we consider all the paths between them. For each path, we pick an edge with a maximal weight, to obtain all path-specific bottlenecks. We then identify the smallest path-specific bottleneck edge in order to find the best feasible bottleneck, i.e., such that larger bottlenecks are avoided.

Therefore, given graph $G$, the bottleneck edge between $u \in V$ and $v \in V$ can be identified via extracting the minimax edge between them. With $P_{u,v}$ denoting the set of all possible paths from  $u$ to $v$ over $G$, the bottleneck can be computed by

\begin{equation}\label{eq:MM}
     b(u,v;G) = \min_{p \in P_{u,v}} \max_{e\in p} w_e .
\end{equation}

The quantity in Eq. \ref{eq:MM} satisfies the  (ultra) metric properties under some basic assumptions on the edge weights such as symmetry and nonnegativity. Hence, it is sometimes used as a proper distance measure to extract manifolds and elongated clusters in a non-parametric way \citep{Chehreghani20Minimx, KimC07}.

However, in our setting, such conditions  do not need to be fulfilled by the edge weights. In general,  we tolerate positive as well as negative edge weights, and  we assume the graph might directed, i.e., the edge weights are not necessarily symmetric. Therefore, despite the absence of (ultra) metric properties, the concept of minimax edges is still relevant for bottleneck identification.

To compute the minimax edge, one does not need to investigate all possible paths between the source and target nodes, which might be computationally infeasible. As studied in \cite{Hu61}, minimax edges and paths over an arbitrary undirected  graph are equal to the minimax edges over any minimum spanning tree (MST) computed over that graph. This equivalence simplifies the calculation of minimax edges, as there is only one path between every two vertices over an MST, whose maximal edge weight yields the minimax edge, i.e., the desired bottleneck.

For directed graphs, an MST might not represent the minimax edges in a straightforward manner. Hence, we instead rely on a modification \citep{berman1987optimal} of Dijkstra's algorithm \citep{dijkstra1959note} to extract minimax paths rather than the shortest paths.

\subsection{Probabilistic model for bottleneck identification}

In this paper, we study bottleneck identification in uncertain and stochastic settings. Therefore, instead of considering the weights $w_e$ for $e \in E$ to be fixed, we view them as stochastic with fixed, albeit unknown, distribution parameters. Additionally, we assume that the weight of each edge follows a Gaussian distribution with known and bounded variance. The Gaussian edge weight assumption is common for many important problem settings, like minimization of travel time \citep{seshadri2010algorithm} or energy consumption \citep{ijcai2020-0284} in road networks. Furthermore, we assume that all edge weights are mutually independent. Hence,

\begin{equation*}
    w_e \sim \mathcal{N}(\theta_e^*, \sigma_e^2) ,
\end{equation*}

where $\theta_e^*$ denotes the unknown mean of edge $e$, and $\sigma_e^2$ is the known variance. Without loss of generality, we assume the bounded variance $\sigma_e^2 \leq 1$. However, we emphasize that we \emph{do not} assume that $w_e$ and $\theta_e^*$ are bounded or non-negative.

It is convenient to be able to make use of prior knowledge in online learning problems where the action space is large, which motivates a Bayesian approach where we assume that the unknown mean $\theta^*_e$ is sampled from a known prior distribution:

\begin{equation*}
    \theta_e^* \sim \mathcal{N}(\mu_{e,0}, \varsigma_{e,0}^2) .
\end{equation*}

We use a Gaussian prior for $\theta_e^*$ since it is conjugate to the Gaussian likelihood and allows for efficient recursive updates of posterior parameters upon a new weight observation $w_{e,t}$ at time $t$:

\begin{align}
    &\varsigma_{e,t+1}^2 \leftarrow \left(\frac{1}{\varsigma_{e,t}^2} + \frac{1}{\sigma^2_e}\right)^{-1} ,\label{eq:posterior_variance}\\
    &\mu_{e,t+1} \leftarrow \varsigma_{e,t+1}^2 \left(\frac{\mu_{e,t}}{\varsigma_{e,t}^2} + \frac{w_{e,t}}{\sigma^2_e}\right) . \label{eq:posterior_mean}
\end{align}

Since our long-term objective is to find a path which minimizes the \emph{expected} maximum edge weight along that path, we need a \emph{framework} to sequentially select paths to update these parameters and learn enough information about the edge weight distributions.

\section{Online Bottleneck Learning Framework}

Consider a stochastic combinatorial semi-bandit problem \citep{cesa2012combinatorial} with time horizon $T$, formulated as a problem of cost minimization rather than reward maximization. There is a set of base arms $\mathcal{A}$ (where we let $d := \vert \mathcal{A} \vert$) from which we may, at each time step $t \in [T]$, select a subset (or \emph{super arm}) $\bm{a}_t \subseteq \mathcal{A}$. The selection is further restricted such that $\bm{a}_t \in \mathcal{I} \subseteq 2^\mathcal{A}$, where $\mathcal{I}$ is called the set of \emph{feasible} super arms.

Upon selection of $\bm{a}_t$, the environment reveals a feedback $X_{i,t}$ drawn from some fixed and unknown distribution for each base arm $i \in \bm{a}_t$ (i.e., \emph{semi-bandit} feedback). Furthermore, we then receive a super arm cost from the environment, $c(\bm{a}_t) := \max_{i \in \bm{a}_t} X_{i,t}$, i.e., the maximum of all base arm feedback for the selected super arm and the current time step. The objective is to select super arms $\bm{a}_t$ to minimize $\E{ \sum_{t=1}^{T} c(\bm{a}_t)}$. This objective is typically reformulated as an equivalent \emph{regret} minimization problem, where the (expected) regret is defined as

\begin{equation}
    \text{Regret}(T) := \left(\sum_{t\in [T]} \E{c(\bm{a}_t)}\right) - T \cdot \min_{\bm{a} \in \mathcal{I}} \E{c(\bm{a})} . \label{eq:exact_regret}
\end{equation}

To connect this to the probabilistic bottleneck identification model introduced in the previous section, we let each edge $e \in E$ in the graph $G$ correspond to exactly one base arm $i \in \mathcal{A}$. For the online minimax path problem, the feasible set of super arms is then the set of all admissible paths in the graph, where the paths are directed or undirected depending on the type of graph. The feedback of each base arm $i$ is simply the Gaussian weight of the matching edge $e$, with known variance $\sigma_i^2$ and unknown mean $\theta^*_i$.

We denote the expected cost of a super arm $f_{\bm{\theta}}(\bm{a})$, where $\bm{\theta}$ is a mean vector and $f_{\bm{\theta}}(\bm{a}) := \E{\max_{i \in \bm{a}} C_i}$ such that $C_i \sim \mathcal{N}(\theta_i, \sigma_i^2)$. For Bayesian bandit settings and algorithms, it is common to consider the notion of \emph{Bayesian regret}, with an additional expectation over problem instances drawn from the prior distribution:

\begin{equation*}
    \text{BayesRegret}(T) := \E{\text{Regret}(T)} .
\end{equation*}

\subsection{Thompson Sampling with exact objective}

It is not sufficient to find the super arm $\bm{a}$ which minimizes $f_{\bm{\mu}_t}(\bm{a})$ in each time step $t$, since a strategy which is \emph{greedy} with respect to possibly imperfect current cost estimates may converge to a sub-optimal super arm. Thompson Sampling is one of several methods developed to address the trade-off between exploration and exploitation in stochastic online learning problems. It has been shown to exhibit good performance in many formulations, e.g., linear contextual bandits and combinatorial semi-bandits.

The steps performed in each time step $t$ by Thompson Sampling, adapted to our setting, are described in Algorithm \ref{alg:exact_algorithm}. First, a mean vector $\Tilde{\bm{\theta}}$ is sampled from the current posterior distribution (or from the prior in the first time step). Then, an arm $\bm{a}_t$ is selected which minimizes the expected cost $f_{\Tilde{\bm{\theta}}} (\bm{a}_t)$ with respect to the sampled mean vector. These first two steps are equivalent to selecting the arm according to the posterior probability of it being optimal. In combinatorial semi-bandit problems, the method of finding the best super arm according to the sampled parameters is often called an \emph{oracle}.

When the super arm $\bm{a}_t$ is played, the environment reveals the feedback $X_{i,t}$ if and only if $i \in \bm{a}_t$, which is a property called \emph{semi-bandit feedback}. Finally, these observations are used to update the posterior distribution parameters.

\begin{algorithm}[tb]
\caption{TS for minimax paths (exact)}
\label{alg:exact_algorithm}
\textbf{Input}: Prior parameters $\bm{\mu}_0, \bm{\varsigma}_0$
\begin{algorithmic}[1]
\STATE For each base arm, play a super arm which contains it.
\FOR{$t \leftarrow 1, \dots, T$}
\FOR{$i \in \mathcal{A}$}
\STATE $\Tilde{\theta}_i \leftarrow $ Sample from posterior $\mathcal{N}\left(\mu_{i,t-1}, \varsigma_{i,t-1}^2\right)$
\ENDFOR
\STATE $\bm{a}_t \leftarrow \arg \min_{\bm{a} \in \mathcal{I}} f_{\Tilde{\bm{\theta}}} (\bm{a})$
\STATE Play arm $\bm{a}_t$, observe feedback $X_{j,t}$ for $j \in \bm{a}_t$
\STATE Compute $\bm{\mu}_{t}, \bm{\varsigma}_{t}$ with feedback using Eqs. \ref{eq:posterior_variance} and \ref{eq:posterior_mean}
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Regret analysis of Thompson Sampling for minimax paths}

We use the technique to analyze the Bayesian regret of Thompson Sampling for general bandit problems introduced by \cite{russo2014learning} and further elaborated by \cite{slivkins2019}, carefully adapting it to our problem setting. This technique was originally devised to enable convenient conversion of existing UCB regret analyses to Thompson Sampling, but can also be applied to novel TS applications. In the rest of this section, we outline the most important steps of the proof of Theorem \ref{alg:exact_algorithm}, leaving technical details to the supplementary material.

\begin{theorem}
\label{thm:regret_main}
The Bayesian regret of Algorithm \ref{alg:exact_algorithm} is $\mathcal{O}(d\sqrt{T \log T})$.
\end{theorem}

We initially define a sequence of upper and lower confidence bounds, for each time step $t$:

\begin{align*}
    &U_t(\bm{a}) := f_{\hat{\bm{\theta}}_{t-1}}(\bm{a})  + \max_{i \in \bm{a}} \sqrt{\frac{32 \log T}{N_{t-1}(i)}} \\
    &L_t(\bm{a}) := f_{\hat{\bm{\theta}}_{t-1}}(\bm{a})  - \max_{i \in \bm{a}} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}
\end{align*}

where $\hat{\theta}_{i,t}$ is the average feedback of base arm $i$ until time $t$ and $N_t(i)$ is the number of times base arm $i$ has been played as part of a super arm until time $t$.

\begin{lemma}
\label{lem:regret_decomposition_main}
For Algorithm \ref{alg:exact_algorithm}, we have that $\text{BayesRegret}(T) = \sum_{t \in [T]} \E{U_t(\bm{a_t}) - L_t(\bm{a_t})} + \sum_{t \in [T]} \E{f_{\bm{\theta}^*}(\bm{a}_t) - U_t (\bm{a}_t) } + \sum_{t \in [T]} \E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) }$.
\end{lemma}

This Bayesian regret decomposition is a direct application of Proposition 1 of \cite{russo2014learning}. It utilizes the fact that given the history of selected arms and received feedback until time $t$, the played super arm $\bm{a}_t$ and the best possible super arm $\bm{a}^* := \arg \min_{\bm{a} \in \mathcal{I}} f_{\bm{\theta}^*}(\bm{a})$ are identically distributed under Thompson Sampling. Furthermore, also given the history, $U_t(\bm{a})$ and $L_t(\bm{a})$ are deterministic functions of the super arm $\bm{a}$. This enables the decomposition of the regret into terms of the expected confidence width, the expected overestimation of the super arm with least mean cost, and the expected underestimation of the selected super arm. By showing that $f_{\bm{\theta}^*}(\bm{a}) \in [L_t(\bm{a}), U_t(\bm{a})]$ with high probability, we can bound the last two of these terms.

\begin{lemma}
\label{lem:bad_event_regret_terms_main}
For any $t \in [T]$, we have that $\E{f_{\bm{\theta}^*}(\bm{a}_t) - U_t (\bm{a}_t) } \leq \frac{4d}{T}$ and $\E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) } \leq \frac{4d}{T}$.
\end{lemma}

Both terms are bounded in the same way, for which we need a few intermediary results. Focusing on the overestimation of the optimal super arm, we can see that:

\begin{align*}
    &\E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) } = \\
    &\E{f_{\hat{\bm{\theta}}_{t-1}}(\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) - \max_{i \in \bm{a}^*} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}} .
\end{align*}

First, in Lemma \ref{lem:reward_function_bound_main}, the difference between the true mean cost $f_{\bm{\theta}^*}(\bm{a})$ of a super arm $\bm{a}$ and the corresponding estimated mean $f_{\hat{\bm{\theta}}}(\bm{a})$ is bounded. The resulting upper bound is the maximum of the differences of the true and estimated means of each individual base arm feedback, such that:

\begin{lemma}
\label{lem:reward_function_bound_main}
For any super arm $\bm{a} \in \mathcal{I}$ and time step $t \in [T]$, we have that $\vert f_{\bm{\theta}^*}(\bm{a}) - f_{\hat{\bm{\theta}}_t}(\bm{a}) \vert \leq 2 \max_{i\in\bm{a}} \vert \theta^*_i - \hat{\theta}_{i,t} \vert$.
\end{lemma}

This is achieved by decomposing the absolute value into a sum of the positive and negative portions of the difference, then bounding each individually. Focusing on the positive portion by assuming that $f_{\hat{\bm{\theta}}_{t-1}}(\bm{a}^*) \geq f_{\bm{\theta}^*}(\bm{a}^*)$, and letting $Z_i \sim \mathcal{N}(\hat{\theta}_{i,t-1}, \sigma^2_i)$, $Y_i \sim \mathcal{N}(\theta^*_{i}, \sigma^2_i)$, $\delta_{i,t-1} :=  \theta^*_i - \hat{\theta}_{i,t-1}$ and $Q_i := Z_i - \delta_{i,t-1}$, for $i \in \bm{a}$, we can see that:

\begin{align*}
    &f_{\hat{\bm{\theta}}_{t-1}}(\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) =\\
    &\E{\max_{i \in \bm{a}} Z_i} - \E{\max_{i \in \bm{a}} Y_i} = \\
    &\E{\max_{i \in \bm{a}} (Q_i + \delta_{i,t-1})} - \E{\max_{i \in \bm{a}} Y_i} \leq \\
    &\E{\max_{i \in \bm{a}} Q_i} + \max_{i \in \bm{a}} \delta_{i,t-1} - \E{\max_{i \in \bm{a}} Y_i} = \\
    &\max_{i \in \bm{a}} \delta_{i,t-1} \;\;.
\end{align*}

The negative portion is bounded in the same way, directly leading to the result of Lemma \ref{lem:reward_function_bound_main}. With this result, we can proceed with Lemma \ref{lem:bad_event_regret_terms_main}, where we let $[x]^+ := \max(0, x)$:

\begin{align}
    &\E{2\max_{i \in \bm{a}^*} \vert \delta_{i,t-1} \vert - \max_{i \in \bm{a}^*} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}} \leq \nonumber\\
    &\E{2\max_{i \in \bm{a}^*} \left[\vert \delta_{i,t-1} \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}}\right]^+} \leq \nonumber\\
    &2 \sum_{i \in \mathcal{A}} \E{ \left[\vert \delta_{i,t-1} \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}}\right]^+} = \nonumber\\
    &2 \sum_{i \in \mathcal{A}} \prob{\vert \delta_{i,t-1} \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \cdot \label{eq:bad_event_probability}\\
    &\E{ \vert \delta_{i,t-1} \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\bigg\vert\;\; \vert \delta_{i,t-1} \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \label{eq:bad_event_expectation}
\end{align}

The probability in Eq. \ref{eq:bad_event_probability} is of the event that the difference between the estimated and true means of an arm $i$ exceeds the confidence radius $\sqrt{8 \log T / N_{t-1}(i)}$, while Eq. \ref{eq:bad_event_expectation} is the expected difference conditional on that event. We bound Eq. \ref{eq:bad_event_probability} with Lemma \ref{lem:bad_event_probability_main} and Eq. \ref{eq:bad_event_expectation} with Lemma \ref{lem:bad_event_expectation_main}.

\begin{lemma}
\label{lem:bad_event_probability_main}
$\prob{\forall t \in [T]\; \forall i \in \mathcal{A},\;\; \vert \delta_{i,t-1} \vert \leq \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \geq 1 - \frac{2}{T}$.
\end{lemma}

It is now sufficient to show that the difference $\delta_{i,t-1}$ is small for all base arms $i \in \mathcal{A}$ with high probability, which we accomplish using a standard concentration analysis through application of Hoeffding inequality and union bounds.

\begin{lemma}
\label{lem:bad_event_expectation_main}
For any $t \in [T]$ and $i \in \mathcal{A}$, we have

\begin{align*}
    \E{ \vert \delta_{i,t-1} \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\bigg\vert\;\; \vert \delta_{i,t-1} \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \leq 1 .
\end{align*}
\end{lemma}

Though the rewards are unbounded, this expectation can be bounded by utilizing the fact that the mean of a truncated Gaussian distribution is increasing in the mean of the distribution before truncation, by Theorem 2 of \cite{horrace2015moments}. We can see that:

\begin{align*}
    &\E{ \vert \delta_{i,t-1} \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\bigg\vert\;\; \vert \delta_{i,t-1} \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} =  \\
    &\E{ \delta_{i,t-1} - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\bigg\vert\;\;  \delta_{i,t-1} -  \sqrt{\frac{8 \log T}{N_{t-1}(i)}} > 0} \leq \\
    &\E{ \delta_{i,t-1} \;\;\bigg\vert\;\;  \delta_{i,t-1} > 0} .
\end{align*}

We know that $\delta_{i,t-1}$ is zero-mean Gaussian with variance at most one, hence $\E{ \delta_{i,t-1} \;\;\bigg\vert\;\;  \delta_{i,t-1} > 0} \leq 1$.

With the result from Lemma $\ref{lem:bad_event_regret_terms_main}$, the last two terms of the regret decomposition in Lemma \ref{lem:regret_decomposition_main} are bounded by constants in $T$. Focusing on the remaining term, we just need to show that $\sum_{t \in [T]} \E{U_t(\bm{a}_t) - L_t(\bm{a}_t)} \leq \mathcal{O} (d \sqrt{T \log T})$ to prove Theorem \ref{thm:regret_main}:

\begin{align*}
    &\sum_{t \in [T]} \E{U_t(\bm{a}_t) - L_t(\bm{a}_t)} =\\
    &\sqrt{128 \log T} \sum_{t\in [T]} \E{\max_{i\in \bm{a}_t} \frac{1}{\sqrt{N_{t-1}(i)}}} \leq \\
    &\sqrt{128 \log T} \sum_{t\in [T]} \E{\sum_{i\in \bm{a}_t} \frac{1}{\sqrt{N_{t-1}(i)}}} = \\
    &\sqrt{128 \log T} \sum_{i\in \mathcal{A}} \E{\sum_{t:i\in \bm{a}_t} \frac{1}{\sqrt{N_{t-1}(i)}}} \leq\\
    &\sqrt{128 \log T} \sum_{i\in \mathcal{A}} \E{2 \sqrt{N_{T}(i)}} \leq \\
    &\sqrt{128 \log T} \cdot \E{2 \sqrt{d \sum_{i\in \mathcal{A}} N_{T}(i)}} \leq \\
    &\sqrt{128 \log T} \cdot \E{2 \sqrt{d^2 T}} = \\
    &2 d \sqrt{128  T \log T} = \\
    &\mathcal{O} (d \sqrt{T \log T}) .
\end{align*}

We note that the final upper bound is tight up to a polylogarithmic factor, according to existing lower bounds for combinatorial semi-bandit problems \citep{kveton2015tight}.

\subsection{Thompson Sampling with approximate objective}

Unfortunately, exact expressions for computing the expected maximum of Gaussian random variables only exist when the variables are few. In other words, we cannot compute $f_{\bm{\theta}} (\bm{a})$ exactly for a super arm $\bm{a}$ containing many base arms, necessitating some form of approximation approach. While it is possible to approximate $f_{\bm{\theta}} (\bm{a})$ through e.g., Monte Carlo simulations, we want to be able to perform the cost minimization step using an efficient oracle. Therefore, we propose the approximation method outlined in Algorithm \ref{alg:approximation_algorithm}, where the minimization step has been modified from Algorithm \ref{alg:exact_algorithm} with an alternative super arm cost function $\Tilde{f}_{\Tilde{\bm{\theta}}} (\bm{a}) := \max_{i \in \bm{a}} \Tilde{\theta}_i$.

Switching objectives, from finding the super arm which minimizes the expected maximum base arm feedback, to instead minimize the maximum expected feedback, has the benefit of allowing us to utilize the efficient deterministic minimax path algorithms introduced earlier for both directed and undirected graphs.

It is possible to use alternative notions of regret to evaluate combinatorial bandit algorithms with approximate oracles \citep{chen2013combinatorial, chen2016combinatorial}. For our experimental evaluation of Algorithm \ref{alg:approximation_algorithm}, we introduce the following definition of approximate regret:

\begin{equation*}
    \text{ApproxRegret(T)} := \left(\sum_{t \in [T]} \Tilde{f}_{\bm{\theta}^*} (\bm{a}_t)\right) - T \cdot \min_{\bm{a} \in \mathcal{I}} \Tilde{f}_{\bm{\theta}^*} (\bm{a}) .
\end{equation*}

An alternative Bayesian bandit algorithm which can be used with the alternative objective is BayesUCB \citep{kaufmann2012bayesian}, which we use as a baseline for our experiments. Like Thompson Sampling, BayesUCB has been adapted to combinatorial semi-bandit settings \citep{nuara2018combinatorial, ijcai2020-0284}. Whereas Thompson Sampling in Algorithm \ref{alg:approximation_algorithm} encourages exploration by applying the oracle to parameters sampled the posterior distribution, with BayesUCB the oracle is instead applied to optimistic estimates based on the posterior distribution. In practice, this is accomplished for our cost minimization problem by using lower quantiles of the posterior distribution of each base arm. This principle of selecting plausibly optimal arms is called \emph{optimism in the face of uncertainty} and is the underlying idea of all bandit algorithms based on UCB.

\begin{figure*}[htb!] \centering
    \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{results_cumulative_regret_manhattan.png}
         \caption{ }
         \label{fig:ManhattanCumulative}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
      \includegraphics[width=\textwidth]{results_instant_regret_manhattan.png}
         \caption{ }
         \label{fig:ManhattanInstant}
    \end{subfigure}
\begin{subfigure}{0.11\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{Manhattan.jpg}
         \caption{ }
         \label{fig:ManhattanRoad}

    \end{subfigure}
    \caption{Experimental results on the Manhattan road network. (a) Average cumulative regret for BayesUCB (B-UCB), greedy (GR), and Thompson Sampling (TS) over time with horizon $T=8000$. (b) Corresponding average instant regret results. (c) The paths explored by the TS agent is shown in red, with opacity illustrating the amount of exploration of each segment.}\label{fig:surat}
\end{figure*}

\begin{algorithm}[tb]
\caption{TS for minimax paths (approximation)}
\label{alg:approximation_algorithm}
\textbf{Input}: Prior parameters $\bm{\mu}_0, \bm{\varsigma}_0$
\begin{algorithmic}[1]
\STATE For each base arm, play a super arm which contains it.
\FOR{$t \leftarrow 1, \dots, T$}
\FOR{$i \in \mathcal{A}$}
\STATE $\Tilde{\theta}_i \leftarrow $ Sample from posterior $\mathcal{N}\left(\mu_{i,t-1}, \varsigma_{i,t-1}^2\right)$
\ENDFOR
\STATE $\bm{a_t} \leftarrow \arg \min_{\bm{a} \in \mathcal{I}} \max_{i \in \bm{a}} \Tilde{\theta}_i$
\STATE Play arm $\bm{a}_t$, observe feedback $X_{j,t}$ for $j \in \bm{a}_t$
\STATE Compute $\bm{\mu}_{t}, \bm{\varsigma}_{t}$ with feedback using Eq. \ref{eq:posterior_variance} and \ref{eq:posterior_mean}
\ENDFOR
\end{algorithmic}
\end{algorithm}

To connect the different objectives in Algorithm \ref{alg:exact_algorithm} and Algorithm \ref{alg:approximation_algorithm}, we note that by Jensen's inequality, $\Tilde{f}_{\Tilde{\bm{\theta}}} (\bm{a}) \leq f_{\Tilde{\bm{\theta}}} (\bm{a})$ and that the approximation objective consequently will underestimate super arm costs. However, we establish an upper bound on this difference through Theorem \ref{thm:optimal_arm_difference_main}.

\begin{theorem}
\label{thm:optimal_arm_difference_main}
Given the optimal super arm $\bm{a^*}$ for Algorithm \ref{alg:exact_algorithm} and the optimal super arm $\Tilde{\bm{a}}^*$ for Algorithm \ref{alg:approximation_algorithm}, we have that $ f_{\bm{\theta}^*}(\Tilde{\bm{a}}^*) - f_{\bm{\theta}^*}(\bm{a}^*) \leq \sqrt{2 \log d}$.
\end{theorem}

For any super arm $\bm{a} \in \mathcal{I}$, let $Y_i$ for $i \in \bm{a}$ be Gaussian random variables with $Y_i \sim \mathcal{N}(\theta^*_i, \sigma_i^2)$. Furthermore, let $W_i := Y_i - \theta^*_i$, such that $W_i \sim \mathcal{N}(0, \sigma^2_i)$. Then, the following holds:

\begin{align*}
    &\E{\max_{i \in \bm{a}} Y_i} =\\
    &\E{\max_{i \in \bm{a}} (W_i + \theta_i^*)} \leq \\
    &\E{\max_{i \in \bm{a}} W_i} + \max_{i \in \bm{a}} \E{Y_i} \leq \\
    &\sqrt{2 \log d} + \max_{i \in \bm{a}} \E{Y_i} \, ,
\end{align*}

where the last inequality is due to Lemma 9 in \cite{orabona2015optimal} and since $\sigma_i^2 \leq 1$ for all $i \in \bm{a}$. We also note that, by Jensen's inequality, we have $\max_{i \in \bm{a}} \E{Y_i} \leq \E{\max_{i \in \bm{a}} Y_i}$. Moreover, by definition we know that $\bm{a}^* = \arg \min_{\bm{a} \in \mathcal{I}} \E{\max_{i \in \bm{a}} Y_i}$ and $\Tilde{\bm{a}}^* = \arg \min_{\bm{a} \in \mathcal{I}} \max_{i \in \bm{a}} \E{ Y_i}$. Consequently, we have,

\begin{align*}
    &\max_{i \in \Tilde{\bm{a}}^*} \E{Y_i} \leq \max_{i \in \bm{a}^*} \E{Y_i} \leq \\
    &\E{\max_{i \in \bm{a}^*} Y_i} \leq \E{\max_{i \in \Tilde{\bm{a}}^*} Y_i} \leq \\
    &\sqrt{2 \log d} + \max_{i\in \Tilde{\bm{a}}^*} \mathbb{E}\left[ Y_i \right] .
\end{align*}

Hence, we can conclude that

\begin{align*}
    &f_{\bm{\theta}^*}(\Tilde{\bm{a}}^*) - f_{\bm{\theta}^*}(\bm{a}^*) =\\ &\E{\max_{i \in \Tilde{\bm{a}}^*} Y_i} - \E{\max_{i \in \bm{a}^*} Y_i}\leq \\
    &\sqrt{2 \log d}\, .
\end{align*}

In other words, Theorem \ref{thm:optimal_arm_difference_main} holds and the optimal solutions of the exact Algorithm \ref{alg:exact_algorithm} and the approximate Algorithm \ref{alg:approximation_algorithm} differ by at most $\sqrt{2 \log d}$. This bound is independent of the mean vector $\bm{\theta}^*$, depending only on the number of base arms and that the variance is bounded.

\section{Experimental Results}

In this section, we conduct bottleneck identification experiments using Algorithm \ref{alg:approximation_algorithm} for two real-world applications, i) road (transport) networks, and ii) collaboration (social) networks. These experiments are performed with an extended version of the simulation framework in \cite{tstutorial} and evaluated using our approximate definition of regret.

In the supplementary material, we provide more details on the experimental results. In addition, there, we compare Algorithm \ref{alg:exact_algorithm} to Algorithm \ref{alg:approximation_algorithm} through a toy example.

\subsection{Road networks}

Identification of bottlenecks in a road network is a vital tool for traffic planners to analyze the network and prevent congestion.
In this application, our goal is to find the bottleneck between a source and a target, i.e., a road segment which is necessary to pass and also has minimal traffic flow. In the road network model, we let the nodes represent intersections and the directed edges represent road segments, with travel time divided by distance (seconds per meter) as edge weights.
The bottleneck between a pair of intersections is the minimum bottleneck over all paths connecting them, where the bottleneck for each of these paths is the largest weight over all road segments along it.
Note that in order for the bottleneck between a pair of intersections to have a meaning, there needs to exist at least one path connecting them.

We collect road networks of four cities, shown in Table \ref{tab:roadGraphs}, from \cite{OpenStreetMap}, where the average travel time as well as the distance is provided for each (directed) edge.
We simulate an environment with the stochastic edge weights sampled from $w_e \sim \mathcal{N}(\theta_e^*, \sigma_e^2)$, where the observation noise is $\sigma_e = 0.4$.
For the experiments, the environment samples the true unknown mean $\theta_e^*$ from the known prior $\theta_e^* \sim \mathcal{N}(\mu_{e,0}, {\varsigma_{e,0}}^2)$, where
$\varsigma_{e,0} = 0.4 \textrm{s/m}$, and $\mu_{e,0}$
is the average travel time divided by distance provided by OpenStreetMap~(OSM).

\begin{figure*}[htb!] \centering
    \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{results_cumulative_regret_salzburg.png}
         \caption{ }
         \label{fig:Salzburg}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
      \includegraphics[width=\textwidth]{results_cumulative_regret_Eindhoven.png}
         \caption{ }
         \label{fig:Eindhoven}
    \end{subfigure}
\begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{results_cumulative_regret_Oslo.png}
         \caption{ }
         \label{fig:Oslo}

    \end{subfigure}
    \caption{Average cumulative regret for BayesUCB (B-UCB), greedy (GR), and Thompson Sampling (TS) over time with horizon $T=6000$, for Salzburg (a), Eindhoven (b) and Oslo (c). }\label{fig:allCumulativa}
\end{figure*}

We consider a greedy agent (GR) as a baseline, which always chooses the path with the lowest current estimate of expected cost. We evaluate the Thompson Sampling agent (TS) and the  BayesUCB agent (B-UCB) in relation to the baseline.
We run the simulations with all different agents (GR, TS, B-UCB) for each road network and report cumulative regret at a specific horizon $T$, averaged over five repetitions. The horizon is chosen such that the instant regret is almost stabilized for all three agents.

\begin{table}[b]
\centering
\caption{A description of the road networks. } \label{tab:roadGraphs}
\begin{tabular}{|c||c|c| c| c| c|} \hline
Road network    & \#Node & \#Edge &  Avg. Degree \\ \hline \hline
Eindhoven      &   7501    &   10776  &  2.873 \\\hline
Oslo      &  8153 & 11192   & 2.745 \\\hline
Manhattan  &   4593    &  8130    &  3.540   \\ \hline
Salzburg   &   2921    &  3848   & 2.634   \\\hline
\end{tabular}
\end{table}

Figure \ref{fig:ManhattanCumulative} illustrates the average cumulative regret for the Manhattan road network over time, where at the horizon $T=8000$ the TS agent yields the lowest cumulative regret. Then, B-UCB follows TS and achieves a better result compared to the greedy baseline.  Figure \ref{fig:ManhattanInstant} shows average instant regret, which is high for the TS and B-UCB agents in the beginning; however, further on, one can see that first TS and then B-UCB start saturating, by achieving sufficient exploration. Figure \ref{fig:ManhattanRoad} visualizes the Manhattan road network, where the paths explored by the TS agent are shown in red. The road segments that are explored more by the TS agent are displayed as more opaque.

 Figure \ref{fig:allCumulativa} shows the average cumulative regret for the three other road networks, respectively the cities of Salzburg, Eindhoven and Oslo. The results imply that TS yields the smallest cumulative regret, and that the cumulative regret of B-UCB is smaller than GR. Instant regret plots and road networks for these cities are provided in the supplementary material.

\begin{figure}[b!] \centering
    \begin{subfigure}{0.7\columnwidth}
    \centering
    \captionsetup{justification=centering}
      \includegraphics[width=\columnwidth]{results_cumulative_regret_geom.png}
         \caption{}
         \label{fig:geomCumulative}
    \end{subfigure}
\begin{subfigure}{0.7\columnwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\columnwidth]{results_instant_regret_geom.png}
         \caption{ }
         \label{fig:geomInstat}
    \end{subfigure}
    \caption{Experimental results on the collaboration network. (a) Avg. cumulative regret for BayesUCB (B-UCB), greedy (GR), and Thompson Sampling (TS) over time with horizon $T=2000$. (b) Corresponding avg. instant regret results.}\label{fig:geom}
\end{figure}

\subsection{Collaboration network}

We consider a collaboration network from computational geometry (Geom) \citep{jones2002computational} as an application of our approach to social networks.
More specifically, we use the version provided by \cite{handcock2003statnet} and distributed among the Pajek datasets \citep{pajek} where certain author duplicates, occurring in minor or major name variations, have been merged. The \cite{handcock2003statnet} version is based on the BibTeX bibliography \citep{beebe2002}, to which the database from \cite{jones2002computational} has been exported.
The network has 9072 vertices representing the authors and 22577 edges with the edge weights representing the number of mutual works between a pair of authors.

We simulate an environment where each edge weight is sampled as $w_e \sim \mathcal{N}(\theta_e^*, \sigma_e^2)$, within which $\theta_e^*$ is regarded as the true (negative) mean number of shared publications between a pair of authors linked by the edge $e$, and the observation noise is $\sigma_e = 20$.
Furthermore, in this experiment, while the true negative mean number of mutual publications are assumed (by the agent) to be distributed according to the prior $\theta_e^* \sim \mathcal{N}(\mu_{e,0}, \varsigma_{e,0}^2)$ with $\varsigma_{e,0} = 5$, we instead generate the mean from a wider prior $\theta_e^* \sim \mathcal{N}(\mu_{e,0}, 20^2)$, simulating a scenario where the prior belief of the agent is too high.
The assumed mean $\mu_{e,0}$ of the prior is however consistent with the distribution from which $\theta_e^*$ is sampled, and is directly determined by the pairwise negative number of mutual collaborations from the dataset in \cite{handcock2003statnet}.

Figure \ref{fig:geom} shows the cumulative and instant regret, averaged over five runs for the three agents with horizon $T=2000$, again chosen such that the instant regret is stabilized for all agents.
One can see that in Figure \ref{fig:geomCumulative}, the TS agent reaches the lowest cumulative regret. Figure \ref{fig:geomInstat} suggests that as we go further in time, the instant regret of the TS and B-UCB agents approaches zero, where this happens earlier for the TS agent.

\section{Conclusion}
We developed an online learning framework for bottleneck identification in networks via minimax paths.
In particular, we modeled this task as a combinatorial semi-bandit problem for which we proposed a combinatorial version of Thompson Sampling. We then established an upper bound on the  Bayesian regret of the Thompson Sampling method.
To deal with the computational intractability of the problem, we devised an alternative problem formulation which approximates the original objective.
Finally, we investigated the framework on several directed and undirected real-world networks from  transport and collaboration domains. Our experimental results demonstrate its effectiveness  compared to alternatives such as greedy and B-UCB methods.

\section*{Acknowledgements}
This work is funded by the Strategic Vehicle Research and Innovation Programme (FFI) of Sweden, through the project EENE. We want to thank Emilio Jorge, Emil Carlsson and Tobias Johansson for insightful discussions around the proofs.

\putbib[references]

\end{bibunit}

\begin{bibunit}[aaai22]

\setcounter{secnumdepth}{2}
\renewcommand{\thesubsection}{\Alph{subsection}}
\newpage
\onecolumn
\section*{Supplementary Material}

\subsection{Regret analysis}

Here, we include detailed proofs for the theorems and lemmas in the main paper. We use the technique to analyze the Bayesian regret of Thompson Sampling for general bandit problems outlined by \cite{russo2014learning} and further detailed by \cite{slivkins2019}, carefully adapting it to our problem setting.

\begin{theorem}
The Bayesian regret of Algorithm 1 is $\mathcal{O}(d\sqrt{T \log T})$.
\end{theorem}

\begin{proof}
By Lemma \ref{lem:regret_decomposition} combined with Lemma \ref{lem:over_under_estimation}, we have

\begin{align*}
    \text{BayesRegret}(T) \leq 8d + \sum_{t \in [T]} \E{U_t(\bm{a}_t) - L_t(\bm{a}_t)} =& \\
     8 d + 2 \sum_{t \in [T]} \E{\max_{i\in \bm{a}_t} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}} =& \\
     8 d + \sqrt{128 \log T} \sum_{t \in [T]} \E{\max_{i\in \bm{a}_t} \frac{1}{\sqrt{N_{t-1}(i)}}} \leq& \\
     8 d + \sqrt{128 \log T} \sum_{t \in [T]} \E{\sum_{i\in \bm{a}_t} \frac{1}{\sqrt{N_{t-1}(i)}}} =& \\
     8 d + \sqrt{128 \log T} \sum_{i\in \mathcal{A}} \E{\sum_{t:i\in \bm{a}_t} \frac{1}{\sqrt{N_{t-1}(i)}}} =& \\
     8 d + \sqrt{128 \log T} \sum_{i\in \mathcal{A}} \E{\sum_{j=1}^{N_{T}(i)} \frac{1}{\sqrt{j}}} \leq& \\
     \intertext{(See proof of Lemma 1 in \citealt{russo2014learning})}
     8 d + 2 \sqrt{128 \log T} \sum_{i\in \mathcal{A}} \E{\sqrt{N_{T}(i)}} \leq& \\
     \intertext{(Cauchy-Schwarz inequality)}
     8 d + 2 \sqrt{128 \log T} \cdot \E{\sqrt{d \sum_{i\in \mathcal{A}} N_{T}(i)}} \leq& \\
     8 d + 2 \sqrt{128 \log T} \cdot \E{\sqrt{d^2 T}} =& \\
     8 d + 2 d \sqrt{128  T \log T} =& \\
     \mathcal{O}(d\sqrt{T \log T}) &
\end{align*}
\end{proof}

\begin{lemma}
\label{lem:regret_decomposition}
For Algorithm 1, we have that $\text{BayesRegret}(T) = \sum_{t \in [T]} \E{U_t(\bm{a_t}) - L_t(\bm{a_t})} + \\ \sum_{t \in [T]} \E{f_{\bm{\theta}^*}(\bm{a}_t) - U_t (\bm{a}_t) } + \sum_{t \in [T]} \E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) }$.
\end{lemma}

\begin{proof}
By Proposition 1 in \cite{russo2014learning}, we can decompose the Bayesian regret of the algorithm in the following way:

\begin{align*}
    \text{BayesRegret}(T) = \sum_{t \in [T]} \E{f_{\bm{\theta}^*}(\bm{a}_t) - L_t (\bm{a}_t) } + \sum_{t \in [T]} \E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) } =& \\
    \sum_{t \in [T]} \E{U_t(\bm{a_t}) - L_t(\bm{a_t})} + \sum_{t \in [T]} \E{f_{\bm{\theta}^*}(\bm{a}_t) - U_t (\bm{a}_t) } + \sum_{t \in [T]} \E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) } &
\end{align*}
\end{proof}

\begin{lemma}
\label{lem:over_under_estimation}
For any $t \in [T]$, we have that $\E{f_{\bm{\theta}^*}(\bm{a}_t) - U_t (\bm{a}_t) } \leq \frac{4d}{T}$ and $\E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) } \leq \frac{4d}{T}$.
\end{lemma}

\begin{proof}
\begin{align*}
    \E{L_t (\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) } =& \\
    \E{f_{\hat{\bm{\theta}}_{t-1}}(\bm{a}^*) - f_{\bm{\theta}^*}(\bm{a}^*) - \max_{i \in \bm{a}^*} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}} \leq& \\
    \intertext{(By Lemma \ref{lem:reward_function_bound})}
    \E{2\max_{i \in \bm{a}^*} \vert \hat{\theta}_{i,t-1} - \theta^*_i \vert - \max_{i \in \bm{a}^*} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}} =& \\
    \intertext{(Let $j = \arg \max_{i \in \bm{a}^*} \vert \hat{\theta}_{i,t-1} - \theta^*_i \vert $)}
    \E{2 \vert \hat{\theta}_{j,t-1} - \theta^*_j \vert - \max_{i \in \bm{a}^*} \sqrt{\frac{32 \log T}{N_{t-1}(i)}}} \leq& \\
    \E{2 \vert \hat{\theta}_{j,t-1} - \theta^*_j \vert - \sqrt{\frac{32 \log T}{N_{t-1}(j)}}} \leq& \\
    \E{2 \left[\vert \hat{\theta}_{j,t-1} - \theta^*_j \vert - \sqrt{\frac{8 \log T}{N_{t-1}(j)}}\right]^+} \leq& \\
    \E{2 \sum_{i \in \mathcal{A}} \left[\vert \hat{\theta}_{i,t-1} - \theta^*_i \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}}\right]^+} =& \\
    2 \sum_{i \in \mathcal{A}} \E{ \left[\vert \hat{\theta}_{i,t-1} - \theta^*_i \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}}\right]^+} =& \\
    2 \sum_{i \in \mathcal{A}} \E{ \vert \hat{\theta}_{i,t-1} - \theta^*_i \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; \vert \hat{\theta}_{i,t-1} - \theta^*_i \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \prob{\vert \hat{\theta}_{i,t-1} - \theta^*_i \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \leq& \\
    \intertext{(By Lemma \ref{lem:bad_event_expectation})}
    2 \sum_{i \in \mathcal{A}} \prob{\vert \hat{\theta}_{i,t-1} - \theta^*_i \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \leq& \\
    \intertext{(By Lemma \ref{lem:concentration})}
    2 \sum_{i \in \mathcal{A}} \frac{2}{T} \leq& \\
    \frac{4d}{T} &
\end{align*}

The proof for $\E{f_{\bm{\theta}^*}(\bm{a}_t) - U_t (\bm{a}_t) } \leq \frac{4d}{T}$ is done in the same way.
\end{proof}

\begin{lemma}
\label{lem:reward_function_bound}
For any super arm $\bm{a} \in \mathcal{I}$ and time step $t \in [T]$, we have that $\vert f_{\bm{\theta}^*}(\bm{a}) - f_{\hat{\bm{\theta}}_{t-1}}(\bm{a}) \vert \leq 2 \max_{i\in\bm{a}} \vert \theta^*_i - \hat{\theta}_{i,t-1} \vert$.
\end{lemma}

\begin{proof}

Let $Y_i$ and $Z_i$ for $i \in \bm{a}$ be Gaussian random variables with $Y_i \sim \mathcal{N}(\theta_i^*, \sigma^2_i)$ and $Z_i \sim \mathcal{N}(\hat{\theta}_{i,t-1}, \sigma^2_i)$.

\begin{align*}
\vert f_{\bm{\theta}^*}(\bm{a}) - f_{\hat{\bm{\theta}}_{t-1}}(\bm{a}) \vert =& \\
\left\vert \E{\max_{i \in \bm{a}} Y_i} - \E{\max_{i \in \bm{a}} Z_i} \right\vert =& \\
\intertext{(Define $[x]^+ := \max(0, x)$)}
\left[ \E{\max_{i \in \bm{a}} Y_i} - \E{\max_{i \in \bm{a}} Z_i} \right]^+ + \left[\E{\max_{i \in \bm{a}} Z_i} - \E{\max_{i \in \bm{a}} Y_i} \right]^+ =&
\intertext{(Let $\delta_{i,t-1} := \theta^*_i - \hat{\theta}_{i,t-1}$, $O_i := Y_i + \delta_{i,t-1}$, $Q_i := Z_i - \delta_{i,t-1}$)}
\left[ \E{\max_{i \in \bm{a}} (O_i - \delta_{i,t-1})} - \E{\max_{i \in \bm{a}} Z_i} \right]^+ + \left[\E{\max_{i \in \bm{a}} (Q_i + \delta_{i,t-1})} - \E{\max_{i \in \bm{a}} Y_i} \right]^+ \leq& \\
\left[ \E{\max_{i \in \bm{a}} O_i + \max_{i \in \bm{a}} (-\delta_{i,t-1})} - \E{\max_{i \in \bm{a}} Z_i} \right]^+ + \left[\E{\max_{i \in \bm{a}} Q_i + \max_{i \in \bm{a}} \delta_{i,t-1}} - \E{\max_{i \in \bm{a}} Y_i} \right]^+ =& \\
\left[ \E{\max_{i \in \bm{a}} O_i} + \max_{i \in \bm{a}} (-\delta_{i,t-1}) - \E{\max_{i \in \bm{a}} Z_i} \right]^+ + \left[\E{\max_{i \in \bm{a}} Q_i} + \max_{i \in \bm{a}} \delta_{i,t-1} - \E{\max_{i \in \bm{a}} Y_i} \right]^+ =& \\
\intertext{(Since $\E{\max_{i \in \bm{a}} O_i} = \E{\max_{i \in \bm{a}} Z_i}$ and $\E{\max_{i \in \bm{a}} Q_i} = \E{\max_{i \in \bm{a}} Y_i}$)}
\left[\max_{i \in \bm{a}} (-\delta_{i,t-1})\right]^+ + \left[\max_{i \in \bm{a}} \delta_{i,t-1}\right]^+ \leq& \\
2 \max_{i \in \bm{a}} \vert \delta_{i,t-1} \vert =& \\
2 \max_{i \in \bm{a}} \vert \theta^*_i - \hat{\theta}_{i,t-1} \vert &
\end{align*}
\end{proof}

\begin{lemma}
\label{lem:concentration}
$\prob{\forall t \in [T]\; \forall i \in \mathcal{A},\;\; \vert \theta^*_i - \hat{\theta}_{i,t-1} \vert \leq \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \geq 1 - \frac{2}{T}$.
\end{lemma}

\begin{proof}

We define $\Bar{v}_{i,m}$ as the average feedback of base arm $i$ for the first $m$ times it has been played as part of a super arm, i.e., such that $\hat{\theta}_{i,t} = \Bar{v}_{i,N_{t}(i)}$. Then:

\begin{align*}
    \prob{\forall t \in [T]\; \forall i \in \mathcal{A},\;\; \vert \theta^*_i - \hat{\theta}_{i,t-1} \vert \leq \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} =& \\
    1 - \prob{\exists t \in [T]\; \exists i \in \mathcal{A},\;\; \vert \theta^*_i - \hat{\theta}_{i,t-1} \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \geq& \\
    \intertext{(Union bound)}
    1 - \sum_{i \in \mathcal{A}} \sum_{t \in [T]} \prob{\vert \theta^*_i - \hat{\theta}_{i,t-1} \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} =& \\
    1 - \sum_{i \in \mathcal{A}} \sum_{t \in [T]} \sum_{m = 1}^{t-1} \prob{\vert \theta^*_i - \Bar{v}_{i,m} \vert > \sqrt{\frac{8 \log T}{m}} \;\land\; N_{t-1}(i) = m} \geq& \\
    1 - \sum_{i \in \mathcal{A}} \sum_{t \in [T]} \sum_{m = 1}^{t-1} \prob{\vert \theta^*_i - \Bar{v}_{i,m} \vert > \sqrt{\frac{8 \log T}{m}}} \geq& \\
    \intertext{(Hoeffding inequality, specifically version in Theorem A.2 of \citealt{slivkins2019})}
    1 - \sum_{i \in \mathcal{A}} \sum_{t \in [T]} \sum_{m = 1}^{t-1} \frac{2}{T^4} \geq& \\
    \intertext{(We assume that $T \geq d$)}
    1 - \frac{2}{T} &
\end{align*}
\end{proof}

\begin{lemma}
\label{lem:bad_event_expectation}
For any $t \in [T]$ and $i \in \mathcal{A}$, we have

\begin{align*}
    \E{ \vert \hat{\theta}_{i,t-1} - \theta^*_i \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; \vert \hat{\theta}_{i,t-1} - \theta^*_i \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} \leq 1
\end{align*}
\end{lemma}
\begin{proof}

We know that the average feedback $\hat{\theta}_{i,t-1}$ is Gaussian with $\E{\hat{\theta}_{i,t-1}} = \theta^*_i$ and variance $\leq 1$. Let $Z := \hat{\theta}_{i,t-1} - \theta^*_i$. Then, $Z$ is Gaussian with mean $0$ and variance $\leq 1$. The following holds:

\begin{align*}
    \E{ \vert Z \vert - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; \vert Z \vert > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} =& \\
    \left(\E{ Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; Z > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} + \E{ (- Z) - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; (-Z) > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}}\right)/2 =& \\
    \intertext{($Z$ is $0$-mean Gaussian, hence $Z \overset{d}{=} -Z$)}
    \E{ Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; Z > \sqrt{\frac{8 \log T}{N_{t-1}(i)}}} =& \\
    \E{ Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}}> 0} &
\end{align*}

We notice that $(Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}})$ is Gaussian with mean $(- \sqrt{\frac{8 \log T}{N_{t-1}(i)}})$, where $(- \sqrt{\frac{8 \log T}{N_{t-1}(i)}}) < 0$. Furthermore (see e.g., Theorem 2 in \citealt{horrace2015moments}), the expected value after truncation is increasing in $(- \sqrt{\frac{8 \log T}{N_{t-1}(i)}})$. Hence,

\begin{align*}
    \E{ Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}} \;\;\;\bigg\vert\;\;\; Z - \sqrt{\frac{8 \log T}{N_{t-1}(i)}}> 0} \leq& \\
    \E{ Z \;\;\;\bigg\vert\;\;\; Z > 0} \leq& \\
    \intertext{($Z$ is Gaussian with mean $0$ and variance $\leq 1$)}
    \phi(0) / (1 - \Phi(0)) \leq 1
\end{align*}
\end{proof}

\begin{theorem}
Given the optimal super arm $\bm{a^*}$ for Algorithm 1 and the optimal super arm $\Tilde{\bm{a}}^*$ for Algorithm 2, we have that $ f_{\bm{\theta}^*}(\Tilde{\bm{a}}^*) - f_{\bm{\theta}^*}(\bm{a}^*) \leq \sqrt{2 \log d}$.
\end{theorem}

\begin{proof}

For any super arm $\bm{a} \in \mathcal{I}$, let $Y_i$ for $i \in \bm{a}$ be Gaussian random variables with $Y_i \sim \mathcal{N}(\theta_i^*, \sigma_i^2)$. Let $W_i := Y_i - \theta_i^*$, such that $W_i \sim \mathcal{N}(0, \sigma_i^2)$. Then, the following holds:

\begin{align*}
    \mathbb{E}\left[ \max_{i\in \bm{a}} Y_i \right] =& \\
    \mathbb{E}\left[ \max_{i\in \bm{a}} (W_i + \theta_i^*) \right] \leq& \\
    \mathbb{E}\left[ \max_{i\in \bm{a}} \left(W_i + \max_{j\in \bm{a}} \mathbb{E}\left[ Y_j \right]\right) \right] =& \\
    \mathbb{E}\left[ \max_{i\in \bm{a}} W_i \right] + \max_{i\in \bm{a}} \mathbb{E}\left[ Y_i \right] \leq& \\
    \intertext{(By Lemma 9 in \citealt{orabona2015optimal}, and $\sigma_i^2 \leq 1$ for all $i \in \bm{a}$)}
    \sqrt{2 \log d} + \max_{i\in \bm{a}} \mathbb{E}\left[ Y_i \right]
\end{align*}

Furthermore, by Jensen's inequality, we have $\max_{i\in \bm{a}} \mathbb{E}\left[ Y_i \right] \leq  \mathbb{E}\left[ \max_{i\in \bm{a}} Y_i \right]$. Moreover, by definition we know that $\bm{a}^* = \arg \min_{\bm{a} \in \mathcal{I}} \E{\max_{i \in \bm{a}} Y_i}$ and $\Tilde{\bm{a}}^* = \arg \min_{\bm{a} \in \mathcal{I}} \max_{i \in \bm{a}} \E{ Y_i}$. Consequently, we have:

\begin{align*}
    \max_{i \in \Tilde{\bm{a}}^*} \E{Y_i} \leq& \\
    \max_{i \in \bm{a}^*} \E{Y_i} \leq& \\
    \E{\max_{i \in \bm{a}^*} Y_i} \leq& \\
    \E{\max_{i \in \Tilde{\bm{a}}^*} Y_i} \leq& \\
    \sqrt{2 \log d} + \max_{i\in \Tilde{\bm{a}}^*} \mathbb{E}\left[ Y_i \right]
\end{align*}

Hence, we conclude

\begin{align*}
     f_{\bm{\theta}^*}(\Tilde{\bm{a}}^*) - f_{\bm{\theta}^*}(\bm{a}^*) = \E{\max_{i \in \Tilde{\bm{a}}^*} Y_i} - \E{\max_{i \in \bm{a}^*} Y_i} \leq \sqrt{2 \log d}
\end{align*}

\end{proof}

\subsection{Experimental results}

\renewcommand{\thefigure}{B.\arabic{figure}}
\setcounter{figure}{0}
\renewcommand{\thetable}{B.\arabic{table}}
\setcounter{table}{0}

In this section, we provide more details on our road networks experiment.  In addition, we compare Algorithm 1 to Algorithm 2 through a toy example.

\begin{table}[b]
\centering
\caption{Average cumulative regret and corresponding standard deviation over five runs, at the horizon, denoted by $T$.} \label{tab:inst}
\begin{tabular}{|c|c||c|c||c|c||c|c|}
\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}Road \\ Network\end{tabular}} & \multirow{3}{*}{T} & \multicolumn{6}{c|}{Agent}                                                                              \\ \cline{3-8}
                                                                         &                    & \multicolumn{2}{c||}{Greedy}       & \multicolumn{2}{c||}{B-UCB}      & \multicolumn{2}{c|}{TS}           \\ \cline{3-8}
                                                                         &                    & \multicolumn{1}{c|}{avg.} & SD   & \multicolumn{1}{c|}{avg.} & SD & \multicolumn{1}{|c|}{avg.} & SD    \\ \hline\hline
Eindhoven                                                                & 6000               & 792.7                     & 455.5 & 460.5 & 277.3                   & 269.9                     & 115.6 \\ \hline
Oslo                                                                     & 6000               & 636.7                     & 209.7 & 408.2 & 159.2                   & 272.5                     & 138.9 \\ \hline
Manhattan                                                                & 8000               & 1479.6                    & 475.1 & 757.1 & 157.7                   & 545.1                     & 112.1 \\ \hline
Salzburg                                                                 & 6000               & 1009.3                    & 196.3 & 283.3 & 88.1                    & 141.1                     & 26.1  \\ \hline
\end{tabular}
\end{table}

\subsubsection{Road Networks}

We studied the road networks of four cities in our experiments. Table \ref{tab:inst} shows the average cumulative regrets and their corresponding standard deviations over five runs.

Figure \ref{fig:Inst} illustrates instant regret plots and road networks of Salzburg, Eindhoven, and Oslo  with $T=6000$. One can see that the TS and B-UCB instant regrets are high initially, but they drop in magnitude further on in time because of their exploration. Average cumulative regret plots of mentioned cities are presented in Section 4.

\begin{figure*}[t] \centering
    \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{results_instant_regret_salzburg.png}
         \caption{ \footnotesize{} }
         \label{fig:SlazburgInst}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
      \includegraphics[width=\textwidth]{results_instant_regret_Eindhoven.png}
         \caption{\footnotesize{}}
         \label{fig:EindInstant}
    \end{subfigure}
\begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{results_instant_regret_Oslo.png}
         \caption{ \footnotesize{} }
         \label{fig:OsloInst}
    \end{subfigure}
        \begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{Salzburg.jpg}
         \caption{ \footnotesize{} }
         \label{fig:SlazburgRoad}
    \end{subfigure}
    \begin{subfigure}{0.34\textwidth}
    \centering
    \captionsetup{justification=centering}
      \includegraphics[width=\textwidth]{Eindhoven.jpg}
         \caption{\footnotesize{}}
         \label{fig:EindRoad}
    \end{subfigure}
\begin{subfigure}{0.32\textwidth}
    \centering
    \captionsetup{justification=centering}
        \includegraphics[width=\textwidth]{Oslo.jpg}
         \caption{ \footnotesize{} }
         \label{fig:OsloRoad}
    \end{subfigure}
    \caption{Instant regret averaged over 5 runs for Bayes UCB (B-UCB), greedy (GR), and Thompson Sampling (TS), with horizon $T=6000$, for the Salzburg (a), Eindhoven (b) and Oslo (c) road networks. Below these, visualizations of the paths explored by the TS agent are shown in red, for each road network, respectively. Opacity illustrates the amount of exploration of each of the road segments.}\label{fig:Inst}
\end{figure*}

\subsubsection{Exact objective toy example}

While it is not feasible to evaluate Algorithm 1 on graphs representing real-life transportation or social networks, it is possible for small synthetic graphs. We construct a graph consisting of 6 nodes and 10 edges, with the source and target nodes connected by four paths of length 2 and four paths of length 3. For each edge $e$, we use the sample the mean from a standard Gaussian prior, such that $\theta_e^* \sim \mathcal{N}(0,1)$. The stochastic weights are then generated in each time step $t$ such that $w_{e,t} \sim \mathcal{N}(\theta^*_e, 1)$.

In order to calculate the expected cost of each path, we use existing exact expressions for the expected maximum of two \citep{clark1961greatest} and three \citep{lo2020improving, guptagaussians} independent Gaussian random variables. Instead of using an oracle, we simply enumerate the paths to find the one with minimum expected cost.

In Figure \ref{fig:toy_example}, we compare Algorithm 1 (TS with exact objective) and Algorithm 2 (TS with approximate objective) using the exact notion of (cumulative) regret as defined in Eq. 4. Furthermore, we include a greedy baseline which also uses the exact objective. We use a horizon of $T=10000$ and average the results over 20 experiments, wherein each algorithm is applied to a problem instance sampled from the prior.

We can see that the regret of exact TS quickly saturates, while approximate TS and the greedy method tend to end up in sub-optimal solutions. For approximate TS, this is to be expected since optimal arms for the exact and approximate problems may be different. It is worth noting, however, that approximate TS performs better than the exact greedy method on average.

\begin{figure}[t]
\centering
\includegraphics[width=0.5\columnwidth]{results_toy_example.png}
\caption{Experimental results with average cumulative regret on the toy example, with $T=10000$, on exact TS, approximate TS and exact greedy.}
\label{fig:toy_example}
\end{figure}

\putbib[references]
\end{bibunit}
\end{document}