2 马尔可夫奖励过程（Markov reward process, MRP）

MRP是在马尔科夫链的基础上加上了奖励函数。
回报函数：

2.1 贝尔曼方程

状态价值函数：

2.2求解价值函数

迭代解法：

3 马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作）。
策略定义了在某种状态下智能体采取的动作。如下式子所示，

Q函数又称动作价值函数，定义了在某个状态之后采取某个动作，它可能得到回报期望，即

对动作进行求和，就可以得到价值函数：

贝尔曼期望方程

本质上因为智能体多了一个动作，所以状态之间的转移概率由策略决定的。同样地的理解，在MRP中，转移概率是确定即策略是确定，所以我们只需要去求解价值函数即可。但是在马尔可夫决策过程中，其策略是未确定的，所以我们需要去寻找一个策略使得价值函数最大，该策略被称为最佳策略。
为了寻找到最佳策略使得价值函数最大即每个状态的价值最大，我们采用策略迭代和价值迭代来解决该问题。

3.1 策略迭代

策略迭代分为策略评估和策略改进两个阶段。第一阶段时策略是固定的，我们根据该策略去估计状态价值函数，第二阶段中在得到价值函数之后去仅有推算Q函数，然后对Q函数进行最大化去进一步改进策略。

3.2 价值迭代

价值迭代算法的思想很简单，通过贝尔曼最优方程进行迭代，最后收敛到最佳价值函数，然后从最佳价值函数中提取最佳策略，可以根据贝尔曼最优方程进行计算。
这个迭代公式思想和EM算法很像。

习题

1、折扣因子的目的是表现了智能体更希望得到现有的奖励，对未来的奖励要打折扣。同时，某些马尔科夫链是环状的，可能不会终止，这样我们就需要避免无穷的奖励。其次，我们无法建立一个完美的环境模型，对未来的评估可能是不准确的，因此对未来的价值添加一个折扣因子。
2、 解析解涉及到矩阵求逆的操作，其时间复杂度很高。
3、蒙特卡洛法，通过自举方式迭代求解。
4、相比于马尔可夫奖励过程，马尔科夫决策过程在得到当前状态之后，智能体会根据当前状态决定采取何种动作，从而进入下一个状态。最本质的区别是智能体可以通过动作来影响下一个时刻的状态，而马尔可夫奖励过程中智能体没有动作，直接根据一个概率分布进入下一个状态。本质上来说，马尔可夫奖励过程是马尔科夫决策过程在策略确定情况下的随机过程问题。
5、主要是决策过程相比于奖励过程复杂了许多，决策过程多了一个策略函数，同时决定到下一个状态的因素也多了一个动作。
6、策略迭代和价值迭代。

面试题

1、马尔可夫过程是一个当前状态只依赖前一个时刻的随机过程，这也是马尔可夫过程最基本的性质。马尔科夫决策过程是智能体在进入下一个状态时，智能体会有一个动作去影响对下一个状态的转移概率分布，同时还有状态的奖励函数。
2、价值迭代或者策略迭代
3、
4、根据最优性准则定理。所以在达到最佳状态价值时，其策略也是最佳的。
5、期望变大，方差变小。