如何求強(qiáng)化學(xué)習(xí)最優(yōu)解

在一篇文章強(qiáng)化學(xué)習(xí)與馬爾可夫決策中缩麸，介紹了使用馬爾可夫決策過程對強(qiáng)化學(xué)習(xí)的過程進(jìn)行建模。通過建墓ε冢可以得出，只要求解最優(yōu)價(jià)值函數(shù)术唬，即可得到對應(yīng)的最優(yōu)策略薪伏。那么如何求解最優(yōu)價(jià)值函數(shù)呢？本篇文章將介紹一些最優(yōu)價(jià)值函數(shù)的求解算法粗仓。

predict和control

首先介紹一下強(qiáng)化學(xué)習(xí)的兩個(gè)基本問題嫁怀，預(yù)測和控制。

predict

在已知狀態(tài)集 $S$ 借浊，動(dòng)作集 $A$ 塘淑，模型狀態(tài)轉(zhuǎn)化概率矩陣 $P$ ，即時(shí)獎(jiǎng)勵(lì) $R$ 蚂斤，衰減因子 $\gamma$ 的條件下存捺，給定策略 $\pi$ ，預(yù)測該策略的狀態(tài)價(jià)值函數(shù) $v(\pi)$ 曙蒸。這一過程一般稱為策略評估捌治。

control

在已知狀態(tài)集 $S$ ，動(dòng)作集 $A$ 逸爵，模型狀態(tài)轉(zhuǎn)化概率矩陣 $P$ 具滴，即時(shí)獎(jiǎng)勵(lì) $R$ ，衰減因子 $\gamma$ 的條件下师倔，求解最優(yōu)的狀態(tài)價(jià)值函數(shù) $v_*$ 和最優(yōu)策略 $\pi_*$ 构韵。

從mode-based的方面去看這兩個(gè)問題其實(shí)更好理解，在了解模型機(jī)制的基礎(chǔ)上趋艘，預(yù)測所有可能的狀態(tài)價(jià)值函數(shù)疲恢，然后基于預(yù)測的值，來選取最優(yōu)價(jià)值函數(shù)和最優(yōu)策略瓷胧，這個(gè)過程被稱為策略迭代显拳。

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃是一種可以求解強(qiáng)化學(xué)習(xí)兩個(gè)基本問題的一種方式，其理論依據(jù)是貝爾曼方程搓萧。狀態(tài)價(jià)值函數(shù)的貝爾曼方程如下：

$v_\pi=\sum_{a\epsilon A}\pi(a|s)(R_a^s+\gamma\sum_{{s'}\epsilon S}P_{ss'}^av_\pi(s'))$

通過這個(gè)公式可以看出杂数，當(dāng)前迭代周期某狀態(tài) $s$ 的狀態(tài)價(jià)值宛畦，可以通過上一個(gè)迭代周期內(nèi)的狀態(tài)價(jià)值來計(jì)算更新。這就滿足了使用動(dòng)態(tài)規(guī)劃的兩個(gè)條件揍移，問題的最優(yōu)解可以由子問題的最優(yōu)解構(gòu)成且可以通過較小的子問題狀態(tài)遞推出較大子問題的狀態(tài)次和。

策略評估

結(jié)合貝爾曼方程，預(yù)測問題求解的過程如下：

$v_{k+1}^\pi(s)=\sum_{a\epsilon A}\pi(a|s)(R_s^a+\gamma\sum_{{s'}\epsilon S}P_{ss'}^av_k^\pi(s'))$

其中 $v_k(s)$ 表示第 $k$ 輪狀態(tài) $s$ 的價(jià)值函數(shù)那伐。

策略迭代

控制問題的求解一般可以使用greedy策略踏施。對于當(dāng)前狀態(tài) $s_t$ ，選擇后續(xù)所有可能轉(zhuǎn)移到的狀態(tài)集合 $S_{t+1}$ 中罕邀，狀態(tài)價(jià)值最大的那個(gè)狀態(tài)對應(yīng)的策略 $\pi$ 畅形。

整個(gè)策略迭代過程可以理解為以下兩個(gè)過程：

使用當(dāng)前策略 $\pi$ 評估計(jì)算當(dāng)前策略的狀態(tài)價(jià)值 $v(s)$ 。
根據(jù)狀態(tài)價(jià)值 $v(s)$ 根據(jù)一定的方法（比如貪婪法）更新策略 $\pi$ 诉探。

重復(fù)迭代以上兩個(gè)過程日熬，最終得到收斂的策略 $\pi_*$ 和狀態(tài)價(jià)值 $v_*$ 。

蒙特卡洛法

蒙特卡洛法是一種通過采樣近似求解問題的方法肾胯。與動(dòng)態(tài)規(guī)劃不同碍遍，蒙特卡洛法不需要考慮交互過程中的狀態(tài)轉(zhuǎn)化，其通過采樣若干完整的交互狀態(tài)序列來估計(jì)狀態(tài)的真實(shí)值阳液。

完整的交互狀態(tài)序列指的是從開始到終點(diǎn)的交互序列怕敬，可以在迭代的過程中產(chǎn)生。通過多組完整的交互狀態(tài)序列進(jìn)行來近似的估計(jì)狀態(tài)價(jià)值帘皿，之后便可以求解預(yù)測和控制問題了东跪。

由于蒙特卡洛法是通過采樣的方式來估計(jì)狀態(tài)價(jià)值，不需要考慮交互過程中狀態(tài)的轉(zhuǎn)化鹰溜，因此屬于mode-free的強(qiáng)化學(xué)習(xí)求解方法虽填。反觀動(dòng)態(tài)規(guī)劃，由于考慮狀態(tài)的轉(zhuǎn)化曹动，因此屬于mode-based的強(qiáng)化學(xué)習(xí)求解方法斋日。

策略評估

使用蒙特卡洛法進(jìn)行策略評估的理論依據(jù)是狀態(tài)價(jià)值函數(shù)的定義：

$v_\pi(s)=E_\pi(G_t|S_t=s)=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s)$

從公式上可以看出，每個(gè)狀態(tài)的價(jià)值函數(shù)墓陈，等于其后續(xù)所有的獎(jiǎng)勵(lì)與對應(yīng)的衰減乘積求和的期望恶守。

因此，對于一個(gè)策略 $\pi$ 贡必，如果采樣得到的完整的 $T$ 個(gè)交互狀態(tài)序列如下：

$S_1,A_1,R_2,S_2,A_2,...,S_t,A_t,R_{t+1},...,R_T,S_T$

那么對于 $t$ 時(shí)刻的狀態(tài)價(jià)值函數(shù)可以通過下面的方式進(jìn)行求解：

$\begin{gathered} G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...\gamma^{T-t-1}R^T\\ v_\pi(s)\approx average(G_t),s.t.S_t=s \end{gathered}$

如此一來兔港，就簡單的解決了預(yù)測問題，不過還可以進(jìn)行進(jìn)一步的優(yōu)化仔拟。在上式中衫樊，計(jì)算狀態(tài)價(jià)值函數(shù)需要使用到后續(xù)所有獎(jiǎng)勵(lì)的均值，這意味著必須存儲(chǔ)相關(guān)的所有獎(jiǎng)勵(lì)的值，而且其存儲(chǔ)量會(huì)隨著采樣數(shù)量的增加而增加科侈。

為了解決這個(gè)問題载佳，引入了累計(jì)更新平均值的方法，即下面這個(gè)公式：

$\begin{aligned} \mu_k&=\frac{1}{k}\sum_j^kx_j\\ &=\frac{1}{k}(x_k+\sum_j^{k-1}x_j)\\ &=\frac{1}{k}(x_k+(k-1)\mu_{k-1})\\ &=\mu_{k-1}+\frac{1}{k}(x_k-\mu_{k-1}) \end{aligned}$

其中 $\mu_k$ 表示第 $k$ 輪迭代的均值臀栈， $\mu_{k-1}$ 表示第 $k-1$ 輪迭代的均值刚盈。

參考這個(gè)公式，我們可以將狀態(tài)價(jià)值公式的計(jì)算改寫為：

$\begin{gathered} N_k(S_t)=N_{k-1}(S_t)+1\\ V_k(S_t)=V_{k-1}(S_t)+\frac{1}{N_k(S_t)}(G_t-V_{k-1}(S_t)) \end{gathered}$

這樣一來挂脑，只需要保存上一輪的次數(shù)和對應(yīng)的收獲，即可求解當(dāng)前輪次的均值欲侮。如果數(shù)據(jù)量過大崭闲，以至于 $N_k(S_t)$ 無法準(zhǔn)確的計(jì)算，還可以使用一個(gè)系數(shù) $\alpha$ 來代替威蕉，將更新公式改為：

$V_k(S_t)=V_{k-1}(S_t)+\alpha(G_t-V_{k-1}(S_t))$

根據(jù)狀態(tài)價(jià)值函數(shù)的求解公式刁俭，同時(shí)可以類推出動(dòng)作價(jià)值函數(shù)的求解公式：

$Q_k(S_t,A_t)=Q_{k-1}(S_t,A_t)+\alpha(G_t-Q_{k-1}(S_t,A_t))$

策略迭代

與動(dòng)態(tài)規(guī)劃不同，蒙特卡洛法的目標(biāo)是得到最優(yōu)動(dòng)作函數(shù) $q_*$ 而不是最優(yōu)價(jià)值函數(shù) $v_*$ 韧涨。同時(shí)牍戚，蒙特卡洛法在進(jìn)行策略選取的時(shí)候，使用的也不是greedy法虑粥，而是 $\epsilon$ -greedy法如孝。

$\epsilon$ -greedy的區(qū)別是增加了一個(gè)參數(shù) $\epsilon$ 。在進(jìn)行策略選擇時(shí)娩贷，使用1- $\epsilon$ 的概率選擇當(dāng)前最大的動(dòng)作函數(shù)對應(yīng)的動(dòng)作第晰， $\epsilon$ 的概率隨機(jī)在 $m$ 個(gè)動(dòng)作中選取一個(gè)動(dòng)作。用公式表示如下：

$\pi(a|s)= \begin{cases} \epsilon/m+1-\epsilon &\text{if } a^*=\arg\max_{a\epsilon A}Q(s,a)\\ \epsilon/m &\text{else} \end{cases}$

一般來說 $\epsilon$ 的取值一般比較小彬祖，且在實(shí)際使用中會(huì)隨著訓(xùn)練的不斷迭代而減小茁瘦。在強(qiáng)化學(xué)習(xí)訓(xùn)練的過程中，通過這種隨機(jī)選取動(dòng)作的方式储笑，可以增加樣本的多樣性甜熔，探索到更多的樣本空間。

完整的算法流程如下:

初始化所有的動(dòng)作價(jià)值 $Q(s,a)=0$ 突倍，狀態(tài)次數(shù) $N(s,a)=0$ 腔稀，采樣次數(shù) $k=0$ ，隨機(jī)初始化一個(gè)策略 $\pi$ 羽历。
$k=k+1$ , 基于策略進(jìn)行第 $k$ 次蒙特卡羅采樣烧颖，得到一個(gè)完整的狀態(tài)序列:

$S_1,A_1,R_2,S_2,A_2,...,S_t,A_t,R_{t+1},...,R_T,S_T$
對于該狀態(tài)序列里出現(xiàn)的每一狀態(tài)行為對，計(jì)算其收獲, 更新其計(jì)數(shù)和行為價(jià)值函數(shù)：

$\begin{gathered} G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...\gamma^{T-t-1}R^T\\ N(S_t,A_t)=N(S_t,A_t)+1\\ Q(S_t,A_t)=Q(S_t,A_t)+\frac{1}{N(S_t,A_t)}(G_t-Q(S_t,A_t)) \end{gathered}$
基于新計(jì)算出的動(dòng)作價(jià)值窄陡，更新當(dāng)前的 $\epsilon$ -greedy策略：

$\begin{gathered} \epsilon=\frac{1}{k}\\ \pi(a|s)= \begin{cases} \epsilon/m+1-\epsilon &\text{if } a^*=\arg\max_{a\epsilon A}Q(s,a)\\ \epsilon/m &\text{else} \end{cases} \end{gathered}$
如果所有的 $Q(s,a)$ 收斂炕淮，則對應(yīng)的所有 $Q(s,a)$ 即為最優(yōu)的動(dòng)作價(jià)值函數(shù) $q_*$ 。對應(yīng)的策略即為最優(yōu)策略 $\pi_*$ 跳夭。否則轉(zhuǎn)到第二步涂圆。

時(shí)序差分TD

時(shí)序差分法與蒙特卡洛法一樣们镜，都是model-free強(qiáng)化學(xué)習(xí)問題的求解方法。區(qū)別在于润歉，時(shí)序差分法是在沒有采樣到完整的交互序列的情況下模狭，通過部分的狀態(tài)序列去估計(jì)狀態(tài)的價(jià)值。

策略評估

考慮狀態(tài)價(jià)值函數(shù)的另一種形式：

$v_\pi(s)=E_\pi(R_{t+1}+\gamma{v_{\pi}(S_{t+1})}|S_t=s)$

時(shí)序差分法用 $R_{t+1}+\gamma{v_{t+1}(s)}$ 來近似的代替收獲 $G_t$ 踩衩，使得只需要兩個(gè)連續(xù)的狀態(tài)和對應(yīng)的獎(jiǎng)勵(lì)嚼鹉，即可求解。 $R_{t+1}+\gamma{V(S_{t+1})}$ 一般稱為TD目標(biāo)值驱富， $R_{t+1}+\gamma{V(S_{t+1})}-V(S_t)$ 稱為TD誤差锚赤，用TD目標(biāo)值近似代替收獲的過程稱為引導(dǎo)(bootstrapping)。

因此褐鸥，時(shí)序差分 $G(t)$ 的表達(dá)式為：

$G(t)=R_{t+1}+\gamma V(S_{t+1})$

時(shí)序差分的價(jià)值函數(shù)迭代式為：

$\begin{gathered} V_k(S_t)=V_{k-1}(S_t)+\alpha(G_t-V_{k-1}(S_t))\\ Q_k(S_t,A_t)=Q_{k-1}(S_t,A_t)+\alpha(G_t-Q_{k-1}(S_t,A_t)) \end{gathered}$

其中 $\alpha$ 是一個(gè)值為[0,1]之間的數(shù)线脚。

策略迭代

對于時(shí)序差分，也可以用 $\epsilon$ -greedy來進(jìn)行價(jià)值迭代叫榕，和蒙特卡羅法的區(qū)別主要只是在于收獲的計(jì)算方式不同浑侥。

n步時(shí)序差分

普通的時(shí)序差分主要關(guān)注的是當(dāng)前時(shí)刻以及下一時(shí)刻的狀態(tài)價(jià)值，可以理解為向前一步來近似求解晰绎。n步時(shí)序差分的意思是向前n步來進(jìn)行求解寓落，其收獲 $G_t^{(n)}$ 的表達(dá)式如下：

$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+\gamma^{n-1}R_{t+n}+\gamma^nV(S_{t+n})$

當(dāng)n趨于無窮大時(shí)，即覆蓋到完整的交互序列時(shí)荞下，n步時(shí)序差分也就變成了蒙特卡洛零如。與普通的時(shí)序差分相比，n步時(shí)序差分因?yàn)榭紤]了向前n步锄弱，所以會(huì)更加精確一些考蕾。

TD( $\lambda$ )

在使用n步時(shí)序差分的時(shí)候，這個(gè)n是一個(gè)超參數(shù)会宪，需要通過不斷的優(yōu)化去選擇一個(gè)最優(yōu)的值肖卧。這一過程比較繁瑣，為了解決這個(gè)問題掸鹅，引入了一個(gè)值為[0,1]的參數(shù) $\lambda$ 塞帐。定義 $\lambda$ -收獲是n從1到 $\infty$ 所有步的收獲乘以權(quán)重的和，每一步的權(quán)重是 $(1-\lambda)\lambda^{n-1}$ 巍沙。

這樣 $\lambda$ -收獲可以表示為：

$G_t^\lambda=(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}G_t^{(n)}$

迭代函數(shù)可以表示為：

$\begin{gathered} V(S_t)=V(S_t)+\alpha(G_t^\lambda-V(S_t))\\ Q(S_t,A_t)=Q(S_t,A_t)+\alpha(G_t^\lambda-Q(S_t,A_t)) \end{gathered}$

從上面的式子可以看出葵姥，當(dāng) $\lambda$ 等于0時(shí)，算法就變成了普通的時(shí)序差分句携，當(dāng) $\lambda$ 等于1時(shí)榔幸，則變成了蒙特卡洛。因此，TD( $\lambda$ )就是在兩者之間作了一個(gè)平衡削咆。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末牍疏，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子拨齐，更是在濱河造成了極大的恐慌鳞陨，老刑警劉巖，帶你破解...
沈念sama閱讀 221,430評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件瞻惋，死亡現(xiàn)場離奇詭異厦滤，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)歼狼，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,406評論 3贊 398
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門掏导，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人蹂匹，你說我怎么就攤上這事“简冢” “怎么了限寞？”我有些...
開封第一講書人閱讀 167,834評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長仰坦。經(jīng)常有香客問我履植，道長，這世上最難降的妖魔是什么悄晃？我笑而不...
開封第一講書人閱讀 59,543評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任玫霎，我火速辦了婚禮，結(jié)果婚禮上妈橄，老公的妹妹穿的比我還像新娘庶近。我一直安慰自己，他們只是感情好眷蚓，可當(dāng)我...
茶點(diǎn)故事閱讀 68,547評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布鼻种。她就那樣靜靜地躺著，像睡著了一般沙热。火紅的嫁衣襯著肌膚如雪叉钥。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,196評論 1贊 308
城市分裂傳說
那天篙贸，我揣著相機(jī)與錄音投队，去河邊找鬼。笑死爵川，一個(gè)胖子當(dāng)著我的面吹牛敷鸦，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播，決...
沈念sama閱讀 40,776評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼轧膘，長吁一口氣：“原來是場噩夢啊……” “哼钞螟！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起谎碍，我...
開封第一講書人閱讀 39,671評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤鳞滨，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后蟆淀，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拯啦，經(jīng)...
沈念sama閱讀 46,221評論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,303評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年熔任，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了褒链。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,444評論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡疑苔，死狀恐怖甫匹，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情惦费，我是刑警寧澤兵迅，帶...
沈念sama閱讀 36,134評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站薪贫，受9級(jí)特大地震影響恍箭，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜瞧省，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,810評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一扯夭、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧鞍匾，春花似錦交洗、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,285評論 0贊 24
一樁弒父案藕筋，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至梳码，卻和暖如春隐圾，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背掰茶。一陣腳步聲響...
開封第一講書人閱讀 33,399評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工暇藏，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人濒蒋。一個(gè)月前我還...
沈念sama閱讀 48,837評論 3贊 376
代替公主和親
正文我出身青樓盐碱，卻偏偏與公主長得像把兔，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子瓮顽，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,455評論 2贊 359

如何求強(qiáng)化學(xué)習(xí)最優(yōu)解

predict和control

動(dòng)態(tài)規(guī)劃

蒙特卡洛法

時(shí)序差分TD

n步時(shí)序差分

推薦閱讀更多精彩內(nèi)容