共计 5013 个字符，预计需要花费 13 分钟才能阅读完成。
强化学习从根底到进阶 - 常见问题和面试必知必答 [2]：马尔科夫决策、贝尔曼方程、动静布局、策略价值迭代
1. 马尔科夫决策外围词汇
- 马尔可夫性质（Markov property，MP）：如果某一个过程将来的状态与过来的状态无关，只由当初的状态决定，那么其具备马尔可夫性质。换句话说，一个状态的下一个状态只取决于它的以后状态，而与它以后状态之前的状态都没有关系。
- 马尔可夫链（Markov chain）：概率论和数理统计中具备马尔可夫性质且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）。
- 状态转移矩阵（state transition matrix）：状态转移矩阵相似于条件概率（conditional probability），其示意当智能体到达某状态后，达到其余所有状态的概率。矩阵的每一行形容的是从某节点达到所有其余节点的概率。
- 马尔可夫处分过程（Markov reward process，MRP）：实质是马尔可夫链加上一个处分函数。在马尔可夫处分过程中，状态转移矩阵和它的状态都与马尔可夫链的一样，只多了一个处分函数。处分函数是一个冀望，即在某一个状态能够取得多大的处分。
- 范畴（horizon）：定义了同一个回合（episode）或者一个残缺轨迹的长度，它是由无限个步数决定的。
- 回报（return）：把处分进行折扣（discounted），而后取得的对应的处分。
- 贝尔曼方程（Bellman equation）：其定义了以后状态与将来状态的迭代关系，示意以后状态的价值函数能够通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动静布局创始人理查德 $\cdot$ 贝尔曼（Richard Bellman）而得名，同时也被叫作“动静布局方程”。贝尔曼方程即 $V(s)=R(s)+ \gamma \sum_{s’ \in S}P(s’|s)V(s’)$，特地地，其矩阵模式为 $\mathrm{V}=\mathrm{R}+\gamma \mathrm{PV}$。
- 蒙特卡洛算法（Monte Carlo algorithm，MC algorithm）：可用来计算价值函数的值。应用本节中小船的例子，当失去一个马尔可夫处分过程后，咱们能够从某一个状态开始，把小船放到水中，让它随波流动，这样就会产生一个轨迹，从而失去一个折扣后的处分 $g$。当积攒该处分到肯定数量后，用它间接除以轨迹数量，就会失去其价值函数的值。
- 动静布局算法（dynamic programming，DP）：其可用来计算价值函数的值。通过始终迭代对应的贝尔曼方程，最初使其收敛。当最初更新的状态与上一个状态差距不大的时候，动静布局算法的更新就能够进行。
- Q 函数（Q-function）：其定义的是某一个状态和某一个动作所对应的有可能失去的回报的冀望。
- 马尔可夫决策过程中的预测问题 ：即策略评估问题，给定一个马尔可夫决策过程以及一个策略 $\pi$，计算它的策略函数，即每个状态的价值函数值是多少。其能够通过动静布局算法解决。
- 马尔可夫决策过程中的管制问题 ：即寻找一个最佳策略，其输出是马尔可夫决策过程，输入是最佳价值函数（optimal value function）以及最佳策略（optimal policy）。其能够通过动静布局算法解决。
- 最佳价值函数 ：搜寻一种策略 $\pi$，使每个状态的价值最大，$V^*$ 就是达到每一个状态的极大值。在极大值中，咱们失去的策略是最佳策略。最佳策略使得每个状态的价值函数都获得最大值。所以当咱们说某一个马尔可夫决策过程的环境可解时，其实就是咱们能够失去一个最佳价值函数。
2. 常见问题汇总
2.1 为什么在马尔可夫处分过程中须要有折扣因子？
（1）首先，是有些马尔可夫过程是环状的，它并没有起点，所以咱们想防止无穷的处分。
（2）另外，咱们想把不确定性也示意进去，心愿尽可能快地失去处分，而不是在将来的某个时刻失去处分。
（3）接上一点，如果这个处分是有理论价值的，咱们可能更心愿立即就失去处分，而不是前面才能够失去处分。
（4）还有，在有些时候，折扣因子也能够设为 0。当它被设为 0 后，咱们就只关注它以后的处分。咱们也能够把它设为 1，设为 1 示意将来取得的处分与以后取得的处分是一样的。
所以，折扣因子能够作为强化学习智能体的一个超参数进行调整，而后就会失去不同行为的智能体。
2.2 为什么矩阵模式的贝尔曼方程的解析解比拟难求得？
通过矩阵求逆的过程，咱们就能够把 $V$ 的解析解求进去。然而这个矩阵求逆的过程的复杂度是 $O(N^3)$，所以当状态十分多的时候，比方从 10 个状态到 1000 个状态，到 100 万个状态，那么当咱们有 100 万个状态的时候，转移矩阵就会是一个 100 万乘 100 万的矩阵。对于这样一个大矩阵进行求逆是十分艰难的，所以这种通过解析解去解的办法，只能利用在很小量的马尔可夫处分过程中。
2.3 计算贝尔曼方程的常见办法有哪些，它们有什么区别？
（1）蒙特卡洛办法：可用来计算价值函数的值。以本书中的小船示例为例，当失去一个马尔可夫处分过程后，咱们能够从某一个状态开始，把小船放到水中，让它“同流合污”，这样就会产生一条轨迹，从而失去一个折扣后的处分 $g$。当积攒该处分到肯定数量后，间接除以轨迹数量，就会失去其价值函数的值。
（2）动静布局办法：可用来计算价值函数的值。通过始终迭代对应的贝尔曼方程，最初使其收敛。当最初更新的状态与上一个状态区别不大的时候，通常是小于一个阈值 $\gamma$ 时，更新就能够进行。
（3）以上两者的联合办法：咱们也能够应用时序差分学习办法，其为动静布局办法和蒙特卡洛办法的联合。
2.4 马尔可夫处分过程与马尔可夫决策过程的区别是什么？
绝对于马尔可夫处分过程，马尔可夫决策过程多了一个决策过程，其余的定义与马尔可夫处分过程是相似的。因为多了一个决策，多了一个动作，因而状态转移也多了一个条件，即执行一个动作，导致将来状态的变动，其不仅依赖于以后的状态，也依赖于在以后状态下智能体采取的动作决定的状态变动。对于价值函数，它也多了一个条件，多了一个以后的动作，即以后状态以及采取的动作会决定以后可能失去的处分的多少。
另外，两者之间是有转换关系的。具体来说，已知一个马尔可夫决策过程以及一个策略 $\pi$ 时，咱们能够把马尔可夫决策过程转换成马尔可夫处分过程。在马尔可夫决策过程中，状态的转移函数 $P(s’|s,a)$ 是基于它的以后状态和以后动作的，因为咱们当初已知策略函数，即在每一个状态，咱们晓得其采取每一个动作的概率，所以咱们就能够间接把这个动作进行加和，就能够失去对于马尔可夫处分过程的一个转移概率。同样地，对于处分，咱们能够把动作去掉，这样就会失去一个相似于马尔可夫处分过程的处分。
2.5 马尔可夫决策过程中的状态转移与马尔可夫处分过程中的状态转移的构造或者计算方面的差别有哪些？
对于马尔可夫链，它的转移概率是间接决定的，即从以后时刻的状态通过转移概率失去下一时刻的状态值。然而对于马尔可夫决策过程，其中间多了一层动作的输入，即在以后这个状态，首先要决定采取某一种动作，再通过状态转移函数变动到另外一个状态。所以在以后状态与将来状态转移过程中多了一层决策性，这是马尔可夫决策过程与之前的马尔可夫过程的不同之处。在马尔可夫决策过程中，动作是由智能体决定的，所以多了一个组成部分，智能领会采取动作来决定将来的状态转移。
2.6 咱们如何寻找最佳策略，寻找最佳策略办法有哪些？
实质来说，当咱们获得最佳价值函数后，咱们能够通过对 Q 函数进行最大化，从而失去最佳价值。而后，咱们间接对 Q 函数取一个让动作最大化的值，就能够间接失去其最佳策略。具体方法如下，
（1）穷举法（个别不应用）：假如咱们有无限个状态、无限个动作可能性，那么每个状态咱们能够采取 $A$ 种动作策略，那么总共就是 $|A|^{|S|}$ 个可能的策略。咱们能够把他们穷举一遍，而后算出每种策略的价值函数，比照一下就能够失去最佳策略。然而这种办法的效率极低。
（2）策略迭代：一种迭代办法，其由两局部组成，以下两个步骤始终在迭代进行，最终收敛，其过程有些相似于机器学习中的 EM 算法（冀望 - 最大化算法）。第一个步骤是策略评估，即以后咱们在优化这个策略 $\pi$，在优化过程中通过评估从而失去一个更新的策略；第二个步骤是策略晋升，即获得价值函数后，进一步推算出它的 Q 函数，失去它的最大值。
（3）价值迭代：咱们始终迭代贝尔曼最优方程，通过迭代，其能逐步趋向于最佳策略，这是价值迭代办法的外围。咱们为了失去最佳的 $V^*$，对于每个状态的 $V^*$ 值，间接应用贝尔曼最优方程进行迭代，迭代屡次之后它就会收敛到最佳策略及其对应的状态，这里是没有策略函数的。
3. 面试必知必答
3.1 友善的面试官：请问马尔可夫过程是什么？马尔可夫决策过程又是什么？其中马尔可夫最重要的性质是什么呢？
马尔可夫过程是一个二元组 $<S,P>$，$S$ 为状态汇合，$P$ 为状态转移函数；
马尔可夫决策过程是一个五元组 $<S,P,A,R,\gamma>$，其中 $R$ 示意从 $S$ 到 $S’$ 可能取得的处分冀望，$\gamma$ 为折扣因子，$A$ 为动作汇合；
马尔可夫最重要的性质是下一个状态只与以后状态无关，与之前的状态无关，也就是 $p(s_{t+1} | s_t)= p(s_{t+1}|s_1,s_2,…,s_t)$。
3.2 友善的面试官：请问咱们个别怎么求解马尔可夫决策过程？
咱们求解马尔可夫决策过程时，能够间接求解贝尔曼方程或动静布局方程：
$$V(s)=R(S)+ \gamma \sum_{s’ \in S}p(s’|s)V(s’)$$
特地地，其矩阵模式为 $\mathrm{V}=\mathrm{R}+\gamma \mathrm{PV}$。然而贝尔曼方程很难求解且计算复杂度较高，所以能够应用动静布局、蒙特卡洛以及时序差分等办法求解。
3.3 友善的面试官：请问如果数据流不具备马尔可夫性质怎么办？应该如何解决？
如果不具备马尔可夫性，即下一个状态与之前的状态也无关，若仅用以后的状态来求解决策过程，势必导致决策的泛化能力变差。为了解决这个问题，能够利用循环神经网络对历史信息建模，取得蕴含历史信息的状态表征，表征过程也能够应用注意力机制等伎俩，最初在表征状态空间求解马尔可夫决策过程问题。
3.4 友善的面试官：请别离写出基于状态价值函数的贝尔曼方程以及基于动作价值函数的贝尔曼方程。
（1）基于状态价值函数的贝尔曼方程: $V_{\pi}(s) = \sum_{a}{\pi(a|s)}\sum_{s’,r}{p(s’,r|s,a)[r(s,a)+\gamma V_{\pi}(s’)]}$；
（2）基于动作价值函数的贝尔曼方程: $Q_{\pi}(s,a)=\sum_{s’,r}p(s’,r|s,a)[r(s’,a)+\gamma V_{\pi}(s’)]$。
3.5 友善的面试官：请问最佳价值函数 $V^*$ 和最佳策略 $\pi^*$ 为什么等价呢？
最佳价值函数的定义为 $V^* (s)=\max_{\pi} V_{\pi}(s)$，即咱们搜寻一种策略 $\pi$ 来让每个状态的价值最大。$V^*$ 就是达到每一个状态其的最大价值，同时咱们失去的策略就能够说是最佳策略，即 $\pi^{*}(s)=\underset{\pi}{\arg \max}~ V_{\pi}(s)$。最佳策略使得每个状态的价值函数都获得最大值。所以如果咱们能够失去一个最佳价值函数，就能够说某一个马尔可夫决策过程的环境被解。在这种状况下，其最佳价值函数是统一的，即其达到的下限的值是统一的，但这里可能有多个最佳策略对应于雷同的最佳价值。
3.6 友善的面试官：能不能手写一下第 $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]
$$
更多优质内容请关注公号：汀丶人工智能
