Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits
Bilkent 大學研究團隊提出 SAT-CTS 演算法，捨棄傳統通道狀態估測，僅靠二元回饋即可讓毫米波網路快速達到 2.5 Gbps 的平均吞吐量門檻。
- 捨棄高成本的 CSI 估測，改採輕量級 ACK/NACK 二元回饋進行波束與傳輸速率動態分配。
- 引入「滿意度閾值」概念，解決傳統 MAB 演算法為追求全局最佳解而導致初期網路不穩的問題。
- 首創組合半海盜問題的有限時間遺憾邊界證明，在非可實現目標下依然具備 O((log T)²) 的效能保證。
毫米波（mmWave）通訊雖然能提供超高頻寬，但其高度定向的波束極易受到實體阻擋，傳統依賴精確通道狀態資訊（CSI）的波束對齊方式成本過高且容易失效。Bilkent 大學研究團隊提出了一種名為 SAT-CTS 的機器學習演算法，直接跳過 CSI 估測，僅透過終端設備回傳的二元 ACK/NACK 訊號，就能確保每個用戶端達到例如 2.5 Gbits/sec 的平均吞吐量門檻，為無基地台狀態感知的波束配置建立全新數學模型。
毫米波通訊的波束對齊難題與無 CSI 挑戰
毫米波技術被視為下一代無線網路（如 6G）的基石，主要用於應對行動數據需求的爆炸性增長，以及支援互動式擴增實境與超高畫質串流等需要極大頻寬的應用。透過利用大量未充分使用的頻譜，毫米波能實現前所未有的峰值數據速率。然而，毫米波獨特的傳播特性，包含高路徑損耗、易受物理阻擋以及極強的方向性，為系統帶來了根本性的限制。
為了克服嚴重的路徑損耗，基地台（BS）與使用者設備（UE）必須使用高度定向的窄波束進行通訊。在傳統架構下，系統需要獲取精確的 CSI（通道狀態資訊） 來對齊這些波束。但在配備龐大天線陣列的毫米波系統中，進行通道探測（Channel Sounding）的成本極高；加上使用者的移動性與環境遮蔽，會迅速讓既有的 CSI 估算失效，迫使系統頻繁重新訓練，進而產生巨大的傳輸開銷與延遲。
研究團隊將目光轉向「無 CSI 的波束自適應（Beam Adaptation without CSI）」技術。發射端完全避開顯式的通道估測，轉而依賴最輕量化的鏈路層回饋。在此架構下，ACK/NACK 回饋提供了一個可靠的二元訊號，用以指示當前的波束與速率配置是否能在當下的傳播條件下順利傳送封包。系統僅需透過這個二元訊號進行迭代更新，就能隱式追蹤優質的波束方向，徹底擺脫獲取 CSI 的重擔。
放棄完美極大值：多武裝海盜演算法的滿意度轉向
將波束與傳輸速率分配模型化後，這本質上是一個典型的序列決策問題。決策系統（Learner）必須在「探索（Exploration）」未知的波束速率組合，以及「利用（Exploitation）」已知表現良好的配置之間取得平衡。學界通常使用 MAB（多武裝海盜問題，Multi-Armed Bandit） 演算法來處理這類探索與利用的權衡。
過去已有大量 MAB 演算法被提出，用於在指數級增長的組合配置中尋找「最佳超級臂（Best Super-arm）」。然而，這些傳統方法的設計初衷多半是追求長期的全局最佳化。在實際的通訊應用中，這會導致系統過度探索次佳配置，造成演算法收斂緩慢。在通訊初期的數個回合內，使用者往往會經歷低落的網路可靠度與吞吐量。
為了改善此缺陷，研究團隊引入了經濟學家 Herbert Simon 的「有限理性（Bounded-rationality）」概念，將重點從「尋找全局最大值」轉移到「尋找夠好的配置」。他們提出將問題框架改為滿足型組合多武裝海盜問題（Satisficing CMAB），並設定一個平均吞吐量門檻 $\tau_r$（例如每時槽 2.5 Gbps）。演算法的目標不再是無止盡地尋找最高網速，而是以最少的樣本數據，迅速達到並維持這個令使用者滿意的服務品質目標。
SAT-CTS 演算法設計與輕量化二元回饋機制
團隊提出的 SAT-CTS（滿足型組合湯普森取樣，Satisficing Combinatorial Thompson Sampling） 演算法，是一套輕量級且具備閾值感知的分配策略。演算法針對每一個「基地台-波束-速率」組合（Base Arm），維護一組共享的計數器與 Beta 機率分佈模型，用來推估該組合的傳輸成功機率。
在每一個時間槽的開頭，SAT-CTS 會計算每個組合的經驗平均值與下界置信區間（LCB），並將這些數值輸入分配預言機（如匈牙利演算法）中進行決策。系統會優先採用期望值超過 $\tau_r$ 門檻的配置，直接將波束與對應的調變編碼策略（MCS）指派給使用者設備。傳輸完成後，基地台僅需回收 1（ACK，成功）或 0（NACK，斷線）的二元訊號來更新系統。
如果目前沒有任何配置能穩定滿足 $\tau_r$ 門檻，SAT-CTS 會進入一個「承諾型 CTS 階段（Committed CTS phase）」。在此階段，演算法會將所有 Beta 先驗機率重置為 Beta(1,1)，並強制執行純粹的湯普森取樣達 $2^i$ 個回合。這種分段且承諾式的設計，確保了每一次探索階段都在明確的時間跨度內進行，並擁有乾淨的先驗數據，為後續嚴格的數學遺憾分析奠定了基礎。
首創理論極限突破：滿足型遺憾與標準遺憾雙保證
本研究最具突破性的學術貢獻，在於提出了首個針對「滿足型目標組合半海盜問題」的有限時間遺憾邊界（Finite-time regret bounds）。研究人員定義了累積滿足型遺憾（Cumulative Satisficing Regret），用來衡量系統表現低於 $\tau_r$ 門檻市所產生的效能落差，並針對兩種情境給出了嚴謹的數學證明。
第一種情境是「目標可實現（Realizable）」，意即當前的實體通道環境的確存在某種配置能穩定超越 $\tau_r$。數學證明顯示，在此條件下，SAT-CTS 演算法的期望累積滿足型遺憾會被一個與時間無關的常數（Time-independent constant）嚴格限制。這代表演算法只要經過短暫的學習期，就能徹底鎖定達標的波束，之後不論運行多久，都不會再產生額外的遺憾值。
第二種情境是「目標非可實現（Non-realizable）」，也就是使用者設定的 $\tau_r$ 過高，無論怎麼調整都無法達標。演算法在經歷有限的預期過渡期後，會自動退化回標準的 CTS 模式，並致力於逼近系統的最大物理極限。在此情境下，SAT-CTS 的標準遺憾值增長速度被證明為 $O((\log T)^2)$。這項雙軌保證確保了演算法在未知的網路環境中，無論目標設定是否合理，都能展現出最佳的適應力與數學最佳性。
DeepMIMO 模擬器中的動態通道與跨用戶公平性
為了驗證理論模型的實用性，研究團隊在配備 DeepMIMO 模擬器的多基地台、多使用者 MISO 系統中進行了實驗。該模擬器能生成符合現實物理條件的稀疏多徑通道向量（Sparse multipath channels），並採用擬靜態（Quasi-static）假設，即通道在單一時間槽內保持穩定，但在不同時間槽之間會發生動態變化。
實驗數據證實，由於具備明確的滿意度門檻，SAT-CTS 在降低「滿足型遺憾」方面的表現，始終優於標準的組合湯普森取樣（CTS）與組合信心上限（CUCB）等傳統基準演算法。它避免了因持續追求微小極大值而導致的波束頻繁切換。
在實際部署考量上，這種反饋效率極高的學習機制展現了優異的跨使用者公平性。即使在缺乏任何通道狀態知識的前提下，SAT-CTS 仍能為處於不同物理位置、面臨不同遮蔽條件的使用者，均衡地分配波束與速率資源，確保整體網路的服務品質（QoS）達標，為超低延遲控制頻道的應用提供了高度可行的實作藍圖。
當演算法放棄追求全局最佳解，轉而鎖定滿足服務品質的明確門檻時，就能在無需高昂探測成本下，極大化毫米波網路的早期吞吐量。