  Beam alignment (BA) is to ensure the transmitter and receiver beams are
accurately aligned to establish a reliable communication link in
millimeter-wave (mmwave) systems. Existing BA methods search the entire beam
space to identify the optimal transmit-receive beam pair, which incurs
significant BA latency on the order of seconds in the worst case. In this
paper, we develop a learning algorithm to reduce BA latency, namely
Hierarchical Beam Alignment (HBA) algorithm. We first formulate the BA problem
as a stochastic multi-armed bandit problem with the objective to maximize the
cumulative received signal strength within a certain period. The proposed
algorithm takes advantage of the correlation structure among beams such that
the information from nearby beams is extracted to identify the optimal beam,
instead of searching the entire beam space. Furthermore, the prior knowledge on
the channel fluctuation is incorporated in the proposed algorithm to further
accelerate the BA process. Theoretical analysis indicates that the proposed
algorithm is asymptotically optimal. Extensive simulation results demonstrate
that the proposed algorithm can identify the optimal beam with a high
probability and reduce the BA latency from hundreds of milliseconds to a few
milliseconds in the multipath channel, as compared to the existing BA method in
IEEE 802.11ad.
