分層強化學習研究進展

摘要：首先介紹了半馬爾可夫決策過程、分層與抽象等分層強化學習的理論基礎；其次，較全面地比較HAM、options、MAXQ和HEXQ四種典型的學習方法，從典型學習方法的拓展、學習分層、部分感知馬爾可夫決策過程、并發和多agent合作等方面討論分層強化學習的研究現狀；最后指出分層強化學習未來的發展方向。

關鍵詞：分層強化學習； 半馬爾可夫決策過程； 抽象

中圖分類號：TP18文獻標志碼：A

文章編號：1001－3695(2008)04－0974－05

強化學習（reinforcement learning，RL）[1]是指agent通過與環境的直接交互，學習狀態到行為的映射策略，以使agent行為從環境中獲得最大的累積獎賞值。由于RL具有在線自學習等特點，目前已經成為機器學習研究中活躍的領域之一[1，2]。但是，經典RL常采用狀態—動作表來表示行為策略，當問題規模較大時，不可避免地會出現耗時、維數災難等問題。因此，經典RL不適合大規模問題的學習。

解決RL存在問題的主要途徑有函數逼近和任務分層等方法[3，4]。但是，如果函數逼近方法中的泛化偏置與問題不匹配，將導致收斂速度很慢，甚至不能正確收斂[3， 5]。與函數逼近方法不同，分層強化學習（HRL）引入抽象機制（動作抽象和狀態抽象）。建立在合理抽象機制上的HRL能簡化問題的狀態、動作和目標結構，減少存儲要求和計算量，加快學習速度，因而能解決大規模問題的學習[4]。近年來，HRL吸引了許多學者的注意，成為機器學習研究領域的熱點之一。

1從MDP到SMDP

經典RL采用馬爾可夫決策過程（Markov decision process，MDP）[3，5]來建模。

定義1MDP可定義為一個四元組〈S，A，P，R〉。其中：S為環境狀態集合；A為agent執行的動作集合；P:S×A×S→[0，1]為狀態轉換概率函數，記為p(s′|s，a)；R:S×A→IR為獎賞函數（IR為實數集），記為r(s，a)。

定義5安全狀態抽象是指值函數在抽象前后保持一致的狀態抽象。

從表1可以看到，雖然四種典型學習方法都是以SMDP為理論基礎，通過引入動作抽象機制，將MDP轉換為SMDP問題，但與僅轉換為單個SMDP的HAM和options方法不同，MAXQ和HEXQ方法創建了多個SMDP的分層，并使每個SMDP同時學習。

在HRL中，學習速度與策略最終優化程度往往是一對矛盾。雖然分層學習能大大減少學習時間，但是由于設計者對原MDP問題強制性地增加了任務分層約束，限制了策略的搜索空間，使得尋找全局最優策略變得比較困難。因此在HRL中人們往往放寬了對策略最終優化程度的要求，所追求的不再是全局最優，而是次最優，即在某種意義上最優。例如，HAM、options和HEXQ方法一般收斂到與任務分層結構兼容的分層最優；MAXQ方法則一般收斂到更弱的遞歸最優。

另一對矛盾是策略最終優化程度與狀態抽象、子任務策略重用。Dietterich[10]在MAXQ方法中分別定義了最大節點無關性、葉子節點無關性、結果分布無關性、終止和屏蔽五個安全狀態抽象條件，并證明了在使用安全狀態抽象情況下MQXQ Q－學習算法也能以概率1收斂到遞歸最優策略。因此，盡管在一般情況下MAXQ方法只能收斂到較弱的遞歸最優，但由于隔離了子任務環境，允許使用安全狀態抽象，并使子任務策略在不同應用環境中可重用。另一方面，能收斂到分層最優的HRL方法在子任務中通常不能使用狀態抽象，也不能共享子任務的策略，Parr和Sutton對此無不表示遺憾。但是，HEXQ方法比較特殊，它既可收斂到分層最優，又可自動進行狀態抽象和子任務策略重用。

自動分層是HAM、options和MAXQ方法懸而未決的問題。由于這些方法的分層結構都是由設計者事先給出，很顯然，算法所搜索的策略優化程度取決于設計者先驗知識等因素。因此，自動分層顯得尤為重要。正如Dietterich[10]所說：“A key open question is how to form task hierarchies automatically。”HEXQ方法較好地解決了這個問題，使得子任務生成、子任務交互和子任務抽象等分層工作都由算法自動完成，但它只適用于可分解的MDP問題。

4HRL的研究現狀

典型HRL方法都存在以下局限：a)除了HEXQ方法以外，其余三種方法的任務分層結構都是設計者給定的；b)假定agent能完全感知到環境狀態信息；c)學習的策略限于agent動作的順序組合；d)只考慮單agent的情況。針對這些不足，當前HRL研究者主要圍繞典型方法的拓展、自動分層、部分感知馬爾可夫決策過程、并發活動以及多agent合作等方面開展研究。

4．1典型方法的拓展

Andre等人[12]在LISP語言基礎上，提出了ALISP語言，并將其引入到HAM方法中，形成可編程（可規劃）的HAM，即PHAM。他們借助MAXQ值函數分解思想，進一步研究了既可進行安全狀態抽象，又可保留分層最優的PHAM改進方法[13]。與MAXQ值函數的兩部分分解機制不同，這種改進的PHAM使用了三部分的分解機制，即增加了當前子任務以外的期望回報函數部分。但是，值函數的三部分分解機制存在一個問題：當前子任務以外的回報函數部分依賴于狀態變量數量。因此，這種方法不適用于具有許多狀態變量的應用。為此，Marthi等人[14]巧妙地用其他兩部分函數來表示這部分函數，使其在保留分層最優特征的同時又進一步提高了狀態抽象水平。

為使HEXQ的安全狀態抽象機制能應用于無限、有折扣的MDP中，Hengst[15~17]在該算法的值函數中引入一個附加的折扣函數，而且他又進一步在算法中加入限制策略搜索深度、限制出口狀態數量以及合并出口三條啟發式規則，使算法的學習時間和存儲要求都有明顯減少，但該方法沒有提供任何最優保證。在HEXQ方法中，分層結構一旦創建后就不可更改，因此動態適應性較差。為此，Potts等人[18]用自修補方法允許各分層并發創建，通過實驗證明了這種改進方法的健壯性得到明顯的改善。

4．2自動分層

自動分層主要研究子任務自動發現以及子任務自動抽象等內容，是當前HRL研究的熱點之一。

目前子任務自動發現大致包括以下幾種方法：a)通過識別有用的子目標，定義用于完成有用子目標的抽象動作。可作為有用子目標的特征主要有高頻訪問或高回報梯度的狀態[19]、在成功軌跡上高頻訪問的狀態區域[20]、高密集連接的區域之間的狀態集[21，22]。Asadi和Huber[23，24]則通過分析事先學到的策略來發現子目標。b)允許agent在環境中漫游，以發現狀態聚類，然后在此基礎上定義options[25]。c)在可分解狀態空間用HEXQ創建子任務；用動態貝葉斯網絡（dynamic Bayesian network，DBN）[26]確定狀態變量的因果關系，然后引入分層options[27]。除了以上方法外，Elfwing[28]結合遺傳算法和MAXQ方法，提出了一種分層學習的進化方法；Bakker等人[29]則提出了由高層分派子目標到低層，低層學習指定子目標策略的自動分層算法。

子任務自動抽象主要包括連續U樹[5，30]、T樹[5]、結構抽象[31]和模型最小化[32]等方法。U樹方法通過重新離散化命題狀態空間進行狀態抽象，開始時將環境視為單一的抽象狀態，然后進行遞歸分裂。連續U樹方法是對U樹方法的擴展，能處理連續狀態空間的狀態抽象。T樹方法則將連續U樹方法應用到SMDP中，以增加抽象狀態的解析度。Fitch等人[31]研究了對稱性等幾種類型的結構抽象；Asadi和Huber[32]擴展了e約簡的最小化模型，并將其應用到MDP中創建抽象狀態。

圖形模型框架也為自動抽象提供了強有力的方法。例如，Bui等人[33]提出的抽象隱藏馬爾可夫模型就是一種分層圖形模型，這種模型能對抽象策略進行編碼；Manfredi等人[34]給出了一種用圖形模型進行狀態抽象和策略抽象的兩階段學習方法。

4．3分層的部分感知馬爾可夫決策過程

不確定性的順序決策問題大多采用部分感知馬爾可夫決策過程（partially observable MDP，POMDP）[35]來解決。在POMDP中狀態被隱藏，agent僅通過觀測值來估計潛在的狀態。但是，目前絕大部分POMDP工作局限于未分層模型，不適合于大規模問題。為此，研究人員將分層機制應用于POMDP中，形成分層的部分感知馬爾可夫決策方法（hierarchical POMDP，HPOMDP）。

Hernandez等人[36]將前綴樹模型泛化到抽象動作，提出了分層的短期存儲方法（hierarchical short－term memory，HSM）。HSM從存儲的觀察值—動作—回報序列中構造狀態估計器，而序列長度是可變的。HSM的不足之處是缺乏強有力的理論支持。Theocharous等人[37]對分層隱藏的馬爾可夫模型（hierarchical hidden Markov model，HHMM）進行擴展，提出了一種HPOMDP方法。他們開發了分層EM推理算法，從觀察值和動作序列中學習模型參數。測試表明這種方法的學習和規劃性能都比POMDP好[38]。但是，EM推理算法的時間復雜度為O(ST3)（其中：S是潛在的狀態集；T是序列長度），這使得對于長數據序列的模型訓練非常困難。為此，Theocharous等人[26]采用DBNs來表示這種HPOMDP，推理算法的時間復雜度則由O(ST3)變為O(S1．5T)。這就允許agent能更快地學習長數據序列的模型參數，且無須對訓練數據進行手工分割。

上面介紹的方法適用于agent通信是免費的情形。Ghavamzadeh等人[41]將這種方法進行擴展，增加通信決策功能，使其適用于非免費通信的問題。此外，Mehta等人[42]研究了另一種相似的方法。所不同的是他們的方法允許多個agent共享分層值函數，且學習算法是基于平均回報而非基于折扣回報的。

5結束語

學習時間和維數災難等缺陷限制了RL在大規模學習問題上的應用，引入分層機制是擺脫這種困境的一種有效手段。盡管HRL在近年來的研究中已經取得了不少成果，但仍然面臨著許多挑戰。筆者認為，除了以上所討論的研究方向外，下面三個方面也將成為HRL重要的研究內容。

a)問題的表示和抽象。問題表示和抽象是HRL的關鍵部分，決定了搜索空間的大小和拓撲結構，從而影響學習速度和能力。因此，簡化的問題表示和提高抽象程度是HRL研究永恒的話題。

b)分層策略的直接搜索方法。目前，解決MDP問題的大多數方法都是先計算最佳值函數，然后從中抽取最優策略。與值函數方法相比，分層策略的直接搜索方法更方便連續空間以及POMDP問題的解決。引入分層機制的分層策略直接搜索方法也是HRL將來重要的研究內容之一。

c)大規模問題的應用。最近，已有HRL在大規模工程問題成功應用的相關報道。例如，Ghavamzadeh等人[41]將多agent－HRL應用于多車輛自動導航（AGV）問題；Li等人[43]將HRL應用于電梯群控優化問題。但是，由于HRL是一個相對新穎的研究領域，在大規模問題上的應用還比較少，如何快速、有效地應用這種技術也是將來面臨的挑戰之一。

參考文獻：

[1]高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，2004，30(1):86－100.

[2]FISCHER F， ROVATSOS M， WEISS G. Hierarchical reinforcement learning in communication－mediated multiagent coordination[C]//Proc of the 3rd International Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press， 2004.

[3]HENGST B. Discovering hierarchy in reinforcement learning[D]. Sydney: University of New South Wales， 2003.

[4]SKELLY M M. Hierarchical reinforcement learning with function approximation for adaptive control[D]. Ohio: Case Western Reserve University， 2004.

[5]UTHER W T B. Tree based hierarchical reinforcement learning[D]. Pittsburgh: Carnegie Mellon University， 2002.

[6]BELLMAN R E， DREYFUS S E. Applied dynamic programming[M]. New Jersey: Princeton University Press， 1962.

[7]WATKINS C， DAYAN P. Q－learning[J]. Machine Learning， 1992，8(3):279－292.

[8]PARR R. Hierarchical control and learning for Markov decision processes[D]. Berkeley， California: University of California， 1998.

[9]SUTTON R S， PRECUP D， SINGH S. Between MDPs and semi－MDPs a framework for temporal abstraction in reinforcement learning[J]. Artificial Intelligence， 1999，112(1):181－211.

[10]DIETTERICH T G. Hierarchical reinforcement learning with the MAXQ value function decomposition[J]. Journal of Artificial Intelligence Research， 2000，13(1):227－303.

[11]PRECUP D. Temporal abstraction in reinforcement learning[D]. Massachusetts: University of Massachusetts， 2000.

[12]ANDRE D， RUSSELL S J. Programmatic reinforcement learning agents[M]. Cambridge: MIT Press， 2001.

[13]ANDRE D. Programmable reinforcement learning agents[D]. Berkeley: University of California， 2003.

[14]MARTHI B， RUSSELL S. A compact， hierarchically optimal Q－function decomposition[C]//Proc of Conference on Uncertainty in Artificial Intelligence(UAI). Montreal: ACM Press， 2006.

[15]HENGST B.Safe state abstraction and discounting in hierarchical reinforcement learning[R]. Sydney: University of New South Wales， 2003.

[16]HENGST B. Variable resolution hierarchical RL[R]. Sydney: University of New South Wales， 2003.

[17]HENGST B. Model approximation for HEXQ hierarchical reinforcement learning[C]//Proc of the 15th European Conference on Machine Learning. Berlin: Springer－Verlag， 2004.

[18]POTTS D， HENGST B. Concurrent discovery of task hierarchies[C]//Proc of AAAI Spring Symposium on Knowledge Representation and Ontology for Autonomous Systems. San Jose: AAAI Press， 2004.

[19]STOLLE M， PRECUP D. Learning options in reinforcement learning[C]//Proc of the 5th International Symposium on Abstraction， Reformulation and Approximation. Alberta: AAAI Press， 2002.

[20]McGOVERN A. Autonomous discovery of temporal abstract from interaction with an environment[D]. Massachusetts: University of Massachusetts， 2002.

[21]SIMSEK O， BARTO A G. Using relative novelty to identify useful temporal abstractions in reinforcement learning[C]//Proc of the 21st International Conference on Machine Learning. New York: ACM Press， 2004.

[22]SIMSEK O， WOLFE A P， BARTO A G. Identifying useful subgoals in reinforcement learning by local graph partitioning[C]//Proc of the 22nd International Conference on Machine Learning. New York: ACM Press， 2005.

[23]ASADI M， HUBER M. Accelerating action dependent hierarchical reinforcement learning through autonomous subgoal discovery[C]//Proc of ICML’05 Workshop on Rich Representations for Reinforcement Learning. New York: ACM Press， 2005.

[24]ASADI M， HUBER M. Hierarchical state abstraction with sub－goal discovery using learned policies[C]//Proc of International Confe－rence on Machine Learning， Models， Technologies and Applications. Las Vegas: ACM Press， 2005.

[25]MANNOR S， MENACHE I， HOZE A， et al. Dynamic abstraction in reinforcement learning via clustering[C]//Proc of the 21st International Conference on Machine Learning. New York: ACM Press， 2004.

[26]THEOCHAROUS G， MURPHY K， KAELBLING L. Representing hierarchical POMDPs as DBNs for multi－scale robot localization[C]//Proc of IEEE Conference on Robotics and Automation. New Orleans: IEEE Press， 2004.

[27]JONSSON A， BARTO A G. A causal approach to hierarchical decomposition of factored MDPs[C]//Proc of the 22nd International Confe－rence on Machine Learning. New York: ACM Press， 2005.

[28]ELFWING S. An evolutionary approach to automatic construction of the structure in hierarchical reinforcement learning[D]. Stockholm: Royal Institute of Technology， 2003.

[29]BAKKER B， SCHMIDHUBER J. Hierarchical reinforcement learning based on subgoal discovery and subpolicy specialization[C]//Proc of the 8th Conference on Intelligent Autonomous Systems. Amsterdam: IOS Press， 2004.

[30]AU M， MAIRE F. Automatic state construction using decision tree for reinforcement learning agents[C]//Proc of International Conference on Intelligent Agents， Web Technologies and Internet Commerce(CIMCA). Gold Coast: IEEE Press， 2004.

[31]FITCH R， HENGST B， SUC D， et al. Structural abstraction experiments in reinforcement learning[C]//Proc of the 18th Australian Joint Conference on Artificial Intelligence. Sydney: Springer－Verlag， 2005.

[32]ASADI M， HUBER M. State space reduction for hierarchical reinforcement learning[C]//Proc of the 17th International FLAIRS Conference. Miami: AAAI Press， 2004.

[33]BUI H， VENKATESH S， WEST G. Policy recognition in the abstract hidden Markov model[J]. Journal of Artificial Intelligence Research， 2002，17(1):451－499.

[34]MANFREDI V， MAHADEVAN S. Hierarchical reinforcement lear－ning using graphical models[C]//Proc of ICML’05 Workshop on Rich Representations for Reinforcement Learning. New York: ACM Press， 2005.

[35]KAELBLING L P， LITTMAN M L， CASSANDRA A R. Planning and acting in partially observable stochastic domains[J]. Artificial Intelligence， 1998，101(1):99－134.

[36]HERNANDEZ N，MAHADEVAN S.Hierarchical memory－based rein－forcement learning[C]//Proc of Neural Information Processing Systems. Denver: MIT Press， 2001.

[37]THEOCHAROUS G， GOHANIMANESH K， MAHDEVAN S. Lear－ning hierarchical partially observable Markov decision process models for robot navigation[C]//Proc of IEEE International Conference on Robotics and Automation. Seoul: IEEE Press， 2001.

[38]THEOCHAROUS G. Hierarchical learning and planning in partially observable Markov decision process[D]. Michigan: Michigan State University， 2002.

[39]MARTHI B， LATHAM D， RUSSELL S， et al. Concurrent hierarchical reinforcement learning[C]//Proc of the 19th International Joint Conference on Artificial Intelligence. Edinburgh: IEEE Press， 2005.

[40]ROHANIMANESH K， MAHADEVAN S. Decision－theoretic planning with concurrent temporally extended actions[C]//Proc of the 17th Conference on Uncertainty in Artificial Intelligence. New York: ACM Press， 2001.

[41]GHAVAMZADEH M， MAHADEVAN S， MAKAR R. Hierarchical multiagent reinforcement learning[J]. Journal of Autonomous Agents and Multi－Agent Systems， 2006，13(2):197－229.

[42]MEHTA N， TADEPALLI P. Multi－agent shared hierarchy reinforcement learning[C]//Proc of ICML’05 Workshop on Rich Representations for Reinforcement Learning. New York: ACM Press， 2005.

[43]LI Wei， YE Qing－tai， ZHU Chang－ming. Application of hierarchical reinforcement learning in engineering domain[J]. Journal of Systems Science and Systems Engineering， 2005，14(2):207－217.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”