多Agent MDPs中并行Rollout學習算法

李 豹

（中國人民銀行蕪湖市中心支行，安徽蕪湖 241000）

目前，多Agent學習已成為人工智能領域的熱點，大多數(shù)研究工作是基在于Markov對策（Markov games）理論框架下研究.和單Agent學習不同，多Agent學習在Agent選擇動作或行為時，需要考慮所有Agent值函數(shù)的某種平衡解（equilibrium Learners），因此在本質上，Markov對策可看成是將馬爾科夫決策過程（MDPs）從單Agent擴展到多Agent領域.其算法成果包括Minimax－Q學習算法和Friend－or－Foe－Q（FFQ）學習算法［1－2］、Nash Q學習算法［3］、CE－Q學習算法［4］等.在實際中，大多數(shù)多Agent系統(tǒng)，由于系統(tǒng)本身自有的特點，在多Agent學習時，其狀態(tài)空間和行動集合往往特別巨大.同時，多Agent之間行為預測也會擴大空間需求，為此，需要研究逼近的方法來降低空間需求.使用神經元動態(tài)規(guī)劃（NDP）理論來逐步逼近求解取得了重要的理論和應用成果［5－8］.

Bertsekas等在1997年提出了一個仿真優(yōu)化Rollout算法［9－10］.它有兩個優(yōu)點：一是Rollout算法新策略即能通過離線仿真也可通過在線計算得到，并且比TD學習和Q學習優(yōu)化波動小.二是rollout算法有較強的并行性，更容易在多核系統(tǒng)或計算機集群上并行求解.從這兩點來，rollout算法更具有實際可操作性.文獻［11－12］發(fā)展了MDP性能勢的相關理論，為MDP性能分析和優(yōu)化提供了新的理論框架，產生許多基于理論計算或仿真的優(yōu)化算法［13－14］，性能勢既能通過泊松方程求解得到，也能通過一條樣本軌道仿真學習得到，它因而能和Rollout算法很好地結合.

1 多Agent MDPs模型

定義1 Markov對策.Markov對策（MG）通常有5元組構成.其中n表示多個Agent的數(shù)量.X表示Agent的狀態(tài)集合.Ai表示Agent的行動集合.P表示Agent的狀態(tài)轉移概率函數(shù).fi表示Agenti的立即報酬代價函數(shù)X×A→f.

在單Agent MDPs中，時間t下，Q學習更新公式為

其中，αt為學習步長，可為常數(shù)或衰減步長，γ為折扣因子.

由于單Agent無需考慮與其他Agent通信，其本質上就是經典的馬爾科夫決策過程.而多Agent需要所有Agent互相協(xié)作完成整個問題的求解，多Agent學習后Q值更新公式為

∈A定義為Agenti可選的行動集合，A為所有Agent的聯(lián)合行動空間，A＝A1×A2×…×An.定義為Agenti在狀態(tài)中選擇某種Nash平衡下的值函數(shù)，其算法有Minimax－Q、FFQ、Nash－Q及CE－Q學習等.

定義2 性能勢.性能勢理論為MDP的優(yōu)化提供了一個統(tǒng)一的框架，運用性能勢理論，從泊松方程入手，可以在較少的假設條件下建立起MDP基于性能勢的最優(yōu)性原理和最優(yōu)性方程，且容易證明其最優(yōu)解的存在性定理.另一方面性能勢也可以定義在一條樣本軌道上，在系統(tǒng)模型未知的問題中可以建立基于樣本軌道的仿真和在線優(yōu)化算法.文獻［12］中給出了性能勢理論，Agenti在狀態(tài)x下的性能勢為

2 基于rollout思想的多Agent學習算法

在單Agent的Q學習算法中，更新Q值原則是按照最優(yōu)行動集合時的折扣累計代價值，而Rollout算法是建立一個初始策略v0，通過rollout產生更新策略v1，更新策略比初始策略更能接近Nash最優(yōu)平衡解.文獻［6］中，在性能勢理論框架下給出了rollout算法.基于此，Rollout算法Q值更新公式為

將rollout算法推廣到多Agent學習中得到如下算法1.

算法1 Multi－Agent rollout algorithms for Agenti

Step1：初始策略v0，精度ε；Step2：對于Agenti，由初始策略v0仿真學習得到性能勢和平均代價對于狀態(tài)x∈X，隨機選擇一個行動a∈Ai，通過狀態(tài)轉移概率仿真下一個狀態(tài)x′，計算求得狀態(tài)x所有行動a的按下式計算

作為狀態(tài)x的更新行動，這樣構成新策略v1；Step4：如果達到收斂條件，算法結束；否則令v0＝v1，轉step2.v1（x）表示在x狀態(tài)在所有Agent的Nash平衡解下對應的更新策略，Nash平衡解可利用多AgentQ學習得到，例如使用極小極大學習的計算公式為

算法1中，由v0得到的性能勢gv0結果，需要建立狀態(tài)與性能勢的一一對應數(shù)據(jù)表格，當系統(tǒng)狀態(tài)空間很大時，易造成“維數(shù)災”.我們可以利用神經元動態(tài)規(guī)劃方法，用一條神經網(wǎng)絡來近似逼近性能勢.此時計算機保存是神經元網(wǎng)絡的逼近結構，而不是狀態(tài)和性能勢的一一對應關系，從而加快算法的執(zhí)行效率.

當Agent數(shù)量過大或每個Agent的狀態(tài)空間過多時，可能需要花費很長的時間才能獲得滿意的解，這對于那些實時性要求高的系統(tǒng)有很大局限.我們可以設計并行算法來加快學習收斂速度，真正地降低算法的執(zhí)行時間.并行算法的設計一般從串行算法入手，尋找可并行部分，包括劃分、計算、同步等階段［15］.多Agent rollout算法可并行部分有：多個Agent學習、Agent的行動集合、Agent的狀態(tài)集及Nash平衡解的計算等.此外，若用神經元網(wǎng)絡逼近性能勢，神經網(wǎng)絡劃分等也可以采用并行算法.

本文采用劃分行動集合的并行思想，即每個處理節(jié)點只初始化和更新某些行動集合，利用消息傳遞接口框架（Message Passing Interface，MPI）建立并行算法如算法2.

算法2 Multi－Agent parallel rollout algorithms for Agenti.Step1：（劃分階段）假設有H個處理節(jié)點，將候選的行動集合D（i）劃分H個子集｛U1，U2，…，UH｝節(jié)點i只處理Uh；Step2：（計算階段）按照算法1，計算狀態(tài)－行動對進行全收集操作，將每個處理節(jié)點中收集起來；Step4：（計算階段）按照算法1的公式（6）計算v1（x），并將v1（x）廣播（MPI＿Bcast）到所有處理節(jié)點；Step5：若滿足終止條件，結束算法；否則轉Step2.算法2的Step3中，MPI＿ALLgather和MPI＿Bcast為MPI中定義的標準函數(shù)，前者表示把各個處理節(jié)點中某個變量全收集到每個處理節(jié)點中，后者含義是將某個變量廣播到所有處理節(jié)點中［15］.

衡量算法2性能需考慮并行加速比和執(zhí)行效率.并行加速比＝并行執(zhí)行總時間／串行計算時間，執(zhí)行效率為并行加速比／處理節(jié)點數(shù).并行加速比越高，表明并行計算獲得性能提升越好；執(zhí)行效率越高，表明

算法1中，由v0得到的性能勢gv0結果，需要建立狀態(tài)與性能勢的一一對應數(shù)據(jù)表格，當系統(tǒng)狀態(tài)空間很大時，易造成“維數(shù)災”.我們可以利用神經元動態(tài)規(guī)劃方法，用一條神經網(wǎng)絡來近似逼近性能勢.此時計算機保存是神經元網(wǎng)絡的逼近結構，而不是狀態(tài)和性能勢的一一對應關系，從而加快算法的執(zhí)行效率.

當Agent數(shù)量過大或每個Agent的狀態(tài)空間過多時，可能需要花費很長的時間才能獲得滿意的解，這對于那些實時性要求高的系統(tǒng)有很大局限.我們可以設計并行算法來加快學習收斂速度，真正地降低算法的執(zhí)行時間.并行算法的設計一般從串行算法入手，尋找可并行部分，包括劃分、計算、同步等階段［15］.多Agent rollout算法可并行部分有：多個Agent學習、Agent的行動集合、Agent的狀態(tài)集及Nash平衡解的計算等.此外，若用神經元網(wǎng)絡逼近性能勢，神經網(wǎng)絡劃分等也可以采用并行算法.

本文采用劃分行動集合的并行思想，即每個處理節(jié)點只初始化和更新某些行動集合，利用消息傳遞接口框架（Message Passing Interface，MPI）建立并行算法如算法2.

算法2 Multi－Agent parallel rollout algorithms for Agenti.Step1：（劃分階段）假設有H個處理節(jié)點，將候選的行動集合D（i）劃分H個子集｛U1，U2，…，UH｝節(jié)點i只處理Uh；Step2：（計算階段）按照算法處理節(jié)點的使用率越高.

3 實例求解

考慮一個多級倉庫商品庫存控制問題，把每級倉庫看出一個Agent，多級倉庫商品庫存控制構成了一個典型的多Agent MDPs.

實例1：假設一種商品的倉庫共有兩級，商品需求量符合λ＝4的泊松分布，兩級倉庫商品的單位定購費均為10，庫存費為10，缺貨損失費為20，第1級倉庫總容量為20，第2級倉庫總容量為16.該多Agent系統(tǒng)的狀態(tài)數(shù)量為21×17＝357個.

因為這兩級倉庫是純團隊合作的關系，即若每級倉庫利益最大化，那么兩級倉庫也能達到最大整體利益，團隊Q值更新公式為

利用（9）更新公式求解上例，得到結果如表1.由表1可知，進行6次迭代后，實驗結果依然保持不變，這表明實驗結果已收斂.agenti＝1時，rollout算法運行實驗結果如圖1所示.

圖1 算法1求解例1迭代結果（Agent i＝1）

表1 算法1求解例1結果

實例2：為驗證Rollout算法的并行效果，考慮一個狀態(tài)集合較多庫存問題.假設5級倉庫，每級倉庫容量均為6，各級倉庫商品的庫存費用Cb＝｛5，3，4，2，3｝，缺貨損失費用Cl＝｛6，8，7，8，9｝，定購費用Cd＝｛2，3，5，3，6｝，需求量分布為：λ1＝2，λ2＝3，λ3＝1，λ4＝2，λ5＝3泊松分布，系統(tǒng)狀態(tài)為16 807個.

若使用Q學習算法求解該例，在計算機中保存的是Q因子（狀態(tài)－行動對），由于狀態(tài)集合很大，往往會出現(xiàn)“維數(shù)災”，導致問題不可解.而使用rollout算法，利用性能勢理論，借助于神經元動態(tài)規(guī)劃的泛化能力，將性能勢的計算從高維空間映射到低維空間，從而節(jié)約存貯空間，在上例中可使用28×15×1BP神經網(wǎng)絡逼近性能勢，二值化后，28×15×1網(wǎng)絡結構最多可表示16384個狀態(tài)，而28×15×1網(wǎng)絡結構只有435個權值，這樣大大減少了內存的消耗.令迭代次數(shù)為20，在MPIICH2－1.0.5環(huán)境，CPU為雙至強E5620（8個處理節(jié)點）的高性能服務器下，使用并行處理算法2得到的實驗結果如表2所示.由表2還可以看出，當庫存控制狀態(tài)數(shù)增大時，并行執(zhí)行效率總體是趨優(yōu)的.

表2 算法2求解例2的實驗結果

4 結論

Rollout算法是一個很好的逼近最優(yōu)解算法.在多Agent學習中，在性能勢的框架里運用Rollout算法，使用神經元網(wǎng)絡逼近性能勢，既可以解決模型未知的情況克服“建模難”的問題，也可以大大減少多A－gent學習程序對空間的需求，從而克服“維數(shù)災”的問題.同時，由于Rollout算法比其他仿真算法具有更強的內在并行性，在rollout算法基礎上進行多Agent學習，具有良好的可行性和有效性.

由于多Agent學習重要的一點是如何計算和選擇平衡解的問題.在本文中，利用已有多Agent Q學習的求平衡解算法，如何在性能勢的框架內，利用rollout算法本身的特點建立更優(yōu)秀算法是下一步所要考慮的問題.

［1］ Littman M.Markov games as a framework for multi－Agent reinforcement learning［C］//Proceedings of the Eleventh International Conference on Machine Learning.San.Francisco：Morgan Kaufmann Publishers，1994：157－163.

［2］ Littman M.Friend or foe Q－learning in general－sum Markov games［C］//Proceedings of Eighteenth International Conference on Machine Learning.Williams，College，MA，San Mateo，CA：Morgan Kaufmann Publishers，2001：322－328.

［3］ Hu J，Wellman M.Nash Q－learning for general－sum stochastic games［J］.Machine Learning Research，2003，4：1 039－1 069.

［4］ Greenwald A，Hall K.Correlated Q－learning［C］//Proceedings of the Twentieth International Conference on Machine Learning.Washington DC，USA：AAAI Press，2003：242－249.

［5］ 殷保群，奚宏生，周亞平.排隊系統(tǒng)性能分析與Markov控制過程［M］.合肥：中國科學技術大學出版社，2004.

［6］ 李豹，程文娟，周雷，等.rollout及其并行求解算法在多類商品庫存控制中的應用［J］.系統(tǒng)仿真學報，2007，19（17）：3 883－3 887.

［7］ Bertsekas D P.Dynamic Programming and Optimal Control，Vol.Ⅱ，4th Edition：Approximate Dynamic Programming［M］.Belmont：MA，Athena Scientific，2012.

［8］ Sutton R S，Barto A G.Reinforcement learning：an introduction［M］.Cambridge：MA，MIT Press，1998.

［9］ Bertsekas D P，Tsitsiklis J N，Wu C.Rollout algorithms for combinatorial optimization［J］.Heuristics，1997，3：245－262.

［10］Bertsekas D P.Rollout Algorithms for Discrete Optimization：A Survey［C］//Handbook of Combinatorial Optimization.Berlin：springer，2005：2 989－3 014.

［11］Li X，Cao X R.Performance optimization of queueing systems with perturbation realization［J］.European Journal of Operations Research，2012，218（2）：293－304.

［12］Cao X R.Stochastic Learning and Optimization－A Sensitivity－Based Approach［M］.New York：Springer，2007.

［13］Cao X R，Wang D X，Lu T，et al.Stochastic Control via Direct Comparison［J］.Discrete Event Dynamic Systems：Theory and Applications，2011，21：11－38.

［14］Yin B Q，Lu S，Guo D.Analysis of Admission Control in P2P－Based Media Delivery Network Based on POMDP［J］.International Journal of Innovative Computing，Information and Control，2011，7（7B）：4 411－4 422.

［15］陳國良.并行算法的設計與分析［M］.北京：高等教育出版社，2009.