Online Learning for Position-Aided Millimeter Wave Beam Training

I. INTRODUCTION

• Risk-aware beam-pair selection uses UCB to select high-risk pairs less often, balancing early-stage users’ learning burden against learning speed.The paper also analyzes the regret cost introduced by risk-awareness.Source: §I · pp. 1, 3
• Beam refinement is formulated as a continuum-armed bandit and adapts HOO with modifications, while the two-layer hierarchy refines only directions selected by beam selection.The paper states that this hierarchy is more efficient than learning refined directions directly.Source: §I · pp. 1–3
• With 16×16 arrays and a training budget of 30 beam pairs, the method gains an average 1dB over exhaustive search over 2712 beam pairs within 100 time steps.The reported gain reaches about 1.5dB over time.Source: §I · p. 2
• Prior position-aided methods include offline measurement databases, supervised learning, and scatterer-based approaches; this paper limits its context to transmitter and receiver position and proposes online multi-armed bandit learning.The cited prior MAB beam-training methods use single-play formulations or rely on unimodal success probability, which random blockage may not guarantee.Source: §I · pp. 2–3

A. System model

• The system model assumes uniform planar arrays, half-wavelength element spacing, one RF chain, no backplane radiation, and a progressive-phase codebook with beams separated by their 3dB beamwidths.The codebook covers the +z half-space.Source: A. System model · pp. 3–4, Figure 1 · p. 4

B. Data model

• The evaluation uses 10,000 ray-traced channel samples at 60GHz for a 16×16 UPA at both ends, with a 5m location bin and antennas at 7m (BS) and 1.5m (MU).Vehicles are cars and trucks on a two-lane street; the larger trucks can block the mobile user.Source: B. Data model · p. 4

III. POSITION-AIDED BEAM ALIGNMENT

• Geometry can leave only a few plausible directions at a location, such as LOS and building-reflection paths; simulations allow position error within a 5m bin, with 30 trained pairs yielding negligible loss for 16×16 arrays.Overlapping bins can mitigate edge effects at bin boundaries.Source: §III · pp. 4–5, Figure 3 · p. 5

A. Overview of the proposed position-aided beam alignment

• In the uplink, the MU sends its position, the BS returns a promising beam-pair subset, and the MU trains those pairs and feeds back the best index; the BS maintains the database.The subset size trades training overhead against alignment accuracy, and different selection methods can be used in the framework.Source: A. Overview of the proposed… · p. 5, Figure 4 · p. 5

B. Quantifying beam alignment accuracy

• Power loss captures beam-misalignment severity, distinguishing alignments 3 dB versus 10 dB from optimal; the former likely still provides a good link, while the latter likely cannot.With an unmodified codebook, ξ ≥1 always; with refinement, ξ < 1 is possible.Source: B. Quantifying beam alignment accuracy · pp. 5–6

C. Offline inverse fingerprinting beam pair selection

• AvgPow selects beam pairs by average channel strength, while MinMisProb targets misalignment probability.The database contains beam-pair channel strengths measured at location bins.Source: C. Offline inverse fingerprinting beam… · p. 6
• Offline MinMisProb minimizes misalignment probability by greedily selecting pairs with the highest estimated probability of being optimal.The method is based on offline inverse fingerprinting.Source: C. Offline inverse fingerprinting beam… · p. 6
• Risk-aware online MinMisProb rejects selected pairs according to their risk of low received power and replaces them using both MinMisProb and AvgPow.This is intended to reduce severe misalignment during learning.Source: C. Offline inverse fingerprinting beam… · p. 6

IV. PROPOSED TWO-LAYER ONLINE LEARNING

• The two-layer learner selects coarse promising directions, optionally refines them, trains the subset, and updates position-specific learning parameters from measurements.Refinement is restricted to promising directions.Source: §IV · p. 6, Figure 5 · p. 7

A. Problem statement

• Online MinMisProb estimates unknown selection probabilities on the fly, screening beam pairs through a small offline database to reduce the candidate set when large codebooks make repeated sampling slow.In simulations, an offline database of N = 5 and C = 200 was used for screening.Source: A. Problem statement · p. 7

B. Greedy UCB algorithm

• Treating every candidate subset as an independent super-arm is inefficient because the number of possible subsets is large.The algorithm instead leverages dependence between subsets through the modularity property.Source: B. Greedy UCB algorithm · p. 7
• Because the probability of being optimal is modular, the subset reward decomposes into individual beam-pair rewards, enabling greedy selection by UCB indices.The events that each pair is optimal are mutually exclusive; a UCB index combines observed expected reward with an uncertainty margin.Source: B. Greedy UCB algorithm · p. 7
• The practical binary reward assigns 1 to the strongest pair trained in a subset and 0 to the others, since the best pair across all candidates is unknown.The ideal reward would identify the best pair in the candidate set, but only trained pairs are measured.Source: B. Greedy UCB algorithm · p. 7
• The estimated expected reward is Xtot[i]/Ti, where Xtot tallies times pair i had the strongest measurement and Ti counts its selections.The update increments the tally for the strongest measured pair in the trained subset.Source: B. Greedy UCB algorithm · p. 8
• Convergence of this alternative reward estimate to the true probability of being optimal is not established; the paper leaves guarantees under suitable assumptions to future work.The authors describe this as outside the paper’s focus.Source: B. Greedy UCB algorithm · p. 8
• In multiple-play training, balancing exploitation and exploration trades off the risk of large power losses against the time needed to learn accurate arm statistics.The binary reward also discards the magnitude of beam measurements.Source: B. Greedy UCB algorithm · p. 8

C. Risk-aware greedy UCB algorithm

• A binary risk signal marks a beam pair as risky when its channel strength falls below the best pair in the trained set by the risk threshold.The signal uses a ratio of channel strengths because the optimal pair’s strength may be unknown, especially early in learning.Source: C. Risk-aware greedy UCB algorithm · p. 8
• A Beta prior updated from observed binary signals represents uncertainty in each beam pair’s risk estimate.The Beta distribution is conjugate to the Bernoulli risk signal, so observations update its parameters conveniently.Source: C. Risk-aware greedy UCB algorithm · p. 8
• The algorithm draws a risk estimate from the prior and scales it by a confidence margin to set the probability of rejecting the greedy UCB selection.The margin helps ensure that good pairs are accepted with increasing probability over time, despite nonzero risk from blockage.Source: C. Risk-aware greedy UCB algorithm · p. 8
• When a selected pair is rejected, replacement selection uses the estimated optimality probability if available, or average channel strength otherwise.Unlike Algorithm 1, this variant also uses measurement amplitudes to update risk parameters and select replacements.Source: C. Risk-aware greedy UCB algorithm · p. 9

D. Regret analysis

• Cumulative regret increases when the selected training set includes one or more suboptimal beam pairs rather than the top-Btr pairs by probability of being optimal.The problem-dependent bound expresses regret through optimality gaps between optimal and suboptimal pairs.Source: D. Regret analysis · p. 9
• The greedy UCB regret bound is O(log(n)), with its leading term growing as the optimality gap shrinks and more samples are needed to distinguish pairs.The analysis assumes the ideal reward signal because the alternative signal’s history-dependent distribution prevents the required IID condition; the authors expect the signals to converge for large n.Source: D. Regret analysis · p. 9
• Risk-aware UCB’s bound additionally assumes constant rejection probabilities and a specified optimality gap for replacement selections.The analysis also assumes access to the ideal reward signal; the paper describes these simplifications as enabling tractable analysis.Source: D. Regret analysis · pp. 9–10
• O(log(n)) regret remains for risk-aware greedy UCB, but its larger bound reflects slower learning as high-risk pairs are rejected.Rejection sacrifices information about those pairs, trading learning speed for distributing severe-misalignment risk more evenly among users.Source: D. Regret analysis · p. 10

VI. ONLINE BEAM PAIR REFINEMENT

• Beam pair refinement supplies the second layer of the online learning algorithm, following coarse beam-pair selection.The refinement solution uses modified HOO, as introduced in the section overview.Source: §VI · p. 10

A. Problem statement

• The refinement problem is a stochastic continuum-armed bandit that searches pointing directions within the original pair’s 3dB beamwidths to maximize average channel strength.Each feasible transmit/receive pointing-direction combination is an arm in a continuous search space.Source: A. Problem statement · p. 10

B. Modified HOO for beam pair refinement

• The search tree starts from the original beam pair, and each node has 16 children representing finer combinations of transmit and receive direction adjustments.The grid becomes finer with depth as angular perturbations shrink according to beamwidth/2^ℓ.Source: B. Modified HOO for beam pair refinement · p. 10
• At each iteration, HOO traverses the active tree along the path with the largest B-values, samples a node, then updates learning parameters and B-values.A node expands only after it has been sampled Kexd times, limiting expansion of a suboptimal node.Source: B. Modified HOO for beam pair refinement · pp. 10–11
• A finite tree with maximum depth ℓmax saves computation and storage, while a multiplicative smoothness coefficient better fits the multiplicative nature of antenna gains.The paper motivates finite depth by the small gain impact of small adjustments, such as 1/8 of a beamwidth.Source: B. Modified HOO for beam pair refinement · p. 11
• The modified confidence margin uses norm-UCB because the original HOO margin is too loose when average channel strength is much less than one.The new margin uses sample variance; forced exploration requires at least ⌈αnorm log(n)⌉ samples, with αnorm = 8, and Kmin samples for variance calculation.Source: B. Modified HOO for beam pair refinement · p. 11
• The smoothness coefficient is grounded in a lemma assuming a single-path azimuth PAS and a decreasing, concave beam gain over half a 3dB beamwidth.The residual term Err depends on PAS shape and tends to zero as the angular offset approaches zero.Source: B. Modified HOO for beam pair refinement · pp. 11–12
• The smoothness argument extends to transmit and receive beam patterns, while the stated setting restricts Ψ to at most half a beamwidth.The paper notes that its setting uses ∆φ of Φ/4 or less, where Err is already small.Source: B. Modified HOO for beam pair refinement · p. 12

• Evaluation averages metrics over 100 runs that randomly permute 10,000 ray-traced channel samples.A 50-time-step moving average is used to show trends.Source: §VII · p. 12
• The 3 dB power-loss probability measures how often a selected pair loses more than 3 dB against exhaustive search; positive gain can capture refinement beyond the original codebook.The loss probability measures alignment accuracy, while allowing refinement can produce power loss below one, or positive gain in dB.Source: §VII · p. 12
• The evaluation separately tests selection without refinement, refinement after offline selection, and the integrated solution.Source: §VII · p. 12

• Larger Btr lowers 3 dB power-loss probability, while Γrisk has little effect when it is not too large, such as below 40 dB.With Btr=30 and Γrisk=5 dB, learning shifts from fast early improvement to slower improvement around time index 500 as rejection slows training of identified high-risk pairs.Source: A. Online Beam Pair Selection · p. 12
• Performance without risk-awareness is an order of magnitude worse than with risk-aware selection.Risk estimates limit selection of high-risk beam pairs, reducing the probability of severe misalignment.Source: Figure 7 · p. 13, A. Online Beam Pair Selection · p. 13
• Using average sample reward P̂opt(i) selects more accurate beam pairs than using average channel strength, while the practical reward incurs negligible loss versus the ideal reward.The comparison uses Btr=30 and Γrisk=5 dB; the selected sets are evaluated over 500 channel samples after 2,000 learning steps.Source: A. Online Beam Pair Selection · p. 13, Figure 8 · p. 13
• At Btr=30 and Γrisk=5 dB, average 3 dB power-loss probability falls below 2% quickly and reaches 1% within about 300 time steps.The cited prior work reports negligible data-rate loss versus exhaustive search when average 3 dB power-loss probability is below 1%.Source: A. Online Beam Pair Selection · p. 13
• With 16×16 arrays, Btr=30 keeps per-attempt overhead aligned with the cited offline approach, whose overhead is less than a few percent of IEEE 802.11ad’s.The paper attributes the overhead choice to prior work.Source: A. Online Beam Pair Selection · pp. 13–14
• For 16×16 arrays, position accuracy of a few meters is sufficient; larger 32×32 arrays benefit from smaller location bins such as 2 m.The evaluation uses 5 m bins; prior results found no performance difference for 16×16 arrays across bin sizes from 2 m to 5 m [1].Source: A. Online Beam Pair Selection · p. 14

B. Online beam pair refinement

• Refinement is evaluated for pairs chosen through offline MinMisProb selection, using the first 300 channel samples to form the selection set.The refinement training budget is Btr=30.Source: B. Online beam pair refinement · p. 14
• HOO learns faster than MAB by exploring promising nodes in the search tree instead of uniformly sampling all leaves.The refinement comparison follows offline MinMisProb selection, with Btr=30 and a norm-UCB baseline on the search-tree leaves.Source: B. Online beam pair refinement · p. 14
• Setting αnorm=0 performs best, and ℓmax=3 is used because deeper trees add little gain despite increasing the number of nodes.A larger ℓmax does not add exploration cost for HOO, but the improvement is small.Source: B. Online beam pair refinement · p. 14, Figure 9 · p. 14
• Removing the smoothness coefficient has negligible effect when refinement searches locally within the selected pair’s 3 dB beamwidths.The paper suggests this may make the algorithm robust to small irregularities in real-hardware beam patterns.Source: B. Online beam pair refinement · pp. 14–15, Figure 10 · p. 15

C. Integrated online learning solution

• Starting refinement when a pair is first selected performs best; waiting to start refinement provides no benefit.Refining only pairs with positive reward performs well but is slightly worse than refining all selected pairs from the start.Source: C. Integrated online learning solution · p. 15, Figure 11 · p. 15

VIII. CONCLUSIONS

• The integrated solution gains up to about 1.5 dB over exhaustive search on the original codebook and averages about 1 dB gain within the first 100 time steps.Source: §VIII · p. 15

APPENDIX A PROOF OF THEOREM 1

• Expected regret is expressed through the expected number of times suboptimal beam pairs are selected, weighted by their optimality gaps.The derivation assumes reward signals are independent across time.Source: Appendix A · pp. 15–16
• A suboptimal pair selected over an optimal pair must have a higher UCB value; the proof bounds this event after enough samples using confidence margins.The probability bounds use Chernoff-Hoeffding inequalities, with terms bounded by t^-4.Source: Appendix A · p. 16
• The total regret bound sums contributions across optimal and suboptimal beam-pair combinations.Source: Appendix A · p. 16

APPENDIX B PROOF OF THEOREM 2

• For risk-aware selection, the proof distinguishes pairs selected by UCB from pairs accepted for training and incorporates their acceptance probability into the bound.Regret includes the cost of both accepted and rejected selections.Source: Appendix B · pp. 16–17

APPENDIX C PROOF OF LEMMA 1

• For a general PAS P(φ) with support bounded in [φ0 − Ψ, φ0 + Ψ], the proof applies the single-path argument to the average received power.The single-path PAS is represented by δ(φ − φ⋆) under the normalized-PAS assumption.Source: Appendix C · p. 17
• Err → 0 as Δφ → 0, and Err = 0 when Ψ ≤ Δφ.The proof uses that the integrands are positive and the sum of the integrals is finite; when Ψ ≤ Δφ, the integration intervals disappear.Source: Appendix C · p. 17
• Under the lemma’s assumptions, G(φ; φ0) is decreasing and concave on [φ0, φ0 + Φ/2], making the coefficient positive and decreasing as Δφ decreases.The passage notes this gain property holds, for example, for a uniform planar array.Source: Appendix C · p. 17