# mmWave Beam Alignment using Hierarchical Codebooks and Successive Subtree
Elimination

Nathan Blinn, 111This work has been submitted to the IEEE for possible
publication. Copyright may be transferred without notice, after which this
version may no longer be accessible. and Matthieu Bloch

###### Abstract

We propose a best arm identification multi-armed bandit algorithm in the
fixed-confidence setting for mmWave beam alignment initial access called
Successive Subtree Elimination (SSE). The algorithm performance approaches
that of state-of-the-art Bayesian algorithms at a fraction of the complexity
and without requiring channel state information. The algorithm simultaneously
exploits the benefits of hierarchical codebooks and the approximate
unimodality of rewards to achieve fast beam steering, in a sense that we
precisely define to provide fair comparison with existing algorithms. We
derive a closed-form sample complexity, which enables tuning of design
parameters. We also perform extensive simulations over slow fading channels to
demonstrate the appealing performance versus complexity trade-off struck by
the algorithm across a wide range of channel conditions.

###### Index Terms:

5G, 6G, millimeter-Wave, Internet of Things, Hybrid, Beamforming, Multi-Armed
Bandits.

##  I Introduction

Operation at millimeter-Wave (mmWave) (30-300 GHz) allows the use of wider
signal bandwidth in Internet of Things (IoT), 5G, and 6G technologies [18].
However, signals suffer from significant path loss attenuation and outages,
which can only be overcome with highly directional beams. Fortunately, the
small aperture of antenna elements at millimeter wavelengths allows the
integration of massive Multiple-Input Multiple-Output (MIMO) arrays in compact
devices. In particular, Hybrid Analog-Digital (HAD) MIMO architectures, which
only require a small number of Radio Frequency (RF) paths compared to the
number of antenna elements, have gained traction in beamforming applications
[2, 25]. To make effective use of directional beams, communicating terminals
must first steer their respective beams to spatially align. The current beam
sweep method proposed in the 5G standard [14, 13] consists of an exhaustive
search over all possible directions, in which the number of required channel
observations for alignment scales linearly with the number of directions.
Several classes of algorithms have subsequently been developed to improve upon
this scaling, with the objective of achieving faster initial alignment. The
classes are summarized in Table I and discussed next. Each class offers
different trade-offs between the complexity of the arm selection policy, the
overall number of physical sample measurements required, and performance.

TABLE I: Comparison of beam alignment algorithms. Reference |  Algorithm Class |  Codebook |  Theoretical Guarantees |  Complexity per sample
---|---|---|---|---
HOSUB [6] |  MAB |  Hierarchical |  None |  Low/ Medium
HPM [9] |  Bayesian |  Hierarchical |  Correctness, Sample Complexity |  High/Low
UBA [16] |  MAB |  Pencil Beams |  Regret |  Very Low/ NA
HBA[33] |  MAB |  Pencil Beams |  Regret |  Medium/ NA
[29] |  DNN |  None |  None |  Very High/ Very Low
FastLink [17] |  CS |  Multi-Directional |  Correctness |  Medium/ Medium
2PHTS [31] |  MAB |  Hierarchical |  Correctness, Sample Complexity |  High/ Medium
Present Work |  MAB |  Hierarchical |  Correctness, Sample Complexity |  Low/ Medium

A first class of algorithms uses Bayesian decision-making and leverages
hierarchical beamforming codebooks [34]. A hierarchical beamforming codebook
consists of a set of phase shifts that not only creates pencil beams steering
in precise directions but also aggregates the pencil beams into broader beams.
Examples following the hierarchical codebook approach include [2, 9, 6, 31].
In particular, [9] proposes the Hierarchical Posterior Matching (HPM)
algorithm that exploits full Channel State Information (CSI) to update the
posterior probabilities of the incoming beam direction. The hierarchical
structure of the codebook comes into play by choosing narrower beams as the
posteriors identify more precisely the likely beam direction. This approach
optimally exploits the beamforming codebook by guaranteeing the correct beam
is chosen with high probability based on the posteriors, but requires
substantial channel knowledge. [1] expands on [9] by addressing a more
practical scenario in which both the fading coefficients and noise variance
are unknown.

A second class of algorithms proposes a Deep Neural Network (DNN) approach to
assign beamformer weights [29], instead of relying on a predefined
hierarchical codebooks [2, 9]. The approach is “codebook-free”, so that unlike
[2, 9, 6, 31] the overall performance is not affected by the quality of the
hierarchical codebook. The DNN-learned policy takes the posteriors as inputs,
as computed in [9]. The numerical results show that the DNN performance with
unknown fading coefficient matches the performance of HPM in [9] with a known
coefficient. Both the DNN-policy in [29] and the Bayesian policy in [9]
require overhead computation of posteriors or a forward pass through the DNN,
respectively, but require few channel observations.

A third class of algorithms, which attempts to circumvent the computational
complexity incurred by Bayesian and DNN approaches, is compressed-sensing
techniques. This approach exploits the sparsity associated with mmWave
channels to quickly find the direction of incoming signal. The sparsity comes
from the assumption that mmWave signals only travel along a few paths and
attenuate quickly [26]. To infer user location, the approach in [28] generates
random peaks in multiple beam patterns. The approach does not take the phase
information into consideration and relies only on Received Signal Strength
(RSS). [28] acknowledges the inability to predict multi-path, but claims other
mechanisms can compensate. Similarly, in [17], random hashings of beams with
discrete pointing angles combine to create beamforming patterns that contain
multiple directions. [17] shows analytically and experimentally that the
increased number of hashings increases the probability of correct detection
and the correct direction can be recovered in logarithmic time. The example in
[24] exploits sparsity by formulating the beam alignment task as a sparse
encoding and phaseless decoding problem. This particular algorithm exploits a
HAD beamforming approach, different from other sparsity exploiting approaches.
Finally, the FastLink algorithm from [5] is a Compressed Sensing (CS) method
that uses three-dimensional peak finding to find the optimal direction in time
proportional to the logarithm of the total number of directions, and is
demonstrated both in a numerical simulation as well as a mmWave testbed.

A fourth class of algorithms exploits the conceptual analogy between beam
steering and optimal arm play in a Multi-Armed Bandit (MAB) problem to achieve
low-complexity. Every beam direction corresponds to a set of phase shifts
applied to array elements and can be viewed as an arm to pull in a MAB
algorithm. The RSS acquired with every choice of beam direction can then be
used as a reward and exploited by a MAB exploration strategy as in [15], which
uses many of the regret minimizing algorithms from [4]. The algorithms in [4]
are generally based around the approach of playing the arm with the highest
estimated Upper-Confidence Bound (UCB) of the mean reward. This is a core
methodology in MAB algorithms that yields sublinear regret over the number of
arms pulled. Alternatively, one can use RSS information a priori [30], in
which case MAB algorithms are used to make fine adjustments based on the
information provided. A representative example is Unimodal Beam Alignment
(UBA) [16], which exploits unimodality, i.e., the existence of monotonically
increasing rewards when moving towards the direction of maximum reward. In
this case, a User Equipment (UE) and Base Station (BS) beam pair acts as an
individual arm and the unimodality of the reward structure, [10, 35], allows
one to achieve a regret that accumulates independent of the number of arms.
Experimental results in [16] show that the mutual alignment of both users
exhibits an approximate unimodal structure. Few reward structures are
perfectly unimodal and the algorithm in [16, 10] that plays only samples local
to the current empirical maximum easily gets stuck in local maxima. To address
this issue, [6] adapts Optimal Sampling for Unimodal Bandits (OSUB) [10] for
use with a hierarchical codebook. The numerical simulations show a substantial
reduction in the number of samples required, with robustness to multi-path
effects but no theoretical guarantees. [36] combines Thompson Sampling (TS)
together with the grouping of arms into clusters of beam pointing directions
to induce a hierarchical approach, demonstrating a reduction in number of
overall samples required. The Hierarchical Beam Alignment (HBA) algorithm [33]
adapts the X-arm bandit algorithm [8], but the hierarchical approach of HBA
only indirectly exploits the hierarchical structure and still uses pencil
beams to acquire reward signals. The algorithm also requires the fine tuning
of hyper-parameters and theoretical guarantees are only provided in the form
of regret bounds. The Two Phase Heteroscedastic Track-and-Stop (2PHTS)
algorithm in [31] uses grouped sums of arms as ”super-arms”, which are broader
beams, to create a two-level hierarchical beamformer and uses the arm
selection policy of [12, 22].

Overall, the MAB approach allows one to develop low-complexity solutions to
the initial access beam alignment problem for mmWave systems, at the expense
of requiring more samples than Bayesian approaches. Apart from [6, 31], all of
the mentioned works employing the MAB framework optimize exploration and
exploitation based on regret minimization as opposed to best arm
identification or pure exploration [11, 7]. In practice, one wants to select a
beam and terminate the search phase to begin communication, so that one would
be interested in algorithms designed to terminate once a certain level of
confidence is reached, known as the fixed confidence setting [21, 12] or
terminating after a fixed number of observations, known as the _fixed budget_
setting.

Our main contributions are as follows. We propose two low-complexity
algorithms, Binary SSE and General SSE, that efficiently exploit the reward
structure in the fixed confidence setting. We show that the algorithms are
both $\delta$\- probably approximately correct (PAC) and derive a closed-form
upper bound on the sample complexity. Finally, we provide extensive numerical
simulations comparing the two SSE algorithms, HPM [9], HBA [33], and an
exhaustive search method with pencil beams, showing the benefits of our
algorithms and validating the sample complexity analysis.

The rest of the paper is organized as follows. We present the channel model
used and the beamforming codebook associated with channel observations in
Section II. In addition, we describe the modeling assumptions for the
structure of the RSS. Next, we introduce the two proposed algorithms in
Section III and analyze to prove correctness and sample complexity. We present
numerical simulations in Section IV along with comparisons to theoretical
guarantees. A conclusion in Section V summarizes findings and discusses future
directions for this work.

##  II Problem Setup

Following the setup from [9], at each discrete time step $t\in\mathbb{N}$ a
beacon signal, $\mathbf{s}_{u}(t)\in\mathbb{C}^{I\times 1}$, consisting of $I$
samples at finer time or frequency granularity, is sent by a UE
$u\in\left\\{{1,\dots,U}\right\\}$ to a BS. Each beacon consists of time or
frequency symbols similar to that of the Sounding Reference Signal (SRS) used
in the current 5G standard [14], that is unique to one UE. Beacons from
distinct users are assumed orthonormal to each other, i.e.,
$\mathbf{s}^{H}_{u^{\prime}}(t)\mathbf{s}_{u}(t)=1$ if $u=u^{\prime}$ and zero
otherwise, which allows us to focus on the alignment of the BS with a single
UE and to drop the index $u$ from our notation. We also assume that a UE forms
a single beam, which allows us to model the UE array as a single virtual
antenna, and that the BS observes the beam after propagation using an
$M$-element uniform linear array. A beacon signal propagates over $K$ paths,
each path $k\in\left\\{{1,\dots,K}\right\\}$ characterized by the received
power $P_{k}$, the Angle of Arrival (AoA)
$\theta_{k}\in\Theta\triangleq[\theta_{\textnormal{min}},\theta_{\textnormal{max}}]\subseteq[0,2\pi)$,
and overall subject to a time-varying fading coefficient
$\alpha_{k}(t)\in\mathbb{C}$, governed by a Rician AR1 channel model [9]. The
received signal at the BS is given by

$\displaystyle\mathbf{z}(t)$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}(t)\sqrt{P_{k}}\mathbf{a}(\theta_{k})+\mathbf{n}(t),$
(1)

where

$\displaystyle\mathbf{a}(\theta_{k})\triangleq\frac{1}{\sqrt{M}}\begin{bmatrix}1&\exp\left(j\frac{2\pi
d}{\lambda}\cos(\theta_{k})\right)&\cdots&\exp\left(j\frac{2\pi
d(M-1)}{\lambda}\cos(\theta_{k})\right)\end{bmatrix}^{T},$ (2)

is the array response, $\lambda$ is the center frequency wavelength,
$d=\lambda/2$ is the element spacing of the array, and
$\mathbf{n}(t)\sim\mathcal{C}\mathcal{N}(0,\sigma^{2}\mathbf{I}_{M}$). The raw
Signal-to-Noise Ratio (SNR) of path $k$ is measured as $P_{k}/\sigma^{2}$. The
beamforming vector $\mathbf{w}\in\mathbb{C}^{M\times 1}$ consists of $M$ phase
delays applied to the BS antenna elements as

$\displaystyle y(t)$
$\displaystyle=\mathbf{w}^{H}\mathbf{z}(t)=\mathbf{w}^{H}\sum_{k=1}^{K}\alpha_{k}(t)\sqrt{P_{k}}\mathbf{a}(\theta_{k})+\mathbf{w}^{H}\mathbf{n}(t),$
(3)

where $\mathbf{w}^{H}\mathbf{n}(t)\sim\mathcal{C}\mathcal{N}(0,\sigma^{2})$ is
the receiver noise and $\mathbf{w}^{H}\mathbf{w}=1$. The beamforming vectors
are chosen from a predefined codebook, $\mathcal{W}$, that defines various
beamforming patterns, each with unique pointing directions within $\Theta$.
The objective of the initial alignment phase is to determine the beamforming
vector $\hat{\mathbf{w}}$ in the codebook such that

$\displaystyle\hat{\mathbf{w}}=\mathop{\text{argmin}}_{\mathbf{w}\in\mathcal{W}}{\left\|{\mathbf{w}-\mathbf{a}(\theta_{1})}\right\|},$
(4)

where $\theta_{1}$ is the dominant path AoA, using a sequential _policy_.
Specifically, we consider a MAB policy such that at each time step $t$, a
beamforming vector, $\mathbf{w}_{X(t)}$ is selected from the codebook and the
corresponding observation, $\left|y(t)\right|$, acts as a reward . In order to
use as few samples as possible to make a correct terminal selection with
probably at least $1-\delta$, we study the sample complexity in the _fixed
confidence_ setting [22, 12, 23] for best-arm identification [11, 3, 19]. The
number of samples required is interpreted as the metric of algorithm
_complexity_.

A _hierarchical_ beamforming codebook is one that contains both wide and
narrow beam patterns and in which the wide beam patterns aggregate the
directions defined by the narrow ones. In the rest of the paper, we adopt the
HAD beamforming codebook of [2], restricted as in [9] to a range of AoAs,
$\Theta$. This codebook, denoted $\mathcal{W}^{H}$, consists of $2(2^{H}-1)$
beamforming vectors $\left\\{{\mathbf{w}_{h,i}}\right\\}$,
$h\in\left\\{{1,\dots,H}\right\\}$, $i\in\left\\{{1,\dots,2^{h}}\right\\}$.
The range of AoA is initially split into two intervals and each subsequent
increment of $h$ corresponds to beams that bisect the previous one into
narrower beams as shown in Fig. 1. In particular, the beamforming vectors
$\mathbf{w}_{h+1,2i-1}$ and $\mathbf{w}_{h+1,2i}$ bisect the beamforming
pattern corresponding to vector $\mathbf{w}_{h,i}$.

(a) $h=1$ | (b) $h=2$ | (c) $h=3$
---|---|---
Figure 1: Beamforming patterns for the first three values of $h$ in
hierarchical codebook of [9] with $\theta_{\text{min}}=\pi/6$ $(30^{\circ})$
and $\theta_{\text{max}}=5\pi/6$ $(150^{\circ})$ for $120^{\circ}$ total
angular coverage.

The codebook construction induces a binary tree graph whose vertices $(h,i)$
organize the individual beamforming vectors $\mathbf{w}_{h,i}$ into levels
indicated by $h$. It is convenient to think of each beamforming pattern’s
beamwidth as corresponding to a region $\mathcal{P}_{h,i}\subset\Theta$ such
that $\mathcal{P}_{0,1}=\Theta$ and
$\mathcal{P}_{h,i}=\mathcal{P}_{h+1,2i-1}\cup\mathcal{P}_{h+1,2i}$, which is a
similar setup to [8]. Each beamforming pattern has an associated _gain_ ,
$g^{h-1}$, with its corresponding vector $\mathbf{w}_{h,i}$. The beams at
level $H$ provide the highest gain of any beams, but the narrowest beamwidth.
The steered direction of the beamforming pattern is defined as the midpoint

$\displaystyle\theta_{h,i}\triangleq\theta_{\textnormal{min}}+\frac{\theta_{\textnormal{max}}-\theta_{\textnormal{min}}}{2^{h+1}}(2i-1),$
(5)

as shown in Fig. 2. The narrower beams resulting from bisections of wider
beams correspond to the children vertices of $(h,i)$ denoted
$\mathcal{C}(h,i)=((h+1,2i-1),(h+1,2i))$.

Figure 2: Illustration of beamwidth coverage. Boxes denote regions
$\mathcal{P}_{h,i}$ and the dots indicate the midpoint vertices
$\theta_{h,i}$.

We define the mean-reward function generated by the RSS measurements of the
channel as

$\displaystyle
f(\mathcal{P}_{h,i})\triangleq{\mathbb{E}}{\left(\left|\mathbf{w}_{h,i}^{H}\mathbf{z}(t)\right|\right)}.$
(6)

######  Assumption 1.

For each $h$ there exists a unique beamforming vector $\mathbf{w}_{h,i^{*}}$
such that

$\displaystyle
f^{*}_{h}=f(\mathcal{P}_{h,i^{*}})=\max_{i\in\left\\{{1,\dots,2^{h}}\right\\}}f(\mathcal{P}_{h,i}),$
(7)

and for two consecutive levels of the codebook,

$\displaystyle\frac{f_{h+1}^{*}}{f_{h}^{*}}=g.$ (8)

The design of the hierarchical codebook enables the beamforming vector
$\mathbf{w}_{h,i}$ to operate on $\mathcal{P}_{h,i}$ to form an aggregate of
rewards $f(\mathcal{P}_{h+1,2i-1})$ and $f(\mathcal{P}_{h+1,2i})$. We denote
the difference between mean rewards at a particular level $h$ as

$\displaystyle\Delta_{h,i}\triangleq\begin{cases}f_{h}^{*}-f(\mathcal{P}_{h,i})&\textnormal{if
}i\neq i^{*},\\\ f_{h}^{*}-\max_{i\neq
i^{*}}f(\mathcal{P}_{h,i})&\textnormal{if }i=i^{*}.\end{cases}$ (9)

An illustration of the normalized mean-reward profile (RSS),
$f(\mathcal{P}_{h,i})$, for each level $h$ is shown in Fig. 3. This profile is
generated using the model in (3) by measuring the average RSS with a fixed
AoA, according to $\left|y(t)\right|$, with each beamforming vector in
$\mathcal{W}^{H}$. The dots are the discrete pointing directions
$\theta_{h,i}$ which measurements are taken, and at each $h$, one observes the
existence of a dominant maximum corresponding to $\mathbf{w}_{h,i^{*}}$. There
is a gain of $g\approx 1.25$ ($1$ dB) between $f_{h}^{*}$ and $f_{h+1}^{*}$,
hence we can reasonably conclude adherence to Assumption 1 for RSS
measurements.

Figure 3: Mean-rewards instance with one dominant path for a mmWave channel.

Some AoAs cause the beamforming vector $\mathbf{w}_{H,i^{*}}$ and other
vectors $\mathbf{w}_{H,i}$ to have very similar average RSS measurements.
These are generally the neighboring beamforming patterns corresponding to
$\mathbf{w}_{H,i^{*}\pm 1}$. To accomodate for these similar measurements, we
introduce the region

$\displaystyle\Theta_{\epsilon}\triangleq\left\\{{\mathcal{P}_{H,i}:f(\mathcal{P}_{H,i})\geqslant
f_{H}^{*}-\epsilon}\right\\},$ (10)

for $\epsilon\geqslant 0$. The beamforming vectors,
$\mathbf{w}_{H,i^{\epsilon}}$, with pointing directions
$\theta_{H,i^{\epsilon}}\in\Theta_{\epsilon}$ are called $\epsilon$-optimal,
and by definition, $\mathbf{w}_{H,i^{*}}$ is $\epsilon$-optimal. Section III
describes algorithms that incorporate $\epsilon$ into the stopping criteria
and terminate with a beamforming vector $\mathbf{w}_{H,i}$ that is
$\epsilon$-optimal. Similar to the structure of rewards in [35, 10, 16], we
make the following unimodality assumption about the induced reward structure.
Let $i_{h}\in\left\\{{1,\dots,2^{h}}\right\\}$ denote indices that
differentiate between indices $i$ at various levels, $h$.

######  Assumption 2.

(Unimodality) If $\mathcal{P}_{H,i^{\epsilon}}\in\Theta_{\epsilon}$ then there
exists a path $((1,i_{1}),(2,i_{2}),\dots,(H-1,i_{H-1}),(H,i^{\epsilon}))$
through the graph where

$\displaystyle\mathcal{P}_{H,i^{\epsilon}}\subset\mathcal{P}_{H-1,i_{H-1}}\subset\dots\subset\mathcal{P}_{2,i_{2}}\subset\mathcal{P}_{1,i_{1}}.$
(11)

For each region, the mean-reward functions satisfy

$\displaystyle
f(\mathcal{P}_{H,i^{\epsilon}})>f(\mathcal{P}_{H-1,i_{H-1}})>\dots>f(\mathcal{P}_{2,i_{2}})>f(\mathcal{P}_{1,i_{1}})$
(12)

and

$\displaystyle
g=\frac{f(\mathcal{P}_{H,i^{\epsilon}})}{f(\mathcal{P}_{H-1,i_{H-1}})}=\frac{f(\mathcal{P}_{H-1,i_{H-1}})}{f(\mathcal{P}_{H-2,i_{H-2}})}=\dots=\frac{f(\mathcal{P}_{2,i_{2}})}{f(\mathcal{P}_{1,i_{1}})}.$
(13)

From Assumption 2, $\epsilon$-optimality propagates to wider beams $h<H$ as
follows. At level $H$

$\displaystyle f(\mathcal{P}_{H,i^{\epsilon}})+\epsilon$
$\displaystyle\geqslant f_{H}^{*}=g^{H-h}f_{h}^{*},$ (14)

and for levels $h<H$

$\displaystyle f(\mathcal{P}_{h,i_{h}})+\epsilon_{h}$ $\displaystyle\geqslant
f_{h}^{*},$ (15)

where $\epsilon_{h}\triangleq g^{-(H-h)}\epsilon$. If the average reward
corresponding to $\mathbf{w}_{h,i}$ meets the criteria of (15) then it is
$\epsilon_{h}$-optimal. In a practical scenario, the parameter $\epsilon$
could be set to ensure that the beamforming pattern chosen has the AoA within
its $3$ dB beamwidth.

There are limitations to using hierarchical codebooks with channels that
contain severe multi-path elements. Let $\theta_{k}^{\prime}$ denote a path
such that

$\displaystyle\theta_{k}^{\prime}\in\left\\{{\theta_{k}:\theta_{k}\notin\mathcal{P}_{h,i^{\epsilon}}}\right\\}.$
(16)

In the case of several $\theta_{k}^{\prime}$ with similar angles, there could
be a case in which $f(\mathcal{P}_{h,i})\geqslant f_{h}^{*}$ as a result of
the beamforming vector aggregate observation. This would violate Assumption 2
since the beamforming vector corresponding to the dominant path, $\theta_{1}$,
requires the pointing angle
$\theta_{H,i^{*}}\in\mathcal{P}_{H,i^{*}}\subset\mathcal{P}_{h,i^{*}}$.
Fortunately, the sparsity and high path loss attenuation associated with
mmWave propagation [26] suggest that Assumption 2 holds in most situations.
Fig. 4 shows an example of such a reward profile. This profile is generated
similarly to Fig. 3, with the addition of fixed multi-path AoAs,
$\theta_{2},\dots,\theta_{K}$ with $10$ dB attenuation with respect to AoA
$\theta_{1}$. Strict adherence to Assumption 2, $f_{h}^{*}<f_{h+1}^{*}$ is
shown at each consecutive layer. However, $f_{1}^{*}$ and $f_{2}^{*}$ come
close to producing a violation of (12).

Figure 4: Mean-rewards instance with $K=5$ paths at $10$ dB (on average) down
from the dominant path [26].

##  III Successive Subtree Elimination (SSE) for mmWave Beam Alignment

We now describe algorithms that use the hierarchical codebook described in
Section II and efficiently exploit the induced reward structure. These
algorithms use the binary tree graph representation of each beamforming vector
$\mathbf{w}_{h,i}$, as a vertex $(h,i)$, to take RSS measurements at specified
levels $h$. The algorithms eliminate groups of leaf vertices (subtrees),
corresponding to the narrowest beams in variable quantity depending on the
level. We shall see that this process identifies the dominant path quickly and
efficiently explores the range of AoA.

Figure 5: Illustration of eliminated arms at each level for Binary SSE, hollow
nodes indicate the two arms in contention at a particular level and regions
grayed out denote the eliminated regions. Hollow vertices with an asterisk
indicate the arm selected at each level.

1 Input: $B$, $\epsilon$, $\delta$, and $H$;

2 Initialize: $t=1$, $\left\\{{\mathbf{w}_{h,i}}\right\\}$,
$U_{h,i}(t)=\infty$, $L_{h,i}(t)=-\infty$, $\hat{f}_{h,i}(t)=0$,
$N_{h,i}(t)=0$, for $1\leqslant h\leqslant H$ and $1\leqslant i\leqslant
2^{h}$;

3 Set: $I=0$

4 for  _$h=1,\dots,H$_ do

5 $t\leftarrow 1$;

6 $\mathcal{S}_{h}\leftarrow\mathcal{C}(h-1,I)$;

7 while  _$U_{h,u_{t}}(t)-L_{h,h_{t}}(t)\leqslant\epsilon$_ do

8 for  _$X(t)\in\mathcal{S}_{h}$_ do

9 Sample $X(t)$, observe $\left|y(t)\right|$;

10 Update $N_{X(t)}(t)$, $\hat{f}_{X(t)}(t)$, $U_{X(t)}(t)$, and
$L_{X(t)}(t)$;

11 $t\leftarrow t+1$;

12

13 end for

14 Update $h_{t}$ and $u_{t}$;

15

16 end while

17 $I\leftarrow h_{t}$;

18

19 end for

return $I$

Algorithm 1 Binary SSE

We require estimation with probability $1-\delta$ of the beamforming vector
$\mathbf{w}_{H,i^{*}}$, whose beam pointing angle most closely matches the AoA
according to (4). We achieve this performance using algorithms that, at levels
$h$, play beamforming vectors $\mathbf{w}_{h,i}$ viewed as arms against one
another in a MAB Best Arm Identification (BAI) fixed confidence setting,
whereupon the losing arms not selected have themselves and all of their
descendants eliminated. This is illustrated in Fig. 5 and the pseudocode for
the first algorithm called Binary SSE, is shown in Algorithm 1. At each time
step, we choose one of the arms in contention to sample, $X(t)$, and observe
the reward $\left|y(t)\right|$ according to lines 8-9. The mean rewards up to
time $T$ are estimated by the empirical mean

$\displaystyle\hat{f}_{h,i}(T)=\frac{1}{N_{h,i}(T)}\sum_{t=1}^{T}\left|y(t)\right|\mathds{1}\\!\left\\{X(t)=(h,i)\right\\},$
(17)

where

$\displaystyle
N_{h,i}(T)=\sum_{t=1}^{T}\mathds{1}\\!\left\\{X(t)=(h,i)\right\\},$ (18)

and are updated after sampling in line 10. To allow further generalization
later on, we let $\mathcal{S}_{h}$ denote the set of arms in contention at
level $h$, noting that, $\left|\mathcal{S}_{h}\right|=2$ for Binary SSE. The
total number of arms evaluated is
$N_{H}=\sum_{h}\left|\mathcal{S}_{h}\right|$, and $B>0$ is an estimate of the
reward variance. A confidence term and exploration rate

$\displaystyle
D_{h,i}(t)\triangleq\sqrt{\frac{B\beta(t,\delta)}{2N_{h,i}(t)}},$ (19)
$\displaystyle\beta(t,\delta)\triangleq\log\left(N_{H}\alpha_{1}t^{\alpha}/\delta\right),$
(20)

respectively, are used in the UCB and Lower-Confidence Bound (LCB) terms

$\displaystyle U_{h,i}(t)=\hat{f}_{h,i}(t)+D_{h,i}(t),$ (21) $\displaystyle
L_{h,i}(t)=\hat{f}_{h,i}(t)-D_{h,i}(t),$ (22)

respectively. Parameters are set to $\alpha=4$, $\alpha_{1}=5/4$ as in [21].
We also use the indices

$\displaystyle
h_{t}=\mathop{\text{argmax}}_{i:(h,i)\in\mathcal{S}_{h}}\hat{f}_{h,i}(t),$
(23) $\displaystyle
u_{t}=\mathop{\text{argmax}}_{{i:(h,i)\in\mathcal{S}_{h}},i\neq
h_{t}}U_{h,i}(t)$ (24)

to denote the arm with the best empirical mean at time $t$ and the highest UCB
that is not the empirical best. We use $t_{h}\in\mathbb{N}$ to denote the
number of time steps at a particular level $h$. Line 13 shows the algorithm
updates (23) and (24) following each sampling iteration. The individual MAB
games are independent of all other levels and have a unique time step
increment. _Termination_ at a particular level $h$ is defined as the event at
time step $t_{h}$ in which the beamforming vector corresponding to vertex
$(h,h_{t_{h}})$ is selected under the condition

$\displaystyle U_{h,u_{t_{h}}}(t_{h})-L_{h,h_{t_{h}}}(t_{h})<\epsilon_{h}$
(25)

and other arms and their descendants are discarded. Hence, proceeding
termination, the two children $\mathcal{C}((h,h_{t_{h}}))$ are the new
vertices whose arms are played in the subsequent bandit game at level $h+1$.
The algorithm checks the termination criteria at the start of each sampling
iteration on line 7.

Binary SSE, however, _naively_ exploits the hierarchical codebook. Certain
levels of the codebook are more beneficial to play than others based on the
number of narrowest beams (leaf vertices) eliminated per number of samples
required. Consequently, one might benefit from skipping some levels at the
expense of contending more arms in a BAI MAB game. We characterize the
strategy used to navigate the codebook levels by a pruning vector $\mathbf{p}$
with elements $p_{h}\in\left\\{{0,1}\right\\}$. Specifically, assume that at
level $h-1$, the beamforming vectors corresponding to the vertices in
$\mathcal{S}_{h-1}$ are used in the BAI MAB game to take samples as RSS
measurements. Upon termination, if $p_{h}=1$, the two children vertices’
beamforming vectors of the arm chosen at level $h-1$ are played in the next
level $h$. Lines 5-7 in Algorithm 2 indicate that if $p_{h}=0$, we bypass
level $h$ and, pending $p_{h+1}=1$, put all four arms in contention. If
$p_{h+1}=0$, we bypass this level, and so on. Fig. 6 shows an example of
$\mathbf{p}=[0,1,0,1]$. Note that $p_{H}$ must be set to $1$ because we
require a choice of one of the narrowest mainbeam beamforming patterns.
Therefore, there are $2^{H-1}$ possible strategies for a given hierarchical
codebook with $H$ levels, and the number of arms considered in each strategy
is

$\displaystyle N_{H}\triangleq\sum_{h:p_{h}=1}\left|\mathcal{S}_{h}\right|.$
(26)

We call this algorithm General SSE, and show the full pseudocode in Algorithm
2.

Figure 6: Illustration of eliminated arms at each level for General SSE for
$\mathbf{p}=[0,1,0,1]$. The first starting level considers four vertices. The
final selected nodes are indicated as hollow white with an asterisk.

1 Input: $\mathbf{p}$, $B$, $\epsilon$, $\delta$, and $H$;

2 Initialize: $t=1$, $\left\\{{\mathbf{w}_{h,i}}\right\\}$,
$U_{h,i}(t)=\infty$, $L_{h,i}(t)=-\infty$, $\hat{f}_{h,i}(t)=0$,
$N_{h,i}(t)=0$, for $1\leqslant h\leqslant H$ and $1\leqslant i\leqslant
2^{h}$;

3 $\mathcal{S}_{0}=\left\\{{(0,1)}\right\\}$;

4 for  _$h=1,\dots,H$_ do

5 for  _$(h-1,i)\in\mathcal{S}_{h-1}$_ do

6 $\mathcal{S}_{h}\cup\mathcal{C}(h-1,i)$;

7

8 end for

9 if  _$p_{h}==1$_ then

10

11 $t\leftarrow 1$;

12 Initialize $u_{t}$ and $h_{t}$;

13 while  _ $U_{h,u_{t}}(t)-L_{h,h_{t}}(t)\geqslant\epsilon_{h}$ _ do

14 for  _$X(t)\in\left\\{{(h,h_{t}),(h,u_{t})}\right\\}$_ do

15 Sample $X(t)$, observe $\left|y(t)\right|$;

16 Update $N_{X(t)}(t)$, $\hat{f}_{X(t)}(t)$, $U_{X(t)}(t)$, and
$L_{X(t)}(t)$; (see (18)(17)(21)(22))

17 $t\leftarrow t+1$;

18

19 end for

20 Update $u_{t}$ and $h_{t}$;

21 end while

22 $I\leftarrow h_{t}$;

23 $\mathcal{S}_{h}\leftarrow(h,I)$

24 end if

25

26 end for

return I

Algorithm 2 General SSE

###  III-A Analysis

Binary and General SSE (Algorithm 1 and 2) adapt the sampling and termination
policy of [21]. Specifically, the operation of SSE consists in playing
_independent_ MAB games at each level $h$ (or $h$ dictated by the pruning
vector $\mathbf{p}$). Our analysis shall naturally follow [21] with necessary
changes to account for the use of multiple levels. Specifically, we first show
that, at each level $h$, $(h,u_{t_{h}})$ and $(h,h_{t_{h}})$ are good choices
for sampling, where our policy is _greedy_ toward the stopping criteria. Next,
we show that if the mean rewards are well estimated and the game at level $h$
has not terminated, then corresponding arms have not yet been sufficiently
sampled. Finally, we show that the choice of confidence term and exploration
rate enable the algorithms to terminate in finite time with probability at
least $1-\delta$ given sufficient samples at each level $h$.

We begin by laying some notation that plays a key role in our analysis. For
each level we assume $(h,i^{*})\in\mathcal{S}_{h}$, and we define the midpoint
between the two best arms

$\displaystyle
c_{h}\triangleq\frac{f_{h}^{*}+\max_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}f(\mathcal{P}_{h,i})}{2},$ (27)

as well as events

$\displaystyle\mathcal{A}_{h,i}(t_{h})\triangleq\left\\{{L_{h,i}(t_{h})\leqslant
c_{h}}\right\\}\cap\left\\{{U_{h,i^{*}}(t_{h})\geqslant c_{h}}\right\\},$ (28)
$\displaystyle\mathcal{M}_{h,i}(t_{h})\triangleq\left\\{{L_{h,i}({t_{h}})\leqslant
c_{h}\leqslant
U_{h,i}({t_{h}})}\right\\}\cap\left\\{{D_{h,i}(t_{h})>\epsilon_{h}/2}\right\\}.$
(29)

######  Lemma 1.

If the events
$\left\\{{U_{h,u_{t_{h}}}(t_{h})-L_{h,h_{t_{h}}}(t_{h})\geqslant\epsilon_{h}}\right\\}$
and

$\displaystyle\bigcap_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\mathcal{A}_{h,i}(t_{h})$ (30)

are true then the algorithm has not terminated at time $t_{h}$ at level $h$,
which implies that

$\displaystyle\bigcup_{i\in\left\\{{u_{t_{h}},h_{t_{h}}}\right\\}}\mathcal{M}_{h,i}(t_{h}).$
(31)

must be true.

###### Proof:

Our algorithm differs from [21, 20] in the confidence term (19) and
exploration rate (20), which include the variance estimate of rewards, $B$,
and the total number of arms, $N_{H}$ (26). Nevertheless, we can adapt [21,
Lemma 2] and the detailed proof involves bookkeeping to analyze each statement
outlined and proven in [21, Eqs. (5)-(8)]. ∎

SSE considers $N_{H}$ arms (see (26)) in the total MAB games played, which is
on the order of the logarithm of the number of beamforming vectors required in
traditional MAB strategies using the $2^{H}$ narrowest beams [33, 16]. The
individual spacing between mean rewards of arms also plays a significant role
in determining overall complexity. Let
$\Delta_{h,i,\epsilon}\triangleq\max\left\\{{\Delta_{h,i},\epsilon_{h}/2}\right\\}$,
and

$\displaystyle\mathbf{H}_{h,\epsilon}\triangleq\sum_{i:(h,i)\in\mathcal{S}_{h}}\frac{1}{\Delta_{h,i,\epsilon}^{2}}.$
(32)

######  Lemma 2.

A lower bound on the number of samples of arm $(h,i)$ required to obtain
$D_{h,i}(t_{h})\leqslant\Delta_{h,i,\epsilon}$ is

$\displaystyle
N_{h,i}(t_{h})\geqslant\frac{B}{2\Delta_{h,i,\epsilon}^{2}}\log\left(\frac{N_{H}\alpha_{1}t_{h}^{\alpha}}{\delta}\right),$
(33)

or rounded to the next largest integer, $N^{*}_{h,i}(t_{h})=\lceil
N_{h,i}(t_{h})\rceil$.

###### Proof:

The expression (33) is derived from
$D_{h,i}(t_{h})\leqslant\Delta_{h,i}(t_{h})$ and our choice of confidence term
(19) and exploration rate (20). ∎

The event $\mathcal{A}_{h,i}(t_{h})$ is indicative of the mean rewards being
well estimated, and implies event $\mathcal{M}_{h,i}(t_{h})$ is true. Under
event $\mathcal{M}_{h,i}(t_{h})$, our confidence terms are large, such that
$D_{h,i}(t_{h})>\epsilon_{h}/2$ for $(h,u_{t_{h}})$ and $(h,h_{t_{h}})$. Lemma
2 shows that these large confidence terms are a result of the sampling of an
arm less than $N^{*}_{h,i}(t_{h})$ times. Our next result first shows that the
complement of $\mathcal{A}_{h,i}(t_{h})$, denoted as
$\mathcal{A}_{h,i}^{\prime}(t_{h})=\left\\{{L_{h,i}(t_{h})>c_{h}}\right\\}\cup\left\\{{U_{h,i^{*}}(t_{h})<c_{h}}\right\\}$,
occurs with probability less than $\delta$. Second, we provide a lower bound
on the number of samples, that is a factor of $N^{*}_{h,i}(t_{h})$, required
for SSE to terminate with probability $1-\delta$.

######  Lemma 3.

Under SSE (Algorithm 1 or 2) and Assumption 2 with confidence term (19),
exploration rate (20),

$\displaystyle{\mathbb{P}}{\left(\exists
h\in\left\\{{1,\dots,H}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\mathcal{A}_{h,i}^{\prime}(t_{h})\right)}\leqslant\sum_{h:p_{h}=1}\frac{\left|\mathcal{S}_{h}\right|\delta}{N_{H}\alpha_{1}t_{h}^{\alpha-1}}$
(34)

and

$\displaystyle{\mathbb{P}}{\left(\exists
h\in\left\\{{1,\dots,H}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h}}\mathcal{B}_{h,i}(t_{h})\right)}\leqslant\sum_{h:p_{h}=1}\frac{3\mathbf{H}_{h,\epsilon}\delta}{4N_{H}\alpha_{1}t_{h}^{\alpha}}$
(35)

where

$\displaystyle\mathcal{B}_{h,i}(t_{h})\triangleq\left\\{{N_{h,i}(t_{h})>4N_{h,i}^{*}(t_{h})}\right\\}\cap\mathcal{M}_{h,i}(t_{h}).$
(36)

###### Proof:

One can show that our confidence term (19) and exploration rate (20) do not
affect the bounds from [21, Lemma 3 and 4] for
${\mathbb{P}}{\left(\mathcal{A}_{h,i}^{\prime}(t_{h})\right)}$ and
${\mathbb{P}}{\left(\mathcal{B}_{h,i}(t_{h})\right)}$, respectively, except
for the constant $\left|\mathcal{S}_{h}\right|/N_{H}$ in (34). In order to
extend to all levels, we apply a union bound over $h$. ∎

Lemma 3 shows that, for each arm, under events $\mathcal{A}_{h,i}(t_{h})$ and
$N_{h,i}(t_{h})\geqslant 4N_{h,i}^{*}(t_{h})$, SSE has not terminated with
probability less than $\delta$. Finally, we show that SSE has a finite upper
bound on the sample complexity that also holds with probability at least
$1-\delta$.

######  Lemma 4.

Let $t_{h}^{\delta}=\left\lceil
146B\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)\log(B\max(\mathbf{H}_{h,\epsilon},N_{H})/\delta)\right\rceil$.
For every $T_{h}\geqslant t_{h}^{\delta}$, and $\alpha=4$, the probability
that SSE (Algorithm 1 or 2) under Assumption 2 with confidence term (19),
exploration rate (20), has not terminated over all levels, after
$\sum_{h:p_{h}=1}T_{h}$ total samples, is at most
$\sum_{h:p_{h}=1}4\delta/T_{h}^{2}$.

###### Proof:

The full proof shows that the sample complexity upper bound, $t_{h}^{\delta}$,
holds with probability of occurrence of either event in Lemma 3. For each
level, this probability bound is unchanged from [21, Lemma 5], and a union
bound encompasses all levels. ∎

The full proofs for each lemma are given in the appendix. The key takeaway is
the reduction in complexity compared to traditional MAB settings (no
structural exploitation), in which $2^{H}$ arms are required to be explored.
Only $2H$ arms are explored for Binary SSE combined with the structural
exploitation. Exploiting a unimodal structure of mean rewards with $2^{H}$
total arms will result in only requiring $2^{H-1}$ (half the total arms) on
average. To the best of the authors’ knowledge, no prior work analytically
shows the reduction in complexity for unimodal structure.

###  III-B Optimal Strategy

Using (33), the total number of samples taken for one level $h$ for SSE is

$\displaystyle t_{h}$
$\displaystyle=\sum_{i:(h,i)\in\mathcal{S}_{h}}N_{h,i}(t_{h})\geqslant\frac{\mathbf{H}_{h,\epsilon}B}{2}\log\left(\frac{N_{H}\alpha_{1}t_{h}^{\alpha}}{\delta}\right),$
(37)

and has the closed form solution

$\displaystyle\bar{t}_{h}=\left\lceil-\frac{\mathbf{H}_{h,\epsilon}\alpha
B}{2}W\left(-\frac{2}{\mathbf{H}_{h,\epsilon}\alpha
B\left(\frac{N_{H}\alpha_{1}}{\delta}\right)^{1/\alpha}}\right)\right\rceil,$
(38)

where $W(\cdot)$ is the Lambert-W function, defined such that

$\displaystyle x_{h}t_{h}\geqslant\log(y_{h}t_{h})\iff
t_{h}\geqslant-\frac{1}{x_{h}}W\left(-\frac{x_{h}}{y_{h}}\right),$ (39)

where $x_{h}=2/(\mathbf{H}_{h,\epsilon}\alpha B)$ and
$y_{h}=(N_{H}\alpha_{1}/\delta)^{1/\alpha}$. We define the ratio of leafs
eliminated to samples required as the _efficiency_ of the strategy. For a
beamforming codebook with $2^{H}$ narrow beams, each beam corresponding to a
vertex at level $h$ has $2^{H-h}$ descendent narrow beams that are eliminated
if the respective vertex at level $h$ is eliminated. We model the prior
probabilities for the $k$ path AoAs as uniform random variables
$\theta_{k}\sim\mathcal{U}(\Theta)$. $\bar{t}_{h}$ is a function of the AoAs
that we denote $\bar{t}_{h}(\boldsymbol{\theta})$. Maximizing the average
efficiency over the range of possible path AoAs provides an assessment of
which pruning vector, $\mathbf{p}$, is optimal. Furthermore, the sparsity of
the mmWave channel allows us to focus on the dominant path, $\theta_{1}$ [27,
26], so that the efficiency for level $h$ is

$\displaystyle\xi_{h}(\theta_{1})\triangleq\frac{2^{H-h}}{\bar{t}_{h}(\theta_{1})}.$
(40)

Let $\rho$ denote the number of $1$s in $\mathbf{p}$, i.e.,
$\rho=\mathbf{p}^{T}\mathbf{1}$ The average efficiency for a particular
strategy over all levels is

$\displaystyle\bar{\xi}(\theta_{1};\mathbf{p})=\frac{1}{\rho}\sum_{h:p_{h}=1}\xi_{h}(\theta_{1}).$
(41)

The vector $\mathbf{p}^{*}$ maximizes the average efficiency, such that

$\displaystyle\mathbf{p}^{*}=\mathop{\text{argmax}}_{\mathbf{p}}{\mathbb{E}_{\theta_{1}}}{\left(\bar{\xi}(\theta_{1};\mathbf{p})\right)},$
(42)

which we estimate numerically, using a small increment $\nu>0$, as

$\displaystyle{\mathbb{E}_{\theta_{1}}}{\left(\bar{\xi}(\theta_{1};\mathbf{p})\right)}\approx\frac{1}{\rho}\sum_{h:p_{h}=1}\sum_{a=0}^{2\pi/(3\nu)}\left(\frac{\pi}{6}+a\nu\right)\frac{2^{H-h}}{\bar{t}_{h}(a)}.$
(43)

Fig. 7 shows (43) for $\nu=.03$ obtained for various pruning vectors. The
decimal value $16$ ($[0,1,0,0,0,0]$ binary value) corresponds to the optimal
pruning vector $\mathbf{p}^{*}=[0,1,0,0,0,0,1]$.

Figure 7: Efficiencies of different strategies, $\mathbf{p}$, for $H=7$.

##  IV Numerical Simulations

###  IV-A Methodology and Settings

We execute each simulation by first making $K$ uniformly random selections of
AoAs $\theta_{k}\in\Theta$, each representing the $k^{\textnormal{th}}$ path.
We use a unique random number generator seed for each individual simulation
that we denote with index $\ell$. The $K$-length vector of AoAs chosen for
simulation $\ell$ is denoted $\boldsymbol{\theta}_{\ell}$ with a corresponding
vertex $(H,i^{*}_{\ell})$. We use $\boldsymbol{\theta}_{\ell}$ to then
construct the array response (2). We take samples by applying beamforming
vectors to the channel model observations, as in (3), that are chosen based on
the algorithm policy. Each simulation terminates after the stopping criteria
(25) is met. We compare the performance of five algorithms, Binary SSE and
General SSE to HPM from [9], HBA from [33], and an exhaustive search over all
the narrowest pencil beams at level $H$, corresponding to General SSE with
$\mathbf{p}=[0,\dots,0,1]$. The HPM algorithm acts a baseline of performance
in utilizing perfect channel knowledge in the posterior computations to deploy
the hierarchical codebook. We dynamically determine the number of total
simulations required, $L$, by utilizing the Wilson score [32] interval width.
Specifically, we estimate the probability that an $\epsilon$-optimal arm is
chosen over time, $P_{c}(t)$, as

$\displaystyle\hat{P}_{c}(t,L)=\frac{1}{L}\sum_{\ell=1}^{L}\mathds{1}\\!\left\\{\theta_{H,h_{t}}\in\Theta_{\epsilon},\left|i^{*}_{\ell}-h_{t}\right|\leqslant
1\right\\}$ (44)

at sample number $t$. Simulations are run until the width of the confidence
interval, $\left|w^{+}-w^{-}\right|<0.02$, where

$\displaystyle
P_{c}(t)\in(w^{-},w^{+})=\frac{1}{1+z_{\gamma}/L}\left(\left(\hat{P}_{c}(t,L)+\frac{z_{\gamma}^{2}}{2L}\right)\pm
z_{\gamma}\sqrt{\frac{\hat{P}_{c}(t,L)(1-\hat{P}_{c}(t,L))}{L}+\frac{z_{\gamma}^{2}}{4L^{2}}}\right).$
(45)

$z_{\gamma}=Q^{-1}(\gamma/2)$ and $Q(\cdot)$ is the tail probability function
of the standard normal distribution. For $95\%$ confidence, $\gamma=.95$,
$z_{\gamma}=1.96$ and for our simulations we set $\delta$ to $0.01$.

The algorithms utilize a common beamforming codebook with $H=7$ levels ($128$
pointing angles at the finest resolution) as described in Section II with
$M=100$ antenna elements organized as a uniform linear array. We design the
beamforming architecture to only support $64$ RF chains in a HAD configuration
based on the design in [2]. The phase shifters associated with the analog
portion only support $3$-bit ($2^{3}$) quantized phase increments as well. The
gain parameter is set as $g=10^{.1}$ which corresponds to $1$ dB of gain per
level with the increasingly narrow beams. We set the parameter $\epsilon=3$
for Binary SSE and $\epsilon=5$ for General SSE. These choices of $\epsilon$
may not seem ideal when considering $f(\mathcal{P}_{H,i})\geqslant
f_{H}^{*}-\epsilon$. The parameter $\epsilon$ should be interpreted purely as
a hyperparameter rather than an acceptable RSS. Beamforming gain is also
typically measured with respect to a multiplicative factor, rather than
additive, but we were unable to analyze $\epsilon$-optimality in this fashion
(i.e. $\epsilon f(\mathcal{P}_{H,i})\geqslant f_{H}^{*}$). Recall from (44)
that correctness also hinges on the condition that
$\left|i^{*}-h_{t}\right|\leqslant 1$, which requires the chosen beamforming
vector to be a neighbor of $\mathbf{w}_{H,i^{*}}$, $\mathbf{w}_{H,i\pm 1}$. In
order to optimize hyperparameters, we fix $P_{k}=1$ and assume knowledge of
the relative channel SNR and set $B=\sigma^{2}$. We do not use any knowledge
of the channel fading factor, $\alpha(t)$ (1), in our algorithms. The sequence
$\mathbf{p}$ is chosen as $[0,0,0,1,0,0,1]$ for General SSE, which was
determined to be one of the optimal selections in Section III-B and
accordingly performed best in simulations.

###  IV-B Results and Discussion

A general comparison of the five algorithms is shown in Fig. 8 for SNR $=0$ dB
and no multi-path ($K=1$). The HBA and exhaustive search algorithms only
utilize the narrowest beams at level $H$. Both SSE algorithms show a
substantial improvement from the exhaustive search method, and General SSE is
comparable to HPM, but with no channel fading knowledge or computation of
posteriors. The performance of HBA quickly finds a beam to terminate on, but
is correct less often than General SSE and does not offer guarantees of being
$\delta$-PAC. We calculate the analytical closed-form solutions of the SSE
algorithm complexities according to $\mathbf{\theta}_{\ell}$ and using (38).
We use the lower bound on the number of samples from (36) in Lemma 3,
$N_{h,i}(t_{h})\geqslant 4N_{h,i}^{*}(t_{h})$, with
$\bar{t}(\mathbf{\theta}_{\ell})$ to estimate the average complexity for both
SSE algorithms (i.e. Binary SSE has $\mathbf{p}=[1,\dots,1]$) as

$\displaystyle
T^{a}=\frac{1}{L}\sum_{\ell=1}^{L}\sum_{h:p_{h}=1}4\bar{t}_{h}(\boldsymbol{\theta}_{\ell}).$
(46)

The values of $T^{a}$ are illustrated in Fig. 8 by the vertical dotted lines
with respective line markers. Note that the complexity values are dependent on
parameter tuning of the confidence terms $D_{h,i}(t)$. If not tuned to
accommodate the channel conditions, i.e., $B<\sigma^{2}$, the closed-form
expression calculates the estimated complexity incorrectly. Conversely, overly
conservative parameter values lead to a higher estimated complexity.

Figure 8: Comparison of performance of all algorithms at SNR $=0$ dB.

If there were an ideal codebook with uniformity in the mainlobe and infinitely
small gaps between neighboring beams, we would expect less variation in sample
complexity with different AoAs. A DNN implementation to develop an adaptive
beamformer may lead to mitigation of this issue [29], and the MAB framework
developed here could be adapted. For our work with the hierarchical codebook,
the small gaps between the main beams correspond to very small $\Delta_{h,i}$,
which would cause high sample complexity. We resolve this issue by choosing
$\epsilon$ appropriately, but in order to approximate a hypothetical optimal
codebook, we choose the dominant path AoA, $\theta_{1}$, from the $128$
pointing angles $\theta_{H,i}$ for each simulation. Fig. 9 shows the
comparison of performance of choosing the $\theta_{1}$ uniformly from the
continuum $\Theta$ and discrete set $\left\\{{\theta_{h,i}}\right\\}$. The
performance of each algorithm only varies slightly due to our appropriate
choice of $\epsilon$. An SSE implementation using the broadest beams has
significant sample complexity variation due to the greater non-uniformity
across the main beams.

Figure 9: Comparison of performance of all algorithms at SNR $=0$ dB with AoAs
chosen uniformly or as $\theta_{H,i}$ .

Fig. 10 shows the variation in algorithm performance with SNR, where low SNR
is chosen as $-2.5$ dB and high SNR is chosen as $5$ dB. There is a noticable
degradation in performance for each algorithm. While high SNR yields very good
results for HBA, performance degrades significantly with lower SNR. In [33],
the HBA algorithm is supposed to terminate after reaching a required
resolution rather than what is done in the present work with a fixed
resolution at the codebook level with narrowest beams. Works such as [6, 33,
10] represent a class of algorithms that are highly exploratory in how they
quickly find the best arm, but do not necessarily have termination criteria or
complexity bounds guaranteed in the analysis to be $\delta$-PAC. Note the
large displacement between $T^{a}$ for General SSE and where the simulation
converges for high SNR. In cases of especially pristine channel conditions, it
may only be required to sample each beam once (i.e.
$\bar{t}_{h}=\left|\mathcal{S}_{h}\right|$). The lower bound on samples
determined in Lemma 4 of [21] requires $t_{h}\gg\left|\mathcal{S}_{h}\right|$
to apply. Hence, we see a large discrepancy in the number of samples actually
required at high SNR and what is calculated (dotted line). These results
suggest that the initial alignment “one-off” beam sweep [14, 13] may be a
sufficient policy at especially high SNR.

Figure 10: Comparison of performance of all algorithms at low and high SNR.

Fig. 11 shows the degradation of the algorithms performance in the presence of
multi-path effects ($K=5$). Non-dominant paths are chosen to be $10$ dB down
from the dominant one [26, 27]. In general, there is a small difference in
performance for each of the algorithms, but it is not significant due to the
highly attenuated non-dominant paths. Multi-path effects are compensated for
in HPM by summing over path dependent complex-gain values $\alpha_{k}(t)$ in
the posterior calculation. The results show instances where the dominant path
is determined correctly faster in the presence of multi-path, this is a result
of non-dominant paths in close proximity adding to the dominant one. However,
the performance in terms of correctness, on average, is still slightly
degraded when there are multi-path effects present.

Figure 11: Comparison of performance of all algorithms with and without multi-
path effects with $K=5$ paths.

To illustrate the computational benefits of Binary and General SSE, we finally
provide performance vs complexity curves in Fig. 12 and Fig. 13 as done in
[6]. We assess computational complexity by counting the total number of
arithmetic and search operations in the execution of the algorithm. This
includes $\log()$ and $\exp()$ functions counted as a single operation as
well. Fig. 12 shows the performance vs complexity while Fig. 13 shows the
complexity vs number of measurements. Both are indicative of the policy
overhead involved in selecting each beamforming vector. Each algorithm varies
significantly in the number of computational operations required in order to
obtain the same level of correctness. Note that Binary SSE works exceptionally
at high SNR from a computational standpoint. As anticipated, the posterior
calculations for HPM are expensive relative to the other algorithms.

Figure 12: Comparison of computations for all algorithms with high and low
SNR. Figure 13: Comparison of computations versus samples for all algorithms
with high and low SNR.

##  V Conclusion

We have proposed two variations of SSE for mmWave beam alignment, which
combine the low complexity policy benefits of MAB algorithms with the
performance gains offered by the hierachical codebook. Our analysis shows that
both algorithms are $\delta$-PAC and offer a significant reduction in
computational complexity compared to exhaustive search methods. Simulations
show competitive performance compared to state-of-the art algorithms such as
HPM, as well as a large reduction in policy computational complexity. Ongoing
efforts to extend these results include adapting hierarchical codebooks with
MAB algorithms for multi-user beam alignment along with tracking and more
general beam management practices.

##  Appendix A Proofs

###  A-A Proof of Lemma 1

###### Proof:

We prove the four statements outlined in [21, Eqs. (5)-(8)], to show that with
each the lemma holds. We drop the time index and level dependence for the
duration of the proof, i.e., $U_{u_{t}}$ shortened from
$U_{h,u_{t_{h}}}(t_{h})$. We denote the complement of
$\mathcal{A}_{h,i}(t_{h})$ as
$\mathcal{A}_{h,i}^{\prime}(t_{h})=\left\\{{L_{h,i}(t_{h})>c_{h}}\right\\}\cup\left\\{{U_{h,i^{*}}(t_{h})<c_{h}}\right\\}$,
such that
$\mathcal{A}_{h,i}^{\prime}(t_{h})\cap\mathcal{A}_{h,i}(t_{h})=\emptyset$.

  1. 1.

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{u_{t}}\leqslant
c}\right\\}\cap\left\\{{U_{h_{t}}\geqslant
c}\right\\}\implies\bigcup_{i\in\left\\{{u_{t},h_{t}}\right\\}}$$\left\\{{L_{i}\leqslant
c\leqslant U_{i}}\right\\}$

    1. (a)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{h_{t}}>c}\right\\}\cap\left\\{{L_{u_{t}}>c}\right\\}\implies\mathcal{A}_{u_{t}}^{\prime}$.

    2. (b)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{h_{t}}>c}\right\\}\cap\left\\{{U_{u_{t}}<c}\right\\}\subset\left\\{{U_{u_{t}}-L_{h_{t}}<0}\right\\}\cap\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}$,
which is an empty set.

    3. (c)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{U_{h_{t}}<c}\right\\}\cap\left\\{{L_{u_{t}}>c}\right\\}\implies\hat{f}_{h_{t}}<\hat{f}_{u_{t}}$,
which is false by definition.

    4. (d)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{U_{h_{t}}<c}\right\\}\cap\left\\{{U_{u_{t}}<c}\right\\}\implies\mathcal{A}_{h_{t}}^{\prime}$.

  2. 2.

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{h_{t}}\leqslant
c\leqslant U_{h_{t}}}\right\\}\cap\left\\{{U_{u_{t}}<c\textnormal{ or
}L_{u_{t}}>c}\right\\}\implies D_{h_{t}}>\epsilon/2$

    1. (a)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{h_{t}}\leqslant
c\leqslant
U_{h_{t}}}\right\\}\cap\left\\{{L_{u_{t}}>c}\right\\}\subset\left\\{{U_{h_{t}}-L_{h_{t}}>\epsilon}\right\\}\implies
D_{h_{t}}>\epsilon/2$, since $L_{h_{t}}<L_{u_{t}}$ and
$\hat{f}_{h_{t}}>\hat{f}_{u_{t}}$.

    2. (b)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{h_{t}}\leqslant
c\leqslant
U_{h_{t}}}\right\\}\cap\left\\{{U_{u_{t}}<c}\right\\}\subset\left\\{{U_{h_{t}}>c}\right\\}\cap\left\\{{L_{h_{t}}<c-\epsilon}\right\\}\implies
D_{h_{t}}>\epsilon/2$

  3. 3.

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{u_{t}}\leqslant
c\leqslant U_{u_{t}}}\right\\}\cap\left\\{{U_{h_{t}}<c\textnormal{ or
}L_{h_{t}}>c}\right\\}\implies D_{h_{t}}>\epsilon/2$

    1. (a)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{u_{t}}\leqslant
c\leqslant
U_{u_{t}}}\right\\}\cap\left\\{{L_{h_{t}}>c}\right\\}\subset\left\\{{U_{u_{t}}>\epsilon+c}\right\\}\cap\left\\{{L_{u_{t}}\leqslant
c}\right\\}\implies D_{u_{t}}>\epsilon/2$

    2. (b)

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{u_{t}}\leqslant
c\leqslant
U_{u_{t}}}\right\\}\cap\left\\{{U_{h_{t}}<c}\right\\}\subset\left\\{{U_{u_{t}}-L_{u_{t}}>\epsilon}\right\\}\implies
D_{u_{t}}>\epsilon/2$, since $\hat{f}_{h_{t}}>\hat{f}_{u_{t}}$ and
$L_{h_{t}}>L_{u_{t}}$.

  4. 4.

$\left\\{{U_{u_{t}}-L_{h_{t}}\geqslant\epsilon}\right\\}\cap\left\\{{L_{h_{t}}\leqslant
c\leqslant U_{h_{t}}}\right\\}\cap\left\\{{L_{u_{t}}\leqslant c\leqslant
U_{u_{t}}}\right\\}\subset\left\\{{D_{u_{t}}+D_{h_{t}}>\epsilon}\right\\}\implies
D_{u_{t}}>\epsilon/2$ or $D_{h_{t}}>\epsilon/2$.

∎

###  A-B Proof of Lemma 3

###### Proof:

We first show that the bound for
${\mathbb{P}}{\left(\mathcal{A}_{h,i}^{\prime}(t_{h})\right)}$ is unchanged
from [21, Lemma 3], aside from a constant
$\left|\mathcal{S}_{h}\right|/N_{H}$. Assume $N_{h,i}(t)=u$, with Hoeffding’s
Inequality

$\displaystyle{\mathbb{P}}{\left(L_{h,i}(t_{h})>c_{h},N_{h,i}(t_{h})=u\right)}$
$\displaystyle={\mathbb{P}}{\left(\hat{f}_{h,i}(t_{h})-D_{h,i}(t_{h})>c_{h},N_{h,i}(t_{h})=u\right)}$
(47)
$\displaystyle\leqslant{\mathbb{P}}{\left(\hat{f}_{h,i}(t_{h})-D_{h,i}(t_{h})>f(\mathcal{P}_{h,i}),N_{h,i}(t_{h})=u\right)}$
(48)
$\displaystyle={\mathbb{P}}{\left(\hat{f}_{h,i}(t_{h})-f(\mathcal{P}_{h,i})>D_{h,i}(t_{h}),N_{h,i}(t_{h})=u\right)}$
(49)
$\displaystyle\leqslant\exp\left(-\frac{2(D_{h,i}(t_{h}))^{2}u}{B}\right)$
(50) $\displaystyle=\exp\left(-\beta(t,\delta)\right)$ (51)
$\displaystyle=\frac{\delta}{N_{H}\alpha_{1}t_{h}^{\alpha}}.$ (52)

Similarly,

$\displaystyle{\mathbb{P}}{\left(U_{h,i^{*}}(t_{h})<c_{h},N_{h,i^{*}}(t_{h})=u\right)}\leqslant\frac{\delta}{N_{H}\alpha_{1}t_{h}^{\alpha}},$
(53)

then by using the union bound over arms and possible number of samples for
each arm,

$\displaystyle{\mathbb{P}}{\left(\exists
h\in\left\\{{1,\dots,H}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\mathcal{A}_{h,i}^{\prime}(t_{h})\right)}$ (54)
$\displaystyle={\mathbb{P}}{\left(\exists
h\in\left\\{{1,\dots,H}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\left\\{{L_{h,i}(t_{h})>c_{h}}\right\\}\cup\left\\{{U_{h,i^{*}}(t_{h})<c_{h}}\right\\}\right)}$
(55)
$\displaystyle\leqslant\sum_{h:p_{h}=1}\sum_{i:(h,i)\in\mathcal{S}_{h}}\sum_{u=1}^{t_{h}}\frac{\delta}{N_{H}\alpha_{1}t_{h}^{\alpha}}$
(56)
$\displaystyle=\sum_{h:p_{h}=1}\frac{\left|\mathcal{S}_{h}\right|\delta}{N_{H}\alpha_{1}t_{h}^{\alpha-1}}$
. (57)

Next, we show that the bound on
${\mathbb{P}}{\left(\mathcal{B}_{h,i}(t_{h})\right)}$ does not change from
[21, Lemma 4]. The lower bound on samples in Lemma (2), $N_{h,i}^{*}(t_{h})$
is a factor of the number of samples required in the bound.

$\displaystyle{\mathbb{P}}{\left(\mathcal{B}_{h,i}(t_{h})\right)}$
$\displaystyle={\mathbb{P}}{\left(\left\\{{N_{h,i}(t_{h})>4N_{h,i}^{*}(t_{h})}\right\\}\cap\left\\{{\left\\{{L_{h,i}({t_{h}})\leqslant
c_{h}\leqslant
U_{h,i}({t_{h}})}\right\\}\cap\left\\{{D_{h,i}(t_{h})>\epsilon_{h}/2}\right\\}}\right\\}\right)}$
(58)
$\displaystyle\leqslant{\mathbb{P}}{\left(\left\\{{N_{h,i}(t_{h})>4N_{h,i}^{*}(t_{h})}\right\\}\cap\left\\{{L_{h,i}({t_{h}})\leqslant
c_{h}\leqslant U_{h,i}({t_{h}})}\right\\}\right)}$ (59)
$\displaystyle\leqslant{\mathbb{P}}{\left(\left\\{{N_{h,i}(t_{h})>4N_{h,i}^{*}(t_{h})}\right\\}\cap\left\\{{f_{h,i}(t)-D_{h,i}(t)<c_{h}}\right\\}\right)}$
(60)
$\displaystyle\leqslant\sum_{u=4N_{h,i}^{*}(t_{h})+1}^{\infty}\exp(-2u\left(f(\mathcal{P}_{h,i})-c_{h}-D_{h,i}(t_{h}))^{2}\right)$
(61)
$\displaystyle\leqslant\sum_{u=4N_{h,i}^{*}(t_{h})+1}^{\infty}\exp\left(-2u\left(\frac{\Delta_{h,i,\epsilon}}{2}-\sqrt{\frac{B}{2u}\log\left(\frac{\alpha_{1}N_{H}t_{h}^{\alpha}}{\delta}\right)}\right)^{2}\right)$
(62)
$\displaystyle\leqslant\sum_{u=4N_{h,i}^{*}(t_{h})+1}^{\infty}\exp\left(-2\Delta_{h,i,\epsilon}^{2}\left(\sqrt{u}-\sqrt{N^{*}_{h,i}(t_{h})}\right)^{2}\right)$
(63)
$\displaystyle\leqslant\int_{v=4N_{h,i}^{*}(t_{h})}^{\infty}\exp\left(-2\Delta_{h,i,\epsilon}^{2}\left(\sqrt{v}-\sqrt{N_{h,i}^{*}(t_{h})}\right)^{2}\right)dv$
(64)
$\displaystyle=2\int_{w=\sqrt{N_{h,i}^{*}(t_{h})}}^{\infty}w\exp(-2\Delta_{h,i,\epsilon}^{2}w^{2})dw$
$\displaystyle+2\sqrt{N_{h,i}^{*}(t_{h})}\int_{w=\sqrt{N_{h,i}^{*}(t_{h})}}^{\infty}\exp(-2\Delta_{h,i,\epsilon}^{2}w^{2})dw$
(65)
$\displaystyle=\frac{1}{2\Delta_{h,i,\epsilon}^{2}}\int_{x=2\Delta_{h,i,\epsilon}^{2}N^{*}_{h,i}(t_{h})}^{\infty}\exp(-x)dx$
$\displaystyle+\frac{\sqrt{2\pi
N_{h,i}^{*}(t_{h})}}{\Delta_{h,i,\epsilon}}\int_{y=2\Delta_{h,i,\epsilon}\sqrt{N_{h,i}^{*}(t_{h})}}^{\infty}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^{2}}{2}\right)dy$
(66)
$\displaystyle\leqslant\frac{1}{2\Delta_{h,i,\epsilon}^{2}}\exp(-2\Delta_{h,i,\epsilon}^{2}N_{h,i}^{*}(t_{h}))+\frac{1}{4\Delta_{h,i,\epsilon}^{2}}\exp(-2\Delta_{h,i,\epsilon}^{2}N_{h,i}^{*}(t_{h}))$
(67)
$\displaystyle=\frac{3}{4\Delta_{h,i,\epsilon}^{2}}\exp\left(-2\Delta_{h,i,\epsilon}^{2}\left\lceil\frac{1}{2\Delta_{h,i,\epsilon}^{2}}\log\left(\frac{\alpha_{1}N_{H}t^{\alpha}}{\delta}\right)\right\rceil\right)$
(68)
$\displaystyle\leqslant\frac{3\delta}{4\Delta_{h,i,\epsilon}^{2}\alpha_{1}N_{H}t_{h}^{\alpha}}$
(69)

The analysis produces the same result shown in [20, Appendix B.2], despite our
choice of confidence term and exploration rate. (64)-(68) show that the
expression utilizes a factor of $N_{h,i}^{*}(t_{h})$ from Lemma 2. By the
union bound over $h$ and each arm,

$\displaystyle{\mathbb{P}}{\left(\exists
h\in\left\\{{1,\dots,H}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h}}\mathcal{B}_{h,i}(t_{h})\right)}\leqslant\sum_{h:p_{h}=1}\frac{3\mathbf{H}_{h,\epsilon}\delta}{4\alpha_{1}N_{H}t_{h}^{\alpha}}$
(70)

∎

###  A-C Proof of Lemma 4

###### Proof:

Our proof follows the flow of the proof of [21, Lemma 5], but some terms
differ based on our choice of confidence term, exploration rate, and resulting
reward structure. Often our reward profile contains larger values of
$\Delta_{h,i,\epsilon}$ that induce cases where
$\left|\mathcal{S}_{h}\right|\leqslant\mathbf{H}_{h,\epsilon}$, which we
compensate for. We define two events

$\displaystyle\bar{\mathcal{A}}_{h}^{\prime}\triangleq\left\\{{\exists
t_{h}\in\left\\{{\lceil
T_{h}/2\rceil,\dots,T_{h}}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\mathcal{A}_{h,i}^{\prime}(t_{h})}\right\\}$ (71)

and

$\displaystyle\bar{\mathcal{B}}_{h}\triangleq\left\\{{\exists
t_{h}\in\left\\{{\lceil
T_{h}/2\rceil,\dots,T_{h}}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h}}\mathcal{B}_{h,i}(t_{h})}\right\\},$
(72)

and show that if neither $\bar{\mathcal{A}}_{h}^{\prime}$ nor
$\bar{\mathcal{B}}_{h}$ occur, then SSE terminates at that level $h$ with at
most $T_{h}$ samples. The additional number of rounds required to terminate
when $t_{h}\geqslant\lceil T_{h}/2\rceil$ we denote as $\tau_{h}$, such that

$\displaystyle\lceil T_{h}/2\rceil+\tau_{h}\leqslant T_{h}.$ (73)

We bound the quantity $\tau_{h}$ by applying Lemma 1, which showed
$(h,h_{t_{h}})$ and $(h,u_{t_{h}})$ were good choices for sampling, such that

$\displaystyle\tau_{h}$ $\displaystyle=\sum_{t_{h}=\lceil
T_{h}/2\rceil}^{T_{h}-1}\mathds{1}\\!\left\\{\left\\{{U_{h,h_{t_{h}}}(t_{h})-L_{h,u_{t_{h}}}(t_{h})\geqslant\epsilon_{h}}\right\\}\bigcap_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\mathcal{A}_{h,i}(t_{h})\right\\}$ (74)
$\displaystyle=\sum_{t_{h}=\lceil
T_{h}/2\rceil}^{T_{h}-1}\mathds{1}\\!\left\\{\mathcal{M}_{h,h_{t_{h}}}(t_{h})\cup\mathcal{M}_{h,u_{t_{h}}}(t_{h})\right\\}$
(75) $\displaystyle\leqslant\sum_{t_{h}=\lceil
T_{h}/2\rceil}^{T_{h}-1}\sum_{i:(h,i)\in\mathcal{S}_{h}}\mathds{1}\\!\left\\{\left\\{{\left\\{{i=h_{t}}\right\\}\cup\left\\{{i=u_{t}}\right\\}}\right\\}\cap\mathcal{M}_{h,i}(t_{h})\right\\}$
(76) $\displaystyle=\sum_{t_{h}=\lceil
T_{h}/2\rceil}^{T_{h}-1}\sum_{i:(h,i)\in\mathcal{S}_{h}}\mathds{1}\\!\left\\{\left\\{{\left\\{{i=h_{t}}\right\\}\cup\left\\{{i=u_{t}}\right\\}}\right\\}\cap\left\\{{N_{h,i}(t_{h})\leqslant
4N_{h,i}^{*}(t_{h})}\right\\}\right\\}$ (77) $\displaystyle=\sum_{t_{h}=\lceil
T_{h}/2\rceil}^{T_{h}-1}\sum_{i:(h,i)\in\mathcal{S}_{h}}\mathds{1}\\!\left\\{\left\\{{\left\\{{i=h_{t}}\right\\}\cup\left\\{{i=u_{t}}\right\\}}\right\\}\cap\left\\{{N_{h,i}(t_{h})\leqslant
4N_{h,i}^{*}(T_{h})}\right\\}\right\\}$ (78)
$\displaystyle\leqslant\sum_{i:(h,i)\in\mathcal{S}_{h}}4N_{h,i}^{*}(T_{h}).$
(79)

(75) is a direct application of Lemma 1, and (77) comes from the assumption
that $\mathcal{B}_{h,i}(t_{h})$ has not occurred. We show next that
$T_{h}\geqslant t_{h}^{\delta}$ implies
$T_{h}>2+8\sum_{i:(h,i)\in\mathcal{S}_{h}}N^{*}_{h,i}(T_{h})$. Let

$\displaystyle
T_{h}=CB\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)\log\left(\frac{B\max(\mathbf{H}_{h,\epsilon},N_{H})}{\delta}\right),$
(80)

where $C\geqslant 146$, then for $\alpha=4$ and $\alpha_{1}=5/4$,

$\displaystyle 2+8\sum_{i:(h,i)\in\mathcal{S}_{h}}N_{h,i}^{*}(T_{h})$
$\displaystyle\leqslant
2+8\left|\mathcal{S}_{h}\right|+4B\mathbf{H}_{h,\epsilon}\log\left(\frac{\alpha_{1}N_{H}T_{h}^{4}}{\delta}\right)$
(81)
$\displaystyle\leqslant(10+4\log(\alpha_{1}))B\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)+4B\mathbf{H}_{h,\epsilon}\log\left(\frac{N_{H}}{\delta}\right)$
$\displaystyle+16B\mathbf{H}_{h,\epsilon}\log(T_{h})$ (82)
$\displaystyle\leqslant
14B\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)+4B\mathbf{H}_{h,\epsilon}\log\left(\frac{N_{H}}{\delta}\right)$
$\displaystyle+16B\mathbf{H}_{h,\epsilon}\left(\log(C)+\log(B\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|))+\log(B\max(\mathbf{H}_{h,\epsilon},N_{H}))+\log\left(\frac{N_{H}}{\delta}\right)\right)$
(83)
$\displaystyle\leqslant(14B+16\log(C))B\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)+20B\mathbf{H}_{h,\epsilon}\log\left(\frac{N_{H}}{\delta}\right)$
$\displaystyle+32B\mathbf{H}_{h,\epsilon}\log(B\max(\mathbf{H}_{h,\epsilon},N_{H}))$
(84)
$\displaystyle\leqslant(66+16\log(C))B\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)\log\left(\frac{B\max(\mathbf{H}_{h,\epsilon},N_{H})}{\delta}\right)$
(85)
$\displaystyle<CB\max(\mathbf{H}_{h,\epsilon},\left|\mathcal{S}_{h}\right|)\log\left(\frac{B\max(\mathbf{H}_{h,\epsilon},N_{H})}{\delta}\right)$
(86) $\displaystyle=T_{h}.$ (87)

The analysis shows the difference in expressions from [20, Appendix B.3] given
our choice of confidence term and exploration rate that contain the variance
estimate, $B$. We also incorporate terms to handle the situations where
$N_{H}\geqslant\mathbf{H}_{h,\epsilon}$ or
$\left|\mathcal{S}_{h}\right|\geqslant\mathbf{H}_{h,\epsilon}$. Hence, if
neither of the events $\bar{\mathcal{A}}_{h}^{\prime}$ nor
$\bar{\mathcal{B}}_{h}$ occur, then the total number of samples for SSE, at
level $h$, prior to termination is at most

$\displaystyle\lceil T_{h}/2\rceil+\tau_{h}\leqslant\lceil
T_{h}/2\rceil+\sum_{i:(h,i)\in\mathcal{S}_{h}}N_{h,i}^{*}(t_{h})\leqslant
T_{h}.$ (88)

Finally, we bound the probability of occurrence of either event,
$\bar{\mathcal{A}}_{h}^{\prime}$ or $\bar{\mathcal{B}}_{h}$, where our
previous analysis to derive $T_{h}$ hinges on neither occurring. With
$\alpha=4$, this bound is unchanged from [21, Lemma 5].

$\displaystyle{\mathbb{P}}{\left(\bar{\mathcal{A}}_{h}^{\prime}\cup\bar{\mathcal{B}}_{h}\right)}={\mathbb{P}}{\left(\exists
t_{h}\in\left\\{{\left\lceil
T_{h}/2\right\rceil,\dots,T_{h}-1}\right\\}:\bigcup_{i:(h,i)\in\mathcal{S}_{h},i\neq
i^{*}}\mathcal{A}_{h,i}^{\prime}(t_{h})\bigcup_{i:(h,i)\in\mathcal{S}_{h}}\mathcal{B}_{h,i}(t_{h})\right)}$
(89) $\displaystyle\leqslant\sum_{t_{h}=\left\lceil
T_{h}/2\right\rceil}^{T_{h}-1}\frac{\left|\mathcal{S}_{h}\right|\delta}{N_{H}\alpha_{1}t_{h}^{3}}+\frac{3\delta\mathbf{H}_{h,\epsilon}}{4\alpha_{1}N_{H}t_{h}^{4}}$
(90) $\displaystyle\leqslant\sum_{t_{h}=\left\lceil
T_{h}/2\right\rceil}^{T_{h}-1}\frac{8\left|\mathcal{S}_{h}\right|\delta}{N_{H}\alpha_{1}T_{h}^{3}}+\frac{48\delta\mathbf{H}_{h,\epsilon}}{4\alpha_{1}N_{H}T_{h}^{4}}$
(91)
$\displaystyle\leqslant\left(\frac{T_{h}}{2}\right)\left(\frac{8\delta}{\alpha_{1}T_{h}^{3}}\right)\left(\frac{\left|\mathcal{S}_{h}\right|}{N_{H}}+\frac{3\mathbf{H}_{h,\epsilon}}{2N_{H}T_{h}}\right)$
(92)
$\displaystyle\leqslant\left(\frac{4\delta}{\alpha_{1}T_{h}^{2}}\right)\left(\frac{\left|\mathcal{S}_{h}\right|}{N_{H}}+\frac{3\mathbf{H}_{h,\epsilon}}{2N_{H}T_{h}}\right)$
(93) $\displaystyle<\frac{4\delta}{T_{h}^{2}},$ (94)

where (90) is a direct application of Lemma 3, and (94) comes from the fact
that $T_{h}\geqslant t^{\delta}_{h}\geqslant\mathbf{H}_{h,\epsilon}$. ∎

## References

  * [1] Nabil Akdim, Carles Navarro Manchón, Mustapha Benjillali, and Pierre Duhamel.  Variational hierarchical posterior matching for mmwave wireless channels online learning.  In 2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pages 1–5, Atlanta, Georgia, USA, 2020. IEEE.
  * [2] Ahmed Alkhateeb, Omar El Ayach, Geert Leus, and Robert W Heath.  Channel estimation and hybrid precoding for millimeter wave cellular systems.  IEEE Journal of Selected Topics in Signal Processing, 8(5):831–846, 2014.
  * [3] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári.  Exploration–exploitation tradeoff using variance estimates in multi-armed bandits.  Theoretical Computer Science, 410(19):1876–1902, 2009.
  * [4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2-3):235–256, 2002.
  * [5] Irmak Aykin and Marwan Krunz.  Efficient beam sweeping algorithms and initial access protocols for millimeter-wave networks.  IEEE Transactions on Wireless Communications, 19(4):2504–2514, 2020\.
  * [6] Nathan Blinn, Jana Boerger, and Matthieu Bloch.  mmwave beam steering with hierarchical optimal sampling for unimodal bandits.  In ICC 2021-IEEE International Conference on Communications, pages 1–6, Montreal, Quebec, 2021. IEEE.
  * [7] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.  Pure exploration in multi-armed bandits problems.  In International conference on Algorithmic learning theory, pages 23–37, Porto,Portugal, 2009. Springer.
  * [8] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári.  X-armed bandits.  Journal of Machine Learning Research, 12(May):1655–1695, 2011.
  * [9] Sung-En Chiu, Nancy Ronquillo, and Tara Javidi.  Active learning and csi acquisition for mmwave initial alignment.  IEEE Journal on Selected Areas in Communications, 37(11):2474–2489, 2019.
  * [10] Richard Combes and Alexandre Proutiere.  Unimodal bandits: Regret lower bounds and optimal algorithms.  In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 521–529, Bejing, China, 2014\. PMLR.
  * [11] Eyal Even-Dar, Shie Mannor, and Yishay Mansour.  Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.  Journal of machine learning research, 7(Jun):1079–1105, 2006.
  * [12] Aurélien Garivier and Emilie Kaufmann.  Optimal best arm identification with fixed confidence.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 998–1027, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * [13] 3GPP Radio Access Network Working Group et al.  Nr; nr and ng-ran overall description; stage 2 release 16.  Technical report, 3GPP TR 38.330 v.16.8.0, 2021.
  * [14] 3GPP Radio Access Network Working Group et al.  Physical channels and modulation release 17.  Technical report, 3GPP TR 38.211 v.17.0.0, 2021.
  * [15] Nikhil Gulati and Kapil R Dandekar.  Learning state selection for reconfigurable antennas: A multi-armed bandit approach.  IEEE Transactions on Antennas and Propagation, 62(3):1027–1038, 2013.
  * [16] M. Hashemi, A. Sabharwal, C. Emre Koksal, and N. B. Shroff.  Efficient beam alignment in millimeter wave systems using contextual bandits.  In IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, pages 2393–2401, Honolulu, HI, USA, 2018.
  * [17] Haitham Hassanieh, Omid Abari, Michael Rodriguez, Mohammed Abdelghany, Dina Katabi, and Piotr Indyk.  Fast millimeter wave beam alignment.  In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, SIGCOMM ’18, page 432–445, New York, NY, USA, 2018. Association for Computing Machinery.
  * [18] Shiwen He, Yan Zhang, Jiaheng Wang, Jian Zhang, Ju Ren, Yaoxue Zhang, Weihua Zhuang, and Xuemin Shen.  A survey of millimeter-wave communication: Physical-layer technology specifications and enabling transmission technologies.  Proceedings of the IEEE, 109(10):1666–1705, 2021.
  * [19] K. Jamieson and R. Nowak.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1–6, Princeton, NJ, USA, 2014.
  * [20] Shivaram Kalyanakrishnan.  Learning methods for sequential decision making with imperfect representations.  PhD thesis, 2011.
  * [21] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone.  Pac subset selection in stochastic multi-armed bandits.  In ICML, volume 12, pages 655–662, Edinburgh,Scotland, 2012.
  * [22] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On the complexity of best-arm identification in multi-armed bandit models.  The Journal of Machine Learning Research, 17(1):1–42, 2016.
  * [23] Emilie Kaufmann and Shivaram Kalyanakrishnan.  Information complexity in bandit subset selection.  In Conference on Learning Theory, pages 228–251, Barcelona, Spain, 2013. PMLR.
  * [24] Xingjian Li, Jun Fang, Huiping Duan, Zhi Chen, and Hongbin Li.  Fast beam alignment for millimeter wave communications: A sparse encoding and phaseless decoding approach.  IEEE Transactions on Signal Processing, 67(17):4402–4417, 2019\.
  * [25] Andreas F Molisch, Vishnu V Ratnam, Shengqian Han, Zheda Li, Sinh Le Hong Nguyen, Linsheng Li, and Katsuyuki Haneda.  Hybrid beamforming for massive mimo: A survey.  IEEE Communications Magazine, 55(9):134–141, 2017.
  * [26] Theodore S Rappaport, George R MacCartney, Mathew K Samimi, and Shu Sun.  Wideband millimeter-wave propagation measurements and channel models for future wireless communication system design.  IEEE transactions on Communications, 63(9):3029–3056, 2015.
  * [27] Theodore S Rappaport, Shu Sun, Rimma Mayzus, Hang Zhao, Yaniv Azar, Kevin Wang, George N Wong, Jocelyn K Schulz, Mathew Samimi, and Felix Gutierrez.  Millimeter wave mobile communications for 5g cellular: It will work!  IEEE access, 1:335–349, 2013.
  * [28] Maryam Eslami Rasekh, Zhinus Marzi, Yanzi Zhu, Upamanyu Madhow, and Haitao Zheng.  Noncoherent mmwave path tracking.  In Proceedings of the 18th International Workshop on Mobile Computing Systems and Applications, HotMobile ’17, page 13–18, New York, NY, USA, 2017. Association for Computing Machinery.
  * [29] Foad Sohrabi, Zhilin Chen, and Wei Yu.  Deep active learning approach to adaptive beamforming for mmwave initial alignment.  IEEE Journal on Selected Areas in Communications, 39(8):2347 – 2360, 2021.
  * [30] Vutha Va, Takayuki Shimizu, Gaurav Bansal, and Robert W Heath.  Online learning for position-aided millimeter wave beam training.  IEEE Access, 7:30507–30526, 2019.
  * [31] Yi Wei, Zixin Zhong, Vincent Y F Tan, and Chan Wang.  Fast beam alignment via pure exploration in multi-armed bandits.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 1911–1916, Finland, Espoo, 2022. IEEE.
  * [32] Edwin B Wilson.  Probable inference, the law of succession, and statistical inference.  Journal of the American Statistical Association, 22(158):209–212, 1927.
  * [33] Wen Wu, Nan Cheng, Ning Zhang, Peng Yang, Weihua Zhuang, and Xuemin Shen.  Fast mmwave beam alignment via correlated bandit learning.  IEEE Transactions on Wireless Communications, 18(12):5894–5908, 2019.
  * [34] Zhenyu Xiao, Tong He, Pengfei Xia, and Xiang-Gen Xia.  Hierarchical codebook design for beamforming training in millimeter-wave communication.  IEEE Transactions on Wireless Communications, 15(5):3380–3392, 2016\.
  * [35] Jia Yuan Yu and Shie Mannor.  Unimodal bandits.  In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 41–48, Bellevue, WA, USA, 2011.
  * [36] T. Zhao, M. Li, and M. Poloczek.  Fast reconfigurable antenna state selection with hierarchical thompson sampling.  In ICC 2019 - 2019 IEEE International Conference on Communications (ICC), pages 1–6, Shanghai, China, 2019.

  *[SSE]: Successive Subtree Elimination
  *[mmWave]: millimeter-Wave
  *[IoT]: Internet of Things
  *[MIMO]: Multiple-Input Multiple-Output
  *[HAD]: Hybrid Analog-Digital
  *[RF]: Radio Frequency
  *[HPM]: Hierarchical Posterior Matching
  *[CSI]: Channel State Information
  *[DNN]: Deep Neural Network
  *[RSS]: Received Signal Strength
  *[CS]: Compressed Sensing
  *[MAB]: Multi-Armed Bandit
  *[UCB]: Upper-Confidence Bound
  *[UBA]: Unimodal Beam Alignment
  *[UE]: User Equipment
  *[BS]: Base Station
  *[OSUB]: Optimal Sampling for Unimodal Bandits
  *[TS]: Thompson Sampling
  *[HBA]: Hierarchical Beam Alignment
  *[2PHTS]: Two Phase Heteroscedastic Track-and-Stop
  *[PAC]: probably approximately correct
  *[SRS]: Sounding Reference Signal
  *[AoA]: Angle of Arrival
  *[SNR]: Signal-to-Noise Ratio
  *[BAI]: Best Arm Identification
  *[LCB]: Lower-Confidence Bound


CR-2023/006 August 28, 2024

Machine Learning in Top Physics in the ATLAS and CMS Collaborations

Philip Keicher111Work supported by the Ministry for Education and Research
(BMBF).
Copyright 2023 CERN for the benefit of the ATLAS and CMS Collaborations.
Reproduction of this article or parts of it is allowed as specified in the CC-
BY-4.0 license

Institute of Experimental Physics
University of Hamburg, D-22761 Hamburg, GERMANY

> Machine learning is essential in many aspects of top-quark related physics
> in the ATLAS and CMS Collaborations. This work aims to give a brief overview
> over current applications in the two collaborations as well as on-going
> studies for future applications.

> PRESENTED AT
>
>
>
>
> $15^{\mathrm{th}}$ International Workshop on Top Quark Physics
> Durham, UK, 4–9 September, 2022

##  1 Introduction

Machine learning (ML) applications are nowadays well-established tools in
modern data science problems. An increasing number of techniques and analyses
in high-energy physics are harnessing the capabilities of these methods. Many
of these applications within the community are related to the top quark due to
its rich phenomenology within both the standard model of particle physics (SM)
and beyond. Most of these applications for top quark physics within the ATLAS
[1] and CMS [2] Collaborations can be separated according to three paradigms.
First, ML applications are used as tagging algorithms to identify top quarks.
Second, ML is used to reconstruct top quark properties. Finally, ML is used to
construct observables that have a strong separation of signal and background
processes, thus further increasing the statistical power of analyses. Some
select examples of the usage of ML techniques in these fields within both
ATLAS and CMS Collaborations can be found in the references of this work.

This work focuses on the last field of applications described above.
Specifically, the ML usage of an example from each collaboration and a summary
of select ongoing projects is presented. For a more thorough review of the
analyses, please refer to Refs. [3, 4].

##  2 Machine learning for a probe of EFT operators in the associated
production of top quarks with a Z boson at the CMS experiment

The search for physics beyond the SM is crucial to increase our knowledge of
the fundamental mechanisms of particle physics. For this purpose, effective
field theories (EFTs) have proven themselves as a promising tool. Their
general concept is to extend the known Lagrange function ${\cal L}$ with
additional operators ${\cal O}$ such that

${\cal L}={\cal
L}_{\text{SM}}+\sum_{d>4}^{N}\sum_{i}\frac{c_{i}^{(d)}}{\Lambda^{d-4}}{\cal
O}_{i}^{(d)}.$

In this equation, $d$ refers to the dimension of the operators, $N$ denotes
the maximum dimension of additional operators considered and $\Lambda$ denotes
the energy scale for new physics. The parameters $c_{i}$ are known as the
Wilson coefficients and indicate the contribution of the corresponding
operator to the extension of the SM Lagrangian ${\cal L}_{\text{SM}}$.

The CMS analysis described in Ref. [3] probes these coefficients in the
context of the production of top quarks in association with Z bosons. To this
end, the analysis considers three signal processes that are sensitive to a
different variety of operators: the production of a top quark-antiquark pair
in association with a Z boson ($\text{t}\overline{\text{t}}\text{Z}$) as well
as the production of a single top quark in association with a Z boson and a W
boson (tZW) or an additional jet (tZq). The analysis defines two signal
regions based on the number of leptons in the final state as well as
additional control regions designed to control the dominant background
processes during the estimation of the Wilson coefficients relevant for this
analysis. ML algorithms are employed in the region with three leptons, which
is the focus of the following paragraphs.

Figure 1: Events are first categorized according to three classes within the
SM (top left). Events classified as either tZq or
$\text{t}\overline{\text{t}}\text{Z}$ are then considered for a binary
classification to increase the sensitivity to EFT contributions (bottom left).
The resulting distributions are expected to be sensitive to different values
of the corresponding Wilson coefficients (right). Figure adapted from Ref.
[3].

The ML application in this analysis can be divided into two parts. First,
events are categorized using a multi-classification approach, which is based
on kinematic variables, a b tagging discriminant as well as other more complex
variables. The architecture of this classifier is summarized in Fig.1. It
employs three fully-connected hidden layers with 100 neurons in each layer,
which are activated with the ReLU function. The loss function during the
training consists of the sum of the categorical cross-entropy function and L2
regularization. To mitigate possible over-training effects, dropout and early
stopping are employed during training, which is based on simulated events
corresponding to the dominant physics processes in the analysis phase space.
The target of this classification is to attribute these events according to
three categories. The first two categories correspond to the tZq and the
$\text{t}\overline{\text{t}}\text{Z}$ signal processes, while all other events
are categorized as background processes. The tZW signal process is not
specifically considered in the categorization task due to its small
contribution to the phase space and the significant kinematic similarities
with the other signal processes. The output values of the final layer are
activated using the softmax function, which assigns each event a probabilistic
value for each of these classes. Events are attributed to the class with the
largest activation value in the final layer. This approach yields excellent
control over the SM processes, which is consequently used to increase the
sensitivity to the EFT parameters under scrutiny.

The second part of the ML application in this analysis targets possible EFT
contributions to the signal processes under consideration of interference
effects with the SM and other EFT operators. To this end, different sets of
binary classifiers are trained with events categorized as either
$\text{t}\overline{\text{t}}\text{Z}$ or tZq by the previously-described
multi-classification, respectively. Each set consists of classifiers designed
to separate contributions under the SM hypothesis from contributions of either
specific EFT operators or their superposition, resulting in a total of eight
binary classifiers. A schematic representation of these classifiers is shown
in Fig. 1. Each classifier is based on a dedicated set of input features which
are propagated through an architecture with three hidden layers consisting of
50 rectified linear units, respectively. The final output layer employs the
sigmoid activation function. The loss function of these classifiers consists
of the binary cross-entropy function as well as a L2 regularization term.

During the training, events are weighted according to the probability density
obtained for a wide range of values for the Wilson coefficients corresponding
to the most dominant EFT operators. This facilitates a training under
consideration of different interference effects without a bias to preexisting
results. An example for the expected sensitivity to different values of Wilson
coefficients is shown in Fig. 1, which indicates increasing separation power
for larger contributions of EFT operators. The authors of Ref. [3] show that
this strategy can increase the sensitivity to different Wilson coefficients by
up to $70\,\%$, indicating the importance of ML in this analysis.

##  3 Machine learning in a measurement of charge asymmetry with the ATLAS
experiment

Figure 2: Shown is the distribution of output values of the binary classifier
for simulated events as well as observed data (middle panel). Events are
divided into two regions based on this distribution (red line), and
subsequently used in the unfolding procedure (panels on left and right).
Figure adapted from Ref. [4].

Another promising avenue in the search for physics beyond the SM is to perform
high-precision measurements in the context of the SM itself. In these
approaches, unfolding techniques are powerful and useful tools that aim to
revert effects impeding the accuracy of a measurement arising from the
detector. This facilitates a direct comparison of measured quantities with the
corresponding theoretical predictions.

The analysis presented in Ref. [4] performs such a measurement for the charge
asymmetry between the top quark and antiquark with data obtained with the
ATLAS detector. Such an asymmetry ensues by interference effects at next-to-
leading order in quark-initiated production of a $\text{t}\overline{\text{t}}$
pair, which is difficult to identify since this production is dominated by
gluon-induced processes at the LHC. Therefore, the analysis requires the
presence of an additional photon in the final state to increase the selection
efficiency of quark-induced $\text{t}\overline{\text{t}}$ events. The
resulting analysis phase space is dominated by background processes, which
comprise about $70\,\%$ of the selected events.

The analysis relies on a binary classification to further enhance the signal
purity. The model architecture consists of three hidden layers with up to 96
parametric rectified linear units, while the final layer consists of a single
node using the softmax activation function. The binary cross-entropy is used
as the loss function during training, which is based on simulated events and
kinematic properties of the final state particles as well as additional
information about the b tagging and the event shape. Apart from a separation
of the training data into training, validation and test data sets, the
analysis employs 5-fold cross validation, which enables an optimal usage of
the available events. The output values of this neural network is subsequently
used to define a background-enriched and a signal-enriched region in the phase
space, which is illustrated in Fig. 2. This reduces the background
contamination in the signal region to approximately $45\,\%$, thus greatly
increasing the sensitivity of this analysis.

##  4 Future applications

Machine learning in the top quark sector is a fast evolving field in both the
ATLAS and CMS Collaborations. On the one hand, this involves augmenting
existing applications of ML with novel architectures. One example of this
approach is presented in Ref. [5], where the existing b tagging algorithm used
within CMS was enhanced by a Transformer architecture. This increases the
selection efficiency of b jets, which is expected to have a direct impact on
the reconstruction efficiency of top quarks.

Apart from researching novel architectures, understanding and improving the
training samples is equally crucial to improve future applications. An example
for this type of research is presented in Ref. [6]. The authors investigated a
subset of architectures that showed good identification power for top quarks
in the study presented in Ref. [7], which was based on a fast detector
simulation. In Ref. [6], these models were trained with a full detector
simulation, which is expected to increase the precision of the simulations
used during the training. The authors show that the performance of these
architectures can depend significantly on the precision of the detector
simulation, indicating the need to consider such effects when constructing and
training a ML algorithm. The data set used in this study is publicly available
in CERN OpenData.

On the other hand, novel fields for ML applications are under investigation.
One of the most challenging aspects in top-quark related analyses is currently
the estimation of systematic uncertainties, which is a critical aspect in many
measurements. Due to the high complexity of the underlying effects, the
estimation of these uncertainties often requires dedicated simulations, which
are computationally expensive. These Monte Carlo samples are therefore
produced with a limited amount of events, which can impede the statistical
power of the estimation depending on the phase space used in a given analysis.

One possible solution for this problem could be the DCTR approach, which is
presented in Ref. [8]. The authors show that a binary classification to
separate simulations with different parameter values of the underlying
generator can be used to reweigh the events from one set into the other. This
would potentially enable a continuous reweighing procedure based on the full
phase-space information, thus increasing the interpretability of the
uncertainty estimates and reducing the computational expenses. The
applicability of this method within the collaborations is currently under
investigation.

ACKNOWLEDGEMENTS

Special thanks to my colleagues in the ATLAS and CMS Collaborations for
providing material and reviewing this work.

## References

  * [1] The ATLAS Collaboration  “The ATLAS Experiment at the CERN Large Hadron Collider”  In _JINST_ 3.08, 2008, pp. S08003  DOI: 10.1088/1748-0221/3/08/S08003
  * [2] The CMS Collaboration  “The CMS experiment at the CERN LHC”  In _JINST_ 3.08, 2008, pp. S08004  DOI: 10.1088/1748-0221/3/08/S08004
  * [3] The CMS Collaboration  “Probing effective field theory operators in the associated production of top quarks with a Z boson in multilepton final states at $\sqrt{s}$ = 13 TeV”  In _JHEP_ 12, 2021, pp. 083  DOI: 10.1007/JHEP12(2021)083
  * [4] The ATLAS Collaboration  “Measurement of the charge asymmetry in top-quark pair production in association with a photon with the ATLAS experiment”, 2022  arXiv:2212.10552 [hep-ex]
  * [5] Huilin Qu, Congqiao Li and Sitian Qian  “Particle Transformer for Jet Tagging”  arXiv, 2022  DOI: 10.48550/ARXIV.2202.03772
  * [6] The ATLAS Collaboration  “Constituent-Based Top-Quark Tagging with the ATLAS Detector”, 2022  URL: https://inspirehep.net/literature/2151246
  * [7] Anja Butter  “The Machine Learning landscape of top taggers”  In _SciPost Phys._ 7, 2019  DOI: 10.21468/SciPostPhys.7.1.014
  * [8] Anders Andreassen and Benjamin Nachman  “Neural Networks for Full Phase-space Reweighting and Parameter Tuning”  In _Phys. Rev. D_ 101.9, 2020  DOI: 10.1103/PhysRevD.101.091901
  * [9] Emil Bols et al.  “Jet Flavour Classification Using DeepJet”  In _JINST_ 15.12, 2020  DOI: 10.1088/1748-0221/15/12/P12012
  * [10] The CMS Collaboration  “Evidence for the simultaneous production of four top quarks in proton-proton collisions at $\sqrt{s}$ = 13 TeV”, 2022  URL: https://cds.cern.ch/record/2827591
  * [11] Suyong Choi, Jaehoon Lim and Hayoung Oh  “Data-driven Estimation of Background Distribution through Neural Autoregressive Flows”, 2020  arXiv:2008.03636 [hep-ph]
  * [12] The ATLAS Collaboration  “Search for flavour-changing neutral-current couplings between the top quark and the photon with the ATLAS detector at $\sqrt{s}=13$ TeV”  In _Phys. Lett. B_ , 2022  DOI: 10.1016/j.physletb.2022.137379
  * [13] The ATLAS Collaboration  “Measurement of the $t\overline{t}t\overline{t}$ production cross section in $pp$ collisions at $\sqrt{s}$ = 13 TeV with the ATLAS detector”  In _JHEP_ 11, 2021  DOI: 10.1007/JHEP11(2021)118
  * [14] The ATLAS Collaboration  “Search for flavour-changing neutral current interactions of the top quark and the Higgs boson in events with a pair of $\tau$-leptons in pp collisions at $\sqrt{s}=13$ TeV with the ATLAS detector”, 2022  DOI: 10.48550/arXiv.2208.11415
  * [15] The ATLAS Collaboration  “Observation of single top-quark + photon production with the ATLAS detector”, 2022  DOI: 10.48550/arXiv.2205.03145
  * [16] The ATLAS Collaboration  “Probing the $CP$ nature of the top-Higgs Yukawa coupling in $t\overline{t}H$ and $tH$ events with $H\rightarrow b\overline{b}$ using the ATLAS detector at the LHC”, 2022  URL: http://cds.cern.ch/record/2805772
  * [17] Alexander Shmakov et al.  “SPANet: Generalized permutationless set assignment for particle physics using symmetry preserving attention”  In _SciPost Phys._ 12.5, 2022  DOI: 10.21468/SciPostPhys.12.5.178
  * [18] The CMS Collaboration  “Measurement of the top quark pole mass using $t\overline{t}$+jet events in the dilepton final state in proton-proton collisions at $\sqrt{s}$ = 13 TeV”, 2022  arXiv:2207.02270 [hep-ex]
  * [19] The CMS Collaboration  “Search for new physics using effective field theory in 13 TeV pp collision events that contain a top quark pair and a boosted Z or Higgs boson”, 2022  arXiv:2208.12837 [hep-ex]
  * [20] The CMS Collaboration  “Measurement of the cross section of top quark-antiquark pair production in association with a W boson in proton-proton collisions at $\sqrt{s}$ = 13 TeV”, 2022  arXiv:2208.06485 [hep-ex]