七. 泛化和函數(shù)近似
問題：目前為止，我們假設(shè)值函數(shù)的估計都是用一個表，如Q-table.但是，這個表有局限，因為它局限于狀態(tài)數(shù)和行為數(shù)較少的例子。因為如果狀態(tài)數(shù)和行為數(shù)較大，一方面需要很多的內(nèi)存，另一方面將數(shù)據(jù)填充進(jìn)表格也需要耗費很多的時間。所以，這個是耗時耗空間的。因此，需要有一種方法，將有限的狀態(tài)子空間的子集經(jīng)驗泛化到一個很大的子集中，從而產(chǎn)生好的近似。
解決：這種泛化的方法叫做函數(shù)近似（function approximation）。函數(shù)近似是從一個想得到的函數(shù)（value function）進(jìn)行抽樣，試圖泛化他們來構(gòu)建一個完整的函數(shù)的近似。
7.1 值估計和函數(shù)近似?
本章的新穎之處在于，近似函數(shù)Vt代表的不是一個表，而是用參數(shù)向量參數(shù)化的一個函數(shù)。這意味著值函數(shù)Vt完全依賴于參數(shù)向量，隨著每個時間步長的變化而變化。
均方根誤差（MSE）用來估計值函數(shù)近似方法。
Backup??
7.2 梯度下降法
梯度下降法通過調(diào)整每個樣本后沿著誤差下降最快的方向調(diào)整參數(shù)向量：
在線梯度下降TD(入)用于V估計的算法：
7.3 線性模型
用feature vectors來表示states
7.3.1 粗糙編碼
？？
7.3.2 Tile Coding
？？
7.3.3 徑向基函數(shù)
？？
7.4 函數(shù)近似的控制
八.? Hierarchical ?Reinforcement Learning
有一些情況，就是reward的間隔很久。比如對機器人來說，只有撿到垃圾并且放到倉庫中才能獲得reward，那么這之間的delay將變得很大。因此，需要將reward進(jìn)行shape。
解決方法就是添加intermediate? reward,將目標(biāo)分解成一個個的subgoal。所以，這個想法就是Hierarchical? Reinforcement Learning。但是，這樣就把這個問題從MDP變成SMDP.
8.1 SMDP
SMDP: The amount of time between one decision and the next is arandom variable(either real or integer valued). 也就是說，和MDP不同的是，決策與下個決策之間的時間間隔是隨機的。MDP是假設(shè)每一個constant時間間隔。與MDP不同的是，就多加了一個時間間隔t.
還有一個有顯著不同的地方就是reward的定義：
對于前者是適用于離散的時間空間，對于后者用于連續(xù)的時間空間。
8.2 Option
The option is a behaviour defined in terms of: o={Io,πo,βo}
Io: Set of states in which o can be initiated.
πo(s): Policy(mapping S to A)§ when o is executing.
βo(s) : Probability that o terminates in s.
MDP + Options = SMDP
九. Partial Observability and the POMDP Model
Partial observability: 部分可觀，其實就是狀態(tài)未知，但是知道狀態(tài)的觀測值。
舉個例子，有A,B 兩種狀態(tài)。Agent一開始可能在兩種狀態(tài)中的一種，并且有兩種可能的action, 要么stay, 要么move。 在A的時候utility0 為0, B的時候utility為1。從A出發(fā)只有0.9的概率會達(dá)到B，0.1的概率出發(fā)然后回到A，從B出發(fā)同理。
MDP：
已知agent一開始是在狀態(tài)A，
Q(A, stay) = Uo + [0.9 * 0 + 0.1 * 1] = 0 + 0.1 = 0.1
Q(A, move) = Uo + [0.1 * 0 + 0.9 * 1] = 0 + 0.9 = 0.9
Umax = Max( Q(A, stay), Q(A, move) ) = move
已知agent一開始是在狀態(tài)B，
Q(B, stay) = Uo + [0.9 * 1 + 0.1 * 0] = 0.9 + 1 = 1.9
Q(B, move) = Uo + [0.1 * 1 + 0.9 * 0] = 0.1 + 1 = 1.1
Umax = Max( Q(B, stay), Q(B, move) ) = stay
POMD: 由于信息不完全，可能一開始agent并不知道自己在A還是在B，于是需要給分別可能在A，或者B的可能性賦予權(quán)重，
權(quán)重：假設(shè)有0.4的可能一開始在A，0.6的可能性一開始在B。
U (stay) =? 0.4 * 0.1 +? 0.6 * 1.9 = 1.18
U (move)? = 0.4 * 0.9 + 0.6 * 1.1 = 1.02
1. value function over belief space:
因為狀態(tài)不可觀測，所以agent需要依賴于基于狀態(tài)的先驗概率來做決定。
b是agent狀態(tài)的一個概率估計。
由于每個b是一個概率分布，因此在POMDP中每個value都是整個概率分布的函數(shù)。這將成為問題，因為概率分布是連續(xù)的。除此之外，我們要考慮belief space的巨大復(fù)雜性。
2. value function update
1. payoff(return)?in POMDPs
因為在MDPs中，payoff是取決于系統(tǒng)的state的。然而在POMDPs中，真實的state是不知道的。所以，我們將便利所有的state然后取他們的期望payoff。
已知條件如下：
舉例：
那么：
2.? expression for v and π
由上面的reward方程可以畫圖如下：
由最后一個圖可以知道，這個是一個分段函數(shù)，因此，π的表達(dá)式如下：同時， v的表達(dá)式應(yīng)運而生：
但是可以發(fā)現(xiàn)，上面的v中，最后一個-1基本不起作用的，所以可以將它進(jìn)行剪枝。即只保留前兩個式子，去掉-1的。
3. propagate forward v given an observation
給一個observation z1，我們更新belief基于貝葉斯法則：
因為我們不知道下一步的測量結(jié)果是什么，所以我們要計算belief的期望：
4. state transitions
當(dāng)agent選擇u3的時候，狀態(tài)會發(fā)生改變。當(dāng)我們計算value function的時候，我們不得不將這個潛在的狀態(tài)改變考慮進(jìn)去。
所以，最終的value function如下：考慮到agent從t1時刻切換到t2時刻可以先采取u1，u2，u3的任意一個行為之后再采取u1或者u2，所以我們得到t2時刻的value function：
（咋求的？？？）
5. 重復(fù)1-4的步驟
3. pruning
如果沒剪枝的話上面的例子，T=20的時候，就達(dá)到10的547864次方的線性方程數(shù)，如果剪枝了，在T=20的時候，才12個。
總而言之，POMDPs只能成功運用于小的state space和小的可能的觀測值的盡可能少的action的場景中。
十. ?逆向增強學(xué)習(xí)
我們知道強化學(xué)習(xí)背后的假設(shè)是馬爾科夫決策過程 (MDP)。馬爾可夫決策過程是基于馬爾可夫過程理論的隨機動態(tài)系統(tǒng)的決策過程，其分五個部分：狀態(tài)集 (states)，動作集 (Action)，轉(zhuǎn)移概率，獎勵函數(shù)，衰減因子。
有時候我們不知道轉(zhuǎn)移概率和激勵函數(shù)，便讓系統(tǒng)探索環(huán)境。在探索過程中，環(huán)境根據(jù)我們未知的轉(zhuǎn)移概率和激勵函數(shù)，確定下一個狀態(tài)和給出激勵。這一類強化學(xué)習(xí)被稱為模型無關(guān)的強化學(xué)習(xí)。逆向強化學(xué)習(xí)更極端：系統(tǒng)進(jìn)行探索的過程中，環(huán)境不給出獎勵。一般的強化學(xué)習(xí)的訓(xùn)練數(shù)據(jù)是{s1,a1,r1,...,sn,an,rn}，而逆向強化學(xué)習(xí)的訓(xùn)練數(shù)據(jù)是一組軌跡{ζ=s1,a1,...,sn,an}。
逆向增強學(xué)習(xí)和增強學(xué)習(xí)的對比如下：
1. Behavioural Cloning
為什么人們要發(fā)明逆向強化學(xué)習(xí)呢？說一個場景，訓(xùn)練自動導(dǎo)航機器人，我們拿到的出租車司機的行為數(shù)據(jù)是一組軌跡{ζ=s1,a1,...,sn,an}，我們無法獲得司機在一個地址做了一個動作的即時獎勵?？梢杂糜斜O(jiān)督學(xué)習(xí)處理這個問題，分類器的輸入是地點，輸出是動作。這種方法被稱為行為克隆 (Behavior Cloning)。行為克隆有兩個缺陷。一個是導(dǎo)航本質(zhì)上是強化學(xué)習(xí)的范疇。導(dǎo)航行為的優(yōu)劣是由整體用時決定的，整體用時只有在最后才知道，具有強化學(xué)習(xí)教師信號延遲特點。另一個是行為克隆只學(xué)習(xí)司機的行為，并沒有深究司機的動機。
行為克隆就是使用監(jiān)督學(xué)習(xí)去找到以{(st, at|t belongs to T }表示的數(shù)據(jù)。換句話說，就是找到一個策略去最小化誤差。
限制評估者家族的策略和選擇訓(xùn)練集T，測試集T‘，以避免overfitting，從而有一定程度的泛化是可能的。但是，這個是不足的。為什么呢？
1. 機器人是不靈活的，不能改變目標(biāo)。
2. 當(dāng)需要多于當(dāng)前狀態(tài)以執(zhí)行（例如，當(dāng)環(huán)境輕微地非馬爾可夫）時，這種策略將表現(xiàn)不佳。
2. InverseReinforcement Learning
用人話來說，就是給定observation，找出reward是怎么分布的。換句話來說，就是找到一系列的reward的定義規(guī)則以至于找到最佳的policy。和以前的增強學(xué)習(xí)不同的是，以前的增強學(xué)習(xí)是已知reward然后去尋找最佳的policy，而逆向增強學(xué)習(xí)則是尋找reward怎么定義的。
從數(shù)學(xué)角度上說，
π*僅僅是源于給定的軌跡。那么，要如何去計算期望呢？
我們可以利用樣本的平均值去代替期望：
那么問題又來了，這個是基于value的方程，那么我們要學(xué)習(xí)的是reward。如何將reward和value結(jié)合起來呢？
那么，獲得最優(yōu)的Reward的條件是什么呢？首先是要獲得最優(yōu)的action，然后從這個最優(yōu)的action推到最優(yōu)的reward。
所以，獲得最優(yōu)reward的條件有兩個：
1. 向量R使得策略π最優(yōu)
2. 每一步的π的偏差盡可能的大
對于第二個條件，我們有：
我們希望得到較小的reward但是能得到同樣的效果。（奧科姆剃須刀原理：切勿浪費較多東西去做，用較少的東西，同樣可以做好的事情。）為了達(dá)到這個目的，我們用一個懲罰系數(shù)去懲罰reward。
3. Function Approximation
通常，在巨大的state space的問題中，我們希望用通過限制搜索來使reward盡可能簡單。所以我們設(shè)想用線性的方式表達(dá)reward。所以有：
其中，最優(yōu)化的條件如下：
十一.? Exploration and Controlled Sensing
11.1 Bayesian Updating
關(guān)于我們認(rèn)為系統(tǒng)行為特征的參數(shù)的概率性陳述。我們關(guān)注于性能的不確定性。解決這種性能不確定性(e.g: policy, choice..)，我們有兩種方法：概率論和貝葉斯論。
我們聚焦于貝葉斯論解決這個問題。貝葉斯從關(guān)于參數(shù)的初始belief開始，并結(jié)合先前的測量來計算后面的。
先驗概率：
最優(yōu)的policy 是使得u盡可能的高效。
belief的更新：
11.2 Information Acquisition and VoI
通?？梢允褂脤⒑唵螞Q策問題背景下的不確定性問題相結(jié)合的模型來捕獲信息的好處。接下來通過一個具體的例子來說明這些好處。
在沒有任何信息N幫助的條件下，贏的概率是p。那么期望值可以表示如下：
pR-(1-p):其實是贏的概率p乘以回報R,以及輸?shù)母怕?-p乘以回報-1.
Informative Signal: 在比賽之前，我們有權(quán)決定要不要獲取信息信號S(比如，可以購買報告或者上網(wǎng)查詢相關(guān)信息). 但是這個信息信號可以是好的(g),也可以是壞的(b)，我們假設(shè)這個信號將正確地預(yù)測結(jié)果， 有概率q：
Value of the Signal：
首先，我們需要了解信號如何改變游戲的預(yù)期收益。在給定信號S為good／bad的條件下，游戲的條件值如下：
接著，我們需要找到游戲的價值，因為我們已經(jīng)決定獲取信號，但在我們知道它的實現(xiàn)之前。
因為上面的式子才已知條件概率的部分，現(xiàn)在還需要知道非條件概率的部分：
此外，我們要知道，基于已知信號S, 贏得比賽或者輸?shù)舯荣惖母怕剩ㄓ秘惾~斯）：
最后，我們讓S表示需要在比賽之前獲得信息信號，所以已知信息信號S的期望值為：
Marginal Value of Information(信息的邊際值)：
假設(shè)我們有兩個選擇，即什么都不干(reward=0)，或者是獲得任意一個服從均值是μ的reward。假設(shè)我們關(guān)于μ的prior belief通常以均值和精度分布：
假設(shè)我們獲得了測量值w1,....wn.但是W有不知道的均值μ和知道的精度Bw，并且我們試驗了n次，那么，我們估計的值的精度為：
那么我們估計值的更新如下(用貝葉斯)：
用一個隨機變量(var)去獲得關(guān)于reward的belief，并且用這個來決策我們是否要去比賽：
Value of Information: Maximum price one should pay for knowing the actual value of an uncertainty before deciding on a course of action.
用一個z表示服從于均值為0，方差為1的正態(tài)分布，那么：
當(dāng)我們有了n次的測量值，我們就可以根據(jù)這個value去選擇我們是否要去比賽：Information gain and use in exploration：
exploration是控制移動機器人，以最大限度地了解外部世界。比如機器人需要獲取靜態(tài)環(huán)境的映射。如果我們將地圖表示為“占用網(wǎng)格”，則探索是最大限度地提高每個網(wǎng)格單元的累積信息。POMDP已經(jīng)包含此功能，但是我們需要定義一個適當(dāng)?shù)氖找婧瘮?shù)。一個好的選擇是信息獲取(Information gain)：減少機器人belief的熵作為其行為的函數(shù)
Exploration Heuristics(啟發(fā)式探索):
greedy method：
十二.? Multi-agent Reinforcement Learning
12.1 On Self-Interest：
這不一定意味著機器人們想要造成對方的傷害，或者甚至只關(guān)心自己。反之，這意味著每個機器人都有他們自己對于當(dāng)前世界state的描述，這可以包括對其他機器人來說是好的事情。
一個簡單的例子來說明action space是怎么定義的(取兩個action行為的積)：
一個簡單的例子（錘子剪刀布）來說明payoff是怎么定義的(bi-matrix)：
12.2 payoff
12.2.1 ?common-payoff(pure coordinate)：
對于所有的行為，任意的兩對兒agent，他們得到的結(jié)果都是一樣的。比如，最簡單的，靠路的一邊行走。
12.2.2 ?Constant Sum(Pure competition):
有一個常量c，對每組策略，A1xA2, 他們的回報R(A1)+R(A2) = c.也就是有一個想妥協(xié)，有一個堅決不妥協(xié)，唱反調(diào)。
12.3 ?Strategies：
12.3.1? Dominance
Dominance：如果有另一個行為更好，那么這個行為將一直受控。
比如囚徒問題。
Iterated Dominance：行為總是被混合的策略控制。
12.3.2? Minimax
minimax optimal strategy.
12.4 Equilibrium
12.4.1 Nash Equilibrium
納什平衡就是一個聯(lián)合的策略，所有的agent都對對方給出最佳的反應(yīng)。因為每個agent都是給出最佳的反應(yīng)，所以沒有一個agent能單方面的得到額外的好處。
12.5 Game
