# Axial Magnetic Quadrupole Mode of Dielectric Resonator for Omnidirectional
Wireless Power Transfer

Esmaeel Zanganeh, Elizaveta Nenasheva, Polina Kapitanova This work was
supported by the Russian Science Foundation (Project No. 20-72-10090). PK
acknowledges the Priority 2030 Federal Academic Leadership Program. EZ
acknowledges Dr. Alena Shchelokova for sharing the ceramic hollow disk
resonators. (Corresponding author: Esmaeel Zanganeh.)Esmaeel Zanganeh and
Polina Kapitanova are with School of Physics and Engineering, ITMO University,
197101, Saint Petersburg, Russia. (e-mail<EMAIL_ADDRESS>Elizaveta Nenasheva is with Ceramics Co., Ltd, 194223, Saint Petersburg,
Russia.

###### Abstract

To achieve omnidirectional wireless power transfer with high efficiency, a
high Q-factor transmitter generating homogeneous magnetic field is crucial.
Traditionally, orthogonal coils of different shapes are used to realize
transmitters. In this paper, we develop an omnidirectional magnetic resonant
wireless power transfer system based on a dielectric disk resonator with
colossal permittivity and low loss operating at axial magnetic quadrupole
mode. The constant power transfer efficiency of $88\%$ at the frequency of 157
MHz over the transfer distance of $3~{}cm$ for all angular positions of a
receiver is experimentally demonstrated. The possibility of multi-receivers
charging is also studied demonstrating a total efficiency of $90\%$ regardless
of angular position between two receivers with respect to the transmitting
disk resonator. The minimized exposure of biological tissues to the electric
and magnetic fields as well as a low specific absorption rate is observed that
makes the WPT system safer for charging with higher input power.

###### Index Terms:

Omnidirectional, Magnetic quadrupole, wireless power transfer (WPT),
dielectric resonator

##  I Introduction

Wireless power transfer (WPT) technologies are used to charge batteries of
different electronic devices [1, 2, 3, 4, 5]. Among different techniques, the
magnetic resonant WPT has attracted great attention for its potential in safe
mid-range charging [6, 7, 8, 9, 10]. However, the power transfer efficiency
(PTE) of magnetic resonant WPT systems based on metal coils still suffer from
high ohmic and radiation losses and their angular instability [11, 12, 13]. To
reduce the ohmic loss and enhance the PTE, the use of dielectric resonators
instead of metallic coils have been recently proposed [14, 15, 16]. To further
enhance the PTE of WPT systems, a dielectric metasurface supporting a quasi
magnetic bound state in the continuum was introduced [16]. Another useful
feature of the dielectric resonators is the ability to engineer the response
by combination of different modes [17, 18, 19]. Thus, nonradiating sources
based on anapole states of dielectric disk resonators can be obtained [20, 21,
22, 23] bringing a benefit for PTE enhancement of WPT systems due to
suppression of radiation losses [24].

To expand charging regions for more convenient utilization, modern WPT systems
are required to be insensitive to positional misalignment [25, 26]. Therefore,
for WPT to arbitrary spatial position devices, omnidirectional systems have
been intensively investigated [27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39]. Most of the proposed omnidirectional WPT systems are based on orthogonal
transmitting (Tx) coils of different shapes [29, 27, 30, 28]. Such structures
effectively eliminate the cross-coupling effect between multiple coils and
generate uniform magnetic field. However, these structures need several power
sources to feed each Tx coil and dynamically control the phases and amplitudes
of coil currents. Recently, Tx coils fed by a single power source generating
uniform magnetic fields were implemented [32, 34]. One of the drawbacks of
these systems is the existence of the blind zones with very small
electromagnetic coupling to a reciever (Rx) and as a result, low PTE. Another
limitation is the safety of omnidirectional WPT systems to the biological
tissues. As soon as the shielding techniques could not be applied, the level
of electric and magnetic fields created by omnidirectional WPT systems must
satisfy the limitations regulated by the standard [40]. Thus, the allowable
power transferred by an omnidirectional WPT system could be limited.

In this letter, we propose an omnidirectional WPT system based on a dielectric
hollow disk resonator operating at axial magnetic quadrupole mode. We
demonstrate that at this mode, the resonator produces a homogeneous magnetic
field in the transverse plane which can be potentially used to enable
equivalent power transmission to Rxs at any angular position around the Tx. We
theoretically and experimentally study the omnidirectional WPT system with
single and two Rxs in MHz frequency band. We demonstrate that the advantage of
the dielectric resonator with respect to metallic coils is the confinement of
the electric field. As a result, the exposure of electric and magnetic fields
to biological tissues is minimized. This results in a very low specific
absorption rate (SAR), making it a safer option for omnidirectional wireless
charging.

Figure 1: (a) Schematic view of the dielectric hollow disk resonator with
outer radius $R_{o}=62.2~{}mm$, inner radius $R_{in}=50.75~{}mm$, height
$h=100~{}mm$, permittivity $\varepsilon=1000$ and loss tangent
$tan\delta=4\times 10^{-4}$. Simulated magnetic field distributions of (b) the
TMD (b), TMQ (c), and AMQ (d) resonator modes in the transverse and axial
planes. Figure 2: (a) Schematic view of a WPT system based on the dielectric
hollow disk resonator excited by a simple copper loop. The radius of the Rx
resonator and load loop is set as $R_{2}=R_{3}=40~{}mm$ for systems operating
at all three modes under study. Transfer distance is $d=3~{}cm$. The wire
radius is $t=2~{}mm$.(b) PTE of the WPT systems operating at the TMD, TMQ, and
AMQ modes extracted from the simulated S-parameters by Eq(1). Simulated
magnetic field distributions of the WPT systems operating at the TMD (c) TMQ
(d), and AMQ (e) modes at the transverse and axial planes.

##  II Eigenmode analysis

A schematic view of the dielectric hollow disk resonator is shown in Fig.
fig1(a). We start with the eigenmode analysis of the dielectric resonator in
CST Microwave Studio 2022, which reveals three modes at the frequencies of
138, 152.5, and 150.2 MHz, respectively. Simulated magnetic field
distributions of all modes in both transverse ($\it{x}$-$\it{y}$) and axial
($\it{x}$-$\it{z}$) planes are illustrated in Fig. fig1(b-d). For the first
mode at the frequency of 138 MHz, the magnetic field oscillates along the
$\it{x}$-axis (see Fig. fig1(b)). From the point of view of traditional
dielectric resonators antenna design, this mode is known as HEM11δ [41]. For
the second mode at the frequency of 152.5 MHz, the magnetic field is
oscillating inside of the resonator providing four maximums in the transverse
plane as shown in Fig. fig1(c). This mode is classified as HEM21δ mode. At the
frequency of 150.2 MHz, the homogeneous radial magnetic field distribution in
the transverse plane together by oscillating fields in z-direction is
obtained. This mode is classified as TE011+δ mode. However, using Mie
scattering theory [42], the obtained HEM11δ, HEM21δ, and TE011+δ modes can be
classified as transverse magnetic dipole (TMD), transverse magnetic quadrupole
(TMQ), and axial magnetic quadrupole (AMQ), respectively.

To design a highly efficient omnidirectional WPT system, one needs to provide
a high Q-factor and uniform magnetic field distribution over the angle. The
numerically estimated Q-factor is found as high as 2510 for all the modes
under consideration. However, the magnetic field distributions of TMD and TMQ
modes have blind zones which may lead to weak coupling with Rx. The AMQ mode
provides a uniform magnetic field distribution in the transverse plane. Being
properly excited, this mode can be used to overcome the blind zone limitation
and implement the Tx for an omnidirectional WPT system enabling power
transmission to Rxs at any angular position around the Tx.

Figure 3: (a) Photo of the omnidirectional WPT system experimental setup with
one $Rx$. (b) Measured S-parameters of the system for different angular
positions of the $Rx$. (c) Measured and simulated PTE of the omnidirectional
WPT system at the frequency of 157 MHz as a function of the $Rx$ angular
position $\theta$. The inset shows the design of the $Tx$ with symmetrical
excitation shielded loop centered on the hollow disk with a radius of
$R_{1}=45~{}mm$ and height $L=25~{}mm$ and a $2~{}mm$ gap between its two
vertical sections.

##  III Numerical study

The PTE of WPT systems based on the dielectric hollow disk resonator operating
at the TMD, TMQ, and AMQ modes is numerically studied. A schematic view of the
WPT system created in the CST is shown in Fig. fig2(a). The dielectric
resonator excited by a copper source loop with radius $R_{1}$ is used as the
Tx. The Rx resonator is placed at a transfer distance $d$ with respect to the
Tx. The Rx resonator is a simple copper loop with a radius of $R_{2}$
terminated by a capacitor $C$ to provide a resonance at the same frequency as
the Tx. A load loop made of a copper wire with a radius of $R_{3}$ is placed
at a distance of $S$ from the Rx resonator. A $50~{}\Omega$ port is inserted
in the slits on both source and load loops. The reflection and transmission
coefficients for the different angular positions of the Rx are numerically
obtained in CST Microwave Studio and used to calculate the PTE as follows:

$\eta=\frac{\mid S_{21}\mid^{2}}{1-\mid S_{11}\mid^{2}}\times 100~{}\%.$ (1)

The geometrical parameters and capacitance value obtained during the numerical
optimization of the WPT systems at different modes are listed in Table. I. The
PTEs calculated by Eq (1) as a function of Rx angular position are shown in
Fig. fig2(b). At TMD mode the PTE is zero for the angles around $90^{o}$ and
the Rx cannot be charged there. The magnetic field of the system working at
TMD is oscillating in $\it{x}$ direction and is minimum around
$\theta=90^{0}$. For the system working at TMQ mode, there are two blind zones
around $80^{o}$ and $100^{o}$ angles, where the PTE is around $40\%$. The
magnetic field is oscillating along both $\it{x}$ and $\it{y}$ axes (Fig.
fig2(d)). In the system working at AMQ mode, the PTE is over $80\%$ for all
angles. The magnetic field provides almost uniform distribution in the
transverse plane Fig. fig2(e). However, the PTE is not still constant due to
the asymmetric excitation of the Tx.

TABLE I: Geometrical parameters, capacitor value, and resonant frequency of WPT systems operating at TMD (HEM11δ), TMQ (HEM21δ), and AMQ (TE011+δ) modes. Mode |  $R_{1}$(mm) |  $S_{off}$ (mm) |  $C$ (pf) |  $S$ (mm) | f (MHz)
---|---|---|---|---|---
TMD | 45 | 0 | 7.4 | 15 | 138
TMQ | 30 | 30 | 6.45 | 12 | 153
AMQ | 30 | 30 | 6.7 | 12 | 150

To achieve the constant PTE of the WPT system working at the AMQ mode, we come
up with a symmetric source loop design, as shown in the inset of Fig. fig3(c).
The PTE of the WPT system working at the AMQ mode with symmetrical excitation
is calculated and shown in Fig. fig3(c). The maximal PTE of $90\%$ for all
angular positions of the single Rx is achieved numerically.

##  IV Experimental study

Next, we experimentally study the performance of the WPT system operating at
the AMQ mode. The fabricated prototype of the WPT system is shown in Fig.
fig3(a). It comprises of a dielectric hollow disk resonator excited by a
symmetric source loop as the Tx, and an Rx resonator coupled to a load loop.
Due to some technical limitations, we could not fabricate the disk with the
parameters used in simulations. Thus, we stack it of five hollow disks with
the following dimensions: the inner radius of $R_{in}=50.75~{}mm$, the outer
radius of $R_{o}=62.2~{}mm$, and the height of $h_{d}=20~{}mm$. The hollow
disks are made from BaSrTiO3, including Mg-containing compositions and have
the permittivity of $\varepsilon\ =1000$ and $tan\delta=4\times 10^{-4}$ (at 1
MHz) [43]. Since the ceramic disks are fragile, several thin hollow spacers
made of plexiglas with relative dielectric permittivity around $3.5$ and
electrical conductivity of $0.02~{}Sm^{-1}$ and height of $3~{}mm$ are used
between them. The symmetric source loop is a shielded loop made of a coaxial
cable [44]. The Rx resonator is made of copper wire with radius
$R_{2}=34~{}mm$ and wire diameter $t=1~{}mm$. To provide the resonance at the
frequency of 157 MHz, the Rx is matched by $C=6.8~{}pf$ capacitor. The load
loop radius is $R_{3}=30~{}mm$. The end of the source and load loops are
connected to the $50~{}\Omega$ ports of a Vector Network Analyzer (VNA) by
coaxial cables.

The S-parameters of the WPT system as a function of the Rx angular position
with the step of $15^{o}$ are measured and several of them are shown in Fig.
fig3(b). Then, the PTE is calculated using Eq.(1) and compared to the
simulated PTE in Fig. fig3(c). An equivalent PTE above $88\%$ for all Rx
angular positions is achieved.

Figure 4: (a) Photo of the omnidirectional WPT system experimental setup with two $Rxs$ separated by angle $\theta_{2}$. (b) Measured S-parameters of the omnidirectional WPT system for $\theta_{2}=50^{0}$ and $\theta_{2}=180^{0}$. (c) Measured and simulated PTEs of $Rx_{1}$, $Rx_{2}$ and total PTE of the omnidirectional WPT system at the frequency of 154 MHz as a function of $\theta_{2}$. Note that the angles between $0^{o}$ to $50^{o}$ are not feasible due to the receivers’ size restrictions. TABLE II: Comparison of omnidirectional and directional magnetic resonant WPT systems based on metallic and dielectric resonators. Ref. | Frequency | Tx resonator type | PTE($\%$) |  | Blind zone | Distance/ $\lambda$ | Tx size/ $\lambda$
---|---|---|---|---|---|---|---
[6] | 10 MHz | Metal coil | 94 |  | Yes | 0.025 | 0.02
[14] | 232 MHz | Dielectric disk | 90 |  | Yes | 0.03 | 0.0649
[15] | 2.4 GHz | Dielectric sphere | 80 |  | Yes | 0.05 | 0.8
[24] | 408 MHz | Dielectric disk | 92 |  | Yes | 0.055 | 0.1142
[31] | 535 KHz | Orthogonal coils | 78 |  | No | 0 | $5.35\times 10^{-4}$
[32] | 13.56 MHz | Cubic Metal coil | 60 |  | No | 0.0136 | 0.009
[33] | 20 KHz | Orthogonal coils | 11.5 |  | No | $4\times 10^{-6}$ | $2\times 10^{-5}$
[34] | 13.56$\And$27.12 MHz | Metal coil | 61.6$\And$65.4 |  | No | 0.004 | 0.0072
[36] | 6.78 MHz | Metal coil | 74.2 (DC-DC) |  | No | $4.5\times 10^{-4}$ | 0.0034
This work | 157 MHz | Dielectric disk | 88 |  | No | 0.016 | 0.065

##  V Multi-receiver omnidirectional WPT

We also experimentally study the system with two Rxs. An identical second Rx
($Rx_{2}$) is added to the system with the angular position of $\theta_{2}$
with respect to the $Rx_{1}$ as shown in Fig. fig4(a). The S-parameters of the
system as a function of the $\theta_{2}$ with the step of $20^{o}$ are
measured and several of them are depicted in Fig. fig4(b). One can see that
not only the operational frequency is stable for all angular positions, but
also the transmission and reflection coefficient magnitudes are at the same
level. The PTEs of $Rx_{1}$ and $Rx_{2}$ are calculated from the measured
S-parameters using Eq (1). The total PTE is calculated as the sum of the first
and second Rx PTEs.

The variation of the $Rx_{1}$, $Rx_{2}$, and total PTEs concerning the angle
between the $Rx_{1}$ and $Rx_{2}$, ($\theta_{2}$), are compared to the
simulated results in Fig. fig4(c). One can see the total PTE remains almost
$90\%$ regardless of the addition of the $Rx_{2}$, or its position. Also, the
PTEs of $Rx_{1}$ and $Rx_{2}$ remain stable and almost equal for all angles.
Therefore, it is clear that the WPT system operating at AMQ can be applied to
omnidirectional WPT with multi-receivers.

##  VI Discussion

To understand the benefits of the proposed WPT system, we compare its
characteristics with other implementations reported in the literature (Table.
II). The proposed omnidirectional WPT system operates at the frequency of 157
MHz and achieves $88\%$ of the PTE to a single Rx over $3~{}cm$ transfer
distance. This PTE is comparable to the systems reported in [6, 14, 24, 15]
that do not offer omnidirectionality. Compared to the omnidirectional WPT
systems reported in [31, 32, 33, 34, 36], the proposed WPT system provides the
highest PTE over a larger distance without any blind zone. For instance, our
proposed system outperforms the metal coil-based system in Ref. [34] in both
efficiency ($88\%$ vs. $65.4\%$) and operation distance normalized to
wavelength ($0.016$ vs. $0.004$). This demonstrates the superior performance
of our proposed WPT system.

To ensure the safety, it is crucial to examine the field exposure to
biological tissues and SAR [40]. The electric and magnetic fields of the
proposed WPT system’s Tx with symmetric excitation are compared with fields of
the metal Txs of omnidirectional WPT systems reported in Ref. [34] and Ref.
[36]. The central cross sections of the electric and magnetic field
distributions simulated in CST Microwave Studio are compared in Fig. 5(a) and
(b), respectively. The magnetic field of the proposed Tx based on dielectric
disk resonator has the highest amplitude at short distances $d$ in comparison
to the magnetic fields provided by the designs reported in Ref. [34] and Ref.
[36]. Its magnitude decays faster as $d$ increases (Fig. 5(a)), indicating
strong accumulation of the magnetic field in proximity of the dielectric
resonator. The electric field of the proposed Tx (see Fig. 5(b)) is negligible
compared to electric fields of the metal Txs reported in Ref. [34] and Ref.
[36]. Therefore, the proposed omnidirectional WPT system based on the
dielectric resonator offers the strong confinement of the electric field
providing less exposure of the electric field [40] to surrounding biological
tissues compared to WPT systems based on metal Txs.

To perform SAR analysis, we employ CST Microwave Studio and a computer-aided-
design model of the front part of a human arm as depicted in Fig. 5(c). The
model consists of the main biological tissues of the arm characterized by
their corresponding electromagnetic properties. The distance between the Tx
and the arm is 4 cm. For the input power of 0.5 W, the maximal calculated SAR
is 0.034 W/kg, averaged over 1 g of tissue (see Fig. 5(c)). There are no
nonlinear effects in the WPT system, and the maximal SAR for different input
powers can be obtained by scaling up these results. According to the IEEE
safety regulation [40], which specifies the maximum SAR value for limbs and
pinnae as 4 W/kg, a maximal input power of 117 W is allowed.

Figure 5:  Simulated (a) magnetic and (b) electric fields of the proposed
omnidirectional WPT Tx as a function of the distance $d$ compared to the Tx of
the omnidirectional WPT systems based on metallic coils reported in Refs [34]
(square coil) and [36]. To verify the correctness of our simulations with the
results presented in Ref. [34] we made sure that the reflection coefficient
coincides with Fig. 12(a) in Ref. [34]. Magnetic field data presented in Fig.
2 of Ref. [36] is added to panel (a), which coincides with the recalculated
magnetic field of the Tx. (c) Simulated SAR of the omnidirectional WPT Tx in
an arm located at a distance of $4~{}cm$.

##  VII Conclusion

We proposed the omnidirectional WPT system based on a dielectric hollow disk
resonator operating at AMQ mode. A uniform radial magnetic field in the
transverse plane of the Tx resonator is generated helping to avoid the blind
zone. A symmetric excitation loop to achieve a constant PTE over all angular
positions of the Rx is proposed. With respect to the experimental data, the
omnidirectional WPT system provides $88\%$ of PTE over all angles at the
transfer distance of $3~{}cm$ to a single Rx. The possibility of charging
multi-receivers is also experimentally verified. The results showed a stable
and high efficiency of $90\%$ regardless of the angle between two Rxs.
Examination of the safety issues of the proposed WPT system revealed minimal
exposure of the electromagnetic fields to biological tissues, resulting in a
very low SAR. These findings establish the proposed WPT system as a safer
option for omnidirectional wireless charging.

## References

  * [1] M. Song, P. Jayathurathnage, E. Zanganeh, M. Krasikova, P. Smirnov, P. Belov, P. Kapitanova, C. Simovski, S. Tretyakov, and A. Krasnok, “Wireless power transfer based on novel physical concepts,” _Nature Electronics_ , vol. 4, pp. 707–716, 10 2021.
  * [2] A. Mahesh, B. Chokkalingam, and L. Mihet-Popa, “Inductive wireless power transfer charging for electric vehicles–a review,” _IEEE Access_ , vol. 9, pp. 137 667–137 713, 2021.
  * [3] Z. Zhang, H. Pang, A. Georgiadis, and C. Cecati, “Wireless power transfer—an overview,” _IEEE Transactions on Industrial Electronics_ , vol. 66, no. 2, pp. 1044–1058, 2019.
  * [4] M. Song, P. Belov, and P. Kapitanova, “Wireless power transfer inspired by the modern trends in electromagnetics,” _Applied Physics Reviews_ , vol. 4, 2017\.
  * [5] C. Jiang, K. Chau, C. Liu, and C. H. Lee, “An overview of resonant circuits for wireless power transfer,” _Energies_ , vol. 10, no. 7, p. 894, 2017.
  * [6] A. Kurs, A. Karalis, R. Moffatt, J. D. Joannopoulos, P. Fisher, and M. Soljačić, “Wireless power transfer via strongly coupled magnetic resonances,” _science_ , vol. 317, no. 5834, pp. 83–86, 2007.
  * [7] M. Dionigi, A. Costanzo, F. Mastri, and M. Mongiardo, “Magnetic resonant wireless power transfer,” in _Wireless Power Transfer_. River Publishers, 2022, pp. 157–197.
  * [8] S. Niu, H. Xu, Z. Sun, Z. Shao, and L. Jian, “The state-of-the-arts of wireless electric vehicle charging via magnetic resonance: principles, standards and core technologies,” _Renewable and Sustainable Energy Reviews_ , vol. 114, p. 109302, 2019.
  * [9] X. Mou, D. T. Gladwin, R. Zhao, and H. Sun, “Survey on magnetic resonant coupling wireless power transfer technology for electric vehicle charging,” _IET Power Electronics_ , vol. 12, no. 12, pp. 3005–3020, 2019.
  * [10] M. Song, P. Smirnov, E. Puhtina, E. Zanganeh, S. Glybovski, P. Belov, and P. Kapitanova, “Multi-mode metamaterial-inspired resonator for near-field wireless power transfer,” _Applied Physics Letters_ , vol. 117, no. 8, p. 083501, 2020.
  * [11] F. Liu, Y. Yang, D. Jiang, X. Ruan, and X. Chen, “Modeling and optimization of magnetically coupled resonant wireless power transfer system with varying spatial scales,” _IEEE Transactions on Power Electronics_ , vol. 32, no. 4, pp. 3240–3250, 2017.
  * [12] E. Shamonina, L. Solymar, and V. Kalinin, “On wireless power transfer between coils in the presence of radiation,” _Journal of Physics D: Applied Physics_ , vol. 54, no. 40, p. 405502, 2021.
  * [13] T. Sasatani, A. P. Sample, and Y. Kawahara, “Room-scale magnetoquasistatic wireless power transfer using a cavity-based multimode resonator,” _Nature Electronics_ , vol. 4, no. 9, pp. 689–697, 2021.
  * [14] M. Song, P. Belov, and P. Kapitanova, “Wireless power transfer based on dielectric resonators with colossal permittivity,” _Applied Physics Letters_ , vol. 109, no. 22, p. 223902, 2016.
  * [15] M. Song, I. Iorsh, P. Kapitanova, E. Nenasheva, and P. Belov, “Wireless power transfer based on magnetic quadrupole coupling in dielectric resonators,” _Applied Physics Letters_ , vol. 108, no. 2, p. 023902, 2016.
  * [16] Y. Xie, Z. Zhang, Y. Lin, T. Feng, and Y. Xu, “Magnetic quasi-bound state in the continuum for wireless power transfer,” _Phys. Rev. Applied_ , vol. 15, p. 044024, Apr 2021.
  * [17] H. K. Shamkhi, K. V. Baryshnikova, A. Sayanskiy, P. Kapitanova, P. D. Terekhov, P. Belov, A. Karabchevsky, A. B. Evlyukhin, Y. Kivshar, and A. S. Shalin, “Transverse scattering and generalized kerker effects in all-dielectric mie-resonant metaoptics,” _Physical review letters_ , vol. 122, no. 19, p. 193905, 2019.
  * [18] A. E. Miroshnichenko, A. B. Evlyukhin, Y. F. Yu, R. M. Bakker, A. Chipouline, A. I. Kuznetsov, B. Luk’yanchuk, B. N. Chichkov, and Y. S. Kivshar, “Nonradiating anapole modes in dielectric nanoparticles,” _Nature communications_ , vol. 6, no. 1, pp. 1–8, 2015.
  * [19] V. E. Babicheva and A. B. Evlyukhin, “Resonant lattice kerker effect in metasurfaces with electric and magnetic optical responses,” _Laser & Photonics Reviews_, vol. 11, no. 6, p. 1700132, 2017.
  * [20] E. Zanganeh, A. Evlyukhin, A. Miroshnichenko, M. Song, E. Nenasheva, and P. Kapitanova, “Anapole meta-atoms: Nonradiating electric and magnetic sources,” _Physical Review Letters_ , vol. 127, no. 9, p. 096804, 2021.
  * [21] P. Kapitanova, E. Zanganeh, N. Pavlov, M. Song, P. Belov, A. Evlyukhin, and A. Miroshnichenko, “Seeing the unseen: experimental observation of magnetic anapole state inside a high-index dielectric particle,” _Annalen der Physik_ , vol. 532, no. 12, p. 2000293, 2020.
  * [22] A. A. Basharin, E. Zanganeh, A. K. Ospanova, P. Kapitanova, and A. B. Evlyukhin, “Selective superinvisibility effect via compound anapole,” _Physical Review B_ , vol. 107, no. 15, p. 155104, 2023.
  * [23] E. Zanganeh, M. Song, A. Evlyukhin, and P. Kapitanova, “Electromagnetic anapole states of nano-disks,” in _AIP Conference Proceedings_ , vol. 2300, no. 1. AIP Publishing LLC, 2020, p. 020138.
  * [24] E. Zanganeh, M. Song, A. C. Valero, A. S. Shalin, E. Nenasheva, A. Miroshnichenko, A. Evlyukhin, and P. Kapitanova, “Nonradiating sources for efficient wireless power transfer,” _Nanophotonics_ , vol. 10, no. 17, pp. 4399–4408, 2021.
  * [25] J. Kim, D.-H. Kim, and Y.-J. Park, “Free-positioning wireless power transfer to multiple devices using a planar transmitting coil and switchable impedance matching networks,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 64, no. 11, pp. 3714–3722, 2016.
  * [26] E. Zanganeh, A. Sayanskiy, S. Kosulnikov, and P. Kapitanova, “Extreme metasurfaces enable targeted and protected wireless energy transfer,” _Advanced Materials Technologies_ , p. 2202133, 2023.
  * [27] J. Feng, Q. Li, and F. C. Lee, “Load detection and power flow control algorithm for an omnidirectional wireless power transfer system,” _IEEE Transactions on Industrial Electronics_ , vol. 69, no. 2, pp. 1422–1431, 2021\.
  * [28] Z. Ye, Y. Sun, X. Liu, P. Wang, C. Tang, and H. Tian, “Power transfer efficiency analysis for omnidirectional wireless power transfer system using three-phase-shifted drive,” _Energies_ , vol. 11, no. 8, 2018.
  * [29] Z. Zhang and B. Zhang, “Angular-misalignment insensitive omnidirectional wireless power transfer,” _IEEE Transactions on Industrial Electronics_ , vol. 67, no. 4, pp. 2755–2764, 2020.
  * [30] J. Feng, Q. Li, F. C. Lee, and M. Fu, “Transmitter coils design for free-positioning omnidirectional wireless power transfer system,” _IEEE Transactions on Industrial Informatics_ , vol. 15, no. 8, pp. 4656–4664, 2019\.
  * [31] D. Lin, C. Zhang, and S. R. Hui, “Mathematic analysis of omnidirectional wireless power transfer—part-ii three-dimensional systems,” _IEEE Transactions on Power Electronics_ , vol. 32, no. 1, pp. 613–624, 2016.
  * [32] N. Ha-Van and C. Seo, “Analytical and experimental investigations of omnidirectional wireless power transfer using a cubic transmitter,” _IEEE Transactions on Industrial Electronics_ , vol. 65, no. 2, pp. 1358–1366, 2017.
  * [33] H. Han, Z. Mao, Q. Zhu, M. Su, and A. P. Hu, “A 3d wireless charging cylinder with stable rotating magnetic field for multi-load application,” _IEEE Access_ , vol. 7, pp. 35 981–35 997, 2019.
  * [34] C. Lu, X. Huang, X. Tao, X. Liu, C. Rong, Y. Zeng, and M. Liu, “Design and analysis of an omnidirectional dual-band wireless power transfer system,” _IEEE Transactions on Antennas and Propagation_ , vol. 69, no. 6, pp. 3493–3502, 2020.
  * [35] J. Li, Y. Yang, H. Yan, C. Liu, L. Dong, and G. Wang, “Quasi-omnidirectional wireless power transfer for a sensor system,” _IEEE Sensors Journal_ , vol. 20, no. 11, pp. 6148–6159, 2020.
  * [36] N. Ha-Van, Y. Liu, P. Jayathurathnage, C. R. Simovski, and S. A. Tretyakov, “Cylindrical transmitting coil for two-dimensional omnidirectional wireless power transfer,” _IEEE Transactions on Industrial Electronics_ , vol. 69, no. 10, pp. 10 045–10 054, 2022.
  * [37] T. Feng, Z. Zuo, Y. Sun, X. Dai, X. Wu, and L. Zhu, “A reticulated planar transmitter using a three-dimensional rotating magnetic field for free-positioning omnidirectional wireless power transfer,” _IEEE Transactions on Power Electronics_ , vol. 37, no. 8, pp. 9999–10 015, 2022.
  * [38] J. Feng, Q. Li, and F. C. Lee, “Load detection and power flow control algorithm for an omnidirectional wireless power transfer system,” _IEEE Transactions on Industrial Electronics_ , vol. 69, no. 2, pp. 1422–1431, 2022\.
  * [39] P. Jayathurathnage, X. Dang, C. R. Simovski, and S. A. Tretyakov, “Self-tuning omnidirectional wireless power transfer using double-toroidal helix coils,” _IEEE Transactions on Industrial Electronics_ , vol. 69, no. 7, pp. 6828–6837, 2022.
  * [40] I. C. 1, “Ieee standard for safety levels with respect to human exposure to electric, magnetic and electromagnetic fields, 0 hz to 300 ghz,” _The Institute of Electrical and Electronics Engineers New York, NY_ , 2019.
  * [41] R. K. Mongia and P. Bhartia, “Dielectric resonator antennas—a review and general design relations for resonant frequency and bandwidth,” _International Journal of Microwave and Millimeter-Wave Computer-Aided Engineering_ , vol. 4, no. 3, pp. 230–247, 1994.
  * [42] C. Bohren and D. Huffman, _Absorption and Scattering of Light by Small Particles_. John Wiley & Sons, New York, 2008.
  * [43] E. Nenasheva, N. Kartenko, I. Gaidamaka, O. Trubitsyna, S. Redozubov, A. Dedyk, and A. Kanareykin, “Low loss microwave ferroelectric ceramics for high power tunable devices,” _Journal of the European Ceramic Society_ , vol. 30, no. 2, pp. 395–400, 2010.
  * [44] C. F. Carobbi and L. M. Millanta, “Analysis of the common-mode rejection in the measurement and generation of magnetic fields using loop probes,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 53, no. 2, pp. 514–523, 2004.


# Information Directed Sampling for Sparse Linear Bandits

Botao Hao
Deepmind
<EMAIL_ADDRESS>
&Tor Lattimore
Deepmind
<EMAIL_ADDRESS>
Wei Deng
Department of Mathematics
Purdue University
<EMAIL_ADDRESS>

###### Abstract

Stochastic sparse linear bandits offer a practical model for high-dimensional
online decision-making problems and have a rich information-regret structure.
In this work we explore the use of information-directed sampling (IDS), which
naturally balances the information-regret trade-off. We develop a class of
information-theoretic Bayesian regret bounds that nearly match existing lower
bounds on a variety of problem instances, demonstrating the adaptivity of IDS.
To efficiently implement sparse IDS, we propose an empirical Bayesian approach
for sparse posterior sampling using a spike-and-slab Gaussian-Laplace prior.
Numerical results demonstrate significant regret reductions by sparse IDS
relative to several baselines.

##  1 Introduction

Standard linear bandits associate each action with a feature vector and assume
the mean reward is the inner product between the feature vector and an unknown
parameter vector (Auer, 2002; Dani et al., 2008; Rusmevichientong and
Tsitsiklis, 2010; Chu et al., 2011; Abbasi-Yadkori et al., 2011). Sparse
linear bandits generalize linear bandits by assuming the unknown parameter
vector is sparse (Abbasi-Yadkori et al., 2012; Carpentier and Munos, 2012; Hao
et al., 2020b) and is of great practical significance for modeling high-
dimensional online decision-making problems (Bastani and Bayati, 2020).

Lattimore and Szepesvári (2020, §24.3) established a $\Omega(\sqrt{sdn})$
regret lower bound for the _data-rich regime_ , where $n$ is the horizon, $d$
is the feature dimension, $s$ is the sparsity and data-rich regime refers to
the horizon $n\geq d^{\alpha}$ for some $\alpha>0$. This means polynomial
dependence on $d$ is generally not avoidable without additional assumptions.
However, this bound hides much of the rich structure of sparse linear bandits
by a crude maximisation over all environments.

When the action set admits a well-conditioned exploration distribution, Hao et
al. (2020b) discovered the information-regret trade-off phenomenon by
establishing an $\Theta(\operatorname{poly}(s)n^{2/3})$ minimax rate for the
_data-poor regime_. An interpretation for this optimal rate is that the agent
needs to acquire enough information for fast sparse learning by pulling
informative actions that even have high regret. Explore-then-commit algorithm
can achieve this rate for the data-poor regime but is sub-optimal in the data-
rich regime. Therefore, our goal is to develop an efficient algorithm that can
adapt to different information-regret structures for sparse linear bandits.

#### Contributions

Our contribution is three-fold:

  * •

We prove that optimism-based algorithms fail to optimally address the
information-regret trade-off in sparse linear bandits, which results in a sub-
optimal regret bound.

  * •

We provide the first analysis using information theory for sparse linear
bandits and derive a class of nearly optimal Bayesian regret bounds for IDS
that can adapt to information-regret structures.

  * •

To approximate the information ratio, we develop an empirical Bayesian
approach for sparse posterior sampling using spike-and-slab Gaussian-Laplace
prior. Through several experiments, we justify the great empirical performance
of sparse IDS with an efficient implementation.

##  2 Preliminary

We first introduce the basic setup of stochastic sparse linear bandits. The
agent receives a compact action set $\mathcal{A}\subseteq\mathbb{R}^{d}$ in
the beginning where $|\mathcal{A}|=K$. At each round $t$, the agent chooses an
action $A_{t}\in\mathcal{A}$ and receives a reward $Y_{t}=\langle
A_{t},\theta^{*}\rangle+\eta_{t},$ where $(\eta_{t})_{t=1}^{n}$ is a sequence
of independent standard Gaussian random variables and
$\theta^{*}\in\mathbb{R}^{d}$ is the true parameter unknown to the agent. We
make the mild boundedness assumption that for all $a\in\mathcal{A}$,
$\|a\|_{\infty}\leq 1$. The notion of sparsity can be defined through the
parameter space $\Theta$:

$\Theta=\left\\{\theta\in\mathbb{R}^{d}\Bigg{|}\sum_{j=1}^{d}\operatorname{\mathds{1}}\\{\theta_{j}\neq
0\\}\leq s,\|\theta\|_{2}\leq 1\right\\}\,.$

We assume $s$ is known and it can be relaxed by putting a prior on it. We
consider the Bayesian setting where $\theta^{*}$ is a random variable taking
values in $\Theta$ and denote $\rho$ as the prior distribution. The optimal
action is $x^{*}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\mathbb{E}[\langle
a,\theta^{*}\rangle|\theta^{*}]$. The agent chooses $A_{t}$ based on the
history $\mathcal{F}_{t}=(A_{1},Y_{1},\ldots,A_{t-1},Y_{t-1})$. Let
$\mathcal{D}(\mathcal{A})$ be the space of probability measures over
$\mathcal{A}$. A policy $\pi=(\pi_{t})_{t\in\mathbb{N}}$ is a sequence of
deterministic functions where $\pi_{t}(\mathcal{F}_{t})$ specifies a
probability distribution over $\mathcal{A}$. The information-theoretic
Bayesian regret of a policy $\pi$ (Russo and Van Roy, 2014) is defined as

$\mathfrak{BR}(n;\pi)=\mathbb{E}\left[\sum_{t=1}^{n}\langle
x^{*},\theta^{*}\rangle-\sum_{t=1}^{n}Y_{t}\right]\,,$

where the expectation is over the interaction sequence induced by the agent
and environment and the prior distribution over $\theta^{*}$.

#### Notation

Denote $I_{d}$ as the $d\times d$ identity matrix. Let
$[n]=\\{1,2,\ldots,n\\}$. For a vector $x$ and positive semidefinite matrix
$A$, we let $\|x\|_{A}=\sqrt{x^{\top}Ax}$ be the weighted $\ell_{2}$-norm and
$\sigma_{\min}(A)$ be the minimum eigenvalue of $A$. The relation $x\gtrsim y$
means that $x$ is greater or equal to $y$ up to some universial constant and
$\widetilde{O}(\cdot)$ hides modest logarithmic factors and universal
constant. The cardinality of a set $\mathcal{A}$ is denoted by
$|\mathcal{A}|$. Given a measure $\mathbb{P}$ and jointly distributed random
variables $X$ and $Y$ we let $\mathbb{P}_{X}$ denote the law of $X$ and we let
$\mathbb{P}_{X|Y}$ be the conditional law of $X$ given $Y$:
$\mathbb{P}_{X|Y}(\cdot)=\mathbb{P}(X\in\cdot|Y)$. The mutual information
between $X$ and $Y$ is
$I(X;Y)=\mathbb{E}[D_{\mathrm{KL}}(\mathbb{P}_{X|Y}||\mathbb{P}_{X})]$ where
$D_{\mathrm{KL}}$ is the relative entropy. We write
$\mathbb{P}_{t}(\cdot)=\mathbb{P}(\cdot|\mathcal{F}_{t})$ as the posterior
measure where $\mathbb{P}$ is the probability measure over $\theta$ and the
history and $\mathbb{E}_{t}(\cdot)=\mathbb{E}(\cdot|\mathcal{F}_{t})$. Denote
$I_{t}(X;Y)=\mathbb{E}_{t}[D_{\mathrm{KL}}(\mathbb{P}_{t,X|Y}||\mathbb{P}_{t,X})]$.

##  3 Related work

Table 1: Comparisons with existing results. APS11, LCS15, HLW20 refer to
Abbasi-Yadkori et al. (2012); Lattimore et al. (2015); Hao et al. (2020b)
accordingly. Exploratory action set is defined in Definition 5.2 and $K$ is
the number of actions. The last lower bound is developed in Hao et al.
(2020b).

| Action set | Algorithm | Type | Rate
---|---|---|---|---
APS11 | arbitrary | online-to-confidence | freq | $O(\sqrt{sdn})$
LCS15 | hypercube | elimination | freq | $O(s\sqrt{n})$
HLW20 | exploratory | explore-then-commit | freq | $O(s^{2/3}n^{2/3})$
This paper | arbitrary | sparse IDS | Bayesian | $O(\min(\sqrt{sdn},\sqrt{dn\log(K)}))$
This paper | arbitrary | sparse TS | Bayesian | $O(\min(\sqrt{sdn},\sqrt{dn\log(K)}))$
This paper | exploratory | sparse IDS | Bayesian | $O(\min(sn^{2/3},\sqrt{sdn})$
Lower bound | arbitrary | NA | minimax | $\Omega(\sqrt{sdn})$
Lower bound | exploratory | NA | minimax | $\Omega(\min(s^{1/3}n^{2/3},\sqrt{dn}))$

#### Sparse linear bandits

Abbasi-Yadkori et al. (2012) proposed an inefficient online-to-confidence-set
conversion approach that achieves an $\widetilde{O}(\sqrt{sdn})$ upper bound
for an arbitrary action set. Lattimore et al. (2015) developed a selective
explore-then-commit algorithm that only works when the action set is exactly
the binary hypercube and derived an optimal $O(s\sqrt{n})$ upper bound. Hao et
al. (2020b) introduced the notion of an exploratory action set and proved a
$\Theta(\operatorname{poly}(s)n^{2/3})$ minimax rate for the data-poor regime
using an explore-then-commit algorithm. Hao et al. (2021) extended this
concept to a MDP setting. Carpentier and Munos (2012) considered a special
case where the action set is the unit sphere and the noise is vector-valued so
that the noise becomes smaller as the dimension grows. We summarize the
comparison of existing results with our work in Table 1.

#### Sparse linear contextual bandits

It recently became popular to study the contextual setting, where the action
set changes from round to round. These results can not be reduced to our
setting since they rely on either careful assumptions on the context
distribution (Bastani and Bayati, 2020; Wang et al., 2018; Kim and Paik, 2019;
Wang et al., 2020; Ren and Zhou, 2020; Oh et al., 2020) such that classical
high-dimensional statistics can be used, or have polynomial dependency on the
number of actions (Agarwal et al., 2014; Foster and Rakhlin, 2020; Simchi-Levi
and Xu, 2020).

#### Information-directed sampling

Russo and Van Roy (2018) introduced IDS and derived Bayesian regret bounds for
multi-armed bandits, linear bandits and combinatorial bandits. Liu et al.
(2018) studied IDS for bandits with graph-feedback. Kirschner and Krause
(2018); Kirschner et al. (2020a) investigated the use of IDS for bandits with
heteroscedastic noise and partial monitoring. Kirschner et al. (2020b) proved
the asymptotic optimality of frequentist IDS for linear bandits.

#### Information-theoretic analysis

Russo and Van Roy (2014) introduced an information-theoretic analysis of
Thompson sampling (TS) and Bubeck and Sellke (2020) strengthened the result
with a first-order Bayesian regret analysis. Dong and Roy (2018); Dong et al.
(2019) extended the analysis to infinite-many actions and logistic bandits.
Lattimore and Szepesvári (2019) explored the use of information-theoretic
analysis for partial monitoring. Lu and Van Roy (2019) generalized the
analysis to reinforcement learning.

#### Bayesian sparse linear regression.

In the Bayesian framework, spike-and-slab methods are commonly used as
probabilistic tools for sparse linear regression but most of prior works focus
on variable selection and parameter estimation rather than uncertainty
quantification (Mitchell and Beauchamp, 1988; George and McCulloch, 1993;
Ročková and George, 2018). Bai et al. (2020) provided a comprehensive
overview.

##  4 Does the optimism optimally balance information and regret?

We demonstrate the necessity of balancing the trade-off between information
and regret through a simple sparse linear bandit instance. We give an example
where the optimal regret is only possible by playing actions that are known to
be sub-optimal. This phenomenon has disturbing implications for policies based
on the principle of optimism, which is that they can never be minimax optimal
in certain regime.

#### Illustrative example

Consider a problem instance where $\mathcal{A}=\mathcal{I}\cup\mathcal{U}$ is
the union of an informative action set $\mathcal{I}$ and an uninformative
action set $\mathcal{U}$:

  * •

$\mathcal{I}$ is a _subset_ of the hypercube that has three properties. First,
$|\mathcal{I}|=O(s\log(ed/s))$. Second, the last coordinate of actions in
$\mathcal{I}$ is always -1. Third, the empirical covariance of the uniform
distribution over $\mathcal{I}$ has a restricted minimum eigenvalue
(Definition A.1) at least 1/4. We prove such $\mathcal{I}$ does exist in
Appendix A.1 through a probabilistic argument.

  * •

$\mathcal{U}=\\{x\in\mathbb{R}^{d}|x_{j}\in\\{-1,0,1\\}\ \text{for}\
j\in[d-1],\|x\|_{1}=s-1,x_{d}=0\\}.$

The true parameter
$\theta^{*}=(\varepsilon,\ldots,\varepsilon,0,\ldots,0,-1),$ where
$\varepsilon>0$ is a small constant.

#### Information-regret structure

Sampling an action uniformly at random from $\mathcal{I}$ ensures the
covariance matrix is well-conditioned so that sparse learning such as Lasso
(Tibshirani, 1996) can be used for learning $\theta^{*}$ faster than ordinary
least squares. This means pulling actions from $\mathcal{I}$ provides more
information to infer $\theta^{*}$ than from $\mathcal{U}$. On the other hand,
actions from $\mathcal{I}$ lead to high regret due to the last coordinate -1.
As a consequence, Hao et al. (2020b) has proven that the minimax regret for
this problem is $\Theta(\operatorname{poly}(s)n^{2/3})$ when the horizon is
smaller than the ambient dimension.

#### Sub-optimality of optimism-based algorithms

We argue the optimism principle does not take this subtle trade-off into
consideration and yields sub-optimal regret in the data-poor regime. In
general, optimism-based algorithms choose
$A_{t}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}\rangle,$ where $\mathcal{C}_{t}\subseteq\mathbb{R}^{d}$
is a confidence set that contains the true $\theta^{*}$ with high probability.
We assume that there exists a constant $c>0$ such that
$\mathcal{C}_{t}\subseteq\\{\theta:(\widehat{\theta}_{t}-\theta)^{\top}V_{t}(\widehat{\theta}_{t}-\theta)\leq
c\sqrt{s\log(n)}\\},$ where $V_{t}=\sum_{s=1}^{t}A_{s}A_{s}^{\top}$ and
$\widehat{\theta}_{t}$ is some sparsity-aware estimator. Such confidence set
can be constructed through an online-to-confidence set conversion approach
(Abbasi-Yadkori et al., 2012). Define
$\mathfrak{R}_{\theta}(n;\pi)=\mathbb{E}[\sum_{t=1}^{n}\langle
x^{*},\theta\rangle-\sum_{t=1}^{n}Y_{t}]$ for a fixed $\theta$.

######  Claim 4.1.

Let $\pi^{\text{opt}}$ be such an optimism-based algorithm. There exists a
sparse linear bandit instance characterized by $\theta$ such that for the
data-poor regime, we have

$\mathfrak{R}_{\theta}(n;\pi^{\text{opt}})\gtrsim n/(\log(n)s\log(ed/s))\,.$

The proof is deferred to Appendix A.1. The reason is that optimism-based
algorithms do not choose actions for which they have collected enough
statistics to prove these actions are suboptimal, but in the sparse linear
setting it can be worth playing these actions when they are informative about
other actions for which the statistics are not yet so clear. This phenomenon
has been observed before in linear and structured bandits (Lattimore and
Szepesvari, 2017; Combes et al., 2017; Hao et al., 2020a).

##  5 Information-directed sampling

As shown by Hao et al. (2020b), although the explore-then-commit algorithm can
achieve the minimax optimal regret in the data-poor regime, it suffers sub-
optimal regret in the data-rich regime. This motivates us consider IDS.

###  5.1 Design principle of IDS

Unlike the optimism principle, IDS explicitly balances the amount of
information it gains about the optimal action and expected single-round regret
through minimizing a notion of information ratio. More formally, when playing
action $a$, the _information gain_ $I_{t}(x^{*};Y_{t,a})$ is the mutual
information between the optimal action and the reward the agent receives for
taking action $a$, and the expected single-round regret is
$\Delta_{t}(a):=\mathbb{E}_{t}[\langle x^{*},\theta^{*}\rangle-\langle
a,\theta^{*}\rangle]$. The information ratio is defined as

$\Psi_{t,\lambda}(\pi)=\frac{(\Delta_{t}^{\top}\pi)^{\lambda}}{I_{t}^{\top}\pi}\,,$
(5.1)

where we write $\Delta_{t}\in\mathbb{R}^{|\mathcal{A}|}$ and
$I_{t}\in\mathbb{R}^{|\mathcal{A}|}$ as corresponding vectors. Then IDS takes
the action according to
$\pi_{t}=\mathop{\mathrm{argmin}}_{\pi\in\mathcal{D}(\mathcal{A})}\Psi_{t,2}(\pi)$.

######  Remark 5.1.

The information ratio defined in Eq. (5.1) is a little more general than what
Russo and Van Roy (2018) introduced which specified $\lambda=2$. As observed
by Lattimore and György (2020), the right value of $\lambda$ depends on the
dependence of the regret on the horizon.

###  5.2 Information-theoretic Bayesian regret bound

In this section, we derive a class of Bayesian regret upper bound for sparse
IDS. We first define a notion of exploratory action set.

######  Definition 5.2 (Exploratory action set).

Let
$C_{\min}(\mathcal{A})=\max_{\mu\in\mathcal{D}(\mathcal{A})}\sigma_{\min}(\mathbb{E}_{A\sim\mu}[AA^{\top}]).$
For an action set $\mathcal{A}$, if $C_{\min}(\mathcal{A})\geq 1$, we say
$\mathcal{A}$ is exploratory.

We say that $\mathcal{A}$ has sparse optimal actions if the optimal action is
$s$-sparse almost surely with respect to the prior. One can verify the action
set of the hard instance developed in Hao et al. (2020b)111The hard instance
is almost the same as the one in illustrative example except the informative
action set is a full hypercube. is exploratory and has sparse optimal actions
since sampling uniformly from the corner of informative action set shows that
$C_{\min}(\mathcal{A})\geq 1$ and the optimal actions always come from
uninformative action set, which is sparse.

######  Theorem 5.3 (Regret bound for sparse IDS).

Suppose $\pi^{\text{IDS}}=(\pi_{t})_{t\in\mathbb{N}}$ where
$\pi_{t}=\mathop{\mathrm{argmin}}_{\pi}\Psi_{t,2}(\pi)$. Let
$\Delta=\min(\log(K),2s\log(Cdn^{1/2}/s))$ for some absolute constant $C>0$.
For an arbitrary action set, the following regret bound holds

$\mathfrak{BR}(n;\pi^{\text{IDS}})\leq\sqrt{\frac{1}{2}nd\Delta}\,.$

When $\mathcal{A}$ is exploratory and has sparse optimal actions, the
following regret bound holds

$\begin{split}\mathfrak{BR}(n;\pi^{\text{IDS}})\leq\min\left\\{\sqrt{\frac{1}{2}nd\Delta},\frac{s^{\frac{2}{3}}n^{\frac{2}{3}}\Delta^{\frac{1}{3}}}{(2C_{\min}(\mathcal{A}))^{\frac{1}{3}}}\right\\}\,.\end{split}$

This theorem shows the great adaptivity of IDS for sparse linear bandits in
the sense that a single policy adapts to different information-regret
structures. We summarize the regret bounds in a variety of of different
regimes in Table 2.

######  Remark 5.4.

The explore-then-comment algorithm proposed by Hao et al. (2020b) for sparse
linear bandits has $O(\operatorname{poly}(s)n^{2/3})$ regret bound when the
action set is exploratory and it is known that this $O(n^{2/3})$ rate is not
improvable. Thus, it is sub-optimal for data-rich regime comparing with
$\Theta(\sqrt{sdn})$ minimax rate. In contrast, IDS is nearly optimal in both
regimes.

Table 2: Summary of regret bounds of IDS for different regimes. Data-rich
regime refers to $n\gtrsim d^{3}\Delta/s^{4}$ and large $K$ refers to
$K\gtrsim d\exp(s)$.

| Arbitrary action set | Exploratory (data-rich) | Exploratory (data-poor)
---|---|---|---
Large $K$ | $O(\sqrt{nds})$ | $O(\sqrt{nds})$ | $O(sn^{2/3})$
Small $K$ | $O(\sqrt{nd\log(K)})$ | $O(\sqrt{nd\log(K)})$ | $O(s^{2/3}n^{2/3}\log^{1/3}(K))$

As a direct application of our analysis, we also include a novel Bayesian
regret bound for sparse TS.

######  Corollary 5.5 (Regret bound for sparse TS).

For an arbitrary action set, the following regret bound holds for some
absolute constant $C>0$

$\mathfrak{BR}(n;\pi^{\text{TS}})\leq\sqrt{\frac{1}{2}nd\min(\log(K),2s\log(Cdn^{1/2}/s))}\,.$

###### Proof of Theorem 5.3.

We prove our main result in three steps. All the proofs of technical lemmas
are deferred to the appendix.

#### Step 1: Generic Bayesian regret upper bound

We define $\Psi_{*,\lambda}\in\mathbb{R}$ as the _worse-case information
ratio_ such that for each $t\in[n]$,
$\Psi_{t,\lambda}(\pi_{t})\leq\Psi_{*,\lambda}$ almost surely.

######  Lemma 5.6.

Suppose $\pi^{\text{IDS}}=(\pi_{t})_{t\in\mathbb{N}}$ where
$\pi_{t}=\mathop{\mathrm{argmin}}_{\pi}\Psi_{t,2}(\pi)$. Then the following
regret bound holds

$\mathfrak{BR}(n;\pi^{\text{IDS}})\leq\inf_{\lambda\geq
2}2^{1-2/\lambda}\Psi^{1/\lambda}_{*,\lambda}I(x^{*};\mathcal{F}_{n+1})^{1/\lambda}n^{1-1/\lambda}\,,$

where $\mathcal{F}_{n+1}$ refers to the history.

This lemma demonstrates the adaptivity of a single IDS for different
information ratios. The choice of $\lambda$ essentially trades off the
information-ratio and the horizon.

#### Step 2: Bounding the worse-case information ratio

We bound the worse-case information ratio for different $\lambda$. It shows
that for certain action sets, the worse-case information ratio with
$\lambda=3$ could be much smaller than the one with $\lambda=2$.

######  Lemma 5.7.

For an arbitrary action set, we have $\Psi_{*,2}\leq d/2$. For an exploratory
action set that has sparse optimal actions, we have $\Psi_{*,3}\leq
s^{2}/(4C_{\min}(\mathcal{A})).$

The bound of $\Psi_{*,2}$ essentially follows Russo and Van Roy (2014,
Proposition 5) that bounds the information ratio of IDS by TS. And
$\Psi_{*,3}$ is bounded by the information ratio of a mixture policy
$\pi_{t}^{\text{mix}}=(1-\gamma)\pi_{t}^{\text{TS}}+\gamma\mu$ where $\mu$ is
an exploratory policy such that
$\sigma_{\min}(\mathbb{E}_{A\sim\mu}[AA^{\top}])$ is a constant and the
mixture rate $\gamma\geq 0$ is optimized to minimize the bound.

#### Step 3: Bounding the mutual information

The mutual information $I(x^{*};\mathcal{F}_{n+1})$ quantifies the cumulative
information gain about the optimal action. Russo and Van Roy (2014, 2018)
naively bound this term by entropy $H(x^{*})$, which can be arbitrarily large
or even infinite for some priors. Instead, we bound this term by the mutual
information between the true parameter and the history through data-processing
lemma.

######  Lemma 5.8.

$I(x^{*};\mathcal{F}_{n+1})\leq
I(\theta^{*};\mathcal{F}_{n+1})\leq\min\\{\log(K),2s\log(Cdn^{1/2}/s)\\}$.

Our proof is based on the metric entropy of the parameter space and square
root KL-divergence that is commonly used in information-theoretic lower bound
analysis (Yang and Barron, 1999). As a by-product of our analysis, by setting
$s=d$, our analysis recovers the $\widetilde{O}(d\sqrt{n})$ Bayesian regret
bound for TS under linear bandits with infinitely many actions without using
rate-distortion theory (Dong and Roy, 2018). Combining Lemmas 5.6-5.8 yields
our conclusion. ∎

##  6 Computational methods

In this section, we provide an efficient implementation of sparse IDS. The
main challenge is to generate posterior samples in a computationally efficient
manner to approximate the information ratio. Due to the lack of conjugate
prior, we propose an empirical Bayesian approach for sparse sampling with
spike-and-slab priors.

###  6.1 An empirical Bayesian approach for sparse sampling

In the Bayesian framework, the golden standard for modeling $\theta^{*}$ is to
place spike-and-slab priors (Mitchell and Beauchamp, 1988). With a
hierarchical structure over the parameter and model space, vanilla spike-and-
slab priors usually have the following form

$\begin{split}\rho(\theta|\bm{\gamma},\sigma^{2})=\prod_{j=1}^{d}\left[\gamma_{j}\psi_{1}(\theta_{j},\sigma)+(1-\gamma_{j})\psi_{0}(\theta_{j},\sigma)\right],\rho(\bm{\gamma}|\beta)=\prod_{j=1}^{d}\beta^{\gamma_{j}}(1-\beta)^{1-\gamma_{j}}\,,\end{split}$
(6.1)

where $\bm{\gamma}=(\gamma_{1},\ldots,\gamma_{d})^{\top}$ is an intermediate
binary vector that indexs the $2^{d}$ possible models and $\beta\in[0,1]$
denotes a priori fraction of relevant variables among all the parameters. In
particular, $\psi_{1}(\theta,\sigma)$ serves as a slab distribution to models
relevant variables and $\psi_{0}(\theta,\sigma)$ is a point mass at zero that
serves as a spike distribution to model irrelevant variables.

######  Remark 6.1.

It is typical to assume $\beta$ follows a Beta prior as
$\beta\sim\text{Beta}(a,b)$ and variance $\sigma^{2}$ follows an inverse gamma
prior $\rho(\sigma^{2})=\text{IG}(\nu/2,\nu\lambda/2)$ with $\nu=1$ and
$\lambda=1$ (Rořková and George (2014)). For simplicity, we do not impose
those additional layers of priors.

Prior specification. Although the prior in Eq. (6.1) is theoretically sound,
exploring the full posterior in high-dimensions over the entire model space
using point-mass spike-and-slab priors can be computationally prohibitive.
Therefore, the spike distribution is usually relaxed as a small-scale Gaussian
distribution (Rořková and George, 2014) or Laplace distribution (Ročková and
George, 2018). Thus, we consider a spike-and-slab Gaussian-Laplace prior that
inherits the property of the Lasso (Tibshirani, 1996) for variable selection
while the Gaussian component avoids the potential over-shrinkage effect. Each
component of the prior is specified as

$\psi_{0}(\theta,\sigma)=\frac{1}{2\sigma\lambda_{0}}\exp\left(-\frac{|\theta|}{\sigma\lambda_{0}}\right),\psi_{1}(\theta,\sigma)=\frac{1}{\sqrt{2\pi\sigma^{2}\lambda_{1}}}\exp\left(-\frac{\theta^{2}}{2\sigma^{2}\lambda_{1}}\right)\,,$

where $\lambda_{0}>0$ denotes a scaling parameter that encourages the
shrinkage of irrelevant parameters and $\lambda_{1}$ is often set to a large
value for a standard regularization (Rořková and George, 2014).

An empirical Bayesian approach. Suppose
$\mathcal{L}(\mathcal{F}_{n+1}|\theta,\sigma^{2})$ is the likelihood function
where $Z_{n}$ is the historical data. According to the Bayes rule, the full
posterior follows

$p(\theta,\bm{\gamma}|\mathcal{F}_{n+1},\sigma^{2},\beta)\propto\mathcal{L}(\mathcal{F}_{n+1}|\theta,\sigma^{2})\rho(\theta|\bm{\gamma},\sigma^{2})\rho(\bm{\gamma}|\beta)\,.$
(6.2)

To speed up the sampling, we only sample $\theta$ and optimize $\bm{\gamma}$
with respect to the posterior instead. To tackle this issue of the binary
vector $\bm{\gamma}$, we consider a continuous relaxation by introducing a
latent vector $\nu\in[0,1]^{d}$ as the probability of the variable being
included in the model. We focus on the simulations of the conditional
expectation of the complete posterior:

$\mathbb{E}_{\bm{\gamma}|\cdot}\left[\log
p(\theta,\bm{\gamma}|\mathcal{F}_{n+1},\sigma^{2},\beta)\right]=\log\mathcal{L}(\mathcal{F}_{n+1}|\theta,\sigma^{2})+\mathbb{E}_{\bm{\gamma}|\cdot}\left[\log\rho(\bm{\gamma}|\beta)+\log\rho(\theta|\bm{\gamma},\sigma^{2})\right]+C_{1}\,,$

where $C_{1}$ is the normalizing constant and
$\mathbb{E}_{\bm{\gamma}|\cdot}[\cdot]$ denotes the the conditional
expectation with respect to $\gamma$ given the current parameter $\theta$.
Then we compute

$\mathbb{E}_{\bm{\gamma}|\cdot}\left[\log\rho(\bm{\gamma}|\beta)\right]=\sum_{i=1}^{d}\mathbb{E}_{\bm{\gamma}|\cdot}\left[\gamma_{i}\log(\beta)+(1-\gamma_{i})\log(1-\beta)\right]=\sum_{i=1}^{d}\log\left(\dfrac{\beta}{1-\beta}\right)\nu_{i}+C_{2}\,,$

where $C_{2}=d\log(1-\beta)$ and
$\nu_{i}=\mathbb{E}_{\bm{\gamma}|\cdot}[\gamma_{i}]$ denotes a conditional
probability. By the Bayes rule, we have

$\nu_{i}=\mathbb{P}(\gamma_{i}=1|\theta_{i},\beta)=\frac{\rho(\theta_{i}|\gamma_{i}=1)\mathbb{P}(\gamma_{i}=1|\beta)}{\rho(\theta_{i}|\gamma_{i}=1)\mathbb{P}(\gamma_{i}=1|\beta)+\rho(\theta_{i}|\gamma_{i}=0)\mathbb{P}(\gamma_{i}=0|\beta)}\,.$
(6.3)

For the mixture prior, we optimize the variational lower bound

$\begin{split}\mathbb{E}_{\bm{\gamma}|\cdot}[\log\rho(\theta|\bm{\gamma},\sigma^{2})]\geq\sum_{j=1}^{d}-\frac{1-\nu_{j}}{\lambda_{0}}\frac{|\theta_{j}|}{\sigma}-\frac{\nu_{j}}{\lambda_{1}}\frac{\theta_{j}^{2}}{{2\sigma^{2}}}+C_{3}\,,\end{split}$

where the inequality follows by Jensen’s inequality and $C_{3}$ denotes a
trivial constant.

We summarize the full sampling procedure in Algorithm 1. Given a current
estimate of $(\theta^{(k)},\nu^{(k)})$ at step $k$ and $\mathcal{F}_{n+1}$, we
adapt an empirical Bayesian method (Deng et al., 2019) by iteratively sampling
$\theta$ based on the negative log-posterior with adaptive priors

$Q(\theta|\theta^{(k)},\nu^{(k)},\mathcal{F}_{n+1})=-\log\mathcal{L}(\mathcal{F}_{n+1}|\theta,\sigma^{2})+\sum_{i=1}^{d}\left(\frac{1-\rho_{i}}{\lambda_{0}}\frac{|\theta_{i}|}{\sigma}+\frac{\rho_{i}}{\lambda_{1}}\frac{\theta_{i}^{2}}{{2\sigma^{2}}}\right)\,,$

and optimizing the conditional probability $\nu$ through stochastic
approximation algorithms (Robbins and Monro (1951)) until the equilibrium is
achieved.

Algorithm 1 Empirical Bayesian sparse sampling

1: Input: dataset $\mathcal{F}_{n+1}$, learning rate $(\eta_{k})$, step size
$(\omega_{k})$, a priori knowledge of $\sigma^{2}$ and $\beta$, thinning
factor $T$, number of posterior samples $M$, regularization parameters
$\lambda_{0}$, $\lambda_{1}$.

2: Initialize: $\theta^{(0)}\sim N(0,0.1I_{d})$ and
$\nu^{(0)}=(0.5,\ldots,0.5)^{\top}$.

3: for $k\geq 1$ do

4: Sampling step:
$\theta^{(k+1)}=\theta^{(k)}-\eta_{k}\frac{\partial}{\partial\theta}Q(\theta|\theta^{(k)},\nu^{(k)},\mathcal{F}_{n+1})+\sqrt{2\eta_{k}}\xi^{(k)},$
where $\xi^{(k)}$ is a standard Gaussian random vector.

5: Stochastic approximation step:
$\nu^{(k+1)}=(1-\omega_{k})\nu^{(k)}+\omega_{k}\nu,$ where $\nu$ is derived
from Eq. (6.3).

6: end for

7: Output: $M$ posterior samples
$\theta^{(T)},\theta^{(2T)},\ldots,\theta^{(MT)}$.

###  6.2 Optimize the information ratio

For sparse linear bandits, it is expensive to estimate and optimize the
original information ratio that involves the calculation of KL-divergence.
Following Section 6.3 in Russo and Van Roy (2018), we optimize a variance-
based information ratio instead:
$\pi_{t}=\mathop{\mathrm{argmin}}_{\pi}(\Delta_{t}^{\top}\pi)^{2}/(2v_{t}^{\top}\pi),$
where we define
$v_{t}(a)=\mathbb{E}_{t}[a^{\top}\mathbb{E}_{t}[\theta^{*}|x^{*}]-a^{\top}\mathbb{E}_{t}[\theta^{*}]]^{2}$
for each $a\in\mathcal{A}$. With sufficient number of posterior samples of
$\theta^{*}$ produced by Algorithm 1, we can accurately estimate
$\mathbb{E}_{t}[\theta^{*}|x^{*}],\mathbb{E}_{t}[\theta^{*}]$ and the
information ratio. The detailed procedure is deferred to Appendix B. For the
optimization step, we simply choose the action who can has the minimum per-
action variance-based information ratio to accelerate the computation. The
overall algorithm can be found in Algorithm 2.

Algorithm 2 Sparse IDS

1: Input: time horizon $n$, action set $\mathcal{A}$, number of posterior
samples per round $M$.

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

3: Obtain $M$ posterior samples $\theta^{1},\ldots,\theta^{M}$ by Algorithm 1.

4: Calculate $\widehat{\Delta}_{t}\in\mathbb{R}^{|\mathcal{A}|}$ and
$\widehat{v}_{t}\in\mathbb{R}^{|\mathcal{A}|}$ using Algorithm 3 in Appendix
B.

5: Take the action
$A_{t}=\mathop{\mathrm{argmin}}_{a\in\mathcal{A}}\widehat{\Delta}_{t}^{2}(a)/\widehat{v}_{t}(a)$
and receive a reward: $Y_{t}=\langle A_{t},\theta^{*}\rangle+\eta_{t}.$

6: end for

##  7 Experiments

Figure 1: Posterior distributions for the first three coordinates. The red
lines are posterior means.

First, we evaluate the performance of the empirical Bayesian sparse sampling
procedure for generating posterior samples through an offline sparse linear
regression. We set $d=10,s=3,n=100$ and the actions are drawn i.i.d from a
multivariate normal distribution $N(0,\Sigma)$ with $\Sigma_{ij}=0.6^{|i-j|}$.
The true parameter is $\theta^{*}=(3,2,0,0,\ldots,0)\in\mathbb{R}^{10}$. We
plot the empirical posterior distributions as well as their posterior mean for
the first three covariates in Figure 1. It shows that the posterior
distribution concentrates well around the true value and the algorithm
identifies the sparse pattern quickly.

Second, we evaluate sparse IDS with several other competitors. In particular,
we compare with LinUCB (Abbasi-Yadkori et al., 2011), LinTS with Gaussian
prior (Agrawal and Goyal, 2013), IDS for linear bandits (Algorithm 6 in Russo
and Van Roy (2018)) and ESTC (Hao et al., 2020b). Note that the first three
algorithms are not sparsity-aware. Our sparse sampling procedure naturally
induces a sparse TS algorithm so we include it into comparison.

#### Setting

All the true parameters are randomly generated from a multivariate normal
distribution, truncated to be sparse and normalized to have square norm 1. The
noise variance is fixed to be 2 and we replicate the experiments over 200
trials. We plot the empirical cumulative Bayesian regret. Each Bayesian
algorithm will take 10000 posterior samples. We use the TS without blow-up
factor for the variance and tune the length of confidence interval of LinUCB
over a candidate set.

#### Hard sparse linear bandits instance

Consider the hard problem instance introduced in Section 4 that includes
informative and uninformative action sets and set $d=10,s=2$. For each trial,
we record the number of pulls of sparse TS and sparse IDS for informative
actions. We draw the histogram of number of pulls during 200 trial in Figure
2. It is clear that IDS tends to invest more on the informative action sets
but suffer less regret than TS if there exists an information-regret trade-off
phenomenon.

Figure 2: The left panel is the cumulative regret and the right panel is the
histogram of number of pulls for informative actions. It’s clear that sparse
TS does not value information enough as it should.

#### Multivariate Gaussian action set

We consider a more general case where each action is generated from
multivariate normal distribution $N(0,\Sigma)$ with $\Sigma_{ij}=0.6^{|i-j|}$.
The number of actions $K$ is fixed to be 200 and the level of sparsity $s/d$
is fixed to be 0.1. We report the results in Figure 3 for $d=20,40,100$. It is
obvious that sparse IDS consistently outperforms other algorithms and the
improvement increases as the feature dimension increases. ESTC performs better
than non sparsity-aware algorithms in the data-poor regime but perform poorly
for the data-rich horizon.

Figure 3: Cumulative regret for $d=20,40,100$.

##  8 Conclusion

In this work, we investigate the theoretic and practical applicability of
information-directed sampling for sparse linear bandits. An interesting future
direction is to extend similar ideas to sparse linear contextual bandits.

## References

  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , pages 2312–2320, 2011.
  * Abbasi-Yadkori et al. [2012] Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari.  Online-to-confidence-set conversions and application to sparse stochastic bandits.  In _Artificial Intelligence and Statistics_ , pages 1–9, 2012.
  * Agarwal et al. [2014] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire.  Taming the monster: A fast and simple algorithm for contextual bandits.  In _International Conference on Machine Learning_ , pages 1638–1646. PMLR, 2014.
  * Agrawal and Goyal [2013] Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In _International Conference on Machine Learning_ , pages 127–135. PMLR, 2013.
  * Auer [2002] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Bai et al. [2020] Ray Bai, Veronika Rockova, and Edward I George.  Spike-and-slab meets lasso: A review of the spike-and-slab lasso.  _arXiv preprint arXiv:2010.06451_ , 2020.
  * Bastani and Bayati [2020] Hamsa Bastani and Mohsen Bayati.  Online decision making with high-dimensional covariates.  _Operations Research_ , 68(1):276–294, 2020.
  * Bubeck and Sellke [2020] Sébastien Bubeck and Mark Sellke.  First-order bayesian regret analysis of thompson sampling.  In _Algorithmic Learning Theory_ , pages 196–233. PMLR, 2020.
  * Carpentier and Munos [2012] Alexandra Carpentier and Rémi Munos.  Bandit theory meets compressed sensing for high dimensional stochastic linear bandit.  In _Artificial Intelligence and Statistics_ , pages 190–198, 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, 2011.
  * Combes et al. [2017] Richard Combes, Stefan Magureanu, and Alexandre Proutiere.  Minimal exploration in structured stochastic bandits.  In _Advances in Neural Information Processing Systems_ , pages 1763–1771, 2017.
  * Dani et al. [2008] Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * Deng et al. [2019] Wei Deng, Xiao Zhang, Faming Liang, and Guang Lin.  An adaptive empirical bayesian method for sparse deep learning.  _Advances in neural information processing systems_ , 2019:5563, 2019.
  * Dong and Roy [2018] Shi Dong and Benjamin Van Roy.  An information-theoretic analysis for thompson sampling with many actions.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 4161–4169, 2018.
  * Dong et al. [2019] Shi Dong, Tengyu Ma, and Benjamin Van Roy.  On the performance of thompson sampling on logistic bandits.  In _Conference on Learning Theory_ , pages 1158–1160. PMLR, 2019\.
  * Foster and Rakhlin [2020] Dylan Foster and Alexander Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 3199–3210. PMLR, 2020.
  * George and McCulloch [1993] Edward I George and Robert E McCulloch.  Variable selection via gibbs sampling.  _Journal of the American Statistical Association_ , 88(423):881–889, 1993.
  * Hao et al. [2020a] Botao Hao, Tor Lattimore, and Csaba Szepesvari.  Adaptive exploration in linear contextual bandit.  _AISTATS_ , 2020a.
  * Hao et al. [2020b] Botao Hao, Tor Lattimore, and Mengdi Wang.  High-dimensional sparse linear bandits.  _Advances in Neural Information Processing Systems_ , 33, 2020b.
  * Hao et al. [2021] Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang.  Online sparse reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 316–324. PMLR, 2021.
  * Javanmard and Montanari [2014] Adel Javanmard and Andrea Montanari.  Confidence intervals and hypothesis testing for high-dimensional regression.  _The Journal of Machine Learning Research_ , 15(1):2869–2909, 2014.
  * Kim and Paik [2019] Gi-Soo Kim and Myunghee Cho Paik.  Doubly-robust lasso bandit.  In _Advances in Neural Information Processing Systems_ , pages 5869–5879, 2019.
  * Kirschner and Krause [2018] Johannes Kirschner and Andreas Krause.  Information directed sampling and bandits with heteroscedastic noise.  In _Conference On Learning Theory_ , pages 358–384. PMLR, 2018.
  * Kirschner et al. [2020a] Johannes Kirschner, Tor Lattimore, and Andreas Krause.  Information directed sampling for linear partial monitoring.  In _Conference on Learning Theory_ , pages 2328–2369. PMLR, 2020a.
  * Kirschner et al. [2020b] Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári.  Asymptotically optimal information-directed sampling.  _arXiv preprint arXiv:2011.05944_ , 2020b.
  * Lattimore and György [2020] Tor Lattimore and András György.  Mirror descent and the information ratio.  _arXiv preprint arXiv:2009.12228_ , 2020.
  * Lattimore and Szepesvari [2017] Tor Lattimore and Csaba Szepesvari.  The end of optimism? an asymptotic analysis of finite-armed linear bandits.  In _Artificial Intelligence and Statistics_ , pages 728–737, 2017\.
  * Lattimore and Szepesvári [2019] Tor Lattimore and Csaba Szepesvári.  An information-theoretic approach to minimax regret in partial monitoring.  In _Conference on Learning Theory_ , pages 2111–2139. PMLR, 2019\.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lattimore et al. [2015] Tor Lattimore, Koby Crammer, and Csaba Szepesvári.  Linear multi-resource allocation with semi-bandit feedback.  In _Advances in Neural Information Processing Systems_ , pages 964–972, 2015.
  * Liu et al. [2018] Fang Liu, Swapna Buccapatnam, and Ness Shroff.  Information directed sampling for stochastic bandits with graph feedback.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Lu and Van Roy [2019] Xiuyuan Lu and Benjamin Van Roy.  Information-theoretic confidence bounds for reinforcement learning.  _arXiv preprint arXiv:1911.09724_ , 2019.
  * Mitchell and Beauchamp [1988] T. J. Mitchell and J. J. Beauchamp.  Bayesian Variable Selection in Linear Regression.  _Journal of the American Statistical Association_ , 83(404):1023–1032, 1988.
  * Oh et al. [2020] Min-hwan Oh, Garud Iyengar, and Assaf Zeevi.  Sparsity-agnostic lasso bandit.  _arXiv preprint arXiv:2007.08477_ , 2020.
  * Ren and Zhou [2020] Zhimei Ren and Zhengyuan Zhou.  Dynamic batch learning in high-dimensional sparse linear contextual bandits.  _arXiv preprint arXiv:2008.11918_ , 2020.
  * Robbins and Monro [1951] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  _Annals of Mathematical Statistics_ , 22:400–407, 1951\.
  * Ročková and George [2018] Veronika Ročková and Edward I George.  The spike-and-slab lasso.  _Journal of the American Statistical Association_ , 113(521):431–444, 2018.
  * Rořková and George [2014] Veronika Rořková and Edward I. George.  EMVS: The EM Approach to Bayesian variable selection.  _Journal of the American Statistical Association_ , 109(506):828–846, 2014.
  * Rudelson and Zhou [2013] Mark Rudelson and Shuheng Zhou.  Reconstruction from anisotropic random measurements.  _IEEE Transactions on Information Theory_ , 59(6):3434–3447, 2013.
  * Rusmevichientong and Tsitsiklis [2010] Paat Rusmevichientong and John N Tsitsiklis.  Linearly parameterized bandits.  _Mathematics of Operations Research_ , 35(2):395–411, 2010.
  * Russo and Van Roy [2014] Daniel Russo and Benjamin Van Roy.  Learning to optimize via posterior sampling.  _Mathematics of Operations Research_ , 39(4):1221–1243, 2014.
  * Russo and Van Roy [2018] Daniel Russo and Benjamin Van Roy.  Learning to optimize via information-directed sampling.  _Operations Research_ , 66(1):230–252, 2018.
  * Simchi-Levi and Xu [2020] David Simchi-Levi and Yunzong Xu.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  _Available at SSRN_ , 2020.
  * Tibshirani [1996] R. Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society, Series B_ , 58:267–288, 1996.
  * Vershynin [2009] Roman Vershynin.  On the role of sparsity in compressed sensing and random matrix theory.  In _2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_ , pages 189–192. IEEE, 2009\.
  * Wang et al. [2018] Xue Wang, Mingcheng Wei, and Tao Yao.  Minimax concave penalized multi-armed bandit model with high-dimensional covariates.  In _International Conference on Machine Learning_ , pages 5200–5208, 2018.
  * Wang et al. [2020] Yining Wang, Yi Chen, Ethan X Fang, Zhaoran Wang, and Runze Li.  Nearly dimension-independent sparse linear bandit over small action spaces via best subset selection.  _arXiv preprint arXiv:2009.02003_ , 2020.
  * Yang and Barron [1999] Yuhong Yang and Andrew Barron.  Information-theoretic determination of minimax rates of convergence.  _Annals of Statistics_ , pages 1564–1599, 1999.

##  Appendix A Proofs

###  A.1 Proof of Claim 4.1

We first define the notion of restricted minimum eigenvalue.

######  Definition A.1 (Restricted minimum eigenvalue).

Given a symmetric matrix $H\in\mathbb{R}^{d\times d}$ and integer $s\geq 1$,
and $L>0$, the restricted minimum eigenvalue of $H$ is defined as

$\phi^{2}(H,s,L):=\min_{{\mathcal{S}}\subset[d],|{\mathcal{S}}|\leq
s}\min_{\theta\in\mathbb{R}^{d}}\Big{\\{}\frac{\langle\theta,H\theta\rangle}{\|\theta_{{\mathcal{S}}}\|_{2}^{2}}:\theta\in\mathbb{R}^{d},\|\theta_{{\mathcal{S}}^{c}}\|_{1}\leq
L\|\theta_{{\mathcal{S}}}\|_{1}\Big{\\}}.$

Suppose $\\{x^{(t)}\\}_{t=1}^{k}\subseteq\mathbb{R}^{d}$ are $k$ independent
random vectors who first $d-1$ coordinates are drawn uniformly from
$\\{-1,1\\}$ and the last coordinate is 1. Denote
$\widehat{\Sigma}=\sum_{t=1}^{k}x^{(t)}x^{(t)\top}$. It is easy to see
$\mathbb{E}[\widehat{\Sigma}]=I_{d}$ and
$\sigma_{\min}(\mathbb{E}[\widehat{\Sigma}])=1$. From the definition of
restricted minimum eigenvalue, we have for any $L>0$,

$\phi^{2}(\mathbb{E}[\widehat{\Sigma}],s,L)\geq\sigma_{\min}^{2}(\mathbb{E}[\widehat{\Sigma}])=1.$

According to Theorem 10 in Javanmard and Montanari [2014] (essentially from
Theorem 6 in Rudelson and Zhou [2013]), if the population covariance matrix
satisfies the restricted eigenvalue condition, the empirical covariance matrix
satisfies it as well with high probability. Specifically, when
$k=C_{1}s\log(ed/s)$ for some large constant $C_{1}>0$, the following holds:

$\mathbb{P}\left(\phi^{2}(\widehat{\Sigma},s,3)\geq\frac{1}{4}\right)\geq
1-2\exp(-k/C_{1})\geq 0.5.$

According to probabilistic argument, there exists a set of fixed actions
$\\{x^{(1)},\ldots,x^{(k)}\\}$ with $k=C_{1}s\log(ed/s)$ such that if we pull
uniformly at random from them, the restricted minimum eigenvalue of the
resulting covariance matrix is at least 1/4.

Next we compute how many rounds at most the optimism-based algorithm will
choose from informative action set $\mathcal{I}$. Let $N_{t-1}(a)$ as the
number of pulls for action $a$ until round $t$. Since we have
$\theta^{*}\in\mathcal{C}_{t}$ with high probability, then

$\max_{a\in\mathcal{U}}\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}\rangle\geq\max_{a\in\mathcal{U}}\langle
a,\theta^{*}\rangle\geq s\varepsilon.$

On the other hand for any action $a\in\mathcal{I}$,

$\begin{split}\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}\rangle&=\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}-\theta^{*}\rangle+\langle
a,\theta^{*}\rangle\leq\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}-\theta^{*}\rangle+\max_{a\in\mathcal{I}}\langle
a,\theta^{*}\rangle\\\ &=\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}-\theta^{*}\rangle+s\varepsilon-1\leq
2c\sqrt{\|a\|_{V_{t}^{-1}}s\log(n)}+s\varepsilon-1\\\ &\leq
2c\sqrt{\frac{s\log(n)}{N_{t-1}(a)}}+s\varepsilon-1.\end{split}$

If $N_{t-1}(a)>4c^{2}s\log(n)$ for $a\in\mathcal{I}$, then we have
$\max_{\widetilde{\theta}\in\mathcal{C}_{t}}\langle
a,\widetilde{\theta}\rangle<s\varepsilon$. Based on the optimism principle,
the algorithm will switch to pull uninformative actions. This leads to the
fact that optimism-based algorithm will pull at most
$|\mathcal{I}|4c^{2}s\log(n)$ rounds of information actions. According to the
proof of minimax lower bound in Hao et al. [2020b], we have when
$\sum_{a\in\mathcal{I}}N_{n}(a)<1/(s\varepsilon^{2})$, there exists another
sparse parameter $\theta^{\prime}$ such that

$R_{\theta}(n)+R_{\theta^{\prime}}(n)\gtrsim
ns\varepsilon\exp\left(-\frac{2n\varepsilon^{2}s^{2}}{d}\right)\,.$ (A.1)

By choosing $\varepsilon=\sqrt{1/(s^{2}\log(n)4c^{2}|\mathcal{I}|)}$, we have
for $d\geq n/(s\log(n)\log(ed/s))$

$R_{\theta}(n)+R_{\theta^{\prime}}(n)\gtrsim\frac{n}{\sqrt{\log(n)}|\mathcal{I}|}\,.$
(A.2)

Note that $|\mathcal{I}|=O(s\log(d/s))$ as we proved before. Then we can argue
there exists a sparse linear bandit instance such that optimism-based
algorithm will suffer linear regret for a data-poor regime. This ends the
proof.

###  A.2 Proof of Lemma 5.6

We decompose the Bayesian regret in terms of the instantaneous regret:

$\begin{split}\mathfrak{BR}(n;\pi^{\text{IDS}})&=\mathbb{E}\left[\sum_{t=1}^{n}\langle
x^{*},\theta\rangle-\sum_{t=1}^{n}Y_{t}\right]=\mathbb{E}\left[\sum_{t=1}^{n}\mathbb{E}_{t}\left[\langle
x^{*},\theta^{*}\rangle-Y_{t}\right]\right]\\\
&=\mathbb{E}\left[\sum_{t=1}^{n}\sum_{a}\mathbb{E}_{t}\left[\langle
x^{*},\theta^{*}\rangle-\langle
a,\theta^{*}\rangle\right]\pi_{t}(a)\right]=\mathbb{E}\left[\sum_{t=1}^{n}\langle\pi_{t},\Delta_{t}\rangle\right],\end{split}$
(A.3)

where the third equation is due to the zero mean of the noise.

We then bound one-step instantaneous regret. From the definition of $\pi_{t}$,
we have

$\pi_{t}=\mathop{\mathrm{argmin}}_{\pi\in\mathcal{D}(\mathcal{A})}\frac{\langle\pi,\Delta_{t}\rangle^{2}}{\langle\pi,I_{t}\rangle}.$
(A.4)

In addition, we denote

$q_{\lambda,t}=\mathop{\mathrm{argmin}}_{\pi\in\mathcal{D}(\mathcal{A})}\Psi_{t,\lambda}(\pi)=\mathop{\mathrm{argmin}}_{\pi\in\mathcal{D}(\mathcal{A})}\frac{\langle\pi,\Delta_{t}\rangle^{\lambda}}{\langle\pi,I_{t}\rangle}.$
(A.5)

Note that

$\nabla_{\pi}\Psi_{t,2}(\pi)=\frac{2\langle\pi,\Delta_{t}\rangle\Delta_{t}}{\langle\pi,I_{t}\rangle}+\frac{\langle\pi,\Delta_{t}\rangle^{2}I_{t}}{\langle\pi,I_{t}\rangle^{2}}.$

By the first-order optimality condition in Lemma C.1,

$0\leq\left\langle\nabla_{\pi}\Psi_{t,2}(\pi_{t}),q_{\lambda,t}-\pi_{t}\right\rangle=\frac{2\langle
q_{\lambda,t}-\pi_{t},\Delta_{t}\rangle\langle\pi_{t},\Delta_{t}\rangle}{\langle\pi_{t},I_{t}\rangle}-\frac{\langle
q_{\lambda,t}-\pi_{t},I_{t}\rangle\langle\pi_{t},\Delta_{t}\rangle^{2}}{\langle\pi_{t},I_{t}\rangle^{2}}.$

This further implies

$2\langle
q_{\lambda,t},\Delta_{t}\rangle\geq\langle\pi_{t},\Delta_{t}\rangle\Big{(}1+\frac{\langle
q_{\lambda,t},I_{t}\rangle}{\langle\pi_{t},I_{t}\rangle}\Big{)}\geq\langle\pi_{t},\Delta_{t}\rangle.$

Based on the above equation, we can bound the generalized information ratio as
follows:

$\begin{split}\frac{\langle\pi_{t},\Delta_{t}\rangle^{\lambda}}{\langle\pi_{t},I_{t}\rangle}&=\frac{\langle\pi_{t},\Delta_{t}\rangle^{2}\langle\pi_{t},\Delta_{t}\rangle^{\lambda-2}}{\langle\pi_{t},I_{t}\rangle}\leq\frac{2^{\lambda-2}\langle\pi_{t},\Delta_{t}\rangle^{2}\langle
q_{\lambda,t},\Delta_{t}\rangle^{\lambda-2}}{\langle\pi_{t},I_{t}\rangle}\\\
&\leq\frac{2^{\lambda-2}\langle
q_{\lambda,t},\Delta_{t}\rangle^{\lambda-2}\langle
q_{\lambda,t},\Delta_{t}\rangle^{2}}{\langle
q_{\lambda,t},I_{t}\rangle}=2^{\lambda-2}\min_{\pi\in\mathcal{D}(\mathcal{A})}\frac{\langle\pi,\Delta_{t}\rangle^{\lambda}}{\langle\pi,I_{t}\rangle},\end{split}$

where the first inequality is from Eq. (A.4) and the second inequality is from
Eq. (A.5). According to the definition of $\Psi_{*,\lambda}$, we have

$\langle\pi_{t},\Delta_{t}\rangle\leq
2^{1-2/\lambda}\langle\pi_{t},I_{t}\rangle^{1/\lambda}\Psi_{*,\lambda}^{1/\lambda}.$

Next we prove $\langle\pi_{t},I_{t}\rangle=I_{t}(x^{*};(A_{t},Y_{t}))$. By the
chain rule of mutual information,

$\begin{split}I_{t}(x^{*};(A_{t},Y_{t}))&=I_{t}(x^{*};A_{t})+I_{t}(x^{*};Y_{t}|A_{t})=I_{t}(x^{*};Y_{t}|A_{t})\\\
&=\sum_{a\in\mathcal{A}}\pi_{t}(a)I_{t}(x^{*};Y_{t}|A_{t}=a),\end{split}$

where we use the fact that $A_{t}$ and $x^{*}$ are independent. If $Z$ is
independent of $X$ and $Y$, then we have $I(X;Y|Z)=I(X;Y)$. Since $A_{t}$ is
independent of $x^{*}$ and $Y_{t}$ conditional on $\mathcal{F}_{t}$, then

$\sum_{a\in\mathcal{A}}\pi_{t}(a)I_{t}(x^{*};Y_{t}|A_{t}=a)=\sum_{a\in\mathcal{A}}\pi_{t}(a)I_{t}(x^{*};Y_{t,a})=\langle\pi_{t},I_{t}\rangle.$

This proves the previous claim. Combining with Eq. (A.3),

$\begin{split}\mathfrak{BR}(n;\pi^{\text{IDS}})&=\mathbb{E}\left[\sum_{t=1}^{n}\langle\pi_{t},\Delta_{t}\rangle\right]\leq\mathbb{E}\left[\sum_{t=1}^{n}2^{1-2/\lambda}I_{t}(x^{*};(A_{t},Y_{t}))^{1/\lambda}\Psi_{*,\lambda}^{1/\lambda}\right]\\\
&=2^{1-2/\lambda}\Psi_{*,\lambda}^{1/\lambda}\mathbb{E}\left[\sum_{t=1}^{n}I_{t}(x^{*};(A_{t},Y_{t}))^{1/\lambda}\right]\\\
&\leq
2^{1-2/\lambda}\Psi_{*,\lambda}^{1/\lambda}n^{1-1/\lambda}\mathbb{E}\left[\sum_{t=1}^{n}I_{t}(x^{*};(A_{t},Y_{t}))\right]^{1/\lambda},\end{split}$
(A.6)

where the last inequality is from Holder’s inequality with
$p=\lambda/(\lambda-1)$ and $q=\lambda$.

In the end, we bound the cumulative information gain using the chain rule of
mutual information,

$\begin{split}&\sum_{t=1}^{n}\mathbb{E}[I_{t}(x^{*};(A_{t},Y_{t}))]=\sum_{t=1}^{n}I(x^{*};(A_{t},Y_{t})|\mathcal{F}_{t})=I(x^{*};\mathcal{F}_{n+1}).\end{split}$

Combining with Eq. (A.6), we have

$\mathfrak{BR}_{n}(\pi,\rho)\leq
2^{1-2/\lambda}(\Psi_{*,\lambda}I(x^{*};\mathcal{F}_{n+1}))^{1/\lambda}n^{1-1/\lambda}.$

This ends the proof.

###  A.3 Proof of Lemma 5.8

Denote $Z_{1}=(A_{1},Y_{1}),\ldots,Z_{n}=(A_{n},Y_{n})$ such that
$Z^{n}=(Z_{1},\ldots,Z_{n})$. When the number of actions $K$ is small, we
could directly bound it by

$I(x^{*};Z^{n})=H(x^{*})-H(x^{*}|Z^{n})\leq
H(x^{*})\leq\log|\mathcal{A}|=\log(K),$

where for the first inequality we use the non-negativity of Shannon entropy.

When the number of actions is large or infinite, we will bound it through the
following information-theoretic argument. Recall that
$x^{*}=\mathop{\mathrm{argmin}}_{a\in\mathcal{A}}x^{\top}\theta^{*}$ so
$x^{*}$ can be viewed as a deterministic function $\theta^{*}$. By the data
processing lemma (Lemma C.2), we have $I(x^{*};Z^{n})\leq
I(\theta^{*};Z^{n})$. In other words, we bound the information gain regarding
the optimal action by the information gain regarding the true parameter.

Recall that we assume the prior distribution of $\theta^{*}$ is
$\rho(\theta^{*})$ that takes the value in $\Theta$. From Vershynin [2009] ,
we know $\Theta$ enjoys an $\varepsilon$-net $\mathcal{N}_{\varepsilon}$ under
$\ell_{2}$-norm and its cardinality at most $(Cd/s\varepsilon)^{s}$ where $C$
is a constant. Hence, its metric entropy satisfies

$\log|\mathcal{N}_{\varepsilon}|\leq s\log(Cd/s\varepsilon).$ (A.7)

Suppose the Bayes mixture density
$p_{\rho}(z^{n})=\int_{\theta\in\Theta}p(z^{n}|\theta)d\rho(\theta)$.
According to the definition of mutual information,

$\begin{split}I(\theta^{*};Z^{n})&=\mathbb{E}_{\theta^{*}}\left[D_{\mathrm{KL}}(\mathbb{P}_{Z^{n}|\theta^{*}}||\mathbb{P}_{Z^{n}})\right]\\\
&=\int_{\theta^{*}\in\Theta}\int
p(z^{n}|\theta^{*})\log\Big{(}\frac{p(z^{n}|\theta^{*})}{p_{w}(z^{n})}\Big{)}\mu(dz^{n})d\rho(\theta^{*})\\\
&\leq\int_{\theta\in\Theta}\int
p(z^{n}|\theta^{*})\log\Big{(}\frac{p(z^{n}|\theta^{*})}{q(z^{n})}\Big{)}\mu(dz^{n})d\rho(\theta^{*})\\\
&=\int_{\theta\in\Theta}D_{\mathrm{KL}}(\mathbb{P}_{Z^{n}|\theta^{*}}||\mathbb{Q}_{Z^{n}})d\rho(\theta^{*}).\end{split}$
(A.8)

where the inequality is due to the fact that Bayes mixture density
$p_{\rho}(z^{n})$ minimizes the average KL divergences over any choice of
densities $q(z^{n})$. Then we choose ${\rho}_{1}$ as an uniform distribution
over $\mathcal{N}_{\varepsilon}$ such that
$q(z^{n})=p_{\rho_{1}}(z^{n})=\int_{\theta\in\Theta}p(z^{n}|\theta)d\rho_{1}(\theta)$
and we denote $\mathbb{Q}_{Z^{n}}$ as the corresponding probability measure.
Since $\mathcal{N}_{\varepsilon}$ is an $\varepsilon$-net over $\Theta$ under
$\ell_{2}$-norm, for each $\theta\in\Theta$, there exists
$\widetilde{\theta}\in\Theta$ such that
$\|\theta-\widetilde{\theta}\|_{2}\leq\varepsilon$.

To bound the KL-divergence term, we follow

$\begin{split}D_{\mathrm{KL}}(\mathbb{P}_{Z^{n}|\theta}||\mathbb{Q}_{Z^{n}})&=\mathbb{E}\left[\log\frac{p(z^{n}|\theta^{*})}{(1/|\mathcal{N}_{\varepsilon}|)\sum_{\widetilde{\theta}\in\mathcal{N}_{\varepsilon}}p(z^{n}|\widetilde{\theta})}\right]\\\
&\leq\mathbb{E}\left[\log\frac{p(z^{n}|\theta^{*})}{(1/|\mathcal{N}_{\varepsilon}|)p(z^{n}|\widetilde{\theta})}\right]\\\
&\leq\log|\mathcal{N}_{\varepsilon}|+D_{\mathrm{KL}}(\mathbb{P}_{Z^{n}|\theta}||\mathbb{P}_{Z^{n}|\widetilde{\theta}}).\end{split}$
(A.9)

By the chain rule of KL-divergence,

$D_{\mathrm{KL}}(P_{Z^{n}|\theta}||\mathbb{P}_{Z^{n}|\widetilde{\theta}})\leq\mathbb{E}\left[\sum_{t=1}^{n}D_{\mathrm{KL}}(\mathbb{P}_{Y_{t}|A_{t},Z^{t-1},\theta^{*}}||\mathbb{P}_{Y_{t}|A_{t},Z^{t-1},\widetilde{\theta}})\right],$

where we define $Z^{0}=\emptyset$. Under linear model Eq.
(LABEL:def:sparse_linear) and bandit $\theta$, we know $Y_{t}\sim
N(A_{t}^{\top}\theta,1)$. A straightforward computation leads to

$\begin{split}D_{\mathrm{KL}}(\mathbb{P}_{Y_{t}|A_{t},Z^{t-1},\theta^{*}}||\mathbb{P}_{Y_{t}|A_{t},Z^{t-1},\widetilde{\theta}})&=\frac{1}{2\sigma^{2}}\|A_{t}^{\top}\theta^{*}-A_{t}^{\top}\widetilde{\theta}\|_{2}^{2}\\\
&\leq\frac{1}{2\sigma^{2}}\|A_{t}\|_{\infty}^{2}\|\theta^{*}-\widetilde{\theta}\|_{1}^{2}\\\
&\leq\frac{1}{2\sigma^{2}}s\|\theta^{*}-\widetilde{\theta}\|_{2}^{2}\\\
&\leq\frac{s}{2\sigma^{2}}\varepsilon^{2},\end{split}$ (A.10)

where the first inequality we use the fact that $\|a\|_{\infty}\leq 1$ and the
parameters are sparse. Here actually we only require $\|a\|_{\infty}$ for
$a\in\mathcal{A}$ being bounded by a constant since evetually it will only
appears inside the logarithm term. Putting Eqs. (A.7)-(A.10) together, we have

$I(\theta^{*};Z^{n})\leq\int_{\theta^{*}\in\Theta}\Big{(}s\log(Cd/s\varepsilon)+\frac{ns}{2\sigma^{2}}\varepsilon^{2}\Big{)}d\theta^{*}=s\log(Cd/s\varepsilon)+\frac{ns}{2\sigma^{2}}\varepsilon^{2}.$

With the choice of $\varepsilon=1/\sqrt{n}$, we finally have

$I(\theta^{*};Z^{n})\leq 2s\log(Cdn^{1/2}/s).$

This ends the proof.

###  A.4 Proof of Lemma 5.7

For any particular policy $\widetilde{\pi}$, if one can derive an worse-case
bound of $\Psi_{t,\lambda}(\widetilde{\pi})$, we get an upper bound for
$\Psi_{*,\lambda}$ automatically. The remaining step is to choose proper
policy $\widetilde{\pi}$.

First, we bound the information ratio with $\lambda=2$ that essentially
follows Proposition 5 in Russo and Van Roy [2014] and Lemma 3 in Russo and Van
Roy [2014] for a Gaussian noise. By the definition of mutual information, for
any $a\in\mathcal{A}$, we have

$\begin{split}I_{t}(x^{*};Y_{t,a})&=D_{\mathrm{KL}}\left(\mathbb{P}_{t}((x^{*},Y_{t,a}))||\mathbb{P}_{t}(x^{*}\in\cdot)\mathbb{P}_{t}\big{(}Y_{t,a}\in\big{)}\right)\\\
&=\sum_{a^{*}\in\mathcal{A}}\mathbb{P}_{t}(x^{*}=a^{*})D_{\mathrm{KL}}\left(\mathbb{P}_{t}(Y_{t,a}=\cdot|x^{*}=a^{*})||\mathbb{P}_{t}(Y_{t,a}=\cdot)\right).\end{split}$
(A.11)

Define $R_{\max}$ as the upper bound of maximum expected reward. It is easy to
see $Y_{t,a}$ is a $\sqrt{R_{\max}^{2}+1}$ sub-Gaussian random variable.
According to Lemma 3 in Russo and Van Roy [2014], we have

$I_{t}(x^{*};Y_{t,a})\geq\frac{2}{R_{\max}^{2}+1}\sum_{a^{*}\in\mathcal{A}}\mathbb{P}_{t}(x^{*}=a^{*})\Big{(}\mathbb{E}_{t}[Y_{t,a}|x^{*}=a^{*}]-\mathbb{E}_{t}[Y_{t,a}]\Big{)}^{2}.$
(A.12)

We bound the information ratio of IDS by the information ratio of TS:

$\Psi_{*,2}\leq\max_{t\in[n]}\frac{\langle\pi_{t}^{\text{TS}},\Delta_{t}\rangle^{2}}{\langle\pi_{t}^{\text{TS}},I_{t}\rangle}.$

Using the matrix trace rank trick described in Proposition 5 in Russo and Van
Roy [2014], we have $\Psi_{*,2}\leq(R_{\max}^{2}+1)d/2$ in the end.

Second, we bound the information ratio with $\lambda=3$. Recall that the
exploratory policy $\mu$ is defined as

$\max_{\mu\in\mathcal{D}(\mathcal{A})}\
\sigma_{\min}\Big{(}\int_{x\in\mathcal{A}}xx^{\top}d\mu(x)\Big{)}\,.$

Consider a mixture policy
$\pi_{t}^{\text{mix}}=(1-\gamma)\pi_{t}^{\text{TS}}+\gamma\mu$ where the
mixture rate $\gamma\geq 0$ will be decided later. Then we will bound the
following in two steps.

$\Psi_{t,3}(\pi_{t}^{\text{mix}})=\frac{\langle\pi_{t}^{\text{mix}},\Delta_{t}\rangle^{3}}{\langle\pi_{t}^{\text{mix}},I_{t}\rangle}.$

#### Step 1: Bound the information gain

According the lower bound of information gain in Eq. (A.12),

$\begin{split}\langle\pi_{t}^{\text{mix}},I_{t}\rangle&\geq\frac{2}{(R_{\max}^{2}+1)}\sum_{a\in\mathcal{A}}\pi_{t}^{\text{mix}}(a)\sum_{a^{*}\in\mathcal{A}}\mathbb{P}_{t}(x^{*}=a^{*})\left(\mathbb{E}_{t}[Y_{t,a}|x^{*}=a^{*}]-\mathbb{E}_{t}[Y_{t,a}]\right)^{2}\\\
&=\frac{2}{(R_{\max}^{2}+1)}\sum_{a\in\mathcal{A}}\pi_{t}^{\text{mix}}(a)\sum_{a^{*}\in\mathcal{A}}\mathbb{P}_{t}(x^{*}=a^{*})\left(a^{\top}\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-a^{\top}\mathbb{E}_{t}[\theta^{*}]\right)^{2}.\end{split}$

By the definition of the mixture policy, we know that
$\pi_{t}(a)\geq\gamma\mu(a)$ for any $a\in\mathcal{A}$. Then we have

$\begin{split}\langle\pi_{t}^{\text{mix}},I_{t}\rangle\geq&\frac{2}{(R_{\max}^{2}+1)}\gamma\sum_{a^{*}\in\mathcal{A}}\mathbb{P}_{t}(x^{*}=a^{*})\\\
&\cdot\sum_{a\in\mathcal{A}}\mu(a)(\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-\mathbb{E}_{t}[\theta^{*}])^{\top}aa^{\top}(\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-\mathbb{E}_{t}[\theta^{*}]).\end{split}$

From the definition of minimum eigenvalue, we have

$\langle\pi_{t}^{\text{mix}},I_{t}\rangle\geq\frac{2\gamma}{(R_{\max}^{2}+1)}\sum_{a\in\mathcal{A}}\mathbb{P}_{t}(x^{*}=a)C_{\min}\left\|\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-\mathbb{E}_{t}[\theta^{*}]\right\|_{2}^{2}.$

#### Step 2: Bound the instant regret

We decompose the regret by the contribution from the exploratory policy and
the one from TS:

$\begin{split}&\langle\pi_{t}^{\text{mix}},\Delta_{t}\rangle\\\
&=\sum_{a}\mathbb{E}_{t}\Big{[}\langle x^{*},\theta^{*}\rangle-\langle
a,\theta^{*}\rangle\Big{]}\pi_{t}^{\text{mix}}(a),\\\
&=(1-\gamma)\sum_{a}\pi_{t}^{\text{TS}}(a)\mathbb{E}_{t}\Big{[}\langle
x^{*},\theta^{*}\rangle-\langle
a,\theta^{*}\rangle\Big{]}+\gamma\sum_{a}\mathbb{E}_{t}\Big{[}\langle
x^{*},\theta^{*}\rangle-\langle a,\theta^{*}\rangle\Big{]}\mu(a)\\\
&=(1-\gamma)\sum_{a}\mathbb{P}_{t}(x^{*}=a)\mathbb{E}_{t}\Big{[}\langle
x^{*},\theta^{*}\rangle-\langle
a,\theta^{*}\rangle\Big{]}+\gamma\sum_{a}\mathbb{E}_{t}\Big{[}\langle
x^{*},\theta^{*}\rangle-\langle a,\theta^{*}\rangle\Big{]}\mu(a)\end{split}$
(A.13)

Since $R_{\max}$ is the upper bound of maximum expected reward, the second
term can be bounded $2R_{\max}\gamma$. Next we bound the first term as
follows:

$\begin{split}&\sum_{a}\mathbb{P}_{t}(x^{*}=a)\mathbb{E}_{t}\Big{[}\langle
x^{*},\theta^{*}\rangle-\langle a,\theta^{*}\rangle\Big{]}\\\
&=\sum_{a}\mathbb{P}_{t}(x^{*}=a)\Big{(}\mathbb{E}_{t}[\langle
a,\theta^{*}\rangle|x^{*}=a]-\mathbb{E}_{t}[\langle
a,\theta^{*}\rangle]\Big{)}\\\
&=\sum_{a}\mathbb{P}_{t}^{1/2}(x^{*}=a)\mathbb{P}_{t}^{1/2}(x^{*}=a)\Big{(}\mathbb{E}_{t}[\langle
a,\theta^{*}\rangle|x^{*}=a]-\mathbb{E}_{t}[\langle
a,\theta^{*}\rangle]\Big{)}\\\
&\leq\sqrt{\sum_{a}\mathbb{P}_{t}(x^{*}=a)\Big{(}\mathbb{E}_{t}[\langle
a,\theta^{*}\rangle|x^{*}=a]-\mathbb{E}_{t}[\langle
a,\theta^{*}\rangle]\Big{)}^{2}},\end{split}$

where we use Cathy-Schwarz inequality. Since all the optimal actions are
sparse, any action $a$ with $\mathbb{P}_{t}(x^{*}=a)>0$ must be sparse. Then
we have

$\left(a^{\top}(\mathbb{E}_{t}[\theta^{*}|x^{*}=a]-\mathbb{E}_{t}[\theta^{*}])\right)^{2}\leq
s^{2}\left\|\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-\mathbb{E}_{t}[\theta^{*}]\right\|_{2}^{2},$

for any action $a$ with $\mathbb{P}_{t}(x^{*}=a)>0$. This further implies

$\begin{split}&\sum_{a}\mathbb{P}_{t}(x^{*}=a)\mathbb{E}_{t}\Big{[}\langle
x^{*},\theta^{*}\rangle-\langle a,\theta^{*}\rangle\Big{]}\\\
&\leq\sqrt{\sum_{a}\mathbb{P}_{t}(x^{*}=a)s^{2}\left\|\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-\mathbb{E}_{t}[\theta^{*}]\right\|_{2}^{2}}\\\
&=\sqrt{\frac{s^{2}(R_{\max}^{2}+1)}{2\gamma
C_{\min}}\frac{2\gamma}{(R_{\max}^{2}+1)}\sum_{a}\mathbb{P}_{t}(x^{*}=a)C_{\min}\left\|\mathbb{E}_{t}[\theta^{*}|x^{*}=a^{*}]-\mathbb{E}_{t}[\theta^{*}]\right\|_{2}^{2}}\\\
&\leq\sqrt{\frac{s^{2}(R_{\max}^{2}+1)}{2\gamma
C_{\min}}\langle\pi_{t}^{\text{mix}},I_{t}\rangle}.\end{split}$ (A.14)

Putting Eq. (A.13) and (A.14) together, we have

$\langle\pi_{t}^{\text{mix}},\Delta_{t}\rangle\leq\sqrt{\frac{s^{2}(R_{\max}^{2}+1)}{2\gamma
C_{\min}}\langle\pi_{t}^{\text{mix}},I_{t}\rangle}+2R_{\max}\gamma.$

By optimizing the mixture rate $\gamma$, we have

$\frac{\langle\pi_{t}^{\text{mix}},\Delta_{t}\rangle^{3}}{\langle\pi_{t}^{\text{mix}},I_{t}\rangle}\leq\frac{s^{2}(R_{\max}^{2}+1)}{8R^{2}_{\max}C_{\min}}\leq\frac{s^{2}}{4C_{\min}}.$

This ends the proof.

##  Appendix B Detailed algorithms

For each $a\in\mathcal{A}$, we expand $v_{t}(a)$ as follows:

$\begin{split}v_{t}(a)&=\text{Var}_{t}(\mathbb{E}_{t}[a^{\top}\theta|x^{*}])=\mathbb{E}_{t}\Big{[}a^{\top}\mathbb{E}_{t}[\theta|x^{*}]-\mathbb{E}_{t}\big{[}a^{\top}\mathbb{E}_{t}[\theta|x^{*}]\big{]}\Big{]}^{2}\\\
&=\mathbb{E}_{t}\Big{[}a^{\top}\mathbb{E}_{t}[\theta|x^{*}]-a^{\top}\mathbb{E}_{t}[\theta]\Big{]}^{2}=a^{\top}\mathbb{E}_{t}[(\mathbb{E}_{t}[\theta|x^{*}]-\mathbb{E}_{t}[\theta])(\mathbb{E}_{t}[\theta|x^{*}]-\mathbb{E}_{t}[\theta])^{\top}]a.\end{split}$

We denote $\mu_{t}=\mathbb{E}_{t}[\theta]$ as the posterior mean and
$\mu_{t}^{a}=\mathbb{E}_{t}[\theta|x^{*}=a]$. We let
$\Phi\in\mathbb{R}^{|\mathcal{A}|\times d}$ as the feature matrix where each
row of $\Phi$ represent each action in $\mathcal{A}$. We summarize the
procedure of estimating $\Delta_{t},I_{t}$ in Algorithm 3.

Algorithm 3 Approximate $\Delta_{t}$, $v_{t}$ based on posterior samples

1: Input: $M$ posterior samples $\theta^{1},\ldots,\theta^{M}$ from Eq. (6.2),
action set $\mathcal{A}$.

2: Calculate $\widehat{\mu}_{t}=\sum_{m}\theta^{m}/M$.

3: for $a\in\mathcal{A}$ do

4: Find
$\widehat{\Theta}_{a}=\\{m\in[M]:(\Phi\theta^{m})_{a}=\max_{a^{\prime}\in\mathcal{A}}(\Phi\theta^{m})_{a^{\prime}}\\}$.

5: Calculate $\widehat{p}^{*}_{a}=|\widehat{\Theta}_{a}|/M$.

6: Calculate
$\widehat{\mu}_{t}^{a}=\sum_{m\in\widehat{\Theta}_{a}}\theta^{m}/|\widehat{\Theta}_{a}|$.

7: Calculate
$\widehat{v}_{t}(a)=a^{\top}\sum_{a}\widehat{p}^{*}_{a}(\widehat{\mu}_{t}^{a}-\widehat{\mu}_{t})(\widehat{\mu}_{t}^{a}-\widehat{\mu}_{t})^{\top}a,\widehat{\Delta}_{t}(a)=\sum_{a\in\mathcal{A}}\widehat{p}^{*}_{a}a^{\top}\widehat{\mu}^{a}_{t}-a^{\top}\widehat{\mu}_{t}.$

8: end for

9: Output: $\widehat{v}_{t},\widehat{\Delta}_{t}$.

##  Appendix C Supporting lemmas

######  Lemma C.1 (First-order optimality condition.).

Suppose that $f_{0}$ in a convex optimization problem is differentiable. Let
$\mathcal{X}$ denote the feasible set. Then $x$ is optimal if and only if
$x\in\mathcal{X}$ and $\nabla f_{0}(x)^{\top}(y-x)\geq 0,\forall
y\in\mathcal{X}.$

######  Lemma C.2 (Data processing lemma).

If $Z=g(Y)$ for a deterministic function $g$, then $I(X;Y)\geq I(X;Z)$.