強(qiáng)化學(xué)習(xí)(Reinforcement Learning)
Created by | Created on |
---|---|
xbo | June 10, 2019 |
強(qiáng)化學(xué)習(xí)基本概念
強(qiáng)化學(xué)習(xí)四要素:狀態(tài)(state)、動作(action)、策略(policy)歹嘹、獎勵(reward)。
名詞 | 解釋 |
---|---|
智能體 | 學(xué)習(xí)器與決策者的角色徒溪。 |
環(huán)境 | 智能體之外一切組成的、與之交互的事物金顿。 |
動作 | 智能體的行為表征臊泌。 |
狀態(tài) | 智能體從環(huán)境獲取的信息。 |
獎勵 | 環(huán)境對于動作的反饋揍拆。 |
策略 | 智能體根據(jù)狀態(tài)進(jìn)行下一步動作的函數(shù)渠概。 |
狀態(tài)轉(zhuǎn)移概率 | 智能體做出動作后進(jìn)入下一狀態(tài)的概率。 |
RL考慮的是智能體(Agent)與環(huán)境(Environment)的交互問題:
智能體處在一個環(huán)境中嫂拴,每個狀態(tài)為智能體對當(dāng)前環(huán)境的感知播揪;智能體只能通過動作來影響環(huán)境,當(dāng)智能體執(zhí)行一個動作后筒狠,會使得環(huán)境按某種概率轉(zhuǎn)移到另一個狀態(tài)猪狈;同時,環(huán)境會根據(jù)潛在的獎賞函數(shù)反饋給智能體一個獎賞辩恼。
--- 周志華 《機(jī)器學(xué)習(xí)》
RL的目標(biāo)是找到一個最優(yōu)策略雇庙,使智能體獲得盡可能多的來自環(huán)境的獎勵。例如賽車游戲灶伊,游戲場景是環(huán)境疆前,賽車是智能體,賽車的位置是狀態(tài)聘萨,對賽車的操作是動作竹椒,怎樣操作賽車是策略,比賽得分是獎勵米辐。在論文中中常用觀察(Observation)而不是環(huán)境胸完,因為智能體不一定能得到環(huán)境的全部信息书释,只能得到自身周圍的信息。
在每個時間步(timestep)舶吗,智能體在當(dāng)前狀態(tài)根據(jù)觀察來確定下一步的動作,因此狀態(tài)和動作之間存在映射關(guān)系择膝,這種關(guān)系就是策略誓琼,用表示:
記作,
表示動作action肴捉,
表示狀態(tài)state腹侣。
學(xué)習(xí)開始時往往采用隨機(jī)策略進(jìn)行實驗得到一系列的狀態(tài)、動作和獎勵樣本齿穗,算法根據(jù)樣本改進(jìn)策略傲隶,最大化獎勵。由于獎勵越來越大的特性窃页,這種算法被稱作增強(qiáng)學(xué)習(xí)跺株。
馬爾可夫決策過程(Markov Decision Process, MDP)
馬爾可夫性
系統(tǒng)的下一個狀態(tài)僅與當(dāng)前狀態(tài)有關(guān),而與歷史狀態(tài)無關(guān)脖卖。
此處的狀態(tài)是指完全可觀察的全部的環(huán)境狀態(tài)
回報(Return)
為最大化長期累積獎賞乒省,定義當(dāng)前時刻后的累積獎賞為回報(Return),考慮折扣因子(避免時間過長時畦木,總回報無窮大):
值函數(shù)(Value Function)
強(qiáng)化學(xué)習(xí)的目標(biāo)是學(xué)習(xí)到一個策略來最大化期望袖扛,即希望智能體執(zhí)行一系列的動作來獲得盡可能多的平均回報。為評估一個策略的期望回報十籍,需要定義值函數(shù).
狀態(tài)值函數(shù):在狀態(tài)下獲得的期望回報蛆封。
狀態(tài)-動作值函數(shù):在狀態(tài)下執(zhí)行動作
后獲得的期望回報。
根據(jù)馬爾可夫特性勾栗,二者有如下關(guān)系:
即狀態(tài)值函數(shù)是動作-狀態(tài)值函數(shù)
關(guān)于動作
的期望惨篱。
貝爾曼方程(Bellman equation)
其意義在于當(dāng)前狀態(tài)的值函數(shù)可以通過下一狀態(tài)的值函數(shù)來計算。同理围俘,狀態(tài)-動作值函數(shù)也有類似關(guān)系妒蛇。
計算狀態(tài)值函數(shù)的目的是為了構(gòu)建學(xué)習(xí)算法從數(shù)據(jù)中得到最優(yōu)策略,每個策略對應(yīng)著一個狀態(tài)值函數(shù)楷拳,最優(yōu)策略對應(yīng)著最優(yōu)狀態(tài)值函數(shù)绣夺。
基于值函數(shù)的學(xué)習(xí)方法
求解最優(yōu)策略等價于求解最優(yōu)的值函數(shù),這是求解最優(yōu)策略的一種方法欢揖,稱為基于值函數(shù)的學(xué)習(xí)方法陶耍,DQN采用該算法。
最優(yōu)的值必然為最大值她混,故等式右側(cè)的
值必然為使
取最大的
值烈钞。
由于值函數(shù)是對策略的評估泊碑,為不斷優(yōu)化直至選出最優(yōu)策略,一種可行的方式是依據(jù)值函數(shù)選取策略更新的方式毯欣。常見的策略有兩種:
- 貪婪策略
貪婪策略是一個確定性策略馒过,即始終選取使值函數(shù)最大的策略。這是智能體對已知知識的利用(exploitation)酗钞,不好更新出更好的值腹忽,但可以得到更好的測試效果用于判斷算法是否有效。
- ε-greedy策略:
選取不使值函數(shù)最大的動作表示智能體對未知知識的探索(exploration)砚作,探索未知的動作會產(chǎn)生的未知的效果窘奏,有利于更新值,有可能獲得更好的策略葫录,故ε-greedy策略平衡了探索和利用着裹。
分類
馬爾科夫鏈過程
- 基于模型的(Model-based):動態(tài)規(guī)劃
- 無模型的(Model-free):強(qiáng)化學(xué)習(xí)
- 基于值函數(shù)的(Value-based)
- 基于策略梯度的(Policy-gradient)
- 基于模型的(Model-based)
無模型強(qiáng)化學(xué)習(xí)方法
基于模型的強(qiáng)化學(xué)習(xí)方法(動態(tài)規(guī)劃)的前提是知道環(huán)境的狀態(tài)轉(zhuǎn)移概率,但在實際問題中米同,狀態(tài)轉(zhuǎn)移的信息往往無法獲知骇扇,由此需要數(shù)據(jù)驅(qū)動的無模型(model-free)的方法。
蒙特卡羅(Monte Carlo)方法
在無模型時面粮,一種自然的想法是通過隨機(jī)采樣的經(jīng)驗平均來估計期望值匠题,此即蒙特卡羅法。其過程可以總結(jié)如下:
- 智能體與環(huán)境交互后得到交互序列
- 通過序列計算出各個時刻的獎賞值
- 將獎賞值累積到值函數(shù)中進(jìn)行更新
- 根據(jù)更新的值函數(shù)來更新策略
在動態(tài)規(guī)劃中但金,為保證算法的收斂性韭山,算法會逐個掃描狀態(tài)空間中的狀態(tài),計算值函數(shù)時用到了當(dāng)前狀態(tài)的所有后繼狀態(tài)的值函數(shù)冷溃。而蒙特卡羅利用經(jīng)驗平均估計狀態(tài)的值函數(shù)钱磅,此處的經(jīng)驗是指一次試驗,而一次試驗要等到終止?fàn)顟B(tài)出現(xiàn)才結(jié)束似枕,因此學(xué)習(xí)速度慢盖淡,效率不高。下圖較直觀展示了二者的不同凿歼。
在蒙特卡羅中褪迟,如果采用確定性策略,每次試驗的軌跡都是一樣的答憔,因此無法進(jìn)一步改進(jìn)策略味赃。為了使更多狀態(tài)-動作對參與到交互過程中,即平衡探索和利用虐拓,常用ε-greedy策略來產(chǎn)生動作 心俗,以保證每個狀態(tài)-動作對都有機(jī)會作為初始狀態(tài),在評估狀態(tài)-動作值函數(shù)時,需要對每次試驗中所有狀態(tài)-動作對進(jìn)行估計城榛。
時序差分方法(Temporal Difference)
由于蒙特卡羅需要獲得完整軌跡揪利,才能進(jìn)行策略評估并更新,效率較低狠持。時序差分法結(jié)合了動態(tài)規(guī)劃和蒙特卡羅疟位,即模擬一段軌跡(一步或者幾步),然后利用貝爾曼方程進(jìn)行自迭代更新喘垂,如下圖所示:
對該方法的通俗理解:
你需要從A點(diǎn)出發(fā)甜刻,經(jīng)過B點(diǎn)后到C點(diǎn),你有兩個路段(A-B,B-C)的估計用時王污,在一次實驗中罢吃,經(jīng)過A-B路段后得到一個準(zhǔn)確用時楚午,根據(jù)這個準(zhǔn)確用時和B-C路段的估計用時即可得到新的全路段估計用時(即更新)昭齐。
上述例子體現(xiàn)了TD學(xué)習(xí)的主要原則:不必等到實驗結(jié)束再沿著實驗路徑進(jìn)行更新。
區(qū)別
蒙特卡羅使用的是值函數(shù)最原始的定義矾柜,即利用所有獎賞的累積和來估計值函數(shù)阱驾;
動態(tài)規(guī)劃和時序差分則利用一步預(yù)測方法來計算當(dāng)前狀態(tài)值函數(shù),不同的是怪蔑,動態(tài)規(guī)劃利用模型計算后繼狀態(tài)里覆,時序差分利用實驗得到后繼狀態(tài)。
Q-learning
Q學(xué)習(xí)基于時序差分得到更新Q值的方法:
迭代得到的值沒有直接賦予新的Q值缆瓣,而是采用遞進(jìn)的方式更新原有Q值喧枷,這能夠減少估計誤差造成的影響,類似隨機(jī)梯度下降弓坞,最終收斂到最優(yōu)Q值隧甚。
深度Q網(wǎng)絡(luò)(Deep Q-Network, DQN)
函數(shù)近似(Function Approximation)
動態(tài)規(guī)劃、蒙特卡羅渡冻、時序差分等都有一個共同前提:狀態(tài)空間和動作空間是離散的且不能太大戚扳。通常值函數(shù)用表格的形式的表示(Q-Table),故又稱之為表格型強(qiáng)化學(xué)習(xí)族吻。但在很多問題中帽借,狀態(tài)空間維數(shù)很大,甚至可能是連續(xù)的超歌,無法用表格表示砍艾,即在訓(xùn)練過程中,僅通過反復(fù)的測試無法獲得足夠的樣本來遍歷每個狀態(tài)巍举,這樣在應(yīng)用過程中若遇到未遍歷的狀態(tài)將導(dǎo)致算法失敗辐董。
人類在學(xué)習(xí)過程中不可能遍歷所有的情況,更多的是將新情況與記憶進(jìn)行比對禀综,如果相似简烘,則采用相似的做法苔严。因此,如果能用一個函數(shù)來表示值函數(shù)孤澎,輸入任意的狀態(tài)都能輸出結(jié)果届氢,那么就可以把Q矩陣的更新問題變成一個函數(shù)擬合問題,相近的狀態(tài)也就可以得到相近的動作覆旭,這就是值函數(shù)近似(value function approximator):退子,通過更新參數(shù)
來使得Q函數(shù)逼近最優(yōu)的Q值。
上述操作將求解值函數(shù)問題轉(zhuǎn)化為函數(shù)優(yōu)化問題型将,從而可以使用監(jiān)督學(xué)習(xí)(supervised learning).監(jiān)督學(xué)習(xí)是一種常見且易于解決的問題寂祥,線性回歸(Linear Regression) 、支持向量機(jī)(Support Vector Machine)七兜、決策樹(Decision Tree)丸凭, 以及神經(jīng)網(wǎng)絡(luò)(Neural Network )等都可以用來解決此類問題,一般做法是:
1 確定一個損失函數(shù)loss function
2 計算關(guān)于損失函數(shù)的梯度
3 使用梯度下降比如隨機(jī)梯度下降(SGD)等方法來更新
使用深度神經(jīng)網(wǎng)絡(luò)做值函數(shù)近似來解決強(qiáng)化學(xué)習(xí)問題即是深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,Deep Q-Learning,DQN)
DQN
與Q-Learning相比腕铸,DQN主要改進(jìn)在以下三個方面:
(1)DQN利用深度卷積網(wǎng)絡(luò)(Convolutional Neural Networks,CNN)來逼近值函數(shù)惜犀;
(2)DQN利用經(jīng)驗回放訓(xùn)練強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過程;
Q-Leaning 方法基于當(dāng)前策略進(jìn)行交互和改進(jìn)狠裹,每一次模型利用交互生成的數(shù)據(jù)進(jìn)行學(xué)習(xí)虽界,學(xué)習(xí)后的樣本被直接丟棄。但如果使用機(jī)器學(xué)習(xí)模型代替表格式模型后再采用這樣的在線學(xué)習(xí)方法涛菠,就有可能遇到兩個問題莉御,這兩個問題也都和機(jī)器學(xué)習(xí)有關(guān)。
- 交互得到的序列存在一定的相關(guān)性俗冻。交互序列中的狀態(tài)行動存在著一定的相關(guān)性礁叔,而對于基于最大似然法的機(jī)器學(xué)習(xí)模型來說,我們有一個很重要的假設(shè):訓(xùn)練樣本是獨(dú)立且來自相同分布的言疗,一旦這個假設(shè)不成立晴圾,模型的效果就會大打折扣。而上面提到的相關(guān)性恰好打破了獨(dú)立同分布的假設(shè)噪奄,那么學(xué)習(xí)得到的值函數(shù)模型可能存在很大的波動死姚。
為解決以上兩個問題,引入經(jīng)驗回放勤篮。Replay Buffer 包含了收集樣本和采樣樣本兩個過程都毒。收集的樣本按照時間先后順序存入結(jié)構(gòu)中,如果Replay Buffer 已經(jīng)存滿樣本碰缔,那么新的樣本會將時間上最久遠(yuǎn)的樣本覆蓋账劲。而對采樣來說,如果每次都取出最新的樣本, 那么算法就和在線學(xué)習(xí)相差不多瀑焦; 一般來說腌且,Replay Buffer 會從緩存中均勻地隨機(jī)采樣一批樣本進(jìn)行學(xué)習(xí)。這樣榛瓮,每次訓(xùn)練的樣本通常來自多次交互序列铺董,這樣單一序列的波動就被減輕很多,訓(xùn)練效果也就更加穩(wěn)定禀晓。同時精续,一份樣本也可以被多次訓(xùn)練,提高了樣本的利用率粹懒。- 交互數(shù)據(jù)的使用效率重付。采用梯度下降法進(jìn)行模型更新時,模型訓(xùn)練往往需要經(jīng)過多輪迭代才能收斂凫乖。每一次迭代都需要使用一定數(shù)量的樣本計算梯度确垫, 如果每次計算的樣本在計算一次梯度后就被丟棄,那么我們就需要花費(fèi)更多的時間與環(huán)境交互并收集樣本拣凹。
為解決以上兩個問題森爽,引入經(jīng)驗回放恨豁。Replay Buffer 包含了收集樣本和采樣樣本兩個過程嚣镜。收集的樣本按照時間先后順序存入結(jié)構(gòu)中,如果Replay Buffer 已經(jīng)存滿樣本橘蜜,那么新的樣本會將時間上最久遠(yuǎn)的樣本覆蓋菊匿。而對采樣來說,如果每次都取出最新的樣本计福, 那么算法就和在線學(xué)習(xí)相差不多跌捆; 一般來說,Replay Buffer 會從緩存中均勻地隨機(jī)采樣一批樣本進(jìn)行學(xué)習(xí)象颖。這樣佩厚,每次訓(xùn)練的樣本通常來自多次交互序列,這樣單一序列的波動就被減輕很多说订,訓(xùn)練效果也就更加穩(wěn)定抄瓦。同時,一份樣本也可以被多次訓(xùn)練陶冷,提高了樣本的利用率钙姊。
(3)DQN獨(dú)立設(shè)置了目標(biāo)網(wǎng)絡(luò)來單獨(dú)處理時序差分中的偏差。
在Q-Learning中埂伦,通過當(dāng)前時刻的回報和下一時刻的價值估計進(jìn)行更新煞额,由于數(shù)據(jù)本身存在著不穩(wěn)定性, 每一輪迭代都可能產(chǎn)生一些波動,這些波動會立刻反映到下一個迭代的計算中膊毁,這樣我們就很難得到一個平穩(wěn)的模型胀莹。為了減輕相關(guān)問題帶來的影響,需要盡可能地將兩個部分解耦婚温,由此引入目標(biāo)網(wǎng)絡(luò)嗜逻,其訓(xùn)練過程如下:
- 在訓(xùn)練開始時,兩個模型使用完全相同的參數(shù)缭召。
- 在訓(xùn)練過程中栈顷, Behavior Network 負(fù)責(zé)與環(huán)境交互,得到交互樣本嵌巷。
- 在學(xué)習(xí)過程中萄凤,由Q-Learning 得到的目標(biāo)價值由Target Network 計算得到;然后用它和Behavior Network 的估計值進(jìn)行比較得出目標(biāo)值并更新Behavior Network搪哪。
- 每當(dāng)訓(xùn)練完成一定輪數(shù)的迭代靡努, Behavior Network 模型的參數(shù)就會同步給Target Network ,這樣就可以進(jìn)行下一個階段的學(xué)習(xí)晓折。
通過使用Target Network 惑朦,計算目標(biāo)價值的模型在一段時間內(nèi)將被固定,這樣模型可以減輕模型的波動性漓概。
DQN完整算法
具體訓(xùn)練過程:
Step 1: 用一個深度神經(jīng)網(wǎng)絡(luò)來作為值的值函數(shù)近似漾月,參數(shù)為
:
Step 2: 在值中使用均方差來定義目標(biāo)函數(shù)即損失函數(shù):
此處Target即為算法流程中的目標(biāo)網(wǎng)絡(luò)。
Step 3:計算參數(shù)關(guān)于損失函數(shù)的梯度:
Step 4: 使用SGD實現(xiàn)End-to-end的優(yōu)化目標(biāo)
得到上述梯度胃珍,且可以從深度神經(jīng)網(wǎng)絡(luò)中進(jìn)行計算梁肿,因此可以使用隨機(jī)梯度下降算法來更新參數(shù),從而得到最優(yōu)的Q值觅彰。