# First-principles calculations for transient absorption of laser-excited
magnetic materials

Shunsuke A. Sato<EMAIL_ADDRESS>Center for Computational Sciences,
University of Tsukuba, Tsukuba 305-8577, Japan  Max Planck Institute for the
Structure and Dynamics of Matter, Luruper Chaussee 149, 22761 Hamburg, Germany

###### Abstract

We investigate the modification in the optical properties of laser-excited
bulk cobalt and nickel using the time-dependent density functional theory at a
finite electron temperature. As a result of the first-principles simulation, a
complex change in the photoabsorption of the magnetic materials is observed
around the $M_{2,3}$ absorption edge. Based on the microscopic analysis, we
clarify that this complex absorption change consists of the two following
components: (i) the decrease in the photoabsorption in a narrow energy range
around the $M_{2,3}$ edge, which reflects the blue shift of the absorption
edge due to the light-induced demagnetization, and (ii) the increase in the
photoabsorption in a wider range around the $M_{2,3}$ edge, which reflects the
modification in the local-field effect due to the light-induced electron
localization. The relation between the transient optical and magnetic
properties may open a way to monitor ultrafast (de)magnetization and spin
dynamics in magnetic materials via transient absorption spectroscopy.

##  I Introduction

Owing to the recent developments in laser technologies, the study of highly
nonlinear nonequilibrium electron dynamics in solids has become experimentally
accessible Brabec and Krausz (2000); Krausz and Ivanov (2009); Mourou  _et
al._ (2012), offering novel opportunities for investigating the optical
control of electric transport Schiffrin  _et al._ (2013); Higuchi  _et al._
(2017); Sato  _et al._ (2019); McIver  _et al._ (2020) and the emergence of a
dynamical phase of matter Oka and Aoki (2009); Lindner  _et al._ (2011). In
the ultrafast regime, the transient optical properties of solids that are
driven by intense light pulses have been intensively studied in the attosecond
regime, and a microscopic understanding of the nonequilibrium electron
dynamics during and after laser excitation has been obtained Schultze  _et
al._ (2014); Zürch  _et al._ (2017); Lucchini  _et al._ (2016); Moulet  _et
al._ (2017); Buades  _et al._ (2021); Lucchini  _et al._ (2021). Recently, the
attosecond circular dichroism technique, which enables the study of light-
induced ultrafast spin dynamics in magnetic materials, has been developed,
opening a novel avenue toward achieving optical control of ultrafast spin
dynamics and magnetization Siegrist  _et al._ (2019).

First-principles electron dynamics simulations based on the time-dependent
density functional theory (TDDFT) have been a powerful tool to obtain
microscopic insight into light-induced ultrafast phenomena Runge and Gross
(1984); Bertsch  _et al._ (2000). Recently, this approach has been used in the
field of attosecond transient absorption spectroscopy in solids, enabling
access to the microscopic mechanism behind the macroscopic ultrafast phenomena
Lucchini  _et al._ (2016); Volkov  _et al._ (2019); Siegrist  _et al._ (2019).

In this work, we study the transient optical properties of laser-excited
magnetic materials, namely cobalt and nickel, using first-principles electron
dynamics simulations, aiming to find a signature of light-induced
magnetization and spin dynamics in the transient absorption spectra. Once the
relation between magnetization dynamics and transient absorption is
established, a complementary and alternative technique to the attosecond
circular dichroism technique is established to investigate light-induced
magnetization and spin dynamics. Through microscopic simulations, we find a
complex modification in the photoabsorption of the laser-excited magnetic
materials around their $M_{2,3}$ absorption edge. This modification reflects
light-induced electron localization around the ions and a reduction in the a
exchange splitting in the $3p$ semicore bands. Hence, the microscopic
information of magnetic systems is indeed integrated in the transient
absorption spectrum.

This paper is organized as follows. In Sec. II, we first revisit the electron
dynamics simulations with the TDDFT and describe a method to compute the
optical properties of solids. In Sec. III, we study the transient optical
properties of laser-excited magnetic materials and analyze the microscopic
origin behind the observed modification of photoabsorption. Finally, our
findings are summarized in Sec. IV. Atomic units are used unless stated
otherwise.

##  II Methods

###  II.1 Electron dynamics simulation

Firstly, we briefly revisit the electron dynamics simulations based on the
TDDFT Runge and Gross (1984); Bertsch  _et al._ (2000). The details of the
method are described elsewhere Sato (2021). The light-induced electron
dynamics in solids is described by the following time-dependent Kohn–Sham
equation,

$\displaystyle i\frac{\partial}{\partial
t}u_{b,s,\bm{k}}(\bm{r},t)=\hat{h}_{s,\bm{k}}(t)u_{b,s,\bm{k}}(\bm{r},t),$ (1)

where $b$ is the band index, $s$ is the spin index ($s=\uparrow$ or
$\downarrow$), $\bm{k}$ is the Bloch wavevector, and
$u_{b,s,\bm{k}}(\bm{r},t)$ represents the periodic part of the time-dependent
Bloch orbitals. The time-dependent Kohn–Sham Hamiltonian,
$\hat{h}_{s,\bm{k}}(t)$, is given by

$\displaystyle\hat{h}_{s,\bm{k}}(t)=\frac{\left[\bm{p}+\bm{k}+\bm{A}(t)\right]^{2}}{2}+\hat{v}_{ion}+v_{Hxc}\left[\rho_{e}(\bm{,}t),\rho_{s}(\bm{r},t)\right],$
(2)

where $\bm{A}(t)$ is a time-varying spatially-uniform vector potential, which
is related to the external laser electric field as
$\bm{E}(t)=-\dot{\bm{A}}(t)$. The ionic potential is denoted as
$\hat{v}_{ion}$, and it may consist of spatially non-local parts when using
the norm-conserving pseudopotential method Kleinman and Bylander (1982);
Troullier and Martins (1991). The Hartree-exchange-correlation potential is
denoted as $v_{Hxc}\left[\rho_{e}(\bm{r},t),\rho_{s}(\bm{r},t)\right]$, and it
is a functional of the electron density, $\rho_{e}(\bm{r},t)$, and the spin
density, $\rho_{s}(\bm{r},t)$. The total electron density,
$\rho_{e}(\bm{r},t)$, is given by the sum of the spin density as
$\rho_{e}(\bm{r},t)=\rho_{\uparrow}(\bm{r},t)+\rho_{\downarrow}(\bm{r},t)$,
and each spin density is defined as

$\displaystyle\rho_{s}(\bm{r},t)=\sum_{b}\frac{1}{\Omega_{BZ}}\int_{BZ}d\bm{k}f_{b,s,\bm{k}}\left|u_{b,s,\bm{k}}(\bm{r},t)\right|^{2},$
(3)

where $\Omega_{BZ}$ is the volume of the Brillouin zone, and $f_{b,s,\bm{k}}$
is the occupation of the orbital. We define the occupation factor as a
Fermi–Dirac distribution, that is

$\displaystyle
f_{b,s,\bm{k}}=\frac{1}{e^{(\epsilon_{b,s,\bm{k}}-\mu)/k_{B}T_{e}}+1},$ (4)

where $\mu$ is the chemical potential, $T_{e}$ is the electron temperature,
and $\epsilon_{b,s,\bm{k}}$ are the single-particle energies of the self-
consistent solutions of the following static Kohn–Sham equations at
$t=-\infty$:

$\displaystyle\hat{h}_{s,\bm{k}}(t=-\infty)u_{b,s,\bm{k}}(\bm{r},t=-\infty)=\epsilon_{b,s,\bm{k}}u_{b,s,\bm{k}}(\bm{r},t=-\infty).$

Note that the eigenstates $u_{b,s,\bm{k}}(\bm{r},t=-\infty)$ are used as the
initial conditions for Eq. (1).

Using these time-dependent Kohn–Sham orbitals, $u_{b,s,\bm{k}}(\bm{r},t)$, one
can evaluate the electric current as a function of time as

$\displaystyle\bm{J}(t)=-\frac{1}{\Omega_{cell}}\sum_{b,s}\frac{1}{\Omega_{BZ}}\int_{BZ}d\bm{k}f_{b,s,\bm{k}}\int_{cell}d\vec{r}u^{*}_{b,s,\bm{k}}(\bm{r},t)\bm{v}_{\bm{k}}(t)u_{b,s,\bm{k}}(\bm{r},t),$
(6)

where $\Omega_{cell}$ is the volume of the unit cell, and $\bm{v}_{\bm{k}}(t)$
is the velocity operator defined as

$\displaystyle\bm{v}_{\bm{k}}(t)=\frac{\left[\bm{r},\hat{h}_{s,\bm{k}}(t)\right]}{i\hbar},$
(7)

where the commutator means $\left[A,B\right]=AB-BA$. In this work, we evaluate
the optical properties of materials using the computed current, $\bm{J}(t)$.

###  II.2 Linear response calculation for the optical absorption of solids

As described in Sec. II.1, one can evaluate the electric current induced by
given electric fields. Hence, the TDDFT simulation yields the current as a
functional of electric fields, namely $\bm{J}(t)=\bm{J}[\bm{E}(t)](t)$. In the
weak-field limit, $|\bm{E}(t)|\rightarrow 0$, each component of the current
can be expanded up to the first order of the electric fields as

$\displaystyle J_{\alpha}(t)=\sum_{\beta}\int
dt^{\prime}\sigma_{\alpha\beta}(t-t^{\prime})E_{\beta}(t^{\prime}),$ (8)

where $J_{\alpha}$ is the $\alpha$-component of $\bm{J}(t)$, $E_{\beta}(t)$ is
the $\beta$-component of $\bm{E}(t)$, and $\sigma_{\alpha\beta}(t)$ is the
linear conductivity tensor in the time domain. By applying to the Fourier
transformation to Eq. (8), one can obtain the linear optical conductivity in
the frequency domain as

$\displaystyle\tilde{J}_{\alpha}(\omega)=\sum_{\beta}\tilde{\sigma}_{\alpha\beta}(\omega)\tilde{E}_{\beta}(\omega),$
(9)

where $\tilde{J}_{\alpha}(\omega)$, $\tilde{E}_{\beta}(\omega)$, and
$\tilde{\sigma}_{\alpha\beta}(\omega)$ are the Fourier transforms of
$J_{\alpha}(t)$, $E_{\beta}(t)$, and $\sigma_{\alpha\beta}(t)$, respectively.
Therefore, by analyzing the applied electric fields and induced current, one
can evaluate the linear optical conductivity,
$\tilde{\sigma}_{\alpha\beta}(\omega)$. Furthermore, one can evaluate the
dielectric function as

$\displaystyle\epsilon_{\alpha\beta}=\delta_{\alpha\beta}+4\pi
i\frac{\tilde{\sigma}_{\alpha\beta}}{\omega}$ (10)

and the absorption coefficient as

$\displaystyle\mu_{\alpha}(\omega)=\frac{2\omega}{c}\mathrm{Im}\left[\sqrt{\epsilon_{\alpha\alpha}}\right].$
(11)

For practical calculations, we employ an impulsive distortion as the electric
field that corresponds to the following vector potential:

$\displaystyle\bm{A}(t)=-k_{0}\bm{e}_{\bm{\beta}}\Theta(t),$ (12)

where $k_{0}$ is strength of the impulsive distortion, $\bm{e}_{\beta}$ is the
unit vector along the $\beta$-direction, and $\Theta(t)$ is the Heaviside step
function. Under the impulsive distortion described by Eq. (12), we solve Eq.
(1) and compute the induced electric current $\bm{J}(t)$. Based on Eq. (9), we
then evaluate the optical conductivity as

$\displaystyle\tilde{\sigma}_{\alpha\beta}(\omega)=\frac{1}{k_{0}}\int^{\infty}_{0}dtJ_{\alpha}(t)e^{i\omega
t-\gamma t},$ (13)

where $\gamma$ is an effective damping parameter used to reduce the numerical
noise due to the finite time of the simulations. In this work, we set $\gamma$
to $0.5$ eV. Using Eqs. (10) and (11), we evaluate the absorption coefficients
of the solids.

In this work, we study the absorption coefficients of bulk cobalt and nickel
by changing the electron temperature, $T_{e}$, in order to analyze the
transient optical properties of the materials after laser irradiation Sato
_et al._ (2014). All calculations in this work were performed using the
Octopus code Tancogne-Dejean  _et al._ (2020). We employ the adiabatic local
spin density approximation (ALSDA) for the exchange-correlation functional
Perdew and Wang (1992). For bulk cobalt, we employ a hexagonal single crystal
structure, and we set the lattice parameter $a$ to $2.51$ $\mathrm{\AA}$ and
the lattice constant ratio $c/a$ to $1.622$ Hermann (2017). The hexagonal
lattice is discretized into $24\times 24\times 38$ real-space grid points, and
the first Brillouin zone is discretized into $24^{3}$ $k$-points. For bulk
nickel, we employ an $\mathrm{fcc}$ lattice structure, and we set the lattice
constant $a$ to $3.52$ $\mathrm{\AA}$ Hermann (2017). The $\mathrm{fcc}$
lattice is discretized into $28^{3}$ real-space grid points, and the
corresponding Brillouin zone is discretized into $24^{3}$ $k$-points. Both
cobalt and nickel atoms are described using a norm-conserving pseudopotential
method, treating $3s$, $3p$, $3d$, and $4s$ electrons as valence electrons
Troullier and Martins (1991); Reis  _et al._ (2003); Oliveira and Nogueira
(2008).

##  III Results

###  III.1 Electronic structure and optical absorption of magnetic materials

To study the optical properties of laser-excited magnetic materials, we first
revisit the electronic structures of bulk cobalt and nickel as well as their
optical properties in the equilibrium phase.

Figure 1 (a) shows the electronic structure of bulk cobalt. The majority (red-
solid line) and minority (blue-dotted line) spin bands are illustrated
separately. Here, the electron temperature $T_{e}$ is set to $300$ K. As seen
from the figure, bulk cobalt exhibits the non-degenerate spin bands and is
indeed a magnetic system in the present simulation. The computed magnetic
moment $\mu$ at $T_{e}=300$ K is $1.7\mu_{B}$ per atom. Figure 1 (b) shows the
same electronic structure of bulk cobalt but in a wider energy region. Here,
the cobalt $3s$ bands are located at around $-95$ eV from the Fermi energy,
and the $3p$ bands are located at around $-60$ eV. In both semicore ($3s$ and
$3p$) bands, large energy splits are observed. These are exchange splits due
to the intrinsic magnetization and are consistent with previously reported
large exchange splits Valencia  _et al._ (2010); Tesch  _et al._ (2014). The
computed exchange splitting of the cobalt $3p$ bands in Fig. 1 (b) is about
$2.3$ eV.

Figure 1:  Electronic structure of bulk cobalt. The band structure is computed
at $T_{e}=300$ K. Panel (a) shows the majority (red) and minority (blue) spin
bands around the Fermi surface. Panel (b) shows the same electronic structure
as panel (a) but in a wider energy range, which includes the Co $3s$ and $3p$
bands.

Figure 2 (a) shows the electronic structure of bulk nickel, in which both the
majority and minority spin bands are illustrated. In Fig. 2 (b), the same
electronic structure is shown for a wider energy range. As for bulk cobalt
(Fig. 1), bulk nickel is also a magnetic material, and the two spin bands are
non-degenerate. The computed magnetic moment at $T_{e}=300$ K is $0.67\mu_{B}$
per atom. As seen from Fig. 2 (b), the semicore bands of nickel also exhibit a
large exchange split. The computed exchange split of the nickel $3p$ bands is
about $1$ eV.

Figure 2:  Electronic structure of bulk nickel. The band structure is computed
at $T_{e}=300$ K. Panel (a) shows majority (red) and minority (blue) spin
bands around the Fermi surface. Panel (b) shows the same electronic structure
as panel (a) but in a wider energy range, which includes the Ni $3s$ and $3p$
bands.

Having revisited the basic electronic structure of cobalt and nickel, we
investigate the optical properties of these magnetic materials in the
equilibrium phase via real-time linear-response calculations based on the
TDDFT introduced in Sec. II.2. Figure 3 (a) shows the computed absorption
coefficient of bulk cobalt with an electron temperature of $300$ K. Here,
three simulation results are shown. The red solid line shows the results of
the full TDDFT simulation with the ALSDA. The blue dashed line shows the
results obtained using the independent-particle (IP) approximation, where the
time-dependence of the Hartree-exchange-correlation potential is ignored, and
$v_{Hxc}[\rho_{e}(\bm{r},t),\rho_{s}(\bm{r},t)]$ is frozen at $t=0$. The green
dotted line shows the results of the TDDFT simulation using the spin-
degenerate electronic configuration.

As seen from Fig. 3 (a), the full TDDFT result shows a sharp increase in the
photoabsorption at around $56$ eV. This energy corresponds to the $M_{2,3}$
absorption edge of bulk cobalt. Around the $M_{2,3}$ edge, the result obtained
using the IP approximation shows a large deviation from the full TDDFT
simulation result. This indicates that the microscopic screening effect in the
time-dependent Hartree potential has a significant role in the photoabsorption
around the $M_{2,3}$ edge of cobalt. This is known as the strong local-field
effect for semicore electronic responses of transition metals, reflecting a
large spatial overlap between the electronic states of the $3p$ and $3d$ bands
Krasovskii and Schattke (1999).

From Fig. 3 (a), it can be seen that the result of the spin-degenerate TDDFT
simulation is similar to that of the full TDDFT simulation, exhibiting a blue
shift of the spectrum around the $M_{2,3}$ absorption edge. The blue shift of
the absorption can be understood as the disappearance of the exchange split of
the $3p$ bands in the spin-degenerate electronic configuration: In the spin
nondegenerate configuration, as shown in Fig. 1 (b), the higher-energy $3p$
band is closer to the Fermi surface than the other spin band due to the
exchange split. Once the exchange split vanishes due to the spin degeneracy,
the energy difference between the $3p$ bands and the Fermi surface effectively
increases, resulting in the blue shift of the absorption edge. This
circumstance suggests the possibility to monitor the magnetization of
materials via the position of the semicore absorption edge.

Figure 3:  Photoabsorption spectra of (a) cobalt and (b) nickel. In both
panels, the results of the full TDDFT simulation are shown by the red solid
lines, those of the IP approximation are shown by the blue dashed lines, and
those of the TDDFT simulation with the spin-degenerate electronic
configuration are shown by the green dotted lines.

Figure 3 (b) shows the absorption coefficient of bulk nickel. By comparing
Fig. 3 (a) and Fig. 3 (b), it can be observed that cobalt and nickel show
similar behaviors. Therefore, the features discussed above are not unique
properties of cobalt but rather general properties of magnetic materials.

###  III.2 Transient optical properties of laser-excited magnetic materials

Here, we study the optical properties of laser-excited magnetic materials
using finite-electron-temperature TDDFT simulations by mimicking the two-
temperature state of laser-excited matter, in which the electronic system
reaches a thermalized hot-electron state while the ionic system remains cold
Sato  _et al._ (2014). We evaluate the change in the absorption coefficient,
$\mu(\omega)$, by increasing the electron temperature, $T_{e}$. Figure 4 (a)
shows the change in the absorption coefficient of cobalt for different
electron temperatures,
$\Delta\mu(\mu,T_{e})=\mu(\omega,T_{e})-\mu(\omega,T_{e}=300~{}\mathrm{K})$,
from room temperature ($T_{e}=300~{}\mathrm{K}$). Similarly, Figure 4 (b)
shows the results for bulk nickel. As seen from Fig. 4, cobalt and nickel show
similar features: the change in the absorption coefficients can be interpreted
as the combination of a decrease in the photoabsorption in the narrower energy
range around the $M_{2,3}$ absorption edge and an increase in the
photoabsorption in the wider energy range. For cobalt, a significant decrease
in the photoabsorption is observed even for a high electron temperature
($T_{e}=0.5$ eV). By contrast, for nickel, a relatively weak decrease in the
absorption is observed, and this decrease is even overcome by the increase in
the absorption observed for high electron temperatures. This indicates that
the narrow-energy-range decrease in the photoabsorption around the $M_{2,3}$
edge reflects a magnetic property of materials since cobalt has a larger
magnetization than nickel.

Figure 4:  Change in the photoabsorption, $\Delta\mu$, for different electron
temperatures, $T_{e}$, for (a) Co and (b) Ni. The results were obtained using
the TDDFT with different electron temperatures.

To confirm this hypothesis, we evaluate the change in the absorption spectrum
using the spin-degenerate electronic configuration. Figure 5 shows the change
in the absorption coefficients with the increase in the electron temperature,
$T_{e}$, for (a) cobalt and (b) nickel using the spin-degenerate electronic
configuration. In agreement with our hypothesis, neither cobalt nor nickel
show a significant decrease in the photoabsorption around the $M_{2,3}$ edge
when the two spin components are degenerate. Therefore, we can confirm that
the decrease n the photoabsrotion in the narrow energy range around the
absorption edge in Figs. 4 (a) and (b) is an intrinsic property of magnetic
materials. As seen from Fig. 4, both cobalt and nickel with the spin-
degenerate configuration show a photoabsorption increase in the wide energy
range around the absorption edge. A similar behavior has been observed in a
previous experiment for laser-excited bulk titanium, and the photoabsortion
increase has been explained in terms of the modification in the local-field
effect due to light-induced ultrafast electron localization around transition
metal elements Volkov  _et al._ (2019). Therefore, the wide-energy-range
absorption increase in cobalt and nickel can be also understood as a general
feature of transition metals due to the light-induced electron localization.

Figure 5:  Change in the photoabsorption, $\Delta\mu$, with the increase in
the electron temperature, $T_{e}$, for (a) Co and (b) Ni. The results were
obtained using the TDDFT with the spin-degenerate electronic configuration.

To develop a microscopic understanding of the observed decrease in
photoabsorption around the $M_{2,3}$ absorption edge, we evaluate the magnetic
properties of cobalt and nickel at a finite electron temperature, $T_{e}$.
Figure 6 shows the magnetization, $\mu$, and the exchange split of the $3p$
bands, $\Delta_{xc}$, for bulk (a) cobalt and (b) nickel. As seen from Fig. 6
(a), the magnetization of cobalt decreases with the increase in the electron
temperature but remains finite at $T_{e}=0.5$ eV. By contrast, as seen from
Fig. 6 (b), the magnetization of nickel decreases with the increase in $T_{e}$
and disappears at $T_{e}=0.3$ eV. In both cases, the exchange split,
$\Delta_{xc}$, shows a very similar trend to that of the magnetization.
Furthermore, the evolution of the exchange split, $\Delta_{xc}$, upon
increasing the electron temperature is similar to that observed for the
photoabsorption: The photoabsorption of cobalt continues to decrease around
the absorption edge for $T_{e}<0.5$ eV (see Fig. 4 (a)), whereas that of
nickel is saturated at around $T_{e}=0.3$ eV (see Fig. 4 (b)) due to the
closing of the exchange splitting of the nickel $3p$ bands, $\Delta_{xc}$.
This indicates that the decrease in the photoabsorption around the $M_{2,3}$
absorption edge of laser-excited cobalt and nickel can be understood in terms
of the blue shift of the absorption edge through the reduction in the exchange
split upon increasing the electron temperature.

Figure 6:  Magnetic properties of (a) Co and (b) Ni at a finite electron
temperature. In each panel, the magnetic moment $\mu$ and the exchange-
splitting of the $3p$ bands are shown as a function of the electron
temperature.

Based on the above analysis, we find that the change in the photoabsorption of
laser-excited cobalt and nickel consists of the photoabsorption increase in a
wider energy range around the absorption edge and the photoabsorption decrease
in a narrow energy range around the absorption edge. The photoabsorption
increase is a common feature of laser-excited transition metals, which
reflects the laser-induced electron localization and modification in the
microscopic screening properties. On the other hand, the photoabsorption
decrease is a unique feature of laser-excited magnetic materials, which
reflects the light-induced local demagnetization around the ions and the
subsequent reduction in the exchange splitting of semicore states. Therefore,
this finding indicates that element-specific local magnetization dynamics can
be investigated via time-resolved transient absorption spectroscopy as
transient magnetic properties are recoded in transient absorption spectra.

##  IV Summary and Outlook

We studied the optical properties of laser-excited bulk cobalt and nickel by
extending the first-principles calculation on the transient absorption
spectroscopy with the TDDFT Sato  _et al._ (2014) to magnetic materials. The
simulation results show that the transient absorption of laser-excited
magnetic materials mainly consists of two components. One is the decrease in
the photoabsorption in the narrow energy range around the $M_{2,3}$ absorption
edge, and the other is the increase in the photoabsorption in the wider energy
range. The wider-range photoabsorption increase is consistent with a previous
result reported for laser-excited titanium Volkov  _et al._ (2019), where the
absorption increase had been explained in terms of the modification in the
local-field effects through laser-induced electron localization. Therefore,
the increase in the photoabsorption of cobalt and nickel upon increasing the
electron temperature can be interpreted as a general feature of laser-excited
transition metals. By contrast, we found that the photoabsorption decrease
around the $M_{2,3}$ edge is an intrinsic property of magnetic materials.
Based on the microscopic analysis of the magnetic properties at a finite
electron temperature, the decrease in photoabsorption can be understood as the
blue shift of the absorption edge due to the decrease in the exchange
splitting.

The above analysis clarifies the relation between element-specific local
magnetic properties and optical responses of semicore states of the
corresponding element. Based on this finding, one may investigate light-
induced magnetization and spin dynamics in the time domain using transient
absorption spectroscopy. For example, the application of the attosecond
transient absorption spectroscopy Schultze  _et al._ (2014); Lucchini  _et
al._ (2016) to magnetic materials may enable access to the ultrafast spin
dynamics and magnetization with the attosecond resolution. Therefore, in
addition to the recently developed attosecond circular dichroism technique
with circularly polarized probe pulses Siegrist  _et al._ (2019), the
transient absorption spectroscopy with linearly polarized probe pulses can be
a complementary and alternative approach to study real-time magnetization and
spin dynamics in magnetic materials.

###### Acknowledgements.

This work was supported by JSPS KAKENHI Grant Number JP20K14382. The author
thanks Enago for the English language review.

## References

  * Brabec and Krausz (2000) T. Brabec and F. Krausz, Rev. Mod. Phys. 72, 545 (2000).
  * Krausz and Ivanov (2009) F. Krausz and M. Ivanov, Rev. Mod. Phys. 81, 163 (2009).
  * Mourou  _et al._ (2012) G. Mourou, N. Fisch, V. Malkin, Z. Toroker, E. Khazanov, A. Sergeev, T. Tajima, and B. Le Garrec, Optics Communications 285, 720 (2012).
  * Schiffrin  _et al._ (2013) A. Schiffrin, T. Paasch-Colberg, N. Karpowicz, V. Apalkov, D. Gerster, S. Mühlbrandt, M. Korbman, J. Reichert, M. Schultze, S. Holzner, J. V. Barth, R. Kienberger, R. Ernstorfer, V. S. Yakovlev, M. I. Stockman, and F. Krausz, Nature 493, 70 (2013).
  * Higuchi  _et al._ (2017) T. Higuchi, C. Heide, K. Ullmann, H. B. Weber, and P. Hommelhoff, Nature 550, 224 (2017).
  * Sato  _et al._ (2019) S. A. Sato, J. W. McIver, M. Nuske, P. Tang, G. Jotzu, B. Schulte, H. Hübener, U. De Giovannini, L. Mathey, M. A. Sentef, A. Cavalleri, and A. Rubio, Phys. Rev. B 99, 214302 (2019).
  * McIver  _et al._ (2020) J. W. McIver, B. Schulte, F.-U. Stein, T. Matsuyama, G. Jotzu, G. Meier, and A. Cavalleri, Nature Physics 16, 38 (2020).
  * Oka and Aoki (2009) T. Oka and H. Aoki, Phys. Rev. B 79, 081406 (2009).
  * Lindner  _et al._ (2011) N. H. Lindner, G. Refael, and V. Galitski, Nature Physics 7, 490 (2011).
  * Schultze  _et al._ (2014) M. Schultze, K. Ramasesha, C. Pemmaraju, S. Sato, D. Whitmore, A. Gandman, J. S. Prell, L. J. Borja, D. Prendergast, K. Yabana, D. M. Neumark, and S. R. Leone, Science 346, 1348 (2014).
  * Zürch  _et al._ (2017) M. Zürch, H.-T. Chang, L. J. Borja, P. M. Kraus, S. K. Cushing, A. Gandman, C. J. Kaplan, M. H. Oh, J. S. Prell, D. Prendergast, C. D. Pemmaraju, D. M. Neumark, and S. R. Leone, Nature Communications 8, 15734 (2017).
  * Lucchini  _et al._ (2016) M. Lucchini, S. A. Sato, A. Ludwig, J. Herrmann, M. Volkov, L. Kasmi, Y. Shinohara, K. Yabana, L. Gallmann, and U. Keller, Science 353, 916 (2016).
  * Moulet  _et al._ (2017) A. Moulet, J. B. Bertrand, T. Klostermann, A. Guggenmos, N. Karpowicz, and E. Goulielmakis, Science 357, 1134 (2017).
  * Buades  _et al._ (2021) B. Buades, A. Picón, E. Berger, I. León, N. Di Palo, S. L. Cousin, C. Cocchi, E. Pellegrin, J. H. Martin, S. Mañas-Valero, E. Coronado, T. Danz, C. Draxl, M. Uemoto, K. Yabana, M. Schultze, S. Wall, M. Zürch, and J. Biegert, Applied Physics Reviews 8, 011408 (2021).
  * Lucchini  _et al._ (2021) M. Lucchini, S. A. Sato, G. D. Lucarelli, B. Moio, G. Inzani, R. Borrego-Varillas, F. Frassetto, L. Poletto, H. Hübener, U. De Giovannini, A. Rubio, and M. Nisoli, Nature Communications 12, 1021 (2021).
  * Siegrist  _et al._ (2019) F. Siegrist, J. A. Gessner, M. Ossiander, C. Denker, Y.-P. Chang, M. C. Schröder, A. Guggenmos, Y. Cui, J. Walowski, U. Martens, J. K. Dewhurst, U. Kleineberg, M. Münzenberg, S. Sharma, and M. Schultze, Nature 571, 240 (2019).
  * Runge and Gross (1984) E. Runge and E. K. U. Gross, Phys. Rev. Lett. 52, 997 (1984).
  * Bertsch  _et al._ (2000) G. F. Bertsch, J.-I. Iwata, A. Rubio, and K. Yabana, Phys. Rev. B 62, 7998 (2000).
  * Volkov  _et al._ (2019) M. Volkov, S. A. Sato, F. Schlaepfer, L. Kasmi, N. Hartmann, M. Lucchini, L. Gallmann, A. Rubio, and U. Keller, Nature Physics 15, 1145 (2019).
  * Sato (2021) S. A. Sato, Computational Materials Science 194, 110274 (2021).
  * Kleinman and Bylander (1982) L. Kleinman and D. M. Bylander, Phys. Rev. Lett. 48, 1425 (1982).
  * Troullier and Martins (1991) N. Troullier and J. L. Martins, Phys. Rev. B 43, 1993 (1991).
  * Sato  _et al._ (2014) S. A. Sato, Y. Shinohara, T. Otobe, and K. Yabana, Phys. Rev. B 90, 174303 (2014).
  * Tancogne-Dejean  _et al._ (2020) N. Tancogne-Dejean, M. J. T. Oliveira, X. Andrade, H. Appel, C. H. Borca, G. Le Breton, F. Buchholz, A. Castro, S. Corni, A. A. Correa, U. De Giovannini, A. Delgado, F. G. Eich, J. Flick, G. Gil, A. Gomez, N. Helbig, H. Hübener, R. Jestädt, J. Jornet-Somoza, A. H. Larsen, I. V. Lebedeva, M. Lüders, M. A. L. Marques, S. T. Ohlmann, S. Pipolo, M. Rampp, C. A. Rozzi, D. A. Strubbe, S. A. Sato, C. Schäfer, I. Theophilou, A. Welden, and A. Rubio, The Journal of Chemical Physics 152, 124119 (2020).
  * Perdew and Wang (1992) J. P. Perdew and Y. Wang, Phys. Rev. B 45, 13244 (1992).
  * Hermann (2017) K. Hermann,  _Crystallography and surface structure: an introduction for surface scientists and nanoscientists_ (John Wiley & Sons, 2017).
  * Reis  _et al._ (2003) C. L. Reis, J. M. Pacheco, and J. L. Martins, Phys. Rev. B 68, 155111 (2003).
  * Oliveira and Nogueira (2008) M. J. Oliveira and F. Nogueira, Computer Physics Communications 178, 524 (2008).
  * Valencia  _et al._ (2010) S. Valencia, A. Kleibert, A. Gaupp, J. Rusz, D. Legut, J. Bansmann, W. Gudat, and P. M. Oppeneer, Phys. Rev. Lett. 104, 187401 (2010).
  * Tesch  _et al._ (2014) M. F. Tesch, D. Legut, H.-C. Mertins, M. C. Gilbert, C. Jansing, J. Hamrle, J. Rusz, P. M. Oppeneer, D. E. Bürgler, C. M. Schneider, A. Gaupp, and U. Berges, Phys. Rev. B 89, 140404 (2014).
  * Krasovskii and Schattke (1999) E. E. Krasovskii and W. Schattke, Phys. Rev. B 60, R16251 (1999).


# Federated Learning for Heterogeneous Bandits with Unobserved Contexts

Jiabin Lin and Shana Moothedath  Electrical and Computer Engineering
Iowa State University, Ames, IA, USA
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study the federated stochastic multi-arm contextual bandits with unknown
contexts, in which $M$ agents face $M$ different bandit problems and
collaborate to learn. The communication model consists of a central server and
$M$ agents, and the agents share their estimates with the central server
periodically to learn to choose optimal actions to minimize the total regret.
We assume that the exact contexts are not observable, and the agents observe
only a distribution of contexts. Such a situation arises, for instance, when
the context itself is a noisy measurement or based on a prediction mechanism.
Our goal is to develop a distributed and federated algorithm that facilitates
collaborative learning among the agents to select a sequence of optimal
actions to maximize the cumulative reward. By performing a feature vector
transformation, we propose an elimination-based algorithm and prove the regret
bound for linearly parametrized reward functions. Finally, we validated the
performance of our algorithm and compared it with another baseline approach
using numerical simulations on synthetic data and the real-world movielens
dataset.

##  I Introduction

Online learning for sequential decision-making frequently arises in diverse
domains, spanning control systems and robotics [1, 2], clinical trials [3],
communications [4], and recommender systems [5]. The multi-arm bandits (MAB)
model the iterative interaction of a system with the environment to learn
optimal decisions [6]. In MABs, the learner aims to maximize the reward by
engaging in rounds where they interact with the environment, choose actions
based on current estimates, receive rewards, and update estimates accordingly.

A central challenge in bandit problems is the exploration-exploitation trade-
off. While accurate estimation with minimal exploration is ideal for
maximizing rewards, insufficient exploration often leads to suboptimal
decisions. Striking a suitable exploration-exploitation balance is crucial and
this is even more challenging in scenarios where the exact contexts are
unknown. In many practical instances, the exact contexts are often unknown,
where the contexts are noisy measurements or based on certain prediction
mechanisms, such as weather or stock market prediction. In such situations,
decisions must be made based on limited information.

Over the last decade, multi-agent MAB problems have been widely studied in
many papers [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]. In multi-agent MAB,
multiple agents/learners collaborate to learn and optimize their decisions
based on their local knowledge about the environment. Recently, federated
learning has gained attention due to increasing focus on security and privacy.
In federated learning, the agents do not share the raw data with the other
agents or the server but rather share only the local estimates. Federated MABs
are also studied in some of the recent papers [18, 19, 20, 21].

Our goal in this paper is to present an algorithm for the distributed and
federated contextual multi-armed bandit problem with $M$ agents/learners when
the exact context is unknown. In our setting, $M$ agents work collaboratively
and concurrently to learn optimal actions to maximize the total (cumulative)
reward. The agents communicate with a central server in a periodic fashion and
update their local models by utilizing the global information from the central
server. Bandit learning with hidden contexts is challenging for the learner
because estimating the reward function relies on noisy observations due to
unknown exact contexts. To overcome these challenges, we make use of a feature
mapping technique used in [22] for a single-agent bandit setting to transform
the problem. After this transformation, a new set of feature vectors is
presented so that under this set of $d$-dimensional context feature vectors,
the reward is an unbiased observation for the action choice. Motivated by the
approach in [23], we propose a federated algorithm and prove the regret bound
for the linear reward function. The key difference in our approach is that we
consider a setting where the contexts are unobservable, while in [23], the
contexts are known.

This paper makes the following contributions.

  1. $\bullet$

We model a distributed $M$-agent, federated stochastic linear contextual
bandit where the agents face different bandits and the exact contexts are
unknown.

  2. $\bullet$

We present a Fed-PECD algorithm and prove the regret bound for distributed
stochastic bandits with linear parametrized reward function when the exact
context is hidden and the context distribution is available.

  3. $\bullet$

We validated the performance of our approach and compared the different models
via numerical simulations on synthetic data and on real-world movielens data.

The organization of the paper is as follows. In Section II, we present the
related work. In Section III, we discuss the notations used in the paper,
problem formulation, and a motivating scenario for the problem. In Section IV,
we present our proposed algorithm and regret analysis of the algorithm. In
Section V, we present the numerical experiments and in Section VI, we give the
concluding remarks.

##  II Related Work

Distributed bandits have been widely studied for different learning models and
communication models. The stochastic multi-agent linear contextual bandit
problem was studied in [7], and an Upper Confidence Bound (UCB)-based
algorithm was proposed with guarantees. The communication model considered in
[7] consists of a central server that can communicate with all the agents. In
[7], the agents observe the exact contexts while we consider cases where the
contexts are unobservable and only the context distribution is available.
Contextual bandits with context distribution (unknown context) were studied in
[22] for a single-agent setting. Later, references [8, 9] considered a
distributed contextual MAB problem when the contexts are hidden and proposed
an elimination-based algorithm. We note that the learning models in [7, 8, 9]
considered a setting where all agents encounter the same bandit. In contrast,
this paper introduces a context where agents face different bandit problems,
thus characterizing heterogeneous agents. In [24], we studied the feature
selection problem for multi-agent bandits with a fixed action set, which is
different from this work, which studies CBs.

Decentralized MAB problems have been studied in many papers including [10, 11,
12, 13, 14, 15, 16, 17] and different communications models were considered,
such as each agent communicates with only two other agents [13], each agent
communicate only once [12], and each agent can communicate with every other
agent. We note that the model considered in this paper is a centralized and
federated communication model. Federated decentralized MAB problems are
studied in [25, 26] with the primary focus on differential privacy. In [18] a
fully decentralized federated MAB problem was investigated where agents find
the optimal arm with limited communication and can only share their rewards
with neighbors. Reference [19, 20] considered a federated MAB problem where
the local agent and central server collaborate to maximize the cumulative
reward based on the local and global reward with and without personalization,
respectively. A federated residual learning algorithm was introduced in [21]
for the federated bandit problem where the agent chooses the optimal arm based
on the global and local model with communication latency.

##  III Notations and Problem Formulation

###  III-A Notations

The norm of a vector $z\in\mathbb{R}^{d}$ with respect to a matrix
$V\in\mathbb{R}^{d\times d}$ is defined as $\|z\|_{V}:=\sqrt{z^{\top}Vz}$.
$|z|$ for a vector $z$ denotes element-wise absolute values. Further, ⊤
denotes matrix or vector transpose, $A^{\dagger}$ denotes the pseudo-inverse
of a matrix $A$, and $\langle\cdot,\cdot\rangle$ denotes inner product. For an
integer $N$, we define $\left[N\right]:=\\{1,2,\ldots,N\\}$. We use
$\|\cdot\|$ to denote the induced $\ell_{2}$ norm.

###  III-B Problem Formulation

In this section, we first present the standard linear contextual bandit
problem. Let ${\pazocal{A}}$ be the action set with $|{\pazocal{A}}|=K$,
${\pazocal{C}}$ be the context set, and the environment is defined by a fixed
and unknown reward function
$y:{\pazocal{A}}\times{\pazocal{C}}\rightarrow\mathbb{R}$. In a linear bandit
setting, at any round $t\in\mathbb{N}$, the agent observes a context
$c_{t}\in{\pazocal{C}}$ and chooses an action $a_{t}\in{\pazocal{A}}$. Each
context-action pair $\left(a,c\right)$, $a\in{\pazocal{A}}$ and
$c\in{\pazocal{C}}$, is associated with a feature vector
$\phi_{a,c}\in\mathbb{R}^{d}$, i.e.,
$\phi_{a_{t},c_{t}}=\phi\left(a_{t},c_{t}\right)$. Upon selection of an action
$a_{t}$, the agent observes a reward $y_{t}\in\mathbb{R}$,
$y_{t}:=\langle\theta^{\star},\phi_{a_{t},c_{t}}\rangle+\eta_{t},$ where
$\theta^{\star}\in\mathbb{R}^{d}$ is the unknown reward parameter,
$\langle\theta^{\star},\phi_{a_{t},c_{t}}\rangle=r\left(a_{t},c_{t}\right)$ is
the expected reward for action $a_{t}$ at round $t$, i.e.,
$r\left(a_{t},c_{t}\right)=\mathbb{E}[y_{t}]$, and $\eta_{t}$ is
$\sigma$-Gaussian, additive noise. The goal is to choose optimal actions
$a_{t}^{\star}$ for all $t\in T$ such that the cumulative reward,
$\sum_{t=1}^{T}y_{t}$, is maximized. This is equivalent to minimizing the
cumulative (pseudo)-regret denoted as

$\pazocal{R}_{T}=\sum_{t=1}^{T}\langle\theta^{\star},\phi_{a_{t}^{\star},c_{t}}^{t}\rangle-\sum_{t=1}^{T}\langle\theta^{\star},\phi_{a_{t},c_{t}}^{t}\rangle.$
(1)

Here $a_{t}^{\star}$ is the optimal/best action for context $c_{t}$, and
$a_{t}$ is the action chosen by the agent for context $c_{t}$.

In this paper, we consider a federated linear contextual bandit problem
consisting of $M$ agents with heterogeneous data. The agent’s goal is to learn
collaboratively and concurrently. Each agent $i\in[M]$ is a user in the system
whose user profile is denoted by $c_{i}\in\mathbb{R}^{d}$ and all agents have
the same action set ${\pazocal{A}}=[K]$. The context vector $c_{i}$ cannot be
observed by the agent $i$ and only the context distribution $\mu_{i}$ is
available. This situation occurs in various scenarios, such as in recommender
systems, where other family members may use the same user profile to log in to
Netflix. Consequently, the learner lacks knowledge of the exact user
information (context vector).

The goal of the agents is to learn to choose optimal actions based on their
local observation. To achieve this, at every time step, the agents choose
actions from their action set and receive the reward
$y_{a,i}=\langle\theta_{a_{i,t}},\phi_{a_{i,t},c_{i}}\rangle+\eta_{i,t}$,
where $\phi_{a_{i,t},c_{i}}$ is the feature vector of agent $i$ for action
$a_{i,t}$ and $\eta_{i,t}$ is the random noise. Note that the rewards received
by the agents for the same action are different as it is a function of the
agent’s context vector, thus capturing the heterogeneous nature of the agents.
Further, for action $a\in{\pazocal{A}}$, the reward parameter $\theta_{a}$
depends on the action and is the same across agents. Such a model hence
captures the heterogeneous nature of the agents while still allowing a
collaborative learning paradigm due to the shared parameter
$\\{\theta_{a}\\}_{a\in{\pazocal{A}}}$. The linear structure of the reward
function captures the intrinsic correlation between rewards for different
agents pulling the same arm with the same parameter $\theta_{a}$.

Our goal is to learn an optimal mapping $\mu_{i}\rightarrow a_{i}^{\star}$ of
context distribution to action that maximizes the cumulative reward, where
$a_{i}^{\star}$ is the optimal action for user/agent $i$, for all $i\in[M]$.
In other words, we try to find the optimal estimated action that minimizes the
cumulative regret

$\displaystyle\pazocal{R}\left(T\right)=\sum_{i=1}^{M}\sum_{t=1}^{T}\langle\theta_{a_{i}^{\star}},\phi_{a_{i}^{\star},c_{i}}\rangle-\sum_{i=1}^{M}\sum_{t=1}^{T}\langle\theta_{a_{i,t}},\phi_{a_{i,t},c_{i}}\rangle,$
(2)

where $a_{i}^{\star}\in{\pazocal{A}}$ is the optimal action for agent $i$
provided we know $\phi$ and $\mu_{i}$, but not $c_{i}$.

Our communication model consists of a central server in the system which can
communicate with each agent periodically with zero latency. Each agent shares
its local estimate with the central server, the server then aggregates the
estimates and broadcasts a global estimate to each agent. Each agent now
updates their local model. Note that communication is always a major
bottleneck, and we need to carefully consider its usage to keep the
communication cost as small as possible. The agents can only share their
estimates with the central server to obtain the global estimated model,
without sharing raw data. In this way, the local data is always private for
each agent and hence the communication model is federated. We have the
following standard assumptions on the parameters.

######  Assumption 1.

There exist constants $s\geqslant 0$, $0\leqslant\ell,L\leqslant 1$ such that
$\left\|\theta_{a}\right\|_{2}\leqslant s$,
$0\leqslant\ell\leqslant\left\|\phi_{a,c_{i}}\right\|_{2}\leqslant L\leqslant
1$, for all $i\in[M]$ action $a\in{\pazocal{A}}$.

######  Assumption 2.

Each element $\eta_{i,t}$ of the noise sequence
$\\{\eta_{i,t}\\}_{i=1,t=1}^{M,\infty}$ is a 1-subgaussian sampled independent
with $\mathbb{E}[\eta_{i,t}]=0$, $\mathbb{E}[e^{\lambda\eta_{i,t}}]\leqslant
e^{\frac{\lambda^{2}}{2}}$ for any $\lambda>0$.

##  IV The Proposed Algorithm and Guarantee

This section presents our proposed algorithm and its regret guarantee.

Algorithm IV.1 Fed-PECD: agent $i$

Input: $T,M,K$, $\alpha$, $f_{p}$

1:Nature chooses $\mu_{t}\in{\pazocal{P}}\left({\pazocal{C}}\right)$ and
learner observes $\mu_{t}$

2:Set $\Psi_{t}=\\{{\psi}_{a,\mu_{i}}:a\in{\pazocal{A}}\\}$ where
$\\{{\psi}_{a,\mu_{i}}:=\mathbb{E}_{c_{i}\sim\mu_{i}}[\phi_{a,c_{i}}]\\}$

3:Initialization: Pull each arm $a\in{\pazocal{A}}$ and receive reward
$y_{a,i};\hat{\theta}_{a,i}^{0}\leftarrow\frac{y_{a,i}\psi_{a,\mu_{i}}}{\left\|\psi_{a,\mu_{i}}\right\|^{2}}$;
Send $\left\\{\hat{\theta}_{a,i}^{0}\right\\}_{a\in{\pazocal{A}}}$ to the
server; ${\pazocal{A}}_{i}^{0}\leftarrow{\pazocal{A}};p\leftarrow 1$

4:while not reaching the time horizon $T$ do

5: Receive
$\left\\{\left(\hat{\theta}_{a}^{p},V_{a}^{p}\right)\right\\}_{a\in{\pazocal{A}}^{p-1}}$
from the server

6: for $a\in{\pazocal{A}}_{i}^{p-1}$ do

7:
$\hat{r}_{a,i}^{p}\leftarrow\psi_{a,\mu_{i}}^{\top}\hat{\theta}_{a}^{p},\quad
u_{a,i}^{p}\leftarrow\alpha\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}/\ell$

8: end for

9:

$\displaystyle\hat{a}_{i}^{p}\leftarrow\arg\max\limits_{a\in{\pazocal{A}}_{i}^{p-1}}\hat{r}_{a,i}^{p},{\pazocal{A}}_{i}^{p}\leftarrow\\{a\in{\pazocal{A}}_{i}^{p-1}\mid\hat{r}_{a,i}^{p}+u_{a,i}^{p}\geqslant\hat{r}_{\hat{a}_{i}^{p},i}^{p}-u_{\hat{a}_{i}^{p},i}^{p}\\}$

10: Send ${\pazocal{A}}_{i}^{p}$ to the central server

11: Receive $f_{a,i}^{p}$ for all $a\in{\pazocal{A}}_{i}^{p}$

12: for $a\in{\pazocal{A}}_{i}^{p}$ do

13: Pull arm $a$ $f_{a,i}^{p}$ times and receive
$\left\\{y_{a,i}\right\\}_{t\in{\pazocal{T}}_{a,i}^{p}}$

14: end for

15: Send $\left\\{\hat{\theta}_{a,i}^{p}\right\\}_{a\in{\pazocal{A}}_{i}^{p}}$
to the server; pull $\hat{a}_{i}^{p}$ until phase length equals $f_{p}+K$

16: $p\leftarrow p+1$

17:end while

###  IV-A Federated Phased Elimination with Context Distribution (Fed-PECD)
Algorithm

Algorithm IV.2 Fed-PECD: Central server

Input: $T,M,K$, $\alpha$, $f_{p}$

1:Initialization: Receive
$\left\\{\hat{\theta}_{a,i}^{0}\right\\}_{a,i};\bar{e}_{a,i}\leftarrow\frac{\hat{\theta}_{a,i}^{0}}{\left\|\hat{\theta}_{a,i}^{0}\right\|}$
for all
$i\in[M],a\in{\pazocal{A}};V_{a}^{1}\leftarrow(\sum_{i\in[M]}\frac{\hat{\theta}_{a,i}^{0}(\hat{\theta}_{a,i}^{0})^{\top}}{\left\|\hat{\theta}_{a,i}^{0}\right\|})^{\dagger}$,
$\hat{\theta}_{a}^{1}\leftarrow
V_{a}^{1}\left(\sum_{i\in[M]}\hat{\theta}_{a,i}^{0}\right)$ for all
$a\in{\pazocal{A}};$ Broadcast
$\left\\{\hat{\theta}_{a}^{1},V_{a}^{1}\right\\}_{a\in{\pazocal{A}}};p\leftarrow
1$

2:while not reaching the time horizon $T$ do

3: Receive

$\displaystyle\left\\{{\pazocal{A}}_{i}^{p}\right\\}_{i\in[M]}$

; Set
$\scalebox{0.89}{\mbox{$\displaystyle{\pazocal{A}}^{p}\leftarrow\cup_{i=1}^{M}{\pazocal{A}}_{i}^{p}$}},\scalebox{0.89}{\mbox{$\displaystyle\pazocal{R}_{a}^{p}\leftarrow\left\\{i:a\in{\pazocal{A}}_{i}^{p}\right\\}$}}$

4: Solve the multi-agent G-optimal design problem, and obtain solution
$\pi^{p}=\left\\{\pi_{a,i}^{p}\right\\}_{i\in[M],a\in{\pazocal{A}}_{i}^{p}}$

5: For every agent $i$, send
$\left\\{f_{a,i}^{p}:=\left\lceil\pi_{a,i}^{p}f_{p}\right\rceil\right\\}_{a\in{\pazocal{A}}_{i}^{p}}$

6: Receive
$\left\\{(a,\hat{\theta}_{a,i}^{p})\right\\}_{a\in{\pazocal{A}}_{i}^{p}}$ from
each agent $i$

7: for $a\in A^{p}$ do

8:

$\displaystyle
V_{a}^{p+1}\leftarrow(\sum_{i\in\pazocal{R}_{a}^{p}}f_{a,i}^{p}\frac{\hat{\theta}_{a,i}^{p}\left(\hat{\theta}_{a,i}^{p}\right)^{\top}}{\left\|\hat{\theta}_{a,i}^{p}\right\|^{2}})^{\dagger},\hat{\theta}_{a}^{p+1}\leftarrow
V_{a}^{p+1}\left(\sum_{i\in\pazocal{R}_{a}^{p}}f_{a,i}^{p}\hat{\theta}_{a,i}^{p}\right)$

9: end for

10: Broadcast
$\left\\{(\hat{\theta}_{a}^{p+1},V_{a}^{p+1})\right\\}_{a\in{\pazocal{A}}^{p}}$
to all agents

11: $p\leftarrow p+1$

12:end while

The Fed-PECD algorithm consists of two parts: an agent part and a central
server part. We present the pseudocode of the algorithm in Algorithm IV.1 and
Algorithm IV.2. The agents and the server work in phases. The agents
communicate with the central server at the end of each phase and update their
local models. We denote ${\pazocal{A}}_{i}^{p}$ as the active arm set for
agent $i$ in phase $p$ and
${\pazocal{A}}^{p}=\cup_{i=1}^{M}{\pazocal{A}}_{i}^{p}$ as the active arm set
for all the agents in phase $p$, where $M$ is the total number of agents. Let
$\pazocal{R}_{a}^{p}=\\{i:a\in{\pazocal{A}}_{i}^{p}\\}$ be the set of agents
with active arm $a$ in phase $p$, ${\pazocal{T}}_{a,i}^{p}$ be the number of
times we pulled action $a$ for agent $i$ in phase $p$. We denote the length of
phase $p$ as $f_{p}+K$, where $K$ is the number of actions. Now, we elaborate
on the process of our algorithm.

In the initialization phase, the agents explore by pulling the arms
$a\in{\pazocal{A}}$ and receive rewards $y_{a,i}$ for the chosen action. Each
agent then obtains a local estimate of the reward parameter
$\hat{\theta}^{0}_{a,i}$ and shares it with the central server. The central
server aggregates all the local estimates of the agents to obtain a global
estimate $\hat{\theta}_{a}$ and $V_{a}$. Then the central server broadcasts
$(\hat{\theta}_{a},V_{a})$ pairs to each agent, and the agents, upon receiving
this information, will update their local models before the next phase. This
completes the initialization phase and the agents proceed to the first phase
of the learning algorithm.

At each phase $p$, after receiving $(\hat{\theta}_{a},V_{a})$ pairs, each
agent first computes the estimated reward $\hat{r}_{a,i}^{p}$ and confidence
interval $u_{a,i}^{p}$ for each action $a$. By using the estimate pair
$(\hat{r}_{a,i}^{p},u_{a,i}^{p})$, the agent finds the optimal action and
updates the active action set as in Line 9 in Algorithm IV.1. In other words,
the actions that result in a low reward are eliminated. The agents communicate
the current active action set with the central server, which is then used to
obtain ${\pazocal{A}}^{p}$ and $\pazocal{R}_{a}^{p}$. The central server will
also compute $f_{a,i}^{p}$ and broadcast to each agent $i$ by solving the
multi-agent G-optimal design [6, Chapter 21] to find the distribution
$\pi_{a,i}$ for each action $a$ of each agent. After receiving $f_{a,i}^{p}$
from the central server, the agents choose the actions from the active action
set according to $f_{a,i}^{p}$ and find the average reward. Then each agent
updates $\hat{\theta}_{a,i}^{p}$, shares it with the central server, and
updates its potential global matrix with this new $\hat{\theta}_{a,i}^{p}$.
Note that the agents do not share $\psi_{a,\mu_{i}}$ or the chosen actions
with the central server, thus the local data is private and agents only share
their estimates with the central server, and thus our algorithm is federated.

We now present the regret and communication bounds for our algorithm. Recall
that $f_{p}+K$ denotes the length of the $p$-th phase, where $K$ denotes the
number of actions.

######  Theorem 1.

Consider time horizon $T$ that consists of $H$ phases with $f_{p}=cn^{p}$,
where $c$ and $n>1$ are fixed integers and $n^{p}$ denotes the $pth$-power of
$n$. Let

$\alpha=\min\\{\sqrt{2\log\frac{2MKH}{\delta}},\sqrt{2\log\frac{KH}{\delta}+d\log\left(ke\right)}\\}$

where $k>1$ is a number satisfying $kd\geqslant
2log\left(KH/\delta\right)+dlog\left(ke\right)$. Then, with probability (w.p)
at least $1-\delta$ the cumulative regret of our algorithm scales in

$O\left(\frac{L}{\ell}\sqrt{dKMT(\log(K(\log T)/\delta)+\min\\{d,\log
M\\})}\right)$

and communication cost scales in $O\left(Md^{2}K\log{T}\right)$.

Proof of Theorem 1 is presented in Subsection IV-B.

###  IV-B Regret Analysis

To bound our algorithm’s cumulative regret and communication cost, we extend
the approach in [23] to the case where the contexts are hidden and not
observable. We show that even when the contexts are unobservable, the proof
approach extends and our algorithm achieves the same order-wise bounds as in
[23]. We present the proof for the sake of completeness. We first present the
preliminary lemmas and then prove the main result.

We first define an event ${\pazocal{E}}\left(\alpha\right)$ as

${\pazocal{E}}\left(\alpha\right):=\\{\exists
p\in[H],i\in[M],a\in{\pazocal{A}}_{i}^{p-1},\left|\hat{r}_{a,i}^{p}-r_{a,i}\right|\geqslant
u_{a,i}^{p}=\alpha\sigma_{a,i}^{p}\\},$

where
$\displaystyle\alpha=\min\left\\{\sqrt{2\log\left(2MKH/\delta\right)},\sqrt{2\log\left(KH/\delta\right)+d\log\left(ke\right)}\right\\}$
, and
$\sigma_{a,i}^{p}:=\frac{\sqrt{10}}{\ell}\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}$.

We refer to ${\pazocal{E}}\left(\alpha\right)$ as a “bad" event and
${\pazocal{E}}^{c}\left(\alpha\right)$ as a "good" event. We define
$\pazocal{F}_{p}:=\left\\{\hat{\theta}_{a,i}^{p}\right\\}_{p\in[H],i\in[M],a\in{\pazocal{A}}_{i}^{p}}$,
the information available at the end of phase $p$.

We first show that the good event ${\pazocal{E}}^{c}\left(\alpha\right)$
occurs with high probability. Then, we show that if a good event occurs, the
best action is not eliminated from the action set during the arm elimination
procedure.

######  Lemma 2.

For our Fed-PECD algorithm,
${\mathbb{P}}[{\pazocal{E}}\left(\alpha\right)]\leq\delta$.

For proof of Lemma 2, we refer to the Appendix (Section -B).

######  Lemma 3.

If ${\pazocal{E}}^{c}\left(\alpha\right)$ occurs, we must have
$a_{i}^{\star}\in{\pazocal{A}}_{i}^{p}$, i.e., any optimal arm will never be
eliminated.

For proof of Lemma 3, we refer to the Appendix in [23]. We now present the
regret bound for the good events below.

######  Lemma 4.

If ${\pazocal{E}}^{c}\left(\alpha\right)$ occurs, the regret of Fed-PECD in
phase $p$ is upper bounded by $\frac{4\sqrt{10}\alpha
L}{\ell}\sqrt{dKM}\frac{f^{p}+K}{\sqrt{f^{p-1}}}$.

For proof of Lemma 4 we refer to Section -C in the Appendix. Using the above
lemmas, we now bound the regret below.

Proof of Theorem 1: Recall the superscript $p$ of $n$ is the exponent. Then,
with probability at least $1-\delta$ and $n>1$, the total regret over the $H$
phases can be bounded as

(3) (4) (5) (6) (7)

Eq. (3) follows from Lemma 4. Eq. (4) follows from $f_{p}=cn^{p}$. Eq. (5)
follows from $\sum_{n=0}^{N-1}r^{n}=\frac{1-r^{N}}{1-r}$. Eq. (6) follows from
$n^{\frac{H}{2}}-1\leqslant\sqrt{n^{H}-1}$. Eq. (7) follows from
$T=\sum_{p-1}^{H}f_{p}+KH\geqslant\sum_{p-1}^{H}cn^{p}=cn\frac{n^{H}-1}{n-1}$.

Since $\alpha=O\left(\sqrt{\log\left(K\left(\log
T\right)/\delta\right)+\min\\{d,\log M\\}}\right),$ the regret scales in

$O\left(\frac{L}{\ell}\sqrt{dKM(\log(K(\log T)/\delta)+\min\\{d,\log
M\\}}\left(\sqrt{T}+K\right)\right).$

When $K=O\left(\sqrt{T}\right)$, the cumulative regret scales as

$O\left(\frac{L}{\ell}\sqrt{dKMT(\log(K(\log T)/\delta)+\min\\{d,\log
M\\}}\right).$

We define communication cost as the number of scalars communicated between the
server and the agents. The communication cost bound follows from Theorem 1 in
[23] and is omitted here in the interest of space. ∎

##  V Numerical Experiments

(a) (b)

(c) (d)

Figure 1: Per-agent (average) cumulative regret $R(T)$ versus time $T$. We
compared the performance of our algorithm with the Fed-PE algorithm in [23]
(the variant in which the actual context is observable, i.e., exact). We
performed the experiments for both the synthetic data and the movielens data.
Synthetic data: Figure 1(a) for two different variants, exact and hidden and
Figure 1(b) for different number of agents, $M=50,100,150$. Movielens data:
Figure 1(c) presents the plot for two different variants, exact and hidden,
and Figure 1(d) presents the plot for different numbers of agents,
$M=50,100,150$. As expected, exact outperforms the hidden setting. The figures
also show that the per-agent regret decreases as the number of agents
increases, validating the benefit of collaborative learning.

We validated the performance of our algorithm using both synthetic and real-
world datasets. We considered two different settings, (i) exact in which the
actual feature vector $c_{i}$ is known to all the agents and (ii) hidden in
which the feature vector is unknown and the agents only observe a distribution
$\mu_{i}$. We compared the performance of our algorithm by varying the number
of agents to see the effect of agents on the learning process. All the
experiments were conducted using Python. We set $\delta=0.1$, $T=2^{17}$,
$f_{p}=2^{p}$, $p\in\\{1,2,\cdots,17\\}$. Thus, the length of phase $p$ is
$2^{p}+K$. To compare the performance for different number of agents, we set
$M=\\{50,100,150\\}$.

Synthetic data: In this dataset we set $K=10$ and $d=3$ and the feature
vectors $\phi_{a,c}$ were generated randomly. From $\phi_{a,c}$, we
constructed $\psi_{a,\mu}$ by adding an observation noise. The suboptimal
reward gap and $\|\phi_{a,c}\|_{2}$ of the data lie in $[0.2,0.4]$ and
$[0.5,1]$, respectively. We set $\theta_{a}=[1,0,0]$. We present the plots
showing variations of the cumulative regret with respect to time for different
settings and for different numbers of agents in Figure 1. Each point in the
plot was averaged over 100 independent trials. Our experimental results given
in Figure 1(a) show that the exact setting outperforms the hidden setting, as
expected, since the agents observe the actual contexts. We varied the number
of agents as $M=50,100,150$ and compared the per-agent cumulative regret as
shown in Figure 1(b). It demonstrates that as the number of agents increases,
the per-agent (average) cumulative regret decreases. This is expected since
when more agents work collaboratively, each agent receives more information at
the end of each phase, thus accelerating the learning process. We ran for
$2^{17}$ time-period.

Movielens data: We used Movielens-100K data [27] to evaluate the performance
of our algorithm. We first get the rating matrix $r\in\mathbb{R}^{943\times
1682}$ by using a non-negative matrix factorization $r=WH$, where
$W\in\mathbb{R}^{943\times 3}$, $H\in\mathbb{R}^{3\times 1682}$. We used the
k-mean clustering algorithm with $k=30$ on $H$ to cluster the action set into
$30$ clusters. Thus, the number of actions $K=30$ and $\theta_{a}$, for
$a\in{\pazocal{A}}$, is the center of the respective cluster. We set $M=100$
by randomly selecting 100 users from the dataset. For this experiment, we
noticed that the suboptimal reward gap for the data lies in $[0.01,0.8]$ and
$\|\phi_{a,c}\|_{2}^{2}$ lies in $[0.4,0.8]$. We present the plots showing the
variation of the cumulative regret with respect to time for the movielens data
for different settings and for different numbers of agents in Figure 1. The
reward $r(a,c_{i})$ is bounded above by $1$, and the observation noise
$\eta_{i}$ is set as Gaussian with zero mean and standard deviation $10^{-3}$.
In this experiment, as expected, the variant that does not observe the context
(hidden) is outperformed by the variant that uses the context observation
(exact) for the estimation, as shown in Figure 1(c). We varied the number of
agents as $M=50,100,150$ and ran for a time period of $2^{17}$ and the plots
are shown in Figure 1(d). The plots show that the per-agent regret decreases
as the number of agents increases, validating the benefit of collaborative
learning.

##  VI Conclusion

In this work, we studied a distributed and federated contextual MAB problem
with unknown contexts where $M$ agents face different bandit problems and the
agents’ goal is to minimize the total cumulative regret. We considered a
setting where the exact contexts are hidden and unobservable to the agents. In
our model, each agent shares the local estimates with the central server and
receives the aggregated global estimates from the server, and based on this
information, each agent updates their local model. We proposed an elimination-
based algorithm, Fed-PECD, and proved the regret and communication bounds for
the linearly parametrized reward function. We evaluated the performance of our
algorithm using synthetic and movielens data and compared it with a baseline
approach.

## References

  * [1] M. Y. Cheung, J. Leighton, and F. S. Hover, “Autonomous mobile acoustic relay positioning as a multi-armed bandit with switching costs,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2013, pp. 3368–3373.
  * [2] V. Srivastava, P. Reverdy, and N. E. Leonard, “Surveillance in an abruptly changing world via multiarmed bandits,” in _IEEE Conference on Decision and Control (CDC)_ , 2014, pp. 692–697.
  * [3] M. Aziz, E. Kaufmann, and M.-K. Riviere, “On multi-armed bandit designs for dose-finding clinical trials,” _The Journal of Machine Learning Research_ , vol. 22, no. 1, pp. 686–723, 2021.
  * [4] A. Anandkumar, N. Michael, A. K. Tang, and A. Swami, “Distributed algorithms for learning and cognitive medium access with logarithmic regret,” _IEEE Journal on Selected Areas in Communications_ , vol. 29, no. 4, pp. 731–745, 2011.
  * [5] L. Li, W. Chu, J. Langford, and R. E. Schapire, “A contextual-bandit approach to personalized news article recommendation,” in _Proceedings of the 19th international conference on World wide web_ , 2010, pp. 661–670.
  * [6] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [7] Y. Wang, J. Hu, X. Chen, and L. Wang, “Distributed bandit learning: Near-optimal regret with efficient communication,” _arXiv preprint arXiv:1904.06309_ , 2019.
  * [8] J. Lin and S. Moothedath, “Distributed stochastic bandits with hidden contexts,” _European Control Conference_ , 2022.
  * [9] J. Lin and S. Moothedath, “Distributed stochastic bandit learning with delayed context observatio,” _European Control Conference_ , 2022.
  * [10] P. Landgren, V. Srivastava, and N. E. Leonard, “Distributed cooperative decision making in multi-agent multi-armed bandits,” _Automatica_ , vol. 125, p. 109445, 2021.
  * [11] D. Martínez-Rubio, V. Kanade, and P. Rebeschini, “Decentralized cooperative stochastic bandits,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [12] E. Hillel, Z. S. Karnin, T. Koren, R. Lempel, and O. Somekh, “Distributed exploration in multi-armed bandits,” _Advances in Neural Information Processing Systems_ , vol. 26, 2013.
  * [13] N. Korda, B. Szorenyi, and S. Li, “Distributed clustering of linear bandits in peer to peer networks,” in _International Conference on Machine Learning_ , 2016, pp. 1301–1309.
  * [14] C. Tao, Q. Zhang, and Y. Zhou, “Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits,” in _Annual Symposium on Foundations of Computer Science (FOCS)_ , 2019, pp. 126–146.
  * [15] J. Zhu, E. Mulle, C. S. Smith, and J. Liu, “Decentralized multi-armed bandit can outperform classic upper confidence bound,” _arXiv preprint arXiv:2111.10933_ , 2021.
  * [16] A. Sankararaman, A. Ganesh, and S. Shakkottai, “Social learning in multi agent multi armed bandits,” _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , vol. 3, no. 3, pp. 1–35, 2019.
  * [17] X. Wang, H. Xie, and J. Lui, “Multi-player multi-armed bandits with finite shareable resources arms: Learning algorithms & applications,” _arXiv preprint arXiv:2204.13502_ , 2022.
  * [18] Z. Zhu, J. Zhu, J. Liu, and Y. Liu, “Federated bandit: A gossiping approach,” in _Abstract Proceedings of the 2021 ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems_ , 2021, pp. 3–4.
  * [19] C. Shi and C. Shen, “Federated multi-armed bandits,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 11, 2021, pp. 9603–9611.
  * [20] C. Shi, C. Shen, and J. Yang, “Federated multi-armed bandits with personalization,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 2917–2925.
  * [21] A. Agarwal, J. Langford, and C.-Y. Wei, “Federated residual learning,” _arXiv preprint arXiv:2003.12880_ , 2020.
  * [22] J. Kirschner and A. Krause, “Stochastic bandits with context distributions,” _Advances in Neural Information Processing Systems_ , vol. 32, pp. 14 113–14 122, 2019.
  * [23] R. Huang, W. Wu, J. Yang, and C. Shen, “Federated linear contextual bandits,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [24] J. Lin and S. Moothedath, “Feature selection in distributed stochastic linear bandits,” _American Control Conference (ACC)_ , 2022.
  * [25] T. Li, L. Song, and C. Fragouli, “Federated recommendation system via differential privacy,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 2592–2597.
  * [26] A. Dubey and A. Pentland, “Differentially-private federated linear bandits,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 6003–6014, 2020.
  * [27] F. M. Harper and J. A. Konstan, “The movielens datasets: History and context,” _ACM Transactions on Interactive Intelligent Systems (TIIS)_ , vol. 5, no. 4, pp. 1–19, 2015.

###  -A Preliminaries

To prove Theorem 1, we first present the following supporting lemmas.

######  Lemma .5.

Let $\zeta\in\mathbb{R}^{n}$ be an 1-sub-Gaussian random vector conditioned on
$\pazocal{F}_{p-1}$ and $A\in\mathbb{R}^{n\times n}$ be an
$\pazocal{F}_{p-1}$-measurable matrix. Let $\lambda>0$ and
$det\left(I_{n}-2\lambda AA^{\top}\right)>0$. Then, we have

$\mathbb{E}\left[e^{\lambda\|A\zeta\|^{2}}\mid\pazocal{F}_{p-1}\right]\leq\sqrt{\frac{1}{det\left(I_{n}-2\lambda
AA^{\top}\right)}}.$

###### Proof.

For proof of this lemma, see Lemma 4 in [23] (supplementary material). ∎

Next, we show that $\hat{r}_{a,i}^{p}-r_{a,i}$ is a conditionally sub-Gaussian
random variable for all phase $p\in[H]$, any agent $i\in[M]$, and arm
$a\in{\pazocal{A}}_{i}^{p-1}$.

######  Lemma .6.

At phase $p\in[H]$, for any agent $i\in[M]$, and arm
$a\in{\pazocal{A}}_{i}^{p-1},\hat{r}_{a,i}^{p}-r_{a,i}$ is a conditionally
sub-Gaussian random variable, i.e.,
$\mathbb{E}\left[\exp\left(\lambda\left(\hat{r}_{a,i}^{p}-r_{a,i}\right)\right)\mid\pazocal{F}_{p-1}\right]\leqslant\exp\left(\frac{\lambda^{2}\left(\sigma_{a,i}^{p}\right)^{2}}{2}\right)$,
for any $\lambda\in\mathbb{R}$, where
$\sigma_{a,i}^{p}:=\frac{\sqrt{10}}{\ell}\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}$.

###### Proof.

Let $\xi_{a,i}^{p-1}$ be the sum of the independent sub-Gaussian noise
incurred during the collaborative exploration step in phase $p-1$, i.e.,
$\xi_{a,i}^{p-1}:=\sum_{t\in{\pazocal{T}}_{a,i}^{p-1}}\eta_{i,t}$. We know
$f_{a,i}^{p-1}$ and $\xi_{a,i}^{p-1}$ are conditionally
$\sqrt{f_{a,i}^{p-1}}$-sub-Gaussian random variables. Recall the definition of
local estimators,

$\displaystyle\hat{\theta}_{a,i}^{p-1}$
$\displaystyle=\left(\frac{1}{f_{a,i}^{p-1}}\sum_{t\in{\pazocal{T}}_{a,i}^{p-1}}y_{i,t}\right)\frac{\psi_{a,\mu_{i}}}{\left\|\psi_{a,\mu_{i}}\right\|^{2}}$
$\displaystyle=\left(\phi_{a,c_{i}}^{\top}\theta_{a}+\frac{\xi_{a,i}^{p-1}}{f_{a,i}^{p-1}}\right)\frac{\psi_{a,\mu_{i}}}{\left\|\psi_{a,\mu_{i}}\right\|^{2}}$
$\displaystyle=\left(\psi_{a,\mu_{i}}^{\top}\theta_{a}+\frac{\xi_{a,i}^{p-1}}{f_{a,i}^{p-1}}+\phi_{a,c_{i}}^{\top}\theta_{a}-\psi_{a,\mu_{i}}^{\top}\theta_{a}\right)\frac{\psi_{a,\mu_{i}}}{\left\|\psi_{a,\mu_{i}}\right\|^{2}}$
$\displaystyle=\frac{\psi_{a,\mu_{i}}\psi_{a,\mu_{i}}^{\top}}{\left\|\psi_{a,\mu_{i}}\right\|^{2}}\theta_{a}+\frac{\psi_{a,\mu_{i}}\xi_{a,i}^{p-1}}{f_{a,i}^{p-1}\left\|\psi_{a,\mu_{i}}\right\|^{2}}+\frac{\psi_{a,\mu_{i}}(\phi_{a,c_{i}}^{\top}-\psi_{a,\mu_{i}}^{\top})}{\left\|\psi_{a,\mu_{i}}\right\|^{2}}\theta_{a}.$
(8)

We know $\hat{r}_{a,i}^{p}=\psi_{a,\mu_{i}}^{\top}\hat{\theta}_{a}^{p}$ and
$V_{a}^{p}=\left(\sum_{j\in\pazocal{R}_{a}^{p-1}}f_{a,j}^{p-1}\frac{\psi_{a,\mu_{j}}\psi_{a,\mu_{j}}^{\top}}{\left\|\psi_{a,\mu_{j}}\right\|^{2}}\right)^{\dagger}$.
Thus

$\displaystyle\hat{r}_{a,i}^{p}-r_{a,i}=\psi_{a,\mu_{i}}^{\top}\hat{\theta}_{a}^{p}-\phi_{a,c_{i}}^{\top}\theta_{a}$
$\displaystyle=\psi_{a,\mu_{i}}^{\top}V_{a}^{p}(\sum_{j\in\pazocal{R}_{a}^{p-1}}f_{a,j}^{p-1}\hat{\theta}_{a,j}^{p-1})-\phi_{a,c_{i}}^{\top}\theta_{a}$
(9) (10) (11)

Eq. (9) follows from Eq. (8). Eq. (10) follows from
$\left(\phi_{a,c_{j}}^{\top}-\psi_{a,\mu_{j}}^{\top}\right)\theta_{a}\leqslant
2$, $e_{a,j}=\frac{\psi_{a,j}}{\left\|\psi_{a,j}\right\|}$, and
$V_{a}^{p}=\left(\sum_{j\in\pazocal{R}_{a}^{p-1}}f_{a,j}^{p-1}\frac{\psi_{a,\mu_{j}}\psi_{a,\mu_{j}}^{\top}}{\left\|\psi_{a,\mu_{j}}\right\|^{2}}\right)^{\dagger}$.
Finally, Eq. (11) follows from
$\left(\phi_{a,c_{i}}^{\top}-\psi_{a,\mu_{i}}^{\top}\right)\theta_{a}\leqslant
2$.

Given $f_{a,i}^{p-1},\xi_{a,i}^{p-1}$ are conditionally
$\sqrt{f_{a,i}^{p-1}}$-sub-Gaussian random variables. Thus
$\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)$ is a conditionally
$\sqrt{\left(1^{2}+2^{2}\right)f_{a,j}^{p-1}}=\sqrt{5f_{a,j}^{p-1}}$ sub-
Gaussian random variable. Also Eq. (10) is a linear combination of
$\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)$ and
$\left(\psi_{a,\mu_{i}}^{\top}-\phi_{a,c_{i}}^{\top}\right)\theta_{a}$. Thus,
given $\pazocal{F}_{p-1}$, $\hat{r}_{a,i}^{p}-r_{a,i}$ is a conditionally sub-
Gaussian random variable, whose parameter can be bounded as

(12) (13)

Eq. (12) follows from $\left(a+b\right)^{2}\leqslant 2a^{2}+2b^{2}$ and uses
the fact that
$\psi_{a,\mu_{i}}=\mathbb{E}_{c_{i}\sim\mu_{i}}\left[\phi_{a,c_{i}}\mid\pazocal{F}_{p-1},\mu_{i},c_{i}\right]$.
Eq. (13) follows from $\left\|\psi_{a,\mu_{j}}\right\|\geqslant\ell$,
$A\left(A\right)^{\dagger}A=A$ for all $i$, $a$. ∎

######  Lemma .7.

From the definition of
$\sigma_{a,i}^{p}:=\frac{\sqrt{10}}{\ell}\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}$,
where $V_{a}^{p}$ is a symmetric matrix, for all $a\in[K],i\in[M],$ and
$p\in[H]$, we have $\frac{\ell\sigma_{a,i}^{p}}{\sqrt{10L}}\geqslant 1$.

###### Proof.

We have

$\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}^{2}-\psi_{a,\mu_{i}}^{\top}\psi_{a,\mu_{i}}=\psi_{a,\mu_{i}}^{\top}\left(V_{a}^{p}-I\right)\psi_{a,\mu_{i}}.$

Since $V_{a}^{p}$ is a symmetric matrix, $V_{a}^{p}-I$ is also a symmetric
matrix. By using the eigendecomposition of the symmetric matrix $V_{a}^{p}-I$,
we know there exists an orthogonal matrix $U$ such that
$\Lambda=diag\left(\lambda_{1},\lambda_{2},\cdots,\lambda_{n}\right)=U\left(V_{a}^{p}-I\right)U^{\top}$,
where $\lambda_{i}>0$ is the $i$-th eigenvalue of $V_{a}^{p}-I$. Therefore we
get

$\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}^{2}-\psi_{a,\mu_{i}}^{\top}\psi_{a,\mu_{i}}=\psi_{a,\mu_{i}}^{\top}U^{\top}\Lambda
U\psi_{a,\mu_{i}}=\left\|\Lambda^{\frac{1}{2}}U\psi_{a,\mu_{i}}\right\|_{2}^{2}\geqslant
0$

and

$\displaystyle\frac{1}{L}\left(\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}^{2}-\psi_{a,\mu_{i}}^{\top}\psi_{a,\mu_{i}}\right)$
$\displaystyle=\frac{\ell^{2}\left(\sigma_{a,i}^{p}\right)^{2}}{10L}-\frac{\psi_{a,\mu_{i}}^{\top}\psi_{a,\mu_{i}}}{L}$
$\displaystyle\geqslant\frac{\ell^{2}\left(\sigma_{a,i}^{p}\right)^{2}}{10L}-1\geqslant
0.$

Thus $\frac{\ell\sigma_{a,i}^{p}}{\sqrt{10L}}\geqslant 1$ and this completes
the proof. ∎

Recall the event ${\pazocal{E}}\left(\alpha\right)$

${\pazocal{E}}\left(\alpha\right):=\\{\exists
p\in[H],i\in[M],a\in{\pazocal{A}}_{i}^{p-1},\left|\hat{r}_{a,i}^{p}-r_{a,i}\right|\geqslant
u_{a,i}^{p}=\alpha\sigma_{a,i}^{p}\\},$

where
$\displaystyle\alpha=\min\left\\{\sqrt{2\log\left(2MKH/\delta\right)},\sqrt{2\log\left(KH/\delta\right)+d\log\left(ke\right)}\right\\}$
, and
$\sigma_{a,i}^{p}:=\frac{\sqrt{10}}{\ell}\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}$.
We refer to ${\pazocal{E}}\left(\alpha\right)$ as a “bad" event and
${\pazocal{E}}^{c}\left(\alpha\right)$ as a "good" event. We define
$\pazocal{F}_{p}:=\left\\{\hat{\theta}_{a,i}^{p}\right\\}_{p\in[H],i\in[M],a\in{\pazocal{A}}_{i}^{p}}$,
the information available at the end of phase $p$.

In Lemma 2, we show that the probability of bad events is only less than
$\delta$.

###  -B Proof of Lemma 2

Let $\alpha=\min\left\\{\alpha_{1},\alpha_{2}\right\\}$, where

$\displaystyle\alpha_{1}=\sqrt{2\log\left(2MKH/\delta\right)}$
$\displaystyle\alpha_{2}=\sqrt{2\log\left(KH/\delta\right)+d\log\left(ke\right)}$

From Theorem 1, we know $k>1$ and
$k\geqslant\left\\{\frac{\alpha_{2}^{2}}{d}\right\\}$. This choice of $k$
requires $\alpha_{2}^{2}\geqslant d$. Based on the definition of
${\pazocal{E}}\left(\alpha\right)$, we have

${\pazocal{E}}\left(\alpha\right)={\pazocal{E}}\left(\min\left\\{\alpha_{1},\alpha_{2}\right\\}\right)\supset{\pazocal{E}}\left(\max\left\\{\alpha_{1},\alpha_{2}\right\\}\right),$

which implies that
${\mathbb{P}}[{\pazocal{E}}\left(\alpha\right)]=\max\left({\mathbb{P}}[{\pazocal{E}}\left(\alpha_{1}\right)],{\mathbb{P}}[{\pazocal{E}}\left(\alpha_{2}\right)]\right)$.
Therefore, we need to prove that
${\mathbb{P}}[{\pazocal{E}}\left(\alpha_{i}\right)]\leqslant\delta$, for all
$i\in\left\\{1,2\right\\}$. In the following, we bound
${\mathbb{P}}[{\pazocal{E}}\left(\alpha_{1}\right)]$ and
${\mathbb{P}}[{\pazocal{E}}\left(\alpha_{2}\right)]$ separately.

(i) Bound ${\mathbb{P}}[{\pazocal{E}}\left(\alpha_{1}\right)]$. Based on Lemma
.6 and Hoeffding’s inequality, we have

$\displaystyle{\mathbb{P}}[|\hat{r}_{a,i}^{p}-r_{a,i}|\geqslant\alpha_{1}\sigma_{a,i}^{p}\mid\pazocal{F}_{p}]$
$\displaystyle\leqslant
2\exp\left(-\frac{\alpha_{1}^{2}\left(\sigma_{a,i}^{p}\right)^{2}}{2\left(\sigma_{a,i}^{p}\right)^{2}}\right)$
$\displaystyle=2\exp\left(-\frac{\alpha_{1}^{2}}{2}\right)=\frac{\delta}{MKH}.$

Then, by using the union bound, we get

$\displaystyle{\mathbb{P}}[{\pazocal{E}}\left(\alpha_{1}\right)]$
$\displaystyle={\mathbb{P}}[\exists
p\in[H],i\in[M],a\in{\pazocal{A}}_{i}^{p-1},|\hat{r}_{a,i}^{p}-r_{a,i}|\geqslant\alpha_{1}\sigma_{a,i}^{p}]$
$\displaystyle\leqslant\sum_{p\in[H]}\sum_{i\in[M]}\sum_{a\in{\pazocal{A}}_{i}^{p-1}}{\mathbb{P}}[|\hat{r}_{a,i}^{p}-r_{a,i}|\geqslant\alpha_{1}\sigma_{a,i}^{p}\mid\pazocal{F}_{p-1}]$
$\displaystyle\leqslant HMK\frac{\delta}{MKH}=\delta.$

(ii) Bound ${\mathbb{P}}[{\pazocal{E}}\left(\alpha_{2}\right)]$.

$\displaystyle|\hat{r}_{a,i}^{p}-r_{a,i}|\leqslant\left|\psi_{a,\mu_{i}}^{\top}V_{a}^{p}\left(\sum_{j\in\pazocal{R}_{a}^{p-1}}\frac{e_{a,j}}{\left\|\psi_{a,\mu_{j}}\right\|}\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)\right)\right|+2$
$\displaystyle\leqslant\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}\cdot\left\|\sum_{j\in\pazocal{R}_{a}^{p-1}}\frac{e_{a,j}}{\left\|\psi_{a,\mu_{j}}\right\|}\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)\right\|_{V_{a}^{p}}+2$
(14)
$\displaystyle\leqslant\frac{\sigma_{a,i}^{p}}{\sqrt{10}}\left\|\sum_{j\in\pazocal{R}_{a}^{p-1}}\frac{e_{a,j}}{\left\|\psi_{a,\mu_{j}}\right\|}\ell\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)\right\|_{V_{a}^{p}}+\frac{2\ell\sigma_{a,i}^{p}}{\sqrt{10L}}$
(15)

Eq. (14) follows from Cauchy-Schwarz inequality. Eq. (15) follows from Lemma
.7. Therefore, when ${\pazocal{E}}\left(\alpha_{2}\right)$ happens, by the
definition of the event ${\pazocal{E}}\left(\alpha\right)$, we have

$\frac{1}{\sqrt{10}}\left\|\sum_{j\in\pazocal{R}_{a}^{p-1}}\frac{e_{a,j}}{\left\|\psi_{a,\mu_{j}}\right\|}\ell\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)\right\|_{V_{a}^{p}}+\frac{2\ell}{\sqrt{10L}}\geqslant\alpha_{2}$

hold for some phase $p$ and arm $a$.

Let us define the term

$\Xi_{a,p}:=\frac{1}{10}\left\|\sum_{j\in\pazocal{R}_{a}^{p-1}}\frac{e_{a,j}}{\left\|\psi_{a,\mu_{j}}\right\|}\ell\left(\xi_{a,j}^{p-1}+2f_{a,j}^{p-1}\right)\right\|_{V_{a}^{p}}^{2}$

for a given phase $p$ and arm $a$. Note that

In the following proof, we use matrix form for $\Xi_{a,p}$. Since
$f_{a,i}^{p-1}$ may equal 0 under the Block-Coordinate Ascent (BCA) algorithm
[23] (Algorithm 3 in supplementary), and when this occurs, agent $i$ does not
choose arm $a$ during the collaborative exploration step in phase $p$, even
though $a$ is in the active arm set. In this case, $\xi_{a,i}^{p-1}=0$.
Therefore, we define $\zeta_{a,i}$ as follows.

$\zeta_{a,i}=\left\\{\begin{array}[]{cl}\frac{\ell\left(\xi_{a,i}^{p-1}+2f_{a,i}^{p-1}\right)}{\sqrt{5}\sqrt{f_{a,i}^{p-1}}\left\|\psi_{a,\mu_{i}}\right\|},&\text{if
}f_{a,i}^{p-1}\neq 0,\\\ 0,&\text{if }f_{a,i}^{p-1}=0.\end{array}\right.$

Then, we know $\\{\zeta_{a,i}\\}_{i\in\pazocal{R}_{a}^{p-1}}$ are
conditionally independent 1-sub-Gaussian random variables. we define vector
$\zeta:=\\{\zeta_{a,i}\\}_{i\in\pazocal{R}_{a}^{p-1}}$ and matrix
$A:=\left(a_{i,j}\right)_{i,j\in\pazocal{R}_{a}^{p-1}}$ where

$a_{i,j}=\sqrt{f_{a,i}^{p-1}}e_{a,i}^{\top}\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)^{\dagger}e_{a,j}\sqrt{f_{a,j}^{p-1}}.$

Here $A$ is a symmetric matrix and

$\displaystyle\sum_{k\in\pazocal{R}_{a}^{p-1}}a_{i,k}a_{k,j}=\sum_{k\in\pazocal{R}_{a}^{p-1}}\Biggl{(}\sqrt{f_{a,i}^{p-1}}e_{a,i}^{\top}\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)^{\dagger}$
$\displaystyle\cdot
e_{a,k}\sqrt{f_{a,k}^{p-1}}\sqrt{f_{a,k}^{p-1}}e_{a,k}^{\top}\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)^{\dagger}e_{a,j}\sqrt{f_{a,j}^{p-1}}\Biggr{)}$
$\displaystyle=\sqrt{f_{a,i}^{p-1}}e_{a,i}^{\top}\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)^{\dagger}\cdot\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)$
$\displaystyle\hskip
85.35826pt\cdot\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)^{\dagger}e_{a,j}\sqrt{f_{a,j}^{p-1}}$
$\displaystyle=\sqrt{f_{a,i}^{p-1}}e_{a,i}^{\top}V_{a}^{p}\left(V_{a}^{p}\right)^{\dagger}V_{a}^{p}e_{a,j}\sqrt{f_{a,j}^{p-1}}$
$\displaystyle=\sqrt{f_{a,i}^{p-1}}e_{a,i}^{\top}V_{a}^{p}e_{a,j}\sqrt{f_{a,j}^{p-1}}=a_{i,j}.$

Therefore, we know $A^{2}=A$, which implies that all the eigenvalues of $A$
are either $1$ or $0$. Also, we can get

$\displaystyle\mathrm{trace}\left(A\right)=\sum_{i\in\pazocal{R}_{a}^{p-1}}a_{i,i}$
$\displaystyle=\sum_{i\in\pazocal{R}_{a}^{p-1}}\sqrt{f_{a,i}^{p-1}}e_{a,i}^{\top}\left(\sum_{k\in\pazocal{R}_{a}^{p-1}}f_{a,k}^{p-1}e_{a,k}e_{a,k}^{\top}\right)^{\dagger}e_{a,i}\sqrt{f_{a,i}^{p-1}}$
$\displaystyle=V_{a}^{p}\left(\sum_{i\in\pazocal{R}_{a}^{p-1}}f_{a,i}^{p-1}e_{a,i}e_{a,i}^{\top}\right)^{\dagger}=V_{a}^{p}\left(V_{a}^{p}\right)^{\dagger}=\mathrm{rank}\left(V_{a}^{p}\right)=d_{a}^{p}.$

We know that all eigenvalues are either $1$ or $0$. Since the
$\mathrm{rank}\left(A\right)=d_{a}^{p}$, there are exactly $d_{a}^{p}$
eigenvalues that are equal to $1$, and the rest of the eigenvalues are all
$0$. Thus, $\mathrm{rank}\left(A\right)=d_{a}^{p}\leqslant d$.

From the definition of $\zeta$ and since $A^{2}=A$, we have
$\Xi_{a,p}=\frac{1}{2}\zeta^{\top}A\zeta=\frac{1}{2}\|A\zeta\|^{2}$, where
$\zeta$ is a conditionally 1 -sub-Gaussian random vector. Here, $A$ is an
$\pazocal{F}_{p}$-measurable matrix. Therefore, for any
$\lambda\in\left(0,1/2\right)$, we have

(16)
$\displaystyle={\mathbb{P}}[\|A\zeta\|^{2}+\frac{4\ell^{2}}{5L}\geqslant\alpha_{2}^{2}\mid\pazocal{F}_{p-1}]$
$\displaystyle={\mathbb{P}}[e^{\lambda\|A\zeta\|^{2}+\frac{4\ell^{2}\lambda}{5L}}\geqslant
e^{\lambda\alpha_{2}^{2}}\mid\pazocal{F}_{p-1}]$ $\displaystyle\leqslant
e^{-\lambda\alpha_{2}^{2}}\mathbb{E}[e^{\lambda\|A\zeta\|^{2}+\frac{4\ell^{2}\lambda}{5L}}\mid\pazocal{F}_{p-1}]$
(17) $\displaystyle\leqslant
e^{-\lambda\alpha_{2}^{2}+\frac{4\ell^{2}\lambda}{5L}}\sqrt{\frac{1}{det\left(I_{d}-2\lambda
A^{2}\right)}}$ (18)
$\displaystyle=e^{-\lambda\alpha_{2}^{2}+\frac{4\ell^{2}\lambda}{5L}}\left(1-2\lambda\right)^{-d_{a}^{p}/2}$
(19) $\displaystyle\leqslant
e^{-\lambda\alpha_{2}^{2}+\frac{4\ell^{2}\lambda}{5L}}\left(1-2\lambda\right)^{-d/2}$

Eq. (17) follows from Markov’s inequality, Eq. (18) follows from Lemma .5, Eq.
(19) follows from the fact that the eigenvalues of $A$ are either 1 or 0 and
there are exactly $d_{a}^{p}$ number of $1$’s.

By choosing
$\lambda=\frac{\alpha_{2}^{2}-d}{2\alpha_{2}^{2}}\in\left(0,\frac{1}{2}\right)$,
we have

$\displaystyle{\mathbb{P}}[\left(\sqrt{\Xi_{a,p}}+\frac{2\ell}{\sqrt{10L}}\right)^{2}\geqslant\alpha_{2}^{2}\mid\pazocal{F}_{p-1}]\leqslant\left(\frac{\alpha_{2}^{2}}{d}\right)^{d/2}e^{-\frac{\alpha_{2}^{2}-d}{2}+\frac{4\ell^{2}\lambda}{5L}}\leqslant\frac{\delta}{KH}$

The last inequality follows by the following analysis:

$\displaystyle\left(\frac{\alpha_{2}^{2}}{d}\right)^{d/2}e^{-\frac{\alpha_{2}^{2}-d}{2}+\frac{4\ell^{2}\lambda}{5L}}\leqslant\frac{\delta}{KH}$
$\displaystyle\scalebox{0.9}{\mbox{$\displaystyle\Leftrightarrow\frac{d}{2}\left(2\log\alpha_{2}-\log
d\right)+\frac{d}{2}+\frac{4\ell^{2}\lambda}{5L}-\frac{1}{2}\left(\sqrt{2\log\left(KH/\delta\right)+d\log\left(ke\right)}\right)^{2}$}}$
$\displaystyle\hskip 113.81102pt\leqslant\log\left(\frac{\delta}{KH}\right)$
$\displaystyle\Leftrightarrow
d\log\alpha_{2}\leqslant\frac{d\log\left(dk\right)}{2}-\frac{4\ell^{2}\lambda}{5L}$
$\displaystyle\Leftrightarrow\alpha_{2}^{2}\leqslant
dke^{-\frac{8\ell^{2}\lambda}{5dL}}$
$\displaystyle\Leftrightarrow\alpha_{2}^{2}\leqslant dk.$

The last step is assured by the definition of $k$. We finish the proof by
using the union bound over phase $p$ and arm $a$ that
${\mathbb{P}}[{\pazocal{E}}\left(\alpha_{2}\right)]\leqslant
HK\frac{\delta}{HK}=\delta$. ∎

Lemma 4 presents a bound on the regret for the good events. The proofs of both
these results follows a similar approach as in [23] (Lemmas 13 and 14 in
supplementary material) and uses the earlier lemmas of this paper (Lemmas
.5-2).

###  -C Proof of Lemma 4

The proof follows similar steps as in [23]. The per-phase regret bound is
different, in terms of a factor, from that in [23] as shown in the earlier
lemmas of this paper. We present the proof below for completeness

When ${\pazocal{E}}^{c}\left(\alpha\right)$ occurs, the following is true for
all $p\in[H],i\in[M],$ and $a\in{\pazocal{A}}_{i}^{p-1}$.

$\left|\hat{r}_{a,i}-r_{a,i}\right|\leqslant
u_{a,i}^{p}=\alpha\sigma_{a,i}^{p}=\alpha\frac{\sqrt{10}}{\ell}\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}.$

Recall the definition of the active action set ${\pazocal{A}}_{i}^{p}$ (line 9
of Algorithm IV.1). Thus if any active action $a\in{\pazocal{A}}_{i}^{p}$ is
selected in phase $p$, then we will incur a regret that is upper bounded by

$\displaystyle\Delta_{a,i}$ $\displaystyle=r_{a_{i}^{\star},i}-r_{a,i}$
$\displaystyle=r_{a_{i}^{\star},i}-\hat{r}_{a_{i}^{\star},i}-r_{a,i}+\hat{r}_{a,i}+\hat{r}_{a_{i}^{\star},i}-\hat{r}_{a,i}$
$\displaystyle\leqslant
u_{a_{i}^{\star},i}^{p}+u_{a,i}^{p}+\hat{r}_{\hat{a_{i}},i}-\hat{r}_{a,i}$
(20) $\displaystyle\leqslant
u_{a_{i}^{\star},i}^{p}+u_{a,i}^{p}+u_{a,i}^{p}+u_{\hat{a}_{i},i}^{p}$ (21)
$\displaystyle=u_{\hat{a}_{i},i}^{p}+u_{a_{i}^{\star},i}^{p}+2u_{a,i}^{p}$
$\displaystyle\leqslant 4\max_{a\in{\pazocal{A}}_{i}^{p}}u_{a,i}^{p}.$ (22)

Eq. (20) follows from
$\hat{r}_{a_{i}^{\star},i}\leqslant\hat{r}_{\hat{a}_{i},i}$. Eq. (21) follows
from
$\hat{r}_{a,i}^{p}+u_{a,i}^{p}\geqslant\hat{r}_{\hat{a_{i}},i}^{p}-u_{\hat{a}_{i},i}^{p}$.
Eq. (22) follows from Lemma 3 that any optimal arm will never be eliminated

We know that the length of the phase in the Fed-PECD algorithm is fixed as
$f^{p}+K$ for $p\in[H]$. Then, given that the good event
${\pazocal{E}}^{c}\left(\alpha\right)$ happens, the total regret incurred
during phase $p$, denoted as $R_{p}$, can be bounded as follows.

$\displaystyle R_{p}$
$\displaystyle\leqslant\sum_{i\in[M]}4\max_{a\in{\pazocal{A}}_{i}^{p}}u_{a,i}^{p}\left(f^{p}+K\right)$
$\displaystyle=4\left(f^{p}+K\right)\sqrt{\left(\sum_{i\in[M]}1\cdot\max_{a\in{\pazocal{A}}_{i}^{p}}u_{a,i}^{p}\right)^{2}}$
$\displaystyle\leqslant
4\left(f^{p}+K\right)\sqrt{\left(\sum_{i\in[M]}1^{2}\right)\left(\sum_{i\in[M]}\max_{a\in{\pazocal{A}}_{i}^{p}}\left(u_{a,i}^{p}\right)^{2}\right)}$
(23)
$\displaystyle=4\left(f^{p}+K\right)\sqrt{M\sum_{i\in[M]}\max_{a\in{\pazocal{A}}_{i}^{p}}\left(u_{a,i}^{p}\right)^{2}}$
$\displaystyle\leqslant\frac{4\sqrt{10}\alpha
L}{\ell}\left(f^{p}+K\right)\sqrt{M\sum_{i\in[M]}\max_{a\in{\pazocal{A}}_{i}^{p}}\frac{\psi_{a,\mu_{i}}^{\top}}{\left\|\psi_{a,\mu_{i}}\right\|_{2}}V_{a}^{p}\frac{\psi_{a,\mu_{i}}}{\left\|\psi_{a,\mu_{i}}\right\|_{2}}}$
(24) $\displaystyle\leqslant\frac{4\sqrt{10}\alpha
L}{\ell}\left(f^{p}+K\right)\sqrt{M\sum_{i\in[M]}\max_{a\in{\pazocal{A}}_{i}^{p}}e_{a,i}^{\top}\left(\sum_{j\in\pazocal{R}_{a}^{p}}\left\lceil\pi_{a,j}f^{p-1}\right\rceil
e_{a,j}e_{a,j}^{\top}\right)^{\dagger}e_{a,i}}$ (25)
$\displaystyle\leqslant\frac{4\sqrt{10}\alpha
L}{\ell}\left(f^{p}+K\right)\sqrt{\frac{M}{f^{p-1}}\sum_{i\in[M]}\max_{a\in{\pazocal{A}}_{i}^{p}}e_{a,i}^{\top}\left(\sum_{j\in\pazocal{R}_{a}^{p}}\pi_{a,j}e_{a,j}e_{a,j}^{\top}\right)^{\dagger}e_{a,i}}$
(26) $\displaystyle\leqslant\frac{4\sqrt{10}\alpha
L}{\ell}\left(f^{p}+K\right)\sqrt{\frac{dKM}{f^{p-1}}}$ (27)
$\displaystyle=\frac{4\sqrt{10}\alpha
L}{\ell}\sqrt{dKM}\frac{f^{p}+K}{\sqrt{f^{p-1}}}$

Eq. (23) follows from Cauchy-Schwarz inequality that
$\left(\sum_{i=1}^{n}u_{i}v_{i}\right)^{2}\leqslant\left(\sum_{i=1}^{n}u_{i}^{2}\right)\left(\sum_{i=1}^{n}v_{i}^{2}\right)$.
Eq. (24) follows from
$u_{a,i}^{p}:=\frac{\sqrt{10}\alpha}{\ell}\left\|\psi_{a,\mu_{i}}\right\|_{V_{a}^{p}}$,
$\ell\leqslant\left\|\psi_{a,\mu_{i}}\right\|^{2}\leqslant L$. Eq. (25)
follows from $f_{a,i}^{p}:=\left\lceil\pi_{a,i}f^{p-1}\right\rceil$. Eq. (26)
follows from $\left\lceil\ x\right\rceil\geqslant x$. Eq. (27) follows from
the fact that summation is the solution to the multi-agent G-optimal design,
which equals $\sum_{a}d_{a}^{p}\leqslant dK$.

We note that the upper bound also holds for $p=1$ when $f^{0}=1$. This is
because in the initialization step the matrix $V_{a}^{0}$ is defined as
$V_{a}^{0}:=\left(\sum_{j\in[M]}e_{a,j}e_{a,j}^{\top}\right)^{\dagger}\preceq\left(\sum_{j\in\pazocal{R}_{a}^{p}}\left\lceil\pi_{a,j}f^{0}\right]e_{a,j}e_{a,j}^{\top}\right)^{\dagger}$
for any $\pi$. This is true although the central server does not utilize the
G-optimal design to obtain $\pi^{0}$ during initialization. Thus, Eq. (25)
still holds and this completes the proof. ∎