一. 增強學(xué)習(xí)簡介
1.1 什么是增強學(xué)習(xí)？
機器學(xué)習(xí)的算法可以分為三類：監(jiān)督學(xué)習(xí)，非監(jiān)督學(xué)習(xí)和增強學(xué)習(xí)。 增強學(xué)習(xí)也稱為強化學(xué)習(xí)。
增強學(xué)習(xí)就是將情況映射為行為，也就是去最大化收益。學(xué)習(xí)者并不是被告知哪種行為將要執(zhí)行，而是通過嘗試學(xué)習(xí)到最大增益的行為并付諸行動。也就是說增強學(xué)習(xí)關(guān)注的是智能體如何在環(huán)境中采取一系列行為，從而獲得最大的累積回報。通過增強學(xué)習(xí)，一個智能體應(yīng)該知道在什么狀態(tài)下應(yīng)該采取什么行為。RL是從環(huán)境狀態(tài)到動作的映射的學(xué)習(xí)，我們把這個映射稱為策略。
比如：flappy bird是現(xiàn)在很流行的一款小游戲，不了解的同學(xué)可以點鏈接進去玩一會兒?，F(xiàn)在我們讓小鳥自行進行游戲，但是我們卻沒有小鳥的動力學(xué)模型，也不打算了解它的動力學(xué)。要怎么做呢？ 這時就可以給它設(shè)計一個增強學(xué)習(xí)算法，然后讓小鳥不斷的進行游戲，如果小鳥撞到柱子了，那就獲得-1的回報，否則獲得0回報。通過這樣的若干次訓(xùn)練，我們最終可以得到一只飛行技能高超的小鳥，它知道在什么情況下采取什么動作來躲避柱子。
增強學(xué)習(xí)和監(jiān)督學(xué)習(xí)的區(qū)別是：
1.? 增強學(xué)習(xí)是試錯學(xué)習(xí)(Trail-and-error)，由于沒有直接的指導(dǎo)信息，智能體要以不斷與環(huán)境進行交互，通過試錯的方式來獲得最佳策略。
2. ?延遲回報，增強學(xué)習(xí)的指導(dǎo)信息很少，而且往往是在事后（最后一個狀態(tài)）才給出的，這就導(dǎo)致了一個問題，就是獲得正回報或者負(fù)回報以后，如何將回報分配給前面的狀態(tài)。
增強學(xué)習(xí)的一個挑戰(zhàn)是exploration和exploitation之間的權(quán)衡。
Exploration就是嘗試之前沒有執(zhí)行過的動作以期望獲得超乎當(dāng)前最有行為的收益。
Exploitation就是執(zhí)行根據(jù)歷史經(jīng)驗學(xué)習(xí)到的獲得最大收益的動作。
1.2 增強學(xué)習(xí)構(gòu)成的元素
1.policy 定義為在給定時刻t下，智能體表現(xiàn)的方式。具體來說，policy就是從環(huán)境狀態(tài)到動作行為的一個映射。policy是增強學(xué)習(xí)的核心。
2.reward function定義為在增強學(xué)習(xí)問題中的目標(biāo)。具體來說，reward就是從環(huán)境狀態(tài)到獎勵的一個映射。智能體的任務(wù)就是在長期的過程中，不斷最大化所得的總獎勵。注意，這里的reward function指的是單次行為所造成環(huán)境狀態(tài)改變所帶來的獎勵，所以為即時獎勵。這個reward function定義了對智能體來說，什么是對的行為，什么是錯誤的行為。
3.value function定義為在長期獎勵。也就是說是reward function的累加。如果說reward function告訴智能體什么行為是好的壞的，那么value function告訴智能體的是長期以來你的行為是好的還是壞的。
感覺來說，追求最大的reward為第一位，value為第二位。因為沒有reward就沒有value而言。但是，對于決策動作來說，應(yīng)該考慮value為第一位因為我們追求的是長期的回報。對于估計reward是很簡單的，因為在執(zhí)行完當(dāng)前任務(wù)之后，就馬上能獲得回報。但是對value來說，回報需要經(jīng)過一段時間的動作執(zhí)行才能夠得到。所以，value estimation是增強學(xué)習(xí)一個核心的內(nèi)容。
雖然增強學(xué)習(xí)的核心是value estimation，但是也有例外的情況，這就是進化算法。進化算法直接在策略空間搜索最優(yōu)策略，對于策略空間較小或者易于求出策略空間的情況下，進化算法是有效的，另外當(dāng)環(huán)境狀態(tài)無法準(zhǔn)確感知的情況下，進化算法具有優(yōu)勢。
4. a model of environment定義為對環(huán)境行為的模擬。比如說，給定state和action，我們要估計下一個時刻的state和reward，這時候就需要model of environment作出預(yù)測。
二. 可衡量的反饋(Evaluative feedback)
2.1 多臂老虎機問題
在多臂老虎機問題中，每個行為有個對應(yīng)的期望或者平均reward，我們稱這個為value of this action。如果你知道每個行為所對應(yīng)的value，那么每次試驗?zāi)愣紩x擇對應(yīng)最大value的那個行為。但是我們假設(shè)你不知道每個行為所對應(yīng)的確切的value，但是你可有一個估計的value。
greedy action：如果保持估計value的話，那么在任何時刻都至少有一個action擁有最大的value。那么每次執(zhí)行這個對應(yīng)最大估計value的action，稱為greedy action。
Exploitation:每次選擇行為時選擇greedy action。
Exploration:每次選擇行為時選擇non-greedy action。
exploitation是正確的事，因為它每次都嘗試去最大化value的值，但是從長期來看，exploration可能會比exploitation帶來更大的收益。所以，需要在exploitation和exploration之間找到一個平衡。
2.2 Action-Value Method
聲明：Q*(a)表示action的真實值， Qt(a)表示action的估計值。
如何action a被執(zhí)行k次，并且得到reward是r1,....,rk，那么估計值就是
Qt(a) = (r1+r2+...+rk) / k
如果k=0，那么Qt(a) = 0； 如果k=∞，那么Qt(a)=Q*(a)
eplison-greedy methods：在大多數(shù)的時間內(nèi)使用exploitation,在eplison概率的情況下使用exploration。
eplison-greedy methods的好處取決于任務(wù)。如果該行為的value的方差很大，那么可以說eplison-greedy methods最終表現(xiàn)的會比greedy methods好。如果該行為的value的方差為0，那么可以說greedy methods更好，因為它每次都是執(zhí)行最大value的行為。
2.3 Soft-max Action Selection
eplison-greedy methods雖然有很多的好處，但是一個缺點就是在exploration的時候，選擇每個action的概率是一樣的。那么就是說，它很可能會選到一個最爛的action。soft-max action selection就是基于對這種情況的考慮，在exploration的時候，還是給greedy action最大的概率，其他的action根據(jù)其value的大小，按概率進行選擇。也就是說，最爛的行為被選到的概率是最小的。
2.4 Evaluation Versus Instruction
evaluative-feedback:當(dāng)執(zhí)行完一個行為后，得到的reward只是反映出你這個行為有多好，但是沒有一個明確的表態(tài)說你這個行為是正確的還是錯誤的。
instructive-feedback:當(dāng)執(zhí)行完一個行為后，它會告訴你這個行為是正確的還是錯誤的。所以在選擇行為的時候，就選擇在多大數(shù)時間內(nèi)提醒的是正確的動作。這種方法也被稱為supervised learning。
比如有100個行為，你選了第32號行為，那么evaluative-feedback會告訴你，你的score是7.2，那么instructive-feedback會說67號行為可能才是正確的行為。
2.5 Incremental Implementation
Qt(a) = (r1+r2+...+rk) / k 計算Qt(a)的話，要存好多的r1到rk的值，那么隨著時間的增長，需要的計算量和內(nèi)存都很大。那么Qt(a)可換一種方式表達：那么，可以表達為：
new estimate = old estimate + (target - old estimate) / step size
target - old estimate = error?
step size隨著k改變，從這個式子同樣可以看出，當(dāng)k趨近于無窮大的時候，這個error就很小，那么old estimate就幾乎約等于new estimate，也就是說收斂了。
2.6 Tracking a Nonstationary Problem
上面所討論的問題都是基于恒定的，假設(shè)多臂老虎機的action所對應(yīng)的值不是恒定的，是變化的，那又該如何處理。一個最典型的做法就是將step size設(shè)置為常數(shù)，因為2.4的公式中，step size是隨著執(zhí)行k次action而變化的。其中， alpha為step-size，是0-1之間的取值。這導(dǎo)致Qk為過去所得到的所有reward的weighted平均值和Q0.
因為
所以稱為weighted average。
2.7 Optimistic Initial Values
所有我們之前討論的方法都在一定程度上依賴于初始動作的值。初始動作值可以作為一種簡單的手段來鼓勵explore.
比如，多臂老虎機的問題，我們設(shè)置每個動作的初始估計值為5而不是0，動作的真實值是服從0，1正態(tài)分布。 那么無論你一開始選擇哪個動作，反饋總是小于初始估計值。那么，這種優(yōu)化機制會鼓勵去explore，因為每次動作的執(zhí)行，都會讓智能體很失望，因為真實值和估計值總是相差很大。所以即使是采用greedy的方法，那也會采取不同動作n次，直到估計值收斂。這個初始化方法對于stational的問題會鼓勵explore并且有效，但是對于nonstational的問題，就并能得到很好的效果。
2.8 Reinforcement Comparison
從直覺來說，一個動作能帶來更大的reward應(yīng)該多執(zhí)行些，帶來更小的reward應(yīng)該少執(zhí)行些。但是，怎么樣才知道一個動作帶來的reward是更大還是更小呢？這時候就需要和一個標(biāo)準(zhǔn)水平對比reward，叫做reference reward。reference reward通常來說就是前k個動作的帶來的reward 的平均值。
Reinforcement Comparison：就是一個基于下列想法的方法：當(dāng)一個動作帶來比reference reward更大的reward，那么就說這個reward更大。反之亦然。
所以該方法選擇action不是基于對value的估計，而只是計算一個均值。對某個動作的偏好可以用softmax表示：
該式子表示在t時刻選擇action a的概率。
pt(a)表示在t時刻，對action a的偏好程度。該偏好程度可通過下列公式進行更新：
Belta是一個正的step size參數(shù)。rt是即時reward，r-t是reference reward。從這個式子可以看出來，當(dāng)action帶來reward更大的時候，那么選擇該action的概率就會增大。反之亦然。
reference reward的更新通過下面這個公式進行：alpha是在于[0,1]之間取值的step size的參數(shù)。
2.9 Pursuit Methods
Pursuit Methods：這個方法是action-value和action preference的結(jié)合。該思想是不斷的‘pursuit’ greedy action（就是Q最大的那個action）然后通過action preference來更新對該action的偏好。
對該greedy action選擇的概率的更新如下：
對其他的action選擇的概率的更新如下：
對Q的更新同value-action的方法。
2.10 Associative Search
到目前為止，我們還沒考慮過一種情況，那就是不同動作要對應(yīng)不同的情況。我們考慮的都是在task是stationary的時候，采取單一最優(yōu)動作，或者在task是nonstationary的時候采取一系列最優(yōu)動作以滿足環(huán)境的變化。但是，在通常的強化學(xué)習(xí)任務(wù)中，設(shè)計到的環(huán)境變化往往不是單一的，所以我們要讓智能體學(xué)會如何在不同的環(huán)境中，采取不同的動作。
還是老虎機的例子，你可能面對n個賭博臂，如果每次變化是隨機的，那你面對的是單一的nonstationary的問題，如果每次變化是固定的，那你面對的是單一的stationary的問題。那么，能不能換個復(fù)雜點的情況。就是每當(dāng)你選擇不同的賭博臂的時候，老虎機的提示燈顏色變化不同，這個可以作為你選擇賭博臂的一個提示。比如說，所學(xué)到的結(jié)果是，當(dāng)是紅色提示燈的時候，選擇1號賭博臂，當(dāng)時黃色提示燈的時候，選擇2號賭博臂。所以，這個是強化學(xué)習(xí)更典型的一個問題。因此，這時候會需要state表示你周圍的環(huán)境，將其與action聯(lián)系起來。在接下來的一章會展開介紹。
三. 馬爾可夫鏈
3.1 The Agent-Environment Interface
agent：學(xué)習(xí)者和決策者
environment：除了agent之外的任何一切
state：環(huán)境的抽象表達
policy：agent會生成一個從state到選擇action的概率的一個映射，這個映射為policy。
3.2 Goals and Rewards
reward：要設(shè)置為我們想達到的目標(biāo)。如果agent為我們的目標(biāo)做出了行動，那么就應(yīng)該給它獎勵。明確的是，這個獎勵的信號應(yīng)該定義為你想要達成的目標(biāo)是什么，而不是告訴它如何去達成這個目標(biāo)，比如設(shè)置子任務(wù)之類的。所以來說reward和goal是相連的，我們的goal決定了reward的定義。
3.3 Returns
Return 的無限表達：簡單地，我們可以將return定義為reward的和：episodic tasks：在任務(wù)中，有一個自然的表示任務(wù)終結(jié)的時間點，我們把這個開始到結(jié)束的一個過程稱為episode，比如說一盤游戲的結(jié)束，一盤棋的結(jié)束等。每個episode結(jié)束的那個特殊的state稱為terminal state。所有的nonterminal state的集合用S表示，含有terminal state的S用S+表示。episodic tasks能應(yīng)用上面定義的return。
continuing tasks：但是不同于episodic tasks，有的任務(wù)并沒有自然的終止過程。比如一個任務(wù)需要貫穿一個agent的一生。所以對于這種任務(wù)而言，終止時間T=∞。所以，對于return來說，很有肯能就是∞，假設(shè)定義r為1.
Return的有限表達：discount rate決定了未來reward在當(dāng)前的價值。如何r<1，那么一個無限的和就會有一個有限的值。如果r=0，那么agent是鼠目寸光的，只關(guān)心當(dāng)前reward的最大回報就好。如果r趨近于1，那么agent是很有遠見的，未來reward對當(dāng)前價值的影響越大。
3.4 Unified Notation for Episodic and Continuing Tasks
S_t,i 表示在時間t，第i個episode的狀態(tài)。但是因為每個episode的狀態(tài)具有共性，所以常用S_t代替S_t,i。此表示法同樣的道理用于a_t,i, r_t,i等。absorbing state：僅在自身和reward為0之間轉(zhuǎn)換。如上圖實心正方形所示。
上圖可知，無論是加S0-S2，還是S0-S∞，結(jié)果都是3.所以，這個對有限的reward也適用，因為其可以表示為：所以，用這個表示episode和continuing tasks的關(guān)系。
3.5 馬爾科夫特性
Markov property: 馬爾可夫性(無后效性)，也就是指系統(tǒng)的下個狀態(tài)只與當(dāng)前狀態(tài)信息有關(guān)，而與更早之前的狀態(tài)無關(guān)。
state： 對agent來說一切有用的外界信息。
Markov：所有的state信號能成功的表示所有相關(guān)的信息。
試想下，如果在t的時刻采取的動作，那么在t+1的時刻，環(huán)境對行為會產(chǎn)生什么反應(yīng)？所以這個是個動態(tài)的過程，用數(shù)學(xué)可表示為：但是，如果這個state符合馬爾科夫特性，那么在t+1時刻的反應(yīng)僅僅依賴于t時刻的state和action。甚至在一些不符合馬爾科夫的state里，我們可以認(rèn)為它們近似于馬爾科夫特性。
3.6 馬爾科夫決策過程
Markov decision process（MDP）：符合馬爾科夫特性的增強學(xué)習(xí)任務(wù)叫做馬爾科夫決策過程。與上面不同的是MDP考慮了動作，即系統(tǒng)下個狀態(tài)不僅和當(dāng)前的狀態(tài)有關(guān)，也和當(dāng)前采取的動作有關(guān)。舉下棋的例子，當(dāng)我們在某個局面（狀態(tài)s）走了一步(動作a)，這時對手的選擇（導(dǎo)致下個狀態(tài)s’）我們是不能確定的，但是他的選擇只和s和a有關(guān)，而不用考慮更早之前的狀態(tài)和動作，即s’是根據(jù)s和a隨機生成的。
Hidden Markov Model（HMM）:它用來描述一個含有隱含未知參數(shù)的馬爾可夫過程。
www.cnblogs.com/skyme/p/4651331.html
finite Markov decision process：如果state和action的空間是有限的，那么稱為有限的馬爾科夫決策過程。
給定state St和action a，下一個狀態(tài)St+1的概率是：
給定state St和action a，下一個狀態(tài)reward的是：3.7 Value Functions
State-value function:
the value of a state under a policy, denoted Vpai(s)
Action-value function:
在Qπ(s,a)中，不僅策略π和初始狀態(tài)s是我們給定的，當(dāng)前的動作a也是我們給定的，這是Qπ(s,a)和Vπ(a)的主要區(qū)別。
例子：
blog.csdn.net/zz_1215/article/details/44138823
3.8 貝爾曼方程（Bellman Equation）
Bellman equation：
Vπ(s,a)和Qπ(s,a)這兩個式子稱為貝爾曼方程，它表明了當(dāng)前狀態(tài)的值函數(shù)與下個狀態(tài)的值函數(shù)的關(guān)系。optimal policy: 當(dāng)且僅當(dāng)一個policy比之前的policy所帶來的Value相等或者更好，這個policy稱為最優(yōu)policy。
optimal state-value function：optimal action-value function：
四. 動態(tài)規(guī)劃
增強學(xué)習(xí)的目的就是求解馬爾可夫決策過程(MDP)的最優(yōu)策略，使其在任意初始狀態(tài)下，都能獲得最大的Vπ值。(本文不考慮非馬爾可夫環(huán)境和不完全可觀測馬爾可夫決策過程(POMDP)中的增強學(xué)習(xí))。那么如何求解最優(yōu)策略呢？基本的解法有三種：動態(tài)規(guī)劃法(dynamic programming methods)，蒙特卡羅方法(Monte Carlo methods)，時間差分法(temporal difference)。動態(tài)規(guī)劃法是其中最基本的算法，也是理解后續(xù)算法的基礎(chǔ)。
動態(tài)規(guī)劃是一種通過把復(fù)雜問題劃分為子問題，并對自問題進行求解，最后把子問題的解結(jié)合起來解決原問題的方法?！竸討B(tài)」是指問題由一系列的狀態(tài)組成，而且狀態(tài)能一步步地改變，「規(guī)劃」即優(yōu)化每一個子問題。因為MDP 的 Markov 特性，即某一時刻的子問題僅僅取決于上一時刻的子問題的 action，并且 Bellman 方程可以遞歸地切分子問題，所以我們可以采用動態(tài)規(guī)劃來求解 Bellman 方程。
優(yōu)化目標(biāo)：
4.1 Policy Evaluation
policy evaluation: ?對于任意的policy，計算state-value function。
對于確定性策略，值函數(shù)：
擴展到更一般的情況，如果在某策略π下，π(s)對應(yīng)的動作a有多種可能，每種可能記為π(a|s)，則狀態(tài)值函數(shù)定義如下：
一般采用迭代的方法更新狀態(tài)值函數(shù)，首先將所有Vπ(s)的初值賦為0（其他狀態(tài)也可以賦為任意值，不過吸收態(tài)必須賦0值），然后采用如下式子更新所有狀態(tài)s的值函數(shù)（第k+1次迭代）：
對于Vπ(s)，僅用一個數(shù)組保存各狀態(tài)值函數(shù)，每當(dāng)?shù)玫揭粋€新值，就將舊的值覆蓋,形如[Vk+1(s1),Vk+1(s2),Vk(s3)..]，第k+1次迭代的Vπ(s)可能用到第k+1次迭代得到的Vπ(s')。更新算法如下：
4.2 Policy Improvement
Policy Improvement：上一節(jié)中進行策略估計的目的，是為了尋找更好的策略，這個過程叫做策略改進。
假設(shè)我們有一個策略π，并且確定了它的所有狀態(tài)的值函數(shù)Vπ(s)。對于某狀態(tài)s，有動作a0=π(s)。 那么如果我們在狀態(tài)s下不采用動作a0，而采用其他動作a≠π(s)是否會更好呢？要判斷好壞就需要我們計算行為值函數(shù)Qπ(s,a)。
評判標(biāo)準(zhǔn)是：Qπ(s,a)是否大于Vπ(s)。如果Qπ(s,a)> Vπ(s)，那么至少說明新策略【僅在狀態(tài)s下采用動作a，其他狀態(tài)下遵循策略π】比舊策略【所有狀態(tài)下都遵循策略π】整體上要更好。
策略改進定理(policy improvement theorem)：π和π'是兩個確定的策略，如果對所有狀態(tài)s∈S有Qπ(s,π'(s))≥Vπ(s)，那么策略π'必然比策略π更好，或者至少一樣好。其中的不等式等價于Vπ'(s)≥Vπ(s)。
有了在某狀態(tài)s上改進策略的方法和策略改進定理，我們可以遍歷所有狀態(tài)和所有可能的動作a，并采用貪心策略來獲得新策略π'。即對所有的s∈S, 采用下式更新策略：
這種采用關(guān)于值函數(shù)的貪心策略獲得新策略，改進舊策略的過程，稱為策略改進(Policy Improvement)。
4.3 Policy Iteration
策略迭代算法就是上面兩節(jié)內(nèi)容的組合。假設(shè)我們有一個策略π，那么我們可以用policy evaluation獲得它的值函數(shù)Vπ(s)，然后根據(jù)policy improvement得到更好的策略π'，接著再計算Vπ'(s),再獲得更好的策略π''，整個過程順序進行如下圖所示：算法如下：
4.4 Value Iteration
policy iteration的缺點：在每次的policy iteration中，都包含了policy evaluation，因為policy evaluation自身則需要掃描(sweep)所有的狀態(tài)若干次，其中巨大的計算量直接影響了策略迭代算法的效率。我們必須要獲得精確的Vπ值嗎？事實上不必，有幾種方法可以在保證算法收斂的情況下，縮短策略估計的過程。
Value Iteration：policy iteration的policy evaluation可以被簡化以至于不會失去其收斂的保證。Value Iteration就是其中一種簡化的辦法。它的每次迭代只掃描(sweep)了每個狀態(tài)一次。值迭代的每次迭代對所有的s∈S按照下列公式更新：
即在值迭代的第k+1次迭代時，直接將能獲得的最大的Vπ(s)值賦給Vk+1。值迭代算法直接用可能轉(zhuǎn)到的下一步s'的V(s')來更新當(dāng)前的V(s)，算法甚至都不需要存儲策略π。而實際上這種更新方式同時卻改變了策略πk和V(s)的估值Vk(s)。 直到算法結(jié)束后，我們再通過V值來獲得最優(yōu)的π。此外，值迭代還可以理解成是采用迭代的方式逼近1中所示的貝爾曼最優(yōu)方程。
值迭代完整的算法如圖所示：
由上面的算法可知，值迭代的最后一步，我們才根據(jù)V*(s)，獲得最優(yōu)策略π*。
一般來說值迭代和策略迭代都需要經(jīng)過無數(shù)輪迭代才能精確的收斂到V*和π*， 而實踐中，我們往往設(shè)定一個閾值來作為中止條件，即當(dāng)Vπ(s)值改變很小時，我們就近似的認(rèn)為獲得了最優(yōu)策略。在折扣回報的有限MDP(discounted finite MDPs)中，進過有限次迭代，兩種算法都能收斂到最優(yōu)策略π*。
動態(tài)規(guī)劃的優(yōu)點在于它有很好的數(shù)學(xué)上的解釋，但是動態(tài)要求一個完全已知的環(huán)境模型，這在現(xiàn)實中是很難做到的。
4.5 Asynchronous Dynamic Programming（異步動態(tài)規(guī)劃）
動態(tài)規(guī)劃的缺點：在上面討論過的DP中，它涉及了對所有狀態(tài)集的掃描。當(dāng)狀態(tài)數(shù)量較大的時候，動態(tài)規(guī)劃法的效率也將是一個問題。異步動態(tài)規(guī)劃就很好的解決了這個問題。
These algorithms back up the values of states in any order whatsoever, using whatever values of other states happen to be available. The values of some states may be backed up several times before the values of others are backed up once.
4.6 Generalized Policy Iteration
Generalized Policy Iteration：我們使用廣義策略迭代（GPI）一詞來引用policy evaluation和policy improvement過程互動的一般思路，而不依賴于兩個流程的粒度和其他細節(jié)。
GPI可表示為如下：
五. 蒙特卡洛方法
蒙特卡羅方法又叫統(tǒng)計模擬方法，它使用隨機數(shù)（或偽隨機數(shù)）來解決計算的問題，是一類重要的數(shù)值計算方法。該方法的名字來源于世界著名的賭城蒙特卡羅，而蒙特卡羅方法正是以概率為基礎(chǔ)的方法。
一個簡單的例子可以解釋蒙特卡羅方法，假設(shè)我們需要計算一個不規(guī)則圖形的面積，那么圖形的不規(guī)則程度和分析性計算（比如積分）的復(fù)雜程度是成正比的。而采用蒙特卡羅方法是怎么計算的呢？首先你把圖形放到一個已知面積的方框內(nèi)，然后假想你有一些豆子，把豆子均勻地朝這個方框內(nèi)撒，散好后數(shù)這個圖形之中有多少顆豆子，再根據(jù)圖形內(nèi)外豆子的比例來計算面積。當(dāng)你的豆子越小，撒的越多的時候，結(jié)果就越精確。
現(xiàn)在我們開始講解增強學(xué)習(xí)中的蒙特卡羅方法，與上篇的DP不同的是，這里不需要對環(huán)境的完整知識。蒙特卡羅方法僅僅需要經(jīng)驗就可以求解最優(yōu)策略，這些經(jīng)驗可以在線獲得或者根據(jù)某種模擬機制獲得。
要注意的是，我們僅將蒙特卡羅方法定義在episode task上，所謂的episode task就是指不管采取哪種策略π，都會在有限時間內(nèi)到達終止?fàn)顟B(tài)并獲得回報的任務(wù)。比如玩棋類游戲，在有限步數(shù)以后總能達到輸贏或者平局的結(jié)果并獲得相應(yīng)回報。
那么什么是經(jīng)驗?zāi)?？?jīng)驗其實就是訓(xùn)練樣本。比如在初始狀態(tài)s，遵循策略π，最終獲得了總回報R，這就是一個樣本。如果我們有許多這樣的樣本，就可以估計在狀態(tài)s下，遵循策略π的期望回報，也就是狀態(tài)值函數(shù)Vπ(s)了。蒙特卡羅方法就是依靠樣本的平均回報來解決增強學(xué)習(xí)問題的。
盡管蒙特卡羅方法和動態(tài)規(guī)劃方法存在諸多不同，但是蒙特卡羅方法借鑒了很多動態(tài)規(guī)劃中的思想。在動態(tài)規(guī)劃中我們首先進行策略估計，計算特定策略π對應(yīng)的Vπ和Qπ，然后進行策略改進，最終形成策略迭代。這些想法同樣在蒙特卡羅方法中應(yīng)用。
5.1 Monte Carlo Policy Evaluation（State Values）
every-visit MC method：Vπ(s)是在所有的episodes里，每次對state s訪問產(chǎn)生的所有回報的平均值。
first-visit MC method：Vπ(s)是在所有的episodes里，第一次對state s訪問產(chǎn)生的所有回報的平均值。
first-visit MC method的算法如下：
舉例如下：
5.2 Monte Carlo Estimation of Action Values
如果模型是不可知的，那么此時去估計action values比state values來的更好。如果模型已知，只要state values就足夠了；如果模型未知，只有state values是不夠的。因為在狀態(tài)轉(zhuǎn)移概率p(s'|a,s)已知的情況下，策略估計后有了新的值函數(shù)，我們就可以進行策略改進了，只需要看哪個動作能獲得最大的期望累積回報就可以。然而在沒有準(zhǔn)確的狀態(tài)轉(zhuǎn)移概率的情況下這是不可行的。為此，我們需要估計動作值函數(shù)Qπ(s,a)。Qπ(s,a)的估計方法前面類似，即在狀態(tài)s下采用動作a，后續(xù)遵循策略π獲得的期望累積回報即為Qπ(s,a)，依然用平均回報來估計它。有了Q值，就可以進行策略改進了
持續(xù)探索(Maintaining Exploration)：
下面我們來探討一下Maintaining Exploration的問題。前面我們講到，我們通過一些樣本來估計Q和V，并且在未來執(zhí)行估值最大的動作。這里就存在一個問題，假設(shè)在某個確定狀態(tài)s0下，能執(zhí)行a0, a1, a2這三個動作，如果智能體已經(jīng)估計了兩個Q函數(shù)值，如Q(s0,a0), Q(s0,a1)，且Q(s0,a0)>Q(s0,a1)，那么它在未來將只會執(zhí)行一個確定的動作a0。這樣我們就無法更新Q(s0,a1)的估值和獲得Q(s0,a2)的估值了。這樣的后果是，我們無法保證Q(s0,a0)就是s0下最大的Q函數(shù)。
Maintaining Exploration的思想很簡單，就是用softpolicies來替換確定性策略，使所有的動作都有可能被執(zhí)行。比如其中的一種方法是ε-greedy policy，即在所有的狀態(tài)下，用1-ε的概率來執(zhí)行當(dāng)前的最優(yōu)動作a0，ε的概率來執(zhí)行其他動作a1, a2。這樣我們就可以獲得所有動作的估計值，然后通過慢慢減少ε值，最終使算法收斂，并得到最優(yōu)策略。簡單起見，在下面MC控制中，我們使用exploring start，即僅在第一步令所有的a都有一個非零的概率被選中。
5.3 Monte Carlo Control
我們看下MC版本的策略迭代過程：
根據(jù)前面的說法，值函數(shù)Qπ(s,a)的估計值需要在無窮多episode后才能收斂到其真實值。這樣的話策略迭代必然是低效的。在上一篇DP中，我們了值迭代算法，即每次都不用完整的策略估計，而僅僅使用值函數(shù)的近似值進行迭代，這里也用到了類似的思想。每次策略的近似值，然后用這個近似值來更新得到一個近似的策略，并最終收斂到最優(yōu)策略。這個思想稱為廣義策略迭代。
具體到MC control，就是在每個episode后都重新估計下動作值函數(shù)（盡管不是真實值），然后根據(jù)近似的動作值函數(shù)，進行策略更新。這是一個episode by episode的過程。
一個采用exploring starts的Monte Carlo control算法，如下圖所示，稱為Monte Carlo ES。而對于所有狀態(tài)都采用softpolicy的版本，這里不再討論。
Monte Carlo方法的一個顯而易見的好處就是我們不需要環(huán)境模型了，可以從經(jīng)驗中直接學(xué)到策略。它的另一個好處是，它對所有狀態(tài)s的估計都是獨立的，而不依賴與其他狀態(tài)的值函數(shù)。在很多時候，我們不需要對所有狀態(tài)值進行估計，這種情況下蒙特卡羅方法就十分適用。
不過，現(xiàn)在增強學(xué)習(xí)中，直接使用MC方法的情況比較少，而較多的采用TD算法族。但是如同DP一樣，MC方法也是增強學(xué)習(xí)的基礎(chǔ)之一，因此依然有學(xué)習(xí)的必要。
5.4? On-Policy Monte Carlo Control
你估計policy或者value-function的時候，需要用到一些樣本，這些樣本也是需要采用某種策略（可能固定、可能完全隨機、也可能隔一段時間調(diào)整一次）生成的。那么，判斷on-policy和off-policy的關(guān)鍵在于，你所估計的policy或者value-function和你生成樣本時所采用的policy? 是不是一樣。如果一樣，那就是on-policy的，否則是off-policy的?；趀xperience replay的方法基本上都是off-policy的。
on-policy: On-policy methods attempt to evaluate or improve the policy that is used to make decisions.
epsilon-soft on policy算法如下：
5.5 Off-Policy Monte Carlo Control
off-policy: the distinguishing feature of on-policy methods is that they estimate the value of a policy while using it for control. In off-policy methods these two functions are separated. The policy used to generate behaviour, called the behaviour policy, may in fact be unrelated to the policy that is evaluated and improved, called the estimation policy. An advantage of this separation is that the estimation policy may be deterministic (e.g., greedy), while the behaviour policy can continue to sample all possible actions.
off-policy算法如下：
六. 時間差分學(xué)習(xí)
對于動態(tài)規(guī)劃算法有如下特性：
1. 需要環(huán)境模型，即狀態(tài)轉(zhuǎn)移概率Psa。需要環(huán)境模型指的是，需要環(huán)境已知，比如grid的游戲，當(dāng)前狀態(tài)已知，并且知道采取哪個動作，那么下一個狀態(tài)一定是已知的，即你將會出現(xiàn)在grid的哪個格子中。
2. 狀態(tài)值函數(shù)的估計是自舉的(bootstrapping)，即當(dāng)前狀態(tài)值函數(shù)的更新依賴于已知的其他狀態(tài)值函數(shù)。
相對的，蒙特卡羅方法的特點則有：
1. 可以從經(jīng)驗中學(xué)習(xí)不需要環(huán)境模型。不需要環(huán)境模型指的是，允許環(huán)境位置。比如開車的小游戲，那么僅僅知道你當(dāng)前的狀態(tài)和你下一個將要采取的動作，你是不知道下一狀態(tài)的。因為你可以覺得你自己的狀態(tài)，可是什么時候你前面會出現(xiàn)一輛車子這個是未知的。所以，這種情況是環(huán)境位置，所以需要蒙特卡洛用概率去估計你下一個的狀態(tài)。
2. 狀態(tài)值函數(shù)的估計是相互獨立的
3. 只能用于episode tasks
而我們希望的算法是這樣的：
1. 不需要環(huán)境模型
2. 它不局限于episode task，可以用于連續(xù)的任務(wù)
時間差分學(xué)習(xí)(Temporal-Difference learning, TD learning)正是具備了上述特性的算法，它結(jié)合了DP和MC，并兼具兩種算法的優(yōu)點。
6.1 TD Prediction
在介紹TD learning之前，我們先引入如下簡單的蒙特卡羅算法，我們稱為constant-αMC，它的狀態(tài)值函數(shù)更新公式如下：其中Rt是每個episode結(jié)束后獲得的實際累積回報，α是學(xué)習(xí)率，這個式子的直觀的理解就是用實際累積回報Rt作為狀態(tài)值函數(shù)V(st)的估計值。具體做法是對每個episode，考察實驗中st的實際累積回報Rt和當(dāng)前估計V(st)的偏差值，并用該偏差值乘以學(xué)習(xí)率來更新得到V(St)的新估值。不同的是，對于蒙特卡羅算法，必須等到一個episode結(jié)束之后才能知道Rt, 但是TD算法只要等到下一個時間點t+1即可獲得rt.
所以，最簡單的TD方法，即TD(0)：
與MC不同的是，TD(0)用代替了Rt.
為什么修改成這種形式呢，我們回憶一下狀態(tài)值函數(shù)的定義：容易發(fā)現(xiàn)MC是利用6.3的形式去估計target，而DP是利用6.4的形式去估計target。The Monte Carlo target is an estimate because the expected value in(6.3) is not known; a sample return is used in place of the real expected return. The DP target is an estimate not because of the expected values, which are assumed to be completely provided by a model of the environment, but because Vpai(St+1) is not known and the current estimate, ,Vt(s+1) is used instead. The TD target is an estimate for both reasons: it samples the expected values in(6.4) and it uses the current estimate instead of the true. Thus, TD methods combine the sampling of Monte Carlo with the bootstrapping of DP. 即利用真實的立即回報rt+1和下個狀態(tài)的值函數(shù)V(st+1)來更新V(st)，這種方式就稱為時間差分(temporal difference)。由于我們沒有狀態(tài)轉(zhuǎn)移概率，所以要利用多次實驗來得到期望狀態(tài)值函數(shù)估值。類似MC方法，在足夠多的實驗后，狀態(tài)值函數(shù)的估計是能夠收斂于真實值的。
那么MC和TD(0)的更新公式的有何不同呢？我們舉個例子，假設(shè)有以下8個episode, 其中A-0表示經(jīng)過狀態(tài)A后獲得了回報0:
首先我們使用constant-ααMC方法估計狀態(tài)A的值函數(shù)，其結(jié)果是V(A)=0V(A)=0，這是因為狀態(tài)A只在episode 1出現(xiàn)了一次，且其累計回報為0。
現(xiàn)在我們使用TD(0)的更新公式，簡單起見取λ=1λ=1，我們可以得到V(A)=0.75V(A)=0.75。這個結(jié)果是如何計算的呢？ 首先，狀態(tài)B的值函數(shù)是容易求得的，B作為終止?fàn)顟B(tài)，獲得回報1的概率是75%，因此V(B)=0.75V(B)=0.75。接著從數(shù)據(jù)中我們可以得到狀態(tài)A轉(zhuǎn)移到狀態(tài)B的概率是100%并且獲得的回報為0。根據(jù)公式(2)可以得到V(A)←V(A)+α[0+λV(B)?V(A)]V(A)←V(A)+α[0+λV(B)?V(A)]，可見在只有V(A)=λV(B)=0.75V(A)=λV(B)=0.75的時候，式(2)收斂。對這個例子，可以作圖表示：
可見式(2)由于能夠利用其它狀態(tài)的估計值，其得到的結(jié)果更加合理，并且由于不需要等到任務(wù)結(jié)束就能更新估值，也就不再局限于episode task了。此外，實驗表明TD(0)從收斂速度上也顯著優(yōu)于MC方法。
將式(2)作為狀態(tài)值函數(shù)的估計公式后，前面文章中介紹的策略估計算法就變成了如下形式，這個算法稱為TD prediction:
6.2 Advantages of TD Prediction Methods
1. ?Comparing with DP, TD does not require a model of the environment, of its reward and next-state probability distributions.
2. Comparing with MC, TD is naturally implemented in an on-line, fully incremental fashion. With Monte Carlo methods one must wait until the end of an episode, because only then is the return known, whereas with TD methods one need wait only one time step.
3. ?Some Monte Carlo methods must ignore or discount episodes on which experimental actions are taken, which can greatly slow learning. TD methods are much less susceptible to these problems because they learn from each transition regardless of what subsequent actions are taken.
6.3 Optimality of TD(0)
batch updating: updates are made only after processing each complete batch of training data. 假設(shè)只能獲得有限數(shù)量的經(jīng)驗，比如說10個片段或者100個時間步長。在這種情況下，一個通用的增量式學(xué)習(xí)方法的策略是重復(fù)的學(xué)習(xí)這些經(jīng)驗直到方法收斂到一個答案。給定一個近似值函數(shù)V,在每一個時間步長t，當(dāng)一個非終止?fàn)顟B(tài)被訪問的時候，由上面的式子計算。但是值函數(shù)只更新1次，用所有增量的和。然后重復(fù)直到收斂。我們稱之為批更新因為更新發(fā)生在處理完每一批訓(xùn)練數(shù)據(jù)之后。
在批更新下，TD(0)確定的收斂到一個答案并且獨立于步長參數(shù)α，只要α足夠小。MC方法也收斂到一個確定的答案，但是是一個不同的解。理解這兩個解的不同將有助于我們理解這兩種方法的不同。
6.4 Sarsa: On-Policy TD Control
現(xiàn)在我們利用TD prediction組成新的強化學(xué)習(xí)算法，用到?jīng)Q策/控制問題中。在這里，強化學(xué)習(xí)算法可以分為在線策略(on-policy)和離線策略(off-policy)兩類。首先要介紹的sarsa算法屬于on-policy算法。
與前面DP方法稍微有些區(qū)別的是，sarsa算法估計的是動作值函數(shù)(Q函數(shù))而非狀態(tài)值函數(shù)。也就是說，我們估計的是策略π下，任意狀態(tài)s上所有可執(zhí)行的動作a的動作值函數(shù)Qπ(s,a)，Q函數(shù)同樣可以利用TD Prediction算法估計。如下就是一個狀態(tài)-動作對序列的片段及相應(yīng)的回報值。
給出sarsa的動作值函數(shù)更新公式如下：可見上式與TD(0)的形式基本一致。需要注意的是，對于每個非終止的狀態(tài)st，在到達下個狀態(tài)st+1后，都可以利用上述公式更新Q(st,At)，而如果stst是終止?fàn)顟B(tài)，則要令Q(st+1=0,at+1。由于動作值函數(shù)的每次更新都與(st,at,rt+1,st+1,at+1)相關(guān)，因此算法被命名為sarsa算法。
Sarsa的算法如下：
6.5 Q-Learning: Off-Policy TD Control
在sarsa算法中，選擇動作時遵循的策略和更新動作值函數(shù)時遵循的策略是相同的，即??greedy??greedy的策略，而在接下來介紹的Q-learning中，動作值函數(shù)更新則不同于選取動作時遵循的策略，這種方式稱為離策略(Off-Policy)。Q-learning的動作值函數(shù)更新公式如下：Q-learning 算法如下：
Sarsa和Q-learning的唯一不同之處不是在于動作的選取。不同之處在于Q(s,a)的更新。因為Q-learning的動作選取是eplison-greedy,也就是說不是每次都是選擇Q-max的動作,但是更新的時候，他都是按照Q-max的選擇的那個動作去更新的。這樣造成的后果就是有時候，選擇執(zhí)行的那個動作和更新的時候選擇的那個動作會不一樣。但是，對于sarsa來說，每次選取執(zhí)行的動作和更新的動作是完全一致的。換句話來說，當(dāng)時完全greedy的情況下，那么sarsa和Q-learning的更新是一樣的。
6.6 Actor-Critic Methods
一句話概括 Actor Critic 方法:
結(jié)合了 Policy Gradient (Actor) 和 Function Approximation (Critic) 的方法.Actor基于概率選行為,Critic基于Actor的行為評判行為的得分,Actor根據(jù)Critic的評分修改選行為的概率.
Actor Critic 方法的優(yōu)勢: 可以進行單步更新, 比傳統(tǒng)的 Policy Gradient 要快.Actor Critic 方法的劣勢: 取決于 Critic 的價值判斷, 但是 Critic 難收斂, 再加上 Actor 的更新, 就更難收斂. 為了解決收斂問題, Google Deepmind 提出了Actor Critic升級版Deep Deterministic Policy Gradient. 后者融合了 DQN 的優(yōu)勢, 解決了收斂難的問題.
critic是state-value function，在每次動作選擇完成后，critic估計這個動作使得結(jié)果變好了還是變壞了。這個估計就是TD誤差：
如果這個誤差是正的，那么說明這個動作將來被選去的概率要增大，反之亦然。
actor選取動作是根據(jù)softmax方程：
p(s,a)表示t時刻actor的可修正的策略參數(shù)，即在每個狀態(tài)s選擇action a的概率。概率更新如下：
6.7 R-Learning for Undiscounted Continuing Tasks
R學(xué)習(xí)是一種離線策略控制方法，用于沒有折扣和不能分成片段式任務(wù)的高級增強學(xué)習(xí)方法。算法如下：
