机器学习 强化学习

强化学习课程笔记：PPO、Q-Learning、Actor + Critic、Sparse Reward、IRL

Posted by Lucius on June 15, 2021

Introduction

Two Learning Modes

强化学习 (Reinforcement Learning)：

  • 机器与环境交互

  • 机器从环境中获得奖励，从而知道其表现的好坏

示范学习 (Learning by demonstration)：

  • 也被称为模仿学习 (imitation learning) 和学徒式学习 (apprenticeship learning)

  • 一个专家展示如何解决任务，机器从专家的示范中学习

Reinforcement Learning

Basic ideas

三大关键点：Observation (State) -> Action (Change the environment) -> Reward

其中 State 指观察到的环境的状态。

episode：一次从训练开始至结束的过程。

强化学习的核心目标就是让机器学习如何最大化每个 episode 中的累积期望奖励。

Difficulties

  • 奖励的延迟 (Reward delay)

  • 有些行为虽然当时没有拿到奖励，但其对后续拿到的奖励仍然有贡献，如何处理此类行为，是一大难点

  • Agent 的行为影响后续收到的数据

  • 需要让 Agent 不断去探索 (Exploration)

Policy-based

Policy-based 方法，即学出一个 Actor：

Neural network as Actor

其中若 Actor 是深度神经网络，则这个过程称为深度强化学习 (Deep Reinforcement Learning)。

  • 传统做法是存一个 table 来对应 observation-action，神经网络与其对比，泛化能力更强 (generalization)

Goodness of Actor

使用同一个 Actor (网络所有参数相同) 玩大量的游戏，以其每次 episode 的 total reward 的期望值来衡量这个 Actor 的好坏。

Pick the best Actor

使用梯度下降的方式求解使 $\bar{R}_{\theta}$ 最大的 $\theta$：

$$ \nabla \bar{R}_{\theta} \approx\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} R\left(\tau^{n}\right) \nabla \log p\left(a_{t}^{n} \mid s_{t}^{n}, \theta\right) $$

由于梯度代表函数值增加最快的方向，因此当 $R\left(\tau^{n}\right)$ 为正时，模型倾向于调整 $\theta$ 使 $p\left(a_{t}^{n} \mid s_{t}^{n}\right)$ 增加，为负时则使 $p\left(a_{t}^{n} \mid s_{t}^{n}\right)$ 减小。

当 $R\left(\tau^{n}\right)$ 始终为正时，由于所有 action 的概率相加为 1，因此无法使每个 action 的概率增加，并且若出现未采样到的 action，效果也不尽如人意。

基于此，有时会在模型中引入 bias，使 $R\left(\tau^{n}\right)$ 有正有负：

$$ \nabla \bar{R}_{\theta} \approx\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} (R\left(\tau^{n}\right)-b) \nabla \log p\left(a_{t}^{n} \mid s_{t}^{n}, \theta\right) $$
Value-based

引入 Critic，其并不能决定行为，但可以评价 actor 的好坏。

通常来说，有三种类型的 Critic：

  • critic 是一个神经网络，用于评估 actor $\pi$

  • 状态价值函数 (State value function) $V^{\pi}(s)$
    • $V^{\pi}(s)$ 代表使用 actor $\pi$，当出现状态 s 后的累积期望 reward
  • State-action value function $Q^{\pi}(s,a)$
    • 对于 actor $\pi$，当状态和行动分别为 s 和 a 时的累积期望 reward

State value function

衡量 $V^{\pi}(s)$ 有两种方法，分别是：

  • Monte-Carlo based approach

  • Temporal-difference approach

其中 MC 方法，即令 critic 观察 $\pi$ 完成游戏；而 TD 则通过 $V^{\pi}\left(s_{t}\right)-V^{\pi}\left(s_{t+1}\right) = r_{t}$ 来递推 $V^{\pi}(s)$。

State-action value function

根据 $Q^{\pi}(s,a)$，引出 Q-Learning 的概念：

A3C

Asynchronous Advantage Actor-Critic (A3C)

具体来说，Actor + Critic 即是将原先 Policy-based 中的 $R\left(\tau^{n}\right)$ 由 critic 来衡量，如下：

Inverse Reinforcement Learning

在现实生活中，存在大量应用，我们无法得知其 reward function，因此我们需要引入逆强化学习。

具体来说，IRL 的核心原则是 “老师总是最棒的” (The teacher is always the best)，具体流程如下：

  • 初始化 actor

  • 在每一轮迭代中
    • actor 与环境交互，得到具体流程 (trajectories)
    • 定义 reward function，使得 teacher 的 trajectories 始终好于 actor
    • 根据新的 reward function，actor 学习最大化 reward
  • 输出最终的 reward function，并根据该 function 训练 actor

Proximal Policy Optimization (PPO)

Policy Gradient

Policy of Actor

Policy $\pi$ 是一个参数为 $\theta$ 的网络：

  • 输入：机器观察到的环境，用向量或矩阵表示

  • 输出：每个 action 对应输出层中的一个神经元

Actor, Env, Reward

Trajectory: $\tau=\left\{s_{1}, a_{1}, s_{2}, a_{2}, \cdots, s_{T}, a_{T}\right\}$

Probability: $p_{\theta}(\tau)=p\left(s_{1}\right) \prod_{t=1}^{T} p_{\theta}\left(a_{t} \mid s_{t}\right) p\left(s_{t+1} \mid s_{t}, a_{t}\right)$

Reward:

  • $R(\tau)=\sum_{t=1}^{T} r_{t}$

  • $\bar{R}_{\theta}=\sum_{\tau} R(\tau) p_{\theta}(\tau)=E_{\tau \sim p_{\theta}(\tau)}[R(\tau)]$

Policy Gradient:

$$ \begin{aligned} \nabla \bar{R}_{\theta} & =\sum_{\tau} R(\tau) \nabla p_{\theta}(\tau) \\ & =\sum_{\tau} R(\tau) p_{\theta}(\tau) \frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)} \\ &=\sum_{\tau} R(\tau) p_{\theta}(\tau) \nabla \log p_{\theta}(\tau) \\ &=E_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log p_{\theta}(\tau)\right] \\ &\approx \frac{1}{N} \sum_{n=1}^{N} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(\tau^{n}\right) \\ &=\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right) \end{aligned} $$

Implementation

Tip1: 避免 $R\left(\tau^{n}\right)$ 始终为正，令 $b$ 为 $R\left(\tau^{n}\right)$ 平均值，对原模型进行修正

Tip2: 某个 action 只能影响后续 reward 的大小，因此权重应从 $R\left(\tau^{n}\right)$ 修改为 $\sum_{t^{\prime}=t}^{T_{n}} r_{t^{\prime}}^{n}$，即 action 后续 reward 之和。

从这个思路继续想，越靠后的 reward 受当前 action 的影响越小，因此乘上衰减系数的幂次，即将 $\sum_{t^{\prime}=t}^{T_{n}} r_{t^{\prime}}^{n}$ 修改为 $\sum_{t^{\prime}=t}^{T_{n}} \gamma^{t^{\prime}-t} r_{t^{\prime}}^{n}\ (\gamma<1)$。

之后用 $A^{\theta}(s_t,a_t)$ 表示 $\sum_{t^{\prime}=t}^{T_{n}} \gamma^{t^{\prime}-t} r_{t^{\prime}}^{n}-b$，代表面对状态 $s_t$ 时采取 $a_t$ 的相对权重。

From on-policy to off-policy

On-policy v.s. Off-policy

On-policy: The agent learned and the agent interacting with the environment is the same.

Off-policy: The agent learned and the agent interacting with the environment is different.

在之前的 Policy-based approach 中，$\bar{R}_{\theta}$ 梯度如下：

$$ \nabla \bar{R}_{\theta}=E_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log p_{\theta}(\tau)\right] $$

在训练过程中，每当 $\theta$ 更新，我们就需要用 $\pi_{\theta}$ 重新收集数据。而对于 Off-policy，我们希望从 $\pi_{\theta’}$ 中收集数据，保持 $\theta’$ 不变的同时训练 $\theta$，即重复使用 sample data。

Importance Sampling

我们希望用 $\pi_{\theta’}$ 生成数据，来训练 $\theta$，即使用 $q(x)$ 分布下的数据，得到 $p(x)$ 分布下的结果。

公式推导如下：

$$ \begin{aligned} E_{x \sim p}[f(x)]&=\int f(x) p(x) d x\\ &=\int f(x) \frac{p(x)}{q(x)} q(x) d x\\ &=E_{x \sim q}\left[f(x) \mid \frac{p(x)}{q(x)}\right] \end{aligned} $$

虽然期望相同，但方差却不同：

$$ \begin{aligned} E_{x \sim p}[f(x)]&=E_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] \\ \operatorname{Var}_{x \sim p}[f(x)]&=E_{x \sim p}\left[f(x)^{2}\right]-\left(E_{x \sim p}[f(x)]\right)^{2} \\ \operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] &=E_{x \sim q}\left[\left(f(x) \frac{p(x)}{q(x)}\right)^{2}\right]-\left(E_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]\right)^{2} \\ &=E_{x \sim p}\left[f(x)^{2} \frac{p(x)}{q(x)}\right]-\left(E_{x \sim p}[f(x)]\right)^{2} \end{aligned} $$

这也就导致如果数据量不是特别大，则这种估计方式可能会出现很大误差：

Off-policy

根据 Importance Sampling，得到 Off-policy 下的梯度：

$$ \begin{aligned} \nabla \bar{R}_{\theta} &= E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta}}\left[A^{\theta}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right]\\ &= E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{P_{\theta}\left(s_{t}, a_{t}\right)}{P_{\theta^{\prime}}\left(s_{t}, a_{t}\right)} A^{\theta '}(s_t,a_t ) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right] \\ &= E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} \frac{p_{\theta}\left(s_{t}\right)}{p_{\theta^{\prime}}(s_t)} A^{\theta'}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right] \\ &=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)}A^{\theta'}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)\right] \end{aligned} $$

即可以看作是 $J^{\theta^{\prime}}(\theta)$ 的梯度：

$$ J^{\theta^{\prime}}(\theta)=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right] $$

PPO

PPO v.s. TRPO

在 Off-policy 上增加不同的限制，即可得到 PPO、TRPO：

其中 KL 不是参数的距离，而是 action 的距离。另外，PPO 与 TRPO 的实验效果差不多，但 TRPO 的求解难度大很多。

PPO 具体算法如下：

PPO2

先前提过，Importance Sampling 中两个分布不宜相差过大，因此通过将 $\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)}$ 限制在 $[1-\epsilon,1+\epsilon]$ 中，得到 PPO2 算法：

图中横轴表示 $\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)}$ 的数值，纵轴表示 $\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)}$ clip 后的值。

Q-Learning

Q-Learning：给定 $Q^{\pi}(s,a)$，寻找到新 actor $\pi’$ 比 $\pi$ 更好，即 $V^{\pi^{\prime}}(s) \geq V^{\pi}(s)$。基于该想法，我们得到 $\pi’$ 如下：

$$ \pi^{\prime}(s)=\arg \max _{a} Q^{\pi}(s, a) $$

因此 $\pi’$ 只与 Q 有关，没有多余参数，另外也不太适合连续的 action。

接下来，我们证明 $\pi’$ 比 $\pi$ 更好：

注意 $Q^{\pi}(s,\pi’(s))$ 表示遇到状态 s，按照 $\pi’(s)$ 走一步，之后仍然按照 $\pi(s)$ 行动。

Introduction

Target Network

  • 一开始左右两个网络 $Q^{\pi}$ 相同

  • 固定右边的 $Q^{\pi}$，输入 $s_{t+1},\pi(s_{t+1})$，得到 $r_{t}+\mathrm{Q}^{\pi}\left(s_{t+1}, \pi\left(s_{t+1}\right)\right)$

  • 训练 N 遍左边的 $Q^{\pi}$，使得 $Q^{\pi}(s_t,a_t)$ 与 $r_{t}+\mathrm{Q}^{\pi}\left(s_{t+1}, \pi\left(s_{t+1}\right)\right)$ 尽可能相近

  • 将右边的 $Q^{\pi}$ 替换成左边的，回到第一步

Exploration

样本中没有穷尽所有的 action，所以寻找 $a=\arg \max _{a} Q(s, a)$ 时只会遍历已知的 action，但可能存在其他 action 效果更好，因此在训练中需要考虑 Exploration。

Replay Buffer

将 $\pi$ 与环境交互得到的大量 $s_t,a_t,r_t,s_{t+1}$ 存入 Buffer，每次选出一个 batch 用于模型训练：

Typical Q-Learning Algorithm

  • Initialize Q-function $Q$, target Q-function $\hat{Q}=Q$

  • In each episode

    • For each time step t
      • Given state $s_t$, take action $a_t$ based on Q (epsilon greedy)
      • Obtain reward $r_t$, and reach new state $s_{t+1}$
      • Store $(s_t,a_t,r_t,s_{t+1})$ into buffer
      • Sample $(s_i,a_i,r_i,s_{i+1})$ from buffer (usually a batch)

      • Target $y=r_i+\max _{a} \hat{Q}\left(s_{i+1}, a\right)$

      • Update the parameters of $Q$ to make $Q(s_i,a_i)$ close to $y$ (regression)
      • Every C steps reset $\hat{Q}=Q$

Tips of Q-Learning

Double DQN

Q value 通常会被高估：

原因在于下述式子中的 $\max$ 使得 Q value 总是比较大：

$$ Q\left(s_{t}, a_{t}\right) \longleftrightarrow r_{t}+\max _{a} Q\left(s_{t+1}, a\right) $$

因此我们可以使用 Target Network，通过 $Q$ 选择 action，再用 $Q’$ 估计 Q value：

Dueling DQN

Dueling DQN 在改变了最后输出层的结构，使 Q value 等于两个分支的和：

其中 $V(s)$ 为标量，预测 state value；而 $A(s,a)$ 是矢量，预测与状态相关的 action advantage value，并且该矢量通过归一化总和为 0。可以这样理解，state function 用于预测 state 的好坏，而 advantage function 则预测在该 state 下每个 action 的重要程度。

Prioritized Reply

在 Replay Buffer 中，使拥有更大 TD error 的数据被抽中的概率更大：

Multi-step

为了使预测更加鲁棒，泛化性能更强，将 MC 与 TD 两种方法进行合并，用多步间的差值来进行模型优化：

Noisy Net

为了使模型具有一定的探索能力，分别在 Action 与 Parameters 两个维度引入 Noise：

两种方法进行对比：

  • Noise on Action
    • 给定相同的 state，agent 可能会执行不同的 action
    • 整个模型倾向于「随机乱试」，现实中的 policy 不会这样工作
  • Noise on Parameters
    • 给定相同的 state，agent 会执行相同的 action
      • State-dependent Exploration
    • 整个模型在「有系统地试」，Explore in a consistent way
Distributional Q-function

$Q^{\pi}(s, a)$ 是一个随机变量，在先前的方法中，我们主要关注该随机变量的期望值，而在该 tip 中，我们更关注其的分布情况：

通常来说，在 $Q^{\pi}(s, a)$ 期望值差不多时，我们更倾向于选择方差更小的，降低模型风险。

Rainbow

将多种模型方法合并在一起，查看每种方法的具体效果、所有方法叠加的效果以及去掉某种方法时的效果：

Continuous Actions

在 Q-Learning 方法中，我们使用下述公式得到 action：

$$ a=\arg \max _{a} Q(s, a) $$

如果 a 为离散变量，则我们可以通过枚举的方式进行求解；而如果 a 为连续变量，我们则需要使用如下一些方法进行求解：

  • 随机取样

    • 取样 $\left\{a_{1}, a_{2}, \cdots, a_{N}\right\}$，选其中最大的 Q value

  • 梯度下降
    • 将该问题当作优化问题，使用常见的梯度下降作为优化方法
  • 设计一个网络作为优化方法

  • 放弃 Q-Learning
    • 可以使用 Policy-based 或者 Actor + Critic 的方法

Actor + Critic

Advantage Actor-Critic

在 Policy Gradient 中，我们得到如下梯度：

其中由于 Sample 的次数比较有限，因此 $G_t^n$ 的数值不太稳定，即该随机变量的方差较大，因此对其进行如下改进：

即中间的关键项从 $\sum_{t^{\prime}=t}^{T_{n}} \gamma^{t^{\prime}-t} r_{t^{\prime}}^{n}-b$ 变为了 $Q^{\pi_{\theta}}\left(s_{t}^{n}, a_{t}^{n}\right)-V^{\pi_{\theta}}\left(s_{t}^{n}\right)$，这意味着我们需要同时训练 Q 和 V 两个 network，使问题变得更加难以处理。

为了简化这个问题，我们进行如下近似：

$$ Q^{\pi}\left(s_{t}^{n}, a_{t}^{n}\right)=E\left[r_{t}^{n}+V^{\pi}\left(s_{t+1}^{n}\right)\right]\approx r_{t}^{n}+V^{\pi}\left(s_{t+1}^{n}\right) $$

该近似方式在实验中取得了不错的效果，因此关键项变为：

$$ r_{t}^{n}+V^{\pi}\left(s_{t+1}^{n}\right)-V^{\pi}\left(s_{t}^{n}\right) $$

我们只需训练 V 一个 network 即可。

Tips

由于我们需要训练 actor $\pi(s)$ 和 critic $V^{\pi}(s)$，而这两个网络都是以 state 为输入，即网络对 state 的前期处理相同，因此可以共用一部分参数：

另外，出于 exploration 的目的，我们希望各 action 的概率相对均匀，即 entropy 的值更大，因此我们可以将各 action 的 entropy 作为 regularization 加入 expected reward 中，即令网络生成更大的 entropy。

Asynchronous

相比于 Advantage Actor-Critic，A3C (Asynchronous Advantage Actor-Critic) 在其上增加了分布式的方法：

即每一个 worker 分布式训练，得到对应梯度，直接更新最终的网络；更新完后再复制参数，继续训练。这里可能会出现，「复制参数的网络」和「之后更新的网络」不是同一个网络，但对总的结果影响不大。

Pathwise Derivative Policy Gradient

该方法依然是 actor + critic 的方法，但可以用于求解连续 action 的问题。

原先的 actor-critic 中的 critic 主要是判断 actor 的好坏，而在 pathwise derivative policy gradient 中，critic 会给出下一步的 action。

其具体流程如下所示：

Sparse Reward

现实生活中，大量任务的 reward 都是 sparse 的，即很多行为当下无法得到直接的 reward，要等到很多步后，才能得到 reward。

对于此类问题，我们通常需要引导着 machine 去学习。具体来说，有如下三种方法：

  • Reward Shaping

  • Curriculum Learning

  • Hierarchical RL

Reward Shaping

通过对每一步的 reward 重新赋值，让 reward 不再稀疏，或者说通过对 reward 的重新取值，引导 machine 向着正确的方向训练。

为了实现这一目的，我们引入 Curiosity 机制，即增加新的 reward：

对于 $(a_t,s_t,s_{t+1})$，我们根据 $s_{t+1}$ 的难以预测程度来评估其 ICM 的 reward。然而存在某些 states 虽然难以预测，但并不重要，因此我们需要对 states 进行特征提取，选出关键特征：

Curriculum Learning

规划 machine 的学习任务，让任务从简单到难，使 machine 循序渐进地学习。

除了主动的规划学习任务，我们也可以采用反向的方法 (Reverse Curriculum Generation)：

  • 随机生成多个任务

  • 删除 reward 特别大和特别小的任务，即难度过大与过小的任务

  • 对于其他任务，按难度排序，由简至易，依次学习

Hierarchical RL

层次化地训练 agent，例如 校长 -> 教授 -> 研究生，从上至下依次安排学习任务，需要满足以下条件：

  • 如果低层次的 agent 没有完成目标，则高层次的 agent 会受到惩罚

  • 如果某个 agent 完成了错误的目标，则认为最初的目标是错误的

Imitation Learning

在现实生活中，可能存在以下的情况：

  • machine 能与环境交互，但无法显式地得到 reward

  • 某些任务难以定义 reward

  • Hand-crafted rewards 可能会出现难以控制的行为

为了解决上述情况，引入了 Imitation Learning，即 learning by demonstration，apprenticeship learning。

Behavior Cloning

行为复制，即监督学习。

该方法存在以下几个问题：

  • expert 的数据有限 (可用增强数据缓解)

  • agent 不仅会学习相关 action，也会学习无关 action

  • 由于容量有限，agent 可能会挑选错误的行为来学习

基于上述问题，machine 对于某一个 state 学出的 action 可能会与 expert 有一定区别，误差不断累积，会导致后续产生的 state 与 action 差别非常大。

Inverse Reinforcement Learning

由于直接复制 expert 行为的方法存在问题，我们采用别的方式来生成 reward function：

上述方式通过不断改变 reward function，使得 expert 所产生的交互流程拥有更大的 reward。反复迭代后，得到最终的 reward function，再重新训练 actor。

最后是 IRL 与 GAN 的对比：

CATALOG
    FEATURED TAGS
    数学 机器学习 计算机图形学 生成式 AI 深度学习 凸优化 数据挖掘 模式识别 近邻搜索 Matplotlib 线性代数 聚类算法 哈希算法 强化学习 推荐系统 概率论 模型查搜 泛函分析 演化算法 理论计算机科学