Fast mmwave Beam Alignment via Correlated Bandit Learning

• Exhaustive search scans all transmitter-receiver beam combinations, while mobility repeatedly invokes alignment and IEEE 802.11ad may take seconds with many candidate beams.Source: §I · p. 2
• The paper formulates beam alignment as a stochastic multi-armed bandit that sequentially selects beams to maximize cumulative received signal strength over a period.Source: §I · p. 3
• HBA incorporates prior knowledge of channel fluctuation to accommodate reward uncertainty, avoid excessive exploration, and further accelerate alignment.Source: §I · p. 3
• HBA identifies the optimal beam with high probability using fewer measurements in multipath channels, even with coarse prior knowledge, and reduces latency by orders of magnitude versus IEEE 802.11ad.Source: §I · p. 3
• In multipath channels, the mean RSS function's multimodality characterizes beam correlation, so measurements of a beam also inform nearby beams and help narrow the search.Source: §I · pp. 2–4
• A sublinear regret bound, O(√T log T), indicates that HBA is asymptotically optimal.Source: §I · p. 4

II. RELATED WORK

• Prior solutions include compressed-sensing alignment with O(L log N) measurements when accurate phase information is available, and multi-resolution search that progresses from wide to narrow beams,.Here, L is the number of channel paths and N the number of beams.Source: §II · p. 4
• Prior work includes hierarchical codebook search jointly using sub-array and deactivation techniques, orthogonal-pilot low-overhead beam alignment for multiuser mmWave systems, and Wi-Fi out-of-band information to identify the optimal beam.Source: §II · p. 4
• Bandit-based prior work includes a unimodal method for static single-path channels and a distributed method based on adversarial bandit theory.Source: §II · p. 5
• Earlier approaches do not provide a method for fast, accurate beam alignment in complicated multipath channels; this work uses beam correlation and prior knowledge to address that gap.The authors distinguish their approach by leveraging correlation among nearby beams and using RSS.Source: §II · pp. 4–5

A. Beam Alignment Model

• The modeled system is a static point-to-point mmwave link with uniform linear arrays; the receiver stays quasi-omnidirectional while the transmitter scans beams.The channel uses a sparse clustered model with one dominant LOS path and additional NLOS paths.Source: A. Beam Alignment Model · p. 5
• In the IEEE 802.11ad procedure, measuring every transmit beam to find the maximum-magnitude received signal leads to high measurement complexity and latency as the beam space grows.Source: A. Beam Alignment Model · pp. 6–7

B. Problem Formulation

• Each candidate beam is a bandit arm, and its observed RSS is a random reward affected by channel fluctuation; the formulation assumes Gaussian reward variance σ^2 for simplicity.The authors state that the algorithm can also be applied to non-Gaussian settings, as validated in Section VI.Source: B. Problem Formulation · p. 7
• The policy selects beams sequentially to maximize expected cumulative RSS over T time slots, with the selected beam and observed RSS forming the history used for later choices.Source: B. Problem Formulation · p. 7
• Nearby beams have correlated RSS, while channel-fluctuation prior knowledge can account for reward uncertainty; the authors use both properties to accelerate convergence and reduce BA latency.Source: B. Problem Formulation · p. 8

IV. FAST BEAM ALIGNMENT

• The fast beam-alignment approach first characterizes the multimodal mean-RSS structure, then uses correlation and prior knowledge to identify the optimal beam.Source: §IV · p. 8

A. Correlation Structure

• The paper defines unimodality as a path from any beam to the optimal beam along which mean reward increases, so there are no local optimal beams.Source: A. Correlation Structure · p. 8
• In a single-path channel the mean RSS over beams is unimodal, whereas in multipath it is multimodal, with the LOS path causing the dominant peak and NLOS paths causing other peaks.For the illustrated two-path, 128-beam case, the LOS peak is around 10 dB higher than the NLOS peak.Source: A. Correlation Structure · p. 9, Figure 3 · p. 10
• A dissimilarity function q(x1, x2) = w∥x1 − x2∥^β represents reward discrepancy between points, using smoothness of nearby rewards to support faster alignment.The text states that nearby points normally have similar rewards and bounded dissimilarity.Source: A. Correlation Structure · p. 10

B. Prior Knowledge

• Known channel-fluctuation variance accommodates reward uncertainty and reduces exploration; it can be collected during initialization or periodically, since statistics change slowly in static environments.The algorithm can also use coarse prior knowledge, at the cost of slower convergence or lower beam-detection accuracy.Source: B. Prior Knowledge · p. 10

C. Hierarchical Beam Alignment (HBA) Algorithm

• HBA adapts and extends HOO [29] for multimodal rewards, using prior channel-variance knowledge and Bayesian principles to set a confidence margin that avoids unnecessary exploration.The margin is intended to accelerate convergence compared with HOO’s larger margin for accommodating reward uncertainty.Source: C. Hierarchical Beam Alignment (HBA)… · p. 11
• HBA explores more intensively around well-performing beams by incrementally expanding a search tree, measuring selected beams, and updating the tree to narrow the search region.Tree nodes represent search regions, with deeper nodes representing smaller regions.Source: C. Hierarchical Beam Alignment (HBA)… · p. 11
• The search stops when the region width is below ζ/N, selecting a beam in the final region; larger ζ speeds convergence but lowers detection accuracy.The stopping condition is x_H − x_L < ζ/N, where 0 < ζ < 1.Source: C. Hierarchical Beam Alignment (HBA)… · p. 14
• HBA explores regions with high estimated maximum rewards intensively and others loosely, making it more efficient than exhaustive search.The method uses high estimated rewards (Q-values) to identify regions where the optimal beam is likely to be located.Source: C. Hierarchical Beam Alignment (HBA)… · p. 14
• HBA begins with the entire beam region and adaptively partitions it, gradually zooming toward the region containing the optimal beam.The paper illustrates this zooming process in Fig. 4(a).Source: C. Hierarchical Beam Alignment (HBA)… · pp. 14–15, Figure 4 · p. 15
• Selected beams progress from random locations across the full region to locations nearer the dominant peak and finally around the optimal beam.The illustrated batches show intensive exploration near good beams and looser exploration elsewhere.Source: C. Hierarchical Beam Alignment (HBA)… · p. 15, Figure 4 · p. 15

D. Complexity Analysis

• HBA stores T tree nodes after T time slots, giving linear storage complexity O(T).The tree adds one node at each time slot.Source: D. Complexity Analysis · p. 15
• Updating the attributes of all tree nodes makes the running time per time slot linear.Source: D. Complexity Analysis · p. 15
• Across T time slots, HBA has computational complexity O(T^2).Source: D. Complexity Analysis · p. 15
• The terminating condition makes the tree finite, bounding both storage and computational complexity.Source: D. Complexity Analysis · p. 15

V. REGRET PERFORMANCE ANALYSIS

• Under the weak Lipschitz condition, the reward function avoids sharp valleys near the optimum, and the condition applies only near that point.The paper describes this condition as mild and well justified in many practical applications.Source: §V · pp. 15–16
• The regret analysis assumes bounded region diameters and well-shaped regions, which bound reward variation within each region.The paper states that its reward-function regions satisfy both conditions.Source: §V · p. 16
• Suboptimal nodes are visited a logarithmic number of times, and higher channel-fluctuation variance requires more exploration to resolve reward uncertainty.Source: §V · pp. 16–17
• HBA’s expected cumulative regret is sublinear in T, making the algorithm asymptotically optimal as it converges to the optimal beam.For finite horizons, the regret bound characterizes convergence speed.Source: §V · p. 17

A. Simulation Setup

• The simulated IEEE 802.11ad system operates at 60 GHz with 2.16 GHz bandwidth, a 20 m transmission distance, and 50 dBm average EIRP.The EIRP is described as consistent with FCC regulations for 60 GHz unlicensed bands,.Source: A. Simulation Setup · p. 17
• The channel model uses up to five paths—one dominant LOS and four NLOS—with extra NLOS path loss uniformly distributed from 7 to 13 dB.Shadow fading follows N(0, σ^2), with σ set to 2 dB.Source: A. Simulation Setup · pp. 17–18
• Results are averaged over 50,000 Monte Carlo samples with different channel fading and locations; HBA parameters ρ1=3, γ=0.5, and ζ=0.1 were selected through extensive trials.Source: A. Simulation Setup · p. 18
• HBA is compared with IEEE 802.11ad scanning, UCB, UBA, and HOO as benchmark methods.UCB does not exploit both correlation structures; UBA exploits unimodal beam structure, and HOO exploits beam correlation.Source: A. Simulation Setup · p. 18

B. Regret Performance

• HBA achieves bounded regret, outperforms the benchmarks, and converges to the optimal beam in about 25 time slots.The paper attributes its faster convergence to combining correlation structure with prior information.Source: B. Regret Performance · pp. 18–19, Figure 5 · p. 19
• UBA's unimodal-beam assumption mismatches the multipath reward's multimodal structure, producing worse performance than not exploiting correlation.UBA performs poorly in multipath, unlike HBA.Source: B. Regret Performance · p. 19, C. Measurement Complexity and Beam… · p. 21
• Regret under uniform and Rayleigh channel fluctuations is very close to Gaussian, while higher fluctuation variance raises regret.The paper relates higher variance to greater exploration effort.Source: B. Regret Performance · p. 19

C. Measurement Complexity and Beam Detection Accuracy

• As the number of paths increases, measurement counts increase slightly, while beam detection accuracy decreases from 99.6% in a single-path channel to 97.4%.Source: C. Measurement Complexity and Beam… · p. 21
• For 512 beams, the proposed algorithm needs around 40 measurements to identify the optimal beam, reducing the number of measurements by 12 times.Source: C. Measurement Complexity and Beam… · p. 20
• The measurement count increases by 32% as transmission distance increases; at 50 meters with N = 256, the algorithm needs about 44 measurements, 5.8 times fewer than 802.11ad.Source: C. Measurement Complexity and Beam… · pp. 21–22
• Overestimating prior knowledge increases measurements but can improve detection accuracy; underestimating it slightly reduces measurements while accuracy decreases.The paper attributes overestimation's additional exploration to a larger confidence margin.Source: C. Measurement Complexity and Beam… · p. 22
• Even with coarse prior knowledge, HBA substantially reduces measurements versus benchmarks and achieves high beam detection accuracy.Source: C. Measurement Complexity and Beam… · p. 22

D. BA Latency

• Latency accounting includes protocol and feedback overhead; if BA misses the current A-BFT stage, it waits for the next beacon interval, set to 100 ms in simulation.Source: D. BA Latency · p. 23
• For 256 beams, one user's BA latency drops from 106.07 ms to 0.94 ms; for four users, it falls from more than 700 ms to about 2.35 ms.Source: D. BA Latency · p. 23

VII. CONCLUSION

• HBA uses beam correlation and prior channel-fluctuation knowledge to accelerate BA and identify the optimal beam with few measurements, even for large beam counts.Source: §VII · p. 24
• The authors state that HBA can meet delay-sensitive Gbps application demands, including cordless virtual-reality gaming.Source: §VII · p. 24

A. Proof of Theorem 1

• In the single-path channel, mean RSS increases toward the optimal beam and decreases away from it, establishing a unimodal beam-space function.Source: A. Proof of Theorem 1 · p. 24

B. Proof of Corollary 1

• In multipath, aggregated RSS combines unimodal path functions into a multimodal function, with the dominant peak corresponding to the LOS path.Source: B. Proof of Corollary 1 · p. 25

C. Proof of Lemma 1

• To bound expected visits to a selected node, the proof follows its root-to-node path and identifies the deepest optimal node on that path.Source: C. Proof of Lemma 1 · p. 25
• After more than m visits, the probability of selecting a node in a region is bounded by the probabilities that the optimal-node Q-value is below f* or the region's E-value is at least f*.Source: C. Proof of Lemma 1 · p. 26
• The proof bounds three terms separately and substitutes those intermediate bounds to obtain an upper bound.Source: C. Proof of Lemma 1 · pp. 26, 28

D. Proof of Theorem 2

• The proof decomposes total regret into contributions from T1, T2, and T3, then bounds each subtree separately.T1 contains ΦH and its descendants; T2 and T3 collect specified near-optimal nodes at depths below H.Source: D. Proof of Theorem 2 · p. 29
• T2 regret is bounded by a constant because T2 is a finite tree.The proof also bounds T1 using the fact that |T1| ≤ T and that its beams are 4ρ1γH-optimal.Source: D. Proof of Theorem 2 · p. 29
• For T3, nodes in Ωh are 4ρ1γh−1-optimal, their count is below 2|Φh−1|, and their expected sampling count is bounded using Lemma 1.The proof uses these properties to derive the T3 regret bound.Source: D. Proof of Theorem 2 · p. 30
• Choosing γH on the order of (T/log T)−1/(κ+2) yields the stated rate, while known smoothness permits α = β and κ = 0.The passage attributes these parameter choices to.Source: D. Proof of Theorem 2 · p. 30