1
Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits
arXiv:2604.14908v1 [cs.LG] 16 Apr 2026
Emre Özyıldırım , Barış Yaycı , Umut Eren Akturk , and Cem Tekin , Senior Member, IEEE
Abstract—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, thresholdaware 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. Index Terms—Millimeter wave, beam adaptation, rate adaptation, combinatorial bandits, satisficing.
I. I NTRODUCTION Millimeter-wave (mmWave) communication has emerged as a cornerstone technology for next-generation wireless networks, driven by the relentless growth in mobile data demand and the proliferation of bandwidth-hungry applications such as interactive extended reality [2] and ultra-high-definition streaming [3]. By leveraging large swaths of underutilized spectrum, mmWave enables unprecedented peak data rates and supports ultra-low latency services that are essential for such emerging applications. At the same time, the unique This work was supported in part by the Scientific and Technological Research Council of Türkiye (TUBITAK) BILGEM Grant; TUBITAK Grant 124E065; by the Turkish Academy of Sciences Distinguished Young Scientist Award Program (TUBA-GEBIP-2023); by TUBITAK 2024 Incentive Award. The authors are with the Department of Electrical and Electronics Engineering, Bilkent University, Ankara, Türkiye (email: [email protected]; [email protected]; [email protected]; [email protected]). E. Özyıldırım and B. Yaycı contributed equally to this work. A preliminary version of this work was presented at the AI and ML for Next-Generation Wireless Communications and Networking Workshop at NeurIPS 2025 [1] (non-archival).
propagation characteristics of mmWave, such as high path loss, susceptibility to blockage, and strong directionality, introduce fundamental challenges in acquiring channel state information (CSI), efficiently aligning beams, and adjusting data rates to meet service demands [4]. Accurate CSI is often unavailable in mmWave systems because highly directional links with large arrays (often under hybrid analog/digital constraints) make channel sounding expensive, while mobility and blockage can rapidly invalidate any estimate, forcing frequent re-training with substantial overhead and latency [5]. This motivates beam adaptation without CSI, where the transmitter avoids explicit channel estimation and instead uses minimal link-layer feedback [6]– [8]. In particular, ACK/NACK feedback provides a reliable binary signal indicating whether the current beam configuration can sustain the required packet delivery (and thus throughput) under the prevailing propagation conditions. By iteratively updating the beam choice based solely on this feedback, the system can implicitly track the good beam directions and maintain throughput targets while eliminating the CSI acquisition burden. We study downlink data transmission in a multi-user, multibase station Multiple Input Single Output (MISO) system, where multiple base stations (BSs) serve single-antenna user equipments (UEs) [9]. In mmWave communications, transmitters employ highly directional narrow beams to mitigate severe path loss and blockage [10]. Reliable links require these beams to be accurately steered toward the UEs [11], [12]. Each UE can be served by one of several candidate beams across different BSs. A BS transmits data to a UE using the selected beam at the highest feasible rate, determined by the chosen modulation and coding scheme (MCS). We model this as a joint beam and rate adaptation problem without CSI, where after each transmission the BS receives binary ACK/NACK feedback for the selected beam–rate pair. We consider a centralized architecture in which a learner coordinates beam and rate assignments for the BSs and UEs at the beginning of each time slot over an ultra-low latency control channel (Fig. 1). At the end of each slot, BSs return feedback to the learner, which updates assignments to improve system performance. We cast the problem of learning the best beam-rate assignments by relying solely on ACK/NACK feedback as a sequential decision-making problem. This setup exhibits the canonical exploration–exploitation tradeoff: the learner must explore different beam-rate pairs to learn which ones perform well while exploiting known good configurations to satisfy throughput requirements. This tradeoff is optimality balanced by multi-armed bandit (MAB) algorithms [13] that
2
TABLE I: Comparison with related works.
Learner
Communication Workflow 1: Learner makes the beam assignments 2: BS send the data to users 3: UE provides feedback 4:BS provides learner with the feedback
Work
Combinatorial Setup
MAB & Comm. System Together
Satisficing Threshold
Beam + Data (Align & Rate)
MAMBA [6] HBA [7] CCBM [21] CCVB for BS [22] FBA [23] CCV–MAB [24]
✗ ✗ ✓ ✓ ✗ ✓
✓ ✓ ✓ ✓ ✗ ✗
✗ ✗ ✗ ✗ ✗ ✗
✓ ✗ ✗ ✗ ✗ ✗
Our work
✓
✓
✓
✓
1 4
BS
2
UE
3
UE
UE BS
BS UE UE
UE
Fig. 1: System model.
can adapt beams and rates in a completely data-driven manner. While a wide range of MAB algorithms has been proposed for identifying the best choice (i.e., the best super-arm) among combinatorially many configurations (i.e., super-arms) [14]– [17], many of these methods are inherently designed to prioritize long-term optimality and thus may over-explore in practice rather than quickly settling on a configuration that already satisfies the throughput requirements, as a result, they can exhibit slow convergence and poor early performance, leading to suboptimal communication reliability and throughput during the early rounds of communication. Departing from the prior work, we focus on designing algorithms that learn a good-enough configuration in the most sample efficient way. We do this by modeling the joint beam and rate adaptation process as a satisficing combinatorial MAB (CMAB) with semi-bandit feedback, and develop a scalable learning algorithm, called satisficing combinatorial Thompson sampling (SAT-CTS), that ensures acceptable per-UE average throughput. Our approach follows Herbert Simon’s boundedrationality perspective, where agents aim to reach an aspiration level under limited time and information [18]. Instead of focusing on convergence to a maximizer, we measure how quickly the assignments achieve a satisficing threshold by analyzing a satisficing version of regret. We provide finite-time regret bounds for SAT-CTS under two scenarios. When the satisficing threshold τr is realizable (i.e., achievable by some assignment with margin), we prove a horizon-free upper bound on the expected cumulative satisficing regret that depends only on system parameters. When τr is non-realizable (higher than the best achievable throughput), we show that SAT-CTS reduces to standard combinatorial Thompson sampling (CTS) [16] after a finite transient phase and therefore inherits the CTS standard regret bound up to an additive constant. To the best of our knowledge, these are the first finite-time regret guarantees for CMAB with satisficing objectives. We evaluate our approach in a simulated multi-BS, multiUE MISO system with realistic channel vectors generated by the DeepMIMO simulator [19]. UEs are modeled as stationary within each time slot, consistent with the quasi-static assumption used in prior beam-training studies [12], [20]. Our proposed algorithm SAT-CTS, which takes the satisficing
threshold as an input and tests the selected super arm’s performance under this threshold, outperforms CTS [16] and combinatorial upper confidence bound (CUCB) [15] baselines in terms of satisficing regret. Compared with the preliminary workshop version [1], the present paper uses a committedround SAT-CTS design with reset fresh CTS rounds and removes the optimistic UCB gate, which enables the finitetime regret analysis. In a nutshell, we propose the first scalable, regret-optimal, binary-feedback-enabled beam and rate adaptation algorithm for mmWave systems in the absence of CSI. We rigorously prove the optimality of SAT-CTS in terms of the satisficing regret, and demonstrate that it outperforms well-known CMAB algorithms utilized for beam and rate adaptation. The rest of the paper is organized as follows. Related work is given in Section II. The beam and rate adaptation problem is formalized in Section III. SAT-CTS algorithm is proposed in Section IV. Regret analysis of SAT-CTS under realizable target is done in Section V. Experimental results on the DeepMIMO simulator are reported in Section VI. Concluding remarks are given in Section VII. II. R ELATED W ORK In mmWave networks, the central challenge is assigning beams together with appropriate rates so that data transmissions succeed under directional links and SNR thresholds. Several non-bandit approaches tackle the alignment phase. For instance, Hassanieh et al. [23] design fast probing to identify a good beam, but do not address multi-user assignment or data rate selection. Marzi et al. [25] employ compressive sensing techniques that utilize the sparsity of the mmWave channel to reduce the alignment overhead. Wang et al. [26] propose a hierarchical multi-resolution search procedure to identify the optimal beam while minimizing the probing overhead. Several other works incorporate contextual information, such as position information, into the beam search process to enable rapid identification of the optimal beam [27], [28]. There also exists a plethora of MAB-based formulations for beam alignment. Wei et al. [12] treat fast beam alignment as a pure exploration problem, identifying the best beam from pilot measurements (received signal strength) without sending real data or choosing rates. Ghosh et al. [29] propose a MAB algorithm that utilizes the unimodal structure of the RSS to maximize the probability of the identification of the best beam given a fixed transmission budget. Several other works, such
3
as [6], [7], [30], [31], approach the beam alignment problem from a regret minimization perspective and propose algorithms that continuously explore and exploit. However, continuous exploration can lead to suboptimality if the goal is to identify the best beam for data transmission during an alignment phase with pilot symbols. On the other hand, when used to directly select beams for data transmission, continuous exploration can result in suboptimal beam selections for data transfer. In contrast to these works, we apply MAB algorithms for beam tracking without requiring pilot-symbol-based beam alignment. Instead, we aim directly for data transmission in each slot with the chosen beam (see Fig. 2 for the process of beam selection and data transmission). Moreover, to reduce suboptimal explorations, we incorporate a satisficing approach where the goal is to select beam-rate pairs that guarantee a target level of throughput demand instead of the highest throughput. Along regret minimization direction, contextual combinatorial beam management [21] extends alignment to a contextual, combinatorial setting with multiple UEs and BSs and a probing budget, and tries to maximize a contextual reward. Beam alignment in non-stationary environments is considered in [32] and [33]. Another related work [22] focuses on the problem of multi-user small BS association in a contextual setup with dynamic UE presence using contextual combinatorial volatile MAB without beam management. Relatedly, CCV-MAB [24] addresses contextual combinatorial bandits with time-varying availability, offering regret guarantees via adaptive discretization. Yet it remains communication-agnostic (no beam/rate modeling or ACK/NACK signals). A procedure similar to adaptive discretization, called dynamic beam zooming, is proposed in [34] for beam alignment and tracking. MAMBA [6] jointly adapts beam and MCS from ACK/NACK, yet remains a single-user, single-BS formulation without combinatorial matching. Our research fills the gap between alignment-only pilot methods and single-link bandits by providing a target-aware, multi-user assignment mechanism that operates directly on the data plane with provable performance guarantees. III. P ROBLEM F ORMULATION We consider a multi-user mmWave MISO system where B BSs, each with N transmit antennas, serve M single-antenna UEs as in Fig. 1. A. System Model and SNR System parameters are summarized in Table II. For an integer n, let [n] := {1, . . . , n}. Each BS b ∈ [B] selects its beams from its predefined analog beamforming codebook of size K [35], defined as Cb := { fb,k ∈ CN : k ∈ [K]}, with each beamforming vector fb,k normalized, ∥fb,k ∥2 = 1. The mmWave channel, as observed in measurement studies [36], [37], follows a multipath model with a small number of propagation paths, resulting in a sparse structure. While our learning algorithms are not restricted to work under a specific channel model, a common model for the channel vector from
TABLE II: Summary of notation for multi-UE multi-BS mmWave MISO system. Symbol
Description
System Parameters B M K N Cb λ, d pb
Number of BSs Number of UEs Beams per BS codebook Antennas per BS Codebook for BS b Wavelength, antenna spacing Transmit power for BS b
Channel Parameters hm,b Lm,b βm,b,ℓ θm,b,ℓ a(·) fb,k
Channel: BS b to UE m Number of paths (BS b, UE m) Complex gain, ℓth path AoD, ℓth path Array steering vector kth beam from BS b
Signal Parameters ym RSSm (fb,k ) am,b,k nm 2 σm
Received signal at UE m Received power for beam fb,k hH m,b fb,k (projection) 2 Noise, CN (0, σm ) Noise variance at UE m
BS b to UE m is the Lm,b -path Saleh–Valenzuela model [38], given as Lm,b
hm,b =
q
N Lm,b
X
βm,b,ℓ a(cos θm,b,ℓ ),
(1)
ℓ=1
where βm,b,ℓ and θm,b,ℓ are the complex gain and angleof-departure (AoD) of path ℓ for that specific BS-UE link, and the array steering vector is a(cos θm,b,ℓ ) = 2π 2π [1, ej λ d cos θm,b,ℓ , . . . , ej λ d(N −1) cos θm,b,ℓ ]T defined as in [29]. Here, λ represents the carrier wavelength and d represents the antenna spacing. We assume a quasi-static channel model, where the channel vector hm,b remains constant during a time slot, but can vary between time slots [39]. Consider BS b transmitting symbol s to UE m with transmit power pb . Without loss of generality, assume s = 1. When BS b transmits with with beam fb,k , the received signal at UE m √ 2 is given by ym = pb hH m,b fb,k + nm where nm ∼ CN (0, σm ) is the complex additive white Gaussian noise (AWGN). The instantaneous received-signal-strength (RSS) is equal to the magnitude squared of the received signal, which is given √ 2 as RSSm (fb,k ) = |ym |2 = | pb hH m,b fb,k + nm | . Letting H am,b,k = hm,b fb,k , we have √ 2 RSSm (fb,k ) = pb am,b,k + nm √ = pb |am,b,k |2 + 2 pb ℜ{a∗m,b,k nm } + |nm |2 . √ 2 Note that 2 pb ℜ{a∗m,b,k nm } ∼ N 0, 2pb |am,b,k |2 σm and the noise-power term |nm |2 is an exponential random vari2 4 able with mean σm and variance σm . Assuming a high SNR 2 2 regime, i.e., pb |am,b,k | ≫ σm , the following approximation can be obtained as in [12]: √ RSSm (fb,k ) = | pb am,b,k + nm |2 2 ≈ pb |am,b,k |2 + N (0, 2pb |am,b,k |2 σm ).
4
the Shannon-Hartley theorem. At the end of time slot t, BS b receives the transmission success indicator (ACK/NACK feedback) from UE m, which is given by: ( 2 pb |hH m,b fb,k | ≥ γth (ρm,t ) (ACK) 1 if 2 σ m xm,t := 0 otherwise (NACK - outage)
Coherence Time: Channel Stays Constant ( t time slots )
CP Learner
Beam Selection S
S
S
...
DATA
DATA
UE
BS 2
BS 1
Data Transfer ...
...
DATA
ACK
NACK
ACK
...
Feedback
Time
Fig. 2: Process of beam and rate assignment. The expected RSS within a time slot is then given as 2 E[RSSm (fb,k )|hm,b ] = pb hH m,b fb,k , which yields a signal 2 2 to noise ratio (SNR) equal to pb hH m,b fb,k /σm . B. Combinatorial Multi-Armed Bandit Formulation Beam k of BS b is denoted by tuple (b, k). We denote the set of all beams by K := [B] × [K]. Additionally, we define a discrete set of feasible transmission rates R = {r1 , r2 , . . . , rR } where r1 < r2 < . . . < rR represent the available data rates in bits per channel use. Different data rates can be achieved by choosing a different MCS. We assume |K| ≥ M . Let T represent the time horizon. We consider a centralized system where the learner coordinates beam and rate selection for downlink transmission. As presented in Fig. 2, the following events take place sequentially at each time slot t. At the beginning of each time slot t ∈ [T ], the learner assigns exactly one beam to each UE via a mapping πt : {1, . . . , M } → K, and selects a transmission rate for each UE via a mapping ρt : {1, . . . , M } → R. Here, πm,t = (bm,t , km,t ) represents the beam assigned to UE m with bm,t representing the assigned BS and km,t representing the beam of the assigned BS. For each UE m ∈ [M ], the learner communicates this information with the associated BS through an ultra-low latency control channel. After this communication, BS bm,t uses its beam πm,t = (bm,t , km,t ) to transmit data to UE m at rate ρm,t . We assume that each beam k ∈ K can serve at most one UE as in [40], [41]. A base arm is indexed by i = (m, (b, k), r), where m ∈ [M ] is the UE, (b, k) ∈ K is the BS–beam pair, and r ∈ R is the rate. Let A represent the set of base arms and let S := {{(π1 , ρ1 ), . . . , (πM , ρM )} : πm ∈ K, ρm ∈ R
πm ̸= πn for n ̸= m}
represent the set of super arms. For a super arm s ∈ S, let πm (s) be the beam assigned to UE m and ρm (s) be the rate selected for UE m. For a given rate ρm,t and beam allocation πm,t = (b, k), the transmission is successful if the instantaneous SNR exceeds the threshold required for the selected rate. Define the SNR threshold for rate r ∈ R as γth (r) = 2r − 1 based on
The instantaneous reward for UE m at time t is rm,t = ρm,t × xm,t , where the UE receives the selected rate ρm,t if transmission is successful and zero otherwise. The transmission success probability for UE m with beam (b, k) and rate r is denoted as ! 2 pb |hH m,b fb,k | ≥ γth (r) , ψm,(b,k),r := P 2 σm where the randomness is over the channel vector hm,b . These probabilities are unknown, which makes the decision-making process without channel state knowledge challenging. An optimal super arm is a super arm that maximizes the expected total throughput, which is given as " M # X ∗ ∗ (π , ρ ) ∈ arg max E ρm × x m (π,ρ)∈S
= arg max (π,ρ)∈S
m=1
M X m=1
ρm × ψm,πm ,ρm ,
where ρm is the transmission rate selected for UE m, xm ∈ {0, 1} represents the random ACK/NACK feedback under super arm choice (π, ρ), and ψm,πm ,ρm is the transmission success probability for UE m with beam πm and rate ρm . Given assignment St = {(π1,t , ρ1,t ), . . . , (πM,t , ρM,t )}, the learner observes at the end of slot t the per-UE ACK/NACK feedback xm,t ∈ {0, 1} for m = 1, . . . , M . This information, which will be used by the learner for subsequent super arm selections, is known as the semi-bandit feedback and is communicated by the BSs to the learner via the ultra-low latency control link. Define the satisficing threshold as τr ∈ R+ representing the target average throughput per UE. This threshold can be interpreted as the desired minimum average data rate that should be achieved across all UEs. For instance, in 6G scenarios one can aim for average throughput τr = 2.5 Gbits/sec per UE per time slot. The per-round satisficing regret of St is # " M 1 X ρm,t · ψm,πm,t ,ρm,t , ∆sat (St ) := τr − M m=1 +
and the cumulative satisficing regret over T time slots is RS (T ) :=
T X
∆sat (St ).
(2)
t=1
In the next section, we will propose an algorithm that minimizes the satisficing regret. This way, the algorithm will achieve an average throughput that is above τr in all but a finite number of initial rounds. A stricter notion of regret, called the standard regret, compares the performance of the learner with
5
that of the best super arm. The T round standard regret is given as T
M
1 XX ∗ ∗ ,ρ∗ − ρm,t ψm,π Rstd (T ) := (ρ ψm,πm ). m,t ,ρm,t m M t=1 m=1 m When τr is not realizable, i.e., there is no super arm that achieves τr , we will bound the standard regret. IV. FAST B EAM AND R ATE A DAPTATION VIA SAT-CTS A. Algorithm Description Satisficing Combinatorial Thompson Sampling (SAT-CTS) selects BS-beam-rate combinations for each UE to meet the target throughput. Its pseudocode is given in Algorithm 1. Each arm i = (m, (b, k), r) maintains shared counters (ni , si ) updated every round, where ni represents the number of times arm i has been selected, and si represents the number of times its transmission is successful.1 The algorithm also keeps Beta priors that represent the distribution of transmission success probability of each arm. First, the algorithm selects a sequence of super arms such that each arm gets played at least once, initializing its counters. The deterministic initialization phase lasts for T0 rounds. At each time step, the algorithm computes empirical means ψ̂i (t) = si /ni and confidence q 3 log t radius c(t, ni (t)) = 2ni (t) , yielding LCB and MEAN indices (lines 19–23). These are fed to the assignment oracle (e.g., the Hungarian algorithm, line 24) , and the gate plays the first candidate whose average meets τr in the order LCB, MEAN (lines 25–29). If neither gate fires, the algorithm enters a committed CTS phase: it resets all Beta priors to Beta(1, 1) and runs CTS for exactly 2i rounds without rechecking the gate (lines 31– 44). During these rounds, both shared counters and private Beta posteriors are updated. After phase i completes, the phase counter increments and the gate is re-evaluated. This committed-phase structure ensures each CTS instance runs on a deterministic horizon with fresh priors, enabling a clean regret analysis via a geometric-series framework [42]. B. Time Complexity Analysis Per-round time complexity of the standard Hungarian algorithm during application for a square n × n matrix is O(n3 ). On application for rectangular matrices m × n, the complexity is O(m2 n), if m < n. Considering that beams are being matched to UEs, the dimensions are m = M , the number of UEs, and n = BKR, the total number of beam-rate pairs that can be assigned to UEs. Since the number of UEs is less than the number of beams for assignment to all UEs to be feasible, the per-round time complexity for the m × n matrix is O(M 2 × B × K × R). The complexity of other areas of the algorithm such as computing Thompson samples is O(M × B × K × R), which is a term of smaller order than the complexity of the Hungarian algorithm. Therefore, omitting all terms of smaller order through the Big-O notation, the total time complexity of SAT-CTS over T rounds is O(T (M 2 × B × K × R)). 1 To emphasize the dependence on t, the values of these counters are sometimes represented by ni (t) and si (t).
Algorithm 1 SAT-CTS Require: M UEs; beam set K = [B] × [K]; rate set R = {r1 < · · · < rR }; target τr 1: For all m ∈ [M ], (b, k) ∈ K, r ∈ R: 2: nm,(b,k),r ← 0, sm,(b,k),r ← 0 3: S = {(π1 , ρ1 ), . . . , (πM , ρM )} : 4: πm ∈ K, ρm ∈ R, πm ̸= πn ∀ m ̸= n 5: Primitives: 6: BestAssign(Score) PM 7: := arg maxs∈S m=1 Scorem,πm (s),ρm (s) 8: Avg(Score, PMs) 1 9: := M m=1 Scorem,πm (s),ρm (s) 10: // Initialization: cover all base arms 11: Choose super arms s1 , . . . , sT0 ∈ S s.t. every base arm i ∈ A appears in at least one sj 12: for j = 1 to T0 do 13: Play sj ; observe xm,j ∈ {0, 1} for each m; update n, s counters 14: end for 15: CTS round counter i ← 1 16: t ← T0 + 1 17: while t ≤ T do 18: // Compute indices 19: for each m, (b, k), r do p 20: ψ̂ ← sm,(b,k),r /nm,(b,k),r ; c ← 3 log t/(2nm,(b,k),r ) LCBm,(b,k),r ← r max{0, ψ̂−c} MEANm,(b,k),r ← rψ̂ end for SL ← BestAssign(LCB), SM ← BestAssign(MEAN) // Gate 26: if Avg(LCB, SL ) ≥ τr then 27: Play SL ; observe and update shared counters; t ← t+1 28: else if Avg(MEAN, SM ) ≥ τr then 29: Play SM ; observe and update shared counters; t ← t+1 30: else 31: // Committed CTS phase i 32: Reset: Am,(b,k),r ← 1, Bm,(b,k),r ← 1 ∀ m, (b, k), r 33: for j = 1 to min(2i , T −t+1) do 34: for each m, (b, k), r do 35: ψ̃m,(b,k),r ∼ Beta(Am,(b,k),r , Bm,(b,k),r ) 36: end for 37: Play BestAssign(rψ̃); observe xm,t ∈ {0, 1} 38: for each m do 39: nm,πm,t ,ρm,t += 1; sm,πm,t ,ρm,t += xm,t 40: Am,πm,t ,ρm,t += xm,t ; Bm,πm,t ,ρm,t += 1 − xm,t 41: end for 42: t←t+1 43: end for 44: i←i+1 45: end if 46: end while 21:
22: 23: 24: 25:
6
C. Main Regret Bounds and Their Discussion We next summarize the main finite-time guarantees of SATCTS. Before providing the main results, we introduce notation, definitions, and assumptions under which the main results hold. 1) Notation: a) System parameters: M : number of UEs; B: number of BSs; K: number of beams per BS; R: number of discrete rate levels; T : time horizon; T0 : number of initialization rounds; A: set of all base arms, with |A| = M BKR; S: set of all feasible super arms (assignments); R = {r1 < · · · < rR }: set of available rates; rmax := maxr∈R r: maximum rate. b) Per-arm quantities: For each base arm i ∈ A: Xi,t ∈ {0, 1}: ACK/NACK outcome at time t, with E[Xi,t ] = ψi ; ψi : transmission success probability; µi := ri ψi ∈ [0, rmax ]: expected throughput; ni (t): number of times arm i has been played up to time t; ψ̂i (t): empirical success probability; ψ̂i,n : empirical success probability based on n i.i.d. samples. c) Assignment-level quantities: A super arm s ∈ S includes exactly one base arm per UE, hence exactly M base arms, written as {im (s)}M m=1 . PM PM 1 1 • g(s) := M m=1 µim (s) = M m=1 rim (s) ψim (s) : average expected throughput of assignment s. When the dependence on the success-probability vector needs to be explicit, we write g(s; PMψs ). 1 • ĝshared (s, t) := M m=1 rim (s) ψ̂im (s) (t): empirical average throughput using shared counters. • ∆sat (s) := [τr − g(s)]+ : per-round satisficing regret of assignment s. ⋆ ⋆ ⋆ • s ∈ arg maxs∈S g(s): optimal assignment; g := g(s ): optimal average throughput. ⋆ • ∆s := g(s ) − g(s): standard regret gap of assignment s. • ∆max := maxs∈S ∆s : maximum standard regret gap.
LCBi (t) := ri max{0, ψ̂i (t) − c(t, ni (t))}: lower confidence bound index. • MEANi (t) := ri ψ̂i (t): empirical mean index.
•
e) Gap quantities: ∆⋆ := g ⋆ − τr : realizability margin. std ⋆ • ∆min := mins∈S, s̸=s⋆ g(s )−g(s) : minimum standard regret gap. • Ssat := {s ∈ S : g(s) ≥ τr }: satisficing assignment set. • Sbad := {s ∈ S : g(s) < τr }: bad assignment set. (i) • Sbad := {s ∈ Sbad : i ∈ s}: bad assignments containing arm i. bad • ∆i := mins∈S (i) ∆sat (s): minimum satisficing gap for
•
bad
(i)
(i)
r2
i When Sbad = ∅, we adopt the convention 2(∆bad := 0. )2 i nr ⋆ • ∆⋆ := τr −g : non-realizability margin (used when τr > g ⋆ ). nr • ∆ (s) := τr − g(s): per-assignment non-realizability gap.
•
f) Events: The good event at time t, under which confidence bounds hold for all base arms: o \n Gt := ψ̂i (t) − ψi ≤ c(t, ni (t)) . (3) i∈A
•
The overestimation event for base arm i at time t with threshold ε > 0: n o Ei,t (ε) := {i ∈ St } ∩ ψ̂i,ni (t) ≥ ψi + ε . (4)
g) Auxiliary counting quantities: St ∈ S: super arm PT played at time t. • BLCB (T ) := t=T0 +1 1{St ∈ Sbad , Gt , LCB at t}: bad pulls in the LCB phase. P T • BMEAN (T ) := ∈ t=T0 +1 1{St Sbad , Gt , MEAN at t}: bad pulls in the MEAN phase. PT ⋆ • Bsub (T ) := t=1 1{St ̸= s }: number of suboptimal plays in a fresh CTS instance. • Ti (T ) := {t ∈ {T0 + 1, . . . , T } : arm i is played at time t}: pull times of arm i. h) CTS-phase constants: Bcts := rmax /M : boundedsmoothness constant for the CTS phase (Lemma 3); k ⋆ := M ; Kmax := M ; α1 : absolute constant from Theorem 1 of [16]; δ ∈ (0, 1/4): confidence parameter; Ĉ1 , Ĉ0 : suboptimality constants (defined explicitly in Lemma 13); N0 : critical observation count (defined in Section V-D as a function of δ); ⋆ TCTS : critical CTS horizon (Given in Definition 1 as a function ⋆ ⌉: critical round index. of δ); i⋆ := ⌈log2 TCTS 2) Assumptions: The first two assumption are related to whether τr can be achieved by some assignment. Our algorithm achieves different regret guarantees under these assumptions. •
Assumption 1 (Realizability with margin). We assume that ∆⋆ = g ⋆ − τr > 0, i.e., the optimal assignment achieves the target with positive margin.
d) Concentration and index values: q 3 log t • c(t, n) := 2n : concentration radius.
arm i (when Sbad ̸= ∅). ∆bad norm • ∆i := rii : normalized gap for arm i.
•
Assumption 2 (Non-realizability). The satisficing threshold is strictly larger than the maximum achievable average through⋆ put, i.e., τr > g ⋆ . In other words, ∆nr ⋆ = τr − g > 0.
The next assumption is a standard simplifying assumption in CMAB theoretical analysis; see, e.g., [43].
Assumption 3 (Unique optimal assignment). The optimal assignment is unique, i.e., arg maxs∈S g(s) = {s⋆ }.
Under Assumptions 1 and 3, we have s⋆ ∈ Ssat , ∆std min > 0. 3) Satisficing regret bound under realizable target: When the target is realizable, SAT-CTS incurs bounded satisficing regret independent of horizon T . Theorem 1. Under Assumptions 1 and 3, the expected cumulative satisficing regret satisfies E RS (T ) ≤ Rinit + Rconf + RMEAN + RCTS , where Rinit is the expected satisficing regret during initialization phase, Rconf is the expected satisficing regret incurred when the good event in (3) fails for some t, and RMEAN ,
7
RCTS represent the expected satisficing regrets incurred during MEAN and CTS phases of SAT-CTS respectively under the good event. Each term above is a finite constant independent of T , whose values are explicitly given as Rinit = T0 τr , Rconf =
V. R EALIZABLE S ATISFICING R EGRET A NALYSIS In this section we upper bound the satisficing regret when τr is realizable. Omitted proofs can be found in Appendix A.
A. Technical Lemmas X π2 ri2 , |A|τr , RMEAN = τr 2 The following is a result of subgaussianity of ψ̂i,n − ψi . 3 2 (∆bad i ) i∈A
Lemma 1. For each arm i ∈ A and n ≥ 1, the empirical Ĉ1 log 2 ⋆ 2 Ĉ1 i log 2 + Ĉ0 (i ) + Ĉ0 i⋆ + success probability ψ̂i,n satisfies, for all ε > 0, 2 1 − 2δ 2 ! −2nε2 P ψ̂ ≥ ψ + ε ≤ e , P ψ̂ ≤ ψ − ε ≤ e−2nε . i,n i i,n i 2Ĉ1 δ log 2 for any δ ∈ (0, 1/4). + (1 − 2δ)2 Using Lemma 1 and union bound gives the following concentration lemma for ψ̂i (t). The proof of Theorem 1 is given in Section V. This Lemma 2. For any arm i ∈ A and any t > T0 , theorem shows for the first time that bounded satisficing regret P ψ̂ (t) − ψi > c(t, ni (t)) ≤ 2t−2 . i can be achieved for a combinatorial semi-bandit problem. Interestingly, the expected regret during rounds in which The next lemma characterizes the smoothness of the exconfidence bounds fail or rounds in the MEAN phase of SAT- pected average throughput in base arm rewards. CTS increase linearly with the number of base arms. This scaling matches with the scaling of the gap-dependent regret Lemma 3. For any feasible assignment sM∈ S and any two with base arms in standard CMAB with linear rewards [44]. success-probability vectors ψs , ψ̃s ∈ [0, 1] , 2 rmax The inverse dependence on (∆bad i ) in RMEAN represents |g(s; ψs ) − g(s; ψ̃s )| ≤ ∥ψs − ψ̃s ∥1 . M hardness of distinguishing satisficing assignments from others. Under the good event, no regret is incurred during the LCB Hence the bounded-smoothness assumption in [16] holds with phase. The regret coming from the CTS phase is a constant Bcts := rmax /M . independent of T . Our proof uses geometrically increasing The next lemma bounds the regret under Gtc . phase lengths to show that occurrence probability of CTS phases geometrically decay. In each CTS phase, we utilize Lemma 4. For t > T0 , we have P(Gtc ) ≤ 2|A| t−2 , and " # the suboptimal assignment selection bound for CTS given in X π2 [16]. However, it is shown in [16, Theorem 3] that the regret c E ∆sat (St ) 1{Gt } ≤ |A| τr . 3 of CTS can have exponential dependence on M . To the best of t>T0 our knowledge, there is no known tighter bound for the regret −2 c of CTS for the assignment problem that we consider in our Proof. The bound P(Gt ) ≤ 2|A| t follows by a union bound over i ∈ A using Lemma 2. Since ∆sat (St ) ≤ τr , work. Nevertheless, we perform comprehensive experiments to show how the regret scales with M and other parameters E[∆sat (St ) 1{Gtc }] ≤ τr P(Gtc ) ≤ 2|A| τr t−2 . that determine the number of base arms in Section VI. Summing the above display over t > T0 yields the result. 4) Standard regret bound under non-realizable target: When the target is non-realizable, SAT-CTS incurs regret The next lemma proves conservatism of LCB on Gt . polylogarithmic in T . Lemma 5. For t > T0 , on Gt , for every base arm i ∈ A we Theorem 2. Under Assumptions 2 and 3, SAT-CTS achieves have µi ≥ LCBi (t). Consequently, for any assignment s ∈ S, PM 1 the following standard regret bound g(s) ≥ M m=1 LCBim (s) (t). ⋆
RCTS ≤ τr
E[Rstd (T )] = O((log T )2 ). The proof of Theorem 2 is given in Appendix B. This theorem shows that under non-realizable target, the standard regret of SAT-CTS grows almost as slow as that of CTS [16], which is O(log T ). Indeed, in the proof of Theorem 2, we show that SAT-CTS incurs only a finite expected transient outside committed CTS rounds. After this transient, its regret is governed by the sum of the regret contributions of restarted CTS rounds, resulting in standard regret that grows polylogarithmically with the horizon T . These results prove the versatility of SAT-CTS by showing that it can work favorably under both settings without knowing which setting it is facing with.
Proof. On Gt , ψi ≥ max{0, ψ̂i (t) − c(t, ni (t))}, hence µi = ri ψi ≥ ri max{0, ψ̂i (t) − c(t, ni (t))} = LCBi (t). Averaging over the M components of any s gives the stated inequality. B. Regret Decomposition We work with the expected cumulative satisficing regret E[RS (T )]. SAT-CTS operates in three phases: LCB, MEAN, and CTS. We bound each phase’s contribution separately, using the bad pull counts BLCB (T ) and BMEAN (T ) from Section IV-C. The following lemma decomposes the regret of SAT-CTS over phases.
8
hP i T Lemma 6. Lemma 11. Fix i ∈ A and ε > 0. E t=T0 +1 1{Ei,t (ε)} ≤ π2 2ε12 . E RS (T ) ≤ |A| τr + τr E BLCB (T ) + E BMEAN (T ) 3 Proof. By Lemma 10 and linearity of expectation, X " T # +E ∆sat (St ) + T0 τr , T X X t∈TCTS E 1{Ei,t (ε)} ≤ P ψ̂i,n ≥ ψi + ε . n=1 where TCTS is the set of time steps in the CTS phase. t=T0 +1 Proof. Write 1 = 1{Gt } + 1{Gtc }. Initialization costs at most By Lemma 1, P ψ̂ ≥ ψ + ε ≤ e−2nε2 . Hence i,n i 2 T0 τr regret. The contribution from Gtc is at most π3 |A|τr by T ∞ Lemma 4. On Gt , bad pulls in the LCB and MEAN phases X X 2 1 1 are counted by BLCB and BMEAN , each costing at most τr . P ψ̂i,n ≥ ψi + ε ≤ e−2nε = 2ε2 ≤ 2, 2ε e −1 The CTS-phase regret is bounded separately since each CTS n=1 n=1 round uses fresh priors and the satisficing regret per round is which follows from ex − 1 ≥ x with x = 2ε2 . controlled by the standard CTS regret (Section V-D). Equipped with the results above, we bound E[BMEAN (T )] Next, we show that there are no bad pulls in the LCB phase. in the following lemma. Lemma 7. On Gt , BLCB (T ) = 0 a.s. P ri2 Lemma 12. E BMEAN (T ) ≤ i∈A 2 (∆bad . )2 i Proof. On Gt , if s is selected in the LCB phase then g(s) ≥ P 1 Proof. By Lemma 9 and linearity of expectation, / Sbad . m LCBim (s) (t) ≥ τr by Lemma 5, so s ∈ M " T # By Lemma 7, the regret in Lemma 6 simplifies to X X norm E[BMEAN (T )] ≤ E 1{Ei,t (∆i )} . S π2 i∈A t=T +1 0 |A| τr + τr E BMEAN (T ) E R (T ) ≤ 3 (5) ∆bad X Apply Lemma 11 to each i with ∆norm = rii , to obtain i +E ∆sat (St ) + T0 τr . t∈TCTS X X 1 ri2 = . E[BMEAN (T )] ≤ norm 2 It remains to bound E[BMEAN (T )] (Section V-C) and the 2(∆i )2 2 (∆bad i ) i∈A i∈A CTS-phase regret (Section V-D). (i)
C. Bounding E[BMEAN (T )] Recall the overestimation event Ei,t (ε) from (4) and the (i) norm gap quantities ∆bad , Sbad from Section IV-C. The i , ∆i following lemma relates bad arm pulls in the MEAN phase with the overestimation events.
Arms with Sbad ri2 := 0). ( 2(∆bad )2
=
∅ contribute zero by convention
i
D. CTS-Phase Analysis
The CTS phase runs in rounds i = 1, 2, 3, . . . with a doubling schedule: round i runs a fresh CTS instance (initialised Lemma 8. On any round t in the MEAN phase, with Beta(1, 1) priors) for exactly 2i steps. All observations M update the shared counters used by the MEAN gate. After [ {St ∈ Sbad , ĝshared (St , t) ≥ τr } ⊆ Eim (St ),t ∆norm im (St ) . round i, if any assignment satisfies ĝshared (s, t) ≥ τr , the m=1 MEAN gate takes over; otherwise round i + 1 begins. We analyse this phase following the geometric-series framework Next, we bound BMEAN (T ) in terms of the events in (4). of SELECT [42], treating each fresh CTS round as the oracle. P PT Lemma 9. BMEAN (T ) ≤ i∈A t=T0 +1 1{Ei,t (∆norm )}. i Recall that under Assumption 3, s⋆ is the unique optimal Proof. By Lemma 8, every MEAN-phase bad pull implies super arm. For a fresh CTS instance on a deterministic Ei,t (∆norm ) for at least one base arm P i used at time t. Hence horizon T , recall Bsub (T ) from Section IV-C. Let i norm " T # 1{St ∈ Sbad , MEAN phase} ≤ )}. i∈A 1{Ei,t (∆i X std ⋆ Summing over t = T0 + 1, . . . , T yields the claim. g(s ) − g(St ) RegCTS (T ) := E Recall the pull-time set Ti (T ) from Section IV-C. The next lemma bounds occurrences of Ei,t (ε) in terms of deviations of ψ̂i,n . 10. Fix i ∈ 1{E = i,t (ε)} t=T +1 o PT 0 n n=1 1 ψ̂i,n ≥ ψi + ε .
Lemma PT
APand
ε
> 0. Then 1{E ≤ i,t (ε)} t∈Ti (T )
Using Lemma 10, the next lemma bounds the expected occurrences of Ei,t (ε).
t=1
denote the standard regret of a fresh CTS instance over a deterministic horizon T . By Lemma 3, the bounded-smoothness assumption in [16] holds with Bcts = rmax /M . The next lemma, whose proof follows from Theorem 1 of [16], bounds the expected number of times a suboptimal assignment is played in a single phase of CTS. Lemma 13. For a fresh CTS instance on deterministic horizon T , letting Bcts := rmax /M (Lemma 3), for any 0 < ε <
9
M ∆std min
, we have E[Bsub (T )]
2 rmax (k⋆ )2 +2
≤
Ĉ1 log T + Ĉ0 ,
where Ĉ1 :=
X
2 8Bcts |s|2
2 , ∆s − 2Bcts ((k ⋆ )2 + 2)ε i∈A k ⋆ 2 8 4 |A|Kmax k⋆ + 3|A| + α1 · 2 2 + 1 Ĉ0 := log 2 , 2 ε ε ε ε max
s: i∈s, s̸=s⋆
with Bcts = rmax /M , k ⋆ = M , Kmax = M , and α1 the absolute constant from Theorem 1 of [16]. For δ ∈ (0, 14 ), define 2 rmax M 1 + 2 2 2∆⋆ rmax , N0 := 2∆2 log δ ⋆ as the critical observation count, where ∆⋆ := g ⋆ − τr > 0. The next lemma relates the MEAN gate failure with deviation of the base arm rewards.
2N ∆2 exp − r20 ⋆ max 2 . =M· 2∆ 1 − exp − r2 ⋆ max
2∆2
x Using 1 − e−x ≥ 1+x , x ≥ 0, with x = r2 ⋆ , we get max
Therefore,
2 1+x 1 rmax 1 ≤ . = 1 + = 1 + 1 − e−x x x 2∆2⋆
P(·) ≤ M
1+
2 rmax 2∆2⋆
2N0 ∆2 · exp − 2 ⋆ . rmax
By the choice of N0 ,
M 2N0 ∆2⋆ ≥ log 2 rmax
r2
max 1 + 2∆ 2 ⋆
δ
,
so P(·) ≤ δ.
⋆ Definition 1 (Critical CTS horizon). Define TCTS as the smallest positive integer satisfying
Lemma 14. For any time t at which every constituent arm of 1 ⋆ ⋆ s⋆ has been pulled at least once, + Ĉ0 ). (6) TCTS − N0 ≥ (Ĉ1 log TCTS δ M [ ⋆ ∆⋆ is finite and Since log grows slower than linearly, TCTS {ĝshared (s⋆ , t) < τr } ⊆ ψ̂im (s⋆ ) (t) − ψim (s⋆ ) < − r depends only on problem parameters and δ. max m=1 Utilizing Lemma 14, the next lemma shows that MEAN gate failure has negligible probability after the critical observation count has been reached. Lemma 15. If every constituent arm im (s⋆ ), m ∈ [M ], has been observed at least N0 times via the shared counters at some time t0 , then P(∃ t ≥ t0 : ĝshared (s⋆ , t) < τr ) ≤ δ, where ĝshared (s⋆ , t) is evaluated using the shared counters at time t. Proof. Since ĝshared (s⋆ , t) changes only when a constituent arm of s⋆ is pulled, it suffices to take the union over pull counts rather than time steps. At any time t ≥ t0 where the gate fails, each constituent arm im (s⋆ ) has some pull count nim (s⋆ ) (t) ≥ N0 . By Lemma 14, gate failure at time t implies that at least one arm im (s⋆ ) ⋆ . Therefore: satisfies ψ̂im (s⋆ ) (t) − ψim (s⋆ ) < − r∆ max ⋆
{∃ t ≥ t0 : ĝshared (s , t) < τr } M ∞ [ [ ∆⋆ ⋆ ⋆ . ⊆ ψ̂im (s ),n − ψim (s ) < − rmax m=1 n=N0
Taking probabilities and applying the union bound: P(∃ t ≥ t0 : ĝshared (s⋆ , t) < τr ) M X ∞ X ∆⋆ ≤ P ψ̂im (s⋆ ),n − ψim (s⋆ ) < − rmax m=1 n=N0 M X ∞ X 2n∆2 ≤ exp − 2 ⋆ (Lemma 1) rmax m=1 n=N0
⋆ . The next lemma puts an upper bound on TCTS
Lemma 16. The critical horizon satisfies #+ " 2Ĉ1 Ĉ1 δN0 + Ĉ0 ⋆ TCTS ≤ δ log δ + . Ĉ1 The next lemma shows that the CTS plays the optimal arm at least as much as the critical observation count with overwhelming probability. ⋆ Lemma 17. For any deterministic T ≥ TCTS , P(Ns⋆ (T ) < N0 ) ≤ δ, where Ns⋆ (T ) denotes the number of times the unique optimal arm s⋆ is played up to time T .
Proof. Since s⋆ is the unique optimal arm, every play is either optimal or suboptimal, so Ns⋆ (T ) = T − Bsub (T ). Hence P(Ns⋆ (T ) < N0 ) = P(Bsub (T ) > T − N0 ) ≤ ≤
Ĉ1 log T + Ĉ0 ≤ δ, T − N0
E[Bsub (T )] T − N0
where the second step is Markov’s inequality, the third uses Lemma 13, and the last follows from Definition 1. The key result given below proves that CTS phases become rarer over time. Proposition 1. Under Assumptions 1 and 3, for any CTS ⋆ round i with 2i ≥ TCTS , P(round i+1 starts | round i started) ≤ 2δ.
Proof. Let round i be the most recently completed CTS round, ⋆ with T = 2i ≥ TCTS . Condition on the event that round i started. Round i + 1 starts only if the MEAN gate fails after
10
round i, i.e., if at the gate-evaluation time t ĝshared (s, t) < τr for all s ∈ S. Since s⋆ ∈ S, this implies in particular that ĝshared (s⋆ , t) < τr . Therefore, {round i + 1 starts} ⊆ {ĝshared (s⋆ , t) < τr }. Now decompose according to whether s⋆ has been played at least N0 times during round i: P(round i + 1 starts | round i started)
≤ P(Ns⋆ (T ) < N0 ) + P(ĝshared (s⋆ , t) < τr , Ns⋆ (T ) ≥ N0 ) .
The first term is at most δ by Lemma 17. For the second term, on the event {Ns⋆ (T ) ≥ N0 }, each constituent arm of s⋆ has at least N0 observations in the shared counters. Hence Lemma 15 implies P(∃ t′ after round i : ĝshared (s⋆ , t′ ) < τr | Ns⋆ (T ) ≥ N0 ) ≤ δ.
E. Proof of Theorem 1 π2 |A| τr + τr E[BMEAN (T )] E[RS (T )] ≤ T0 τr + X3 ∆sat (St ) +E t∈TCTS
by (5). The first term is the initialization cost, bounded by Rinit = T0 τr . The second term is bounded by Rconf by Lemma 4. The third term is bounded by RMEAN by Lemma 12. The fourth term is bounded by RCTS by Corollary 1. All four terms are finite constants independent of T . VI. E XPERIMENTS A. Experimental Setup
! Ĉ1 i⋆ log 2 + Ĉ0 2Ĉ1 δ log 2 + + , 1 − 2δ (1 − 2δ)2
We consider a multi-cell mmWave communication system with 3 BSs, where each BS is equipped with a uniform linear array (ULA) of 64 antenna elements with full wavelength spacing. Each BS can form 120 directional beams, resulting in a total of 360 beams across the network that serve 15 UEs distributed across the coverage area. The channel characteristics are obtained using the DeepMIMO dataset [19], specifically the city_3_houston_28 scenario, which provides realistic channel realizations based on ray-tracing simulations in an urban environment.2 The system operates with a bandwidth of 50 MHz [19], enabling high-throughput communication in the millimeter-wave band. The system employs adaptive modulation with three discrete rate levels: {6, 8, 12} bits/symbol, which correspond to achievable data rates of 300 Mbps, 400 Mbps, and 600 Mbps respectively with the 50 MHz bandwidth. The target performance which is equal to satisficing threshold is set at τr = 8 bits/symbol for the realizable case, corresponding to 400 Mbps per user, and in the non-realizable case it is set to τr = 25 bits/symbol which corresponds to 1.25 Gbps. For all measurements, simulations were repeated for 5 independent runs and the average with standard deviation is plotted. For the optimization oracle, the Hungarian Algorithm is used [45]. The channel gain randomness is achieved by modeling the array steering vector in (1) as a Gaussian distributed random variable with mean equal to the channel vector. As benchmarks, we use CTS [16], CUCB [15], and the preliminary workshop version of our method, denoted by SAT-CTS-W [1]. In the theoretical analysis (Sections V–B), each committed CTS round is modeled as a fresh instance initialized with Beta(1, 1) priors. This fresh-start construction is introduced to obtain a clean finite-time regret analysis by decoupling successive CTS rounds and enabling a deterministic-horizon argument. In the simulations, however, we do not restart the Beta priors at the beginning of each CTS round; the CTS phase instead samples from the global posterior accumulated over all previous rounds, allowing it to retain history. We have observed that this minor modification consistently improves empirical performance.
⋆ where i⋆ = ⌈log2 TCTS ⌉. In particular, this is a finite constant independent of T .
2 Our implementation is available at https://github.com/Bilkent-CYBORG/ Satisficing-with-Binary-Feedback-for-Combinatorial-Beam-Alignment.
Thus the second term is also at most δ. Combining the two bounds yields P(round i+1 starts | round i started) ≤ 2δ. ⋆ ⌉, Definition 2 (Critical round index). Define i⋆ := ⌈log2 TCTS i ⋆ ⋆ so that 2 ≥ TCTS for all i ≥ i .
The following proposition shows that the occurrence probability of CTS phases geometrically decay over phases. Proposition 2. For all k ≥ 0, P(round i⋆ +k starts) ≤ (2δ)k . Proof. If round i does not start, neither does round i + 1, so for all i ≥ i⋆ , P(round i+1 starts) = P(round i+1 starts | round i started) · P(round i started) ≤ 2δ · P(round i started),
where the inequality follows from Proposition 1. Applying this recursively, P(round i⋆ +k starts) ≤ 2δ · P(round i⋆ +k−1 started) ≤ (2δ)2 · P(round i⋆ +k−2 started) ≤ . . . ≤ (2δ)k · P(round i⋆ started) ≤ (2δ)k .
Next, we bound the CTS-phase regret of SAT-CTS. Corollary 1. Under Assumptions 1 and 3, the expected cumulative satisficing regret incurred during the CTS phase satisfies X Ĉ1 log 2 ⋆ 2 (i ) + Ĉ0 i⋆ E ∆sat (St ) ≤ τr 2 t∈TCTS
1.0
SAT-CTS SAT-CTS-W CTS CUCB
50000 40000
Jain’s Fairness Index
Cumulative Satisficing Regret
11
30000 20000 10000
0.8 0.6 0.4 SAT-CTS SAT-CTS-W CTS CUCB
0.2
0 0
2000
4000
6000
8000
0.0
10000
0
Time Slot
6000
20000
0 −100 −200
SAT-CTS SAT-CTS-W CTS CUCB
−300
0 2000
10000
100
40000
0
8000
Fig. 5: Jain’s Fairness Index over time.
Sum of Log Utilities
Cumulative Satisficing Regret
SAT-CTS SAT-CTS-W CTS CUCB
60000
4000
Time Slot
Fig. 3: Cumulative satisficing regret (realizable, τr = 8).
80000
2000
4000
6000
8000
10000
Time Slot Fig. 4: Cumulative satisficing regret (non-realizable, τr = 25). We measure the cumulative satisficing regret for varying thresholds and assess user-level fairness on the same performance metric as our objective, throughput. Let rm,t = ρm,t xm,t be UE m’s throughput (bits/symbol) at slot t; define PT cumulative throughput Gm (T ) = t=1 rm,t . We report Jain’s Fairness Index [46]: 2 h PM i m=1 Gm (T ) 1 J(T ) = ∈ M ,1 , PM M m=1 G2m (T ) where J = 1 indicates perfectly even throughput across UEs and smaller values indicate disparity. The cumulative fairness over time is also measured in simulation. B. Results and Discussion Fig. 3 shows the cumulative satisficing regret under a realizable threshold (τr = 8).3 Among all algorithms, the proposed SAT-CTS achieves the lowest cumulative satisficing 3 Some error bars are not visible because the standard deviation over different runs is very small.
0
2000
4000
6000
8000
10000
Time Slot Fig. 6: Sum of log utilities over time. regret throughout the horizon. Its regret increases only during the initial learning period and then flattens early, indicating that the algorithm quickly identifies beam-rate assignments whose average throughput satisfies the target. This behavior is consistent with Theorem 1, which guarantees a horizonfree upper bound on the cumulative satisficing regret when the target is realizable. At T = 10,000, SAT-CTS attains the smallest regret, followed by SAT-CTS-W, then CTS, while CUCB performs significantly worse. These results empirically support the algorithmic changes made relative to the workshop version, namely replacing the earlier design with the committed-round SAT-CTS structure and removing the optimistic UCB gate. When the target is non-realizable (τr = 25, Fig. 4), all methods obtain linear satisficing regret because no super arm can meet the threshold. In SAT-CTS, the decision gate (LCB → MEAN) frequently finds that no candidate achieves the target; it therefore enters committed CTS rounds, which are effectively standard CTS on the super-arm. As a result, SATCTS, SAT-CTS-W, and CTS behave nearly identically. This is precisely as predicted by Theorem 2, which shows that SAT-
12
CTS reduces to CTS after a finite transient when the target is non-realizable. CUCB, in contrast, incurs cumulative regret more than double that of the other methods confirming that its purely optimistic exploration is inefficient even under nonrealizability. Fairness results in Figure 5 show that both SAT-CTS and SAT-CTS-W achieve substantially higher Jain’s Fairness Index than CTS and CUCB throughout the horizon. At early time slots, all methods improve rapidly, but the SAT-CTS variants separate from the baselines as learning progresses. At T = 10,000, SAT-CTS-W reaches a Jain’s index of 0.776, followed by SAT-CTS at 0.764, while CTS and CUCB lag behind at 0.669 and 0.574, respectively. This indicates that the satisficing-based methods allocate service more evenly across users over time. PM Fig. 6 shows the sum of log utilities m=1 log Gm (T ), another standard measure of fairness. At T = 10,000, SATCTS-W achieves 153.5, SAT-CTS reaches 153.3, and CTS attains 152.9, while CUCB remains clearly below at 135.4. Taken together, these results show that SAT-CTS matches or exceeds the workshop version on fairness-related metrics and consistently improves over the classical baselines. C. Scalability Experiments We next evaluate how the proposed method scales with the different parameters of the problem. In particular, we study the effect of increasing the beam codebook size, the number of BSs, and the number of users on cumulative satisficing regret at T = 10,000 (mean ± std). TABLE III: Cumulative satisficing regret at T = 10,000 across beam codebook sizes (15 users, 3 BSs, τr = 8 bits/symbol, averaged over 5 runs). K (beams/BS) Algorithm
30
60
120
240
SAT-CTS SAT-CTS-W CTS CUCB
8169 ± 199 15410 ± 67 8414 ± 86 38426 ± 153
7975 ± 10 19442 ± 23 7928 ± 87 43074 ± 71
5596 ± 71 7331 ± 10 8940 ± 67 54451 ± 51
4156 ± 997 8263 ± 28 10182 ± 102 61286 ± 14
Table III shows that SAT-CTS remains robust as the beam codebook size grows. The performance improvement with larger beam codebooks can be explained by two complementary effects. First, SAT-CTS adapts quickly enough to benefit from the richer beam set without incurring excessive exploration cost which can be seen by comparing with the CTS. Second, as the number of beams increases, the beams become narrower and more directional, which concentrates transmit power more effectively toward the intended UE. This improves the received SNR and reduces the outage probability, making it easier to find beam-rate assignments that satisfy the throughput target. Table IV evaluates scaling with the number of BSs. The two BS case appears more challenging for all methods, but when the system expands to three BSs, SAT-CTS achieves the lowest regret and improves substantially over CTS, as also reflected by the SAT-CTS/CTS ratio dropping to 0.693.
TABLE IV: Cumulative satisficing regret at T = 10,000 across number of base stations (15 users, K = 120 beams/BS, τr = 8 bits/symbol, averaged over 5 runs). Number of BSs Algorithm
1
2
3
SAT-CTS SAT-CTS-W CTS CUCB
7247 ± 89 10137 ± 126 7341 ± 100 21391 ± 54
17161 ± 183 30791 ± 52 17370 ± 82 51465 ± 81
6207 ± 903 8074 ± 505 8952 ± 16 54387 ± 61
SAT-CTS/CTS
0.987
0.988
0.693
This indicates that SAT-CTS benefits more effectively from the additional spatial diversity and assignment flexibility available in the larger network, while CUCB remains consistently much worse than the Thompson sampling based methods. TABLE V: Cumulative satisficing regret at T = 10,000 across number of users (3 BSs, K = 120 beams/BS, 360 total beams, τr = 8 bits/, averaged over 5 runs). Number of Users Algorithm
15
50
100
SAT-CTS SAT-CTS-W CTS CUCB
5596 ± 71 7331 ± 10 8940 ± 67 54451 ± 51
4940 ± 25 7380 ± 149 6115 ± 61 52199 ± 53
1634 ± 8 3657 ± 5 4463 ± 21 50259 ± 37
Table V examines the effect of increasing the number of users. This table suggests that, in the considered environment, increasing the number of users can improve learning efficiency. A possible reason is that the learner receives more semi-bandit feedback in each round, since one ACK/NACK outcome is observed per served user. At the same time, because 360 beams are available for at most 100 users, beam contention remains limited in these experiments. Thus, the additional feedback appears to outweigh the increased assignment complexity in this setting. We emphasize, however, that this is an empirical observation for the present scenario rather than a general claim for all system scales. CUCB, in contrast, remains an order of magnitude worse across all cases. VII. C ONCLUSION AND F UTURE R ESEARCH We formulated a multi-user beam–rate selection problem with ACK/NACK feedback as a satisficing combinatorial bandit with a per-user throughput threshold and a no–beamsharing assignment, for which we proposed SAT-CTS, an ifgated policy that blends conservative and exploratory indices. We established finite-time regret bounds for SAT-CTS: when the satisficing threshold is realizable, we proved a horizonfree upper bound on cumulative satisficing regret; when the threshold is non-realizable, we showed that SAT-CTS reduces to CTS after a finite transient and inherits the standard CTS regret bound. In experiments on time-varying channels using DeepMIMO as an accurate simulator of real-life environments, SAT-CTS reached realizable targets with lower cumulative satisficing regret than baselines found in the literature, consistent with our theoretical bounds, while behaving comparably to CTS when the target was infeasible, as predicted by our
13
reduction theorem. As future work, it is possible to extend our formulations and approaches to contextual combinatorial bandits that exploit side information (e.g., geometry, mobility) to accelerate learning and improve robustness. One could also explicitly incorporate fairness objectives as constraints or via multi-objective optimization.
ni (T0 + 1), ni (T0 + 1) + 1, . . . , ni (T ) exactly once. Therefore
= 2t−3 .
T X
Note that for t > T0 , we have 1 ≤ ni (t) ≤ t. Thus, ψ̂i (t) − ψi > c(t, ni (t)) ⊆
n=1
ψ̂i,n − ψi > c(t, n)
=
2t−3 = 2t−2 .
B. Proof of Lemma 3 We have M
1 X rim (s) ψim (s) − ψ̃im (s) M m=1 M
≤
1 X ri (s) ψim (s) − ψ̃im (s) M m=1 m
M rmax X ψi (s) − ψ̃im (s) M m=1 m rmax = ∥ψs − ψ̃s ∥1 . M
≤
Let St = s ∈ Sbad and ĝshared (s, t) ≥ τr . Then ĝshared (s, t) − g(s) ≥ τr − g(s) = ∆sat (s). Write M
If for all m we had ∆bad im (s) rim (s)
X n=ni (T0 +1)
≤
n o 1 ψ̂i,n ≥ ψi + ε
T n o X 1 ψ̂i,n ≥ ψi + ε .
n=1
E. Proof of Lemma 13 Let θi (t) ∼ Beta(Ai , Bi ) denote the Thompson sample for arm i at time t, and let θSt (t) := (θi1 (St ) (t), . . . , θiM (St ) (t)). We apply the four-event decomposition of the supplementary material of [16] directly to 1{St ̸= s⋆ } rather than to the regret-weighted quantity ∆St · 1{St ̸= s⋆ }. Recall the four events: • A(t) = {St ∈ / OPT}, • B(t) = {∃ i ∈ St , |ψ̂i (t) − ψi | > ε/|St |}, ⋆ 2 • C(t) = {∥θSt (t) − ψSt ∥1 > ∆St /Bcts − ((k ) + 1)ε}, p 2 log T /ni (t)}. • D(t) = {∃ i ∈ St , |θi (t) − ψ̂i (t)| > Term 1 (B(t) ∧ A(t), Section B.3.1 of [16]): By Lemma 3 of [16], the expected number of rounds arm i is played with 2 empirical mean deviation > ε/Kmax is at most 1 + Kmax /ε2 . Summing over arms and dropping the ∆max weight: T X t=1
T X t=1
1 X rim (s) ψ̂im (s) (t) − ψim (s) . M m=1
ψ̂im (s) (t) − ψim (s) < ∆norm im (s) =
=
E[1{B(t) ∧ A(t)}] ≤ |A| +
2 |A|Kmax . ε2
Term 2 (¬B ∧C ∧D ∧A, Section p B.3.2 of [16]): By Lemma 4 of [16], Pr[|θi (t) − ψ̂i (t)| > 2 log T /ni (t)] ≤ 2/T . A union bound over arms gives:
C. Proof of Lemma 8
ĝshared (s, t) − g(s) =
1{Ei,t (ε)}
ni (T )
n=1
|g(s; ψs ) − g(s; ψ̃s )| =
X t∈Ti (T )
o
t X P ψ̂i,n − ψi > c(t, n)
n=1 t X
1{Ei,t (ε)} =
t=T0 +1
Using the two displays above, we obtain the following via the union bound P ψ̂i (t) − ψi > c(t, ni (t)) ≤
contradiction. Hence at least one m satisfies
As t ranges over Ti (T ), the count ni (t) takes distinct values
For a fixed n ≥ 1, we have by Lemma 1 P ψ̂i,n − ψi > c(t, n) ≤ 2 exp −2nc(t, n)2 = 2 exp −3 log t
t n [
∆sat (s) 1 X ri (s) · = ∆sat (s), M m=1 m rim (s)
D. Proof of Lemma 10
A. Proof of Lemma 2
o
M
ĝshared (s, t) − g(s) <
ψ̂im (s) (t) − ψim (s) ≥ ∆norm im (s) .
A PPENDIX A O MITTED P ROOFS OF R ESULTS IN S ECTION V
n
then since ∆bad im (s) ≤ ∆sat (s) for each im (s) ∈ s,
,
E[1{¬B(t) ∧ C(t) ∧ D(t) ∧ A(t)}] ≤ 2|A|.
Term 3 (¬B ∧ C ∧ ¬D ∧ A, Section B.3.3 of [16]): Define the sufficiency threshold Li (s) :=
2 8Bcts |s|2 log T = . 2 (∆s − 2Bcts ((k ⋆ )2 + 2)ε)2 (k⋆ )2 +2 ∆s − ε 2Bcts |s| |s|
2 log T
14
By Section B.3.3 of [16], if ni (t) > Li (St ) for all i ∈ St then ¬B ∧ C ∧ ¬D ∧ A cannot occur. Hence at any such round there exists a witness arm i ∈ St with ni (t) ≤ Li (St ) ≤ Lmax , i where Lmax := maxs: i∈s, s̸=s⋆ Li (s). Since ni (t) increments i with each pull of arm i, arm i can serve as witness for at most rounds. Summing over arms: Lmax i T X t=1
E[1{¬B(t)∧C(t)∧¬D(t)∧A(t)}] ≤
X
Lmax = Ĉ1 log T. i
H. Proof of Corollary 1 For any CTS round i, since ∆sat (St ) = [τr − g(St )]+ , and g(s⋆ ) > τr under realizability, we have ∆sat (St ) = 0 whenever St = s⋆ . Also, for any t, ∆sat (St ) ≤ τr . Hence, "
i∈A
Term 4 (¬C ∧ A, Section B.3.4 of [16]): By Lemma 7 of [16] applied to the count (dropping the ∆max factor): k⋆ T X 8 4 k⋆ E[1{¬C(t) ∧ A(t)}] ≤ α1 · 2 2 + 1 log 2 . ε ε ε t=1 Summing all four terms, with Ĉ0 collecting Terms 1, 2, and 4, yields the result.
E
t∈round i
Suppose for contradiction that for all m ∈ [M ], ∆⋆ . ψ̂im (s⋆ ) (t) − ψim (s⋆ ) ≥ − rmax Since rim (s⋆ ) ≤ rmax , multiplying both sides by rim (s⋆ ) gives
rim (s⋆ ) ψ̂im (s⋆ ) (t) − ψim (s⋆ ) ≥ −rim (s⋆ ) ·
∆⋆ ≥ −∆⋆ rmax
for every m. Averaging over m = 1, . . . , M :
∆sat (St ) ≤ τr E[Bsub (2i )] ≤ τr (Ĉ1 i log 2+ Ĉ0 ),
where the last inequality follows from Lemma 13. Therefore, the total CTS-phase satisficing regret satisfies " # X E ∆sat (St ) ≤
F. Proof of Lemma 14
# X
t∈TCTS ∞ X
τr (Ĉ1 i log 2 + Ĉ0 ) P(round i starts) i=1 ⋆ iX −1
≤ τr
(Ĉ1 i log 2 + Ĉ0 )
i=1 ∞ X
+ τr ≤ τr
(Ĉ1 (i⋆ + k) log 2 + Ĉ0 )(2δ)k
k=0 ! Ĉ1 i⋆ log 2 + Ĉ0 2Ĉ1 δ log 2 Ĉ1 log 2 ⋆ 2 ⋆ (i ) + Ĉ0 i + + , 2 1 − 2δ (1 − 2δ)2
where the second inequality follows from Proposition 2, and M ⋆ X i⋆ = ⌈log2 TCTS ⌉. Thus, the CTS-phase satisficing regret is 1 rim (s⋆ ) ψ̂im (s⋆ ) (t) − ψim (s⋆ ) O((log T ⋆ )2 ), which is a finite constant independent of T . ĝshared (s⋆ , t) − g(s⋆ ) = M m=1 CTS M
≥
1 X (−∆⋆ ) = −∆⋆ . M m=1
Hence ĝshared (s⋆ , t) ≥ g(s⋆ ) − ∆⋆ = τr , contradicting ĝshared (s⋆ , t) < τr . Therefore at least one m ∈ [M ] satisfies ψ̂im (s⋆ ) (t) − ψim (s⋆ ) < −∆⋆ /rmax . G. Proof of Lemma 16 Rearranging (6), we need the smallest T such that aT +b ≥ 0 +Ĉ0 log T , where a := Ĉδ > 0, b := − δNĈ . By Lemma 8 of 1 1 [47], this inequality holds for all " #+ + 2 1 2Ĉ1 Ĉ1 δN0 + Ĉ0 T ≥ log − b = log + . a a δ δ Ĉ1 ⋆ Since TCTS is an integer, " #+ 2 Ĉ Ĉ δN + Ĉ 1 1 0 0 ⋆ . TCTS ≤ δ log δ + Ĉ1
A PPENDIX B S TANDARD R EGRET A NALYSIS FOR N ON -R EALIZABLE TARGET In this section we analyze SAT-CTS when the satisficing threshold is non-realizable. In this case, no assignment can achieve the target average throughput. We show that the expected number of rounds in which the LCB or MEAN gate fires after initialization is finite. We also show that the expected number of rounds in which SAT-CTS does not execute a CTS step is finite. The remaining regret is therefore governed by the sum of the regret contributions of committed CTS rounds. Since each committed CTS round is restarted with fresh priors, the total standard regret is obtained by summing the regret over all CTS rounds, which yields an O((log T )2 ) bound, similar to the non-realizable regret bound in [42]. We use the same notation as in Section IV-C. Recall that g(s), g ⋆ , and s⋆ denote the average expected throughput, optimal throughput, and unique optimal assignment, respectively. Recall ∆nr (s) from Section IV-C. Under Assumption 2, we have ∆nr (s) ≥ ∆nr ⋆ >0
for all s ∈ S.
15
A. LCB and MEAN Gates under Non-Realizability
then
We first show that on the good event, the LCB gate cannot fire, while the MEAN gate can fire only finitely many times in expectation.
ĝshared (SM , t) − g(SM ) <
Lemma 18 (LCB gate cannot fire on the good event). For all t > T0 , on Gt , the LCB gate does not fire. Equivalently, 1{Avg(LCB, SL ) ≥ τr , Gt } = 0
M
1 X LCBim (SL ) (t) = Avg(LCB, SL ). M m=1
g(SL ) ≥ Avg(LCB, SL ) ≥ τr . ⋆
< τr .
Definition 3 (MEAN-gate firing count). Define the number of rounds in which the MEAN gate fires after initialization up to time T as NMEAN (T ) :=
T X t=T0 +1
1{ĝshared (SM , t) ≥ τr },
where SM denotes the assignment returned by the MEAN oracle at time t. Since ĝshared (SM , t) = Avg(MEAN, SM ),
∆nr (SM ) . rim (SM )
This proves the claim. Lemma 20 (Finite expected number of MEAN-gate firings). For all T ≥ T0 + 1, E[NMEAN (T )] ≤
Hence, if the LCB gate fired on Gt , then This contradicts Assumption 2, since g(SL ) ≤ g Therefore the LCB gate cannot fire on Gt .
which is a contradiction. Hence there exists at least one m ∈ [M ] such that ψ̂im (SM ) (t) − ψim (SM ) ≥
a.s.
Proof. Let SL be the assignment returned by the LCB oracle at time t > T0 . By Lemma 5, on Gt we have g(SL ) ≥
M
1 X nr ∆ (SM ) = ∆nr (SM ), M m=1
X i∈A
ri2 . 2 2(∆nr ⋆ )
Proof. By Lemma 19, every MEAN-gate firing at time t > T0 implies that for at least one constituent arm im (SM ), ψ̂im (SM ) (t) − ψim (SM ) ≥
∆nr (SM ) . rim (SM )
Since ∆nr (SM ) ≥ ∆nr ⋆ , it follows that nr T X X ∆⋆ NMEAN (T ) ≤ 1 Ei,t . ri i∈A t=T0 +1
Taking expectations and applying Lemma 11 with ε = ∆nr ⋆ /ri gives E[NMEAN (T )] ≤
1
X
2 2(∆nr ⋆ /ri ) i∈A
=
X i∈A
ri2 . 2 2(∆nr ⋆ )
this is exactly the number of post-initialization rounds in which the MEAN gate fires. Lemma 19 (A MEAN-gate firing implies a single-arm upward deviation). For any round t > T0 , nr M [ ∆ (SM ) Eim (SM ),t {ĝshared (SM , t) ≥ τr } ⊆ , rim (SM ) m=1 where Ei,t (ε) is the overestimation event defined in (4). Proof. If the MEAN gate fires at time t > T0 , then ĝshared (SM , t) ≥ τr . Since g(SM ) < τr under Assumption 2, it follows that ĝshared (SM , t) − g(SM ) ≥ τr − g(SM ) = ∆nr (SM ). Write
B. Transient Contribution Outside CTS Rounds We now bound the number of rounds in which SAT-CTS does not execute a CTS step. Definition 4 (Non-CTS rounds). Let TnonCTS (T ) := {t ∈ [T ] : no CTS step is executed at time t}. These are the rounds in which SAT-CTS does not execute a CTS step. Lemma 21 (Finite expected number of non-CTS rounds). For all T ≥ 1, X ri2 π2 |A| + . E |TnonCTS (T )| ≤ T0 + 2 3 2(∆nr ⋆ ) i∈A
ĝshared (SM , t) − g(SM ) =
M 1 X ri (S ) ψ̂im (SM ) (t) − ψim (SM ) . M m=1 m M
If for all m ∈ [M ] we had ∆nr (SM ) ψ̂im (SM ) (t) − ψim (SM ) < , rim (SM )
Proof. The initialization phase contributes exactly T0 nonCTS rounds. For t > T0 , on Gt , the LCB gate cannot fire by Lemma 18. Therefore, if SAT-CTS does not execute a CTS step at time t > T0 , then either Gtc occurs or the MEAN gate fires. Hence |TnonCTS (T )| ≤ T0 +
T X t=T0 +1
1{Gtc } + NMEAN (T ).
16
Taking expectations, using X π2 P(Gtc ) ≤ |A| 3
Proof. Decompose the standard regret into regret incurred on CTS rounds and regret incurred on non-CTS rounds:
t>T0
X
Rstd (T ) =
from Lemma 4, and applying Lemma 20, we get X ri2 π2 . |A| + E |TnonCTS (T )| ≤ T0 + 2 3 2(∆nr ⋆ )
t∈TCTS (T )
g(s⋆ ) − g(St )
X
+
t∈TnonCTS (T )
i∈A
g(s⋆ ) − g(St ) ,
where TCTS (T ) := [T ] \ TnonCTS (T ).
C. Proof of Theorem 2 Recall that the algorithm executes CTS in committed phases of lengths 21 , 22 , . . . , 2j , . . ., where each committed phases is restarted with fresh Beta(1, 1) priors. Therefore, the regret accumulated during CTS rounds is obtained by summing the regret bounds of fresh CTS instances over the committed phases. Let J(T ) := log2 max{1, T − T0 + 2} . Up to time T , there are at most J(T ) committed CTS phases after initialization. Lemma 22 (CTS-round regret contribution). The expected standard regret accumulated over CTS rounds up to time T is at most J(T ) X ∆max Ĉ1 j log 2 + Ĉ0 ,
For the non-CTS rounds, each round contributes at most ∆max . Hence E
X
t∈TnonCTS (T )
g(s⋆ ) − g(St ) ≤ ∆max E |TnonCTS (T )| .
Applying Lemma 21, we obtain E
j=1
X
t∈TnonCTS (T )
where Ĉ1 , Ĉ0 are from Lemma 13 and ∆max is from Section IV-C. Proof. The jth committed CTS round runs a fresh CTS instance for at most 2j steps. By Lemma 13, E[Bsub (2j )] ≤ Ĉ1 log(2j ) + Ĉ0 = Ĉ1 j log 2 + Ĉ0 . Since each suboptimal play incurs at most ∆max standard regret, the expected standard regret of the jth round is at most ∆max E[Bsub (2j )] ≤ ∆max Ĉ1 j log 2 + Ĉ0 . Summing over all committed CTS rounds completed by time T yields the result. The theorem given below is the full version of Theorem 2, which explicitly describes the constants appearing in the O (log T )2 term in the standard regret bound. Theorem 3 (Standard regret under non-realizability). Under Assumptions 2 and 3, the expected standard regret of SAT-CTS satisfies
nr g(s⋆ ) − g(St ) ≤ Rtrans .
For the CTS rounds, Lemma 22 yields E
X
t∈TCTS (T )
J(T ) X g(s⋆ ) − g(St ) ≤ ∆max Ĉ1 j log 2+ Ĉ0 . j=1
Combining the two bounds gives J(T )
E[R
std
nr (T )] ≤ Rtrans +
X
∆max Ĉ1 j log 2 + Ĉ0 .
j=1
PJ(T ) PJ(T ) 2 Finally, since j=1 j = O(J(T ) ), j=1 1 = O(J(T )), and J(T ) = ⌈log2 (max{1, T−T0+2})⌉ = O(log T ), it follows that E[Rstd (T )] = O (log T )2 .
J(T ) nr E[Rstd (T )] ≤ Rtrans +
X
∆max Ĉ1 j log 2 + Ĉ0 ,
j=1
where nr Rtrans := ∆max
X π2 ri2 T0 + |A| + 2 3 2(∆nr ⋆ ) i∈A
Consequently, E[Rstd (T )] = O (log T )2 .
! ,
A PPENDIX C P SEUDOCODES OF CUCB AND CTS In this section, we represent the full pseudocodes of the competitor algorithms we used in Section VI.
17
Algorithm 2 CUCB: Combinatorial Upper Confidence Bound
Algorithm 3 CTS: Combinatorial Thompson Sampling
Require: M users, beam set K = [B] × [K], rate set R = {r1 < · · · < rR }, time horizon T 1: Initialize: 2: nm,(b,k),r ← 0, ψ̂m,(b,k),r ← 0 for all m ∈ [M ], (b, k) ∈ K, r ∈ R {Counts and success-rate estimates} 3: for t = 1 to T do 4: Step 1: UCB index computation on success probability 5: for each m ∈ [M ], (b, k) ∈ K, r ∈ R do 6: if nm,(b,k),r = 0 then UCBm,(b,k),r ← +∞ else s 3 log t 7: UCBm,(b,k),r ← ψ̂m,(b,k),r + 2nm,(b,k),r 8: θm,(b,k),r ← r · UCBm,(b,k),r 9: end for
Require: M users, beam set K = [B] × [K], rate set R = {r1 < · · · < rR }, time horizon T 1: Initialize: 2: Am,(b,k),r ← 1, Bm,(b,k),r ← 1 for all m ∈ [M ], (b, k) ∈ K, r ∈ R {Beta priors on ψ} 3: for t = 1 to T do 4: Step 1: Thompson sampling from posterior 5: for each m ∈ [M ], (b, k) ∈ K, r ∈ R do 6: ψ̃m,(b,k),r ∼ Beta(Am,(b,k),r , Bm,(b,k),r ) 7: θm,(b,k),r ← r · ψ̃m,(b,k),r {expected throughput sample} 8: end for
10: 11: 12: 13: 14: 15:
Step 2: Construct super-arm via optimal assignment (no sharing) S = {{(π1 , ρ1 ), . . . , (πM , ρM )} : πm ∈ K, ρm ∈ R, πm ̸= πn ∀m ̸= n}P M At ← arg maxs∈S m=1 θm,πm (s),ρm (s)
Step 3: Assign super-arm and update estimates (ACK/NACK) 16: Assign At = {(π1,t , ρ1,t ), . . . , (πM,t , ρM,t )} with πm,t = (bm,t , km,t ) 17: Observe xm,t ∈ {0, 1} for m = 1, . . . , M 18: for each user m ∈ [M ] do 19: nm,πm,t ,ρm,t ← nm,πm,t ,ρm,t + 1 20: ψ̂m,πm,t ,ρm,t ← ψ̂m,πm,t ,ρm,t + xm,t − ψ̂m,πm,t ,ρm,t nm,πm,t ,ρm,t 21: end for 22: end for
9: 10: 11: 12: 13: 14:
Step 2: Construct super-arm via optimal assignment (no sharing) S = {{(π1 , ρ1 ), . . . , (πM , ρM )} : πm ∈ K, ρm ∈ R, πm ̸= πn ∀m ̸= n}P M At ← arg maxs∈S m=1 θm,πm (s),ρm (s)
Step 3: Assign super-arm and update posteriors (ACK/NACK) 15: Assign At = {(π1,t , ρ1,t ), . . . , (πM,t , ρM,t )} with πm,t = (bm,t , km,t ) 16: Observe xm,t ∈ {0, 1} for m = 1, . . . , M 17: for each user m ∈ [M ] do 18: Am,πm,t ,ρm,t ← Am,πm,t ,ρm,t + xm,t 19: Bm,πm,t ,ρm,t ← Bm,πm,t ,ρm,t + (1 − xm,t ) 20: end for 21: end for R EFERENCES [1] E. Özyıldırım, B. Yaycı, U. E. Akturk, and C. Tekin, “Satisficing with binary feedback: Multi-user mmwave beam and rate adaptation via combinatorial bandits,” in NeurIPS Workshop, 2025. [Online]. Available: https://openreview.net/forum?id=qLtBU0mVB1 [2] J. Struye, F. Lemic, and J. Famaey, “Covrage: Millimeter-wave beamforming for mobile interactive virtual reality,” IEEE Trans. Wireless Commun., vol. 22, no. 7, pp. 4828–4842, 2022. [3] Y. Liu et al., “Mec-assisted panoramic VR video streaming over millimeter wave mobile networks,” IEEE Trans. Multimedia, vol. 21, no. 5, pp. 1302–1316, 2018. [4] T. S. Rappaport et al., “Wideband millimeter-wave propagation measurements and channel models for future wireless communication system design,” IEEE Trans. Commun., vol. 63, no. 9, pp. 3029–3056, 2015. [5] W. Deng et al., “CSI transfer from sub-6G to mmWave: Reducedoverhead multi-user hybrid beamforming,” IEEE J. Sel. Areas Commun., vol. 43, no. 3, pp. 973–987, 2025. [6] I. Aykin et al., “MAMBA: A multi-armed bandit framework for beam tracking in millimeter-wave systems,” in Proc. IEEE INFOCOM, 2020, pp. 1469–1478. [7] W. Wu et al., “Fast mmWave beam alignment via correlated bandit learning,” IEEE Trans. Wireless Commun., vol. 18, no. 12, pp. 5894– 5908, 2019. [8] A. Ktari, H. Ghauch, and G. Rekaya-Ben Othman, “Machine learning techniques for blind beam alignment in mmWave massive MIMO,” Entropy, vol. 26, no. 8, p. 626, 2024. [9] A. Paulraj et al., “An overview of mimo communications - a key to gigabit wireless,” Proc. IEEE, vol. 92, no. 2, pp. 198–218, 2004. [10] S. Hur et al., “Millimeter wave beamforming for wireless backhaul and access in small cell networks,” IEEE Trans. Commun., vol. 61, no. 10, pp. 4391–4403, Oct. 2013. [11] P. Zhou et al., “Enhanced random access and beam training for millimeter wave wireless local networks with high user density,” IEEE Trans. Wireless Commun., vol. 16, pp. 7760–7773, 2017.
18
[12] Y. Wei, Z. Zhong, and V. Y. Tan, “Fast beam alignment via pure exploration in multi-armed bandits,” IEEE Trans. Wireless Commun., vol. 22, no. 5, pp. 3264–3279, 2022. [13] T. Lattimore and C. Szepesvári, Bandit algorithms. Cambridge University Press, 2020. [14] B. Kveton et al., “Tight regret bounds for stochastic combinatorial semibandits,” in Proc. AISTATS, 2015, pp. 535–543. [15] W. Chen, Y. Wang, and Y. Yuan, “Combinatorial multi-armed bandit: General framework and applications,” in Proc. ICML, 2013, pp. 151– 159. [16] S. Wang and W. Chen, “Thompson sampling for combinatorial semibandits,” in Proc. ICML, 2018, pp. 5114–5122. [17] A. Hüyük and C. Tekin, “Thompson sampling for combinatorial network optimization in unknown environments,” IEEE Trans. Netw., vol. 28, no. 6, pp. 2836–2849, 2020. [18] H. A. Simon, “A behavioral model of rational choice,” The Quarterly Journal of Economics, vol. 69, no. 1, pp. 99–118, 1955. [19] A. Alkhateeb, “DeepMIMO: A generic deep learning dataset for millimeter wave and massive MIMO applications,” 2019. [Online]. Available: https://arxiv.org/abs/1902.06435 [20] Z. Tang et al., “A high-accuracy adaptive beam training algorithm for mmwave communication,” in Proc. IEEE GLOBECOM Workshops, 2018, pp. 1–6. [21] Z. Li et al., “Contextual combinatorial beam management via online probing for multiple access mmWave wireless networks,” IEEE J. Sel. Areas Commun., vol. 43, no. 3, pp. 959 – 972, 2025. [22] M. A. Qureshi, A. Nika, and C. Tekin, “Multi-user small base station association via contextual combinatorial volatile bandits,” IEEE Trans. Commun., vol. 69, no. 6, pp. 3726–3740, 2021. [23] H. Hassanieh et al., “Fast millimeter wave beam alignment,” in Proc. ACM SIGCOMM, 2018, p. 432–445. [24] A. Nika, S. Elahi, and C. Tekin, “Contextual combinatorial volatile multi-armed bandit with adaptive discretization,” in Proc. AISTATS, 2020, pp. 1486–1496. [25] Z. Marzi, D. Ramasamy, and U. Madhow, “Compressive channel estimation and tracking for large arrays in mm-Wave picocells,” IEEE J. Sel. Topics Signal Process., vol. 10, no. 3, pp. 514–527, 2016. [26] J. Wang et al., “Beam codebook based beamforming protocol for multiGbps millimeter-wave WPAN systems,” IEEE J. Sel. Areas Commun., vol. 27, no. 8, pp. 1390–1399, 2009. [27] G. Ghatak et al., “Beamwidth optimization and resource partitioning scheme for localization assisted mm-Wave communication,” IEEE Trans. Commun., vol. 69, no. 2, pp. 1358–1374, 2020. [28] A. Ali, N. González-Prelcic, and R. W. Heath, “Millimeter wave beamselection using out-of-band spatial information,” IEEE Trans. Wireless Commun., vol. 17, no. 2, pp. 1038–1052, 2017. [29] D. Ghosh, M. K. Hanawal, and N. Zlatanov, “UB3: Fixed budget best beam identification in mmwave massive MISO via pure exploration unimodal bandits,” IEEE Trans. Wireless Commun., vol. 23, no. 10, pp. 12 658–12 669, 2024. [30] M. Hashemi et al., “Efficient beam alignment in millimeter wave systems using contextual bandits,” in Proc. IEEE INFOCOM, 2018, pp. 2393– 2401. [31] Y. Zhang et al., “MmWave codebook selection in rapidly-varying channels via multinomial Thompson sampling,” in Proc. ACM MobiHoc, 2021, pp. 151–160. [32] K. Min, H.-S. Park, and H.-S. Lee, “Beam alignment for non-stationary environments using a novel time-varying structured bandit,” IEEE Trans. Veh. Technol., 2024. [33] G. Ghatak, “Best arm identification based beam acquisition in stationary and abruptly changing environments,” IEEE Trans. Signal Process., vol. 72, pp. 670–685, 2024. [34] N. Blinn and M. Bloch, “MAB dynamic beam zooming for mmWave alignment and tracking,” IEEE Trans. Wireless Commun., vol. 24, no. 9, pp. 7908 – 7922, 2025. [35] S. He et al., “Codebook-based hybrid precoding for millimeter wave multiuser systems,” IEEE Trans. Signal Process., vol. 65, no. 20, pp. 5289–5304, 2017. [36] H. Zhang et al., “mmwave indoor channel measurement campaign for 5g new radio indoor broadcasting,” IEEE Trans. Broadcast., vol. 68, no. 2, pp. 331–344, 2022. [37] X. Wu et al., “60-ghz millimeter-wave channel measurements and modeling for indoor office environments,” IEEE Trans. Antennas Propag., vol. 65, no. 4, pp. 1912–1924, 2017. [38] A. A. M. Saleh and R. A. Valenzuela, “A statistical model for indoor multipath propagation,” IEEE J. Sel. Areas Commun., vol. 5, no. 2, pp. 128–137, 1987.
[39] S. H. Lim et al., “Efficient beam training and sparse channel estimation for millimeter wave communications under mobility,” IEEE Trans. Commun., vol. 68, no. 10, pp. 6583–6596, Oct. 2020. [40] J. Wang, H. Zhu, L. Dai, N. J. Gomes, and J. Wang, “Low-complexity beam allocation for switched-beam based multiuser massive MIMO systems,” IEEE Trans. Wireless Commun., vol. 15, no. 12, pp. 8236– 8248, 2016. [41] J. Wang, H. Zhu, N. J. Gomes, and J. Wang, “Frequency reuse of beam allocation for multiuser massive MIMO systems,” IEEE Trans. Wireless Commun., vol. 17, no. 4, pp. 2346–2359, 2018. [42] Q. Feng, T. Ma, and R. Zhu, “Satisficing regret minimization in bandits,” in Proc. ICLR, 2025. [Online]. Available: https: //openreview.net/forum?id=5WPQIVgWCg [43] R. Combes, M. Lelarge, A. Proutière, and M. S. Talebi, “Stochastic and adversarial combinatorial bandits,” CoRR, vol. abs/1502.03475, 2015. [Online]. Available: http://arxiv.org/abs/1502.03475 [44] N. Merlis and S. Mannor, “Tight lower bounds for combinatorial multiarmed bandits,” in Proc. COLT, J. Abernethy and S. Agarwal, Eds., vol. 125, 09–12 Jul 2020, pp. 2830–2857. [45] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97, 1955. [46] R. Jain, D.-M. W. Chiu, and W. R. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” Digital Equipment Corporation, Tech. Rep. DEC-TR-301, Sep. 1984. [47] A. Antos, V. Grover, and C. Szepesvári, “Active learning in heteroscedastic noise,” Theoretical Computer Science, vol. 411, no. 29, pp. 2712–2728, 2010, algorithmic Learning Theory (ALT 2008). [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S0304397510002021