  The beam alignment (BA) problem consists in accurately aligning the
transmitter and receiver beams to establish a reliable communication link in
wireless communication systems. Existing BA methods search the entire beam
space to identify the optimal transmit-receive beam pair. This incurs a
significant latency when the number of antennas is large. In this work, we
develop a bandit-based fast BA algorithm to reduce BA latency for
millimeter-wave (mmWave) communications. Our algorithm is named Two-Phase
Heteroscedastic Track-and-Stop (2PHT\&S). We first formulate the BA problem as
a pure exploration problem in multi-armed bandits in which the objective is to
minimize the required number of time steps given a certain fixed confidence
level. By taking advantage of the correlation structure among beams that the
information from nearby beams is similar and the heteroscedastic property that
the variance of the reward of an arm (beam) is related to its mean, the
proposed algorithm groups all beams into several beam sets such that the
optimal beam set is first selected and the optimal beam is identified in this
set after that. Theoretical analysis and simulation results on synthetic and
semi-practical channel data demonstrate the clear superiority of the proposed
algorithm vis-\`a-vis other baseline competitors.
