上次讲到强化学习的问题可以分成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的具体讨论下次再说。
