大數據環境下的增強學習綜述*

仵 博，馮延蓬，孟憲軍，江建舉，何國坤

（深圳職業技術學院 教育技術與信息中心，廣東 深圳 518055）

增強學習（Reinforcement Learning，簡稱RL）是一種有效的最優控制學習方法，實現系統在模型復雜或者不確定等條件下基于數據驅動的多階段優化學習控制，是近年來一個涉及機器學習、控制理論和運籌學等多個學科的交叉研究方向．增強學習因其具有較強的在線自適應性和對復雜系統的自學能力，使其在機器人導航、非線性控制、復雜問題求解等領域得到成功應用[1-4]．

經典增強學習算法按照是否基于模型分類，可分為基于模型（Model-based）和模型自由（Model-free）兩類．基于模型的有TD學習、Q學習、SARSA和ACTOR-CRITIC等算法．模型自由的有DYNA-Q和優先掃除等算法．以上經典增強學習算法在理論上證明了算法的收斂性，然而，在實際的應用領域，特別是在大數據環境下，學習的參數個數很多，是一個典型的NP難問題，難以最優化探索和利用兩者之間的平衡[5-8]．因此，經典增強學習算法只在理論上有效．

為此，近年來的增強學習研究主要集中在減少學習參數數量、避免后驗分布全采樣和最小化探索次數等方面，達到算法快速收斂的目的，實現探索和利用兩者之間的最優化平衡．當前現有算法按照類型可分為五類：1）抽象增強學習；2）可分解增強學習；3）分層增強學習；4）關系增強學習；5）貝葉斯增強學習．

1 抽象增強學習

抽象增強學習（Abstraction Reinforcement Learning，簡稱 ARL）的核心思想是忽略掉狀態向量中與當前決策不相關的特征，只考慮那些有關的或重要的因素，達到壓縮狀態空間的效果[9]．該類算法可以在一定程度上緩解“維數災”問題．狀態抽象原理如圖1所示．

目前，狀態抽象方法有狀態聚類、值函數逼近和自動狀態抽象等方法．函數逼近方法難于確保增強學習算法能夠收斂，采用線性擬合和神經網絡等混合方法來實現函數逼近是當前的研究熱點和方向．狀態聚類利用智能體狀態空間中存在的對稱性來壓縮狀態空間，實現狀態聚類．自動狀態抽象增強學習方法利用 U-樹自動地由先驗知識推理出狀態抽象，是狀態抽象增強學習研究的方向之一．以上算法都在一定程度上緩解了增強學習中大規模狀態造成算法無法收斂的問題，但是存在以下缺點：1）增強學習的績效依賴于狀態抽象方法對狀態空間的劃分，如何合理劃分子空間是狀態抽象增強學習面臨的難題．如果空間劃分過粗，難以實現增強學習算法的快速收斂；而如果空間劃分過細，則會喪失泛化能力．2）狀態抽象方法與特定問題表示相關，缺少統一的理論框架，阻礙了狀態抽象增強學習的廣泛應用．

圖1 狀態抽象原理示意圖

圖2 可分解原理示意圖

2 可分解增強學習

可分解增強學習（Factored Reinforcement Learning，簡稱 FRL）是一種對狀態轉移函數和報酬函數進行壓縮表示的增強學習方法[10]．該方法的核心思想是首先利用動態貝葉斯網絡的條件獨立特性和上下文獨立特性將狀態轉移函數和報酬函數進行可分解描述，將離散的概率分布函數轉化成決策樹來表示，達到將大規模指數級的狀態空間壓縮到多項式級別的狀態空間的目的，然后采用決策論回歸方法對決策樹進行學習，可分解原理如圖2所示．

可分解增強學習的思想來源于Boutilier等人在2000年發表在《Artificial Intelligence》上的論文，該論文指出采用可分解表示方法可以將高維狀態空間壓縮為低維可求解空間，并詳細介紹可分解的理論和方法，以及結構化動態規劃（Structured Dynamic Programming，簡稱SDP）算法，為可分解增強學習奠定了理論基礎．更進一步，Guestrin等人[11]提出結構化線性規劃（Structured Linear Programming，簡稱SLP）算法和可分解增強學習算法，實現了求解240～250規模的問題．

由于FRL極大地降低求解問題的規模，提供學習算法收斂速度，成為近年來的研究熱點．例如，Degris等人提出的SDYNA算法，Kroon等人提出的KWIK算法[12]，Kozloval等人提出的IMPSPITI算法和 TeXDYNA 算法[13]，Hester等人提出的RL-DT算法[14]，Szita等人提出的 FOIM 算法[15]，Vigorito等人針對狀態和動作連續情況下提出的OISL算法[16]0．

以上FRL算法相同之處是首先采用監督學習方法建立狀態轉移函數和報酬函數的可分解表示，然后根據觀察結果，采用不同的方法來更新狀態轉移函數模型和報酬函數模型．因此，如何建立應用對象的可分解泛化表示，減少學習的參數個數，提高在后驗分布采樣算法的性能是目前研究的難點．

3 分層增強學習

分層增強學習（Hierarchical Reinforcement Learning，簡稱HRL）實質上也是一種任務分層方法，其核心思想是將一個大規模難于求解的問題分解成若干個較小規模易于求解的問題[10]．該算法可以有效解決學習參數數量隨狀態變量維數成指數級增長這一“維數災”問題[17]．HRL任務分層方法可分為手工分層和自動分層，手工分層方法是根據智能體先驗知識采用手工方式來分解，自動任務分層方法是通過自動探索，自動發現和構造某種形式的層次結構．根據先驗知識，采用自動任務分層方法是目前HRL領域的研究熱點．HRL原理如圖3所示．

圖3 分層原理示意圖

由于HRL能夠有效降低求解問題的規模，成為當前增強學習研究的熱點和難點．在當前研究成果中，具有里程牌意義的算法為Option算法、HAMs算法和MAXQ算法．Option算法的任務分層其實是在大數據空間上探索子目標并構造Option的過程．HAMs算法通過引入有限狀態機概念，使之用于表達大數據空間中的區域策略．MAXQ算法的任務分層是在任務空間上構造多個子任務的過程，它直接從任務分層的角度來處理大數據模型，所有子任務構成一個任務圖．

近年來，國內外研究人員針對以上三個算法缺點，提出不少改進型 HRL算法．例如，Subramanian等人提出的 Human-Options方法[18]，Joshi等人[19]采用面向對象表示方法來構造HRL模型，利用特定領域知識進行動作選擇，以提高學習效果．Jong等人結合 Rmax算法和MAXQ算法的優點，提出一種混合型RMAXQ算法[20]．

以上算法在特定的實驗平臺和應用領域有效，但是面對如何劃分層次來保證HRL算法收斂的實時性和策略求解的最優性是目前的難題．

4 關系增強學習

人們在處理復雜領域的問題的時候，會很自然的使用關系的方法．關系增強學習（Relational Reinforcement Learning，簡稱RRL）是采用關系邏輯或圖結構等表示方法來描述環境[21]．當前RRL的研究主要以關系表示為基礎，考慮在關系表示上如何把握環境的不同狀態[22]．RRL在的優點在于：首先，它可以將在相似環境中的對象和已經學習到的知識泛化到不同的任務中；其次，使用關系表示也是一種比較自然的利用先驗知識（背景知識）的方式．目前比較常用的方法就是用一階邏輯形式擴展成關系先驗，或者擴展成能表達概率和效用的擴展邏輯行為語言[23,24]．

RRL利用關系邏輯的形式來描述復雜問題，利用先驗知識進行邏輯推理，符合人類的思維習慣．但是，從目前應用來看，RRL只在小規模特定問題有效，例如積木世界、十五子棋和一些小游戲中．如何實現RRL的泛化，如何在大規模動態不確定環境下進行邏輯推理是RRL領域中的難題．

5 貝葉斯增強學習

貝葉斯增強學習（Bayesian Reinforcement Learning，簡稱 BRL）利用模型先驗知識對未知模型參數建模，然后根據觀察數據對未知模型參數的后驗分布進行更新，最后根據后驗分布進行規劃，以期最大化期望報酬值[25]．由于 BRL為最優化探索和利用之間的平衡提供一種完美的解決方案，得到廣泛關注，成為當前RL領域研究的熱點．RRL原理如圖4所示．

BRL可分為模型自由[26]和基于模型[27]兩類．模型自由增強學習算法直接學習最優策略和最優值函數，需求太多的探索，造成算法收斂速度慢，無法實現在線學習．同時，在實際的應用領域狀態轉移函數往往會丟失數據，造成算法的失真．基于模型的增強學習利用先驗知識緩和數據丟失，加速算法收斂，減少探索次數，能夠最優化平衡探索和利用二者之間的關系．但是，基于模型的增強學習計算量大，使其無法實現在線學習．為此，如何有效降低未知參數個數，提高在高維后驗概率分布上規劃的效率是目前增強學習的難題．

圖4 貝葉斯增強學習原理示意圖

6 結 論

在大數據中進行機器學習，特別是增強學習，是當前大數據基礎研究的熱點和難點，也是推進大數據應用的關鍵．規模巨大的數據是增強學習的瓶頸，針對于此，本文研究了當前五類增強學習方法，并指出它們的優勢和缺點．大數據的關鍵在于應用，選用何種增強學習方法需要根據特定的應用而定．當前，在大數據應用領域，將監督學習或半監督學習與增強學習相結合是一條有效的方法．

[1] Silver D, Sutton R, Müller M. Temporal-difference search in computer Go[J]．Machine Learning, 2012，87：183-219．

[2] 徐昕，沈棟，高巖青，等．基于馬氏決策過程模型的動態系統學習控制：研究前沿與展望[J]．自動化學報，2012，38（5）：673-687．

[3] Wang F Y, Jin N, Liu D R, et al. Adaptive dynamic programming for finite horizon optimal control of discrete time nonlinear systems with ?-error bound[J]．IEEE Transactions on Neural Networks,2011，22（1）：24-36．

[4] Hafner R, Riedmiller M. Reinforcement learning in feedback control: challenges and benchmarks from technical process control[J]．Machine Learning,2011，84：137-169．

[5] Choi J, Kim K E. Inverse reinforcement learning in partially observable environments[J]．Journal of Machine Learning Research, 2011，12：691-730．

[6] Meltzoff, A N, Kuhl, P K, Movellan J, et al. Foundations for a new science of learning[J]．Science, 2009，325：284-288．

[7] Kovacs T, Egginton R. On the analysis and design of software for reinforcement learning with a survey of existing systems[J]．Machine Learning, 2011，84：7-49．

[8] Doshi-Velez F, Pineau J, Roy N. Reinforcement learning with limited reinforcement: Using Bayes risk for active learning in POMDPs[J]．Artificial Intelligence,2012，1870-188：115-132．

[9] Frommberger L, Wolter D. Structural knowledge transfer by spatial abstraction for reinforcement learning agents[J]．Adaptive Behavior, 2010，18（6）：531-539．

[10] Kozlova O. Hierarchical & Factored reinforcement learning[D]．Paris: Université Pierre et Marie Curie, 2010．

[11] Guestrin C, Koller D, Parr R, et al. Efficient solution algorithms for factored MDPs[J]．Journal of Artificial Intelligence Research, 2003，19：399-468．

[12] Kroon M, Whiteson S. Automatic feature selection for model-based reinforcement learning in factored MDPs[C]//Wani M A, Kantardzic M M, Palade V, et al.Proceedings of 2009 International Conference on Machine Learning and Applications. Washington, DC:IEEE Press, 2009：324-330．

[13] Kozloval O, Sigaud O, Wuillemin P H, et al. Considering unseen states as impossible in factored reinforcement learning[C]//Buntine W. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases: Part I. Berlin:Springer-Verlag, 2009：721-735．

[14] Hester T, Stone P. Generalized model learning for reinforcement learning in factored domains[C]//Decker K, Sichman J, Sierra C, et al. The Eighth International Conference on Autonomous Agents and Multiagent Systems. Richland, SC: IFAAMS, 2009：10-15．

[15] Szita I, Lorincz A. Optimistic initialization and greediness lead to polynomial time learning in factored MDPs[C]//Wani M A, Kantardzic M M, Palade V, et al.Proceedings of 2009 International Conference on Machine Learning and Applications. Washington, DC:IEEE Press, 2009：1001-1008．

[16] Vigorito C M, Barto A G. Incremental structure learning in factored MDPs with continuous states and actions[R]．Amherst: University of Massachusetts Amherst,2009．

[17] 杜小勤，李慶華，韓建軍．HAMs體系中的同態變換方法研究[J]．小型微型計算機系統，2008，29（11）：2075-2082．

[18] Subramanian K, Isbell C, Thomaz A. Learning options through human interaction[C]//Beal J, Knox W B.Proceedings of 2011 IJCAI Workshop on Agents Learning Interactively from Human Teachers. Palo Alto: AAAI Press, 2011：39-45．

[19] Joshi M, Khobragade R, Sarda S. Hierarchical action selection for reinforcement learning in infinite Mario[C]//Kersting K, Toussaint M. The Sixth Starting Artificial Intelligence Research Symposium.Lansdale, PA: IOS Press, 2012：162-167．

[20] Jong N K, Stone P. Hierarchical model-based reinforcement learning: Rmax+MAXQ[C]//McCallum A, Roweis S. Proceedings of the Twenty-Fifth International Conference on Machine Learning. Madison, Wisconsin: ACM Press, 2008：432-439．

[21] Liu Q，Gao Y，Chen D X，et al. A Heuristic Contour Prolog List Method Used in Logical Reinforcement Learning[J]．Journal of Information & Computational Science, 2008，5（5）：2001-2007．

[22] Song Z W, Chen X P, Cong S. Agent learning in relational domains based on logical MDPs with negation[J]．Journal of Computers, 2008，3（9）：29-38．

[23] Sanner S, Kersting K. Symbolic Dynamic Programming for First-order POMDPs[C]//Fox M, Poole D.Proceeding of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10). Atlanta: AAAI Press,2010：1140-1146．

[24] 劉全，周文云，李志濤．關系強化學習方法的初步研究[J]．計算機應用與軟件，2010，27（2）：40-43．

[25] Ghavamzadeh M, Engel Y. Bayesian actor-critic algorithms[C]//Ghahramani, Z. Proceedings of the 24thInternational Conference on Machine Learning. New York: ACM Press, 2007：297-304．

[26] Poupart P, Vlassis N. Model-based Bayesian reinforcement learning in partially observable domains [C] //Padgham L, ParkesD. Proceedings of the International Joint Conference on Autonomous Agents and Multi Agent Systems. New York: ACM Press, 2008：1025-1032．

[27] Ross S, Pineau J, Chaib-draa B, et al. A Bayesian approach for learning and planning in partially observable Markov decision processes[J]．Journal of Machine Learning Research, 2011，12：1729-1770．