强化学习的本质是强化学习
Published:
关于强化学习的入门级总结，主要包括基于值函数和策略函数的两大类方法。
参考了 Stanford’CS246’Reinforce Learning
以及 深度学习，邱锡鹏著
Introduction
强化学习的任务是，选择一个策略（状态$s$到动作$a$的映射），目的是最大化期望回报$E[G]$.
由于强化学习中的特点是，回报通常具有延迟性，因此回报应该综合考虑当前回报和未来回报，
\[E[G] =E[\sum_{t=0}^T \gamma r(t)], 0 < \gamma < 1\]Value Function Based Method
基于值函数的方法，本质是为状态$s$和给定状态下不同的动作$a$定义其值作为当前策略的评估，最佳的策略就是最大化值函数。
给定策略，$V(s)$为对应状态$s$的值函数，$Q(s,a)$为对应状态$s$下执行对应动作$a$的值函数。
Model-Based Method
在给定世界的模型，通常满足马尔可夫决策过程，也即给定了$s,a$之间的转移概率矩阵$P$。此时最佳的策略为确定性策略，只需要对应值函数，贪心地选择值最大的即可。
Policy Iteration
策略迭代算法，迭代地执行下列两个步骤：
- 策略评估，根据概率转移矩阵$P$评估当前策略
- 策略改进，基于评估的结果，选择最大的值函数对应的策略
对于策略评估，根据世界的马尔可夫性质，$ V= R + \gamma P V $
由于$\gamma<1$,$P$为概率转移矩阵，$I- \gamma P$可逆，上述方程有闭式解$V = (I - \gamma P)^{-1} R$
或者可以进行Jacobi迭代求解$V$，即不断令$V_{k+1} = R + \gamma P V_k$
假设$V$为闭式解，也即，$V = R+ \gamma P V$。
则可以得到，$V_{k+1} - V = \gamma P(V_k - V),V_k-V = (\gamma P)^k(V_0 - V)$
又有$\rho(\gamma P) <1$ ,因此上述的Jacobi迭代法收敛于理论解$V$.
对于策略改进部分，选择最优的$Q$函数，$\pi(s) = \text{argmax}_a Q(s,a)$
由于选择的是当前状态下的最优解，改进后的新策略将永远选择更优的解，可以简单证明使用新策略后值函数$V(s)$将优于旧策略下的值函数，证明只需用到策略改进中的$\text{ max}$的放缩以及$Q,V$两个值函数之间的关系即可，$V^{\pi_{i+1}} \ge V^{\pi_i}$, 证明细节此处暂略。
再者，当达到最优的策略的时候，策略改进后的结果将不变，此时迭代法停止。
由于策略总数仅有$A^S$ 种可能，因此上述的策略迭代算法将在$A^S$步迭代内收敛。
Value Iteration
策略迭代算法将策略评估和策略改进分为两个不同的步骤，而值迭代的核心思想是，既然策略改进中总是选择最优的值函数，那么可以在策略评估的过程中直接对最优解进行评估，相当于将策略评估和策略改进合为一步。
值迭代的核心是，$V_{k+1}(s) = \max_a R(a,s) + \gamma \sum_{s’} P(s,s’) V_k(s’)$
上述称为贝尔曼方程，将其看作一个算子$B$，可以证明这是一个收缩算子. \(\begin{align} \Vert BV_i - BV_j \Vert & = \Vert \max_{a_i} (R + \gamma P V_i) - \max_{a_i} (R + \gamma P V_j) \Vert \\ &= \Vert \max_a \gamma P (V_i -V_j) \Vert \\ &\le \Vert V_i -V_j \Vert \Vert \max_a \gamma \sum_{s'} P(s,s') \Vert \\ &= \gamma \Vert V_i - V_j \Vert \end{align}\) 由于对于理论最优解$V$，满足$BV=V$.
因此上述策略迭代算法收敛到理论最优解$V$.
有意思的是，可以看到值迭代算法实际上是策略迭代算法的一个特例，即当策略迭代算法中的策略评估只进行一步的特例。
Model-Free Method
在已知世界模型的前提下，可以采用上述的策略迭代或者值迭代算法，但是如果世界模型未知，此时的智能体（agent）只能通过和世界交互来获取关于世界模型的信息，并且通常需要基于蒙特卡罗方法给与关于回报的估计。
关于蒙特卡罗和MCMC，感兴趣也可以移步至 蒙特卡罗方法
使用蒙特卡罗方法估计回报作为$Q$值，
\[Q_n= \frac{1}{n} \sum_i G_i = \frac{1}{n} (G_n+ (n-1)Q_{n-1}) = Q_{n-1} +\frac{1}{n}(G_n - Q_{n-1})\]更一般地，取超参数$\alpha>\frac{1}{n}$ ，表示对于新的采样赋予更多的权重，在变化的世界模型也更为合理，给予方法一定程度遗忘过去的可能。
对于Model-Free Method，更重要的内容是利用（Exploitation）和探索（Exploration）之间的矛盾，由于世界的信息是未知的，为了准确地利用蒙特卡罗方法评估，需要不断利用旧的策略。但如果一直采用旧的策略，又不能发现可能潜在的更优的新策略。
通常解决上述矛盾的方法是$\epsilon$-贪心策略，以$\epsilon$的概率随机选择一种策略，以$1-\epsilon$的概率选择原有的最佳策略。
可以证明，$\epsilon$-贪心策略也满足$V$值函数的单调性质，证明的过程用到了一些放缩和构造，此处暂略。本质上，在策略迭代算法中，选取最佳的策略可以使得单调递增，在$\epsilon$-贪心策略中，可以使得期望的值函数单调递增。
Temporal Difference
上述的蒙特卡洛估计没有基于世界的马尔可夫性的假设，利用上述假设，可以得到时序差分方法（Temporal Difference，TD）。
如果令
\[Q_n= Q_{n-1} +\alpha (G_n - Q_{n-1}) \approx Q_{n-1} +\alpha (r +\gamma Q_{n-1} - Q_{n-1})\]则为同策略的时序差分方法：SARSA。
如果令
\[Q_n= Q_{n-1} +\alpha (G_n - Q_{n-1}) \approx Q_{n-1} +\alpha (r +\gamma \max Q_{n-1} - Q_{n-1})\]则为异策略的时序差分方法：Q-Learning
本质上，两种方法的区别是，Q-Learning学习到值函数的是关于策略$\pi$，而SARSA学习到的值函数是关于策略$\pi^{\epsilon}$的。
Maximum Bias
一个有趣的问题是，由于上述的策略都在不断贪心地选择最优的$Q$值函数。
但即便得到了一个关于$Q$的无偏估计，$E[\hat Q] = Q$ ,但是上述策略计算出的$V$值函数可能仍然是有偏的。
\[E[\hat V] = E[\max \hat Q(a),\hat Q(a')] \ge \max E[\hat Q(a), \hat Q(a')]\]上式用到了$\max$函数的凸性。
Value Function Approximation
值函数近似（Value Function Approximation）是一种有效的方法，由于$(a,s)$的数目在实际问题中通常过大，用一个表格记录值函数的方式不使用。此时可以通过一些特征提取之后，得到值函数近似,$ f(a,s) \approx Q(a,s)$.
例如，不使用时序差分方法下，近似的目标是：$ \mathcal{L}(f(a,s),G)$.
在使用时序差分的方法下(以Q-Learning为例），近似的目标是：$\mathcal{L}(r + \gamma \max_a f(a,s),f(a,s))$
如果利用神经网络进行拟合，即为深度强化学习，代表的例子如Deep Q-Learning，DQN。
关于 DQN，需要使用目标网络冻结，经验池回放等技术，基于DQN还有诸多技术，一个著名的例子是 Rianbow，集成了7大技术, 可以参见 Github
Policy Function Based Method
上述的方法都是基于值函数的方法（Value Function Based Method），但是上述方法本质都是在估计状态的值函数，根据值函数选择最优的解，基于值函数的方法的弊端是不支持随机决策。在很多情况下，比如世界部分可观测、博弈对抗的情况等，随机决策往往比确定性的策略更为有效。
Policy Gradient Descent
基于策略函数的方法是直接对$\pi(a \vert s)$这个转移概率进行计算，通常采用基于梯度的方法,
\[\begin{align} \nabla E_{\theta}[G] &= E_\theta [\nabla \log p(\theta) G] \\ &= E_\theta[ \nabla \log \prod_t\pi(a \vert s) p(s' \vert s,a) G] \\ &= E_\theta[ \nabla (\sum_t \log\pi(a \vert s) + \sum_t \log p(s' \vert s,a)) G] \\ &= E_\theta [G \sum_t \nabla \log\pi(a \vert s)] \end{align}\]Gradient Descent with Baseline
Baseline方法引入一个与动作$a$无关，仅与状态$s$有关的基准量$b(s)$.
\[\begin{align} E_\theta [b(s)\nabla \log\pi(a \vert s)] &= E_s [E_a[b(s)\nabla \log\pi(a \vert s)]]\\ &= E_s [\int_a b(s)\nabla \pi(a \vert s) ]\\ &= E_s[b(s) \nabla \int \pi(a \vert s)] \\ &= E_s[b(s) \nabla 1] \\ &= 0 \end{align}\]因此，在原本的梯度上减去作为Baseline的$b(s)$.
\[\nabla E_{\theta}[G] = E_\theta [G \sum_t \nabla \log\pi(a \vert s)] = E_\theta [(G-b) \sum_t \nabla \log\pi(a \vert s)]\]不仅不改变结果，而且可以减小方差，此即为Basline优化后的策略梯度下降算法。