# Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits

arXiv: https://arxiv.org/abs/2604.14908 · HTML: https://mlsanity.com/paper/2604.14908/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 69 references that are in the map.
- First posted on arXiv 16 Apr 2026.

## Builds on (most cited first, 18 of 18)

- [Sionna: An Open-Source Library for Next-Generation Physical Layer Research](https://mlsanity.com/paper/2203.11854/) (2022)
- [DeepMIMO: A Generic Deep Learning Dataset for Millimeter Wave and Massive MIMO Applications](https://mlsanity.com/paper/1902.06435/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Fast mmwave Beam Alignment via Correlated Bandit Learning](https://mlsanity.com/paper/1909.03313/) (2019)
- [Thompson Sampling for Combinatorial Network Optimization in Unknown Environments](https://mlsanity.com/paper/1907.04201/) (2019)
- [CoVRage: Millimeter-Wave Beamforming for Mobile Interactive Virtual Reality](https://mlsanity.com/paper/2212.05865/) (2022)
- [Contextual Combinatorial Beam Management via Online Probing for Multiple Access mmWave Wireless Networks](https://mlsanity.com/paper/2412.10385/) (2024)
- [Combinatorial Bandits Revisited](https://mlsanity.com/paper/1502.03475/) (2015)
- [Enhanced Random Access and Beam Training for mmWave Wireless Local Networks with High User Density](https://mlsanity.com/paper/1709.03734/) (2017)
- [Real-Time Millimeter-Wave MIMO Channel Sounder for Dynamic Directional Measurements](https://mlsanity.com/paper/1807.11921/) (2018)
- [Thompson Sampling for Linearly Constrained Bandits](https://mlsanity.com/paper/2004.09258/) (2020)
- [Fast Beam Alignment via Pure Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2210.12625/) (2022)
- [Best Arm Identification Based Beam Acquisition in Stationary and Abruptly Changing Environments](https://mlsanity.com/paper/2307.05023/) (2023)
- [CSI Transfer From Sub-6G to mmWave: Reduced-Overhead Multi-User Hybrid Beamforming](https://mlsanity.com/paper/2403.10873/) (2024)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Beamwidth Optimization and Resource Partitioning Scheme for Localization Assisted mm-wave Communications](https://mlsanity.com/paper/2005.04900/) (2020)

## Abstract (arXiv)

We study downlink beam and rate adaptation in a multi-user mmWave MISO system where multiple base stations (BSs), each using analog beamforming from finite codebooks, serve multiple single-antenna user equipments (UEs) with a unique beam per UE and discrete data transmission rates. BSs learn about transmission success based on ACK/NACK feedback. To encode service goals, we introduce a satisficing throughput threshold τr and cast joint beam and rate adaptation as a combinatorial semi-bandit over beam-rate tuples. Within this framework, we propose SAT-CTS, a lightweight, threshold-aware policy that blends conservative confidence estimates with posterior sampling, steering learning toward meeting τr rather than merely maximizing. Our main theoretical contribution provides the first finite-time regret bounds for combinatorial semi-bandits with satisficing objective: when τr is realizable, we upper bound the cumulative satisficing regret to the target with a time-independent constant, and when τr is non-realizable, we show that SAT-CTS incurs only a finite expected transient outside committed CTS rounds, after which its regret is governed by the sum of the regret contributions of restarted CTS rounds, yielding an O((log T)2) standard regret bound. On the practical side, we evaluate the performance via cumulative satisficing regret to τr alongside standard regret and fairness. Experiments with time-varying sparse multipath channels show that SAT-CTS consistently reduces satisficing regret and maintains competitive standard regret, while achieving favorable average throughput and fairness across users, indicating that feedback-efficient learning can equitably allocate beams and rates to meet QoS targets without channel state knowledge.