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

arXiv:2604.14908 · cs.LG, cs.SY, eess.SY, stat.ML · Submitted 2026-04-16 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits".

Jane: Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits addresses the challenge of efficiently learning optimal beam and data rate assignments in multi-user millimeter-wave Massive MIMO systems without explicit…

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So Jane, we're looking at this paper today titled "Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits." It tackles the challenge of figuring out the best beam settings and data rates in multi-user millimeter-wave massive MIMO systems when you don't have perfect channel state information.

Jane: That sounds incredibly complex, Tom; what exactly is the core idea this paper is pushing?

Lu: Essentially, they are modeling the problem as a combinatorial semi-bandit where the learner coordinates beam and rate assignments based only on feedback from user equipments using ACK/NACK signals.

Meng: So it's about learning these settings without knowing the exact channel conditions beforehand, which makes sense in real-world mmWave scenarios.

Lalam: It sounds like they are designing a way for the system to make good decisions under uncertainty, which is always something we focus on when building robust AI systems.

Tom: Exactly! The main thesis here is introducing SAT-CTS, a lightweight policy that blends conservative confidence estimates with posterior sampling to steer the learning process toward hitting a specific service goal called a satisficing throughput threshold rather than just chasing the absolute highest possible throughput.

Jane: That's what I find fascinating about their approach; instead of aiming for pure maximization, they are trying to hit a target level of performance.

Lu: Their main theoretical contribution is providing the first finite-time regret bounds for combinatorial semi-bandits with this satisficing objective, showing bounded cumulative satisficing regret when that target is reachable and polylogarithmic standard regret when it isn't.

Meng: Finite-time bounds are crucial because they tell us exactly how long we need to run the algorithm to get a reliable result in practice, which is something engineers really need.

Lalam: If we can prove the convergence speed under these specific conditions, that means our future AI systems will be much more predictable when deployed in complex networks.

Tom: It really matters because this research moves beyond just finding the absolute best configuration and focuses on finding a "good enough" one quickly to meet service requirements.

Paper summary: Jane: I think what’s important is how they handle the trade-off between exploring new beam-rate pairs and exploiting what we already know works well.

Lu: They define base arms as specific beam-rate combinations for a user, and super arms as the full set of assignment decisions for all users, which sets up the combinatorial space nicely.

Meng: From an engineering standpoint, modeling it this way helps structure the exploration process so it doesn't just wander randomly through too many options.

Lalam: It seems like their approach is designed to be very sample-efficient by being smarter about when to explore versus when to commit to a known good setting.

Tom: Speaking of that trade-off, they detail the SAT-CTS algorithm which has three main phases: a deterministic initialization phase where all base arms are played at least once, followed by a decision gate that checks lower confidence bounds and empirical means against the target average throughput tau r, and finally a committed CTS phase if neither gate fires.

Jane: That multi-stage process sounds very practical; it's not just one continuous learning loop.

Lu: The structure of SAT-CTS is what allows them to achieve those specific regret guarantees, showing how their hybrid strategy manages the exploration and exploitation balance effectively within the combinatorial semi-bandit framework.

Meng: I wonder how the system handles that decision gate when the feedback from users is noisy; does it make decisions quickly enough to stay efficient?

Lalam: If I look at this from a cultural perspective, this kind of careful policy design—prioritizing meeting a goal over chasing perfection—is really valuable for building reliable AI agents that operate in real-world, imperfect environments.

Tom: Moving into the conclusion of this paper, we have to talk about the implications of "Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits" and its authors.

Jane: The authors are tackling a very practical communication challenge where precise channel knowledge isn't available, which is a huge step for deploying advanced wireless technologies.

Lu: It suggests that feedback-efficient learning can be used to equitably allocate beams and rates to meet quality of service targets without needing explicit channel state knowledge.

Paper summary: Meng: For deployment, this means we might see communication systems that are much more resilient because they don't need perfect sensing capability constantly.

Lalam: The paper shows that learning can be shaped to prioritize meeting a service goal, which speaks to how we design AI agents to serve human needs effectively in complex infrastructures.

Tom: So, in simple terms, the core message is about creating a smarter way for systems to adapt their beam and rate choices when they don't know the channel perfectly by aiming for a satisfactory level of performance instead of trying to achieve an unattainable maximum.

Jane: That’s a clear summary: it’s about using sophisticated learning rules to hit a target rather than chasing infinity.

Lu: This framework, which treats the problem as a satisficing combinatorial MAB with semi-bandit feedback, offers a solid foundation for analyzing how learning algorithms behave in these complex combinatorial settings.

Meng: I'm curious if this method scales well when you have many different base stations involved; the paper mentions improving performance when expanding to three BSs, which is a key practical test for any new AI technique.

Lalam: This research gives us a blueprint for building more reliable AI decision-making processes where the goal is defined by service quality rather than just raw performance metrics.

Tom: We’ve covered the summary and now we’re wrapping up with the final thoughts on this paper, "Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits."

Jane: The implications really boil down to making wireless communication systems far more robust in environments where perfect channel knowledge is just out of reach.

Lu: It provides theoretical backing for how learning algorithms can be designed to prioritize meeting service goals, which is a significant step in understanding combinatorial bandit problems.

Meng: From an implementation standpoint, the paper’s focus on finite-time regret bounds gives us a concrete mathematical guarantee about how quickly these learning policies will stabilize under realistic conditions.

Lalam: This work helps shape the future of AI by showing how to build agents that are not just powerful, but also targeted toward achieving specific, measurable outcomes in challenging conditions.

Conclusion: Tom: So, we've been diving deep into the technical details of SAT-CTS, but now it's time to wrap up and really look at what this paper means for us in the real world. Jane, can you give us a quick recap on what this title actually tells us about the research?

Jane: Absolutely. This paper, "Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits," is fundamentally about figuring out how to manage beam and data rate assignments in multi-user millimeter-wave systems without having perfect channel information. Essentially, it introduces a new learning approach called SAT-CTS that focuses on hitting a specific service goal rather than just trying to achieve the highest possible throughput.

Lu: That's the big conceptual shift, Jane; moving from pure maximization to satisfying a target performance level is what opens up so many creative possibilities for how AI agents can behave in complex resource allocation scenarios.

Meng: From an engineering standpoint, this tells me that we don't always need perfect channel state information to make very good decisions in high-frequency wireless systems, which simplifies deployment considerably.

Lalam: I see a huge cultural implication here; it suggests that we can design AI systems that are inherently goal-oriented and resilient, which is a much more valuable quality for widespread use across various sectors.

Tom: Exactly! When we look at the authors and the work they did, what's their main contribution to this conversation?

Jane: The main contribution is proving that this satisficing approach works reliably in complex combinatorial settings, giving us concrete regret bounds—meaning we know exactly how long the learning process will take based on whether our target is achievable or not.

Lu: Their ability to provide those finite-time regret guarantees for both realizable and non-realizable targets shows a deep theoretical understanding of how these semi-bandit problems behave under different constraints.

Meng: I'm particularly interested in the practical impact of those bounds; knowing that we can predict the convergence time under various network conditions is what makes deploying this kind of AI much more feasible for real infrastructure.

Lalam: For me, it means our future AI models won't just be about brute-force optimization; they’ll be about intelligently managing constraints to deliver reliable service consistently across a network.

Tom: It sounds like the implication here is that we can build communication systems that are much more robust because they don't require perfect sensing capability constantly, and this research gives us the mathematical tools to guarantee those results. Where do you think this leads us next?

Bilkent University

cs.LG, cs.SY, eess.SY, stat.ML

Submitted: 2026-04-16

Updated: 2026-10-01

Code: https://github.com/Bilkent-CYBORG/Satisficing-with-Binary-Feedback-for-Combinatorial-Beam-Alignment

Importance score: 88/100

The gist: Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits addresses the challenge of efficiently learning optimal beam and data rate assignments in multi-user millimeter-wave

Key concepts

Combinatorial Semi-Bandit (CMAB): This models the problem where an agent must choose between multiple options (arms) to maximize its reward. In this context, the agent decides which beam and rate combination to use for a specific user based on feedback it receives, like whether a connection was successful or not.
Satisficing Throughput Threshold ($ au_r$): Instead of trying to find the absolute best possible throughput, this sets a minimum acceptable target. The algorithm tries to find beam and rate assignments that achieve at least this threshold. It balances exploration with exploitation by prioritizing configurations that meet this required performance level.
SAT-CTS Algorithm: This is the proposed learning policy. It combines conservative confidence estimates (lower confidence bounds) with sampling techniques (Thompson Sampling). Its main feature is a decision gate that checks if an option meets the target throughput before committing to it, steering the learning process toward satisfying service goals.
Regret Bounds: Regret measures how much worse an algorithm performs compared to the best possible outcome over time. The paper provides two types: finite-time bounds when a target is achievable, and polylogarithmic bounds when the target is impossible to meet.

Terminology

Regret — 148× in this paper · explained in 3 episodes
Adaptation — 22× in this paper · explained in 1 episode
Alignment — 19× in this paper · explained in 1 episode
Steering — 5× in this paper · explained in 2 episodes
Channel State Information — 4× in this paper
Combinatorial Thompson Sampling — 4× in this paper
AI Agents — 3× in this paper · explained in 2 episodes
Core — 2× in this paper · explained in 2 episodes
Robustness — 2× in this paper · explained in 5 episodes
Accuracy — 1× in this paper · explained in 1 episode
Active Learning — 1× in this paper · explained in 6 episodes
Alignment Problem — 1× in this paper · explained in 1 episode
Benchmark — 1× in this paper · explained in 2 episodes
Contextual Bandits — 1× in this paper · explained in 3 episodes
Decoupling — 1× in this paper · explained in 2 episodes
Gap-Dependent Regret — 1× in this paper · explained in 2 episodes
Multi-objective Optimization — 1× in this paper · explained in 4 episodes
Multiple Input Single Output — 1× in this paper
Sparsity — 1× in this paper · explained in 4 episodes

Summary

Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits addresses the challenge of efficiently learning optimal beam and data rate assignments in multi-user millimeter-wave Massive MIMO systems without explicit Channel State Information (CSI). This work introduces SAT-CTS, a lightweight, thresholdaware policy that blends conservative confidence estimates with posterior sampling to steer learning toward meeting a specified service goal (satisficing throughput threshold) rather than merely maximizing throughput. The main theoretical contribution provides the first finite-time regret bounds for combinatorial semi-bandits with a satisficing objective, showing bounded cumulative satisficing regret when the target is realizable and polylogarithmic standard regret when it is non-realizable.

How it works

The problem is modeled as a combinatorial semi-bandit (CMAB) where the learner coordinates beam and rate assignments based solely on ACK/NACK feedback from User Equipments (UEs). The decision-making process involves an exploration–exploitation tradeoff, where the learner must explore different beam-rate pairs to learn which ones perform well while exploiting known good configurations to satisfy throughput requirements. The system defines a set of base arms as tuples of (UE, BS–beam pair, rate), and a set of super arms as the complete assignment decisions for all users.

The SAT-CTS algorithm operates in three main phases:

A deterministic initialization phase lasting up to T0 rounds where all base arms are played at least once.
A decision gate that evaluates lower confidence bounds (LCB) and empirical means (MEAN) against the satisficing threshold, casting a selection based on which index meets or exceeds the target average throughput, τr.
A committed CTS phase: if neither gate fires, the algorithm resets Beta priors to Beta(1, 1) and runs standard Combinatorial Thompson Sampling (CTS) for exactly 2i rounds without rechecking the gate.

Key Theoretical Contributions and Regret Analysis

The paper provides two primary regret guarantees based on whether the satisficing threshold τr is realizable:

(Realizable Target)

When τr is realizable, SAT-CTS incurs a horizon-free upper bound on expected cumulative satisficing regret that depends only on system parameters. The total expected cumulative satisficing regret E[R S(T)] is bounded by a finite constant independent of T, decomposed into initialization cost (Rinit), confidence failure cost (Rconf), mean phase cost (RMEAN), and CTS phase cost (RCTs).

(Non-Realizable Target)

When τr is non-realizable, the algorithm reduces to standard combinatorial Thompson sampling after a finite transient phase. The standard regret of SAT-CTS is shown to be polylogarithmic in T, specifically E[R std(T)] = O((log T) 2). This is achieved because the regret after the transient phase is governed by the sum of regrets from restarted CTS rounds, yielding an O((log T) 2) bound.

Performance and Fairness in Experiments

Experiments conducted using a DeepMIMO simulator on a multi-BS, multi-UE MISO system demonstrate that SAT-CTS consistently reduces satisficing regret and maintains competitive standard regret while achieving favorable average throughput and fairness across users. The results show that SAT-CTS outperforms standard CTS [16] and combinatorial upper confidence bound (CUCB) [15] baselines in terms of satisficing regret. Furthermore, fairness metrics, such as Jain’s Fairness Index J(T) and the sum of log utilities, indicate that SAT-CTS variants achieve substantially higher fairness than classical baselines throughout the horizon.

Scalability and Robustness

The study evaluates how SAT-CTS scales with system parameters:

(Beam Codebook Size)

SAT-CTS remains robust as the beam codebook size grows, benefiting from quicker adaptation and improved SNR due to narrower beams.

(Number of BSs)

When expanding to three BSs, SAT-CTS achieves the lowest regret and improves substantially over CTS, with the SAT-CTS/CTS ratio dropping to 0.693.

(Number of Users)

Increasing the number of users can improve learning efficiency because the learner receives more semi-bandit feedback per round, as long as beam contention remains limited.

Conclusion

SAT-CTS is proposed as a scalable, regret-optimal algorithm for mmWave systems in the absence of CSI. It provides provable performance guarantees by rigorously analyzing its behavior under both realizable and non-realizable target scenarios, demonstrating that feedback-efficient learning can equitably allocate beams and rates to meet QoS targets without requiring channel state knowledge. Future work is suggested to extend these formulations to contextual combinatorial bandits that exploit side information like geometry or mobility.

Improvements for AI systems

As a fastidious researcher, I have analyzed the provided paper, Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits (SAT-CTS). The core innovation lies in applying a satisficing objective—aiming for a minimum required throughput threshold—to the traditionally maximizer-based combinatorial bandit framework for joint beam and rate adaptation in multi-user mmWave systems without Channel State Information (CSI).

The primary improvements this research enables are centered around developing highly robust, feedback-efficient resource allocation algorithms.

Here are the specific improvements and what the resulting AI system can achieve:

) 1. Development of Threshold-Aware Policy Learning

The paper introduces the SAT-CTS algorithm, which explicitly incorporates a satisficing throughput threshold (τr) as an input, moving beyond simple maximization toward meeting a service quality goal.

The improved AI system will learn to satisfy hard Quality of Service (QoS) constraints rather than just chasing theoretical maximum rates.

) 2. Finite-Time Regret Guarantees for Realizable Targets

The authors provide the first finite-time regret bounds for combinatorial semi-bandits with a satisficing objective.

The system will exhibit a guaranteed horizon-free upper bound on cumulative satisficing regret when the target is achievable, meaning it converges to meeting the QoS goal within a predictable time frame, regardless of how long the communication lasts (T).

) 3. Robust Performance Under Non-Realizable Targets

The analysis demonstrates that if the target throughput (τr) is impossible to achieve (non-realizable), the algorithm degrades gracefully, reducing to standard Combinatorial Thompson Sampling (CTS) after a finite transient phase.

The AI system will maintain competitive performance even when ideal conditions are unattainable, showing superior robustness compared to purely optimistic exploration methods like CUCB, which suffer from significantly higher regret in this scenario.

) 4. Enhanced Fairness in Resource Allocation

The experimental results show that SAT-CTS consistently maintains a higher Jain's Fairness Index and Sum of Log Utilities compared to baselines (CTS, CUCB), especially over longer horizons.

The improved AI system will allocate beams and data rates more equitably across all users, ensuring no single user is severely starved of resources while others are saturated.

) 5. Scalable Performance in Complex mmWave Environments

The algorithm proves its scalability across increasing network complexity (more BSs, more UEs, larger beam codebooks).

The AI system will perform optimally in dense urban or large-scale mmWave deployments by effectively utilizing the increased spatial diversity and assignment flexibility afforded by a larger network structure.

) 6. Feedback Efficiency and CSI Independence

The entire framework operates solely on binary ACK/NACK feedback, requiring no explicit Channel State Information (CSI).

The AI system will be highly practical for real-world mmWave networks where accurate CSI acquisition is expensive or impossible due to blockage, mobility, or hardware constraints.

In summary, the improved AI system will function as a Goal-Oriented Resource Allocator for mmWave networks. It doesn't just find the fastest possible connection; it finds the most reliable and fair set of beam and rate assignments that ensures every user meets a pre-defined minimum quality standard (τr), while providing mathematically rigorous guarantees on how quickly it will achieve that goal.