Chapter2 马尔可夫决策过程（MDP）

1 Keywords

• 马尔可夫性质(Markov Property): 如果某一个过程未来的转移跟过去是无关，只由现在的状态决定，那么其满足马尔可夫性质。换句话说，一个状态的下一个状态只取决于它当前状态，而跟它当前状态之前的状态都没有关系。
• 马尔可夫链(Markov Chain): 概率论和数理统计中具有马尔可夫性质（Markov property）且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）。
• 状态转移矩阵(State Transition Matrix): 状态转移矩阵类似于一个 conditional probability，当我们知道当前我们在 \(s_t\) 这个状态过后，到达下面所有状态的一个概念，它每一行其实描述了是从一个节点到达所有其它节点的概率。
• 马尔可夫奖励过程(Markov Reward Process, MRP)： 即马尔可夫链再加上了一个奖励函数。在 MRP之中，转移矩阵跟它的这个状态都是跟马尔可夫链一样的，多了一个奖励函数(reward function)。奖励函数是一个期望，它说当你到达某一个状态的时候，可以获得多大的奖励。
• horizon: 定义了同一个 episode 或者是整个一个轨迹的长度，它是由有限个步数决定的。
• return: 把奖励进行折扣(discounted)，然后获得的对应的收益。
• Bellman Equation（贝尔曼等式）: 定义了当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算。Bellman Equation 因其提出者、动态规划创始人 Richard Bellman 而得名 ，同时也被叫作“动态规划方程”。\(V(s)=R(S)+ \gamma \sum_{s' \in S}P(s'|s)V(s')\) ，特别地，矩阵形式：\(V=R+\gamma PV\)。
• Monte Carlo Algorithm（蒙特卡罗方法）： 可用来计算价值函数的值。通俗的讲，我们当得到一个MRP过后，我们可以从某一个状态开始，然后让它让把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的 Discounted 的奖励 \(g\) 直接算出来。算出来过后就可以把它积累起来，当积累到一定的轨迹数量过后，然后直接除以这个轨迹，然后就会得到它的这个价值。
• Iterative Algorithm（动态规划方法）： 可用来计算价值函数的值。通过一直迭代对应的Bellman Equation，最后使其收敛。当这个最后更新的状态跟你上一个状态变化并不大的时候，这个更新就可以停止。
• Q函数 (action-value function)： 其定义的是某一个状态某一个行为，对应的它有可能得到的 return 的一个期望（over policy function）。
• MDP中的prediction（即policy evaluation问题）： 给定一个 MDP 以及一个 policy \(\pi\) ，去计算它的 value function，即每个状态它的价值函数是多少。其可以通过动态规划方法（Iterative Algorithm）解决。
• MDP中的control问题： 寻找一个最佳的一个策略，它的 input 就是MDP，输出是通过去寻找它的最佳策略，然后同时输出它的最佳价值函数(optimal value function)以及它的这个最佳策略(optimal policy)。其可以通过动态规划方法（Iterative Algorithm）解决。
• 最佳价值函数(Optimal Value Function)： 我们去搜索一种 policy \(\pi\) ，然后我们会得到每个状态它的状态值最大的一个情况，\(v^*\) 就是到达每一个状态，它的值的极大化情况。在这种极大化情况上面，我们得到的策略就可以说它是最佳策略(optimal policy)。optimal policy 使得每个状态，它的状态函数都取得最大值。所以当我们说某一个 MDP 的环境被解了过后，就是说我们可以得到一个 optimal value function，然后我们就说它被解了。

2 Questions

• 为什么在马尔可夫奖励过程（MRP）中需要有discount factor?

  答：

  1. 首先，是有些马尔可夫过程是带环的，它并没有终结，然后我们想避免这个无穷的奖励；
  2. 另外，我们是想把这个不确定性也表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励；
  3. 接上面一点，如果这个奖励是它是有实际价值的了，我们可能是更希望立刻就得到奖励，而不是我们后面再得到奖励。
  4. 还有在有些时候，这个系数也可以把它设为 0。比如说，当我们设为 0 过后，然后我们就只关注了它当前的奖励。我们也可以把它设为 1，设为 1 的话就是对未来并没有折扣，未来获得的奖励跟我们当前获得的奖励是一样的。

  所以，这个系数其实是应该可以作为强化学习 agent 的一个 hyperparameter 来进行调整，然后就会得到不同行为的 agent。

• 为什么矩阵形式的Bellman Equation的解析解比较难解？

  答：通过矩阵求逆的过程，就可以把这个 V 的这个价值的解析解直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 \(O(N^3)\)。所以就当我们状态非常多的时候，比如说从我们现在十个状态到一千个状态，到一百万个状态。那么当我们有一百万个状态的时候，这个转移矩阵就会是个一百万乘以一百万的一个矩阵。这样一个大矩阵的话求逆是非常困难的，所以这种通过解析解去解，只能对于很小量的MRP。

• 计算贝尔曼等式（Bellman Equation）的常见方法以及区别？

  答：

  1. Monte Carlo Algorithm（蒙特卡罗方法）： 可用来计算价值函数的值。通俗的讲，我们当得到一个MRP过后，我们可以从某一个状态开始，然后让它让把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的 Discounted 的奖励 \(g\) 直接算出来。算出来过后就可以把它积累起来，当积累到一定的轨迹数量过后，然后直接除以这个轨迹，然后就会得到它的这个价值。
  2. Iterative Algorithm（动态规划方法）： 可用来计算价值函数的值。通过一直迭代对应的Bellman Equation，最后使其收敛。当这个最后更新的状态跟你上一个状态变化并不大的时候，通常是小于一个阈值 \(\gamma\) ，这个更新就可以停止。
  3. 以上两者的结合方法： 另外我们也可以通过 Temporal-Difference Learning 的那个办法。这个 Temporal-Difference Learning 叫 TD Leanring，就是动态规划和蒙特卡罗的一个结合。

• 马尔可夫奖励过程（MRP）与马尔可夫决策过程 （MDP）的区别？

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

  另外，两者之间是有转换关系的。具体来说，已知一个 MDP 以及一个 policy \(\pi\) 的时候，我们可以把 MDP 转换成MRP。在 MDP 里面，转移函数 \(P(s'|s,a)\) 是基于它当前状态以及它当前的 action，因为我们现在已知它 policy function，就是说在每一个状态，我们知道它可能采取的行为的概率，那么就可以直接把这个 action 进行加和，那我们就可以得到对于 MRP 的一个转移，这里就没有 action。同样地，对于奖励，我们也可以把 action 拿掉，这样就会得到一个类似于 MRP 的奖励。

• MDP 里面的状态转移跟 MRP 以及 MP 的结构或者计算方面的差异？

  答：

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

• 我们如何寻找最佳的policy，方法有哪些？

  答：本质来说，当我们取得最佳的价值函数过后，我们可以通过对这个 Q 函数进行极大化，然后得到最佳的价值。然后，我们直接在这个Q函数上面取一个让这个action最大化的值，然后我们就可以直接提取出它的最佳的policy。

  具体方法：

  1. 穷举法（一般不使用）：假设我们有有限多个状态、有限多个行为可能性，那么每个状态我们可以采取这个 A 种行为的策略，那么总共就是 \(|A|^{|S|}\) 个可能的 policy。我们可以把这个穷举一遍，然后算出每种策略的 value function，然后对比一下可以得到最佳策略。但是效率极低。
  2. Policy iteration： 一种迭代方法，有两部分组成，下面两个步骤一直在迭代进行，最终收敛：(有些类似于ML中EM算法（期望-最大化算法）)
     • 第一个步骤是 policy evaluation ，即当前我们在优化这个 policy \(\pi\) ，所以在优化过程中得到一个最新的这个 policy 。
     • 第二个步骤是 policy improvement ，即取得价值函数后，进一步推算出它的 Q 函数。得到 Q 函数过后，那我们就直接去取它的极大化。
  3. Value iteration: 我们一直去迭代 Bellman Optimality Equation，到了最后，它能逐渐趋向于最佳的策略，这是 value iteration 算法的精髓，就是我们去为了得到最佳的 \(v^*\) ，对于每个状态它的 \(v^*\) 这个值，我们直接把这个 Bellman Optimality Equation 进行迭代，迭代了很多次之后它就会收敛到最佳的policy以及其对应的状态，这里面是没有policy function的。

3 Something About Interview

• 高冷的面试官: 请问马尔可夫过程是什么?马尔可夫决策过程又是什么?其中马尔可夫最重要的性质是什么呢?

  答: 马尔可夫过程是是一个二元组 $ <S,P> $ ,S为状态的集合,P为状态转移概率矩阵; 而马尔可夫决策过程是一个五元组 $ <S,P,A,R,> $,其中 \(R\) 表示为从 \(S\) 到 \(S'\) 能够获得的奖励期望, \(\gamma\)为折扣因子, \(A\) 为动作集合. 马尔可夫最重要的性质是下一个状态只与当前状态有关,与之前的状态无关,也就是 \(P[S_{t+1} | S_t] = P[S_{t+1}|S_1,S_2,...,S_t]\)

• 高冷的面试官: 请问我们一般怎么求解马尔可夫决策过程?

  答: 我们直接求解马尔可夫决策过程可以直接求解贝尔曼等式(动态规划方程),即\(V(s)=R(S)+ \gamma \sum_{s' \in S}P(s'|s)V(s')\) ，特别地，矩阵形式：\(V=R+\gamma PV\).但是贝尔曼等式很难求解且计算复杂度较高,所以可以使用动态规划,蒙特卡洛,时间差分等方法求解.

• 高冷的面试官: 请问如果数据流不满足马尔科夫性怎么办？应该如何处理?

  答: 如果不满足马尔科夫性,即下一个状态与之前的状态也有关，若还仅仅用当前的状态来进行求解决策过程，势必导致决策的泛化能力变差。 为了解决这个问题，可以利用RNN对历史信息建模，获得包含历史信息的状态表征。表征过程可以 使用注意力机制等手段。最后在表征状态空间求解马尔可夫决策过程问题。

• 高冷的面试官: 请分别写出基于状态值函数的贝尔曼方程以及基于动作值的贝尔曼方程.

  答:

  • 基于状态值函数的贝尔曼方程: \(v_{\pi}(s) = \sum_{a}{\pi(a|s)}\sum_{s',r}{p(s',r|s,a)[r(s,a)+\gamma v_{\pi}(s')]}\)
  • 基于动作值的贝尔曼方程: \(q_{\pi}(s,a)=\sum_{s',r}p(s',r|s,a)[r(s',a)+\gamma v_{\pi}(s')]\)

• 高冷的面试官: 请问最佳价值函数(optimal value function) \(v^*\) 和最佳策略(optimal policy) \(\pi^*\) 为什么等价呢？

  答: 最佳价值函数的定义为： \(v^* (s)=\max_{\pi} v^{\pi}(s)\) 即我们去搜索一种 policy \(\pi\) 来让每个状态的价值最大。\(v^*\) 就是到达每一个状态，它的值的极大化情况。在这种极大化情况上面，我们得到的策略就可以说它是最佳策略(optimal policy)，即 $ ^{*}(s)=~ v^{}(s) $. Optimal policy 使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个 optimal value function，就可以说某一个 MDP 的环境被解。在这种情况下，它的最佳的价值函数是一致的，就它达到的这个上限的值是一致的，但这里可能有多个最佳的 policy，就是说多个 policy 可以取得相同的最佳价值。

• 高冷的面试官：能不能手写一下第n步的值函数更新公式呀？另外，当n越来越大时，值函数的期望和方差分别变大还是变小呢？

  答：\(n\)越大，方差越大，期望偏差越小。值函数的更新公式? 话不多说，公式如下： \[ Q\left(S, A\right) \leftarrow Q\left(S, A\right)+\alpha\left[\sum_{i=1}^{n} \gamma^{i-1} R_{t+i}+\gamma^{n} \max _{a} Q\left(S',a\right)-Q\left(S, A\right)\right] \]

MDP

本章给大家介绍马尔可夫决策过程。

• 在介绍马尔可夫决策过程之前，先介绍它的简化版本：马尔可夫链以及马尔可夫奖励过程，通过跟这两种过程的比较，我们可以更容易理解马尔可夫决策过程。
• 第二部分会介绍马尔可夫决策过程中的 policy evaluation，就是当给定一个决策过后，怎么去计算它的价值函数。
• 第三部分会介绍马尔可夫决策过程的控制，具体有两种算法：policy iteration 和 value iteration。

上图介绍了在强化学习里面 agent 跟 environment 之间的交互，agent 在得到环境的状态过后，它会采取动作，它会把这个采取的动作返还给环境。环境在得到 agent 的动作过后，它会进入下一个状态，把下一个状态传回 agent。在强化学习中，agent 跟环境就是这样进行交互的，这个交互过程是可以通过马尔可夫决策过程来表示的，所以马尔可夫决策过程是强化学习里面的一个基本框架。

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

在介绍马尔可夫决策过程(Markov Decision Process，MDP)之前，先给大家梳理一下马尔可夫过程(Markov Process，MP)、马尔可夫奖励过程(Markov Reward Processes，MRP)。这两个过程是马尔可夫决策过程的一个基础。

Markov Process(MP)

Markov Property

如果一个状态转移是符合马尔可夫的，那就是说一个状态的下一个状态只取决于它当前状态，而跟它当前状态之前的状态都没有关系。

我们设状态的历史为 \(h_{t}=\left\{s_{1}, s_{2}, s_{3}, \ldots, s_{t}\right\}\)（\(h_t\) 包含了之前的所有状态），如果一个状态转移是符合马尔可夫的，也就是满足如下条件： \[ p\left(s_{t+1} \mid s_{t}\right) =p\left(s_{t+1} \mid h_{t}\right) \tag{1} \]

\[ p\left(s_{t+1} \mid s_{t}, a_{t}\right) =p\left(s_{t+1} \mid h_{t}, a_{t}\right) \tag{2} \]

从当前 \(s_t\) 转移到 \(s_{t+1}\) 这个状态，它是直接就等于它之前所有的状态转移到 \(s_{t+1}\)。如果某一个过程满足马尔可夫性质(Markov Property)，就是说未来的转移跟过去是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

Markov Process/Markov Chain

首先看一看马尔可夫链(Markov Chain)。举个例子，这个图里面有四个状态，这四个状态从 \(s_1,s_2,s_3,s_4\) 之间互相转移。比如说从 \(s_1\) 开始，

• \(s_1\) 有 0.1 的概率继续存活在 \(s_1\) 状态，
• 有 0.2 的概率转移到 \(s_2\)，
• 有 0.7 的概率转移到 \(s_4\) 。

如果 \(s_4\) 是我们当前状态的话，

• 它有 0.3 的概率转移到 \(s_2\) ，
• 有 0.2 的概率转移到 \(s_3\) ，
• 有 0.5 的概率留在这里。

我们可以用状态转移矩阵(State Transition Matrix) \(P\) 来描述状态转移 \(p\left(s_{t+1}=s^{\prime} \mid s_{t}=s\right)\)，如下式所示。 \[ P=\left[\begin{array}{cccc} P\left(s_{1} \mid s_{1}\right) & P\left(s_{2} \mid s_{1}\right) & \ldots & P\left(s_{N} \mid s_{1}\right) \\ P\left(s_{1} \mid s_{2}\right) & P\left(s_{2} \mid s_{2}\right) & \ldots & P\left(s_{N} \mid s_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ P\left(s_{1} \mid s_{N}\right) & P\left(s_{2} \mid s_{N}\right) & \ldots & P\left(s_{N} \mid s_{N}\right) \end{array}\right] \] 状态转移矩阵类似于一个 conditional probability，当我们知道当前我们在 \(s_t\) 这个状态过后，到达下面所有状态的一个概念。所以它每一行其实描述了是从一个节点到达所有其它节点的概率。

Example of MP

上图是一个马尔可夫链的例子，我们这里有七个状态。比如说从 \(s_1\) 开始到 \(s_2\) ，它有 0.4 的概率，然后它有 0.6 的概率继续存活在它当前的状态。 \(s_2\) 有 0.4 的概率到左边，有 0.4 的概率到 \(s_3\) ，另外有 0.2 的概率存活在现在的状态，所以给定了这个状态转移的马尔可夫链后，我们可以对这个链进行采样，这样就会得到一串的轨迹。

下面我们有三个轨迹，都是从同一个起始点开始。假设还是从 \(s_3\) 这个状态开始，

• 第一条链先到了 \(s_4\)， 又到了 \(s_5\)，又往右到了 \(s_6\) ，然后继续存活在 \(s_6\) 状态。
• 第二条链从 \(s_3\) 开始，先往左走到了 \(s_2\) 。然后它又往右走，又回到了\(s_3\) ，然后它又往左走，然后再往左走到了 \(s_1\) 。
• 通过对这个状态的采样，我们生成了很多这样的轨迹。

Markov Reward Process(MRP)

马尔可夫奖励过程(Markov Reward Process, MRP) 是马尔可夫链再加上了一个奖励函数。在 MRP 中，转移矩阵和状态都是跟马尔可夫链一样的，多了一个奖励函数(reward function)。奖励函数 \(R\) 是一个期望，就是说当你到达某一个状态的时候，可以获得多大的奖励，然后这里另外定义了一个 discount factor \(\gamma\) 。如果状态数是有限的，\(R\) 可以是一个向量。

Example of MRP

这里是我们刚才看的马尔可夫链，如果把奖励也放上去的话，就是说到达每一个状态，我们都会获得一个奖励。这里我们可以设置对应的奖励，比如说到达 \(s_1\) 状态的时候，可以获得 5 的奖励，到达 \(s_7\) 的时候，可以得到 10 的奖励，其它状态没有任何奖励。因为这里状态是有限的，所以我们可以用向量 \(R=[5,0,0,0,0,0,10]\) 来表示这个奖励函数，这个向量表示了每个点的奖励大小。

我们通过一个形象的例子来理解 MRP。我们把一个纸船放到河流之中，那么它就会随着这个河流而流动，它自身是没有动力的。所以你可以把 MRP 看成是一个随波逐流的例子，当我们从某一个点开始的时候，这个纸船就会随着事先定义好的状态转移进行流动，它到达每个状态过后，我们就有可能获得一些奖励。

Return and Value function

这里我们进一步定义一些概念。

• Horizon 是指一个回合的长度（每个回合最大的时间步数），它是由有限个步数决定的。

• Return(回报) 说的是把奖励进行折扣后所获得的收益。Return 可以定义为奖励的逐步叠加，如下式所示：

\[ G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} R_{t+4}+\ldots+\gamma^{T-t-1} R_{T} \]

这里有一个叠加系数，越往后得到的奖励，折扣得越多。这说明我们其实更希望得到现有的奖励，未来的奖励就要把它打折扣。

• 当我们有了 return 过后，就可以定义一个状态的价值了，就是 state value function。对于 MRP，state value function 被定义成是 return 的期望，如下式所示： \[ \begin{aligned} V_{t}(s) &=\mathbb{E}\left[G_{t} \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots+\gamma^{T-t-1} R_{T} \mid s_{t}=s\right] \end{aligned} \]

\(G_t\) 是之前定义的 discounted return，我们这里取了一个期望，期望就是说从这个状态开始，你有可能获得多大的价值。所以这个期望也可以看成是对未来可能获得奖励的当前价值的一个表现，就是当你进入某一个状态过后，你现在就有多大的价值。

Why Discount Factor

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

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

Discount factor 可以作为强化学习 agent 的一个超参数来进行调整，然后就会得到不同行为的 agent。

这里我们再来看一看，在这个 MRP 里面，如何计算它的价值。这个 MRP 依旧是这个状态转移。它的奖励函数是定义成这样，它在进入第一个状态的时候会得到 5 的奖励，进入第七个状态的时候会得到 10 的奖励，其它状态都没有奖励。

我们现在可以计算每一个轨迹得到的奖励，比如我们对于这个 \(s_4,s_5,s_6,s_7\) 轨迹的奖励进行计算，这里折扣系数是 0.5。

• 在 \(s_4\) 的时候，奖励为零。

• 下一个状态 \(s_5\) 的时候，因为我们已经到了下一步了，所以我们要把 \(s_5\) 进行一个折扣，\(s_5\) 本身也是没有奖励的。

• 然后是到 \(s_6\)，也没有任何奖励，折扣系数应该是 \(\frac{1}{4}\) 。

• 到达 \(s_7\) 后，我们获得了一个奖励，但是因为 \(s_7\) 这个状态是未来才获得的奖励，所以我们要进行三次折扣。

所以对于这个轨迹，它的 return 就是一个 1.25，类似地，我们可以得到其它轨迹的 return 。

这里就引出了一个问题，当我们有了一些轨迹的实际 return，怎么计算它的价值函数。比如说我们想知道 \(s_4\) 状态的价值，就是当你进入 \(s_4\) 后，它的价值到底如何。一个可行的做法就是说我们可以产生很多轨迹，然后把这里的轨迹都叠加起来。比如我们可以从 \(s_4\) 开始，采样生成很多轨迹，都把它的 return 计算出来，然后可以直接把它取一个平均作为你进入 \(s_4\) 它的价值。这其实是一种计算价值函数的办法，通过这个蒙特卡罗采样的办法计算 \(s_4\) 的状态。接下来会进一步介绍蒙特卡罗算法。

Bellman Equation

但是这里我们采取了另外一种计算方法，我们从这个价值函数里面推导出 Bellman Equation（贝尔曼等式），如下式所示： \[ V(s)=\underbrace{R(s)}_{\text {Immediate reward }}+\underbrace{\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right)}_{\text {Discounted sum of future reward }} \] 其中：

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

Bellman Equation 定义了当前状态跟未来状态之间的这个关系。

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

Law of Total Expectation

在推导 Bellman equation 之前，我们可以仿照Law of Total Expectation(全期望公式)的证明过程来证明下面的式子： \[ \mathbb{E}[V(s_{t+1})|s_t]=\mathbb{E}[\mathbb{E}[G_{t+1}|s_{t+1}]|s_t]=E[G_{t+1}|s_t] \]

Law of total expectation 也被称为 law of iterated expectations(LIE)。如果 \(A_i\) 是样本空间的有限或可数的划分(partition)，则全期望公式可以写成如下形式： \[ \mathrm{E}(X)=\sum_{i} \mathrm{E}\left(X \mid A_{i}\right) \mathrm{P}\left(A_{i}\right) \]

证明：

为了记号简洁并且易读，我们丢掉了下标，令 \(s=s_t,g'=G_{t+1},s'=s_{t+1}\)。我们可以根据条件期望的定义来重写这个回报的期望为： \[ \begin{aligned} \mathbb{E}\left[G_{t+1} \mid s_{t+1}\right] &=\mathbb{E}\left[g^{\prime} \mid s^{\prime}\right] \\ &=\sum_{g^{\prime}} g^{\prime}~p\left(g^{\prime} \mid s^{\prime}\right) \end{aligned} \] > 如果 \(X\) 和 \(Y\) 都是离散型随机变量，则条件期望（Conditional Expectation）\(E(X|Y=y)\)的定义如下式所示： > \[ > \mathrm{E}(X \mid Y=y)=\sum_{x} x P(X=x \mid Y=y) > \]

令 \(s_t=s\)，我们对 \(\mathbb{E}\left[G_{t+1} \mid s_{t+1}\right]\) 求期望可得： \[ \begin{aligned} \mathbb{E}\left[\mathbb{E}\left[G_{t+1} \mid s_{t+1}\right] \mid s_{t}\right] &=\mathbb{E} \left[\mathbb{E}\left[g^{\prime} \mid s^{\prime}\right] \mid s\right]\\ &=\mathbb{E} \left[\sum_{g^{\prime}} g^{\prime}~p\left(g^{\prime} \mid s^{\prime}\right)\mid s\right]\\ &= \sum_{s^{\prime}}\sum_{g^{\prime}} g^{\prime}~p\left(g^{\prime} \mid s^{\prime},s\right)p(s^{\prime} \mid s)\\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} \frac{g^{\prime} p\left(g^{\prime} \mid s^{\prime}, s\right) p\left(s^{\prime} \mid s\right) p(s)}{p(s)} \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} \frac{g^{\prime} p\left(g^{\prime} \mid s^{\prime}, s\right) p\left(s^{\prime}, s\right)}{p(s)} \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} \frac{g^{\prime} p\left(g^{\prime}, s^{\prime}, s\right)}{p(s)} \\ &=\sum_{s^{\prime}} \sum_{g^{\prime}} g^{\prime} p\left(g^{\prime}, s^{\prime} \mid s\right) \\ &=\sum_{g^{\prime}} \sum_{s^{\prime}} g^{\prime} p\left(g^{\prime}, s^{\prime} \mid s\right) \\ &=\sum_{g^{\prime}} g^{\prime} p\left(g^{\prime} \mid s\right) \\ &=\mathbb{E}\left[g^{\prime} \mid s\right]=\mathbb{E}\left[G_{t+1} \mid s_{t}\right] \end{aligned} \]

Bellman Equation Derivation

Bellman equation 的推导过程如下： \[ \begin{aligned} V(s)&=\mathbb{E}\left[G_{t} \mid s_{t}=s\right]\\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}|s_t=s\right] +\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\ldots \mid s_{t}=s\right]\\ &=R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s] \\ &=R(s)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s]\\ &=R(s)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right) \end{aligned} \]

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

Bellman Equation 定义了状态之间的迭代关系，如下式所示。 \[ V(s)=R(s)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right) \]

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

我们可以把 Bellman Equation 写成一种矩阵的形式，如下式所示。 \[ \left[\begin{array}{c} V\left(s_{1}\right) \\ V\left(s_{2}\right) \\ \vdots \\ V\left(s_{N}\right) \end{array}\right]=\left[\begin{array}{c} R\left(s_{1}\right) \\ R\left(s_{2}\right) \\ \vdots \\ R\left(s_{N}\right) \end{array}\right]+\gamma\left[\begin{array}{cccc} P\left(s_{1} \mid s_{1}\right) & P\left(s_{2} \mid s_{1}\right) & \ldots & P\left(s_{N} \mid s_{1}\right) \\ P\left(s_{1} \mid s_{2}\right) & P\left(s_{2} \mid s_{2}\right) & \ldots & P\left(s_{N} \mid s_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ P\left(s_{1} \mid s_{N}\right) & P\left(s_{2} \mid s_{N}\right) & \ldots & P\left(s_{N} \mid s_{N}\right) \end{array}\right]\left[\begin{array}{c} V\left(s_{1}\right) \\ V\left(s_{2}\right) \\ \vdots \\ V\left(s_{N}\right) \end{array}\right] \] 首先有这个转移矩阵。我们当前这个状态是一个向量 \([V(s_1),V(s_2),\cdots,V(s_N)]^T\)。我们可以写成迭代的形式。我们每一行来看的话，\(V\) 这个向量乘以了转移矩阵里面的某一行，再加上它当前可以得到的 reward，就会得到它当前的价值。

当我们把 Bellman Equation 写成矩阵形式后，可以直接求解： \[ \begin{aligned} V &= R+ \gamma PV \\ IV &= R+ \gamma PV \\ (I-\gamma P)V &=R \\ V&=(I-\gamma P)^{-1}R \end{aligned} \]

我们可以直接得到一个解析解(analytic solution): \[ V=(I-\gamma P)^{-1} R \] 我们可以通过矩阵求逆把这个 V 的这个价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 \(O(N^3)\)。所以当状态非常多的时候，比如说从十个状态到一千个状态，到一百万个状态。那么当我们有一百万个状态的时候，这个转移矩阵就会是个一百万乘以一百万的矩阵，这样一个大矩阵的话求逆是非常困难的，所以这种通过解析解去求解的方法只适用于很小量的 MRP。

Iterative Algorithm for Computing Value of a MRP

接下来我们来求解这个价值函数。我们可以通过迭代的方法来解这种状态非常多的 MRP(large MRPs)，比如说：

• 动态规划的方法，
• 蒙特卡罗的办法(通过采样的办法去计算它)，
• 时序差分学习(Temporal-Difference Learning)的办法。 Temporal-Difference Learning 叫 TD Leanring，它是动态规划和蒙特卡罗的一个结合。

首先我们用蒙特卡罗(Monte Carlo)的办法来计算它的价值函数。蒙特卡罗就是说当得到一个 MRP 过后，我们可以从某一个状态开始，把这个小船放进去，让它随波逐流，这样就会产生一个轨迹。产生了一个轨迹过后，就会得到一个奖励，那么就直接把它的折扣的奖励 \(g\) 算出来。算出来过后就可以把它积累起来，得到 return \(G_t\)。 当积累到一定的轨迹数量过后，直接用 \(G_t\) 除以轨迹数量，就会得到它的价值。

比如说我们要算 \(s_4\) 状态的价值。

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

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

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

Bootstrap 本意是“解靴带”；这里是在使用徳国文学作品《吹牛大王历险记》中解靴带自助(拔靴自助)的典故，因此将其译为“自举”。

Markov Decision Process(MDP)

MDP

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

• 这里多了一个决策，多了一个动作。
• 状态转移也多了一个条件，变成了 \(P\left(s_{t+1}=s^{\prime} \mid s_{t}=s, a_{t}=a\right)\)。你采取某一种动作，然后你未来的状态会不同。未来的状态不仅是依赖于你当前的状态，也依赖于在当前状态 agent 采取的这个动作。
• 对于这个价值函数，它也是多了一个条件，多了一个你当前的这个动作，变成了 \(R\left(s_{t}=s, a_{t}=a\right)=\mathbb{E}\left[r_{t} \mid s_{t}=s, a_{t}=a\right]\)。你当前的状态以及你采取的动作会决定你在当前可能得到的奖励多少。

Policy in MDP

• Policy 定义了在某一个状态应该采取什么样的动作。

• 知道当前状态过后，我们可以把当前状态带入 policy function，然后就会得到一个概率，即 \[ \pi(a \mid s)=P\left(a_{t}=a \mid s_{t}=s\right) \]

概率就代表了在所有可能的动作里面怎样采取行动，比如可能有 0.7 的概率往左走，有 0.3 的概率往右走，这是一个概率的表示。

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

• 假设这个概率函数应该是稳定的(stationary)，不同时间点，你采取的动作其实都是对这个 policy function 进行采样。

我们可以将 MRP 转换成 MDP。已知一个 MDP 和一个 policy \(\pi\) 的时候，我们可以把 MDP 转换成 MRP。

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

\[ P^{\pi}\left(s^{\prime} \mid s\right)=\sum_{a \in A} \pi(a \mid s) P\left(s^{\prime} \mid s, a\right) \]

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

\[ R^{\pi}(s)=\sum_{a \in A} \pi(a \mid s) R(s, a) \]

Comparison of MP/MRP and MDP

这里我们看一看，MDP 里面的状态转移跟 MRP 以及 MP 的一个差异。

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

Value function for MDP

顺着 MDP 的定义，我们可以把 状态-价值函数(state-value function)，就是在 MDP 里面的价值函数也进行一个定义，它的定义是跟 MRP 是类似的，如式 (3) 所示： \[ v^{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} \mid s_{t}=s\right] \tag{3} \] 但是这里 expectation over policy，就是这个期望是基于你采取的这个 policy ，就当你的 policy 决定过后，我们通过对这个 policy 进行采样来得到一个期望，那么就可以计算出它的这个价值函数。

这里我们另外引入了一个 Q 函数(Q-function)。Q 函数也被称为 action-value function。Q 函数定义的是在某一个状态采取某一个动作，它有可能得到的这个 return 的一个期望，如式 (4) 所示： \[ q^{\pi}(s, a)=\mathbb{E}_{\pi}\left[G_{t} \mid s_{t}=s, A_{t}=a\right] \tag{4} \] 这里期望其实也是 over policy function。所以你需要对这个 policy function 进行一个加和，然后得到它的这个价值。 对 Q 函数中的动作函数进行加和，就可以得到价值函数，如式 (5) 所示： \[ v^{\pi}(s)=\sum_{a \in A} \pi(a \mid s) q^{\pi}(s, a) \tag{5} \] #### Q-function Bellman Equation

此处我们给出 Q 函数的 Bellman equation：

\[ \begin{aligned} q(s,a)&=\mathbb{E}\left[G_{t} \mid s_{t}=s,a_{t}=a\right]\\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid s_{t}=s,a_{t}=a\right] \\ &=\mathbb{E}\left[R_{t+1}|s_{t}=s,a_{t}=a\right] +\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\ldots \mid s_{t}=s,a_{t}=a\right]\\ &=R(s,a)+\gamma \mathbb{E}[G_{t+1}|s_{t}=s,a_{t}=a] \\ &=R(s,a)+\gamma \mathbb{E}[V(s_{t+1})|s_{t}=s,a_{t}=a]\\ &=R(s,a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s,a\right) V\left(s^{\prime}\right) \end{aligned} \]

Bellman Expectation Equation

我们可以把状态-价值函数和 Q 函数拆解成两个部分：即时奖励(immediate reward) 和后续状态的折扣价值(discounted value of successor state)。

通过对状态-价值函数进行一个分解，我们就可以得到一个类似于之前 MRP 的 Bellman Equation，这里叫 Bellman Expectation Equation，如式 (6) 所示： \[ v^{\pi}(s)=E_{\pi}\left[R_{t+1}+\gamma v^{\pi}\left(s_{t+1}\right) \mid s_{t}=s\right] \tag{6} \] 对于 Q 函数，我们也可以做类似的分解，也可以得到 Q 函数的 Bellman Expectation Equation，如式 (7) 所示： \[ q^{\pi}(s, a)=E_{\pi}\left[R_{t+1}+\gamma q^{\pi}\left(s_{t+1}, A_{t+1}\right) \mid s_{t}=s, A_{t}=a\right] \tag{7} \] Bellman expectation equation 定义了你当前状态跟未来状态之间的一个关联。

我们进一步进行一个简单的分解。

我们先给出等式 (8)： \[ v^{\pi}(s)=\sum_{a \in A} \pi(a \mid s) q^{\pi}(s, a) \tag{8} \] 再给出等式 (9)： \[ q^{\pi}(s, a)=R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{\pi}\left(s^{\prime}\right) \tag{9} \] 等式 (8) 和等式 (9) 代表了价值函数跟 Q 函数之间的一个关联。

也可以把等式 (9) 插入等式 (8) 中，得到等式 (10)： \[ v^{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{\pi}\left(s^{\prime}\right)\right) \tag{10} \] 等式 (10) 代表了当前状态的价值跟未来状态价值之间的一个关联。

我们把等式 (8) 插入到等式 (9)，就可以得到等式 (11)： \[ q^{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) \sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) q^{\pi}\left(s^{\prime}, a^{\prime}\right) \tag{11} \] 等式 (11) 代表了当前时刻的 Q 函数跟未来时刻的 Q 函数之间的一个关联。

等式 (10) 和等式 (11) 是 Bellman expectation equation 的另一种形式。

Backup Diagram

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

我们把上面这样的图称为 backup diagram(备份图)，因为它们图示的关系构成了更新或备份操作的基础，而这些操作是强化学习方法的核心。这些操作将价值信息从一个状态（或状态-动作对）的后继状态（或状态-动作对）转移回它。

每一个空心圆圈代表一个状态，每一个实心圆圈代表一个状态-动作对。

\[ v^{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{\pi}\left(s^{\prime}\right)\right) \tag{12} \] 如式 (12) 所示，我们这里有两层加和：

• 第一层加和就是这个叶子节点，往上走一层的话，我们就可以把未来的价值(\(s'\) 的价值) backup 到黑色的节点。
• 第二层加和是对 action 进行加和。得到黑色节点的价值过后，再往上 backup 一层，就会推到根节点的价值，即当前状态的价值。

上图是状态-价值函数的计算分解图，上图 B 计算公式为 \[ v^{\pi}(s)=\sum_{a \in A} \pi(a \mid s) q^{\pi}(s, a) \tag{i} \] 上图 B 给出了状态-价值函数与 Q 函数之间的关系。上图 C 计算 Q 函数为 \[ q^{\pi}(s,a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{\pi}\left(s^{\prime}\right) \tag{ii} \]

将式 (ii) 代入式 (i) 可得： \[ v^{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{\pi}\left(s^{\prime}\right)\right) \] 所以 backup diagram 定义了未来下一时刻的状态-价值函数跟上一时刻的状态-价值函数之间的关联。

对于 Q 函数，我们也可以进行这样的一个推导。现在的根节点是这个 Q 函数的一个节点。Q 函数对应于黑色的节点。我们下一时刻的 Q 函数是叶子节点，有四个黑色节点。 \[ q^{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) \sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) q^{\pi}\left(s^{\prime}, a^{\prime}\right) \tag{13} \] 如式 (13) 所示，我们这里也有两个加和：

• 第一层加和是先把这个叶子节点从黑色节点推到这个白色的节点，进了它的这个状态。
• 当我们到达某一个状态过后，再对这个白色节点进行一个加和，这样就把它重新推回到当前时刻的一个 Q 函数。

在上图 C 中， \[ v^{\pi}\left(s^{\prime}\right)=\sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) q^{\pi}\left(s^{\prime}, a^{\prime}\right) \tag{iii} \] 将式 (iii) 代入式 (ii) 可得到 Q 函数： \[ q^{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) \sum_{a^{\prime} \in A} \pi\left(a^{\prime} \mid s^{\prime}\right) q^{\pi}\left(s^{\prime}, a^{\prime}\right) \] 所以这个等式就决定了未来 Q 函数跟当前 Q 函数之间的这个关联。

Policy Evaluation(Prediction)

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

• MDP，你其实可以把它想象成一个摆渡的人在这个船上面，她可以控制这个船的移动，这样就避免了这个船随波逐流。因为在每一个时刻，这个人会决定采取什么样的一个动作，这样会把这个船进行导向。

• MRP 跟 MP 的话，这个纸的小船会随波逐流，然后产生轨迹。

• MDP 的不同就是有一个 agent 去控制这个船，这样我们就可以尽可能多地获得奖励。

我们再看下 policy evaluation 的例子，怎么在决策过程里面计算它每一个状态的价值。

• 假设环境里面有两种动作：往左走和往右走。
• 现在的奖励函数有两个变量：动作和状态。但我们这里规定，不管你采取什么动作，只要到达状态 \(s_1\)，就有 5 的奖励。只要你到达状态 \(s_7\) 了，就有 10 的奖励，中间没有任何奖励。
• 假设我们现在采取的一个策略，这个策略是说不管在任何状态，我们采取的策略都是往左走。假设价值折扣因子是零，那么对于确定性策略(deterministic policy)，最后估算出的价值函数是一致的，即

\[ V^{\pi}=[5,0,0,0,0,0,10] \]

Q: 怎么得到这个结果？

A: 我们可以直接在去 run 下面这个 iterative equation： \[ v_{k}^{\pi}(s)=r(s, \pi(s))+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, \pi(s)\right) v_{k-1}^{\pi}\left(s^{\prime}\right) \] 就把 Bellman expectation equation 拿到这边来，然后不停地迭代，最后它会收敛。收敛过后，它的值就是它每一个状态的价值。

再来看一个例子(practice 1)，如果折扣因子是 0.5，我们可以通过下面这个等式进行迭代： \[ v_{t}^{\pi}(s)=\sum_{a} P(\pi(s)=a)\left(r(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v_{t-1}^{\pi}\left(s^{\prime}\right)\right) \] 然后就会得到它的状态价值。

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

Prediction and Control

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

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

举一个例子来说明 prediction 与 control 的区别。

首先是预测问题：

• 在上图的方格中，我们规定从 A \(\to\) A' 可以得到 +10 的奖励，从 B \(\to\) B' 可以得到 +5 的奖励，其它步骤的奖励为 -1。
• 现在，我们给定一个 policy：在任何状态中，它的行为模式都是随机的，也就是上下左右的概率各 25%。
• 预测问题要做的就是，在这种决策模式下，我们的 value function 是什么。上图 b 是对应的 value function。

接着是控制问题：

• 在控制问题中，问题背景与预测问题相同，唯一的区别就是：不再限制 policy。也就是说行为模式是未知的，我们要自己确定。

• 所以我们通过解决控制问题，求得每一个状态的最优的 value function（如上图 b 所示），也得到了最优的 policy（如上图 c 所示）。

• 控制问题要做的就是，给定同样的条件，在所有可能的策略下最优的价值函数是什么？最优策略是什么？

Dynamic Programming

动态规划(Dynamic Programming，DP)适合解决满足如下两个性质的问题：

• 最优子结构(optimal substructure)。最优子结构意味着，我们的问题可以拆分成一个个的小问题，通过解决这个小问题，最后，我们能够通过组合小问题的答案，得到大问题的答案，即最优的解。
• 重叠子问题(Overlapping subproblems)。重叠子问题意味着，子问题出现多次，并且子问题的解决方案能够被重复使用。

MDP 是满足动态规划的要求的，

• 在 Bellman equation 里面，我们可以把它分解成一个递归的结构。当我们把它分解成一个递归的结构的时候，如果我们的子问题子状态能得到一个值，那么它的未来状态因为跟子状态是直接相连的，那我们也可以继续推算出来。
• 价值函数就可以储存并重用它的最佳的解。

动态规划应用于 MDP 的规划问题(planning)而不是学习问题(learning)，我们必须对环境是完全已知的(Model-Based)，才能做动态规划，直观的说，就是要知道状态转移概率和对应的奖励才行

动态规划能够完成预测问题和控制问题的求解，是解 MDP prediction 和 control 一个非常有效的方式。

Policy Evaluation on MDP

Policy evaluation 就是给定一个 MDP 和一个 policy，我们可以获得多少的价值。就对于当前这个策略，我们可以得到多大的 value function。

这里有一个方法是说，我们直接把这个 Bellman Expectation Backup 拿过来，变成一个迭代的过程，这样反复迭代直到收敛。这个迭代过程可以看作是 synchronous backup 的过程。

同步备份(synchronous backup)是指每一次的迭代都会完全更新所有的状态，这样对于程序资源需求特别大。异步备份(asynchronous backup)的思想就是通过某种方式，使得每一次迭代不需要更新所有的状态，因为事实上，很多的状态也不需要被更新。

\[ v_{t+1}(s)=\sum_{a \in \mathcal{A}} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right) v_{t}\left(s^{\prime}\right)\right) \tag{14} \] * 等式 (14) 说的是说我们可以把 Bellman Expectation Backup 转换成一个动态规划的迭代。 * 当我们得到上一时刻的 \(v_t\) 的时候，就可以通过这个递推的关系来推出下一时刻的值。 * 反复去迭代它，最后它的值就是从 \(v_1,v_2\) 到最后收敛过后的这个值。这个值就是当前给定的 policy 对应的价值函数。

Policy evaluation 的核心思想就是把如下式所示的 Bellman expectation backup 拿出来反复迭代，然后就会得到一个收敛的价值函数的值。 \[ v_{t+1}(s)=\sum_{a \in \mathcal{A}} \pi(a \mid s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right) v_{t}\left(s^{\prime}\right)\right) \tag{15} \] 因为已经给定了这个函数的 policy function，那我们可以直接把它简化成一个 MRP 的表达形式，这样的话，形式就更简洁一些，就相当于我们把这个 \(a\) 去掉，如下式所示： \[ v_{t+1}(s)=R^{\pi}(s)+\gamma P^{\pi}\left(s^{\prime} \mid s\right) v_{t}\left(s^{\prime}\right) \tag{16} \] 这样它就只有价值函数跟转移函数了。通过去迭代这个更简化的一个函数，我们也可以得到它每个状态的价值。因为不管是在 MRP 以及 MDP，它的价值函数包含的这个变量都是只跟这个状态有关，就相当于进入某一个状态，未来可能得到多大的价值。

• 比如现在的环境是一个 small gridworld。这个 agent 的目的是从某一个状态开始，然后到达终点状态。它的终止状态就是左上角跟右下角，这里总共有 14 个状态，因为我们把每个位置用一个状态来表示。

• 这个 agent 采取的动作，它的 policy function 就直接先给定了，它在每一个状态都是随机游走，它们在每一个状态就是上下左右行走。它在边缘状态的时候，比如说在第四号状态的时候，它往左走的话，它是依然存在第四号状态，我们加了这个限制。

• 这里我们给的奖励函数就是说你每走一步，就会得到 -1 的奖励，所以 agent 需要尽快地到达终止状态。

• 状态之间的转移也是确定的。比如从第六号状态往上走，它就会直接到达第二号状态。很多时候有些环境是 概率性的(probabilistic)， 就是说 agent 在第六号状态，它选择往上走的时候，有可能地板是滑的，然后它可能滑到第三号状态或者第一号状态，这就是有概率的一个转移。但这里把这个环境进行了简化，从六号往上走，它就到了二号。

• 所以直接用这个迭代来解它，因为我们已经知道每一个概率以及它的这个概率转移，那么就直接可以进行一个简短的迭代，这样就会算出它每一个状态的价值。

我们再来看一个动态的例子，首先推荐斯坦福大学的一个网站：GridWorld: Dynamic Programming Demo ，这个网站模拟了单步更新的过程中，所有格子的一个状态价值的变化过程。

这里有很多格子，每个格子都代表了一个状态。在每个格子里面有一个初始值零。然后在每一个状态，它还有一些箭头，这个箭头就是说它在当前这个状态应该采取什么样的策略。我们这里采取一个随机的策略，不管它在哪一个状态，它上下左右的概率都是相同的。比如在某个状态，它都有上下左右 0.25 的概率采取某一个动作，所以它的动作是完全随机的。

在这样的环境里面，我们想计算它每一个状态的价值。我们也定义了它的 reward function，你可以看到有些状态上面有一个 R 的值。比如我们这边有些值是为负的，我们可以看到格子里面有几个 -1 的奖励，只有一个 +1 奖励的格子。在这个棋盘的中间这个位置，可以看到有一个 R 的值是 1.0，为正的一个价值函数。 所以每个状态对应了一个值，然后有一些状态没有任何值，就说明它的这个 reward function，它的奖励是为零的。

我们开始做这个 policy evaluation，policy evaluation 是一个不停迭代的过程。当我们初始化的时候，所有的 \(v(s)\) 都是 0。我们现在迭代一次，迭代一次过后，你发现有些状态上面，值已经产生了变化。比如有些状态的值的 R 为 -1，迭代一次过后，它就会得到 -1 的这个奖励。对于中间这个绿色的，因为它的奖励为正，所以它是 +1 的状态。

所以当迭代第一次的时候，\(v(s)\) 某些状态已经有些值的变化。

• 我们再迭代一次(one sweep)，然后发现它就从周围的状态也开始有值。因为周围状态跟之前有值的状态是临近的，所以它就相当于把旁边这个状态转移过来。所以当我们逐渐迭代的话，你会发现这个值一直在变换。

• 等迭代了很多次过后，很远的这些状态的价值函数已经有些值了，而且你可以发现它这里整个过程呈现逐渐扩散开的一个过程，这其实也是 policy evaluation 的一个可视化。

• 当我们每一步在进行迭代的时候，远的状态就会得到了一些值，就逐渐从一些已经有奖励的这些状态，逐渐扩散，当你 run 很多次过后，它就逐渐稳定下来，最后值就会确定不变，这样收敛过后，每个状态上面的值就是它目前得到的这个 value function 的值。

MDP Control

Policy evaluation 是说给定一个 MDP 和一个 policy，我们可以估算出它的价值函数。还有问题是说如果我们只有一个 MDP，如何去寻找一个最佳的策略，然后可以得到一个最佳价值函数(Optimal Value Function)。

Optimal Value Function 的定义如下式所示： \[ v^{*}(s)=\max _{\pi} v^{\pi}(s) \] Optimal Value Function 是说，我们去搜索一种 policy \(\pi\) 来让每个状态的价值最大。\(v^*\) 就是到达每一个状态，它的值的极大化情况。

在这种极大化情况上面，我们得到的策略就可以说它是最佳策略(optimal policy)，如下式所示： \[ \pi^{*}(s)=\underset{\pi}{\arg \max }~ v^{\pi}(s) \] Optimal policy 使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个 optimal value function，就可以说某一个 MDP 的环境被解。在这种情况下，它的最佳的价值函数是一致的，就它达到的这个上限的值是一致的，但这里可能有多个最佳的 policy，就是说多个 policy 可以取得相同的最佳价值。

Q: 怎么去寻找这个最佳的 policy ？

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

最简单的策略搜索办法就是穷举。假设状态和动作都是有限的，那么每个状态我们可以采取这个 A 种动作的策略，那么总共就是 \(|A|^{|S|}\) 个可能的 policy。那我们可以把策略都穷举一遍，然后算出每种策略的 value function，对比一下就可以得到最佳策略。

但是穷举非常没有效率，所以我们要采取其他方法。搜索最佳策略有两种常用的方法：policy iteration 和 value iteration。

寻找这个最佳策略的过程就是 MDP control 过程。MDP control 说的就是怎么去寻找一个最佳的策略来让我们得到一个最大的价值函数，如下式所示： \[ \pi^{*}(s)=\underset{\pi}{\arg \max } ~ v^{\pi}(s) \] 对于一个事先定好的 MDP 过程，当 agent 去采取最佳策略的时候，我们可以说最佳策略一般都是确定的，而且是稳定的(它不会随着时间的变化)。但是不一定是唯一的，多种动作可能会取得相同的这个价值。

我们可以通过 policy iteration 和 value iteration 来解 MDP 的控制问题。

Policy Iteration

Policy iteration 由两个步骤组成：policy evaluation 和 policy improvement。

• 第一个步骤是 policy evaluation，当前我们在优化这个 policy \(\pi\)，在优化过程中得到一个最新的 policy。我们先保证这个 policy 不变，然后去估计它出来的这个价值。给定当前的 policy function 来估计这个 v 函数。
• 第二个步骤是 policy improvement，得到 v 函数过后，我们可以进一步推算出它的 Q 函数。得到 Q 函数过后，我们直接在 Q 函数上面取极大化，通过在这个 Q 函数上面做一个贪心的搜索来进一步改进它的策略。
• 这两个步骤就一直是在迭代进行，所以在 policy iteration 里面，在初始化的时候，我们有一个初始化的 \(V\) 和 \(\pi\) ，然后就是在这两个过程之间迭代。
• 左边这幅图上面的线就是我们当前 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 算出来，如下式所示： \[ q^{\pi_{i}}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{\pi_{i}}\left(s^{\prime}\right) \] 对于每一个状态，第二个步骤会得到它的新一轮的这个 policy ，就在每一个状态，我们去取使它得到最大值的 action，如下式所示： \[ \pi_{i+1}(s)=\underset{a}{\arg \max } ~q^{\pi_{i}}(s, a) \] 你可以把 Q 函数看成一个 Q-table:

• 横轴是它的所有状态，
• 纵轴是它的可能的 action。

得到 Q 函数后，Q-table也就得到了。

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

Bellman Optimality Equation

当一直在采取 arg max 操作的时候，我们会得到一个单调的递增。通过采取这种 greedy，即 arg max 操作，我们就会得到更好的或者不变的 policy，而不会使它这个价值函数变差。所以当这个改进停止过后，我们就会得到一个最佳策略。

当改进停止过后，我们取它最大化的这个 action，它直接就会变成它的价值函数，如下式所示： \[ q^{\pi}\left(s, \pi^{\prime}(s)\right)=\max _{a \in \mathcal{A}} q^{\pi}(s, a)=q^{\pi}(s, \pi(s))=v^{\pi}(s) \] 所以我们有了一个新的等式： \[ v^{\pi}(s)=\max _{a \in \mathcal{A}} q^{\pi}(s, a) \] 上式被称为 Bellman optimality equation。从直觉上讲，Bellman optimality equation 表达了这样一个事实：最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。

当 MDP 满足 Bellman optimality equation 的时候，整个 MDP 已经到达最佳的状态。它到达最佳状态过后，对于这个 Q 函数，取它最大的 action 的那个值，就是直接等于它的最佳的 value function。只有当整个状态已经收敛过后，得到一个最佳的 policy 的时候，这个条件才是满足的。

最佳的价值函数到达过后，这个 Bellman optimlity equation 就会满足。

满足过后，就有这个 max 操作，如第一个等式所示： \[ v^{*}(s)=\max _{a} q^{*}(s, a) \] 当我们取最大的这个 action 的时候对应的值就是当前状态的最佳的价值函数。

另外，我们给出第二个等式，即 Q 函数的 Bellman equation： \[ q^{*}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{*}\left(s^{\prime}\right) \] 我们可以把第一个等式插入到第二个等式里面去，如下式所示： \[ \begin{aligned} q^{*}(s, a)&=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{*}\left(s^{\prime}\right) \\ &=R(s,a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) \max _{a} q^{*}(s', a') \end{aligned} \] 我们就会得到 Q 函数之间的转移。它下一步这个状态，取了 max 这个值过后，就会跟它最佳的这个状态等价。

Q-learning 是基于 Bellman Optimality Equation 来进行的，当取它最大的这个状态的时候（ \(\underset{a'}{\max} q^{*}\left(s^{\prime}, a^{\prime}\right)\) ），它会满足下面这个等式： \[ q^{*}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) \max _{a^{\prime}} q^{*}\left(s^{\prime}, a^{\prime}\right) \]

我们还可以把第二个等式插入到第一个等式，如下式所示： \[ \begin{aligned} v^{*}(s)&=\max _{a} q^{*}(s, a) \\ &=\max_{a} \mathbb{E}[G_t|s_t=s,a_t=a]\\ &=\max_{a}\mathbb{E}[R_{t+1}+\gamma G_{t+1}|s_t=s,a_t=a]\\ &=\max_{a}\mathbb{E}[R_{t+1}+\gamma v^*(s_{t+1})|s_t=s,a_t=a]\\ &=\max_{a}\mathbb{E}[R_{t+1}]+ \max_a \mathbb{E}[\gamma v^*(s_{t+1})|s_t=s,a_t=a]\\ &=\max_{a} R(s,a) + \max_a\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{*}\left(s^{\prime}\right)\\ &=\max_{a} \left(R(s,a) + \gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) v^{*}\left(s^{\prime}\right)\right) \end{aligned} \] 我们就会得到状态-价值函数的一个转移。

Value Iteration

Principle of Optimality

我们从另一个角度思考问题，动态规划的方法将优化问题分成两个部分：

• 第一步执行的是最优的 action；
• 之后后继的状态每一步都按照最优的 policy 去做，那么我最后的结果就是最优的。

Principle of Optimality Theorem:

一个 policy \(\pi(s|a)\) 在状态 \(s\) 达到了最优价值，也就是 \(v^{\pi}(s) = v^{*}(s)\) 成立，当且仅当：

对于任何能够从 \(s\) 到达的 \(s'\)，都已经达到了最优价值，也就是，对于所有的 \(s'\)，\(v^{\pi}(s') = v^{*}(s')\) 恒成立。

Deterministic Value Iteration

Value iteration 就是把 Bellman Optimality Equation 当成一个 update rule 来进行，如下式所示： \[ v(s) \leftarrow \max _{a \in \mathcal{A}}\left(R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right)\right) \] 之前我们说上面这个等式只有当整个 MDP 已经到达最佳的状态时才满足。但这里可以把它转换成一个 backup 的等式。Backup 就是说一个迭代的等式。我们不停地去迭代 Bellman Optimality Equation，到了最后，它能逐渐趋向于最佳的策略，这是 value iteration 算法的精髓。

为了得到最佳的 \(v^*\) ，对于每个状态的 \(v^*\)，我们直接把这个 Bellman Optimality Equation 进行迭代，迭代了很多次之后，它就会收敛。

• 我们使用 value iteration 算法是为了得到一个最佳的策略。
• 解法：我们可以直接把 Bellman Optimality backup 这个等式拿进来进行迭代，迭代很多次，收敛过后得到的那个值就是它的最佳的值。
• 这个算法开始的时候，它是先把所有值初始化，通过每一个状态，然后它会进行这个迭代。把等式 (22) 插到等式 (23) 里面，就是 Bellman optimality backup 的那个等式。有了等式 (22) 和等式 (23) 过后，然后进行不停地迭代，迭代过后，然后收敛，收敛后就会得到这个 \(v^*\) 。当我们有了 \(v^*\) 过后，一个问题是如何进一步推算出它的最佳策略。
• 提取最佳策略的话，我们可以直接用 arg max。就先把它的 Q 函数重构出来，重构出来过后，每一个列对应的最大的那个 action 就是它现在的最佳策略。这样就可以从最佳价值函数里面提取出最佳策略。
• 我们只是在解决一个 planning 的问题，而不是强化学习的问题，因为我们知道环境如何变化。

• value function 做的工作类似于 value 的反向传播，每次迭代做一步传播，所以中间过程的 policy 和 value function 是没有意义的。不像是 policy iteration，它每一次迭代的结果都是有意义的，都是一个完整的 policy。
• 上图是一个可视化的过程，在一个 gridworld 中，我们设定了一个终点(goal)，也就是左上角的点。不管你在哪一个位置开始，我们都希望能够到终点（实际上这个终点是在迭代过程中不必要的，只是为了更好的演示）。Value iteration 的迭代过程像是一个从某一个状态（这里是我们的 goal）反向传播其他各个状态的过程。因为每次迭代只能影响到与之直接相关的状态。
• 让我们回忆下 Principle of Optimality Theorem：当你这次迭代求解的某个状态 s 的 value function \(v_{k+1}(s)\) 是最优解，它的前提是能够从该状态到达的所有状态 s' 此时都已经得到了最优解；如果不是的话，它做的事情只是一个类似传递 value function 的过程。
• 以上图为例，实际上，对于每一个状态，我们都可以看成一个终点。迭代由每一个终点开始，每次都根据 Bellman optimality equation 重新计算 value。如果它的相邻节点 value 发生变化，变得更好，那么它也会变得更好，一直到相邻节点都不变了。因此，在我们迭代到 \(v_7\) 之前，也就是还没将每个终点的最优的 value 传递给其他的所有状态之前，中间的几个 value function 只是一种暂存的不完整的数据，它不能代表每一个 state 的 value function，所以生成的 policy 是一个没有意义的 policy。
• 因为它是一个迭代过程，这里可视化了从 \(v_1\) 到 \(v_7\) 每一个状态的值的变化，它的这个值逐渐在变化。而且因为它每走一步，就会得到一个负的值，所以它需要尽快地到达左上角，可以发现离它越远的，那个值就越小。
• \(v_7\) 收敛过后，右下角那个值是 -6，相当于它要走六步，才能到达最上面那个值。而且离目的地越近，它的价值越大。

Difference between Policy Iteration and Value Iteration

我们来看一个 MDP control 的 Demo。

• 首先来看 policy iteration。之前的例子在每个状态都是采取固定的随机策略，就每个状态都是 0.25 的概率往上往下往左往右，没有策略的改变。
• 但是我们现在想做 policy iteration，就是每个状态的策略都进行改变。Policy iteration 的过程是一个迭代过程。

我们先在这个状态里面 run 一遍 policy evaluation，就得到了一个 value function，每个状态都有一个 value function。

• 现在进行 policy improvement，点一下 policy update。点一下 policy update 过后，你可以发现有些格子里面的 policy 已经产生变化。
• 比如说对于中间这个 -1 的这个状态，它的最佳策略是往下走。当你到达这个状态后，你应该往下，这样就会得到最佳的这个值。
• 绿色右边的这个方块的策略也改变了，它现在选取的最佳策略是往左走，也就是说在这个状态的时候，最佳策略应该是往左走。

我们再 run 下一轮的 policy evaluation，你发现它的值又被改变了，很多次过后，它会收敛。

我们再 run policy update，你发现每个状态里面的值基本都改变，它不再是上下左右随机在变了，它会选取一个最佳的策略。

我们再 run 这个 policy evaluation，它的值又在不停地变化，变化之后又收敛了。

我们再来 run 一遍 policy update。现在它的值又会有变化，就在每一个状态，它的这个最佳策略也会产生一些改变。

再来在这个状态下面进行改变，现在你看基本没有什么变化，就说明整个 MDP 已经收敛了。所以现在它每个状态的值就是它当前最佳的 value function 的值以及它当前状态对应的这个 policy 就是最佳的 policy。

比如说现在我们在右上角 0.38 的这个位置，然后它说现在应该往下走，我们往下走一步。它又说往下走，然后再往下走。现在我们有两个选择：往左走和往下走。我们现在往下走，随着这个箭头的指示，我们就会到达中间 1.20 的一个状态。如果能达到这个状态，我们就会得到很多 reward 。

这个 Demo 说明了 policy iteration 可以把 gridworld 解决掉。解决掉的意思是说，不管在哪个状态，都可以顺着状态对应的最佳的策略来到达可以获得最多奖励的一个状态。

我们再用 value iteration 来解 MDP，点 Toggle value iteration。

• 当它的这个值确定下来过后，它会产生它的最佳状态，这个最佳状态提取的策略跟 policy iteration 得出来的最佳策略是一致的。
• 在每个状态，我们跟着这个最佳策略走，就会到达可以得到最多奖励的一个状态。

我们给出一个Demo，这个 Demo 是为了解一个叫 FrozenLake 的例子，这个例子是 OpenAI Gym 里的一个环境，跟 gridworld 很像，不过它每一个状态转移是一个概率。

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

• Policy Iteration 分两步，首先进行 policy evaluation，即对当前已经搜索到的策略函数进行一个估值。得到估值过后，进行 policy improvement，即把 Q 函数算出来，我们进一步进行改进。不断重复这两步，直到策略收敛。
• Value iteration 直接把 Bellman Optimality Equation 拿进来，然后去寻找最佳的 value function，没有 policy function 在这里面。当算出 optimal value function 过后，我们再来提取最佳策略。

Summary for Prediction and Control in MDP

总结如上表所示，就对于 MDP 里面的 prediction 和 control 都是用动态规划来解，我们其实采取了不同的 Bellman Equation。

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

References

• 强化学习基础 David Silver 笔记
• Reinforcement Learning: An Introduction (second edition)
• David Silver 强化学习公开课中文讲解及实践
• UCL Course on RL(David Silver)
• Derivation of Bellman’s Equation
• 深入浅出强化学习：原理入门

Chapter1 强化学习概述

1 Keywords

• 强化学习（Reinforcement Learning）：Agent可以在与复杂且不确定的Environment进行交互时，尝试使所获得的Reward最大化的计算算法。
• Action: Environment接收到的Agent当前状态的输出。
• State：Agent从Environment中获取到的状态。
• Reward：Agent从Environment中获取的反馈信号，这个信号指定了Agent在某一步采取了某个策略以后是否得到奖励。
• Exploration：在当前的情况下，继续尝试新的Action，其有可能会使你得到更高的这个奖励，也有可能使你一无所有。
• Exploitation：在当前的情况下，继续尝试已知的可以获得最大Reward的过程，即重复执行这个 Action 就可以了。
• 深度强化学习（Deep Reinforcement Learning）：不需要手工设计特征，仅需要输入State让系统直接输出Action的一个end-to-end training的强化学习方法。通常使用神经网络来拟合 value function 或者 policy network。
• Full observability、fully observed和partially observed：当Agent的状态跟Environment的状态等价的时候，我们就说现在Environment是full observability（全部可观测），当Agent能够观察到Environment的所有状态时，我们称这个环境是fully observed（完全可观测）。一般我们的Agent不能观察到Environment的所有状态时，我们称这个环境是partially observed（部分可观测）。
• POMDP（Partially Observable Markov Decision Processes）：部分可观测马尔可夫决策过程，即马尔可夫决策过程的泛化。POMDP 依然具有马尔可夫性质，但是假设智能体无法感知环境的状态 \(s\)，只能知道部分观测值 \(o\)。
• Action space（discrete action spaces and continuous action spaces）：在给定的Environment中，有效动作的集合经常被称为动作空间（Action space），Agent的动作数量是有限的动作空间为离散动作空间（discrete action spaces），反之，称为连续动作空间（continuous action spaces）。
• policy-based（基于策略的）：Agent会制定一套动作策略（确定在给定状态下需要采取何种动作），并根据这个策略进行操作。强化学习算法直接对策略进行优化，使制定的策略能够获得最大的奖励。
• valued-based（基于价值的）：Agent不需要制定显式的策略，它维护一个价值表格或价值函数，并通过这个价值表格或价值函数来选取价值最大的动作。
• model-based（有模型结构）：Agent通过学习状态的转移来采取措施。
• model-free（无模型结构）：Agent没有去直接估计状态的转移，也没有得到Environment的具体转移变量。它通过学习 value function 和 policy function 进行决策。

2 Questions

• 强化学习的基本结构是什么？

  答：本质上是Agent和Environment间的交互。具体地，当Agent在Environment中得到当前时刻的State，Agent会基于此状态输出一个Action。然后这个Action会加入到Environment中去并输出下一个State和当前的这个Action得到的Reward。Agent在Environment里面存在的目的就是为了极大它的期望积累的Reward。

• 强化学习相对于监督学习为什么训练会更加困难？（强化学习的特征）

  答：

  1. 强化学习处理的多是序列数据，其很难像监督学习的样本一样满足IID（独立同分布）条件。

  2. 强化学习有奖励的延迟（Delay Reward），即在Agent的action作用在Environment中时，Environment对于Agent的State的奖励的延迟（Delayed Reward），使得反馈不及时。

  3. 相比于监督学习有正确的label，可以通过其修正自己的预测，强化学习相当于一个“试错”的过程，其完全根据Environment的“反馈”更新对自己最有利的Action。

• 强化学习的基本特征有哪些？

  答：

  1. 有trial-and-error exploration的过程，即需要通过探索Environment来获取对这个Environment的理解。
  2. 强化学习的Agent会从Environment里面获得延迟的Reward。
  3. 强化学习的训练过程中时间非常重要，因为数据都是有时间关联的，而不是像监督学习一样是IID分布的。
  4. 强化学习中Agent的Action会影响它随后得到的反馈。

• 近几年强化学习发展迅速的原因？

  答：

  1. 算力（GPU、TPU）的提升，我们可以更快地做更多的 trial-and-error 的尝试来使得Agent在Environment里面获得很多信息，取得更大的Reward。

  2. 我们有了深度强化学习这样一个端到端的训练方法，可以把特征提取和价值估计或者决策一起优化，这样就可以得到一个更强的决策网络。

• 状态和观测有什么关系？

  答：状态（state）是对世界的完整描述，不会隐藏世界的信息。观测（observation）是对状态的部分描述，可能会遗漏一些信息。在深度强化学习中，我们几乎总是用一个实值向量、矩阵或者更高阶的张量来表示状态和观测。

• 对于一个强化学习 Agent，它由什么组成？

  答：

  1. 策略函数（policy function），Agent会用这个函数来选取它下一步的动作，包括随机性策略（stochastic policy）和确定性策略（deterministic policy）。

  2. 价值函数（value function），我们用价值函数来对当前状态进行评估，即进入现在的状态，到底可以对你后面的收益带来多大的影响。当这个价值函数大的时候，说明你进入这个状态越有利。

  3. 模型（model），其表示了 Agent 对这个Environment的状态进行的理解，它决定了这个系统是如何进行的。

• 根据强化学习 Agent 的不同，我们可以将其分为哪几类？

  答：

  1. 基于价值函数的Agent。 显式学习的就是价值函数，隐式的学习了它的策略。因为这个策略是从我们学到的价值函数里面推算出来的。
  2. 基于策略的Agent。它直接去学习 policy，就是说你直接给它一个 state，它就会输出这个动作的概率。然后在这个 policy-based agent 里面并没有去学习它的价值函数。
  3. 然后另外还有一种 Agent 是把这两者结合。把 value-based 和 policy-based 结合起来就有了 Actor-Critic agent。这一类 Agent 就把它的策略函数和价值函数都学习了，然后通过两者的交互得到一个更佳的状态。

• 基于策略迭代和基于价值迭代的强化学习方法有什么区别?

  答：

  1. 基于策略迭代的强化学习方法，agent会制定一套动作策略（确定在给定状态下需要采取何种动作），并根据这个策略进行操作。强化学习算法直接对策略进行优化，使制定的策略能够获得最大的奖励；基于价值迭代的强化学习方法，agent不需要制定显式的策略，它维护一个价值表格或价值函数，并通过这个价值表格或价值函数来选取价值最大的动作。
  2. 基于价值迭代的方法只能应用在不连续的、离散的环境下（如围棋或某些游戏领域），对于行为集合规模庞大、动作连续的场景（如机器人控制领域），其很难学习到较好的结果（此时基于策略迭代的方法能够根据设定的策略来选择连续的动作)；
  3. 基于价值迭代的强化学习算法有 Q-learning、 Sarsa 等，而基于策略迭代的强化学习算法有策略梯度算法等。
  4. 此外， Actor-Critic 算法同时使用策略和价值评估来做出决策，其中，智能体会根据策略做出动作，而价值函数会对做出的动作给出价值，这样可以在原有的策略梯度算法的基础上加速学习过程，取得更好的效果。

• 有模型（model-based）学习和免模型（model-free）学习有什么区别？

  答：针对是否需要对真实环境建模，强化学习可以分为有模型学习和免模型学习。 有模型学习是指根据环境中的经验，构建一个虚拟世界，同时在真实环境和虚拟世界中学习；免模型学习是指不对环境进行建模，直接与真实环境进行交互来学习到最优策略。总的来说，有模型学习相比于免模型学习仅仅多出一个步骤，即对真实环境进行建模。免模型学习通常属于数据驱动型方法，需要大量的采样来估计状态、动作及奖励函数，从而优化动作策略。免模型学习的泛化性要优于有模型学习，原因是有模型学习算需要对真实环境进行建模，并且虚拟世界与真实环境之间可能还有差异，这限制了有模型学习算法的泛化性。

• 强化学习的通俗理解

  答：environment 跟 reward function 不是我们可以控制的，environment 跟 reward function 是在开始学习之前，就已经事先给定的。我们唯一能做的事情是调整 actor 里面的 policy，使得 actor 可以得到最大的 reward。Actor 里面会有一个 policy， 这个 policy 决定了actor 的行为。Policy 就是给一个外界的输入，然后它会输出 actor 现在应该要执行的行为。

3 Something About Interview

• 高冷的面试官: 看来你对于RL还是有一定了解的,那么可以用一句话谈一下你对于强化学习的认识吗?

  答: 强化学习包含环境,动作和奖励三部分,其本质是agent通过与环境的交互,使得其作出的action所得到的决策得到的总的奖励达到最大,或者说是期望最大。

• 高冷的面试官: 你认为强化学习与监督学习和无监督学习有什么区别?

  答: 首先强化学习和无监督学习是不需要标签的,而监督学习需要许多有标签的样本来进行模型的构建;对于强化学习与无监督学习,无监督学习是直接对于给定的数据进行建模,寻找数据(特征)给定的隐藏的结构,一般对应的聚类问题,而强化学习需要通过延迟奖励学习策略来得到"模型"对于正确目标的远近(通过奖励惩罚函数进行判断),这里我们可以将奖励惩罚函数视为正确目标的一个稀疏、延迟形式。另外强化学习处理的多是序列数据,样本之间通常具有强相关性，但其很难像监督学习的样本一样满足IID条件。

• 高冷的面试官: 根据你上面介绍的内容,你认为强化学习的使用场景有哪些呢?

  答: 七个字的话就是多序列决策问题。或者说是对应的模型未知,需要通过学习逐渐逼近真实模型的问题并且当前的动作会影响环境的状态,即服从马尔可夫性的问题。同时应满足所有状态是可重复到达的(满足可学习型的)。

• 高冷的面试官: 强化学习中所谓的损失函数与DL中的损失函数有什么区别呀?

  答: DL中的loss function目的是使预测值和真实值之间的差距最小,而RL中的loss function是是奖励和的期望最大。

• 高冷的面试官: 你了解model-free和model-based吗?两者有什么区别呢?

  答: 两者的区别主要在于是否需要对于真实的环境进行建模, model-free不需要对于环境进行建模,直接与真实环境进行交互即可,所以其通常需要较大的数据或者采样工作来优化策略,这也帮助model-free对于真实环境具有更好的泛化性能; 而model-based 需要对于环境进行建模,同时再真实环境与虚拟环境中进行学习,如果建模的环境与真实环境的差异较大,那么会限制其泛化性能。现在通常使用model-free进行模型的构建工作。

Reinforement Learning

Reinforcement Learning

强化学习讨论的问题是一个智能体(agent) 怎么在一个复杂不确定的环境(environment)里面去极大化它能获得的奖励。 示意图由两部分组成：agent 和 environment。在强化学习过程中，agent 跟 environment 一直在交互。Agent 在环境里面获取到状态，agent 会利用这个状态输出一个动作(action)，一个决策。然后这个决策会放到环境之中去，环境会根据 agent 采取的决策，输出下一个状态以及当前的这个决策得到的奖励。Agent 的目的就是为了尽可能多地从环境中获取奖励。

我们可以把强化学习跟监督学习做一个对比。

• 举个图片分类的例子，监督学习(supervised learning)就是说我们有一大堆标注的数据，比如车、飞机、凳子这些标注的图片，这些图片都要满足独立同分布(i.i.d.)，就是它们之间是没有关联的。

• 然后我们训练一个分类器，比如说右边这个神经网络。为了分辨出这个图片是车辆还是飞机，训练过程中，我们把真实的标签给了这个网络。当这个网络做出一个错误的预测，比如现在输入了汽车的图片，它预测出来是飞机。我们就会直接告诉它，你这个预测是错误的，正确的标签应该是车。然后我们把这个错误写成一个损失函数(loss function)，通过反向传播(Backpropagation)来训练这个网络。

• 所以在监督学习过程中，有两个假设：

  • 输入的数据（标注的数据）都是没有关联的，尽可能没有关联。因为如果有关联的话，这个网络是不好学习的。
  • 我们告诉学习器(learner)正确的标签是什么，这样它可以通过正确的标签来修正自己的预测。

通常假设样本空间中全体样本服从一个未知分布，我们获得的每个样本都是独立地从这个分布上采样获得的，即独立同分布(independent and identically distributed，简称 i.i.d.)。

在强化学习里面，这两点其实都不满足。举一个 Atari Breakout 游戏的例子，这是一个打砖块的游戏，控制木板左右移动把球反弹到上面来消除砖块。

• 在游戏过程中，大家可以发现这个 agent 得到的观测不是个独立同分布的分布，上一帧下一帧其实有非常强的连续性。这就是说，得到的数据是相关的时间序列数据，不满足独立同分布。
• 另外一点，在玩游戏的过程中，你并没有立刻获得反馈，没有告诉你哪个动作是正确动作。比如你现在把这个木板往右移，那么只会使得这个球往上或者往左上去一点，你并不会得到立刻的反馈。所以强化学习这么困难的原因是没有得到很好的反馈，然后你依然希望 agent 在这个环境里面学习。

强化学习的训练数据就是这样一个玩游戏的过程。你从第一步开始，采取一个决策，比如说你把这个往右移，接到这个球了。第二步你又做出决策，得到的训练数据是一个玩游戏的序列。

比如现在是在第三步，你把这个序列放进去，你希望这个网络可以输出一个决策，在当前的这个状态应该输出往右移或者往左移。这里有个问题：我们没有标签来说明你现在这个动作是正确还是错误，必须等到游戏结束才可能说明，这个游戏可能十秒过后才结束。现在这个动作到底对最后游戏结束能赢是否有帮助，其实是不清楚的。这里就面临延迟奖励(Delayed Reward)，所以就使得训练这个网络非常困难。

我们对比下强化学习和监督学习。

• 强化学习输入的是序列数据，而不是像监督学习里面这些样本都是独立的。
• 学习器并没有被告诉你每一步正确的行为应该是什么。学习器需要自己去发现哪些行为可以得到最多的奖励，只能通过不停地尝试来发现最有利的动作。
  
• Agent 获得自己能力的过程中，其实是通过不断地试错探索(trial-and-error exploration)。
• 探索(exploration)和利用(exploitation)是强化学习里面非常核心的一个问题。
• 探索：你会去尝试一些新的行为，这些新的行为有可能会使你得到更高的奖励，也有可能使你一无所有。
• 利用：采取你已知的可以获得最大奖励的行为，你就重复执行这个动作就可以了，因为你已经知道可以获得一定的奖励。
• 因此，我们需要在探索和利用之间取得一个权衡，这也是在监督学习里面没有的情况。
• 在强化学习过程中，没有非常强的监督者(supervisor)，只有一个奖励信号(reward signal)，并且这个奖励信号是延迟的，就是环境会在很久以后告诉你之前你采取的行为到底是不是有效的。Agent 在这个强化学习里面学习的话就非常困难，因为你没有得到即时反馈。当你采取一个行为过后，如果是监督学习，你就立刻可以获得一个指引，就说你现在做出了一个错误的决定，那么正确的决定应该是谁。而在强化学习里面，环境可能会告诉你这个行为是错误的，但是它并没有告诉你正确的行为是什么。而且更困难的是，它可能是在一两分钟过后告诉你错误，它再告诉你之前的行为到底行不行。所以这也是强化学习和监督学习不同的地方。

通过跟监督学习比较，我们可以总结出强化学习的一些特征。

• 强化学习有这个 试错探索(trial-and-error exploration)，它需要通过探索环境来获取对环境的理解。
• 强化学习 agent 会从环境里面获得延迟的奖励。
• 在强化学习的训练过程中，时间非常重要。因为你得到的数据都是有时间关联的(sequential data)，而不是独立同分布的。在机器学习中，如果观测数据有非常强的关联，其实会使得这个训练非常不稳定。这也是为什么在监督学习中，我们希望数据尽量是独立同分布，这样就可以消除数据之间的相关性。
• Agent 的行为会影响它随后得到的数据，这一点是非常重要的。在我们训练 agent 的过程中，很多时候我们也是通过正在学习的这个 agent 去跟环境交互来得到数据。所以如果在训练过程中，这个 agent 的模型很快死掉了，那会使得我们采集到的数据是非常糟糕的，这样整个训练过程就失败了。所以在强化学习里面一个非常重要的问题就是怎么让这个 agent 的行为一直稳定地提升。

为什么我们关注强化学习，其中非常重要的一点就是强化学习得到的模型可以有超人类的表现。

• 监督学习获取的这些监督数据，其实是让人来标注的。比如说 ImageNet 的图片都是人类标注的。那么我们就可以确定这个算法的上限(upper bound)就是人类的表现，人类的这个标注结果决定了它永远不可能超越人类。
• 但是对于强化学习，它在环境里面自己探索，有非常大的潜力，它可以获得超越人的能力的这个表现，比如谷歌 DeepMind 的 AlphaGo 这样一个强化学习的算法可以把人类最强的棋手都打败。

这里给大家举一些在现实生活中强化学习的例子。

• 在自然界中，羚羊其实也是在做一个强化学习，它刚刚出生的时候，可能都不知道怎么站立，然后它通过试错的一个尝试，三十分钟过后，它就可以跑到每小时 36 公里，很快地适应了这个环境。
• 你也可以把股票交易看成一个强化学习的问题，就怎么去买卖来使你的收益极大化。
• 玩雅达利游戏或者一些电脑游戏，也是一个强化学习的过程。

上图是强化学习的一个经典例子，就是雅达利的一个叫 Pong 的游戏。这个游戏就是把这个球拍到左边，然后左边这个选手需要把这个球拍到右边。训练好的一个强化学习 agent 和正常的选手有区别，强化学习的 agent 会一直在做这种无意义的一些振动，而正常的选手不会出现这样的行为。

在这个 pong 的游戏里面，决策其实就是两个动作：往上或者往下。如果强化学习是通过学习一个 policy network 来分类的话，其实就是输入当前帧的图片，policy network 就会输出所有决策的可能性。

对于监督学习，我们可以直接告诉 agent 正确的标签是什么。但在这种游戏情况下面，我们并不知道它的正确的标签是什么。

在强化学习里面，我们是通过让它尝试去玩这个游戏，然后直到游戏结束过后，再去说你前面的一系列动作到底是正确还是错误。

• 上图的过程是 rollout 的一个过程。Rollout 的意思是从当前帧去生成很多局的游戏。

• 当前的 agent 去跟环境交互，你就会得到一堆观测。你可以把每一个观测看成一个轨迹(trajectory)。轨迹就是当前帧以及它采取的策略，即状态和动作的一个序列： \[ \tau=\left(s_{0}, a_{0}, s_{1}, a_{1}, \ldots\right) \]

• 最后结束过后，你会知道你到底有没有把这个球击到对方区域，对方没有接住，你是赢了还是输了。我们可以通过观测序列以及最终奖励(eventual reward)来训练这个 agent ，使它尽可能地采取可以获得这个最终奖励的动作。

• 一场游戏叫做一个 episode(回合) 或者 trial(试验)。

强化学习是有一定的历史的，只是最近大家把强化学习跟深度学习结合起来，就形成了深度强化学习(Deep Reinforcement Learning)。深度强化学习 = 深度学习 + 强化学习。这里做一个类比，把它类比于这个传统的计算机视觉以及深度计算机视觉。

• 传统的计算机视觉由两个过程组成。
  • 给定一张图，我们先要提取它的特征，用一些设计好的特征(feature)，比如说 HOG、DPM。
  • 提取这些特征后，我们再单独训练一个分类器。这个分类器可以是 SVM、Boosting，然后就可以辨别这张图片是狗还是猫。
• 2012年，Krizhevsky等人提出了AlexNet，AlexNet在ImageNet分类比赛中取得冠军，迅速引起了人们对于卷积神经网络的广泛关注。 大家就把特征提取以及分类两者合到一块儿去了，就是训练一个神经网络。这个神经网络既可以做特征提取，也可以做分类。它可以实现这种端到端的训练，它里面的参数可以在每一个阶段都得到极大的优化，这样就得到了一个非常重要的突破。

我们可以把神经网络放到强化学习里面。

• Standard RL：之前的强化学习，比如 TD-Gammon 玩 backgammon 这个游戏，它其实是设计特征，然后通过训练价值函数的一个过程，就是它先设计了很多手工的特征，这个手工特征可以描述现在整个状态。得到这些特征过后，它就可以通过训练一个分类网络或者分别训练一个价值估计函数来做出决策。
• Deep RL：现在我们有了深度学习，有了神经网络，那么大家也把这个过程改进成一个端到端训练(end-to-end training)的过程。你直接输入这个状态，我们不需要去手工地设计这个特征，就可以让它直接输出动作。那么就可以用一个神经网络来拟合我们这里的价值函数或策略网络，省去了特征工程(feature engineering)的过程。

为什么强化学习在这几年就用到各种应用中去，比如玩游戏以及机器人的一些应用，并且可以击败人类的最好棋手。

这有如下几点原因：

• 我们有了更多的算力(computation power)，有了更多的 GPU，可以更快地做更多的试错的尝试。
• 通过这种不同尝试使得 agent 在这个环境里面获得很多信息，然后可以在这个环境里面取得很大的奖励。
• 我们有了这个端到端的一个训练，可以把特征提取和价值估计或者决策一块来优化，这样就可以得到了一个更强的决策网络。

接下来给大家再看一些强化学习里面比较有意思的例子。

1. DeepMind 研发的一个走路的 agent。这个 agent 往前走一步，你就会得到一个 reward。这个 agent 有不同的这个形态，可以学到很多有意思的功能。比如怎么跨越这个障碍物，就像那个蜘蛛那样的 agent 。怎么跨越障碍物，像这个人有双腿一样， 这个 agent 往前走。以及像这个人形的 agent，怎么在一个曲折的道路上面往前走。这个结果也是非常有意思，这个人形 agent 会把手举得非常高，因为它这个手的功能就是为了使它身体保持平衡，这样它就可以更快地在这个环境里面往前跑，而且这里你也可以增加这个环境的难度，加入一些扰动，这个 agent 就会变得更鲁棒。
2. 机械臂抓取。因为机械臂的应用自动去强化学习需要大量的 rollout，所以它这里就有好多机械臂，分布式系统可以让这个机械臂尝试抓取不同的物体。你发现这个盘子里面物体的形状、形态其实都是不同的，这样就可以让这个机械臂学到一个统一的行为。然后在不同的抓取物下面都可以采取最优的一个抓取特征。你的这个抓取的物件形态存在很多不同，一些传统的这个抓取算法就没法把所有物体都抓起来，因为你对每一个物体都需要做一个建模，这样的话就是非常花时间。但是通过强化学习，你就可以学到一个统一的抓取算法，在不同物体上它都可以适用。
3. OpenAI 做的一个机械臂翻魔方。这里它们 18 年的时候先设计了这个手指的一个机械臂，让它可以通过翻动手指，使得手中的这个木块达到一个预定的设定。人的手指其实非常精细，怎么使得这个机械手臂也具有这样灵活的能力就一直是个问题。它们通过这个强化学习在一个虚拟环境里面先训练，让 agent 能翻到特定的这个方向，再把它应用到真实的手臂之中。这在强化学习里面是一个比较常用的做法，就是你先在虚拟环境里面得到一个很好的 agent，然后再把它使用到真实的这个机器人中。因为真实的机械手臂通常都是非常容易坏，而且非常贵，你没法大批量地购买。2019 年对手臂进一步改进了，这个手臂可以玩魔方了。这个结果也非常有意思，到后面，这个魔方就被恢复成了个六面都是一样的结构了。
4. 一个穿衣服的 agent ，就是训练这个 agent 穿衣服。因为很多时候你要在电影或者一些动画实现人穿衣服的场景，通过手写执行命令让机器人穿衣服其实非常困难。很多时候穿衣服也是一个非常精细的操作，那么它们这个工作就是训练这个强化学习 agent，然后就可以实现这个穿衣功能。你还可以在这里面加入一些扰动，然后 agent 可以抗扰动。可能会有失败的情况(failure case)， agent 就穿不进去，就卡在这个地方。

Introduction to Sequential Decision Making

Agent and Environment

接下来我们讲序列决策(Sequential Decision Making)过程。

强化学习研究的问题是 agent 跟环境交互，上图左边画的是一个 agent，agent 一直在跟环境进行交互。这个 agent 把它输出的动作给环境，环境取得这个动作过后，会进行到下一步，然后会把下一步的观测跟它上一步是否得到奖励返还给 agent。

通过这样的交互过程会产生很多观测，agent 的目的是从这些观测之中学到能极大化奖励的策略。

Reward

奖励是由环境给的一个标量的反馈信号(scalar feedback signal)，这个信号显示了 agent 在某一步采取了某个策略的表现如何。

强化学习的目的就是为了最大化 agent 可以获得的奖励，agent 在这个环境里面存在的目的就是为了极大化它的期望的累积奖励(expected cumulative reward)。

不同的环境，奖励也是不同的。这里给大家举一些奖励的例子。

• 比如说一个下象棋的选手，他的目的其实就为了赢棋。奖励是说在最后棋局结束的时候，他知道会得到一个正奖励或者负奖励。
• 羚羊站立也是一个强化学习过程，它得到的奖励就是它是否可以最后跟它妈妈一块离开或者它被吃掉。
• 在股票管理里面，奖励定义由你的股票获取的收益跟损失决定。
• 在玩雅达利游戏的时候，奖励就是你有没有在增加游戏的分数，奖励本身的稀疏程度决定了这个游戏的难度。

Sequential Decision Making

在一个强化学习环境里面，agent 的目的就是选取一系列的动作来极大化它的奖励，所以这些采取的动作必须有长期的影响。但在这个过程里面，它的奖励其实是被延迟了，就是说你现在采取的某一步决策可能要等到时间很久过后才知道这一步到底产生了什么样的影响。

这里一个示意图就是我们玩这个 Atari 的 Pong 游戏，你可能只有到最后游戏结束过后，才知道这个球到底有没有击打过去。中间你采取的 up 或 down 行为，并不会直接产生奖励。强化学习里面一个重要的课题就是近期奖励和远期奖励的一个权衡(trade-off)。怎么让 agent 取得更多的长期奖励是强化学习的问题。

在跟环境的交互过程中，agent 会获得很多观测。在每一个观测会采取一个动作，它也会得到一个奖励。所以历史是观测(observation)、行为、奖励的序列： \[ H_{t}=O_{1}, R_{1}, A_{1}, \ldots, A_{t-1}, O_{t}, R_{t} \] Agent 在采取当前动作的时候会依赖于它之前得到的这个历史，所以你可以把整个游戏的状态看成关于这个历史的函数： \[ S_{t}=f\left(H_{t}\right) \] Q: 状态和观测有什么关系?

A: 状态(state) \(s\) 是对世界的完整描述，不会隐藏世界的信息。观测(observation) \(o\) 是对状态的部分描述，可能会遗漏一些信息。在 deep RL 中，我们几乎总是用一个实值的向量、矩阵或者更高阶的张量来表示状态和观测。举个例子，我们可以用 RGB 像素值的矩阵来表示一个视觉的观测，我们可以用机器人关节的角度和速度来表示一个机器人的状态。

环境有自己的函数 \(S_{t}^{e}=f^{e}\left(H_{t}\right)\) 来更新状态，在 agent 的内部也有一个函数 \(S_{t}^{a}=f^{a}\left(H_{t}\right)\) 来更新状态。当 agent 的状态跟环境的状态等价的时候，我们就说这个环境是 full observability，就是全部可以观测。换句话说，当 agent 能够观察到环境的所有状态时，我们称这个环境是完全可观测的(fully observed)。在这种情况下面，强化学习通常被建模成一个 Markov decision process(MDP)的问题。在 MDP 中， \(O_{t}=S_{t}^{e}=S_{t}^{a}\)。

但是有一种情况是 agent 得到的观测并不能包含环境运作的所有状态，因为在这个强化学习的设定里面，环境的状态才是真正的所有状态。

• 比如 agent 在玩这个 black jack 这个游戏，它能看到的其实是牌面上的牌。
• 或者在玩雅达利游戏的时候，观测到的只是当前电视上面这一帧的信息，你并没有得到游戏内部里面所有的运作状态。

也就是说当 agent 只能看到部分的观测，我们就称这个环境是部分可观测的(partially observed)。在这种情况下面，强化学习通常被建模成一个 POMDP 的问题。

部分可观测马尔可夫决策过程(Partially Observable Markov Decision Processes, POMDP)是一个马尔可夫决策过程的泛化。POMDP 依然具有马尔可夫性质，但是假设智能体无法感知环境的状态 \(s\)，只能知道部分观测值 \(o\)。比如在自动驾驶中，智能体只能感知传感器采集的有限的环境信息。

POMDP 可以用一个 7 元组描述：\((S,A,T,R,\Omega,O,\gamma)\)，其中 \(S\) 表示状态空间，为隐变量，\(A\) 为动作空间，\(T(s'|s,a)\) 为状态转移概率，\(R\) 为奖励函数，\(\Omega(o|s,a)\) 为观测概率，\(O\) 为观测空间，\(\gamma\) 为折扣系数。

Action Spaces

不同的环境允许不同种类的动作。在给定的环境中，有效动作的集合经常被称为动作空间(action space)。像 Atari 和 Go 这样的环境有离散动作空间(discrete action spaces)，在这个动作空间里，agent 的动作数量是有限的。在其他环境，比如在物理世界中控制一个 agent，在这个环境中就有连续动作空间(continuous action spaces) 。在连续空间中，动作是实值的向量。

例如，

• 走迷宫机器人如果只有东南西北这 4 种移动方式，则其为离散动作空间；
• 如果机器人向 \(360^{\circ}\) 中的任意角度都可以移动，则为连续动作空间。

Major Components of an RL Agent

对于一个强化学习 agent，它可能有一个或多个如下的组成成分：

• 策略函数(policy function)，agent 会用这个函数来选取下一步的动作。

• 价值函数(value function)，我们用价值函数来对当前状态进行估价，它就是说你进入现在这个状态，可以对你后面的收益带来多大的影响。当这个价值函数大的时候，说明你进入这个状态越有利。

• 模型(model)，模型表示了 agent 对这个环境的状态进行了理解，它决定了这个世界是如何进行的。

Policy

我们深入看这三个组成成分的一些细节。

Policy 是 agent 的行为模型，它决定了这个 agent 的行为，它其实是一个函数，把输入的状态变成行为。这里有两种 policy：

• 一种是 stochastic policy(随机性策略)，它就是 \(\pi\) 函数 \(\pi(a | s)=P\left[A_{t}=a | S_{t}=s\right]\) 。当你输入一个状态 \(s\) 的时候，输出是一个概率。这个概率就是你所有行为的一个概率，然后你可以进一步对这个概率分布进行采样，得到真实的你采取的行为。比如说这个概率可能是有 70% 的概率往左，30% 的概率往右，那么你通过采样就可以得到一个 action。
• 一种是 deterministic policy(确定性策略)，就是说你这里有可能只是采取它的极大化，采取最有可能的动作，即 \(a^{*}=\arg \underset{a}{\max} \pi(a \mid s)\)。 你现在这个概率就是事先决定好的。

从 Atari 游戏来看的话，策略函数的输入就是游戏的一帧，它的输出决定你是往左走或者是往右走。

通常情况下，强化学习一般使用随机性策略。随机性策略有很多优点：

• 在学习时可以通过引入一定随机性来更好地探索环境；

• 随机性策略的动作具有多样性，这一点在多个智能体博弈时也非常重要。采用确定性策略的智能体总是对同样的环境做出相同的动作，会导致它的策略很容易被对手预测。

Value Function

价值函数是未来奖励的一个预测，用来评估状态的好坏。

价值函数里面有一个 discount factor(折扣因子)，我们希望尽可能在短的时间里面得到尽可能多的奖励。如果我们说十天过后，我给你 100 块钱，跟我现在给你 100 块钱，你肯定更希望我现在就给你 100 块钱，因为你可以把这 100 块钱存在银行里面，你就会有一些利息。所以我们就通过把这个折扣因子放到价值函数的定义里面，价值函数的定义其实是一个期望，如下式所示： \[ v_{\pi}(s) \doteq \mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s\right], \text { for all } s \in \mathcal{S} \] 这里有一个期望 \(\mathbb{E}_{\pi}\)，这里有个小角标是 \(\pi\) 函数，这个 \(\pi\) 函数就是说在我们已知某一个策略函数的时候，到底可以得到多少的奖励。

我们还有一种价值函数：Q 函数。Q 函数里面包含两个变量：状态和动作，其定义如下式所示： \[ q_{\pi}(s, a) \doteq \mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s, A_{t}=a\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s, A_{t}=a\right] \] 所以你未来可以获得多少的奖励，它的这个期望取决于你当前的状态和当前的行为。这个 Q 函数是强化学习算法里面要学习的一个函数。因为当我们得到这个 Q 函数后，进入某一种状态，它最优的行为就可以通过这个 Q 函数来得到。

Model

第三个组成部分是模型，模型决定了下一个状态会是什么样的，就是说下一步的状态取决于你当前的状态以及你当前采取的行为。它由两个部分组成，

• 概率：这个转移状态之间是怎么转移的，如下式所示：

\[ \mathcal{P}_{s s^{\prime}}^{a}=\mathbb{P}\left[S_{t+1}=s^{\prime} \mid S_{t}=s, A_{t}=a\right] \]

• 奖励函数：当你在当前状态采取了某一个行为，可以得到多大的奖励，如下式所示： \[ \mathcal{R}_{s}^{a}=\mathbb{E}\left[R_{t+1} \mid S_{t}=s, A_{t}=a\right] \]

当我们有了这三个组成部分过后，就形成了一个 马尔可夫决策过程(Markov Decision Process)。这个决策过程可视化了状态之间的转移以及采取的行为。

我们来看一个走迷宫的例子。

• 要求 agent 从 start 开始，然后到达 goal 的位置。
• 每走一步，你就会得到 -1 的奖励。
• 可以采取的动作是往上下左右走。
• 当前状态用现在 agent 所在的位置来描述。

• 我们可以用不同的强化学习算法来解这个环境。

• 如果采取的是 基于策略的(policy-based)RL，当学习好了这个环境过后，在每一个状态，我们就会得到一个最佳的行为。

• 比如说现在在第一格开始的时候，我们知道它最佳行为是往右走，然后第二格的时候，得到的最佳策略是往上走，第三格是往右走。通过这个最佳的策略，我们就可以最快地到达终点。

• 如果换成 基于价值的(value-based)RL 这个算法，利用价值函数来作为导向，我们就会得到另外一种表征，这里就表征了你每一个状态会返回一个价值。

• 比如说你在 start 位置的时候，价值是 -16，因为你最快可以 16 步到达终点。因为每走一步会减一，所以你这里的价值是 -16。

• 当我们快接近最后终点的时候，这个数字变得越来越大。在拐角的时候，比如要现在在第二格 -15。然后 agent 会看上下，它看到上面值变大了，变成 -14 了，它下面是 -16，那么 agent 肯定就会采取一个往上走的策略。所以通过这个学习的值的不同，我们可以抽取出现在最佳的策略。

Types of RL Agents

根据 agent 学习的东西不同，我们可以把 agent 进行归类。

• 基于价值的 agent(value-based agent)。
  • 这一类 agent 显式地学习的是价值函数，
  • 隐式地学习了它的策略。策略是从我们学到的价值函数里面推算出来的。
• 基于策略的 agent(policy-based agent)。
  • 这一类 agent 直接去学习 policy，就是说你直接给它一个状态，它就会输出这个动作的概率。
  • 在基于策略的 agent 里面并没有去学习它的价值函数。
• 把 value-based 和 policy-based 结合起来就有了 Actor-Critic agent。这一类 agent 把它的策略函数和价值函数都学习了，然后通过两者的交互得到一个最佳的行为。

Q: 基于策略迭代和基于价值迭代的强化学习方法有什么区别?

A: 对于一个状态转移概率已知的马尔可夫决策过程，我们可以使用动态规划算法来求解；从决策方式来看，强化学习又可以划分为基于策略迭代的方法和基于价值迭代的方法。决策方式是智能体在给定状态下从动作集合中选择一个动作的依据，它是静态的，不随状态变化而变化。

在基于策略迭代的强化学习方法中，智能体会制定一套动作策略（确定在给定状态下需要采取何种动作），并根据这个策略进行操作。强化学习算法直接对策略进行优化，使制定的策略能够获得最大的奖励。

而在基于价值迭代的强化学习方法中，智能体不需要制定显式的策略，它维护一个价值表格或价值函数，并通过这个价值表格或价值函数来选取价值最大的动作。基于价值迭代的方法只能应用在不连续的、离散的环境下（如围棋或某些游戏领域），对于行为集合规模庞大、动作连续的场景（如机器人控制领域），其很难学习到较好的结果（此时基于策略迭代的方法能够根据设定的策略来选择连续的动作)。

基于价值迭代的强化学习算法有 Q-learning、 Sarsa 等，而基于策略迭代的强化学习算法有策略梯度算法等。此外， Actor-Critic 算法同时使用策略和价值评估来做出决策，其中，智能体会根据策略做出动作，而价值函数会对做出的动作给出价值，这样可以在原有的策略梯度算法的基础上加速学习过程，取得更好的效果。

另外，我们是可以通过 agent 到底有没有学习这个环境模型来分类。

• model-based(有模型) RL agent，它通过学习这个状态的转移来采取动作。
• model-free(免模型) RL agent，它没有去直接估计这个状态的转移，也没有得到环境的具体转移变量。它通过学习价值函数和策略函数进行决策。Model-free 的模型里面没有一个环境转移的模型。

我们可以用马尔可夫决策过程来定义强化学习任务，并表示为四元组 \(<S,A,P,R>\)，即状态集合、动作集合、状态转移函数和奖励函数。如果这四元组中所有元素均已知，且状态集合和动作集合在有限步数内是有限集，则机器可以对真实环境进行建模，构建一个虚拟世界来模拟真实环境的状态和交互反应。

具体来说，当智能体知道状态转移函数 \(P(s_{t+1}|s_t,a_t)\) 和奖励函数 \(R(s_t,a_t)\) 后，它就能知道在某一状态下执行某一动作后能带来的奖励和环境的下一状态，这样智能体就不需要在真实环境中采取动作，直接在虚拟世界中学习和规划策略即可。这种学习方法称为有模型学习。

上图是有模型强化学习的流程图。

然而在实际应用中，智能体并不是那么容易就能知晓 MDP 中的所有元素的。通常情况下，状态转移函数和奖励函数很难估计，甚至连环境中的状态都可能是未知的，这时就需要采用免模型学习。免模型学习没有对真实环境进行建模，智能体只能在真实环境中通过一定的策略来执行动作，等待奖励和状态迁移，然后根据这些反馈信息来更新行为策略，这样反复迭代直到学习到最优策略。

Q: 有模型强化学习和免模型强化学习有什么区别？

A: 针对是否需要对真实环境建模，强化学习可以分为有模型学习和免模型学习。

• 有模型学习是指根据环境中的经验，构建一个虚拟世界，同时在真实环境和虚拟世界中学习；

• 免模型学习是指不对环境进行建模，直接与真实环境进行交互来学习到最优策略。

总的来说，有模型学习相比于免模型学习仅仅多出一个步骤，即对真实环境进行建模。因此，一些有模型的强化学习方法，也可以在免模型的强化学习方法中使用。在实际应用中，如果不清楚该用有模型强化学习还是免模型强化学习，可以先思考一下，在智能体执行动作前，是否能对下一步的状态和奖励进行预测，如果可以，就能够对环境进行建模，从而采用有模型学习。

免模型学习通常属于数据驱动型方法，需要大量的采样来估计状态、动作及奖励函数，从而优化动作策略。例如，在 Atari 平台上的 Space Invader 游戏中，免模型的深度强化学习需要大约 2 亿帧游戏画面才能学到比较理想的效果。相比之下，有模型学习可以在一定程度上缓解训练数据匮乏的问题，因为智能体可以在虚拟世界中行训练。

免模型学习的泛化性要优于有模型学习，原因是有模型学习算需要对真实环境进行建模，并且虚拟世界与真实环境之间可能还有差异，这限制了有模型学习算法的泛化性。

有模型的强化学习方法可以对环境建模，使得该类方法具有独特魅力，即“想象能力”。在免模型学习中，智能体只能一步一步地采取策略，等待真实环境的反馈；而有模型学习可以在虚拟世界中预测出所有将要发生的事，并采取对自己最有利的策略。

目前，大部分深度强化学习方法都采用了免模型学习，这是因为：

• 免模型学习更为简单直观且有丰富的开源资料，像 DQN、AlphaGo 系列等都采用免模型学习；
• 在目前的强化学习研究中，大部分情况下环境都是静态的、可描述的，智能体的状态是离散的、可观察的（如 Atari 游戏平台），这种相对简单确定的问题并不需要评估状态转移函数和奖励函数，直接采用免模型学习，使用大量的样本进行训练就能获得较好的效果。

把几类模型放到同一个饼图里面。饼图有三个组成部分：价值函数、策略和模型。按一个 agent 具不具有三者中的两者或者一者可以把它分成很多类。

Learning and Planning

Learning 和 Planning 是序列决策的两个基本问题。

在强化学习中，环境初始时是未知的，agent 不知道环境如何工作，agent 通过不断地与环境交互，逐渐改进策略。

在 plannning 中，环境是已知的，我们被告知了整个环境的运作规则的详细信息。Agent 能够计算出一个完美的模型，并且在不需要与环境进行任何交互的时候进行计算。Agent 不需要实时地与环境交互就能知道未来环境，只需要知道当前的状态，就能够开始思考，来寻找最优解。

在这个游戏中，规则是制定的，我们知道选择 left 之后环境将会产生什么变化。我们完全可以通过已知的变化规则，来在内部进行模拟整个决策过程，无需与环境交互。

一个常用的强化学习问题解决思路是，先学习环境如何工作，也就是了解环境工作的方式，即学习得到一个模型，然后利用这个模型进行规划。

Exploration and Exploitation

在强化学习里面，探索 和利用 是两个很核心的问题。

• 探索是说我们怎么去探索这个环境，通过尝试不同的行为来得到一个最佳的策略，得到最大奖励的策略。

• 利用是说我们不去尝试新的东西，就采取已知的可以得到很大奖励的行为。

因为在刚开始的时候强化学习 agent 不知道它采取了某个行为会发生什么，所以它只能通过试错去探索。所以探索就是在试错来理解采取的这个行为到底可不可以得到好的奖励。利用是说我们直接采取已知的可以得到很好奖励的行为。所以这里就面临一个权衡，怎么通过牺牲一些短期的奖励来获得行为的理解，从而学习到更好的策略。

下面举一些探索和利用的例子。

• 以选择餐馆为例，
  • 利用：我们直接去你最喜欢的餐馆，因为你去过这个餐馆很多次了，所以你知道这里面的菜都非常可口。
  • 探索：你把手机拿出来，你直接搜索一个新的餐馆，然后去尝试它到底好不好吃。你有可能对这个新的餐馆非常不满意，钱就浪费了。
• 以做广告为例，
  • 利用：我们直接采取最优的这个广告策略。
  • 探索：我们换一种广告策略，看看这个新的广告策略到底可不可以得到奖励。
• 以挖油为例，
  • 利用：我们直接在已知的地方挖油，我们就可以确保挖到油。
  • 探索：我们在一个新的地方挖油，就有很大的概率，你可能不能发现任何油，但也可能有比较小的概率可以发现一个非常大的油田。
• 以玩游戏为例，
  • 利用：你总是采取某一种策略。比如说，你可能打街霸，你采取的策略可能是蹲在角落，然后一直触脚。这个策略很可能可以奏效，但可能遇到特定的对手就失效。
  • 探索：你可能尝试一些新的招式，有可能你会发出大招来，这样就可能一招毙命。

K-armed Bandit

与监督学习不同，强化学习任务的最终奖赏是在多步动作之后才能观察到，这里我们不妨先考虑比较简单的情形：最大化单步奖赏，即仅考虑一步操作。需注意的是，即便在这样的简化情形下，强化学习仍与监督学习有显著不同，因为机器需通过尝试来发现各个动作产生的结果，而没有训练数据告诉机器应当做哪个动作。

想要最大化单步奖赏需考虑两个方面：一是需知道每个动作带来的奖赏，二是要执行奖赏最大的动作。若每个动作对应的奖赏是一个确定值，那么尝试遍所有的动作便能找出奖赏最大的动作。然而，更一般的情形是，一个动作的奖赏值是来自于一个概率分布，仅通过一次尝试并不能确切地获得平均奖赏值。

实际上，单步强化学习任务对应了一个理论模型，即K-臂赌博机(K-armed bandit)。K-臂赌博机也被称为 多臂赌博机(Multi-armed bandit)。如上图所示，K-摇臂赌博机有 K 个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

• 若仅为获知每个摇臂的期望奖赏，则可采用仅探索(exploration-only)法：将所有的尝试机会平均分配给每个摇臂(即轮流按下每个摇臂)，最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。

• 若仅为执行奖赏最大的动作，则可采用仅利用(exploitation-only)法：按下目前最优的(即到目前为止平均奖赏最大的)摇臂，若有多个摇臂同为最优，则从中随机选取一个。

显然，仅探索法能很好地估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会；仅利用法则相反，它没有很好地估计摇臂期望奖赏，很可能经常选不到最优摇臂。因此，这两种方法都难以使最终的累积奖赏最大化。

事实上，探索(即估计摇臂的优劣)和利用(即选择当前最优摇臂)这两者是矛盾的，因为尝试次数(即总投币数)有限，加强了一方则会自然削弱另一方，这就是强化学习所面临的探索-利用窘境(Exploration-Exploitation dilemma)。显然，想要累积奖赏最大，则必须在探索与利用之间达成较好的折中。

Experiment with Reinforcement Learning

强化学习是一个理论跟实践结合的机器学习分支，需要去推导很多算法公式，去理解它算法背后的一些数学原理。另外一方面，上机实践通过实现算法，在很多实验环境里面去探索这个算法是不是可以得到预期效果也是一个非常重要的过程。

在这个链接里面，公布了一些 RL 相关的代码，利用了 Python 和深度学习的一些包(主要是用 PyTorch 为主)。

你可以直接调用现有的包来实践。现在有很多深度学习的包可以用，比如 PyTorch、TensorFlow、Keras，熟练使用这里面的两三种，就可以实现非常多的功能。所以你并不需要从头去造轮子。

OpenAI 是一个非盈利的人工智能研究公司。Open AI 公布了非常多的学习资源以及算法资源，他们之所以叫 Open AI，就是他们把所有开发的算法都 open source 出来。

Gym

OpenAI Gym 是一个环境仿真库，里面包含了很多现有的环境。针对不同的场景，我们可以选择不同的环境，

• 离散控制场景(输出的动作是可数的，比如 Pong 游戏中输出的向上或向下动作)：一般使用 Atari 环境评估
• 连续控制场景(输出的动作是不可数的，比如机器人走路时不仅有方向，还要角度，角度就是不可数的，是一个连续的量 )：一般使用 mujoco 环境评估

Gym Retro 是对 Gym 环境的进一步扩展，包含了更多的一些游戏。

我们可以通过 pip 来安装 Gym:

1

pip install gym

在 Python 环境中导入Gym，如果不报错，就可以认为 Gym 安装成功。

1
2

$python
>>>import gym

1
2
3
4
5
6
7

import gym 
env = gym.make("Taxi-v3") 
observation = env.reset() 
agent = load_agent() 
for step in range(100):
    action = agent(observation) 
    observation, reward, done, info = env.step(action)

强化学习的这个交互就是由 agent 跟环境进行交互。所以算法的 interface 也是用这个来表示。比如说我们现在安装了 OpenAI Gym。

1. 我们就可以直接调入 Taxi-v3 的环境，就建立了这个环境。

2. 初始化这个环境过后，就可以进行交互了。

3. Agent 得到这个观测过后，它就会输出一个 action。

4. 这个动作会被环境拿进去执行这个 step，然后环境就会往前走一步，返回新的 observation、reward 以及一个 flag variable done ，done 决定这个游戏是不是结束了。

几行代码就实现了强化学习的框架。

在 OpenAI Gym 里面有很经典的控制类游戏。

• 比如说 Acrobot 就是把两节铁杖甩了立起来。
• CartPole 是通过控制一个平板，让木棍立起来。
• MountainCar 是通过前后移动这个车，让它到达这个旗子的位置。

大家可以点这个链接看一看这些环境。在刚开始测试强化学习的时候，可以选择这些简单环境，因为这些环境可以在一两分钟之内见到一个效果。

这里我们看一下 CartPole 的这个环境。对于这个环境，有两个动作，Cart 往左移还是往右移。这里得到了观测：

• 这个车当前的位置，
• Cart 当前往左往右移的速度，
• 这个杆的角度以及杆的最高点的速度。

如果 observation 越详细，就可以更好地描述当前这个所有的状态。这里有 reward 的定义，如果能多保留一步，你就会得到一个奖励，所以你需要在尽可能多的时间存活来得到更多的奖励。当这个杆的角度大于某一个角度（没能保持平衡）或者这个车已经出到外面的时候，游戏就结束了，你就输了。所以这个 agent 的目的就是为了控制木棍，让它尽可能地保持平衡以及尽可能保持在这个环境的中央。

1
2
3
4
5
6
7
8

import gym  # 导入 Gym 的 Python 接口环境包
env = gym.make('CartPole-v0')  # 构建实验环境
env.reset()  # 重置一个 episode
for _ in range(1000):
    env.render()  # 显示图形界面
    action = env.action_space.sample() # 从动作空间中随机选取一个动作
    env.step(action) # 用于提交动作，括号内是具体的动作
env.close() # 关闭环境

注意：如果绘制了实验的图形界面窗口，那么关闭该窗口的最佳方式是调用env.close()。试图直接关闭图形界面窗口可能会导致内存不能释放，甚至会导致死机。

当你执行这段代码时，机器人会完全无视那根本该立起来的杆子，驾驶着小车朝某个方向一通跑，直到不见踪影，这是因为我们还没开始训练机器人。

Gym 中的小游戏，大部分都可以用一个普通的实数或者向量来充当动作。打印 env.action_space.sample() 的返回值，能看到输出为 1 或者 0。

env.action_space.sample()的含义是，在该游戏的所有动作空间里随机选择一个作为输出。在这个例子中，意思就是，动作只有两个：0 和 1，一左一右。

env.step()这个方法的作用不止于此，它还有四个返回值，分别是observation、reward、done、info。

• observation(object)是状态信息，是在游戏中观测到的屏幕像素值或者盘面状态描述信息。
• reward(float)是奖励值，即 action 提交以后能够获得的奖励值。这个奖励值因游戏的不同而不同，但总体原则是，对完成游戏有帮助的动作会获得比较高的奖励值。
• done(boolean)表示游戏是否已经完成。如果完成了，就需要重置游戏并开始一个新的 episode。
• info(dict)是一些比较原始的用于诊断和调试的信息，或许对训练有帮助。不过，OpenAI 团队在评价你提交的机器人时，是不允许使用这些信息的。

在每个训练中都要使用的返回值有 observation、reward、done。但 observation 的结构会由于游戏的不同而发生变化。以 CartPole-v0 小游戏为例，我们修改下代码：

1
2
3
4
5
6
7
8
9

import gym  
env = gym.make('CartPole-v0')  
env.reset()  
for _ in range(1000):
    env.render()  
    action = env.action_space.sample() 
    observation, reward, done, info = env.step(action)
    print(observation)
env.close()

输出：

1
2
3
4

[ 0.01653398  0.19114579  0.02013859 -0.28050058]
[ 0.0203569  -0.00425755  0.01452858  0.01846535]
[ 0.02027175 -0.19958481  0.01489789  0.31569658]
......

从输出可以看出这是一个四维的 Observation。在其他游戏中会有维度很多的情况。

env.step()完成了一个完整的 \(S \to A \to R \to S'\) 过程。我们只要不断观测这样的过程，并让机器在其中用相应的算法完成训练，就能得到一个高质量的强化学习模型。

想要查看当前 Gym 库已经注册了哪些环境，可以使用以下代码：

1
2
3
4

from gym import envs
env_specs = envs.registry.all()
envs_ids = [env_spec.id for env_spec in env_specs]
print(envs_ids)

每个环境都定义了自己的观测空间和动作空间。环境 env 的观测空间用env.observation_space表示，动作空间用 env.action_space表示。观测空间和动作空间既可以是离散空间（即取值是有限个离散的值），也可以是连续空间（即取值是连续的）。在 Gym 库中，离散空间一般用gym.spaces.Discrete类表示，连续空间用gym.spaces.Box类表示。

例如，环境'MountainCar-v0'的观测空间是Box(2,)，表示观测可以用 2 个 float 值表示；环境'MountainCar-v0'的动作空间是Dicrete(3)，表示动作取值自{0,1,2}。对于离散空间，gym.spaces.Discrete类实例的成员 n 表示有几个可能的取值；对于连续空间，Box类实例的成员 low 和 high 表示每个浮点数的取值范围。

MountainCar-v0 Example

接下来，我们通过一个例子来学习如何与 Gym 库进行交互。我们选取 小车上山(MountainCar-v0)作为例子。

首先我们来看看这个任务的观测空间和动作空间：

1
2
3
4
5
6
7

import gym
env = gym.make('MountainCar-v0')
print('观测空间 = {}'.format(env.observation_space))
print('动作空间 = {}'.format(env.action_space))
print('观测范围 = {} ~ {}'.format(env.observation_space.low,
        env.observation_space.high))
print('动作数 = {}'.format(env.action_space.n))

输出：

1
2
3
4

观测空间 = Box(2,)
动作空间 = Discrete(3)
观测范围 = [-1.2  -0.07] ~ [0.6  0.07]
动作数 = 3

由输出可知，观测空间是形状为 (2,) 的浮点型 np.array，动作空间是取 {0,1,2} 的 int 型数值。

接下来考虑智能体。智能体往往是我们自己实现的。我们可以实现一个智能体类：BespokeAgent类，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class BespokeAgent:
    def __init__(self, env):
        pass
    
    def decide(self, observation): # 决策
        position, velocity = observation
        lb = min(-0.09 * (position + 0.25) ** 2 + 0.03,
                0.3 * (position + 0.9) ** 4 - 0.008)
        ub = -0.07 * (position + 0.38) ** 2 + 0.07
        if lb < velocity < ub:
            action = 2
        else:
            action = 0
        return action # 返回动作

    def learn(self, *args): # 学习
        pass
    
agent = BespokeAgent(env)

智能体的 decide() 方法实现了决策功能，而 learn() 方法实现了学习功能。BespokeAgent类是一个比较简单的类，它只能根据给定的数学表达式进行决策，不能有效学习。所以它并不是一个真正意义上的强化学习智能体类。但是，用于演示智能体和环境的交互已经足够了。

接下来我们试图让智能体与环境交互，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def play_montecarlo(env, agent, render=False, train=False):
    episode_reward = 0. # 记录回合总奖励，初始化为0
    observation = env.reset() # 重置游戏环境，开始新回合
    while True: # 不断循环，直到回合结束
        if render: # 判断是否显示
            env.render() # 显示图形界面，图形界面可以用 env.close() 语句关闭
        action = agent.decide(observation)
        next_observation, reward, done, _ = env.step(action) # 执行动作
        episode_reward += reward # 收集回合奖励
        if train: # 判断是否训练智能体
            agent.learn(observation, action, reward, done) # 学习
        if done: # 回合结束，跳出循环
            break
        observation = next_observation
    return episode_reward # 返回回合总奖励

上面代码中的 play_montecarlo 函数可以让智能体和环境交互一个回合。这个函数有 4 个参数：

• env 是环境类
• agent 是智能体类
• render是 bool 类型变量，指示在运行过程中是否要图形化显示。如果函数参数 render为 True，那么在交互过程中会调用 env.render() 以显示图形化界面，而这个界面可以通过调用 env.close() 关闭。
• train是 bool 类型的变量，指示在运行过程中是否训练智能体。在训练过程中应当设置为 True，以调用 agent.learn() 函数；在测试过程中应当设置为 False，使得智能体不变。

这个函数有一个返回值 episode_reward，是 float 类型的数值，表示智能体与环境交互一个回合的回合总奖励。

接下来，我们使用下列代码让智能体和环境交互一个回合，并在交互过程中图形化显示，可用 env.close() 语句关闭图形化界面。

1
2
3
4

env.seed(0) # 设置随机数种子,只是为了让结果可以精确复现,一般情况下可删去
episode_reward = play_montecarlo(env, agent, render=True)
print('回合奖励 = {}'.format(episode_reward))
env.close() # 此语句可关闭图形界面

输出：

1

回合奖励 = -105.0

为了系统评估智能体的性能，下列代码求出了连续交互 100 回合的平均回合奖励。

1
2

episode_rewards = [play_montecarlo(env, agent) for _ in range(100)]
print('平均回合奖励 = {}'.format(np.mean(episode_rewards)))

输出：

1

平均回合奖励 = -102.61

小车上山环境有一个参考的回合奖励值 -110，如果当连续 100 个回合的平均回合奖励大于 -110，则认为这个任务被解决了。BespokeAgent 类对应的策略的平均回合奖励大概就在 -110 左右。

测试 agent 在 Gym 库中某个任务的性能时，学术界一般最关心 100 个回合的平均回合奖励。至于为什么是 100 个回合而不是其他回合数（比如 128 个回合），完全是习惯使然，没有什么特别的原因。对于有些环境，还会指定一个参考的回合奖励值，当连续 100 个回合的奖励大于指定的值时，就认为这个任务被解决了。但是，并不是所有的任务都指定了这样的值。对于没有指定值的任务，就无所谓任务被解决了或者没有被解决。

总结一下 Gym 的用法：使用 env=gym.make(环境名) 取出环境，使用 env.reset()初始化环境，使用env.step(动作)执行一步环境，使用 env.render()显示环境，使用 env.close() 关闭环境。

最后提一下，Gym 有对应的官方文档，大家可以阅读文档来学习 Gym。

References

• 百面深度学习

• 强化学习：原理与Python实现

• 强化学习基础 David Silver 笔记

• David Silver 强化学习公开课中文讲解及实践

• UCL Course on RL(David Silver)

• 白话强化学习与PyTorch

• OpenAI Spinning Up

• 神经网络与深度学习

• 机器学习

使用Q-learning解决悬崖寻路问题

强化学习在运动规划方面也有很大的应用前景，具体包括路径规划与决策，智能派单等等，本次项目就将单体运动规划抽象并简化，让大家初步认识到强化学习在这方面的应用。在运动规划方面，其实已有很多适用于强化学习的仿真环境，小到迷宫，大到贴近真实的自动驾驶环境CARLA，对这块感兴趣的童鞋可以再多搜集一点。本项目采用gym开发的CliffWalking-v0环境，在上面实现一个简单的Q-learning入门demo。

CliffWalking-v0环境简介

首先对该环境做一个简介，该环境中文名称叫悬崖寻路问题（CliffWalking），是指在一个4 x 12的网格中，智能体以网格的左下角位置为起点，以网格的下角位置为终点，目标是移动智能体到达终点位置，智能体每次可以在上、下、左、右这4个方向中移动一步，每移动一步会得到-1单位的奖励。

如图，红色部分表示悬崖，数字代表智能体能够观测到的位置信息，即observation，总共会有0-47等48个不同的值，智能体再移动中会有以下限制：

• 智能体不能移出网格，如果智能体想执行某个动作移出网格，那么这一步智能体不会移动，但是这个操作依然会得到-1单位的奖励

• 如果智能体“掉入悬崖” ，会立即回到起点位置，并得到-100单位的奖励

• 当智能体移动到终点时，该回合结束，该回合总奖励为各步奖励之和

实际的仿真界面如下：

由于从起点到终点最少需要13步，每步得到-1的reward，因此最佳训练算法下，每个episode下reward总和应该为-13。所以我们的目标也是要通过RL训练出一个模型，使得该模型能在测试中一个episode的reward能够接近于-13左右。

RL基本训练接口

以下是强化学习算法的基本接口，也就是一个完整的上层训练模式，首先是初始化环境和智能体，然后每个episode中，首先agent选择action给到环境，然后环境反馈出下一个状态和reward，然后agent开始更新或者学习，如此多个episode之后agent开始收敛并保存模型。其中可以通过可视化reward随每个episode的变化来查看训练的效果。另外由于强化学习的不稳定性，在收敛的状态下也可能会有起伏的情况，此时可以使用滑动平均的reward让曲线更加平滑便于分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  '''初始化环境'''  
env = gym.make("CliffWalking-v0")  # 0 up, 1 right, 2 down, 3 left
env = CliffWalkingWapper(env)
agent = QLearning(
    state_dim=env.observation_space.n,
    action_dim=env.action_space.n,
    learning_rate=cfg.policy_lr,
    gamma=cfg.gamma,
rewards = []  
ma_rewards = [] # moving average reward
for i_ep in range(cfg.train_eps): # train_eps: 训练的最大episodes数
    ep_reward = 0  # 记录每个episode的reward
    state = env.reset()  # 重置环境, 重新开一局（即开始新的一个episode）
    while True:
        action = agent.choose_action(state)  # 根据算法选择一个动作
        next_state, reward, done, _ = env.step(action)  # 与环境进行一次动作交互
        agent.update(state, action, reward, next_state, done)  # Q-learning算法更新
        state = next_state  # 存储上一个观察值
        ep_reward += reward
        if done:
            break
    rewards.append(ep_reward)
    if ma_rewards:
        ma_rewards.append(ma_rewards[-1]*0.9+ep_reward*0.1)
    else:
        ma_rewards.append(ep_reward)
    print("Episode:{}/{}: reward:{:.1f}".format(i_ep+1, cfg.train_eps,ep_reward))

任务要求

基于以上的目标，本次任务即使训练并绘制reward以及滑动平均后的reward随episode的变化曲线图并记录超参数写成报告，示例如下：

主要代码清单

main.py 或 task_train.py：保存强化学习基本接口，以及相应的超参数

agent.py: 保存算法模型，主要包含choose_action(预测动作)和update两个函数，有时会多一个predict_action函数，此时choose_action使用了epsilon-greedy策略便于训练的探索，而测试时用predict_action单纯贪心地选择网络的值输出动作

model.py：保存神经网络，比如全连接网络等等，对于一些算法，分为Actor和Critic两个类

memory.py：保存replay buffer，根据算法的不同，replay buffer功能有所不同，因此会改写

plot.py：保存相关绘制函数

参考代码

备注

• 注意 \(\varepsilon\)-greedy 策略的使用，以及相应的参数\(\varepsilon\)如何衰减

• 训练模型和测试模型的时候选择动作有一些不同，训练时采取 \(\varepsilon\)-greedy策略，而测试时直接选取Q值最大对应的动作，所以算法在动作选择的时候会包括sample(训练时的动作采样)和predict(测试时的动作选择)

• Q值最大对应的动作可能不止一个，此时可以随机选择一个输出结果

Chapter3 表格型方法

1 Keywords

• P函数和R函数： P函数反应的是状态转移的概率，即反应的环境的随机性，R函数就是Reward function。但是我们通常处于一个未知的环境（即P函数和R函数是未知的）。
• Q表格型表示方法： 表示形式是一种表格形式，其中横坐标为 action（agent）的行为，纵坐标是环境的state，其对应着每一个时刻agent和环境的情况，并通过对应的reward反馈去做选择。一般情况下，Q表格是一个已经训练好的表格，不过，我们也可以每进行一步，就更新一下Q表格，然后用下一个状态的Q值来更新这个状态的Q值（即时序差分方法）。
• 时序差分（Temporal Difference）： 一种Q函数（Q值）的更新方式，也就是可以拿下一步的 Q 值 \(Q(S_{t+_1},A_{t+1})\) 来更新我这一步的 Q 值 \(Q(S_t,A_t)\) 。完整的计算公式如下：\(Q(S_t,A_t) \larr Q(S_t,A_t) + \alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]\)
• SARSA算法： 一种更新前一时刻状态的单步更新的强化学习算法，也是一种on-policy策略。该算法由于每次更新值函数需要知道前一步的状态(state)，前一步的动作(action)、奖励(reward)、当前状态(state)、将要执行的动作(action)，即 \((S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})\) 这几个值，所以被称为SARSA算法。agent每进行一次循环，都会用 \((S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})\) 对于前一步的Q值（函数）进行一次更新。

2 Questions

• 构成强化学习MDP的四元组有哪些变量？

  答：状态、动作、状态转移概率和奖励，分别对应（S，A，P，R），后面有可能会加上个衰减因子构成五元组。

• 基于以上的描述所构成的强化学习的“学习”流程。

  答：强化学习要像人类一样去学习了，人类学习的话就是一条路一条路的去尝试一下，先走一条路，我看看结果到底是什么。多试几次，只要能一直走下去的，我们其实可以慢慢的了解哪个状态会更好。我们用价值函数 \(V(s)\) 来代表这个状态是好的还是坏的。然后用这个 Q 函数来判断说在什么状态下做什么动作能够拿到最大奖励，我们用 Q 函数来表示这个状态-动作值。

• 基于SARSA算法的agent的学习过程。

  答：我们现在有环境，有agent。每交互一次以后，我们的agent会向环境输出action，接着环境会反馈给agent当前时刻的state和reward。那么agent此时会实现两个方法：

  1.使用已经训练好的Q表格，对应环境反馈的state和reward选取对应的action进行输出。

  2.我们已经拥有了\((S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})\) 这几个值，并直接使用 \(A_{t+1}\) 去更新我们的Q表格。

• Q-learning和Sarsa的区别？

  答：Sarsa算法是Q-learning算法的改进。（这句话出自「神经网络与深度学习」的第 342 页）（可参考SARSA「on-line q-learning using connectionist systems」的 abstract 部分）

  1. 首先，Q-learning 是 off-policy 的时序差分学习方法，Sarsa 是 on-policy 的时序差分学习方法。

  2. 其次，Sarsa 在更新 Q 表格的时候，它用到的 A' 。我要获取下一个 Q 值的时候，A' 是下一个 step 一定会执行的 action 。这个 action 有可能是 \(\varepsilon\)-greddy 方法 sample 出来的值，也有可能是 max Q 对应的 action，也有可能是随机动作。但是就是它实实在在执行了的那个动作。

  3. 但是 Q-learning 在更新 Q 表格的时候，它用到这个的 Q 值 \(Q(S',a')\) 对应的那个 action ，它不一定是下一个 step 会执行的实际的 action，因为你下一个实际会执行的那个 action 可能会探索。Q-learning 默认的 action 不是通过 behavior policy 来选取的，它是默认 A' 为最优策略选的动作，所以 Q-learning 在学习的时候，不需要传入 A'，即 \(a_{t+1}\) 的值。

  4. 更新公式的对比（区别只在target计算这一部分）：

     • Sarsa的公式： \(R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})\) ；
     • Q-learning的公式：\(R_{t+1}+\gamma \underset{a}{\max} Q\left(S_{t+1}, a\right)\)

     Sarsa 实际上都是用自己的策略产生了 S,A,R,S',A' 这一条轨迹。然后拿着 \(Q(S_{t+1},A_{t+1})\) 去更新原本的 Q 值 \(Q(S_t,A_t)\)。 但是 Q-learning 并不需要知道，我实际上选择哪一个 action ，它默认下一个动作就是 Q 最大的那个动作。所以基于此，Sarsa的action通常会更加“保守”、“胆小”，而对应的Q-Learning的action会更加“莽撞”、“激进”。

• On-policy和 off-policy 的区别？

  答：

  1. Sarsa 就是一个典型的 on-policy 策略，它只用一个 \(\pi\) ，为了兼顾探索和利用，所以它训练的时候会显得有点胆小怕事。它在解决悬崖问题的时候，会尽可能地离悬崖边上远远的，确保说哪怕自己不小心探索了一点了，也还是在安全区域内不不至于跳进悬崖。
  2. Q-learning 是一个比较典型的 off-policy 的策略，它有目标策略 target policy，一般用 \(\pi\) 来表示。然后还有行为策略 behavior policy，用 \(\mu\) 来表示。它分离了目标策略跟行为策略。Q-learning 就可以大胆地用 behavior policy 去探索得到的经验轨迹来去优化我的目标策略。这样子我更有可能去探索到最优的策略。
  3. 比较 Q-learning 和 Sarsa 的更新公式可以发现，Sarsa 并没有选取最大值的 max 操作。因此，Q-learning 是一个非常激进的算法，希望每一步都获得最大的利益；而 Sarsa 则相对非常保守，会选择一条相对安全的迭代路线。

3 Something About Interview

• 高冷的面试官：同学，你能否简述on-policy和off-policy的区别？

  答： off-policy和on-policy的根本区别在于生成样本的policy和参数更新时的policy是否相同。对于on-policy，行为策略和要优化的策略是一个策略，更新了策略后，就用该策略的最新版本对于数据进行采样；对于off-policy，使用任意的一个行为策略来对于数据进行采样，并利用其更新目标策略。如果举例来说，Q-learning在计算下一状态的预期收益时使用了max操作，直接选择最优动作，而当前policy并不一定能选择到最优的action，因此这里生成样本的policy和学习时的policy不同，所以Q-learning为off-policy算法；相对应的SARAS则是基于当前的policy直接执行一次动作选择，然后用这个样本更新当前的policy，因此生成样本的policy和学习时的policy相同，所以SARAS算法为on-policy算法。

• 高冷的面试官：小同学，能否讲一下Q-Learning，最好可以写出其 \(Q(s,a)\) 的更新公式。另外，它是on-policy还是off-policy，为什么？

  答： Q-learning是通过计算最优动作值函数来求策略的一种时序差分的学习方法，其更新公式为： \[ Q(s, a) \larr Q(s, a) + \alpha [r(s,a) + \gamma \max_{a'} Q(s', a') - Q(s, a)] \] 其是off-policy的，由于是Q更新使用了下一个时刻的最大值，所以我们只关心哪个动作使得 \(Q(s_{t+1}, a)\) 取得最大值，而实际到底采取了哪个动作（行为策略），并不关心。这表明优化策略并没有用到行为策略的数据，所以说它是 off-policy 的。

• 高冷的面试官：小朋友，能否讲一下SARSA，最好可以写出其Q(s,a)的更新公式。另外，它是on-policy还是off-policy，为什么？

  答：SARSA可以算是Q-learning的改进（这句话出自「神经网络与深度学习」的第 342 页）（可参考SARSA「on-line q-learning using connectionist systems」的 abstract 部分），其更新公式为： \[ Q(s, a) \larr Q(s, a) + \alpha [r(s,a) + \gamma Q(s', a') - Q(s, a)] \] 其为on-policy的，SARSA必须执行两次动作得到 $(s,a,r,s',a') $才可以更新一次；而且 \(a'\) 是在特定策略 \(\pi\) 的指导下执行的动作，因此估计出来的 \(Q(s,a)\) 是在该策略 \(\pi\) 之下的Q-value，样本生成用的 \(\pi\) 和估计的 \(\pi\) 是同一个，因此是on-policy。

• 高冷的面试官：请问value-based和policy-based的区别是什么？

  答：

  1. 生成policy上的差异：前者确定，后者随机。Value-Base中的 action-value估计值最终会收敛到对应的true values（通常是不同的有限数，可以转化为0到1之间的概率），因此通常会获得一个确定的策略（deterministic policy）；而Policy-Based不会收敛到一个确定性的值，另外他们会趋向于生成optimal stochastic policy。如果optimal policy是deterministic的，那么optimal action对应的性能函数将远大于suboptimal actions对应的性能函数，性能函数的大小代表了概率的大小。
  2. 动作空间是否连续，前者离散，后者连续。Value-Base，对于连续动作空间问题，虽然可以将动作空间离散化处理，但离散间距的选取不易确定。过大的离散间距会导致算法取不到最优action，会在这附近徘徊，过小的离散间距会使得action的维度增大，会和高维度动作空间一样导致维度灾难，影响算法的速度；而Policy-Based适用于连续的动作空间，在连续的动作空间中，可以不用计算每个动作的概率，而是通过Gaussian distribution （正态分布）选择action。
  3. value-based，例如Q-learning，是通过求解最优值函数间接的求解最优策略；policy-based，例如REINFORCE，Monte-Carlo Policy Gradient，等方法直接将策略参数化，通过策略搜索，策略梯度或者进化方法来更新策略的参数以最大化回报。基于值函数的方法不易扩展到连续动作空间，并且当同时采用非线性近似、自举和离策略时会有收敛性问题。策略梯度具有良好的收敛性证明。
  4. 补充：对于值迭代和策略迭代：策略迭代。它有两个循环，一个是在策略估计的时候，为了求当前策略的值函数需要迭代很多次。另外一个是外面的大循环，就是策略评估，策略提升这个循环。值迭代算法则是一步到位，直接估计最优值函数，因此没有策略提升环节。

• 高冷的面试官：请简述以下时序差分(Temporal Difference，TD)算法。

  答：TD算法是使用广义策略迭代来更新Q函数的方法，核心使用了自举（bootstrapping），即值函数的更新使用了下一个状态的值函数来估计当前状态的值。也就是使用下一步的 \(Q\) 值 \(Q(S_{t+1},A_{t+1})\) 来更新我这一步的 Q 值 $Q(S_t,A_t) \(。完整的计算公式如下：\)$ Q(S_t,A_t) Q(S_t,A_t) + $$

• 高冷的面试官：请问蒙特卡洛方法（Monte Carlo Algorithm，MC）和时序差分(Temporal Difference，TD)算法是无偏估计吗？另外谁的方法更大呢？为什么呢？

  答：蒙特卡洛方法（MC）是无偏估计，时序差分（TD）是有偏估计；MC的方差较大，TD的方差较小，原因在于TD中使用了自举（bootstrapping）的方法，实现了基于平滑的效果，导致估计的值函数的方差更小。

• 高冷的面试官：能否简单说下动态规划、蒙特卡洛和时序差分的异同点？

  答：

  • 相同点：都用于进行值函数的描述与更新，并且所有方法都是基于对未来事件的展望来计算一个回溯值。

  • 不同点：蒙特卡洛和TD算法隶属于model-free，而动态规划属于model-based；TD算法和蒙特卡洛的方法，因为都是基于model-free的方法，因而对于后续状态的获知也都是基于试验的方法；TD算法和动态规划的策略评估，都能基于当前状态的下一步预测情况来得到对于当前状态的值函数的更新。

    另外，TD算法不需要等到实验结束后才能进行当前状态的值函数的计算与更新，而蒙特卡洛的方法需要试验交互，产生一整条的马尔科夫链并直到最终状态才能进行更新。TD算法和动态规划的策略评估不同之处为model-free和model-based 这一点，动态规划可以凭借已知转移概率就能推断出来后续的状态情况，而TD只能借助试验才能知道。

    蒙特卡洛方法和TD方法的不同在于，蒙特卡洛方法进行完整的采样来获取了长期的回报值，因而在价值估计上会有着更小的偏差，但是也正因为收集了完整的信息，所以价值的方差会更大，原因在于毕竟基于试验的采样得到，和真实的分布还是有差距，不充足的交互导致的较大方差。而TD算法与其相反，因为只考虑了前一步的回报值 其他都是基于之前的估计值，因而相对来说，其估计值具有偏差大方差小的特点。

  • 三者的联系：对于\(TD(\lambda)\)方法，如果 $ = 0$ ，那么此时等价于TD，即只考虑下一个状态；如果$ = 1$，等价于MC，即考虑 \(T-1\) 个后续状态即到整个episode序列结束。

Tabular Methods

本章我们通过最简单的表格型的方法(tabular methods)来讲解如何使用 value-based 方法去求解强化学习。

MDP

强化学习的三个重要的要素：状态、动作和奖励。强化学习智能体跟环境是一步一步交互的，就是我先观察一下状态，然后再输入动作。再观察一下状态，再输出动作，拿到这些 reward 。它是一个跟时间相关的序列决策的问题。

举个例子，在 \(t-1\) 时刻，我看到了熊对我招手，那我下意识的可能输出的动作就是赶紧跑路。熊看到了有人跑了，可能就觉得发现猎物，开始发动攻击。而在 \(t\) 时刻的话，我如果选择装死的动作，可能熊咬了咬我，摔了几下就发现就觉得挺无趣的，可能会走开。这个时候，我再跑路的话可能就跑路成功了，就是这样子的一个序列决策的过程。

当然在输出每一个动作之前，你可以选择不同的动作。比如说在 \(t\) 时刻，我选择跑路的时候，熊已经追上来了，如果说 \(t\) 时刻，我没有选择装死，而我是选择跑路的话，这个时候熊已经追上了，那这个时候，其实我有两种情况转移到不同的状态去，就我有一定的概率可以逃跑成功，也有很大的概率我会逃跑失败。那我们就用状态转移概率 \(p\left[s_{t+1}, r_{t} \mid s_{t}, a_{t}\right]\) 来表述说在 \(s_t\) 的状态选择了 \(a_t\) 的动作的时候，转移到 \(s_{t+1}\) ，而且拿到 \(r_t\) 的概率是多少。

这样子的一个状态转移概率是具有马尔可夫性质的(系统下一时刻的状态仅由当前时刻的状态决定，不依赖于以往任何状态)。因为这个状态转移概率，它是下一时刻的状态是取决于当前的状态，它和之前的 \(s_{t-1}\) 和 \(s_{t-2}\) 都没有什么关系。然后再加上这个过程也取决于智能体跟环境交互的这个 \(a_t\) ，所以有一个决策的一个过程在里面。我们就称这样的一个过程为马尔可夫决策过程(Markov Decision Process, MDP)。

MDP 就是序列决策这样一个经典的表达方式。MDP 也是强化学习里面一个非常基本的学习框架。状态、动作、状态转移概率和奖励 \((S,A,P,R)\)，这四个合集就构成了强化学习 MDP 的四元组，后面也可能会再加个衰减因子构成五元组。

Model-based

如上图所示，我们把这些可能的动作和可能的状态转移的关系画成一个树状图。它们之间的关系就是从 \(s_t\) 到 \(a_t\) ，再到 \(s_{t+1}\) ，再到 \(a_{t+1}\)，再到 \(s_{t+2}\) 这样子的一个过程。

我们去跟环境交互，只能走完整的一条通路。这里面产生了一系列的一个决策的过程，就是我们跟环境交互产生了一个经验。我们会使用 概率函数(probability function)和 奖励函数(reward function)来去描述环境。概率函数就是状态转移的概率，概率函数实际上反映的是环境的一个随机性。

当我们知道概率函数和奖励函数时，我们就说这个 MDP 是已知的，可以通过 policy iteration 和 value iteration 来找最佳的策略。

比如，在熊发怒的情况下，我如果选择装死，假设熊看到人装死就一定会走的话，我们就称在这里面的状态转移概率就是 100%。但如果说在熊发怒的情况下，我选择跑路而导致可能跑成功以及跑失败，出现这两种情况。那我们就可以用概率去表达一下说转移到其中一种情况的概率大概 10%，另外一种情况的概率大概是 90% 会跑失败。

如果知道这些状态转移概率和奖励函数的话，我们就说这个环境是已知的，因为我们是用这两个函数去描述环境的。如果是已知的话，我们其实可以用动态规划去计算说，如果要逃脱熊，那么能够逃脱熊概率最大的最优策略是什么。很多强化学习的经典算法都是 model-free 的，就是环境是未知的。

Model-free

因为现实世界中人类第一次遇到熊之前，我们根本不知道能不能跑得过熊，所以刚刚那个 10%、90% 的概率也就是虚构出来的概率。熊到底在什么时候会往什么方向去转变的话，我们经常是不知道的。

我们是处在一个未知的环境里的，也就是这一系列的决策的概率函数和奖励函数是未知的，这就是 model-based 跟 model-free 的一个最大的区别。

强化学习就是可以用来解决用完全未知的和随机的环境。强化学习要像人类一样去学习，人类学习的话就是一条路一条路地去尝试一下，先走一条路，看看结果到底是什么。多试几次，只要能活命的。我们可以慢慢地了解哪个状态会更好，

• 我们用价值函数 \(V(s)\) 来代表这个状态是好的还是坏的。
• 用 Q 函数来判断说在什么状态下做什么动作能够拿到最大奖励，用 Q 函数来表示这个状态-动作值。

Model-based vs. Model-free

• Policy iteration 和 value iteration 都需要得到环境的转移和奖励函数，所以在这个过程中，agent 没有跟环境进行交互。
• 在很多实际的问题中，MDP 的模型有可能是未知的，也有可能模型太大了，不能进行迭代的计算。比如 Atari 游戏、围棋、控制直升飞机、股票交易等问题，这些问题的状态转移太复杂了。

• 在这种情况下，我们使用 model-free 强化学习的方法来解。
• Model-free 没有获取环境的状态转移和奖励函数，我们让 agent 跟环境进行交互，采集到很多的轨迹数据，agent 从轨迹中获取信息来改进策略，从而获得更多的奖励。

Q-table

接下来介绍下 Q 函数。在多次尝试和熊打交道之后，人类就可以对熊的不同的状态去做出判断，我们可以用状态动作价值来表达说在某个状态下，为什么动作 1 会比动作 2 好，因为动作 1 的价值比动作 2 要高，这个价值就叫 Q 函数。

如果 Q 表格是一张已经训练好的表格的话，那这一张表格就像是一本生活手册。我们就知道在熊发怒的时候，装死的价值会高一点。在熊离开的时候，我们可能偷偷逃跑的会比较容易获救。

这张表格里面 Q 函数的意义就是我选择了这个动作之后，最后面能不能成功，就是我需要去计算在这个状态下，我选择了这个动作，后续能够一共拿到多少总收益。如果可以预估未来的总收益的大小，我们当然知道在当前的这个状态下选择哪个动作，价值更高。我选择某个动作是因为我未来可以拿到的那个价值会更高一点。所以强化学习的目标导向性很强，环境给出的奖励是一个非常重要的反馈，它就是根据环境的奖励来去做选择。

Q: 为什么可以用未来的总收益来评价当前这个动作是好是坏?

A: 举个例子，假设一辆车在路上，当前是红灯，我们直接走的收益就很低，因为违反交通规则，这就是当前的单步收益。可是如果我们这是一辆救护车，我们正在运送病人，把病人快速送达医院的收益非常的高，而且越快你的收益越大。在这种情况下，我们很可能应该要闯红灯，因为未来的远期收益太高了。这也是为什么强化学习需要去学习远期的收益，因为在现实世界中奖励往往是延迟的。所以我们一般会从当前状态开始，把后续有可能会收到所有收益加起来计算当前动作的 Q 的价值，让 Q 的价值可以真正地代表当前这个状态下，动作的真正的价值。

但有的时候把目光放得太长远不好，因为如果事情很快就结束的话，你考虑到最后一步的收益无可厚非。如果是一个持续的没有尽头的任务，即持续式任务(Continuing Task)，你把未来的收益全部相加，作为当前的状态价值就很不合理。

股票的例子就很典型了，我们要关注的是累积的收益。可是如果说十年之后才有一次大涨大跌，你显然不会把十年后的收益也作为当前动作的考虑因素。那我们会怎么办呢，有句俗话说得好，对远一点的东西，我们就当做近视，就不需要看得太清楚，我们可以引入这个衰减因子 \(\gamma\) 来去计算这个未来总收益，\(\gamma \in [0,1]\)，越往后 \(\gamma^n\) 就会越小，也就是说越后面的收益对当前价值的影响就会越小。

举个例子来看看计算出来的是什么效果。这是一个悬崖问题，这个问题是需要智能体从出发点 S 出发，到达目的地 G，同时避免掉进悬崖(cliff)，掉进悬崖的话就会有 -100 分的惩罚，但游戏不会结束，它会被直接拖回起点，游戏继续。为了到达目的地，我们可以沿着蓝线和红线走。

在这个环境当中，我们怎么去计算状态动作价值(未来的总收益)。

• 如果 \(\gamma = 0\)， 假设我走一条路，并从这个状态出发，在这里选择是向上，这里选择向右。如果 \(\gamma = 0\)，用这个公式去计算的话，它相当于考虑的就是一个单步的收益。我们可以认为它是一个目光短浅的计算的方法。

• 如果 \(\gamma = 1\)，那就等于是说把后续所有的收益都全部加起来。在这里悬崖问题，你每走一步都会拿到一个 -1 分的 reward，只有到了终点之后，它才会停止。如果 $ $ 的话，我们用这个公式去计算，就这里是 -1。然后这里的话，未来的总收益就是 \(-1+-1=-2\) 。

• 如果 \(\gamma = 0.6\)，就是目光没有放得那么的长远，计算出来是这个样子的。利用 \(G_{t}=R_{t+1}+\gamma G_{t+1}\) 这个公式从后往前推。

\[ \begin{array}{l} G_{7}=R+\gamma G_{8}=-1+0.6 *(-2.176)=-2.3056 \approx-2.3 \\ G_{8}=R+\gamma G_{9}=-1+0.6 *(-1.96)=-2.176 \approx-2.18 \\ G_{9}=R+\gamma G_{10}=-1+0.6 *(-1.6)=-1.96 \\ G_{10}=R+\gamma G_{11}=-1+0.6 *(-1)=-1.6 \\ G_{12}=R+\gamma G_{13}=-1+0.6 * 0=-1 \\ G_{13}=0 \end{array} \]

这里的计算是我们选择了一条路，计算出这条路径上每一个状态动作的价值。我们可以看一下右下角这个图，如果说我走的不是红色的路，而是蓝色的路，那我算出来的 Q 值可能是这样。那我们就知道，当小乌龟在 -12 这个点的时候，往右边走是 -11，往上走是 -15，它自然就知道往右走的价值更大，小乌龟就会往右走。

类似于上图，最后我们要求解的就是一张 Q 表格，

• 它的行数是所有的状态数量，一般可以用坐标来表示表示格子的状态，也可以用 1、2、3、4、5、6、7 来表示不同的位置。
• Q 表格的列表示上下左右四个动作。

最开始这张 Q 表格会全部初始化为零，然后 agent 会不断地去和环境交互得到不同的轨迹，当交互的次数足够多的时候，我们就可以估算出每一个状态下，每个行动的平均总收益去更新这个 Q 表格。怎么去更新 Q 表格就是接下来要引入的强化概念。

强化就是我们可以用下一个状态的价值来更新当前状态的价值，其实就是强化学习里面 bootstrapping 的概念。在强化学习里面，你可以每走一步更新一下 Q 表格，然后用下一个状态的 Q 值来更新这个状态的 Q 值，这种单步更新的方法叫做时序差分。

Model-free Prediction

在没法获取 MDP 的模型情况下，我们可以通过以下两种方法来估计某个给定策略的价值：

• Monte Carlo policy evaluation
• Temporal Difference(TD) learning

Monte-Carlo Policy Evaluation

• 蒙特卡罗(Monte-Carlo，MC)方法是基于采样的方法，我们让 agent 跟环境进行交互，就会得到很多轨迹。每个轨迹都有对应的 return：

\[ G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \]

• 我们把每个轨迹的 return 进行平均，就可以知道某一个策略下面对应状态的价值。

• MC 是用 经验平均回报(empirical mean return) 的方法来估计。

• MC 方法不需要 MDP 的转移函数和奖励函数，并且不需要像动态规划那样用 bootstrapping 的方法。

• MC 的局限性：只能用在有终止的 MDP 。

• 上图是 MC 算法的概括。
• 为了得到评估 \(v(s)\)，我们进行了如下的步骤：
  • 在每个回合中，如果在时间步 t 状态 s 被访问了，那么
    • 状态 s 的访问数 \(N(s)\) 增加 1，
    • 状态 s 的总的回报 \(S(s)\) 增加 \(G_t\)。
  • 状态 s 的价值可以通过 return 的平均来估计，即 \(v(s)=S(s)/N(s)\)。
• 根据大数定律，只要我们得到足够多的轨迹，就可以趋近这个策略对应的价值函数。

假设现在有样本 \(x_1,x_2,\cdots\)，我们可以把经验均值(empirical mean)转换成 增量均值(incremental mean) 的形式，如下式所示： \[ \begin{aligned} \mu_{t} &=\frac{1}{t} \sum_{j=1}^{t} x_{j} \\ &=\frac{1}{t}\left(x_{t}+\sum_{j=1}^{t-1} x_{j}\right) \\ &=\frac{1}{t}\left(x_{t}+(t-1) \mu_{t-1}\right) \\ &=\frac{1}{t}\left(x_{t}+t \mu_{t-1}-\mu_{t-1}\right) \\ &=\mu_{t-1}+\frac{1}{t}\left(x_{t}-\mu_{t-1}\right) \end{aligned} \] 通过这种转换，我们就可以把上一时刻的平均值跟现在时刻的平均值建立联系，即： \[ \mu_t = \mu_{t-1}+\frac{1}{t}(x_t-\mu_{t-1}) \] 其中：

• \(x_t- \mu_{t-1}\) 是残差
• \(\frac{1}{t}\) 类似于学习率(learning rate)

当我们得到 \(x_t\)，就可以用上一时刻的值来更新现在的值。

我们可以把 Monte-Carlo 更新的方法写成 incremental MC 的方法：

• 我们采集数据，得到一个新的轨迹。
• 对于这个轨迹，我们采用增量的方法进行更新，如下式所示：

\[ \begin{array}{l} N\left(S_{t}\right) \leftarrow N\left(S_{t}\right)+1 \\ v\left(S_{t}\right) \leftarrow v\left(S_{t}\right)+\frac{1}{N\left(S_{t}\right)}\left(G_{t}-v\left(S_{t}\right)\right) \end{array} \]

• 我们可以直接把 \(\frac{1}{N(S_t)}\) 变成 \(\alpha\) (学习率)，\(\alpha\) 代表着更新的速率有多快，我们可以进行设置。

我们再来看一下 DP 和 MC 方法的差异。

• 动态规划也是常用的估计价值函数的方法。在动态规划里面，我们使用了 bootstrapping 的思想。bootstrapping 的意思就是我们基于之前估计的量来估计一个量。

• DP 就是用 Bellman expectation backup，就是通过上一时刻的值 \(v_{i-1}(s')\) 来更新当前时刻 \(v_i(s)\) 这个值，不停迭代，最后可以收敛。Bellman expectation backup 就有两层加和，内部加和和外部加和，算了两次 expectation，得到了一个更新。

MC 是通过 empirical mean return （实际得到的收益）来更新它，对应树上面蓝色的轨迹，我们得到是一个实际的轨迹，实际的轨迹上的状态已经是决定的，采取的行为都是决定的。MC 得到的是一条轨迹，这条轨迹表现出来就是这个蓝色的从起始到最后终止状态的轨迹。现在只是更新这个轨迹上的所有状态，跟这个轨迹没有关系的状态都没有更新。

• MC 可以在不知道环境的情况下 work，而 DP 是 model-based。
• MC 只需要更新一条轨迹的状态，而 DP 则是需要更新所有的状态。状态数量很多的时候（比如一百万个，两百万个），DP 这样去迭代的话，速度是非常慢的。这也是 sample-based 的方法 MC 相对于 DP 的优势。

Temporal Difference

为了让大家更好地理解时序差分(Temporal Difference,TD)这种更新方法，这边给出它的物理意义。我们先理解一下巴普洛夫的条件反射实验，这个实验讲的是小狗会对盆里面的食物无条件产生刺激，分泌唾液。一开始小狗对于铃声这种中性刺激是没有反应的，可是我们把这个铃声和食物结合起来，每次先给它响一下铃，再给它喂食物，多次重复之后，当铃声响起的时候，小狗也会开始流口水。盆里的肉可以认为是强化学习里面那个延迟的 reward，声音的刺激可以认为是有 reward 的那个状态之前的一个状态。多次重复实验之后，最后的这个 reward 会强化小狗对于这个声音的条件反射，它会让小狗知道这个声音代表着有食物，这个声音对于小狗来说也就有了价值，它听到这个声音也会流口水。

巴普洛夫效应揭示的是中性刺激(铃声)跟无条件刺激(食物)紧紧挨着反复出现的时候，中性刺激也可以引起无条件刺激引起的唾液分泌，然后形成条件刺激。

这种中性刺激跟无条件刺激在时间上面的结合，我们就称之为强化。 强化的次数越多，条件反射就会越巩固。小狗本来不觉得铃声有价值的，经过强化之后，小狗就会慢慢地意识到铃声也是有价值的，它可能带来食物。更重要是一种条件反射巩固之后，我们再用另外一种新的刺激和条件反射去结合，还可以形成第二级条件反射，同样地还可以形成第三级条件反射。

在人的身上是可以建立多级的条件反射的，举个例子，比如说一般我们遇到熊都是这样一个顺序：看到树上有熊爪，然后看到熊之后，突然熊发怒，扑过来了。经历这个过程之后，我们可能最开始看到熊才会瑟瑟发抖，后面就是看到树上有熊爪就已经有害怕的感觉了。也就说在不断的重复试验之后，下一个状态的价值，它是可以不断地去强化影响上一个状态的价值的。

为了让大家更加直观感受下一个状态影响上一个状态(状态价值迭代)，我们推荐这个网站：Temporal Difference Learning Gridworld Demo。

• 我们先初始化一下，然后开始时序差分的更新过程。
• 在训练的过程中，这个小黄球在不断地试错，在探索当中会先迅速地发现有奖励的地方。最开始的时候，只是这些有奖励的格子才有价值。当不断地重复走这些路线的时候，这些有价值的格子可以去慢慢地影响它附近的格子的价值。
• 反复训练之后，这些有奖励的格子周围的格子的状态就会慢慢地被强化。强化就是当它收敛到最后一个最优的状态了，这些价值最终收敛到一个最优的情况之后，那个小黄球就会自动地知道，就是我一直往价值高的地方走，就能够走到能够拿到奖励的地方。

下面开始正式介绍 TD 方法。

• TD 是介于 MC 和 DP 之间的方法。
• TD 是 model-free 的，不需要 MDP 的转移矩阵和奖励函数。
• TD 可以从不完整的 episode 中学习，结合了 bootstrapping 的思想。

• 上图是 TD 算法的框架。

• 目的：对于某个给定的策略，在线(online)地算出它的价值函数，即一步一步地(step-by-step)算。

• 最简单的算法是 TD(0)，每往前走一步，就做一步 bootstrapping，用得到的估计回报(estimated return)来更新上一时刻的值。

• 估计回报 \(R_{t+1}+\gamma v(S_{t+1})\) 被称为 TD target，TD target 是带衰减的未来收益的总和。TD target 由两部分组成：

  • 走了某一步后得到的实际奖励：\(R_{t+1}\)，
  • 我们利用了 bootstrapping 的方法，通过之前的估计来估计 \(v(S_{t+1})\) ，然后加了一个折扣系数，即 \(\gamma v(S_{t+1})\)，具体过程如下式所示：

  \[ \begin{aligned} v(s)&=\mathbb{E}\left[G_{t} \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}|s_t=s\right] +\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\ldots \mid s_{t}=s\right]\\ &=R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s] \\ &=R(s)+\gamma \mathbb{E}[v(s_{t+1})|s_t=s]\\ \end{aligned} \]

• TD目标是估计有两个原因：它对期望值进行采样，并且使用当前估计 V 而不是真实 \(v_{\pi}\)。

• TD error(误差) \(\delta=R_{t+1}+\gamma v(S_{t+1})-v(S_t)\)。

• 可以类比于 Incremental Monte-Carlo 的方法，写出如下的更新方法：

\[ v\left(S_{t}\right) \leftarrow v\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma v\left(S_{t+1}\right)-v\left(S_{t}\right)\right) \]

上式体现了强化这个概念。

• 我们对比下 MC 和 TD：
  • 在 MC 里面 \(G_{i,t}\) 是实际得到的值（可以看成 target），因为它已经把一条轨迹跑完了，可以算每个状态实际的 return。
  • TD 没有等轨迹结束，往前走了一步，就可以更新价值函数。

• TD 只执行了一步，状态的值就更新。
• MC 全部走完了之后，到了终止状态之后，再更新它的值。

接下来，进一步比较下 TD 和 MC。

• TD 可以在线学习(online learning)，每走一步就可以更新，效率高。

• MC 必须等游戏结束才可以学习。

• TD 可以从不完整序列上进行学习。

• MC 只能从完整的序列上进行学习。

• TD 可以在连续的环境下（没有终止）进行学习。

• MC 只能在有终止的情况下学习。

• TD 利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率。

• MC 没有假设环境具有马尔可夫性质，利用采样的价值来估计某一个状态的价值，在不是马尔可夫的环境下更加有效。

举个例子来解释 TD 和 MC 的区别，

• TD 是指在不清楚马尔可夫状态转移概率的情况下，以采样的方式得到不完整的状态序列，估计某状态在该状态序列完整后可能得到的收益，并通过不断地采样持续更新价值。
• MC 则需要经历完整的状态序列后，再来更新状态的真实价值。

例如，你想获得开车去公司的时间，每天上班开车的经历就是一次采样。假设今天在路口 A 遇到了堵车，

• TD 会在路口 A 就开始更新预计到达路口 B、路口 C \(\cdots \cdots\)，以及到达公司的时间；
• 而 MC 并不会立即更新时间，而是在到达公司后，再修改到达每个路口和公司的时间。

TD 能够在知道结果之前就开始学习，相比 MC，其更快速、灵活。

• 我们可以把 TD 进行进一步的推广。之前是只往前走一步，即 one-step TD，TD(0)。

• 我们可以调整步数，变成 n-step TD。比如 TD(2)，即往前走两步，然后利用两步得到的 return，使用 bootstrapping 来更新状态的价值。

• 这样就可以通过 step 来调整这个算法需要多少的实际奖励和 bootstrapping。

• 通过调整步数，可以进行一个 MC 和 TD 之间的 trade-off，如果 \(n=\infty\)， 即整个游戏结束过后，再进行更新，TD 就变成了 MC。
• n-step 的 TD target 如下式所示：

\[ G_{t}^{n}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{n-1} R_{t+n}+\gamma^{n} v\left(S_{t+n}\right) \]

• 得到 TD target 之后，我们用增量学习(incremental learning)的方法来更新状态的价值：

\[ v\left(S_{t}\right) \leftarrow v\left(S_{t}\right)+\alpha\left(G_{t}^{n}-v\left(S_{t}\right)\right) \]

Bootstrapping and Sampling for DP,MC and TD

• Bootstrapping：更新时使用了估计：
  • MC 没用 bootstrapping，因为它是根据实际的 return 来更新。
  • DP 用了 bootstrapping。
  • TD 用了 bootstrapping。
• Sampling：更新时通过采样得到一个期望：
  • MC 是纯 sampling 的方法。
  • DP 没有用 sampling，它是直接用 Bellman expectation equation 来更新状态价值的。
  • TD 用了 sampling。TD target 由两部分组成，一部分是 sampling，一部分是 bootstrapping。

DP 是直接算 expectation，把它所有相关的状态都进行加和。

MC 在当前状态下，采一个支路，在一个path 上进行更新，更新这个 path 上的所有状态。

TD 是从当前状态开始，往前走了一步，关注的是非常局部的步骤。

• 如果 TD 需要更广度的 update，就变成了 DP（因为 DP 是把所有状态都考虑进去来进行更新）。
• 如果 TD 需要更深度的 update，就变成了 MC。
• 右下角是穷举的方法（exhaustive search），穷举的方法既需要很深度的信息，又需要很广度的信息。

Model-free Control

Q: 当我们不知道 MDP 模型情况下，如何优化价值函数，得到最佳的策略？

A: 我们可以把 policy iteration 进行一个广义的推广，使它能够兼容 MC 和 TD 的方法，即 Generalized Policy Iteration(GPI) with MC and TD。

Policy iteration 由两个步骤组成：

1. 根据给定的当前的 policy \(\pi\) 来估计价值函数；
2. 得到估计的价值函数后，通过 greedy 的方法来改进它的算法。

这两个步骤是一个互相迭代的过程。

得到一个价值函数过后，我们并不知道它的奖励函数和状态转移，所以就没法估计它的 Q 函数。所以这里有一个问题：当我们不知道奖励函数和状态转移时，如何进行策略的优化。

针对上述情况，我们引入了广义的 policy iteration 的方法。

我们对 policy evaluation 部分进行修改：用 MC 的方法代替 DP 的方法去估计 Q 函数。

当得到 Q 函数后，就可以通过 greedy 的方法去改进它。

上图是用 MC 估计 Q 函数的算法。

• 假设每一个 episode 都有一个 exploring start，exploring start 保证所有的状态和动作都在无限步的执行后能被采样到，这样才能很好地去估计。
• 算法通过 MC 的方法产生了很多的轨迹，每个轨迹都可以算出它的价值。然后，我们可以通过 average 的方法去估计 Q 函数。Q 函数可以看成一个 Q-table，通过采样的方法把表格的每个单元的值都填上，然后我们使用 policy improvement 来选取更好的策略。
• 算法核心：如何用 MC 方法来填 Q-table。

为了确保 MC 方法能够有足够的探索，我们使用了 \(\varepsilon\)-greedy exploration。

\(\varepsilon\text{-greedy}\) 的意思是说，我们有 \(1-\varepsilon\) 的概率会按照 Q-function 来决定 action，通常 \(\varepsilon\) 就设一个很小的值， \(1-\varepsilon\) 可能是 90%，也就是 90% 的概率会按照 Q-function 来决定 action，但是你有 10% 的机率是随机的。通常在实现上 \(\varepsilon\) 会随着时间递减。在最开始的时候。因为还不知道那个 action 是比较好的，所以你会花比较大的力气在做 exploration。接下来随着训练的次数越来越多。已经比较确定说哪一个 Q 是比较好的。你就会减少你的 exploration，你会把 \(\varepsilon\) 的值变小，主要根据 Q-function 来决定你的 action，比较少做 random，这是 \(\varepsilon\text{-greedy}\)。

当我们使用 MC 和 \(\varepsilon\)-greedy 探索这个形式的时候，我们可以确保价值函数是单调的，改进的。

上图是带 \(\varepsilon\)-greedy 探索的 MC 算法的伪代码。

与 MC 相比，TD 有如下几个优势：

• 低方差。
• 能够在线学习。
• 能够从不完整的序列学习。

所以我们可以把 TD 也放到 control loop 里面去估计 Q-table，再采取这个 \(\varepsilon\)-greedy policy improvement。这样就可以在 episode 没结束的时候来更新已经采集到的状态价值。

• 偏差(bias)：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据，如上图第二行所示。
• 方差(variance)：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散，如上图右列所示。

Sarsa: On-policy TD Control

TD 是给定了一个策略，然后我们去估计它的价值函数。接着我们要考虑怎么用 TD 这个框架来估计 Q-function。

Sarsa 所作出的改变很简单，就是将原本我们 TD 更新 V 的过程，变成了更新 Q，如下式所示：

\[ Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right)-Q\left(S_{t}, A_{t}\right)\right] \] 这个公式就是说可以拿下一步的 Q 值 \(Q(S_{t+_1},A_{t+1})\) 来更新我这一步的 Q 值 \(Q(S_t,A_t)\) 。

Sarsa 是直接估计 Q-table，得到 Q-table 后，就可以更新策略。

为了理解这个公式，如上图所示，我们先把 \(R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right.)\) 当作是一个目标值，就是 \(Q(S_t,A_t)\) 想要去逼近的一个目标值。\(R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right.)\) 就是 TD target。

我们想要计算的就是 \(Q(S_t,A_t)\) 。因为最开始 Q 值都是随机初始化或者是初始化为零，它需要不断地去逼近它理想中真实的 Q 值(TD target)，\(R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right)-Q\left(S_{t}, A_{t}\right)\) 就是 TD 误差。

也就是说，我们拿 \(Q(S_t,A_t)\) 来逼近 \(G_t\)，那 \(Q(S_{t+1},A_{t+1})\) 其实就是近似 \(G_{t+1}\)。我就可以用 \(Q(S_{t+1},A_{t+1})\) 近似 \(G_{t+1}\)，然后把 \(R_{t+1}+Q(S_{t+1},A_{t+1})\) 当成目标值。

\(Q(S_t,A_t)\) 就是要逼近这个目标值，我们用软更新的方式来逼近。软更新的方式就是每次我只更新一点点，\(\alpha\) 类似于学习率。最终的话，Q 值都是可以慢慢地逼近到真实的 target 值。这样我们的更新公式只需要用到当前时刻的 \(S_{t},A_t\)，还有拿到的 \(R_{t+1}, S_{t+1}，A_{t+1}\) 。

该算法由于每次更新值函数需要知道当前的状态(state)、当前的动作(action)、奖励(reward)、下一步的状态(state)、下一步的动作(action)，即 \((S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})\) 这几个值 ，由此得名 Sarsa 算法。它走了一步之后，拿到了 \((S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})\) 之后，就可以做一次更新。

我们直接看这个框框里面的更新公式， 和之前的公式是一样的。\(S'\) 就是 \(S_{t+1}\) 。我们就是拿下一步的 Q 值 \(Q(S',A')\) 来更新这一步的 Q 值 \(Q(S,A)\)，不断地强化每一个 Q。

Sarsa 属于单步更新法，也就是说每执行一个动作，就会更新一次价值和策略。如果不进行单步更新，而是采取 \(n\) 步更新或者回合更新，即在执行 \(n\) 步之后再来更新价值和策略，这样就得到了 n 步 Sarsa(n-step Sarsa)。

比如 2-step Sarsa，就是执行两步后再来更新 Q 的值。

具体来说，对于 Sarsa，在 \(t\) 时刻其价值的计算公式为 \[ q_{t}=R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right) \] 而对于 \(n\) 步 Sarsa，它的 \(n\) 步 Q 收获为 \[ q_{t}^{(n)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{n-1} R_{t+n}+\gamma^{n} Q\left(S_{t+n}, A_{t+n}\right) \]

如果给 \(q_t^{(n)}\) 加上衰减因子 \(\lambda\) 并进行求和，即可得到 Sarsa(\(\lambda\)) 的 Q 收获： \[ q_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} q_{t}^{(n)} \] 因此，\(n\) 步 Sarsa(\(\lambda\))的更新策略可以表示为 \[ Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left(q_{t}^{\lambda}-Q\left(S_{t}, A_{t}\right)\right) \] 总的来说，Sarsa 和 Sarsa(\(\lambda\)) 的差别主要体现在价值的更新上。

我们看看用代码去怎么去实现。了解单步更新的一个基本公式之后，代码实现就很简单了。右边是环境，左边是 agent 。我们每次跟环境交互一次之后呢，就可以 learn 一下，向环境输出 action，然后从环境当中拿到 state 和 reward。Agent 主要实现两个方法：

• 一个就是根据 Q 表格去选择动作，输出 action。
• 另外一个就是拿到 \((S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1})\) 这几个值去更新我们的 Q 表格。

Q-learning: Off-policy TD Control

Sarsa 是一种 on-policy 策略。Sarsa 优化的是它实际执行的策略，它直接拿下一步会执行的 action 来去优化 Q 表格，所以 on-policy 在学习的过程中，只存在一种策略，它用一种策略去做 action 的选取，也用一种策略去做优化。所以 Sarsa 知道它下一步的动作有可能会跑到悬崖那边去，所以它就会在优化它自己的策略的时候，会尽可能的离悬崖远一点。这样子就会保证说，它下一步哪怕是有随机动作，它也还是在安全区域内。

而 off-policy 在学习的过程中，有两种不同的策略:

• 第一个策略是我们需要去学习的策略，即target policy(目标策略)，一般用 \(\pi\) 来表示，Target policy 就像是在后方指挥战术的一个军师，它可以根据自己的经验来学习最优的策略，不需要去和环境交互。
• 另外一个策略是探索环境的策略，即behavior policy(行为策略)，一般用 \(\mu\) 来表示。\(\mu\) 可以大胆地去探索到所有可能的轨迹，采集轨迹，采集数据，然后把采集到的数据喂给 target policy 去学习。而且喂给目标策略的数据中并不需要 \(A_{t+1}\) ，而 Sarsa 是要有 \(A_{t+1}\) 的。Behavior policy 像是一个战士，可以在环境里面探索所有的动作、轨迹和经验，然后把这些经验交给目标策略去学习。比如目标策略优化的时候，Q-learning 不会管你下一步去往哪里探索，它就只选收益最大的策略。

再举个例子，如上图所示，比如环境是一个波涛汹涌的大海，但 learning policy 很胆小，没法直接跟环境去学习，所以我们有了 exploratory policy，exploratory policy 是一个不畏风浪的海盗，他非常激进，可以在环境中探索。他有很多经验，可以把这些经验写成稿子，然后喂给这个 learning policy。Learning policy 可以通过这个稿子来进行学习。

在 off-policy learning 的过程中，我们这些轨迹都是 behavior policy 跟环境交互产生的，产生这些轨迹后，我们使用这些轨迹来更新 target policy \(\pi\)。

Off-policy learning 有很多好处：

• 我们可以利用 exploratory policy 来学到一个最佳的策略，学习效率高；
• 可以让我们学习其他 agent 的行为，模仿学习，学习人或者其他 agent 产生的轨迹；
• 重用老的策略产生的轨迹。探索过程需要很多计算资源，这样的话，可以节省资源。

Q-learning 有两种 policy：behavior policy 和 target policy。

Target policy \(\pi\) 直接在 Q-table 上取 greedy，就取它下一步能得到的所有状态，如下式所示： \[ \pi\left(S_{t+1}\right)=\underset{a^{\prime}}{\arg \max}~ Q\left(S_{t+1}, a^{\prime}\right) \] Behavior policy \(\mu\) 可以是一个随机的 policy，但我们采取 \(\varepsilon\text{-greedy}\)，让 behavior policy 不至于是完全随机的，它是基于 Q-table 逐渐改进的。

我们可以构造 Q-learning target，Q-learning 的 next action 都是通过 arg max 操作来选出来的，于是我们可以代入 arg max 操作，可以得到下式： \[ \begin{aligned} R_{t+1}+\gamma Q\left(S_{t+1}, A^{\prime}\right) &=R_{t+1}+\gamma Q\left(S_{t+1},\arg \max ~Q\left(S_{t+1}, a^{\prime}\right)\right) \\ &=R_{t+1}+\gamma \max _{a^{\prime}} Q\left(S_{t+1}, a^{\prime}\right) \end{aligned} \] 接着我们可以把 Q-learning 更新写成增量学习的形式，TD target 就变成 max 的值，即 \[ Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right] \]

我们再通过对比的方式来进一步理解 Q-learning。Q-learning 是 off-policy 的时序差分学习方法，Sarsa 是 on-policy 的时序差分学习方法。

• Sarsa 在更新 Q 表格的时候，它用到的 A' 。我要获取下一个 Q 值的时候，A' 是下一个 step 一定会执行的 action。这个 action 有可能是 \(\varepsilon\)-greedy 方法采样出来的值，也有可能是 max Q 对应的 action，也有可能是随机动作，但这是它实际执行的那个动作。
• 但是 Q-learning 在更新 Q 表格的时候，它用到这个的 Q 值 \(Q(S',a)\) 对应的那个 action ，它不一定是下一个 step 会执行的实际的 action，因为你下一个实际会执行的那个 action 可能会探索。
• Q-learning 默认的 next action 不是通过 behavior policy 来选取的，Q-learning 直接看 Q-table，取它的 max 的这个值，它是默认 A' 为最优策略选的动作，所以 Q-learning 在学习的时候，不需要传入 A'，即 \(A_{t+1}\) 的值。

事实上，Q-learning 算法被提出的时间更早，Sarsa 算法是 Q-learning 算法的改进。

Sarsa 和 Q-learning 的更新公式都是一样的，区别只在 target 计算的这一部分，

• Sarsa 是 \(R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})\) ；
• Q-learning 是 \(R_{t+1}+\gamma \underset{a}{\max} Q\left(S_{t+1}, a\right)\) 。

Sarsa 是用自己的策略产生了 S,A,R,S',A' 这一条轨迹。然后拿着 \(Q(S_{t+1},A_{t+1})\) 去更新原本的 Q 值 \(Q(S_t,A_t)\)。

但是 Q-learning 并不需要知道我实际上选择哪一个 action ，它默认下一个动作就是 Q 最大的那个动作。Q-learning 知道实际上 behavior policy 可能会有 10% 的概率去选择别的动作，但 Q-learning 并不担心受到探索的影响，它默认了就按照最优的策略来去优化目标策略，所以它可以更大胆地去寻找最优的路径，它会表现得比 Sarsa 大胆非常多。

对 Q-learning 进行逐步地拆解的话，跟 Sarsa 唯一一点不一样就是并不需要提前知道 \(A_2\) ，我就能更新 \(Q(S_1,A_1)\) 。在训练一个 episode 这个流程图当中，Q-learning 在 learn 之前它也不需要去拿到 next action \(A'\)，它只需要前面四个 $ (S,A,R,S')$ ，这跟 Sarsa 很不一样。 ## On-policy vs. Off-policy

总结一下 on-policy 和 off-policy 的区别。

• Sarsa 是一个典型的 on-policy 策略，它只用了一个 policy \(\pi\)，它不仅使用策略 \(\pi\) 学习，还使用策略 \(\pi\) 与环境交互产生经验。如果 policy 采用 \(\varepsilon\)-greedy 算法的话，它需要兼顾探索，为了兼顾探索和利用，它训练的时候会显得有点胆小。它在解决悬崖问题的时候，会尽可能地离悬崖边上远远的，确保说哪怕自己不小心探索了一点，也还是在安全区域内。此外，因为采用的是 \(\varepsilon\)-greedy 算法，策略会不断改变(\(\varepsilon\) 会不断变小)，所以策略不稳定。
• Q-learning 是一个典型的 off-policy 的策略，它有两种策略：target policy 和 behavior policy。它分离了目标策略跟行为策略。Q-learning 就可以大胆地用 behavior policy 去探索得到的经验轨迹来去优化目标策略，从而更有可能去探索到最优的策略。Behavior policy 可以采用 \(\varepsilon\)-greedy 算法，但 target policy 采用的是 greedy 算法，直接根据 behavior policy 采集到的数据来采用最优策略，所以 Q-learning 不需要兼顾探索。
• 比较 Q-learning 和 Sarsa 的更新公式可以发现，Sarsa 并没有选取最大值的 max 操作，因此，
  • Q-learning 是一个非常激进的算法，希望每一步都获得最大的利益；
  • 而 Sarsa 则相对非常保守，会选择一条相对安全的迭代路线。

Summary

总结如上图所示。

References

• 百度强化学习

• 强化学习基础 David Silver 笔记

• Intro to Reinforcement Learning (强化学习纲要）

• Reinforcement Learning: An Introduction (second edition)

• 百面深度学习

• 神经网络与深度学习

• 机器学习

• Understanding the Bias-Variance Tradeoff

图像加密算法

Lorenz超混沌系统

​ Lorenz混沌系统是由美国气象学家爱德华·洛伦兹（Edward Lorenz）在1963年提出的一个非常经典且重要的混沌系统。它是对大气热对流现象进行数学建模后得到的一个简化的三维自治动力系统。其动力学方程如下：

\[ \begin{cases} \frac{dx}{dt}=\sigma(y-x)\\ \frac{dy}{dt}=x(\rho-z)-y\\ \frac{dz}{dt}=xy-\beta z \end{cases} \] 其中，\(x\)、\(y\)、\(z\)是系统的三个状态变量，\(\sigma\)、\(\rho\)、\(\beta\)是系统的参数。

​ 这三个参数的取值范围会影响系统的动力学行为。通常情况下，当参数\(\sigma = 10\)，\(\rho = 28\)，\(\beta = 8/3\)时，Lorenz系统处于混沌状态。 Lorenz混沌系统具有以下几个显著的特点：

1. 对初始条件的敏感依赖性：这是混沌系统的一个关键特征，也被称为“蝴蝶效应”。即初始条件的微小变化会随着时间的推移导致系统状态的巨大差异。在Lorenz系统中，即使初始的\(x\)、\(y\)、\(z\)值仅有极其微小的差异，经过一段时间的演化后，系统的轨迹会变得完全不同。
2. 奇怪吸引子：Lorenz系统的相空间中存在一个奇怪吸引子。吸引子是动力系统中系统演化最终趋向的状态集合。Lorenz系统的奇怪吸引子具有复杂的几何结构和分形特征，其形状类似于两个翅膀的蝴蝶，这也是“蝴蝶效应”的一种形象表示。系统的状态会在这个吸引子上不断地运动，但不会收敛到一个固定的点或周期轨道。
3. 不可预测性：由于对初始条件的敏感依赖性，使得Lorenz系统的长期行为是不可预测的。即使我们知道系统的当前状态和精确的动力学方程，也无法准确预测系统未来的状态。 Lorenz混沌系统在许多领域都有广泛的应用，比如保密通信、图像加密、电路设计、生物医学等。在保密通信中，利用Lorenz系统产生的混沌信号可以对信息进行加密，提高通信的安全性；在图像加密中，混沌序列可以用于打乱图像的像素值，实现图像的加密。

龙格-库塔

1. 首先计算四个中间值k1、k2、k3、k4：

   • k1_x是根据当前时刻的x、y、z以及系统参数，通过dx_dt = sigma * (y - x)计算得到的，表示在当前状态下x的变化率。
   • k2_x是在时间步长h/2处，使用当前的x加上h*k1_x/2以及对应的y和z值更新后的中间状态下，再次计算dx_dt得到的变化率。
   • k3_x与k2_x类似，也是在时间步长h/2处，使用当前的x加上h*k2_x/2以及对应的y和z值更新后的中间状态下，计算dx_dt得到的变化率。
   • k4_x是在时间步长h处，使用当前的x加上h*k3_x以及对应的y和z值更新后的状态下，计算dx_dt得到的变化率。

需要的材料

1. 身份证复印件
2. 成绩单
3. 竞赛证明
4. 各大高校申请表

第二问思路

是否对配件检验：

1. 如果对配件检验：得到的配件一定是合格品，只需计算平均价值。

\(E = \frac{(w+c)}{p}\)

\(p\)表示合格品概率，\(w\)表示配件购买价格，\(c\)表示配件检验成本

2. 不对配件检验：会提高成品的不合格率

是否对成品检验：

1. 对成品检验：需要付出检验费用，但卖出的成品一定是合格品，所以不需要支付退还费用。

成本构成：1.合格品的成本（包括配件购买费用+配件检验费用） ；2.组装费用； 3.成品检验费用 ；4.不合格品的成本

2. 对成品不检验：不需要检验费用，但卖出的成品有一部分是不合格品，需要支付退还费用。

成本构成：

枚举所有做法（第二问）

首先考虑不拆解的情况

1. 不检验配件A，不检验配件B，不检验成品，不拆解成品。

成品为合格品概率：\(p(qualified) = p_a * p_b * p_c\)

不合格品概率：\(1 - p(qualified)\)

平均收益：\(E = p(qualified) * w - 1 * (cost) - (1-p(qualified))*(swap)\)

2. 检验配件A，不检验配件B，不检验成品，不拆解成品。

配件A的平均成本：\(\frac{cost + c}{p}\)

成品为合格品概率：\(p(qualified) = p_b * p_c\)

平均收益：\(E = p(qualified) * w - 1*cost - (1-qualified)*swap\)

组成一件成品的价格：\(cost = cost_a + cost_b + eval_a + assemble\)

3. 不检验配件A，检验配件B，不检验成品，不拆解成品。

原理同上

4. 检验配件A，检验配件B，不检验成品，不拆解成品。

合格品概率：\(p(qualified) = p_c\)

平均收益：\(E = p(qualified) * w - 1 * cost - (1-p(qualified))*swap\)

生产价格：\(cost = E(cost_A) + E(cost_B) + assemble\)

综上所述：当不检验成品，且不拆解成品时，卖出每件产品的期望收益为：

\(E = p(qualified) * w - 1*cost - p(unqualified) * swap\)

只是每种情况，计算生产成本的结果不同

5. 不检验配件A，不检验配件B，检验成品，不拆解成品。

合格品概率：\(p(qualified) = p_A * p_B * p_C\)

销售收益：\(p(qualified) * w\)

生产成本：\(cost_A + cost_B + assemble + eval_C\)

6. 检验配件A，不检验配件B，检验成品，不拆解成品。

合格品概率：\(p(qualified) = p_B * p_C\)

销售收益：\(p(qualified) * w\)

成产成本：\(E(cost_A) + cost_B + assemble + eval_C\)

平均收益：\(E = p(qualified) * w - 1*cost\)

7. 不检验配件A，检验配件B，检验成品，不拆解成品

同6

8. 检验配件A，检验配件B，检验成品，不拆解成品

\(cost = E(cost_A) + E(cost_B) + assemble + eval_C\)

综上所述：不拆解成品的情况下，所有方案 卖出一件的预期收益为：

\(E = p(qualified) * w - 1 * cost - p(unqualified)*swap\)

是否检验配件，影响\(cost\)的计算；

是否检验成品，决定了售出成品的不合格率是否为0，可以减少退还损失。

其次考虑拆解成品的情况

由于拆解的是检验不合格的成品，所以，当拆解成品时，必然伴随着检验成品。

1. 不检验配件A，不检验配件B，检验成品，且拆解成品，且不进行二次检验。

暂时认为，这是一种很糟糕的策略，只有在次品率极低的情况下适用。

2. 检验配件A，检验配件B，检验成品，且拆解成品，无需进行二次检验。

第i次合成成功的成本：\(cost(i) = E(cost_A) + E(cost_B) + i*assemble + (i-1)*melt\)

生产成本：$cost = _{i=1}^{} cost(i) $

成品的合格率：\(p(qualified) = p_c\)

卖出一件产品的预期收益同上。

3. 检验配件A，不检验配件B，检验成品，拆解成品，并对B进行二次检验

这里需要用到朴素贝叶斯公式！

成品合格率：\(p(qualified) = p_B * p_C\)

仅因为组装问题导致为次品的概率为：\((1-p_C)*p_B\) ，

配件B损坏导致为次品的概率（包括了B既为次品，还组装失败的情况）：\(1-p_B\)

由于所有配件都至多检验一次，一旦通过检验，则一定为合格品。

第i次合成成功的花费：

\(cost(i) = E(cost_A) + cost_B + i*assemble + (i-1)*melt + (i>1)?:0:1 * eval_c\)

生产成本：

\(cost = p_b*p_c*cost(1) + (1-p_b)*(E(cost_A)+cost_B + assemble + eval_c) + p_b * (1-p_c)^{(i-1)} * p_c *(E_(cost_A) + cost_B + i*assemble + (i-1)*melt)\)

4.不检验A，B，检验成品，拆解成品，并对A，B进行二次检验。

\[cost = \sum_{i=1}^{n} cost_i\]