# Weak gravitational quantum effects in boson particles

Omar Gallegos<EMAIL_ADDRESS>Departamento de Física, Centro de
Investigación y de Estudios Avanzados del IPN, A.P. 14-740, 07000 CDMX,
México. Tonatiuh Matos<EMAIL_ADDRESS>Departamento de Física, Centro
de Investigación y de Estudios Avanzados del IPN, A.P. 14-740, 07000 CDMX,
México.

(February 2019)

###### Abstract

We rewrite the Klein-Gordon (KG) equation in an arbitrary space-time
transforming it into a generalized Schrödinger equation. Then, we take the
weak field limit and show that this equation has certain differences with the
traditional Schrödinger equation plus a gravitational field. Thus, this
procedure shows that the Schrödinger equation derived in a covariant manner is
different from the traditional one. We study the KG equation in a Newtonian
space-time to describe the behavior of a scalar particle in an inertial
system. This particle is immersed in a gravitational field with the new
Schrödinger equation. We study particular physical systems given examples for
which we find their energy levels, effective potential and the wave function
of the systems. The results contain the gravitational effects due to the
curvature of the space-time. Finally, we discuss the possibility of the
experimental verification of these effects in a laboratory using non-inertial
reference frames.

##  1 Introduction

In the last century, General Relativity (GR) and Quantum Mechanics (QM), the
two pillars of modern physics, have been developed and verified independently
with great precision, while quantum physics describes successfully the
behavior of tiny particles, GR is very accurate for forces at cosmic scales.
However, in some cases, the two theories produce incompatible results which
give rise to different definitions for the same concept. We think the
inconsistency between GR and QM owes to the concept of interaction between
particles. In QM two particles interact when they exchange a virtual particle,
while in GR the interaction is just due to the geometry of space-time. In this
work we adopt the geometrical GR concept, instead of the exchange of virtual
particles to test if a boson gas follows the Klein- Gordon equation in a
curved space-time, and to test GR in quantum regime. These results could be
useful either for laboratory particles as well as for the study of the quantum
character of boson particles proposed as dark matter (see for example [1],
[2]).

An important problem in theoretical and fundamental physics is to have a
Theory of Everything where the principal theories in physics, GR and QM, can
be compatible. In the last decades, some theories have been proposed [3],[4]
to this unification. Nevertheless, the experimental verification of these
candidates and their theoretical problems are so far too complex. Several
physicists have tried to test if gravity has a quantum nature with different
proposals for experiments and observations[5][6], but some proposals are not
feasible with the technology available to this day. We do not pretend to
propose a new Theory of Everything, instead we want to give a new different
way to measure the gravitational effect due to the curvature of space-time on
quantum systems, specially on scalar particles. These results do not
definitely prove if gravity is or not a quantum interaction but they present a
closer path to answer this fundamental question.

Einstein’s Equivalence Principle (EEP), one of the foremost ideas for
developing General Relativity, where the concept of inertia takes a different
role from the one used in Newtonian mechanics. EEP states that experiments in
a sufficiently small freely falling laboratory, over a sufficiently short
time, give results that are indistinguishable from those of the same
experiments in an inertial frame in the presence of a gravitational field.
Hence, we use this principle to develop this work, studying some different
examples of QM on an inertial frame immersed in a gravitational field. To
measure these effects in a laboratory, we will place a quantum system on a
non-inertial frame, hoping to get the same results both in the theoretical
part and in the experimental one. Furthermore, we expect to obtain results on
quantization as in QM. So, one of the objectives of this paper is to test the
EEP in quantum scales, thus a proof of GR in a quantum scale.

We would expect that there exists a regime where the quantum aspects of
gravity are detectable. With a simple dimensional analysis we may have an idea
where the gravitational effects on a quantum system are important, i.e. the
physical scale where these effects can be observed. It is possible to compare
two well-known quantities in QM and GR, which are the Bohr radius $r_{bohr}$
and the Schwarzschild radius $r_{sch}$. Both radii are defined as
$r_{bohr}=\hbar/(\mu c\alpha)$ and $r_{sch}=2GM/c^{2}$ where $c$, $G$,
$\alpha$ are the speed of light, the gravitational constant and the fine-
structure constant respectively. Also $\hbar=h/2\pi$ is the Planck’s constant,
while $M$ is the mass that produces the gravitational field, $\mu$ is the
reduced mass of a couple of particles. In a case where the comparison between
masses is such that $M>>m$, it leads us to the approximation $\mu\approx m$,
where $m$ is the mass of a boson particle, which is inside a gravitational
field generated by a source of mass $M$. Thereby, the following expression is
obtained when both radii $r_{bohr}\sim r_{sch}$ are comparable

$M\sim\dfrac{\hbar c}{2G\alpha m}=\dfrac{m_{pl}^{2}}{2\alpha
m}\approx\dfrac{3.25\times 10^{-14}}{m}\text{kg}^{2},$ (1)

where $m_{pl}=\sqrt{\hbar c/G}$ is the Planck’s mass. This result was inspired
by the micro black holes described in[7] and it enables us to find the limit
for measuring quantum gravitational effects. If we assume $m=m_{e}$ is the
mass of an electron, we obtain that $M\sim 3.57\times 10^{16}$kg is the mass
for which an electron should feel a gravitational effect. On the other hand,
the mass of Earth is $\sim 5\times 10^{24}$kg, namely, we should measure in
Earth the quantum gravitational effects on an electron. If we consider now the
mass of an ultralight scalar particle $\sim 10^{-22}eV/c^{2}$, the mass
proposed in models of Scalar Field Dark Matter (SFDM)[1], [2], we calculate
from Eq.(1) that $M\sim 10^{12}M_{\odot}$ (the galaxies have a mass of this
order). Thus, we can say, if dark matter is a scalar field with mass $m\sim
10^{-22}eV/c^{2}$ [1], [2], the galaxy should present a gravitational quantum
behavior. In this work, we study well-known examples of QM for scalar
particles with corrections due to the curvature of space-time.

##  2 Generalized Schrödinger Equation

In order to analyze the gravitational effect due to curvature of space-time in
a quantum system, we focus on a scalar field following reference [8], in which
the KG covariant equation with an external potential is described

$\Box\Phi-\dfrac{d\mathscr{V}}{d\Phi^{*}}=0,$ (2)

here
$\Box=g^{\mu\nu}\nabla_{\mu}\nabla_{\nu}=\dfrac{1}{\sqrt{-g}}\partial_{\mu}(\sqrt{-g}g^{\mu\nu}\partial_{\nu})$
is the D’Alembertian operator associated to an arbitrary metric $g_{\mu\nu}$,
$\Phi=\Phi(t,\vec{x})$ is the scalar field, $\Phi^{*}=\Phi^{*}(t,\vec{x})$ is
its conjugated complex and the scalar field potential is
$\mathscr{V}=\mathscr{V}(\Phi,\Phi^{*})$ endowed with an external potential
$V$ just as it is shown in the following equation

$\mathscr{V}=\left(\dfrac{m^{2}c^{2}}{\hbar^{2}}+\dfrac{\lambda
n_{0}}{2}+\dfrac{2m}{\hbar^{2}}V\right)\Phi\Phi^{*},$ (3)

where $m$ is the mass of the scalar field and $n_{0}=n_{0}(t,\vec{x})$ is
defined as the scalar field density, namely $n_{0}=|\Phi|^{2}$. The space-time
is expanded in a 3+1 slices, such that the coordinate $t$ here is the
parameter of evolution, the 3+1 metric then reads

$\mathrm{d}s^{2}=-N^{2}c^{2}\mathrm{d}t^{2}+\gamma_{ij}\left(\mathrm{d}x^{i}+N^{i}c\,\mathrm{d}t\right)\left(\mathrm{d}x^{j}+N^{j}c\,\mathrm{d}t\right),$
(4)

$N$ represents the lapse function which measures the proper time of the
observers traveling along the world line, $N^{i}$ is the shift vector that
measures the displacement of the observers between the spatial slices and
$\gamma_{ij}$ is the spatial metric.

The KG equation is a covariant equation whose origin lies in quantum field
theory. We can obtain a Schrödinger equation, starting from equation (2) with
the potential in Eq.(3), using the metric (4) and transforming the scalar
field by $\Phi(t,\vec{x})=\Psi(t,\vec{x})e^{-i\omega t}$. Following [8] we
obtain

$\displaystyle
i\nabla^{0}\Psi-\frac{1}{2\omega}\Box_{G}\Psi+\frac{1}{2\omega}\left(\widetilde{m}^{2}+\lambda
n_{0}+V\right)\Psi$
$\displaystyle+\quad\frac{1}{2}\left(-\frac{\omega}{N^{2}}+i\,\Box_{G}\,t\right)\Psi$
$\displaystyle=$ $\displaystyle 0,$ (5)

being $\lambda$ the coupling parameter. Here $\omega=mc^{2}/\hbar$ is the
characteristic frequency of the scalar field. The D’Alembertian operator
$\Box_{G}=\nabla^{\mu}\nabla_{\mu}$ is associated to the metric (4), and
$\widetilde{m}$ stands for the mass in units where $c=\hbar=1$, i.e,
$\widetilde{m}=m^{2}c^{2}/\hbar^{2}$ (see [8]). We can interpret the function
$\Psi$ as a wave function analogously as in QM.

Beginning with Eq.(2) but now using the $\Psi$ variable, we obtain Eq.(5)
using the 3+1 metric (4) and the potential (3). Equation (5) can be
interpreted as the covariant generalization of the Schrödinger equation for
any curved space-time, (see[9] and [8]) where this equation in the weak field
limit reduces to the standard Schrödinger one. Hereafter, we use the Newtonian
geometry given by the Newtonian metric

$ds^{2}=-\left(1-\dfrac{2GM}{rc^{2}}\right)c^{2}dt^{2}+\left(1+\dfrac{2GM}{rc^{2}}\right)dx_{i}dx^{i},$
(6)

Newtonian gravity is known to be valid when the gravitational fields are weak,
that is $GM/rc^{2}<<1$. Using the Newtonian metric in Eq.(5) yields

$\dfrac{\hbar^{2}}{2m}\Box_{N}\Psi+\left(1+\dfrac{2U}{c^{2}}\right)^{-1}\left(i\hbar\dfrac{\partial\Psi}{\partial
t}+\dfrac{mc^{2}}{2}\Psi\right)-\dfrac{\hbar^{2}}{2m}V\Psi=0,$ (7)

where $U=-GM/r$ is the gravitational potential, hither the D’Alembertian
operator $\Box_{N}$ is related to the metric given by Eq.(6). Furthermore, we
do not consider self-interaction, here the contribution of the term $\lambda$
is negligible. We take into account that the evolution of this function is
small, thus the contribution of $\partial_{0}^{2}\Phi$ can be taken as null
because the Newtonian potential fulfills $U/c^{2}<<1$. Additionally, one can
ignore terms of equal or greater order than
$\left(\dfrac{2U}{c^{2}}\right)^{2}$. With all this in mind, the linearization
of the generalized Schrödinger equation (7) gives rise to the following
equation

$-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+V\Psi+mU\Psi+\left(\dfrac{2U}{c^{2}}V-\dfrac{2\hbar^{2}U}{mc^{2}}\nabla^{2}\right)\Psi=i\hbar\dfrac{\partial\Psi}{\partial
t}.$ (8)

Henceforth, we are going to work with the Laplacian operator
$\nabla^{2}=\nabla\cdot\nabla$ in flat space, specially for the examples in
the following chapters where we use spherical symmetry. In other words,
equation (8) comes from the KG equation in a curved space-time immersed in a
weak gravitational field, which is described by a Newtonian geometry.

Focusing on the comparison of the traditional Schrödinger equation plus a
gravitational potential, we note that now there are two additional terms
inside the parenthesis in Eq.(8). These terms were not simply added in the
Schrödinger equation, they appear from the covariant meaning of the equation.
From a qualitative point of view, this means that the QM version of the
interactions between particles fulfills the Schrödinger equation, while the GR
version of these interactions fulfills the generalized Schrödinger Eq.(8).
This difference is the main idea of this work. In what follows, we calculate
the quantum quantities for different external potentials of well known
problems in QM and compare them with those corresponding to GR. For the
subsequent chapters our equation of motion will be given by Eq.(8).

With the goal of testing EEP in a quantum region, we are going to show in the
subsequent chapters distinct calculations about well known examples in QM. In
them, the correction terms due to the curvature of space-time which were
introduced in the KG covariant equation derived in Eq.(8) are going to appear.
To compare the cases with and without a gravitational source, the extra terms
in Eq.(8) will be taken as perturbations in the Schrödinger equation, for this
reason we decide to opt for the QM formalism, using perturbation theory to
give a clearer comparison between the cases with and without gravitational
field. The results of the gravitational field contribution have been well
studied in the standard literature.

##  3 Free Particle

Firstly, we consider a free scalar particle with mass $m$ under the influence
of a gravitational field generated by a source of mass $M$. Using an external
potential $V_{free}=0$ in the equation of motion (8), we have that

$-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+mU\Psi-\dfrac{2\hbar^{2}U}{mc^{2}}\nabla^{2}\Psi=i\hbar\dfrac{\partial\Psi}{\partial
t},$ (9)

we recall that the gravitational potential is defined by $U=-GM/r$ and that an
extra term $-\dfrac{2\hbar^{2}U}{mc^{2}}\nabla^{2}\Psi$ appears in the
Schrödinger equation, although the treatment on these equations will be in the
QM formalism. Using perturbation theory, from the previous equation we can
write a principal Hamiltonian operator $\hat{H}_{0}$ and a perturbed
Hamiltonian operator $\hat{H}_{p}$ in the following way

$\displaystyle\hat{H}_{0}\Psi=-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+mU\Psi=-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi-\dfrac{GMm}{r}\Psi,$
(10)
$\displaystyle\hat{H}_{p}\Psi=-\dfrac{2\hbar^{2}U}{mc^{2}}\nabla^{2}\Psi=\dfrac{4U}{c^{2}}(E_{n}^{(0)}-mU)\Psi.$
(11)

In general, to find the corrections to eigenvalues of energy due to a
perturbation in QM, the following expression is used

$E_{n}=E_{n}^{(0)}+\bra{\psi^{(0)}_{n}}\hat{H}_{p}\ket{\psi^{(0)}_{n}}+\sum_{m\neq
n}\dfrac{|\bra{\psi^{(0)}_{m}}\hat{H}_{p}\ket{\psi^{(0)}_{n}}|^{2}}{E_{n}^{(0)}-E_{m}^{(0)}}+...,$
(12)

we can associate the Eq.(12) as a series of contributions of higher order
correction of energies $E_{n}=E_{n}^{(0)}+E_{n}^{(1)}+E_{n}^{(2)}+...$, where
$E_{n}^{(j)}$ is the $j$th-order correction of the eigenvalues in the $n$th-
state of energy, hence we can say that the first-order correction is given by
$E_{n}^{(1)}=\bra{\psi^{(0)}_{n}}\hat{H}_{p}\ket{\psi^{(0)}_{n}}$. The zero-
order correction for eigenvalues of energy $E_{n}^{(0)}$ and the
eigenfunctions are the well-known exact solutions of QM (without gravitational
field). Equation (12) gives the correction for a non-degenerated quantum
system, though first-order correction is valid for both cases (degenerate and
non degenerate systems). We do not present an expression for the second order
correction in a degenerate system because the corrections we make are at most
of first-order. Nevertheless, such a case can be found in standard QM
textbooks.

Going back to our example of a free scalar particle inside a gravitational
field, the first order correction of energy using the perturbed Hamiltonian
from the hydrogen atom-like problem in QM is

$\displaystyle E_{n}$ $\displaystyle\approx
E^{(0)}_{n}\left(1-\dfrac{4GM}{\rho_{0}c^{2}n^{2}}+...\right),$ (13)
$\displaystyle=E^{(0)}_{n}\left(1+\dfrac{8E^{(0)}_{n}}{mc^{2}}+...\right),$

being $E^{(0)}_{n}$ the well known energy for the hydrogen atom, that is

$E^{(0)}_{n}=-\dfrac{(GM)^{2}m^{3}}{2\hbar^{2}n^{2}}=-\dfrac{GMm}{2\rho_{0}n^{2}},$
(14)

where $\rho_{0}=\hbar^{2}/(GMm^{2})$ is the Bohr radius for the gravitational
case. Thus, we expect that the gravitational field modifies the energy of a
free particle in a quadratic level, suppressed by the rest energy of the boson
particle. This result is surprising for an ultra-light dark matter boson
[1][10], because this model postulates a boson particle with a mass of the
order of $10^{-22}$eV$/c^{2}$. With such a mass the self-gravitation effects
of the boson field are important in a system of particles, a feature that a
heavy boson system does not present.

##  4 Isotropic Harmonic Oscillator

Another important example, not only in QM but in physics as a whole, is the
study of the harmonic oscillator potential. With this in mind, we analyze the
case of potential $V_{osc}$ for an isotropic harmonic oscillator. This
analysis can be done in two ways. The first one is to start from Eq.(8) with
the principal potential given by the gravitational type $U=-GM/r$ and taking
the isotropic harmonic oscillator $V_{osc}=\dfrac{1}{2}m\omega_{0}^{2}r^{2}$
as perturbation. The other way is to regard the principal Hamiltonian like as
that of an isotropic harmonic oscillator, while the perturbation is taken from
the gravitational potential. Therefore, equation (8) with the potential
$V_{osc}$, transforms into

$-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+mU\Psi+\dfrac{1}{2}m\omega_{0}^{2}r^{2}\Psi+\left[\dfrac{2U}{c^{2}}\left(\dfrac{1}{2}m\omega_{0}^{2}r^{2}\right)-\dfrac{2\hbar^{2}U}{mc^{2}}\nabla^{2}\right]\Psi=i\hbar\dfrac{\partial\Psi}{\partial
t}.$ (15)

###  4.1 Harmonic Oscillator inside a Gravitational Field

We start with the first cases exposed previously, we suppose that one has an
isotropic harmonic oscillator immersed in a gravitational field, that means,
$V_{osc}<<U$. To solve this problem we can take the principal Hamiltonian
operator $\hat{H}_{0}$ with the gravitational part and the perturbed
Hamiltonian $\hat{H}_{p}$ in the following way

$\displaystyle\hat{H}_{0}\Psi$
$\displaystyle=-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi-\dfrac{GMm}{r}\Psi,$ (16)
$\displaystyle\hat{H}_{p}$
$\displaystyle=\dfrac{1}{2}m\omega_{0}^{2}r^{2}-\dfrac{GMm\omega_{0}^{2}r}{c^{2}}+\dfrac{4GME^{(0)}_{n}}{rc^{2}}.$
(17)

We are interested in the wave function with spherical symmetry
$\Psi=\Psi(t,r,\theta,\phi)$. Thus, we apply the separation of variables
method for $\Psi=R_{nl}(r)Y_{lj}(\theta,\phi)\exp(-\dfrac{iE_{n}}{\hbar}t)$,
where $Y_{lj}$ are the spherical harmonics and $R_{nl}(r)$ is the radial
function for the hydrogen atom problem. Here $n,l$, and $j$ play the role of
quantum numbers as in QM. The $\hat{H}_{0}$ Hamiltonian contains the well-
known solutions of the eigenvalues from the hydrogen atom problem in terms of
the recurrence relation for powers of $r$. It can be shown that the correction
for first order of energy from Eq.(12) is given by

$\displaystyle E_{n}=$ $\displaystyle
E^{(0)}_{n}\left[1-\dfrac{8E^{(0)}_{n}}{mc^{2}}-\dfrac{\omega_{0}^{2}\rho_{0}^{2}}{c^{2}}(3n^{2}-l(l+1))\right]$
(18)
$\displaystyle+\dfrac{1}{4}m\omega_{0}^{2}\rho_{0}^{2}\left[n^{2}(5n^{2}+1-3l(l+1))\right],$

where $E^{(0)}_{n}$ is given by Eq.(14). Note that if $\omega_{0}=0$, we
return to the case of a free particle on a gravitational field. Observe that
as in the previous case, the modifications due to the gravitational field are
of second order, but now, an additional term is added which is proportional to
the mass and the frequency $\omega_{0}$. In this case, the second term of the
contributions of the perturbations of the gravitational potential due to the
harmonic oscillator are negligible for ultra-light masses. Nevertheless, if it
is a massive boson then the quadratic contributions are not important. In any
case, for any boson mass there is a contribution of the harmonic oscillator
that must be taken into account.

###  4.2 Gravitational Field inside Harmonic Oscillator

On the other hand, assuming the gravitational field as a perturbation in an
isotropic harmonic oscillator with spherical symmetry, the principal
Hamiltonian operator $\hat{H}_{0}$ is given by

$\displaystyle\hat{H}_{0}\Psi$
$\displaystyle=-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+\dfrac{1}{2}m\omega_{0}^{2}\left[\left(r-\dfrac{GM}{c^{2}}\right)^{2}-\left(\dfrac{GM}{c^{2}}\right)^{2}\right]\Psi,$
$\displaystyle\approx-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+\dfrac{1}{2}m\omega_{0}^{2}r^{2}-\Psi-\dfrac{1}{2}m\omega_{0}^{2}\left(\dfrac{GM}{c^{2}}\right)^{2}\Psi.$
(19)

Since the quantum system is far from the source, it is possible to do the
previous approximation. For the perturbed Hamiltonian $\hat{H}_{p}$ we have

$\hat{H}_{p}=-\dfrac{GMm}{r}+\dfrac{4GME^{(0)}_{n}}{rc^{2}}.$ (20)

The principal Hamiltonian is that of an isotropic harmonic oscillator with
spherical symmetry whose eigenfunctions are well known from QM. These
solutions are obtained after applying the separation of variables method, just
as in the previous case
$\Psi_{nklj}(t,r,\theta,\phi)=R_{kl}(r)Y_{lj}(\theta,\phi)\exp(-iE_{n}t)$.
Here $R_{nl}(r)$ is the radial function for an isotropic harmonic oscillator
$R_{kl}(r)=r^{l}e^{-\gamma r^{2}}L^{(l+1/2)}_{k}(2\gamma r^{2})$, with
$\gamma=\dfrac{m\omega}{2\hbar}$ and $L^{p}_{q}(x)$ being the generalized
associated Laguerre polynomials. The set $(n,k,l,j)$ become the quantum
numbers for the isotropic harmonic oscillator with spherical symmetry from QM.
Thus, the first order correction for the energy from Eq.(12) is given by

$E_{n}=\hbar\omega_{0}\left(n+\dfrac{3}{2}\right)-\dfrac{1}{2}m\omega_{0}^{2}\left(\dfrac{GM}{c^{2}}\right)^{2}-GMm\left[1-\dfrac{4E^{(0)}_{n}}{mc^{2}}\right]\left\langle\dfrac{1}{r}\right\rangle,$
(21)

where $E^{(0)}_{n}=\hbar\omega_{0}\left(n+\dfrac{3}{2}\right)$ is a well known
result from QM. Also note that there is a degeneration of these numbers since
$n=2k+l$. A more general solution of $\left\langle\dfrac{1}{r}\right\rangle$
was found in [11], that for the case we are discussing reduces to the
expression

$\displaystyle\left\langle\dfrac{1}{r}\right\rangle=$
$\displaystyle\sqrt{\dfrac{m\omega_{0}}{\hbar}}\Gamma(l+1)[\dfrac{1}{2}(n-l-1)]!\times$
(22)
$\displaystyle\sum_{t}\dfrac{(-1)^{t}}{[1/2(n-l-1)-t]!\Gamma(1/2(2l+1)+t+1)}\binom{-1/2}{t}^{2},$

where $\Gamma(z)$ is the Gamma function
$\Gamma(z)=\int^{\infty}_{0}t^{z-1}\exp(-t)dt$. When only the first term is
taken from the sum of Eq.(22), we obtain the energy value

$\displaystyle E_{n}=$
$\displaystyle\hbar\omega\left(n+\dfrac{3}{2}\right)-\dfrac{1}{2}m\omega_{0}^{2}\left(\dfrac{GM}{c^{2}}\right)^{2}$
$\displaystyle-
GMm\sqrt{\dfrac{m\omega_{0}}{\hbar}}\left[1-\dfrac{4E^{(0)}_{n}}{mc^{2}}\right]\Gamma(l+1)[\dfrac{1}{2}(n-l-1)]!.$
(23)

Note that if $G=0$, we return to the solution for an isotropic harmonic
oscillator with spherical symmetry without gravitational field. It is peculiar
that the Schwarzschild radius $r_{sch}$ is obtained in a very natural way.

The two cases we have analyzed in this section are extreme, and correspond to
those where the gravitational field is much more intense than the harmonic
oscillator and vice-versa. The case where the two potentials are comparable is
much more complex and we leave it for a future work.

##  5 Infinite Spherical Well

In this section we continue discussing well known examples from QM with the
novelty of the presence of a gravitational field. We now deal with the problem
of an infinite spherical well barrier $V_{inf}(r)$ that has two regions, this
problem is commonly used in experimental verification or applications of QM.
The barrier potential is given by

$V_{inf}(r)=\left\\{\begin{array}[]{ll}0\ \ \ \text{if}\ \ \ 0<r<a,\\\ \infty\
\ \ \text{otherwise}.\\\ \end{array}\right.$ (24)

We are only interested in studying the region where $0<r<a$, since outside of
this region the wave function is zero, thus the probability to find a particle
in the $r>a$ is null. The equation of motion (8) in the region of interest is

$-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+mU\Psi-\dfrac{2\hbar^{2}U}{mc^{2}}\nabla^{2}\Psi=i\hbar\dfrac{\partial\Psi}{\partial
t}.$ (25)

We can choose a principal Hamiltonian operator $\hat{H}_{0}$ from the motion
equation, where

$\hat{H}_{0}\Psi=-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi=E^{(0)}\Psi.$ (26)

The zero-order correction of the energy is then
$E^{(0)}_{ln}=\dfrac{\hbar^{2}}{2m}\dfrac{q_{ln}^{2}}{a^{2}}$. We can define
the perturbed Hamiltonian $\hat{H}_{p}$ from the KG equation

$\displaystyle\hat{H}_{p}=-\dfrac{GMm}{r}\left(1+\dfrac{4E^{(0)}}{mc^{2}}\right).$
(27)

The first-order correction of the energy $E^{(1)}$ can be calculated using the
zero-order correction of the eigenfunction
$\Psi_{nlk}^{(0)}(r,\theta,\phi)=A_{ln}j_{l}\left(\dfrac{q_{ln}}{a}r\right)Y_{lj}(\theta,\phi)$.
Here $q_{ln}$ is n-th root of the Bessel spherical functions $j_{l}(x)$ and
$A_{ln}$ is the constant of normalization

$A_{ln}^{2}=\dfrac{2}{a^{3}[j_{l+1}(q_{ln})]^{2}}.$ (28)

Therefore

$E_{ln}^{(1)}=-GMm\left(1+\dfrac{4E^{(0)}}{mc^{2}}\right)\left\langle\dfrac{1}{r}\right\rangle,$
(29)

where, from perturbation theory we have

$\left\langle\dfrac{1}{r}\right\rangle=A_{ln}^{2}\int_{0}^{a}\absolutevalue{j_{l}\left(\dfrac{q_{ln}}{a}r\right)}^{2}rdr.$
(30)

Unfortunately, it is not possible to solve the last integral with analytic
methods, thus we will integrate it numerically. In general, there exists for
each state $n=2l+1$ degeneration, thus for $l=0$, we have that
$j_{0}(x)=\sin(x)/x$, whose n-th root is $q_{0n}=n\pi$ and the normalization’s
constant is $A_{01}=\sqrt{2/a}$. Hence

$\left\langle\dfrac{1}{r}\right\rangle\approx\dfrac{2a}{\pi^{2}}(1.218),$ (31)

Now, for $l=1$ the first excited state is three-fold degenerate, which means
we need the first three roots of
$j_{1}(x)=\dfrac{\sin(x)}{x^{2}}-\dfrac{\cos(x)}{x}$. The roots are
$q_{11}\approx 4.49340$, $q_{12}\approx 7.72525$ and $q_{13}\approx 10.90412$.
Therefore for $n=1$

$\left\langle\dfrac{1}{r}\right\rangle\approx
A_{11}^{2}\left(\dfrac{a}{q_{11}}\right)^{2}(0.4124),$ (32)

for $n=2$

$\left\langle\dfrac{1}{r}\right\rangle\approx
A_{12}^{2}\left(\dfrac{a}{q_{12}}\right)^{2}(0.4590),$ (33)

and for $n=3$

$\left\langle\dfrac{1}{r}\right\rangle\approx
A_{13}^{2}\left(\dfrac{a}{q_{13}}\right)^{2}(0.4778).$ (34)

We can continue this process for the next excited states, as in the previous
cases. If we make $G=0$, we return to solutions for QM without gravitational
field.

##  6 Spherical Potential Barrier

The problem of square well potential with certain symmetry (spherical,
cartesian or cylindrical) is important for some experiments of quantum
systems. In this section, we study a square well barrier with spherical
symmetry. Similarly as in the previous sections, we analyze the case of QM for
a square well potential with space-time curvature. We use the Newtonian metric
from (6), so the equation of motion (8) transforms into

$-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+mU\Psi+V_{B}\left(1+\dfrac{2U}{c^{2}}\right)\Psi-\dfrac{4U}{c^{2}}\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi=i\hbar\dfrac{\partial\Psi}{\partial
t}$ (35)

where again $U=-GM/r$ is the gravitational potential. We take the Laplacian
operator $\nabla^{2}$ in spherical coordinates and the potential $V_{B}$ as

$V_{B}(r)=\left\\{\begin{array}[]{ll}-U_{0}\ \ \ \text{if}\ \ \ r<a,\\\ 0\ \ \
\ \ \ \ \text{if}\ \ \ r>a,\end{array}\right.$ (36)

Thus, from Eq.(35) we can identify a principal Hamiltonian operator
$\hat{H}_{0}$

$\hat{H}_{0}\Psi=-\dfrac{\hbar^{2}}{2m}\nabla^{2}\Psi+V_{B}\Psi=E^{(0)}\Psi.$
(37)

The perturbed Hamiltonian $\hat{H}_{p}$ can be defined from Eq.(35)

$\hat{H}_{p}=-\dfrac{GMm}{r}\left(1+\dfrac{4E^{(0)}}{mc^{2}}-\dfrac{2V_{B}}{mc^{2}}\right)$
(38)

In general, we can find the fist-order correction of energy from Eq.(12) with
the perturbed Hamiltonian operator in Eq.(37). This yields

$E^{(1)}=-GMm\left(1+\dfrac{4E^{(0)}}{mc^{2}}-\dfrac{2V_{B}}{mc^{2}}\right)\left\langle\dfrac{1}{r}\right\rangle.$
(39)

The case where $E<0$ shows the quantum nature of the system due to the fact
that the energy spectrum is discrete. Potential $V_{B}$ defines naturally two
regions, $Region\ I$ ($r<a$) and $Region\ II$ ($r>a$). Both regions without
gravitational field are well-known. For $Region\ I$ the first-order correction
of energy $E^{(1)}_{I}$ is given by

$E^{(1)}_{I}=-GMm\left(1+\dfrac{4E_{I}^{(0)}}{mc^{2}}+\dfrac{2U_{0}}{mc^{2}}\right)\left\langle\dfrac{1}{r}\right\rangle_{I},$
(40)

where the zero-order correction of the eigenvalue is
$E_{I}^{(0)}=\dfrac{\hbar^{2}}{2m}(\gamma_{ln})^{2}$ and the zero-order
correction eigenfunction reads
$\Psi_{lnj}(r,\theta,\phi)=R_{ln}(r)Y_{lp}(\theta,\phi)$. As usual,
$Y_{lp}(\theta,\phi)$ are the spherical harmonic functions and
$R_{ln}(r)=A_{ln}j_{l}(\gamma_{ln}r)$ is the radial solution, such that
$j_{l}(x)$ are the spherical Bessel functions. Also $k_{1}=\gamma_{ln}$ is the
n-th solution of the transcendental equation due to the boundary and
continuity condition given by

$\dfrac{1}{h_{l}^{(1)}(ik_{2}r)}\dfrac{dh_{l}^{(1)}(ik_{2}r)}{dr}|_{r=a}=\dfrac{1}{j_{l}(ik_{1}r)}\dfrac{dj_{l}(ik_{1}r)}{dr}|_{r=a}.$
(41)

For $l=0$, it reduces to the transcendental equation

$-k_{2}=k_{1}\cot(k_{1}a).$ (42)

In the limit $|E|<<U_{0}$, we return to the solution for the first root. When
$l=0$ we recover the same result as in the last section, namely
$k_{1}a\approx\pi/2$. In general for Region I, we need to integrate

$\left\langle\dfrac{1}{r}\right\rangle_{I}=A_{ln}^{2}\int^{a}_{0}\absolutevalue{j_{l}\left(\dfrac{\sigma_{ln}}{a}r\right)}^{2}rdr,$
(43)

where $\sigma_{ln}=a\gamma_{ln}$. If we define the parameter
$\eta=\sigma_{ln}/q_{ln}$ that compares the n-th solution of the
transcendental equation with the n-th root, we see that when $\eta=1$ we
return to case of Section 5. However, the solution of this integral should be
calculated using numerical methods.

In $Region\ II$, the zero-order correction is given by

$E_{II}^{(0)}=\dfrac{\hbar^{2}}{2m}(\gamma^{*}_{ln})^{2}=\dfrac{\hbar^{2}}{2M}\left(\dfrac{\sigma^{*}_{ln}}{a}\right)^{2},$
(44)

where we have introduced the new parameters
$\sigma^{*}_{ln}=a\gamma^{*}_{ln}$, and $\eta^{*}=\gamma^{*}_{ln}/q_{ln}$. The
first-order correction is similar to that of $Region\ I$

$E^{(1)}_{II}=-GMm\left(1+\dfrac{4E_{II}^{(0)}}{mc^{2}}\right)\left\langle\dfrac{1}{r}\right\rangle_{II},$
(45)

with the eigenfunction
$\Psi_{lnj}(r,\theta,\phi)=R_{ln}(r)Y_{lj}(\theta,\phi)$. Nevertheless, the
radial function has a new form
$R_{ln}(r)=Bh_{l}^{(1)}(i\gamma_{ln}^{*}r)=Bj_{l}(i\gamma_{ln}^{*}r)+iBn_{l}(i\gamma_{ln}^{*}r)$,
where $B$ is a constant of normalization, $h_{l}^{(1)}(x)$ are the spherical
Hankel functions of the first kind, $n_{l}(x)$ are the spherical Neumann
function and $k_{2}=\gamma_{ln}^{*}$ is the solution of the transcendental
equation (41). Therefore

$\displaystyle\left\langle\dfrac{1}{r}\right\rangle_{II}=$ $\displaystyle
B^{2}\int_{a}^{\infty}\absolutevalue{h_{l}^{(1)}\left(i\gamma^{*}_{ln}\right)}^{2}rdr$
$\displaystyle=$ $\displaystyle
B^{2}\int_{a}^{\infty}\left(\absolutevalue{j_{l}(i\gamma_{ln}^{*}r)}^{2}-\absolutevalue{n_{l}(i\gamma_{ln}^{*}r)}^{2}\right)rdr,$
(46)

This is a general solution of this perturbation, and if we want to solve this
integral, we need to set every parameter for a specific case. As expected,
just like in the previous cases, if $G=0$ we return to the solutions without a
gravitational field.

##  7 Conclusions

Throughout the course of this work we studied the KG equation in a weak
gravitational field for different external potentials with the objective of
understanding the quantum effects of a boson gas on a gravitational field.
Typical examples of QM were analyzed featuring the addition of space-time
curvature (or gravitational effects). Starting from the most general equation
for bosons in Quantum Field Theory in curved space-times, we found a
generalized Schrödinger equation that is simply the KG covariant one. To solve
the differential equation, we identified the principal and perturbed
Hamiltonian operator in each case, and compared them with the well-known
results in QM. Each example was worked out on an inertial frame. This is an
important aspect to highlight due to the main idea of this work. We expect to
obtain the same results when gravitational effects are measured on a quantum
system in the laboratory. This quantum system (with scalar particles) will be
on a non-inertial frame, where we predict that the Einstein’s equivalence
principle gives us a correspondence between experimental and theoretical
results.

These results let us find the limit, where we could measure quantum
gravitational effects, namely $2\alpha\,mM/m_{pl}^{2}\sim 1$. For this
analysis we could be able to apply our results in micro black holes scale[7].
For example, if we consider a mass of a scalar particle $m$ as the mass of the
electron, we obtain that the gravitational mass $M$ that affects the electron
by quantum gravitational effects is $\sim 10^{16}$kg. In the same way, a
$M\sim 10^{13}$kg could affect a particle with a proton mass. If we think on
the easiest non-inertial frame, we could think on a rotating system, for which
there would not be a real mass $M$, but rather an effective mass given by
angular frequency $\Omega$, where $\Omega^{2}=GM/r^{3}$. Using a detector to
$r=1$ meter, the corresponding gravity can be reached with a rotational wheel
spinning with an angular frequency of $\Omega\approx 1543$ rad/s=245 rev/s for
$M\sim 10^{16}$kg, and $\Omega\approx 25$ rad/s=3.9 rev/s for $M\sim
10^{13}$kg. However, for a mass $M\sim M_{\odot}$, we would need an angular
frequency of $\Omega\sim 10^{9}$rev/s, to obtain relativistic effects.

Analyzing the typical experiments on a harmonic oscillator [12] and on an
infinite well barrier [13] for a particle with an electron mass, the
correction due to the gravitational effects has, in both cases, a dominant
term which is given by $GMm\left\langle\dfrac{1}{r}\right\rangle$. For the
case of a harmonic oscillator with frequency $\omega_{0}\sim G$Hz and using
the value for the mass $M\sim 10^{16}$kg. The dominant term of the first-order
correction of the energy in this case is $\sim 10^{-5}E_{osc}^{(0)}$ from
Eq.(4.2), while other contributions in this equation are
$<10^{-9}E^{(0)}_{osc}$. On the other hand, for a particle with an electron
mass confined in an infinite well barrier of width $a\sim 10$nm, it is
possible to obtain that $E_{inf}^{(0)}\sim 10$eV. The dominant term in Eq.(29)
is $\sim 10^{-5}E_{inf}^{(0)}$ for the first-order correction of energy, and
the other term in this correction is $<10^{-20}E_{inf}^{(0)}$. Note that in
either cases, the first-order corrections of energy have the same order if we
compare them with their zero-order counterparts. With this analysis it is
possible to conclude that we can measure in a laboratory the effects of the
quantization of a weak gravitational field directly or using non-inertial
systems.

##  8 Acknowledgments

This work was partially supported by CONACyT México under grants CB-2011 No.
166212, CB-2014-01 No. 240512, Project No. 269652 and Fronteras Project 281;
Xiuhcoatl and Abacus clusters at Cinvestav, IPN; I0101/131/07 C-234/07 of the
Instituto Avanzado de Cosmología (IAC) collaboration (http:// www.iac.edu.mx).
O.G. acknowledge financial support from CONACyT doctoral fellowship. Works of
T.M. are partially supported by Conacyt through the Fondo Sectorial de
Investigación para la Educación, grant CB-2014-1, No. 240512

## References

  * [1] T. Matos and F. S. Guzman, “Scalar fields as dark matter in spiral galaxies,” Class. Quant. Grav., vol. 17, pp. L9–L16, 2000.
  * [2] L. Hui, J. P. Ostriker, S. Tremaine, and E. Witten, “Ultralight scalars as cosmological dark matter,” Phys. Rev., vol. D95, no. 4, p. 043541, 2017\.
  * [3] A. Ashtekar and P. Singh, “Loop quantum cosmology: A status report,” Class. Quant. Grav, vol. 28, p. 213001, 2011.
  * [4] E. Witten, “String theory dynamics in various dimensions,” Nuclear Physics, vol. 443, p. 85–126, 1995.
  * [5] R. A. Norte, M. Forsch, A. Wallucks, I. Marinković, and S. Gröblacher, “Platform for measurements of the casimir force between two superconductors,” Physical Review Letters, vol. 121, p. 030405, 2018.
  * [6] S. Bose, A. Mazumdar, G. W. Morley, H. Ulbricht, M. Toroš, M. Paternostroa, A. A. Geraci, P. F. Barker, M. S. Kim, and G. Milburn, “Spin entanglement witness for quantum gravity,” Physical Review Letters, vol. 119, p. 240401, 2017.
  * [7] S. Dimopoulos and G. Landsberg, “Black holes at the large hadron collider,” Physical Review Letters, vol. 87, p. 161602, 2001.
  * [8] T. Matos, B. T. Avilez, Ana, and P.-H. Chavanis, “Energy balance of a bose gas in curved spacetime,” 2016.
  * [9] P.-H. Chavanis and T. Matos, “Covariant theory of Bose-Einstein condensates in curved spacetimes with electromagnetic interactions: the hydrodynamic approach,” Eur. Phys. J. Plus, vol. 132, no. 1, p. 30, 2017.
  * [10] T. Matos and L. A. Urena-Lopez, “A Further analysis of a cosmological model of quintessence and scalar dark matter,” Phys. Rev., vol. D63, p. 063506, 2001.
  * [11] L. Armstrong, “O(2,1) and the harmonic oscillator radial function,” Journal of Mathematical Physics, vol. 12, no. 6, p. 956, 1971.
  * [12] W. M. Itano, C. R. Monroe, D. M. Meekhof, B. E. K. D. Leibfried, and D. J. Wineland, “Quantum harmonic oscillator state synthesis and analysis,” Atom Optics, vol. 2995, 1997.
  * [13] S. Chu, J.E.Bjorkholm, A. Ashkin, and A. Cable, “Experimental observation of optically trapped atom,” Physical Review Letters, vol. 57, no. 3, p. 314, 1986.


# Pure exploration in multi-armed bandits with low rank structure using
oblivious sampler

Yaxiong Liu
Graduate School of Information Science and Technology
Hokkaido University
Sapporo, Japan
<EMAIL_ADDRESS>
&Atsuyoshi Nakamura
Graduate School of Information Scienece and Technology
Hokkaido University
Sapporo, Japan
<EMAIL_ADDRESS>
Kohei Hatano
Department of Informatics
Kyushu University
Fukuoka, Japan
<EMAIL_ADDRESS>
Eiji Takimoto
Department of Informatics
Kyushu University
Fukuoka, Japan
<EMAIL_ADDRESS>

###### Abstract

In this paper, we consider the low rank structure of the reward sequence of
the pure exploration problems. Firstly, we propose the separated setting in
pure exploration problem, where the exploration strategy can not receive the
feedback of its explorations. Due to this separation, it requires that the
exploration strategy to sample the arms obliviously. By involving the kernel
information of the reward vectors, we provide efficient algorithms for both
time-varying and fixed cases with regret bound $O(d\sqrt{(\ln N)/n})$. Then,
we show the lower bound to the pure exploration in multi-armed bandits with
low rank sequence. There is an $O(\sqrt{\ln N})$ gap between our upper bound
and the lower bound.

_Keywords_ Pure exploration $\cdot$ Multi-armed bandits $\cdot$ low rank
structure $\cdot$ Oblivious sampling

##  1 Introduction

Pure exploration in multi-armed bandits is first introduced by Bubeck et al.
(2009) and has been further extensively researched in the academic community
and applied in the industry. This problem is based on the stochastic multi-
armed bandits and assumes that exploration is in the total process and
recommends only the last round $n$. This problem is described as follows: On
round $t\in[n]:$ the exploration strategy explores some arm $I_{t}\in[N]$ and
then receives the feedback $\bm{l}_{t}(I_{t})$ from the environment with some
underlying distribution. Then the recommendation strategy gives a
recommendation $J_{t}$. Note that this exploration process ends when the
environment determines. The goal of the algorithm is to guarantee that the
recommendation is optimised with respect to the _simple regret_ maximised.

As we mentioned, the performance of the algorithm is highly-related to the
exploration strategy, sampling the arms, and recommendation strategy,
selecting the arm. In this paper, we consider the oblivious sampling with a
structured reward sequence.

To the best knowledge of us, all the algorithms for pure exploration assume
that the exploration strategy samples the arms adaptively. It implies that the
exploration strategy can receive the feedback of its selection
$\bm{l}_{t}(I_{t})$ and update the sampling by rounds. However, in our
mentioned oblivious sampler, we assume that the feedback can be only received
by the recommendation strategy. It means that the exploration strategy is
fixed in advance of the learning process, while the recommendation strategy
can only give recommendations from the oblivious sample determined by the
exploration strategy.

Meanwhile, we involve the low rank structure of the reward sequence in our
work. The low rank structure reward has been first introduced by Hazan et al.
(2016) in the online learning framework. Specifically, the $N$ dimensional
reward vector $\bm{l}_{t}$ is dependent on $d$ factors ($d$-dimensional seed
vector) according to an $N\times d$ kernel matrix under the low rank
assumption. In the bandit problem, this setting is similar to linear bandits
(Cesa-Bianchi and Lugosi, 2012) and linear contextual bandits (Chu et al.,
2011), when the kernel is fixed or stochastic, respectively. Therefore, there
is a straightforward algorithm for pure exploration setting based on linear
contextual bandits algorithm when the exploration part can deploy the adaptive
sampler and the running round $n$ is given to the exploration strategy in
advance (Bubeck et al., 2009), when the kernel is known to the algorithm.
Otherwise, without the prior knowledge of $n$, there is an extra $\ln n$
factor incurred by doubling-trick (Besson and Kaufmann, 2018; Zimmert and
Seldin, 2019).

Using the oblivious sampler for pure exploration problem can be widely
utilised in practice scenarios. Concretely, in crowdsourcing (Ghezzi et al.,
2018), one user will deliver the tasks to the workers with a platform. In this
scenario, this user will provide the task $t$ on the platform. Then the
platform will select one of the $N$ workers to accomplish this task. Next,
this user receives the feedback from the work $I_{t}\in[N]$ and decides which
worker is the most appropriate for his tasks according to the historical
record. Finally, the process will end, when some worker leaves the platform.
In this case, the platform plays the role of the exploration part, and the
user plays the recommendation part. For some privacy reasons, the oblivious
sampler should be deployed, while the reward is confidential to the platform.
Simultaneously, on the low rank setting aspect, the rewards of these $N$
workers are depending on the ability of the workers and the task $t$ itself.
Mathematically, we can model the ability of the workers with an $N\times d$
matrix with respect to the seed vector (about the task). We assume that the
user can not parameterise the task into a vector, while the platform can
parameterise the task but does not know the content due to privacy reasons.
More generally, the kernel matrix, representing the ability of the workers,
can be fixed or stochastic.

Due to our assumption, the UCB or Thompson sampling can not be utilised, since
the exploration part can not receive the feedback of its selections. A core
problem in algorithm designing in this paper is to propose an oblivious
sampler for the exploration strategy, which can provide necessary information
to the recommendation strategy with respect to the low rank structure.
Therefore, we propose firstly an efficient algorithm for pure exploration in
multi-armed bandits with stochastic kernels. In this algorithm, the
exploration strategy samples the arms uniformly in each round. From the
feedback of the exploration arm, the recommendation strategy constructs an
unbiased estimator to the seed vector and recommends the estimated best arm
with the averaged estimated seed vectors and the kernel matrices. By some
restrictions to the kernel matrix and seed vector, our proposed algorithm
achieves the regret bound as $O\left(d\sqrt{\frac{\ln N}{n}}\right)$.

Next, we consider the fixed kernel case by releasing the range restriction on
the seed vector and the kernel matrix. By involving the Bary-centric spanner
(Awerbuch and Kleinberg, 2004), the exploration strategy focuses on exploring
$d$ “important arms” from the total $N$ fixed arms during the learning process
one by one on each round. Then the recommendation strategy can estimate the
seed vector according to the feedback and the corresponding arms. In this
designed algorithm, the regret bound is as same as the stochastic case.

Finally, we show a lower bound to the pure exploration problem with low rank
structure as $\Omega\left(\frac{d}{\sqrt{n}}\right)$. There is still a
$\sqrt{\ln N}$ gap for the separated setting.

Main contributions: In this paper, we focus on the pure exploration problem in
multi-armed bandits utilising oblivious sampler. Concretely, we can summarise
as follows:

  * •

We consider the low rank reward sequence in pure exploration problem. We
propose the algorithms for fixed and stochastic kernels respectively. For the
latter case, our algorithm guarantees an upper bound as
$O\left(\sqrt{\frac{d^{2}\ln N}{n}}\right)$ by sampling the arms uniformly.
For the former case, our proposed algorithm achieves the same regret bound
with less restriction on the range of seed vectors and kernel matrix. In this
algorithm, we need only obtain the Bary-centric spanner at the beginning of
the algorithm and sample the exploration according to these “important" arms
on each round.

  * •

We demonstrate a lower bound $\Omega\left(\sqrt{\frac{d\ln N}{n}}\right)$ for
pure exploration problem with low rank structure. It implies that our proposed
upper bound is near-optimal.

Here we conclude our contribution in the following chart:

Table 1: Comparison with our work and previous works | Fixed kernel | Stochastic kernel
---|---|---
Oblivious sampler |  $O\left(\frac{d\sqrt{\ln N}}{\sqrt{n}}\right)$ $\Omega\left(\sqrt{\frac{d\ln N}{n}}\right)$ |  $O\left(\sqrt{\frac{d^{2}\ln N}{n}}\right)$ $\Omega\left(\sqrt{\frac{d\ln N}{n}}\right)$
Adaptive sampler |  $\Theta\left(\sqrt{\frac{d\ln N}{n}}\right)$ Bubeck et al. (2009, 2012a) |  $O\left(\sqrt{\frac{d^{2}\ln n}{n}}\right)$ Bubeck et al. (2009); Chu et al. (2011)

Related Work: The setting of pure exploration with multi-armed bandits is
similar but different from the best arm identification problems (Jamieson and
Nowak, 2014; Madani et al., 2004). In the best arm identification problem, the
budget of exploration $n$ is one of the prior information to the algorithm,
while in the pure exploration problem, the stopping signal is given by the
environment arbitrarily.

Low rank sequence in prediction with expert advice can be seen as a full-
information setting for multi-armed bandits with low rank structure with the
fixed kernel. In a low rank setting, the $N$-dimensional reward vectors are
actually from a $d$-dimensional kernel space. A central work in the low rank
setting is to explore the $d$-dimensional seed vector during the learning
process. With the prior information about the kernel space, the regret bound
to Expert advice with low rank structure is $\Theta(\sqrt{dn})$, which is not
related to the dimensional of the reward vector.

Our low rank setting in multi-armed bandits can be seen as linear bandits or
linear contextual bandits with respect to the fixed or stochastic kernel
respectively. In the former case, Bubeck et al. (2012b); Dani et al. (2007)
provide an upper bound $O\left(\sqrt{dn\ln N}\right)$, and lower bound
$\Omega\left(d\sqrt{n}\right)$ to regret, respectively. In the latter case,
the upper bound is $O\left(\sqrt{\frac{d^{2}\ln N}{n}}\right)$ (Bubeck et al.,
2012b). Again, we need to emphasis, we can not directly utilise the existing
algorithm for linear (contextual) bandits, due to the oblivious sampling
setting, which is not concerned with traditional pure exploration research
(Bubeck et al., 2009).

##  2 Preliminaries

First of all, we define some notations used in this paper. We let $[n]$ denote
$\\{1,\cdots,n\\}$ for a positive integer $n$. A vector is denoted by a bold
letter and the $i$-th component of a vector $\bm{a}$ is denoted by
$\bm{a}(i)$. A matrix and its $i$-th row is denoted by a capital letter and
its corresponding small letter subscripted with $i$, respectively. For
example, the $i$-th row of matrix $U$ is denoted by $\bm{u}_{i}.$

For a positive integer $N$, we define $\Delta(N)$ as

$\Delta(N)=\left\\{\bm{x}:\sum_{i=1}^{N}\bm{x}(i)=1\quad\land\quad\bm{x}(i)\geq
0\quad\forall i\in[N]\right\\}.$ (1)

###  2.1 Pure exploration in multi-armed bandits

In this sub-section, let us have a review of the problem setting of “pure
exploration” in $N$-armed bandits problem proposed by Bubeck et al. (2009).

For each round $t=1,2,3,\cdots:$

  1. 1.

Algorithm chooses $\varphi_{t}\in\Delta(N)$ and pulls $I_{t}\in[N]$ according
to the distribution $\varphi_{t}$.

  2. 2.

Environment returns reward $\bm{l}_{t}(I_{t})$, where
$\bm{l}_{t}\in[-1,1]^{N}$.

  3. 3.

If the environment sends a stopping signal then

stopping time $n$ is set to the current time $t$ and

the algorithm outputs $J_{n}\in[N]$ and the game is over,

otherwise the game continues.

In this paper, we consider the stochastic bandits problem, where we assume
that the reward sequence $\bm{x}_{1},\bm{x}_{2},\cdots$ is an i.i.d random
variable sequence. Moreover, we let $\bm{\mu}$ denote that
$\mathbb{E}\left[\bm{x}_{t}\right]$ for all $t\in\mathbb{N}_{+}.$

The goal of the algorithm is to minimise the simple regret $r_{n}$, which is
defined as follows:

$r_{n}=\max_{i\in[N]}\bm{\mu}(i)-\bm{\mu}(J_{n}),$ (2)

where $n$ is the stopping time that is decided by the environment.

An algorithm for this problem can be determined by designing a sampling (or
allocation) strategy and a recommendation strategy. A sampling strategy
decides how to choose $\varphi_{t}$ at $t=1,2,\cdots$, and a recommendation
strategy decides how to choose $J$. Two types of sampling strategies are
considered. One is _oblivious_ and the other is _adaptive_. An oblivious
sampler chooses $\varphi_{t}$ independently of history
$I_{1},\bm{l}_{1}(I_{1}),\cdots,I_{t-1},\bm{l}_{t-1}(I_{t-1})$ while an
adaptive sampler chooses $\varphi_{t}$ depending on it. In this paper, we only
consider oblivious samplers as sampling strategies.

Bubeck et al. (2009) proposed a uniform allocation strategy and Empirical Best
Arm (EBA) recommendation strategy. It means that for each round $t$, the
algorithm will select the arm uniformly from $1$ to $N$ for $\varphi_{t}$ (on
round $t$ selecting arm $t\mod N$) and outputs

$J_{n}=\operatorname*{arg\,max}_{j\in[N]}\frac{1}{|T_{j}(n)|}\sum_{s\in
T_{j}(n)}\bm{l}_{s}(j)$ (3)

at the stopping time $n$, where $T_{j}(t)=\left\\{s:I_{s}=j,\forall
s\in[t]\right\\}$.

######  Theorem 1 (Bubeck et al. (2009)).

If we run the algorithm of pure exploration in $N$-armed bandits problem using
uniformly allocation and EBA recommendation strategies for $n$ rounds, the
simple regret $r_{n}$ is bounded as follows:

$r_{n}\leq O\left(\sqrt{\frac{N\ln N}{n}}\right).$

###  2.2 Low rank structure

We say that the reward sequence $\bm{x}_{1},\bm{x}_{2},\cdots$ is $d$-rank
reward sequence if and only if

$\mathrm{rank}([\bm{x}_{1},\cdots,\bm{x}_{T}])\leq d\text{ for all
}T\in\mathbb{N}_{+},$

where $[\bm{x}_{1},\cdots,\bm{x}_{T}]$ is a matrix whose $t$-th column is
$\bm{x}_{t}$. A $d$-rank reward sequence is said to have the low rank
structure when $d\ll N$. For a $d$-rank reward sequence
$\bm{x}_{1},\bm{x}_{2},\cdots$, there are a kernel matrix
$U\in\mathbb{R}^{N\times d}$ and $d$-dimensional vector sequence
$\bm{v}_{1},\bm{v}_{2},\cdots$ such that $\bm{x}_{t}=U\bm{v}_{t}$ for all
$t\in\mathbb{N}_{+}$. We call $\bm{v}_{t}$ the seed vector of the reward
vector $\bm{x}_{t}$. In our stochastic setting, seed vector sequence
$\bm{v}_{1},\bm{v}_{2},\cdots$ is an i.i.d. random variable sequence that
satisfies $\bm{v}_{t}\sim\mathcal{D}$, $U\bm{v}_{t}\in[-1,1]^{N}$ and
$\mathbb{E}[\bm{v}_{t}]=\bm{v}$ for some distribution $\mathcal{D}$, some
$d$-dimensional vector $\bm{v}$ and all $t\in\mathbb{N}_{+}$.

Furthermore, we extend the low-rank structure of the reward sequence from the
fixed kernel $U$ to the random kernel sequence $U_{1},U_{2},\cdots$. A reward
sequence $\bm{x}_{1},\bm{x}_{2},\cdots$ is said to have the low rank structure
for the i.i.d. random kernel sequence
$U_{1},U_{2},\cdots\in\mathbb{R}^{N\times d}$ with $d\ll N$ if there are seed
vector sequence $\bm{v}_{1},\bm{v}_{2},\cdots$ and a matrix
$U\in\mathbb{R}^{N\times d}$ such that $\bm{x}_{t}=U_{t}\bm{v}_{t}$ for all
$t\in\mathbb{N}_{+}$ and $\mathbb{E}[U_{t}]=U$. We let $\bm{u}_{t,i}$ denote
the $i$-th row of $U_{t}$, thus $\mathbb{E}[\bm{u}_{t,i}]=\bm{u}_{i}$ holds.
The seed vector sequence $\bm{v}_{1},\bm{v}_{2},\cdots$ is also assumed to be
an i.i.d. random variable sequence that satisfies $\bm{v}_{t}\sim\mathcal{D}$,
$U_{t}\bm{v}_{t}\in[-1,1]^{N}$ and $\mathbb{E}[\bm{v}_{t}]=\bm{v}$ for some
distribution $\mathcal{D}$, some $d$-dimensional vector $\bm{v}$ and all
$t\in\mathbb{N}_{+}$. Further we assume that the kernel matrices and the seed
vectors are independent, thus
$\mathbb{E}[\bm{x}_{t}]=\mathbb{E}[U_{t}]\cdot\mathbb{E}[\bm{v}_{t}]=U\bm{v}\in[-1,1]^{N}$.
We also assume that all rows of the kernel matrices $\bm{u}_{t,i}$ and
$\bm{u}_{i}$ belong to a domain $\mathcal{U}$. Note that the random kernel
setting includes the fixed kernel setting.

Finally, we assume that the kernel information $U_{t}$ is given to the
algorithm in advance on each round $t\in[T]$.

##  3 Main Result

In this section, we demonstrate the main results of our paper. In the first
sub-section, we give an algorithm for the stochastic kernel with oblivious
sampler. In the second sub-section, we design an algorithm for the fixed
kernel (low rank reward) case. We need emphasis that we constrain the
stochastic kernel and seed vector to obtain the desirable simple regret bound.
Finally, we show the lower bound of the pure exploration problem which
indicates that there is still a $O(\sqrt{\ln N})$ gap between the current
bounds.

###  3.1 Low rank reward with stochastic kernel

In this sub-section, we consider the pure exploration problem in multi-armed
bandits with the stochastic kernel. One of the central problems in the
separated setting is that the exploration strategy is only depended on the
kernel information instead of the feedback of the pulled arm in ordinary
setting. Once the exploration strategy receives the kernel information
$U_{t}$, the exploration strategy is requested to output an oblivious
distribution to sample the pulled arm $I_{t}$. A straightforward idea is to
explore the arms uniformly, if there is no specified structure upon the reward
sequence. With the assistance of the kernel information, in this part, we
proposed an efficient sampler by involving the John distribution over all arms
(Grötschel et al., 2012; Cesa-Bianchi and Lugosi, 2012).

Again, our goal is to minimise the simple regret defined as follows:

$r_{n}=\max_{i\in[N]}\bm{u}_{i}\cdot\bm{v}-\bm{u}_{J_{n}}\cdot\bm{v}.$ (4)

In principle, we can recommend the arm more effectively, if the recommendation
part can estimate the seed vector $\bm{v}_{t}$. Instead of recommending from
$N$-arms, the recommendation strategy performs well, if it is confronted to a
lower dimensional space, a $d$-dimensional action space. Firstly, we propose
the estimator of the seed vector $\bm{v}_{t}$ as follows:

$\hat{\bm{v}}_{t}=A_{t}^{-1}\bm{u}_{t,I_{t}}^{\top}\bm{x}_{t}(I_{t}),$ (5)

where
$A_{t}=\left[\sum_{i=1}^{N}\bm{p}_{t}(i)\bm{u}_{t,i}^{\top}\bm{u}_{t,i}\right]=\mathbb{E}_{I_{t}\sim\bm{p}_{t}}\left[\bm{u}_{t,I_{t}}^{\top}\bm{u}_{t,I_{t}}\right]$
for some exploration distribution $\bm{p}_{t}\in\Delta(N).$ Meanwhile, we see
that $\hat{v}_{t}$ is unbiased, since

$\mathbb{E}_{I_{t}\sim\bm{p}_{t}}[\bm{\hat{v}}_{t}]=\mathbb{E}_{I_{t}\sim\bm{p}_{t}}[A_{t}^{-1}\bm{u}_{t,I_{t}}^{\top}\bm{x}_{t}(I_{t})]=\mathbb{E}_{I_{t}\sim\bm{p}_{t}}[A_{t}^{-1}\bm{u}_{t,I_{t}}^{\top}\bm{u}_{t,I_{t}}\bm{v}_{t}]=\bm{v}_{t}.$
(6)

Since $\bm{v}_{t}$ is a random variable with respect to some underlying
distribution, we have that
$\mathbb{E}\left[\mathbb{E}_{I_{t}\sim\bm{p}_{t}}[\hat{\bm{v}}_{t}]\right]=\bm{v}$.

Thus, the recommendation strategy selects the arm $J_{n}$ by the best estimate
arm such that

$J_{n}=\operatorname*{arg\,max}_{i\in[N]}\left(\left(\frac{1}{n}\sum_{s=1}^{n}U_{s}\right)\left(\frac{1}{n}\sum_{s=1}^{n}\hat{\bm{v}}_{s}\right)\right)(i).$
(7)

Then we can demonstrate the algorithm for this low rank loss with stochastic
kernel as follows:

Algorithm 1 Algorithm for pure exploration in stochastic kernel bandits

0: A uniformly distribution
$\bm{p}_{t}=\left(\frac{1}{N},\cdots,\frac{1}{N},\cdots,\frac{1}{N}\right)$

for $t=1,2,\cdots$ do

Receive $U_{t}$ the kernel of round $t$ and sample the arm $I_{t}$ according
to distribution $\bm{p}_{t}$.

The recommendation receives the reward $\bm{x}_{t}$ and calculate
$\hat{\bm{v}}_{t}=A_{t}^{-1}\bm{u}_{t,I_{t}}^{\top}\bm{x}_{t}(I_{t}),$ (8)
where $A_{t}=\mathbb{E}_{\bm{p}_{t}}[(\bm{u}_{t,i})^{\top}(\bm{u}_{t,i})]$ .

if the environment sends a stopping signal then

Set $n$ to $t$.

Recommend
$J_{n}=\max_{j\in[N]}\left(\frac{1}{n}\sum_{s=1}^{n}\bm{u}_{s,j}\right)\left(\frac{1}{n}\sum_{s=1}^{n}\hat{\bm{v}}_{s}\right)$
and stop.

end if

end for

Note that the simple regret is based on the expectation of the kernel matrix
$U=\mathbb{E}[U_{t}],$ although it emerges not during the learning process.
Before we state our main result, let us introduce McDiarmid’s inequality
firstly.

######  Theorem 2.

Let $f:\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}\rightarrow\mathbb{R}$
satisfy the bounded difference property with bounds $c_{1},\cdots,c_{n}:$

$\forall
i\in[n]\sup_{x_{i}^{{}^{\prime}}\in\mathcal{X}_{i}}\left|f(x_{1},\cdots,x_{i},\cdots,x_{n})-f(x_{1},\cdots,x_{i}^{{}^{\prime}},\cdots,x_{n})\right|\leq
c_{i}.$

Consider independent random variable $X_{1},\cdots,X_{n}$ where
$X_{i}\in\mathcal{X}_{i},\forall i.$ Then for all $\epsilon>0$,

$\mathbb{P}\left[f(X_{1},\cdots,X_{n})-\mathbb{E}\left[f(X_{1},\cdots,X_{n})\right]\geq\epsilon\right]\leq\exp\left(-\frac{2\epsilon^{2}}{\sum_{i=1}^{n}c_{i}^{2}}\right)$
(9)

The main Theorem is given as follows:

######  Theorem 3.

In the pure exploration multi-armed bandits problem with time-varying kernel
$U_{t}\in\mathbb{R}^{N\times d}$ according to some underlying distribution. If
the exploration process is run by $n$ times with some exploration distribution
$\bm{p}_{t}$ and the recommendation strategy is defined as in Equation (7).
The simple regret $r_{n}$ defined in Equation (4) is bounded:

$\mathbb{E}[r_{n}]\leq O\left(\alpha\beta\sqrt{\frac{\ln N}{n}}\right),$ (10)

where
$\alpha=\max_{t}\left\\{\sup_{\bm{a},\bm{b}\in\mathcal{U}}\bm{a}^{\top}A_{t}^{-1}\bm{b}\right\\}$
and $\beta\geq\|\bm{u}_{t,i}\|\|\bm{v}_{t}\|_{\star}$ with respect to some
norm $\|\cdot\|$ and its dual norm $\|\cdot\|_{\star}$ for all $t\in[T]$ and
$i\in[N]$. In particular, if $\mathcal{U}$ is a finite subset of
$\\{0,1\\}^{d}$ we have further

$\mathbb{E}[r_{n}]\leq
O\left(d\max_{t}\\{\lambda_{\min}(A_{t})\\}\sqrt{\frac{\ln N}{n}}\right),$
(11)

if $\beta\leq 1$.

###### Proof.

We firstly bound the probability that the recommendation strategy does not
select the optimal arm. Hence, we denote that when $J_{t}=j$ and $j\neq
j^{\star}$ then

$\begin{split}&\mathbb{P}_{\\{(U_{s},\bm{v}_{s})\\}_{s=1}^{t}\sim\mathcal{D}^{t}}\left[J_{t}=j\right]\\\
&\leq\mathbb{P}_{\\{(U_{s},\bm{v}_{s})\\}_{s=1}^{t}\sim\mathcal{D}^{t}}\left[\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{u}_{s,j}}{t}\right>-\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{u}_{s,j^{\star}}}{t}\right>\geq
0\right]\\\
&=\mathbb{P}_{\\{(U_{s},\bm{v}_{s})\\}_{s=1}^{t}\sim\mathcal{D}^{t}}\left[\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{u}_{s,j}-\bm{u}_{s,j^{\star}}}{t}\right>-\left<\bm{v},\bm{h}_{j}\right>\geq-\left<\bm{v},\bm{h}_{j}\right>\right],\end{split}$
(12)

where $\bm{h}_{j}=\bm{u}_{j}-\bm{u}_{j^{\star}},$
$\bm{h}_{s,j}=\bm{u}_{s,j}-\bm{u}_{s,j^{\star}}$.

Set that

$f(X_{1},\cdots,X_{t})=\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{u}_{s,j}-\bm{u}_{s,j^{\star}}}{t}\right>_{H_{t}},$

where $X_{s}=(U_{s},\bm{v}_{s})\sim\mathcal{D}$, we have that
$\mathbb{E}[f(X_{1},\cdots,X_{t})]=\langle\bm{v},\bm{u}_{j}-\bm{u}_{j^{\star}}\rangle.$

On the other hand, $\forall s\in[t]$, we assume that $U_{s}$ and $\bm{v}_{s}$
are independent. So we have that

$\begin{split}&\mathbb{P}_{(U_{s},\bm{v}_{s})\sim\mathcal{D}}\left[\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{h}_{s,j}}{t}\right>-\langle\bm{v},\bm{h}_{j}\rangle\geq-\langle\bm{v},\bm{h}_{j}\rangle\right]\\\
&=\int_{U_{s}\in\mathcal{U},\forall
s\in[t]}\mathbb{P}_{\bm{v}_{s}\sim\mathcal{D}_{v}}\left[\left.\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{h}_{s,j}}{t}\right>-\langle\bm{v},\bm{h}_{j}\rangle\geq-\langle\bm{v},\bm{h}_{j}\rangle\right|U_{1},\cdots,U_{t}\right]d\mathcal{D}_{U}\\\
&\leq\max_{U_{1},\cdots,U_{t}}\mathbb{P}_{\bm{v}_{s}\sim\mathcal{D}_{v}}\left[...\right|U_{1},\cdots,U_{t}]\end{split}$
(13)

Therefore, for a fixed sequence of $\\{U_{1},\cdots,U_{t}\\}$ we have that

$\begin{split}&\left|f(X_{1},\cdots,X_{s},\cdots,X_{t})-f(X_{1},\cdots,X_{s}^{{}^{\prime}},\cdots,X_{t})\right|\\\
&\leq\left|\frac{1}{t}\left<\frac{\sum_{s=1}^{t}\bm{h}_{s,j}}{t},A^{-1}_{s}\bm{u}_{s,I_{s}}(\bm{u}_{s,I_{s}}(\bm{v}_{s}-\bm{v}_{s}^{\prime}))\right>\right|\\\
&\leq\frac{2}{t}\left(\frac{\sum_{s=1}^{t}\bm{h}_{s,j}}{t}\right)^{\top}A_{s}^{-1}\bm{u}_{s,I_{s}}\beta\\\
&\leq\frac{2}{t}\max_{\bm{a},\bm{b}\in\mathcal{U}}\bm{a}^{\top}A_{s}^{-1}\bm{b}\beta\leq
2\frac{\alpha}{t}\beta,\end{split}$ (14)

where the first inequality is due to $\forall\bm{l}_{t}\in[0,1]^{N},$
$\|\bm{u}_{t,i}\|\|\bm{v}_{t}\|_{\star}\leq\beta$ and third inequality is from
the the definition of $\alpha$ in the algorithm.

Next, due to the McDiarmid’s inequality, we have that for all $j\neq
j^{\star}$

$\begin{split}\mathbb{P}_{U,\bm{v}}[J_{t}=j]&\leq\max_{U_{1},\cdots,U_{t}}\mathbb{P}_{\bm{v}}\left[\left.\left<\frac{\sum_{s=1}^{t}\hat{\bm{v}}_{s}}{t},\frac{\sum_{s=1}^{t}\bm{h}_{s,j}}{t}\right>-\left<\bm{v},\bm{h}_{j}\right>\geq-\left<\bm{v},\bm{h}_{j}\right>\right|U_{1},\cdots,U_{t}\right]\\\
&\leq\exp\left(-\frac{2\times\langle\bm{h}_{j},\bm{v}\rangle^{2}}{\sum_{s=1}^{t}(\frac{\alpha\beta}{t})^{2}}\right)\\\
&\leq\exp\left(-\frac{2\times\langle\bm{h}_{j},\bm{v}\rangle^{2}t}{(\alpha\beta)^{2}}\right)\end{split}$

Furthermore, by defining
$\Delta_{j}=(\bm{u}_{j^{\star}}-\bm{u}_{j})\cdot\bm{v}=\bm{l}(j^{\star})-\bm{l}(j)$
we have:

$\begin{split}\mathbb{E}\left[r_{n}\right]&=\sum_{j=1}^{N}\Delta_{j}\mathbb{P}\left[J_{t}=j\right]\leq\sum_{j:\Delta_{j}>\epsilon}\Delta_{j}\mathbb{P}\left[J_{t}=j\right]+\sum_{j:\Delta_{j}\leq\epsilon}\mathbb{P}\left[J_{t}=j\right]\\\
&\leq\sum_{j:\Delta_{j}\geq\epsilon}\Delta_{j}\exp\left(-\frac{2\Delta_{j}^{2}n}{(\alpha\beta))^{2}}\right)+\epsilon\end{split}$
(15)

A function $f:x\rightarrow x\exp(-Cx^{2})$ is a decreasing function on
$[\frac{1}{\sqrt{2C}},1]$ for any $C>0$. Taking
$C=\frac{n}{2(\alpha\beta))^{2}}$ we obtain that

$\mathbb{E}\left[r_{n}\right]\leq\epsilon+(N-1)\epsilon\exp\left(-\frac{\epsilon^{2}n}{2(\alpha\beta))^{2}}\right),$
(16)

when $\epsilon\geq\frac{1}{\sqrt{\frac{n}{2(\alpha\beta)^{2}}}}$.
Particularly, we have that

$\mathbb{E}\left[r_{n}\right]\leq O\left(\alpha\beta\sqrt{\frac{\ln
N}{n}}\right),$ (17)

by setting $\epsilon=\sqrt{\alpha\beta\frac{2\ln N}{n}}.$

In particular, if $\bm{u}_{t,i}\in\\{0,1\\}^{d}$ we have that

$\max_{\bm{a},\bm{b}\in\mathcal{U}}\bm{a}^{\top}A_{t}^{-1}\bm{b}\leq\|\bm{a}\|_{2}\|\bm{b}\|_{2}\lambda_{\min}(A_{t})\leq
d\lambda_{\min}(A_{t})$ (18)

∎

######  Remark 1.

Cesa-Bianchi and Lugosi (2012) states several applications for binary case of
domain $\mathcal{U}$. For instance, $\lambda_{\min}(A_{t})$ can be lower
bounded by $\frac{1}{4}$, if $\|\bm{v}_{t}\|_{2}\leq 1$ and
$\bm{u}_{t,i}\in\\{0,1\\}^{d}$. It implies that our simple regret bound can
achieve $O\left(d\sqrt{\frac{\ln N}{n}}\right)$. See details in section 5.2 in
(Cesa-Bianchi and Lugosi, 2012).

###  3.2 Low rank reward with fixed kernel

In this part, we consider the pure exploration in multi-armed bandits with low
rank reward. The fixed kernel assumption can be seen as an easier case of
time-varying kernel case. In this part, we provide an algorithm with Bary-
centric spanner Awerbuch and Kleinberg (2004); Cesa-Bianchi and Lugosi (2012);
Dani et al. (2007) to sample the arms to explore. Our proposed algorithm can
achieve the regret bound $O\left(d\sqrt{\frac{\ln N}{n}}\right)$ without any
further constraints over the kernel matrix and the seed vectors.

In this sub-section, we denote the indices of the Bary-centric spanner as
$\\{i_{1},\cdots,i_{d}\\}\subseteq[N].$ The exploration strategy selects
$i_{j}$ if $t\mod j=0$ and the recommendation strategy is as follows:

$J_{t}=\operatorname*{arg\,max}_{j\in[N]}\bm{u}_{j}\cdot(V^{-1}\hat{\bm{l}}_{t})$
(19)

where

$\hat{\bm{l}}_{t}=\left(\frac{\sum_{s\in
T_{i_{1}}(t)}\bm{l}_{s}(i_{1})}{|T_{i_{1}}(t)|},\cdots,\frac{\sum_{s\in
T_{i_{d}}(t)}\bm{l}_{s}(i_{d})}{|T_{i_{d}}(t)|}\right),$ (20)

and $V\in\mathbb{R}^{d\times d}$ is defined later.

######  Theorem 4.

For a full rank matrix
$U=\left[\bm{u}_{1}^{\top},\cdots,\bm{u}_{N}^{\top}\right]^{\top}$, where
$\bm{u}_{i}\in\mathbb{R}^{d}$ is the $i$-th row vector, we can find a full
rank $d\times d$ matrix composed by
$V=[\bm{u}_{i_{1}}^{\top},\cdots,\bm{u}_{i_{d}}^{\top}]^{\top}$ such that

$\det(V)=\operatorname*{arg\,max}_{[i_{1},\cdots
i_{d}]\subset[N]}\left|\det\left([\bm{u_{i_{1}}}^{\top},\cdots,\bm{u}_{i_{d}}^{\top}]^{\top}\right)\right|.$
(21)

Then for all $i$, we can find a $d$-dimensional vector $\bm{w}\in[-1,1]^{d}$
such that $\bm{u}_{i}^{\top}=V\bm{w}$.

This theorem indicates the Bary-centric spanner
$\bm{u}_{i_{1}},\cdots,\bm{u}_{i_{d}}$ for the fixed kernel
$\\{\bm{u}_{1},\cdots,\bm{u}_{N}\\}.$

See proof in supplementary material.

Now we give our main result.

######  Theorem 5.

Running uniformly allocation to the selected
$\\{i_{1},\cdots,i_{d}\\}\subseteq[N]$ arms in Equation (21) for the low rank
structure and above mentioned recommendation strategy in Equation (19). We
have an upper bound to the simple regret after $n$ times exploration:

$\mathbb{E}\left[r_{n}\right]\leq O\left(\sqrt{\frac{d^{2}\ln N}{n}}\right).$
(22)

Proof sketch: The basic idea of proving Theorem 5 is similar to the previous
part. Due to the Bary-centric spanner and the McDiarmid’ s inequality, we can
bound the probability of selecting the “wrong" arm to recommend on the final
round. Concretely,

$\mathbb{P}[J_{t}\neq
j^{\star}]\leq\exp\left(-\frac{\langle\bm{u}_{j}-\bm{u}_{j^{\star}},\bm{v}\rangle^{2}\lfloor\frac{t}{d}\rfloor}{2d}\right).$

Then we follow the same analysis to the upper bound of the simple regret and
obtain our conclusion. See the detail of the proof in the Supplementary
material.

######  Remark 2.

When $d=N$, by a more refined analysis, we can recover the simple regret in
$O\left(\sqrt{\frac{N\ln N}{n}}\right).$ See more details in supplementary
material.

We give an efficient algorithm in the following part, which approximates the
Bary-centric spanner in polynomial times. Awerbuch and Kleinberg (2004)
provides an approximation algorithm for calculating the Bary-centric spanner
effectively. With the time cost $O(d\log_{C}d)$ the algorithm can output a
$d\times d$ matrix $\widehat{V}$ such that for any $\bm{u}_{i}\in U$ there
exists $\bm{w}\in[-C,C]^{d}$ where $\bm{u}_{i}^{\top}=\widehat{V}\bm{w}$.

Algorithm 2 $C$-approximate algorithm for pure exploration low rank bandits

0: An oracle $\mathcal{O}(U)=\widehat{V}$ as the $C$-approximation algorithm
for Bary-centric spanner.

When $t=0$ calculate $\widehat{V}=\mathcal{O}(U)$ and denote
$\widehat{V}=\left[\bm{u}_{i_{1}}^{\top},\cdots,\bm{u}_{i_{d}}^{\top}\right]^{\top}$,
where $\\{i_{1},\cdots,i_{d}\\}\subseteq[N]$.

for $t=1,\cdots,n$ do

Select arm $i_{s}$ when $s=t\mod d$ and $s\neq 0$; $i_{d}$, otherwise.

Receive $\bm{l}_{t}(i_{s})$ and calculate
$\hat{\bm{l}}_{t}=\left(\frac{\sum_{s\in
T_{i_{1}}(t)}\bm{l}_{s}(i_{1})}{|T_{i_{1}}(t)|},\cdots,\frac{\sum_{s\in
T_{i_{d}}(t)}\bm{l}_{s}(i_{d})}{|T_{i_{d}}(t)|}\right).$ (23)

if the environment sends a stopping signal then

Set $n$ to $t$.

Recommend
$J_{n}=\max_{j\in[N]}\left<\bm{u}_{j},\hat{V}^{-1}\hat{\bm{l}}_{t}\right>$ and
stop.

end if

end for

######  Proposition 1.

Running our algorithm for $n$ rounds, we have the upper bound to the simple
regret as follows:

$\mathbb{E}\left[r_{n}\right]\leq O\left(Cd\sqrt{\frac{\ln N}{n}}\right)$ (24)

###  3.3 Lower bound

In this part, we provide a lower bound to pure exploration with low rank
sequence. Generally, there is a gap $\sqrt{\ln N}$ to our upper bound to the
pure exploration in separated setting when $d\leq\ln N.$ It implies that our
proposed algorithm is sub-optimal. Meanwhile our proposed lower bound is
similar to the lower bound of linear bandits but with a $\sqrt{n}$ factor Dani
et al. (2007). In comparison to the united setting, we also provide a lower
bound when $d\geq\ln N$, which states that there is an optimal result for the
united setting.

To demonstrate our main result, firstly we extend the lower bound for pure
exploration with multi-armed bandits from the traditional result in Auer et
al. (2002). Then, in our proof, we are going to reduce the problem for low
rank sequence to a corresponding 2-armed bandits, and obtain the lower bound
to pure exploration with low rank structure.

######  Lemma 1.

The lower bound to the simple regret for the stochastic multi-armed bandits is
$\Omega\left(\sqrt{\frac{N}{n}}\right)$.

See the proof in Appendix

Now we attempt to show the lower bound to low rank loss.

######  Theorem 6.

The lower bound to the simple regret for the multi-armed bandits with low rank
sequence is $\Omega\left(\frac{d}{\sqrt{n}}\right),$ where the kernel matrix
is a fixed $N\times d$ matrix.

###### Proof.

Without loss the generality, we assume that there are $N=2^{d}$ arms that each
arm $\bm{u}_{i}\in\mathcal{A}=\\{+1,-1\\}^{d}$ and seed vector
$\bm{v}_{t}\in\mathcal{L}=\\{\pm\bm{e}_{i}:1\leq i\leq d\\}$. We give a
distribution $\mathcal{P}_{\bm{b}}$ upon $\mathcal{L}$ such that

$\mathcal{P}_{\bm{b}}(\bm{x})=\begin{cases}\frac{1+\bm{b}(i)\epsilon}{2d}&\text{$\bm{x}=\bm{e}_{i}$}\\\
\frac{1-\bm{b}(i)\epsilon}{2d}&\text{$\bm{x}=-\bm{e}_{i}$},\end{cases}$ (25)

for some $\epsilon\in(0,1/2)$ and $\bm{b}\in\\{\pm 1\\}^{d}$.

Hence, the simple regret is formulated as follows:

$\begin{split}r_{n}=\max_{i\in[N]}\mathbb{E}_{\bm{v}_{n}\sim\mathcal{P}_{\bm{b}}}[\bm{u}_{i}\cdot\bm{v}_{n}]-\mathbb{E}_{\bm{v}_{n}\sim\mathcal{P}_{\bm{b}}}[\bm{u}_{\varphi_{n}}\cdot\bm{v}_{n}]=\max_{i\in[N]}\bm{u}_{i}\bm{v}-\bm{u}_{\varphi_{n}}\bm{v},\end{split}$
(26)

where
$\bm{v}=\mathbb{E}[\bm{v}_{n}]=\sum_{i=1}^{d}\frac{1+\bm{b}(i)\epsilon}{2d}\cdot\bm{e}_{i}+\frac{1-\bm{b}(i)\epsilon}{2d}\cdot(-\bm{e}_{i}).$
Hence, we have that

$\bm{b}=\operatorname*{arg\,max}_{\bm{u}\in\mathcal{A}}\bm{u}\cdot\bm{v},$
(27)

since
$\bm{v}=\mathbb{E}[\bm{v}_{n}]=\left(\frac{\bm{b}(1)\epsilon}{2d},\cdots,\frac{\bm{b}(d)\epsilon}{d}\right).$

We simplify that $\bm{u}_{\varphi_{n}}=\bm{u}_{n}\in\\{\pm 1\\}^{d}$, then we
have that

$\begin{split}r_{n}&=\bm{b}\cdot\bm{v}-\bm{u}_{n}\cdot\bm{v}=\sum_{i=1}^{d}\bm{v}(i)(\bm{b}(i)-\bm{u}_{n}(i))\\\
&=\sum_{i=1}^{d}\frac{\bm{b}(i)\epsilon}{d}\left(\bm{b}(i)-\bm{u}_{n}(i)\right)=\sum_{i=1}^{d}\frac{\bm{b}(i)\epsilon}{d}2\mathbb{I}_{[\bm{b}(i)\neq\bm{u}_{n}(i)]}.\end{split}$
(28)

Next, we define
$r_{n}^{i}(\bm{b}(i))=\frac{\bm{b}(i)\epsilon}{d}2\mathbb{I}_{[\bm{b}(i)\neq\bm{u}_{n}(i)]}.$
Then, we have that $r_{n}^{i}(\bm{b}(i))$ is at least the regret that would be
incurred if the algorithm knew that the adversary was using one of the
$\mathbb{P}_{\bm{b}}$ distributions and also knew $\\{\bm{b}(j):j\neq i\\}$.
In this case it would know that the algorithm is incurred a $(\pm 1)$
Bernoulli distribution of $\bm{u}_{n}\cdot\bm{v}_{n}$ with mean:

$\mathbb{E}\left[\sum_{j\neq
i}\bm{v}_{n}(j)\bm{u}_{n}(j)\right]+\bm{b}(i)\bm{u}_{n}(i)\frac{\epsilon}{d}.$
(29)

Clearly, since the algorithm knew $\\{\bm{b}(j):j\neq i\\}$ the algorithm is
supposed to set $\bm{u}_{n}(j)=\bm{b}(j),$ for any $j\neq i$. Therefore we
have that

$\mathbb{E}\left[\sum_{j\neq i}\bm{v}_{n}(j)\bm{u}_{n}(j)\right]=\sum_{j\neq
i}1\times\frac{1+\bm{b}(j)\epsilon}{2d}\cdot\bm{b}(j)+(-1)\times\frac{1-\bm{b}(j)\epsilon}{2d}\cdot\bm{b}(j)=\frac{(d-1)\epsilon}{d}$

On the other hand, we can consider this game as a 2-armed bandit problem with

  * •

arm 1: Selecting $\bm{u}_{n}(i)=1$ with mean
$\frac{(d-1)\epsilon+\bm{b}(i)\epsilon}{d};$

  * •

arm 2: Selecting $\bm{u}_{n}(i)=-1$ with mean
$\frac{(d-1)\epsilon-\bm{b}(i)\epsilon}{d}.$

Utilising the Lemma 1, we have that

$\mathbb{E}[r_{n}^{i}(\bm{b}(i))]\geq\Omega\left(\sqrt{\frac{1}{n}}\right).$

Therefore,

$\mathbb{E}[r_{n}]=\sum_{i=1}^{d}\mathbb{E}\left[r_{n}^{i}(\bm{b}(i))\right]\geq\Omega\left(\frac{d}{\sqrt{n}}\right).$
(30)

∎

In the following corollary, we show another form of the lower bound
$\Omega\left(\sqrt{\frac{d\ln N}{n}}\right),$ when $d\geq\ln N.$

######  Corollary 1.

For all $N=2^{k}$, $k\in\\{1,\cdots,d\\}$ and all outputs of the
recommendation strategy, there is a strategy of setting seed vector
$\bm{v}_{t}$ such that

$\mathbb{E}\left[r_{n}\right]\geq\Omega\left(\sqrt{\frac{d\ln N}{n}}\right).$

###### Proof.

We break the the $d$-dimensional feature space into smaller $k$ dimensional
space. Setting $\beta=\frac{d}{k}$, for each $k$-dimensional space, with
$N$-arms, round $\frac{n}{\beta}$ and the expectation of the seed vector
$\bm{v}_{k}\in\mathbb{R}^{k}$ we have that

$\mathbb{E}[r^{j}_{\frac{n}{\beta}}]\geq\Omega\left(k\sqrt{\frac{1}{\frac{n}{\beta}}}\right)=\Omega\left(\sqrt{\frac{dk}{n}}\right)$

according to Theorem 6.

At round $\tau=(j-1)\frac{n}{\beta}+t$ the seed vector is $\bm{v}_{t,i}$ such
that $(0,\cdots,0,\bm{v}_{t,i},0\cdots,0)\in\mathbb{R}^{d},$ and similar to
the reward sequence. The strategy of setting seed vector is cycling in each
round block with size $\frac{n}{\beta}$. Therefore we have that

$\mathbb{E}\left[r_{n}\right]=\frac{1}{\beta}\sum_{j=1}^{\beta}\mathbb{E}\left[r^{j}_{\frac{n}{\beta}}\right]=\Omega\left(\sqrt{\frac{dk}{n}}\right)=\Omega\left(\sqrt{\frac{d\ln
N}{n}}\right).$ (31)

∎

######  Remark 3.

The lower bounds we offered in this section are for both cases of the
separated (oblivious sampling) and united (non-oblivious sampling) exploration
and recommendation strategies. In the case of united setting, there is an
upper bound to the simple regret by $O\left(\sqrt{\frac{d\ln N}{n}}\right)$.
This bound can be obtained, when the exploration strategy is UCB and the
recommendation strategy is to output the average distribution of the outputs
of UCB. In the oblivious sampler case, there is still a $\sqrt{\ln N}$ gap
between the upper bound and the lower bound for both fixed and time-varying
kernel.

##  4 Conclusion and future work

In this paper we extend the pure exploration for multi-armed bandits to the
low rank reward. In our problem setting, we restrict that the exploration and
recommendation strategy only share few information. It implies that the
exploration strategy is requested to sample the arms obliviously. Meanwhile,
we involve the kernel space of the reward sequence. Furthermore, we consider
the kernel is fixed and stochastic respectively and propose the efficient
algorithms and demonstrate simple regret bounds. We provide algorithms which
guarantee regret bound $O\left(d\sqrt{\frac{\ln N}{n}}\right)$ for both fixed
and stochastic kernel setting.

Clearly, our designed algorithms require the prior information of the kernel
in each round. A challenging future work is to design algorithms without the
kernel information. Meanwhile the adversarial Multi-armed bandits with low
rank reward is also an open problem left.

## References

  * Bubeck et al. [2009] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.  Pure exploration in multi-armed bandits problems.  In _International conference on Algorithmic learning theory_ , pages 23–37. Springer, 2009.
  * Hazan et al. [2016] Elad Hazan, Tomer Koren, Roi Livni, and Yishay Mansour.  Online learning with low rank experts.  In _Conference on Learning Theory_ , pages 1096–1114, 2016.
  * Cesa-Bianchi and Lugosi [2012] Nicolo Cesa-Bianchi and Gábor Lugosi.  Combinatorial bandits.  _Journal of Computer and System Sciences_ , 78(5):1404–1422, 2012.
  * 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.
  * Besson and Kaufmann [2018] Lilian Besson and Emilie Kaufmann.  What doubling tricks can and can’t do for multi-armed bandits.  _arXiv preprint arXiv:1803.06971_ , 2018.
  * Zimmert and Seldin [2019] Julian Zimmert and Yevgeny Seldin.  An optimal algorithm for stochastic and adversarial bandits.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 467–475. PMLR, 2019.
  * Ghezzi et al. [2018] Antonio Ghezzi, Donata Gabelloni, Antonella Martini, and Angelo Natalicchio.  Crowdsourcing: a review and suggestions for future research.  _International Journal of management reviews_ , 20(2):343–363, 2018.
  * Awerbuch and Kleinberg [2004] Baruch Awerbuch and Robert D Kleinberg.  Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches.  In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , pages 45–53, 2004.
  * Bubeck et al. [2012a] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Sham M Kakade.  Towards minimax policies for online linear optimization with bandit feedback.  In _Conference on Learning Theory_ , pages 41–1. JMLR Workshop and Conference Proceedings, 2012a.
  * Jamieson and Nowak [2014] Kevin Jamieson and Robert Nowak.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _2014 48th Annual Conference on Information Sciences and Systems (CISS)_ , pages 1–6. IEEE, 2014.
  * Madani et al. [2004] Omid Madani, Daniel J Lizotte, and Russell Greiner.  The budgeted multi-armed bandit problem.  In _Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004. Proceedings 17_ , pages 643–645. Springer, 2004.
  * Bubeck et al. [2012b] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations and Trends® in Machine Learning_ , 5(1):1–122, 2012b.
  * Dani et al. [2007] Varsha Dani, Sham M Kakade, and Thomas Hayes.  The price of bandit information for online optimization.  _Advances in Neural Information Processing Systems_ , 20, 2007.
  * Grötschel et al. [2012] Martin Grötschel, László Lovász, and Alexander Schrijver.  _Geometric algorithms and combinatorial optimization_ , volume 2.  Springer Science & Business Media, 2012.
  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002\.

##  5 Supplementary material

###  5.1 Proof of Theorem 4

###### Proof.

We prove our result by contradiction. Suppose that $\|\bm{w}\|_{\infty}>1$,
then we assume that there exists one $i\in[N]$ such that
$\bm{u}_{i}=\sum_{j=1}^{d}\bm{w}(j)\bm{u}_{i_{j}}$ and without loss the
generality we can assume that $\bm{w}(1)>1$. Then we have that

$\begin{split}&\left|\det\left([\bm{u}_{i},\bm{u}_{i_{2}},\cdots,\bm{u}_{i_{d}}]\right)\right|\\\
&=\left|\det\left(\left[\sum_{j=1}^{d}\bm{w}(j)\bm{u}_{i_{j}},\bm{u}_{i_{2}},\cdots,\bm{u}_{i_{d}}\right]\right)\right|\\\
&=\left|\det\left(\sum_{j=1}^{d}\bm{w}(j)\left[\bm{u}_{i_{j}},\bm{u}_{i_{2}},\cdots,\bm{u}_{i_{d}}\right]\right)\right|\\\
&=|\bm{w}(1)|\left|\det\left([\bm{u}_{1},\bm{u}_{i_{2}},\cdots,\bm{u}_{i_{d}}]\right)\right|\\\
&=|\bm{w}(1)|\det(V).\\\ \end{split}$

It leads to a contradiction that there is a matrix
$V^{\prime}=[\bm{u}_{i}^{\top},\bm{u}_{i_{2}}^{\top},\cdots,\bm{u}_{i_{d}}^{\top}]^{\top}$
with $\det(V^{\prime})>\det(V).$ Therefore, we have our conclusion. ∎

###  5.2 Proof of Theorem 5

###### Proof.

$\begin{split}&\mathbb{P}\left[J_{t}\neq j^{\star}\right]\\\
&=\mathbb{P}\left[\langle\bm{u}_{j}-\bm{u}_{j^{*}},V^{-1}\cdot\hat{\bm{l}}_{t}\rangle\geq
0\right]\\\
&=\mathbb{P}\left[\langle\bm{u}_{j}-\bm{u}_{j^{*}},V^{-1}\cdot\hat{\bm{l}}_{t}\rangle-\langle\bm{u}_{j}-\bm{u}_{j^{*}},\bm{v}\rangle\geq-\langle\bm{u}_{j}-\bm{u}_{j^{*}},\bm{v}\rangle\right]\end{split}$
(32)

Denoting $\bm{h}_{j}=\bm{u}_{j}-\bm{u}_{j^{*}}$, we can further rewrite the
above equation as follows:

$\begin{split}&\mathbb{P}\left[\hat{\mu}_{j,t}-\hat{\mu}_{j^{*},t}\geq
0\right]\\\ &=\mathbb{P}\left[\langle\bm{h}_{j}\cdot
V^{-1},\hat{\bm{l}}_{t}\rangle-\langle\bm{h}_{j}V^{-1},\tilde{\bm{l}}\rangle\geq-\langle\bm{h}_{j},\bm{v}\rangle\right]\end{split}$
(33)

Setting $X_{s}=\bm{l}_{s}(i_{s\mod d})$ when $(s\mod d)\neq 0,$
$X_{s}=\bm{l}_{s}(i_{d})$ otherwise, and

$f(X_{1},\cdots,X_{t})=\left<\left(\frac{\sum_{s\in
T_{i_{1}}(t)}X_{s}}{|T_{i_{1}}(t)|},\cdots,\frac{\sum_{s\in
T_{i_{d}}(t)}X_{s}}{|T_{i_{d}}(t)|}\right),V^{-1}\bm{h}_{j}\right>,$ (34)

then we have that

$\begin{split}\left|f(X_{1},\cdots,X_{s},\cdots,X_{t})-f(X_{1},\cdots,X_{s}^{{}^{\prime}},\cdots,X_{t})\right|&\leq\left|\left<\frac{X_{s}-X_{s}^{{}^{\prime}}}{|T_{i_{s\mod
d}}(t)|},V^{-1}(\bm{u}_{j^{*}}-\bm{u}_{j})\right>\right|\\\
&\leq\left\lVert\frac{X_{i}-X_{i}^{{}^{\prime}}}{|T_{i_{s\mod
d}}(t)|}\right\lVert_{1}\|V^{-1}(\bm{u}_{j^{*}}-\bm{u}_{j})\|_{\infty}\\\
&\leq\frac{1}{\lfloor\frac{t}{d}\rfloor}\cdot 2,\end{split}$

while the coefficients of $\bm{u}_{j^{*}},\bm{u}_{j}$ are constrained in
$[-1,1]$ with respect to $V$. Thus, we set that
$c_{i}=\frac{2}{\lfloor\frac{t}{d}\rfloor}$.

Utilising McDiarmid’s inequality to Equation above we obtain that

$\begin{split}&\mathbb{P}\left[\langle\bm{h}_{j}\cdot
V^{-1},\hat{\bm{l}}_{t}\rangle-\langle\bm{h}_{j}V^{-1},\tilde{\bm{l}}\rangle\geq-\langle\bm{h}_{j},\bm{v}\rangle\right]\\\
&\leq\exp\left(-\frac{2\times\langle\bm{h}_{j},\bm{v}\rangle^{2}}{\sum_{i=1}^{t}\left(\frac{2}{\lfloor\frac{t}{d}\rfloor}\right)^{2}}\right)\leq\exp\left(-\frac{1\times\langle\bm{h}_{j},\bm{v}\rangle^{2}\lfloor\frac{t}{d}\rfloor}{2d}\right),\end{split}$
(35)

where $n$ is the total rounds for exploration.

Next we give the upper bound to the simple regret.

$\begin{split}\mathbb{E}\left[r_{n}\right]&=\sum_{j=1}^{N}\Delta_{j}\mathbb{P}\left[I_{t}=j\right]\leq\sum_{j:\Delta_{j>\epsilon}}\Delta_{j}\mathbb{P}\left[\hat{\mu}_{j,t}\geq\hat{\mu}_{j^{*},t}\right]+\sum_{j:\Delta_{j}\leq\epsilon}\mathbb{P}\left[I_{t}=j\right]\\\
&\leq\sum_{j:\Delta_{j}\geq\epsilon}\Delta_{j}\exp\left(-\frac{\Delta_{j}^{2}n}{2d}\right)+\epsilon\end{split}$
(36)

A function $f:x\rightarrow x\exp(-Cx^{2})$ is a decreasing function on
$[\frac{1}{\sqrt{2C}},1]$ for any $C>0$. Taking $C=\frac{n}{2d^{2}}$ we obtain
that

$\mathbb{E}\left[r_{n}\right]\leq\epsilon+(N-1)\epsilon\exp\left(-\frac{\epsilon^{2}n}{2d^{2}}\right),$
(37)

when $\epsilon\geq\frac{1}{\sqrt{\frac{n}{2d^{2}}}}$. Particularly, we have
that

$\mathbb{E}\left[r_{n}\right]\leq O\left(\sqrt{\frac{d^{2}\ln N}{n}}\right),$
(38)

by setting $\epsilon=\sqrt{\frac{2d^{2}\ln N}{n}}.$ ∎

###  5.3 Details of Remark 2

Let us have a review of the case of $d=N$, and offer a more refined analysis.
Due to the fact that $\bm{u}_{i}\cdot
V^{-1}\hat{\bm{l}}_{t}=\hat{\bm{l}}_{t}(i),\forall i\in[N],$ when $V=U$, we
have further:

$\begin{split}f(X_{1},\cdots,X_{t})&=\left<\left(\frac{\sum_{s\in
T_{i_{1}}(t)}X_{s}}{|T_{i_{1}}(t)|},\cdots,\frac{\sum_{s\in
T_{i_{N}}(t)}X_{s}}{|T_{i_{N}}(t)|}\right),V^{-1}\bm{h}_{j}\right>\\\
&=\left<\bm{u}_{j},V^{-1}\hat{\bm{l}}_{t}\right>-\left<\bm{u}_{j},V^{-1}\hat{\bm{l}}_{t}\right>\\\
&=\frac{\sum_{s\in T_{j}(t)}X_{s}}{|T_{j}(t)|}-\frac{\sum_{s\in
T_{j^{*}}(t)}X_{s}}{|T_{j^{*}}(t)|}.\end{split}$ (39)

Next, we can have that

$\left|f(X_{1},\cdots,X_{s},\cdots,X_{t})-f(X_{1},\cdots,X_{s}^{{}^{\prime}},\cdots,X_{t})\right|=\left|\frac{\sum_{s\in
T_{j}(t)}X_{s}}{|T_{j}(t)|}-\frac{\sum_{s\in
T_{j^{*}}(t)}X_{s}}{|T_{j^{*}}(t)|}\right|,$ (40)

so

$\left|f(X_{1},\cdots,X_{s},\cdots,X_{t})-f(X_{1},\cdots,X_{s}^{{}^{\prime}},\cdots,X_{t})\right|\leq\begin{cases}\frac{2}{\lfloor\frac{t}{N}\rfloor}&\text{$s\in
T_{j}(t)\cup T_{j^{*}}(t)$}\\\ 0&\text{otherwise}\end{cases}.$ (41)

Now we can set
$c_{i}=\begin{cases}\frac{2}{\lfloor\frac{t}{N}\rfloor}&\text{$s\in
T_{j}(t)\cup T_{j^{*}}(t)$}\\\ 0&\text{otherwise}\end{cases}.$

Therefore, utilising the McDiarmid’s inequality we obtain that

$\begin{split}\mathbb{P}\left[\hat{\mu}_{j,t}-\hat{\mu}_{j^{*},t}\geq
0\right]&\leq\exp\left(-\frac{2\times\langle\bm{h}_{j},\bm{v}\rangle^{2}}{\sum_{i=1}^{t}\left(c_{i}\right)^{2}}\right)\\\
&\leq\exp\left(-\frac{1\times\langle\bm{h}_{j},\bm{v}\rangle^{2}\lfloor\frac{t}{N}\rfloor}{2}\right),\end{split}$
(42)

and the previous bound $O\left(\sqrt{\frac{N\ln N}{n}}\right).$

###  5.4 Proof of Lemma 1

To prove Lemma 1, we need to assume the following two allocation strategies of
the environment.

  * •

We assume that arm $i^{*}$ is Bernoulli distributed with parameter
$\frac{1+\epsilon}{2}$ and others with parameter $\frac{1-\epsilon}{2}$. The
arm $i^{*}$ is selected by the environment at the beginning of the learning
process uniformly. We denote that $\mathbb{P}_{i^{*}}$ to the probability
conditioned on $i^{*}$ being the “good” arm.

  * •

We assume that all arms are Bernoulli distributed with parameter
$\frac{1-\epsilon}{2}$, and we denote this allocation by $\mathbb{P}_{0}$.

To simplify the notations we denote $N_{i}$ to the number of arm $i$ chosen by
the exploration strategy $\mathcal{A}$. Let $e_{t}=\bm{l}_{t}(i_{t})$ be a
random variable denoting the reward of exploration at time $t$, and let
$\bm{e}_{t}$ denote the sequence of rewards explored up through round
$t:\bm{e}_{t}=(e_{1},\cdots,e_{t})$. For shorthand $\bm{e}_{T}=\bm{e}$.

Obviously any randomised recommendation strategy is equivalent to an a-priori
random choice from the set of all deterministic strategies. On the one hand,
the exploration processes the exploration arm $I_{t}$ according to the history
$\bm{e}_{t-1}$, on the other hand, the recommendation strategy makes
recommendation $J_{t}$ according to the reward sequence $\bm{e}_{t}$ at the
end of round $t$. Therefore, we can formally regard the algorithm
$\mathcal{A}$ as a fixed function, which at round $t$, maps the exploration
$\bm{e}_{t-1}$ to the next exploration $e_{t}$ and at the end of the round $t$
further to the recommendation $J_{t}$.

######  Lemma 2 (Auer et al. [2002]).

Let $f:\\{0,1\\}^{T}\rightarrow[0,M]$ be any bounded function defined on
exploration sequence $\bm{e}$. Then, for any action $i^{\star}$

$\mathbb{E}_{i^{*}}[f(\bm{e})]\leq\mathbb{E}_{0}[f(\bm{e})]+\frac{M}{2}\sqrt{\mathbb{E}_{0}[N_{i^{*}}]\ln(1-4\epsilon^{2})}.$
(43)

###### Proof.

$\begin{split}\mathbb{E}_{i^{*}}[f(\bm{e})]-\mathbb{E}_{0}[f(\bm{e})]&=\sum_{\bm{e}}f(\bm{e})(\mathbb{P}_{i^{*}}\\{\bm{e}\\}-\mathbb{P}_{0}\\{\bm{e}\\})\\\
&\leq\sum_{\bm{e}:\mathbb{P}_{i^{*}}\\{\bm{e}\\}\geq\mathbb{P}_{0}\\{\bm{e}\\}}f(\bm{e})(\mathbb{P}_{i^{*}}\\{\bm{e}\\}-\mathbb{P}_{0}\\{\bm{e}\\})\\\
&\leq
M\sum_{\bm{e}:\mathbb{P}_{i^{*}}\\{\bm{e}\\}\geq\mathbb{P}_{0}\\{\bm{e}\\}}(\mathbb{P}_{i^{*}}\\{\bm{e}\\}-\mathbb{P}_{0}\\{\bm{e}\\})\\\
&=\frac{M}{2}\|\mathbb{P}_{i^{*}}-\mathbb{P}_{0}\|_{1}.\end{split}$

By

$\|\mathbb{P}_{i^{*}}-\mathbb{P}_{0}\|_{1}^{2}\leq 2\ln
2\mathrm{KL}(\mathbb{P}_{0}\|\mathbb{P}_{i^{*}}),$

we have that

$\begin{split}\mathrm{KL}(\mathbb{P}_{0}\|\mathbb{P}_{i^{*}})&=\sum_{t=1}^{T}\mathrm{KL}(\mathbb{P}_{0}\\{e_{t}|\bm{e}_{t-1}\|\mathbb{P}_{i^{*}}\\{e_{t}|\bm{e}_{t-1}\\})\\\
&=\sum_{t=1}^{T}\sum_{\bm{e}_{t}\in\\{0,1\\}^{t}}\mathbb{P}_{0}\\{\bm{e}_{t}\\}\ln\frac{\mathbb{P}_{0}\\{e_{t}|\bm{e}_{t-1}\\}}{\mathbb{P}_{i^{*}}\\{e_{t}|\bm{e}_{t-1}\\}}\\\
&=\sum_{t=1}^{T}\sum_{\bm{e}_{t}\in\\{0,1\\}^{t}}\mathbb{P}_{0}\\{\bm{e}_{t-1}\\}\mathbb{P}_{0}\\{e_{t}|\bm{e}_{t-1}\\}\ln\frac{\mathbb{P}_{0}\\{e_{t}=1|\bm{e}_{t-1}\\}}{\mathbb{P}_{i^{*}}\\{e_{t}=1|\bm{e}_{t-1}\\}}\\\
&=\sum_{t=1}^{T}\mathbb{P}_{0}\\{i_{t}\neq
i^{*}\\}\mathrm{KL}\left(\frac{1-\epsilon}{2}\left\lVert\frac{1-\epsilon}{2}\right.\right)+\mathbb{P}_{0}\\{i_{t}=i^{*}\\}\mathrm{KL}\left(\frac{1-\epsilon}{2}\left\lVert\frac{1+\epsilon}{2}\right.\right)\\\
&=\sum_{t=1}^{T}\mathbb{P}_{0}\\{i_{t}=i^{*}\\}\left(-\frac{1}{2}\ln(1-4\epsilon^{2})\right)\\\
&=\mathbb{E}_{0}[N_{i^{*}}]\left(-\frac{1}{2}\ln(1-4\epsilon^{2})\right)\end{split}$

The second equality is from the definition of the conditional relative
entropy. The fourth equality is due to the fact that the conditional
probability distribution $\mathbb{P}_{0}\\{e_{t}|\bm{e}_{t-1}\\}$ for $e_{t}$
is uniform upon $\\{0,1\\}.$ Meanwhile the conditional distribution
$\mathbb{P}_{i^{*}}\\{e_{t}|\bm{e}_{t-1}\\}$ to $e_{t}$ is determined by the
choice of $i^{*}$. Once $i^{*}=i_{t}$ the probability over 1 is
$\frac{1+\epsilon}{2}$, otherwise, $\frac{1-\epsilon}{2}.$ ∎

According to above Lemma, we may have the lower bound to the pure exploration
problem in the following theorem.

######  Theorem 7.

For any recommendation strategy $\mathcal{A}$ and for the distribution on
rewards given above, the expected regret of $\mathcal{A}$ is lower bounded by
$\Omega\left(\sqrt{\frac{N}{n}}\right)$.

###### Proof.

We see the recommendation strategy $\mathcal{A}$ into two parts, in the first
$n$ rounds, the strategy actually processes exploration upon $N$ arms. At the
end of round $n$, the strategy recommends an arm $J_{n}$ as the output of the
recommendation.

We denote that $r_{n}$ to be the reward of the recommendation. Then, we have
that

$\mathbb{E}_{i^{*}}[r_{n}]=\left(\frac{1+\epsilon}{2}\cdot\mathbb{P}_{i^{*}}(J_{n}=i^{*})\right)+\left(\frac{1-\epsilon}{2}\cdot\mathbb{P}_{i^{*}}(J_{n}\neq
i^{*})\right)=\frac{1}{2}-\frac{\epsilon}{2}+\epsilon\mathbb{P}_{i^{*}}(J_{n}=i^{*}).$
(44)

Further,

$\mathbb{E}_{i^{*}}[\bm{l}(i^{*})-\bm{l}(J_{n})]=\epsilon-\epsilon\mathbb{P}_{i^{*}}(i_{n}=i^{*})$
(45)

Note that
$\mathbb{P}_{i^{*}}(J_{n}=i^{*})=\mathbb{E}_{i^{*}}[\mathbb{I}_{J_{n}=i^{*}}].$

Then, we have that

$\frac{1}{N}\sum_{i^{*}=1}^{N}\mathbb{E}_{i^{*}}[\bm{l}(i^{*})-\bm{l}(J_{n})]=\epsilon\left(1-\frac{1}{N}\sum_{i^{*}=1}^{N}\mathbb{P}_{i^{*}}(J_{n}=i^{*})\right)$
(46)

Now, we set that $f(\bm{e}_{n})=\mathbb{I}_{J_{n}=i^{*}}$. Obviously
$\mathbb{P}_{0}[f(\bm{e})]=1,$ while all expectations are the same.

Due to above lemma, we have that

$\frac{1}{N}\sum_{i^{*}=1}^{N}\mathbb{E}_{i^{*}}[\bm{l}(i^{*})-\bm{l}(J_{n})]\geq\epsilon\left(1-\frac{1}{N}+\sqrt{\frac{T}{N}\ln(1-4\epsilon^{2})}\right),$
(47)

where it follows from
$\sum_{i=1}^{N}\sqrt{\mathbb{E}_{0}[N_{i}]}\leq\sqrt{Nn}$.

Then, we have that
$\frac{1}{N}\sum_{i^{*}=1}^{T}\mathbb{E}_{i^{*}}[\bm{l}(i^{*})-\bm{l}(J_{n})]\geq\Omega\left(\frac{\epsilon}{2}-C\epsilon\sqrt{\frac{n}{N}}\right)$
by $-\ln(1-x)\leq 4\ln(4/3)x$ for $x\in[0,1/4].$

By setting $\epsilon=\frac{N}{n}$, we have our conclusion. ∎