前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >CS229 课程笔记之十五：强化学习与控制

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

作者头像
口仆
发布于 2020-08-14 15:26:30
5430
发布于 2020-08-14 15:26:30
举报
文章被收录于专栏：用户2133719的专栏

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

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

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

1 马尔可夫决策过程

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

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

，其中：

S

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

S

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

A

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

P_{sa}

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

s \in S

以及动作

a \in A

，

P_{sa}

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

P_{sa}

给出当我们在状态

s

采取了行动

a

时，下一个状态的分布；

\gamma \in[0,1)

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

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

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

S

相关，即

R : S \mapsto \mathbb{R}

。

马尔可夫决策过程（MDP）的执行如下：我们从某个状态

s_0

开始，选择某个动作

a_{0} \in A

来执行 MDP；作为选择的结果，MDP 的状态将随机转移到某个后继状态

s_{1} \sim P_{s_{0} a_{0}}

；然后，我们需要选择另一个动作

a_1

，作为结果，状态会转移至

s_{2} \sim P_{s_{1} a_{1}}

；接下来再选择一个动作

a_2

，以此类推。

该过程可以用下图表示：

s_{0} \stackrel{a_{0}}{\longrightarrow} s_{1} \stackrel{a_{1}}{\longrightarrow} s_{2} \stackrel{a_{2}}{\longrightarrow} s_{3} \stackrel{a_{3}}{\longrightarrow} \ldots

遍历序列中的所有状态和动作，总的收益为：

R\left(s_{0}, a_{0}\right)+\gamma R\left(s_{1}, a_{1}\right)+\gamma^{2} R\left(s_{2}, a_{2}\right)+\cdots

当将奖励函数仅与状态相关时，收益变为：

R\left(s_{0}\right)+\gamma R\left(s_{1}\right)+\gamma^{2} R\left(s_{2}\right)+\cdots

本章将主要使用简单的状态奖励函数

R(s)

，推广至

R(s, a)

并不困难。

在强化学习中，我们的目标就是找到一组动作，来最大化总收益的期望：

\mathrm{E}\left[R\left(s_{0}\right)+\gamma R\left(s_{1}\right)+\gamma^{2} R\left(s_{2}\right)+\cdots\right]

注意在时间步

t

的奖励通过参数

\gamma^t

进行了缩减。因此，为了使得期望较大，我们希望尽可能早地积累正奖励，尽可能推迟负奖励。

「策略」（policy）指的是将状态映射为动作的任意函数

\pi : S \mapsto A

。任意时刻，当我们处在状态

s

，我们采取了行动

a=\pi(s)

，则我们执行了策略

\pi

。我们定义一个策略

\pi

的「值函数」为：

V^{\pi}(s)=\mathrm{E}\left[R\left(s_{0}\right)+\gamma R\left(s_{1}\right)+\gamma^{2} R\left(s_{2}\right)+\cdots | s_{0}=s, \pi\right]
V^{\pi}(s)

即为从状态

s

开始，根据策略

\pi

选择动作所积累的折扣奖励函数的期望。注意

\pi

并非随机变量，上述表示只是一种习惯。

给定一个策略

\pi

，其值函数满足「贝尔曼等式」：

V^{\pi}(s)=R(s)+\gamma \sum_{s^{\prime} \in S} P_{s \pi(s)}\left(s^{\prime}\right) V^{\pi}\left(s^{\prime}\right)

这表示期望和由两部分组成：

  • 即时奖励
R(s)
  • 未来的折扣奖励的期望和（第一步之后），也可以写作
\mathrm{E}_{s^{\prime} \sim P_{s \pi(s)}}\left[V^{\pi}\left(s^{\prime}\right)\right]

贝尔曼等式可以用于求解

V^{\pi}

。在一个有限状态的 MDP 中，我们可以对于每个状态

s

写出其

V^{\pi}(s)

的等式，这可以给出一个含有

|S|

个变量的

|S|

个线性方程，用于进行求解，变量即每个状态的未知

V^{\pi}(s)

。

我们定义「最优值函数」为：

V^{*}(s)=\max _{\pi} V^{\pi}(s) \tag{1}

其表示在所有策略中，可以得到的最大期望和。该函数同样满足贝尔曼等式：

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

第一部分与之前一样，为即时奖励；第二部分为所有动作中最大的未来期望和。

我们可以定义策略

\pi^{*} : S \mapsto A

为：

\pi^{*}(s)=\arg \max _{a \in A} \sum_{s^{\prime} \in S} P_{s a}\left(s^{\prime}\right) V^{*}\left(s^{\prime}\right) \tag{3}
\pi^{*}(s)

给出了动作

a

来使得

(2)

式最大化。

根据上述定义，我们可以推导出如下事实：对于每一个状态

s

和每一种策略

\pi

，都有：

V^{*}(s)=V^{\pi^{*}}(s) \geq V^{\pi}(s)

这个公式表明

(3)

式中定义的策略即为最优策略。注意

\pi^{*}

有一个有趣的特性：其为所有状态

s

的最优策略，因为其定义为状态集到动作集的映射。这意味着无论 MDP 的初始状态是什么，我们都可以使用同样的最优策略

\pi^{*}

。

2 值迭代和策略迭代

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

2.1 值迭代

值迭代算法的流程为：

  1. 对于每个状态
s

，初始化

V(s) :=0
  1. 重复下述过程直至收敛：对于每个状态
s

，更新

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^*

。得到了

V^*

，我们就可以利用

(3)

式来找出最优策略。

2.2 策略迭代

策略迭代的流程为：

  1. 随机初始化
\pi
  1. 重复下述过程直至收敛：
    • 令
    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

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

V

将收敛至

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)}

表示实验

j

的时间点

i

的状态，其对应的动作为

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

的「期望即时奖励估计」

R(s)

来作为其平均奖励。

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

  1. 随机初始化
\pi
  1. 重复下述过程：
    • 在 MDP 中执行
    \pi

    若干次来得到样本（下一步的状态通过观察得到）

    • 使用 MDP 中的累加经验来估计
    P_{sa}

    (以及

    R

    ，如果需要)

    • 基于估计的状态转移概率和奖励函数应用值迭代算法，得到一个新的
    V

    的估计

    • 更新
    \pi

    为关于

    V

    的贪婪策略

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

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

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

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 中执行

m

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

m

个观察序列：

\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}

学习到了

A

和

B

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

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

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

对于

m

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

s

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

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

。

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

  1. 随机采样
m

个状态

s^{(1)}, s^{(2)}, \ldots s^{(m)} \in S
  1. 初始化
\theta := 0
  1. 重复下述过程：
  • 对于
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

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

k

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

最终，拟合值迭代输出

V

，其为对

V^{\star}

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

s

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

\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

是某个决定性函数（如

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 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 1 马尔可夫决策过程
  • 2 值迭代和策略迭代
    • 2.1 值迭代
      • 2.2 策略迭代
      • 3 马尔可夫过程的模型学习
      • 4 连续状态马尔可夫决策过程
        • 4.1 离散化
          • 4.2 值函数近似
            • 4.2.1 使用一个模型或模拟器
            • 4.2.2 拟合值迭代
        • 5 思维导图
        领券

        腾讯云开发者

        扫码关注腾讯云开发者

        扫码关注腾讯云开发者

        领取腾讯云代金券

        热门产品

        热门推荐

        更多推荐

        Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

        深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

        腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

        Copyright © 2013 - 2024 Tencent Cloud.

        All Rights Reserved. 腾讯云 版权所有

        登录 后参与评论