分層強化學習綜述

周文吉，俞揚

(南京大學 軟件新技術(shù)國家重點實驗室，江蘇 南京 210023)

分層強化學習綜述

周文吉，俞揚

(南京大學 軟件新技術(shù)國家重點實驗室，江蘇 南京 210023)

強化學習(reinforcement learning) 是機器學習和人工智能領(lǐng)域的重要分支，近年來受到社會各界和企業(yè)的廣泛關(guān)注。強化學習算法要解決的主要問題是，智能體如何直接與環(huán)境進行交互來學習策略。但是當狀態(tài)空間維度增加時，傳統(tǒng)的強化學習方法往往面臨著維度災(zāi)難，難以取得好的學習效果。分層強化學習(hierarchical reinforcement learning) 致力于將一個復(fù)雜的強化學習問題分解成幾個子問題并分別解決，可以取得比直接解決整個問題更好的效果。分層強化學習是解決大規(guī)模強化學習問題的潛在途徑，然而其受到的關(guān)注不高。本文將介紹和回顧分層強化學習的幾大類方法。

人工智能；機器學習；強化學習；分層強化學習；深度強化學習；馬爾可夫決策過程；半馬爾可夫決策過程；維度災(zāi)難

強化學習要研究的問題是智能體(agents)如何在一個環(huán)境(environment)中學到一定的策略(policy)，使得長期的獎賞(reward)最大。但是傳統(tǒng)的強化學習方法面臨著維度災(zāi)難，即當環(huán)境較為復(fù)雜或者任務(wù)較為困難時，agent的狀態(tài)(state)空間過大，會導(dǎo)致需要學習的參數(shù)以及所需的存儲空間急速增長，強化學習難以取得理想的效果。為了解決維度災(zāi)難，研究者提出了分層強化學習(hierarchical reinforcement learning， HRL)。HRL的主要目標是將復(fù)雜的問題分解成多個小問題，分別解決小問題從而達到解決原問題的目的[1]。近些年來，人們認為分層強化學習基本可以解決強化學習的維度災(zāi)難問題[2-3]，轉(zhuǎn)而將研究方向轉(zhuǎn)向如何將復(fù)雜的問題抽象成不同的層級，從而更好地解決這些問題[4]。

現(xiàn)在已有的一些分層學習大致可以分為4大類，分別是基于選項(option)的強化學習、基于分層抽象機(hierarchical of abstract machines) 的分層強化學習、基于MaxQ值函數(shù)分解 (MaxQ value function decomposition) 的分層強化學習，以及端到端的(end to end)分層強化學習。

1 背景知識

在本節(jié)中，我們主要介紹強化學習、馬爾可夫決策過程(Markov decision process)和半馬爾克夫決策過程(Semi-Markov decision process)的定義以及相關(guān)的背景知識。

1.1 強化學習與馬爾可夫決策過程

強化學習是機器學習和人工智能中一個重要的領(lǐng)域，主要研究的問題是agent如何通過直接與環(huán)境交互來學習策略，使得長期的獎賞最大。強化學習有一些特點，比如無監(jiān)督學習，獎賞的反饋有延遲，agent選擇的動作會影響之后接收的數(shù)據(jù)等。

除了值函數(shù)，動作-值函數(shù)(action-value function)也在強化學習中扮演著重要的角色，記作Qπ(s,a)，表示給定一個策略π，在狀態(tài)s上執(zhí)行動作a可以得到的期望累積獎賞。我們也將Qπ(s,a)叫作Q函數(shù)，其具體的數(shù)學定義表示為

Qπ(s,a)=E{rt+γrt+1+γ2rt+2+…|st=s,at=a,π}

同樣的，我們也希望通過學習到一個最優(yōu)的Q函數(shù)Q*，使agent可以直接通過Q函數(shù)來選擇當前狀態(tài)下應(yīng)該執(zhí)行的動作。

經(jīng)過多年的研究，已經(jīng)出現(xiàn)一些算法，致力于解決傳統(tǒng)的強化學習問題，比如Q-Learning、蒙特卡洛方法(Monte-Carlo learning)、時序差分方法(temporal-difference learning)等。其中Q-Learning方法常常在分層強化學習中被使用。Q-Learning通過不斷迭代更新Q函數(shù)的值來逼近最優(yōu)的Q*。其迭代式如下

Qk+1(s,a)=(1-αk)Qk(s,a)+

αk(r+γmaxa′∈As′Qk(s′,a′))

其中s′表示下一個狀態(tài)。

1.2 半馬爾可夫決策過程

馬爾可夫決策過程中，選擇一個動作后，agent會立刻根據(jù)狀態(tài)轉(zhuǎn)移方程P跳轉(zhuǎn)到下一個狀態(tài)，而在半馬爾可夫決策過程(SMDP)中，當前狀態(tài)到下一個狀態(tài)的步數(shù)是個隨機變量τ，即在某個狀態(tài)s下選擇一個動作a后，經(jīng)過τ步才會以一個概率轉(zhuǎn)移到下一個狀態(tài)s′。此時的狀態(tài)轉(zhuǎn)移概率是s和τ的聯(lián)合概率P(s′,τ|s,a)。根據(jù)τ的定義域不同，SMDP所定義的系統(tǒng)也有所不同。當τ的取值為實數(shù)值，則SMDP構(gòu)建了一個連續(xù)時間-離散事件系統(tǒng)(continuous-time discrete-event system)[5]；而當τ的取值為正整數(shù)，則是一個離散時間SMDP(discrete-time SMDP)[6]。出于簡單考慮，絕大部分分層強化學習都是在離散時間SMDP上進行討論。

2 分層強化學習方法

分層強化學習是將復(fù)雜的強化學習問題分解成一些容易解決的子問題(sub-problem)，通過分別解決這些子問題，最終解決原本的強化學習問題[7-9]。常見的分層強化學習方法可以大致分為四大類，分別為基于選項(option)的強化學習、基于分層抽象機(hierarchical of abstract machines) 的分層強化學習、基于MaxQ函數(shù)分解 (MaxQ value function decomposition) 的分層強化學習，以及端到端的(end to end)的分層強化學習。本節(jié)將對它們逐一進行探討。

2.1 基于選項的分層強化學習

“選項”(option)的概念在1999年由Sutton等人提出[10]，是一種對動作的抽象。一般的，option可表示為一個三元組〈I,π,β〉。其中，π:S×A→[0,1]表示此option中的策略；β:S→[0,1]表示終止條件，β(s)表示狀態(tài)s有β(s)的概率終止并退出此option；I?S表示option的初始狀態(tài)集合。option〈I,π,β〉在狀態(tài)s上可用，當且僅當s∈I。當option開始執(zhí)行時，agent通過該option的π進行動作選擇直到終止。值得注意的是，一個單獨的動作a也可以是一個option，通常被稱作one-step option，I={s:a∈As}，并且對任意的狀態(tài)s都有β(s)=1。

基于option的分層強化學習的過程如下：假設(shè)agent當前在某個狀態(tài)，選擇一個option，通過這個option的策略，agent選擇了一個動作或者另一個option。若選擇了一個動作，則直接執(zhí)行轉(zhuǎn)移到下一個狀態(tài)；若選擇了另一個option，則用選擇的新option繼續(xù)選擇，直到最后得出一個動作。

為了使用option來解決分層強化學習問題，我們還需要定義一個更高層級的策略μ:S×Os→[0,1]。其中，O表示所有option的集合，而Os表示狀態(tài)s下可用的option的集合；μ(s,o)表示在狀態(tài)s時以μ(s,o)的概率選擇o作為當前的option。此時的Q函數(shù)定義為

Qμ(s,o)=E{rt+γrt+1+γ2rt+2+…|or=o,st=s}

此時的Q-Learning的更新公式為

Qk+1(st,ot)=(1-αk)Qk(st,ot)+αk(rt+γrt+1+…+

γτ-1rt+τ+γτmaxo′∈Os′Qk(st+τ,o′))

其中，αk為第k輪迭代時的學習率，τ表示optiono在執(zhí)行τ步之后在狀態(tài)st+τ停止，而o′為在o執(zhí)行結(jié)束后的下一個option?？梢宰⒁獾?，當所有的option均為one-step option時，這個Q-Learning就退化為普通的Q-Learning過程。

2.2 基于分層抽象機的分層強化

分層抽象機(hierarchies of abstract machines， HAMs，)是Parr和Russell提出的方法[11]。和option的方法類似，HAMs的方法也是建立在SMDP的理論基礎(chǔ)之上的。HAMs的主要思想是將當前所在狀態(tài)以及有限狀態(tài)機的狀態(tài)結(jié)合考慮，從而選擇不同的策略。

HAMs也可以通過改進Q-Learning算法進行學習。對于一個馬爾可夫決策過程M和任意一個狀態(tài)機H，H°M是一個MDP[11]，其中狀態(tài)集合為S×SH，動作集合為A×AH。只有當H的狀態(tài)是choice類型的狀態(tài)時，H°M才需要進行決策，其他狀態(tài)下都可以根據(jù)狀態(tài)機的狀態(tài)自動進行狀態(tài)轉(zhuǎn)移，所以實際上H°M是個SMDP。因此我們需要維護的Q函數(shù)為Q([sc,mc],ac)，其中，c表示H°M中需要作出選擇的狀態(tài)的下標，[sc,mc]被稱作選擇點(choice point)。此時Q-Learning的更新公式為

Qk+1([sc,mc],ac)=(1-αk)Qk([sc,mc],ac)+α[rt+

2.3 基于MaxQ值函數(shù)分解的分層強化學習

MaxQ值函數(shù)分解(MaxQ value function decomposition)，是由Dietterich提出的另外一種分層強化學習的方法[12]。首先將一個馬爾可夫決策過程M分解成多個子任務(wù){(diào)M0,M1,…,Mn}，M0為根子任務(wù)，解決了M0就意味著解決了原問題M。對于每一個子任務(wù)Mi，都有一個終止斷言(termination predicate)Ti和一個動作集合Ai。這個動作集合中的元素既可以是其他的子任務(wù)，也可以是一個MDP中的action。一個子任務(wù)的目標是轉(zhuǎn)移到一個狀態(tài)，可以滿足終止斷言，使得此子任務(wù)完成并終止。我們需要學到一個高層次的策略π={π0,…,πn}，其中πi為子任務(wù)Mi的策略。

令V(i,s)表示子任務(wù)i在狀態(tài)s的值函數(shù)，即該子問題從狀態(tài)s開始一直按照某個策略執(zhí)行最終達到終止狀態(tài)的期望累計獎賞。類似的，令Q(i,s,j)為子任務(wù)i在狀態(tài)s執(zhí)行動作j之后按照某個策略執(zhí)行直到達到終止狀態(tài)的期望累計獎賞，可以表示為

Q(i,s,j)=E(rt+γrt+1+γ2rt+2+…|st=s,π)

假設(shè)選擇的動作j一共執(zhí)行了τ步才返回，那么我們可以把Q函數(shù)寫成

其中右邊的第1項實際上是V(j,s)，第2項叫作完成函數(shù)(completion function)，記作C(i,s,j)。則Q函數(shù)的貝爾曼方程可以寫為

γτmaxj′Q(i,s′,j′))=V(j,s)+C(i,s,j)

當選擇的動作j完成后，得到下一個狀態(tài)s′以及做完這個動作經(jīng)過的時間τ，則可更新完成函數(shù)

Ct+1(i,s,j)=(1-αt)Ct(i,s,j)+

αtγτ[maxa′V(a′,s′)+Ct(i,s′,a′)]

這樣也就更新了Q函數(shù)。

圖1為利用MaxQ方法解決taxi problem的任務(wù)劃分示意圖[12]。

圖1 出租車問題的任務(wù)圖Fig.1 Task graph for the taxi problem

出租車問題是指一個出租車agent需要到特定位置接一位乘客并且把他送到特定的位置讓其下車。一共有6個動作，分別是上車(pick up)、下車(drop off)，以及向東南西北四個方向開車的動作。這里使用MaxQ方法，將原問題分解成了get和put兩個子任務(wù)，這兩個子任務(wù)又進行分解，get分解成一個基本動作pick up和一個子任務(wù)navigate，而put也分解成了一個基本動作drop off和一個子任務(wù)navigate。子任務(wù)navigate(t)表示t時刻應(yīng)該開車的方向。對于這個強化學習問題，agent首先選擇get，然后get子問題navigate，直到到達乘客所在地，然后get選擇pick up動作，乘客上車。之后agent選擇put子任務(wù)，put子任務(wù)選擇navigate，直到到達乘客目的地，之后put子任務(wù)選擇drop off動作，乘客下車，任務(wù)完成。

2.4 端到端的的分層強化學習

上述的幾種方法，都需要人工來做很多工作，比如人工進行option的選取，人工進行HAMs的構(gòu)建，人工劃分子任務(wù)等。人工設(shè)計不僅耗時耗力，并且會直接影響最終強化學習結(jié)果的好壞。近些年來人們關(guān)注如何讓agent自己學到合理的分層抽象，而非人為進行劃分和指定。

有人提出利用蟻群算法啟發(fā)式地尋找合理的劃分點[13]。作者利用蟻群算法根據(jù)信息素的變化程度尋找“瓶頸”(bottle neck)，瓶頸像一座橋梁一樣連接著問題空間中不同的連續(xù)區(qū)域。圖2為一個Grid Word問題，agent需要從狀態(tài)s出發(fā)到達狀態(tài)g。通過蟻群算法分析信息素的變化程度找出瓶頸在兩個房間的窄門處，即圖2中的狀態(tài)v附近。

圖2 通過蟻群算法找到從s到g的最短路徑Fig.2 Shortest path between s and g found by ant system

通過多次探索留下的信息素密集程度來找到瓶頸即可將問題空間劃分，再使用基于option的分層強化學習即可解決。

除了啟發(fā)式的抽象方法，有人還提出使用神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)來自動進行問題的分層抽象和學習[14-20]。近些年來神經(jīng)網(wǎng)絡(luò)快速發(fā)展，尤其是在圖像識別領(lǐng)域，更是取得了很多成果。因此有人嘗試通過結(jié)合神經(jīng)網(wǎng)絡(luò)和強化學習來設(shè)計電子游戲的AI，輸入為游戲畫面，通過神經(jīng)網(wǎng)絡(luò)和強化學習學習到游戲策略。有些游戲復(fù)雜度較高，需要使用分層強化學習。文獻[14] 中提出了Option-Critic架構(gòu)，旨在通過神經(jīng)網(wǎng)絡(luò)強大的學習能力，模糊發(fā)現(xiàn)option和學習option之間的界限，直接通過神經(jīng)網(wǎng)絡(luò)一起訓練。在一些游戲上取得了比不使用分層強化學習的Deep Q Network更好的結(jié)果。文獻[15] 中提出了Manager-Worker架構(gòu)，Manager負責給Worker一個子目標，而Worker根據(jù)子目標和當前所處的狀態(tài)給出具體執(zhí)行的動作。在這個方法中，Manager和Worker分別是兩個不同的神經(jīng)網(wǎng)絡(luò)，并且用各自的梯度分別進行優(yōu)化，在實驗中也取得了很好的效果。

人工進行分層和抽象，不僅費時費力，而且容易忽視問題中不易發(fā)現(xiàn)的內(nèi)在聯(lián)系。因此使用端到端的分層強化學習，從分層抽象到訓練學習，都通過機器學習的方法自動進行必然是今后人們不斷研究的方向。

3 總束語

本文對于分層強化學習進行了回顧。首先介紹了強化學習、馬爾科夫決策過程以及半馬爾科夫決策過程的定義和基本概念，規(guī)定了本文的符號使用。然后，在第2節(jié)分4個方面，闡述了Sutton等提出的option方法，Parr和Russell提出的HAMs方法以及Dierrerich等提出的MaxQ方法，闡述了這些方法具體的計算方法。分析了近兩年來的研究方向，介紹了一些端到端的、自動抽象的分層強化學習。分層強化學習是解決大規(guī)模強化學習的潛在途徑，然而其受到的關(guān)注不足。希望本篇綜述能夠引起更多人關(guān)注分層強化學習。

[1]BARTO A G, MAHADEVAN S. Recent advances in hierarchical reinforcement learning[J]. Discrete event dynamic systems, 2013，13(4)： 341-379.

[2]YAN Q, LIU Q, HU D. A hierarchical reinforcement learning algorithm based on heuristic reward function[C]//In Proceedings of 2nd International Conference on Advanced Computer Control. Shenyang, China, 2010, 3：371-376.

[3]DETHLEFS N, CUAYHUITL H. Combining hierarchical reinforcement learning and Bayesian networks for natural language generation in situated dialogue[C]//European Workshop on Natural Language Generation. Nancy, France,2011: 110-120.

[4]AL-EMRAN M. Hierarchical reinforcement learning: a survey[J]. International journal of computing and digital systems, 2015, 4(2):137-143.

[5]MAHADEVAN S, MARCHALLECK N. Self-improving factory simulation using continuous-time average-reward reinforcement learning[C]. In Proceedings of the Machine Learning International Workshop. Nashville, USA, 1997: 202-210.

[6]HOWARD R A. Semi-Markov and decision processes[M]. New York: DOVER Publications, 2007.

[7]GIL P, NUNES L. Hierarchical reinforcement learning using path clustering[C]//In Proceedings of 8th Iberian Conference on Information Systems and Technologies. Lisboa, Portugal, 2013： 1-6.

[8]STULP F, SCHAAL S. Hierarchical reinforcement learning with movement primitives[C]//In Proceedings of 11th IEEE-RAS International Conference on Humanoid Robots. Bled, Slovenia, 2011: 231-238.

[9]DU X, LI Q, HAN J. Applying hierarchical reinforcement learning to computer games[C]//In Proceedings of IEEE International Conference on Automation and Logistics. Xi’an， China, 2009: 929-932.

[10]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/2): 181-211.

[11]PARR R, RUSSELL S. Reinforcement learning with hierarchies of machines[C]//Advances in Neural Information Processing Systems. Colorado, USA, 1998: 1043-1049.

[12]DIETTERICH T G. Hierarchical reinforcement learning with the MAXQ value function decomposition[J]. Journal of artificial intelligence research, 2000, 13: 227-303.

[13]MOHSEN G, TAGHIZADEH N, et al. Automatic abstraction in reinforcement learning using ant system algorithm[C]//In Proceedings of AAAI Spring Symposium: Lifelong Machine Learning. Stanford, USA, 2013: 114-122.

[14]PIERRE-LUC BACON, JEAN HARB. The option-critic architecture[C]//In Proceeding of 31th AAAI Conference on Artificial Intelligence. San Francisco, USA, 2017： 1726-1734.

[15]VEZHNEVETS A S, OSINDERO S, SCHAUL T, et al. FeUdal networks for hierarchical reinforcement learning[C]//In Proceedings of the 34th International Conference on Machine Learning. Sydney, Australia, 2017: 3540-3549.

[16]MNIH V, KAVUKCUOGLU K, SILVER D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(2): 529-533.

[17]TEJAS D. K, KARTHNIK N, ARDAVAN S, et al. Hierarchical deep reinforcement learning: integrating temporal abstraction and intrinsic motivation[C]//Annual Conference on Neural Information Processing Systems. Barcelona, Spain, 2016: 3675-3683.

[18]CARLOS FLORENSA, YAN D, PIETER A. Stochastic neural networks for hierarchical reinforcement learning[EB/OL]. Berkeley, USA, arXiv. 2017, https://arxiv.org/pdf/1704.03012.pdf.

[19]LAKSHMINARAYANAN A S, KRISHNAMURTHY R, KUMAR P, et al. Option discovery in hierarchical reinforcement learning using spatio-temporal clustering[EB/OL]. Madras, India, arXiv, 2016, https://arxiv.org/pdf/1605.05359.pdf.

[20]XUE B ， GLEN B. DeepLoco: dynamic locomotion skills using hierarchical deep reinforcement learning[J]. ACM transactions on graphics，2017， 36(4):1-13.

周文吉，男，1995年生，碩士研究生，主要研究方向為強化學習和數(shù)據(jù)挖掘。

俞揚，男，1982年生，副教授，博士生導(dǎo)師，主要研究方向為人工智能、機器學習、演化計算、數(shù)據(jù)挖掘。曾獲2013年全國優(yōu)秀博士學位論文獎，2011年中國計算機學會優(yōu)秀博士學位論文獎。發(fā)表論文40余篇。

Summarizeofhierarchicalreinforcementlearning

ZHOU Wenji， YU Yang

(National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China)

Reinforcement Learning (RL) is an important research area in the field of machine learning and artificial intelligence and has

increasing attentions in recent years. The goal in RL is to maximize long-term total reward by interacting with the environment. Traditional RL algorithms are limited due to the so-called curse of dimensionality, and their learning abilities degrade drastically with increases in the dimensionality of the state space. Hierarchical reinforcement learning (HRL) decomposes the RL problem into sub-problems and solves each of them to improve learning ability. HRL offers a potential way to solve large-scale RL, which has received insufficient attention to date. In this paper, we introduce and review several main HRL methods.

artificial intelligence; machine learning; reinforcement learning; hierarchical reinforcement learning; deep reinforcement learning; Markov decision process; semi-Markov decision process; dimensional curse

10.11992/tis.201706031

http://kns.cnki.net/kcms/detail/23.1538.TP.20171021.1350.008.html

TP391

A

1673-4785(2017)05-0590-05

中文引用格式：周文吉，俞揚.分層強化學習綜述J.智能系統(tǒng)學報， 2017, 12(5): 590-594.

英文引用格式：ZHOUWenji，YUYang.SummarizeofhierarchicalreinforcementlearningJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 590-594.

2017-06-09. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-10-21.

國家自然科學基金項目(61375061)； 江蘇省自然科學基金項目(BK20160066).

俞揚. E-mail：yuy@nju.edu.cn.