Thresholding Graph Bandits with GrAPL

Daniel LeJeune Gautam Dasarathy Richard G. Baraniuk

Rice University Arizona State University Rice University

###### Abstract

In this paper, we introduce a new online decision making paradigm that we call
_Thresholding Graph Bandits_. The main goal is to efficiently identify a
subset of arms in a multi-armed bandit problem whose means are above a
specified threshold. While traditionally in such problems, the arms are
assumed to be independent, in our paradigm we further suppose that we have
access to the similarity between the arms in the form of a graph, allowing us
to gain information about the arm means with fewer samples. Such a feature is
particularly relevant in modern decision making problems, where rapid
decisions need to be made in spite of the large number of options available.
We present GrAPL, a novel algorithm for the thresholding graph bandit problem.
We demonstrate theoretically that this algorithm is effective in taking
advantage of the graph structure when the structure is reflective of the
distribution of the rewards. We confirm these theoretical findings via
experiments on both synthetic and real data.

##  1 INTRODUCTION

Systems that recommend products, services, or other attention-targets have
become indispensable in the effective curation of information. Such
personalization and recommendation techniques have become ubiquitous not only
in product/content recommendation and ad placements but also in a wide range
of applications like drug testing, spatial sampling, environmental monitoring,
and rate adaptation in communication networks; see, e.g., Villar et al.
(2015); Combes et al. (2014); Srinivas et al. (2010). These are often modeled
as sequential decision making or _bandit problems_ , where an algorithm needs
to choose among a set of decisions (or arms) sequentially to maximize a
desired performance criterion.

Recently, an important variant of the bandit problem was proposed by Locatelli
et al. (2016) and Gotovos et al. (2013), where the goal is to rapidly identify
all arms that are above (and below) a fixed threshold. This _thresholding
bandit_ framework, which may be thought of as a version of the combinatorial
pure exploration problem (Chen et al., 2014), is useful in various
applications like environmental monitoring, where one might want to identify
the hypoxic (low-oxygen-content) regions in a lake; like crowd-sourcing, where
one might want to keep all workers whose productivity trumps the cost to hire
them; or like political polling, where one wants to identify which political
candidate individual voting districts prefer. Such a procedure may even be
considered in human-in-the-loop machine learning pipelines, where the
algorithm might want to select a set of options that meet a certain cut-off
for closer examination by a human expert.

In many important applications, however, one is faced with an enormous number
of arms that need to sorted through almost instantaneously. This makes prior
approaches untenable both from a computational and from a statistical
viewpoint. However, when there is information sharing between these arms, one
might hope that this situation can be improved.

In this paper, we consider the thresholding bandit problem in the setting
where a graph describing the similarities between the arms is available (see
Section 2). We show that if one leverages this graph information, and more
importantly the _homophily_ (that is, that strong connection implies similar
behavior), then one can achieve significant gains over prior approaches. We
develop a novel algorithm, GrAPL (see Section 3), that explicitly takes
advantage of the graph structure and the homophily. We then characterize,
using rigorous theoretical estimates of the error of GrAPL, how this algorithm
indeed leverages this side information to improve upon prior algorithms in
similar settings. Finally, in Section 4, we confirm these theoretical findings
via experiments on real and synthetic data.

##  2 THRESHOLDING GRAPH BANDITS

###  2.1 Thresholding Bandits

Let $N$ denote the number of bandit arms, which are observable via independent
samples of the corresponding _R-sub-Gaussian_ distributions
$\nu_{i},\;i\in[N]$. That is, each distribution $\nu_{i}$ satisfies the
following condition for all $t\in\mathbb{R}$:

$\displaystyle{\mathbb{E}_{X\sim\nu_{i}}\left[\exp\\{t(X-\mu_{i})\\}\right]\leq\exp\\{R^{2}t^{2}/2\\}},$
(1)

where $\mu_{i}=\mathbb{E}_{X\sim\nu_{i}}[X]$. The goal of a learning algorithm
in the thresholding bandit problem is to recover the superlevel set
$\mathcal{S}_{\tau}=\\{i:\mu_{i}\geq\tau\\}$ from these noisy observations.
The learning algorithm is allowed to run for $T$ iterations, and at each
iteration $t\in[T]$ it can select one arm $\pi_{t}\in[N]$ from which to
receive an observation. At the end of the $T$ iterations, the algorithm
returns its estimate $\widehat{\mathcal{S}}$ of the superlevel set
$\mathcal{S}_{\tau}$. This variant of the multi-armed bandit problem was
introduced by Locatelli et al. (2016), who provided the Anytime Parameter-free
Thresholding (APT) algorithm for solving the problem with matching upper and
lower bounds. Mukherjee et al. (2017) and Zhong et al. (2017) have since
provided algorithmic extensions to APT that incorporate variance estimates and
provide guarantees in asynchronous settings. Recently, Tao et al. (2019)
introduced the Logarithmic-Sample Algorithm and proved it to be instance-wise
asymptotically optimal for minimizing aggregate regret.

The thresholding bandit problem can be thought of as a version of the
combinatorial pure exploration (CPE) bandit problem described by Chen et al.
(2014). As such, the appropriate performance loss measures the quality of the
returned superlevel set estimate $\widehat{\mathcal{S}}$ at time $T$ rather
than a traditional notion of regret. We adopt a natural loss function for this
setting (as done by Locatelli et al. (2016)):

$\displaystyle\mathcal{L}_{T}=\mathds{1}\left\\{\left|(\mathcal{S}_{\tau+\varepsilon}\cap\widehat{\mathcal{S}}^{c})\cup(\mathcal{S}_{\tau-\varepsilon}^{c}\cap\widehat{\mathcal{S}})\right|>0\right\\},$
(2)

which for any $\varepsilon>0$ is the indicator that at least one $i$ such that
$|\mu_{i}-\tau|>\varepsilon$ has been classified as being on the wrong side of
the threshold.

Next, we need a notion of complexity that captures the statistical difficulty
of performing the thresholding. Towards this end, we set
$\Delta_{i}\triangleq\Delta_{i}^{\tau,\varepsilon}=|\mu_{i}-\tau|+\varepsilon$,
where $\varepsilon$ is the same quantity as in the definition of
$\mathcal{L}_{T}$, and define the _complexity_ of the thresholding problem as

$\displaystyle H\triangleq
H_{\tau,\varepsilon}=\sum_{i=1}^{N}\Delta_{i}^{-2}.$ (3)

This definition of complexity also plays a key role in the analysis of
Locatelli et al. (2016). Intuitively, if there are values $\mu_{i}$ that are
near the threshold, then the superlevel set will be “hard” to identify, and
the problem complexity $H$ will be correspondingly high. Conversely, if the
values $\mu_{i}$ are far from the threshold, then the superlevel set will be
“easy” to identify, and the problem complexity is correspondingly small.

###  2.2 Thresholding Graph Bandits

As discussed in the introduction, the main contribution of this paper is to
present a new framework for such thresholding bandit problems where one has
access to additional information about the similarities of arms. In
particular, we will model this additional information as a weighted graph that
describes the arm similarities. Let
$\mathcal{G}=(\mathcal{V},\mathcal{E},\bm{\mathrm{W}})$ denote a similarity
graph defined on the $N$ arms such that each arm is a vertex in $\mathcal{V}$
and $\bm{\mathrm{W}}\in\mathbb{R}^{N\times N}$ describes the weights of the
edges $\mathcal{E}$ between these vertices. Let
${\bm{\mathrm{L}}=\bm{\mathrm{D}}-\bm{\mathrm{W}}}$ denote the graph
Laplacian, where
$\bm{\mathrm{D}}=\mathrm{diag}(\bm{\mathrm{W}}\bm{\mathrm{1}})$ is a diagonal
matrix containing the weighted degrees of each vertex. The graph Laplacian in
this context is functionally quite similar to the precision matrix of a
Gaussian graphical model defined on the same graph, where edges on the graph
indicate conditional dependencies between two arms given all other arms, and
the weight indicates the strength of the partial correlation.

The main idea behind leveraging this similarity graph is that, if the learning
algorithm is aware of the similarity structure among arms through the graph
$\mathcal{G}$, and if the rewards $\bm{\mathrm{\mu}}=(\mu_{i})_{i=1}^{N}$ vary
smoothly among similar arms, then the learning algorithm can leverage the
information sharing to avoid oversampling similar arms.

We capture the effectiveness of the graph in helping with the information
sharing using two related notions of complexity. The first is
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}=\sqrt{\bm{\mathrm{\mu}}^{\top}\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{\mu}}}$,
the $\bm{\mathrm{L}}_{\lambda}$ norm of $\bm{\mathrm{\mu}}$, where
$\bm{\mathrm{L}}_{\lambda}=\bm{\mathrm{L}}+\lambda\mathbf{I}$ for some
$\lambda>0$. It is not hard to check that this value is smaller for those
$\bm{\mathrm{\mu}}$’s that are smooth on the graph $\mathcal{G}$ (see, e.g.,
Ando and Zhang (2007)). The second notion of complexity, the _effective
dimension_ , characterizes the helpfulness of the graph itself.

######  Definition 2.1 (Valko et al., 2014, Def. 1).

For any $\gamma>0$, $T\in\\{1,2,\ldots,N\\}$, the effective dimension $d_{T}$
of the regularized Laplacian $\bm{\mathrm{L}}_{\lambda}$ is the largest $d$
such that

$(d-1)\gamma\lambda_{d}\leq\frac{T}{\log(1+T/\gamma\lambda)},$ (4)

where $\lambda_{d}$ is the $d$-th eigenvalue of $\bm{\mathrm{L}}_{\lambda}$
when $\lambda_{1}\leq\ldots\leq\lambda_{N}$.

In Definition 2.1, $T$ is the time horizon of the algorithm; if $T>N$, then
one may use $N$ instead of $T$ on the right side of (4). $\gamma>0$ is a free
parameter that can be tuned in the algorithm design (see Section 3).

It can be checked readily that the effective dimension is no larger than $N$
for any graph. In fact, as observed by Valko et al. (2014), for many graphs of
interest the effective dimension turns out to be significantly smaller than
$N$. As we will see in Section 3, this quantity plays a key role in capturing
the effectiveness of our algorithm in leveraging the arm-similarity
graph.111We also note here that the same authors proposed an improved
definition of effective dimension that is even smaller and remains applicable
in our setting (see Section 1.3.1 of Valko (2016)).

###  2.3 A Non-adaptive Approach

Before introducing our algorithm for thresholding graph bandits, we first
introduce a useful baseline.

Our algorithm for thresholding graph bandits has two primary components. The
first of these is using the graph structure to regularize the estimate of the
arm means using Laplacian regularization techniques, which have received
considerable attention in recent decades (see Belkin et al., 2005; Zhu et al.,
2003; Ando and Zhang, 2007). The second is an adaptive sampling strategy in
the style of the Anytime Parameter-free Thresholding (APT) algorithm of
Locatelli et al. (2016). In this section, we describe an algorithm which has
only the first component—i.e., an algorithm which uses graph-regularized
estimates of the arm means but selects which arm to sample next non-
adaptively; see Algorithm 1.

Algorithm 1 Thresholding via non-adaptive graph-regularized estimation

1:Input: $\tau,\varepsilon,\bm{\mathrm{L}},\gamma,T$

2:$\bm{\mathrm{V}}_{0}\leftarrow\bm{\mathrm{L}}+\lambda\bm{\mathrm{I}}$

3:$\widehat{\bm{\mathrm{\mu}}}_{0}\leftarrow\tau\bm{\mathrm{1}}$

4:$\bm{\mathrm{n}}_{0}\leftarrow\bm{\mathrm{0}}$

5:for $t$ in $1,\ldots,T$ do

6: Determine $\pi_{t}$ non-adaptively

7: Observe $x_{t}\sim\nu_{\pi_{t}}$

8:
$\bm{\mathrm{V}}_{t}\leftarrow\bm{\mathrm{V}}_{t-1}+\gamma^{-1}\bm{\mathrm{e}}_{\pi_{t}}\bm{\mathrm{e}}_{\pi_{t}}^{\top}$

9:
$\bm{\mathrm{x}}_{t}\leftarrow\bm{\mathrm{x}}_{t-1}+\gamma^{-1}x_{t}\bm{\mathrm{e}}_{\pi_{t}}$

10:
$\widehat{\bm{\mathrm{\mu}}}_{t}\leftarrow\bm{\mathrm{V}}_{t}^{-1}\bm{\mathrm{x}}_{t}$

11:end for

12:Output:
$\widehat{\mathcal{S}}=\left\\{i:\widehat{\mu}_{i}^{T}\geq\tau\right\\}$

At each iteration, Algorithm 1 first selects an arm to sample in a non-
adaptive manner. This could be simply the selection of an arm at random or
cycling through a permutation of the arms, for example.

Next, the algorithm solves the following Laplacian-regularized least-squares
optimization problem for some $\gamma>0$:

$\displaystyle\widehat{\bm{\mathrm{\mu}}}_{t}=\operatorname*{\mathop{\arg\min}}_{\bm{\mathrm{\mu}}}\sum_{s=1}^{t}(x_{s}-\mu_{\pi_{s}})^{2}+\gamma\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2}.$
(5)

This optimization problem is known to promote solutions that are _smooth_
across the graph (see Ando and Zhang, 2007). In fact, let
$\bm{\mathrm{e}}_{i}$ denote the $i$-th standard basis vector and recall that
$\pi_{t}$ denotes the index of the arm pulled at time $t$. If we define the
quantities

$\displaystyle\bm{\mathrm{V}}_{t}$
$\displaystyle=\bm{\mathrm{L}}_{\lambda}+\frac{1}{\gamma}\sum_{s=1}^{t}\bm{\mathrm{e}}_{\pi_{s}}\bm{\mathrm{e}}_{\pi_{s}}^{\top},$
(6) $\displaystyle\bm{\mathrm{x}}_{t}$
$\displaystyle=\frac{1}{\gamma}\sum_{s=1}^{t}x_{s}\bm{\mathrm{e}}_{\pi_{s}},$
(7)

then the above optimization problem admits a solution of the form

$\widehat{\bm{\mathrm{\mu}}}_{t}=\bm{\mathrm{V}}_{t}^{-1}\bm{\mathrm{x}}_{t}.$
(8)

We note that this solution also corresponds to _a posteriori_ estimation of
$\bm{\mathrm{\mu}}$ under a Gaussian prior with precision matrix
$\bm{\mathrm{L}}_{\lambda}$ when the distributions $\nu_{i}$ are Gaussian with
variance $R^{2}$. The following proposition characterizes the performance of
Algorithm 1.

######  Proposition 2.2.

If Algorithm 1 is run using a sampling strategy where every $N$ iterations all
arms are sampled, and
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\leq\sqrt{\frac{T}{\gamma\widetilde{H}}}$,
then for $T=kN$ for any positive integer $k$,

$\displaystyle\mathbb{E}\left[\mathcal{L}_{T}\right]\leq\exp\Bigg{\\{}$
$\displaystyle-\frac{\gamma^{2}}{2R^{2}}\left(\sqrt{\frac{T}{\gamma\widetilde{H}}}-\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)^{2}$
$\displaystyle+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\Bigg{\\}},$ (9)

where $\widetilde{H}\triangleq
N/\min{\\{|\mu_{i}-\tau|^{2}:|\mu_{i}-\tau|\geq\varepsilon\\}}$.

Thus with a non-adaptive algorithm, the complexity depends only on the most
difficult arm (the arm with $\mu_{i}$ closest to the threshold). As we will
see next, with our adaptive approach, the complexity and therefore the
algorithmic performance can be significantly improved when there are arms
further away from the threshold.

##  3 GrAPL

In this section, we present our algorithm for thresholding graph bandits. Our
algorithm is inspired in part by the Anytime Parameter-free Thresholding (APT)
algorithm of Locatelli et al. (2016), and also by the work of Valko et al.
(2014), who applied Laplacian regularization to the bandit estimator through
the eigenvectors of $\bm{\mathrm{L}}_{\lambda}$. Unlike Valko et al. (2014),
however, we use the Laplacian directly, and we include the tunable
regularization parameter $\gamma$. We dub our algorithm the Graph-based
Anytime Parameter-Light thresholding algorithm (GrAPL); see Algorithm 2.

Algorithm 2 GrAPL

1:Input: $\tau,\varepsilon,\bm{\mathrm{L}},\gamma,\alpha,\lambda,T$

2:$\bm{\mathrm{V}}_{0}\leftarrow\bm{\mathrm{L}}+\lambda\bm{\mathrm{I}}$

3:$\widehat{\bm{\mathrm{\mu}}}_{0}\leftarrow\tau\bm{\mathrm{1}}$

4:$\widehat{\bm{\mathrm{\Delta}}}_{0}\leftarrow\varepsilon\bm{\mathrm{1}}$

5:$\bm{\mathrm{n}}_{0}\leftarrow\bm{\mathrm{0}}$

6:for $t$ in $1,\ldots,T$ do

7:
$z_{i}^{t}\leftarrow\widehat{\Delta}_{i}^{t-1}\sqrt{n_{i}^{t-1}+\alpha}\;\forall
i$

8: $\pi_{t}\leftarrow\operatorname*{\mathop{\arg\min}}_{i}z_{i}^{t}$

9: Observe $x_{t}\sim\nu_{\pi_{t}}$

10:
$\bm{\mathrm{V}}_{t}\leftarrow\bm{\mathrm{V}}_{t-1}+\gamma^{-1}\bm{\mathrm{e}}_{\pi_{t}}\bm{\mathrm{e}}_{\pi_{t}}^{\top}$

11:
$\bm{\mathrm{x}}_{t}\leftarrow\bm{\mathrm{x}}_{t-1}+\gamma^{-1}x_{t}\bm{\mathrm{e}}_{\pi_{t}}$

12:
$\widehat{\bm{\mathrm{\mu}}}_{t}\leftarrow\bm{\mathrm{V}}_{t}^{-1}\bm{\mathrm{x}}_{t}$

13:
$\widehat{\Delta}_{i}^{t}\leftarrow|\widehat{\mu}_{i}^{t}-\tau|+\varepsilon\;\forall
i$

14:
$\bm{\mathrm{n}}_{t}\leftarrow\bm{\mathrm{n}}_{t-1}+\bm{\mathrm{e}}_{\pi_{t}}$

15:end for

16:Output:
$\widehat{\mathcal{S}}=\left\\{i:\widehat{\mu}_{i}^{T}\geq\tau\right\\}$

At each iteration, GrAPL performs the same estimation routine as Algorithm 1.
Where it differs is in the strategy for choosing the next arm to sample. To
select the arm at iteration $t+1$, we estimate our distances from the
threshold via

$\displaystyle\widehat{\Delta}_{i}^{t}$
$\displaystyle=|\widehat{\mu}_{i}^{t}-\tau|+\varepsilon.$ (10)

We then use these to compute confidence proxies

$\displaystyle z_{i}^{t+1}=\widehat{\Delta}_{i}^{t}\sqrt{n_{i}^{t}+\alpha},$
(11)

where $n_{i}^{t}$ is the number of times arm $i$ has been selected up to time
$t$, and $\alpha>0$ is some small quantity that keeps $z_{i}^{t}$ from being
equal to zero before arm $i$ is sampled. Finally, the algorithm selects the
next arm as

$\displaystyle\pi_{t}=\operatorname*{\mathop{\arg\min}}_{i}{z_{i}^{t}},$ (12)

and the next sample is drawn as $x_{t}\sim\nu_{\pi_{t}}$. The algorithm then
repeats the process in the subsequent iterations until stopped at time $T$.

While GrAPL has three parameters—namely, $\alpha$, $\lambda$, and $\gamma$—and
is therefore not truly parameter-free like APT, the only parameter that needs
to be tuned to the specific problem instance is $\gamma$. A value such as
$10^{-3}$ for $\lambda$ is sufficient to stabilize the linear system solving
in (8) for many problems. If we wish for the algorithm to sample all arms at
least once before sampling an arm twice, we can let $\alpha$ be some very
small value, such as $10^{-8}$; otherwise, we can let $\alpha$ be a larger
value such as $1$. The parameter $\gamma$ is the only parameter that we might
wish to choose appropriately based on the graph and the properties of
$\bm{\mathrm{\mu}}$—see Section 3.3 for a deeper discussion. However, we note
that our main result in Theorem 3.1 below is valid for _any_ values of
$\alpha$, $\lambda$, and $\gamma$.

In terms of implementation, we note that while (8) involves solving a linear
system which can be expensive in general, if the graph is sparse, then there
exist techniques to solve this system efficiently (in time nearly linear in
the number of edges in the graph). Even if the graph is not sparse, it can be
“sparsified” so that the system can be approximately solved efficiently. We
refer the reader to Vishnoi (2013) for more details. We believe this approach
(solving the system with $\bm{\mathrm{V}}_{t}$ directly) significantly reduces
the complexity of implementing a graph-based bandit algorithm compared to the
approach of Valko et al. (2014), which requires a computation of the
eigenspace of $\bm{\mathrm{L}}_{\lambda}$. While computing a restricted
eigenspace can also be done efficiently using similar techniques, $GrAPL{}$
can be implemented in only a few lines of code using a standard solver such as
the conjugate gradient method, readily available in common scientific
computing packages in most programming languages. We have found such an
implementation222See https://github.com/dlej/grapl. fast enough for our
purposes when the solver is initialized with the solution from the previous
iteration. Though we do not include very large graphs in our experiments in
this paper, we have successfully applied GrAPL to sparse graphs with over
100,000 vertices with no major difficulty.

###  3.1 Error Upper Bounds

We present a bound on the error that quantifies the extent to which GrAPL is
able to leverage both the graph structure itself and the smoothness of
$\bm{\mathrm{\mu}}$ on the graph.

######  Theorem 3.1.

If Algorithm 2 is run on a graph
$\mathcal{G}(\mathcal{V},\mathcal{E},\bm{\mathrm{W}})$ with Laplacian
$\bm{\mathrm{L}}$ and effective dimension $d_{T}$, and
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\leq\frac{1}{3M+1}\sqrt{\frac{T}{\gamma
H}}$, then

$\displaystyle\mathbb{E}\left[\mathcal{L}_{T}\right]\leq\exp\Bigg{\\{}$
$\displaystyle-\frac{\gamma^{2}}{2R^{2}}\left(\frac{1}{3M+1}\sqrt{\frac{T}{\gamma
H}}-\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)^{2}$
$\displaystyle+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\Bigg{\\}},$
(13)

where
$M\triangleq\max{\left\\{\sqrt{\alpha/\gamma\lambda},\sqrt{1+\alpha}\right\\}}.$

######  Remark 3.2.

While one must exercise caution when comparing upper bounds, we note that the
primary difference between the performance bounds of Algorithm 1 and GrAPL is
in the complexity quantities. The relationship between these two is given by

$\displaystyle\widetilde{H}\geq\sum_{i=1}^{N}\left(\max{\left\\{|\mu_{i}-\tau|,\varepsilon\right\\}}\right)^{-2}\geq
H.$ (14)

That is, in the worst case, where all values $\mu_{i}$ are close to the
threshold $\tau$, we expect both Algorithm 1 and GrAPL to perform similarly,
but when there are only a few values $\mu_{i}$ near $\tau$, we expect GrAPL to
have a significant advantage.

######  Remark 3.3.

We can decompose $T$ as $T=T_{0}+T_{1}$, where

$\displaystyle T_{0}=\gamma
H(3M+1)^{2}\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2}$ (15)

is the iteration at which the condition for Theorem 3.1 is met, and $T_{1}$ is
the number of iterations after $T_{0}$. Then for $T_{1}\geq 8T_{0}$, the
right-hand side of (3.1) can be upper bounded by

$\displaystyle\exp\left\\{-\frac{\gamma
T_{1}}{4(3M+1)^{2}R^{2}H}+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\right\\}.$
(16)

While this quantity is controllable by the parameter $\gamma$, this control is
limited by the the dependence of $T_{0}$ on $\gamma$. However, with smaller
values of $\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}$—that is, a
_smoother_ graph signal—we may realize the faster convergence rates associated
with larger values of $\gamma$.

######  Remark 3.4.

If we consider the two summands in the exponent of (16), one of the form
$-\Theta(T)$ and the other of the form $\Theta(d_{T}\log T)$, then we can
define the _critical iteration_ $T_{\mathrm{crit}}$ as the iteration at which
point the first of these terms begins to dominate and the bound begins to
rapidly decay with $T$. Specifically, $T_{\mathrm{crit}}$ is the iteration at
which these two terms are equal in magnitude. If we allow the notation
$\widetilde{\Theta}(\cdot)$ to absorb logarithmic factors, we have that
$T_{\mathrm{crit}}=\widetilde{\Theta}(d_{T})$. This is already a significant
improvement over the standard thresholding bandit problem, where every arm
must be drawn at least once, so $T_{\mathrm{crit}}=\widetilde{\Theta}(N)$.

######  Remark 3.5.

The quantity $\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}$ can be
considered with respect to any reference offset used to estimate
$\widehat{\bm{\mathrm{\mu}}}$. For example, if we replaced (8) and (7) with

$\displaystyle\widehat{\bm{\mathrm{\mu}}}_{t}$
$\displaystyle=\bm{\mathrm{V}}_{t}^{-1}\bm{\mathrm{x}}_{t}+\tau\bm{\mathrm{1}}$
(17) $\displaystyle\bm{\mathrm{x}}_{t}$
$\displaystyle=\frac{1}{\gamma}\sum_{s=1}^{t}(x_{s}-\tau)\bm{\mathrm{e}}_{\pi_{s}},$
(18)

then the $\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}$ quantities in the
above bound would be replaced by
$\|\bm{\mathrm{\mu}}-\tau\bm{\mathrm{1}}\|_{\bm{\mathrm{L}}_{\lambda}}$.

###  3.2 Optimality

####  3.2.1 Oracle Sampling Strategy

Consider an oracle algorithm that uses the same estimation strategy as
Algorithm 1 and GrAPL but has access to the values of $|\mu_{i}-\tau|$ and
need only identify the sign of $\mu_{i}-\tau$. Instead of a non-adaptive
sampling strategy, let this algorithm sample according to its knowledge of
$|\mu_{i}-\tau|$. For such an algorithm, if we relax the notion of sampling to
allow the algorithm to make non-integer sample allocations according to an
allocation rule $\bm{\mathrm{\beta}}$ (obeying $\beta_{i}\geq 0$ and
$\sum_{i}\beta_{i}=1$) such that $n_{i}^{t}=\beta_{i}t$, we obtain the
following result.

######  Proposition 3.6.

For the oracle algorithm with sampling allocation $\bm{\mathrm{\beta}}$, if
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\leq\sqrt{\frac{T}{\gamma
H_{*}}}$, then

$\displaystyle\inf_{\bm{\mathrm{\beta}}}\mathbb{E}\left[\mathcal{L}_{T}\right]\leq\exp\Bigg{\\{}$
$\displaystyle-\frac{\gamma^{2}}{2R^{2}}\left(\sqrt{\frac{T}{\gamma
H_{*}}}-\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)^{2}$
$\displaystyle+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\Bigg{\\}},$
(19)

where
$H_{*}\triangleq\sum_{j:|\mu_{j}-\tau|\geq\varepsilon}|\mu_{j}-\tau|^{-2}$.

We note the similarity between $H$ and $H_{*}$. Using the fact that
$|\mu_{i}-\tau|+\varepsilon\leq 2|\mu_{i}-\tau|$ for
$|\mu_{i}-\tau|\geq\varepsilon$, we can relate the two by

$\displaystyle 4H\geq H_{*}\geq H-\varepsilon^{-2}N_{\mathrm{small}},$ (20)

where
$N_{\mathrm{small}}=\left|\left\\{i:|\mu_{i}-\tau|<\varepsilon\right\\}\right|$.
So, except in cases where there are many values $\mu_{i}$ that are near the
threshold, the performance upper bound of GrAPL matches that of the oracle
algorithm. However, in cases where there are many values $\mu_{i}$ that are
within $\varepsilon$ of the threshold, the oracle algorithm can have
significantly lower complexity.

####  3.2.2 Lower Bound for Disconnected Cliques

Consider the following family of graphs of size $N$ consisting of $D$
disconnected $K$-cliques and associated graph signals $\bm{\mathrm{\mu}}$ such
that for each arm $i$ belonging to clique $j$, $\mu_{i}=\mu_{j}$. For this
family of graphs and signals, the thresholding graph bandit problem reduces to
the thresholding bandit problem on $D$ independent arms with complexity
$H^{\prime}\triangleq\sum_{j=1}^{D}(|\mu_{j}-\tau|+\varepsilon)^{-2}=H/K$.
This gives us the following lower bound from Locatelli et al. (2016):

$\displaystyle\mathbb{E}\left[\mathcal{L}_{T}\right]\geq\exp\left\\{-\frac{3KT}{R^{2}H}-4\log(12(\log(T)+1)N)\right\\}.$
(21)

For the lower bound, then, $T_{\mathrm{crit}}=\widetilde{\Theta}(R^{2}H/K)$.

For this family of graphs, the graph Laplacian consists of a matrix with $D$
blocks of the form $K\bm{\mathrm{I}}_{K}-\bm{\mathrm{J}}_{K}$, where
$\bm{\mathrm{J}}_{K}$ is the $K\times K$ matrix of all ones. Therefore, the
eigenvalues of $\bm{\mathrm{L}}_{\lambda}$ are $\lambda$ with multiplicity $D$
and $K+\lambda$ with multiplicity $N-D$. Thus, the effective dimension is the
larger of

$\displaystyle\min\left\\{D,\left\lfloor
1+\frac{T}{\gamma\lambda\log(1+T/\gamma\lambda)}\right\rfloor\right\\}$

and

$\displaystyle\min\left\\{N,\left\lfloor
1+\frac{T}{\gamma(K+\lambda)\log(1+T/\gamma\lambda)}\right\rfloor\right\\}.$

For any desired time horizon (e.g., $T\leq 10,000$), for sufficiently small
$\lambda$, this will result in $d_{T}\leq D$. We also note that for this class
of signals,
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2}=\lambda\|\bm{\mathrm{\mu}}\|_{2}^{2}$,
so for sufficiently small $\lambda$, the bound in Theorem 3.1 holds for all
$T$.

Considering the form of our upper bound in (16), we have for this problem
class that
$T_{\mathrm{crit}}=\widetilde{\Theta}(DR^{2}H/\gamma)=\widetilde{\Theta}(NR^{2}H/\gamma
K)$. So, considering a fixed $N$ and $\gamma$, we can say that GrAPL has
optimal $T_{\mathrm{crit}}$ (up to logarithmic factors) with respect to $R$,
$H$, and $K$ (equivalently, $D$) for this family of graphs and signals. With
$\gamma=N$, this rate would also be optimal with respect to $N$ if it were not
for the condition in (15).

####  3.2.3 Linear Bandits

As pointed out by Valko et al. (2014), if $\bm{\mathrm{\mu}}$ lies in the span
of $D$ eigenvectors of $\bm{\mathrm{L}}$, then the graph bandit problem
reduces to the problem of thresholding _linear bandits_ (Auer, 2003). Results
from the _best arm identification_ problem in linear bandits (Soare et al.,
2014; Tao et al., 2018), another example of pure exploration bandits, suggest
that the optimal sample complexity is linear in the underlying dimension $D$.
In the above example with graphs consisting of $D$ cliques, signal
$\bm{\mathrm{\mu}}$ lies in the span of the $D$ eigenvectors corresponding to
the smallest eigenvalues of $\bm{\mathrm{L}}$, and so our result that
$T_{\mathrm{crit}}=\widetilde{\Theta}(D)$ in this setting is consistent with
results from linear bandits.

###  3.3 Choice of Regularization Parameter

GrAPL has a free parameter $\gamma$ which can be tuned to optimize
$T_{\mathrm{crit}}$, which we discuss in this section. $T_{\mathrm{crit}}$
will be on the order of the larger of $T_{0}$ and $T_{1}$, so to optimize
$T_{\mathrm{crit}}$, we must fix $T_{0}$ and $T_{1}$ to be of the same order.
Here, we simply set $T_{1}=8T_{0}$. Then our optimal choice of $\gamma$ is
that which satisfies (15) and

$\displaystyle\frac{\gamma
T_{1}}{4(3M+1)^{2}R^{2}H}=d_{T_{0}+T_{1}}\log\left(1+\frac{T_{0}+T_{1}}{\gamma\lambda}\right).$

After some algebra, we obtain

$\displaystyle\gamma^{*}=\frac{2R}{\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}}\sqrt{d^{\prime}\log\left(1+\frac{9H(3M+1)^{2}\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2}}{\lambda}\right)},$
(22)

where $d^{\prime}$, the effective dimension at time $T_{0}+T_{1}$ for this
choice of $\gamma$, is the largest $d$ such that

$\displaystyle(d-1)\lambda_{d}\leq\frac{9H(3M+1)^{2}\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2}}{\log\left(1+\frac{9H(3M+1)^{2}\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2}}{\lambda}\right)}.$

As we would expect, the smoother the graph signal is (smaller
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}$) and the larger the amount
of noise, the larger $\gamma$ (the more smoothing) we will require. All
together, this gives us
$T_{\mathrm{crit}}=\widetilde{\Theta}(\sqrt{d^{\prime}}R\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}H)$.
In the worst case, when the graph structure is unhelpful (i.e., when
$d^{\prime}=N$) and the signal is not smooth on the graph (i.e.,
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}=\Theta(\sqrt{N})$), this
gives $T_{\mathrm{crit}}$ a linear dependence on $N$, as we would expect. On
the other hand, in the setting of $D$ cliques, where for sufficiently small
$\lambda$ we can consider
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}=\Theta(\sqrt{D})$, we again
obtain $T_{\mathrm{crit}}=\widetilde{\Theta}(D)$.

##  4 EXPERIMENTS

In experiments on both artificial and real data we demonstrate the advantage
of GrAPL over the APT algorithm of Locatelli et al. (2016), which does not
utilize the graph information, and over Algorithm 1, which uses non-adaptive
random arm sampling. We demonstrate that exploiting the graph structure can
significantly reduce the number of samples necessary to obtain a good estimate
of the superlevel set, and that the adaptive arm selection rule of GrAPL
further reduces the number of samples necessary over non-adaptive sampling
with the same graph-regularized estimator.

###  4.1 Stochastic Block Model

In our first experiment, we let $N=1000$ and sample an unweighted, undirected
graph from a stochastic block model with two communities of size $N/2$, with
within-community edge probability $\log(N/2)/(N/2)$ and between-community edge
probability $\log(N/2)/(N/2)^{3/2}$. We let

$\displaystyle\mu_{i}=\begin{cases}1&i\leq N/2\\\
-1&\text{otherwise},\end{cases}$

and we make the distribution of each arm Gaussian with $\sigma=2$. For GrAPL,
we let $\lambda=10^{-3}$ and $\alpha=1$. With $\tau=0$ and $\varepsilon=0.01$,
we run the algorithms for $T=5000$ iterations and compute the
misclassification error $E$ at each iteration $t$, defined as

$\displaystyle
E=\frac{\left|(\mathcal{S}_{\tau+\varepsilon}\cap\widehat{\mathcal{S}}^{c})\cup(\mathcal{S}_{\tau-\varepsilon}^{c}\cap\widehat{\mathcal{S}})\right|}{\left|\mathcal{S}_{\tau+\varepsilon}\cup\mathcal{S}_{\tau-\varepsilon}^{c}\right|}.$
(23)

Figure 1 shows the median misclassification error for each algorithm and
choice of $\gamma$ over $100$ trials along with the interquartile range. We
note that APT is initialized with an additional $2N=2000$ samples before its
first iteration, so for APT the actual number of samples collected is higher
than the iteration counter. Both GrAPL and Algorithm 1 (for sufficiently large
$\gamma$) are able to exploit the graph structure and converge to the correct
superlevel set much more quickly than APT. However, consistently across values
of $\gamma$, GrAPL converges in turn much more quickly than its non-adaptive
counterpart. In particular, GrAPL makes significant gains in early iterations
and appears to be more robust to the choice of $\gamma$. We also computed
$\gamma^{*}$ according to (22) for this problem and found the average
$\gamma^{*}$ to be 28.72 with a standard deviation of 1.15 over 100 trials,
which agrees with the good performance of GrAPL with $\gamma=10$ and
$\gamma=100$.

Figure 1: Misclassification error $E$ vs. iteration $t$ on the stochastic
block model problem for GrAPL (solid), APT (dashed), and Algorithm 1 (dotted).
Lines indicate the median error, and shaded areas around the lines indicate
the interquartile range. Solid and dotted lines of the same color use the same
value of $\gamma$ for GrAPL and Algorithm 1, respectively.

###  4.2 Small-World Graph

In our next experiment, we again let $N=1000$ and sample small-world graphs
according to the model of Newman and Watts (1999) with new-edge probability
$0.01$ and ring initialized with $4$ neighbors. To generate our smooth signal,
we first generate an i.i.d. Gaussian vector $\bm{\mathrm{y}}\in\mathbb{R}^{N}$
and compute

$\displaystyle\bm{\mathrm{\mu}}_{0}=(\bm{\mathrm{L}}+\bm{\mathrm{I}}/N^{2})^{-1}\bm{\mathrm{y}},$

which we then normalize to have zero median and standard deviation 0.2. The
multiplication by $(\bm{\mathrm{L}}+\bm{\mathrm{I}}/N^{2})^{-1}$ serves
essentially to project $\bm{\mathrm{y}}$ onto the eigenspace of
$\bm{\mathrm{L}}$ corresponding to its smallest eigenvalues, which vary
smoothly along the graph. Following this, we obtain $\bm{\mathrm{\mu}}$ by
adding 0.5 to the signal and clipping the values to be between 0 and 1. The
distribution of each arm is Bernoulli with probability $\mu_{i}$. With
$\tau=0.5$ and $\varepsilon=0.01$, the problem is quite difficult.

Figure 2 shows the misclassification error for this problem when the
algorithms are run over 100 trials for $T=5000$ iterations. As before, we show
the median error and interquartile range. For GrAPL, we let $\lambda=10^{-3}$
and $\alpha=10^{-8}$, and we estimate $\widehat{\bm{\mathrm{\mu}}}$ with
respect to the offset $\tau$ as described in Remark 3.5. On this much more
difficult problem, we have selected a wider range of values for $\gamma$. Here
we again see that although with the best choice of $\gamma$ the advantage of
GrAPL is only slight over Algorithm 1, GrAPL is much more robust to the choice
of $\gamma$, and for poorly chosen $\gamma$ the non-adaptive algorithm
provides almost no advantage over APT. We found the average $\gamma^{*}$ to be
227.9 with a standard deviation of 50.9 over 100 trials for this problem,
which agrees with our finding the best performance at $\gamma=100$. Lastly, we
note that an artifact of the choice of very small $\alpha$ is that there is a
spike in error around $t=N$ which corresponds to GrAPL prioritizing sampling
each arm at least once over the adaptive strategy.

Figure 2: Misclassification error $E$ vs iteration $t$ on the small-world
graph problem for GrAPL (solid), APT (dashed), and Algorithm 1 (dotted). Lines
indicate the median error, and shaded areas around the lines indicate the
interquartile range. Solid and dotted lines of the same color use the same
value of $\gamma$ for GrAPL and Algorithm 1, respectively.

###  4.3 Political Blogs

In our experiment on real-world data, we use the political blogs graph from
Adamic and Glance (2005). The vertices in the graph correspond to political
blogs commenting on US politics around the time of the 2004 U.S. presidential
campaign, and edges denote links from one blog to another. The signal
$\bm{\mathrm{\mu}}$ associated with this graph is

$\displaystyle\mu_{i}=\begin{cases}1&\text{blog $i$ is conservative-
leaning}\\\ 0&\text{blog $i$ is liberal-leaning}.\end{cases}$

We make the edges undirected and set the edge weight equal to the total number
of links from one blog to the other, and then take the largest connected
component, which contained 1222 blogs. The problem we simulate then is that we
would like to identify which of these blogs are conservative and liberal
without actually having to visit and read each blog (expensive sampling), and
we have access to this additional graph information (and cheap computation
compared to the time it would take to visit a blog). We make the distribution
of each arm non-random and let the algorithms take at most $N$ samples. Since
APT requires $2N$ samples for initialization, we do not compare against APT.

Figure 3 shows the misclassification error for $\tau=0.5$ and
$\varepsilon=0.01$, with median error and interquantile range over 100 trials
for Algorithm 1. We run GrAPL with $\lambda=10^{-3}$ and $\alpha=10^{-8}$,
using offset $\tau$, and vary $\gamma$, but we do not run repeated trials
since the observations are non-random. The results are similar to before, in
that using the graph structure provides much better results than not using the
graph, and in that we see GrAPL consistently outperforming Algorithm 1. For
instance, with $\gamma=10^{-5}$, GrAPL is able to reach 1% error at $t\approx
400$, while its random counterpart over the majority of trials does not do the
same until $t>1000$. We would expect the optimal $\gamma$ to be the smallest
$\gamma$ possible based on (22), since there is no noise in the problem.
However, for $\gamma=10^{-7}$, floating point rounding begins to become an
issue—effectively, there is a small nonzero amount of noise due to
rounding—and the performance of GrAPL is worse than with the larger values of
$\gamma$.

Figure 3: Misclassification error $E$ vs iteration $t$ on the political blogs
problem for GrAPL (solid), Algorithm 1 (dotted), and using no graph (dashed).
For Algorithm 1, lines indicate median error, and shaded areas around the
lines indicate the interquartile range. Solid and dotted lines of the same
color use the same value of $\gamma$.

##  5 CONCLUDING REMARKS

In this paper we have introduced a new paradigm of online sequential decision
making that we call Thresholding Graph Bandits, where the main objective is
the identification of the superlevel set of arms whose means are above a given
threshold in a multi-armed bandit setting. Importantly, in our framework, we
have supposed that we have access to a graph that encodes the similarity
between the arms. We have developed GrAPL, a novel algorithm for this
thresholding graph bandits problem, along with theoretical results that show
the relationship between the misclassification rate of GrAPL, the number of
arm pulls, the graph structure, and the smoothness of the reward function with
respect to the given graph. We have also demonstrated that GrAPL is optimal in
terms of the number of arm pulls, the statistical hardness, and the
dimensionality of the problem. Finally, we have confirmed our theoretical
results via experiments on synthetic and real data, highlighting the
significant gains to be had in leveraging the graph information with an
adaptive algorithm.

#### Acknowledgements

This work was supported by NSF grants CCF-1911094, IIS-1838177, and
IIS-1730574; ONR grants N00014-18-12571 and N00014-17-1-2551; AFOSR grant
FA9550-18-1-0478; DARPA grant G001534-7500; and a Vannevar Bush Faculty
Fellowship, ONR grant N00014-18-1-2047.

## References

  * Abbasi-Yadkori et al. (2011) Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems 24_ , pages 2312–2320, 2011.
  * Adamic and Glance (2005) L. A. Adamic and N. Glance.  The political blogosphere and the 2004 US election: divided they blog.  In _Proceedings of the 3rd International Workshop on Link Discovery_ , pages 36–43. ACM, 2005.
  * Ando and Zhang (2007) R. K. Ando and T. Zhang.  Learning on graph with laplacian regularization.  In _Advances in Neural Information Processing Systems 19_ , pages 25–32, 2007.
  * Auer (2003) P. Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3:397–422, 2003\.
  * Belkin et al. (2005) M. Belkin, P. Niyogi, and V. Sindhwani.  On manifold regularization.  In _Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics_ , pages 17–24, 2005.
  * Chen et al. (2014) S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen.  Combinatorial pure exploration of multi-armed bandits.  In _Advances in Neural Information Processing Systems 27_ , pages 379–387, 2014.
  * Combes et al. (2014) R. Combes, A. Proutiere, D. Yun, J. Ok, and Y. Yi.  Optimal rate sampling in 802.11 systems.  In _Proceedings of IEEE INFOCOM 2014 – IEEE Conference on Computer Communications_ , pages 2760–2767, 2014.
  * Gotovos et al. (2013) A. Gotovos, N. Casati, G. Hitz, and A. Krause.  Active learning for level set estimation.  In _Proceedings of the 23rd International Joint Conference on Artificial Intelligence_ , pages 1344–1350, 2013.
  * Locatelli et al. (2016) A. Locatelli, M. Gutzeit, and A. Carpentier.  An optimal algorithm for the thresholding bandit problem.  In _Proceedings of The 33rd International Conference on Machine Learning_ , pages 1690–1698, 2016.
  * Mukherjee et al. (2017) S. Mukherjee, N. K. Purushothama, N. Sudarsanam, and B. Ravindran.  Thresholding bandits with augmented UCB.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , pages 2515–2521, 2017.
  * Newman and Watts (1999) M. E. Newman and D. J. Watts.  Renormalization group analysis of the small-world network model.  _Physics Letters A_ , 263(4-6):341–346, 1999\.
  * Soare et al. (2014) M. Soare, A. Lazaric, and R. Munos.  Best-arm identification in linear bandits.  In _Advances in Neural Information Processing Systems 27_ , pages 828–836. 2014.
  * Srinivas et al. (2010) N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger.  Gaussian process optimization in the bandit setting: No regret and experimental design.  In _Proceedings of the 27th International Conference on Machine Learning_ , pages 1015–1022, 2010.
  * Tao et al. (2018) C. Tao, S. Blanco, and Y. Zhou.  Best arm identification in linear bandits with linear dimension dependency.  In _Proceedings of the 35th International Conference on Machine Learning_ , pages 4877–4886, 2018.
  * Tao et al. (2019) C. Tao, S. Blanco, J. Peng, and Y. Zhou.  Thresholding bandit with optimal aggregate regret.  In _Advances in Neural Information Processing Systems 32_ , pages 11664–11673. 2019.
  * Valko (2016) M. Valko.  _Bandits on graphs and structures_.  habilitation thesis, École normale supérieure de Cachan, 2016\.
  * Valko et al. (2014) M. Valko, R. Munos, B. Kveton, and T. Kocák.  Spectral bandits for smooth graph functions.  In _Proceedings of the 31st International Conference on Machine Learning_ , pages 46–54, 2014.
  * Villar et al. (2015) S. S. Villar, J. Bowden, and J. Wason.  Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges.  _Statistical science: a review journal of the Institute of Mathematical Statistics_ , 30(2):199–215, 2015.
  * Vishnoi (2013) N. K. Vishnoi.  Lx=b. Laplacian solvers and their algorithmic applications.  _Foundations and Trends® in Theoretical Computer Science_ , 8(1–2):1–141, 2013.
  * Zhong et al. (2017) J. Zhong, Y. Huang, and J. Liu.  Asynchronous parallel empirical variance guided algorithms for the thresholding bandit problem.  _arXiv preprint arXiv:1704.04567_ , 2017.
  * Zhu et al. (2003) X. Zhu, Z. Ghahramani, and J. D. Lafferty.  Semi-supervised learning using gaussian fields and harmonic functions.  In _Proceedings of the 20th International Conference on Machine Learning_ , pages 912–919, 2003.

##  Appendix A USEFUL LEMMAS

We introduce the additional notation of

$\displaystyle\bm{\mathrm{\xi}}_{t}=\sum_{s=1}^{t}\bm{\mathrm{e}}_{\pi_{s}}(x_{s}-\mu_{\pi_{s}}),$
(24) $\displaystyle\sigma_{i}^{t}=\sqrt{(\bm{\mathrm{V}}_{t}^{-1})_{ii}},$
(25) $\displaystyle\bm{\mathrm{N}}_{t}=\mathrm{diag}(\bm{\mathrm{n}}_{t}),$
(26)

to be used in the proofs of our results. The following lemmas are proved in
Section E.

######  Lemma A.1.

With probability at least $1-\delta$, for any $i\in[N]$ and $t\geq 1$,

$|\widehat{\mu}_{i}^{t}-\mu_{i}|\leq\sigma_{i}^{t}\left(\frac{R}{\gamma}\sqrt{\log\left(\frac{|\bm{\mathrm{V}}_{t}|}{\delta^{2}|\bm{\mathrm{L}}_{\lambda}|}\right)}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right).$
(27)

######  Lemma A.2.

For all $i\in[N]$ and $t\geq 0$,

$\sigma_{i}^{t}\leq\sqrt{\frac{(\sigma_{i}^{0})^{2}}{1+(\sigma_{i}^{0})^{2}n_{i}^{t}/\gamma}}.$
(28)

######  Lemma A.3.

Let $d_{T}$ be the effective dimension. Then

$\log\frac{|\bm{\mathrm{V}}_{T}|}{|\bm{\mathrm{L}}_{\lambda}|}\leq
2d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right).$ (29)

##  Appendix B PROOF OF PROPOSITION 2.2

For Algorithm 1 to succeed, it must be that $\widehat{\mu}_{i}\geq\tau$ for
each $i$ such that $\mu_{i}\geq\tau+\varepsilon$ and $\widehat{\mu}_{i}<\tau$
for each $i$ such that $\mu_{i}<\tau-\varepsilon$ (we can make this inequality
strict or non-strict without changing probabilistic statements since
$\widehat{\bm{\mathrm{\mu}}}$ is a continuous random variable). For a given
$i$, this is satisfied if $|\widehat{\mu}_{i}-\mu_{i}|\leq|\mu_{i}-\tau|$. We
show this for the case that $\mu_{i}\geq\tau+\varepsilon$. If
$\widehat{\mu}_{i}\geq\mu_{i}$ in this case, then the necessary condition is
satisfied. If $\widehat{\mu}_{i}<\mu_{i}$, then

$\displaystyle\mu_{i}-\tau=|\mu_{i}-\tau|$
$\displaystyle\geq|\widehat{\mu}_{i}-\mu_{i}|=\mu_{i}-\widehat{\mu}_{i}$ (30)
$\displaystyle\implies\tau$ $\displaystyle\leq\widehat{\mu}_{i}.$ (31)

The case where $\mu_{i}\leq\tau-\varepsilon$ is analogous. Thus, a sufficient
condition for the success of Algorithm 1 is that
$|\widehat{\mu}_{i}-\mu_{i}|\leq|\mu_{i}-\tau|$ for all $i$ such that
$|\mu_{i}-\tau|\geq\varepsilon$. If we use Lemmas A.1, A.2, and A.3, we know
that with probability at least $1-\delta$,

$\displaystyle|\widehat{\mu}_{i}^{t}-\mu_{i}|$
$\displaystyle\leq\sigma_{i}^{t}\left(\frac{R}{\gamma}\sqrt{\log\left(\frac{|\bm{\mathrm{V}}_{t}|}{\delta^{2}|\bm{\mathrm{L}}_{\lambda}|}\right)}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)$
(32)
$\displaystyle\leq\sqrt{\frac{(\sigma_{i}^{0})^{2}}{1+(\sigma_{i}^{0})^{2}n_{i}^{t}/\gamma}}\left(\frac{R}{\gamma}\sqrt{2d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)-2\log\delta}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)$
(33)
$\displaystyle\leq\sqrt{\frac{\gamma}{n_{i}^{t}}}\left(\frac{R}{\gamma}\sqrt{2d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)-2\log\delta}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right).$
(34)

Thus Algorithm 1 succeeds with probability at least $1-\delta$ if, for all $i$
such that $|\mu_{i}-\tau|\geq\varepsilon$,

$\displaystyle\sqrt{\frac{\gamma}{n_{i}^{t}}}\left(\frac{R}{\gamma}\sqrt{2d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)-2\log\delta}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)\leq|\mu_{i}-\tau|.$
(35)

Because Algorithm 1 has an equal sampling allocation for each arm, for $T=kN$
we have that $n_{i}^{t}=k=T/N$. Then since for each $i$ the left-hand side of
(35) is the same, we can write the complete sufficient condition as

$\displaystyle\sqrt{\frac{\gamma
N}{T}}\left(\frac{R}{\gamma}\sqrt{2d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)-2\log\delta}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)\leq\min\left\\{|\mu_{i}-\tau|:|\mu_{i}-\tau|\geq\varepsilon\right\\}.$
(36)

The smallest $\delta$ for which this inequality holds is

$\displaystyle\delta=\exp\Bigg{\\{}$
$\displaystyle-\frac{\gamma^{2}}{2R^{2}}\left(\sqrt{\frac{T}{\gamma\widetilde{H}}}-\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)^{2}+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\Bigg{\\}},$
(37)

provided
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\leq\sqrt{\frac{T}{\gamma\widetilde{H}}}$,
where $\widetilde{H}\triangleq
N/\min{\\{|\mu_{i}-\tau|^{2}:|\mu_{i}-\tau|\geq\varepsilon\\}}$.

##  Appendix C PROOF OF THEOREM 3.1

The proof follows the same general strategy as that of Theorem 2 of Locatelli
et al. (2016).

###  C.1 A Favorable Event

Let

$\displaystyle\delta=\exp\bigg{\\{}$
$\displaystyle-\frac{\gamma^{2}}{2R^{2}}\left(\frac{1}{3M+1}\sqrt{\frac{T}{\gamma
H}}-\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)^{2}+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\bigg{\\}},$
(38)

and consider for the rest of the proof an event of probability at least
$1-\delta$ that gives us the result of Lemma A.1. On this event then, for all
$i\in[N]$,

$\displaystyle|\widehat{\mu}_{i}^{t}-\mu_{i}|$
$\displaystyle\leq\sigma_{i}^{t}\left(\frac{R}{\gamma}\sqrt{\log\left(\frac{|\bm{\mathrm{V}}_{t}|}{\delta^{2}|\bm{\mathrm{L}}_{\lambda}|}\right)}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)$
$\displaystyle\leq\sigma_{i}^{t}\left(\frac{R}{\gamma}\sqrt{2d_{T}\log(1+T/\gamma\lambda)-2\log\delta}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)$
$\displaystyle\leq\frac{\sigma_{i}^{t}}{3M+1}\sqrt{\frac{T}{\gamma H}},$ (39)

where the second inequality comes from Lemma A.3 and the third inequality
comes from plugging in $\delta$ using the fact that
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\leq\frac{1}{3M+1}\sqrt{\frac{T}{\gamma
H}}$.

###  C.2 A Helpful Arm

At time $T$, there must exist an arm $k$ such that
$n_{k}^{T}\geq\frac{T}{H\Delta_{k}^{2}}$. If this were not true, then

$\displaystyle
T=\sum_{i=1}^{N}n_{i}^{T}<\sum_{i=1}^{N}\frac{T}{H\Delta_{i}^{2}}=T,$ (40)

which is a contradiction. Let $t\leq T$ be the last time this arm was pulled,
and consider this time for the rest of the proof. Note that
$n_{k}^{t}=n_{k}^{T}\geq\frac{T}{H\Delta_{k}^{2}}$.

###  C.3 Bounding the Other Arms using the Helpful Arm

When $n_{i}^{t}\geq 1$, using Lemma A.2,

$\displaystyle\sigma_{i}^{t}\sqrt{n_{i}^{t}+\alpha}$
$\displaystyle\leq\sqrt{\frac{(\sigma_{i}^{0})^{2}(n_{i}^{t}+\alpha)}{1+(\sigma_{i}^{0})^{2}n_{i}^{t}/\gamma}}$
$\displaystyle\leq\sqrt{\frac{\gamma(n_{i}^{t}+\alpha)}{n_{i}^{t}}}$
$\displaystyle\leq\sqrt{\gamma(1+\alpha)}.$ (41)

So, including the case of $n_{i}^{t}=0$,

$\displaystyle\sigma_{i}^{t}\sqrt{n_{i}^{t}+\alpha}$
$\displaystyle\leq\max{\left\\{\sigma_{i}^{0}\sqrt{\alpha},\sqrt{\gamma(1+\alpha)}\right\\}}\leq\sqrt{\gamma}M,$
(42)

where the last inequality comes from the fact that ${\sigma_{i}^{0}\leq
1/\sqrt{\lambda}}$.

We know that

$\displaystyle|\widehat{\mu}_{i}^{t}-\mu_{i}|$
$\displaystyle\geq\left||\widehat{\mu}_{i}^{t}-\tau|-|\mu_{i}-\tau|\right|=|\widehat{\Delta}_{i}^{t}-\Delta_{i}|,$
(43)

so we can find a lower bound:

$\displaystyle z_{k}^{t}$
$\displaystyle=\widehat{\Delta}_{k}^{t}\sqrt{n_{k}^{t}+\alpha}$
$\displaystyle\geq\left(\Delta_{k}-\frac{\sigma_{k}^{t}}{3M+1}\sqrt{\frac{T}{\gamma
H}}\right)\sqrt{n_{k}^{t}}$
$\displaystyle\geq\sqrt{\frac{T}{H}}\frac{3M}{3M+1},$ (44)

where the last inequality comes from our bound on $n_{k}^{t}$ and from (C.3)
with $\alpha=0$. For the upper bound,

$\displaystyle z_{i}^{t}$
$\displaystyle=\widehat{\Delta}_{i}^{t}\sqrt{n_{i}^{t}+\alpha}$
$\displaystyle\leq\left(\Delta_{i}+\frac{\sigma_{i}^{t}}{3M+1}\sqrt{\frac{T}{\gamma
H}}\right)\sqrt{n_{i}^{t}+\alpha}$
$\displaystyle\leq\Delta_{i}\sqrt{n_{i}^{t}+\alpha}+\frac{M}{3M+1}\sqrt{\frac{T}{H}}.$
(45)

Since we pulled arm $k$ on round $t$, $z_{k}^{t}\leq z_{i}^{t}$, so

$\displaystyle\sqrt{\frac{T}{H}}\frac{3M}{3M+1}\leq\Delta_{i}\sqrt{n_{i}^{t}+\alpha}+\frac{M}{3M+1}\sqrt{\frac{T}{H}},$
(46)
$\displaystyle\implies\frac{1}{3M+1}\sqrt{\frac{T}{H}}\leq\frac{\Delta_{i}\sqrt{n_{i}^{t}+\alpha}}{2M}.$
(47)

###  C.4 Wrapping Up

Finally, we have that

$\displaystyle|\widehat{\mu}_{i}^{T}-\mu_{i}|$
$\displaystyle\leq\frac{\sigma_{i}^{T}}{3M+1}\sqrt{\frac{T}{\gamma
H}}\leq\frac{\Delta_{i}\sigma_{i}^{t}\sqrt{n_{i}^{t}+\alpha}}{2\sqrt{\gamma}M}\leq\frac{\Delta_{i}}{2},$
(48)

where the second inequality comes from the fact that $\sigma_{i}^{t}$ is
decreasing in $t$ and from (47). Now for $i$ such that
$\mu_{i}\geq\tau+\varepsilon$, we have

$\displaystyle\widehat{\mu}_{i}^{T}$
$\displaystyle\geq\mu_{i}-\frac{\Delta_{i}}{2}=\mu_{i}-\frac{\mu_{i}-\tau+\varepsilon}{2}=\frac{\tau+\mu_{i}-\varepsilon}{2}\geq\tau.$
(49)

For $i$ such that $\mu_{i}\leq\tau-\varepsilon$, we have

$\displaystyle\widehat{\mu}_{i}^{T}$
$\displaystyle\leq\mu_{i}+\frac{\Delta_{i}}{2}=\mu_{i}+\frac{\tau-\mu_{i}+\varepsilon}{2}=\frac{\tau+\mu_{i}+\varepsilon}{2}\leq\tau.$
(50)

##  Appendix D PROOF OF PROPOSITION 3.6

The proof of this proposition is the same as the proof of proposition 2.2
until the choice of the sampling allocation $n_{i}^{t}=\beta_{i}t$. Continuing
from (35), we must choose $\bm{\mathrm{\beta}}$ such that, for all $i$ such
that $|\mu_{i}-\tau|\geq\varepsilon$,

$\displaystyle\sqrt{\frac{\gamma}{T}}\left(\frac{R}{\gamma}\sqrt{2d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)-2\log\delta}+\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)\leq\sqrt{\beta_{i}}|\mu_{i}-\tau|.$
(51)

To optimize this inequality such that it holds for the smallest possible
$\delta$, we must make the right-hand side as large as possible. That is, we
must choose $\bm{\mathrm{\beta}}$ that maximizes

$\displaystyle\min_{i:|\mu_{i}-\tau|\geq\varepsilon}\sqrt{\beta_{i}}|\mu_{i}-\tau|.$
(52)

To maximize this minimum, we must choose $\bm{\mathrm{\beta}}$ that makes all
of the terms the same. With the constraint that $\sum_{i}\beta_{i}=1$, this
means that we must choose

$\displaystyle\beta_{i}=\begin{cases}\left(H_{*}|\mu_{i}-\tau|^{2}\right)^{-1}&\text{if
}|\mu_{i}-\tau|\geq\varepsilon\\\ 0&\text{otherwise},\end{cases}$ (53)

where

$\displaystyle
H_{*}=\sum_{j:|\mu_{j}-\tau|\geq\varepsilon}|\mu_{j}-\tau|^{-2}.$ (54)

With this choice of $\bm{\mathrm{\beta}}$, the smallest $\delta$ for which the
inequality holds is

$\displaystyle\delta=\exp\Bigg{\\{}$
$\displaystyle-\frac{\gamma^{2}}{2R^{2}}\left(\sqrt{\frac{T}{\gamma
H_{*}}}-\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\right)^{2}+d_{T}\log\left(1+\frac{T}{\gamma\lambda}\right)\Bigg{\\}},$
(55)

provided
$\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}\leq\sqrt{\frac{T}{\gamma
H_{*}}}$.

##  Appendix E PROOF OF LEMMAS

###  E.1 Proof of Lemma A.1

To prove Lemma A.1, we first need the following lemma, which is a direct
consequence of Theorem 1 of Abbasi-Yadkori et al. (2011):

######  Lemma E.1.

For any $\delta>0$, with probability at least $1-\delta$, for all $t\geq 0$,

$\|\bm{\mathrm{\xi}}_{t}\|_{V_{t}^{-1}}^{2}\leq
R^{2}\log\left(\frac{|\bm{\mathrm{V}}_{t}|}{\delta^{2}|\bm{\mathrm{L}}_{\lambda}|}\right).$
(56)

Using Lemma E.1, the proof of Lemma A.1 follows that of Lemma 3 of Valko et
al. (2014). Let $\bm{\mathrm{N}}_{t}=\mathrm{diag}(\bm{\mathrm{n}}_{t})$, and
note that
$\bm{\mathrm{x}}_{t}={(\bm{\mathrm{N}}_{t}\bm{\mathrm{\mu}}+\bm{\mathrm{\xi}}_{t})/\gamma}$.
Then

$\displaystyle|\widehat{\mu}_{i}^{t}-\mu_{i}|$
$\displaystyle=\left|\langle\bm{\mathrm{e}}_{i},\bm{\mathrm{V}}_{t}^{-1}(\bm{\mathrm{N}}_{t}\bm{\mathrm{\mu}}+\bm{\mathrm{\xi}}_{t})/\gamma-\bm{\mathrm{\mu}}\rangle\right|$
$\displaystyle=\left|\langle\bm{\mathrm{e}}_{i},\bm{\mathrm{V}}_{t}^{-1}\bm{\mathrm{\xi}}_{t}/\gamma-\bm{\mathrm{V}}_{t}^{-1}\left(\bm{\mathrm{V}}_{t}-\bm{\mathrm{N}}_{t}/\gamma\right)\bm{\mathrm{\mu}}\rangle\right|$
$\displaystyle\leq\left|\langle\bm{\mathrm{e}}_{i},\bm{\mathrm{\xi}}_{t}/\gamma\rangle_{\bm{\mathrm{V}}_{t}^{-1}}\right|+\left|\langle\bm{\mathrm{e}}_{i},\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{\mu}}\rangle_{\bm{\mathrm{V}}_{t}^{-1}}\right|$
$\displaystyle\leq\sigma_{i}^{t}\left(\|\bm{\mathrm{\xi}}_{t}/\gamma\|_{\bm{\mathrm{V}}_{t}^{-1}}+\|\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{\mu}}\|_{\bm{\mathrm{V}}_{t}^{-1}}\right),$
(57)

where the last inequality comes from Cauchy-Schwarz and the fact that
$\sigma_{i}^{t}=\|\bm{\mathrm{e}}_{i}\|_{\bm{\mathrm{V}}_{t}^{-1}}$. The first
term is bounded by Lemma E.1, and the second term is bounded as follows:

$\displaystyle\|\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{\mu}}\|_{\bm{\mathrm{V}}_{t}^{-1}}^{2}$
$\displaystyle=\bm{\mathrm{\mu}}^{\top}\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{V}}_{t}^{-1}\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{\mu}}$
$\displaystyle=\bm{\mathrm{\mu}}^{\top}\left(\bm{\mathrm{L}}_{\lambda}-\bm{\mathrm{N}}_{t}^{1/2}\left(\gamma\bm{\mathrm{I}}+\bm{\mathrm{N}}_{t}^{1/2}\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{N}}_{t}^{1/2}\right)^{-1}\bm{\mathrm{N}}_{t}^{1/2}\right)\bm{\mathrm{\mu}}$
$\displaystyle\leq\bm{\mathrm{\mu}}^{\top}\bm{\mathrm{L}}_{\lambda}\bm{\mathrm{\mu}}=\|\bm{\mathrm{\mu}}\|_{\bm{\mathrm{L}}_{\lambda}}^{2},$
(58)

where the second equality comes from the Woodbury matrix identity, and the
first inequality is from the subtrahend being positive semidefinite.

###  E.2 Proof of Lemma A.2

From the Sherman–Morrison formula, for ${t\geq 1}$,

$\displaystyle(\sigma_{i}^{t})^{2}$
$\displaystyle=\bm{\mathrm{e}}_{i}^{\top}\left(\bm{\mathrm{V}}_{t-1}+\bm{\mathrm{e}}_{\pi_{t}}\bm{\mathrm{e}}_{\pi_{t}}^{\top}/\gamma\right)^{-1}\bm{\mathrm{e}}_{i}$
$\displaystyle=\bm{\mathrm{e}}_{i}^{\top}\left(\bm{\mathrm{V}}_{t-1}^{-1}-\frac{\bm{\mathrm{V}}_{t-1}^{-1}\bm{\mathrm{e}}_{\pi_{t}}\bm{\mathrm{e}}_{\pi_{t}}^{\top}\bm{\mathrm{V}}_{t-1}^{-1}}{\gamma+\bm{\mathrm{e}}_{\pi_{t}}\bm{\mathrm{V}}_{t-1}^{-1}\bm{\mathrm{e}}_{\pi_{t}}}\right)\bm{\mathrm{e}}_{i}$
$\displaystyle=(\sigma_{i}^{t-1})^{2}-\frac{\left(\bm{\mathrm{e}}_{i}^{\top}\bm{\mathrm{V}}_{t-1}^{-1}\bm{\mathrm{e}}_{\pi_{t}}\right)^{2}}{\gamma+(\sigma_{\pi_{t}}^{t-1})^{2}},$
(59)

so $\sigma_{i}^{t}$ is decreasing in $t$. When $\pi_{t}=i$, the update depends
only on the previous value $\sigma_{i}^{t-1}$. Consider the setting where
$\pi_{t}=i\;\forall\;t\geq 1$. Then
$(\sigma_{i}^{t})^{2}={\gamma(\sigma_{i}^{0})^{2}/(\gamma+t(\sigma_{i}^{0})^{2})}$,
which can be shown by induction. It clearly holds for $t=0$. For $t\geq 1$,

$\displaystyle(\sigma_{i}^{t})^{2}$
$\displaystyle=(\sigma_{i}^{t-1})^{2}\left(1-\frac{(\sigma_{i}^{t-1})^{2}}{\gamma+(\sigma_{i}^{t-1})^{2}}\right)$
$\displaystyle=\frac{\gamma(\sigma_{i}^{t-1})^{2}}{\gamma+(\sigma_{i}^{t-1})^{2}}$
$\displaystyle=\frac{\gamma^{2}(\sigma_{i}^{0})^{2}}{(\gamma+(t-1)(\sigma_{i}^{0})^{2})\left(\gamma+\frac{\gamma(\sigma_{i}^{0})^{2}}{\gamma+(t-1)(\sigma_{i}^{0})^{2}}\right)}$
$\displaystyle=\frac{\gamma(\sigma_{i}^{0})^{2}}{\gamma+t(\sigma_{i}^{0})^{2}}.$
(60)

In the setting where we do not have $\pi_{t}=i$ for all $t\geq 1$, since
$\sigma_{i}^{t}$ is decreasing even when $\pi_{t}\neq i$, we can upper bound
$\sigma_{i}^{t}$ with what its value would be if at each time $t$ such that
$\pi_{t}\neq i$ we do not update $\sigma_{i}^{t}$. This would mean that by
time $t$, $\sigma_{i}^{t}$ has been updated $n_{i}^{t}$ times, yielding the
stated bound.

###  E.3 Proof of Lemma A.3

This lemma is derived from Lemma 6 of Valko et al. (2014). If
$\bm{\mathrm{Q}}\bm{\mathrm{\Lambda}}\bm{\mathrm{Q}}^{\top}$ is the
eigendecomposition of $\bm{\mathrm{L}}_{\lambda}$, then let
$\bm{\mathrm{V}}_{T}$ and $\bm{\mathrm{\Lambda}}$ in the notation of Valko et
al. (2014) be equal to
$\gamma\bm{\mathrm{Q}}^{\top}\bm{\mathrm{V}}_{T}\bm{\mathrm{Q}}$ and
$\gamma\bm{\mathrm{\Lambda}}$, respectively, in our notation. The result
follows by the invariance of determinants under unitary transformations.