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