二、强化学习—马尔可夫决策过程
文章目录
1. Markov Process马尔科夫过程
- 马尔可夫性质 ：如果一个状态转移是符合马尔可夫的，那就是说一个状态的下一个状态只取决于它当前状态，而跟它当前状态之前的状态都没有关系。
-
马尔可夫链：。举个例子，这个图里面有四个状态，这四个状态从 s1, s2, s3, s4之间互相转移。比如说从 s1 开始，s1 有 0.1 的概率继续存活在 s1 状态，有 0.2 的概率转移到 s2，有 0.7 的概率转移到 s4 。如果 s4 是我们当前状态的话，它有 0.3 的概率转移到 s2，有 0.2 的概率转移到 s3，有 0.5 的概率留在这里。
-
用状态转移矩阵：当我们知道当前我们在 st 这个状态过后，到达下面所有状态的一个概念。所以它每一行其实描述了是从一个节点到达所有其它节点的概率。
2. Markov Reward Process马尔科夫奖励过程(MRP)
马尔可夫奖励过程 (Markov Reward Process, MRP)是马尔可夫链再加上了一个奖励函数。在 MRP中，转移矩阵和状态都是跟马尔可夫链一样的，多了一个奖励函数 (reward function)。奖励函数 R 是一个期望，就是说当你到达某一个状态的时候，可以获得多大的奖励。然后这里另外定义了一个 discount factor γ 。如果状态数是有限的，R 可以是一个向量。
2.1 回报和价值函数
对于 MRP，状态价值函数被定义成是回报的期望，如下式所示：
其中
2.2 贝尔曼方程
从这个价值函数里面推导出 Bellman Equation（贝尔曼等式），如下式所示：
其中：
Bellman Equation 就是当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算。Bellman Equation 因其提出者、动态规划创始人 Richard Bellman 而得名，也叫作“动态规划方程”。
Bellman equation 的推导过程如下：
贝尔曼方程的意义：假设我们当前是在 s1，那么它只可能去到三个未来的状态：有 0.1 的概率留在它当前这个位置，有 0.2 的概率去到 s2 状态，有 0.7 的概率去到 s4 的状态，所以我们要把这个转移乘以它未来的状态的价值，再加上它的 immediate reward 就会得到它当前状态的价值。所以 Bellman Equation 定义的就是当前状态跟未来状态的一个迭代的关系。
3. Markov Decision Process马尔科夫决策过程(MDP)
马尔可夫决策过程 (Markov Decision Process)多了一个 decision，其它的定义跟 MRP都是类似的:
顺着 MDP 的定义，我们可以把状态-价值函数 (state-value function)，就是在 MDP 里面的价值函数也进行一个定义，它的定义是跟 MRP 是类似的，如下所示此处我们给出 Q 函数的 Bellman equation：
MDP 是满足动态规划的要求的，
- 在 Bellman equation 里面，我们可以把它分解成一个递归的结构。当我们把它分解成一个递归的结构的时候，如果我们的子问题子状态能得到一个值，那么它的未来状态因为跟子状态是直接相连的，那我们也可以继续推算出来。价值函数就可以储存并重用它的最佳的解。
- 动态规划应用于 MDP 的规划问题 (planning) 而不是学习问题 (learning)，我们必须对环境是完全已知的 (Model-Based)，才能做动态规划，直观的说，就是要知道状态转移概率和对应的奖励才行
- 动态规划能够完成预测问题和控制问题的求解，是解 MDP prediction 和 control 一个非常有效的方式。
思考
为什么在马尔可夫奖励过程（MRP）中需要有 discount factor?
首先，是有些马尔可夫过程是带环的，它并没有终结，然后我们想避免这个无穷的奖励；另外，我们是想把这个不确定性也表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励；接上面一点，如果这个奖励是它是有实际价值的了，我们可能是更希望立刻就得到奖励，而不是我们后面再得到奖励。还有在有些时候，这个系数也可以把它设为 0。比如说，当我们设为 0 过后，然后我们就只关注了它当前的奖励。我们也可以把它设为 1，设为 1 的话就是对未来并没有折扣，未来获得的奖励跟我们当前获得的奖励是一样的。
计算贝尔曼等式（Bellman Equation）的常见方法以及区别？
- Monte Carlo Algorithm（蒙特卡罗方法）：可用来计算价值函数的值。通俗的讲，我们当得到一个 MRP 过后，我们可以从某一个状态开始，然后让它让把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的Discounted的奖励 g 直接算出来。算出来过后就可以把它积累起来，当积累到一定的轨迹数量过后，然后直接除以这个轨迹，然后就会得到它的这个价值。
- Iterative Algorithm（动态规划方法）：可用来计算价值函数的值。通过一直迭代对应的 BellmanEquation，最后使其收敛。当这个最后更新的状态跟你上一个状态变化并不大的时候，通常是小于一个阈值 γ ，这个更新就可以停止。
- 以上两者的结合方法：另外我们也可以通过 Temporal-Difference Learning 的那个办法。这个Temporal-Difference Learning 叫 TD Leanring，就是动态规划和蒙特卡罗的一个结合。
马尔可夫奖励过程（MRP）与马尔可夫决策过程（MDP）的区别？
相对于 MRP，马尔可夫决策过程 (Markov Decision Process) 多了一个 decision，其它的定义跟 MRP 都是类似的。这里我们多了一个决策，多了一个 action ，那么这个状态转移也多了一个condition，就是采取某一种行为，然后你未来的状态会不同。它不仅是依赖于你当前的状态，也依赖于在当前状态你这个 agent 它采取的这个行为会决定它未来的这个状态走向。对于这个价值函数，它也是多了一个条件，多了一个你当前的这个行为，就是说你当前的状态以及你采取的行为会决定你在当前可能得到的奖励多少。
另外，两者之间是有转换关系的。具体来说，已知一个 MDP 以及一个 policy π 的时候，我们可以把MDP 转换成 MRP。在 MDP 里面，转移函数 P(s′|s, a) 是基于它当前状态以及它当前的 action，因为我们现在已知它 policy function，就是说在每一个状态，我们知道它可能采取的行为的概率，那么就可以直接把这个 action 进行加和，那我们就可以得到对于 MRP 的一个转移，这里就没有 action。同样地，对于奖励，我们也可以把 action 拿掉，这样就会得到一个类似于 MRP 的奖励。
总结
下次说说Q-Learning求解强化学习问题的方法。