MDP 的定义
马尔可夫奖励过程（Markov reward process，MRP）
- 在马尔可夫过程的基础上加入奖励 $R$ 和奖励衰减因子 $\gamma$
- 马尔可夫奖励过程中时刻 $t$ 的回报 $G_{t}$ 是未来奖励的衰减折现
$$ G_{t}=R_{t}+\gamma R_{t+1}+\gamma^2 R_{t+2}+\dots+\gamma^n R_{t+n} $$
- 马尔可夫奖励过程中的状态价值函数 $v(s)=E[G_{t}|S_{t}=s]$，定义了当状态 $s$ 对应的期望回报 ，即从这个状态展开的所有可能未来回报的期望折现
- 价值函数的求解常用方法：动态规划（见下文）、蒙特卡洛法、时序差分算法 TD
马尔可夫决策过程（Markov decision process，MDP）
- 在马尔可夫奖励过程（MRP）的基础上加入 Agent 动作 $A$
- 除了 MRP 的状态价值函数，MDP 还有一个动作价值函数 $Q_{'\pi}(s,a)$
$$ q_{\pi}(s,a) = \mathbb{E}_{\pi}(G_t|S_t=s, A_t=a)) $$
贝尔曼方程
贝尔曼方程，描述了价值函数基于状态的递推关系
状态价值函数的贝尔曼方程： $$ \begin{align} v_{\pi}(s) &= \mathbb{E}_{\pi}(R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3}+...|S_t=s) \\ &= \mathbb{E}_{\pi}(R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3}+...)|S_t=s) \\ &= \mathbb{E}_{\pi}(R_{t+1} + \gamma G_{t+1} | S_t=s) \\ &= \mathbb{E}_{\pi}(R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s) \end{align} $$
同理可得，动作价值函数的贝尔曼方程： $$ q_{\pi}(s,a) = \mathbb{E}_{\pi}(R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1}) | S_t=s, A_t=a) $$
根据两种价值函数的定义和贝尔曼方程，可推导出二者间的转换公式
从动作价值到状态价值的转换公式： $$v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)q_{\pi}(s,a)$$
状态价值函数是所有动作价值函数基于策略 $\pi$ 的期望；策略 $\pi$ 描述了状态下动作的概率分布，而状态价值可表示为所有可能动作价值的加权求和
从状态价值到动作价值的转换公式： $$ q_{\pi}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{\pi}(s') $$
动作价值由两部分组成，第一部分是即时奖励 $R_{t+1}$，另一部分是未来可能状态价值的加权求和后的结果，再根据衰减因子的折现
最后把以上两个转换公式结合起来，并引入转移概率 $P$，得到两个价值函数的贝尔曼期望方程（Bellman Expectation Equation）： $$v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{\pi}(s'))$$
$$q_{\pi}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^a\sum\limits_{a' \in A} \pi(a'|s')q_{\pi}(s',a')$$
最优价值函数
定义最优策略 $\pi^{*}$，确保 Agent 与环境交互过程中的奖励最大化
最优策略的发现是很难的，但可以通过多个策略的比较来找一个次优策略，即寻找局部最优解；而策略的比较一般通过价值函数的比较实现
定义最优策略下对应的最优状态价值函数： $$ v_{*}(s) = \max_{\pi}v_{\pi}(s) $$ 定义最优策略下对应的最优动作价值函数： $$ q_{*}(s,a) = \max_{\pi}q_{\pi}(s,a) $$ 针对状态 $s$ 进行动作 $a$ 决策后可得到奖励 $R_s^a$，为了追求最优动作价值，最优策略会要求未来的每个可能的状态对应价值也都是最优的（考虑衰减折现）： $$q_{*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{*}(s')= R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^a\max_{a'}q_{*}(s',a')$$ 同理可得，为了追求最优状态价值，最优策略会要求未来的每个可能的动作对应价值也都是最优的： $$v_{*}(s) = \max_a(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{*}(s'))$$ 以上两个公式也被称为贝尔曼最优方程（Bellman optimality equation），其描述了最优策略下状态价值和动作价值的转换关系
动态规划求解
动态规划（Dynamic Programming, DP）
- 动态规划的思路（1）对问题进行拆解，将一个复杂问题的最优解拆成若干个小问题的最优解（2）针对子问题状态之间的递推关系，根据子问题的解得出原始问题的结
- 用于强化学习的动态规划方法有两种（1）策略迭代，策略评估和策略提升不断循环交替，直至最后得到最优策略（2）价值迭代，直接使用贝尔曼最优方程来进行动态规划，得到最终的最优状态价值
1_study/algorithm/动态规划算法/维特比算法 Viterbi 就是一种典型的动态规划算法
策略迭代（policy iteration）
- 策略评估（policy evaluation）阶段：从任意一个状态价值函数开始，依据给定的策略 $\pi$，结合贝尔曼期望方程、状态转移概率和奖励同步迭代更新状态价值函数，直至其收敛，得到该策略下最终的状态价值函数 $v(\pi)$；其中第 $k$ 轮迭代过程中的状态价值更新过程如下： $$
v_{k+1}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{k}(s')) $$
- 策略提升（policy improvement）阶段：基于任意一个给定策略 $\pi$，根据策略评估阶段得到的状态价值 $v(\pi)$ 来更新（比如贪婪法）策略，直至其收敛，得到最优策略 $\pi^{*}$ 和状态价值 $v(\pi^{*})$
贪婪法：调整行动策略时，贪心地在每一个状态选择动作价值最大的动作；即 Agent 在某个状态下行为原则，是确保 Agent 在能够到达后续所有可能的状态中状态价值最大
价值迭代（value iteration）
- 价值迭代，可以看作只进行一轮策略评估（未收敛）就进行策略更新的策略迭代算法
- 价值迭代中不存在显式的策略，只是利用贝尔曼最优方程维护了一个状态价值函数，从而大幅减少了迭代次数和计算成本；其中第 $k$ 轮迭代过程中的状态价值更新过程如下：
$$ v_{k+1}(s) = \max_{a \in A}(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{k}(s')) $$
- 当状态价值函数收敛为 $v^{*}$ 时，再利用最优状态价值根据以下等式恢复出最优策略 $\pi^{*}$
$$ \pi^{*}=\arg \max_{a \in A}{R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av^{*}(s') } $$ 分析与总结：
- 动态规划算法使用全宽度（full-width）的回溯机制来进行状态价值的更新，即每一次回溯更新某一个状态的价值时，都要回溯到该状态的所有可能的后续状态，并利用贝尔曼方程更新该状态的价值
- 全宽度的价值更新方式对于状态数较少的强化学习问题还是比较有效的，但是当问题规模很大的时候，动态规划算法将会因贝尔曼维度灾难而无法使用，此时需要考虑其他求解方法
MDP 应用与进阶
部分可观察马尔可夫决策过程（POMDP）：MDP + 隐马尔可夫模型 HMM