上次講到強(qiáng)化學(xué)習(xí)的問題可以分成model-based和model-free兩類，現(xiàn)在我們先看看model-based，我們復(fù)習(xí)一下強(qiáng)化學(xué)習(xí)的3個(gè)組成部分：model,policy和value function：
- model：包括狀態(tài)轉(zhuǎn)移模型和獎勵模型；
- policy：從狀態(tài)到?jīng)Q策的函數(shù)（或映射）；
- value function：指的是處于某個(gè)狀態(tài)的時(shí)候未來收益的折現(xiàn)期望值；
下面介紹一下model-based的情況。
也就是說我們知道了世界的運(yùn)轉(zhuǎn)規(guī)律，在這個(gè)基礎(chǔ)上找到最優(yōu)的策略，使得value function取到最優(yōu)值。
一般來說，強(qiáng)化學(xué)習(xí)的模型包括兩個(gè)：決策模型和獎勵模型。
如果是用馬爾科夫模型，那么就是Markov Decision Process和Markov Reward Process，即MDP和MRP。
馬爾科夫性質(zhì)說的是未來與過去無關(guān)，只跟當(dāng)前有關(guān)。
學(xué)過信息學(xué)競賽的同學(xué)都知道有個(gè)算法叫做動態(tài)規(guī)劃，或者大學(xué)算法課也會學(xué)到。
動態(tài)規(guī)劃的特點(diǎn)就是無后向性，本質(zhì)上也是未來與過去無關(guān)，只跟當(dāng)前有關(guān)。
當(dāng)然，信息學(xué)競賽的動態(tài)規(guī)劃是確定性的，強(qiáng)化學(xué)習(xí)的動態(tài)規(guī)劃是隨機(jī)性的，因此只能近似求解，一般成為近似動態(tài)規(guī)劃，Approximate Dynamic Programming，或者ADP。
另外我們還有一個(gè)期限的概念，一般稱為Horizon。
馬爾可夫鏈可以分為無限和有限兩種。
一般涉及到很多計(jì)算的話，會用到discount factor，那么無窮期限的會涉及到無窮級數(shù)。
計(jì)算Value function可以這樣：
其中s是一個(gè)狀態(tài)，R(s)就是在這個(gè)狀態(tài)可以獲得的期望收益，一般是離開這個(gè)狀態(tài)的瞬間獲得。
那么離開這個(gè)狀態(tài)后，會有一定的概率去到下一個(gè)狀態(tài)s'，概率就是P(s'|s），這是一個(gè)條件概率，然后去到s'之后，在s'的value function取值是V(s'），因此總的獎勵就是所有的V(s'）按概率的加權(quán)值，當(dāng)然，由于這是下一個(gè)狀態(tài)，因此還要乘以discount ratio，這里就是gamma值。
如果有非常多的狀態(tài)，而且是有限的，比如N個(gè)狀態(tài)，那么可以組成一個(gè)列向量V，然后獎勵R(s)也組成一個(gè)向量R，轉(zhuǎn)移概率矩陣是P，那么，我們用線性代數(shù)來表示，可以得到
所以我們可以得到明確的解析解。
當(dāng)然，直接的矩陣求逆需要的復(fù)雜度是O(n^3)，這是比較耗時(shí)的，所以一般會用迭代的方法。
比如一直迭代計(jì)算Value function，直到V(s)不怎么變化為止，這樣復(fù)雜度是O(|S|^2)，因?yàn)槊看斡?jì)算是|S|次，要它收斂最多|S|次，這里|S|=N，這樣可以減少一個(gè)數(shù)量級。
下面介紹一下Markov Decision Process(MDP)。
MDP可以看成一個(gè)tuple，（S,A,P,R,gamma），溫習(xí)一下：
· S：state，表示狀態(tài)空間；
· A：action，表示決策空間；
· P：probability，表示狀態(tài)轉(zhuǎn)移概率矩陣
· R：reward，表示期望獲利；
· gamma：表示折現(xiàn)率
但這里并沒有涉及到policy。
如果涉及到了policy，那么就是MRP，Markov Reward Process
MDP+pi(a|s)=Markov Reward Process
它可以表示為：
而對應(yīng)的公式主要有兩個(gè)：
可以看出，reward函數(shù)和概率轉(zhuǎn)移函數(shù)都有兩種，不帶policy的有s和a兩個(gè)變量，帶policy的只有s一個(gè)變量，而policy本身是從s到a的概率。
然后，把對應(yīng)的R^pi和P^pi代入V的迭代公式，可以計(jì)算出相關(guān)policy下的V^pi的迭代公式，這一般成為一個(gè)policy的Bellman Backup：
其實(shí)也好理解，比如對于r(s,a)這個(gè)函數(shù)，需要兩個(gè)變量，然后pi找個(gè)函數(shù)把s映射到a，所以可以用r(s,pi(s))；對于p(s'|s,a)，也同理把a(bǔ)替換成pi(s)，這樣函數(shù)只有s一個(gè)變量。
另外，我們還可以定義另一個(gè)函數(shù)Q，這個(gè)函數(shù)跟具體的policy有關(guān)，但當(dāng)前要采取的策略未知，只是未來采取的是既定的policy：
可以看到，它有兩個(gè)變量：s和a，其中s是state，a是action；另外，它還自帶有policy pi，后續(xù)的policy是確定的，就是V^pi，但當(dāng)前的policy是未知的，因此保留了action a這個(gè)變量。
這個(gè)新定義的函數(shù)Q有什么作用呢？主要用于迭代。
迭代中我們每次更新一次V^pi，然后代入Q^pi(s,a)中，就可以求得所有s和所有a的值；然后針對每個(gè)s，都可以用對應(yīng)的取到最大值的a值，這個(gè)映射作為新的policy，畢竟policy本身就是s->a的映射，這樣就實(shí)現(xiàn)了policy的迭代，這個(gè)過程稱為policy improvement；設(shè)置初始條件，重復(fù)這個(gè)過程，直到收斂，這個(gè)過程就稱為policy iteration。
在強(qiáng)化學(xué)習(xí)領(lǐng)域，存在著一個(gè)意識形態(tài)分歧，就是關(guān)于到底policy iteration和value iteration哪個(gè)好的問題?？赡茚槍Σ煌膯栴}可以有不同的解。為此，強(qiáng)化學(xué)習(xí)兩大陣營DeepMind和OpenAI可謂針鋒相對：DeepMind是開發(fā)AlphaGo的，因?yàn)閲宓挠⑽氖荊o，所以起了這個(gè)名字，量化礦工一般戲稱自己為“阿爾法狗”；這下棋可以大量生成隨機(jī)博弈的樣本，所以更適合value iteration；但OpenAI是馬斯克贊助的，可希望解決實(shí)際問題而不是打游戲，實(shí)際問題的樣本當(dāng)然是比較昂貴的，比如自動駕駛，要獲得真實(shí)數(shù)據(jù)需要開車實(shí)地去跑，因此樣本很珍貴，這樣更適合用policy iteration。
應(yīng)該說，比較炫酷的成果都是value iteration做出來的，但真正對現(xiàn)實(shí)生活有意義的成果都是policy iteration那方面的。當(dāng)然，也有一些人奉行中庸之道，既不純粹的value iteration，也不純粹的policy iteration，而是各取所長，于是出現(xiàn)了所謂artci critic算法，或者還有新版本A2C、A3C等；當(dāng)然，學(xué)術(shù)界灌水也不要太在意。
類似當(dāng)年regularization，傳統(tǒng)的ridge是L2-norm，后來的lasso是L1-norm，有人說我奉行中庸之道，各取一點(diǎn)，就取了個(gè)名字叫elasitc-net，也發(fā)了不少paper。這年頭，混口飯吃也不容易。
言歸正傳，我們給出policy iteration的具體公式，結(jié)束本次的課程：
首先對于所有的s和a，我們有：
然后我們可以得到新的policy，也就是對Q取最大值對應(yīng)的a：
關(guān)于policy iteration的具體討論下次再說。
