多Agent MDPs中并行Rollout學習算法

李 豹

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

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

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

1 多Agent MDPs模型

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

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

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

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

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

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

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

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

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

算法1 Multi－Agent rollout algorithms for Agenti

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

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

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

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

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

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

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

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

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

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

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

3 實例求解

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

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

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

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

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

表1 算法1求解例1結果

實例2：為驗證Rollout算法的并行效果，考慮一個狀態集合較多庫存問題.假設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泊松分布，系統狀態為16 807個.

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

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

4 結論

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

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

［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］ 殷保群，奚宏生，周亞平.排隊系統性能分析與Markov控制過程［M］.合肥：中國科學技術大學出版社，2004.

［6］ 李豹，程文娟，周雷，等.rollout及其并行求解算法在多類商品庫存控制中的應用［J］.系統仿真學報，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.