基于強化學習的雙人博弈差分隱私保護研究

摘要：針對雙人博弈問題，在學習Q-learning算法的基礎上，利用神經網絡參數逼近的方式更新狀態值函數，選取自適應梯度優化算法進行參數更新，并通過納什均衡思想調節兩個智能體的行為。同時為提高模型的保護效果，對結果添加差分隱私保護，保證智能體博弈過程中數據的安全性。最后，實驗結果驗證了算法的可用性，其能夠訓練兩個智能體在多回合之后穩定抵達各自目標點。

關鍵詞：強化學習；差分隱私；雙人博弈

中圖分類號： TP309;F224.32文獻標識碼： A

收稿日期：2023-01-18；修回日期：2023-05-16

基金項目：國家自然科學基金（61673200），山東省自然科學基金（ZR2022MF231）

第一作者：馬明揚（1998-），女，山東濰坊人，碩士，主要研究方向為差分隱私保護等。

通信作者：楊洪勇（1967-）， 男，山東德州人，博士，教授，主要研究方向為復雜網絡、多智能體系統、智能控制等。

Research on Differential Privacy Protection of Two-player Games Based on Reinforcement Learning

MA Mingyang，YANG Hongyong，LIU Fei

（School of Information and Electrical Engineering， Ludong University， Yantai 264025，China）

Abstract：For the two-player game problem， on the basis of Q-learning algorithm， the state-value function is updated by using neural network parameter approximation， the adaptive gradient optimization algorithm is selected for parameter updating， and the behaviors of the two agents are regulated by the Nash equilibrium idea. At the same time， in order to improve the protection effect of the model， differential privacy protection is added to the results to ensure the security of the data in the process of the two-player games. Finally， the experimental results verify the usability of the algorithm， which is able to train two agents to reach their respective target points stably after multiple rounds.

Keywords： reinforcement learning; differential privacy; two-player games

0 引言

自20世紀50年代中期步入互聯網時代以來，人工智能技術逐漸興起，機器學習作為其核心，旨在幫助人類完成重要的復雜工作^[1]。強化學習應用到多智能體系統，為每個智能體的行為作出有利于自身的決策，使得多智能體系統的整體性能達到最優，當前對多智能體強化學習方法的研究受到許多學者的關注。

強化學習的馬爾科夫決策過程拓展到多智能體系統，被定義為馬爾科夫博弈，主要指智能體之間存在合作、競爭或者共存的局面。近年來，許多學者致力于研究多智能體博弈。董等^[2]對博弈的存在和實踐進行了討論，從系統論角度提出了多智能體演化博弈的理論框架。Chen等^[3]開發了一個馬爾可夫路由游戲（MRG），每個智能體在與運輸網絡中的其他智能體交互時學習并更新自己的路徑選擇策略。雙人博弈也是多智能體博弈的一種，消去法、劃圈法等是用于求解雙人博弈純策略均衡解的經典方法。在博弈過程中，每個智能體都希望自己能夠獲得最大回報，此時的策略集稱為納什均衡。Lemke-Howson^[4]算法、幾何圖形法等是用于求解混合策略納什均衡值的主流計算方法。尹等^[5]運用圖論的知識求解雙人完全信息靜態博弈的納什均衡過程。陳等^[6]在進行狀態空間描述的基礎上，求解了混雜動態博弈的納什均衡。

在雙人博弈的過程中，各智能體之間通過信息交互對當前和下一步行為進行決策，用收集到的數據對模型進行訓練，直至結果收斂，此時，攻擊者可能會利用訓練過程中的模型更新參數對訓練數據的數據集進行攻擊^[7]，進而擾亂正常的交互過程。所以在研究多智能體博弈時，也要注重數據的安全性。在各種隱私保護方法中，差分隱私^[8]通過在數據集中加入滿足某種分布的噪聲來實現隱私保護，不管攻擊者得到的輔助信息是什么，都可以從根本上抵御身份攻擊。差分隱私已被應用到各種領域以保護數據安全。Yang等^[9]提出了一個形式化的框架來驗證概率系統中的差分隱私。吳等^[10]提出了一種基于噪聲前綴樹結構的軌跡數據發布方法，利用差分隱私在保證軌跡數據安全的同時提高了數據可用性。白等^[11]針對健康醫療的非數值型數據，利用差分隱私中的指數機制，設置誤差參數和滿足誤差的統計個數進一步滿足不同安全性和可用性的需求。

在現有的多智能體強化學習算法中，多數研究的關注點都放在最終的任務效果上，往往忽略了理論性的證明與迭代過程中的隱私保護。基于此，本文擬研究基于強化學習的雙人博弈差分隱私保護，在學習Q-learning算法的基礎上，利用神經網絡參數逼近的方式替代值函數表值更新，制定了能夠有效平衡探索與利用的動作選擇策略，并通過納什均衡思想調節兩個智能體的行為。同時為神經網絡的輸出添加合適的滿足拉普拉斯分布的噪聲，提升了數據安全性，并從理論上分析了自適應梯度迭代算法的收斂性，保證了多智能體最終訓練至收斂狀態，同時從仿真實驗中說明了算法的有效性。

1 相關基本理論

1.1 差分隱私

定義1^[12] 設有隨機算法M，對任何兩個鄰近數據集D和D′ ，S∈Range（M） ，若算法M滿足

Pr[M（D）∈S]≤e^ε×Pr[M（D′）∈S]（1）

的概率約束，則其提供ε-差分隱私保護，通過隨機化輸出結果提供隱私保護。其中鄰近數據集是指兩者的對稱差數量為1，參數ε表示隱私保護預算，越接近于0隱私保護程度越高。

定義2 差分隱私保護機制：給定數據集D，設有查詢函數f，其全局敏感度為△f，那么隨機算法M（D）滿足

M（D）=f（D）+LapΔf/ε（2）

提供差分隱私保護。其中全局敏感度

Δf= maxD，D′f（D）-f（D′）₁（3）

Laplace分布的概率密度公式為

p（x｜μ，b）=1/2bexp-｜x-μ｜/b（4）

其中，μ為位置參數，b為尺度參數，該分布可記為Lap（b， μ），當μ=0時，記Lap（b）。

1.2 強化學習

強化學習的基本框架如圖1所示，即智能體在狀態s（state）下完成某項工作時，執行一項行為a（action）與周圍環境進行交互，在共同作用下，智能體會產生新的狀態s′，同時會得到環境給出的一個即時回報r。整個過程中，智能體不斷與環境交互產生數據，同時利用這些數據去學習能夠得到最大獎勵的策略。

大多數的強化學習問題都可以概括為馬爾可夫決策過程，用（S，A，P，R，γ）來表示^[13]。其中S代表有限狀態集合，s∈S表示某個特定狀態；A代表有限動作集合，a∈A表示某個特定的動作；P^a_ss′為狀態轉移概率，表示從s采取行動a轉移到s′的概率；R為回報函數；γ∈[0，1]為折扣因子，體現了未來的獎勵在當前時刻的價值比例。

馬爾科夫決策過程具有無記憶性：

P_r（X_t+1=x|X_t=x_t，X_t－1=x_t－1，…，X₁=x₁）=P_r（X_t+1=x|X_t=x_t）（5）

馬爾科夫決策過程狀態轉移概率為

P^a_ss′=P[S_t+1=s′|S_t=s，A_t=a]（6）

當單智能體延伸至多智能體時，每個智能體仍然遵循最大化累積回報的目標，但此時環境的因素與所有智能體聯合動作相關。馬爾科夫決策過程拓展到多智能體系統，稱為馬爾科夫博弈，參與者會盡可能選取對自身最有利的行為，使其得到的回報最大。它可以通過元組 〈n，S，A₁，…，A_n，T，R₁，…，R_n，γ〉來表示，其中n為智能體個數，S為狀態集合，A_i為智能體i的動作集合，R_i為智能體i的獎勵集合，T為環境狀態轉移概率，γ為折扣因子。

1.3 納什均衡

納什均衡又稱為完全信息靜態博弈納什均衡或者策略博弈納什均衡^[14]。策略博弈可以用一個元組（n，A₁，…，A_n，R₁，…，R_n）表示，n為智能體個數，A_i為智能體i的策略集合，即A_i={a^（i）₁，a^（i）₂，…，a^（i）_m}，R_i為支付函數，是智能體在聯合行為下所得到的回報。

定義3^[14] 策略博弈納什均衡是指所有玩家策略滿足不等式的集合：

V_i（π^*₁，…，π^*_i，…，π^*_n）≥V_i（π^*₁，…，π_i，…，π^*_n）

V_iπ_i∈Π_i， i=1，…，n（7）

其中，V_i（·）為智能體i的值函數，π_i為智能體i在策略空間Π_i中選擇的行為， π^*_i 為智能體的最優策略。式（7）表明當其他智能體都執行納什均衡策略，智能體i通過改變自身策略無法獲得更大的回報。

2 雙人博弈的差分隱私保護算法

多智能體強化學習需要考慮環境的不穩定性、智能體獲取信息的局限性、個體目標的一致性以及可拓展性等，并且在構建算法的過程中，要著重考慮合理性和收斂性，即在共同使用學習算法時，每個智能體能夠學習并收斂到相對于對手的最優策略。在Nash Q-learning學習算法的基礎上進行改進，使改進方法能夠在有效收斂的前提下，加入隱私保護，為其數據添加隱私。

2.1 Nash Q-learning學習算法

Q-learning算法是基于時間差分的強化學習算法，但實際上也可以理解為一個表值學習算法，即智能體在與環境互動過程中形成了一個狀態-動作的Q值表。當智能體完成一件事，有立即獎賞，即做了一個動作能夠立即獲得的獎勵，還有記憶經驗獎勵，即按照訓練時的經驗，上一個動作發生后，接下來怎么做才能獲得更大的獎勵。Q-learning算法的思想同時考慮這兩方面，值函數Q的更新公式為

其中，α_t為學習率，取值在0和1之間，代表未來新值置換原值的比例。γ為折扣因子。r_t為選擇動作后所得到的立即回報。

將單智能體Q-learning方法應用到多智能體中，智能體i不僅要觀察自身回報，還要獲悉他人的回報。當智能體之間是混合關系時，每個智能體各自采取學習方法最大化Q值，可以收斂到納什均衡策略。Nash Q學習算法可應用于多智能體問題中，在智能體i更新當前狀態的Q值時不再只是與自身下一狀態的Q值相關，而是采取納什均衡策略進行更新，使得各個智能體聯系起來，對于其中任意一個智能體來說，無法通過采取其他的策略來獲得更高的累積回報。對于智能體i而言，它的納什Q值定義為

NashQⁱ_t（s′）=π¹（s′）…πⁿ（s′）Qⁱ_t（s′）（9）

此時，假設了所有智能體從下一時刻開始都采取納什均衡策略，納什策略可以通過二次規劃（僅考慮離散的動作空間，π為各動作的概率分布）來求解。

Qⁱ_t+1（s，a₁，a₂，…，a_n）=（1-α_t）Q（s，a₁，a₂，…，a_n）+α_t[rⁱ_t+βNashQⁱ_t（s′）]（10）

其中，NashQⁱ_t（s′）為智能體i在下一狀態的納什均衡點。相比單智能體，多智能體強化學習的智能體需要知道全局狀態、其他智能體的動作以及下一狀態所對應的納什均衡策略，據此計算當前Q值，以做出更好決策，NashQ學習方法通過式（10）進行更新學習。

2.2 雙人博弈差分隱私保護算法設計

Nash Q-learning學習算法中，記錄雙方的Q值需要大量空間，計算過程的復雜也會導致收斂較慢，所以設計一種函數逼近的方式去擬合Q值，使得值函數的更新變為參數的更新，節省算法空間，從而提高算法優化策略的程度，并且給Q值加噪聲，給予隱私保護。

2.2.1 動作選擇策略

首先設置e值，當隨機數小于e時，智能體i選擇當前狀態下Q值最大的動作，當隨機數大于e時，采取玻爾茲曼策略，根據Q值計算各動作的概率，智能體i根據概率選擇下一步動作，動作選擇概率為

P（a｜s）=exp（Q（s，a））/∑aexp（Q（s，a））（11）

該策略方案能夠有效地平衡探索和利用，e值隨著策略的迭代逐漸增大，訓練前期更偏向于探索，后期逐漸訓練完成，更偏向于利用。設置玻爾茲曼策略的意義在于給隨機選擇動作加一個概率，更大概率地去選擇當前Q值最佳的動作，同時也給予探索的機率，前期各動作的概率值趨向一致，訓練后期逐漸得到最優策略時也能促進算法更快收斂。

2.2.2 動作值函數的優化算法

由于多智能體在學習的過程中往往會產生大量特征信息，通常采用深度學習的神經網絡逼近目標函數^[15]，故本文中設置神經網絡非線性逼近Q值，輸入層的神經元個數為觀測值的特征數，輸出層的神經元個數為動作空間的個數，輸出值是每個動作的價值。

損失函數設為

其中，初始值v₀=0，α_t為學習率，衰減系數0lt;βlt;1，用來控制歷史信息的獲取大小，εgt;0，以保證分母不會為0，g_t為損失函數的梯度。從式（13）可以看出，v_t是一個指數式遞減加權的移動平均，越近期的數值加權越大。學習率逐參數地除以經衰減系數控制的歷史梯度平方和的平方根，當參數空間下降平緩時，歷史梯度平方和較小，從而在平緩方向上取得更大的進步，可以加快訓練速度。

2.2.3 數據隱私保護設計

為有效應對隱私泄露，使用添加噪聲的方式實現差分隱私機制以抵抗差分隱私攻擊，保護原始數據。

由于在雙人博弈的過程中，彼此要對狀態值函數產生的數據進行通訊，故對該數據添加符合拉普拉斯分布的噪聲，即QQ+Lap（b），b為尺度參數。添加的噪聲是有一定規律的一組數據，使整個數據結構發生了比較大的變化，從而使得個體數據難以被破解，但對于整體數據而言，拉普拉斯分布具有均值為0的特性，所以在大量數據的訓練背景下不會對最終結果產生明顯的影響。

2.2.4 算法設計與實現

雙人博弈差分隱私保護算法的步驟為：1）設置神經網絡非線性逼近Q值，初始化參數θ。2）循環每一步，迭代次數用t表示，并初始化智能體的狀態。3）根據策略選擇下一步動作。4）執行動作后，智能體i觀察自身和對方智能體所獲得的回報和行動。5）根據神經網絡的輸出值更新值函數，并對其添加噪聲進行隱私保護。6）利用自適應梯度優化算法更新神經網絡參數。7）轉入下一次迭代至步驟3），直到滿足每個回合的結束條件。本文實驗設置中的結束條件為智能體相撞或至少有一個智能體抵達目標點。8）重復執行上述步驟2）至步驟7），滿足設置的回合數后算法結束。

在神經網絡的訓練過程中，由于要求輸入的樣本之間相互獨立，所以不能簡單地依次輸入狀態，需要在回合過程中，將樣本數據信息存入緩沖區。游戲開始后，累積一些數據再訓練，訓練時隨機抽取，以切斷樣本的相關性，并隔5步訓練一次，提升訓練時間。整體算法大致框圖如圖2所示。

2.3 算法收斂性分析

本節主要從理論上分析驗證迭代算法是有效的，即能夠找到使損失函數最小的神經網絡參數。在證明之前，給出分析算法收斂的常見假設。

隨著t的不斷增大f（θ_T）不斷減小，且f（θ_T）≥0有下界，證明收斂。

雖然在迭代過程中為Q值添加了拉普拉斯噪聲的隱私保護，但由于該噪聲均值為0，在多次的添加過程中對其真實值幾乎沒有影響，因此不會影響其收斂性。

3 實驗仿真與分析

3.1 實驗設置

在如圖3a所示的傳統雙人網格博弈游戲中運行算法，其中方框代表智能體，圓形代表終點，四周擬為墻。智能體在該網格的動作空間為上、下、左、右，左上角位置點為0，向右向下逐漸增加，單個網格單位為1，據此可知初始狀態為（0，2）。在訓練過程中，要讓雙智能體沖突得到獎賞的優先級高于僅有單智能體抵達目標點，否則可能會收斂至雙智能體與某個目標點碰撞。因此，獎賞設置為如果兩個智能體同時抵達目標點，獎賞20，回合結束；如果兩個智能體沖突，回報-10，回合結束；如果只有一個智能體抵達目標點，獎賞10，回合結束；如果智能體撞墻，回報-10，回合繼續；到達其他狀態獲得回報0，回合繼續。圖3b是預估的能夠在均衡狀態下抵達終點的可能情況，最終，該算法可以訓練兩個智能體以其中一種方式收斂到終點。

3.2 實驗分析

在Python3.9環境下，運行前面提到的算法，加入拉普拉斯噪聲增添隱私保護，訓練次數設為1 600回合，觀察智能體是否能夠在訓練后以一種穩定的路徑方式抵達目標點。

3.2.1 實驗結果圖

圖4為某次訓練到一定程度后，兩個智能體的路徑，能夠按照要求抵達終點。

3.2.2 損失函數

損失函數的變化過程如圖5所示，反應出算法在不斷的探索開發中最終是否能夠到達收斂狀態，即雙智能體以一種穩定的策略達到目標點。自適應梯度算法有利于修正擺動幅度，使得收斂更快。同時可以看出Cost曲線并不是平滑下降，這是因為在學習的過程中，神經網絡的參數值是一步步學習的，兼顧探索和利用的過程，且加入噪聲，對數據產生影響，在反復學習后，才能達到收斂效果。

3.2.3 結果分析

為了進一步觀察學習過程中實驗結果的情況，在某次實驗每100回合分析結果中goodresult、generalresult、badresult所占數量，分別指的是兩個智能體都到達終點、僅有單智能體抵達終點以及其他情況，并做折線圖展示。通過圖6可以看出隨著智能體不斷學習和參數不斷迭代更新，最終穩定抵達終點，證明了該算法的有效性。

同時做實驗比較添加隱私保護對收斂情況造成的影響，某次實驗結果如表1所示，在前期由于對Q值數據添加噪聲，各智能體的訓練學習受到干擾，但隨著回合數的增加，依據拉普拉斯噪聲分布均值為0的特性，添加隱私保護并不影響最終的收斂情況。

在實驗過程中給噪聲設置不同的尺度參數并進行多次實驗，對比添加噪聲對成功率的影響情況，如表2所示，計算在實驗回合1 000至1 400之間的成功率，可見雖然噪聲對成功率稍有影響，但整體而言并不干擾最后的任務效果。需要注意的是，必須選擇合適的噪聲才能不影響數據的可用性，否則也會出現數據偏離的情況。

4 總結

該文針對雙人博弈問題，在學習Nash Q-learning算法的基礎上，設計神經網絡對狀態值函數進行逼近，將損失函數的最小值作為優化目標，選取自適應梯度算法對神經網絡參數迭代更新，并對神經網絡輸出結果添加隱私保護。最后，實驗表明了算法的可用性，添加了合適的拉普拉斯噪聲，加強了數據的安全性，訓練使得兩個智能體能夠均衡地抵達對應目標點。

參考文獻：

[1]劉豪. 多智能體博弈強化學習算法及其均衡研究[D]. 西安：西安科技大學， 2020.

LIU H. Research on reinforcement learning algorithm and equilibrium of multi-agent game[D]. Xi′an： Xi′an University of Science and Technology， 2020.

[2]DONG Q， WU Z Y， LU J， et al. Existence and practice of gaming： thoughts on the development of multi-agent system gaming[J]. Frontiers of Information Technology amp; Electronic Engineering，2022，23（7）：995-1002.

[3]SHOU Z， CHEN X， FU Y， et al. Multi-agent reinforcement learning for Markov routing games： a new modeling paradigm for dynamic traffic assignment[J]. Transportation Research Part C： Emerging Technologies， 2022， 137：103560.

[4]LEMKE C E， HOWSON J T. Equilibrium points of bimatrix games[J]. Journal of the Society for Industrialamp;Applied Mathematics， 1964， 12（2）： 413-423.

[5]尹佳偉， 程昆.納什均衡解的另一種解法[J].統計與決策，2017（15）：70-72.

YIN J W， CHEN K. Another solving method of nash equilibrium[J]. Statistics amp; Decision， 2017（15）：70-72.

[6]陳向勇，曹進德，趙峰，等. 基于事件驅動控制的混雜動態博弈系統的納什均衡分析[J]. 控制理論與應用， 2021，38（11）：1801-1808.

CHEN X Y， CAO J D， ZHAO F， et al. Nash equilibrium analysis of hybrid dynamic games system based on event-triggered control[J]. Control Theory amp; Applications. 2021，38（11）：1801-1808.

[7]張珊.深度學習中差分隱私保護算法研究[D].呼和浩特：內蒙古大學，2022.

ZHANG S. Research on differential privacy in deep learning[D]. Hohhot： Inner Mongolia University， 2022.

[8]FU J，CHEN Z，HAN X.Adap DP-FL：Differentially Private Federated Learning with Adaptive Noise[C]//2022 IEEE International Conference on Trust，Security and Privacy in Computing and Communications.Wuhan，China：IEEE，2022：656-663.

[9]YANG J， CAO Y， WANG H. Differential privacy in probabilistic systems[J]. Information and Computation， 2017， 254（1）： 84-104.

[10] 吳萬青，趙永新，王巧，等.一種滿足差分隱私的軌跡數據安全存儲和發布方法[J].計算機研究與發展，2021，58（11）：2430-2443.

WU W Q， ZHAO Y X， WANG Q， et al. A safe storage and release method of trajectory data satisfying differential privacy[J]. Journal of Computer Research and Development， 2021，58（11）：2430-2443.

[11] 白伍彤，陳蘭香.基于差分隱私的健康醫療數據保護方案[J].計算機應用與軟件，2022，39（8）：304-311.

BAI W T， CHEN L X. Healthcare data protection scheme based on differential privacy[J]. Computer Applications and Software， 2022，39（8）：304-311.

[12] Dwork C. Differential privacy[C]//Proceedings of the 33rd International Conference on Automata， Languages and Programming-Volume Part II.Berlin， Heidelberg， Springer： 2006.

[13] 王軍，曹雷，陳希亮，等.多智能體博弈強化學習研究綜述[J].計算機工程與應用，2021，57（21）：1-13.

WANG J， CAO L， CHEN X L， et al. Overview on reinforcement learning of multi-agent game[J]. Computer Engineering and Applications， 2021，57（21）：1-13.

[14] 胡浩洋，郭雷.多人非合作隨機自適應博弈[J].控制理論與應用，2018，35（5）：637-643.

HU H Y， GUO L. Non-cooperative stochastic adaptive multi-player games[J]. Control Theory amp; Applications， 2018，35（5）：637-643.

[15] 鄒啟杰，蔣亞軍，高兵，等.協作多智能體深度強化學習研究綜述[J].航空兵器，2022，29（6）：78-88.

ZOU Q J， JIANG Y J， GAO B， et al. An overview of cooperative multi-agent deep reinforcement learning[J]. Aero Weaponry， 2022，29（6）：78-88.

（責任編輯 耿金花）