# Towards Minimax Optimal Best Arm Identification in Linear Bandits

Junwen Yang
Institute of Operations Research and Analytics
National University of Singapore
<EMAIL_ADDRESS>
Vincent Y. F. Tan
Department of Electrical and Computer Engineering
Department of Mathematics
National University of Singapore
<EMAIL_ADDRESS>

###### Abstract

We study the problem of best arm identification in linear bandits in the
fixed-budget setting. By leveraging properties of the G-optimal design and
incorporating it into the arm allocation rule, we design a parameter-free
algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We
provide a theoretical analysis of the failure probability of OD-LinBAI. While
the performances of existing methods (e.g., BayesGap) depend on all the
optimality gaps, OD-LinBAI depends on the gaps of the top $d$ arms, where $d$
is the effective dimension of the linear bandit instance. Furthermore, we
present a minimax lower bound for this problem. The upper and lower bounds
show that OD-LinBAI is minimax optimal up to multiplicative factors in the
exponent. Finally, numerical experiments corroborate our theoretical findings.

##  1 Introduction

The multi-armed bandit problem is a model that exemplifies the exploration-
exploitation tradeoff in online decision making. It has various applications
in drug design, online advertising, recommender systems, and so on. In
stochastic multi-armed bandit problems, the agent sequentially chooses an arm
from the given arm set at each time step and then observes a random reward
drawn from the unknown distribution associated with the chosen arm.

The standard multi-armed bandit problem, where the arms are not correlated
with one another, has been studied extensively in literature. While the
_regret minimization_ problem aims at maximizing the cumulative rewards by the
trade-off between exploration and exploitation [1, 2, 3, 4], the _pure
exploration_ problem focuses on efficient exploration with specific goals,
e.g., to identify the best arm [5, 6, 7, 8, 9, 10]. There are two
complementary settings for the problem of _best arm identification_ : (i)
Given $T\in\mathbb{N}$, the agent aims to maximize the probability of finding
the best arm in at most $T$ time steps; (ii) Given $\delta>0$, the agent aims
to find the best arm with the probability of at least $1-\delta$ in the
smallest number of steps. These settings are respectively known as the fixed-
budget and fixed-confidence settings.

In this paper, we consider the problem of best arm identification in linear
bandits in the fixed-budget setting. In linear bandits, the arms are
correlated through an unknown global regression parameter vector
$\theta^{*}\in\mathbb{R}^{d}$. In particular, each arm $i$ from the arm set
$\mathcal{A}$ is associated with an arm vector $a(i)\in\mathbb{R}^{d}$, and
the expected reward of arm $i$ is given by the inner product between
$\theta^{*}$ and $a(i)$. Hence, the standard multi-armed bandits and linear
bandits are fundamentally different due to the fact that for the latter,
pulling one arm can indirectly reveal information about the other arms but in
the former, the arms are independent.

A wide range of applications in practice can be modeled by linear bandits. For
example, Tao et al. [11] considered online advertising, where the goal is to
select an advertisement from a pool to maximize the probability of clicking
for web users with different features. Empirically, the probability of
clicking can be approximated by a linear combination of various attributes
associated with the user and the advertisements (such as age, gender, the
domain, keywords, advertising genres, etc.). Moreover, Hoffman et al. [12]
applied the linear bandit model into the traffic sensor network problem and
the problem of automatic model selection and algorithm configuration.

#### Main contributions.

Our main contributions are as follows:

  1. (i)

We design an algorithm named Optimal Design-based Linear Best Arm
Identification (OD-LinBAI). This parameter-free algorithm utilizes a phased
elimination-based strategy in which the number of times each arm is pulled in
each phase depends on G-optimal designs [13].

  2. (ii)

We derive an upper bound on the failure probability of OD-LinBAI. In
particular, we show that the exponent depends on a hardness quantity
$H_{2,\mathrm{lin}}$. This quantity is a function of only the first $d-1$
optimality gaps, where $d$ is the dimension of the arm vectors. This is a
significant improvement over the upper bound of the failure probability of
BayesGap in Hoffman et al. [12] which depends on a hardness quantity that
depends on all the gaps. Furthermore, OD-LinBAI is parameter-free, whereas
BayesGap requires the knowledge of the hardness quantity (which is usually not
known).

  3. (iii)

Finally, using ideas from Carpentier and Locatelli [8], we prove a minimax
lower bound which involves another hardness quantity $H_{1,\mathrm{lin}}$. By
comparing $H_{1,\mathrm{lin}}$ to $H_{2,\mathrm{lin}}$, we show that OD-LinBAI
is minimax optimal up to constants in the exponent. Experiments firmly
corroborate the efficacy of OD-LinBAI vis-à-vis BayesGap [12] and its
variants, especially on hard instances.

#### Related work.

The problem of regret minimization in linear bandits was first studied by Abe
and Long [14], and has attracted extensive interest in the development of
various algorithms (e.g., UCB-style algorithms [15, 16, 17, 18, 19], Thompson
sampling [20, 21]). In particular, in the book of Lattimore and Szepesvári
[22], a regret minimization algorithm based on the G-optimal design was
proposed for linear bandits with finitely many arms. Although both this
algorithm and our algorithm OD-LinBAI utilize the G-optimal design technique,
they differ in numerous aspects including the manner of elimination and arm
allocation, which emanates from the two different objectives.

For the problem of best arm identification in linear bandits, the fixed-
confidence setting has previously studied in [11, 23, 24, 25, 26, 27, 28]. In
particular, Soare et al. [23] introduced the optimal G-allocation problem and
proposed a static algorithm $\mathcal{X}\mathcal{Y}$-Oracle as well as a semi-
adaptive algorithm $\mathcal{X}\mathcal{Y}$-Adaptive; see Remark 2 for more
discussions to Soare et al. [23]. Degenne et al. [28] treated the problem as a
two-player zero-sum game between the agent and the nature, and thus designed
an asymptotically optimal algorithm for the fixed-confidence setting.

To the best of our knowledge, Hoffman et al. [12] is the only previous work on
the problem of best arm identification in linear bandits in the fixed-budget
setting. They introduced a gap-based exploration algorithm BayesGap, which is
a Bayesian treatment of UGapEb [9]. However, BayesGap is computationally
expensive and not parameter-free. See Section 4 and Section 5 for more
comparisons.

##  2 Problem setup and preliminaries

#### Best arm identification in linear bandits.

We consider the standard linear bandit problem with an unknown global
regression parameter. In a linear bandit instance $\nu$, the agent is given an
arm set $\mathcal{A}=[K]$, which corresponds to arm vectors
$\\{a(1),a(2),\ldots,a(K)\\}\subset\mathbb{R}^{d}$. At each time $t$, the
agent chooses an arm $A_{t}$ from the arm set $\mathcal{A}$ and then observes
a noisy reward

$X_{t}=\braket{\theta^{*},a(A_{t})}+\eta_{t}$

where $\theta^{*}\in\mathbb{R}^{d}$ is the unknown parameter vector and
$\eta_{t}$ is independent zero-mean $1$-subgaussian random noise.

In the fixed-budget setting, given a time budget $T\in\mathbb{N}$, the agent
aims at maximizing the probability of identifying the best arm, i.e., the arm
with the largest expected reward, with no more than $T$ arm pulls. More
formally, the agent uses an _online_ algorithm $\pi$ to decide the arm
$A_{t}^{\pi}$ to pull at each time step $t$, and the arm
$i_{\mathrm{out}}^{\pi}\in\mathcal{A}$ to output as the identified best arm by
time $T$. We abbreviate $A_{t}^{\pi}$ as $A_{t}$ and $i_{\mathrm{out}}^{\pi}$
as $i_{\mathrm{out}}$ when there is no ambiguity.

For any arm $i\in\mathcal{A}$, let $p(i)=\braket{\theta^{*},a(i)}$ denote the
expected reward. For convenience, we assume that the expected rewards of the
arms are in descending order and the best arm is unique. That is to say,
$p(1)>p(2)\geq\dots\geq p(K)$. For any suboptimal arm $i$, we denote
$\Delta_{i}=p(1)-p(i)$ as the optimality gap. For ease of notation, we also
set $\Delta_{1}=\Delta_{2}$. Furthermore, let $\mathcal{E}$ denote the set of
all the linear bandit instances defined above.

#### Dimensionality-reduced arm vectors.

For any linear bandit instance, if the corresponding arm vectors do not span
$\mathbb{R}^{d}$, i.e.,
$\operatorname{span}\left(\\{a(1),a(2),\dots,a(K)\\}\right)\subsetneq\mathbb{R}^{d}$,
the agent can work with a set of dimensionality-reduced arm vectors
$\\{a^{\prime}(1),a^{\prime}(2),\dots,a^{\prime}(K)\\}\subset\mathbb{R}^{d^{\prime}}$,
that spans $\mathbb{R}^{d^{\prime}}$, with little consequence. Specifically,
let $B\in\mathbb{R}^{d\times d^{\prime}}$ be a matrix whose columns form an
orthonormal basis of the subspace spanned by $a(1),a(2),\dots,a(K)$.111Such an
orthonormal basis can be calculated efficiently with the reduced singular
value decomposition, Gram–Schmidt process, etc. Then the agent can simply set
$a^{\prime}(i)=B^{\top}a(i)$ for each arm $i$.

To verify this, notice that $BB^{\top}$ is a projection matrix onto the
subspace spanned by $\\{a(1),a(2),\dots,a(K)\\}$ and consequently

$\displaystyle p(i)=\braket{\theta^{*},a(i)}$
$\displaystyle=\braket{\theta^{*},BB^{\top}a(i)}=\braket{B^{\top}\theta^{*},B^{\top}a(i)}=\braket{{\theta^{*}}^{\prime},a^{\prime}(i)}.$

Note that $\theta^{*}$ is the unknown parameter vector for original arm
vectors while ${\theta^{*}}^{\prime}=B^{\top}\theta^{*}$ is the corresponding
unknown parameter vector for the dimensionality-reduced arm vectors. In the
problem of linear bandits, what we really care about is not the original
unknown parameter $\theta^{*}$ itself but the inner products between
$\theta^{*}$ and the arm vectors $a(i)$, which establishes the equivalence of
original arm vectors and dimensionality-reduced arm vectors.

In our work, without loss of generality, we assume that the entire set of
original arm vectors $\\{a(1),a(2),\dots,a(K)\\}$ span $\mathbb{R}^{d}$ and
$d\geq 2$.222The situation that $d=1$ is trivial: each arm vector is a scalar
multiple of one another. However, this idea of transforming into
dimensionality-reduced arm vectors is often used in our elimination-based
algorithm. See Section 3 for details.

#### Least squares estimators.

Let $A_{1},A_{2},\dots,A_{n}$ be the sequence of arms pulled by the agent and
$X_{1},X_{2},\dots,X_{n}$ be the corresponding noisy rewards. Suppose that the
corresponding arm vectors $\\{a(A_{1}),a(A_{2}),\dots,a(A_{n})\\}$ span
$\mathbb{R}^{d}$, then the ordinary least squares (OLS) estimator of
$\theta^{*}$ is given by

$\hat{\theta}=V^{-1}\sum_{t=1}^{n}a(A_{t})X_{t}$

where $V=\sum_{t=1}^{n}a(A_{t})a(A_{t})^{\top}\in\mathbb{R}^{d\times d}$ is
invertible. By applying the properties of subgaussian random variables, a
confidence bound for the OLS estimator can be derived as follows.

######  Proposition 1 (Lattimore and Szepesvári [22, Chapter 20]).

If $A_{1},A_{2},\dots,A_{n}$ are deterministically chosen without knowing the
realizations of $X_{1},X_{2},\dots,X_{n}$, then for any $x\in\mathbb{R}^{d}$
and $\delta>0$,

$\Pr\left(\braket{\hat{\theta}-\theta^{*},x}\geq\sqrt{2\|x\|^{2}_{V^{-1}}\log\left(\frac{1}{\delta}\right)}\right)\leq\delta.$

######  Remark 1.

When the arm pulls are not adaptively chosen according to the random rewards,
Proposition 1 no longer applies and an extra factor $\sqrt{d}$ has to be paid
for adaptive arm pulls [18]. Our algorithm avoids this issue by deciding the
arm pulls at the beginning of each phase, and designing the OLS estimator
based on information from current phase. See Section 3 for details.

#### G-optimal design.

The confidence interval in Proposition 1 shows the strong connection between
the arm allocation in linear bandits and experimental design theory [29]. To
control the confidence bounds, we first introduce the G-optimal design
technique into the problem of best arm identification in linear bandits in the
fixed-budget setting. Formally, the G-optimal design problem aims at finding a
probability distribution $\pi:\\{a(i):i\in\mathcal{A}\\}\rightarrow[0,1]$ that
minimises

$g(\pi)=\max_{i\in\mathcal{A}}\|a(i)\|^{2}_{V(\pi)^{-1}}$

where $V(\pi)=\sum_{i\in\mathcal{A}}\pi(a(i))a(i)a(i)^{\top}$. Theorem 1
states the existence of a small-support G-optimal design and the minimum value
of $g$.

######  Theorem 1 (Kiefer and Wolfowitz [13]).

If the arm vectors $\\{a(i):i\in\mathcal{A}\\}$ span $\mathbb{R}^{d}$, the
following statements are equivalent:

  1. (1)

$\pi^{*}$ is a minimiser of $g$.

  2. (2)

$\pi^{*}$ is a maximiser of $f(\pi)=\log\det V(\pi)$.

  3. (3)

$g(\pi^{*})=d$.

Furthermore, there exists a minimiser $\pi^{*}$ of $g$ such that
$|\operatorname{Supp}\left(\pi^{*}\right)|\leq d(d+1)/2$.

######  Remark 2.

It is worth mentioning that the G-optimal design problem for finite arm
vectors is a convex optimization problem while the G-allocation problem in
Soare et al. [23] for the fixed-confidence best arm identification in linear
bandits is an NP-hard discrete optimization problem. A classical algorithm to
solve the G-optimal design problem is the Frank-Wolfe algorithm [30], whose
modified version guarantees linear convergence [31]. For our work, it is
sufficient to compute an $\epsilon$-approximate optimal design333For an
$\epsilon$-approximate optimal design $\pi$, $g(\pi)\leq(1+\epsilon)d$. with
minimal impact on performance. Recently, a near-optimal design with smaller
support was proposed in Lattimore et al. [32], which might be helpful in some
scenarios. See Appendix A for more discussions on the above issues. To reduce
clutter and ease the reading, henceforward in the main text, we assume that a
G-optimal design for finite arm vectors can be found accurately and
efficiently.

##  3 Algorithm

Our algorithm Optimal Design-based Linear Best Arm Identification (OD-LinBAI)
is presented in Algorithm 1.

Algorithm 1 Optimal Design-based Linear Best Arm Identification (OD-LinBAI)

Input: time budget $T$, arm set $\mathcal{A}=[K]$ and arm vectors
$\\{a(1),a(2),\dots,a(K)\\}\subset\mathbb{R}^{d}$.

1:Initialize $t_{0}=1$, $\mathcal{A}_{0}\leftarrow\mathcal{A}$ and $d_{0}=d$.

2:For each arm $i\in\mathcal{A}_{0}$, set $a_{0}(i)=a(i)$.

3:Solve $m$ by Equation (1).

4:for $r=1$ to $\lceil\log_{2}d\rceil$ do

5: Set
$d_{r}=\dim\left(\operatorname{span}\left(\\{a_{r-1}(i):i\in\mathcal{A}_{r-1}\\}\right)\right)$.

6: if $d_{r}=d_{r-1}$ then

7: For each arm $i\in\mathcal{A}_{r}$, set $a_{r}(i)=a_{r-1}(i)$.

8: else

9: Find matrix $B_{r}\in\mathbb{R}^{d_{r-1}\times d_{r}}$ whose columns form a
orthonormal basis of the subspace spanned by
$\\{a_{r-1}(i):i\in\mathcal{A}_{r-1}\\}$.

10: For each arm $i\in\mathcal{A}_{r-1}$, set
$a_{r}(i)=B_{r}^{\top}a_{r-1}(i)$.

11: end if

12: if $r=1$ then

13: Find a G-optimal design
$\pi_{r}:\\{a_{r}(i):i\in\mathcal{A}_{r-1}\\}\rightarrow[0,1]$ with
$|\operatorname{Supp}\left(\pi_{r}\right)|\leq d(d+1)/2$.

14: else

15: Find a G-optimal design
$\pi_{r}:\\{a_{r}(i):i\in\mathcal{A}_{r-1}\\}\rightarrow[0,1]$.

16: end if

17: Set  $T_{r}(i)=\left\lceil\pi_{r}(a_{r}(i))\cdot m\right\rceil\quad\text{
and }\quad T_{r}=\sum_{i\in\mathcal{A}_{r-1}}T_{r}(i).$

18: Choose each arm $i\in\mathcal{A}_{r-1}$ exactly $T_{r}(i)$ times.

19: Calculate the OLS estimator:
$\hat{\theta}_{r}=V_{r}^{-1}\sum_{t=t_{r}}^{t_{r}+T_{r}-1}a_{r}(A_{t})X_{t}\quad\text{
with }\quad V_{r}=\sum_{i\in\mathcal{A}_{r-1}}T_{r}(i)a_{r}(i)a_{r}(i)^{\top}$

20: For each arm $i\in\mathcal{A}_{r-1}$, estimate the expected reward:
$\hat{p}_{r}(i)=\braket{\hat{\theta}_{r},a_{r}(i)}.$

21: Let $\mathcal{A}_{r}$ be the set of $\lceil d/2^{r}\rceil$ arms in
$\mathcal{A}_{r-1}$ with the largest estimates of the expected rewards.

22: Set $t_{r+1}=t_{r}+T_{r}$.

23:end for

Output: the only arm $i_{\mathrm{out}}$ in
$\mathcal{A}_{\lceil\log_{2}d\rceil}$.

The algorithm partitions the whole horizon into $\lceil\log_{2}d\rceil$
phases, and maintains an _active_ arm set $\mathcal{A}_{r}$ in each phase $r$.
The length of each phase is roughly equal to $m$, which will be formally
defined later.

Motivated by the equivalence of the original arm vectors and the
dimensionality-reduced arm vectors, at the beginning of each phase $r$, the
algorithm computes a set of dimensionality-reduced arm vectors
$\\{a_{r}(i):i\in\mathcal{A}_{r-1}\\}\subset\mathbb{R}^{d_{r}}$ which spans
the $d_{r}$-dimensional Euclidean space $\mathbb{R}^{d_{r}}$. This can be
implemented based on the dimensionality-reduced arm vectors of the last phase
$\\{a_{r-1}(i):i\in\mathcal{A}_{r-1}\\}$ in an iterative manner (Lines
$5-11$).

After that, Algorithm 1 finds a G-optimal design $\pi_{r}$ for the current
dimensionality-reduced arm vectors, with a restriction on the cardinality of
the support when $r=1$. OD-LinBAI then pulls each arm in $\mathcal{A}_{r-1}$
according to the proportions specified by the optimal design $\pi_{r}$.
Specifically, the algorithm chooses each arm $i\in\mathcal{A}_{r-1}$ exactly
$T_{r}(i)=\left\lceil\pi_{r}(a_{r}(i))\cdot m\right\rceil$ times, where the
parameter $m$ is fixed among different phases and defined as

$m=\frac{T-\min(K,\frac{d(d+1)}{2})-\sum\limits_{r=1}^{{\lceil\log_{2}d\rceil}-1}{\left\lceil\frac{d}{2^{r}}\right\rceil}}{{\lceil\log_{2}d\rceil}}.$
(1)

Note that $m=\Theta(T/\log_{2}d)$ as $T\rightarrow\infty$ with $K$ fixed.
Lemma 1 in Appendix B shows with such choice of $m$, the total time budget
consumed by the agent is no more than $T$. It turns out that the parameter $m$
plays a significant role in the implementation as well as the theoretical
analysis of Algorithm 1.

Since the support of the G-optimal design $\pi_{r}$ must span
$\mathbb{R}^{d_{r}}$, the OLS estimator can be directly applied (Line $19$).
Then for each arm $i\in\mathcal{A}_{r-1}$, an estimate of the expected reward
is derived. Note that Algorithm 1 decouples the estimates of different phases
and only utilizes the information obtained in the current phase $r$.

At the end of each phase $r$, Algorithm 1 eliminates a subset of possibly
suboptimal arms. In particular, $K-\lceil d/2\rceil$ arms are eliminated in
the first phase and about half of the active arms are eliminated in each of
the following phases. Eventually, there is only single arm $i_{\mathrm{out}}$
in the active set, which is the output of Algorithm 1.

######  Remark 3.

It is worth considering the case of standard multi-armed bandits, which can be
modeled as a special case of linear bandits. In particular, for any arm
$i\in\mathcal{A}=[K]$, the corresponding arm vector is chosen to be $e_{i}$,
which is the $i^{\mathrm{th}}$ standard basis of $\mathbb{R}^{K}$. It follows
that $d=K$, $\theta^{*}=[p(1),p(2),\cdots,p(K)]^{\top}\in\mathbb{R}^{K}$ and
arms are not correlated with one another. A simple mathematical derivation
shows that we can always use a set of standard basis vectors of
$\mathbb{R}^{d_{r}}$ to represent the arm vectors regardless of which arms
remain active during phase $r$. Also, the G-optimal design for a set of
standard basis vectors is the uniform distribution on all of the active arms.
Since pulling one arm is not able to give information about the other arms,
the empirical estimates based on the OLS estimator are exactly the empirical
means. Altogether, for standard multi-armed bandits, OD-LinBAI reduces to the
procedure of Sequential Halving [7], which is a state-of-the-art algorithm for
best arm identification in standard multi-armed bandits.

##  4 Main results

###  4.1 Upper bound

We first state an upper bound on the error probability of OD-LinBAI (Algorithm
1). The proof of Theorem 2 is deferred to Appendix B.

######  Theorem 2.

For any linear bandit instance $\nu\in\mathcal{E}$, OD-LinBAI outputs an arm
$i_{\mathrm{out}}$ satisfying

$\Pr\left[i_{\mathrm{out}}\neq
1\right]\leq\left(\frac{4K}{d}+3\log_{2}d\right)\exp\left(-\frac{m}{32H_{2,\mathrm{lin}}}\right)$

where $m$ is defined in Equation (1) and

$H_{2,\mathrm{lin}}=\max_{2\leq i\leq d}\frac{i}{\Delta_{i}^{2}}.$

Theorem 2 shows the error probability of OD-LinBAI is upper bounded by

$\exp\left(-\Omega\left(\frac{T}{H_{2,\mathrm{lin}}\log_{2}d}\right)\right)$
(2)

which depends on $T$, $d$ and $H_{2,\mathrm{lin}}$. We remark that none of the
three terms is avoidable in view of our lower bounds (see Section 4.2).

In particular, $T$ is the time budget of the problem and $d$ is the effective
dimension of the arm vectors.444Recall that we assume the entire set of
original arm vectors $\\{a(1),a(2),\dots,a(K)\\}$ span $\mathbb{R}^{d}$. Given
$T$ and $d$, $H_{2,\mathrm{lin}}$ quantifies the difficulty of identifying the
best arm in the linear bandit instance. The parameter $H_{2,\mathrm{lin}}$
generalizes its analogue

$H_{2}=\max_{2\leq i\leq K}\frac{i}{\Delta_{i}^{2}}$

proposed by Audibert et al. [33] for standard multi-armed bandits. However,
$H_{2,\mathrm{lin}}$ is not larger than $H_{2}$ since $H_{2,\mathrm{lin}}$ is
only a function of the first $d-1$ optimality gaps while $H_{2}$ considers all
of the $K-1$ optimality gaps. In the extreme case that all of the suboptimal
arms have the same optimality gaps, i.e.,
$\Delta_{2}=\Delta_{3}=\cdots=\Delta_{K}$, the two terms $H_{2}$ and
$H_{2,\mathrm{lin}}$ can differ significantly. In general, we have

$H_{2,\mathrm{lin}}\leq H_{2}\leq\frac{K}{d}H_{2,\mathrm{lin}}$

and both inequalities are essentially sharp, i.e., can be achieved by some
linear bandit instances. This highlights a major difference between best arm
identification in the fixed-budget setting for linear bandits and standard
multi-armed bandits. Due to the linear structure, arms are correlated and we
can estimate the mean reward of one arm with the help of the other arms. Thus,
the hardness quantity $H_{2,\mathrm{lin}}$ is only a function of the top $d$
arms and not all the arms.

#### Comparisons with BayesGap [12].

To the best of our knowledge, the only previous algorithm in the same setting
of best arm identification in linear bandits with a fixed budget with our work
is BayesGap, which is adapted from UGapEb [9] for standard multi-armed
bandits. We compare BayesGap and OD-LinBAI with respect to the algorithm
design as well as the theoretical guarantees in the following.

  1. (i)

The model of BayesGap is Bayesian linear bandits, in which the unknown
parameter vector $\theta^{*}$ is drawn from a known prior distribution
$\mathcal{N}(0,\eta^{2}I)$ and the additive noise is required to be strictly
Gaussian. However, OD-LinBAI does not require these assumptions and the upper
bound holds for any $\theta^{*}\in\mathbb{R}^{d}$.

  2. (ii)

The algorithm and theoretical guarantee of BayesGap explicitly require the
knowledge of a hardness quantity

$H_{1}=\sum_{1\leq i\leq K}\Delta_{i}^{-2}$

to control the confidence region and then allocate exploration. However, this
hardness quantity $H_{1}$ is almost always unknown to the agent in practice.
In most practical applications, BayesGap has to estimate $H_{1}$ in an
adaptive way, which works reasonably well in numerical experiments but lacks
guarantees. On the contrary, OD-LinBAI is fully parameter-free.

  3. (iii)

The error probability of BayesGap is upper bounded by

$\exp\left(-\Omega\left(\frac{T}{H_{1}}\right)\right)$ (3)

which depends on $T$ and $H_{1}$.

Compared with (3), the upper bound of OD-LinBAI in (2) has an extra
$\log_{2}d$ term. This is an interesting phenomena which also occurs in
standard multi-armed bandits [33, 8]. For best arm identification in standard
multi-armed bandits, without the knowledge of the hardness quantity $H_{1}$,
the agent has to pay a price of $\log_{2}K$ for the adaptation to the problem
complexity. In Theorem 3, we prove a similar result for linear bandits, in
which the price for the adaptation is $\log_{2}d$.

The upper bound (3) involves $H_{1}$, which is a function of _all_ the
optimality gaps. It holds that $H_{1}\geq H_{2}\geq H_{2,\mathrm{lin}}$. Thus,
the upper bound of OD-LinBAI is better with regard to the problem complexity
parameter. BayesGap, at least in the theoretical analysis, does not fully
utilize the linear structure of the bandit problem. See Section 4.2 for a more
detailed comparison on different hardness quantities.

###  4.2 Lower bound

Before stating the lower bound formally, we introduce a generalization of
$H_{1}$ that characterizes the difficulty of a linear bandit instance:

$H_{1,\mathrm{lin}}=\sum_{1\leq i\leq d}\Delta_{i}^{-2}.$

This parameter is also associated with the top $d$ arms similarly to
$H_{2,\mathrm{lin}}$. See Table 1 for a thorough comparison on different
hardness quantities.

Table 1: Comparisons of different hardness quantities: $H_{1}$, $H_{2}$, $H_{1,\mathrm{lin}}$ and $H_{2,\mathrm{lin}}$ $H_{1}=\sum_{1\leq i\leq K}\Delta_{i}^{-2}$ | $H_{2}=\max_{2\leq i\leq K}{i}\cdot{\Delta_{i}^{-2}}$ |  $1\leq H_{1}/H_{2}\leq\log(2K)$ [33]
---|---|---
$H_{1,\mathrm{lin}}=\sum_{1\leq i\leq d}\Delta_{i}^{-2}$ | $H_{2,\mathrm{lin}}=\max_{2\leq i\leq d}{i}\cdot{\Delta_{i}^{-2}}$ | $1\leq H_{1,\mathrm{lin}}/H_{2,\mathrm{lin}}\leq\log(2d)$
$1\leq H_{1}/H_{1,\mathrm{lin}}\leq K/d$ | $1\leq H_{2}/H_{2,\mathrm{lin}}\leq K/d$ |

For any linear bandit instance $\nu\in\mathcal{E}$, we denote the hardness
quantity $H_{1,\mathrm{lin}}$ of $\nu$ as $H_{1,\mathrm{lin}}(\nu)$.555When
there is no ambiguity, $H_{1,\mathrm{lin}}$ will also be used. In addition,
let $\mathcal{E}(a)$ denote the set of linear bandit instances in
$\mathcal{E}$ whose $H_{1,\mathrm{lin}}$ is bounded by $a$ ($a>0$), i.e.,
$\mathcal{E}(a)=\\{\nu\in\mathcal{E}:H_{1,\mathrm{lin}}(\nu)\leq a\\}$.

Here we give a minimax lower bound for the problem of best arm identification
in linear bandits in the fixed-budget setting. The proof of Theorem 3 is
deferred to Appendix C, which is built on the connection between linear
bandits and standard multi-armed bandits and then utilizes the minimax lower
bound for standard multi-armed bandits [8].

######  Theorem 3.

If $T\geq a^{2}\log(6Td)/900$, then

$\min_{\pi}\max_{\nu\in\mathcal{E}(a)}\Pr\left[i_{\mathrm{out}}^{\pi}\neq
1\right]\geq\frac{1}{6}\exp\left(-\frac{240T}{a}\right).$

Further if $a\geq 15d^{2}$, then

$\min_{\pi}\max_{\nu\in\mathcal{E}(a)}\left(\Pr\left[i_{\mathrm{out}}^{\pi}\neq
1\right]\cdot\exp\left(\frac{2700T}{H_{1,\mathrm{lin}}(\nu)\log_{2}d}\right)\right)\geq\frac{1}{6}.$

Theorem 3 first shows that for any best arm identification algorithm $\pi$,
even with the knowledge of an upper bound $a$ on the hardness quantity
$H_{1,\mathrm{lin}}$, there exists a linear bandit instance such that the
error probability is at least

$\exp\left(-O\left(\frac{T}{a}\right)\right).$ (4)

Furthermore, for any best arm identification algorithm $\pi$, without the
knowledge of an upper bound $a$ on the hardness quantity $H_{1,\mathrm{lin}}$,
there exists a linear bandit instance $\nu$ such that the error probability is
at least

$\exp\left(-O\left(\frac{T}{H_{1,\mathrm{lin}}(\nu)\log_{2}d}\right)\right).$
(5)

Comparing the lower bounds (4) and (5) in two different settings, we show that
the agent has to pay a price of $\log_{2}d$ in the absence of the knowledge
about the problem complexity. Finding a best arm identification algorithm that
matching the lower bound (4) remains an open problem since the upper bound of
BayesGap (3) involves $H_{1}$ but not $H_{1,\mathrm{lin}}$. However, notice
that the knowledge about the complexity quantity which is required for
BayesGap is usually unavailable in real-life applications.

Now we compare the upper bound on the error probability of OD-LinBAI in (2)
with the lower bound (5). Table 1 shows that $H_{1,\mathrm{lin}}\geq
H_{2,\mathrm{lin}}$ always holds. Therefore, the upper bound (2) is not larger
than the lower bound (5) order-wise in the exponent. However, the upper bound
holds for all instances, while the lower bound is a minimax result which holds
for specific instances. This shows OD-LinBAI (Algorithm 1) is _minimax
optimal_ up to multiplicative factors in the exponent. At the same time, since
an upper bound can never be smaller than a lower bound, we know that the hard
instances for the problem of best arm identification in linear bandits in the
fixed-budget setting are those whose $H_{1,\mathrm{lin}}$ and
$H_{2,\mathrm{lin}}$ are of the same order.

##  5 Numerical experiments

In this section, we evaluate the performance of our algorithm OD-LinBAI and
compare it with Sequential Halving and BayesGap. We present the results of two
synthetic datesets here and the results of a real-world dataset, the Abalone
dataset [34], in Appendix D.3 in the supplementary. Sequential Halving [7] is
a state-of-the-art algorithm for best arm identification in standard multi-
armed bandits. For BayesGap [12], there are two versions: one is BayesGap-
Oracle, which is given the exact information of the required hardness quantity
$H_{1}$; the other is BayesGap-Adaptive, which adaptively estimates the
hardness quantity by the three-sigma rule. Throughout in the synthetic
datesets we assume that the additive random noise follows the standard
Gaussian distribution $\mathcal{N}(0,1)$. In each setting, the reported error
probabilities of different algorithms are averaged over $1024$ independent
trials. Additional implementation details and numerical results are provided
in Appendix D.

###  5.1 Synthetic dataset 1: a hard instance

This dataset, where there are numerous competitors for the second best arm,
was considered for the problem of best arm identification in linear bandits in
the fixed-confidence setting [25, 26]. Similarly, we consider the situation
that $d=2$ and $K\geq 3$. For simplicity, we set the unknown parameter vector
$\theta^{*}=[1,0]^{\top}$. There is one best arm and one worst arm, which
correspond to the arm vectors $a(1)=[1,0]^{\top}$ and
$a(K)=[\cos({3\pi/4}),\sin({3\pi/4})]^{\top}$ respectively. For any arm
$i\in\\{2,3,\dots,K-1\\}$, the corresponding arm vector is chosen to be
$a(i)=[\cos({\pi/4+\phi_{i}}),\sin({\pi/4}+\phi_{i})]^{\top}$ with $\phi_{i}$
drawn independently from $\mathcal{N}(0,0.09)$ independently. Therefore, there
are $K-2$ almost second best arms. Considering the definitions of four
hardness quantities, it holds that

$H_{1}\approx
H_{2}\approx\frac{K}{d}H_{1,\mathrm{lin}}\approx\frac{K}{d}H_{2,\mathrm{lin}}.$

Hence this is a hard instance in the sense that the linear structure is
extremely strong. A good algorithm needs to fully utilize the correlations of
the arms induced by the linear structure to pull arms as efficiently as
possible.

Figure 1: Error probabilities for different numbers of arms $K$ with
$T=25,50,100$ from left to right.

Figure 2: Error probabilities for different time budgets $T$ with
$K=25,50,100$ from left to right.

The experimental results with fixed $T$ and $K$ are presented in Figure 1 and
Figure 2 respectively. In terms of this hard linear bandit instance, OD-LinBAI
is clearly superior compared to its competitors. In fact, OD-LinBAI
consistently pulls only one arm from the $K-2$ almost second best arms and
thus suffers minimal impact from the increase in $K$.

###  5.2 Synthetic dataset 2: ramdom arm vectors

In this experiment, the $K$ arm vectors are uniformly sampled from the unit
$d$-dimensional sphere $\mathbb{S}^{d-1}$. Without loss of generality, we
assume that $a(1),a(2)$ are the two closest arm vectors and then set
$\theta^{*}=a(1)+0.01(a(1)-a(2))$. Thus the best arm is arm $1$ while the
second best arm is arm $2$. Differently from previous works [11, 25, 26, 28],
we set the number of arms to be $K=c^{d}$ with a integer constant $c$.
According to Theorem $8$ in Cai et al. [35], the minimum optimality gap
$\Delta_{1}$ will converge in probability to a positive number as $d$ tends to
infinity so that the random linear bandit instances which we perform our
experiments on are neither too hard nor too easy.

Figure 3: Error probabilities for different $d$ with $c=2$ on the left and
$c=3$ on the right.

Figure 3 shows the error probabilities of the $4$ different algorithms for
this dataset with $c=2$ or $3$ when the time budget $T=2K$. In most
situations, OD-LinBAI outperforms the other algorithms. Moreover, Table 4 and
Table 5 in the supplementary show that OD-LinBAI is computationally efficient
compared to BayesGap, which involves matrix inverse updates to calculate the
confidence widths at each time step. See Appendix D.2 for additional results
and discussion on this dataset.

##  6 Conclusion

In this paper, we introduce the G-optimal design technique into the problem of
best arm identification in linear bandits in the fixed-budget setting. We
design a parameter-free algorithm OD-LinBAI. To characterize the difficulty of
a linear bandit instance, we introduce two hardness quantities
$H_{1,\mathrm{lin}}$ and $H_{2,\mathrm{lin}}$. The upper bound of the error
probability of OD-LinBAI and the minimax lower bound of this problem are
respectively characterized by $H_{1,\mathrm{lin}}$ and $H_{2,\mathrm{lin}}$
instead of their analogues $H_{1}$ and $H_{2}$ in standard multi-armed
bandits. Moreover, OD-LinBAI is minimax optimal up to multiplicative factors
in the exponent, which is also supported by the considerable improvement of
the performance in the numerical experiments over existing algorithms.

An potential direction for future work is to design an instance-dependent
asymptotically optimal algorithm for this problem. However, finding a such
algorithm or even an instance-dependent lower bound for the problem of best
arm identification in standard multi-armed bandits in the fixed-budget setting
remains open.

## References

  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2):235–256, 2002.
  * Bubeck and Cesa-Bianchi [2012] Sébastien Bubeck and Nicolo Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _arXiv preprint arXiv:1204.5721_ , 2012.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Agrawal and Goyal [2012] Shipra Agrawal and Navin Goyal.  Analysis of thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , pages 39–1. JMLR Workshop and Conference Proceedings, 2012.
  * Even-Dar et al. [2006] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan.  Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.  _Journal of machine learning research_ , 7(6), 2006.
  * Bubeck et al. [2009] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.  Pure exploration in multi-armed bandits problems.  In _International conference on Algorithmic learning theory_ , pages 23–37. Springer, 2009.
  * Karnin et al. [2013] Zohar Karnin, Tomer Koren, and Oren Somekh.  Almost optimal exploration in multi-armed bandits.  In _International Conference on Machine Learning_ , pages 1238–1246. PMLR, 2013.
  * Carpentier and Locatelli [2016] Alexandra Carpentier and Andrea Locatelli.  Tight (lower) bounds for the fixed budget best arm identification bandit problem.  In _Conference on Learning Theory_ , pages 590–604. PMLR, 2016.
  * Gabillon et al. [2012] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric.  Best arm identification: A unified approach to fixed budget and fixed confidence.  In _NIPS-Twenty-Sixth Annual Conference on Neural Information Processing Systems_ , 2012.
  * Garivier and Kaufmann [2016] Aurélien Garivier and Emilie Kaufmann.  Optimal best arm identification with fixed confidence.  In _Conference on Learning Theory_ , pages 998–1027. PMLR, 2016.
  * Tao et al. [2018] Chao Tao, Saúl Blanco, and Yuan Zhou.  Best arm identification in linear bandits with linear dimension dependency.  In _International Conference on Machine Learning_ , pages 4877–4886. PMLR, 2018.
  * Hoffman et al. [2014] Matthew Hoffman, Bobak Shahriari, and Nando Freitas.  On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning.  In _Artificial Intelligence and Statistics_ , pages 365–374. PMLR, 2014.
  * Kiefer and Wolfowitz [1960] Jack Kiefer and Jacob Wolfowitz.  The equivalence of two extremum problems.  _Canadian Journal of Mathematics_ , 12:363–366, 1960.
  * Abe and Long [1999] Naoki Abe and Philip M Long.  Associative reinforcement learning using linear probabilistic concepts.  In _ICML_ , pages 3–11. Citeseer, 1999.
  * Auer [2002] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Dani et al. [2008] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade.  Stochastic linear optimization under bandit feedback.  In Rocco A. Servedio and Tong Zhang, editors, _21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008_ , pages 355–366. Omnipress, 2008.  URL http://colt2008.cs.helsinki.fi/papers/80-Dani.pdf.
  * Rusmevichientong and Tsitsiklis [2010] Paat Rusmevichientong and John N Tsitsiklis.  Linearly parameterized bandits.  _Mathematics of Operations Research_ , 35(2):395–411, 2010.
  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _NIPS_ , volume 11, pages 2312–2320, 2011.
  * Chu et al. [2011] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In _Artificial Intelligence and Statistics_ , pages 208–214. PMLR, 2011.
  * Agrawal and Goyal [2013] Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In _International Conference on Machine Learning_ , pages 127–135. PMLR, 2013.
  * Abeille and Lazaric [2017] Marc Abeille and Alessandro Lazaric.  Linear thompson sampling revisited.  In _Artificial Intelligence and Statistics_ , pages 176–184. PMLR, 2017.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Soare et al. [2014] Marta Soare, Alessandro Lazaric, and Rémi Munos.  Best-arm identification in linear bandits.  In _NIPS-Advances in Neural Information Processing Systems 27_ , 2014\.
  * Xu et al. [2018] Liyuan Xu, Junya Honda, and Masashi Sugiyama.  A fully adaptive algorithm for pure exploration in linear bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 843–851. PMLR, 2018.
  * Zaki et al. [2019] Mohammadi Zaki, Avinash Mohan, and Aditya Gopalan.  Towards optimal and efficient best arm identification in linear bandits.  _arXiv preprint arXiv:1911.01695_ , 2019.
  * Fiez et al. [2019] Tanner Fiez, Lalit Jain, Kevin G. Jamieson, and L. Ratliff.  Sequential experimental design for transductive linear bandits.  In _NeurIPS_ , 2019.
  * Kazerouni and Wein [2021] Abbas Kazerouni and Lawrence M Wein.  Best arm identification in generalized linear bandits.  _Operations Research Letters_ , 49(3):365–371, 2021.
  * Degenne et al. [2020] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko.  Gamification of pure exploration for linear bandits.  In _International Conference on Machine Learning_ , pages 2432–2442. PMLR, 2020.
  * Pukelsheim [2006] Friedrich Pukelsheim.  _Optimal design of experiments_.  SIAM, 2006.
  * Frank et al. [1956] Marguerite Frank, Philip Wolfe, et al.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2):95–110, 1956.
  * Damla Ahipasaoglu et al. [2008] S Damla Ahipasaoglu, Peng Sun, and Michael J. Todd.  Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids.  _Optimisation Methods and Software_ , 23(1):5–19, 2008.
  * Lattimore et al. [2020] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz.  Learning with good feature representations in bandits and in RL with a generative model.  In _International Conference on Machine Learning_ , pages 5662–5670. PMLR, 2020.
  * Audibert et al. [2010] Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos.  Best arm identification in multi-armed bandits.  In _COLT_ , pages 41–53, 2010.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Cai et al. [2013] Tony Cai, Jianqing Fan, and Tiefeng Jiang.  Distributions of angles in random packing on spheres.  _Journal of Machine Learning Research_ , 14:1837, 2013.
  * Todd [2016] Michael J. Todd.  _Minimum-volume ellipsoids: Theory and algorithms_.  SIAM, 2016.

##  Appendix A More discussions on the G-optimal design

####  $\epsilon$-approximate G-optimal design.

For the problem of best arm identification in linear bandits in the fixed-
budget setting, it is sufficient to compute an $\epsilon$-approximate
G-optimal design with minimal impact on performance. For an
$\epsilon$-approximate optimal design $\pi$, $g(\pi)\leq(1+\epsilon)d$. Todd
[36] shows that such a design can be computed within $4d(\log\log
d+7/2)+28d/\epsilon$ iterations by the Frank-Wolfe algorithm with a specific
initialization. If we only compute $\epsilon$-approximate G-optimal designs in
OD-LinBAI (Algorithm 1), the upper bound on the error probability will only
deteriorate by a factor of $(1+\epsilon)$ as follows.

######  Theorem 4.

For any linear bandit instance $\nu\in\mathcal{E}$, OD-LinBAI, using
$\epsilon$-approximate G-optimal designs, outputs an arm $i_{\mathrm{out}}$
satisfying

$\Pr\left[i_{\mathrm{out}}\neq
1\right]\leq\left(\frac{4K}{d}+3\log_{2}d\right)\exp\left(-\frac{m}{32(1+\epsilon)H_{2,\mathrm{lin}}}\right)$

where $m$ is defined in Equation (1).

#### Near-optimal design with smaller support.

Recently, a near-optimal design with smaller support was proposed in Lattimore
et al. [32]. In detail, there exists a design
$\pi:\\{a(i):i\in\mathcal{A}\\}\rightarrow[0,1]$ such that $g(\pi)\leq 2d$ and
$|\operatorname{Supp}(\pi)|\leq 4d(\log\log d+11)$. Todd [36] shows that such
a design can be computed within $4d(\log\log d+21/2)$ iterations by the Frank-
Wolfe algorithm with a specific initialization. Since the support of the
design is smaller when $d$ is large, we can choose a larger $m$ in OD-LinBAI
while the total budget consumed by the agent is still bounded by $T$. In
particular, we can choose the parameter $m$ as

$m=\frac{T-\min(K,4d(\log\log
d+11))-\sum\limits_{r=1}^{{\lceil\log_{2}d\rceil}-1}{\left\lceil\frac{d}{2^{r}}\right\rceil}}{{\lceil\log_{2}d\rceil}}.$
(6)

The error probability can be bounded as follows.

######  Theorem 5.

For any linear bandit instance $\nu\in\mathcal{E}$, OD-LinBAI, using near-
optimal designs with smaller support, outputs an arm $i_{\mathrm{out}}$
satisfying

$\Pr\left[i_{\mathrm{out}}\neq
1\right]\leq\left(\frac{4K}{d}+3\log_{2}d\right)\exp\left(-\frac{m}{64H_{2,\mathrm{lin}}}\right)$

where $m$ is defined in Equation (6).

##  Appendix B Proof of Theorem 2

Before going to the proof of Theorem 2, we first introduce some useful lemmas.
Lemma 1 shows Algorithm 1 is feasible in the sense that the total budget
consumed by the agent is no more than $T$, and $i_{\mathrm{out}}$ is well-
defined.

######  Lemma 1.

With parameter $m$ defined as Equation (1), Algorithm 1 terminates in phase
$\lceil\log_{2}d\rceil$ with no more than a total of $T$ arm pulls.

###### Proof.

When $d=2$, Algorithm 1 terminates in one phase. When $d>2$, by the property
of ceiling function, we have
$\frac{1}{2}<\frac{d}{2^{\lceil\log_{2}d\rceil}}\leq 1$. Thus, the number of
arms in $\mathcal{A}_{\lceil\log_{2}d\rceil-1}$ is
${\left\lceil\frac{d}{2^{\lceil\log_{2}d\rceil-1}}\right\rceil}=2$, while the
number of arms in $\mathcal{A}_{\lceil\log_{2}d\rceil}$ is
${\left\lceil\frac{d}{2^{\lceil\log_{2}d\rceil}}\right\rceil}=1$. As a result,
Algorithm 1 always terminates in phase $\lceil\log_{2}d\rceil$.

Now we bound the number of arm pulls. For any phase $r$,
$|\operatorname{Supp}\left(\pi_{r}\right)|$ is always bounded by the
cardinality of the active set $\mathcal{A}_{r-1}$. In particular, for the
first phase, according to Theorem 1, there exists a G-optimal design $\pi_{r}$
with $|\operatorname{Supp}\left(\pi_{r}\right)|\leq d(d+1)/2$. Altogether, we
have

$|\operatorname{Supp}\left(\pi_{r}\right)|\leq\begin{cases}\min(K,\frac{d(d+1)}{2})&\text{when
}r=1\\\ {\left\lceil\frac{d}{2^{r-1}}\right\rceil}&\text{when
}r>1.\end{cases}$

Then the number of total arm pulls is bounded as

$\displaystyle\sum_{r=1}^{\lceil\log_{2}d\rceil}T_{r}$
$\displaystyle=\sum_{r=1}^{\lceil\log_{2}d\rceil}\sum_{i\in\mathcal{A}_{r}}T_{r}(i)$
$\displaystyle=\sum_{r=1}^{\lceil\log_{2}d\rceil}\sum_{i\in\mathcal{A}_{r}}\left\lceil\pi_{r}(a_{r}(i))\cdot
m\right\rceil$
$\displaystyle\leq\sum_{r=1}^{\lceil\log_{2}d\rceil}\left(|\operatorname{Supp}\left(\pi_{r}\right)|+\sum_{i\in\mathcal{A}_{r}}\pi_{r}(a_{r}(i))\cdot
m\right)$ (7)
$\displaystyle\leq\min\left(K,\frac{d(d+1)}{2}\right)+\sum\limits_{r=2}^{{\lceil\log_{2}d\rceil}}{\left\lceil\frac{d}{2^{r-1}}\right\rceil}+\lceil\log_{2}d\rceil\cdot
m$ $\displaystyle=T$ (8)

where line (7) follows from the property of ceiling function and line (8)
follows from the definition of $m$. ∎

Lemma 2 bounds the probability that a certain arm has its estimate of the
expected reward larger than that of the best arm in single phase $r$.

######  Lemma 2.

Assume that the best arm is not eliminated prior to phase $r$, i.e.,
$1\in\mathcal{A}_{r-1}$. Then for any arm $i\in\mathcal{A}_{r-1}$,

$\Pr\left[\hat{p}_{r}(1)<\hat{p}_{r}(i)\mid
1\in\mathcal{A}_{r-1},i\in\mathcal{A}_{r-1}\right]\leq\exp\left(-\frac{m\Delta_{i}^{2}}{8{\left\lceil\frac{d}{2^{r-1}}\right\rceil}}\right).$

###### Proof.

Let $\theta_{r}^{*}$ denote the corresponding unknown parameter vector for the
dimensionality-reduced arm vectors $\\{a_{r}(i):i\in\mathcal{A}_{r-1}\\}$.
Also we set

$V_{r}(\pi_{r})=\sum_{i\in\mathcal{A}_{r-1}}\pi_{r}(a_{r}(i))a_{r}(i)a_{r}(i)^{\top}.$

Then we have

$\displaystyle\phantom{\;=\;}\Pr\left[\hat{p}_{r}(1)<\hat{p}_{r}(i)\mid
1\in\mathcal{A}_{r-1},i\in\mathcal{A}_{r-1}\right]$
$\displaystyle=\Pr\left[\braket{\hat{\theta}_{r}-\theta^{*}_{r},a_{r}(1)-a_{r}(i)}<-\Delta_{i}\mid
1\in\mathcal{A}_{r-1},i\in\mathcal{A}_{r-1}\right]$ (9)
$\displaystyle\leq\exp\left(-\frac{\Delta_{i}^{2}}{2\|a_{r}(1)-a_{r}(i)\|_{V_{r}^{-1}}^{2}}\right)$
(10)
$\displaystyle\leq\exp\left(-\frac{\Delta_{i}^{2}}{8\max_{i\in\mathcal{A}_{r}}\|a_{r}(i)\|_{V_{r}^{-1}}^{2}}\right)$
(11) $\displaystyle\leq\exp\left(-\frac{\Delta_{i}^{2}\cdot
m}{8\max_{i\in\mathcal{A}_{r}}\|a_{r}(i)\|_{V_{r}(\pi_{r})^{-1}}^{2}}\right)$
(12) $\displaystyle=\exp\left(-\frac{m\Delta_{i}^{2}}{8d_{r}}\right)$ (13)
$\displaystyle\leq\exp\left(-\frac{m\Delta_{i}^{2}}{8{\left\lceil\frac{d}{2^{r-1}}\right\rceil}}\right).$
(14)

Line (9) follows from

$\begin{cases}\hat{p}_{r}(1)=\braket{\hat{\theta}_{r},a_{r}(1)}\\\
\hat{p}_{r}(i)=\braket{\hat{\theta}_{r},a_{r}(i)}\\\
\Delta_{i}=\braket{\theta^{*}_{r},a_{r}(1)-a_{r}(i)}=\braket{\theta^{*},a(1)-a(i)}.\end{cases}$

Line (10) follows from Proposition 1, the confidence bound for the OLS
estimator.

Line (11) follows from the triangle inequality for $\|\cdot\|_{V_{r}^{-1}}$
norm.

Line (12) follows from

$\displaystyle\|a_{r}(i)\|_{V_{r}^{-1}}^{2}$
$\displaystyle=a_{r}(i)^{\top}V_{r}^{-1}a_{r}(i)$
$\displaystyle=a_{r}(i)^{\top}\left(\sum_{i\in\mathcal{A}_{r-1}}T_{r}(i)a_{r}(i)a_{r}(i)^{\top}\right)^{-1}a_{r}(i)$
$\displaystyle\leq
a_{r}(i)^{\top}\left(\sum_{i\in\mathcal{A}_{r-1}}m\pi_{r}(a_{r}(i))a_{r}(i)a_{r}(i)^{\top}\right)^{-1}a_{r}(i)$
$\displaystyle=\frac{1}{m}a_{r}(i)^{\top}\left(\sum_{i\in\mathcal{A}_{r-1}}\pi_{r}(a_{r}(i))a_{r}(i)a_{r}(i)^{\top}\right)^{-1}a_{r}(i)$
$\displaystyle=\frac{1}{m}a_{r}(i)^{\top}V_{r}(\pi_{r})^{-1}a_{r}(i)$
$\displaystyle=\frac{1}{m}{\|a_{r}(i)\|_{V_{r}(\pi_{r})^{-1}}^{2}}.$

Line (13) follows from Theorem 1, the property of G-optimal design.

Line (14) follows from the fact that the dimension of the space spanned by the
corresponding arm vectors of the active arm set $\mathcal{A}_{r-1}$ is not
larger than the cardinality of $\mathcal{A}_{r-1}$. ∎

Armed with Lemma 2, then we bound the error probability of single phase $r$ in
Lemma 3.

######  Lemma 3.

Assume that the best arm is not eliminated prior to phase $r$, i.e.,
$1\in\mathcal{A}_{r-1}$. Then the probability that the best arm is eliminated
in phase $r$ is at most

$\begin{cases}\frac{4K}{d}\exp\left(-\frac{m\Delta_{i_{r}}^{2}}{32i_{r}}\right)&\text{when
}r=1\\\ 3\exp\left(-\frac{m\Delta_{i_{r}}^{2}}{32i_{r}}\right)&\text{when
}r>1\end{cases}$

where $i_{r}={\left\lceil\frac{d}{2^{r+1}}\right\rceil+1}$.

###### Proof.

Define $\mathcal{B}_{r}$ as the set of arms in $\mathcal{A}_{r-1}$ excluding
the best arm and ${\left\lceil\frac{d}{2^{r+1}}\right\rceil}-1$ suboptimal
arms with the largest expected rewards. Therefore, we have
$|\mathcal{B}_{r}|=|\mathcal{A}_{r-1}|-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}$
and
$\min_{i\in\mathcal{B}_{r}}\Delta_{i}\geq\Delta_{\left\lceil\frac{d}{2^{r+1}}\right\rceil+1}$.

If the best arm is eliminated in phase $r,$ then at least
${\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1$
arms of $\mathcal{B}_{r}$ have their estimates of the expected rewards larger
than that of the best arm.

Let $N_{r}$ denote the number of arms in $\mathcal{B}_{r}$ whose estimates of
the expected rewards larger than that of the best arm. By Lemma 2, we have

$\displaystyle\operatorname{\mathbb{E}}\left[N_{r}\mid
1\in\mathcal{A}_{r-1}\right]$
$\displaystyle=\sum_{i\in\mathcal{B}_{r}}\Pr\left[\hat{p}_{r}(1)<\hat{p}_{r}(i)\mid
1\in\mathcal{A}_{r-1}\right]$
$\displaystyle\leq\sum_{i\in\mathcal{B}_{r}}\exp\left(-\frac{m\Delta_{i}^{2}}{8{\left\lceil\frac{d}{2^{r-1}}\right\rceil}}\right)$
$\displaystyle\leq|\mathcal{B}_{r}|\max_{i\in\mathcal{B}_{r}}\exp\left(-\frac{m\Delta_{i}^{2}}{8{\left\lceil\frac{d}{2^{r-1}}\right\rceil}}\right)$
$\displaystyle\leq\left(|\mathcal{A}_{r-1}|-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}\right)\exp\left(-\frac{m\Delta_{\left\lceil\frac{d}{2^{r+1}}\right\rceil+1}^{2}}{8{\left\lceil\frac{d}{2^{r-1}}\right\rceil}}\right)$
$\displaystyle\leq\left(|\mathcal{A}_{r-1}|-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}\right)\exp\left(-\frac{m\Delta_{\left\lceil\frac{d}{2^{r+1}}\right\rceil+1}^{2}}{32\left({\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1\right)}\right).$

Then, together with Markov’s inequality, we can get

$\displaystyle\Pr[1\notin\mathcal{A}_{r}\mid 1\in\mathcal{A}_{r-1}]$
$\displaystyle\leq\Pr\left[N_{r}\geq{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1\mid
1\in\mathcal{A}_{r-1}\right]$
$\displaystyle\leq\frac{\operatorname{\mathbb{E}}\left[N_{r}\mid
1\in\mathcal{A}_{r-1}\right]}{{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}$
$\displaystyle\leq\frac{|\mathcal{A}_{r-1}|-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}\exp\left(-\frac{m\Delta_{\left\lceil\frac{d}{2^{r+1}}\right\rceil+1}^{2}}{32\left({\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1\right)}\right).$

When $r=1$, we have $|\mathcal{A}_{r-1}|=K$. Thus,

$\displaystyle\frac{|\mathcal{A}_{r-1}|-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}$
$\displaystyle=\frac{K-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}$
$\displaystyle\leq\frac{K}{{\frac{d}{2}}-{\frac{d}{2^{2}}}}$
$\displaystyle=\frac{4K}{d}.$

When $r>1$, we have
$|\mathcal{A}_{r-1}|={\left\lceil\frac{d}{2^{r-1}}\right\rceil}$. Thus,

$\displaystyle\frac{|\mathcal{A}_{r-1}|-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}$
$\displaystyle=\frac{{\left\lceil\frac{d}{2^{r-1}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\left\lceil\frac{d}{2^{r}}\right\rceil}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}$
$\displaystyle\leq\frac{{\frac{d}{2^{r-1}}}+1-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\frac{d}{2^{r}}}-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}+1}$
$\displaystyle\leq\frac{3\cdot{\frac{d}{2^{r+1}}}+{\frac{d}{2^{r+1}}}+1-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}{{\frac{d}{2^{r+1}}}+{\frac{d}{2^{r+1}}}+1-{\left\lceil\frac{d}{2^{r+1}}\right\rceil}}$
$\displaystyle\leq 3$

where the last inequality results from the fact that for any $x,y>0$,
$\frac{3x+y}{x+y}\leq 3$ .

Eventually, the error probability of phase $r$ can be bounded as

$\Pr[1\notin\mathcal{A}_{r}\mid
1\in\mathcal{A}_{r-1}]\leq\begin{cases}\frac{4K}{d}\exp\left(-\frac{m\Delta_{i_{r}}^{2}}{32i_{r}}\right)&\text{when
}r=1\\\ 3\exp\left(-\frac{m\Delta_{i_{r}}^{2}}{32i_{r}}\right)&\text{when
}r>1\end{cases}$

where $i_{r}={\left\lceil\frac{d}{2^{r+1}}\right\rceil+1}$. ∎

Now we return to the proof of Theorem 2.

###### Proof of Theorem 2.

By applying Lemma 1 and Lemma 3, we have

$\displaystyle\Pr\left[i_{\mathrm{out}}\neq 1\right]$
$\displaystyle=\Pr\left[1\notin\mathcal{A}_{\lceil\log_{2}d\rceil}\right]$
$\displaystyle=\sum_{r=1}^{\lceil\log_{2}d\rceil}\Pr[1\notin\mathcal{A}_{r}\mid
1\in\mathcal{A}_{r-1}]$
$\displaystyle\leq\frac{4K}{d}\exp\left(-\frac{m\Delta_{i_{1}}^{2}}{32i_{1}}\right)+\sum_{r=2}^{\lceil\log_{2}d\rceil}3\exp\left(-\frac{m\Delta_{i_{r}}^{2}}{32i_{r}}\right)$
$\displaystyle\leq\left(\frac{4K}{d}+3\left({\lceil\log_{2}d\rceil}-1\right)\right)\exp\left(-\frac{m}{32}\cdot\frac{1}{\max_{2\leq
i\leq d}\frac{i}{\Delta_{i}^{2}}}\right)$
$\displaystyle<\left(\frac{4K}{d}+3\log_{2}d\right)\exp\left(-\frac{m}{32H_{2,\mathrm{lin}}}\right)$

where $H_{2,\mathrm{lin}}$ is defined as

$H_{2,\mathrm{lin}}=\max_{2\leq i\leq d}\frac{i}{\Delta_{i}^{2}}.$

∎

##  Appendix C Proof of Theorem 3

The proof of Theorem 3 is built on the connection between linear bandits and
standard multi-armed bandits [8]. Therefore, we first introduce the setting of
best arm identification in standard multi-armed bandits.

In a standard multi-armed bandit instance $\tilde{\nu}$, the agent is given an
arm set $\mathcal{A}=[K]$. Each arm $i\in\mathcal{A}$ is associated with a
reward distribution $P_{i}$ supported in $[0,1]$, which is unknown to the
agent. At each time $t$, the agent chooses an arm $A_{t}$ from the arm set
$\mathcal{A}$ and then observes a stochastic reward $X_{t}\in[0,1]$ drawn from
$P_{A_{t}}$.

In the fixed-budget setting, given a time budget $T\in\mathbb{N}$, the agent
also aims at maximizing the probability of identifying the best arm with no
more than $T$ arm pulls. More formally, the agent uses an _online_ algorithm
$\tilde{\pi}$ to decide the arm $A_{t}^{\tilde{\pi}}$ to pull at each time
step $t$, and the arm $i_{\mathrm{out}}^{\tilde{\pi}}\in\mathcal{A}$ to output
as the identified best arm by time $T$.

As in linear bandits, we assume that the expected rewards of the arms are in
descending order and the best arm is unique. Let $\tilde{\mathcal{E}}$ denote
the set of all the linear bandit instances defined above. For any arm
$i\in\mathcal{A}$, let $p(i)$ denote the expected reward under $P_{i}$.
Similarly, for any suboptimal arm $i$, we denote $\Delta_{i}=p(1)-p(i)$ as the
optimality gap. For ease of notation, we also set $\Delta_{1}=\Delta_{2}$.

Moreover, the two hardness quantities $H_{1}$ and $H_{2}$ are also applicable
to standard multi-armed bandits. For any standard multi-armed bandit instance
$\tilde{\nu}\in\tilde{\mathcal{E}}$, we denote the hardness quantity $H_{1}$
of $\tilde{\nu}$ as $H_{1}(\tilde{\nu})$. In addition, let
$\tilde{\mathcal{E}}(a)$ denote the set of standard multi-armed bandit
instances in $\tilde{\mathcal{E}}$ whose $H_{1}$ is bounded by $a$ ($a>0$),
i.e.,
$\tilde{\mathcal{E}}(a)=\\{\tilde{\nu}\in\tilde{\mathcal{E}}:H_{1}(\tilde{\nu})\leq
a\\}$.

A minimax lower bound for the problem of best arm identification in standard
multi-armed bandits in the fixed-budget setting is provided in Theorem 6.

######  Theorem 6 (Adapted from [8, Theorem 1]).

If $T\geq a^{2}\log(6TK)/900$, then

$\min_{\tilde{\pi}}\max_{\tilde{\nu}\in\tilde{\mathcal{E}}(a)}\Pr\left[i_{\mathrm{out}}^{\tilde{\pi}}\neq
1\right]\geq\frac{1}{6}\exp\left(-\frac{240T}{a}\right).$

Further if $a\geq 15K^{2}$, then

$\min_{\tilde{\pi}}\max_{\tilde{\nu}\in\tilde{\mathcal{E}}(a)}\left(\Pr\left[i_{\mathrm{out}}^{\tilde{\pi}}\neq
1\right]\cdot\exp\left(\frac{2700T}{H_{1}(\nu)\log_{2}K}\right)\right)\geq\frac{1}{6}.$

The differences between the constants of Theorem 6 and those of Carpentier and
Locatelli [8] come from the slight difference in the definitions of $H_{1}$.
In particular, as in [22, 33], we define $H_{1}$ as $\sum_{1\leq i\leq
K}\Delta_{i}^{-2}$ instead of $\sum_{2\leq i\leq K}\Delta_{i}^{-2}$.

Now we return to the proof of Theorem 3.

###### Proof of Theorem 3.

The idea of the proof is to reduce the linear bandit problem to the standard
multi-armed bandit problem.

We construct a special linear bandit instance $\nu$ as follows. Recall that we
assume the entire set of original arm vectors $\\{a(1),a(2),\dots,a(K)\\}$
span $\mathbb{R}^{d}$, so it holds that $K\geq d$. For any arm
$i\in\\{1,2,\dots,d\\}$, the corresponding arm vector is chosen to be $e_{i}$,
the $i^{\mathrm{th}}$ standard basis of $\mathbb{R}^{d}$. It follows that
$\theta^{*}=[p(1),p(2),\cdots,p(d)]^{\top}\in\mathbb{R}^{d}$. For all the
remaining arms $i\in\\{d+1,d+2,\dots,K\\}$, the corresponding arm vector
$a(i)$ is chosen to be zero vector, i.e, a vector with all entries equal to
$0$. Furthermore, we require the expected rewards of all the arms to be
nonnegative. That is to say, $p(i)\geq 0$ for all $i\in[K]$ and in particular
$p(i)=0$ for all $i\in\\{d+1,d+2,\dots,K\\}$.

If the agent is given the above extra information that the expected rewards of
all the arms are nonnegative (which can only help the agent improve the
identification probability), then the agent knows immediately that the best
arm must be among the arms $\\{1,2,\dots,d\\}$ since $p(1),p(2),\dots,p(K)\geq
0$. In addition, pulling the remaining arms cannot provide any useful
information since the corresponding arm vectors are vectors of all zeros.
Thus, the best strategy that the agent can follow is to only pull the first
$d$ arms. Consequently, this linear bandit instance $\nu$ is reduced to a
standard bandit instance $\tilde{\nu}$ with $d$ independent arms.

Therefore, Theorem 6 gives a minimax lower bound on the probability of
misidentifying the best arm in the standard bandit instance $\tilde{\nu}$, due
to the fact that any bounded random variable on $[0,1]$ is $1$-subgaussian.
Also, following the above construction, it holds that

$H_{1,\mathrm{lin}}(\nu)=H_{1}(\tilde{\nu}).$

Notice that the agent cannot do better in the absence of the extra information
in the linear bandit instance $\nu$. The minimax lower bound derived from
Theorem 6 is also a minimax lower bound for the problem of best arm
identification in linear bandits in the fixed-budget setting. ∎

##  Appendix D Additional implementation details and numerical results

###  D.1 Additional implementation details

#### OD-LinBAI.

In each phase, we compute an $\epsilon$-approximate G-optimal design, where
$\epsilon=10^{-7}$. As noted in Appendix A, this causes minimal impact on
performance. Moreover, we follow the Wolfe-Atwood Algorithm with the Kumar-
Yildirim start introduced in Todd [36].

#### Sequential Halving.

In any linear banit instance, we treat the $K$ arms as being independent and
then apply Sequential Halving [7].

#### BayesGap.

For unknown parameter vector $\theta^{*}$, we use an uninformative prior with
$\eta=10^{6}$, a very large variance, for a fair comparison. In fact, through
testing we find that this parameter has limited influence on the performance.
With respect to the parameter $\epsilon$ that controls the tolerance of
output, although it suffices to set $\epsilon$ to be the minimum optimality
gap $\Delta_{1}$ theoretically, we follow the setting of Hoffman et al. [12],
i.e., $\epsilon=0$.

  * •

BayesGap-Oracle: We directly give the algorithm exact information of the
required hardness quantity $H_{1}$.

  * •

BayesGap-Adaptive: Following Hoffman et al. [12], we estimate the required
hardness quantity by the three-sigma rule at the beginning of each time step.

###  D.2 Further observations on synthetic dataset 2

It is shown in Figure 3 that BayesGap-Oracle does not outperform its adaptive
version BayesGap-Adaptive and sometimes even falls behind Sequential Halving.
This is partly because BayesGap-Oracle might be too conservative to converge
when $T=2K$. It is noted that in UGapEb [9], from which BayesGap is adapted,
the exploration parameter that controls how much exploration the algorithm
does is tuned even if the required hardness quantity is known to the agent.
Nevertheless, our algorithm OD-LinBAI is fully parameter-free.

The empirical means of $\Delta_{1}$, $H_{1}$, $H_{2}$, $H_{1,\mathrm{lin}}$
and $H_{2,\mathrm{lin}}$ for different $d$ with $c=2$ or $3$ are reported in
Table 2 and Table 3 respectively while the empirical means of the CPU
runtimes666All our experiments are implemented in MATLAB and parallelized on
an Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz. for different algorithms are
listed in Table 4 and Table 5. From these tables, we have the following
observations:

  1. (i)

With the increase in the dimension of the linear bandit instances, the
empirical means of the minimum optimality gap $\Delta_{1}$ vary a little.
However, for OD-LinBAI, the linear bandit instances become easier since the
time budgets grow exponentially.

  2. (ii)

Different from synthetic dataset 1, the values of the four hardness quantities
$H_{1}$, $H_{2}$, $H_{1,\mathrm{lin}}$ and $H_{2,\mathrm{lin}}$ in synthetic
dataset 2 are close, which is because they are dominated by several smallest
optimality gaps.

  3. (iii)

OD-LinBAI shows great superiority in terms of CPU runtimes with the increase
in $d$. Whereas BayesGap is computationally intractable for synthetic dataset
2 with large $d$, due to the time-consuming matrix inverse updates at each
time step.

Table 2: The empirical means of $\Delta_{1}$, $H_{1}$, $H_{2}$, $H_{1,\mathrm{lin}}$ and $H_{2,\mathrm{lin}}$ for different $d$ with $c=2$ $d$ | $\Delta_{1}$ | $H_{1}$ | $H_{2}$ | $H_{1,\mathrm{lin}}$ | $H_{2,\mathrm{lin}}$
---|---|---|---|---|---
2 | 1.040E-01 | 2.054E+09 | 2.054E+09 | 2.054E+09 | 2.054E+09
3 | 6.395E-02 | 2.498E+05 | 2.496E+05 | 2.498E+05 | 2.496E+05
4 | 4.751E-02 | 4.676E+04 | 4.666E+04 | 4.674E+04 | 4.666E+04
5 | 4.632E-02 | 5.305E+03 | 5.180E+03 | 5.264E+03 | 5.180E+03
6 | 4.360E-02 | 3.152E+03 | 2.968E+03 | 3.066E+03 | 2.968E+03
7 | 4.107E-02 | 2.427E+03 | 2.134E+03 | 2.246E+03 | 2.134E+03
8 | 3.998E-02 | 2.994E+03 | 2.490E+03 | 2.623E+03 | 2.490E+03
9 | 3.888E-02 | 2.730E+03 | 1.841E+03 | 1.988E+03 | 1.841E+03
10 | 3.848E-02 | 3.390E+03 | 1.757E+03 | 1.926E+03 | 1.757E+03
11 | 3.763E-02 | 4.809E+03 | 1.787E+03 | 1.932E+03 | 1.741E+03
12 | 3.696E-02 | 7.660E+03 | 2.453E+03 | 2.022E+03 | 1.804E+03
13 | 3.687E-02 | 1.295E+04 | 4.354E+03 | 1.924E+03 | 1.682E+03
14 | 3.657E-02 | 2.358E+04 | 8.747E+03 | 1.982E+03 | 1.708E+03
15 | 3.622E-02 | 4.434E+04 | 1.764E+04 | 2.006E+03 | 1.703E+03
Table 3: The empirical means of $\Delta_{1}$, $H_{1}$, $H_{2}$, $H_{1,\mathrm{lin}}$ and $H_{2,\mathrm{lin}}$ for different $d$ with $c=3$ $d$ | $\Delta_{1}$ | $H_{1}$ | $H_{2}$ | $H_{1,\mathrm{lin}}$ | $H_{2,\mathrm{lin}}$
---|---|---|---|---|---
2 | 4.896E-03 | 6.360E+14 | 6.360E+14 | 6.360E+14 | 6.360E+14
3 | 5.584E-03 | 3.767E+08 | 3.767E+08 | 3.767E+08 | 3.767E+08
4 | 5.655E-03 | 2.814E+06 | 2.812E+06 | 2.813E+06 | 2.812E+06
5 | 5.898E-03 | 3.030E+05 | 3.012E+05 | 3.023E+05 | 3.012E+05
6 | 6.070E-03 | 1.326E+05 | 1.299E+05 | 1.309E+05 | 1.299E+05
7 | 6.224E-03 | 1.128E+05 | 1.074E+05 | 1.083E+05 | 1.074E+05
8 | 6.177E-03 | 9.752E+04 | 8.441E+04 | 8.534E+04 | 8.441E+04
9 | 6.182E-03 | 1.096E+05 | 7.520E+04 | 7.621E+04 | 7.520E+04
Table 4: The empirical means of the CPU runtimes for different algorithms for different $d$ with $c=2$ | CPU runtimes (secs)
---|---
$d$ | OD-LinBAI | Sequential Halving | BayesGap-Oracle | BayesGap-Adaptive
2 | 0.003 | <0.001 | <0.001 | <0.001
3 | 0.006 | <0.001 | 0.001 | 0.001
4 | 0.007 | <0.001 | 0.001 | 0.001
5 | 0.015 | <0.001 | 0.002 | 0.003
6 | 0.015 | <0.001 | 0.006 | 0.007
7 | 0.009 | <0.001 | 0.017 | 0.022
8 | 0.008 | <0.001 | 0.059 | 0.074
9 | 0.011 | <0.001 | 0.206 | 0.245
10 | 0.015 | <0.001 | 0.801 | 0.916
11 | 0.028 | 0.001 | 3.168 | 3.729
12 | 0.067 | 0.001 | 12.992 | 14.163
13 | 0.102 | 0.002 | 49.538 | 54.417
14 | 0.222 | 0.004 | 197.938 | 216.541
15 | 0.413 | 0.008 | 895.692 | 968.930
Table 5: The empirical means of the CPU runtimes for different algorithms for different $d$ with $c=3$ | CPU runtimes (secs)
---|---
$d$ | OD-LinBAI | Sequential Halving | BayesGap-Oracle | BayesGap-Adaptive
2 | 0.003 | <0.001 | 0.001 | 0.001
3 | 0.004 | <0.001 | 0.002 | 0.002
4 | 0.004 | <0.001 | 0.007 | 0.010
5 | 0.005 | <0.001 | 0.049 | 0.065
6 | 0.007 | <0.001 | 0.375 | 0.484
7 | 0.012 | 0.001 | 2.996 | 3.488
8 | 0.037 | 0.001 | 28.768 | 31.679
9 | 0.107 | 0.005 | 247.645 | 280.018

###  D.3 Real-world dataset: Abalone dataset

We conduct an experiment on the Abalone dataset [34], which includes $4177$
groups of $8$ attributes (such as sex, length, diameter, etc.) of the abalone
as well as its target variable which is the abalone’s age. The age of each
abalone is usually hard to determine so it is tempting to predict the age
using the $8$ attributes from physical measurements. To adapt the dataset into
a linear bandit problem, we first use the whole dataset to calculate the
linear regression coefficient vector $\theta^{*}\in\mathbb{R}^{9}$ and then
form a set of arm vectors by the attributes of $400$ abalones with the largest
true ages. Therefore, in this real-world dataset, it holds that $d=9$ and
$K=400$. We assume that the additive random noise follows a Gaussian
distribution $\mathcal{N}(0,10^{2})$. The experimental results of the $4$
different algorithms are shown in Figure 4.

Figure 4: Error probabilities for different time budgets $T$.

From Figure 4, we see that OD-LinBAI outperforms the other competitors for all
time horizons $T$.