強(qiáng)化學(xué)習(xí)入門基礎(chǔ)
文章目錄
1. 強(qiáng)化學(xué)習(xí)基礎(chǔ)知識
1.1 強(qiáng)化學(xué)習(xí)發(fā)展歷程
1.3 強(qiáng)化學(xué)習(xí)應(yīng)用
1.5 強(qiáng)化學(xué)習(xí)智能體的主要組成部分
1. 強(qiáng)化學(xué)習(xí)基礎(chǔ)知識
強(qiáng)化學(xué)習(xí)（reinforcement learning）是受行為心理學(xué)啟發(fā)的一個機(jī)器學(xué)習(xí)領(lǐng)域，其研究的是智能體（agent）如何在一個環(huán)境（environment）中采取動作（action）以最大化我們想要的獎勵（reward）序调。這是一個涵蓋領(lǐng)域非常廣的問題州泊，也在博弈論酱讶、控制論、信息論樊零、運(yùn)籌學(xué)、基于模擬的優(yōu)化容贝、多代理系統(tǒng)、集群智能之景、統(tǒng)計學(xué)和遺傳算法等許多學(xué)科領(lǐng)域得到了研究斤富。在運(yùn)籌學(xué)和控制論領(lǐng)域，強(qiáng)化學(xué)習(xí)方法所在的領(lǐng)域被稱為近似動態(tài)規(guī)劃锻狗。
1.1 強(qiáng)化學(xué)習(xí)發(fā)展歷程
1956年Bellman提出了動態(tài)規(guī)劃方法满力。
1977年Werbos提出只適應(yīng)動態(tài)規(guī)劃算法。
1988年sutton提出時間差分算法轻纪。
1992年Watkins 提出Q-learning 算法油额。
1994年rummery 提出Saras算法。
1996年Bersekas提出解決隨機(jī)過程中優(yōu)化控制的神經(jīng)動態(tài)規(guī)劃方法刻帚。
2006年Kocsis提出了置信上限樹算法潦嘶。
2009年kewis提出反饋控制只適應(yīng)動態(tài)規(guī)劃算法。
2014年silver提出確定性策略梯度（Policy Gradients）算法崇众。
2015年Google-deepmind 提出Deep-Q-Network算法掂僵。
可見航厚，強(qiáng)化學(xué)習(xí)已經(jīng)發(fā)展了幾十年，并不是一門新的技術(shù)锰蓬。在2016年幔睬，AlphaGo擊敗圍棋世界冠軍李世石之后，融合了深度學(xué)習(xí)的強(qiáng)化學(xué)習(xí)技術(shù)大放異彩芹扭，成為這兩年最火的技術(shù)之一麻顶。總結(jié)來說舱卡，強(qiáng)化學(xué)習(xí)就是一個古老而又時尚的技術(shù)辅肾。
圖1 AlphaGo對戰(zhàn)李世石
我們先看看機(jī)器學(xué)習(xí)的分類：
圖2 機(jī)器學(xué)習(xí)分類
可以看出機(jī)器學(xué)習(xí)包括三大類：有監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)轮锥。
回顧下前面課程講過的有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)：
（1）有監(jiān)督學(xué)習(xí)：又稱為有導(dǎo)師的學(xué)習(xí)矫钓，即人工給定一組數(shù)據(jù)，每個數(shù)據(jù)的屬性值也給出交胚，對于數(shù)據(jù)集中的每個樣本份汗，想要算法預(yù)測并給出正確答案盈电。以任務(wù)為驅(qū)動蝴簇，主要包括兩類問題：回歸問題，分類問題匆帚。
（2）無監(jiān)督學(xué)習(xí)：又稱為無導(dǎo)師學(xué)習(xí)熬词，數(shù)據(jù)一般是沒有標(biāo)簽的。以數(shù)據(jù)為驅(qū)動吸重，包括聚類等互拾。
那么，什么是強(qiáng)化學(xué)習(xí)呢嚎幸？
強(qiáng)化學(xué)習(xí)（Reinforcement Learning, RL）?主要用于決策和控制領(lǐng)域颜矿，比如下棋，開車等嫉晶；根據(jù)輸入信息確定行為骑疆。要解決的核心問題是在環(huán)境中執(zhí)行動作以獲得最大的累積獎勵。
強(qiáng)化學(xué)習(xí)是基于當(dāng)前環(huán)境的條件寞钥，而執(zhí)行一個行動趣席，以取得最大化的預(yù)期利益赁豆。其靈感源自于行為主義心理學(xué)，即有機(jī)體如何在環(huán)境給予的獎勵或懲罰的刺激下诈火，逐步形成對刺激的預(yù)期，產(chǎn)生能獲得最大利益的慣性行為状答。比如：在訓(xùn)練狗狗站起來時冷守，如果狗狗站起來就給它獎勵刀崖，如給它肉條吃，如果不站起來就給它一些懲罰教沾，如用鞭子打它蒲跨，這樣的話，通過不斷的強(qiáng)化授翻，從而讓狗能夠?qū)W會站起來這個動作或悲。
強(qiáng)化學(xué)習(xí)也是如此，就是給很多樣本去學(xué)習(xí)算法堪唐，但是對于樣本沒有給出對錯巡语，你執(zhí)行完樣本后最后給出一個反饋，然后算法通過調(diào)整策略和行為來達(dá)到最優(yōu)的狀態(tài)淮菠。
因此男公，相比于有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)，強(qiáng)化學(xué)習(xí)有以下特點：
（1）沒有監(jiān)督數(shù)據(jù)合陵，只有獎勵信號枢赔；
（2）獎勵信號不一定是實時的，而很可能是延后的拥知，即一般具有延時性踏拜；
（3）時間（序列）?是一個重要因素，即強(qiáng)化學(xué)習(xí)的每一步與時間順序前后關(guān)系緊密低剔；
（4）當(dāng)前的行為影響后續(xù)接收到的數(shù)據(jù)速梗；
1.3 強(qiáng)化學(xué)習(xí)應(yīng)用
當(dāng)前，強(qiáng)化學(xué)習(xí)在諸多領(lǐng)域內(nèi)都得到廣泛的應(yīng)用襟齿，包括金融姻锁、醫(yī)療、教育猜欺、計算機(jī)視覺位隶、自然語言處理等領(lǐng)域。
圖3 強(qiáng)化學(xué)習(xí)應(yīng)用
強(qiáng)化學(xué)習(xí)是根據(jù)當(dāng)前的條件作出決策和動作开皿，以達(dá)到某一預(yù)期目標(biāo)涧黄。
智能體（Agent）?是強(qiáng)化學(xué)習(xí)中的動作實體，處于某一環(huán)境?中副瀑。在每個時刻弓熏，智能體和環(huán)境都有自己的狀態(tài)。智能體根據(jù)當(dāng)前狀態(tài)確定一個動作糠睡，并執(zhí)行該動作挽鞠。之后它和環(huán)境進(jìn)入下一個狀態(tài)，同時系統(tǒng)給它一個反饋值，對動作進(jìn)行獎勵或懲罰信认，以迫使智能體執(zhí)行正確的動作材义。
（1）獎勵 Reward
獎勵R_tRt?是信號反饋，是一個標(biāo)量嫁赏，反映智能體在tt時刻做得怎么樣其掂。智能體的目標(biāo)是最大化累積獎勵。
強(qiáng)化學(xué)習(xí)主要基于這樣的“獎勵假設(shè)”：所有的目標(biāo)都可以被描述成最大化累積獎勵潦蝇。
例子：玩游戲時分?jǐn)?shù)的增加/減少款熬。
（2）序列決策 Sequential Decision Making
目標(biāo)：選擇一系列動作來最大化未來的總體獎勵；
這些動作可能產(chǎn)生長期的后果攘乒；
獎勵可能是延遲的贤牛；
為了獲得更多的長期獎勵（long-term reward），有時會犧牲即時獎勵（immediate reward）则酝；
例子：下棋殉簸，每一步棋沒有獎勵，只有在棋局結(jié)束時才有輸/贏的反饋沽讹；
（3）智能體和環(huán)境 Agent and Environment
圖4 智能體和環(huán)境
上圖中般卑，大腦代表智能體，地球代表環(huán)境爽雄。
（4）歷史和狀態(tài) History and State
歷史是觀測（observations）蝠检、動作（actions）和獎勵（rewards）的序列：
H_t = O_1,R_1,A_1,...,A_{t-1},O_t,R_tHt?=O1?,R1?,A1?,...,At?1?,Ot?,Rt?
歷史決定接下來發(fā)生什么：
①、智能體選擇動作盲链；
②蝇率、環(huán)境選擇觀測/獎勵迟杂；
狀態(tài)是用來決定接下來發(fā)生什么的信息刽沾，是關(guān)于歷史的一個函數(shù)：
S_t = f(H_t)St?=f(Ht?)
狀態(tài)分為：環(huán)境狀態(tài)、智能體狀態(tài)和信息狀態(tài)排拷， 它們的含義分別如下所述：
①侧漓、環(huán)境狀態(tài)S^e_tSte?是環(huán)境的私有表示，即環(huán)境用來決定下一個觀測/獎勵的所有數(shù)據(jù)监氢，對智能體通常是不可見的布蔗。即使s^e_tste?是可見的，也可能包含不相關(guān)的信息浪腐。
②纵揍、智能體狀態(tài)S^a_tSta?是智能體的內(nèi)部表示，即智能體用來選擇下一個動作的所有信息议街。智能體狀態(tài)是強(qiáng)化學(xué)習(xí)算法可以利用的信息泽谨。它可以是歷史的任何函數(shù)：S^a_t = f(H_t)Sta?=f(Ht?)。
③、信息狀態(tài)（又稱為Markov狀態(tài)）包括歷史的所有有用信息吧雹。
一個狀態(tài)S_tSt?是Markov的骨杂，當(dāng)且僅當(dāng)：
P[S_{t+1}|S_t] = P[S_{t+1}|S_1,...,S_t]P[St+1?∣St?]=P[St+1?∣S1?,...,St?]
即當(dāng)前狀態(tài)包含了所有相關(guān)的歷史，只要當(dāng)前狀態(tài)可知雄卷，所有的歷史信息都不需要搓蚪。
（5）完全可觀測環(huán)境 Fully Observable Environments
圖5 完全可觀測環(huán)境
（6）部分可觀測環(huán)境 Partially Observable Environments
部分觀測性：智能體間接觀測環(huán)境，比如玩英雄聯(lián)盟或者王者榮耀只能觀察到有視野的部分丁鹉。
在這種情況下妒潭，智能體狀態(tài)≠?=環(huán)境狀態(tài)；
這種問題是部分可觀測馬爾可夫決策過程（Partially Observable Markov Decision Process, POMDP）揣钦；
此時杜耙，智能體必須構(gòu)建自己的狀態(tài)表示S^a_tSta?，例如：
①拂盯、記住完整的歷史：S^a_t=H_tSta?=Ht?佑女；
②、使用循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network, RNN）谈竿，只根據(jù)智能體t-1t?1時刻的狀態(tài)S^a_{t-1}St?1a?和當(dāng)前觀測O_tOt?來獲得當(dāng)前狀態(tài)S^a_tSta?的表示：
S^a_t=\sigma(S^a_{t-1}W_s+O_tW_o)Sta?=σ(St?1a?Ws?+Ot?Wo?)
其中团驱，W_sWs?和W_oWo?表示狀態(tài)和觀測的權(quán)重。
（7）學(xué)習(xí)和規(guī)劃 Learning and Planning
在序列決策中主要包括兩類基本問題：
①空凸、學(xué)習(xí)：環(huán)境在初始時是未知的嚎花，智能體通過與環(huán)境交互來改善它的策略；
②呀洲、規(guī)劃：環(huán)境模型是已知的紊选，智能體使用其模型執(zhí)行計算，而不與環(huán)境進(jìn)行任何交互道逗，從而改善策略兵罢。
（8）探索和利用 Exploration and Exploitation
強(qiáng)化學(xué)習(xí)是一個試錯（trail-and-error）?的學(xué)習(xí)過程，智能體需要從與環(huán)境的交互中發(fā)現(xiàn)好的策略滓窍，同時在這個過程中不至于丟失太多的獎勵卖词；
探索（Exploration）是為了發(fā)現(xiàn)關(guān)于環(huán)境更多的信息；即嘗試不同的行為繼而收集更多的信息吏夯、期望得到更好的決策此蜈。
利用（Exploitation）是根據(jù)現(xiàn)有的已知信息，采取當(dāng)前認(rèn)為最優(yōu)的策略噪生，從而來最大化獎勵裆赵；
探索（未知信息）和利用（已有信息）這兩者是矛盾的，如果“僅利用”跺嗽，則可能只是得到局部最優(yōu)战授，而得不到真正的最優(yōu)策略舔庶；而“僅探索”則可能得到的策略或獎勵都比較差；因此陈醒，智能體在進(jìn)行決策時需要在探索和利用之間進(jìn)行權(quán)衡惕橙。
比如：去餐廳吃飯，探索是嘗試沒有去過的餐廳吃飯钉跷，而利用是選擇原先去過的餐廳中最喜歡吃的那家餐廳弥鹦。
（9）預(yù)測和控制 Prediction and Control
預(yù)測：給定一個策略，來評估未來的獎勵爷辙；
控制：發(fā)現(xiàn)一個策略彬坏， 來優(yōu)化未來的獎勵；
1.5 強(qiáng)化學(xué)習(xí)智能體的主要組成部分
強(qiáng)化學(xué)習(xí)智能體（RL agent）主要由三部分組成：
（1）策略 Policy
策略是智能體的行為膝晾，是狀態(tài)ss到動作aa的映射栓始。
①、對于確定性策略血当，在每種狀態(tài)下智能體要執(zhí)行的動作是唯一的：
a = \pi(s)a=π(s)
比如：在一個紅綠燈路口幻赚，狀態(tài)是綠燈時，執(zhí)行的動作是通過臊旭；狀態(tài)是紅燈時落恼，執(zhí)行的動作是停止。
②离熏、對于不確定性（隨機(jī)性）策略佳谦，智能體在一種狀態(tài)下可以執(zhí)行的動作有多種，策略函數(shù)給出的是執(zhí)行每種動作的概率滋戳，即按概率從各種動作中隨機(jī)選擇一種執(zhí)行：
\pi(a|s)=P[A_t=a|S_t=s]π(a∣s)=P[At?=a∣St?=s]
比如：在一個十字路口钻蔑，定義3個動作：直行、左轉(zhuǎn)彎和右轉(zhuǎn)彎奸鸯；此時這3種動作都可能被執(zhí)行咪笑。
（2）價值函數(shù) Value Function
價值函數(shù)是對未來獎勵的預(yù)測，用來評價狀態(tài)的好壞程度府喳，進(jìn)而來決定動作的選擇蒲肋，例如：
{V_\pi }(s) = {{\rm E}_\pi }[{R_{t + 1}} + \gamma {R_{t + 2}} + {\gamma ^2}{R_{t + 3}} + ...|{S_t} = s]Vπ?(s)=Eπ?[Rt+1?+γRt+2?+γ2Rt+3?+...∣St?=s]
（3）模型 Model
模型是智能體對環(huán)境的表示蘑拯，體現(xiàn)了智能體是如何思考環(huán)境運(yùn)行機(jī)制的钝满。
模型至少解決兩個問題：
①、狀態(tài)轉(zhuǎn)移概率申窘，即預(yù)測下一個狀態(tài)的概率：
p_{ss'}^a = P[{S_{t + 1}} = s'|{S_t} = s,{A_t} = a]pss′a?=P[St+1?=s′∣St?=s,At?=a]
②弯蚜、即時獎勵，即預(yù)測可能獲得的即時獎勵：
R_s^a = E[{R_{t + 1}}|{S_t} = s,{A_t} = a]Rsa?=E[Rt+1?∣St?=s,At?=a]
（1）按智能體的成分分類：
①剃法、基于價值函數(shù)（Value Based）：定義了狀態(tài)或動作的價值函數(shù)碎捺，來表示達(dá)到某種狀態(tài)或執(zhí)行某種動作后得到的獎勵；傾向于選擇價值最大的狀態(tài)或動作；
②收厨、基于策略（Policy Based）：不需要定義價值函數(shù)晋柱，動作直接由策略函數(shù)產(chǎn)生，可以為動作分配概率分布诵叁，按照概率分布來執(zhí)行動作雁竞；
③、Actor-Critic：既有價值函數(shù)拧额，也有策略函數(shù)碑诉，兩者相互結(jié)合解決問題。
圖6 按智能體的成分分類
（2）按有無模型分類：
①侥锦、有模型/基于模型（Model Based）：智能體嘗試建立一個描述環(huán)境動作過程的模型进栽，以此來指導(dǎo)價值或策略函數(shù)的更新；主要是基于動態(tài)規(guī)劃的算法恭垦，包括策略迭代算法和值迭代算法快毛；
②、無模型/不基于模型（Model Free）：智能體不需要關(guān)于環(huán)境的信息番挺，不試圖了解環(huán)境如何工作祸泪，僅聚焦于價值或策略函數(shù)；主要包括蒙特卡洛算法和時序差分學(xué)習(xí)等建芙；
圖7 按有無模型分類
當(dāng)然没隘，還有其他分類方法，比如：按環(huán)境分類（完全可觀測環(huán)境和部分可觀測環(huán)境）禁荸、按使用手段分類（傳統(tǒng)強(qiáng)化學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)）等右蒲。
為什么要介紹動態(tài)規(guī)劃？
正如開篇所講赶熟，在運(yùn)籌學(xué)和控制論領(lǐng)域瑰妄，強(qiáng)化學(xué)習(xí)方法所在的領(lǐng)域被稱為近似動態(tài)規(guī)劃。
動態(tài)規(guī)劃是將復(fù)雜問題拆分成相互聯(lián)系的小問題并按順序進(jìn)行解決映砖，即主要用于解決多階段決策問題间坐，而從廣義上講，強(qiáng)化學(xué)習(xí)問題也是一種多階段決策問題邑退，即智能體通過進(jìn)行多階段決策來獲得最大化收益地技。因此，了解動態(tài)規(guī)劃對學(xué)習(xí)強(qiáng)化學(xué)習(xí)有很大的幫助庵芭。
圖8 Quora關(guān)于動態(tài)規(guī)劃的回答
用一句話解釋動態(tài)規(guī)劃就是”記住之前做過的事“回官，如果更準(zhǔn)確些版扩，其實是”記住之前得到的答案“闺魏。
首先說一下分治法：將原問題分解成規(guī)模更小的子問題，然后將這些子問題逐個擊破辣辫，將已解決的子問題合并，最終得到原問題的解谷遂。在這里葬馋，各個子問題之間是相互獨立的。
動態(tài)規(guī)劃與分治法類似肾扰，但不同的是分解的各個子問題之間是是相互聯(lián)系的畴嘶，通常具有時間或空間上的次序性，在求解的過程中按一定次序?qū)ψ訂栴}進(jìn)行求解集晚。為了避免多次解決這些子問題窗悯，它們的結(jié)果都逐漸被計算并儲存，從簡單的問題直到整個問題都被解決偷拔。
因此蒋院，對于一個動態(tài)規(guī)劃問題，只需要從兩方面進(jìn)行考慮：找出問題之間的聯(lián)系以及儲存子問題的結(jié)果莲绰。
下面將通過圖9路徑選擇問題對動態(tài)規(guī)劃進(jìn)行詳解欺旧。
圖9 路徑選擇問題
如果一類活動過程可以分為若干個互相聯(lián)系的階段，在每一個階段都需要做出決策（采取措施）蛤签，一個階段的決策確定以后辞友，常常影響到下一個階段的決策，從而就完全確定一個過程的活動路線震肮，則稱它為多階段決策問題踏枣。
在多階段決策問題中，各個階段采取的決策钙蒙，一般來說是與時間相關(guān)的茵瀑，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移躬厌，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的马昨，因此有”動態(tài)“的含義，稱這種解決多階段決策最優(yōu)化問題的方法為動態(tài)規(guī)劃方法扛施。
在圖9中鸿捧，所求解的問題是：AA點到EE點；這個問題就是個多階段決策問題疙渣。
（1）階段：把所給求解問題的過程恰當(dāng)?shù)?/b>分成若干個相互聯(lián)系的子問題匙奴，以便能夠按一定次序去求解，每次求解一個子問題妄荔，則對應(yīng)一個階段泼菌。
在圖9中谍肤，階段：圖中的4個階段；
（2）狀態(tài)：狀態(tài)表示每個階段開始面臨的客觀條件哗伯，即在求解子問題時的已知條件荒揣。狀態(tài)描述了研究的問題過程中的狀態(tài)。
在圖9中焊刹，階段1的狀態(tài)是AA系任，階段2的狀態(tài)是B_1B1?、B_2B2?和B_3B3?虐块，以此類推俩滥。那么，各個階段的狀態(tài)可以定義為：
S_1=\{A\}S1?={A}
S_2=\{B_1, B_2, B_3\}S2?={B1?,B2?,B3?}
S_3=\{C_1, C_2, C_3\}S3?={C1?,C2?,C3?}
S_4=\{D_1, D_2\}S4?={D1?,D2?}
最終階段（EE點）在這里表示為S_5S5?贺奠，那么此階段的狀態(tài)定義為：
S_5=\{E\}S5?={E}
在這里霜旧，以上狀態(tài)的定義是為了與圖9相對應(yīng)。而在實際應(yīng)用中敞嗡，我們一般以S_0S0?作為初始狀態(tài)颁糟。
（3）決策：決策表示從當(dāng)前階段的狀態(tài)出發(fā)到達(dá)下一階段的狀態(tài)所做出的的選擇。
在圖9中喉悴，比如當(dāng)前階段是階段1棱貌，狀態(tài)是AA，到達(dá)下一階段2的狀態(tài)箕肃，可以選擇B_1B1?婚脱、B_2B2?和B_3B3?，這里的選擇就是決策勺像；
（4）策略：策略表示由所有階段的決策組成的決策序列障贸。
在圖9中，如果4個階段的選擇分別是B_1B1?吟宦，C_1C1?篮洁、D_1D1?和EE，那么殃姓，這些選擇組成的序列（A \rightarrow B_1 \rightarrow C_1 \rightarrow D_1 \rightarrow EA→B1?→C1?→D1?→E）就是其中一個策略袁波。
（5）狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定兩個相鄰階段的狀態(tài)的演變過程，描述了狀態(tài)之間是如何演變的蜗侈。
在圖9中篷牌，假設(shè)xx點和yy點是相鄰兩個階段的點，dis[x]dis[x]表示從xx點到EE點的距離踏幻，dis[y]dis[y]表示從yy點到EE點的距離枷颊，map(x, y)map(x,y)表示從xx點到y(tǒng)y點的距離，那么，狀態(tài)轉(zhuǎn)移方程可以寫成：
dis[x]=dis[y]+map(x,y)dis[x]=dis[y]+map(x,y)
（6）最優(yōu)策略：最優(yōu)策略表示所有策略中代價最小夭苗、性能最優(yōu)的策略信卡。
在圖9中，如果尋找最優(yōu)策略的話听诸，即是求解從A點到E點的最短路徑問題坐求，這里的最優(yōu)策略是：A \rightarrow B_2 \rightarrow C_1 \rightarrow D_1 \rightarrow EA→B2?→C1?→D1?→E蚕泽。
使用動態(tài)規(guī)劃解決問題時晌梨，最重要的的是確定動態(tài)規(guī)劃三要素：
（1）問題拆分：將原問題拆解為子問題，并找到子問題之間的具體聯(lián)系须妻；
（2）狀態(tài)定義：定義每個階段的狀態(tài)仔蝌；
（3）狀態(tài)轉(zhuǎn)移方程推導(dǎo)：找到從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系；
（1）最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的荒吏，就稱該問題具有最優(yōu)子結(jié)構(gòu)敛惊，即滿足最優(yōu)化原理。簡而言之绰更，一個最優(yōu)化策略的子策略總是最優(yōu)的瞧挤。
（2）無后效性：某階段狀態(tài)一旦確定，這個狀態(tài)的決策只與當(dāng)前狀態(tài)有關(guān)儡湾，與以前各個階段的狀態(tài)無關(guān)特恬。即每個狀態(tài)都是過去歷史的一個完整總結(jié)。
（3）子問題重疊性：子問題之間不是相互獨立的徐钠，一個子問題在下一階段決策中可能被多次使用到癌刽。
下面通過路徑迷宮?和?0-1背包?兩個經(jīng)典案例來溫習(xí)如何通過三要素求解 動態(tài)規(guī)劃問題。
問題描述：
一個機(jī)器人位于一個m \times nm×n網(wǎng)格的左上角（起始點在下圖中標(biāo)記為“StartStart”）尝丐。機(jī)器人每次只能向下或者向右移動一步显拜。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“FinishFinish”）。問總共有多少條不同的路徑爹袁？
圖10 路徑迷宮問題
例如：上圖是一個3 \times 73×7的網(wǎng)格远荠，有多少可能的路徑？
根據(jù)動態(tài)規(guī)劃三要素來對該問題進(jìn)行求解：
（1）問題拆分：
該問題是機(jī)器人從“StartStart”格到“FinishFinish”格失息，機(jī)器人到達(dá)一個格子可以通過其上邊和左邊的格子到達(dá)譬淳，即第(i, j)(i,j)格可以從(i-1, j)(i?1,j)格和(i, j-1)(i,j?1)格到達(dá)，因此根时，可以把第(i, j)(i,j)格問題拆分為(i-1, j)(i?1,j)格和(i, j-1)(i,j?1)格問題瘦赫，然后這兩個問題也可以按以上方式重復(fù)，直到“StartStart”位置蛤迎。
（2）狀態(tài)定義：
在問題階段中提到第(i, j)(i,j)格會和(i-1, j)(i?1,j)格和(i, j-1)(i,j?1)格有關(guān)聯(lián)确虱，那有什么關(guān)聯(lián)呢？可以這樣考慮替裆，第(i-1, j)(i?1,j)格問題的答案其實是從“StartStart”到第(i-1, j)(i?1,j)格的路徑總數(shù)校辩，第(i, j-1)(i,j?1)格同理窘问。因此，我們可以把第(i, j)(i,j)格的狀態(tài)定義為“從StartStart到第(i, j)(i,j)格的路徑總數(shù)”宜咒。
（3）狀態(tài)轉(zhuǎn)移方程推導(dǎo)：
根據(jù)狀態(tài)定義也知道惠赫，第(i, j)(i,j)格的總路徑數(shù)等于第(i-1, j)(i?1,j)格和(i, j-1)(i,j?1)格的路徑數(shù)之和，因此故黑，狀態(tài)轉(zhuǎn)移方程為：
f(i, j)=f(i-1, j)+f(i, j-1)f(i,j)=f(i?1,j)+f(i,j?1)
注意：在實現(xiàn)過程中儿咱，當(dāng)機(jī)器人處于第1行和第1列時，其對應(yīng)路徑總數(shù)都是1场晶。
參考代碼：
classSolution{publicintcountPaths(intm,intn){int[][]f=newint[m][n];for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(i==0||j==0)f[i][j]=1;else{f[i][j]=f[i-1][j]+f[i][j-1];}}}returnf[m-1][n-1];}}
問題描述：
一共有NN個物品混埠，它們有各自的重量和價值，第ii（ii從1開始）件物品的重量為w[i]w[i]诗轻，價值為v[i]v[i]钳宪，在總重量不超過背包承載上限WW的情況下，能夠裝入背包的最大價值是多少扳炬？
圖11 01背包問題
在這里吏颖，如果使用暴力窮舉的方法，每件物品都存在裝入和不裝入兩種情況恨樟，因此半醉，一共需要2^N2N種情況，復(fù)雜度很高厌杜。
如果按照動態(tài)規(guī)劃的方法奉呛，根據(jù)動態(tài)規(guī)劃三要素來進(jìn)行求解：
（1）問題拆分：
該問題的目標(biāo)是使得書包內(nèi)物品的總價值最大，而變量是物品和書包的限重夯尽。
定義dp[i][j]dp[i][j]表示將前ii件商品裝進(jìn)限重為jj的背包可以獲得的最大價值瞧壮，0<=i<=N，0<=j<=W0<=i<=N匙握，0<=j<=W咆槽；
當(dāng)背包的限重為jj時，對于第ii件物品圈纺，有兩種選擇：
①秦忿、背包限重充足，能夠裝下蛾娶，選擇放入灯谣；此時背包的限重減少w[i]w[i]，即j-w[i]j?w[i]蛔琅，裝入背包中物品的價值是裝入前i-1i?1件物品的價值與第ii件物品價值的總和胎许，即dp[i-1][j-w[i]] + v[i]dp[i?1][j?w[i]]+v[i]；
②、背包限重不足辜窑，不放入钩述；此時背包的限重為jj，價值為dp[i-1][j]dp[i?1][j]穆碎；
通過以上兩種方式進(jìn)行重復(fù)牙勘，直到放入物品的數(shù)量為0為止沦辙。
（2）狀態(tài)定義：
根據(jù)問題階段的描述竭翠，可以將第ii個階段的狀態(tài)定義為dp[i][j]dp[i][j]卒废，即前ii件商品裝進(jìn)限重為jj的背包可以獲得的最大價值供填。
（3）狀態(tài)轉(zhuǎn)移方程推導(dǎo)：
根據(jù)問題階段和狀態(tài)定義的描述，第i階段背包的總價值為上述兩種情況中取最大值的情況痹籍，即狀態(tài)轉(zhuǎn)移方程為：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])\ \ if\ \ j>=w[i]dp[i][j]=max(dp[i?1][j],dp[i?1][j?w[i]]+v[i])??if??j>=w[i]
參考代碼：
for(inti=0;i<=N;i++){for(intj=0;j<=W;j++){if(j<w[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}}
在機(jī)器學(xué)習(xí)領(lǐng)域氓仲，環(huán)境通常被闡釋成一個馬爾可夫決策過程（Markov Decision Process, MDP），許多強(qiáng)化學(xué)習(xí)算法都是用了動態(tài)編程（dynamic programming）技術(shù)贺氓。傳統(tǒng)技術(shù)和強(qiáng)化學(xué)習(xí)算法之間主要不同在于后者并不需要關(guān)于 MDP 的知識并且它們的目標(biāo)是無法獲取明確的方法的大型 MDP。強(qiáng)化學(xué)習(xí)要解決的問題可以抽象成馬爾可夫決策過程床蜘。這里先介紹下馬爾可夫過程辙培，再進(jìn)一步介紹馬爾可夫決策過程。
（1）?馬爾可夫特性 Markov Property
在上面介紹強(qiáng)化學(xué)習(xí)的信息狀態(tài)時邢锯，介紹到：
一個狀態(tài)S_tSt?是Markov的扬蕊，當(dāng)且僅當(dāng)：
P[S_{t+1}|S_t] = P[S_{t+1}|S_1,...,S_t]P[St+1?∣St?]=P[St+1?∣S1?,...,St?]
即當(dāng)前狀態(tài)包含了所有相關(guān)的歷史，只要當(dāng)前狀態(tài)可知丹擎，所有的歷史信息都不需要尾抑。
馬爾可夫特性：當(dāng)一個隨機(jī)過程在給定當(dāng)前狀態(tài)及所有過去狀態(tài)情況下，其未來狀態(tài)的條件概率分布僅依賴于當(dāng)前狀態(tài)蒂培。
（2）?馬爾可夫過程 Markov Process
馬爾可夫過程：又稱為馬爾可夫鏈（Markov Chain）再愈，是一個無記憶的隨機(jī)過程，其中护戳，隨機(jī)過程是指一個系統(tǒng)的狀態(tài)隨著時間線隨機(jī)演化翎冲。也就是說，馬爾可夫過程是一個具有馬爾可夫特性的隨機(jī)狀態(tài)序列S_1S1?,?S_2S2?, …媳荒。
馬爾可夫過程可以表示成一個二元組：
<S,P>
其中抗悍，SS是有限的狀態(tài)集合，PP是一個狀態(tài)轉(zhuǎn)移概率矩陣钳枕。
對于馬爾可夫狀態(tài)ss和其后繼狀態(tài)s's′缴渊，狀態(tài)轉(zhuǎn)移概率定義為：
P_{ss'} = P[S_{t+1}=s'|S_t=s]Pss′?=P[St+1?=s′∣St?=s]
狀態(tài)轉(zhuǎn)移矩陣PP定義了所有狀態(tài)的轉(zhuǎn)移概率：
KaTeX parse error: Unknown column alignment: * at position 41: …{\begin{array}{*?{20}{c}} {{P_{1…
其中，nn是狀態(tài)數(shù)量鱼炒，矩陣中的每一行元素之和為1衔沼。
與馬爾可夫過程不同的是，在馬爾可夫決策過程（MDP）中，智能體可以執(zhí)行動作俐巴，從該改變自己和環(huán)境的狀態(tài)骨望，并且得到反饋（即懲罰或獎勵）。
MDP可以表示成一個五元組：
<S,A,P,R,γ>
其中欣舵，SS為有限的狀態(tài)集合擎鸠；
AA為有限的動作集合；
PP為狀態(tài)轉(zhuǎn)移矩陣缘圈，P^a_{ss'} = P[S_{t+1}=s' | S_t=s, A_t=a]Pss′a?=P[St+1?=s′∣St?=s,At?=a]劣光；
RR為獎勵函數(shù)（reward function），R_s^a = E[{R_{t + 1}}|{S_t} = s,{A_t} = a]Rsa?=E[Rt+1?∣St?=s,At?=a]糟把；這個函數(shù)是即時獎勵的期望绢涡，即在時刻tt時，智能體的狀態(tài)為ss遣疯，在執(zhí)行動作aa后雄可，下一個時刻t+1t+1立即能得到的獎勵R_{t+1}Rt+1?的期望。
\gammaγ為折扣因子（discount factor）缠犀，\gamma \in [0,1]γ∈[0,1]数苫；
（1）回報 Return
強(qiáng)化學(xué)習(xí)的目標(biāo)是達(dá)到某種預(yù)期，當(dāng)前執(zhí)行動作的結(jié)果會影響系統(tǒng)后續(xù)的狀態(tài)辨液，因此虐急，需要確定動作在未來是否能夠得到好的回報，這種回報具有延時性滔迈。
定義回報（Return）G_tGt?是從tt時刻之后未來執(zhí)行一組動作能夠獲得的獎勵的總和止吁，即：
{G_t} = {R_{t + 1}} + \gamma {R_{t + 2}} + ... = \sum\limits_{k = 0}^\infty {{\gamma ^k}{R_{t + k + 1}}}Gt?=Rt+1?+γRt+2?+...=k=0∑∞?γkRt+k+1?
這里，折扣因子\gammaγ體現(xiàn)了未來的獎勵在當(dāng)前時刻的價值比例燎悍；
在k+1k+1步后敬惦，獲得的獎勵RR在tt時刻體現(xiàn)的價值是{\gamma} ^k RγkR；
當(dāng)\gammaγ接近0時间涵，趨向于短期性評估仁热；當(dāng)\gammaγ趨向于1時，趨向于考慮遠(yuǎn)期的利益勾哩；
使用折扣因子\gammaγ的原因：
①抗蠢、沒有一個完美的模型能夠擬合出未來會發(fā)生什么，未來具有不確定性思劳，執(zhí)行特定的動作不一定得到特定的狀態(tài)迅矛，所以，將來的獎勵所占的權(quán)重隨著時間衰減潜叛；
②秽褒、如果不加上折扣因子壶硅，當(dāng)狀態(tài)無限時，會導(dǎo)致求和項趨向于無窮大销斟，不收斂庐椒；
③、更符合人類/動物的行為：偏好即時獎勵R_{t+1}Rt+1?蚂踊；
（2）策略 Policy
策略\piπ是給定狀態(tài)下動作的概率分布约谈，用\pi(a|s)π(a∣s)表示在MDP中某一狀態(tài)ss采取動作aa的概率：
\pi(a|s)=P[A_t=a|S_t=s]π(a∣s)=P[At?=a∣St?=s]
一個策略完整定義了智能體的行為，即定義了智能體在各個狀態(tài)下各種可能的動作及其概率的大小犁钟。
MDP的策略僅和當(dāng)前狀態(tài)有關(guān)棱诱，與歷史信息無關(guān)；
（3）價值函數(shù) Value Function
類似于有監(jiān)督學(xué)習(xí)中需要定義損失函數(shù)來評價預(yù)測函數(shù)的優(yōu)劣涝动，在強(qiáng)化學(xué)習(xí)中也需要對策略的優(yōu)劣進(jìn)行評價迈勋，為此定義了了價值函數(shù)。
價值函數(shù)包括狀態(tài)價值函數(shù)（state-value function）v_{\pi}(s)vπ?(s)和動作價值函數(shù)（action-value function）q_{\pi}(s,a)qπ?(s,a)醋粟。
①靡菇、狀態(tài)價值函數(shù)v_{\pi}(s)vπ?(s)表示在狀態(tài)ss下，遵循策略\piπ執(zhí)行動作昔穴，能夠獲得的回報期望镰官；或者說當(dāng)執(zhí)行策略\piπ時，評估智能體處在狀態(tài)ss時的價值大小吗货，即：
v_{\pi}(s)=E_{\pi}[G_t|S_t=s]vπ?(s)=Eπ?[Gt?∣St?=s]
②、動作價值函數(shù)q_{\pi}(s,a)qπ?(s,a)表示在遵循策略\piπ時狈网，對當(dāng)前狀態(tài)ss執(zhí)行具體的動作aa時所能獲得的回報期望宙搬；或者說在執(zhí)行策略\piπ時，評估處在狀態(tài)ss時執(zhí)行動作aa的價值大小拓哺，即：
q_{\pi}(s,a)=E_{\pi}[G_t|S_t=s,A_t=a]qπ?(s,a)=Eπ?[Gt?∣St?=s,At?=a]
動作價值函數(shù)除了指定狀態(tài)ss和策略\piπ外勇垛，還指定了在當(dāng)前狀態(tài)ss時執(zhí)行的動作aa。這個函數(shù)衡量的是按照某一策略士鸥，在某一狀態(tài)時執(zhí)行各種動作的價值闲孤。
（4）貝爾曼期望方程 Bellman Expectation Equation
狀態(tài)價值函數(shù)v_{\pi}(s)vπ?(s)可以分解為即時獎勵與其后繼狀態(tài)的折扣價值之和，即：
v_{\pi}(s)=E_{\pi}[R_{t+1}+{\gamma}v_{\pi}(S_{t+1})|S_t=s]vπ?(s)=Eπ?[Rt+1?+γvπ?(St+1?)∣St?=s]
動作價值函數(shù)可以轉(zhuǎn)化為即時獎勵與后繼狀態(tài)執(zhí)行相應(yīng)動作的折扣價值之和烤礁，即：
q_{\pi}(s,a)=E_{\pi}[R_{t+1}+{\gamma}q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a]qπ?(s,a)=Eπ?[Rt+1?+γqπ?(St+1?,At+1?)∣St?=s,At?=a]
v_{\pi}(s)vπ?(s)和q_{\pi}(s,a)qπ?(s,a)之間的關(guān)系：
下面圖中的空心圓圈表示狀態(tài)讼积，黑色實心圓圈表示動作，連線表示把該狀態(tài)與執(zhí)行的動作關(guān)聯(lián)起來脚仔。
①勤众、使用q_{\pi}(s,a)qπ?(s,a)表示v_{\pi}(s)vπ?(s)：
{v_\pi }(s) = \sum\limits_{a \in A} {\pi (a|s){q_\pi }(s,a)}vπ?(s)=a∈A∑?π(a∣s)qπ?(s,a)
圖12\ 使用q_{\pi}(s,a)表示v_{\pi}(s)圖12?使用qπ?(s,a)表示vπ?(s)
②、使用v_{\pi}(s)vπ?(s)表示q_{\pi}(s,a)qπ?(s,a)：
{q_\pi }(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_\pi }(s')}qπ?(s,a)=Rsa?+γs′∈S∑?Pss′a?vπ?(s′)
圖13\ 使用v_{\pi}(s)表示q_{\pi}(s,a)圖13?使用vπ?(s)表示qπ?(s,a)
將上述兩種情況組合起來鲤脏，可以得到：
{v_\pi }(s) = \sum\limits_{a \in A} {\pi (a|s)}(R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_\pi }(s'))}vπ?(s)=a∈A∑?π(a∣s)(Rsa?+γs′∈S∑?Pss′a?vπ?(s′))
{q_\pi }(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a\sum\limits_{a' \in A} {\pi (a'|s'){q_\pi }(s',a')}}qπ?(s,a)=Rsa?+γs′∈S∑?Pss′a?a′∈A∑?π(a′∣s′)qπ?(s′,a′)
（5）最優(yōu)價值函數(shù) Optimal Value Function
最優(yōu)狀態(tài)價值函數(shù)v_*(s)v??(s)是從所有策略產(chǎn)生的狀態(tài)價值函數(shù)中们颜，選取使?fàn)顟B(tài)ss價值最大的函數(shù)：
{v_*}(s) = \mathop {max}\limits_\pi {v_\pi }(s）v??(s)=πmax?vπ?(s）
類似的吕朵，最優(yōu)動作價值函數(shù)q_*(s,a)q??(s,a)是從所有策略產(chǎn)生的動作價值函數(shù)中，選取使?fàn)顟B(tài)動作對<s,a>價值最大的函數(shù)：
{q_*}(s,a) = \mathop {\max }\limits_\pi {q_\pi }(s,a)q??(s,a)=πmax?qπ?(s,a)
最優(yōu)價值函數(shù)明確了MDP可能的最優(yōu)表現(xiàn)窥突。
（6）最優(yōu)策略 Optimal Policy
對于任何狀態(tài)ss努溃，當(dāng)遵循策略\piπ的價值不小于策略\pi'π′的價值時，則策略\piπ優(yōu)于策略\pi'π′：
\pi \ge \pi ' \ if \ {v_\pi }(s) \ge {v_{\pi '}}(s),\ \forall sπ≥π′?if?vπ?(s)≥vπ′?(s),??s
對于任何MDP：
①阻问、存在一個最優(yōu)策略茅坛，好于或等于所有其他策略；
②则拷、所有的最優(yōu)策略都實現(xiàn)了最優(yōu)價值函數(shù)贡蓖，包括最優(yōu)狀態(tài)價值函數(shù)和最優(yōu)動作價值函數(shù)；
怎么尋找最優(yōu)策略呢煌茬？
最優(yōu)策略可以通過最大化最優(yōu)動作價值函數(shù)q_*(s,a)q??(s,a)來尋找：
KaTeX parse error: Unknown column alignment: * at position 57: … \begin{array}{*?{20}{c}} 1&{if …
對于任何MDP問題斥铺，總存在一個確定性的最優(yōu)策略；
如果知道了最優(yōu)動作價值函數(shù)q_*(s,a)q??(s,a)坛善，則表明找到了最優(yōu)策略晾蜘。
（7）貝爾曼最優(yōu)方程 Bellman Optimality Equation
對于v_*v??，一個狀態(tài)的最優(yōu)價值等于從該狀態(tài)出發(fā)執(zhí)行的所有動作中產(chǎn)生的動作價值中最大的那個動作價值：
{v_*}(s) = \mathop {\max }\limits_a {q_*}(s,a)v??(s)=amax?q??(s,a)
對于q_*q??眠屎，在狀態(tài)ss剔交，采取動作aa的最優(yōu)價值由兩部分組成，一部分是離開狀態(tài)ss時的即時獎勵改衩，另一部分是其后繼狀態(tài)s's′的最優(yōu)狀態(tài)價值的概率求和：
{q_*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_*}(s')}q??(s,a)=Rsa?+γs′∈S∑?Pss′a?v??(s′)
將上述兩種情況組合起來岖常，可以得到：
{v_*}(s) = \mathop {\max }\limits_a (R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_*}(s')})v??(s)=amax?(Rsa?+γs′∈S∑?Pss′a?v??(s′))
{q_*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a\mathop {\max }\limits_{a'} {q_*}(s',a')}q??(s,a)=Rsa?+γs′∈S∑?Pss′a?a′max?q??(s′,a′)
貝爾曼最優(yōu)方程是非線性的，一般通過迭代的方法來求解貝爾曼最優(yōu)方程葫督，例如：基于動態(tài)規(guī)劃的算法（價值迭代竭鞍、策略迭代）、蒙特卡洛算法和時序差分學(xué)習(xí)等橄镜，這些方法在前文中強(qiáng)化學(xué)習(xí)的分類中有提到偎快，后續(xù)會進(jìn)行講解。
本博客所有內(nèi)容僅供學(xué)習(xí)洽胶，不為商用晒夹，如有侵權(quán)，請聯(lián)系博主姊氓，謝謝丐怯。
[1]?動態(tài)規(guī)劃之初識動規(guī)：有了四步解題法模板，再也不害怕動態(tài)規(guī)劃
[2]?動態(tài)規(guī)劃理解
[3]?路徑迷宮問題
[5]?David Silver強(qiáng)化學(xué)習(xí)公開課
[6]?David Silver強(qiáng)化學(xué)習(xí)公開課中文講解
[7] 機(jī)器學(xué)習(xí)原理他膳、算法與應(yīng)用
[8] 人工智能：一種現(xiàn)代的方法（第3版）
[9] An Introduction to Reinforcement Learning
[10] Algorithms for Reinforcement Learning
