# Exploration in Linear Bandits with Rich Action Sets and its Implications for
Inference

Debangshu Banerjee  Avishek Ghosh  Halicioglu Data Science Institute,
University of California, USA  Sayak Ray Chowdhury  Division of Systems
Engineering, Boston University, USA  Aditya Gopalan

###### Abstract

We present a non-asymptotic lower bound on the spectrum of the design matrix
generated by any linear bandit algorithm with sub-linear regret when the
action set has well-behaved curvature. Specifically, we show that the minimum
eigenvalue of the expected design matrix grows as $\Omega(\sqrt{n})$ whenever
the expected cumulative regret of the algorithm is $O(\sqrt{n})$, where $n$ is
the learning horizon, and the action-space has a constant Hessian around the
optimal arm. This shows that such action-spaces force a polynomial lower bound
on the least eigenvalue, rather than a logarithmic lower bound as shown by
Lattimore and Szepesvari (2017)for discrete (i.e., well-separated) action
spaces. Furthermore, while the latter holds only in the asymptotic regime
($n\to\infty$), our result for these “locally rich” action spaces is any-time.
Additionally, under a mild technical assumption, we obtain a similar lower
bound on the minimum eigen value holding with high probability. We apply our
result to two practical scenarios – _model selection_ and _clustering_ in
linear bandits. For model selection, we show that an epoch-based linear bandit
algorithm adapts to the true model complexity at a rate exponential in the
number of epochs, by virtue of our novel spectral bound. For clustering, we
consider a multi agent framework where we show, by leveraging the spectral
result, that no forced exploration is necessary—the agents can run a linear
bandit algorithm and estimate their underlying parameters at once, and hence
incur a low regret.

##  1 INTRODUCTION

Bandit optimisation traditionally focuses on the problem of minimising
cumulative regret, or the shortfall in reward incurred along the trajectory of
learning. To this end, it has yielded optimal, low-regret strategies such as
UCB and Thompson sampling (Abbasi-yadkori et al., 2011; Abeille and Lazaric,
2017). On the other hand, there is also the important inference goal in bandit
problems, in which the experimenter, having access to arms or alternatives,
wishes to infer some useful properties of, or estimate a quantity related to,
the system by sequential sampling. Perhaps the most well-known example is the
problem of best arm identification in multi-armed bandits (Even-Dar et al.,
2006; Soare et al., 2014), which is essentially a sequential hypothesis
testing problem. It is well known that for optimal error rates in identifying
the best arm, it is necessary to sample arms with at least constant
frequencies, which is vastly more exploratory than the frequencies required
for regret minimization (Bubeck et al., 2011).

In this paper, we are interested in identifying settings in which both
objectives – sublinear regret and fast inference (estimation error) – are
simultaneously possible, opening the door to many useful applications that
combine both reward optimisation and statistical inference. As we shall see,
this is possible with standard bandit algorithms such as (linear) UCB provided
there is sufficient ‘local richness’ of actions or arms in the problem (think
‘suitably continuous arm set’), which is often a reasonable structure
encountered in many bandit optimization problems with continuous spaces of
alternatives (power control, dynamic pricing, etc.) To introduce ideas,
consider standard linear bandit with additive Gaussian noise. A key
trajectory-dependent quantity that connects the two goals of regret
minimisation and parameter estimation is the minimum singular value of the
design matrix, $\lambda_{\min}(V_{n})$. To see why, notice that any typical
bandit algorithm for regret minimization forms, either explicitly or
otherwise, confidence sets for the unknown linear model parameter
$\theta^{*}$, of the form $\|\theta-\widehat{\theta}\|_{V_{n}}\leqslant
c\sqrt{\ln(n)}$, where $c>0$ is a constant. Thus, getting a lower bound on the
growth of $\lambda_{\min}(V_{n})$, would help in determining how fast the
confidence sets shrink and in return would help to infer the true bandit
parameter $\theta^{*}$.

The closest related work that sheds light on the singular value of the design
matrix is by Lattimore and Szepesvari (2017). The authors show that for a
discrete action-space bandit and any bandit algorithm with sub-polynomial
regret (e.g., UCB), the minimum singular value of the expected design matrix
($\mathbb{E}[V_{n}]$ ) must grow at a logarithmic rate over time. However,
their analysis holds true only in the asymptotic regime, with no information
available on what happens in a finite time horizon.

We show that in action-spaces with “nice” local curvature properties, bandit
algorithms which have inherently good regret properties (at most of the order
of $\sqrt{n}$), the minimum singular value of the expected design matrix grows
at least as order of $\sqrt{n}$. This is accomplished by a novel use of matrix
perturbation techniques (Weyl’s inequality and the Davis-Kahan sin-$\theta$
theorem) together with the information-theoretic data-processing inequality.
Moreover, this result holds true in a finite-time horizon and not just in the
asymptotic regime: for all time horizons $n$ larger than a baseline value
$n_{0}$, we show $\lambda_{\min}\mathbb{E}[V_{n}]\geqslant\gamma\sqrt{n}$,
where $\gamma$ is a positive constant which depends upon the local curvature
and the algorithm being used. A key implication of this result is that in
bandits with continuous action-spaces, low-regret algorithms also offer
significant exploration in the sense of estimating all ‘directions’ in the
parameter space. This not only extends the work of Lattimore and Szepesvari
(2017) to the continuous action setting but also strengthens it to a finite
time result from an asymptotic one.

We conclude with two illustrative applications of our theory under a mild
assumption that the same $\Omega(\sqrt{n})$ growth of the minimum eigenvalue
holds also in high probability.111In the appendix, we provide a technical
condition on the trajectory of linear bandit algorithms under which this
holds. Specifically, we consider the model-selection (Foster et al., 2019) and
clustering (Gentile et al., 2014a) problems in linear bandits to apply our
result. In the model selection application, the norm of the unknown parameter
$\theta$ is viewed as a measure of complexity of the problem. We show that a
variant of the well-known Optimism in the Face of Uncertainty (OFU) algorithm
can adapt to $\left\lVert\theta\right\rVert$. This is achieved by a careful
application of our result to control the rate at which norm estimates converge
to the the true norm. It is important to note that a similar result is
achieved by Ghosh et al. (2021a) in the different but related setting of
_stochastic contextual bandits_ , albeit with restrictive assumptions on the
contexts. We are able to proceed without such restrictions by virtue of our
result. In the clustering setup, we consider several linear bandit agents
partitioned into $k$ clusters. We propose a clustering algorithm without any
explicit exploration, where the agents simultaneously estimate their (linear
model) parameter and attempt to play low-regret actions. When the clusters are
separated, our algorithm obtains the correct clustering with high probability.
Note that in Gentile et al. (2014b); Ghosh et al. (2021b), the framework of
clustered bandits was considered in a contextual framework with several strong
assumptions on the context distribution. Our work demonstrates that similar
guarantees are attainable (in the context-free linear bandit setup) without
additional assumptions via exploiting the rich-action-set inference result
(Theorem 2.2). Finally, we empirically validate that the minimum eigenvalue of
the design matrix generated by the well-known Thompson sampling algorithm
(Agrawal and Goyal, 2013) indeed grows at a rate larger than $\sqrt{n}$.

Related work. The linear bandit problem has been studied extensively in a
large body of work starting from the classic work of Auer et al. (2002). In
this model, algorithms based on the celebrated optimism in the face of
uncertainty principle has been designed and analyzed by several authors (Chu
et al., 2011; Dani et al., 2008; Abbasi-yadkori et al., 2011). A related
approach is posterior sampling, also known as Thompson sampling, where
sufficient exploration is achieved by randomly sampling a parameter from a
posterior distribution over $\theta$ (Agrawal and Goyal, 2013; Abeille and
Lazaric, 2017). Another related line of work consider the linear reward model
in reproducing kernel Hilbert spaces (Srinivas et al., 2009; Valko et al.,
2013; Chowdhury and Gopalan, 2017). Spectral properties of the expected design
matrix under a discrete action-space has been studied by Lattimore and
Szepesvari (2017), while Hao et al. (2020) handles the finitely many
contextual case with each context having discrete action space. The framework
of model selection has recently gained a lot of momentum in the bandit
literature. For example, Chatterji et al. (2020) introduced a hypothesis test
based framework to select either the standard bandit or the linear bandit
model. Furthermore, in Ghosh et al. (2021a), the authors define parameter norm
and sparsity as complexity parameters for stochastic linear bandit and adapt
to those without any apriori knowledge, and obtain model selection guarantees.
Moreover, Foster et al. (2019) introduces an adaptive algorithm for a similar
linear bandit problem with sparsity as a measure of complexity. Additionally,
there are different line of works, that uses the the corrall framework of
Agarwal et al. (2017) to obtain adaptive algorithms for bandits and
reinforcement learning (for example, see Pacchiano et al. (2020)). Very
recently, for generic contextual bandits, the adaptation question is also
addressed in Krishnamurthy and Athey (2021). Furthermore, on clustering of
bandits, Gentile et al. (2014b) proposes an algorithm that works only when the
cluster separation is large, which was further improved in Ghosh et al.
(2021b), where near optimal regret is obtained even when the clusters are not
separable. Moreover, Ghosh et al. (2021b) also proposes a natural
personalization framework, which is a generalization of the clustering setup.

Notation. For a positive definite matrix $G$, (denoted as $G\succ 0$) and
vector $x$ we write $\|x\|^{2}_{G}=x^{\top}Gx$ The euclidean norm of a vector
$x$ is denoted as $\|x\|$ and the spectral norm of a matrix $G$ is
$\|G\|=\lambda_{\max}(G)$. For hermitian matrices we assume the eigen-
decomposition as $G=\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}$, with
$\lambda_{1}>\lambda_{d}=\lambda_{\min}$. We use standard definitions of
Landau Notation when using $O$, $o$, $\Omega$ and $\omega$ notation. We use
$\mathbb{E}_{\theta}[\;.\;]$, to emphasize that the underlying bandit instance
is parameterized by $\theta$.

Problem setting. We consider the linear bandit model of Abbasi-yadkori et al.
(2011). Let $\mathcal{X}\subset\mathbb{R}^{d}$. The learner interact with the
environment over $n$ rounds. At each round $t$, the learner chooses an action
$A_{t}\in\mathcal{X}$ and correspondingly observes a reward $Y_{t}=\langle
A_{t},\theta\rangle+\eta_{t}$, where $\eta_{t}$ is a zero-mean Gaussian noise,
and $\theta\in\mathbb{R}^{d}$ is the unknown parameter. The optimal action is
$x^{*}=\arg\max_{x\in\mathcal{X}}\langle x,\theta\rangle$. The performance of
the learner is typically measured using its expected regret, defined as

$\displaystyle\mathbb{E}[R_{n}(\theta)]=\mathbb{E}\left[{\sum\nolimits_{t=1}^{n}\langle
x^{*}-A_{t},\theta\rangle}\right]~{}.$

Here the expectation is over the action-selection strategy of the learner,
denoted, where needed, by $\pi$, and over the randomness in observed rewards.

##  2 MAIN RESULT

In this section, we develop our main result which characterizes the growth of
the minimum eigenvalue of the design matrix for linear bandit algorithms run
on action spaces with suitable ‘local curvature’. By this we mean action
spaces which are hyper-surfaces of the form $\\{x:f(x)=c\\}$, where $f$ is a
twice-continuously differentiable function. The following definition expresses
the local curvature property needed for our result.

######  Definition 2.1 (Locally Constant Hessian (LCH) surface).

Consider the action space defined by
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:f(x)=c\\}$, where
$f:\mathbb{R}^{d}\to\mathbb{R}$ is a $C^{2}$ function (i.e., all second-order
partial derivatives of $f$ exist and are continuous) and $c\in\mathbb{R}$. Let
$\theta\in\mathbb{R}^{d}$. $\mathcal{X}$ is said to be a LCH surface w.r.t.
$\theta$ if: (i) there is a unique reward-optimal arm with respect to $\theta$
(denoted by
$\mathrm{OPT}_{\mathcal{X}}(\theta)=\arg\max_{x\in\mathcal{X}}\langle
x,\theta\rangle$), and (ii) there is an open neighborhood
$U\subset\mathbb{R}^{d}$ of $\mathrm{OPT}_{\mathcal{X}}(\theta)$ over which
the Hessian of $f$ is constant and positive-definite.

Examples of LCH action spaces. Any ellipsoidal action space
$\mathcal{E}=\\{x\in\mathbb{R}^{d}:x^{\top}A^{-1}x=c\\}$, with $c>0$ and $A$
positive-definite, is an LCH action space w.r.t. every
$\theta\in\mathbb{R}^{d}$, as the Hessian of $f(x)=x^{\top}A^{-1}x$ is the
constant p.d. matrix $A^{-1}$. However, an action space can be LCH just by
being ‘locally ellipsoidal’. As an example, consider an ellipsoid
$\mathcal{E}=\\{x\in\mathbb{R}^{d}:x^{\top}A^{-1}x=c\\}$. Let $\theta$ be a
bandit parameter and $x^{*}=\arg\max_{x\in\mathcal{E}}\langle x,\theta\rangle$
be optimal for $\theta$. For some $\delta>0$, let $\mathcal{B}_{\delta}$ be an
open $\delta$-ball in $\mathbb{R}^{d}$ containing $x^{*}$. Consider an action
space $\mathcal{X}$ which coincides with $\mathcal{E}$ in the neighborhood
$\mathcal{B}_{\delta}$ and is arbitrary outside it, i.e.,
$\mathcal{X}\cap\mathcal{B}_{\delta}$ = $\mathcal{E}\cap\mathcal{B}_{\delta}$.
It follows that $\mathcal{X}$ is LCH w.r.t. $\theta$.

######  Theorem 2.2.

Let the action-space $\mathcal{X}$ be a Locally Constant Hessian(LCH) surface
in $\mathbb{R}^{d-1}$ w.r.t. a bandit parameter $\theta$. Let
$\bar{G}_{n}=\mathbb{E}_{\theta}\left[\sum_{s=1}^{n}A_{s}A_{s}^{\top}\right]$,
where $A_{s}$ are arms in $\mathcal{X}$ drawn according to some bandit
algorithm. For any bandit algorithm which suffers expected regret222Our big-Oh
and Omega notations throughout omit polylogarithmic dependencies for ease of
presentation. at most $O(\sqrt{n})$,

$\displaystyle\lambda_{\min}(\bar{G}_{n})=\Omega(\sqrt{n})\;.$

That is, there exists an $n_{0}$ and a constant $\gamma>0$, such that for all
$n\geqslant n_{0}$, $\lambda_{\min}(\bar{G}_{n})\geqslant\gamma\sqrt{n}$.

The constant $\gamma$ depends upon the condition number of the Hessian, the
algorithmic constants hidden by $O()$, and the size of the bandit parameter
$\theta$. The constant $n_{0}$ depends on the algorithmic constants hidden by
$O()$, the size of the neighbourbood over which the Hessian is constant, the
size of the action domain $\left\lVert\mathcal{X}\right\rVert$, the singular
value of the Hessian and the size of the bandit parameter $\theta$.

Comparison with the result of Lattimore and Szepesvari (2017). The authors
show a similar result for asymptotically large $n$. Specifically, they show
that for a linear bandit with a discrete action-space (i.e., one for which the
arms’ suboptimality gaps are at least a positive constant), for any good
(i.e., low-regret) bandit algorithm, it holds that

$\displaystyle\lim\inf_{n\to\infty}\frac{\lambda_{\min}(\bar{G}_{n})}{\log
n}>0.$

In contrast, we prove a bound for any finite $n>n_{0}$. Moreover, our result
applies to a broad category of action spaces.

Comparison with Bubeck et al. (2011). Bubeck et al. (2011) show that for a
finite-armed bandit, an optimal cumulative regret ($O(\log T)$) algorithm must
suffer $\Omega(\text{poly}(1/T))$ simple regret, or equivalently, a
probability of misidentifying the best arm for inference, in $T$ time slots.
Optimal inference (best arm) identification algorithms can, in contrast,
obtain $e^{-\Omega(T)}$ simple regret at the cost of linear cumulative regret.
Our result does not contradict this paper as our action space is richer (i.e.,
continuous) than that of a finite-armed bandit, leading to qualitatively
different behavior: (a) On one hand, due to the minimum arm suboptimality gap
in this setting being zero, the optimal cumulative regret rate is
$O(\sqrt{T})$ (regret minimization is harder), (b) On the other hand,
inference is easier with an optimal cumulative regret strategy with estimation
error (for estimating $\theta^{*}$) decaying as $O(T^{-1/4})$. Thus, for
action-spaces which are locally ”nice” enough as described above, any good
regret algorithm must induce a well conditioned expected design matrix, and
this has implications for parameter recovery as illustrated later.

Dependence on dimension. Though our result does not explicitly indicate the
dependence on the ambient (feature) dimension $d$, it is sensitive to it via
the regret of the linear bandit algorithm in question. For example, for the
OFUL algorithm (Abbasi-yadkori et al., 2011), we have a regret bound varying
with the dimension as $O(d)$, while for Thompson Sampling (TS) we have a
regret bound depending on $d$ as $O(d^{3/2})$ (Agrawal and Goyal, 2013;
Abeille and Lazaric, 2017). The constants $n_{0}$ and $\gamma$ of Theorem 2.2
depend on $d$ as $\Omega(d^{2})$ and $\Omega(\frac{1}{d})$ for OFUL and as
$\Omega(d^{3})$ and $\Omega(\frac{1}{d^{3/2}})$ for TS respectively for a
spherical action space. We provide more remarks on this in the experiment
section.

###  2.1 Key Technique: Overview

In this section, for simplicity and insights, we provide a proof sketch for
Theorem 2.2 for the spherical action space $\mathcal{X}=\mathcal{S}^{d-1}$. In
Appendix 7, we first generalize these ideas for general ellipsoidal results,
and finally prove for Locally Constant Hessian surfaces.

###### Proof Sketch.

We start with the following information inequality for linear bandits (see
Lemma 12.1 in appendix and Lattimore and Szepesvári (2020)):

$\displaystyle\frac{1}{2}\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}\geqslant\mathrm{KL}\left(\mathrm{Ber}(\mathbb{E}_{\theta}[Z])||\mathrm{Ber}(\mathbb{E}_{\theta^{\prime}}[Z])\right)$
(1)

for any $\theta^{\prime}\in\mathbb{R}^{d}$ and a measurable random variable
$Z\in(0,1)$. As $\mathrm{span}(\mathcal{S}^{d-1})=\mathbb{R}^{d}$,
$\bar{G}_{n}$ will eventually be non-singular (Lattimore and Szepesvari,
2017). Hence, let the eigendecomposition of $\bar{G}_{n}$ be
$\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}$ with $\lambda_{i}$’s arranged in
descending order. Let us choose $\theta^{\prime}$ to be $\theta+\alpha u_{d}$,
where $\alpha$ is a step size to be determined. This gives the L.H.S. of (1)
as

$\displaystyle\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}=\alpha^{2}\|u_{d}\|^{2}_{\bar{G}_{n}}=\alpha^{2}\lambda_{d}~{}.$
(2)

Let us define an $\varepsilon$-neighbourhood about the optimal arm
$\mathrm{OPT}(\theta)$ for a bandit parameter $\theta$ as

$\displaystyle\mathrm{OPT}_{\varepsilon}(\theta)\triangleq\\{x\in\mathcal{X}\mid
x^{\top}\theta\geqslant\sup\nolimits_{x}x^{\top}\theta-\varepsilon\\}~{}.$

The step size $\alpha$ needs to be chosen such that $\theta$ and
$\theta^{\prime}$ are close in norm. At the same time, we need to ensure that
the optimal arm for $\theta$ is sub-optimal for $\theta^{\prime}$ and vice-
versa. This motivates us to find an $\alpha$ such that

$\displaystyle\mathrm{OPT}_{\varepsilon}(\theta)\cap\mathrm{OPT}_{\varepsilon}(\theta+\alpha
u_{d})=\emptyset~{}.$ (3)

We denote the number of times an arm in the $\varepsilon$-neighbourhood of
$\theta$ is played as

$\displaystyle\mathrm{N}_{\varepsilon,n}(\theta)\triangleq\sum\nolimits_{s=1}^{n}\mathrm{1}\\{A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)\\}$

Now, we define $Z$ in (1) as the fraction of times in $n$ rounds that an arm
in the $\varepsilon$-neighbourhood of $\theta$ is played, i.e.,
$Z\triangleq\frac{\mathrm{N}_{\varepsilon,n}(\theta)}{n}$. Then, as
$\mathrm{OPT}_{\varepsilon}(\theta)$ and
$\mathrm{OPT}_{\varepsilon}(\theta^{\prime})$ are disjoint,
$\mathbb{E}_{\theta}[Z]$ and $\mathbb{E}_{\theta^{\prime}}[Z]$ will be
different (in fact this is what a sub-linear regret algorithm is expected to
do), and hence the right hand side of (1) will be positive. To choose the step
size $\alpha$, we exploit the geometry of the action-space. We refer to the
Figure 1 from which it is clear that the amount $\alpha$ needed to perturb
$\theta$ to $\theta^{\prime}$ such that the disjoint condition (3) holds would
depend upon the orientation of $u_{d}$ with respect to $\mathrm{OPT}(\theta)$,
which is $\theta$ itself, in our geometry. 333For tackling the ellipsoidal
case, we need to change variables (‘whitening’) to bridge to the sphere case;
see Appendix 7.

$\displaystyle
OPT_{\varepsilon}(\theta^{\prime})$$\displaystyle\theta^{\prime}$$\displaystyle\theta$$\displaystyle\alpha
u_{d}$$\displaystyle
OPT_{\varepsilon}(\theta)$$\displaystyle\mathcal{X}=\mathcal{S}{{}^{d-1}}$
Figure 1: The arm set $\mathcal{S}^{d-1}$ with the bandit parameter
$\theta=v$, the optimal arm. The direction $u_{d}$ is approximately orthogonal
to $v$. The task is to find $\alpha$, the amount of perturbation of $\theta$
to $\theta^{\prime}$ in the direction of $u_{d}$, so that the $\varepsilon$
neighbourhood of both $\theta$ and $\theta^{\prime}$ is disjoint

We use the Davis-Kahan matrix perturbation theorem (see Lemma 12.3) to show
$\mathrm{OPT}(\theta)$ (denoted here on as $v$ for notational simplicity) and
$u_{d}$ are approximately orthogonal. In its simplest form, the Theorem states
that given two matrices $A$ and $H$ (symmetric), if $\lambda_{1}(A)$ and all
of $\lambda_{2}(A+H),\cdots,\lambda_{d}(A+H)$ are separated by $\delta$, then
the eigenvector $v$ corresponding to $\lambda_{1}(A)$ and the eigenvectors
$u_{2},\cdots,u_{d}$ corresponding to
$\lambda_{2}(A+H),\cdots,\lambda_{d}(A+H)$, make an inner product of at most
$\left\lVert H\right\rVert/\delta$, i.e.,
$|\max_{i=2,\cdots,d}v^{\top}u_{i}|\leqslant\left\lVert H\right\rVert/\delta$.

We use $A$ as $nvv{{}^{\top}}$ and $H$ as $\bar{G}_{n}-nvv^{\top}$ such that
$v$ is eigen-vector of $nvv{{}^{\top}}$ corresponding to $\lambda_{1}(A)=n$
and $u_{2},\cdots,u_{d}$ are the eigenvectors of $A+H=\bar{G}_{n}$
corresponding to the eigenvalues
$(\lambda_{2}(\bar{G}_{n}),\cdots,\lambda_{d}(\bar{G}_{n}))$. To find an upper
bound of $\langle v,u_{d}\rangle$, we get an upper bound on the spectral norm
of $\bar{G}_{n}-nvv^{\top}$ and the eigen-gap between
$\lambda_{1}(nvv^{\top})=n$ and
$\lambda_{2}(\bar{G}_{n}),\cdots,\lambda_{d}(\bar{G}_{n})$.

We know from Weyl’s Lemma (see Lemma 12.4) that
$\lambda_{i}(\bar{G}_{n})\leqslant\lambda_{i}(nvv^{\top})+\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert=\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert$,
for $i\in\\{2,\cdots,d\\}$ as $\lambda_{i}(nvv^{\top})=0$ for all
$i\in\\{2,\cdots,d\\}$. Thus it suffices to upper bound the spectral norm,
$\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert$. To do so we decompose it into
two cases: when the action played ($A_{s}$) belongs to the optimal set
$\mathrm{OPT}_{\varepsilon}(\theta)$, and when it does not. This yields the
following

$\displaystyle\|\bar{G}_{n}-nvv^{\top}\|$
$\displaystyle\leqslant\sup_{A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)}2\left\lVert
A_{s}-v\right\rVert\mathbb{E}\left[{\mathrm{N}_{\varepsilon,n}(\theta)}\right]$
$\displaystyle\quad\quad+4\mathbb{E}\left[{n-\mathrm{N}_{\varepsilon,n}(\theta)}\right],$
(4)

where we have used the fact that arms in $\mathcal{S}^{d-1}$ has maximum norm
of $1$. We use the geometry of the action-space to determine that for any
$A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)$, we have $\left\lVert
A_{s}-v\right\rVert\leqslant O(\sqrt{\varepsilon})$ (see Appendix 7 for
details). Now, we use the regret property of algorithm to show
$\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]\geqslant
n-c\sqrt{n}/\varepsilon$, as

$\displaystyle c\sqrt{n}$
$\displaystyle\geqslant\mathbb{E}\left[\sum_{s=1}^{n}\max_{x}x^{\top}\theta-
A_{s}^{\top}\theta\right]$
$\displaystyle\geqslant\mathbb{E}\left[\sum_{s=1}^{n}\mathrm{1}\\{A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)\\}(\max_{x}x^{T}\theta-
A_{s}^{T}\theta)\right]$
$\displaystyle\geqslant\varepsilon(\mathbb{E}\left[n-\mathrm{N}_{\varepsilon,n}(\theta)\right])\;.$
(5)

Thus, we have an upper bound on the spectral norm of $\bar{G}_{n}-nvv^{\top}$
as $\|\bar{G}_{n}-nvv^{\top}\|\leqslant
O\big{(}\sqrt{\varepsilon}n+\frac{\sqrt{n}}{\varepsilon}\big{)}.$ Now choosing
$\varepsilon$ to be of the order $\frac{1}{\sqrt{n}}$ with a sufficiently
large constant factor, we ensure the norm of
$\|\bar{G}_{n}-nvv^{\top}\|\leqslant 0.01n$ for all $n$ more than some finite
$n_{0}$. Thus the eigen-gap is at least $0.99n$ and $|\langle
v,u_{d}\rangle|\leqslant 1/99\approx 0$. With this orientation of $u_{d}$, and
the choice of $\varepsilon$, we prove that $\alpha$ has to be of the order of
$\frac{1}{n^{1/4}}$ for
$\mathrm{OPT}_{\varepsilon}(\theta)\cap\mathrm{OPT}_{\varepsilon}(\theta+O(1/n^{1/4})u_{d})=\emptyset$.
The details of this result are provided in the Appendix 7. Now, using our
estimates of $\mathbb{E}_{\theta}[N_{\varepsilon,n}(\theta)]$ (see equation
(2.1)), and by our choice of $\varepsilon=O(1/\sqrt{n})$ we have
$\mathbb{E}_{\theta}[Z]$ close to $1$ and $\mathbb{E}_{\theta^{\prime}}[Z]$
close to $0$. (See the previous discussion for our motivation to choose
disjoint $\varepsilon$ neighbourhood sets). This gives the right hand side of
equation (1) a constant $c$ (See appendix 7 for full details). Therefore
combining with equation (2) we have $\lambda_{d}\geqslant
c/\alpha^{2}=\Omega(\sqrt{n})$. ∎

######  Remark 2.3.

We observe in the above proof that the eigenvector corresponding to the
minimum eigenvalue of $\bar{G}_{n}$ is approximately orthogonal to the
direction of optimal arm. In fact, we show an even stronger fact: every
eigenvector corresponding to each of the eigenvalues, starting from the second
largest to the minimum, must lie in an approximately orthogonal space of the
optimal direction.

##  3 MORE GENERAL ACTION SPACES

###  3.1 Hyper-Surfaces With Continuous Hessian

The basic conclusion of Theorem 2.2 (growth of the minimum eigenvalue of the
design matrix) can be extended beyond LCH action spaces to hyper-surfaces of
the form $\\{x:f(x)=c\\}$ where $f$ is just $C^{2}$ and locally convex,
without requiring a constant Hessian in a neighborhood. However, this comes
potentially at the cost of the $\sqrt{n}$ growth rate of the minimum
eigenvalue.

######  Definition 3.1 (Locally Convex surface).

Consider an action space $\mathcal{X}=\\{x\in\mathbb{R}^{d}:f(x)=c\\}$, where
$f:\mathbb{R}^{d}\to\mathbb{R}$ is a $C^{2}$ function (i.e., all second order
partial derivatives exist and are continuous). With
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ being the optimal arm defined as before,
let the Hessian of $f$ at $\mathrm{OPT}_{\mathcal{X}}(\theta)$, denoted as
$\nabla^{2}f(\mathrm{OPT}_{\mathcal{X}}(\theta))$, be positive definite. Then,
$\mathcal{X}$ is said to be a Locally Convex surface.

######  Remark 3.2.

Locally Convex action spaces are more general than LCH action spaces because
they satisfy the property of the Hessian being positive definite and
continuous at the optimal arm, and do away with the additional requirement of
being constant in a neighbourhood of the optimal arm. This definition can also
be extended to cover the situation when $f$ is a convex function and the
action space is defined as a sub-level set $\\{x:f(x)\leqslant c\\}$ as
described in the next subsection.

For such action-spaces we show that the minimum eigenvalue still enjoys a
polynomial growth rate albeit potentially at a rate less than $\sqrt{n}$.

######  Theorem 3.3.

Let $\mathcal{X}$ be a Locally Convex action space and $\bar{G}_{n}$, be the
expected design matrix. For any bandit algorithm which suffers expected regret
at most $O(\sqrt{n})$, there exists a real number $s$ in the half-open
interval $(0,\frac{1}{2}]$ such that

$\lambda_{\min}(\bar{G}_{n})=\Omega(n^{s})~{}.$

The idea of the proof is to approximate a local neighbourhood around the
optimal arm by an LCH surface, and to argue sufficient separation of optimal
neighbourhoods in the LCH surface to ensure that the optimal neighbourhoods in
the original neighbourhood are separated as well. The rest of the argument
remains the same as for LCH spaces, and can be found in full detail in
Appendix 8.

######  Remark 3.4.

The exponent $s$ defined in Theorem 3.3 depends explicitly on the geometry of
the action-space. In general it depends on how well the surface approximates a
LCH surface and in the Appendix 8 we provide a full methodology on how to
calculate $s$. Here we just remark that for LCH action surfaces we recover the
$\sqrt{n}$ growth rate.

###  3.2 Action Spaces With “Volume”

Our results of Theorem 2.2 and Theorem 3.3 continue to hold even if we replace
the action space $\\{x:f(x)=c\\}$ by action spaces which are defined as sub-
level sets for a $C^{2}$ convex function function $\\{x:f(x)\leqslant c\\}$.
Note that any bandit algorithm would make the greedy choice with respect to an
estimate of the bandit parameter $\theta$. This effectively reduces the
playable action space to that on the surface (maximization of a linear
function over a convex domain occurs at the boundary) and we can take the
action space to be the surface. We can also prove this using the basic
principles used in the proof of Theorem 2.2 and by extension Theorem 3.3. For
example, let $\mathcal{X}$ be a ball in $\mathbb{R}^{d}$, and $\theta$ be a
bandit parameter. Without loss in generality, we can take $\|\theta\|=1$
(otherwise, we can make a change of variable argument like in the ellipsoidal
case to show that the result holds, now including a factor of $\|\theta\|$).
The crux of the proof relies on two factors. (a) First, to show that $u_{d}$,
the eigen-vector, corresponding to the minimum eigen-value is approximately
perpendicular to $\mathrm{OPT}_{\mathcal{X}}(\theta)$. (b) Second to show that
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta+\alpha
u_{d})=\emptyset$. For the first part, the main idea is to bound the norm
$\|A_{s}-\mathrm{OPT}_{\mathcal{X}}(\theta)\|$ for any
$A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$. To do so, note that
we had used $\|A_{s}\|=1$ for the surface action spaces. Now, when action
space is a ball, we can take an upper bound on $\|A_{s}\|\leqslant 1$ while
the remainder of the proof follows as before. For the second part, note that
the boundary of $\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ for a ball is
simply $\mathrm{OPT}_{\varepsilon,\mathcal{S}^{d-1}}(\theta)$ as defined
earlier. Thus ensuring the $\varepsilon$-optimal neighbourhoods of the sphere
are separated ensures the separation of the $\varepsilon$-optimal
neighbourhoods of the ball. Now we can proceed as before and find the order of
the separation to get the same conclusions as in Theorem 2.2 and Theorem 3.3.

##  4 NUMERICAL RESULTS

(a) $d=3$ (b) $d=5$

(c) $d=10$ (d) $d=20$

Figure 2: Scaling of the minimum eigenvalue of design matrix generated by the
Thompson sampling algorithm with time. The plots represent averages over $20$
independent trials. The $X$ axis denotes the number of rounds $n$ and the
$Y$-axis denotes $\frac{\log{\lambda_{\min}(V_{n})}}{\log{n}}$. The dotted
black line is the constant (exponent) $1/2$. Note how
$\frac{\log{\lambda_{\min}(V_{n})}}{\log{n}}$ crosses and settles to a value
above $1/2$ in each case.

In this section, we carry out experiments to understand the rate of growth of
the minimum eigenvalue. We find, using a ”good” bandit algorithm and a ”good”
action space, that the minimum eigen-value of the design matrix grows at a
rate of more than $\sqrt{n}$, with high probability. We use the well-known
linear Thompson Sampling (TS) algorithm (Agrawal and Goyal, 2013) as a
representative algorithm for linear bandits. It is well known that the regret
of TS is $\tilde{O}(\sqrt{n})$ with high probability, where the $\tilde{O}$,
hides logarithmic factors. We use a spherical action space
$\mathcal{X}=\mathcal{S}^{d-1}$ as a candidate for the LCH action surfaces and
we fix the unknown bandit parameter $\theta$ at $e_{1}$. We use a
regularization parameter of $\lambda=1.0$.

We observe from Figure 2 the dispersion and mean trend of the sample
trajectory dependent quantity $\log{\lambda_{\min}(V_{n})}/\log{n}$. We expect
to see to see this term cross the benchmark line of $1/2$ for all $n$ more
than a finite $n_{0}$. In order to demonstrate the high probability
phenomenon, we form a high confidence band of the mean observation of
$\log{\lambda_{\min}(V_{n})}/\log{n}$ with three standard deviations of width.
We plot this confidence band and we show that the lower envelope of the band
remains more than $1/2$. It could be observed that the trend of
$\log{\lambda_{\min}(V_{n})}/\log{n}$ remains increasing, but this could be
accounted for the hidden logarithmic factors in the regret of the TS algorithm
itself.

(a) $n_{0}$ trend with dimension $d$ (b) $\gamma$ trend with dimension $d$

Figure 3: Scaling of the theoretical constants $\gamma$ and $n_{0}$ with the
dimension $d$. Note that $n_{0}$ increases with the dimension $d$ whereas
$\gamma$ decreases with the dimension $d$. Since the algorithmic constants
varies appropriately with the dimension $d$, in the case of TS, our
experimental results corroborates with our theory.

We note that for the spherical action space, the constants $n_{0}$ and
$\gamma$ of Theorem 2.2 would vary with the dimension $d$ as $\Omega(d^{3})$
and $\Omega(1/d^{3/2})$ for TS (see proof of Theorem 2.2). In Figure 3 we
explicitly calculate the the mean $n_{0}$, as the time above and over which
$\log{\lambda_{\min}(V_{n})}/\log{n}$ crosses the $0.5$ bench mark, and
observe that our theoretical lower bound of $n_{0}=\Omega(d^{3})$ is a loose
lower bound and that in practical settings the $n_{0}$ can be much less than
the order $d^{3}$. Similarly for $\gamma$, defined as
$\liminf{\frac{\lambda_{\min}(V_{n})}{\sqrt{n}}}$, is plotted as the mean
trend of $\frac{\log{\lambda_{\min}(V_{n})/\sqrt{n}}}{\log{d}}$ for rounds $n$
more than $1000$, as a reasonable upper estimate of $n_{0}$ and see that this
quantity remains well above the benchmark of $-1.5$, thus showing that
$\gamma=\Omega(1/d^{3/2})$, is indeed a loose lower bound.

##  5 APPLICATIONS

We now give two instances where the eigenvalue bound obtained in Theorem 2.2
can be used to its advantage due to its implication of fast inference about
the unknown parameter. We first start by noting that for parameter estimation
we need a high probability version of the Theorem 2.2.

In Theorem 2.2, the eigenvalue bound is shown on the expected design matrix.
In the simulations (Section 4), we observe (over multiple trials) that the
lower envelope of $\lambda_{\min}(V_{n})$ scales as $\Omega(\sqrt{n})$, which
hints towards a high probability result. It turns out that under an
appropriately defined _stability_ condition, the expectation bound can be
translated to a high probability bound. In Appendix 11 we formally define this
stability condition and its consequences. However, in this section, for
clarity of exposition, we take the high probability bound as granted, and
using this, we consider a couple of applications in bandit model selection and
clustering. Recall that we define the Gram matrix as
$V_{n}=\sum_{s=1}^{n}A_{s}A_{s}^{\top}$.

######  Assumption 5.1.

Given an action-set $\mathcal{X}$ which belongs to the class of _Locally
Constant Hessian_ surfaces (see Definition 2.1) for a bandit parameter
$\theta$, for any bandit algorithm which suffers regret, $R_{n}(\theta)$, at
most $O(\sqrt{n})$, there exists a $\delta\in(0,1]$, such that

$\displaystyle\lambda_{\min}(V_{n})=\Omega(\sqrt{n})~{},$

with probability at least $1-\delta$.

######  Remark 5.2.

Using the aforementioned _stability_ condition we can get similar high
probability versions for _Locally Convex_ action spaces. However as discussed
earlier this could potentially loose the $\sqrt{n}$ growth rate of the minimum
eigen-value. For ease of exposition, we shall assume in this section that the
action-space in consideration is an LCH surface unless mentioned otherwise.

###  5.1 Model Selection in Linear Bandits

A natural measure of complexity of linear bandits is the norm of the parameter
$\theta$. Typically it is assumed that $\theta$ lies in a norm ball with known
radius, i.e., $\|\theta\|\leqslant b$ (Abbasi-yadkori et al., 2011; Chatterji
et al., 2020). This leads to non-adaptive algorithms and the algorithms use
$b$ as a proxy for the problem complexity, which can be a huge over-estimate.
We analyze a linear bandit algorithm, that adapts to the problem complexity
$\|\theta\|$, and as a result, the regret obtained will depend on
$\|\theta\|$. Specifically, we start with an over estimate of $\|\theta\|$,
and successively refine this estimate over multiple epochs. We show that this
refinement strategy yields a consistent sequence of estimates of $\|\theta\|$,
and as a consequence, our regret bound depends on $\|\theta\|$, but not on its
upper bound $b$. Ghosh et al. (2021a) considers a similar model selection
problem in a related setting of _stochastic contextual bandits_ , with
restrictive assumptions on the contexts. We show that model selection
guarantees continue to hold even in the context free setting without any
additional assumption by using the result in Theorem 2.2 and the subsequent
Assumption 5.1. Before that, we restate the algorithm of Ghosh et al. (2021a).

####  5.1.1 Algorithm and its Regret Bound

The algorithm – called Adaptive Linear Bandits (ALB) – uses the OFUL algorithm
of Abbasi-yadkori et al. (2011) as a black-box. The learning proceeds in
epochs – at each epoch $i\geqslant 1$, OFUL is run for $n_{i}=2^{i-1}n_{1}$
episodes with confidence level $\delta_{i}=\frac{\delta}{2^{i-1}}$ and norm
estimate $b^{(i)}$, where the initial epoch length $n_{1}$ and confidence
level $\delta$ are parameters of the algorithm. We begin with $b$ as an
initial (over) estimate of $\left\lVert\theta\right\rVert$, and at the end of
$i$-th epoch, based on the confidence set $\mathcal{B}_{n_{i}}$ build by OFUL,
we choose the new estimate as
$b^{(i+1)}=\max_{\theta\in\mathcal{B}_{n_{i}}}\|\theta\|$. We argue that this
sequence of estimates is indeed consistent, and as a result, the regret
depends on $\left\lVert\theta\right\rVert$.

Algorithm 1 Adaptive Linear Bandit (ALB)

1: Input: An upper bound $b$ of $\left\lVert\theta\right\rVert$, initial epoch
length $n_{1}$, confidence level $\delta\in(0,1]$

2: Initialize estimate of $\|\theta\|$ as $b^{(1)}=b$, set $\delta_{1}=\delta$

3: for epochs $i=1,2\ldots$ do

4: Play OFUL with norm estimate $b^{(i)}$ for $n_{i}$ rounds with confidence
level $\delta_{i}$

5: Refine estimate of $\|\theta\|$ as
$b^{(i+1)}\\!=\\!\max_{\theta\in\mathcal{B}_{n_{i}}}\\!\\!\|\theta\|$

6: Set $n_{i+1}=2n_{i}$, $\delta_{i+1}=\frac{\delta_{i}}{2}$

7: end for

Now, we present the main result of this section. We show that, by virtue of
Theorem 2.2 and the subsequent Assumption 5.1, the norm estimates $b^{(i)}$
computed by ALB (Algorithm 1) indeed converges to the true norm
$\left\lVert\theta\right\rVert$ at an exponential rate with high probability.

######  Lemma 5.3 (Convergence of norm estimates).

Suppose Assumption 5.1 holds. Also, suppose that, for any $\delta\in(0,1]$,
the length $n_{1}$ of the initial epoch satisfies

$\displaystyle
n_{1}\\!\geqslant\\!\max\\!\left\\{n_{0},C\,d^{2}\left(\max\\{p,q\\}\,b^{(1)}\right)^{4}\right\\},$

where $p\\!=\\!O\\!\left(\\!\frac{1}{\sqrt{\gamma_{0}}}\\!\right)$,
$q\\!=\\!O\\!\left(\\!\sqrt{\\!\frac{\log(n_{1}/\delta)}{\gamma_{0}}}\right)$,
and $C>1$ is some sufficiently large universal constant. Then, with
probability exceeding $1-4\delta$, the sequence $\\{b^{(i)}\\}_{i=1}^{\infty}$
converges to $\|\theta\|$ at a rate
$\mathcal{O}\left(\frac{i}{2^{i/4}}\right)$, and $b^{(i)}\leqslant
c_{1}\|\theta\|+c_{2}$, where $c_{1},c_{2}>0$ are universal constants.

Comparison with prior work. Ghosh et al. (2021a) consider the setting
stochastic contextual linear bandits, and show that the norm estimates
converge at a rate $\mathcal{O}\left(\frac{i}{2^{i/2}}\right)$. This seemingly
better rate, however, comes at the cost of restrictive assumptions on the
contexts. Specifically, they assume that the minimum eigenvalue of the
conditional covariance matrix (given observations up to time $t$) is bounded
away from zero. This restriction on the contexts severely limits the
applicability of their result. In contrast, we obtain a slightly worse, but
still exponential, convergence rate
$\mathcal{O}\left(\frac{i}{2^{i/4}}\right)$, albeit with a milder assumption
in the context of our main result (Theorem 2.2).

Armed with the above result, we can now prove a sublinear regret bound of ALB.

######  Corollary 5.4 (Cumulative regret of ALB).

Fix any $\delta\in(0,1]$, and suppose that the hypothesis of Lemma 5.3 holds.
Then, with probability exceeding $1-6\delta$, ALB enjoys the regret bound

$\displaystyle R(n)$
$\displaystyle\\!=\\!\tilde{\mathcal{O}}\\!\left(\|\theta\|\sqrt{dn\log
n_{1}}+d\sqrt{n\log n_{1}\log(n_{1}/\delta)}\\!\right)$
$\displaystyle\leqslant\tilde{\mathcal{O}}\left((\|\theta\|+1)\,d\sqrt{n\log(n/\delta)}\right),$

where $\tilde{\mathcal{O}}$ hides a $\mathsf{polylog}(n/n_{1})$ factor.

######  Remark 5.5.

Note that the above regret depends on $\|\theta\|$ and hence is adaptive to
the norm complexity. Furthermore, the term $(\|\theta\|+1)$ can be reduced to
$(\|\theta\|+\varepsilon)$ for an arbitrary $\varepsilon>0$ by increasing the
length of initial epoch in ALB.

Lemma 5.3 and Corollary 5.4 together highlight the advantage of having an
eigenvalue bound as in Theorem 2.2 in this specific setting of model selection
due to its implication in fast inference and regret minimization,
simultaneously.

###  5.2 Clustering without Exploration in Linear Bandits

We consider a multi-agent system with $N$ users, which communicate with a
“center”. Moreover, the agents are partitioned into $k$ clusters. We aim to
identify the cluster identity of each user so that collaborative learning is
possible within a cluster. Note that previously (Gentile et al., 2014a; Ghosh
et al., 2021b) tackled the problem of online clustering in a stochastic
contextual bandit framework, where the players have additional context
information to make a decision. More importantly, in the mentioned works,
several restrictive assumptions were made on the behavior of the stochastic
context, such as, based on the observation upto time $t$, (a) the conditional
mean is $0$, (b) the conditional covariance matrix is positive definite, time
uniform with the minimum eigenvalue bounded away from $0$ and (c) the
conditional variance of the contexts projected in a fixed direction is
bounded. Apart from these three, there are a few additional technical
assumptions made, see (Gentile et al., 2014a, Lemma 1) for example. We believe
it is difficult to find natural examples of contexts where all these
assumptions are satisfied simultaneously, and the authors of the
aforementioned papers also do not provide any.

To this end, we provide clustering guarantee without these restrictive
assumptions. We only require the action space satisfying Definition 2.1, which
includes standard spaces like spheres and ellipsoids. Furthermore, we obtain
the underlying clustering without _pure (forced) exploration_ —thanks to the
lower bound of Theorem 2.2 and the subsequent Assumption 5.1. This is quite
useful in recommendation systems and advertisement placement, where forced
exploration is often very tricky and not at all desired. We stick to the
framework of standard linear bandits, and we assume a clustering framework,
where the user parameters $\\{\theta^{*}_{1},\ldots,\theta^{*}_{N}\\}$ are
partitioned into $k$ groups. All users in a cluster have the same preference
parameter, and hence, without loss of generality, for all $j\in[k]$, we denote
$\theta^{*}_{j}$ as the preference parameter for cluster $j$. We employ the
standard OFUL of Abbasi-yadkori et al. (2011) as our learning algorithm. Note
that, by virtue of Theorem 2.2 and the subsequent Assumption 5.1, we can
estimate the underlying parameter for any agent $i\in[N]$ in $\ell_{2}$ norm.
We use this information to do the clustering task. Our goal here is to propose
an algorithm that finds the correct clustering of all $N$ users while
simultaneously obtain low regret in the process. Before providing the
algorithm and regret guarantee for clustering let us define the (minimum)
separation parameter as $\Delta=\min_{i,j;i\neq
j}\|\theta^{*}_{i}-\theta^{*}_{j}\|$. Note that if $\Delta$ is large, the
problem is easier to solve, and vice versa. Hence, $\Delta$ is also called the
SNR (signal to noise ratio, since we assume that the noise variance is unity)
of the problem.

####  5.2.1 Algorithm and its regret bound

We now present the clustering algorithm, formally given in Algorithm 2. We let
all the agents play the learning algorithm OFUL of Abbasi-yadkori et al.
(2011) for $n$ rounds. Note that, with a lower bound on the minimum eigenvalue
of the Gram matrix (Theorem 2.2, Assumption 5.1), we now can compute how close
the estimated parameters $\\{\widehat{\theta}^{(i)}\\}_{i=1}^{N}$ are to the
true parameters in $\ell_{2}$ norm. The choice of norm is important here. Note
that OFUL also obtains an estimate of the underlying parameter. However, that
closeness is only guaranteed in a problem dependent matrix norm, which can not
be directly used for inference problems like clustering. Note that Theorem..
basically converts this problem dependent norm to (an universal) $\ell_{2}$
norm closeness guarantee, which enables us to perform clustering. After $n$
rounds, the center performs a pairwise clustering with threshold $\gamma$. If
the pairwise distance between two estimates are less than $\gamma$ they are
estimated to belong to the same cluster, otherwise different. This procedure
is given in the EDGE-CLUSTER subroutine. With properly chosen threshold, we
show that Algorithm 2 clusters the agents correctly with high probability.

Algorithm 2 Cluster without Explore

1: Input: No. of users $N$, learning horizon $n$, high probability parameter
$\delta$, threshold $\eta$ Individual Learning Phase

2: All agents play OFUL($\delta)$ independently for $n$ rounds

3: $\\{\widehat{\theta}^{(i)}\\}_{i=1}^{N}\leftarrow$ All agents’ estimates at
the end of round $n$ and send to the center Cluster the Users at center

4: $\texttt{User-Cluster}\leftarrow$ EDGE-
CLUSTER$(\\{\widehat{\theta}^{(i)}\\}_{i=1}^{N},\eta)$ EDGE-CLUSTER

5: Input: All estimates $\\{\widehat{\theta}^{(i)}\\}_{i=1}^{N}$, threshold
$\eta\geqslant 0$.

6: Construct an undirected Graph $G$ on $N$ vertices as follows:
$||\widehat{\theta}^{*}_{i}-\widehat{\theta}^{*}_{j}||\leqslant\eta\Leftrightarrow
i\sim_{G}j$

7: $\mathcal{C}\leftarrow\\{C_{1},\cdots,C_{k}\\}$ all strongly connected
components of $G$

8: Return : $\mathcal{C}$

######  Lemma 5.6.

Suppose we choose the threshold
$\eta=\frac{4}{n^{1/4}}\sqrt{\frac{2d\log(n/\delta)}{\gamma\log(d/\delta)}}$,
and the separation $\Delta$ satisfies
$\Delta>2\eta=\frac{8}{n^{1/4}}\sqrt{\frac{2d\log(n/\delta)}{\gamma\log^{1/2}(d/\delta)}}.$
Then, Algorithm 2 clusters all $N$ agents correctly with probability at least
$1-4\binom{N}{2}\delta$. Furthermore, the regret of any agent $i\in[N]$ is
given by $R_{i}\leqslant\mathcal{O}(d\sqrt{n}\log(1/\delta))$ with probability
at least $1-\delta$.

Note that the separation decays with $n$, and for a large $n$, this is just a
mild requirement. Also, our clustering algorithm does not incur regret from
pure exploration, and the regret is just from playing the OFUL algorithm.

######  Remark 5.7 (Clustering gain).

We run Algorithm 2 upto to the instant where all users are clustered correctly
wit high probability. In particular, we do not characterize the clustering
gain of Algorithm 2 since this is not the main focus of the paper. In order to
see the gain, one needs to do the following: after the agents are clustered,
the center treats each cluster as a single agent, and averages reward from all
users in the same cluster. This ensures standard deviation of the resulting
noise goes down by a factor of $1/\sqrt{N^{\prime}}$ (clustering gain, similar
to Gentile et al. (2014b); Ghosh et al. (2021b)), where $N^{\prime}$ is the
number of users in the cluster.

Clustering without separation assumption on $\Delta$. In the above result, we
assume that the separation $\Delta$ satisfies the above condition. Instead, if
the learner knows $\Delta$, one can set

$\displaystyle\frac{n}{\log^{2}(n/\delta)}\geqslant
C\frac{d^{2}}{\gamma^{2}\,\Delta^{4}}\left(\frac{1}{\log(d/\delta)}\right)=\tilde{\Omega}(\frac{d^{2}}{\gamma^{2}\,\Delta^{4}}),$

and the threshold $\eta=\Delta/2$ to obtain the same result.

##  6 CONCLUSION

We present a minimum eigenvalue bound on the expected design matrix—a
theoretical extension to what is already known for discrete action space. In
particular, we show that in action spaces with locally ”nice” curvature
properties, the above-mentioned minimum eigenvalue grows at the order of
$\sqrt{n}$. We show that this eigenvalue bound enables us to obtain inference
and minimize regret simultaneously, in the linear bandit setup. We then apply
our findings in two practical applications, _bandit clustering_ and _model
selection_. We emphasize these results pave the way for new research in the
area of stability and robustness of practical bandit algorithms. Such ideas
are not new and the study of differentially private algorithms (Dwork et al.,
2014) focuse on this area precisely. Another line of research is to study the
question of asymptotic optimality for algorithms based on the principle of
optimism in the continuous action domain.

## References

  * Abbasi-yadkori et al. (2011) Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24, pages 2312–2320. Curran Associates, Inc., 2011.
  * Abeille and Lazaric (2017) Marc Abeille and Alessandro Lazaric.  Linear thompson sampling revisited.  In _Artificial Intelligence and Statistics_ , pages 176–184. PMLR, 2017.
  * Agarwal et al. (2017) Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire.  Corralling a band of bandit algorithms.  In _Conference on Learning Theory_ , pages 12–38. PMLR, 2017.
  * 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.
  * 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 et al. (2011) Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.  Pure exploration in finitely-armed and continuous-armed bandits.  _Theoretical Computer Science_ , 412(19):1832–1852, 2011.
  * Chatterji et al. (2020) Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett.  Osom: A simultaneously optimal algorithm for multi-armed and linear contextual bandits.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 1844–1854. PMLR, 26–28 Aug 2020.  URL https://proceedings.mlr.press/v108/chatterji20b.html.
  * Chowdhury and Gopalan (2017) Sayak Ray Chowdhury and Aditya Gopalan.  On kernelized multi-armed bandits.  In _International Conference on Machine Learning_ , pages 844–853. PMLR, 2017.
  * Chu et al. (2011) Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 208–214. JMLR Workshop and Conference Proceedings, 2011.
  * Dani et al. (2008) Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * 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.
  * Foster et al. (2019) Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo.  Model selection for contextual bandits.  _Advances in Neural Information Processing Systems_ , 32:14741–14752, 2019.
  * Gentile et al. (2014a) Claudio Gentile, Shuai Li, and Giovanni Zappella.  Online clustering of bandits.  In _International Conference on Machine Learning_ , pages 757–765. PMLR, 2014a.
  * Gentile et al. (2014b) Claudio Gentile, Shuai Li, and Giovanni Zappella.  Online clustering of bandits.  In _International Conference on Machine Learning_ , pages 757–765. PMLR, 2014b.
  * Ghosh et al. (2021a) Avishek Ghosh, Abishek Sankararaman, and Ramchandran Kannan.  Problem-complexity adaptive model selection for stochastic linear bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1396–1404. PMLR, 2021a.
  * Ghosh et al. (2021b) Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran.  Collaborative learning and personalization in multi-agent stochastic linear bandits.  _arXiv preprint arXiv:2106.08902_ , 2021b.
  * Hao et al. (2020) Botao Hao, Tor Lattimore, and Csaba Szepesvari.  Adaptive exploration in linear contextual bandit.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3536–3545. PMLR, 2020.
  * Kaufmann et al. (2016) Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On the complexity of best-arm identification in multi-armed bandit models.  _The Journal of Machine Learning Research_ , 17(1):1–42, 2016.
  * Krishnamurthy and Athey (2021) Sanath Kumar Krishnamurthy and Susan Athey.  Optimal model selection in contextual bandits with many classes via offline oracles.  _arXiv preprint arXiv:2106.06483_ , 2021.
  * Lattimore and Szepesvari (2017) Tor Lattimore and Csaba Szepesvari.  The end of optimism? an asymptotic analysis of finite-armed linear bandits.  In _Artificial Intelligence and Statistics_ , pages 728–737. PMLR, 2017.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Pacchiano et al. (2020) Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett.  Regret bound balancing and elimination for model selection in bandits and rl.  _arXiv preprint arXiv:2012.13045_ , 2020.
  * Soare et al. (2014) Marta Soare, Alessandro Lazaric, and Rémi Munos.  Best-arm identification in linear bandits.  _Advances in Neural Information Processing Systems_ , 27:828–836, 2014.
  * Srinivas et al. (2009) Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger.  Gaussian process optimization in the bandit setting: No regret and experimental design.  _arXiv preprint arXiv:0912.3995_ , 2009.
  * Stewart (1990) Gilbert W Stewart.  Matrix perturbation theory.  1990\.
  * Tropp (2012) Joel A Tropp.  User-friendly tail bounds for sums of random matrices.  _Foundations of computational mathematics_ , 12(4):389–434, 2012.
  * Tropp (2015) Joel A Tropp.  An introduction to matrix concentration inequalities.  _arXiv preprint arXiv:1501.01571_ , 2015.
  * Valko et al. (2013) Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini.  Finite-time analysis of kernelised contextual bandits.  _arXiv preprint arXiv:1309.6869_ , 2013.

##  7 LOCALLY CONSTANT HESSIAN SURFACES (PROOF OF THEOREM 2.2)

In this section we shall prove Theorem 2.2. We shall divide the proof of the
theorem in three parts. In Section 7.1 we shall prove it for spherical surface
action sets. In Section 7.2 we shall extend the proof for ellipsoidal surface
action sets and finally in Section 7.3 we prove the result for the
generalization to action spaces which are LCH surfaces.

###  7.1 Spherical Action Sets

######  Theorem 7.1.

Let the set of arms be
$\mathcal{X}=\mathcal{S}^{d-1}:=\left\\{x\in\mathbb{R}^{d}:\|x\|=1\right\\}$,
the surface of the $d$ dimensional unit sphere. Let
$\bar{G}_{n}=\mathbb{E}_{\theta}\left[\sum_{s=1}^{n}A_{s}A_{s}^{\top}\right]$,
where $\theta$ is a bandit parameter and $A_{s}$ are arms in $\mathcal{X}$
drawn according to some bandit algorithm. For any bandit algorithm which
suffers expected regret, $R_{n}(\theta)$, at most $O(\sqrt{n})$,

$\displaystyle\lambda_{min}(\bar{G}_{n})=\Omega(\sqrt{n})\;.$

That is there exists constants $\gamma>0$ and a finite time $n_{0}$ such that
for all $n\geqslant n_{0}$, we have
$\lambda_{min}(\bar{G}_{n})\geqslant\gamma\sqrt{n}$.

###### Proof.

We start with a result which is standard while proving such lower bounds
(Lattimore and Szepesvari (2017); Lattimore and Szepesvári (2020); Hao et al.
(2020)) which is using the measure change inequality of Kaufmann et al. (2016)
(see Lemma 12.1) combined with the Divergence Decomposition Lemma under the
Linear Bandit Setup Lattimore and Szepesvári (2020) (see Lemma 12.2) to get

$\displaystyle\frac{1}{2}\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}\geqslant\mathrm{KL}(\mathrm{Ber}(\mathbb{E}_{\theta}[Z])||\mathrm{Ber}(\mathbb{E}_{\theta^{\prime}}[Z]))\;.$
(6)

For any time $n$ we have an eigenvalue decomposition of $\bar{G}_{n}$ as

$\displaystyle\bar{G}_{n}=\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}\;,$ (7)

where
$\lambda_{1}\geqslant\lambda_{2}\geqslant\cdots,\geqslant\lambda_{d}\triangleq\lambda_{min}(\bar{G}_{n})$.
From the regret property we have, for all $M$, such that for any bandit
parameter $\theta$ satisfying $\left\lVert\theta\right\rVert\leqslant 2M$,
there exists a constant $c>0$ such that expected regret
$\mathbb{E}\left[{R_{n}(\theta)}\right]\leqslant c\sqrt{n}$ for any $n$.
Without loss of generality let us fix the bandit parameter $\theta=e_{1}$
(Otherwise we can always rename our coordinate system s.t. in the new system
$\theta=e_{1}$) and $\theta^{\prime}=\theta+\alpha u_{d}$ for some $\alpha$ to
be decided later. This gives,

$\displaystyle\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}=\alpha^{2}\lambda_{d}\;.$
(8)

#####  $\varepsilon$-neighbourhood optimal arms

We shall define $\mathrm{OPT}_{\varepsilon}(\theta)$ as the set of
$\varepsilon-$ suboptimal arms with respect to $\theta$

$\displaystyle\mathrm{OPT}_{\varepsilon}(\theta)\triangleq\\{x\in\mathcal{X}\mid
x^{T}\theta\geqslant\sup_{x}x^{T}\theta-\varepsilon\\}$

We shall with abuse of notation denote
$\mathrm{OPT}_{0}(\theta)=\mathrm{OPT}(\theta)=e_{1}$. Let us also define
$\mathrm{N}_{\varepsilon,n}(\theta)$ to be the number of times in time $n$
that an arm in $\mathrm{OPT}_{\varepsilon}(\theta)$ has been played.

$\displaystyle\mathrm{N}_{\varepsilon,n}(\theta)\triangleq\sum_{s=1}^{n}\mathrm{1}\\{A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)\\}.$

Under the hypothesis that for any bandit parameter $\theta$ satisfying
$\left\lVert\theta\right\rVert\leqslant 2$, there exists a constant $c>0$ such
that $\mathbb{E}R_{n}(\theta)\leqslant c\sqrt{n}$, we have

$\displaystyle
c\sqrt{n}\geqslant\mathbb{E}R_{n}(\theta)\geqslant\mathbb{E}[\sum_{s=1}^{n}\mathrm{1}\\{A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)\\}(\max_{x}x^{T}\theta-
A_{s}^{T}\theta)]\newline
\geqslant\varepsilon(\mathbb{E}[n-\mathrm{N}_{\varepsilon,n}(\theta)])\;.$

Rearranging, we get
$\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]\geqslant
n-\frac{c\sqrt{n}}{\varepsilon}$.

##### Showing that $u_{d}$ is approximately perpendicular to
$\mathrm{OPT}(\theta)$.

Let $v\equiv\mathrm{OPT}(\theta)$. Then, by definition $v=\theta=e_{1}$. Let
us decompose $\bar{G}_{n}$ into $nvv^{\top}$, the unperturbed component, $A$,
and $\bar{G}_{n}-nvv^{\top}$ the perturbation, $H$, as per our notation of the
perturbation lemmas Davis-Kahan(see Lemma 12.3) and Weyl’s lemma (see Lemma
12.4).

$\displaystyle\bar{G}_{n}=\underbrace{nvv^{\top}}_{A}+\underbrace{\bar{G}_{n}-nvv^{\top}}_{H,\text{"perturbation"}}$
(9)

Note that both the unperturbed matrix $A$, the perturbation matrix $H$ are
hermitian. Thus we can use Weyl’s Lemma (Lemma 12.4). This gives us for all
$i=2,3,\cdots,d$

$\lambda_{i}(\bar{G}_{n})\leqslant\underbrace{\lambda_{i}(A)}_{=0}+\lambda_{\max}(H),$
(10)

where we have used $\lambda_{i}(e_{1}e_{1}^{\top})=0$ for all
$i=2,3,\cdots,d$. Now note from the definition of the perturbation matrix $H$
and our notation for the spectral norm

$\displaystyle\lambda_{\max}(H)=\|\bar{G}_{n}-nvv^{\top}\|\newline
=\left\lVert\mathbb{E}\left[{\sum_{s=1}^{n}A_{s}A_{s}^{\top}-vv^{\top}}\right]\right\rVert,$

where in the last equation we have expanded the definition of $\bar{G}_{n}$.
We now decompose the last sum into two parts, all arms, $A_{s}$ which belong
in the group $\mathrm{OPT}_{\varepsilon}(\theta)$ and those that do not. We
are doing this because we shall see that all arms that belong in the group of
$\mathrm{OPT}_{\varepsilon}(\theta)$ will have norm $\|A_{s}-v\|$ small than
those which do not. We get

$\lambda_{max}(H)=\left\lVert\mathbb{E}\left[{\sum_{s:A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)}(A_{s}A_{s}^{\top}-vv^{\top})+\sum_{s:A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)}(A_{s}A_{s}^{\top}-vv^{\top})}\right]\right\rVert.$
(11)

Now, by interchanging norm and expectation and using triangle inequality for
norms we have that

$\lambda_{max}(H)\leqslant\sum_{s:A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)}\mathbb{E}\left[{\left\lVert
A_{s}A_{s}^{\top}-vv^{\top}\right\rVert}\right]+\sum_{s:A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)}\mathbb{E}\left[{\left\lVert(A_{s}A_{s}^{\top}-vv^{\top})\right\rVert}\right]\;.$
(12)

Thus, we see that we need to control the norm of $A_{s}A_{s}^{\top}-vv^{\top}$
for two separate cases. Before we do that, let us first rearrange
$A_{s}A_{s}^{\top}-vv^{\top}$ to get

$\displaystyle\|A_{s}A_{s}^{\top}-vv^{\top}\|=\|(A_{s}-v)A_{s}^{\top}+v(A_{s}-v)^{\top}\|\leqslant\|A_{s}-v\|(\|A_{s}\|+\|v\|)\leqslant
2\|A_{s}-v\|$ (13)

where in the last equation we have used the fact that both $A_{s}$ and $v$
belongs to $\mathcal{S}^{d-1}$. Note that here we need to have kept
$\mathcal{S}^{d-1}$ and a generic upper bound on the arm set $\mathcal{X}$
would have sufficed. Thus, we need to control $\|A_{s}-v\|$ in the two cases.
When $A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)$ we can use a generic
upper bound on the bounded property of the Action Space to get
$\|A_{s}-v\|\leqslant 2$. Now, let us consider the case when
$A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)$. Then by definition of
$\mathrm{OPT}_{\varepsilon}(\theta)$ we have

$\displaystyle A_{s}^{\top}\theta\geqslant
v^{\top}\theta-\varepsilon=1-\varepsilon$ (14)

where we have again used that $v=e_{1}=\theta$ because of the action-space
$\mathcal{X}$. Note here again that for a general geometry $v^{\top}\theta$
would still be some constant depending upon the geometry of the action-space.

Now let us consider the 2 orthogonal components of such an $A_{s}$,
$A_{s}-(A_{s}^{\top}v)v$ and $(A_{s}^{\top}v)v$. We have by Pythagorean
Theorem

$\displaystyle\|A_{s}\|^{2}=\|(A_{s}^{\top}v)v\|^{2}+\|A_{s}-(A_{s}^{\top}v)v\|^{2}.$

Therefore again utilizing that $\|\|A_{s}\|^{2}=1$ (although a generic bound
would have sufficed) and rearranging

$\displaystyle\|A_{s}-(A_{s}^{\top}v)v\|^{2}=1-\|(A_{s}^{\top}v)v\|^{2}.$

Now we utilize the fact that in the spherical geometry we can exactly compute
$A_{s}^{\top}v=A_{s}^{\top}\theta\geqslant 1-\varepsilon$, (see Equation
(14)), to get

$\displaystyle 1-\|(A_{s}^{\top}v)v\|^{2}\leqslant
1-(1-\varepsilon)^{2}=(2\varepsilon-\varepsilon^{2})\;,$

where we have used homogenity of norms in the inequality. For other geometry
we need to use the geometry of the set $\mathrm{OPT}_{\varepsilon}(\theta)$ to
estimate $A_{s}^{\top}v$.

Now, we can conclude that for any
$A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)$, by virtue of orthogonality
between $A_{s}-(A_{s}^{\top}v)v$ and $v-(A_{s}^{\top}v)v$, we have using the
Pythagorean theorem

$\displaystyle\|A_{s}-v\|^{2}=\|A_{s}-(A_{s}^{\top}v)v\|^{2}+\|v-(A_{s}^{\top}v)v\|^{2}.$

Now using the fact that
$v-(A_{s}^{\top}v)v=(1-A_{s}^{\top}v)v\leqslant\varepsilon v$, we get

$\displaystyle\|A_{s}-(A_{s}^{\top}v)v\|^{2}+\|v-(A_{s}^{\top}v)v\|^{2}\leqslant(2\varepsilon-\varepsilon^{2})+\varepsilon^{2}=2\varepsilon\;.$

Thus we have for any $A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)$ the
following estimate

$\|A_{s}-v\|\leqslant\sqrt{2\varepsilon}~{}.$ (15)

Note that by changing the geometry we will have different constants but still
of the same $\sqrt{\varepsilon}$ order.

Thus we have from Equations (12), (13) and (15) along with the trivial bound
of $\|A_{s}-v\|\leqslant 2$, the following estimate on the spectral norm of
the perturbation matrix $H$ :

$\displaystyle\lambda_{max}(H)\leqslant
2\sqrt{2\varepsilon}\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]+4\mathbb{E}_{\theta}[n-\mathrm{N}_{\varepsilon,n}(\theta)]\;,$

where we have used the definitions of
$\mathrm{N}_{\varepsilon,n}(\theta)=\sum_{s=1}^{n}\mathrm{1}\\{A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)\\}$
and
$n-\mathrm{N}_{\varepsilon,n}(\theta)=\sum_{s=1}^{n}\mathrm{1}\\{A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)\\}$.
Then using a crude upper bound of $n$ on
$\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]$ and using the
expression for the lower bound of
$\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]$ to get an upper
bound on $\mathbb{E}_{\theta}[n-\mathrm{N}_{\varepsilon,n}(\theta)]$, we get

$\displaystyle\leqslant
2\sqrt{2\varepsilon}n+4\frac{c\sqrt{n}}{\varepsilon}\;.$ (16)

Till now $\varepsilon$ was a free parameter. We choose
$\varepsilon=\frac{c}{0.01\sqrt{n}}$ such that,
$\frac{c\sqrt{n}}{\varepsilon}=0.01n$. This gives from Equation (16)

$\displaystyle\lambda_{max}(H)\leqslant
2\sqrt{2}\sqrt{\frac{c}{0.01}}n^{\frac{3}{4}}+4*0.01*n~{}.$ (17)

Thus for a large but finite $n$, depending upon $c$ and also on the geometry
of the arm set, we have

$\lambda_{max}(H)\leqslant 0.1n~{}.$ (18)

Hence, from Equation (10), we have

$\lambda_{i}(\bar{G}_{n})\leqslant 0.1n\text{ }\forall i=2,3,\ldots,d\;.$ (19)

Thus we have from Equation (18) the norm of the perturbation matrix; from
equation (7) we have the eigen decompostion of $\bar{G}_{n}$; we also have the
eigen-decomposition of $nvv^{\top}$ as
$nvv^{\top}=nvv^{\top}+\sum_{i=2}^{d}0\tilde{u}_{i}\tilde{u}_{i}^{\top}$ and
from equation (19) we have the eigen-gap
$\delta=\lambda_{1}(nvv^{\top})-\lambda_{2}(\bar{G}_{n})\geqslant
n-0.1n=0.9n$.

Therefore the Davis Kahan Theorem, (see Theorem 12.3) gives us

$\|v^{T}\begin{bmatrix}u_{2}&u_{3}&\cdots&u_{d}\\\
\end{bmatrix}\|\leqslant\frac{\|H\|}{n-0.1n}\leqslant\frac{0.1n}{0.9n}=\frac{1}{9}\;,$

which implies

$\displaystyle\max_{i\in 2,\ldots,d}v^{T}u_{i}\leqslant\frac{1}{9},$

which we interpret as the eigenvector corresponding to
$\lambda_{min}(\bar{G}_{n})$ is sufficiently orthogonal to
$\mathrm{OPT}(\theta)$ when the optimal set decreases as roughly
$\frac{1}{\sqrt{n}}$.

##### The amount $\alpha$ to perturb $\theta$ to $\theta^{\prime}$

In this penultimate section, we will try to find $\alpha$ such that the
$\varepsilon$-optimal arms for $\theta$ and $\theta^{\prime}$ are necessarily
disjoint.

Formally we would want to find the smallest $\alpha$ s.t.

$\mathrm{OPT}_{\varepsilon}(\theta)\cap\mathrm{OPT}_{\varepsilon}(\theta+\alpha
u_{d})=\emptyset$

subject to the constraint $|\langle
u_{d},\mathrm{OPT}(\theta)\rangle|\leqslant\frac{1}{9}$

######  Lemma 7.2.

There exists a constant $\beta$ such that
$\mathrm{OPT}_{\varepsilon}(\theta)\cap\mathrm{OPT}_{\varepsilon}(\theta+\frac{\beta}{n^{1/4}}u_{d})=\emptyset$
with $\varepsilon$ defined as above with $u_{d}$ is subject to the constraint
$|\langle u_{d},\mathrm{OPT}(\theta)\rangle|\leqslant\frac{1}{9}$.

###### Proof.

We will be focusing on $3$ points $\theta$, $\theta+\alpha u_{d}$ and the
centre of the sphere. Since a plane can be drawn passing through any 3 non-
collinear points we will be working in terms of the triangle formed by these
three points. We will refer to Figure 4 for the proof.

Let us first note that for any given arbitrary $\varepsilon$, the
$\mathrm{OPT}_{\varepsilon}(\theta)$ subtends an angle $\psi$ about the
centre. (See left image of Figure 4). In order to ensure that
$\mathrm{OPT}_{\varepsilon}(\theta)$ and
$\mathrm{OPT}_{\varepsilon}(\theta+\alpha u_{d})$ are disjoint, we need to
ensure that angular displacement of $\theta^{\prime}$ is at least twice that
is $2\psi$ from $\theta$ (see left image of Figure 4) and thus choose the step
size $\alpha$ based on the angular displacement $\psi$.

$\displaystyle
OPT_{\varepsilon}(\theta^{\prime})$$\displaystyle\theta^{\prime}$$\displaystyle\theta$$\displaystyle\alpha
u_{d}$$\displaystyle
OPT_{\varepsilon}(\theta)$$\displaystyle\mathcal{X}=\mathcal{S}{{}^{d-1}}$$\displaystyle\angle\psi$
(a)

$\displaystyle\alpha
u_{d}$$\displaystyle\mathrm{OPT}(\theta)=e_{1}$$\displaystyle\mathrm{OPT}(\theta^{\prime})$$\displaystyle\angle
2\psi$$\displaystyle\angle\delta$$\displaystyle\angle\left(\frac{\pi}{2}-\delta-2\psi\right)$
(b)

Figure 4: Proof of Lemma 7.2

Note that even in continuous action-sets with arbitrary geometry, if the
geometry is smooth, the idea still remains the same. Thus we have,

$\displaystyle\psi=\cos^{-1}(1-\varepsilon)$ (20)

(see the left image of Figure 4 for better clarity $\langle
x,\theta\rangle=\cos\psi\geqslant 1-\varepsilon$ for any
$x\in\mathrm{OPT}_{\varepsilon}(\theta)$ ) and hence the displacement must be
at least $2\cos^{-1}(1-\varepsilon)$.

Now from the constraint condition that $v^{\top}u_{d}\leqslant 1/9$, we refer
to the right hand side of figure 4, where $\delta$ is the complementary angle
between by $v$ (and hence $\theta$) and $u_{d}$. Thus

$\displaystyle\sin\delta=\cos(\pi/2-\delta)=\langle v,u_{d}\rangle\leqslant
1/9$ (21)

(see the right image of Figure 4) and hence
$\cos\delta\geqslant\sqrt{\frac{80}{81}}$. Therefore applying the law of sines
we have (see the right image of Figure 4 )

$\displaystyle\frac{\alpha}{\sin
2\psi}=\frac{1}{\sin(\pi/2-\delta-2\psi)}\implies\alpha=\frac{\sin(2\psi)}{\sin(\pi/2-\delta-2\psi)}=\frac{\sin(2\psi)}{\cos(\delta+2\psi)}$
(22)

where $\alpha$ is the step-size to be determined.

Now note from left image of Figure 4 that we have (see Equation (20))

$\displaystyle\cos\psi=1-\varepsilon\implies\sin\psi=\sqrt{2\varepsilon-\varepsilon^{2}}\implies\cos^{-1}(1-\varepsilon)=\sin^{-1}(\sqrt{2\varepsilon-\varepsilon^{2}})\approx\sqrt{2\varepsilon-\varepsilon^{2}}\approx\sqrt{2\varepsilon}$

for small angles and therefore $\sin 2\psi\approx
2\psi=2\cos^{-1}(1-\varepsilon)\approx 2\sqrt{2\varepsilon}$ and
$\cos(\delta+2\psi)\approx\cos\delta\geqslant\sqrt{\frac{80}{81}}$ (see
Equation (21)). Therefore from Equation (22) we have

$\displaystyle\alpha\lessapprox\frac{2\sqrt{2\varepsilon}}{\sqrt{\frac{80}{81}}}=c_{2}\sqrt{\varepsilon}=\beta\frac{1}{n^{\frac{1}{4}}},$

and hence the claim is proved. ∎

##### Finishing the proof

Let us now define the random variable $Z$ in Equation (6) as the fraction of
times an arm in the $\varepsilon$-optimal set has been played, that is
$Z\triangleq\frac{\mathrm{N}_{\varepsilon,n}(\theta)}{n}$. Then , we have

$\displaystyle\mathbb{E}_{\theta}[Z]\geqslant\frac{n-\frac{c\sqrt{n}}{\varepsilon}}{n}=\frac{0.99n}{n}=0.99,$

where we have used the definition of $Z$, the expression for the lower bound
on $\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]$ and the value of
$\varepsilon$. On the other hand, because of the disjoint
$\varepsilon$-optimal sets of $\theta$ and $\theta^{\prime}$ by construction,
we have

$\displaystyle\mathbb{E}_{\theta^{\prime}}[Z]=\frac{\mathbb{E}_{\theta^{\prime}}[\mathrm{N}_{\varepsilon,n}(\theta)]}{n}=\frac{n-\mathbb{E}_{\theta^{\prime}}[\mathrm{N}_{\varepsilon,n}(\theta^{\prime})]}{n}\leqslant\frac{\frac{c\sqrt{n}}{\varepsilon}}{n}=\frac{0.01n}{n}=0.01$

where we have used the regret property of the algorithm of being at most
$c\sqrt{n}$ for any bandit parameter satisfying
$\left\lVert\theta\right\rVert\leqslant 2$ by having $n$ large enough such
that $\left\lVert\theta^{\prime}\right\rVert=\left\lVert\theta+\alpha
u_{d}\right\rVert\leqslant 2$ . Thus using Equations (6) and (8) and using the
estimates of $\mathbb{E}_{\theta^{\prime}}[Z]$ and $\mathbb{E}_{\theta}[Z]$ we
have

$\displaystyle\frac{\alpha^{2}}{2}\lambda_{d}\geqslant\mathrm{KL}(\mathrm{Ber}(\mathbb{E}_{\theta}[Z])||\mathrm{Ber}(\mathbb{E}_{\theta^{\prime}}[Z]))\geqslant
2(\mathbb{E}_{\theta}[Z]-\mathbb{E}_{\theta^{\prime}}[Z])^{2}\geqslant
2(0.99-0.01)^{2}=c_{4}$

where for the second inequality we have used Pinsker’s Inequality. Finally
using Lemma 7.2 to find $\alpha$ which also guarantees our estimates of
$\mathbb{E}_{\theta^{\prime}}[Z]$ and $\mathbb{E}_{\theta}[Z]$, we have

$\displaystyle\lambda_{d}(\bar{G}_{n}))\geqslant
2c_{4}\frac{1}{\alpha^{2}}=c_{5}\frac{1}{(\frac{\beta}{n^{\frac{1}{4}}})^{2}}=c_{6}\sqrt{n}$

This completes the proof with the positive constant $c_{6}$ being redefined as
$\gamma$. ∎

######  Remark 7.3 (Dependence on dimension $d$).

Though our result does not explicitly depend on the dimension $d$, it can
depend on it through the regret upper bound of underlying linear bandit
algorithm. Hypothetically, if there exists an algorithm which does not depend
upon $d$, our result shows that the growth of minimum eigenvalue of design
matrix is also independent of $d$. That being said, the dimensional dependency
enters through the constant $c$ and is different for different algorithms. For
example, for the OFUL algorithm (Abbasi-yadkori et al., 2011), we have
$c=O(d)$. Similarly, for Thompson Sampling algorithm (Abeille and Lazaric,
2017), we get $c=O(d^{3/2})$.

We can show that $n_{0}=\Omega(c^{2})$ and $\gamma=\Omega(\frac{1}{c})$. Let
us compute this for the spherical action set. From Equation (17), we have

$\lambda_{\max}(H)\leqslant
2\sqrt{2}\sqrt{\frac{c}{0.01}}n^{\frac{3}{4}}+4\times 0.01\times n.$

Now, for a large but finite $n$, we have the right hand side to be less than
$0.1n$. This finite $n$ is the $n_{0}$ as defined in Thm 2.3. An easy
calculation shows that $n_{0}=\Omega(c^{2})$. Similarly, $\gamma$ can be
computed as follows. Note that
$\lambda_{d}\geqslant\frac{3.8416}{\alpha^{2}}=\frac{3.8416}{\beta^{2}}\sqrt{n}$,
where $\beta=\frac{2\sqrt{\frac{2c}{0.01}}}{\sqrt{\frac{80}{81}}}$and
$\gamma=\frac{3.8416}{\beta^{2}}$. This implies $\gamma=\Omega(\frac{1}{c})$.

###  7.2 Ellipsoidal Action-Set

######  Theorem 7.4.

Let the set of arms be
$\mathcal{X}=:=\left\\{x\in\mathbb{R}^{d}:x^{\top}A^{-1}x=1\right\\}$, the
surface of the $d$ dimensional ellipsoid ($A$ is symmetric and positive
definite). Let
$\bar{G}_{n}=\mathbb{E}_{\theta}\left[\sum_{s=1}^{n}A_{s}A_{s}^{\top}\right]$,
where $\theta$ is a bandit parameter and $A_{s}$ are arms in $\mathcal{X}$
drawn according to some bandit algorithm.

For any bandit algorithm which suffers expected regret, $R_{n}(\theta)$, at
most $O(\sqrt{n})$,

$\displaystyle\lambda_{min}(\bar{G}_{n})=\Omega(\sqrt{n})\;.$

That is there exists constants $\gamma>0$ and a finite time $n_{0}$ such that
for all $n\geqslant n_{0}$, we have
$\lambda_{min}(\bar{G}_{n})\geqslant\gamma\sqrt{n}$.

######  Remark 7.5.

The constants $n_{0}$ and $\gamma$ depend upon the algorithm constants hidden
by $O()$, the condition number of $A$ and the size of the bandit parameter
$\theta$.

###### Proof.

Let $\mathcal{X}=\\{x\in\mathbb{R}^{d}:x^{\top}A^{-1}x=1\\}$ be an ellipsoidal
action set where $A$ is symmetric positive definite and $\theta$ be the bandit
parameter.

Let us make a change of variable $y=A^{-1/2}x$ for all $x\in\mathcal{X}$. Thus
we have $\left\lVert y\right\rVert^{2}=1$. We define this new transformed
action space $\mathcal{Y}$ and note that $\mathcal{Y}$ is the unit sphere.

Before we proceed further we make the following observations :

$\displaystyle\mathrm{OPT}_{\mathcal{X}}(\theta)=\arg\max_{x\in\mathcal{X}}\langle
x,\theta\rangle=\arg\max_{x\in\mathcal{X}}\langle
A^{-1/2}x,A^{1/2}\theta\rangle$ (23) $\displaystyle=A^{1/2}\arg\max_{y\in
A^{-1/2}\mathcal{X}}\langle
y,A^{1/2}\theta\rangle=A^{1/2}\arg\max_{y\in\mathcal{Y}}\langle
y,A^{1/2}\theta\rangle=A^{1/2}\mathrm{OPT}_{\mathcal{Y}}(A^{1/2}\theta).$

Similarly we have

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=A^{1/2}\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)$
(24)

Thus let us consider the following linear bandit problem where the action set
is $\mathcal{Y}=\mathcal{S}^{d-1}$, and the bandit parameter is
$A^{1/2}\theta$. Let the actions sampled be $\\{y_{i}\\}_{i=1}^{n}$ by any
bandit algorithm with regret at most $O(\sqrt{n})$. Let the design matrix be
$V_{n}=\mathbb{E}\left[{\sum_{i=1}^{n}y_{i}y_{i}^{\top}}\right]$, and the
corresponding eigenvector decomposition be
$\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}$.

From the previous section (see Lemma 7.2) we know,

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\bigg{(}\frac{A^{1/2}\theta}{\left\lVert
A^{1/2}\theta\right\rVert}\bigg{)}\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\bigg{(}\frac{A^{1/2}\theta}{\left\lVert
A^{1/2}\theta\right\rVert}+\alpha u_{d}\bigg{)}=\emptyset\;,$ (25)

for $\alpha=O(1/n^{1/4})$. Thus multiplying the two disconnected sets by
$\left\lVert A^{1/2}\theta\right\rVert$ is still going to keep them
disconnected and hence,

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\Big{(}A^{1/2}\theta+\alpha\left\lVert
A^{1/2}\theta\right\rVert u_{d}\Big{)}=\emptyset.$ (26)

This implies,

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\Big{(}A^{1/2}(\theta+\alpha\left\lVert
A^{1/2}\theta\right\rVert A^{-1/2}u_{d})\Big{)}=\emptyset$ (27)

and thus from the change of variable relation,(See equation (24)), we have

$\displaystyle A^{-1/2}\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\cap
A^{-1/2}\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta+\alpha\left\lVert
A^{1/2}\theta\right\rVert A^{-1/2}u_{d})=\emptyset.$ (28)

Now because continuous functions preserve disjoint sets, we have

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta+\alpha\left\lVert
A^{1/2}\theta\right\rVert A^{-1/2}u_{d})=\emptyset.$ (29)

Now let us define the design matrix $\bar{G}_{n}$ for the action set
$\mathcal{X}$ as
$\bar{G}_{n}=\mathbb{E}\left[{\sum_{i=1}^{n}x_{i}x_{i}^{\top}}\right]$. With
the change of variables we have

$\displaystyle\bar{G}_{n}=\mathbb{E}\left[{\sum_{i=1}^{n}x_{i}x_{i}^{\top}}\right]=A^{1/2}\mathbb{E}\left[{\sum_{i=1}^{n}y_{i}y_{i}^{\top}}\right]A^{1/2}=A^{1/2}\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}A^{1/2}\;,$
(30)

where $u_{i}$ are the eigen-vectors as defined for the action space
$\mathcal{Y}$. Now defining the perturbed
$\theta^{\prime}=\theta+\alpha\left\lVert A^{1/2}\theta\right\rVert
A^{-1/2}u_{d}$, we have

$\displaystyle\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}=\alpha^{2}\left\lVert
A^{1/2}\theta\right\rVert^{2}u_{d}^{\top}A^{-1/2}\Big{(}A^{1/2}\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{T}A^{1/2}\Big{)}A^{-1/2}u_{d}=\alpha^{2}\left\lVert
A^{1/2}\theta\right\rVert^{2}\lambda_{d}$ (31)

Now, from the methodology discussed in the previous section using the Kauffman
measure change inequality 12.1( see the paragraph 7.1), we have

$\displaystyle\lambda_{d}\geqslant\frac{c}{\alpha^{2}\left\lVert
A^{1/2}\theta\right\rVert^{2}}=\frac{c\sqrt{n}}{\left\lVert
A^{1/2}\theta\right\rVert^{2}}\;,$ (32)

for some positive $c$. To conclude the proof we need to find a relation
between the eigenvalues lowest eigenvalue $\mu_{d}$ of $\bar{G}_{n}$ and the
lowest eigenvalue $\lambda_{d}$ of $V_{n}$. For this note, from equation (30)

$\displaystyle\bar{G}_{n}=A^{1/2}V_{n}A^{1/2}=A^{1/2}U\Lambda
U^{\top}A^{1/2}.$ (33)

From spectral theory we have

$\displaystyle\mu_{d}(\bar{G}_{n})=\frac{1}{\left\lVert\bar{G}_{n}^{-1}\right\rVert}.$
(34)

Now from equation (33), and definition of matrix norms and orthogonality of
eigenctors $U$, we have

$\displaystyle\left\lVert G_{n}^{-1}\right\rVert\leqslant\left\lVert
A^{-1/2}\right\rVert^{2}\left\lVert\Lambda^{-1}\right\rVert,$ (35)

and therefore,

$\displaystyle\mu_{d}(\bar{G}_{n})\geqslant\frac{1}{\left\lVert
A^{-1/2}\right\rVert^{2}\left\lVert\Lambda^{-1}\right\rVert}=\frac{\lambda_{d}}{\left\lVert
A^{-1/2}\right\rVert^{2}}\geqslant\frac{c\sqrt{n}}{\left\lVert
A^{-1/2}\right\rVert^{2}\left\lVert
A^{1/2}\theta\right\rVert^{2}}\geqslant\frac{c\sqrt{n}}{\left\lVert
A^{-1/2}\right\rVert^{2}\left\lVert
A^{1/2}\right\rVert^{2}\left\lVert\theta\right\rVert^{2}}.$ (36)

This concludes the proof. ∎

In the next subsection we illustrate that the same proof for ellipsoids can be
done through first principles.

####  7.2.1 Ellipsoidal Sets : Proof by first principles

In this section we highlight the main ideas of the proof and leave the gaps as
an exercise. The proof follows verbatim from the proof for the spherical case
(see subsection 7.1).

######  Remark 7.6.

We present this alternative proof to highlight the main takeaway of the proof
technique, namely to construct an alternative bandit parameter
$\theta^{\prime}$, for which the actions played by the algorithm would
significantly differ from the original bandit parameter and yet for both
parameters, the algorithm plays optimally.

######  Remark 7.7.

The idea of this proof is also to highlight that what really is needed is
information about neighbourhood of the optimal arm, and the global action
space does not influence the exploration strategy of good regret algorithms.
This would be useful for the proof of the LCH surfaces as given in the next
Section 7.3.

###### Proof.

We fix a $\theta$ and start with the Garivier-Kauffman inequality

$\displaystyle\frac{1}{2}\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}\geqslant\mathrm{KL}(\mathrm{Ber}(\mathbb{E}_{\theta}[Z])||\mathrm{Ber}(\mathbb{E}_{\theta^{\prime}}[Z]))\;.$
(37)

and do an eigen-decomposition of $\bar{G}_{n}$ as

$\displaystyle\bar{G}_{n}=\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}\;,$ (38)

where $\lambda_{1},\cdots,\lambda_{d}$ and $u_{1},\cdots,u_{d}$ have the usual
meaning. The crux of the proof remains that we design the perturbed
$\theta^{\prime}$ as before, namely as $\theta^{\prime}=\theta+\alpha u_{d}$
for some $\alpha$ to be computed such that
$\mathrm{OPT}_{\varepsilon}(\theta)$ and
$\mathrm{OPT}_{\varepsilon}(\theta^{\prime})$ are disjoint. With this choice
of $\theta^{\prime}$ we have from the measure change inequality as,

$\displaystyle\|\theta-\theta^{\prime}\|^{2}_{\bar{G}_{n}}=\alpha^{2}\lambda_{d}\;.$
(39)

As before, we have from the definitions of
$\mathrm{OPT}_{\varepsilon}(\theta)$ and $\mathrm{N}_{\varepsilon,n}(\theta)$,

$\displaystyle\mathbb{E}_{\theta^{\prime}}[\mathrm{N}_{\varepsilon,n}(\theta^{\prime})]\geqslant
n-\frac{c\sqrt{n}}{\varepsilon}\;,$ (40)

for all $\theta^{\prime}$ satisfying
$\left\lVert\theta^{\prime}\right\rVert\leqslant
2\left\lVert\theta\right\rVert$ such that
$\mathbb{E}\left[{R_{n}(\theta^{\prime})}\right]\leqslant c\sqrt{n}$, for some
$c>0$. For ellipse we have the
$\mathrm{OPT}(\theta)=\frac{A\theta}{\left\lVert\theta\right\rVert_{A}}$,
which as before we denote as $v$.

##### Showing that $v$ and $u_{d}$ are roughly orthogonal to each other

As before we decompose $\bar{G}_{n}$ as

$\displaystyle\bar{G}_{n}=nvv^{\top}+\bar{G}_{n}-nvv^{\top}$ (41)

and note from Weyl’s Lemma and definition of $\lambda_{i}$, that

$\displaystyle\lambda_{i}(\bar{G}_{n})\leqslant\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert,$
(42)

for $i\in\\{2,3,\cdots,d\\}$. Now decomposing
$\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert$ into the two sets, one
containing arms belonging to the $\mathrm{OPT}_{\varepsilon}(\theta)$ set and
another where arms do not belong to $\mathrm{OPT}_{\varepsilon}(\theta)$, and
further using a generic upper bound of $\sqrt{\lambda_{\max}(A)}$ for the size
of all arms in $\mathcal{X}$, we have,

$\displaystyle\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert\leqslant\sum_{s:A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)}\sqrt{\lambda_{\max}(A)}\mathbb{E}\left[{\left\lVert
A_{s}-v\right\rVert}\right]+\sum_{s:A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)}\sqrt{\lambda_{\max}(A)}\mathbb{E}\left[{\left\lVert(A_{s}-v)\right\rVert}\right]$
(43)

(See previous section of the spherical set section 7.1 for details of this
decomposition). For $A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)$, we need to
find an upper bound for $\left\lVert A_{s}-v\right\rVert$. Now recall the
change of variable formula (Equations 23 and 24) from the last section, namely

$\displaystyle\mathrm{OPT}_{\mathcal{X}}(\theta)=A^{1/2}\mathrm{OPT}_{\mathcal{Y}}(A^{1/2}\theta)$

and

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=A^{1/2}\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)\;,$

where $\mathcal{X}$ and $\mathcal{Y}$ are the ellipse and unit sphere
respectively.

Thus for $A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$, there
exists a $x\in\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)$, such
that $A_{s}=A^{1/2}x$. Therefore, for any
$A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$

$\displaystyle\left\lVert A_{s}-v\right\rVert=\left\lVert
A^{1/2}x-A^{1/2}\mathrm{OPT}_{\mathcal{Y}}(A^{1/2}\theta)\right\rVert$ (44)

for some $x\in\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)$. Now from
the section on the sphere it follows, that for any
$x\in\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)$, we have

$\displaystyle\left\lVert
x-\mathrm{OPT}_{\mathcal{Y}}(A^{1/2}\theta)\right\rVert\leqslant\sqrt{\frac{2\varepsilon}{\left\lVert
A^{1/2}\theta\right\rVert}}$ (45)

(see the section on the sphere for the full detail 7.1). Therefore for any
$A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ we have

$\displaystyle\left\lVert A_{s}-v\right\rVert\leqslant\left\lVert
A^{1/2}\right\rVert\sqrt{\frac{2\varepsilon}{\left\lVert
A^{1/2}\theta\right\rVert}}\;.$

Thus we have

$\displaystyle\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert\leqslant\sqrt{\lambda_{\max}(A)}\left\lVert
A^{1/2}\right\rVert\sqrt{\frac{2\varepsilon}{\left\lVert
A^{1/2}\theta\right\rVert}}\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]+\lambda_{\max}(A)\mathbb{E}_{\theta}[n-\mathrm{N}_{\varepsilon,n}(\theta)]\;.$

Now using the estimates of
$\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]$ (Equation 40) we
have

$\displaystyle\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert\leqslant\sqrt{\lambda_{\max}(A)}\left\lVert
A^{1/2}\right\rVert\sqrt{\frac{2\varepsilon}{\left\lVert
A^{1/2}\theta\right\rVert}}n+\lambda_{\max}(A)\frac{c\sqrt{n}}{\varepsilon}\;.$
(46)

The rest of the proof remains the same as in the spherical case (see
subsection 7.1), but now $n_{0}$ would depend upon the matrix $A$ as well.

##### To show that the sets $\mathrm{OPT}_{\varepsilon}(\theta)$ and
$\mathrm{OPT}_{\varepsilon}(\theta+O(1/n^{1/4})u_{d})$ are disjoint.

Let us first rewrite what we need to show. Namely we want to find an $\alpha$
such that

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta+\alpha
u_{d})=\emptyset\;.$ (47)

Now using the change of variables (Equations (23) and (24)) this is equivalent
to showing

$\displaystyle
A^{1/2}\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)\cap
A^{1/2}\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}(\theta+\alpha
u_{d}))=\emptyset\;,$ (48)

where $\mathcal{Y}$ is the sphere. By the bijection of $A^{1/2}$, the above is
equivalent to showing

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(A^{1/2}\theta+\alpha
A^{1/2}u_{d})=\emptyset\;.$ (49)

Now we know $\langle v,u_{d}\rangle\approx 0$ where $v$ is the optimal arm for
the ellipsoid (see the previous paragraph). But for the ellipsoid we know
$v=\frac{A\theta}{\left\lVert\theta\right\rVert_{A}}$. Thus
$\langle\frac{A\theta}{\left\lVert\theta\right\rVert_{A}},u_{d}\rangle\approx
0$. This implies $\langle A^{1/2}\theta,A^{1/2}u_{d}\rangle\approx 0$. Thus
now we can use the result for the spherical action set (Lemma 7.2), namely,

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\Big{(}\frac{A^{1/2}\theta}{\left\lVert
A^{1/2}\theta\right\rVert}\Big{)}\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\Big{(}\frac{A^{1/2}\theta}{\left\lVert
A^{1/2}\theta\right\rVert}+\alpha^{\prime}\frac{A^{1/2}u_{d}}{\left\lVert
A^{1/2}u_{d}\right\rVert}\Big{)}=\emptyset$ (50)

where $\alpha^{\prime}=O(\frac{1}{n^{1/4}})$. Thus multiplying by $\left\lVert
A^{1/2}\theta\right\rVert$, we have

$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\Big{(}A^{1/2}\theta\Big{)}\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}\Big{(}A^{1/2}\theta+\alpha^{\prime}\frac{{\left\lVert
A^{1/2}\theta\right\rVert}}{\left\lVert
A^{1/2}u_{d}\right\rVert}A^{1/2}u_{d}\Big{)}=\emptyset\;.$ (51)

Thus the required $\alpha=\alpha^{\prime}\frac{{\left\lVert
A^{1/2}\theta\right\rVert}}{\left\lVert A^{1/2}u_{d}\right\rVert}$.

##### Finishing the proof

The rest of the proof follows as the ones shown in the previous two sections
(paragraph 7.1). By ensuring that for a large enough $n$, such that
$\left\lVert\theta^{\prime}\right\rVert\leqslant
2\left\lVert\theta\right\rVert$, and using the implication of the
dijointedness of the $\varepsilon$-optimal sets for $\theta$ and
$\theta^{\prime}$ in the Garivier-Kauffman inequality, we get

$\displaystyle\lambda_{d}\geqslant\frac{c_{1}}{\alpha^{2}}=\frac{c_{1}\sqrt{n}{\left\lVert
A^{1/2}u_{d}\right\rVert}^{2}}{\left\lVert
A^{1/2}\theta\right\rVert^{2}}\geqslant\frac{c_{1}\sqrt{n}\lambda_{\min}(A)}{\left\lVert
A^{1/2}\theta\right\rVert^{2}}=\frac{c_{1}\sqrt{n}}{\left\lVert
A^{-1/2}\right\rVert^{2}\left\lVert A^{1/2}\theta\right\rVert^{2}}\;,$ (52)

for some positive constant $c_{1}$. This completes the proof. ∎

##### Non centred ellipsoids.

Even though we are considering centred ellipsoids, our proofs readily extend
to non-centred ellipsoids. Consider
$\mathcal{X}=\\{x:(x-a)^{\top}M^{-1}(x-a)\\}$ a non-centred ellipsoid. Let
$y=x-a$, Then for all such $x$ in $\mathcal{X}$, $y$ satisfies the equation of
the following centred ellipsoid $\mathcal{Y}=\\{y:y^{\top}M^{-1}y=1\\}$. Now
with the usual definitions of $\mathrm{OPT}_{\mathcal{X}}(\theta)$,
$\mathrm{OPT}_{\mathcal{Y}}(\theta)$,
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ and
$\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$, observe that the following
relations hold true

$\displaystyle\mathrm{OPT}_{\mathcal{X}}(\theta)=\mathrm{OPT}_{\mathcal{Y}}(\theta)+a$
$\displaystyle\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)+a\;.$

With these relations and using arguments similar to this section (subsection
7.2), we have our result readily.

###  7.3 Locally Constant Hessian (LCH) Action Spaces

In this section we prove Theorem 2.2. We begin by recalling our definition of
LCH surfaces (Definition 2.1) and Theorem 2.2:

######  Definition 7.8 (Locally Constant Hessian (LCH) surface).

Consider the action space defined by
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:f(x)=c\\}$, where
$f:\mathbb{R}^{d}\to\mathbb{R}$ is a $C^{2}$ function (i.e., all second-order
partial derivatives of $f$ exist and are continuous) and $c\in\mathbb{R}$. Let
$\theta\in\mathbb{R}^{d}$. $\mathcal{X}$ is said to be a LCH surface w.r.t.
$\theta$ if: (i) there is a unique reward-optimal arm with respect to $\theta$
(denoted by
$\mathrm{OPT}_{\mathcal{X}}(\theta)=\arg\max_{x\in\mathcal{X}}\langle
x,\theta\rangle$), and (ii) there is an open neighborhood
$U\subset\mathbb{R}^{d}$ of $\mathrm{OPT}_{\mathcal{X}}(\theta)$ over which
the Hessian of $f$ is constant and positive-definite.

We are now ready to prove our main result.

######  Theorem 7.9.

Let the action-space $\mathcal{X}$ be a Locally Constant Hessian(LCH) surface
in $\mathbb{R}^{d-1}$ w.r.t. a bandit parameter $\theta$. Let
$\bar{G}_{n}=\mathbb{E}_{\theta}\left[\sum_{s=1}^{n}A_{s}A_{s}^{\top}\right]$,
where $A_{s}$ are arms in $\mathcal{X}$ drawn according to some bandit
algorithm. For any bandit algorithm which suffers expected regret at most
$O(\sqrt{n})$,

$\displaystyle\lambda_{\min}(\bar{G}_{n})=\Omega(\sqrt{n})\;.$

That is, there exists an $n_{0}$ and a constant $\gamma>0$, such that for all
$n\geqslant n_{0}$, $\lambda_{\min}(\bar{G}_{n})\geqslant\gamma\sqrt{n}$.

######  Remark 7.10.

The constant $\gamma$ depends upon the condition number of the Hessian, the
algorithmic constants hidden by $O()$, and the size of the bandit parameter
$\theta$. The constant $n_{0}$ depends on the algorithmic constants hidden by
$O()$, the size of the neighbourbood over which the Hessian is constant, the
size of the action domain $\left\lVert\mathcal{X}\right\rVert$, the singular
value of the Hessian and the size of the bandit parameter $\theta$.

######  Remark 7.11.

The proof essentially follows the proof of Section 7.2.1. We present it here
for the sake of completeness.

###### Proof.

Consider, the action space given by the curve
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:f(x)=1\\}$. Assume that $\mathcal{X}$ is
upper bounded in norm by a constant represented as $\lambda(\mathcal{X})$. Let
us define $\mathrm{OPT}_{\mathcal{X}}(\theta)$ and
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ as before for a bandit
parameter $\theta$. Let $U$ be an open-neighbourhood of
$\mathrm{OPT}_{\mathcal{X}}(\theta)$, over which the Hessian of $f$,
$\nabla^{2}f$, is a constant $H$, and is positive-definite.

We shall show that in this setup the conclusion of
$\lambda_{\min}(\bar{G}_{n})$ holds true.

As before, we define
$\bar{G}_{n}=\mathbb{E}\left[{\sum_{s=1}^{n}A_{s}A_{s}^{\top}}\right]$ where
$A_{s}\in\mathcal{X}$ and we have a eigenvalue decomposition of
$\sum_{i=1}^{d}\lambda_{i}u_{i}u_{i}^{\top}$.

We make a Taylor Series approximation of $f$ about
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ (denoted here as $x^{*}$ for notational
ease) in the neighbourhood of $U$.

$\displaystyle f(x)=f(x^{*})+(x-x^{*})^{\top}\nabla
f(x^{*})+(x-x^{*})^{\top}\nabla^{2}f(x^{*})(x-x^{*}).$ (53)

(Note that we have assumed the Hessian is constant in $U$, so there are no
third order terms.) Simplifying the above the expression, we get the following
quadratic term,

$\displaystyle(x-x^{*})^{\top}\nabla^{2}f(x^{*})(x-x^{*})+(x-x^{*})^{\top}\nabla
f(x^{*})=0\;.$ (54)

Completing the squares we get the following equation for the ellipsoid,

$\displaystyle(x-a)^{\top}M^{-1}(x-a)=1$ (55)

where $M^{-1}=\frac{H}{4b^{\top}H^{-1}b}$, $a=x^{*}-1/2H^{-1}b$ and $b=\nabla
f(x^{*})$, for all $x\in U$.

Thus for all $x\in U\subset\mathcal{X}$, $x$ satisfies the equation of the
ellipse $\mathcal{Y}=\\{x:(x-v)^{\top}M^{-1}(x-v)=1\\}$. The following claims
are immediately clear
$\mathrm{OPT}_{\mathcal{X}}(\theta)=\mathrm{OPT}_{\mathcal{Y}}(\theta)$ and
for small $\varepsilon$ such that
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\subset U$, we have
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$.

Let us then choose an $\varepsilon$ small enough so that
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$.

As a first step we see that the estimates of
$\mathbb{E}_{\theta^{\prime}}[\mathrm{N}_{\varepsilon,n}(\theta^{\prime})]\geqslant
n-\frac{c\sqrt{n}}{\varepsilon}$ remain true, for the entire action space
$\mathcal{X}$, for all $\theta^{\prime}$ such that
$\left\lVert\theta^{\prime}\right\rVert\leqslant
2\left\lVert\theta\right\rVert$ for which
$\mathbb{E}\left[{R_{n}(\theta^{\prime})}\right]\leqslant c\sqrt{n}$ for some
positive constant $c$.

As the next order of business we need to show
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ is approximately orthogonal to $u_{d}$.
For this first we note that
$\mathrm{OPT}_{\mathcal{X}}(\theta)=\mathrm{OPT}_{\mathcal{Y}}(\theta)$. Thus
it suffices to show that $\mathrm{OPT}_{\mathcal{Y}}(\theta)$ is approximately
orthogonal to $u_{d}$.

As before denote $\mathrm{OPT}_{\mathcal{Y}}(\theta)=v$ and decompose
$\bar{G}_{n}$ as

$\displaystyle\bar{G}_{n}=nvv^{\top}+\bar{G}_{n}-nvv^{\top}$ (56)

and note from Weyl’s Lemma and definition of $\lambda_{i}$, that

$\displaystyle\lambda_{i}(\bar{G}_{n})\leqslant\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert,$
(57)

for $i\in\\{2,3,\cdots,d\\}$. Now decomposing
$\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert$ into the two sets, one
containing arms belonging to the
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ set and another where arms do
not belong to the $\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ set and
further using the generic upper bound of $\lambda_{\max}(\mathcal{X})$ for the
size of all arms we have,

$\displaystyle\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert\leqslant\sum_{s:A_{s}\in\mathrm{OPT}_{\varepsilon}(\theta)}\lambda(\mathcal{X})\mathbb{E}\left[{\left\lVert
A_{s}-v\right\rVert}\right]+\sum_{s:A_{s}\notin\mathrm{OPT}_{\varepsilon}(\theta)}\lambda(\mathcal{X})\mathbb{E}\left[{\left\lVert(A_{s}-v)\right\rVert}\right]\;.$
(58)

Note as before, this can be be upper bounded using the estimates of
$\mathbb{E}_{\theta}[\mathrm{N}_{\varepsilon,n}(\theta)]$ as

$\displaystyle\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert\leqslant\frac{c\sqrt{n}\lambda(\mathcal{X})^{2}}{\varepsilon}+n\lambda(\mathcal{X})\sup_{A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)}\left\lVert
A_{s}-v\right\rVert\;.$ (59)

Now for small $\varepsilon$ such that
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$
we have
$\sup_{A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)}\left\lVert
A_{s}-v\right\rVert=\sup_{A_{s}\in\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)}\left\lVert
A_{s}-v\right\rVert$ for which we know $\left\lVert
A_{s}-v\right\rVert\leqslant O(\sqrt{\varepsilon})$. Thus by choosing
$\varepsilon$ as $O(1/\sqrt{n})$ for sufficiently large $n$, such that
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$,
we have (by choosing appropriate constant for reference see the section on the
sphere)

$\displaystyle\left\lVert\bar{G}_{n}-nvv^{\top}\right\rVert\leqslant 0.1n\;.$
(60)

Thus we have the separation of eigen-values between $\lambda_{1}(nvv^{\top})$
and $\lambda_{2}(\bar{G}_{n})$ as at least $0.9n$. This gives us from the
Davis-Kahan Theorem

$\displaystyle|v^{\top}u_{d}|\leqslant 1/9$ (61)

(See the previous sections for details). Thus we have
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ is approximately orthogonal to $u_{d}$.

As the next order of business we need to find a perturbed version of $\theta$,
namely $\theta^{\prime}=\theta+\alpha u_{d}$ such that
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ and
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})$ are disjoint. First
let us choose $\varepsilon$ small enough by sufficiently large $n$ such
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)=\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$.
Now as before for the ellipsoid case we have
$\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta+O(1/n^{1/4})u_{d})=\emptyset$.
Now by the continuity of
$\mathrm{OPT}_{\mathcal{Y}}(\theta)=\frac{M\theta}{\left\lVert\theta\right\rVert_{M}}+a$,
we have for sufficiently large $n$,
$\mathrm{OPT}_{\mathcal{Y}}(\theta+O(1/n^{1/2})u_{d})\in U$ and hence for
small $\varepsilon$ we have
$\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta+O(1/n^{1/4})u_{d})\subset U$.
Thus for large enough $n$, we have two disjoint sets
$\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta)$ and
$\mathrm{OPT}_{\varepsilon,\mathcal{Y}}(\theta+O(1/n^{1/4})u_{d})$ both
contained in $U$ and thus
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\cap\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta+O(1/n^{1/4})u_{d})=\emptyset$.
As before, we can now use the Gariver-Kauffman inequality to get

$\displaystyle\lambda_{d}(\bar{G}_{n})\geqslant\gamma\sqrt{n}$ (62)

for large enough $n$ depending upon $U$, and some constant $\gamma$ depending
upon the Hessian. This completes our proof. ∎

##  8 LOCALLY CONVEX SURFACES (PROOF OF THEOREM 3.3)

In this section we provide a proof of Theorem 3.3. We begin again by by
recalling or definition of Locally Convex surfaces (Definition 3.1) and
Theorem 3.3 for Locally Convex Action Sets.

######  Definition 8.1 (Locally Convex surface).

Consider an action space $\mathcal{X}=\\{x\in\mathbb{R}^{d}:f(x)=c\\}$, where
$f:\mathbb{R}^{d}\to\mathbb{R}$ is a $C^{2}$ function (i.e., all second order
partial derivatives exist and are continuous). With
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ being the optimal arm defined as before,
let the Hessian of $f$ at $\mathrm{OPT}_{\mathcal{X}}(\theta)$, denoted as
$\nabla^{2}f(\mathrm{OPT}_{\mathcal{X}}(\theta))$, be positive definite. Then,
$\mathcal{X}$ is said to be a Locally Convex surface.

######  Theorem 8.2.

Let $\mathcal{X}$ be a Locally Convex action space and $\bar{G}_{n}$, be the
expected design matrix. For any bandit algorithm which suffers expected regret
at most $O(\sqrt{n})$, there exists a real number $s$ in the half-open
interval $(0,\frac{1}{2}]$ such that

$\lambda_{\min}(\bar{G}_{n})=\Omega(n^{s})~{}.$

######  Remark 8.3.

The exponent $s$ defined in Theorem 8.2 depends explicitly on the geometry of
the action-space. In general it depends on how well the surface approximates a
LCH surface. The best we can say when no other information is given about the
action space is that the eigenvalue grows polynomially, which still results in
a polynomial rate of the parameter estimation.

###### Proof of Theorem 8.2.

The proof utilizes the following lemmas,

######  Lemma 8.4.

We can construct a quadratic approximation $\mathcal{E}$ about
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ similar to the construction for the LCH
case.

######  Lemma 8.5.

There exists a one-to-one map,
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}:\mathcal{X}\to\mathcal{E}$ and a
positive real number $p$ in the interval $(0,1]$, such that the
$\varepsilon$-optimal set in $\mathcal{X}$,
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ is contained in an
$O(\varepsilon^{p})$-optimal set in $\mathcal{E}$ for small enough
$\varepsilon$ .

######  Lemma 8.6.

There exists a positive real number $s$ in the interval $(0,\frac{1}{2}]$,
such that for $\theta^{\prime}=\theta+O(\sqrt{\frac{1}{n^{s}}})u_{d}$, the
$O(\varepsilon^{2s})$-optimal sets in the approximation $\mathcal{E}$,
$\mathrm{OPT}_{O(\varepsilon^{2s}),\mathcal{E}}(\theta)$ and
$\mathrm{OPT}_{O(\varepsilon^{2s}),\mathcal{E}}(\theta^{\prime})$ are
disjoint, and the image of the $\varepsilon$-optimal set
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})$ under the operator
defined in Lemma 8.5 is contained in
$\mathrm{OPT}_{O(\varepsilon^{2s}),\mathcal{E}}(\theta^{\prime})$.

Thus using Lemma 8.5 and Lemma 8.6, we ensure that the $\varepsilon$-optimal
sets of $\mathcal{X}$ for the bandit parameters $\theta$ and $\theta^{\prime}$
are disjoint. The remainder of the proof is the same as in the earlier cases.
∎

###### Proof of Lemma 8.4.

By the $C^{2}$ definition, there exists an open set $W\in\mathbb{R}^{d}$ such
that the Hessian of $f$ over $W\cap\mathcal{X}\triangleq U$,
$\nabla^{2}(f)(U)$ exists and is positive definite. Let $\mathcal{E}$ be a
quadratic approximation ellipsoid (similar to the construction as in the
locally constant hessian (LCH) case) about
$\mathrm{OPT}_{\mathcal{X}}(\theta)$. ∎

###### Proof of Lemma 8.5.

Let $\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}:\mathcal{X}\to\mathcal{E}$ be
the best approximation operator denoted by

$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(y)=\mathop{\mathrm{argmin}}_{x\in\mathcal{E}}\left\lVert
x-y\right\rVert$

for any $y$ in $\mathcal{X}$. This operator finds the nearest point to a point
in the action set $\mathcal{X}$ to the ellipsoid approximation $\mathcal{E}$.

From continuity of $f$ and construction of $\mathcal{E}$, there exists a small
neighbourhood $W$ about $\mathrm{OPT}_{\mathcal{X}}(\theta)$ such that the
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}$ operator is injective. As in the
proof of the Locally Constant Hessian (LCH) case, we shall restrict our
attention to the neighbourhood of $U\cap W\triangleq V$.

Let $x\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$. By definition,

$x^{\top}\theta\geqslant\mathrm{OPT}_{\mathcal{X}}(\theta)^{\top}\theta-\varepsilon.$

Now $x=\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)+r\vec{u}$ where $\vec{u}$
is the normal at $x$ and $r$ is
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)-x\right\rVert$. Note
that as $\varepsilon\to 0$,
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)\to\mathrm{OPT}_{\mathcal{X}}(\theta)$
and $x\to\mathrm{OPT}_{\mathcal{X}}(\theta)$. Therefore $r\to 0$. Thus
$r=O(\varepsilon^{p})$, for some $p>0$. Then, without loss of generality
assuming $\left\lVert\theta\right\rVert=1$, we have by Cauchy-Schwartz,

$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)^{\top}\theta+r\geqslant\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)^{\top}\theta+r\vec{u}^{\top}\theta=x^{\top}\theta\geqslant\mathrm{OPT}_{\mathcal{X}}(\theta)^{\top}\theta-\varepsilon=\mathrm{OPT}_{\mathcal{E}}(\theta)^{\top}\theta-\varepsilon\;.$

Thus
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)\in\mathrm{OPT}_{O(\varepsilon^{\min{(1,p)}}),\mathcal{E}}(\theta)$.

Let $\varepsilon_{1}$ be such that for all
$\varepsilon\leqslant\varepsilon_{1}$,
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)\subset V$, then we have
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta))\subset\mathrm{OPT}_{O(\varepsilon^{\min{(1,p)}}),\mathcal{E}}(\theta)$
for all $\varepsilon\leqslant\varepsilon_{1}$. ∎

###### Proof of Lemma 8.6.

From the ellipsoidal case, we have by construction,
$\theta^{\prime}=\theta+\alpha u_{d}$, where $\alpha=O(\sqrt{\varepsilon})$
and $u_{d}$ is the eigen-vector corresponding to the minimum eigen-value to
ensure separation. This required showing that $u_{d}$ and
$\mathrm{OPT}(\theta)$ are roughly perpendicular to each other. For the
current case, it is also possible to show that $u_{d}$ and
$\mathrm{OPT}_{\mathcal{X}}(\theta)$ is approximately perpendicular under the
polynomial approximation assumption for $\varepsilon=O(\frac{1}{\sqrt{n}})$.
We leave this as an easy exercise.

Thus let us construct $\theta^{\prime}=\theta+\alpha u_{d}$, where $\alpha$,
would have to be carefully constructed, such that as $\varepsilon\to 0$,
$\alpha\to 0$. Let,
$x\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})$. By definition,

$x^{\top}\theta^{\prime}\geqslant\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime})^{\top}\theta^{\prime}-\varepsilon.$

For $\alpha$ very small, we have,
$\left\lVert\theta^{\prime}\right\rVert\approx 1$, and as before using the
approximation operator and Cauchy-Schwartz, we have

$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)^{\top}\theta^{\prime}+r_{1}\geqslant\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))^{\top}\theta^{\prime}+r_{2}\vec{u}^{\top}\theta^{\prime}-\varepsilon\;.$
(63)

where $r_{1}$ is the approximation error
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)-x\right\rVert$,
$r_{2}$ is the approximation error
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))-\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime})\right\rVert$
and $\vec{u}$ is the normal at $\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime})$.

As $\varepsilon\to 0$, we have $\theta^{\prime}\to\theta$ (because $\alpha\to
0$) and therefore $x\to\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime})$. Thus
$r_{1}=O(\varepsilon^{q})$ for some $q>0$ by the polynomial approximation.
Also $\vec{u}$ approaches the normal at $\mathrm{OPT}_{\mathcal{X}}(\theta)$
and thus by continuity of $f$, there exists an $\varepsilon_{2}$ such that for
all $\varepsilon\leqslant\varepsilon_{2}$ we have
$\vec{u}^{\top}\theta^{\prime}\geqslant 0$. Thus for small enough
$\varepsilon$, we have for any
$x\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})$,

$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)^{\top}\theta^{\prime}+O(\varepsilon^{q})\geqslant\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))^{\top}\theta^{\prime}-\varepsilon\;.$
(64)

Note that as $\varepsilon\to 0$, we have
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))\to\mathrm{OPT}_{\mathcal{E}}(\theta)$
and
$\mathrm{OPT}_{\mathcal{E}}(\theta^{\prime})\to\mathrm{OPT}_{\mathcal{E}}(\theta)$,
and thus we have
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))-\mathrm{OPT}_{\mathcal{E}}(\theta^{\prime})\right\rVert=O(\varepsilon^{r})$
for some $r>0$. This implies,

$\mathrm{OPT}_{\mathcal{E}}(\theta^{\prime})^{\top}\theta^{\prime}-\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))^{\top}\theta^{\prime}\leqslant\left\lVert\mathrm{OPT}_{\mathcal{E}}(\theta^{\prime})-\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))\right\rVert\left\lVert\theta^{\prime}\right\rVert\leqslant
O(\varepsilon^{r})\;.$

Using this relation we get,

$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)^{\top}\theta^{\prime}\geqslant\mathrm{OPT}_{\mathcal{E}}(\theta^{\prime})^{\top}\theta^{\prime}-\varepsilon-O(\varepsilon^{r})-O(\varepsilon^{q}).$

Thus we have
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)\in\mathrm{OPT}_{O(\varepsilon^{\min{(1,q,r)}}),\mathcal{E}}(\theta^{\prime})$.
Let $\varepsilon_{3}$ be such that for all
$\varepsilon\leqslant\varepsilon_{3}$,
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})\subset V$, then we
have
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime}))\subset\mathrm{OPT}_{O(\varepsilon^{\min{(1,q,r)}}),\mathcal{E}}(\theta)$
for all $\varepsilon\leqslant\varepsilon_{3}$.

Thus for all
$\varepsilon\leqslant\min{(\varepsilon_{1},\varepsilon_{2},\varepsilon_{3})}$,
we have
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta))\subset\mathrm{OPT}_{O(\varepsilon^{\min{(1,p)}}),\mathcal{E}}(\theta)\subset\mathrm{OPT}_{O(\varepsilon^{\min{(1,p,q,r)}}),\mathcal{E}}(\theta)$

and
$\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime}))\subset\mathrm{OPT}_{O(\varepsilon^{\min{(1,q,r)}}),\mathcal{E}}(\theta^{\prime})\subset\mathrm{OPT}_{O(\varepsilon^{\min{(1,p,q,r)}}),\mathcal{E}}(\theta^{\prime})$.

Now from the LCH case, we have
$\mathrm{OPT}_{O(\varepsilon^{\min{(1,p,q,r)}}),\mathcal{E}}(\theta)$ and
$\mathrm{OPT}_{O(\varepsilon^{\min{(1,p,q,r)}}),\mathcal{E}}(\theta^{\prime})$
are disjoint if
$\theta^{\prime}=\theta+O(\sqrt{\varepsilon^{\min{(1,p,q,r)}}})u_{d}$, and by
construction based on the injectivity of the approximation operator,
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$ and
$\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})$ are as well
disjoint.

This gives us by choice of $\varepsilon=O(\frac{1}{\sqrt{n}})$

$\displaystyle\lambda_{d}\geqslant\Omega(n^{s})$

where $s\in(0,1/2]$ and defined as $s=\frac{1}{2}\min{(1,p,q,r)}$. This
completes our proof. ∎

######  Remark 8.7.

For the LCH case, we have no approximation error and the exponents defined by
$p,q,r$, are strictly more than $1$ (they are in fact $\infty$) and we get
back the results of Theorem 7.9 of $\Omega(\sqrt{n})$.

######  Remark 8.8.

Note that the $s$ defined in Theorem 8.2 is defined as
$\frac{1}{2}\min{(1,p,q,r)}$, where each $p,q,r$ represent the approximation
error with respect to an LCH surface. Specifically with $\mathcal{E}$ being
defined as the approximating Ellipsoid and $\mathcal{X}$ denoting the original
action space, we have $p$ defined as the rate at which
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)-x\right\rVert$ goes
to $0$, that is
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)-x\right\rVert=O(\varepsilon^{p})$
for any $x\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$. Similarly $q$ is
defined as
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)-x\right\rVert=O(\varepsilon^{q})$
for any $x\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta^{\prime})$ and $r$
is defined as
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(\mathrm{OPT}_{\mathcal{X}}(\theta^{\prime}))-\mathrm{OPT}_{\mathcal{E}}(\theta^{\prime})\right\rVert=O(\varepsilon^{r})$.

###  8.1 Example of Locally Convex action space:

In this subsection we demonstrate experimentally an action space which is
_convex_ and for which the minimum eigenvalue grows slower than
$\Omega(\sqrt{n})$. Consider the action-space
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:\left\lVert x\right\rVert_{10}\leqslant
1\\}$. Clearly, this is a convex set. We set the bandit parameter as
$\theta=(1,\ldots,1)$, as a vector of $1$s of size $d$. We use Thompson
Sampling as the representative algorithm and plot the growth of the minimum
eigenvalue versus rounds $n$ as in Section 4. In order to demonstrate the high
probability phenomenon, we form a high confidence band of the mean observation
of $\log{\lambda_{\min}(V_{n})}/\log{n}$ with three standard deviations of
width.We observe the the minimum eigenvalue grows less than
$\Omega(\sqrt{n})$.

Figure 5: Scaling of the minimum eigenvalue of design matrix (generated by the
Thompson sampling algorithm) with time for the action space
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:\left\lVert x\right\rVert_{10}\leqslant
1\\}$ . The plots represent averages over $20$ independent trials. The $X$
axis denotes the number of rounds $n$ and the $Y$-axis denotes
$\frac{\log{\lambda_{\min}(V_{n})}}{\log{n}}$. We plot the mean trend of
$\frac{\log{\lambda_{\min}(V_{n})}}{\log{n}}$ along with three standard
deviations. The dotted black line is the constant (exponent) $1/2$. Note that
$\frac{\log{\lambda_{\min}(V_{n})}}{\log{n}}$ settles at value below $1/2$. We
plot this for two dimensions $5$ and $20$ to note the dependence on dimension
$d$. We note that these corroborate with our theory.

##### Justification :

Let us first observe that the Hessian at $\mathrm{OPT}_{\mathcal{X}}(\theta)$
is positive definite and continuous for our choice of $\theta$. We can also
calculate that for our choice of the action space $\mathcal{X}$, any point
$x\in\mathrm{OPT}_{\varepsilon,\mathcal{X}}(\theta)$,

$\displaystyle\left\lVert
x-\mathrm{OPT}_{\mathcal{X}}(\theta)\right\rVert=\varepsilon^{1/10}~{}.$

(This is easy to see for dimension $2$.) Thus the
$\left\lVert\bar{\mathbf{P}}_{\mathcal{X},\mathcal{E}}(x)-x\right\rVert$ as
defined in the proof of Theorem 8.2 (see Section 8) is of the order of
$\varepsilon^{1/10}$ and hence $p$ as defined above is $1/10$. This means that
$\lambda_{\min}(V_{n})=\Omega(n^{0.1})$. This is true as observed from our
experiments as observed in Figure 5. However we specifically also show that
the minimum eigenvalue $\lambda_{\min}(V_{n})$ is growing at a rate less than
$\sqrt{n}$. This corroborates our results.

##  9 MODEL SELECTION: PROOF OF RESULTS

###### Proof of Lemma 5.3.

We consider doubling epochs, with lengths $n_{i}=2^{i-1}n_{1}$, where $n_{1}$
is the initial epoch length and $N$ is the total number of epochs. Then, from
the doubling principle, we get

$\displaystyle\sum_{i=1}^{N}2^{i-1}n_{1}=n\,\,\Rightarrow\,N=\log_{2}\left(1+n/n_{1}\right)=\mathcal{O}\left(\log(n/n_{1})\right).$

Now, consider the $i$-th epoch. Let $\widehat{\theta}_{n_{i}}$ be the least
square estimate of $\theta$ at the end of epoch $i$. The confidence interval
at the end of epoch $i$, i.e., after OFUL is run with a norm estimate
$b^{(i)}$ for $n_{i}$ rounds with confidence level $\delta_{i}$, is given by

$\displaystyle\mathcal{B}_{n_{i}}=\left\\{\theta\in\mathbb{R}^{d}:\|\theta-\widehat{\theta}_{n_{i}}\|_{(V_{n_{i}}+\lambda
I)}\leqslant\sqrt{\beta_{n_{i}}(\delta_{i})}\right\\}.$

Here $\beta_{n_{i}}(\delta_{i})$ denotes the radius and $\Sigma_{n_{i}}$
denotes the shape of the ellipsoid. Under Assumption 5.1, the ellipsoid takes
the form

$\displaystyle\mathcal{B}_{n_{i}}=\left\\{\theta\in\mathbb{R}^{d}:\|\theta-\widehat{\theta}_{n_{i}}\|\leqslant\frac{\sqrt{\beta_{n_{i}}(\delta_{i})}}{\sqrt{\lambda+\gamma_{0}n_{i}}}\right\\},$

with probability at least $1-\delta_{i}=1-\delta/2^{i-1}$. Here, we use the
fact that $\gamma_{\min}(V_{n_{i}})\geqslant\lambda+\gamma_{0}\sqrt{n_{i}}$
under Assumption 5.1, provided $n_{i}\geqslant n_{0}$. To ensure this, we
choose $n_{1}\geqslant n_{0}$. Now, note that $\theta\in\mathcal{B}_{n_{i}}$
with probability at least $1-\delta_{i}$. Therefore, we have

$\displaystyle\|\widehat{\theta}_{n_{i}}\|\leqslant\|\theta\|+\frac{\sqrt{\beta_{n_{i}}(\delta_{i})}}{\sqrt{\lambda+\gamma_{0}\sqrt{n_{i}}}}$

with probability at least $1-2\delta_{i}$. Recall that at the end of the
$i$-th epoch, ALB set the estimate of $\|\theta\|$ to
$b^{(i+1)}=\max_{\theta\in\mathcal{B}_{n_{i}}}\|\theta\|$. Then, from the
definition of $\mathcal{B}_{n_{i}}$, we obtain

$\displaystyle
b^{(i+1)}=\|\widehat{\theta}_{n_{i}}\|+\frac{\sqrt{\beta_{n_{i}}(\delta_{i})}}{\sqrt{\lambda+\gamma_{0}\sqrt{n_{i}}}}\leqslant\|\theta\|+2\frac{\sqrt{\beta_{n_{i}}(\delta_{i})}}{\sqrt{\lambda+\gamma_{0}\sqrt{n_{i}}}}$

with probability higher than $1-2\delta_{i}$. If noise is distributed as
$\mathcal{N}(0,1)$, the confidence radius reads

$\displaystyle\sqrt{\beta_{n_{i}}(\delta_{i})}=b^{(i)}\sqrt{\lambda}+\sqrt{2\log(1/\delta_{i})+d\log(1+n_{i}/(\lambda
d))}~{},$

We now substitute $n_{i}=2^{i-1}n_{1}$ and $\delta_{i}=\frac{\delta}{2^{i-1}}$
to obtain $\sqrt{\lambda+\gamma_{0}\sqrt{n_{i}}}\geqslant
2^{\frac{i-1}{4}}\sqrt{\gamma_{0}\sqrt{n_{1}}}$, and

$\displaystyle\frac{\sqrt{\beta_{n_{i}}(\delta_{i})}}{\sqrt{\lambda+\gamma_{0}n_{i}}}\leqslant
C_{1}\frac{b^{(i)}\sqrt{\lambda}}{2^{\frac{i-1}{4}}\sqrt{\gamma_{0}\sqrt{n_{1}}}}+C_{2}\frac{i}{2^{\frac{i-1}{4}}\sqrt{\gamma_{0}\sqrt{n_{1}}}}\sqrt{2\log(1/\delta_{1})+d\log(1+n_{1}/(\lambda
d))}$

for some universal constants $C_{1},C_{2}$. Using this, we further obtain

$\displaystyle b^{(i+1)}$
$\displaystyle\leqslant\|\theta\|+2C_{1}\frac{b^{(i)}\sqrt{\lambda}}{2^{\frac{i-1}{4}}\sqrt{\gamma_{0}\sqrt{n_{1}}}}+2C_{2}\frac{i}{2^{\frac{i-1}{4}}\sqrt{\gamma_{0}\sqrt{n_{1}}}}\sqrt{2\log(1/\delta_{1})+d\log(1+n_{1}/(\lambda
d))}$
$\displaystyle\leqslant\|\theta\|+b^{(i)}\frac{p}{2^{\frac{i-1}{4}}}\sqrt{\frac{1}{\sqrt{n_{1}}}}+\frac{iq}{2^{\frac{i-1}{4}}}\sqrt{\frac{d}{\sqrt{n_{1}}}},$

with probability at least $1-2\delta_{i}$, where we introduce the terms

$\displaystyle
p=\frac{2C_{1}\sqrt{\lambda}}{\sqrt{\gamma_{0}}}\,\,\,\,\text{and}\,\,\,q=\frac{2C_{2}}{\sqrt{\gamma_{0}}}\sqrt{2\log(1/\delta_{1})+\log(1+n_{1}/\lambda)}.$

Therefore, with probability at least $1-2\delta_{i}$, we obtain

$\displaystyle
b^{(i+1)}-b^{(i)}\leqslant\|\theta\|-\left(1-\frac{p}{2^{\frac{i-1}{4}}}\frac{1}{n_{1}^{1/4}}\right)b^{(i)}+\frac{iq}{2^{\frac{i-1}{4}}}\frac{\sqrt{d}}{n_{1}^{1/4}}.$

Note that by construction, $b^{(i)}\geqslant\|\theta\|$. Hence, provided
$n_{1}>\frac{2p^{4}}{2^{i}}$, we have

$\displaystyle
b^{(i+1)}-b^{(i)}\leqslant\frac{p}{2^{\frac{i-1}{4}}}\frac{\left\lVert\theta\right\rVert}{n_{1}^{1/4}}+\frac{iq}{2^{\frac{i-1}{4}}}\frac{\sqrt{d}}{n_{1}^{1/4}},$

with probability at least $1-2\delta_{i}$. From the above expression, we have
$\sup_{i}b^{(i)}<\infty$ with probability greater than or equal to
$1-\sum_{i}2\delta_{i}=1-\sum_{i}2\delta/2^{i-1}=1-4\delta$. From the
expression of $b^{(i+1)}$ and using the above fact, we get
$\lim_{i\rightarrow\infty}b^{(i)}\leqslant\|\theta\|$. However, by
construction $b^{(i)}\geqslant\|\theta\|$. Using this, along with the above
observation, we obtain

$\displaystyle\lim_{i\rightarrow\infty}b^{(i)}=\|\theta\|.$

with probability exceeding $1-4\delta$. Therefore, we deduce that the sequence
$\\{b^{(1)},b^{(2)},...\\}$ converges to $\|\theta\|$ with probability at
least $1-4\delta$, and hence our successive refinement algorithm is
consistent.

Rate of Convergence. Since
$b^{(i+1)}-b^{(i)}=\tilde{\mathcal{O}}\left(\frac{i}{2^{i/4}}\right)$ with
high probability, the rate of convergence of the sequence
$\\{b^{(i)}\\}_{i=1}^{\infty}$ is exponential in the number of epochs.

A uniform upper bound on $b^{(i)}$. Consider the sequences
$\Bigg{\\{}\frac{i}{2^{\frac{i-1}{4}}}\Bigg{\\}}_{i=1}^{\infty}$ and
$\Bigg{\\{}\frac{1}{2^{\frac{i-1}{4}}}\Bigg{\\}}_{i=1}^{\infty}$. Let $t_{i}$
and $u_{i}$ denote the $i$-th term of the sequences respectively. It is easy
to see that $\sup_{i}t_{i}<\infty$ and $\sup_{i}u_{i}<\infty$, and that the
sequences $\\{t_{i}\\}_{i=1}^{\infty}$ and $\\{u_{i}\\}_{i=1}^{\infty}$ are
convergent. Now, we have

$\displaystyle
b^{(2)}\leqslant\|\theta\|+u_{1}\frac{pb^{(1)}}{n_{1}^{1/4}}+t_{1}\frac{q\sqrt{d}}{n_{1}^{1/4}}$

with probability at least $1-2\delta$. Similarly, we write $b^{(3)}$ as

$\displaystyle
b^{(3)}\leqslant\|\theta\|+u_{2}\frac{pb^{(2)}}{n_{1}^{1/4}}+t_{2}\frac{q\sqrt{d}}{n_{1}^{1/4}}\leqslant\left(1+u_{2}\frac{p}{n_{1}^{1/4}}\right)\|\theta\|+\left(u_{1}u_{2}\frac{p}{n_{1}^{1/4}}\frac{p}{n_{1}^{1/4}}b^{(1)}\right)+\left(t_{1}u_{2}\frac{p}{n_{1}^{1/4}}\frac{q\sqrt{d}}{n_{1}^{1/4}}+t_{2}\frac{q\sqrt{d}}{n_{1}^{1/4}}\right)$

with probability at least $1-2\delta-\delta=1-3\delta$. Similarly, we write
expressions for $b^{(4)},b^{(5)},...$. Now, provided $n_{1}\geqslant
C\,d^{2}\left(\max\\{p,q\\}\,b^{(1)}\right)^{4}$, where $C$ is a sufficiently
large constant, $b^{(i)}$ can be upper-bounded, with with probability at least
$1-\sum_{i}2\delta_{i}=1-4\delta$, as

$\displaystyle b^{(i)}\leqslant c_{1}\|\theta\|+c_{2}$

for all $i$, where $c_{1},c_{2}>0$ are some universal constants, which are
obtained from summing an infinite geometric series with decaying step size. ∎

###### Proof of Corollary 5.4.

The cumulative regret of ALB is given by

$\displaystyle
R(n)\leqslant\sum_{i=1}^{N}R^{\texttt{OFUL}}(n_{i},\delta_{i},b^{(i)}),$

where $N$ denotes the total number of epochs and
$R^{\texttt{OFUL}}(n_{i},\delta_{i},b^{(i)})$ denotes the cumulative regret of
OFUL, when it is run with confidence level $\delta_{i}$ and norm upper bound
$b^{(i)}$ for $n_{i}$ episodes. Using the result of Abbasi-yadkori et al.
(2011), we have

$\displaystyle
R^{\texttt{OFUL}}(n_{i},\delta_{i},b^{(i)})=\mathcal{O}\left(b_{i}\sqrt{dn_{i}\log
n_{i}}+d\sqrt{n_{i}\log n_{i}\log(n_{i}/\delta)}\right)$

with probability at least $1-\delta_{i}$. Now, using Lemma 5.3, we obtain

$\displaystyle
R(n)\leqslant(c_{1}\|\theta\|+c_{2})\sum_{i=1}^{N}\mathcal{O}\left(\sqrt{dn_{i}\log
n_{i}}\right)+\sum_{i=1}^{N}\mathcal{O}\left(d\sqrt{n_{i}\log
n_{i}\log(n_{i}/\delta)}\right)$

with probability at least $1-4\delta-\sum_{i}\delta_{i}$. Substituting
$n_{i}=2^{i-1}n_{1}$ and $\delta_{i}=\frac{\delta}{2^{i-1}}$, we get

$\displaystyle
R(n)\leqslant(c_{1}\|\theta\|+c_{2})\sum_{i=1}^{N}\mathcal{O}\left(\sqrt{i\,dn_{i}\log
n_{1}}\right)+\sum_{i=1}^{N}\mathcal{O}\left(\mathsf{poly}(i)\,d\sqrt{n_{i}\log
n_{1}\log(n_{1}/\delta)}\right)$

with probability at least $1-4\delta-2\delta=1-6\delta$. Using the above
expression, we get the regret bound

$\displaystyle R(n)$
$\displaystyle\leqslant\mathcal{O}\left((c_{1}\|\theta\|+c_{2})\sqrt{d\log
n_{1}}+d\sqrt{\log
n_{1}\log(n_{1}/\delta)}\right)\sum_{i=1}^{N}\mathsf{poly}(i)\sqrt{n_{i}}$
$\displaystyle\leqslant\mathcal{O}\left((c_{1}\|\theta\|+c_{2})\sqrt{d\log
n_{1}}+d\sqrt{\log
n_{1}\log(n_{1}/\delta)}\right)\mathsf{poly}(N)\,\,\sum_{i=1}^{N}\sqrt{n_{i}}$
$\displaystyle\leqslant\mathcal{O}\left((c_{1}\|\theta\|+c_{2})\sqrt{d\log
n_{1}}+d\sqrt{\log
n_{1}\log(n_{1}/\delta)}\right)\mathsf{polylog}(n/n_{1})\,\,\sum_{i=1}^{N}\sqrt{n_{i}}$
$\displaystyle\leqslant\mathcal{O}\left((c_{1}\|\theta\|+c_{2})\sqrt{d\log
n_{1}}+d\sqrt{\log
n_{1}\log(n_{1}/\delta)}\right)\mathsf{polylog}(n/n_{1})\sqrt{n}$
$\displaystyle=\mathcal{O}\left(\left(\|\theta\|\sqrt{dn\log
n_{1}}+d\sqrt{n\log
n_{1}\log(n_{1}/\delta)}\right)\mathsf{polylog}(n/n_{1})\right),$

where we have used that $N=\mathcal{O}\left(\log(n/n_{1})\right)$, and
$\sum_{i=1}^{N}\sqrt{n_{i}}=\mathcal{O}(\sqrt{n})$. The above regret bound
holds with probability greater than or equal to $1-6\delta$, which completes
the proof. ∎

##  10 CLUSTERING IN MULTI AGENT BANDITS: PROOFS OF RESULT

###### Proof of Lemma 5.6.

Let us look at the parameter estimate of agent $i$, and without loss of
generality, assume that agent $i$ belongs to cluster $j$. Since we let the
agents play OFUL for $n$ time steps, from Abbasi-yadkori et al. (2011), for
agent $i$, we obtain

$\displaystyle\|\widehat{\theta}^{(i)}-\theta^{*}_{j}\|_{\bar{V}_{n}}\leqslant
2\sqrt{d\log(n/\delta)},$

where $\bar{V}_{n}=\sum_{t=1}^{n}x_{{A_{t}},t}x_{{A_{t}},t}^{\top}+\lambda I$,
where $A_{t}$ is the action of agent $i$ at time $t$. The above holds with
probability at least $1-\delta$. Furthermore, we assume that OFUL is run with
regularization parameter $\lambda$ chosen as $\mathcal{O}(1)$. Continuing, we
obtain

$\displaystyle\sqrt{\lambda_{\min}(\bar{V}_{n})}\,\|\widehat{\theta}^{(i)}-\theta^{*}_{j}\|\leqslant
2\sqrt{d\log(n/\delta)}.$

We now use Assumption 5.1, with $\lambda=\mathcal{O}(1)$. Using Weyl’s
inequality, we obtain,
$\lambda_{\min}(\bar{V}_{n})>\frac{\gamma}{2}\sqrt{n}\sqrt{\log(d/\delta)}$,
with probability at least $1-\delta$. With this we have,

$\displaystyle\|\widehat{\theta}^{(i)}-\theta^{*}_{j}\|\leqslant\frac{2\sqrt{2}}{\sqrt{\gamma}n^{1/4}}\frac{1}{\log(d/\delta)^{1/4}}\sqrt{d\log(n/\delta)}=\frac{1}{n^{1/4}}\,\frac{2\sqrt{2}\sqrt{d}}{\sqrt{\gamma}}\sqrt{\frac{\log(n/\delta)}{\log^{1/2}(d/\delta)}}.$

From the separation condition on $\Delta$ and the choice of threshold $\eta$,
we obtain

$\displaystyle\|\widehat{\theta}^{(i)}-\theta^{*}_{j}\|\leqslant\frac{\eta}{2},$

with probability at least $1-2\delta$. We now consider $2$ cases:

Case I: Agents $i$ and $i^{\prime}$ belong to same cluster $j$: In this setup
we have

$\displaystyle\|\widehat{\theta}^{(i)}-\widehat{\theta}^{(i^{\prime})}\|$
$\displaystyle\leqslant\|\widehat{\theta}^{(i)}-\theta^{*}_{j}\|+\|\widehat{\theta}^{(i^{\prime})}-\theta^{*}_{j}\|$
$\displaystyle\leqslant\frac{\eta}{2}+\frac{\eta}{2}=\eta,$

with probability at least $1-4\delta$.

Case II: Agents $i$ and $i^{\prime}$ belong to different cluster $j$ and
$j^{\prime}$ respectively: In this case we have

$\displaystyle\|\widehat{\theta}^{(i)}-\widehat{\theta}^{(i^{\prime})}\|$
$\displaystyle=\|(\widehat{\theta}^{(i)}-\theta^{*}_{j})+(\theta^{*}_{j^{\prime}}-\widehat{\theta}^{(i^{\prime})})-(\theta^{*}_{j^{\prime}}-\theta^{*}_{j})\|$