CS285 Part 2 - RL 概述

Posted on Edited on In

本节将勾勒强化学习算法的轮廓，

记号与术语

Markov Chain $\mathcal{M} = \{\mathcal{S}, \mathcal{T}\}$，其中 $\mathcal{S}$ 是状态空间，$\mathcal{T}$ 是转移矩阵。

但是在 MDP 中，转移还和操作有关。我们用 $\mathcal{M} = \{\mathcal{S}, \mathcal{A}, \mathcal{T}, r\}$ 来刻画一个 MDP，现在 $\mathcal{T}$ 变成了一个三维张量。定义 $\mu_{t, j} = p(s_t = j), \xi_{t, k} = p(a_t = k), \mathcal{T}_i^{jk} = p(s_{t + 1} = i | s_t = j, a_t = k)$，那么

$$
\mu_{t + 1, i} = \mathcal{T}_i^{jk}\mu_{tj}\xi_{tk}
$$

而上面 $r$ 是奖励函数：$r : \mathcal{S}\times\mathcal{A}\rightarrow \mathbb{R}$。

注意即便增加了决策，将 $\mathbf{a}$ 和 $\mathbf{s}$ tuple 起来，整个过程还是可以用一个 Markov Chain 来刻画。转移为

$$
p((\mathbf{s}_{t + 1}, \mathbf{a}_{t + 1}) | (\mathbf{s}_t, \mathbf{a}_t)) = p(\mathbf{s}_{t + 1} | \mathbf{s}_t, \mathbf{a}_t)\pi_\theta(\mathbf{a}_{t + 1} | \mathbf{s}_{t + 1}) \label{trans}
$$

强化学习将需要学习一个策略的分布 $\pi_\theta(\mathbf{a} | \mathbf{s})$，其中 $\theta$ 是神经网络的参数。那么在整个 MDP 过程中，产生一个状态序列的概率是

$$
p_{\theta}(\mathbf{s}_1, \mathbf{a}_1, …, \mathbf{s}_T, \mathbf{a}_T) = p(\mathbf{s}_1)\prod_{t = 1}^T \pi_{\theta}(\mathbf{a}_t | \mathbf{s}_t)p(\mathbf{s}_{t + 1} | \mathbf{s}_t, \mathbf{a}_t)
$$

RL 的目的是最优化整个过程中的奖励总和，即求

$$
\theta^* = \arg\max_\theta \mathbb{E}_{\tau\sim p_{\theta}(\tau)}\left[\sum_{t}r(\mathbf{s}_t, \mathbf{a}_t)\right]
$$

一种 MDP 是有限时间步（Finite horizon）的。根据 $\ref{trans}$ 提供的结论，将期望用线性性展开，只需要优化

$$
\arg\max_{\theta} = \sum_{t = 1}^T \mathbb{E}_{(\mathbf{s}_t, \mathbf{a}_t)\sim p_{\theta}(\mathbf{s}_t, \mathbf{a}_t)}[r(\mathbf{s}_t, \mathbf{a}_t)] \label{finitecase}
$$

在无限时间步（Infinite horizon）的情况下，我们熟知不可约的 Markov chain 前 $T$ 项的均值都是收敛到稳态分布的，此时你就要对着下面的式子优化，其中 $p_{\theta}$ 是一个稳态。

$$
\mathbb{E}_{(\mathbf{s}, \mathbf{a})\sim p_\theta(\mathbf{s}, \mathbf{a})}[r(\mathbf{s}, \mathbf{a})]\label{infinitecase}
$$

$\ref{finitecase}, \ref{infinitecase}$ 分别是有限时间步 MDP 和无限时间步 MDP 需要优化的东西。在 RL 中我们需要考虑的东西是期望，一方面的原因是 $r(\mathbf{x})$ 可能不是可导的，但是 $\mathbf{E}_{\pi_\theta}[r(\mathbf{x})]$ 关于 $\theta$ 是可导的。不妨考虑如下直观的例子：

例子. 现在智能体面临一个向左转的桥，其以 $\mathrm{Bern}(p)$ 决定是否左转。如果成果左转将会获得 $1$ 的 Reward，否则获得 $-1$ 的 Reward。

强化学习算法

强化学习算法的框架：

  1. 采样（i.e. 模拟当前的策略，生成一些轨迹）
  2. 拟合一些模型，其功能可能包括：
    • 估算状态转移的概率；
    • 估计当前局面的期望 Reward。
  3. 优化：$\theta \leftarrow \theta + \alpha\nabla_\theta J(\theta)$

主流的强化学习算法几乎都限制在上述框架中，参见算法分类一节。

选择算法时需要考虑如下因素：

  1. 你是在现实世界中运行策略还是在某个模拟的环境。
  2. 拟合模型可能非常难。

价值函数

可以将代价 $\ref{finitecase}$ 写成某种递归的形式：

$$
\mathbb{E}_{\mathbf{s}_1\sim p(\mathbf{s}_1)}[
\mathbb{E}_{\mathbf{a}_1\sim \pi(\mathbf{a}_1 | \mathbf{s}_1)}[{\color{blue}{r(\mathbf{s}_1, \mathbf{a}_1) + \mathbb{E}_{\mathbf{s}_2\sim p(\mathbf{s}_2 | \mathbf{s_1}, \mathbf{a}_1)}[\mathbb{E}_{\mathbf{a}_2\sim\pi(\mathbf{a}_2 | \mathbf{s}_2)}[{\color{red}{r(\mathbf{s}_2, \mathbf{a}_2) + \cdots}}]| \mathbf{s}_1, \mathbf{a}_1]}}| \mathbf{s}_1]]
$$

因为是 Markov Chain，而中间的东西都是 conditional on 当前状态的，所以我们定义

$$
Q(\mathbf{s}_1, \mathbf{a}_t) = r(\mathbf{s}_1, \mathbf{a}_1) + \mathbb{E}_{\mathbf{s}_2\sim p(\mathbf{s}_2 | \mathbf{s_1}, \mathbf{a}_1)}[\mathbb{E}_{\mathbf{a}_2\sim\pi(\mathbf{a}_2 | \mathbf{s}_2)}[r(\mathbf{s}_2, \mathbf{a}_2) + \cdots]| \mathbf{s}_1, \mathbf{a}_1]
$$

现在你需要优化的东西无非就是

$$
\mathbb{E}_{\mathbf{s}_1\sim p(\mathbf{s}_1)}[\mathbb{E}_{\mathbf{a}_1\sim\pi(\mathbf{a}_1 | \mathbf{s}_1)}[Q(\mathbf{s}_1, \mathbf{a}_1) | \mathbf{s}_1]]
$$

更一般地我们定义

定义（Q-function）.

$$
Q^\pi(\mathbf{s}_t, \mathbf{a}_t) = \sum_{t’ = t}^T\mathbb{E}[r(\mathbf{s}_{t’}, \mathbf{a}_{t’}) | \mathbf{s}_t, \mathbf{a}_t]
$$

定义（Value function）.

$$
V^{\pi}(\mathbf{s}_t) = \sum_{t’ = t}^T\mathbb{E}[r(\mathbf{s}_{t’}, \mathbf{a}_{t’}) | \mathbf{s}_t]
$$

简而言之，$Q^{\pi}$ 刻画了采取当前操作之后期望得到的奖励，而 $V^\pi$ 刻画了当前局面下期望得到的奖励。

定义了这两个函数之后就有两个自然的想法来优化 $\pi$：

  1. 直接让 $\pi(\mathbf{a}|\mathbf{s}) = 1$，这里 $\mathbf{a} = \arg\max_\mathbf{a}Q^\pi(\mathbf{s}, \mathbf{a})$。这样将会得到我们熟悉的策略迭代算法。
  2. 增加 $Q^\pi(\mathbf{s}, \mathbf{a}) > V^\pi(\mathbf{s})$（优于平均的决策）的概率。直觉上，这是直接对策略网络进行梯度下降的算法的运行效果。

算法分类

主流的 RL 算法大概有如下几类（上面三种都不需要知道转移张量 $\mathcal{T}$，称作 Model-Free RL）：

  • Policy Gradient. 直接用梯度下降优化目标函数。
  • Value-Based. 拟合 $V^\pi$ 和 $Q^\pi$，然后选择最优的决策（策略迭代、值迭代算法）。
  • Actor-Critic. 拟合 $V^\pi$ 和 $Q^\pi$，并用梯度下降优化目标函数。
  • Model-Based RL. 拟合转移概率，然后在此基础上有一大套 MCTS 之类的算法，也可以对策略做梯度下降。

各算法的细节将在后续笔记中补全。