Markov 决策过程，是对概率论和随机过程的 Markov 链 的增强，在 Markov 链上加入了更多的假设。
Markov 奖励过程
Markov 奖励过程（Markov reward process，MRP）是在 Markov 过程的基础上引入奖励函数和折扣因子的得到的随机过程。
奖励函数为状态空间 \mathcal{S} 到一个实数 \mathbb{R} 的函数 r(s)，指的是一步转移到状态 s 时可以获得的奖励的期望，即
r(s) = \mathbb{E}(R_t \, | \, S_t = s);
式中 R_t 指的是 t 时刻获得的奖励。这里奖励 R_t 的分布只与状态 S_t 有关。
引入一个折扣因子 \gamma，则回报（return）定义为 t 时刻开始的衰减奖励之和：
G_t = R_t + \gamma R_{t + 1} + \gamma^2 R_{t + 2} + \cdots = \sum_{k = 0}^\infty \gamma^k R_{t + k}.
警告
真实的强化学习中，Agent 与环境的一次交互一般有终止状态，从而回报 G_t 实际上是一个有限和。数学上可以添加一个奖励恒为 0 的吸收态，将终止视为向吸收态的转移。但编程上要注意特殊处理这个状态。
引入价值（value）函数 V(s) = \mathbb{E}(G_t \, | \, S_t = s)，指的是 G_t 的期望。
\begin{aligned}
V(s) & = \mathbb{E}(G_t \, | \, S_t = s) \\
& = \mathbb{E} \left( R_t + \gamma R_{t + 1} + \gamma^2 R_{t + 2} + \cdots \right) \\
& = \mathbb{E} \left( R_t + \gamma R_{t + 1} + \gamma^2 R_{t + 2} + \cdots \, \middle| \, S_t = s \right) \\
& = \mathbb{E} \left( R_t \, \middle| \, S_t = s \right) + \gamma \mathbb{E} \left( R_{t + 1} + \gamma R_{t + 2} + \cdots R_t \, \middle| \, S_t = s \right) \\
& = r(s) + \gamma \mathbb{E}(G_{t + 1} \, | \, S_t = s)
\end{aligned}
回忆条件期望的 Tower Property：
\mathbb{E}(\mathbb{E}(X \, | \, Y, Z) \, | \, Z) = \mathbb{E}(X \, | \, Z)
又由 \{ S_t \} 的 Markov 性，有：
\begin{aligned}
\mathbb{E}(V(S_{t + 1}) \, | \, S_t) &= \mathbb{E}(\mathbb{E}(G_{t + 1} \, | \, S_{t + 1}) \, | \, S_t) \\
& = \mathbb{E}(\mathbb{E}(G_{t + 1} \, | \, S_{t + 1}, S_t) \, | \, S_t) \\
& = \mathbb{E}(G_{t+1} \, | \, S_t)
\end{aligned}
取 S_t = s，就得到 \mathbb{E}(V(S_{t + 1}) \, | \, S_t = s) = \mathbb{E}(G_{t + 1} \, | \, S_t = s)，因此
V(s) = \mathbb{E}(V(S_{t + 1}) \, | \, S_t = s)
由全概率公式，有
\mathbb{E}(V(S_{t + 1}) \, | \, S_t = s) = \sum_{s' \in \mathcal{S}} V(s') p(s' \, | \, s);
最终，我们得到了 Bellman 方程：
V(s) = \sum_{s' \in \mathcal{S}} V(s') p(s' \, | \, s).
上述方程的直观理解是：当前状态 s 可以获得回报的期望，等于下一状态 s' 回报期望对概率的加权平均。
Markov 决策过程
在 Markov 奖励过程的基础上，再引入动作空间和策略函数，我们就得到了 Markov 决策过程。
引入动作空间（action space），记为 \mathcal{A}，其中的元素称为动作 a，相应地将奖励函数修改为 r(s, a)（同时与 s 和 a 有关），状态转移函数修改为 p(s' \, | \, s, a)。在 Markov 过程的基础上，Markov 决策过程添加了一条动作序列 A_1, A_2, \dots，其中 A_i 是取值自 \mathcal{A} 的随机变量。
智能体可以按照一定的策略（policy）来执行动作。具体地说，给定状态 s，智能体以一个概率分布给出动作 a：
\pi (a \, | \, s) = \mathbb{P}(A_t = a \, | \, S_t = s),
这里的 \pi 称为策略函数。
引入动作并给定策略后，价值需要分为状态价值和动作价值。状态价值定义为：
V_\pi (s) = \mathbb{E}_\pi [G_t \, | \, S_t = s];
动作价值则定义为：
Q_\pi (s, a) = \mathbb{E}_\pi [G_t \, | \, S_t = s, A_t = a];
有 Bellman 方程 成立：
Q_{\pi}(s, a) = \mathbb{E} \left[R_t + \gamma Q_{\pi}(S_{t+1}, A_{t + 1}) \middle| S_t = s, A_t = a \right].
当动作、状态都离散时，Bellman 方程可以写为：
V_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \, | \, s) \left[ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V_\pi (s') \right]
Q_\pi(s, a) = r(s, a) + \gamma \sum_{s' \in \mathcal{S}} \left[ p(s' \, | \, s, a) \sum_{a' \in \mathcal{A}} Q_\pi(s', a') \pi(a' \, | \, s') \right].
形式化定义
Markov 决策过程定义为一个六元组 (\mathcal{S}, \mathcal{A}, p, r, \gamma, \rho_0)，其中：
- \mathcal{S}：状态空间，其中的元素称为状态（state）
- \mathcal{A}：动作空间，其中的元素称为动作（action）
- p：状态转移函数，p(s' | s, a)
- r：奖励函数，描述获得奖励（的期望）
- \gamma：折扣因子
- \rho_0：初始分布
MDP 与 MRP 的关系
将 MDP 的相关变量对 a 加权求和，得到关于状态的边缘分布，就成为了一个 MRP
\tilde r(s) = \sum_{a \in \mathcal A} r(s, a) \pi(a \, | \, s)
\tilde p(s' \, | \, s) = \sum_{a \in \mathcal A} p(s' \, | \, s, a) \pi(a \, | \, s).
最优策略
策略之间可以定义偏序关系。给定两个策略 \pi_1, \pi_2，它们可以分别导出状态价值 V_{\pi_1}, V_{\pi_2}。若对任意的状态 s \in \mathcal{S} 都有 V_{\pi_1}(s) \ge V_{\pi_2} (s)，则称 \pi_1 \ge \pi_2。
定理
总是存在一个最优策略 \pi^*，它与任意的策略 \pi 都可比，并且总是有 \pi^* \ge \pi。换句话说，偏序关系 \le 存在最大元素 \pi。它是一个格（lattice）。
定理的证明可以参考 https://zhuanlan.zhihu.com/p/108484403 ，大致思路是构造 Bellman 算子，并证明它是一个压缩映射。
最优策略 \pi^* 不一定唯一，但是最优策略导出的状态价值 V^* 唯一。
笔记
例如有些时候两条路径的期望回报相同，则此时的策略选择哪一条都可以。
直观上，状态 s 的最大回报，应该等于该状态下采取最佳的行动得到的期望回报，因此：
V^*(s) = \max_{a \in \mathcal{A}} Q^*(s, a);
由此可以导出 Bellman 最优方程：
V^*(s) = \max_{a \in \mathcal{A}} \left[ r(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V^*(s') \right];
Q^*(s, a) = r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) \max_{a' \in \mathcal{A}} Q^*(s', a').
这两个方程描述了最优策略应该满足的方程。可以证明 Bellman 最优方程是最优状态价值的充分必要条件：当一个状态价值函数 V(s) 满足 Bellman 最优方程时，它就是最优状态价值。
已知最优状态价值，就可以依据“最佳行动”的 Bellman 方程导出最优策略：
\pi^*(s) \in \arg \max_{a \in \mathcal{A}} \left[ r(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V^*(s') \right].
由于最优价值状态也要满足一般的 Bellman 方程，与 Bellman 最优方程对比，可以知道此时 \pi^*(a \, | \, s) 必须令最大的 Q^*(s, a) 的权为 1，而其他权为 0，这样加权平均才成为最大值。因此，最优策略多数情况下是一个确定性策略。当多个行动都能达到最大值时，策略可以在最大行动之间随机选择，此时最优策略才可以是一个随机性策略。
策略函数的评估
将 Bellman 方程的右端视为一个函数，则函数可以导出一个迭代方程，第 k 轮迭代的状态价值为 V_k(s)。选定任意初始值 V_0(s)，令：
V_{k + 1}(s) = \sum_{a \in \mathcal{A}} \pi(a \, | \, s) \left[ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V_k (s') \right]
则经过足够多次迭代后，可以证明迭代向量列将收敛到不动点，不动点就是真正的价值函数。
证明方法：使用泛函分析的压缩映射定理。定义算子：
\mathcal{B}(v_k) = r + \gamma P v_k
则有 v_{k+1}= \mathcal{B}(v_k)。要证明向量列 \{ v_k \} 收敛，只需证明算子 \mathcal{B} 是一个压缩映射。
这就是 动态规划求解策略函数 的基本原理。
策略函数的提升
观察 Bellman 方程：
V_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \, | \, s) \left[ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V_\pi (s') \right]
可以发现策略 \pi 根据了其概率函数，将动作 a 进行了加权平均。如果我们构造一个确定性策略 \pi'，在状态 s 下不做加权平均，而是只选择回报最大的动作 a：
V_{\pi'}(s) = \max_{a \in \mathcal{A}} \left[ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V_{\pi'} (s') \right],
则直观上 \pi' 可以得到更大的回报。
警告
改变策略 \pi 的同时，价值 V_\pi(s), Q_\pi(s, a) 的更新都需要 Bellman 方程做约束，所以以上只是一个启发式推导，而不是证明。
这一现象的严格说明是策略提升定理（policy improvement theorem）：
对于策略 \pi，若确定性策略 \pi' 在任意状态下都有
Q_\pi \left(s, \pi'(s) \right) \ge V_\pi(s),
则对任意状态 s，都有
V_{\pi'}(s) \ge V_{\pi}(s).
价值的提升
可以将 Bellman 最优方程也视为迭代方程：
V_{k + 1}(s) = \max_{a \in \mathcal{A}} \left[ r(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s' \, | \, s, a) V_k(s') \right];
选定一定的初值之后，经过多次迭代，至收敛就可以得到最优价值。这是 动态规划求解最优价值函数 的基本原理。