CS229 课程笔记之十五：强化学习与控制

口仆

发布于 2020-08-14 15:26:30

5800

本章将开始介绍「强化学习」与适应性控制。在监督学习中，对于训练集我们均有明确的标签，算法只需要模仿训练集中的标签来给出预测即可。但对于某些情况，例如序列性的决策过程和控制问题，我们无法构建含有标签的训练集。即无法提供一个明确的监督学习算法来进行模仿。

在强化学习的框架下，我们只会给出一个「奖励函数」（reward function），该函数会告知学习程序（leaning agent）什么时候的动作是好的，什么时候的是不好的。算法的工作是找出随着时间推移如何选择动作来得到最大的奖励。

强化学习已经成功用于多种场景，包括：无人直升机的自主飞行、机器人行走、手机网络路由、市场策略选择、工厂控制、高效率的网页索引等。我们将从「马尔可夫决策过程」开始介绍强化学习，其给出了强化学习问题的常见形式。

1 马尔可夫决策过程

一个马尔可夫决策过程是一个五元组

\left(S, A,\left\{P_{s a}\right\}, \gamma, R\right)

，其中：

是一个「状态」集。例如在无人直升机的自主飞行中，

可以是直升机所有可能的位置与方向；

是一个「动作」集。例如你可以推动直升机控制摇杆的所有方向；

P_{sa}

是状态转移概率，对于每个状态

s \in S

以及动作

a \in A

，

P_{sa}

为状态空间上的分布。简单来说，

P_{sa}

给出当我们在状态

采取了行动

时，下一个状态的分布；

\gamma \in[0,1)

被称为「折扣因子」（discount factor）；

R : S \times A \mapsto \mathbb{R}

为「奖励函数」。有时候奖励函数被写作仅与状态

2 值迭代和策略迭代

下面介绍求解有限状态 MDP 的两种高效算法：值迭代和策略迭代。我们目前只考虑「有限」状态和动作空间的 MDP。

2.1 值迭代

值迭代算法的流程为：

对于每个状态

，初始化

V(s) :=0

重复下述过程直至收敛：对于每个状态

，更新

V(s) :=R(s)+\max _{a \in A} \gamma \sum_{s^{\prime}} P_{s a}\left(s^{\prime}\right) V\left(s^{\prime}\right)

该算法可以理解为不断更新

(2)

式中的值函数。算法的内循环有两种更新方法：

「同步」更新：计算所有状态的

V(s)

，然后全部替换旧的值

「异步」更新：按某种顺序遍历状态，一次更新一个值

不论是异步还是同步更新，值迭代算法最终都会使

收敛至

V^*

。得到了

V^*

，我们就可以利用

(3)

式来找出最优策略。

2.2 策略迭代

策略迭代的流程为：

随机初始化

\pi

重复下述过程直至收敛：
- 令
V :=V^{\pi}
- 对于每个状态
s
，更新
\pi(s) :=\arg \max _{a \in A} \sum_{s^{\prime}} P_{s a}\left(s^{\prime}\right) V\left(s^{\prime}\right)

可以看到，该算法在内循环中计算当前策略的值函数，然后使用当前值函数更新策略。该步骤中找出的策略也被称为关于

的「贪婪策略」。在有限次数的迭代后，

将收敛至

V^*

，

\pi

将收敛至

\pi^*

。注意：在内循环第一步中值函数的求解方式如之前所述，为含有

|S|

个变量的线性方程组。

值迭代和策略迭代是求解 MDP 的标准算法，目前没有好坏之分。一般对于较小的 MDP，策略迭代往往更快，迭代次数较少；而对于较大状态空间的 MDP，求解

V^{\pi}

相对较难，通常使用值迭代。在实际应用中，值迭代比策略迭代要使用得更加频繁（因为实际问题中状态通常较多）。

3 马尔可夫过程的模型学习

在实际问题中，我们无法得知状态转移概率和奖励函数，因此需要基于「数据」来进行估计。例如我们进行了一系列实验，得到如下所示的一系列马尔可夫过程：

\begin{array}{l}{s_{0}^{(1)} \stackrel{a_{0}^{(1)}}{\longrightarrow} s_{1}^{(1)} \stackrel{a_{1}^{(1)}}{\longrightarrow} s_{2}^{(1)} \stackrel{a_{2}^{(1)}}{\longrightarrow} s_{3}^{(1)} \stackrel{a_{3}^{(1)}}{\longrightarrow} \ldots} \\ {s_{0}^{(2)} \stackrel{a_{0}^{(2)}}{\longrightarrow} s_{1}^{(2)} \stackrel{a_{1}^{(2)}}{\longrightarrow} s_{2}^{(2)} \stackrel{a_{2}^{(2)}}{\longrightarrow} s_{3}^{(2)} \stackrel{a_{3}^{(2)}}{\longrightarrow} \ldots} \\ {\ldots}\end{array}

其中

s_{i}^{(j)}

表示实验

的时间点

的状态，其对应的动作为

a_{i}^{(j)}

。在实际中，每个实验可以运行至马尔可夫过程终止，或某个较大但有限的时间点。

基于上述"经验"，我们可以利用极大似然估计来求出状态转移概率：

P_{s a}\left(s^{\prime}\right)=\frac{\# \text { times took we action } a \text { in state } s \text { and got to } s^{\prime}}{\# \text { times we took action a in state } s} \tag{4}

如果比例为

0/0

，则使用

1/|S|

替代。当我们进行更多的实验，得到更多的"经验"时，我们可以用一种较高效的方法来更新状态转移概率：具体来说，我们可以记录上式的分子与分母值，新的数据直接在旧数据的基础上累加即可。类似地，如果奖励函数

未知，我们可以用状态

的「期望即时奖励估计」

R(s)

来作为其平均奖励。

在学习出 MDP 的模型后，我们可以使用值迭代或策略迭代来求解 MDP，找出最佳策略。例如，将模型学习和值迭代结合在一起，我们可以得出下面的算法，用于未知概率转移矩阵的 MDP 的学习：

随机初始化

\pi

重复下述过程：
- 在 MDP 中执行
\pi
若干次来得到样本（下一步的状态通过观察得到）
- 使用 MDP 中的累加经验来估计
P_{sa}
(以及
R
，如果需要)
- 基于估计的状态转移概率和奖励函数应用值迭代算法，得到一个新的
V
的估计
- 更新
\pi
为关于
V
的贪婪策略

对于该算法，可以通过下述手段来使其运行更快：在第二步的值迭代的内循环中，每次不初始化

为 0，而初始化为上一次外循环中得到的结果。

4 连续状态马尔可夫决策过程

到目前为止，我们都在讨论有限数量状态下的 MDP，现在我们将开始讨论「无限状态」下的 MDP (

S=\mathbb{R}^{n}

)。

4.1 离散化

求解连续状态 MDP 的最简单的方法就是「离散化状态空间」，然后使用之前提到的值迭代或状态迭代算法。例如，对于一个二维状态

(s_1,s_2)

，我们可以用一个网格来进行离散化：

每一个网格细胞代表一个独立的离散状态

\bar{s}

，然后我们就可以用一个离散状态的 MDP

\left(\bar{S}, A,\left\{P_{\overline{s} a}\right\}, \gamma, R\right)

来估计连续状态下的 MDP，使用值迭代或策略迭代来求解

V^{\star}(\bar{s})

和

\pi^{\star}(\bar{s})

。当实际的系统处于某个连续值的状态

s \in S

时，我们先计算其对应的离散状态

\bar{s}

，然后执行最优策略

\pi^{\star}(\bar{s})

。

离散化的方法对很多问题都有较好的效果，但其存在两点不足：

第一点是对

V^{\star}

和

\pi^{\star}

的表达过于 naive，即假设其在离散的区段上取值不变。例如下面的线性回归问题，如果使用离散化来表达，则得到如下结果：

可以看出离散化对光滑数据的拟合并不好，我们可能需要更加精确的离散化（非常小的网格）来获得精确的估计。

第二点是「维度诅咒」（curse of dimensionality）。假设

S=\mathbb{R}^{n}

，且我们将每个维度的状态离散化为

个值，则总的离散状态数为

k^n

。其随着维数的增加呈指数上升趋势，难以推广至大型问题。从经验上来说，离散化对 1 维和 2 维问题的效果最好，如果注意离散化的方法，则其对 4 维以下问题也效果不错，如果你特别牛批，甚至能应用到 6 维问题，再高的话基本上就不行了。

4.2 值函数近似

下面介绍另一种直接在连续状态 MDP 中寻找最佳策略的方法。我们将直接估计

V^{\star}

，而不去进行离散化。该方法称为「值函数近似」，已经成功应用于许多强化学习问题。

4.2.1 使用一个模型或模拟器

为了设计一个值函数估计算法，需要先假设我们有一个「模型」（或「模拟器」）。对于 MDP，通俗来说，模拟器就是一个黑盒子，接收输入状态

s_t

（连续值）和动作

a_t

，根据状态转移概率

P_{s_ta_t}

输出下一个状态

s_{t+1}

，：

我们有多种方式来得到上述模型。第一种方法是使用物理模拟。例如使用软件包来对某些问题进行物理描述，进行模拟；第二种方法是从已有的数据中进行学习。例如，假设我们在一个 MDP 中执行

次「试验」，每次试验包含 T 个时间步，动作的选择可以随机或是执行某种特定的策略，或是其他方式。然后，我们会得到如下的

个观察序列：

\begin{array}{c}{s_{0}^{(1)} \stackrel{a_{0}^{(1)}}{\longrightarrow} s_{1}^{(1)} \stackrel{a_{1}^{(1)}}{\longrightarrow} s_{2}^{(1)} \stackrel{a_{2}^{(1)}}{\longrightarrow} \cdots \stackrel{a_{T-1}^{(1)}}{\longrightarrow} s_{T}^{(1)}} \\ {s_{0}^{(2)} \stackrel{a_{0}^{(2)}}{\longrightarrow} s_{1}^{(2)} \stackrel{a_{1}^{(2)}}{\longrightarrow} s_{2}^{(2)} \stackrel{a_{2}^{(2)}}{\longrightarrow} \cdots \stackrel{a_{T-1}^{(2)}}{\longrightarrow} s_{T}^{(2)}} \\ {\cdots} \\ {s_{0}^{(m)} \stackrel{a_{0}^{(m)}}{\longrightarrow} s_{1}^{(m)} \stackrel{a_{1}^{(m)}}{\longrightarrow} s_{2}^{(m)} \stackrel{a_{2}^{(m)}}{\longrightarrow} \cdots \stackrel{a_{T-1}^{(m)}}{\longrightarrow} s_{T}^{(m)}}\end{array}

我们会使用一个学习算法来将

s_{t+1}

表示为

s_t

和

a_t

的函数。一种可能的线性模型如下：

s_{t+1}=A s_{t}+B a_{t} \tag{5}

我们可以使用试验中收集到的数据来估计参数：

\arg \min _{A, B} \sum_{i=1}^{m} \sum_{t=0}^{T-1}\left\|s_{t+1}^{(i)}-\left(A s_{t}^{(i)}+B a_{t}^{(i)}\right)\right\|^{2}

学习到了

和

后，一种选择是建立一个「决定性」模型，即给定输入

s_t

和

a_t

后，输出

s_{t+1}

，例如式

(5)

；另一种选择是建立一个「随机」模型，即

s_{t+1}

是输入的随机函数：

s_{t+1}=A s_{t}+B a_{t}+\epsilon_{t}

其中

\epsilon_{t}

是噪声项，分布为

\epsilon_{t} \sim \mathcal{N}(0, \Sigma)

，

\Sigma

也可以从数据中学习。

需要注意，上面我们所列举的都是「线性」模型，实际上非线性模型（例如定义

s_{t+1}=A \phi_{s}\left(s_{t}\right)+B \phi_{a}\left(a_{t}\right)

）或非线性学习算法（例如局部加权线性回归）都可以用于构建模拟器。

4.2.2 拟合值迭代

下面介绍用于估计连续状态 MDP 值函数的「拟合值迭代」算法。这里假设状态空间连续，但动作空间较小且离散（一般来说，动作集的离散化相对容易很多）。

在值迭代中，我们会进行如下更新：

\begin{align*} V(s) & :=R(s)+\gamma \max _{a} \int_{s^{\prime}} P_{s a}\left(s^{\prime}\right) V\left(s^{\prime}\right) d s^{\prime} \tag{6}\\ &=R(s)+\gamma \max _{a} \mathrm{E}_{s^{\prime} \sim P a}\left[V\left(s^{\prime}\right)\right] \tag{7}\end{align*}

注意这里对于连续值需使用积分。拟合值迭代的主要思想就是：基于有限的状态样本

s^{(1)}, \ldots, s^{(m)}

对上述过程进行估计。

具体来说，我们会使用一个监督学习算法（线性回归），将值函数用状态的线性或非线性函数估计：

V(s)=\theta^{T} \phi(s)

其中

\phi

是状态的某种适当的特征映射。

对于

个有限状态样本中的每一个状态

，拟合值迭代会先计算一个量

y^{(i)}

，作为对

R(s)+\gamma \max _{a} \mathrm{E}_{s^{\prime} \sim P a}\left[V\left(s^{\prime}\right)\right]

的估计，然后使用监督学习算法尝试去让

V(s)

接近

R(s)+\gamma \max _{a} \mathrm{E}_{s^{\prime} \sim P a}\left[V\left(s^{\prime}\right)\right]

（即接近

y^{(i)}

），从而学习出参数

\theta

。

具体来说，算法的过程如下：

随机采样

个状态

s^{(1)}, s^{(2)}, \ldots s^{(m)} \in S

初始化

\theta := 0

重复下述过程：

对于

i=1, \ldots, m

在原始的值迭代（离散值）中，我们需要更新

V\left(s^{(i)}\right) :=y^{(i)}

。在本算法中，我们希望

V\left(s^{(i)}\right) \approx y^{(i)}

，使用监督学习算法：

\operatorname{Set} \theta :=\arg \min _{\theta} \frac{1}{2} \sum_{i=1}^{m}\left(\theta^{T} \phi\left(s^{(i)}\right)-y^{(i)}\right)^{2}

上述算法使用了线性回归，实际上其他的回归算法也可以使用，如加权线性回归。

与离散状态集的值迭代不同，拟合值迭代并不一定总是会收敛。不过在实际应用中，其通常会收敛（或近似收敛）。需要注意的是，如果我们使用「决定性」模型（模拟器），那么算法中

k = 1

，因为下一个状态只有一个确定的值；否则我们需要取

个样本并求均值（即随机模型）。

最终，拟合值迭代输出

，其为对

V^{\star}

的估计。由于状态集连续，所以我们无法直接给出针对所有状态的完整最优策略，而是根据特定的状态选择特定的动作。当系统处于状态

时，可以通过下面的公式来选择动作：

\arg \max _{a} \mathrm{E}_{s^{\prime} \sim P_{s a}}\left[V\left(s^{\prime}\right)\right]

上式计算的过程与算法的内循环类似，对于每一个动作，我们采样

s_{1}^{\prime}, \ldots, s_{k}^{\prime} \sim P_{s a}

，类似地，如果使用决定性模型，则

k=1

。

在实际应用中，还有其他方法来估计上述值，例如：如果模拟器的形式为

s_{t+1} = f\left(s_{t}, a_{t}\right)+\epsilon_{t}

，其中

是某个决定性函数（如

f\left(s_{t}, a_{t}\right)=A s_{t}+B a_{t}

），

\epsilon

是 0 均值高斯噪声，则可以通过下述公式选择动作：

\arg \max _{a} V(f(s, a))

可以理解为令

\epsilon_t = 0

（忽略模拟器中的噪声）及

k=1

。我们也可以通过下述公式推导：

\begin{aligned} \mathrm{E}_{s^{\prime}}\left[V\left(s^{\prime}\right)\right] & \approx V\left(\mathrm{E}_{s^{\prime}}\left[s^{\prime}\right]\right) \\ &=V(f(s, a)) \end{aligned}

其中期望是针对

s^{\prime} \sim P_{s a}

的。第一步可以参考 Jensen 不等式（只要噪声项很小，则估计一般合理）。对于无法使用上述估计方法的问题，则可能需要采样

k|A|

个样本，这通常计算量较大。

5 思维导图

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

强化学习

本文分享自口仆微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

强化学习

登录后参与评论

0 条评论

热度