deep reinforcement learning

强化学习算法分类

强化学习算法的分类图如下图所示：

model-based && model-free

在马尔可夫决策过程（MDP）中，有五个关键元素：$S,A,P,R,\gamma$，分别代表状态空间，动作空间，状态转移函数，奖励函数以及折扣因子（防止奖励的累加和趋于无穷导致无偏向）。当这些元素全部已知时，模型就是已知的，可以无需和环境交互，直接在模型上进行计算，比如使用value iteration或者policy iteration等方法。但是现实中agent往往无法知道状态转移函数以及奖励函数，这时模型就是未知的，需要通过和环境交互，不断试错，观察环境相关信息并利用反馈的奖励信号来不断学习。如果通过学习习得了状态转移函数以及奖励函数，那么就可以使用前述方法进行求解，这就是model-based方法。如果不对环境进行建模，直接寻找最优策略，那就是model-free方法。

value-based && policy-based

基于价值的方法需要对动作价值函数$Q^\pi(s,a)$进行优化，其优点在于采样效率相对较高，值函数估计方差小，不易陷入局部最优；缺点是它通常不能处理连续动作空间问题，且最终的策略通常为确定性策略而不是概率分布的形式。基于策略的方法直接对策略进行优化，通过对策略迭代更新，实现累积奖励最大化。与基于价值的方法相比，基于策略的方法具有策略参数化简单、收敛速度快的优点，且适用于连续或高维的动作空间。除了基于价值的方法和基于策略的方法，更流行的是两者的结合，这衍生出了Actor-Critic方法。Actor-Critic方法结合了两种方法的优点，利用基于价值的方法学习Q值函数或状态价值函数V来提高采样效率（Critic），并利用基于策略的方法学习策略函数（Actor），从而适用于连续或高维的动作空间。

MC && TD

时间差分（Temporal Difference，TD）方法和蒙特卡罗（Monte Carlo，MC）方法最大的不同之处在于如何进行参数更新，蒙特卡罗方法必须等到一条轨迹生成（真实值）后才能更新，而时间差分方法在每一步动作执行都可以通过自举法（估计值）及时更新。这种差异将使时间差分方法具有更大的偏差，而使蒙特卡罗方法具有更大的方差。

on-policy && off-policy

在线策略（On-Policy）方法和离线策略（Off-Policy）方法依据策略学习的方式对强化学习算法进行划分。在线策略方法要求智能体要评估提升的策略和与环境交互的策略必须是相同的，而离线策略方法评估和提升的策略与生成数据的策略是不同的，它可以利用其他智能体与环境交互生成的数据来提升自己的策略。

Policy（策略）与Policy Optimization（策略优化）

策略(Policy)是一种从状态(State)到动作(Action)的映射，而所谓的策略优化(Policy Optimization)就是要寻找到最优的映射。策略优化算法大体分为两种：基于value的方法需要对价值函数进行建模和估计，以此为依据制定策略，代表方法有Q-learning和DQN；基于策略的方法则是对策略函数直接进行建模和估计，优化策略函数使奖励最大化，代表方法有REINFORCE和交叉熵算法等。而将二者结合所产生的结构————Actor-Critic则是在Model-free类方法中应用最广的结构，它通过对价值函数的优化来引导策略改进。

首先回顾一下策略函数、状态价值函数、状态动作价值函数、动态规划、策略评估、策略迭代和价值迭代。

策略函数（Policy Function）常表示为：$\pi(s):S\rightarrow A$，是从状态集合到动作集合的一个映射，策略函数的最优化是强化学习算法的核心任务。

状态价值函数（State Value Function）也可简称为价值函数，用于评价策略的优劣。其意义是，当处于状态$s_t$时，从下一个状态$s_{t+1}$开始，直至一个Episode结束，都按照策略$\pi(s)$与env进行交互，将从$s_{t+1}$到$s_\infty$过程中得到的reward的降权值累加起来，取其期望值作为状态$s_t$的价值。

状态动作价值函数（State-action Value Function）也可简称为Q值函数，是对状态-动作对优劣的评估，相比状态价值函数，除了给定状态外还要给定某个动作$a$。

动态规划（Dynamic Programming，DP）是一种解决复杂问题的思想方法，其整体思想就是化繁为简，将复杂问题分解为一个个相对简单的子问题，然后通过解决子问题后再串起来，理论上也就解决了整个复杂问题了。所以一个问题要想去用DP去解决的话它必定要满足这两个条件：第一，问题有一定结构并且可以进行拆分成一步步的子问题；第二，子问题需要出现多次并可以用解决方法不断去套用迭代。而MDP刚好符合这两个特征，首先MDP的转移状态可以分解成连续的子状态之间的转移，然后可以用贝尔曼方程不断去套用迭代计算状态和行动的价值函数继而得到单个状态的最优策略，从而最后再全部串起来就ok了。

策略评估（Policy Evaluation）是做策略迭代的前置任务，在做出最好的选择之前，首先要对所有选择做评估，然后才能进行选择。具体来说就是通过贝尔曼期望方程来迭代计算每个状态的价值函数。

策略迭代（Policy Iteration），如果我们已经完成了对一个策略的评估，想要提升这个策略怎么办？很好办，那就基于前边得到的评估结果，按照贪心的思想，总是挑往价值函数大的方向走就好啦！每次策略评估之后，从值函数中寻找到可以使后继状态价值增加最多的行为作为新的策略，然后再次评估，以此类推，一直到价值函数不再发生变化为止。

价值迭代（Value Iteration），这种算法更加简单粗暴，指导思想也很简单，就是使用贝尔曼最优方程，将策略改进视为值函数的改进，每一步都求取最大的值函数。

Value based optimization（基于价值的优化）

基于价值的优化方法往往需要在策略估计和策略提升两个过程之间交替，其大致的解决方法如下图所示：

对于简单且离散的问题（比如4x4迷宫的最短路径问题），直接使用表格方法即可。但是对于复杂或连续的问题就需要进行价值函数的拟合。对于model-free问题，需要使用MC或者TD方法来更新参数，对于model-based的问题，直接用规划方法如策略迭代等来更新参数即可。

Policy based optimization（基于策略的优化）

深度强化学习中的策略可以被分为确定性策略和随机性策略，前者对于某种状态，其能选择的动作是确定的，后者则是不同的动作有不同的概率。在优化过程中，可以使用基于梯度的方法，比如REINFORCE，也可以使用无梯度的方法，比如交叉熵方法。基于策略的优化方法的基本思路和任何启发式算法的思路是一致的，即建立输入和输出之间的可微的参数模型，然后通过梯度优化搜索合适的参数，具体分为三个步骤：首先确立策略模型$\pi_\theta(x)$，然后构建优势评价函数（往往是累积折扣奖励）$metric=J(\pi_\theta)$，最后进行参数更新$\theta=\theta+\alpha\nabla_\theta J(\pi_\theta)$。其中确立策略模型需要借助神经网络，输入是状态信息，输出是动作的概率分布（以随机性策略为例），即$\pi_\theta:S\rightarrow P(A)$。

基于梯度的优化

基于梯度的优化方法是使用在期望回报（总的奖励）上的梯度估计来进行梯度下降以改进策略，而这个期望回报是从采样轨迹中得到的。这里我们把关于策略参数的梯度叫作策略梯度（Policy Gradient）。我们将从一个状态开始的累计折扣奖励表示为$J(\pi)=\mathbb{E}_{r\sim\pi}[R(\tau)]$，那么策略梯度$PG$可以表示为$\Delta\theta=\alpha\nabla_\theta J(\pi_\theta)=\alpha\mathbb{E}_{\tau\sim\pi_\theta}\left[\sum_{t=0}^T\nabla_\theta(log\pi_\theta(A_t|S_t))Q^{\pi_\theta}(S_t,A_t)\right]$，这就是最原始的REINFORCE方法。对上述公式的直观解释是：前半部分是一个方向向量，参数在这个方向上更新可以增大或降低给定状态下某个动作发生的可能性；后半部分是一个标量，以累积折扣奖励的大小作为权重；因此这个公式的直观解释就是增大高回报状态-动作对出现的概率，降低低回报状态-动作对出现的概率。

无梯度优化

无梯度优化的方法包括交叉熵方法、协方差矩阵自适应方法、爬山法等等，这并非主流方法，因此本文不做涉猎。

Actor-Critic（AC框架）

在策略梯度方法中，如果使用MC或TD进行估计，那么产生的更新往往有较大的方差。一种改进方式是使用一个如基于价值的优化中的批判者（Critic）来估计动作价值函数，此时如果我们还采用了参数化的价值函数近似方法，就构成了Actor-Critic结构，它是一个既基于策略也基于价值的方法。它同时学习Actor函数————策略函数$\pi(s)$以及Critic函数————状态价值函数$V(s)$，并使用自举法(Bootstrapping)的思想来估计Q值函数。相比于策略梯度方法，最重要的改动在于提供了多种可选择的Critic函数（原Q值函数也可以作为Critic函数）：总回报、某个动作之后的回报、TD残差等等，当选择的Critic函数是以牺牲偏差为代价减小方差的几种函数时，就得到了经典的AC方法。