RL 系列：1. Markov 决策过程
本文旨在阐述基于 Markov 决策过程的强化学习原理，聚焦于关键公式（省去一些繁杂的数学推导），快速领会 RL 的核心理念。
RL 概述
强化学习的理念：Agent 根据 Environment 输出的 St 和 Rt 综合判断，产生当前步骤的动作 At，放入 Environment 执行；Environment 根据 At 执行的结果，输出下一个状态 S_{t+1} 和当前动作带来的奖励 R_{t+1}，返回给 Agent。 
强化学习和监督学习的区别：
- RL 得到的时序数据不满足独立同分布；
- RL 无实时明确反馈当前 Action 是否正确，奖励信号延迟。（通过 rollout 过程从当前帧对 Action 进行采样，得到多个 observation， 每个 observe 对应一条 trajectory，即一个 State 和 Action 的序列 τ=(s0,a0,s1,a1,…)；通过最终 reward 来观测当前 trajectory 是否合适）
Markov 奖励过程
状态价值函数：\(V^t(s)\)
定义：在状态\(s\)的回报期望 定义： \[ \begin{align*} V^t(s) &= \mathbb{E}[G_t|s_t=s] \\ &= \mathbb{E}[{r_{t+1}+\gamma r_{t+2}+{\gamma}^2 r_{t+3}+...+\gamma^{T-t-1} r_T |s_t=s}] \\ \end{align*} \] 其中，\(T\)是最终时刻，\(\gamma\)是折扣因子。
为什么要加入折扣因子\(\gamma\)呢？
- 部分 Markov 过程带环，我们不希望获得无穷的奖励；
- 由于未来的不确定性，对未来的评估增加一个折扣；
- 更倾向于得到实时奖励（现在的钱比未来的钱更有价值）。
两种计算方法：
蒙特卡洛采样：从某个状态开始，把小船放到状态转移矩阵里面，让它“随波逐流”，产生多条轨迹；分别计算每条轨迹对应的回报，累积后取平均值，得到某个状态的价值。
动态规划（基于贝尔曼方程）：通过自举不断迭代贝尔曼方程，直到价值函数收敛。
价值函数的贝尔曼方程：当前状态与未来状态之间的迭代关系
表示当前状态的价值函数可以通过下个状态的价值函数来计算。 \[ V(s)=R(s)+\gamma\sum_{s'\in S}p(s'|s)V(s') \]
- \(s'\)代表未来的所有状态；\(p(s'|s)\)是从当前状态转移到未来状态的概率；
- \(V(s), V(s')\)分别对应当前、未来状态的价值。
- \(R(s)\)为即时奖励。
Markov 决策过程
策略函数： \[ \pi(a|s)=p(a_t=a|s_t=s) \]
动作价值函数（Q函数）：在状态\(s\)采取动作\(a\)，得到的回报期望。 \[ \begin{align*} Q_{\pi}(s, a) &= \mathbb{E}_{\pi}[G_t|s_t=s, a_t=a] \\ &= R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V(s') \\ \end{align*} \]
价值函数\(V_\pi(s)\)：对Q函数中的动作进行加和。 \[ \begin{align*} V_\pi(s) &= \mathbb{E}_\pi[G_t|s_t=s] \\ &= \sum_{a\in A}\pi(a|s)Q_\pi(s, a) \\ \end{align*} \]
贝尔曼期望方程
备份图：每一个空心圆圈代表一个状态：每一个实心圆圈代表一个状态-动作对。 
- 当前价值与未来价值的关联：（代入\(Q_{\pi}(s, a)\)）
\[ V_\pi(s)=\sum_{a\in A}\pi(a|s)(R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V(s')) \]
- 当前时刻的Q函数与未来时刻的Q函数之间的关联：（代入\(V_\pi(s')\)）
\[ Q_\pi(s, a)=R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)\sum_{a'\in A}\pi(a'|s')Q_\pi(s', a') \]
Markov 决策过程中的预测（策略评估）
预测：给定一个策略，我们要确定它的价值函数是多少；
控制：在没有策略的前提下，我们要确定最佳的价值函数以及对应的决策方案。
RL中的解决步骤：通过解决预测问题，进而解决控制问题。
\(V_t\)的递推公式： \[ V^{t+1}(s)=\sum_{a\in A}\pi(a|s)(R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V^t(s')) \] 贝尔曼期望备份反复迭代，然后得到一个收敛的价值函数的值。
如果给定一个策略：可以把动作\(a\)去掉，即转化为 Markov 奖励过程的表达形式： \[ V^{t+1}(s)=r_\pi(s)+\gamma P_\pi(s'|s)V_t(s') \]
Markov 决策过程中的控制
预测过程给定 Markov 决策过程和策略，因此可以估算出价值函数的值；但如果只有 Markov 决策过程，那么应该如何寻找最佳的策略，从而得到最佳价值函数呢？
最佳价值函数：搜索一种策略\(\pi\)，使得每个状态的价值最大。 \[ V^*(s)=\max_{\pi}V_\pi(s) \]
此时，得到的最佳策略为： \[ \pi^*(s)=\argmax_\pi V_\pi(s) \] 最佳策略使得每个状态的价值函数都取得最大值。
策略迭代=策略评估+策略改进
- 策略评估：给定当前的策略函数\(\pi\)，估计状态价值函数\(V\)；
- 策略改进：由\(V\)计算\(Q\)函数，最大化Q函数；通过在 Q 函数做一个贪心的搜索来进一步改进策略\(\pi\)。
策略改进
- 得到状态价值函数\(V\)后，计算Q函数：
\[ Q_{\pi_i}(s, a)=R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V_{\pi_i}(s') \]
- 对于每个状态，取使其最大化的动作，即：
\[ \pi_{i+1}(s)=\argmax_{a}Q_{\pi_i}(s, a) \]
价值迭代
贝尔曼最优方程：当前状态的最佳价值函数值必须等于：在这个状态下采取最好动作得到的回报的期望。
\[ V_\pi(s)=\max_{a\in A}Q_\pi(s, a) \]
满足贝尔曼最优方程后，采用最大化操作，有： \[ V^*(s)=\max_a Q^*(s, a) \]
\[ Q^*(s, a)=R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V^*(s') \]
最优性原理定理：一个策略\(\pi(a|s)\)在状态\(s\)达到最优价值，即\(V_\pi(s)=V^*(s)\)成立，当且仅当：对于任何从\(s\)出发能够到达的\(s\)，都已经达到了最优价值。即对于所有的\(s\)，\(V_\pi(s')=V^*(s')\)成立。
如果已知子问题\(V^*(s')\)的最优解，可以通过价值迭代函数得到最优的\(V^*(s)\)的解。即： \[ V(s)\leftarrow \max_a(R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V^*(s')) \]
价值迭代算法：获取最优策略\(\pi\)
初始化：令\(k=0\)，对于所有状态\(s\)，\(V_0(s)=0\)；
对于\(k=1:H\)（\(H\)是让\(V(s)\)收敛所需的迭代次数）
- 对于所有状态\(s\):
\[ Q_{k+1}(s, a)=R(s, a)+\gamma\sum_{s'\in S}p(s'|s, a)V_k(s') \]
- \(k\leftarrow k+1\).
迭代后提取最优策略：直接使用\(\argmax\)操作。
策略迭代与价值迭代的区别：
都可以解决 Markov 决策过程的控制问题。
策略迭代：每一次迭代的都包含一个完整策略，中间状态有意义。
价值迭代：对于所有状态，分别迭代价值函数直至收敛，得到最佳价值\(V^*\)；类似于价值从某一个状态反向传播到其他各个状态的过程，中间过程的策略和价值函数无意义。得到最优价值后，才提取最佳策略。
总结：策略迭代分两步。首先进行策略评估，即对当前已经搜索到的策略的状态价值函数进行估值；得到估值后，把 Q 函数算出来，更新策略。不断重复这两步，直到策略收敛。价值迭代直接使用贝尔曼最优方程进行迭代，从而寻找最佳的价值函数。找到最佳价值函数后，再提取最佳策略。
小结：使用动态规划算法来解 Markov 决策过程里面的预测和控制，并且采取不同的贝尔曼方程。
对于预测问题（即策略评估的问题），不停地执行贝尔曼期望方程，这样可以估计出给定的策略，然后得到价值函数；
对于控制问题，如果采取策略迭代，使用贝尔曼期望方程；如果采取价值迭代，使用贝尔曼最优方程。
