【DataWhale打卡】周博磊博士-第二节马尔科夫决策过程，主要内容：

• 马尔科夫链、马尔科夫奖励过程、马尔科夫决策过程
• Policy evaluation in MDP
• Control in MDP: policy iteration & value iteration

这部分主要讲的除了MDP问题本身，主要是动态规划方面的求解方法。

一、引入

Agent 在得到环境的状态过后，它会采取行为，它会把这个采取的行为返还给环境。环境在得到 agent 的行为过后，它会进入下一个状态，把下一个状态传回 agent。

在强化学习中，这个交互过程是可以通过马尔可夫决策过程来表示的，所以马尔可夫决策过程是强化学习里面的一个基本框架。

在马尔可夫决策过程中，它的环境是 fully observable ，就是全部可以观测的。但是很多时候环境里面有些量是不可观测的，但是这个部分观测的问题也可以转换成一个 MDP 的问题。

二、Markov Process(MP)

Markov Property

如果一个状态转移是符合马尔可夫的，那就是说一个状态的下一个状态只取决于它当前状态，而跟它当前状态之前的状态都没有关系。
如果某一个过程满足马尔可夫性质(Markov Property)，就是说未来的转移跟过去是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

Markov Chain

可以用状态转移矩阵(State Transition Matrix)来描述这样的状态转移。状态转移矩阵类似于一个 conditional probability，当知道当前在 s_tst 这个状态过后，到达下面所有状态的一个概念。所以它每一行其实描述了是从一个节点到达所有其它节点的概率。

三、Markov Reward Process(MRP)

马尔可夫奖励过程(Markov Reward Process, MRP) 是马尔可夫链再加上了一个奖励函数。

在 MRP 中，转移矩阵跟它的这个状态都是跟马尔可夫链一样的，多了一个奖励函数(reward function)。

奖励函数是一个期望，就是说当你到达某一个状态的时候，可以获得多大的奖励，然后这里另外定义了一个 discount factor \gammaγ 。

Return & Value function

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

关于$\gamma$的解释

这里解释一下为什么需要 discount factor。

• 有些马尔可夫过程是带环的，它并没有终结，想避免这个无穷的奖励。
• 并没有建立一个完美的模拟环境的模型，也就是说，对未来的评估不一定是准确的，不一定完全信任的模型，因为这种不确定性，所以对未来的预估增加一个折扣。想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。
• 如果这个奖励是有实际价值的，可能是更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。
• 在人的行为里面来说的话，大家也是想得到即时奖励。
• 有些时候可以把这个系数设为 0，设为 0 过后，就只关注了它当前的奖励。也可以把它设为 1，设为 1 的话就是对未来并没有折扣，未来获得的奖励跟当前获得的奖励是一样的。

Value Funtion in MRP

蒙特卡罗采样法：比如计算$V(s_4)$的值，那么就采样从s4开始很多轨迹，到最终的价值，平均一下作为value值。

贝尔曼等式：Bellman Equation 定义了当前状态跟未来状态之间的这个关系。

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

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

Bellman Equation 就是当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算。

Bellman Equation 因其提出者、动态规划创始人 Richard Bellman 而得名 ，也叫作“动态规划方程”。

可以把 Bellman Equation 写成一种矩阵的形式。首先有这个转移矩阵。当前这个状态是一个向量 $[V(s_1),V(s_2),\cdots ,V(s_N){]}^T$。可以写成迭代的形式。每一行来看的话，V这个向量乘以了转移矩阵里面的某一行，再加上它当前可以得到的 reward，就会得到它当前的价值。

当写成如下的矩阵形式后:

$$V=R+\gamma PV$$

就可以直接得到一个解析解(analytic solution):

$$V=(I-\gamma P{)}^{-1}R$$

通过矩阵求逆的过程把这个 V 的这个价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 $O(N^3)$。在量级很大的时候，求解难度很大。只适合于小量的MRP。

通过迭代法解决大型的MRP

• 通过动态规划的方法，
• 通过蒙特卡罗的办法，就通过采样的办法去计算它，
• 通过 Temporal-Difference Learning 的办法。这个 Temporal-Difference Learning 叫 TD Leanring，它是动态规划和蒙特卡罗的一个结合。

1. Monte Carlo(MC)

和上文类似，相同的意思，采样，然后取平均。

2. Dynamic Programming(DP)

用这个动态规划的办法，一直去迭代它的 Bellman Equation，让它最后收敛，就可以得到它的一个状态。

当这个最后更新的状态跟你上一个状态变化并不大的时候，更新就可以停止，就可以输出最新的 V’(s)V′(s) 作为它当前的状态。

动态规划的方法基于后继状态值的估计来更新状态值的估计（算法二中的第 3 行用 V’ 来更新 V ）。也就是说，它们根据其他估算值来更新估算值。称这种基本思想为 bootstrapping。

四、Markov Decision Process(MDP)

MDP定义

相对于 MRP，马尔可夫决策过程(Markov Decision Process)多了一个 decision，其它的定义跟 MRP 都是类似的。

这里多了一个决策，多了一个 action ，那么这个状态转移也多了一个 condition，就是你采取某一种行为，然后你未来的状态会不同。

它不仅是依赖于你当前的状态，也依赖于在当前状态你这个 agent 它采取的这个行为会决定它未来的这个状态走向。

对于这个价值函数，它也是多了一个条件，多了一个你当前的这个行为，就是说你当前的状态以及你采取的行为会决定你在当前可能得到的奖励多少。

Policy in MDP

Policy 定义了在某一个状态应该采取什么样的行为。

当知道当前状态过后，可以带入这个 policy function，那会得到一个概率，概率就代表了在所有可能的行为里面怎样去采取行动。

这个策略也可能是确定的，它有可能是直接输出一个值，或者就直接告诉你当前应该采取什么样的行为，而不是一个行为的概率。

这里有一个假设，就是这个概率函数应该是静态的(stationary)，不同时间点，采取的行为其实都是对这个 policy function 进行采样。

**这里说明了 MDP 跟 MRP 的之间的一个转换。**已知一个 MDP 和一个 policy \piπ 的时候，可以把 MDP 转换成 MRP。

在 MDP 里面，转移函数 P(s’|s,a) 是基于它当前状态以及它当前的 action。因为现在已知它 policy function，就是说在每一个状态，知道它可能采取的行为的概率，那么就可以直接把这个 action 进行加和，直接把这个 a 去掉，那就可以得到对于 MRP 的一个转移，这里就没有 action。

对于这个奖励函数，也可以把 action 拿掉，这样就会得到一个类似于 MRP 的奖励函数。

Comparison of MP、MRP & MDP

MDP 里面的状态转移跟 MRP 以及 MP 的差异

• 马尔可夫过程的转移是直接就决定。比如当前状态是 s，那么就直接通过这个转移概率决定了下一个状态是什么。

• 但对于 MDP，它的中间多了一层这个行为 a

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

Value funtion in MDP

这里 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 diagram图理解(10)&(11)

Backup DIagram for $V^{\pi }$

Backup 类似于 bootstrapping 之间这个迭代关系，就对于某一个状态，它的当前这个价值是跟它未来价值线性相关的。

可以看到这里有两层加和。第一层加和就是这个叶子节点，然后往上走一层的话，就可以把未来的这个价值 s’ backup 到黑色的节点。然后再有一层加和，第二层加和，这个加和是把 action 进行加和。

得到黑色节点的价值过后，再往上 backup 一层，然后就会推到根节点的价值，根节点就是当前状态。所以 Backup Diagram 定义了你未来下一时刻的状态跟你上一时刻的状态之间的一个关联。

Backup Diagram for $Q^{\pi }$

对于 Q 函数，就现在的根节点是这个 Q 函数的一个节点。这个 Q 函数是对于黑色的这个节点。下一时刻的这个 Q 函数是叶子节点，有四个黑色结点。那么这里也有两个加和。

第一层加和是先把这个叶子节点从黑节点推到这个白色的这个节点，进了它的这个状态，就当到达某一个状态过后，这个白色节点，然后再进行一个加和，这样就把它重新推回到当前节点的一个 Q 函数，所以这个等式就决定了未来 Q 函数跟当前 Q 函数之间的这个关联。

Policy Evaluation /Prediction

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

Decision Making in Markov Decision Process

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

• Prediction 是说给定一个 MDP 以及一个 policy π ，去计算它的 value function，就对于每个状态，它的价值函数是多少。
• Control 是说去寻找一个最佳的策略：
  • 它的 input 就是 MDP，
  • 输出是通过去寻找它的最佳策略，然后同时输出它的最佳价值函数(optimal value function)以及它的最佳策略(optimal policy)。
• 在 MDP 里面，prediction 和 control 都可以通过这个动态规划去解决。
• 要强调的是，这两者的区别就在于，
  • 预测问题是给定一个 policy，要确定它的 value function 是多少。
  • 而控制问题是在没有 policy 的前提下，要确定最优的 value function 以及对应的决策方案。
• 实际上，这两者是递进的关系，在强化学习中，通过解决预测问题，进而解决控制问题。

五、动态规划

动态规划是说把可以把一个问题分解成一个最佳子结构，当可以把一些子结构都可以解决的话，那么它就可以组成一个最优的解。

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

1. Policy Evaluation on MDP

Policy evaluation 就是当给定一个 MDP 的时候，有一个事先定好的 policy。那么可以获得多少的价值。

就对于当前这个策略，可以得到多大的这个 value function。这里一个方法是说，直接把这个 Bellman Expectation Backup，这个等式拿出来，变成一个迭代的过程，这样反复迭代直到收敛。这样就可以计算它的一个过程。这个迭代过程是可以看作是 synchronous backup 的一个过程。

2. Policy Evaluation

Policy evaluation 的核心思想就是直接把这个 Bellman expectation backup（15）式。然后反复迭代，然后就会得到一个收敛的价值函数的值。

因为已经给定了这个函数的 policy function，那可以直接把它简化成一个 MRP 的表达形式，那么它的形式就更简洁一些，就相当于把这个 a 去掉，得到（16）式。

这样它就只有价值函数跟转移函数了。通过去迭代这个更简化的一个函数，也可以得到它每个状态的价值。因为不管是在 MRP 以及 MDP，它的这个价值函数包含的这个变量都是只跟这个状态有关，就相当于进入某一个状态，未来可能得到多大的价值。

3. Optimal Value Function

Policy evaluation 是说给定一个 MDP 和一个 policy，可以估算出它的价值函数。

这个问题的另外一方面是说如果只有一个 MDP，如何去寻找一个最佳的策略，然后可以得到一个最佳价值函数(Optimal Value Function)。

Optimal Value Function 的定义是说，去搜索一种 policy π ，然后会得到每个状态它的状态值最大的一个情况，v∗ 就是到达每一个状态，它的值的极大化情况。

在这种极大化情况上面，得到的策略就可以说它是最佳策略(optimal policy)。Optimal policy 使得每个状态，它的状态函数都取得最大值。

所以当说某一个 MDP 的环境被解了过后，就是说可以得到一个 optimal value function，然后就说它被解了。在这种情况下面，然后它的最佳的价值函数是一致的，就它达到了这个 upper bound，它的值是一致的，但是这里可能有多个最佳的 policy，多个 policy 可以取得相同的最佳价值。

Finding Optimal Policy

寻找这个最佳的 policy ，这里一个隐含条件是当取得最佳的价值函数过后，其实可以通过对这个 Q 函数进行极大化，然后得到最佳的价值。当所有东西都收敛过后，因为 Q 函数是关于状态跟动作的一个函数，所以对某一个状态采取一个行为，然后可以使得这个 Q 函数最大化，那么就这个行为就应该是最佳的行为。所以当能优化出一个 Q 函数，可以直接在这个 Q 函数上面取一个让这个 action 最大化的值，就可以直接提取出它的最佳策略。

Policy Search

这里一种策略搜索办法是可以去穷举。假设有有限多个状态、有限多个行为可能性，那么每个状态可以采取这个 A 种行为的策略，那么总共就是 $|A{|}^{|S|}$ 个可能的 policy。那么有一种方法是直接可以把这个把穷举一遍，然后算出每种策略的 value function，然后对比一下可以得到最佳策略。

但是一个问题是这样的穷举非常没有效率，所以要采取另外的一些办法，所以在解这个搜索最佳策略的方法有两种比较常用的方法：一种是叫 policy iteration，另外一种是叫 value iteration 的一个方法。

4. Policy Iteration

policy iteration 也是一个迭代算法。它主要由两个步骤组成:

• 第一个步骤是 policy evaluation，就跟之前说的这个评价一个已有的这个价值函数的价值是一致的，就是当前在优化这个 policy \piπ ，所以在优化过程中得到一个最新的这个 policy 。让先保证这个 policy 不变，那么去估计它出来的这个价值。给定当前的policy function，去估计这个 v 函数。
• 取得 v 函数过后，可以进一步推算出它的 Q 函数。得到 Q 函数过后，那就直接去取它的极大化。在 Q 函数上面取极大化，**这样就有了第二步骤：改进它的策略。**通过在这个 Q 函数上面做一个贪心的搜索，这样就会进一步改进它的策略。
• 这两个步骤就一直是在迭代进行，所以在这个 policy iteration 里面，在初始化的时候，有一个初始化的 V 和 π 。然后就是在这两个过程之间迭代，左边这幅图上面这根曲线就是当前这个 v 的值，下面是 policy 的值。就跟踢皮球一样，先给定当前已有的这个 policy function，然后去算它的这个 v。算出 v 过后，会得到一个 Q 函数，Q 函数采取 greedy 的策略，这样有踢皮球，踢回这个 policy 。然后就会进一步改进那个 policy ，得到一个改进的 policy 过后，它还不是最佳的，再进行 policy evaluation，然后又会得到一个新的 value function。基于这个新的 value function 再进行 Q 函数的极大化 ，这样就逐渐迭代，然后就会得到收敛。

Policy Improvement

当得到这个 v 值过后，就可以通过这个 reward function 以及状态转移把它的这个 Q-function 算出来。对于每一个状态，第二个步骤会得到它的一个新一轮的这个 policy ，就在每一个状态，去取使它得到最大值的 action。你可以把这个 Q 函数看成一个 Q-table。横轴是它的所有状态，纵轴是它的可能的 action。Q 函数得到过后，Q-table 就得到了。

那么对于某一个状态，每一列里面会取最大的那个值，最大值对应的那个 action 就是它现在应该采取了更佳的action。所以你看这里下面这个 arg max 操作就说在每个状态里面，去采取一个 action，这个 action 就是能使这一列的 Q 最大化的那个动作。

Monotonic Improvement in Policy

.

当改进停止过后，取它极大化的这个 action 之后，它直接就会变成它的这个价值函数$q^{\pi }(s,\pi \prime (s))=ma{x}_{a\in A}{q}^{\pi }(s,a)=q^{\pi }(s,\pi (s))=v^{\pi }(s)$, 有了一个新的等式:
$$v^{\pi }(s)=ma{x}_{a\in A}{q}^{\pi }(s,a)$$
上式被称为 Bellman Optimality Equation。**这个 Bellman Optimality Equation 满足的时候，是说整个 MDP 已经到达最佳的状态。**它到达最佳状态过后，对于这个 Q 函，取它最大的 action 时候的那个值，就是直接等于它的最佳的这个 value function。只有当整个状态已经收敛过后，得到一个最佳的 policy 的时候，这个条件才是满足的。

5. Bellman Optimality Equation

最佳的价值函数到达过后，这个 Bellman Optimlity Equation 就会满足。满足过后，就有这个 max 操作，当取最大的这个 action 的时候对应的那个值就是当前那个状态的最佳的价值函数。

可以把第一个等式插入到第二个等式里面去，然后就会得到这个 Q 函数之间的这个转移。它下一步这个状态取了这个 max 这个值过后，就会也跟它下一个最佳的这个状态等价。

6. Value Iteration

**Value iteration 说的是把 Bellman Optimality Equation 当成一个 update rule 来进行。**之前是说上面这个等式只有当整个状态已经到达最佳状态的时候，然后才满足。但这里可以把它转换成一个 backup 的等式。 Backup 就是说一个迭代的等式，不停地去迭代 Bellman Optimality Equation，到了最后，它能逐渐趋向于最佳的策略，所以这也是 value iteration 算法的精髓，就是去为了得到最佳的v∗ ，对于每个状态它的 v∗ 这个值，直接把这个 Bellman Optimality Equation 进行迭代，迭代了很多次之后它就会收敛。

具体算法如下：

Policy Iteration & Value Iteration 的区别

再来对比下 policy iteration 和 value iteration，这两个算法都可以解 MDP 的控制问题。

• Policy iteration 由两部分组成：policy evaluation 和 policy improvement。它很清楚地把这个过程分成了两步，就首先对于当前已经搜索到的策略函数，然后对它进行一个估值，得到估值过后，把 Q 函数算出来，进一步进行改进。
• 但对于 value iteration 的话，它是直接把 Bellman Optimality Equation 拿进来，然后直接去寻找最佳的 value function，没有 policy function 在这里面，当把这个 optimal value function 算出来过后，那可以在最后再执行一步这个提取过程，最佳策略提取过程。这样就可以把它的最佳策略抽取过来。

7. Prediction & Control in MDP

这里是一个总结，就对于 MDP 里面的 prediction 和 control 都是用动态规划来讲，其实采取了不同的 Bellman Equation。

• 如果是一个 prediction 的问题，即 policy evaluation 的问题，那就直接是把这个 Bellman Expectation Equation 拿进来，就是不停地 run 这个 Bellman Expectation Equation，这样就可以去估计出给定的这个策略，然后可以得到的价值函数。
• 对于 control，
  • 如果采取的算法是 policy iteration，那这里用的是 Bellman Expectation Equation 。把它分成两步，先上它的这个价值函数，再去优化它的策略，然后不停迭代。这里用到的只是 Bellman Expectation Equation。
  • 如果采取的算法是 value iteration，那这里用到的 Bellman Equation 就是 Bellman Optimality Equation，通过 arg max 这个过程，不停地去 arg max 它，最后它就会达到最优的状态。

总结

总体来看，MDP这部分理解比较清晰，但是动态规划这边还需要反复观看才能深入理解。