# HoloBeam: Learning Optimal Beamforming in Far-Field Holographic Metasurface
Transceivers
††thanks: Manjesh K. Hanawal thanks funding support from SERB, Govt of India,
through Core Research Grant (CRG/2022/008807) and MATRICS grant
(MTR/2021/000645), and DST-Inria Targeted Programme.

Debamita Ghosh, IITB-Monash Research Academy, India, e-mail:
<EMAIL_ADDRESS>
Manjesh K. Hanawal, MLiONS Lab, IEOR, IIT Bombay, India, e-mail:
<EMAIL_ADDRESS>
Nikola Zlatanov, Innopolis University, Russia, e-mail<EMAIL_ADDRESS>
###### Abstract

Holographic Metasurface Transceivers (HMTs) are emerging as cost-effective
substitutes to large antenna arrays for beamforming in Millimeter and
TeraHertz wave communication. However, to achieve desired channel gains
through beamforming in HMT, phase-shifts of a large number of elements need to
be appropriately set, which is challenging. Also, these optimal phase-shifts
depend on the location of the receivers, which could be unknown. In this work,
we develop a learning algorithm using a fixed-budget multi-armed bandit
framework to beamform and maximize received signal strength at the receiver
for far-field regions. Our algorithm, named Holographic Beam (HoloBeam)
exploits the parametric form of channel gains of the beams, which can be
expressed in terms of two phase-shifting parameters. Even after
parameterization, the problem is still challenging as phase-shifting
parameters take continuous values. To overcome this, HoloBeam works with the
discrete values of phase-shifting parameters and exploits their unimodal
relations with channel gains to learn the optimal values faster. We upper
bound the probability of HoloBeam incorrectly identifying the (discrete)
optimal phase-shift parameters in terms of the number of pilots used in
learning. We show that this probability decays exponentially with the number
of pilot signals. We demonstrate that HoloBeam outperforms state-of-the-art
algorithms through extensive simulations.

###### Index Terms:

Holographic Metasurface Transceivers, beam forming, bandit learning, fixed
budget pure exploration

##  I Introduction

The demand for high-data rates is growing with the emergence of data-intensive
applications, which are expected to offer energy efficiency and low latency.
New solutions are needed to enhance the network capacity and connectivity in
the next-generation wireless networks to support these applications.
Millimeter wave (mmWave) and TeraHertz (THz) communication technologies are
potential solutions due to the availability of large bandwidths at very high
frequencies. However, mmWave and THz signals are prone to severe deterioration
from reflections and absorption, significantly restricting their direct
adaptation in cellular networks [1], [2].

Base stations (BSs) with massive antenna arrays can be used to focus the
transmission energy in the desired direction through beamforming. This can
offer high beamforming gains and compensate for the signal degradation [3].
However, implementing a BS with a large antenna array increases hardware
complexity and costs. HMTs are emerging as a low-cost solution for building a
massive antenna array [4, 5, 6].

An HMT is a rectangular surface consisting of nearly infinite low-cost
metamaterial elements densely deployed into a limited surface area to form a
spatially continuous transceiver aperture. HMTs can be considered as an
extension of the traditional massive antenna arrays with discrete antennas to
the continuous reflecting surfaces [7]. Each metamaterial element in HMT acts
as a phase-shifting antenna that can change the phase of
transmitting/receiving signals and thereby beamform the transmit/receive
signals to/from the desired direction with high channel gains and enhancing
the received signal strength (RSS) at the receiver [7]. The channel gain from
HMT to receivers depends on the phase-shift at each element. Identifying the
correct phase-shifts for all the elements is a fundamental and challenging
task [8, 9, 10], since the required phase-shifts depend on various factors
such as channel state information (CSI) and user location, which are unknown.
Our goal in this work is to develop a beamforming algorithm that learns
optimal phase-shifts and maximizes RSS in HMT systems. As the number of phase-
shifting elements in an HMT can be large, learning the optimal phase-shifts is
not trivial. We tackle this task by exploiting the structural properties of
the channel gains in the phase-shift values.

In the far-field region, the channel gain of beams can be expressed in a
parametric form by setting each phase-shift of the HMT as a function of two
common phase-shifting parameters [11, 12]. To maximize the RSS at the receiver
location, these parameters must be set to a value that corresponds to the
receiver’s location. However, in practice, the receiver’s location is unknown,
and the phase-shifting parameters associated with its location must be
learned. In particular, these parameters are related to the azimuth and
elevation of the receiver’s location from the center of the HMT and need to be
estimated by measuring the RSS received at the receiver. We exploit this fact
to develop a learning algorithm to beamform HMT towards the receiver and
maximize RSS.

The two phase-shifting parameters take continuous values, and learning the
optimal values is not practically feasible in a finite time. Therefore, we
discretize the range of these parameters and search for the optimal values
over the discretized space. The discretization is done in such a way that
optimal values in the discrete space and the continuous space are close. We
use a fixed-budget multi-armed bandit (MAB) framework to develop an algorithm
named Holographic Beam (HoloBeam) to identify the optimal phase-shifting
parameters in the discrete space. The algorithm works in two phases. Each
phase learns the optimal value of one parameter while keeping the other
parameter constant. Further, the algorithm exploits the unimodal structure of
the RSS for each parameter to reduce the pilots required to identify the
optimal value of these parameters. The algorithm works in batches where one-
third of discrete parameter values are eliminated at the end of every batch.

Next, we provide theoretical guarantees on the performance of HoloBeam. The
analysis uses tail bounds of the non-central Chi-squared distribution to
demonstrate that the error probability goes to zero exponentially in the
number of pilot symbols used to estimate the parameters. In particular, we
establish that HoloBeam achieves an error probability of the order of
$\mathcal{O}\bigg{(}\sum\limits_{i=1}^{2}\log_{2}K_{i}\exp\left\\{-\frac{n\Delta_{i}^{2}}{\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}\bigg{)}$
after using $n$ pilot symbols during channel estimation, where $K_{i}$ denote
the number of phase-shifting parameters in the discrete space, $\Delta_{i}$ is
the minimum gap between mean RSS of successive values in the discrete set of
$\beta_{i}$ for $i=1,2$, $\sigma^{2}$ is the variance of noise, and $G$ is
associated with dimensions and radiation properties of the HMT.

In summary, our main contributions are as follows:

  * •

We exploit the parametric properties of the far-filed channel gains to set up
the beamforming problem in the HMT system as a fixed-budget MAB problem.

  * •

We exploit the unimodal structure of the far-field channel gains and propose
an algorithm named HoloBeam that identifies the best phase-shift parameters.

  * •

We upper bound the error probability of HoloBeam and demonstrate that it is
strictly smaller than the case when no unimodality is exploited.

  * •

Extensive numerical simulations validated that HoloBeam significantly
outperforms the state-of-the-art algorithms.

##  II Related Work

Some prominent channel estimation schemes such as exhaustive search [13],
hierarchical search [14, 15, 16], and compressed sensing [15, 16, 17, 18] are
applicable to the HMT systems. However, all these schemes require high
training overheads and system latency. Some CSI estimation schemes, such as
least-square estimation-based approach [19], and subspace-based approach [10]
are developed for holographic MIMO (HMIMO) communications. However, the
computational complexity scales up with the number of phase-shift elements in
[19] and [10]. The authors in [20] give an overview of the efficient channel
estimation approaches on HMIMO communications. An efficient CSI scheme of
line-of-sight (LOS) dominated far-field channel between an HMT and a user is
proposed in [11]. The computational cost and the training overhead of the
proposed scheme do not scale with the number of phase-shift elements of the
HMT, but they did not provide any theoretical guarantee on their proposed
algorithm. A pure-exploration based algorithm with a theoretical guarantee is
proposed in [21], which outperforms the one in [11]. However, none of the
above-mentioned works exploit the unimodal structure of the far-field channel
model of the HMT system.

The papers [22, 23, 24] exploit the unimodal structure of the RSS in mmWave
massive antenna systems using a MAB approach in cumulative regret minimization
setting that balances exploration and exploitation. However, due to continuous
exploration in regret settings, sub-optimal phase-shifts can be used for data
transfer, resulting in outages. Therefore, regret is not the right performance
measure. To overcome these issues, we address the beamforming problem of the
HMT system in pure-exploration setting.

The pure-exploration strategies proposed in [25, 26, 27] exploit the benefits
of hierarchical codebooks and the unimodality structure of the beam signal
strengths to achieve higher data rates in mmWave massive antenna systems. All
these works are based on fixed confidence setting that uses the benefits of
hierarchical codebooks. However, pure-exploration fixed-budget setting [28,
29] are more suitable for the beamforming problem, as the exploration can be
completed within the channel estimation phase. The Unimodal Bandit for Best
Beam (UB3) algorithm developed in [12] exploits the unimodal structure of the
RSS of the mmWave massive antenna system and identifies the best beam with
high probability within a fixed budget of channel estimation. Note that all
the above-mentioned works are applied to mmWave massive antenna systems, and
none of them are applied to the HMT systems.

We develop a learning algorithm that identifies the best phase-shifts using a
fixed-budget pure-exploration setup by exploiting the parametric and unimodal
structure of the far-field channel gains of the HMT systems. To our knowledge,
this has not been studied in HMT systems.

The paper is organized as follows. The channel model for the HMT system is
given in Sec. III. The channel estimation strategy is formulated in Sec. IV.
The proposed algorithm for learning the optimal phase-shifts is given in Sec.
V. We provided the theoretical guarantee of the proposed algorithm in Sec. VI.
Numerical evaluation of the proposed algorithm is provided in Sec. VII.
Finally, Sec. VIII concludes the paper.

##  III Channel Model and Channel Estimation

In this section, we consider the channel model as given in [21] for which we
propose our algorithm. We follow the setup and notation provided in [11, 21].

###  III-A Channel Model

We consider an HMT of width $L_{x}$ and length $L_{y}$ comprised of $M$ number
of sub-wavelength phase-shifting elements. We assume a LOS between an HMT and
each user [30], and the non-line-of-sight (NLOS) components are incorporated
into the noise model [31, 32]. We consider that each user sends orthogonal
pilots to the HMT, and thereby, we focus on the CSI estimation between the HMT
and a typical user, see Fig. 1.

Figure 1: The HMT-assisted wireless communication system [11].

Assuming that the HMT lies in the Cartesian coordinate system with the centre
of the surface at the origin, let $\beta_{m_{x}m_{y}}$ be the phase-shift at
the $(m_{x},m_{y})^{th}$ element, where
$m_{x}\in\left\\{-\frac{(L_{x}/d_{r})-1}{2},\dots,\frac{(L_{x}/d_{r})-1}{2}\right\\}$,
$m_{y}\in\left\\{-\frac{(L_{y}/d_{r})-1}{2},\dots,\frac{(L_{y}/d_{r})-1}{2}\right\\}$,
and $d_{r}$ be the distance between two neighbouring phase-shifting elements.
We denote $\lambda$ as the wavelength of the carrier frequency,
$k_{0}=2\pi/\lambda$ be the wave number, $d_{0}$ be the distance between the
user and the center of the HMT, and $F_{m_{x}m_{y}}$ be the effect of the size
and power radiation pattern of the $(m_{x},m_{y})^{th}$ phase-shifting element
on the channel coefficient [33]. In the far-field, the radiation pattern of
all the phase-shifting elements of the HMT is identical, i.e.,
$F_{m_{x}m_{y}}=F,\;\forall m_{x},m_{y}$ holds [33]. Finally, we denote
$\theta$ and $\phi$ as the elevation and azimuth angles of the signals from
the user to the centre of the HMT, refer to Fig. 2 in [21]. We consider the
phase-shift imposed by the $(m_{x},m_{y})^{th}$ element is set to

$\beta_{m_{x}m_{y}}=-\mod(k_{0}d_{r}(m_{x}\beta_{1}+m_{y}\beta_{2}),2\pi),$
(1)

where $\beta_{1}$ and $\beta_{2}$ are the phase-shifting parameters [11, 34,
35] and they are the only degrees of freedom in $\beta_{m_{x}m_{y}}$. With
$\beta_{m_{x}m_{y}}$ as in (1), the channel between the HMT and the typical
user [21, 11] for far-field regions is given by

$\displaystyle H^{ff}(\beta_{1},\beta_{2})$
$\displaystyle=\left(\frac{\sqrt{F}\lambda e^{-jk_{0}d_{0}}}{4\pi
d_{0}}\right)L_{x}L_{y}\mathrm{sinc}\big{(}K_{x}\pi(\alpha_{1}-\beta_{1})\big{)}$
$\displaystyle\qquad\times\mathrm{sinc}\big{(}K_{y}\pi(\alpha_{2}-\beta_{2})\big{)},$
(2)

where
$K_{x}=L_{x}/\lambda,K_{y}=L_{y}/\lambda,\alpha_{1}=\sin(\theta)\cos(\phi),\alpha_{2}=\sin(\theta)\sin(\phi),$
and $\mathrm{sinc}(x)=\frac{\sin(x)}{x}$. Note that $\alpha_{1}\in[-1,1]$ and
$\alpha_{2}\in[-1,1]$, and their values depend on the user’s location, i.e.,
on $\theta$ and $\phi$. Therefore, $\alpha_{1}$ and $\alpha_{2}$ are the two
unknown parameters that need to be learned by the HMT [21].

Figure 2: The optimal value is attained at the highest peak of the central
lobe of $|H^{ff}(\beta_{1},\beta_{2})|$, i.e.
$(\beta^{*}_{1},\beta^{*}_{2})=(\alpha_{1},\alpha_{2})=(0.5,-0.5).$

###  III-B Channel Estimation

The RSS at the HMT for fixed phase-shifting parameters
$(\beta_{1},\beta_{2}),$ denoted by $r(\beta_{1},\beta_{2})$, is given by

$\displaystyle r(\beta_{1},\beta_{2})$ $\displaystyle=\big{|}\sqrt{P}\times
H^{ff}(\beta_{1},\beta_{2})+\zeta\big{|}^{2},$ (3)

which is induced when the user sends a pilot symbol $x_{p}=\sqrt{P}$ to the
HMT, where $P$ is the pilot transmit power and $\zeta$ is the complex-valued
additive white Gaussian noise (AWGN) with zero mean and variance $\sigma^{2}$
at the HMT. The mean RSS of $r(\beta_{1},\beta_{2})$, denoted by
$\mu(\beta_{1},\beta_{2})$, is given by

$\displaystyle\mu(\beta_{1},\beta_{2})=\mathbb{E}\left[r(\beta_{1},\beta_{2})\right]=\left\lvert\sqrt{P}\times
H^{ff}(\beta_{1},\beta_{2})\right\rvert^{2}+\sigma^{2}.$ (4)

Our goal is to identify the optimal phase-shifting parameters that maximize
the mean RSS $\mu(\beta_{1},\beta_{2})$, i.e.,

$\displaystyle(\beta_{1}^{*},\beta_{2}^{*})$
$\displaystyle=\operatorname*{arg\,max}_{\begin{subarray}{c}\beta_{1}\in[-1,1],\beta_{2}\in[-1,1]\end{subarray}}\mu(\beta_{1},\beta_{2}).$
(5)

Notice that $\mu(\beta_{1},\beta_{2})$ is maximized at the same points where
the absolute value of the HMT-user channel given by (III-A) is maximized,
i.e., $\beta_{1}^{*}=\alpha_{1},\beta_{2}^{*}=\alpha_{2}$ (see Fig. 2). Note
that $(\alpha_{1},\alpha_{2})$ are unknown and need to be learned. Moreover,
$\alpha_{1}$ and $\alpha_{2}$ take continuous values in the range $[-1,1]$
making it infeasible to learn their exact values within a finite number of
pilot symbols. We thus quantize the range of the phase-shifting parameters and
work with their discrete values.

##  IV Discretizating Phase-Shifting Parameters

In this section, we discretize the range of the phase-shifting parameters such
that the optimal values of these parameters in the discrete set are not far
from the optimal values in the continuous space, and the difference in their
corresponding mean RSS value remains small.

###  IV-A Discretization of the Phase-Shifting Parameters

We discretize the range of $\beta_{1}$ into $K_{1}$ equally spaced points. The
set of discrete phase-shift parameters, denoted by $\mathcal{B}_{1}$, is

$\displaystyle\mathcal{B}_{1}=\\{\beta^{1}_{1},\beta^{2}_{1},\dots,\beta^{K_{1}}_{1}\\},$
(6)

where $\beta^{k}_{1}=\beta^{1}_{1}+(k-1)d_{1},k=1,2,\ldots,K_{1}$ and $d_{1}$
is a constant to be set later. Similarly, we discretize the range of
$\beta_{2}$ into $K_{2}$ equally spaced points, denoted by $\mathcal{B}_{2}$,
is

$\displaystyle\mathcal{B}_{2}=\\{\beta^{1}_{2},\beta^{2}_{2},\dots,\beta^{K_{2}}_{2}\\},$
(7)

where $\beta^{k}_{2}=\beta^{1}_{2}+(k-1)d_{2},k=1,2,\ldots,K_{2}$ and $d_{2}$
is a constant to be set later.

Objective: We revise objective in Eq. (5) to the following by restricting to
the discrete sets $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$.

$\displaystyle(\beta_{1}^{k_{1}^{*}},\beta_{2}^{k_{2}^{*}})$
$\displaystyle=\operatorname*{arg\,max}_{\begin{subarray}{c}\beta_{1}\in\mathcal{B}_{1},\beta_{2}\in\mathcal{B}_{2}\end{subarray}}\mu(\beta_{1},\beta_{2}).$
(8)

Here $k_{1}^{*}$ and $k_{2}^{*}$ denote the index of the optimal values in the
set $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$, respectively. We construct
$\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ such that the mean RSS achieved from
(5) remains close to that obtained from (8). To demonstrate this, we use the
following notations and unimodality property of the mean RSS in each argument
over the discrete spaces.

For a fixed $\beta^{0}_{2}\in[-1,1]$ we write
$r_{1}(\beta_{1}):=r(\beta_{1},\beta^{0}_{2})$,
$\mu_{1}(\beta_{1}):=\mu(\beta_{1},\beta^{0}_{2})$ for all
$\beta_{1}\in\mathcal{B}_{1}$. Similarly, for a fixed $\beta^{0}_{1}\in[-1,1]$
we write $r_{2}(\beta_{2}):=r(\beta^{0}_{1},\beta_{2})$,
$\mu_{2}(\beta_{2})=\mu(\beta^{0}_{1},\beta_{2})$ for all
$\beta_{2}\in\mathcal{B}_{2}$, . We set $\beta_{1}^{1}=\beta_{2}^{1}=-1$ and
$\beta_{1}^{K_{1}}=\beta_{2}^{K_{2}}=1$ in $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$.

######  Definition 1 (Unimodality).

For any discrete set $\mathcal{B}=\\{b_{1},b_{2},\ldots,b_{K}\\}$, we say that
a real-valued function $f:\mathcal{B}\rightarrow\mathcal{R}$, is unimodal if
there exits an $1<i^{*}<K$ such that

$\displaystyle f(b_{1})<f(b_{2})<\dots<f(b_{i^{*}})>..>f(b_{K-1})>f(b_{K})$
(9)

The following lemma established the unimodal property of the function
$\mu_{1}:\mathcal{B}_{1}\rightarrow\mathcal{R}$ for any
$\beta_{2}^{0}\in[-1,1]$. For notational convenience we write
$G:=\big{|}\sqrt{P}\left(\frac{\sqrt{F}\lambda e^{-jk_{0}d_{0}}}{4\pi
d_{0}}\right)L_{x}L_{y}\big{|}^{2}$.

######  Lemma 1.

Let $\mathcal{B}_{1}$ be such that $K_{1}=\left\lceil 2/d_{1}\right\rceil+1$
and $d_{1}=\frac{1}{K_{x}}$, then $\mu_{1}(\beta_{1})$ is unimodal on
$\mathcal{B}_{1}$. Similarly, let $K_{2}=\left\lceil 2/d_{2}\right\rceil+1$
and $d_{2}=\frac{1}{K_{y}}$ in $\mathcal{B}_{2}$, then $\mu_{2}(\beta_{2})$ is
unimodal on $\mathcal{B}_{2}$.

###### Proof.

The proof is given in Sec. IX-A. ∎

For $\beta_{2}$ fixed at $\beta^{0}_{2}$, every side lobe of
$|H^{ff}(\beta_{1},\beta^{0}_{2})|$ hits zero at the periodicity of $\pi$, and
the central lobe hits zero at the periodicity of $2\pi$. When we discretize
the phase-shifting parameter $\beta_{1}$ as in Lemma 1, we get one discrete
value in each side lobe and two values in the central lobe of
$|H^{ff}(\beta_{1},\beta^{0}_{2})|$, (see Fig. 3). One of these values in the
central lobe is closest to $\alpha_{1}$, given by $\beta^{k_{1}^{*}}_{1}$.
Moreover, if one of the values in the central lobe hits zero, the other will
be the optimal value, i.e., $\alpha_{1}$. The following proposition bounds the
difference in the optimal mean RSS obtained from (5) and (8).

######  Proposition 1.

Consider $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ be as specified in Lemma 1.
Let $|\beta^{k_{1}^{*}}_{1}-\alpha_{1}|=\epsilon_{1}$ and
$|\beta^{k_{2}^{*}}_{2}-\alpha_{2}|=\epsilon_{2}$. Then,

$\displaystyle\left\lvert\mu(\alpha_{1},\alpha_{2})-\mu(\beta^{k_{1}^{*}}_{1},\beta^{k_{2}^{*}}_{2})\right\rvert$
$\displaystyle=G\big{(}1-\big{|}\mathrm{sinc}\big{(}K_{x}\pi\epsilon_{1}\big{)}\mathrm{sinc}\big{(}K_{y}\pi\epsilon_{2}\big{)}\big{|}^{2}\big{)}.$
(10) $\displaystyle\leq G\left[1-\left(2/\pi\right)^{4}\right].$ (11)

###### Proof.

The proof is given in Sec. IX-B. ∎

Note that as $\epsilon_{1},\epsilon_{2}\to 0$,
$\mu(\beta^{k_{1}^{*}}_{1},\beta^{k_{2}^{*}}_{2})\to\mu(\alpha_{1},\alpha_{2})$
in (10). Further, the proof establishes that $\epsilon_{1}\leq 1/(2K_{x})$ and
$\epsilon_{2}\leq 1/(2K_{y})$, to obtain the bound (11). The worst-case
scenario occurs when the mean RSS values of both discrete parameters in the
central lobe are the same and result in the maximum error, i.e.,
$\epsilon_{1}=1/(2K_{x})$ and $\epsilon_{2}=1/(2K_{y})$.

Figure 3: Mean RSS vs Discrete and Continuous $\beta_{2}$, where
$\beta^{0}_{1}=-0.5$.

###  IV-B Problem Formulation

We assume a block fading channel model where the duration of each block is
denoted as $T=T_{E}+T_{D}$. We use duration $T_{E}$ to estimate the phase-
shifting parameters and the remaining $T_{D}$ for data transmission. We
consider a slotted system where $n$ pilot symbols are used over $T_{E}$. Each
pilot symbol is assumed to be of one slot duration. We consider an additive
white Gaussian noise channel, where HMT observes noisy RSS values in each
slot. For each phase-shifting parameter, the observations are independently
and identically distributed.

We address the channel estimation problem as a fixed-budget pure-exploration
MAB approach [28, 36]. In a MAB framework, a policy is any strategy that
selects the best phase-shifting parameter value based on noisy RSS observed in
the previous slots. Let $\mathbf{\Pi}$ denote the set of pure exploration
strategies that output the best parameter values using $n$ pilots symbols. For
any policy $\pi\in\Pi$, let
$(\beta^{\hat{k}_{1}^{\pi}}_{1},\beta^{\hat{k}_{2}^{\pi}}_{2})\in\mathcal{B}_{1}\times\mathcal{B}_{2}$
denote the parameters output by the policy. Our objective is to learn a policy
that minimizes the probability of misidentifying the optimal phase-shifting
parameters as given by

$\displaystyle\min_{\pi\in\mathbf{\Pi}}\Pr\bigg{(}\bigcup\limits_{i=1,2}\Big{\\{}\beta^{\hat{k}_{i}^{\pi}}_{i}\neq\beta^{*}_{i}\Big{\\}}\bigg{)},$
(12)

where $\Pr(\cdot)$ is calculated with respect to the samples induced by the
policy.

##  V Proposed Algorithm

In this section, we develop an algorithm that minimizes the probability of
misidentifying the optimal phase-shifting parameters with a budget of $n$.
Note that the channel gain function has a variable separable in the phase-
shifting parameters, i.e., each $\mathrm{sinc}$ function in (III-A) depends
only on one of the parameters. Hence, we can learn one of the parameters while
fixing the other.

We propose the Holographic Beam (HoloBeam) algorithm that finds the best
phase-shift parameters by exploiting the unimodal structure of mean RSS using
$n$ pilot symbols. The HoloBeam works in two phases, each consisting of $n/2$
pilot symbols. In first phase, HoloBeam fixes $\beta_{2}$ to
$\beta^{0}_{2}\in\mathcal{B}_{2}$ and runs a baseline algorithm
$\beta_{1}$-HoloBeam that outputs $\beta^{\hat{k}_{1}}_{1}\in\mathcal{B}_{1}$.
In second phase, HoloBeam fixes $\beta_{1}$ to
$\beta^{\hat{k}_{1}}_{1}\in\mathcal{B}_{1}$ and runs $\beta_{2}$-HoloBeam
algorithm that output $\beta^{\hat{k}_{2}}_{2}\in\mathcal{B}_{2}$. The pseudo-
code of HoloBeam is given in ALGO 1.

ALGO 1: Holographic Beam (HoloBeam)

1: Input: $n$, $\beta^{0}_{2}$, $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$. ★★
Phase 1: Best Phase-Shift Estimation for $\beta_{1}$ ★★

2: Fix $\beta_{2}$ at $\beta^{0}_{2}$. Set $\mathcal{D}_{1}=\mathcal{B}_{1}$.

3: Run $\beta_{1}$-HoloBeam$\big{(}n/2,\mathcal{D}_{1}\big{)}$, and
$\beta^{\hat{k}_{1}}_{1}$ is the output of Phase 1 after $L_{1}+1$ batches. ★★
Phase 2: Best Phase-Shift Estimation for $\beta_{2}$ ★★

4: Fix $\beta_{1}$ at $\beta^{\hat{k}_{1}}_{1}$. Set
$\mathcal{D}_{2}=\mathcal{B}_{2}$.

5: Run $\beta_{2}$-HoloBeam$\big{(}n/2,\mathcal{D}_{2}\big{)}$, and
$\beta^{\hat{k}_{2}}_{2}$ is the output of Phase 2 after $L_{2}+1$ batches.

6: Output: $\beta^{\hat{k}_{1}}_{1}$ and $\beta^{\hat{k}_{2}}_{2}$.

7: Phase-shifts at HMT:  Set the phase-shift of the $(m_{x},m_{y})^{th}$
element at the HMT to
$\beta_{m_{x}m_{y}}=-\mod\big{(}k_{0}d_{r}(m_{x}\beta^{\hat{k}_{1}}_{1}+m_{y}\beta^{\hat{k}_{2}}_{2}),2\pi\big{)}.$

###  V-A The Baseline Algorithm: $\beta_{i}$-HoloBeam

The HoloBeam runs $\beta_{i}$-HoloBeam algorithm in phase $i$ for $i=1,2$. In
phase $i$, $\beta_{i}$-HoloBeam exploits the unimodal structure of the mean
RSS. It divides the $n/2$ pilot symbols into $L_{i}+1$ batches (see 15). The
$l$-th batch contains $N^{l}_{i}$ pilots, where $N^{l}_{i}$ is set as

$N^{l}_{i}=\begin{cases}\frac{2^{L_{i}-2}}{3^{L_{i}-1}}\frac{n}{2}&\mbox{ for
}l=1,2\\\ \frac{2^{L_{i}-(l-1)}}{3^{L_{i}-(l-2)}}\frac{n}{2}&\mbox{ for
}l=3,4,\ldots,L_{i}+1\end{cases}$ (13)

We set $N^{l}_{i}$ as in (13) so that $N^{l}_{i}$ satisfy the following

$\displaystyle\sum\limits_{l=1}^{L_{i}+1}N^{l}_{i}=2\times\frac{2^{L_{i}-2}\frac{n}{2}}{3^{L_{i}-1}}+\sum_{l=3}^{L_{i}+1}\frac{2^{L_{i}-(l-1)}\frac{n}{2}}{3^{L_{i}-(l-2)}}=\frac{n}{2}.$
(14)

After $L_{i}+1$ batches, $\beta_{i}$-HoloBeam outputs
$\beta^{\hat{k}_{i}}_{i}\in\mathcal{B}_{i}$, which we declare as the best
phase-shift parameter value for $\beta_{i}$.

The pseudo-code of $\beta_{i}$-HoloBeam is given in ALGO 2. It works as
follows. The set $\mathcal{A}_{l}$ denotes the set of discrete parameter
values for $\beta_{i}$ in batch $l$, and $j_{l}:=|\mathcal{A}_{l}|$ denotes
the number of values in the set $\mathcal{A}_{l}$. In each batch $l=1,2,\ldots
L_{i}$, HMT uses $N^{l}_{i}/4$ number of pilots for each value in
$\mathcal{S}_{l}=\\{\beta^{k^{A}}_{i},\beta^{k^{B}}_{i},\beta^{k^{C}}_{i},\beta^{k^{D}}_{i}\\}\subset\mathcal{A}_{l}$,
where $\mathcal{S}_{l}$ is selected such that it include the two extremes and
two middle parameter values uniformly spaced from them (lines $4$-$7$). At the
end of batch $l$, HMT obtains the empirical means
$\hat{\mu}^{l}_{\beta^{k}_{i}}$ for each $\beta^{k}_{i}\in\mathcal{S}_{l}$
(line $8$). Based on these empirical means, the algorithm eliminates at most
$1/3^{rd}$ of the number of values from the set $\mathcal{A}_{l}$111If the
number of parameters in a batch is not a multiple of $4$, then less than
$1/3^{rd}$ will be eliminated in that batch.. Specifically, if
$\beta^{k^{A}}_{i}$ or $\beta^{k^{B}}_{i}$ has the highest empirical means,
then all the values succeeding $\beta^{k^{C}}_{i}$ in $\mathcal{A}_{l}$ are
eliminated (line $11$). Similarly, if $\beta^{k^{C}}_{i}$ or
$\beta^{k^{D}}_{i}$ have the highest empirical means, then all the values
preceding $\beta^{k^{B}}_{i}$ in $\mathcal{A}_{l}$ are eliminated (line $13$).
Fig. 4 gives a pictorial representation of eliminating these values in the two
cases. The remaining set of values is then transferred to the next batch. In
batch $L_{i}+1$, we are left with three parameter values. Each is sampled
$N^{L_{i}+1}_{i}/3$ times, and the one with the highest empirical mean is the
output as the best parameter value of $\beta_{i}$ (lines $17$-$22$).

ALGO 2: $\beta_{i}$-HoloBeam

1: Input: $n/2$ and $\mathcal{D}_{i}$.

2: Initialise: $\mathcal{A}_{1}=\mathcal{D}_{i}$,
$j_{1}\leftarrow|\mathcal{A}_{1}|$. Calculate $L_{i}$ from (15).

3: for $l=1$ to $L_{i}$ do

4: $\beta^{k^{A}}_{i}\leftarrow$ First phase-shift parameter of
$\mathcal{A}_{l}$.

5: $\beta^{k^{B}}_{i}\leftarrow\lceil j_{l}/3\rceil^{th}$ phase-shift
parameter of $\mathcal{A}_{l}$.

6: $\beta^{k^{C}}_{i}\leftarrow\lfloor 2j_{l}/3\rfloor^{th}$ phase-shift
parameter of $\mathcal{A}_{l}$.

7: $\beta^{k^{D}}_{i}\leftarrow$ Last phase-shift parameter of
$\mathcal{A}_{l}$.

8: HMT collects $\frac{N^{l}_{i}}{4}$ pilots for each value in
$\mathcal{S}_{l}=\\{\beta^{k^{A}}_{i},\beta^{k^{B}}_{i},\beta^{k^{C}}_{i},\beta^{k^{D}}_{i}\\}$
and compute empirical means denoted as $\hat{\mu}^{l}_{\beta^{k^{A}}_{i}}$,
$\hat{\mu}^{l}_{\beta^{k^{B}}_{i}}$, $\hat{\mu}^{l}_{\beta^{k^{C}}_{i}}$,
$\hat{\mu}^{l}_{\beta^{k^{D}}_{i}}$.

9:
$x^{*}_{l}=\operatorname*{arg\,max}_{\beta^{k}_{i}\in\mathcal{S}_{l}}\hat{\mu}^{l}_{\beta^{k}_{i}}.$

10: if $\beta^{x^{*}_{l}}_{i}==\\{\beta^{k^{A}}_{i},\beta^{k^{B}}_{i}\\}$ then

11:
$\mathcal{A}_{l+1}\leftarrow\\{\beta^{k}_{i}\in\mathcal{A}_{l}:\beta^{k^{A}}_{i}\leq\beta^{k}_{i}\leq\beta^{k^{C}}_{i}\\}$

12: else if $\beta^{x^{*}_{l}}_{i}==\\{\beta^{k^{C}}_{i},\beta^{k^{D}}_{i}\\}$
then

13: $\mathcal{A}_{l+1}$
$\leftarrow\\{\beta^{k}_{i}\in\mathcal{A}_{l}:\beta^{k^{B}}_{i}\leq\beta^{k}_{i}\leq\beta^{k^{D}}_{i}\\}$

14: end if

15: $j_{l+1}\leftarrow|\mathcal{A}_{l+1}|;$

16: end for

17: for $l=L_{i}+1$ do

18:
$\mathcal{A}_{L_{i}+1}=\\{\beta^{k^{A}}_{i},\beta^{k^{B}}_{i},\beta^{k^{C}}_{i}\\}$;

19: HMT collects $\frac{N^{L_{i}+1}_{i}}{3}$ pilots for each value in
$\mathcal{A}_{L_{i}+1}$, and obtain $\hat{\mu}^{l}_{\beta^{k^{A}}_{i}}$,
$\hat{\mu}^{l}_{\beta^{k^{B}}_{i}}$, $\hat{\mu}^{l}_{\beta^{k^{C}}_{i}}$.

20: Obtain
$\beta^{\hat{k}_{i}}_{i}=\operatorname*{arg\,max}_{k\in\mathcal{A}_{L_{i}+1}}\hat{\mu}_{k}.$

21: end for

22: Output: $\beta^{\hat{k}_{i}}_{i}$

Figure 4: Different cases of elimination in batch $l$.

Note that the values between $\beta^{k^{A}}_{i}$ and $\beta^{k^{B}}_{i}$ or
the values between $\beta^{k^{C}}_{i}$ and $\beta^{k^{D}}_{i}$ are eliminated
in each batch, and the values between $\beta^{k^{B}}_{i}$ and
$\beta^{k^{C}}_{i}$ always survive for $i=1,2$. After batch
$l=1,2,\ldots,L_{i}$, only $\lfloor\frac{2}{3}j_{l}\rfloor$ of the values
survive. For ease of exposition, we will drop the $\lfloor\rfloor$ function
since this drop will influence only a few constants in the analysis. Hence,
based on the elimination strategy and $N^{l}_{i}$ as given in (13), after the
end of $L_{i}$ batches, there will be three parameter values, i.e.
$\left(2/3\right)^{L_{i}}K_{i}=3$. Therefore, we get

$\displaystyle L_{i}=\frac{\log_{2}K_{i}/3}{\log_{2}3/2},\text{ for }i=1,2.$
(15)

##  VI Analysis

In this section, we find an upper bound on the error probability of HoloBeam
for fixed-budget pure exploration bandits with unimodal structure.

######  Theorem 1.

Consider $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ as given in Lemma 1. In phase
$i$, HoloBeam runs $\beta_{i}$-HoloBeam in $L_{i}+1$ batches, where
$L_{i}=\frac{\log_{2}K_{i}/3}{\log_{2}3/2}$, and
$K_{i}=\left\lvert\mathcal{B}_{i}\right\rvert$, $i=1,2$. Let
$\beta^{\hat{k}_{i}}_{i}$ be the output after phase $i$, and
$\Delta_{i}=\min\limits_{2\leq k\leq
K_{i}-1}\big{|}\mu_{i}(\beta^{k}_{i})-\mu_{i}(\beta^{k-1}_{i})\big{|}>0$
denotes the minimum gap between the mean RSS of any two neighbouring parameter
values of $\beta_{i}$. Then, for any $n>(K_{1}+K_{2})$, the error probability
of HoloBeam is upper bounded as

$\displaystyle\Pr\bigg{(}\bigcup\limits_{i=1,2}\Big{\\{}\beta^{\hat{k}_{i}^{\pi}}_{i}\neq\beta^{*}_{i}\Big{\\}}\bigg{)}$
$\displaystyle\leq
4\sum\limits_{i=1}^{2}\bigg{[}\left(\frac{\log_{2}K_{i}/3}{\log_{2}3/2}-1\right)\exp\left\\{-\frac{n\Delta_{i}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}$
$\displaystyle\qquad\qquad+2\exp\left\\{-\frac{nK_{i}\Delta_{i}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}\bigg{]}.$
(16)

###### Proof.

The proof is in Sec. IX-C. ∎

As the first term is dominant in (1), the error probability of HoloBeam in (1)
is thus of order $\mathcal{O}\left(\sum\limits_{i=1}^{2}\log
K_{i}\exp\left\\{-\frac{n\Delta_{i}^{2}}{\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}\right)$.
For unstructured bandits, the error probability of Seq. Halv. algorithm is of
order $O\left(\sum\limits_{i=1}^{2}\log K_{i}\exp\left\\{-\frac{n/H_{i}}{\log
K_{i}\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}\right)$ which matches with the
lower bound up to a multiplicative factor of $\log_{2}(K_{i})$ [37], where
$H_{i}$ is the complexity parameter that depends on the sub-optimality gap of
$\beta_{i}$. As expected, the error probability of HoloBeam is smaller than
that of Seq. Halv., as the $\log K_{i}$ factor present in the denominator of
exponent of the error bound of Seq. Halv. does not appear in the exponent of
the error bound of HoloBeam.

##  VII Numerical Simulations

For the numerical evaluation, we set $L_{x}=L_{y}=1$m, carrier frequency is 30
GHz, $\lambda=1$cm, $d_{r}=\lambda/4$, $F=1.6d_{r}/\lambda$, and the noise
power for $200$ KHz ($\sigma^{2}$) is $-115$ dBm as in [9]. We compare
HoloBeam with the following algorithms:

Iterative Algorithm (Iterative Algo.) [11] estimates the best phase-shifts
based on stopping criteria. The algorithm is based on the initial value of
$(\beta^{0}_{1},\beta^{0}_{2})$ [11, Sec. V.C]. Two-Stage Phase-Shifts
Estimation Algorithm (Two-Stage Algo.) [21] is based on pure-exploration which
performs better than Iterative Algo. [11]. Sequential Halving (Seq. Halv.)
[38] is a fixed budget pure-exploration algorithm for unstructured bandits,
which is optimal by [37]. Linear Search Elimination (LSE) [39] is a well-known
algorithm for unimodal bandits proposed for continuous arms. We have
considered it for a fixed $T_{E}$ budget and discrete points. HBA [24]
algorithm performs well for regret minimization that exploits the unimodal
structure of mean RSS. The algorithm parameters are kept at $\rho_{1}=3$,
$\gamma=0.5$. HOSUB [25] is a fixed-confidence pure-exploration based
algorithm that exploits the unimodality of mean RSS.

Note that we have adopted all these algorithms, except Iterative Algo. and
Two-Stage Algo., to fixed-budget setting, which works in two phases, where
phase $i$ identifies the best parameter value of $\beta_{i}$. We ran the
simulation $1000$ times and average values are plotted with $95\%$ confidence
intervals.

(a) Error Prob. vs No. of pilot symbols $(n)$ for
$d_{0}=800$m and $P=\\{5,20\\}$dBm.

(b) Error Prob. vs No. of pilot symbols $(n)$ for
$P=20$ dBm and $d_{0}=\\{800,500\\}$ m.

Figure 5: Error probability performance of HoloBeam vs State-of-the-art
Algorithms

(a) Achievable rate vs No. of pilot symbols $(n)$
for transmit power $P=\\{5,20\\}$ dBm.

(b) Achievable rate vs transmit power of the pilot
signals (in dBm) for $d_{0}=\\{500,800\\}$ m and $n=100$.

Figure 6: Throughput performance of HoloBeam vs State-of-the-art Algorithms

###  VII-A Comparison with other pure exploration algorithms

We compare the error probability performance for HoloBeam with the state-of-
the-art algorithms used for pure-exploration, refer Fig. 5. When we increase
the power of the pilot signals, the accuracy of the estimation of
$(\alpha_{1},\alpha_{2})$ increases as received signals become less noisy.
Thereby, the error probability decreases, refer to Fig. 5(a). Moreover, as
distance increases, the error probability of the algorithms increases, refer
to Fig. 5(b).

For transmit power $P=20$ dBm, HoloBeam can identify the best phase-shifts
with a probability of more than 80% within $200$ pilot symbols. In contrast,
the other state-of-the-art algorithms identify the best phase-shifts with a
probability of at least $45\%$. Furthermore, Seq. Halv. needs at least
$K_{i}\log_{2}(K_{i})$ batches (i.e. at least $250$ batches) to complete phase
$i$, $i=1,2$. Hence, fewer pilots will remain for the algorithm to execute in
the neighbourhood of the optimal phase-shifts compared to HoloBeam. This
demonstrates the advantage of exploiting the unimodality of the mean RSS.

###  VII-B Comparison of throughput performance

Note that Seq. Halv. and LSE are not included for throughput comparison due to
their poor performance, as seen in Fig. 5. We have also considered the oracle
scheme where $(\alpha_{1},\alpha_{2})$ are estimated perfectly and achieve the
maximum rate. We define the throughput as the achievable data rates at the
user obtained by the best estimated phase-shifts at the HMT after using $n$
number of pilots, as given by

$\displaystyle
R\big{(}\beta^{\hat{k}_{1}}_{1},\beta^{\hat{k}_{2}}_{2}\big{)}=\frac{T_{D}}{T}\log_{2}\bigg{(}1+\frac{P\big{|}H^{ff}(\beta^{\hat{k}_{1}}_{1},\beta^{\hat{k}_{2}}_{2})\big{|}^{2}}{\sigma^{2}}\bigg{)},$
(17)

where $P$ is the transmission power at the HMT and $T_{D}$ is the duration
left for data transmission.

As the number of pilots increases, the channel estimation time increases,
decreasing the data transmission time. At the same time, as we increase the
number of pilots, the estimation accuracy of $(\alpha_{1},\alpha_{2})$
increases and the average throughput increases. This trade-off in Eq. 17 is
captured in Fig. 6(a). In Fig. 6(b), with an increase in the power of the
pilot signals, the average throughput increases, but decreases significantly
as the user moves far from the HMT. Moreover, HoloBeam can improve the average
throughput by more than 30% compared to the state-of-the-art algorithms within
$500$ pilot symbols.

##  VIII Conclusion and future work

We investigated learning optimal beamforming in an HMT-assisted wireless
system using the fixed-budget pure-exploration framework. We exploited the
parametric nature and unimodality of the channel gains to develop an algorithm
named HoloBeam. HoloBeam identified the best phase-shifting parameters using a
given number of pilots, and the error probability decays exponentially in the
number of pilots. Simulations validated the efficiency of HoloBeam as compared
to the state-of-the-art algorithms. However, HoloBeam works well when only the
LOS path is present satisfying unimodal property. However, when NLOS paths are
present, we face multimodal functions. It is interesting to extend HoloBeam or
develop new algorithms that adapt to channel gains with multiple modes.

##  IX Appendix

In this section, we will provide proof of the main results.

###  IX-A Proof of Lemma 1

###### Proof.

By using (4) and (III-A) for any $\beta^{i}_{1}\in\mathcal{B}_{1}$, we obtain

$\displaystyle\mu_{1}(\beta^{i}_{1})-\sigma^{2}=G\big{|}\mathrm{sinc}\big{(}K_{x}\pi(\alpha_{1}-\beta^{i}_{1})\big{)}$
$\displaystyle\qquad\times\mathrm{sinc}\big{(}K_{y}\pi(\alpha_{2}-\beta^{0}_{2})\big{)}\big{|}^{2}$

For $\beta^{i+1}_{1}=\beta^{i}_{1}+d_{1}\in\mathcal{B}_{1}$, we have the
following

$\displaystyle\mu_{1}(\beta^{i+1}_{1})-\sigma^{2}$
$\displaystyle=G\big{|}\mathrm{sinc}\big{(}K_{x}\pi(\alpha_{1}-\beta^{i+1}_{1})\big{)}\mathrm{sinc}\big{(}K_{y}\pi(\alpha_{2}-\beta^{0}_{2})\big{)}\big{|}^{2}.$

For $d_{1}=1/K_{x}$,
$|\sin\big{(}K_{x}\pi(\alpha_{1}-\beta^{i}_{1}-d_{1})\big{)}|$
$=|\sin\big{(}K_{x}\pi(\alpha_{1}-\beta^{i}_{1})\big{)}|$. Applying this fact,
we get

$\displaystyle\frac{\mu_{1}(\beta^{i}_{1})-\sigma^{2}}{\mu_{1}(\beta^{i+1}_{1})-\sigma^{2}}=\left\lvert\frac{\alpha_{1}-\beta^{i}_{1}-d_{1}}{\alpha_{1}-\beta^{i}_{1}}\right\rvert^{2}=\left\lvert\frac{\alpha_{1}-\beta^{i+1}_{1}}{\alpha_{1}-\beta^{i}_{1}}\right\rvert^{2}.$
(18)

According to (18) we get

$\displaystyle\mu(\beta^{i}_{1})$ $\displaystyle\leq\mu(\beta^{i+1}_{1})\text{
for }i\in\\{1,2,\dots,k_{1}^{*}-1\\},$ $\displaystyle\mu(\beta^{i}_{1})$
$\displaystyle\geq\mu(\beta^{i+1}_{1})\text{ for
}i\in\\{k_{1}^{*},k_{1}^{*}+1,\dots,K_{1}-1\\}.\qed$ (19)

###  IX-B Proof of Proposition 1

###### Proof.

By (4) and (III-A) for $\alpha_{1}$ and $\alpha_{2}$, we have the following

$\displaystyle\mu(\alpha_{1},\alpha_{2})=G+\sigma^{2}.$ (20)

By (4) and (III-A), for $\beta^{k_{1}^{*}}_{1}=\alpha_{1}\pm\epsilon_{1}$, and
$\beta^{k_{2}^{*}}_{2}=\alpha_{2}\pm\epsilon_{2}$, we get

$\displaystyle\mu(\beta^{k_{1}^{*}}_{1},\beta^{k_{2}^{*}}_{2})$
$\displaystyle=G\big{|}\mathrm{sinc}\big{(}\pm
K_{x}\pi\epsilon_{1}\big{)}\mathrm{sinc}\big{(}\pm
K_{y}\pi\epsilon_{2}\big{)}\big{|}^{2}+\sigma^{2}.$ (21)

As $\mathrm{sinc}(-x)=\mathrm{sinc}(x)$, the difference between (20) and (21)
is given by

$\displaystyle\big{|}\mu(\alpha_{1},\alpha_{2})-\mu(\beta^{k_{1}^{*}}_{1},\beta^{k_{2}^{*}}_{2})\big{|}$
$\displaystyle=G\big{[}1-\big{|}\mathrm{sinc}\big{(}K_{x}\pi\epsilon_{1}\big{)}\mathrm{sinc}\big{(}K_{y}\pi\epsilon_{2}\big{)}\big{|}^{2}\big{]}.$
(22)

The worst case can happen when $\mu_{1}(\beta^{k}_{1})$ is the same for the
two discrete values in the central lobe. This can be possible as the two
points will lie on opposite sides of $\alpha_{1}$. Therefore, this worst case
scenario would happen when $\epsilon_{1}=\frac{1}{2K_{x}}$. Thereby, if we
consider any $\epsilon_{1}\in\big{[}0,\frac{1}{2K_{x}}\big{)}$, then

$\displaystyle\big{|}\mathrm{sinc}\big{(}K_{x}\pi(\alpha_{1}-\beta^{k_{1}^{*}}_{1}\big{)}\big{|}\geq\big{|}\mathrm{sinc}\big{(}\pi/2\big{)}\big{|}=2/\pi.$
(23)

Similarly, the worst case scenario of $\mu_{2}(\beta^{k}_{2})$ would happen
when $\epsilon_{2}=\frac{1}{2K_{y}}$, and, thereby for any
$\epsilon_{2}\in\big{[}0,\frac{1}{2K_{y}}\big{)}$, we get

$\displaystyle\big{|}\mathrm{sinc}\big{(}K_{y}\pi(\alpha_{2}-\beta^{k_{2}^{*}}_{2}\big{)}\big{|}=\big{|}\mathrm{sinc}\big{(}K_{y}\pi\epsilon_{2}\big{)}\big{|}\geq
2/\pi.$ (24)

Hence, by applying (23) an (24) in (IX-B), for
$0\leq\epsilon_{1}<\frac{1}{2K_{x}}$ and $0\leq\epsilon_{2}<\frac{1}{2K_{y}}$,
we get the bound in (11). ∎

###  IX-C Proof of Theorem 1

###### Proof.

HoloBeam divides $n$ pilot symbols into $n/2$ for each phase $i$ which is
further splitted into $L_{i}+1$ batches that satisfies (14), where
$L_{i}=\frac{\log_{2}K_{i}/3}{\log_{2}3/2}$ and outputs the phase-shift
parameter $\beta^{\hat{k}_{i}}_{i}$ for phases $i=1,2$. Let us denote

$\displaystyle
I:=\Pr\big{(}\beta^{\hat{k}_{1}}_{1}\neq\beta^{k_{1}^{*}}_{1}\big{)}\text{ and
}II:=\Pr\big{(}\beta^{\hat{k}_{2}}_{2}\neq\beta^{k_{2}^{*}}_{2}\big{)}.$ (25)

We will now upper bound the probability of error as,

$\displaystyle\Pr\bigg{(}\bigcup\limits_{i=1,2}\Big{\\{}\beta^{\hat{k}_{i}^{\pi}}_{i}\neq\beta^{*}_{i}\Big{\\}}\bigg{)}=I+II$
(26)

  * •

Upper Bound of I : As $\beta^{\hat{k}_{1}}_{1}$ can be eliminated in any phase
$l=1,\dots,L_{1}+1$, we get

$\displaystyle\Pr(\beta^{\hat{k}_{1}}_{1}\neq\beta^{k_{1}^{*}}_{1})$
$\displaystyle\leq\sum_{l=1}^{L_{1}+1}\Pr(\beta^{k_{1}^{*}}_{1}\text{ elim. in
}l).$ (27)

where $L_{1}=\frac{\log_{2}K_{1}/3}{\log_{2}3/2}$. In phase $l$, the following
cases can happen:

    1. 1.

Case 0:
$\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{B}}_{1},\dots,\beta^{k^{C}}_{1}\\}$, and
$\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}$ or $\hat{\mu}^{l}_{\beta^{k^{D}}_{1}}$ is
greater than both $\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}$ and
$\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}$, or $\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}$ or
$\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}$ is greater than both
$\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}$ and $\hat{\mu}^{l}_{\beta^{k^{D}}_{1}}$.

    2. 2.

Case 1:
$\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{A}}_{1},\dots,\beta^{k^{B}}_{1}\\}$, and
$\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}$ or $\hat{\mu}^{l}_{\beta^{k^{D}}_{1}}$ is
greater than both $\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}$ and
$\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}$.

    3. 3.

Case 2:
$\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{C}}_{1},\dots,\beta^{k^{D}}_{1}\\}$, and
$\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}$ or $\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}$ is
greater than both $\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}$ and
$\hat{\mu}^{l}_{\beta^{k^{D}}_{1}}$.

Note that $\beta^{k_{1}^{*}}_{1}$ will get eliminated if
$\beta^{k_{1}^{*}}_{1}$ falls either in Case 1 or Case 2 but will not get
eliminated if it falls in Case 0. Therefore, Case 0 is not favourable here.
Further note that Case 1 and Case 2 are symmetrical, illustrated in Fig. 7.
Therefore, to get the upper bound of the error probability, we will focus on
Cases 1 and 2, and without loss of generality, we consider Case 1.

$\beta^{k_{1}^{*}}_{1}$$\beta^{k_{1}^{*}}_{1}$$\beta^{k_{1}^{*}}_{1}$$\beta^{k^{A}}_{1}$$\beta^{k^{B}}_{1}$$\Delta^{1}_{B_{1},C_{1}}$$\beta^{k^{C}}_{1}$$\beta^{k^{D}}_{1}$Case
1Case 2Case 0 Figure 7: Different cases of elimination in any phase $l$.

$\displaystyle\Pr\big{(}\beta^{k_{1}^{*}}_{1}\text{ elim. in }l\big{)}$
$\displaystyle\leq\Pr\bigg{(}\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}>\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}\text{and}\,\,\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}|\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{A}}_{1},\dots,\beta^{k^{B}}_{1}\\}\bigg{)}$
$\displaystyle+\Pr\bigg{(}\hat{\mu}^{l}_{\beta^{k^{D}}_{1}}>\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}\text{and}\,\,\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}|\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{A}}_{1},\dots,\beta^{k^{B}}_{1}\\}\bigg{)}$
(28)

For Case 1, $\mu_{1}(\beta^{k^{C}}_{1})\geq\mu_{1}(\beta^{k^{D}}_{1})$ by
unimodality. Therefore, we can upper bound (28) as

$\displaystyle\Pr\big{(}\beta^{k_{1}^{*}}_{1}\text{ elim. in }l\big{)}$
$\displaystyle\leq
2\Pr\bigg{(}\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}>\hat{\mu}^{l}_{\beta^{k^{A}}_{1}}\text{and}\,\,\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}|\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{A}}_{1},..,\beta^{k^{B}}_{1}\\}\bigg{)},$
(29)

Now for Case 1, $\mu_{1}(\beta^{k^{B}}_{1})$ is always greater than
$\mu_{1}(\beta^{k^{C}}_{1})$, but $\mu_{1}(\beta^{k^{A}}_{1})$ may not be
greater than $\mu_{1}(\beta^{k^{C}}_{1})$. Then, we can further upper bound (•
‣ IX-C) as

$\displaystyle\Pr\big{(}\beta^{k_{1}^{*}}_{1}\text{ elim. in }l\big{)}$
$\displaystyle\leq
2\Pr\bigg{(}\hat{\mu}^{l}_{\beta^{k^{C}}_{1}}>\hat{\mu}^{l}_{\beta^{k^{B}}_{1}}|\beta^{k_{1}^{*}}_{1}\in\\{\beta^{k^{A}}_{1},\dots,\beta^{k^{B}}_{1}\\}\bigg{)}.$
(30)

We next upper bound the right-hand side of (• ‣ IX-C). We denote
$\chi_{\nu}^{2}(q)$ as a non-central Chi-squared distribution with $\nu$
degrees of freedom and non-centrality parameter $q$. As $r_{1}(\beta^{k}_{1})$
follows non-central Chi-squared distribution, according to [21, Lemma 2], we
denote

$\displaystyle\hat{\mu}_{B_{1}}$
$\displaystyle:=\frac{2m_{1}}{\sigma^{2}}\hat{\mu}_{\beta^{k^{B}}_{1}}\sim\chi^{2}_{2m_{1}}(m_{1}q_{B_{1}})$
(31) $\displaystyle\hat{\mu}_{C_{1}}$
$\displaystyle:=\frac{2m_{1}}{\sigma^{2}}\hat{\mu}_{\beta^{k^{C}}_{1}}\sim\chi^{2}_{2m_{1}}(m_{1}q_{C_{1}})$
(32) $\displaystyle\mu_{B_{1}}$
$\displaystyle:=\mu_{1}(\beta^{k^{B}}_{1})=\sigma^{2}+\frac{\sigma^{2}}{2}q_{B_{1}}$
(33) $\displaystyle\mu_{C_{1}}$
$\displaystyle:=\mu_{1}(\beta^{k^{C}}_{1})=\sigma^{2}+\frac{\sigma^{2}}{2}q_{C_{1}}$
(34)

where $m_{1}=\frac{N^{l}_{1}}{4}$,
$q_{B_{1}}=\frac{2\big{|}\sqrt{P}H^{ff}(\beta^{k^{B}}_{1},\beta^{0}_{2})\big{|}^{2}}{\sigma^{2}}$
and
$q_{C_{1}}=\frac{2\big{|}\sqrt{P}H^{ff}(\beta^{k^{C}}_{1},\beta^{0}_{2})\big{|}^{2}}{\sigma^{2}}$.
Now we will use the upper and lower tail bounds for non-central Chi-squared
distribution [40] to derive the upper bound in (• ‣ IX-C).

######  Lemma 2.

Let $X\sim\chi_{\nu}^{2}(q_{1})$, $q_{1}>0$ and $Y\sim\chi_{\nu}^{2}(q_{2})$,
$q_{2}>0$ and $q_{1}<q_{2}$. $X$ and $Y$ are independent. Then,

$\displaystyle\Pr(X>Y)\leq
2\exp\bigg{\\{}\frac{-\nu(\nu+q_{1})^{2}(q_{2}-q_{1})^{2}}{4(\nu+2q_{2})^{2}(2\nu+q_{1}+q_{2})^{2}}\bigg{\\}}$
(35)

###### Proof.

We will use Theorem 3 and 4 of [40] to prove the above lemma. Refer [40] for
the proof of these theorems.

$\displaystyle\Pr(X>Y)$
$\displaystyle=\Pr\bigg{(}\frac{X/\nu}{Y/\nu}>1\bigg{)}$ (36)

We denote $F=\frac{X/\nu}{Y/\nu}$ as doubly non-central F distrbution.
According to [40], we can write (36) as

$\displaystyle\Pr\big{(}F>1\big{)}\leq$
$\displaystyle\Pr\big{(}X>(\nu+q_{1})(1+\delta)\big{)}$
$\displaystyle+\Pr\big{(}Y<(\nu+q_{2})(1-\delta)\big{)}$ (37)

where $\delta=\frac{q_{2}-q_{1}}{2\nu+q_{1}+q_{2}}$ and $0<\delta<1$. By [40,
Thm. 3], we obtain

$\displaystyle\Pr$ $\displaystyle\big{(}X>(\nu+q_{1})(1+\delta)\big{)}$
$\displaystyle\leq\exp\bigg{\\{}\frac{-\nu(\nu+q_{1})^{2}\delta^{2}}{4(\nu+2q_{1})(\nu+2q_{1}+(\nu+q_{1})\delta)}\bigg{\\}}$
(38)

By [40, Thm. 4] and $q_{1}<q_{2}$, we obtain

$\displaystyle\Pr\big{(}Y<(\nu+q_{2})(1-\delta)\big{)}\leq\exp\bigg{\\{}\frac{-\nu(\nu+q_{1})^{2}\delta^{2}}{4(\nu+2q_{2})^{2}}\bigg{\\}}.$
(39)

Applying $\nu,q_{1},q_{2}>0$ and $q_{1}<q_{2}$, we obtain

$\displaystyle\big{(}\nu+2q_{2}\big{)}^{2}>(\nu+2q_{1})\big{(}\nu+2q_{1}+(\nu+q_{1})\delta\big{)}.$
(40)

Applying (40) in (• ‣ IX-C), we obtain

$\displaystyle\Pr\big{(}X>(\nu+q_{1})(1+\delta)\big{)}\leq\exp\bigg{\\{}\frac{-\nu(\nu+q_{1})^{2}\delta^{2}}{4(\nu+2q_{2})^{2}}\bigg{\\}}.$
(41)

Applying (41) and (39) in (37) we get (35). ∎

For our case
$\nu=\frac{N^{l}_{1}}{2},q_{1}=\frac{N^{l}_{1}}{4}q_{C_{1}},q_{2}=\frac{N^{l}_{1}}{4}q_{B_{1}}$,
and
$\Delta^{l}_{B_{1},C_{1}}=\mu_{B_{1}}-\mu_{C_{1}}=\frac{\sigma^{2}}{2}(q_{B_{1}}-q_{C_{1}})$.
Applying these facts and Lemma 2 in (• ‣ IX-C), we obtain

$\displaystyle\Pr\big{(}\beta^{k_{1}^{*}}_{1}\text{ elim. in }l\big{)}$
$\displaystyle\leq
4\exp\bigg{\\{}\frac{-N^{l}_{1}(\Delta^{l}_{B_{1},C_{1}})^{2}(\mu_{C_{1}})^{2}}{8(2\mu_{B_{1}}-\sigma^{2})^{2}(\mu_{B_{1}}+\mu_{C_{1}})^{2}}\bigg{\\}}.$
(42)

Using the value of $G$, $\forall k\in\\{1,2,\dots,K_{i}\\}$ for $i=1,2$ the
mean RSS can be bounded as

$\displaystyle\sigma^{2}\leq\mu_{i}(\beta^{k}_{i})\leq G+\sigma^{2}.$ (43)

Applying (43) in (42), we obtain

$\displaystyle\Pr\big{(}\beta^{k_{1}^{*}}_{1}\text{ elim. in }l\big{)}\leq
4\exp\bigg{\\{}-\frac{N^{l}_{1}(\Delta^{l}_{B_{1},C_{1}})^{2}}{32\sigma^{4}(1+3G/\sigma^{2})^{4}}\bigg{\\}}.$
(44)

For case 1, $\Delta^{l}_{B_{1},C_{1}}>0$ for the unimodal structure between
$\mu_{B_{1}}$ and $\mu_{C_{1}}$. We define $\Delta_{1}=\min\limits_{2\leq
k\leq K_{1}-1}\big{|}\mu_{1}(\beta^{k}_{1})-\mu_{1}(\beta^{k-1}_{1})\big{|}$.
By the fact that there are at least $j_{l}/3$ parameters between
$\beta^{k^{B}}_{1}$ and $\beta^{k^{C}}_{1}$, we have
$\Delta^{l}_{B_{1},C_{1}}\geq(j_{l}/3)\Delta_{1}$. Thus from (44) we get

$\displaystyle\Pr(\beta^{k_{1}^{*}}_{1}\text{ elim. in }l)\leq
4\exp\bigg{\\{}\frac{-N^{l}_{1}\big{(}j_{l}\Delta_{1}\big{)}^{2}}{288\sigma^{4}(1+3G/\sigma^{2})^{4}}\bigg{\\}}.$
(45)

Using $j_{l}=\left(2/3\right)^{l}K$ in (45), we can find the probability of
the best value is eliminated in batches 1, 2, $L_{1}+1$, and the rest of the
batches separately. Using (13) and (15) for batch 1 and 2, we have

$\displaystyle\Pr($ $\displaystyle\beta^{k_{1}^{*}}_{1}\text{ elim. in
}1\&2)\leq
4\exp{\left\\{-\frac{nK_{1}\Delta_{1}^{2}}{576\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}}$
$\displaystyle+4\exp\left\\{-\frac{nK_{1}\Delta_{1}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}.$
$\displaystyle\leq
8\exp\left\\{-\frac{nK_{1}\Delta_{1}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}.$
(46)

For $L_{1}+1$ where the best value is selected among three values and each
value is sampled $n/18$ times, we get

$\displaystyle\Pr(\beta^{k_{1}^{*}}_{1}\text{ elim. in batch }L_{1}+1)$
$\displaystyle\leq
4\exp\left\\{-\frac{n\Delta_{1}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}$
(47)

By (45), the error probability for remaining phases is

$\displaystyle\Pr(\beta^{k_{1}^{*}}_{1}\text{ elim. in batch 3 to batch
$L_{1}$})$ $\displaystyle\leq
4\sum_{l=3}^{L_{1}}\exp\left\\{\frac{-n(K_{1})^{2}\Delta_{1}^{2}}{576\sigma^{4}(1+3G/\sigma^{2})^{4}}\frac{2^{L_{1}-l+1}}{3^{L_{1}-l+2}}\left(\frac{2}{3}\right)^{2l}\right\\}$
$\displaystyle\leq
4(L_{1}-2)\exp\left\\{-\frac{n\Delta_{1}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}.$
(48)

By (• ‣ IX-C) and (• ‣ IX-C), the upper bound is

$\displaystyle\Pr(\beta^{\hat{k}_{1}}_{1}\neq\beta^{k_{1}^{*}}_{1})\leq
8\exp\left\\{-\frac{nK_{1}\Delta_{1}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}$
$\displaystyle+4(L_{1}-1)\exp\left\\{-\frac{n\Delta_{1}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}.$
(49)

  * •

Upper Bound of II : We have $L_{2}=\frac{\log_{2}K_{2}/3}{\log_{2}3/2}$.
Following the same lines of proof from (27)-(• ‣ IX-C), we obtain

$\displaystyle\Pr(\beta^{\hat{k}_{2}}_{2}\neq\beta^{k_{2}^{*}}_{2})\leq\sum_{l=1}^{L_{2}+1}\Pr(\beta^{k_{2}^{*}}_{2}\text{
elim. in }l).$ $\displaystyle\leq
2\sum_{l=1}^{L_{2}+1}\Pr\bigg{(}\hat{\mu}^{l}_{\beta^{k^{C}}_{2}}>\hat{\mu}^{l}_{\beta^{k^{B}}_{2}}|\beta^{k_{2}^{*}}_{2}\in\\{\beta^{k^{A}}_{2},\dots,\beta^{k^{B}}_{2}\\}\bigg{)}.$
(50)

We next upper bound the right-hand side of (• ‣ IX-C). According to [21, Lemma
2],

$\displaystyle\hat{\mu}_{B_{2}}$
$\displaystyle:=\frac{2m_{2}}{\sigma^{2}}\hat{\mu}_{\beta^{k^{B}}_{2}}\sim\chi^{2}_{2m_{2}}(m_{2}q_{B_{2}})$
(51) $\displaystyle\hat{\mu}_{C_{2}}$
$\displaystyle:=\frac{2m_{2}}{\sigma^{2}}\hat{\mu}_{\beta^{k^{C}}_{2}}\sim\chi^{2}_{2m_{2}}(m_{2}q_{C_{2}})$
(52) $\displaystyle\mu_{B_{2}}$
$\displaystyle:=\mu_{2}(\beta^{k^{B}}_{2})=\sigma^{2}+\frac{\sigma^{2}}{2}q_{B_{2}}$
(53) $\displaystyle\mu_{C_{2}}$
$\displaystyle:=\mu_{2}(\beta^{k^{C}}_{2})=\sigma^{2}+\frac{\sigma^{2}}{2}q_{C_{2}}$
(54)

where $m_{2}=\frac{N^{l}_{2}}{4}$,
$q_{B_{2}}=\frac{2\big{|}\sqrt{P}H^{ff}(\beta^{\hat{k}_{L_{1}+1}}_{1},\beta^{k^{B}}_{2})\big{|}^{2}}{\sigma^{2}}$
and
$q_{C_{2}}=\frac{2\big{|}\sqrt{P}H^{ff}(\beta^{\hat{k}_{L_{1}+1}}_{1},\beta^{k^{C}}_{2})\big{|}^{2}}{\sigma^{2}}$.
Furthermore, we denote

$\displaystyle\Delta^{l}_{B_{2},C_{2}}=\mu_{B_{2}}-\mu_{C_{2}}>0,$
$\displaystyle\Delta_{2}=\min\limits_{2\leq k\leq
K_{2}-1}\big{|}\mu_{2}(\beta^{k}_{2})-\mu_{2}(\beta^{k-1}_{2})\big{|},$

where $\Delta^{l}_{B_{2},C_{2}}\geq(j_{l}/3)\Delta_{2}$. Using these facts in
the following lines of proof from (35)-(• ‣ IX-C), we obtain

$\displaystyle\Pr(\beta^{\hat{k}_{2}}_{2}\neq\beta^{k_{2}^{*}}_{2})\leq
8\exp\left\\{-\frac{nK_{2}\Delta_{2}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}$
$\displaystyle+4(L_{2}-1)\exp\left\\{-\frac{n\Delta_{2}^{2}}{1296\sigma^{4}(1+3G/\sigma^{2})^{4}}\right\\}.$
(55)

Combining (49) and (55), we obtain the bound in (1).∎

## References

  * [1] Z. Wan, Z. Gao, F. Gao, M. Di Renzo, and M.-S. Alouini, “Terahertz Massive MIMO with Holographic Reconfigurable Intelligent Surfaces,” _IEEE Transactions on Communications_ , 2021.
  * [2] V. Jamali, A. M. Tulino, G. Fischer, R. R. Müller, and R. Schober, “Intelligent Surface-Aided Transmitter Architectures for Millimeter-Wave Ultra Massive MIMO Systems,” _IEEE Open Journal of the Communications Society_ , vol. 2, pp. 144–167, 2020.
  * [3] E. G. Larsson, O. Edfors, F. Tufvesson, and T. L. Marzetta, “Massive MIMO for next generation wireless systems,” _IEEE communications magazine_ , vol. 52, no. 2, pp. 186–195, 2014.
  * [4] Q. Wu and R. Zhang, “Intelligent Reflecting Surface Enhanced Wireless Network via Joint Active and Passive Beamforming,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 11, pp. 5394–5409, 2019.
  * [5] C. Huang, S. Hu, G. C. Alexandropoulos, A. Zappone, C. Yuen, R. Zhang, M. Di Renzo, and M. Debbah, “Holographic MIMO Surfaces for 6G Wireless Networks: Opportunities, Challenges, and Trends,” _IEEE Wireless Communications_ , vol. 27, no. 5, pp. 118–125, 2020.
  * [6] L. Huang, S. Zhang, and T. Zentgraf, “Metasurface holography: from fundamentals to applications,” _Nanophotonics_ , vol. 7, no. 6, pp. 1169–1190, 2018.
  * [7] S. Hu, F. Rusek, and O. Edfors, “Beyond Massive MIMO: The Potential of Data Transmission With Large Intelligent Surfaces,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 10, pp. 2746–2758, 2018.
  * [8] I. Yoo and D. R. Smith, “Holographic Metasurface Antennas for Uplink Massive MIMO Systems,” _arXiv preprint arXiv:2108.12513_ , 2021.
  * [9] H. Zhang, N. Shlezinger, F. Guidi, D. Dardari, M. F. Imani, and Y. C. Eldar, “Beam Focusing for Near-Field Multiuser MIMO Communications,” _IEEE Transactions on Wireless Communications_ , 2022.
  * [10] Ö. T. Demir, E. Björnson, and L. Sanguinetti, “Channel Modeling and Channel Estimation for Holographic Massive MIMO With Planar Arrays,” _IEEE Wireless Communications Letters_ , vol. 11, no. 5, pp. 997–1001, 2022\.
  * [11] M. Ghermezcheshmeh and N. Zlatanov, “Parametric Channel Estimation for LoS Dominated Holographic Massive MIMO Systems,” _IEEE Access_ , 2023.
  * [12] D. Ghosh, H. Rahman, M. K. Hanawal, and N. Zlatanov, “UB3: Best Beam Identification in Millimeter Wave Systems via Pure Exploration Unimodal Bandits,” _arXiv preprint arXiv:2301.03456_ , 2022.
  * [13] F. Dai and J. Wu, “Efficient broadcasting in ad hoc wireless networks using directional antennas,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 17, no. 4, pp. 335–347, 2006.
  * [14] Z. Xiao, T. He, P. Xia, and X.-G. Xia, “Hierarchical Codebook Design for Beamforming Training in Millimeter-Wave Communication,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 5, pp. 3380–3392, 2016\.
  * [15] K. Chen and C. Qi, “Beam Training Based on Dynamic Hierarchical Codebook for Millimeter Wave Massive MIMO,” _IEEE Communications Letters_ , vol. 23, no. 1, pp. 132–135, 2018.
  * [16] J. Zhang, Y. Huang, Q. Shi, J. Wang, and L. Yang, “Codebook Design for Beam Alignment in Millimeter Wave Communication Systems,” _IEEE Transactions on Communications_ , vol. 65, no. 11, pp. 4980–4995, 2017.
  * [17] Y. Peng, Y. Li, and P. Wang, “An Enhanced Channel Estimation Method for Millimeter Wave Systems With Massive Antenna Arrays,” _IEEE Communications Letters_ , vol. 19, no. 9, pp. 1592–1595, 2015.
  * [18] C.-R. Tsai, Y.-H. Liu, and A.-Y. Wu, “Efficient Compressive Channel Estimation for Millimeter-Wave Large-Scale Antenna Systems,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 9, pp. 2414–2428, 2018.
  * [19] Ö. T. Demir, E. Björnson, and L. Sanguinetti, “Channel Modeling and Channel Estimation for Holographic Massive MIMO With Planar Arrays,” _IEEE Wireless Communications Letters_ , vol. 11, no. 5, pp. 997–1001, 2022\.
  * [20] J. An, C. Yuen, C. Huang, M. Debbah, H. V. Poor, and L. Hanzo, “A Tutorial on Holographic MIMO Communications—Part I: Channel Modeling and Channel Estimation,” _IEEE Communications Letters_ , 2023.
  * [21] D. Ghosh, M. K. Hanawal, and N. Zlatanov, “Learning Optimal Phase-Shifts of Holographic Metasurface Transceivers,” _arXiv preprint arXiv:2301.03371_ , 2022.
  * [22] M. Hashemi, A. Sabharwal, C. Emre Koksal, and N. B. Shroff, “Efficient Beam Alignment in Millimeter Wave Systems Using Contextual Bandits,” in _IEEE Conference on Computer Communications (INFOCOM)_ , 2018, pp. 2393–2401.
  * [23] I. Aykin, B. Akgun, M. Feng, and M. Krunz, “MAMBA: A Multi-armed Bandit Framework for Beam Tracking in Millimeter-wave Systems,” in _IEEE INFOCOM 2020 - IEEE Conference on Computer Communications_ , 2020, pp. 1469–1478.
  * [24] W. Wu, N. Cheng, N. Zhang, P. Yang, W. Zhuang, and X. Shen, “Fast mmwave Beam Alignment via Correlated Bandit Learning,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 12, pp. 5894–5908, 2019.
  * [25] N. Blinn, J. Boerger, and M. Bloch, “mmWave Beam Steering with Hierarchical Optimal Sampling for Unimodal Bandits,” in _ICC 2021-IEEE International Conference on Communications_. IEEE, 2021, pp. 1–6.
  * [26] Y. Wei, Z. Zhong, and V. Y. Tan, “Fast Beam Alignment via Pure Exploration in Multi-Armed Bandits,” _IEEE Transactions on Wireless Communications_ , 2022\.
  * [27] N. Blinn and M. Bloch, “mmWave Beam Alignment using Hierarchical Codebooks and Successive Subtree Elimination,” _arXiv preprint arXiv:2209.02896_ , 2022.
  * [28] J.-Y. Audibert, S. Bubeck, and R. Munos, “Best Arm Identification in Multi-Armed Bandits,” in _COLT_. Citeseer, 2010, pp. 41–53.
  * [29] E. Kaufmann, O. Cappé, and A. Garivier, “On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models,” _Joural of Machine Learning Research_ , vol. 17, no. 1, p. 1–42, January 2016.
  * [30] M. R. Akdeniz, Y. Liu, M. K. Samimi, S. Sun, S. Rangan, T. S. Rappaport, and E. Erkip, “Millimeter Wave Channel Modeling and Cellular Capacity Evaluation,” _IEEE journal on selected areas in communications_ , vol. 32, no. 6, pp. 1164–1179, 2014.
  * [31] ——, “Millimeter Wave Channel Modeling and Cellular Capacity Evaluation,” _IEEE journal on selected areas in communications_ , vol. 32, no. 6, pp. 1164–1179, 2014.
  * [32] W. Wang and W. Zhang, “Joint Beam Training and Positioning for Intelligent Reflecting Surfaces Assisted Millimeter Wave Communications,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 10, pp. 6282–6297, 2021\.
  * [33] S. W. Ellingson, “Path Loss in Reconfigurable Intelligent Surface-Enabled Channels,” in _2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)_. IEEE, 2021, pp. 829–835.
  * [34] K. T. Selvan and R. Janaswamy, “Fraunhofer and Fresnel Distances: Unified derivation for aperture antennas,” _IEEE Antennas and Propagation Magazine_ , vol. 59, no. 4, pp. 12–15, 2017.
  * [35] M. Najafi, V. Jamali, R. Schober, and H. V. Poor, “Physics-Based Modeling and Scalable Optimization of Large Intelligent Reflecting Surfaces,” _IEEE Transactions on Communications_ , vol. 69, no. 4, pp. 2673–2691, 2020.
  * [36] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone, “PAC Subset Selection in Stochastic Multi-armed Bandits,” in _Proceedings of the 29th International Coference on International Conference on Machine Learning (ICML)_. Madison, WI, USA: Omnipress, 2012, p. 227–234.
  * [37] A. Carpentier and A. Locatelli, “Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem,” in _Conference on Learning Theory_. PMLR, 2016, pp. 590–604.
  * [38] Z. Karnin, T. Koren, and O. Somekh, “Almost Optimal Exploration in Multi-Armed Bandits,” in _International Conference on Machine Learning_. PMLR, 2013, pp. 1238–1246.
  * [39] J. Y. Yu and S. Mannor, “Unimodal Bandits,” in _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , 2011, p. 41–48.
  * [40] M. Ghosh, “Exponential Tail Bounds for Chisquared Random Variables,” _Journal of Statistical Theory and Practice_ , vol. 15, no. 2, p. 35, 2021\.