【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.有模型学习
考虑多步强化学习任务，暂且先假定任务对应的马尔可夫决策过程四元组$E=<X,A,P,R>$均为已知，这样的情形称为“模型已知”，即机器已对环境进行了建模，能在机器内部模拟出与环境相同或近似的状况。在已知模型的环境中学习称为“有模型学习”（model-based learning）。此时，对于任意状态$x,x’$和动作$a$，在$x$状态下执行动作$a$转移到$x’$状态的概率$P_{x \to x’}^a$是已知的，该转移所带来的奖赏$R_{x \to x’}^a$也是已知的。为便于讨论，不妨假设状态空间$X$和动作空间$A$均为有限。
2.策略评估
在模型已知时，对任意策略$\pi$能估计出该策略带来的期望累积奖赏。令函数$V^{\pi}(x)$表示从状态$x$出发，使用策略$\pi$所带来的累积奖赏；函数$Q^{\pi}(x,a)$表示从状态$x$出发，执行动作$a$后再使用策略$\pi$带来的累积奖赏。这里的$V(\cdot)$称为“状态值函数”（state value function），$Q(\cdot)$称为“状态-动作值函数”（state-action value function），分别表示指定“状态”上以及指定“状态-动作”上的累积奖赏。
由累积奖赏的定义，有状态值函数：
\[\begin{cases} V_T^{\pi} (x) = \mathbb{E}_{\pi} \left[ \frac{1}{T} \sum_{t=1}^T r_t \mid x_0 = x \right], \quad \text{T步累积奖赏} \\ V_{\gamma}^{\pi}(x) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{+\infty} \gamma^t r_{t+1} \mid x_0 = x \right] , \quad \gamma \text{折扣累积奖赏} \end{cases} \tag{1}\]个人注解：函数$V$是基于状态$x$，在执行策略$\pi$后所能得到的累积奖赏，式(1)列出来了两种不同的累积奖赏计算方式。
令$x_0$表示起始状态，$a_0$表示起始状态上采取的第一个动作；对于$T$步累积奖赏，用下标$t$表示后续执行的步数。我们有状态-动作值函数：
\[\begin{cases} Q_T^{\pi} (x,a) = \mathbb{E}_{\pi} \left[ \frac{1}{T} \sum_{t=1}^T r_t \mid x_0 = x, a_0 = a \right] \\ Q_{\gamma}^{\pi}(x,a) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{+\infty} \gamma^t r_{t+1} \mid x_0 = x,a_0 = a \right] \end{cases} \tag{2}\]个人注解：函数$Q$是基于状态$x$，先执行动作$a$，然后再执行策略$\pi$后所能得到的累积奖赏。
由于MDP具有马尔可夫性质，即系统下一时刻的状态仅由当前时刻的状态决定，不依赖于以往任何状态，于是值函数有很简单的递归形式。对于$T$步累积奖赏有：
\[\begin{align} V_T^{\pi}(x) &= \mathbb{E}_{\pi} \left[ \frac{1}{T} \sum_{t=1}^T r_t \mid x_0 = x \right] \\&= \mathbb{E}_{\pi} \left[ \frac{1}{T} r_1 + \frac{T-1}{T} \frac{1}{T-1} \sum_{t=2}^T r_t \mid x_0 = x \right] \\&= \sum_{a \in A} \pi (x,a) \sum_{x' \in X} P_{x\to x'}^a \left( \frac{1}{T} R_{x \to x'}^a + \frac{T-1}{T} \mathbb{E}_{\pi} \left[ \frac{1}{T-1} \sum_{t=1}^{T-1} r_t \mid x_0 = x' \right] \right) \\&= \sum_{a \in A} \pi (x,a) \sum_{x' \in X} P_{x\to x'}^a \left( \frac{1}{T} R_{x \to x'}^a + \frac{T-1}{T} V_{T-1}^{\pi} (x') \right) \end{align} \tag{3}\]这样的递归等式称为Bellman等式。
个人注解：$\pi (x,a) = P(action=a \mid state = x)$表示在状态$x$下选择动作$a$的概率。
类似的，对于$\gamma$折扣累积奖赏有：
\[\begin{align} V_{\gamma}^{\pi} (x) &= \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_{t+1} \mid x_0 = x \right] \\&= \mathbb{E}_{\pi} \left[ r_1 + \sum_{t=1}^{\infty} \gamma^t r_{t+1} \mid x_0 = x \right] \\&= \mathbb{E}_{\pi} \left[ r_1 + \gamma \sum_{t=1}^{\infty} \gamma^{t-1} r_{t+1} \mid x_0 = x \right] \\&= \sum_{a \in A} \pi (x,a) \sum_{x' \in X} P_{x \to x'}^a \left( R_{x \to x'}^a + \gamma \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_{t+1} \mid x_0 = x' \right] \right) \\&= \sum_{a \in A} \pi (x,a) \sum_{x' \in X} P_{x \to x'}^a \left( R_{x \to x'}^a + \gamma V_{\gamma}^{\pi} (x') \right) \end{align} \tag{4}\]个人注解：式(3)和式(4)通过利用MDP的马尔可夫性质，将未来长期累积奖赏递归地分解为“当前一步奖赏+下一状态价值”，从而建立了价值函数的Bellman递归形式。该推导的意义在于：将原本难以直接求解的长期累积奖赏问题转化为可迭代计算的递归问题，使得策略$\pi$的预期累积奖赏能够被有效评估与优化，是动态规划、价值迭代、Q-learning等强化学习方法的理论基础。
需注意的是，正是由于$P$和$R$已知，才可以进行全概率展开。
用上面的递归等式来计算值函数，实际上就是一种动态规划算法。对于$V_T^{\pi}$，可设想递归一直进行下去，直到最初的起点；换言之，从值函数的初始值$V_0^{\pi}$出发，通过一次迭代能计算出每个状态的单步奖赏$V_1^{\pi}$，进而从单步奖赏出发，通过一次迭代计算出两步累积奖赏$V_2^{\pi}$，$\cdots \cdots$图16.7中算法遵循了上述流程，对于$T$步累积奖赏，只需迭代$T$轮就能精确地求出值函数。
对于$V_{\gamma}^{\pi}$，由于$\gamma^t$在$t$很大时趋于0，因此也能使用类似的算法，只需将图16.7算法的第3行根据式(4)进行替换。此外，由于算法可能会迭代很多次，因此需设置一个停止准则。常见的是设置一个阈值$\theta$，若在执行一次迭代后值函数的改变小于$\theta$则算法停止；相应的，图16.7算法第4行中的$t=T+1$需替换为：
\[\max_{x\in X} \lvert V(x) - V'(x) \rvert < \theta \tag{5}\]有了状态值函数$V$，就能直接计算出状态-动作值函数：
\[\begin{cases} Q_T^{\pi} (x,a) = \sum_{x' \in X} P_{x \to x'}^a \left( \frac{1}{T} R_{x \to x'}^a + \frac{T-1}{T} V_{T-1}^{\pi} (x') \right) \\ Q_{\gamma}^{\pi} (x,a) = \sum_{x' \in X} P_{x \to x'}^a \left( R_{x \to x'}^a + \gamma V_{\gamma}^{\pi} (x') \right) \end{cases} \tag{6}\]3.策略改进
对某个策略的累积奖赏进行评估后，若发现它并非最优策略，则当然希望对其进行改进。理想的策略应能最大化累积奖赏：
\[\pi ^* = \underset{\pi}{\text{arg max}} \sum_{x \in X} V^{\pi} (x) \tag{7}\]一个强化学习任务可能有多个最优策略，最优策略所对应的值函数$V^*$称为最优值函数，即：
\[\forall x \in X : V^*(x) = V^{\pi ^*}(x) \tag{8}\]注意，当策略空间无约束时式(8)的$V^*$才是最优策略对应的值函数，例如对离散状态空间和离散动作空间，策略空间是所有状态上所有动作的组合，共有$\lvert A \rvert^{\lvert X \rvert}$种不同的策略。若策略空间有约束，则违背约束的策略是“不合法”的，即便其值函数所取得的累积奖赏值最大，也不能作为最优值函数。
由于最优值函数的累积奖赏值已达最大，因此可对前面的Bellman等式(3)和(4)做一个改动，即将对动作的求和改为取最优：
\[\begin{cases} V_T^* (x) = \underset{a \in A}{\text{max}} \sum_{x' \in X} P_{x\to x'}^a \left( \frac{1}{T} R_{x \to x'}^a + \frac{T-1}{T} V^*_{T-1}(x') \right) \\ V_{\gamma}^* (x) = \underset{a \in A}{\text{max}} \sum_{x' \in X} P_{x \to x'}^a \left( R_{x \to x'}^a + \gamma V_{\gamma}^* (x') \right) \end{cases} \tag{9}\]换言之：
\[V^*(x) = \underset{a \in A}{\text{max}} Q^{\pi ^*} (x,a) \tag{10}\]代入式(6)可得最优状态-动作值函数：
\[\begin{cases} Q^*_T (x,a) = \sum_{x' \in X} P_{x \to x'}^a \left( \frac{1}{T} R_{x\to x'}^a + \frac{T-1}{T} \underset{a' \in A}{\text{max}} Q^*_{T-1}(x',a') \right) \\ Q^*_{\gamma} (x,a) = \sum_{x' \in X} P_{x \to x'}^a \left( R_{x \to x'}^a + \gamma \underset{a' \in A}{\text{max}} Q^*_{\gamma} (x',a') \right) \end{cases} \tag{11}\]上述关于最优值函数的等式，称为最优Bellman等式，其唯一解是最优值函数。
最优Bellman等式揭示了非最优策略的改进方式：将策略选择的动作改变为当前最优的动作。显然，这样的改变能使策略更好。不妨令动作改变后对应的策略为$\pi ‘$，改变动作的条件为$Q^{\pi} (x, \pi ‘ (x)) \geqslant V^{\pi} (x)$，以$\gamma$折扣累积奖赏为例，由式(6)可计算出递推不等式：
\[\begin{align} V^{\pi} (x) & \leqslant Q^{\pi} (x, \pi ' (x)) \\&= \sum_{x' \in X} P_{x \to x'}^{\pi ' (x)} \left( R_{x \to x'}^{\pi ' (x)} + \gamma V^{\pi}(x') \right) \\& \leqslant \sum_{x' \in X} P_{x \to x'}^{\pi ' (x)} \left( R_{x \to x'}^{\pi ' (x)} + \gamma Q^{\pi} (x', \pi ' (x')) \right) \\&= \sum_{x' \in X} P_{x \to x'}^{\pi '(x)} \left( R_{x \to x'}^{\pi ' (x)} + \sum_{x'' \in X} P_{x'\to x''}^{\pi '(x')} \left( \gamma R_{x' \to x''}^{\pi'(x')} + \gamma^2 V^{\pi} (x'') \right) \right) \\& \leqslant \sum_{x' \in X} P_{x \to x'}^{\pi'(x)} \left( R_{x \to x'}^{\pi'(x)} + \sum_{x'' \in X} P_{x' \to x''}^{\pi '(x')} \left( \gamma R_{x'\to x''}^{\pi '(x')} + \gamma^2 Q^{\pi}(x'', \pi'(x'')) \right) \right) \\& \leqslant \cdots \\& \leqslant \sum_{x' \in X} P_{x \to x'}^{\pi '(x)} \left( R_{x\to x'}^{\pi' (x)} + \sum_{x'' \in X} P_{x' \to x''}^{\pi '(x')} \left( \gamma R_{x' \to x''}^{\pi '(x')} + \sum_{x'' \in X} P_{x'' \to x'''}^{\pi '(x'')} \left( \gamma^2 R_{x'' \to x'''}^{\pi '(x'')} + \cdots \right) \right) \right) \\& = V^{\pi'} (x) \end{align} \tag{12}\]个人注解：在式(12)中，推导的第一步用了$Q^{\pi} (x, \pi ‘ (x)) \geqslant V^{\pi} (x)$这个公式，第二步基于式(6)中的第2个式子，此后就一直循环用这两个式子推导。最后一步参考式(1)中的第2个式子。
值函数对于策略的每一点改进都是单调递增的，因此对于当前策略$\pi$，可放心地将其改进为：
\[\pi ' (x) = \underset{a \in A}{\text{arg max}} Q^{\pi} (x,a) \tag{13}\]直到$\pi ‘$与$\pi$一致、不再发生变化，此时就满足了最优Bellman等式，即找到了最优策略。
4.策略迭代与值迭代
由第2部分和第3部分，我们知道了如何评估一个策略的值函数，以及在策略评估后如何改进至获得最优策略。显然，将这两者结合起来即可得到求解最优解的方法：从一个初始策略（通常是随机策略）出发，先进行策略评估，然后改进策略，评估改进的策略，再进一步改进策略，$\cdots \cdots$不断迭代进行策略评估和改进，直到策略收敛、不再改变为止。这样的做法称为“策略迭代”（policy iteration）。
- 第1步：$\lvert A(x) \rvert$是$x$状态下所有可选动作数。
- 第4步：参考式(3)。注意，本文只考虑有模型学习，因此$P_{x \to x’}^a$和$R_{x \to x’}^a$是已知的。此外，在第1部分，我们已经假设过状态空间$X$和动作空间$A$都是有限的，其分别表示整个任务过程（即所有$t$）中所有可能出现的状态合集和动作合集。
- 第11步：式(6)计算Q值。
图16.8给出的算法描述，就是在基于$T$步累积奖赏策略评估的基础上，加入策略改进而形成的策略迭代算法。类似的，可得到基于$\gamma$折扣累积奖赏的策略迭代算法。策略迭代算法在每次改进策略后都需重新进行策略评估，这通常比较耗时。
由式(12)可知，策略改进与值函数的改进是一致的，因此可将策略改进视为值函数的改善，即由式(9)可得：
\[\begin{cases} V_T (x) = \underset{a \in A}{\text{max}} \sum_{x' \in X} P_{x\to x'}^a \left( \frac{1}{T} R_{x \to x'}^a + \frac{T-1}{T} V_{T-1}(x') \right) \\ V_{\gamma} (x) = \underset{a \in A}{\text{max}} \sum_{x' \in X} P_{x \to x'}^a \left( R_{x \to x'}^a + \gamma V_{\gamma} (x') \right) \end{cases} \tag{14}\]于是可得到值迭代（value iteration）算法，如图16.9所示：
- 第3步：式(14)更新值函数。
- 最后一步输出：式(6)计算Q值。
若采用$\gamma$折扣累积奖赏，只需将图16.9算法中第3行替换为：
\[\forall x \in X : V'(x) = \underset{a \in A}{\text{max}} \sum_{x' \in X} P_{x \to x'}^a (R_{x \to x'}^a + \gamma V(x')) \tag{15}\]从上面的算法可看出，在模型已知时强化学习任务能归结为基于动态规划的寻优问题。与监督学习不同，这里并未涉及到泛化能力，而是为每一个状态找到最好的动作。
