强化学习基础巩固（一）——马尔可夫决策过程

这个学期需要找实习了，为了巩固一下基础知识，在这个系列中重温强化学习基础。本系列的知识基于Easy RL进行梳理巩固。

马尔可夫决策过程

首先重温马尔可夫性质：即一个状态的转移只依赖于当前状态，而与之前的历史状态无关。
马尔可夫决策过程是我们最常用的强化学习问题框架，相比于马尔可夫奖励过程，马尔可夫决策过程多了动作空间，允许智能体在不同的状态下采取不同的动作。此外，状态转移也多了一个条件，变成$P(s_{t+1}=s^\prime|s_t=s,a_t=a)$。对于奖励函数，也多了一个条件：当前动作，变成$R(s_t=s,a_t=a)=\mathbb{E}[r_t|s_t=s,a_t=a]$。

价值函数

在马尔可夫决策过程中，价值函数可写为

$$V_\pi(s) = \mathbb{E}_\pi[G_t|s_t=s]$$

其中，期望基于我们当前采取的策略。
为表示某个动作$a$对应的价值，引入$Q$函数——动作价值函数。$Q$函数定义的是在某一个状态采取某一个动作可能得到的总回报的期望，即：

$$Q_\pi(s,a) = \mathbb{E}_\pi[G_t|s_t=s,a_t=a]$$

那么我们可以在这里得到状态价值函数和动作价值函数的关系：

$$V_\pi(s) = \sum_{a\in A} \pi(a|s) Q_\pi(s,a)$$

在这里，我们直接写出$Q$函数的贝尔曼方程：

$$\begin{aligned} Q_\pi(s,a) &= R(s,a) + \gamma \sum_{s' \in S} p(s'|s,a) V_\pi(s') \\ &= R(s,a) + \gamma \sum_{s' \in S} p(s'|s,a) \sum_{a \in A} \pi(a|s') Q_\pi(s', a) \end{aligned}$$

$V$函数的贝尔曼方程本应为：

$$V_\pi(s) = R(s,a) + \gamma \sum_{s' \in S} p(s'|s,a) V_\pi(s')$$

但这里出现了未定义的$a$，故我们计算$V$函数的贝尔曼期望方程更有意义，即：

$$\begin{aligned} V_\pi(s) &= \mathbb{E}[R(s,a) + \gamma V_\pi(s')] \\ &= \sum_{a\in A} \pi(a|s) \left (R(s,a) + \gamma \sum_{s' \in S} p(s'|s,a) V_\pi(s') \right ) \end{aligned}$$

同理有$Q$函数的贝尔曼期望方程：

$$Q_\pi(s,a) = \mathbb{E}[R(s,a) + \gamma Q_\pi(s',a')]$$

策略迭代

策略迭代即通过计算$Q$函数，并不断更新，同时收敛状态价值函数与动作价值函数。
我们通过数次迭代后，会得到一个更好的或不变的策略，而不会变差。当迭代完成后，我们就会得到一个最佳策略，此时让$Q$函数最大的动作会直接得到状态价值函数：

$$Q_\pi(s,\pi'(s)) = \max_a Q_\pi(s,a)=Q_\pi (s,\pi(s))=V_\pi(s)$$

那么我们就得到了贝尔曼最优方程：

$$V_\pi(s) =\max_a Q_\pi(s,a)$$

这表明，最佳策略下，一个状态的价值必须等于在这个状态下选取最好动作得到的回报的期望。只有整个状态已经收敛后，即得到最佳价值函数后，贝尔曼最优方程才能成立：

$$V^*(s) = \max_a Q^*(s,a)$$

那么可以给出$Q$函数的贝尔曼最优方程：

$$Q^*(s,a) = R(s,a) + \gamma \sum_{s' \in S} p(s'|s,a) \max_{a'} Q^*(s',a')$$

这就是Q-Learning算法的更新基础。
同理我们可以获得状态价值函数的贝尔曼最优方程：

$$V^*(s) = \max_a \left (R(s,a) + \gamma \sum_{s' \in S} p(s'|s,a) V^*(s') \right )$$

即状态价值函数的转移。

Q&A

Q：为什么马尔可夫奖励过程中需要设置折扣因子？
A：

1. 有些马尔可夫奖励过程为环，并没有终止节点，要避免无穷奖励。
2. 表示不确定性，需要尽快的获得奖励而不是在未来的某个时刻获得奖励。
3. 可以动态调整，如设置为0时表示只关注当前奖励。

Q：为什么很难求得矩阵形式的贝尔曼方程解析解？
A：因为随着状态空间复杂度的增加，矩阵求拟求解复杂度以$O(N^3)$上升。

Q：计算贝尔曼方程的常见方法有哪些，有什么区别？
A：

1. 蒙特卡洛方法：用大量的采样直接估计价值函数的值
2. 动态规划方法：一直迭代对应的贝尔曼方程，直至收敛来获得价值函数的值。
3. 时序差分方法，实为蒙特卡洛方法与动态规划方法的结合。

Q：马尔可夫奖励过程与马尔可夫决策过程的区别？
A：马尔可夫决策过程相对于马尔可夫奖励过程多了一个决策过程，所以状态转移多出动作$a$作为条件，表示状态转移同时取决于当前状态与当前动作。这也导致价值函数多了一个动作作为条件，表示当前状态采取动作可能得到的回报。
二者之间存在转换关系，在已知策略函数时，可以通过直接将动作加和得到马尔可夫奖励过程的转移概率。

Q：马尔可夫决策过程的状态转移和马尔可夫奖励过程的状态转移的结构或计算方面的差异有哪些？
A：对于马尔可夫奖励过程，状态转移概率是确定的。而马尔可夫决策过程中，由于多出动作作为输出，状态转移受动作影响而不再确定。

Q：如何寻找最佳策略，方法有哪些？
A：获得最佳价值函数后，可以直接通过$\argmax_a Q$找到最佳策略。具体方法如下，
（1）穷举法（一般不使用）：假设我们有有限个状态、有限个动作可能性，那
么每个状态我们可以采取 $A$ 种动作策略，那么总共就是 $|A|^{|S|}$ 个可能的策略。我们可以把他们穷举一遍，然后算出每种策略的价值函数，对比一下就可以得到最佳策略。但是这种方法的效率极低。
（2）策略迭代：一种迭代方法，其由两部分组成，以下两个步骤一直在迭代进行，最终收敛，其过程有些类似于机器学习中的 EM 算法（期望-最大化算法）。第一个步骤是策略评估，即当前我们在优化这个策略 $\pi$，在优化过程中通过评估从而得到一个更新的策略；第二个步骤是策略提升，即取得价值函数后，进一步推算出它的 $Q$ 函数，得到它的最大值。
（3）价值迭代：我们一直迭代贝尔曼最优方程，通过迭代，其能逐渐趋向于最佳策略，这是价值迭代方法的核心。我们为了得到最佳的$V^∗$，对于每个状态的$V^*$值，直接使用贝尔曼最优方程进行迭代，迭代多次之后它就会收敛到最佳策略及其对应的状态，这里是没有策略函数的。

Q：如果数据流不具备马尔可夫性质怎么办？怎么处理？
A：如果不具备马尔可夫性质，即下一个状态与之前的状态也有关，若仅用当前的状态来求解决策过程，势必导致决策的泛化能力变差。为了解决这个问题，可以利用循环神经网络对历史信息建模，获得包含历史信息的状态表征，表征过程也可以使用注意力机制等手段，最后在表征状态空间求解马尔可夫决策过程问题。

Q：分别写出基于状态价值函数的贝尔曼方程与基于动作价值函数的贝尔曼方程
A：基于状态价值函数：

$$V_\pi(s) = \sum_{a \in A}\pi(a|s)\sum_{s' \in S}p(s'|s,a)[r + \gamma V_\pi(s')]$$

基于动作价值函数：

$$Q_\pi(s,a) = \sum_{s' \in S}p(s'|s,a)[r+\gamma V_\pi(s')]$$

Q：为什么最佳价值函数$V^*$和最佳策略$\pi^*$等价？
A：最佳价值函数的定义为$V^*(s) = \max_\pi V_\pi (s)$，即搜索一种策略让每个状态价值最大。$V^*$就是到达每个状态的最大价值，同时我们的策略就可以说是最佳策略，即$\pi^*(s) = \argmax_\pi V_\pi(s)$。

Q：手写一下第$n$步的价值函数更新公式。另外，当$n$越来越大时，价值函数的期望和方差是分别变大还是变小？
A：公式：

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left [ \sum^n_{i=1}\gamma^{i-1}r_{t+i} + \gamma^n\max_aQ(s',a)-Q(s,a) \right ]$$

$n$越大，方差越大，期望偏差越小。