强化学习总览

Last updated on 2018-12-07…

强化学习本身是一个非常通用的人工智能范式，在直觉上让人觉得非常适合用来模拟各种时序决策任务，如语音、文本类任务。

当它和深度神经网络这种只要给我足够层和足够多的神经元，可以逼近任何函数的非线性函数近似模型结合在一起简直完美，无怪乎 DeepMind团队经常号称人工智能=深度学习+强化学习。

定义

在强化学习中，有两个可以进行交互的对象：智能体和环境：

智能体（agent）可以感知外界环境的状态（state）和反馈的奖励（reward），并进行学习和决策。智能体的决策功能是指根据外界环境的状态来做出不同的动作（action），而学习功能是指根据外界环境的奖励来调整策略。
环境（environment）是智能体外部的所有事物，并受智能体动作的影响而改变其状态，并反馈给智能体相应的奖励。

基本要素

状态s是对环境的描述，可以是离散的或连续的，其状态空间为S；
动作a是对智能体行为的描述，可以是离散的或连续的，其动作空间为A；
策略π(a|s)是智能体根据环境状态s来决定下一步的动作a的函数；
状态转移概率 p(s′|s, a)是在智能体根据当前状态 s 做出一个动作 a 之后，环境在下一个时刻转变为状态s′的概率；
即时奖励r(s, a, s′)是一个标量函数，即智能体根据当前状态s做出动作a之后，环境会反馈给智能体一个奖励，这个奖励也经常和下一个时刻的状态s′ 有关。

策略

智能体的策略（policy）就是智能体如何根据环境状态s来决定下一步的动作a，通常可以分为下面两组：

确定性策略（Deterministic Policy）是从状态空间到动作空间的映射函数π : S → A。
随机性策略（StochasticPolicy）表示在给定环境状态时，智能体选择某个动作的概率分布。

通常情况下，强化学习一般使用随机性的策略。随机性的策略可以有很多优点:

在学习时可以通过引入一定随机性更好地探索环境。
二是使得策略更加地多样性。

比如在围棋中，确定性策略总是会在同一个位置上下棋，会导致你的策略很容易被对手预测。

马尔可夫决策过程

Markov Decision Process，MDP

1、为了简单起见，我们将智能体与环境的交互看作是离散的时间序列。下图给出了智能体与环境的交互。

智能体从感知到的初始环境s0 开始，然后决定做一个相应的动作a₀，环境相应地发生改变到新的状态s₁，并反馈给智能体一个即时奖励r₁，然后智能体又根据状态s₁做一个动作a₁，环境相应改变为s₂，并反馈奖励r₂。这样的交互可以一直进行下去。其中r_t = r(s_t−1, a_t−1, s_t)是第t时刻的即时奖励。

智能体与环境的交互的过程可以看作是一个马尔可夫决策过程。

2、马尔可夫过程（Markov Process）是具有马尔可夫性的随机变量序列s₀, s₁, … ，s_t ∈ S，其下一个时刻的状态s_t+1只取决于当前状态s_t，其中p(s_t+1|s_t)称为状态转移概率

加入一个额外的变量：动作 a 其中p(s_t+1|s_t, a_t)为状态转移概率。

3、最终，给定策略π(a|s)，马尔可夫决策过程的一个轨迹（trajectory） 的概率为下图给出了马尔可夫决策过程的图模型表示

RL的目标函数

总回报

给定策略 π(a|s)，智能体和环境一次交互过程的轨迹 τ 所收到的累积奖励为总回报（return）。

假设环境中有一个或多个特殊的终止状态（terminal state），当到达终止状态时，一个智能体和环境的交互过程就结束了。
这一轮交互的过程称为一个回合（episode）或试验（trial）。
一般的强化学习任务（比如下棋、游戏）都属于这种回合式的任务。

如果环境中没有终止状态（比如终身学习的机器人），即T = ∞，称为持续性强化学习任务，其总回报也可能是无穷大。为了解决这个问题，我们可以引入一个折扣率来降低远期回报的权重。折扣回报（discounted return）定义为其中γ ∈ [0, 1]是折扣率。当γ 接近于0时，智能体更在意短期回报；而当γ 接近于1时，长期回报变得更重要。

目标函数

因为策略和状态转移都有一定的随机性，每次试验得到的轨迹是一个随机序列，其收获的总回报也不一样。强化学习的目标是学习到一个策略π_θ(a|s)来最大化期望回报（expected return），即希望智能体执行一系列的动作来获得尽可能多的平均回报。其中θ 为策略函数的参数。

RL的值函数

为了评估一个策略π 的期望回报，我们定义两个值函数：状态值函数和状态-动作值函数。

状态值函数

一个策略π的期望回报可以分解为其中V^π(s)称为状态值函数（state value function），表示从状态s开始，执行策略π得到的期望总回报 其中τ_s₀ 表示轨迹τ 的起始状态。

为了方便起见，我们用τ_0:T 来表示从轨迹s₀, a₀, s₁, … , s_T，用τ_1:T表示轨迹s₁, a₁, … , s_T，因此有τ_0:T = s₀, a₀, τ_1:T。

根据马尔可夫性V^π(s)可展开得到（公式14.18） 上式最后一行也称为贝尔曼方程（Bellman equation），表示当前状态的值函数可以通过下个状态的值函数来计算。

如果给定策略π(a|s)，状态转移概率p(s′|s, a)和奖励r(s, a, s′)，我们就可以通过迭代的方式来计算V^π(s)。

由于存在折扣率，迭代一定步数后，每个状态的值函数就会固定不变。

状态-动作值函数（Q函数）

贝尔曼方程中的第二个期望是指初始状态为s 并进行动作a，然后执行策略π 得到的期望总回报，称为状态-动作值函数（state-action value function）（公式14.19） 状态-动作值函数也经常称为Q函数（Q-function）。

状态值函数V^π(s)是Q函数Q^π(s, a)关于动作a的期望：

结合上面两个公式，Q函数可以写为

值函数的作用

值函数可以看作是对策略π的评估。如果在状态s，有一个动作a使得Q^π(s, a) > V^π(s)，说明执行动作a比当前的策略π(a|s)要好，我们就可以调整参数使得策略π(a|s)的概率增加。

RL的分类

强化学习的算法非常多，大体上可以分为基于值函数的方法（包括动态规划、时序差分学习等）、基于策略函数的方法（包括策略梯度等）以及融合两者的方法。不同算法之间的关系如下图所示。

一般而言，基于值函数的方法策略更新时可能会导致值函数的改变比较大，对收敛性有一定影响，而基于策略函数的方法在策略更新时更加更平稳些。
但后者因为策略函数的解空间比较大，难以进行充分的采样，导致方差较大，并容易收敛到局部最优解。
Actor-Critic算法通过融合两种方法，取长补短，有着更好的收敛性。

基于值函数的学习方法

值函数是对策略π的评估，如果策略π有限（即状态数和动作数都有限）时，可以对所有的策略进行评估并选出最优策略π^∗。 但这种方式在实践中很难实现。假设状态空间S 和动作空间A都是离散且有限的，策略空间为|A|^|S|，往往也非常大。

一种可行的方式是通过迭代的方法不断优化策略，直到选出最优策略。

对于一个策略π(a|s)，其Q函数为Q^π(s, a)，我们可以设置一个新的策略π′(a|s) 即π′(a|s)为一个确定性的策略，也可以直接写为如果执行π’，会有

根据上式，我们可以通过下面方式来学习最优策略：先随机初始化一个策略，计算该策略的值函数，并根据值函数来设置新的策略，然后一直反复迭代直到收敛。

基于值函数的策略学习方法中最关键的是如何计算策略π 的值函数，一般有动态规划或蒙特卡罗两种计算方式。

动态规划算法（模型已知）

从贝尔曼方程可知，如果知道马尔可夫决策过程的状态转移概率p(s′|s, a)和奖励r(s, a, s′)，我们直接可以通过贝尔曼方程来迭代计算其值函数。这种模型已知的强化学习算法也称为基于模型的强化学习（Model-Based ReinforcementLearning）算法，这里的模型就是指马尔可夫决策过程。

在已知模型时，可以通过动态规划的方法来计算。常用的方法主要有策略迭代算法和值迭代算法。

1、策略迭代（Policy Iteration）

每次迭代可以分为两步：

策略评估（policy evaluation）：计算当前策略下，每个状态的值函数，即算法14.1中的3-6步。策略评估可以通过贝尔曼方程进行迭代计算V^π(s)。如果状态数有限时，也可以通过直接求解Bellman方程来得到得到V^π(s)。
策略改进（policy improvement）：根据值函数来更新策略，即算法14.1中的7-8步。

策略迭代中的策略评估和策略改进是交替轮流进行，其中策略评估也是通过一个内部迭代来进行计算，其计算量比较大。

事实上，我们不需要每次计算出每次策略对应的精确的值函数，也就是说内部迭代不需要执行到完全收敛。

2、值迭代（Value Iteration）

值迭代方法将策略评估和策略改进两个过程合并，来直接计算出最优策略。

假设最优策略π^∗对应的值函数称为最优值函数，那么最优状态值函数V^∗(s)和最优状态-动作值函数Q^∗(s, a)的关系为

根据贝尔曼方程可知，最优状态值函数V^∗(s)和最优状态-动作值函数Q^∗(s, a)也可以进行迭代计算。这两个公式称为贝尔曼最优方程（Bellman Optimality Equation）。

值迭代方法通过直接优化贝尔曼最优方程，迭代计算最优值函数。值迭代方法如算法14.2所示。

3、策略迭代 VS 值迭代

策略迭代是根据贝尔曼方程来更新值函数，并根据当前的值函数来改进策略。每次迭代的时间复杂度最大为O(|S|³|A|³)，最大迭代次数为|A|^|S|。

值迭代算法是直接使用贝尔曼最优方程来更新值函数，收敛时的值函数就是最优的值函数，其对应的策略也就是最优的策略。每次迭代的时间复杂度最大为O(|S|²|A|)，但迭代次数要比策略迭代算法更多

值迭代和策略迭代都需要经过非常多的迭代次数才能完全收敛。在实际应用中，可以不必等到完全收敛。这样，当状态和动作数量有限时，经过有限次迭代就可以能收敛到近似最优策略。

蒙特卡罗方法（模型无关）

在很多应用场景中，马尔可夫决策过程的状态转移概率p(s′|s, a)和奖励函数 r(s, a, s′) 都是未知的。在这种情况下，我们一般需要智能体和环境进行交互，并收集一些样本。然后再根据这些样本来求解马尔可夫决策过程最优策略。

这种模型未知，基于采样的学习算法也称为模型无关的强化学习（Model-Free Reinforcement Learning）算法。

Q函数Q^π(s, a)为初始状态为s，并执行动作a后的所能得到的期望总回报，可以写为其中τ_{s₀=s,a₀=a} 表示轨迹τ 的起始状态和动作为s, a。

如果模型未知，Q函数可以通过采样来进行计算，这就是蒙特卡罗方法。对于一个策略 π，智能体从状态 s，执行动作 a 开始，然后通过随机游走的方法来探索环境，并计算其得到的总回报。

假设我们进行N 次试验，得到N 个轨迹τ⁽¹⁾, τ⁽²⁾, · · · , τ^(N)，其总回报分别为G(τ⁽¹⁾), G(τ⁽²⁾), · · · , G(τ^(N))。 Q函数可以近似为

当N → ∞时

近似估计出Q函数之后，就可以进行策略改进。然后在新的策略下重新通过采样来估计Q函数，并不断重复，直至收敛。

但在蒙特卡罗方法中，如果采用确定性策略π，每次试验得到的轨迹是一样的，只能计算出Q^π(s, π(s))，而无法计算其它动作a′ 的Q函数，因此也无法进一步改进策略。

这样情况仅仅是对当前策略的利用（exploitation），而缺失了对环境的探索（exploration），即试验的轨迹尽可能覆盖所有的状态和动作，以找到更好的策略。

为了平衡利用和探索，我们可以采用ϵ-贪心法（ϵ-greedy method）。对于一个目标策略π，其对应的ϵ-贪心法策略为这样，ϵ-贪心法将一个仅利用的策略转为带探索的策略。每次选择动作π(s)的概率为1 − ϵ + 1/|A|，其它动作的概率为 1/|A|。

同策略：在蒙特卡罗方法中，如果采样策略是π^ϵ(s)，不断改进策略也是π^ϵ(s)而不是目标策略π(s)。这种采样与改进策略相同（即都是π^ϵ(s)）的强化学习方法叫做同策略（on policy）方法。

异策略：如果采样策略是π^ϵ(s)，而优化目标是策略π，可以通过重要性采样，引入重要性权重来实现对目标策略π 的优化。这种采样与改进分别使用不同策略的强化学习方法叫做异策略（off policy）方法。

蒙特卡罗采样方法一般需要拿到完整的轨迹，才能对策略进行评估并更新模型，因此效率也比较低。

时序差分学习方法（两者结合）

时序差分学习（temporal-difference learning）是上面两者的结合。

时序差分学习是模拟一段轨迹，每行动一步(或者几步)，就利用贝尔曼方程来评估行动前状态的价值。当时序差分学习中每次更新的动作数为最大步数时，就等价于蒙特卡罗方法。

首先，将蒙特卡罗方法中Q函数的估计改为增量计算的方式，假设第N 试验后值函数的平均为其中τ_{s₀=s,a₀=a} 表示轨迹τ 的起始状态和动作为s, a。

值函数Qˆπ(s, a)在第N 试验后的平均等于第N − 1试验后的平均加上一个增量。

更一般性地，我们将权重系数 1/N 改为一个比较小的正数α。这样每次采用一个新的轨迹τ_{s₀=s,a₀=a} ，就可以更新值函数Qˆπ(s, a)。

其中增量称为蒙特卡罗误差，表示当前轨迹的真实回报G(τ_{s₀=s,a₀=a})与期望回报Qˆπ(s, a)之间的差距

在上式中，G(τ_{s₀=s,a₀=a})为一次试验的完整轨迹所得到的总回报。

为了提高效率，可以借助动态规划的方法来计算G(τ_{s₀=s,a₀=a})，而不需要得到完整的轨迹。

从s, a开始，采样下一步的状态和动作(s′, a′)，并得到奖励r(s, a, s′)，然后利用贝尔曼方程来近似估计G(τ_{s₀=s,a₀=a})。其中Qˆπ(s′, a′)是当前的Q函数的近似估计。

结合上面两式，有

因此，更新Qˆπ(s, a)只需要知道当前状态s和动作a、奖励r(s, a, s′)、下一步的状态s′ 和动作a′。这种策略学习方法称为 SARSA 算法[Rummery and Niranjan, 1994]。

1、SARSA算法（State Action Reward State Action，SARSA）[Rummery and Niranjan, 1994]如算法14.3所示，其采样和优化的策略都是π^ϵ，因此是一种同策略算法。

为了提高计算效率，我们不需要对环境中所有的s, a组合进行穷举，并计算值函数。只需要将当前的探索(s, a, r, s′, a′)中s′, a′ 作为下一次估计的起始状态和动作。

时序差分学习是强化学习的主要学习方法，其关键步骤就是在每次迭代中优化 Q 函数来减少现实 r + γQ(s′, a′) 和预期 Q(s, a) 的差距。

2、Q-Learning 算法[Watkins and Dayan, 1992]是一种异策略的时序差分学习算法。在Q学习中，Q函数的估计方法为相当于让Q(s, a)直接去估计最优状态值函数Q^∗(s, a)。

与SARSA 算法的不同，Q 学习算法不通过π^ϵ来选下一步的动作 a′，而是直接选最优的Q函数，因此更新后的Q函数是关于策略π的，而不是策略π^ϵ的。

其实，SARSA算法（State Action Reward State Action）是Q-Learning算法的改进，Q-Learning出现的更早。

基于策略函数的学习方法

强化学习的目标是学习到一个策略π_θ(a|s)来最大化期望回报。一种直接的方法是在策略空间直接搜索来得到最佳策略，称为策略搜索（policy search）。

策略搜索本质是一个优化问题，可以分为基于梯度的优化和无梯度优化。

策略搜索和基于值函数的方法相比，策略搜索可以不需要值函数，直接优化策略。参数化的策略能够处理连续状态和动作，可以直接学出随机性策略。

策略梯度（policy gradient）是一种基于梯度的强化学习方法。假设π_θ(a|s)是一个关于 θ 的连续可微函数，我们可以用梯度上升的方法来优化参数 θ 使得目标函数J (θ)最大。

目标函数J (θ)关于策略参数θ 的导数为

其中 ∂/∂θ log pθ(τ) 为函数 log pθ(τ) 关于 θ 的偏导数。从上式中可以看出，参数θ 优化的方向是使得总回报G(τ)越大的轨迹τ 的概率pθ(τ)也越大。

∂/∂θ log pθ(τ) 可以进一步分解为

可以看出，∂/∂θ log pθ(τ)是和状态转移概率无关，只和策略函数相关。

因此，策略梯度 ∂J(θ)/∂θ 可写为

其中G(τ_t:T)为从时刻t作为起始时刻收到总回报

REINFORCE 算法

策略梯度公式中，期望可以通过采样的方法来近似。

对当前策略π_θ，可以随机游走采集多个轨迹τ⁽¹⁾, τ⁽²⁾, … , τ^(N)，每一条轨迹τ(n) = s⁽ⁿ⁾₀, a⁽ⁿ⁾₀, s⁽ⁿ⁾₁, a⁽ⁿ⁾₁, … ，其梯度定义为

结合随机梯度上升算法，我们可以每次采集一条轨迹，计算每个时刻的梯度并更新参数，称为REINFORCE算法[Williams, 1992]，如算法14.6所示。

带基准线的 REINFORCE 算法

REINFORCE算法的一个主要缺点是不同路径之间的方差很大，导致训练不稳定，这是在高维空间中使用蒙特卡罗方法的的通病。一种减少方差的通用方法是引入一个控制变量（V(s)）。

实际上，减去一个基线虽然不会改变更新值的期望值，但是它会影响更新的方差。通过减去平均回报（基准），梯度算法能够学习的更快。对于MDP问题，基线则依赖于状态。比如对于一些状态来说，他们都具有比较大的动作值函数。那么我们就需要有一个大的基线来区分更大的动作值和相对小的动作值。但是对于其他一些状态，所有状态的值函数都比较小，那么我们就需要一个小的基线值。

所以问题来了，如何定基线的大小？一个自然的选择就是使用估计的状态值函数公式。它只依赖于状态。另外的话，状态值函数其实就是相当于一个均值。因为REINFORCE是基于MC的，自然我们也可以方便的使用MC来学习这个值函数。

Actor-Critic 算法

在REINFORCE算法中，每次需要根据一个策略采集一条完整的轨迹，并计算这条轨迹上的回报。这种采样方式的方差比较大，学习效率也比较低。

状态开始s的总回报可以通过当前动作的即时奖励r(s, a, s′)和下一个状态s′ 的值函数来近似估计。

我们可以借鉴时序差分学习的思想，使用动态规划方法来提高采样的效率，即从状态开始s的总回报可以通过当前动作的即时奖励r(s, a, s′)和下一个状态s′ 的值函数来近似估计。

演员-评论员算法（Actor-Critic Algorithm）是一种结合策略梯度和时序差分学习的强化学习方法。

演员（actor）是指策略函数π_θ(s, a)，即学习一个策略来得到尽量高的回报
评论员（critic）是指值函数V_ϕ(s)，对当前策略的值函数进行估计，即评估actor的好坏。借助于值函数，Actor-Critic算法可以进行单步更新参数，不需要等到回合结束才进行更新

在 Actor-Critic 算法中的策略函数π_θ(s, a)和值函数V_ϕ(s)都是待学习的函数，需要在训练过程中同时学习。

假设从时刻t开始的回报G(τ_t:T)，我们用下面公式近似计算。其中s_t+1 是 t+1 时刻的状态，r_t+1 是即时奖励。

在每步更新中，分别进行策略函数π_θ(s, a)和值函数V_ϕ(s)的学习。

一方面，更新参数ϕ使得值函数V_ϕ(s_t)接近于估计的真实回报Gˆ(τ_t:T)
另一方面，将值函数V_ϕ(s_t)作为基函数来更新参数θ，减少策略梯度的方差。

在每步更新中:

演员根据当前的环境状态s和策略π_θ(a|s)去执行动作a，环境状态变为s′，并得到即时奖励r。
评论员（值函数V_ϕ(s)）根据环境给出的真实奖励和之前标准下的打分(r + γV_ϕ(s′))，来调整自己的打分标准，使得自己的评分更接近环境的真实回报。
演员则跟据评论员的打分，调整自己的策略π_θ，争取下次做得更好。

开始训练时，演员随机表演，评论员随机打分。通过不断的学习，评论员的评分越来越准，演员的动作越来越好。

总结

一般而言：

基于值函数的方法策略更新时可能会导致值函数的改变比较大，对收敛性有一定影响，
基于策略函数的方法在策略更新时更加更平稳些。但因为策略函数的解空间比较大，难以进行充分的采样，导致方差较大，并容易收敛到局部最优解。
Actor-Critic算法通过融合两种方法，取长补短，有着更好的收敛性。

这些不同的强化学习算法的优化步骤都可以分为三步：

（1）执行策略，生成样本
（2）估计回报
（3）更新策略

下表给出了四种典型的强化学习算法（SARSA、Q学习、REINFORCE、Actor-Critic算法）的比较。

A Survey on Reinforcement Learning

定义