强化学习：Markov Decision Process (基于南大俞扬博士演讲的修改和补充）
马尔科夫决策过程（Markov Decision Process）
一、强化学习基本数学模型——马尔科夫过程（Markov Process）
大家可能听到了很多词，包括MDP，Q-Learning 、还有很多算法的名字，我在报告里就简单介绍一下强化学习发展的过程，以及里面会碰到什么问题。
强化学习的历史非常悠久，其中，早期的强化学习和它的一个数学模型MDP有很大关系，我先直观介绍一下MDP。
-
对MDP的直观介绍
MDP（Markov Decision Process）里面有三个词，其中过程“Process”是代表时间变动的变量，马尔科夫“Markov”说明这个变动是没有记忆效应的，下一步往哪儿走只取决于当前状态。马尔科夫过程可以用图(graph)来描述，这个图上的每个点就是这一个状态。这上面有很多边(edge)，表示它可以做的动作。对于每一个状态来说，出边的概率和为1。这是从它的状态和转移（transition）角度来看的。
我们还可以从时间的角度来看。比如说现在在某个状态，而到下一时刻，它会根据不同的转移概率转移到不同的状态去。随着时间变化而转移到下一个时刻的状态去，我们把它称之为水平（horizon）视角。
稳态分布（Stationary Distribution）
-
什么是稳态分布?
大部分马尔科夫的过程都会有一个稳态分布，意为当时间很长甚至无穷远的时候，大部分马尔科夫都会收敛到一个均衡的分布上，不再随时间变化。
比如说天气，确定了出太阳、多云和下雨的转移概率p(s'|s)以后，可能到30天以后它出太阳、下雨还是多云的概率和今天是不是出太阳已经没有关系了，它会收敛到一个确定的概率分布上面去。
-
马尔科夫回报过程（Markov Reward Process）？
马尔科夫回报过程是当状态出现转移的时候，除了用刚才的转移概率描述以外，还存在一个奖赏。
假设天气一直是出太阳的状态，这样运行下去以后，我能拿到的总回报是多少。这个总的回报可以用一个符号V来表示。根据之前我们的描述，我们可以有不同的计算方式，比如说全部加起来或者打个折再相加。
怎么算长期回报？我们从初始状态开始，按照0.2、0.7、0.1分别转移到不同的状态之后，按新的概率，把这个状态以下总的回报值加起来，就得到这个状态回报的值。相当于这一步展开以后再部加起来。这就变成一个递归式，也就是第0步变成第1步要计算的步骤，第1步又变成第2步要算的步骤。
算法里有一个加速计算的方式，叫动态规划( Dynamic Programming)，是倒过来算的。(这个公式称为Bellman Equation)
可以理解为，首先设置最后一层（第T层）的V值是0，倒过来算T-1层的V层是多少，再倒过来算T-2的......把这个式子重复T次。
这是走T步的，还有走无穷多步的。我们假设站在无穷大的最后一个点上，这个点照样每个状态上面的V都是0，然后算无穷大-1步是多少，无穷大-2步是多少，往后退无穷多步。但是算法无法实现这个过程，实际上用算法也不需要退无穷多步，因为存在折扣，即退一定步数以后，这个值就会固定不变。
二、马尔科夫决策过程（Markov Decision Process）
-
如何形成马尔科夫决策过程？
对于马尔科夫过程和马尔科夫决策过程，我们只能观察它运行下去的结果，而不能对它的运行过程加以干涉。加上一个决策以后就可以干涉（动作）了，这就是马尔科夫决策过程，不同的动作决定了转移的概率是不一样的，所以现在我们可以在每个状态上选择不同的动作。 (红蓝色点代表着两个动作)
再看马尔科夫决策过程的水平视角，由于每个状态可能做不同的动作，所以转移概率也不同。
总的来说， 马尔科夫决策过程里有一个四元组，即状态、动作、奖赏、转移概率。
这个四元组和强化学习里面的四元组一样的，所以早期的强化学习是完全以MDP为数学基础的，对它来说也是要找一个策略，这个策略就是选择不同动作会有不同的概率，或者是确定性策略（deterministic policy），在一个状态就输出一个动作。
-
早期强化学习的策略和其特点
早期的策略是用表格表示的，表格上记录了每个状态下的动作，是一个非常简单的模型。这个模型在强化学习里面很常用。在监督学习中，早期也用过这种模型，但由于在真实应用里面很少用得上，所以很快就被淘汰了。
它的特点是表达能力极强，不过前提是动作和状态都是离散的。为什么表达能力极强呢？比如说对于确定性策略，每个状态下面做什么动作可以直接修改，而不影响到其他状态的动作(因为每个状态都是根据自己可做动作的价值来选择动作的)，所以它的表达很灵活。早期强化学习的很多理论都是建立在这种表达上，它虽然不实用，但是理论性质很好。
-
如何求解马尔科夫决策过程上的最优策略？
我们首先希望在马尔科夫决策过程上计算出给定策略的总回报。
这7和前面讲的在马尔科夫回报过程上计算总回报是一样的，因为一旦给定策略以后，它的转移分布已经全部确定了。这就退化成一个马尔科夫回报过程，即给定一个策略以后我们计算回报方式跟前面一样。稍微不一样的一点是，它的转移是按照策略给出的动作的概率进行的。所以写V的时候，V右上角写了一个π，这个π就是表示我们当前固定的策略是什么，给出了不同的策略以后，我们要算的V值的结果是不一样的。这个V值表示的含义是，从s这个部分出发，走了很久以后看它的回报是多少。
Q值函数用来描述动作价值。Q值函数比V函数多了一个动作输入，它要估计的是在状态s做了动作a以后，再跟着这个策略π一直做下去，它的回报是多少。有了Q值函，看到状态s后，把每个a带进去，看哪个a出来的Q值大，就用哪个a。所以这样就可以在当前状态直接决定用哪个动作了。
Q和V是有直接的对应关系的，如果按照策略来选择动作，平均的Q值就是V值（因为状态下的每个动作都是一样的概率被选择到）。
三、计算最优策略
-
最优策略是否存在？
我们考虑最优策略的时候会想，是否会有一个策略在所有状态上表现都是最好的，还是只能找到在绝大部分时候表现都最好、但在个别状态上面值要差一点的策略。实际上前者是存在的，这个结论依赖于一个假设，即策略需要用表格来表示。因为用表格来表示的话，它的表达能力足够强。
最优策略对应的V值就是最优V值，对应的Q值就是最优Q值，怎么样求取最优的策略呢？由于这个V和Q之间是有一定关系的，所以我这里先直接给出两个等式，一个是通过Q值来算Q值的，一个是通过V值来算V值的。只要把最优Q和V的关系代到一般Q和V的关系中就直接可得。
-
最优策略的两种算法
有这两个等式以后，就可以来求取最优策略。
-
第一种方法：首先评估给定一个策略以后，这个策略有多好，然后找一个方向来提高这个策略。
这个算法的意思是，先计算你给出的这个策略的V值，然后用这种等式来更新这个策略，更新完以后又去计算这个V值是多少，又来更新这个策略，这样就可以保证这个策略最后收敛到最优策略。当然前提是你使用的是这个表格状态表示，有穷多个的状态和有穷多个的动作，这个方式对应的等式就是刚才的第一个等式。这个算法可能效率比较低，因为它需要不断的评估更新后的策略。这一方法称为策略迭代。
-
第二种方法：直接通过V值来更新V值，这一方法称为值迭代 （Value Iteration）。
根据这两个等式就可以有两种计算最优策略的方法。在这里纪念一下提出者Bellman，实际上动态规划就是他的发明。
-
最优策略的复杂度是多少？
另外，我们看到这样一个求解最优策略的过程，它的复杂度是多少呢？它的复杂度是状态数量乘以动作数量 O(|S|*|A|)，这已经是在一个很简单的MDP上（确定性 MDP），这个复杂度从状态数量和动作数量上看，好像是一个线性的复杂度，复杂度并不高。前面我们说了强化学习求解最优策略是NP难的问题，那么这个差别在什么地方呢？差别就在于，通常在度量一个问题的复杂度时，并不是根据它有多少状态来度量的，而是用状态空间的维度来度量。因此Bellman发明了一个词叫“维度灾难”。如果我们用维度来度量的话，这个复杂度就是一个非常高的复杂度，比如说对于围棋来说，它的维度是19×19，但是它的有效状态数量超过了10的170次方。
这里简单的介绍了一下在MDP、马尔科夫决策上，怎么去求得一个策略。但是MDP并不是强化学习，因为它的四元组都已给出，特别是奖赏和转移。你任给它一个状态和动作，都可以算出奖赏值；转移也是，输入一个状态、动作以后，它会告诉你转移出来的状态是什么。
本文为俞扬博士《强化学习前沿》的上篇，下篇敬请关注雷锋网的后续内容。
雷锋网原创文章，未经授权禁止转载。详情见转载须知。