基于多智能體強化學習的動態頻譜分配方法綜述

宋 波, 葉 偉, 孟祥輝

(1.航天工程大學電子與光學工程系, 北京 101416; 2.中國人民解放軍95801部隊, 北京 100076)

0 引 言

近年來,5G移動通信技術獲得迅速發展和應用,該技術在物聯網、車聯網中具有非常廣泛的應用前景,因此導致了無線電設備數量的快速增長和對頻譜需求的大幅增加。目前的頻譜管理方式仍然以靜態分配為主,將頻譜進行劃分后分配給固定的授權用戶,這種已經延續了上百年的頻譜管理體制已經無法繼續滿足網絡容量的擴增對頻譜的需求。

1998年Mitola等人提出了認知無線電和認知循環概念[1],引入了一種自動感知外部無線環境,自主決策并機會式接入空閑頻譜的新型無線電技術。Haykin等人對認知無線電的構成、關鍵技術和應用前景的進一步研究,完善了認知循環定義[2]。IEEE、FCC和ITU等機構均對認知無線電給予了充分重視,進行了廣泛研究,給出了定義并制定了相關標準,如IEEE 802.22無線地域網標準、IEEE 1900.7動態頻譜接入網絡標準等。

動態頻譜分配技術作為認知無線電的關鍵技術,可以大幅提高對頻譜資源的利用效率,改善目前的頻譜資源在開發利用中存在的不均衡的現象,因此在業界引起了廣泛關注與深入研究。目前來看,基于非智能技術的動態頻譜分配算法的研究根據理論基礎可以分為以下3個方向:基于圖論、博弈論和交易理論的方法。其中基于圖論的動態頻譜分配算法把問題抽象為圖論中的頂點著色問題,將各認知無線電用戶及其可用信道作為圖中的頂點,當用戶間不能共用同一信道時,以邊進行連接,將頻譜分配過程抽象為對這種被稱為干擾圖的各頂點的逐一著色過程。

干擾圖的頂點著色是一個非確定多項式難題問題,難以得到最優解,Peng等人提出了尋求次優解的啟發式算法[3],該算法需要事先設定不同應用環境以對不同節點設置優先級,對優先級高的節點優先分配頻譜,當信道較多時計算復雜度較高,收斂速度慢。廖楚林等人提出了一種分解復雜干擾圖為簡單圖的方法,將對節點的依次染色轉化為簡單圖的并行染色[4],改善了順序染色帶來的時間開銷大的問題。郝丹丹等人提出了一種基于信道回報的異構頻譜分配算法,在首次分配時以貪婪方法分配信道減小算法迭代次數[5]。Wang等提出了一種列表著色算法,每一輪隨機分配信道后在列表中刪去該信道,提升了收斂速度[6]。劉鵬等提出了基于量子遺傳和圖著色方法的動態頻譜分配算法[7],將小生境技術與量子遺傳算法相結合,可以解決算法陷入局部最優問題,通過動態調整旋轉門并提高染色體閾值,提高了整體收斂速度。何建強等人提出了一種基于顏色敏感圖著色的改進方法,以最大化帶寬為目標函數,在二次分配時采取最大公平準則,在性能上優于單一顏色敏感圖著色算法和最大公平準則算法[8]。

利用博弈論分析與解決多個認知無線電用戶競爭頻譜獲得最大頻譜利用效率的動態頻譜分配算法取得了很好的效果。Neel等人第一次分析了博弈論在認知無線電系統中的應用前景,推導并提出了在完全潛博弈模型下,動態頻譜分配將最終收斂到納什均衡[9],之后分別分析了利用重復博弈、短視博弈、S-模博弈、潛博弈的認知無線電模型的收斂性[10]。滕志軍等人提出了一種基于潛博弈的分布式算法,通過仿真驗證了收斂性[11]。Cao等人提出了一種分布式局部議價算法,改進了一般基于博弈論的頻譜分配納什均衡在環境拓撲結構發生改變時必須重新計算的不足,并根據Feed Poverty策略提升了算法的公平性[12],但假設了合作博弈的前提,而一般情況下,各用戶間是非合作關系。Etkin等人針對非合作博弈下難以收斂到納什均衡的問題,以重復博弈的方法證明了其長期有效性[13]。徐昌彪等人提出了一種改進定價函數的博弈論動態頻譜分配模型,并分別在靜態博弈與動態博弈下進行了驗證[14]。

除了基于圖論和博弈論的方法外,基于頻譜市場理論和拍賣機制的動態頻譜分配算法也發展出了不少成果。基于拍賣理論的動態頻譜分配方法將活躍認知用戶視作拍賣競標者,將空閑頻譜認知用戶視作拍賣出售者,基站作為拍賣交易方協調競標與出售過程[15]。Chen等人提出了一種基于簡化VGG(Vickrey-Clark-Groves)模型的頻譜拍賣算法,根據累積參與與成功接入次數提出了一種基于首次定價封閉拍賣的新叫價方法,降低了頻譜切換時的通信中斷并提高了頻譜分配的公平性[16]。Zhou等人提出了一種可信雙頻譜拍賣模型,解決了頻譜重復利用和雙拍賣中的不可信問題[17]。Wang等人考慮以最大化頻譜利用率作為目標函數,引入近似誠信概念,兼顧頻譜利用率與誠信,可以最大化頻譜拍賣者利潤[18]。基于拍賣理論的方法整體上雖然能在限定主次用戶條件下收斂到最大化頻譜利用效率,但缺乏靈活性。

上述算法雖然可以解決動態頻譜分配中的頻譜利用與用戶通信效能和網絡通信效能間的約束與優化問題,但存在靈活性差,收斂速度慢和無法滿足分布式條件下需求的問題。這種中心化的分配方法對控制中心與用戶間的通信條件和頻譜感知的精確性要求比較高,在實際中實現難度大。

隨著近年來強化學習等機器學習研究領域的快速發展,基于機器學習算法的智能動態頻譜分配方法逐漸吸引了越來越多研究者的注意。

強化學習(reinforcement learning, RL)是為解決馬爾可夫決策過程(Markov decision process, MDP)策略優化問題發展出的機器學習算法分支,用于解決具有馬爾可夫性的動態環境序貫決策問題。

近年來,在多智能體系統問題中引入RL后獲得了很好的效果,多智能體強化學習(multi-agent reinforcement learning, MARL)方法逐漸成為機器學習與群體智能的研究熱點,而多認知用戶網絡在分布式決策模式下的動態頻譜分配問題可以視為多個智能體的分布式馬爾可夫決策過程。這種分布式群體智能方法在動態頻譜分配問題中的應用前景十分廣闊。

下面首先對RL和MARL的相關理論基礎進行簡要介紹并對發展現狀進行梳理;對近年來基于MARL的動態頻譜分配方法方面的相關工作進行了歸納與分析;最后對當前算法中存在的關鍵問題與解決思路進行概括與展望。

1 強化學習

認知環的感知與決策過程如圖1所示,基于圖論的頻譜分配模型如圖2所示。

圖1 認知環的感知與決策過程

圖2 基于圖論的頻譜分配模型

RL是一種針對MDP長期收益最大化的機器學習算法。而MDP可以這樣描述:如果環境當前狀態st,智能體觀測到該狀態后,根據策略π(at|st)選取動作at,環境根據狀態轉移概率p(st+1|st,at)∈(0,1)進入下一狀態st+1,智能體根據動作好壞獲得環境給予的即時獎勵rt,由于智能體做出決策只基于st,與之前的所有狀態s0,s1,…,st-1無關,因此(s,a,r)具有馬爾可夫鏈性質,MDP如圖3所示。

圖3 MDP示意圖

根據貝爾曼方程,狀態st的價值函數v(st)為

(1)

式中:{at}表示t時刻所有動作的集合；{st+1}表示t+1時刻所有狀態的集合；γ∈(0,1)為折扣因子,表示未來狀態下的獎勵對當前策略的影響程度。

為表征動作a的好壞,定義動作狀態價值函數(也稱為Q函數)q(st,at)為

q(st,at)=

(2)

式中：{at+1}表示t+1時刻所有動作的集合。

根據是否學習p(st+1|st,at)與rt,可以將強化學習方法分為基于模型的RL(model-based RL, MBRL)方法和與模型無關的RL(model-free RL, MFRL)方法兩類。其中,MFRL已成為當前的主流方向。下面分別對基于值函數和策略梯度的MFRL算法與MBRL算法進行介紹。

1.1 基于值函數的強化學習方法

1.1.1 Q-學習方法

Q-學習是一種經典的時序差分RL算法,Q-學習將當前時刻的回報與下一時刻的狀態Q函數的最大值作為當前狀態最優策略的Q值估計,以其與當前狀態下Q函數的誤差對當前狀態下的Q函數進行更新:

(3)

式(3)的更新過程如圖4所示。

圖4 Q-學習更新過程

Q-學習的訓練過程中需要建立并初始化一個|S|×|A|(S為環境狀態空間)的Q值表格,根據式(3)迭代更新該表格,待其收斂后,最佳策略π*(st|at)為

(4)

表格式Q-學習無法應用于狀態空間和動作空間都很大或者動作空間連續或不存在終止狀態的問題中,而深度Q-學習能有效解決這些問題。

1.1.2 深度Q-學習方法

2015年,一種結合了深度神經網絡擬合能力的Q函數擬合方法——深度Q-學習(deep Q-learning, DQL)被Mnih等人提出[19],大幅提升了RL在復雜環境下的學習能力,引起了廣泛關注。

在文獻[19]中,作者提出的深度Q-網絡(deep Q-network, DQN)將Atari游戲畫面直接輸入卷積神經網絡進行狀態特征提取,利用2層全連接層進行Q函數的擬合，DQN結構如圖5所示。同時提出了經驗回放、隨機采樣、批次訓練等技術減小樣本間的相關以加快DQN訓練速度,DQN是一種端到端學習的RL算法。

圖5 深度Q-網絡

由于在Q-學習和DQL中,Q值的估計直接利用下一狀態最優Q值,造成了對Q值的過高估計。因此,Hasselt等人提出了一種雙Q-學習方法以改善對Q值的過高估計造成的訓練波動問題[20],并將其與DQN結合,提出了一種改進后的深度雙Q網絡(double deep Q-network, DDQN)算法[21],在估計當前Q值時用相同結構,但參數不同的另一個DQN(稱為目標網絡)代替,用行為網絡與環境交互,有效改善了DQN訓練不穩定的問題。Wang等人將Q函數分解為狀態價值函數V與各動作的優勢函數A(ai)的組合,提高了Q函數的表示能力,在Atari游戲環境中獲得了超過DQN的表現[22]。Fortunato等人為提高DQL算法的策略探索能力,提出了一種在DQN參數中加入隨機噪聲的Noisy Net算法[23],通過在神經網絡超參數中隨機加噪的方法提高了DQN在價值函數表示的多樣性與隨機性。Hessel等人將上述改進進行了有效結合并全部集中在了所提出的Rainbow算法中[24],成為DQL的發展里程碑與集大成者。

DQL相比于表格式Q-學習方法解決了在連續狀態空間下的適用性,但仍無法有效解決連續動作空間如機械手臂的連續控制問題。Gu等人提出的歸一化優勢函數(normalized advantage functions, NAF)算法[25]第一次將Q-學習算法完整的拓展到了連續控制問題中。NAF采用了與競爭DQN[22]類似的思路,將Q函數分解為優勢函數與狀態價值函數的組合,將狀態輸入神經網絡中輸出動作并作為Q-學習方法中的最大價值動作,以被評估動作與Q函數最優值的差構建一個二次型作為優勢函數,利用經驗回放、隨機采樣與批次訓練等DQN的經典技巧進行訓練。NAF算法的提出擴展了DQN的應用范圍。

下面對MFRL的另一條發展路徑——基于策略梯度的RL方法進行簡要介紹。

1.2 基于策略梯度的強化學習方法

1.2.1 隨機策略梯度算法

相比于值函數方法通過搜索Q值最大的動作獲得最優策略,策略梯度方法直接通過訓練優化策略函數π(a|s),同時由于策略函數是動作的概率分布,天然地保留了一定的探索性,也有避免陷入局部最優的優勢。

如果智能體在參數為ω的策略函數πω(a|s)下對環境進行探索與采樣,軌跡為T,在使得T的累積獎勵最大的優化目標下,可以得到目標函數ytarget(ω)為

(5)

式中:r(T)為軌跡T下的獎勵函數。

可利用梯度上升法求上述目標函數的最大值,對式(5)求導可得

(6)

式(5)被稱為策略梯度(policy gradient, PG),在離散動作空間問題中,將式(6)中求數學期望的形式變換一下,可得

(7)

同時可以利用優勢函數Aπ,γ:

Aπ,γ=r+γ·v(st+1)-v(st)

(8)

代替式(7)中的累積獎勵,可以顯著改善訓練中策略梯度的波動。

Konda等人提出的行動器—評判器(actor-critic, AC)算法[26]中利用線性擬合算法擬合πω(a|s)、價值函數v(s)與優勢函數Aπ,γ,以優勢函數Aπ,γ作為損失函數進行訓練;Mnih等人提出了一種用深度神經網絡分別擬合πω(a|s)與v(s),并利用多線程采樣交互進行訓練的異步優勢AC(asynchronous advantage AC, A3C)算法[27],有效提升了訓練速度。

這些基于策略梯度的AC算法對策略的訓練需要基于當前策略與環境的交互數據支撐,這種同策略方法存在策略函數方差大、訓練不夠穩定的問題。因此,Schulman等從策略更新約束的角度提出了改進方法:利用更新前后的策略分布KL散度作為約束項以提高收斂穩定性,稱為置信域策略優化(trust region policy optimization, TRPO)算法[28],但該算法每次更新需要計算費舍爾信息矩陣的逆,計算復雜度比較高,后Wu等人提出用Kronecker分解來降低費舍爾信息矩陣求逆運算的復雜度[29];Schulman等人后來又提出一種TRPO算法的改進算法:近端策略優化(proximal policy optimization, PPO)算法,PPO算法通過限制更新前后策略分布比率的范圍代替TRPO的復雜優化方法,使得計算復雜度大幅降低,但實際效果不低于TRPO算法[30]。

為改善隨機策略梯度方法基于同策略更新,無法充分利用歷史交互數據的缺陷,Wang等人提出了一種異策略更新的AC算法——經驗回放AC算法(actor-critic experience replay, ACER)[31],利用了Munos等人提出的Retrace算法[32]使用異策略經驗緩存更新當前策略的Q函數,利用重要性采樣方法進行策略梯度的更新;同時,為解決策略梯度波動的問題,提出了一種類似于TRPO算法的KL散度約束以降低策略梯度方差,但由于只用了KL散度的一階導,計算復雜度上比TRPO算法低。

由于A3C、TRPO、PPO等隨機策略梯度算法不能利用歷史數據進行學習,而ACER算法雖然利用了重要性采樣等手段具備了異策略更新的能力,但DQN中的隨機采樣、批次訓練等可以提高訓練效率的手段難以應用到Critic的更新上。確定策略梯度算法可以很好地解決這個問題。

1.2.2 確定策略梯度算法

Silver等人提出一種使得AC算法中策略梯度更新與價值函數更新解耦,從而可以利用隨機采樣和批次訓練加快價值函數訓練的深度確定性策略梯度(deep deterministic policy gradient, DDPG)方法,有效提升了AC算法的收斂性[33]。隨機策略梯度算法中策略網絡輸出動作空間的概率分布,根據分布采樣得到具體動作,DDPG算法則直接輸出確定動作,如果以參數為β的深度神經網絡μβ(s)擬合該函數,以參數為θ的深度神經網絡Qθ(s,a)擬合價值函數,則目標函數可以這樣定義:

(9)

(10)

式中:ytarget(θ)為值函數網絡更新的目標函數;ytarget(β)為策略網絡更新的目標函數。

作者證明了Qθ(s,a)不必遵從固定策略,這意味著可以通過經驗緩存機制更有效率的訓練價值函數,但基于TD-error的更新容易過高估計Q函數。

為解決DDPG過高估計Q函數的問題,Fujimoto等人提出的雙延遲深度確定性策略梯度算法(twin delayed deep deterministic poli-cy gradient algorithm, TD3)[34]進行了如下改進:① 同時訓練兩個Q函數,選擇輸出較小的值;② 延遲更新策略網絡,減小策略更新的波動;③ 在策略網絡輸出中加噪聲,以平滑Q函數的估計誤差。

DDPG與TD3雖然實現了連續動作問題的異策略學習,但由于其采用了確定性的動作策略網絡,訓練過程對超參數(如學習率α等)的調整比較敏感,而且確定性策略輸出帶來了對環境探索性不足的問題。因此,Haarnoja等人提出通過在Critic部分的Q函數中加入熵約束的軟AC(soft AC, SAC)算法,學習過程中不但要最大化Q函數,同時要最大化動作的熵,以增強動作的探索性[35]。

1.3 基于模型的強化學習方法

RL的經典算法動態規劃(dynamic programming, DP)以當前狀態為根節點,根據狀態轉移函數與策略函數建立未來狀態作為葉子節點的狀態轉移樹型結構,根據樹型結構計算每個狀態下的葉子節點(后續狀態)的期望累積回報,這是一種典型的MBRL方法。但這種方法在計算狀態的價值時需要遍歷所有以該狀態為根節點的所有葉子節點狀態,在狀態空間很大的問題上實現起來復雜度過高。

基于模型的Dyna算法框架首先由Sutton等人提出[36],是一種結合了MBRL和MFRL的算法。該算法中,首先初始化一個狀態轉移模型,根據當前狀態和動作輸出下一狀態和當前(s,a)下的獎勵;初始化Q函數。在與環境交互過程中,根據Q函數結合貪婪策略進行軌跡的更新,根據交互軌跡對Q函數和模型分別進行更新;同時隨機產生狀態與動作輸入模型后,利用模型輸出的下一狀態與獎勵對Q函數進行n次更新。Silver等人提出的Dyna-2算法[37]對Dyna算法進行了改進:該算法在每輪的更新中需要重新建立一個稱為瞬時記憶的Q′函數,利用Q′進行策略的選擇以產生交互軌跡,對模型與被稱為長期記憶的Q函數進行更新。

相比于Dyna算法每一次更新需要對環境進行完整的蒙特卡羅探索,蒙特卡羅樹搜索(Monte-Carlo tree search, MCTS)算法[38]首先通過隨機采樣動作后得到當前狀態為根節點的子節點,如果該子節點尚未被探索就將其加入蒙特卡羅樹中,之后在該節點后用模擬交互的方法直到得到終止狀態,根據模擬交互得到的終止狀態獲得的獎勵對該子節點處的總探索數及勝利數(以圍棋為例)信息進行更新,在之后對該節點的探索中以置信度上界(upper confidence bound, UCB)方法在此信息的基礎上增加隨機性并作為采樣的依據。

MBRL在AlphaGo[39]算法中大獲成功,在2016年AlphaGo以5∶0擊敗了歐洲圍棋冠軍樊麾,2017年以3∶0擊敗了專業9段棋手柯潔,在人工智能的研究中具有里程碑式的意義。該算法結合了MCTS與AC算法的優勢,首先利用人類專業棋手的對決棋譜和監督學習方法對策略網絡進行訓練,并開創性地采用了一種自博弈方法進一步對策略網絡進行提升,在MCTS的初始搜索中利用訓練好的策略網絡指導探索行為,避免了從零開始學習。

在其后續的改進版本AlphaZero中[40],進一步強化了自博弈方法的重要性,DeepMind團隊利用與AlphaGo的自博弈代替人類專業棋手的棋譜來監督訓練的方法大幅度提高了AlphaZero算法的訓練速度與效果,同樣利用MCTS方法進行策略搜索與狀態轉移模型的學習。

AlphaGo與AlphaZero算法的成功大大刺激了基于模型算法的研究熱度,但這種專門針對圍棋和象棋等棋類游戲的強化學習算法如何泛化在其他領域的問題中也被人們經常討論和質疑。而MuZero算法的提出[41]為這個問題的解決提出了一種前景非常廣闊的思路:通過環境轉移模型在建模時以隱藏狀態的形式進行表示與學習,在減小狀態空間復雜度的同時不以精確表示真實的環境狀態轉移為目的,而是以對策略提升的貢獻為評價指標,同時利用了MCTS方法以解決狀態空間過大的問題。該算法的提出把AlphaGo及后續改進的算法拓展到雅達利游戲測試環境中,在同MFRL和其他MBRL基線算法的對比中取得了最好的結果。

近年來,人們開始考慮利用離線采樣交互的軌跡代替智能體與環境交互利用試錯的方法進行強化學習,如模仿學習與結合了生成式對抗網絡(generative adversarial network, GAN)[42]思想的生成式對抗模仿學習(generative adversarial imitation learning, GAIL)[43]以及離線學習(offline reinforcement learning, ORL)[44]。這些方法立足于改善現存的強化學習算法在訓練過程中必須不斷重新與環境交互的過程,致力于解決利用離線的采樣數據進行強化學習訓練過程中存在的問題,也同樣是強化學習的熱點方向之一。

當強化學習應用在實際問題的解決中不可避免的遇到了在部分復雜控制問題中所遇到的維度災難問題,特別是在下文中提到的集中式MARL問題中隨著智能體個數的增加而出現的維度指數性增長。而分層強化學習在近年來由于其具有的分解復雜任務空間為子空間的特性,在解決狀態空間非常大的問題時相比于其他強化學習方法具有明顯的優勢,受到了研究者們的廣泛關注。分層強化學習中基于選項、基于分層抽象以及基于值函數分解[45]的思想已經部分應用于多智能體問題的解決中,特別是利用基于值函數分解的方法解決MARL方面已經涌現出了不少成果,是最近受到廣泛關注的熱點方向。

2 多智能體強化學習

MARL與單智能體RL所不同之處在于其要解決的是分布式部分可觀測MDP(decentralized partially observable MDP, Dec-POMDP)。Dec-POMDP可用一個元組〈N,S,A,R,T,γ,O〉來表示,其中N表示智能體集合;S表示環境全局狀態空間;A表示智能體聯合動作空間,動作向量a=[a1,a2,…,ai,…]∈A,其中ai代表智能體i的獨立動作;R表示當前狀態-動作對(s,a1,a2,…,ai,…)下的全局獎勵函數;T代表環境的狀態轉移函數T(s′|s,A)∈(0,1);γ為折扣因子;O為各時刻智能體部分觀測狀態向量[o1,o2,…,oi,…]。Dec-POMDP如圖6所示。

圖6 部分可觀測MDP

對于多智能體在環境中的學習過程,當采用中心化訓練時,以完全合作博弈來描述;當采用無中心化的完全競爭模式進行訓練時,以完全競爭博弈來描述;當采用無中心化的混合策略進行訓練時,即智能體間既競爭又合作時,以隨機博弈來描述[46]。

MARL的優化目標可以用一個納什均衡來表示:

(11)

MARL相比于單智能體強化學習的難點在于對每個智能體來說,其他智能體的策略優化過程構成了環境的一部分,因此對每個智能體來說,環境的狀態轉移概率是非平穩的,這就意味著如果不加限制地利用單智能體強化學習方法解決多智能體問題,會存在收斂困難的問題。

隨著近年來DQN、DDPG等深度強化學習算法的提出,吸收了這些算法優點的多智能體深度強化學習算法逐漸發展起來并取得了一系列成果。

按照MARL算法的訓練與決策方式,可以分為3種類型,即集中訓練集中執行、集中訓練分布執行與分布訓練分布執行模式[52]。

集中訓練集中執行模式下,通過一個中心訓練并控制所有智能體的行為。Sukhbaatar等人提出了一種CommNet算法和隱層信息池化共享的思想,利用深度神經網絡(deep neural network, DNN)的全連接性進行隱式的信息共享,同時利用平均池化方法可以適用于智能體數量變化的場景[53]。Peng等提出了一種BicNet算法,利用循環神經網絡(recurrent neural network, RNN)的記憶功能,依靠隱藏狀態hi在各智能體間共享信息[54]。

此類方法存在的問題主要是:隨著智能體數量的增加,聯合動作空間呈指數增長,導致了計算復雜度增加,訓練難度加大;同時也無法解決智能體信用分配避免“懶惰智能體”問題。

在分布訓練分布執行模式下,可分為基于獨立值函數的學習——獨立Q-學習(independent Q-learning, IQL)與基于AC結構的算法兩種。其中,Tan等人最早提出IQL方法[55],在同構智能體前提下,作者證明了IQL能收斂到團隊最優均衡策略;Littman等人提出的Team-Q算法能在確定環境條件下收斂,但如果環境是非平穩的則難以收斂[47];Matignon等人提出了一種滯后Q-學習算法[56],通過設置兩個不同的學習率因子調整價值函數的更新;基于此,Omidshafiei等人采用基于RNN的DQN代替了之前的表格學習[57],加入RNN結構的DQN具有記憶能力,能在一定程度上克服環境的非平穩性造成的難以訓練的問題。

基于AC結構的獨立學習算法有Perolat等人提出的虛構AC算法[58],該算法通過對行動器與評判器設置不同的更新延遲,以增加策略更新的穩定性。

分布訓練分布執行模式算法在無相互協作和全局信息的條件下進行獨立訓練存在的主要問題是訓練難度大,隨著智能體數量增加,收斂變得非常困難。

集中訓練分布執行結構下智能體間可以建立通信從而傳遞信息進行協調,由于深度強化學習的興起,智能體間可以利用DNN中的全連接層進行信息傳遞與融合,這方面具有代表性的算法有:Foerster等人提出的增強型智能體間學習(reinforced inter-agent learning, RIAL)與微分型智能體間學習(differential inter-agent learning, DIAL)[59],代表各智能體的DQN均以RNN構建并相互串聯,將并行決策架構改為串行決策架構,利用RNN的記憶功能對智能體間的動作進行學習與協調;Mao等人提出了一種基于AC架構的多智能體協作學習方法AC-CNet與A-CCNet[60],其中AC-CNet在行動器端建立通信網絡進行信息編碼與交換,A-CCNet則在評判器端進行信息編碼與共享;Lowe等人則提出了一種多智能體深度確定性策略梯度(multi-agent deep deterministic policy gradient, MADDPG)算法[61],在集中訓練下,利用全局狀態信息分別訓練各個智能體的值函數網絡,促進各智能體的策略網絡進行更新。

針對集中訓練的MARL算法無法有效解決智能體信用分配問題從而容易導致出現“懶惰智能體”現象的問題,Foerster等提出了一種反事實基線MARL(counterfactual baseline of MARL, COMA)算法[62],以非納什均衡策略下聯合Q函數的期望與納什均衡策略聯合Q函數得到反事實基線,依此評估單個智能體對總體收益所做貢獻;而Sunehag等人則結合分層強化學習中的值函數分解方法,將其應用在MARL的智能體信用評價上[63],論文中提出的分解方法建立了兩個強假設:① 聯合價值函數對獨立價值函數是單調的;② 聯合價值函數與獨立價值函數符合線性擬合的關系。這兩點假設在實際情況下均不容易滿足。因此,Rashid等人提出了一種改進的值函數分解方法——QMIX[64],該算法利用全連接層對聯合值函數與獨立值函數的關系進行非線性擬合,提升了分解的多樣化,增強了獨立值函數的表示能力。隨著多頭注意力機制[65]在深度學習研究中獲得越來越廣泛的關注,Yang等人提出了一種利用泰勒展開對聯合值函數進行非線性分解的Qatten算法,并利用多頭注意力機制網絡實現了不同階數系數的訓練,在多智能體實驗環境星際爭霸多智能體挑戰賽(starcraft multi-agent challenge, SMAC)中取得了很好的效果[66]。

MARL方法近年來獲得了迅速發展,雖然還存在理論支撐較少、算法的泛化性不足等問題,但在應用并解決自動駕駛[67]、集群規劃[68]、資源調度[69]等問題中已經顯示出較好的前景,在認知無線電與動態頻譜分配的研究者中也有越來越多的人將目光投入這一生機勃勃且前景廣闊的研究領域中,涌現出了一些開創性的工作,下面將進行簡要介紹。

3 基于多智能體強化學習的動態頻譜分配方法

基于傳統算法如圖染色法、博弈論與交易理論的方法需要利用中心控制實體對頻譜資源進行分配。這些方法存在的共性問題主要是頻譜分配控制中心與用戶間的通信需要占用大量資源,并且這些算法魯棒性差,環境發生變化時必須重新進行分配,因此時間開銷比較大,達不到實際應用中動態頻譜分配的實時性要求。

而利用MARL方法恰好能解決這樣的問題,各智能體可以根據對信道環境的部分觀測信息,根據訓練所得的經驗進行分布式決策并收斂到最優。當外部環境變化時,各個用戶(智能體)可以根據訓練好的策略迅速進行響應,并快速收斂。這種智能化的動態頻譜分配方法在對動態環境的適應性和重新分配頻譜的實時性上相比傳統的算法具有巨大的優勢。

3.1 基于Dec-POMDP的動態頻譜分配模型分析

動態頻譜分配模型的研究是研究動態分配算法的基礎,也是認知無線電理論研究的重要方面,Zhao等人[70]總結了動態頻譜分配的研究成果,將動態頻譜分配模型總結為專用模型、開放共享模型和分層接入模型3種,其中專用模型分為頻譜產權模型與動態專有模型;分層接入模型分為頻譜下墊接入模型與機會式頻譜接入模型兩種。動態頻譜分配模型分類如圖7所示。

圖7 動態頻譜分配模型

其中頻譜產權模型下各用戶把擁有的頻譜作為可自由支配的財產,可以互相租賃、出售,無需監管部門介入;動態專有模型下根據各用戶的頻譜需求在空域與頻譜對頻譜資源進行快速分配;開放共享模型中無主次用戶的區別,可以采取合作(或中心化)和競爭(或去中心化)的頻譜分配方式,在工業、科學、醫療頻段這些無授權用戶的頻段中可以采用這樣的接入方式;頻譜下墊接入模型中認知用戶通過微功率技術(如超寬帶技術)接入頻譜,需要滿足主用戶接收端的干擾溫度約束[71];機會式頻譜接入模型既是Mitola在關于認知無線電的定義中建議的一種模型,也是最能夠兼容當前的頻譜管理政策與無線電系統的模型,因此成為了當前認知無線電研究領域的主流[70]。

南京郵電大學的夏婷婷等人針對多認知用戶下的機會式頻譜接入問題,提出了一種基于Dec-POMDP的模型[73],以各信道的可用性作為狀態向量s(t)=[s1,s2,…,sN],sn∈{0(空閑),1(占用)},1≤n≤N,以各認知用戶的頻譜接入行為作為動作向量a(t)=[a1(t),a2(t),…,aN(t)],其中an(t)表示各用戶在時隙t的頻譜接入動作(選擇哪個信道接入)。以認知用戶在時隙t的吞吐量作為獎勵函數,通過作者提出的發送前請求(request to send, RTS)和發送前確認(confirm to send, CTS)以及在觀測到可用信道時采取的隨機等待時間等機制進行信道的準入,以本地對s(t)的觀測和是否準入發射信道作為觀測值o(t)。

電子科技大學的郭冰潔提出的Dec-POMDP動態頻譜分配模型中各用戶的時隙中加入確認字符(acknowledge character, ACK)狀態字,將觀測信道狀態增加為4種:空閑、繁忙、成功、失敗。除此之外,還在觀測信息種加入了繁忙率指標來表示截至當前觀測時隙觀測信道為繁忙的次數與對該信道的總觀測次數的比率[74],通過加入該統計量表征各信道的繁忙程度。但該模型在獎勵函數的設計中沒有考慮用戶業務的服務質量(quality of service, QoS),僅簡單地以接入信道成功與否作為獎勵的依據,在實際動態頻譜分配中,不僅要考慮到用戶能否接入頻譜,還必須考慮接入同一信道后造成的干擾(尤其是對主用戶)對QoS造成的影響,在此約束條件下進行權衡。

電子科技大學的何浩考慮了在能效約束下優化認知用戶的總吞吐率的問題,在文獻[75]中,他在將信道狀態建模為有限狀態馬爾可夫信道(finite state Markov channel, FSMC),在考慮了不同信道狀態(信道增益)下基于M元正交振幅調制下滿足誤碼率門限下的最小功率約束條件下,將所有信道的信道狀態與頻譜感知結果作為狀態向量s,將各用戶的信道選擇與速率選擇(調制信息)作為動作向量a,目標函數為在平均功率耗費門限約束下最大化各用戶的總吞吐量,由于認知用戶對狀態信息的觀測由認知用戶發送導頻到基站，由基站估計后回傳得到,因此也是部分觀測狀態,本文在這種Dec-POMDP模型下提出其最優策略滿足納什均衡。

上面所提的這些模型中都沒有將發射功率控制及其對網絡效用造成的影響進行考慮,廣東工業大學的葉梓峰提出頻譜下墊接入模型中[76],通過微基站作為感知節點輔助次用戶進行頻譜接入決策。將認知無線電網絡中的微基站接收到的主用戶、次用戶信號與噪聲功率的和作為狀態向量,以離散化的功率水平控制作為動作向量,在主用戶QoS滿足門限要求時,其獎勵函數為次用戶的信噪比和;當主用戶QoS在次用戶接入后不滿足門限要求,則獎勵函數為次用戶信噪比和的負值。目標函數為最大化網絡的總吞吐率。

綜上所述,把動態頻譜分配問題映射到Dec-POMDP模型中,其狀態空間S主要表示當前頻譜分配的狀態、信道狀態(信道增益)以及主用戶接收端的信號與干擾加噪聲功率比(signal to interference plus noise ratio, SINR);決策(動作)空間A主要可以分為兩個方面,一是頻譜的分配,二是認知用戶的功率控制(功率水平的選擇);而獎勵函數R是MARL的關鍵,一般是在頻譜分配約束(一個信道同時最多只能分配給一個次用戶)下的總頻譜利用率與主用戶干擾溫度約束下的認知無線電網絡的總吞吐率以及主用戶QoS的變化。

Dec-POMDP與動態頻譜分配過程之間的映射關系如圖8所示。

圖8 基于Dec-POMDP的動態頻譜分配建模

3.2 基于Dec-POMDP模型的動態頻譜分配方法

目前基于Dec-POMDP模型和MARL的動態頻譜分配算法分為:基于獨立Q-學習(independent Q-learning, IQL)的方法、基于合作Q-學習(cooperative Q-learning, CQL)的方法、基于聯合Q-學習(joint Q-learning, JQL)的方法以及基于多智能體AC算法(multi-agent AC，MAAC)的集中訓練分布執行方法。

3.2.1 基于IQL的動態頻譜分配方法

基于獨立Q-學習的方法使每個智能體(用戶)根據獨立觀測的信息利用式(3)和式(4)進行狀態價值估計與策略的優化,通過大量訓練收斂到穩定點。

Li等人分析了兩認知用戶下無協同的基于IQL的動態頻譜分配過程,證明并驗證了認知用戶無論在僅獲得部分觀測信息或完整觀測時均可收斂到穩定點(納什均衡點)[77];Teng等提出了一種基于IQL的競價拍賣機制進行動態頻譜分配[78],次用戶通過IQL算法學習最優的競價策略,主用戶則根據次用戶的策略產生可接受價格向量確保自身利益,該算法有效提升了競價效率;Wu等根據認知網絡中用戶間由于頻譜接入行為造成的相互干擾構建了IQL的獎勵函數[79];伍春等將無監督機器學習方法k-means與IQL算法結合,用戶進行聚類減小智能體數量后,用可變學習率IQL方法進行策略優化[80];除此之外,Zia等人討論了在多層異構網絡下,D2D通信用戶與蜂窩用戶間的動態頻譜共享問題,利用IQL算法進行優化并與兩種理想狀態方法進行了對比[81]; Asheralieva等人利用IQL算法優化一個基站內的D2D通信用戶動態頻譜分配問題,并提出了一種利用當前狀態下Q函數的的玻爾茲曼分布作為策略函數,增加策略的隨機性與探索性,與貪婪Q-學習、其他兩種理想狀態下的傳統算法進行了對比,證明了基于MARL方法相較于傳統方法在性能上的優越性[82]。

上述方法均采用了表格學習對各用戶的獨立Q函數進行更新,而這種方法隨著智能體數量、觀測狀態空間的增加,Q表的更新和收斂速度會受到很大的影響,因此Naparstek等人結合DQL領域的進展,提出利用DQN擬合各用戶的Q函數,并加入循環神經網絡層如長短期記憶(long short-term memory, LSTM)網絡或門控循環單元(gated recurrent unit, GRU)網絡,利用構造的DQN的記憶能力和認知用戶的同構性,僅訓練一個DQN網絡將其在用戶間共享,利用RNN的記憶性在用戶間建立協調關系,利用經驗回放和隨機采樣等DQN中的技巧加快了訓練速度[83]。Zhao等人提出的MADQN算法是一種結合了DQN的IQL方法,在仿真實驗中用戶數較少的環境下,與基于比例公平權重的信道選擇算法和隨機分配算法進行對比,在單用戶吞吐率、系統總吞吐率、單用戶的成功發送概率等性能指標上優于兩類傳統方法[84]。Nasir等人對基于DQN與IQL的認知無線電網絡中的功率分配算法進行了研究,與傳統算法進行對比后,結果表明該算法不僅在頻譜效率和系統總吞吐率上取得比傳統算法更好的表現,在收斂速度上也有不低于傳統算法的表現[85]。

基于IQL算法的動態頻譜分配方法忽略了對于單個用戶而言外部環境變化具有的非馬爾可夫鏈的性質,其狀態轉移模型并不是平穩的,加之在值函數的優化上沒有考慮用戶間協作產生均衡策略的約束,因此適用的用戶數量較少,訓練時收斂速度慢,且不一定能收斂到最優策略,往往得到的是次優策略。

3.2.2 基于CQL的動態頻譜分配方法

基于合作Q-學習的方法中單個用戶Q函數中不僅考慮當前狀態下自身動作,還包含了其他用戶動作的因素,通過考慮其他智能體的策略優化趨勢,使得單獨用戶的Q函數可以更快收斂到穩定點(或納什均衡點)。

CQL算法在更新獨立Q函數過程中需要得到其他所有智能體的動作與Q函數以及環境的聯合狀態信息,在分布式決策條件下,全局狀態實際上不容易得到;這種完備的信息交互在實際的通信網絡中將造成很大的通信開銷,難以實現。

3.2.3 基于JQL的動態頻譜分配方法

基于JQL的方法是一種集中訓練集中執行的方法,該方法將所有用戶的動作視為在全局環境狀態下的統一動作,因此將分布執行下智能體決策的部分可觀測馬爾可夫決策問題簡化為一般的馬爾可夫決策問題,從而可以直接應用單智能體強化學習。

Wang等人將DQN作為集中訓練集中執行算法,在實驗環境中驗證了算法的收斂性,與Whittle索引啟發式算法和信道正相關條件下的最優短視算法進行對比,結果表明DQN能收斂到與最優算法相近的結果[88]。

但這種JQL算法首先需要進行集中決策,在每個狀態下都必須確保中心對用戶的完全控制,因此存在通信開銷大的缺點;其次是該算法要求得到對環境的完整感知信息,由于多徑、陰影衰落和路徑損耗,這種對環境的完整感知在實際中難以做到;加之該方法隨著用戶數量增加,其評估與決策的動作空間維度呈指數級增長,容易造成值函數表示困難、難以訓練等問題。所以其適合解決用戶數量較少的問題,不適合解決用戶數量龐大如超密集網絡的動態頻譜分配問題。

3.2.4 基于MAAC的動態頻譜分配方法

由于多智能體環境中單個智能體的環境非平穩性,給基于Q-學習的算法帶來了很大的挑戰,雖然可以利用合作學習或集中學習的方法減緩因此造成的影響,但收斂速度慢、容易陷入局部最優或某一固定點以及協同、控制中對通信需求較大等缺點仍然難以有效解決。

因此,隨著近年來集中訓練分布執行的MARL算法取得了很多突破與進展,利用該類型的MARL算法解決多用戶動態頻譜分配策略的訓練就顯的非常具有研究意義與前景。

Li等人提出了一種利用MAAC算法解決車聯網環境中D2D用戶與蜂窩用戶間的動態頻譜分配問題的方法。并在MAAC算法的基礎上,提出了一種基于距離降低訓練樣本需求的NAAC算法可以進一步加快訓練的速度,降低計算復雜度。在實驗中將MAAC和NAAC算法與DQN、IQL以及基于主從博弈的隨機學習算法(stochastic learning algorithm, SLA)進行了對比,無論在用戶的中斷率還是收斂后的網絡整體效用上均大大超過了DQN、IQL和SLA算法[89]。

表1中對比了4種基于多智能體強化學習方法的動態頻譜方法的特點。

表1 4種方法特性對比

4 基于多智能體強化學習的動態頻譜分配方法關鍵問題

通過總結歸納上述文獻可以發現,現有的文獻中在建立基于Dec-POMDP模型的MARL動態頻譜分配算法中往往將SUA與OSA模型分開考慮,即利用功率控制算法解決SUA問題,利用頻譜選擇接入算法解決OSA問題。而在實際的動態頻譜分配問題中,頻譜分配與功率控制需要同時考慮;在集中訓練分布執行的MARL算法中,集中訓練過程需要對環境具有完整的觀測或估計,如何由認知用戶的部分觀測信息推斷出頻譜分配的完整信息是一個重要的問題;當前的MARL算法多數應用在智能體數量固定的環境中,而認知無線電網絡中用戶數量可能是動態變化的。

通過以上分析可以進一步梳理出如下3種基于MARL的動態頻譜分配方法的關鍵問題。

(1)基于Dec-POMDP建立更合理的動態頻譜分配模型

在基于OSA的模型中,往往只考慮了頻譜的選擇,次用戶在頻譜感知后只要檢測到主用戶信號的存在,就要立即從該信道中退出,這種接入方式既增加了次用戶的中斷率,容易增加次用戶的通信時延,又使得次用戶的頻譜利用率降低;而基于SUA的模型中,基于超寬帶等技術的認知用戶受限于在所有頻段上的發射功率都處于較低水平,為保證主用戶的干擾溫度約束,信道容量容易受限,在主用戶未占用的頻帶內,功率不能靈活調整以提高QoS。因此,可以考慮結合頻譜下墊接入與機會式頻譜接入模型,在主用戶占用的頻帶內,在主用戶干擾溫度約束下以SUA接入,而在主用戶尚未占用的頻帶內以OSA接入,以進一步提高頻譜利用率與次用戶QoS。

基于MARL的動態頻譜分配方法中,獎勵函數以及產生的即時獎勵是促進算法優化的激勵信號,如何合理設置獎勵函數是算法能否快速收斂的關鍵因素,尤其是獎勵函數中體現對主用戶QoS的保護以及提高頻譜利用率的約束條件是算法合理性的關鍵條件,需要進行進一步深入研究。

(2)基于分層抽象建立部分觀測到狀態的映射

傳統的POMDP問題的解決方法中加入了信念向量的輔助,信念向量由歷史觀測值{ot,at,ot-1,at-1,…,o0,a0}組成的觀測向量由狀態轉移函數進行變換后得到一個關于真實狀態轉移的概率分布。但實際上狀態轉移函數是未知的,而利用分層強化學習可以解決這個問題,在不需要信念向量的條件下,通過設置選項、分層抽象等方法，從觀測信息中對真實的環境全局狀態進行學習,映射到動態頻譜分配問題中,也就是利用認知用戶的不完全頻譜感知信息在集中訓練架構下通過分層強化學習的方法估計真實的頻譜分配狀態,這也將解決集中訓練方法中真實狀態不可知條件下全局Q函數的學習問題。

(3)認知無線電網絡的動態拓展

目前基于MARL的動態頻譜分配算法存在的主要問題之一是如何應用在用戶數量變化的認知無線電網絡中,換言之,也就是如何解決智能體策略的泛化性。利用集中訓練分布執行的模式有效解決了多智能體間環境的非平穩性導致的訓練收斂性問題,但集中訓練的前提是多智能體整體所處外部環境是平穩的,一旦加入新的用戶,即智能體后,多智能體整體的外部環境也變得非平穩,這就導致一旦網絡內用戶數量發生變化,網絡內的所有用戶的策略都需要重新進行訓練。

隨著離線強化學習的提出,這種利用其他智能體與環境的交互軌跡對新的智能體策略進行訓練的方式為解決智能體策略的泛化性或者認知無線電網絡用戶的可擴展性提供了新的思路。

5 結束語

基于傳統理論的動態頻譜分配算法存在分配時間長,計算復雜度高,不適應動態變化的無線通信環境且不適合分布式決策的缺點,而隨著MARL為代表的群體智能技術的興起和發展,基于這種群體智能技術的動態頻譜分配方法相比于傳統方法來說具有智能化、實時化和分布化的諸多優勢。本文對現有的基于MARL的動態頻譜分配方法的研究現狀進行了梳理與總結,根據應用算法框架將這些研究成果分為4種類型,比較了4種類型方法的優劣,結合RL、MARL及其在動態頻譜分配問題中的應用,提出了模型建立、從部分觀測信息中分層學習以及認知無線電網絡用戶的拓展性中存在的關鍵問題,并分析了解決思路。