马尔科夫决策过程

马尔科夫过程 Markov Process(MP)

（1）马尔科夫性质

（2）马尔科夫过程/马尔科夫链

马尔科夫奖励过程 Markov Reward Process(MRP)

1. horizon：同一个episode或者是整个一个轨迹的长度，它是由有限个步数决定的。
2. return：Return 说的是我们把奖励进行折扣，然后获得的这个收益。Return 可以定义为奖励的逐步叠加，然后这里有一个叠加系数，就是越往后得到的奖励，折扣得越多。这说明我们其实更希望得到现有的奖励，未来的奖励就要把它打折扣。
3. state value function：这里定义成return的期望，G_t是discount return。这里取了一个期望，期望就是说从这个状态开始，你有可能获得多大的价值。所以这个期望也可以看成是一个对未来可能获得奖励的它的当前价值的一个表现。就是当你进入某一个状态过后，你现在就有多大的价值。

为什么需要discounted factor？

1. 有些马尔可夫过程是带环的，它并没有终结，我们想避免这个无穷的奖励。
2. 我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。
3. 外如果这个奖励是有实际价值的了，我们可能是更希望立刻就得到奖励，而不是后面再得到奖励。
4. 在人的行为里面来说的话，大家也是想得到即时奖励。
5. 在有些时候，这个系数也可以把它设为 0。比如说，当我们设为 0 过后，然后我们就只关注了它当前的奖励。我们也可以把它设为 1，设为 1 的话就是对未来并没有折扣，未来获得的奖励跟我们当前获得的奖励是一样的。这个系数其实是应该可以作为强化学习 agent 的一个超参数 hyper parameter 来进行调整，然后就会得到不同行为的 agent。

这里就引出了一个问题，当我们有了一些轨迹的实际 return，怎么计算它的价值函数。比如说我们想知道s₄状态的价值，就是当你进入s₄后，它的价值到底如何。一个可行的做法就是说我们可以产生很多轨迹，然后把这里的轨迹都叠加起来。比如我们可以s₄开始，采样生成很多轨迹，都把它的 return 计算出来，然后可以直接把它取一个平均作为你进入s₄它的价值。这其实是一种计算价值函数的办法，通过这个蒙特卡罗采样的办法计算s₄的状态。接下来会进一步介绍蒙特卡罗算法。
但是这里我们采取了另外一种计算方法，我们通过一定的推导就可以从这个价值函数里面推导出 Bellman Equation（贝尔曼等式） 。Bellman Equation 定义了当 前状态跟未来状态之间的这个关系。

其中，

• s’可以看成未来的所有状态
• 转移P(s’|s)是指从当前状态转移到未来状态的概率
• 第二部分可以看成是一个 Discounted sum of future reward
• V(s’)代表未来某一个状态的价值。我们从当前状态开始，有一定的概率渠道未来的所有状态，所以我们要把这个概率也写上去，这个转移矩阵也写上去，然后我们就得到了未来状态，再乘以γ，这样就可以把未来的奖励打折扣

未来打了折扣的奖励加上当前立刻可以得到的奖励，就组成了这个 Bellman Equation。Bellman Equation 的推导过程如下：

Bellman Equation 就是当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算。Bellman Equation 因其提出者、动态规划创始人Richard Bellman 而得名 ，也叫作“动态规划方程”。

解释：Bellman Equation 定义了状态之间的迭代关系。假设有一个马尔可夫转移矩阵是右边这个样子。Bellman Equation 描述的就是当前状态到未来状态的一个转移。假设我们当前是在 s₁， 那么它只可能去到三个未来的状态：有 0.1 的概率留在它当前这个位置，有 0.2 的概率去到 s₂状态，有 0.7 的概率去到 s₃的状态，所以我们要把这个转移乘以它未来的状态的价值，再加上它的 immediate reward 就会得到它当前状态的价值。所以Bellman Equation 定义的就是当前状态跟未来状态的一个迭代的关系。

贝尔曼方程的矩阵形式

迭代方法计算MRP的价值函数

由于上述贝尔曼方程矩阵形式的问题求解规模是O(n³)，比较复杂。因此人们又提出了三种通过迭代的方式来计算MRP的价值函数。

• 动态规划（Dynamic Programming）
• 蒙特卡洛（Monte-Carlo evaluation）
• 时间差分（Temporal-Difference learning）
  其中，时间差分方法是动态规划和蒙特卡洛方法的结合。

（1）蒙特卡洛算法计算MRP的价值函数

我们可以从某一个状态开始，然后让它让把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的 discounted 的奖励 g 直接算出来。算出来过后就可以把它积累起来，当积累到一定的轨迹数量过后，然后直接除以这个轨迹，然后就会得到它的这个价值。
比如说我们要算 s₄ 状态的一个价值，就可以从 s₄ 状态开始，随机产生很多轨迹，就产生很多小船，然后扔到这个转移矩阵里面去，然后它就会随波逐流，产生轨迹。每个轨迹，我们可以算到它的这个 return 。那么每个轨迹都会得到一个 return，让我们得到大量的 return 。比如说一百个、一千个的 return ，然后直接取一个平均，那么就可以等价于它现在 s₄ 这个价值。因为 s₄ 的价值 V(s₄) 定义了你未来可能得到多少的奖励。这就是蒙特卡罗采样的方法。

（2）动态规划算法计算MRP的价值函数

我们也可以用这个动态规划的办法，就通过这种一直去迭代它的 Bellman Equation，让它最后收敛，我们就可以得到它的一个状态。所以在这里算法二就是一个迭代的算法，通过 bootstraping 的办法，然后去不停地迭代这个 Bellman Equation。当这个最后更新的状态跟你上一个状态变化并不大的时候，这个更新就可以停止，我们就可以输出最新的 V’(s) 作为它当前的状态。所以这里就是利用到了 Bellman Equation，就把 Bellman Equation 变成一个 Bellman Update，这样就可以得到它的一个价值。

马尔科夫决策过程 Markov Decision Process(MDP)

相对于 MRP， 马尔可夫决策过程(Markov Decision Process) 多了一个 decision ，其它的定义跟 MRP 都是类似的。这里我们多了一个决策，多了一个 action，那么这个状态转移也多了一个 condition，就是你采取某一种行为，然后你未来的状态会不同。它不仅是依赖于你当前的状态，也依赖于在当前状态你这个 agent 它采取的这个行为会决定它未来的这个状态走向。对于这个价值函数，它也是多了一个条件，多了一个你当前的这个行为，就是说你当前的状态以及你采取的行为会决定你在当前可能得到的奖励多少。

Policy in MDP

策略（Policy）有两种形式：

• 概率：表示在某个状态采取某个动作的概率
• 确定值：直接输出一个值或者直接告诉你当前应该采取什么动作，而不是一个行为的概率
  然后这里我们有一个假设，就是这个概率函数应该是静态的(stationary)，不同时间点，你采取的行为其实都是对这个 policy function 进行采样。

MP/MRP 和 MDP的对比

简单来说，MDP 比 MP/MRP 多了一层action选择的过程，这里的行为由agent决定。
具体差异：

• 马尔可夫过程的转移是直接就决定。比如当前状态是 s，那么就直接通过这个转移概率决定了下一个状态是什么。
• ** 但对于 MDP，它的中间多了一层这个行为 a ，就是说在你当前这个状态的时候，首先要决定的是采取某一种行为，那么你会到了某一个黑色的点。到了这个黑色的节点，因为你有一定的不确定性，当你当前状态决定过后以及你当前采取的行为过后，你到未来的状态其实也是一个概率分布。所以你采取行为后，你可能有多大的概率到达某一个未来状态，以及另外有多大概率到达另外一个状态。所以在这个当前状态跟未来状态转移过程中这里多了一层决策性，这是 MDP 跟之 前的马尔可夫过程很不同的一个地方。在马尔可夫决策过程中，行为是由 agent 决定，所以多了一个 component，agent 会采取行为来决定未来的状态转移 **。

Value function for MDP

• state-value function：它的定义是跟 MRP 是类似的，但是这里 expectation
  over policy，就是这个期望是基于你采取的这个 policy ，就当你的 policy 决定过后，我们通过对这个 policy 进行采样来得到一个期望，那么就可以计算出它的这 个价值函数。
• Q 函数(action-value function)：这个 Q 函数定义的是在某一个状态采取某一个行为，然后它有可能得到的这个 return 的一个期望。这里期望其实也是 over policy function。所以你需要对这个 policy function 进行一个加和，然后最后得到它的这个价值。
• 对 Q 函数中的行为函数进行加和，就可以得到价值函数。

Bellman Expectation Equation

通过对状态-价值函数进行一个分解，我们就可以得到一个类似于之前 MRP 的 Bellman Equation，这里叫 Bellman Expectation Equation 。
对于 Q 函数，我们也可以做类似的分解，也可以得到对于 Q 函数的 Bellman Expectation Equation。
Bellman Expectation Equation 定义了你当前状态跟未来状态之间的一个关联。

那我们进一步进行一个简单的分解。等式 8 和等式 9 代表了价值函数跟 Q 函数之间的一个关联。我们把等式 8 插入到等式 9，就可以得到等式 11，它象征了你当前时刻的 Q 函数跟未来时刻的 Q 函数之间的一个关联。也可以把等式 9 插入等式 8 中，得到等式 10。等式 10 代表了当前状态的价值跟未来状态价值之间的一个关联。

这里有一个概念叫 Backup 。Backup 类似于 bootstraping(拔靴自助) 之间这个迭代关系，就对于某一个状态，它的当前这个价值是跟它未来价值线性相关的。你可以看到我们这里有两层加和。第一层加和就是这个叶子节点，然后往上走一层的话，我们就可以把未来的这个价值 backup 到黑色的节点。然后再有一层加和，第二层加和，这个加和是把 action 进行加和。得到黑色节点的价值过后，再往上 backup 一层，然后就会推到根节点的价值，根节点就是我们当前状态。所以Backup Diagram 定义了你未来下一时刻的状态跟你上一时刻的状态之间的一个关联。

同样对于 Q 函数，我们也可以进行这样的一个推导，就现在的根节点是这个 Q 函数的一个节点。这个 Q 函数是对于黑色的这个节点。我们下一时刻的这个 Q 函数是叶子节点，有四个黑色结点。那么我们这里也有两个加和。
第一层加和是先把这个叶子节点从黑节点推到这个白色的这个节点，进了它的这个状态，就当我们到达某一个状态过后，这个白色极点，然后再进行一个加和，这样就把它重新推回到当前节点的一个 Q 函数，所以这个等式就决定了未来 Q 函数跟当前 Q 函数之间的这个关联。

Policy Evaluation

当我们知道一个 MDP 以及要采取的策略 π ，那我们计算价值函数的过程，就是 policy evaluation 。就像我们在评估这个策略，我们会得到多大的奖励。Policy evaluation 在有些地方也被叫做 prediction ，也就是预测你当前采取的这个策略最终会产生多少的价值。

MDP，你其实可以把它想象成一个摆渡的人在这个船上面，她可以控制这个船的移动，这样就避免了这个船随波逐流。因为在每一个时刻，这个人会决定采取什么样的一个行为，这样会把这个船进行导向。MRP 跟马尔可夫链的过程的话，这个纸的小船会随波逐流，然后产生轨迹。MDP 的不同就是我们有一个 agent 去控制这个船，这样我们就可以尽可能多地获得奖励。

policy evaluation 的例子：怎么在这个决策过程里面计算它每一个状态的价值？

1. 假设环境里面有两种行为：往左走和往右走。
2. 现在的奖励函数应该是关于行为以及状态两个变量的一个函数。但我们这里就说，不管你采取什么行为，只要到达状态 s₁，就有 5 的奖励。只要你到达状态 s₇ 了，就有 10 的奖励，中间没有任何奖励。
3. 假设我们现在采取的一个策略，这个策略是说不管在任何状态，我们采取的策略都是往左走，这里假设价值折扣因子是零，那么对于 deterministic policy，最后估算出的价值函数是一致的。怎么得到这个结果，我们可以直接在去 run 这个 iterative equation，就把这个 Bellman Expectation Equation 拿到这个里面来，然后不停地迭代，最后它会收敛。收敛过后，它的值就是它每一个状态的价值。

再来看另外一个情况，就是如果折扣因子是 0.5，我们可以通过这个等式进行迭代：

然后就会得到它的状态。
另外一个练习的例子，就是说我们现在采取的 policy 在每个状态，我们有 0.5 的概率往左走，有 0.5 的概率往右走，那么放到这个状态里面去
如何计算？
其实也是把这个 Bellman Expectation Equation 拿出来，然后进行迭代就可以算出来了，就当我们开始的时候，我们可以初始化。初始化这个不同的 v(s’)都会有一个值，那么放到这个里面去迭代，最后它的v ，然后就会算出来。

prediction 和 control

MDP 的 prediction 和 control 是 MDP 里面的核心问题。

1. Prediction 是说给定一个 MDP 以及一个 policy π，去计算它的 value function，就等于每个状态它的价值函数是多少。
2. Control 这个问题是说我们去寻找一个最佳的一个策略，它的 input 就是MDP，输出是通过去寻找它的最佳策略，然后同时输出它的最佳价值函数(optimal value
   function)以及它的这个最佳策略(optimal policy)。
3. 在 MDP 里面，prediction 和 control 都可以通过这个动态规划去解决。

动态规划

动态规划是说我们把可以把一个问题分解成一个最佳子结构，当我们可以把一些子结构都可以解决的话，那么它就可以组成一个最优的解。MDP是满足动态规划的要求的，就是在 Bellman Equation 里面，我们可以把它分解成一个递归的一个结构。当我们把它分解成一个递归的结构的时候，如果我们的
子问题子状态能得到一个值，那么它的未来状态因为跟子状态是直接相连的，那我们也可以继续推算出来，所以这个价值函数就可以储存它以及重用它的最佳的解。所以动态规划是解 MDP prediction 和 control 一个非常有效的方式。

Policy evaluation on MDP