10-07 12:18 阅读 111

关注

机器学习基础（第二版）翻译 第17章强化学习

引言

本章介绍了强化学习，这是机器学习的一个丰富领域，与控制理论、优化和认知科学有关。强化学习是指在学习者积极与环境互动以实现特定目标的情况下进行规划和学习的研究。这种主动的交互作用证明了用来指代学习者的代理的术语。代理目标的实现通常是通过它从环境中获得的奖励并寻求最大化的奖励来衡量的。

我们首先介绍了强化学习的一般场景，然后介绍了马尔可夫决策过程$(MDPs)$的模型，在该领域被广泛采用，以及与该模型相关的政策或政策价值等基本概念。本章的其余部分介绍了针对规划问题的几种算法，它对应于代理已知环境模型的情况，然后是针对未知模型的更一般情况的一系列学习算法

17.1学习场景

强化学习的一般场景如图17.1所示。与前几章中考虑的监督学习场景不同，这里的学习者不会被动地接收一个标记的数据集。相反，它通过与环境的交互，通过一个行动过程来收集信息。为了响应一个动作，学习者或代理会接收到两种类型的信息：它在环境中的当前状态，以及特定于任务及其相应目标的实值奖励。

代理的目标是最大化其奖励，从而确定实现该目标的最佳行动方案或策略。 然而，他从环境中获得的信息只是与刚刚采取的行动相关的即时奖励。 环境不提供未来或长期的奖励反馈。 强化学习的一个重要方面是考虑延迟奖励或惩罚。 代理面临着探索未知状态和行动以获取有关环境和奖励的更多信息与利用已收集的信息来优化其奖励之间的两难境地。 这被称为强化学习固有的探索与开发权衡。

图 17.1 强化学习的一般场景的表示。

请注意，强化学习的学习场景与前几章中讨论的监督学习的学习场景之间存在一些差异。 与监督学习不同，在强化学习中，根据绘制的实例没有固定的分布； 它是定义观察分布的策略的选择。 事实上，政策的细微变化可能会对收到的奖励产生巨大影响。 此外，一般来说，环境可能不是固定的，并且可能会因代理选择的操作而变化。 对于某些学习问题，这可能是比标准监督学习更现实的模型。 最后，请注意，与监督学习不同，在强化学习中，训练和测试阶段是混合的。

这里可以区分两种主要设置：一种是代理已知环境模型，在这种情况下，其最大化收到的奖励的目标被简化为规划问题； 以及环境模型未知的情况，在这种情况下，代理面临学习问题。 在后一种情况下，代理必须从状态中学习并奖励收集的信息，以获取有关环境的信息并确定最佳行动策略。 本章介绍了这两种设置的算法解决方案

17.2 马尔可夫决策过程模型

我们首先介绍马尔可夫决策过程 $(MDP)$ 模型，这是强化学习中广泛采用的环境和与环境交互的模型。 $MDP$ 是一个马尔可夫过程，定义如下。

定义 17.1 $(MDP)$ 马尔可夫决策过程 $(MDP)$ 定义为：

• 一组状态 S，可能是无限的。

图 17.2

MDP 在不同时间的状态和转换的图示。

1. • 一组状态$S$，可能是无限的。

2. • 开始状态或初始状态 $s{}_0\in S$。

3. • 一组动作A，可能是无限的。

4. • 转移概率$P[s^{\prime }\mid s,a]$：目标状态$s^{\prime }=\delta (s,a)$ 上的分布。

5. • 奖励概率$P[r^{\prime }$\mid$s,a]$：返回的奖励分布 $r^{\prime }=r(s,a)$。

该模型是马尔可夫模型，因为转移和奖励概率仅取决于当前状态，而不取决于状态和所采取行动的整个历史。 MDP 的这个定义可以进一步推广到非离散状态和动作集的情况。

在离散时间模型中，在一组决策时期 $0,...,T$，这就是我们将在下面采用的模型。该模型也可以直接推广到连续时间模型，其中在任意时间点采取行动。

当 $T$是有限的时，MDP 被称为具有有限的范围。独立于时间范围的有限性，当$S和A$都是有限集时，MDP 被称为有限集。在这里，我们考虑一般情况，当采取行动$a$ 时，状态$s$的奖励 $r(s,a)$是一个随机变量。然而，在许多情况下，奖励被假定为状态和动作对$(s,a)$的确定性函数。

图 17.2 说明了对应于$MDP$ 的模型。在时间$t\in 0,...,T$ 代理观察到的状态是 $s_t$并且它在$a{}_t\in A$处采取行动。达到的状态是 $s_{t+1}$（概率为 $[s_{t+1}\mid s_t,a_t])$收到的奖励为$r_{t+1}\in R$概率为$P[r_{t+1}\mid s_t,a_t])。$

许多现实世界的任务都可以用$MDP$来表示。图 17.3 给出了机器人在网球场上捡球的简单$MDP$示例。

17.3 策略

$MDP$环境中代理的主要问题是确定在每个状态下要采取的动作，即动作策略。

17.3.1 定义

定义 17.2（策略） 策略是映射 $\pi$:S$\to \Delta$(A)，其中 $\Delta (A)是A$上的一组概率分布。如果对于任何$s$,在唯一的$a\in A$，则策略$\pi$是确定性的 使得 $\pi (s)(a)=1$。在这种情况下，我们可以通过从 S 到 A 的映射来识别 $\pi$，并使用 π(s) 来表示该动作。

更准确地说，这是固定策略的定义，因为动作分布的选择不依赖于时间。 更一般地说，我们可以将非平稳策略定义为由$t$索引的一系列映射 $\pi t:S\to \Delta (A)。$特别是，在有限范围的情况下，非平稳策略通常是优化奖励所必需的。

代理的目标是找到最大化其预期（奖励）回报的策略。它沿着特定的状态序列 s${}_0$,... 遵循确定性策略 π 接收到的回报。$...,s_T$定义如下：

1. 对于有限范围$(T<\infty ):{\sum }_{t=0}^{T}r（s_t,\pi (s{}_t)$

2. 对于无限范围$（T=\infty ）:{\sum }_{t=0}^{+\infty }{\gamma }^{t}r(s_t,\pi (s_t))$,其中$\gamma \in [0,1)$是一个小于用于折现未来奖励的常数因子。

请注意，回报是一个单一的标量，总结了可能无限的即时奖励序列。在打折的情况下，早期奖励被认为比后期奖励更有价值。

17.3.2 政策价值

这导致了每个状态的政策价值的以下定义。

定义 17.3（策略值） 策略$\pi$在状态=$s\in S的值V\pi (s)$定义为从$s$开始并遵循策略 $\pi$ 时返回的预期奖励： 1.有限范围：$V_{\pi }(s)=E_{at\sim \pi (S{}_t)}[{\sum }_{t=0}^{T}r（s_t,a_t)\mid s_0=s];$
2.无限范围:$V_{\pi }(s)=E_{at\sim \pi (S{}_t)}[{\sum }_{t=0}^T{\gamma }^{t}r（s_t,a_t)\mid s_0=s],$其中期望是根据分布$\pi (s_t)$随机选择一个行为$a_t$，一个无限的无法折扣的范围也经常被认为是基于平均奖励存在时的限制。

17.3.3最优策略

从状态 s $\in$ S 开始，为了最大化其奖励，代理自然会寻找具有最大值 $V_{\pi }(s)$ 的策略$\pi 。$在本节中，我们将展示，值得注意的是，对于无限范围设置中的任何有限$MDP$，都存在对任何起始状态都是最优的策略，即具有以下定义的策略。

定义17.4（最佳策略） 一个策略${\pi }^{\ast }$是最优的，如果它的值对于每个状态$s\in S$都是最大的，也就是说，对于任何策略$\pi$和任何状态$s\in S，V{}_{{\pi }^{\ast }}(s)\ge V_{\pi }(s)。$

图 17.3

机器人在网球场上捡球的简单 MDP 示例。 动作集是 A = {search, Carry, pick} 并且状态集简化为 S = {start, other}。 每个转换都标有动作，然后是转换概率的概率和采取该动作后收到的奖励。 $R_1、R_2和R_3$实数，表示与每个转换相关的奖励（确定性奖励的情况）。

此外，我们将证明对于任何 MDP 都存在确定性最优策略。 为此，引入状态-动作值函数的概念很方便。

定义 17.5（状态-动作价值函数） 与策略$\pi$相关的状态-动作价值函数$Q$被定义为所有$(s,a)\in S\times A$作为在状态$s\in A$采取动作$a\in A$的预期回报$S$，然后遵循策略$\pi ：$

$$\begin{array}{rlrlrlr}{Q}_{\pi }(s,a)& =\sum [r(s,a)]+\sum _{a_t\sim \pi (s{}_t}[\sum _{t=1}^{+\infty }{\gamma }^t(s_t,a_t)\mid s_0=s,a_0=a]& & & & & (17.1)\\ & =\sum [r(s,a)+\gamma V_{\pi }(s_1)\mid s_0=s,a_0=a].& & & & & \end{array}$$

请注意，${\sum }_{a\sim \pi (s)}[Q_{\pi }(s,a)]=V_{\pi }(s)$（参见命题17.9）

定理17.6（策略改进定理） 对于任意两种策略$\pi$和${\pi }^{\prime }$，适用如下

$({\forall }_s\in S,\sum _{a\sim {\pi }^{\prime }(s)}(s,a)]\ge \sum _{a\sim \pi (s)}[Q_{\pi }(s,a)])\Rightarrow ({\forall }_s\in S,V_{{\pi }^{\prime }}(s)\ge V_{\pi }(s))$.

此外，左侧至少一个状态 的严格不等式意味着右侧至少一个状态 s 的严格不等式

证明：假设 $\pi$验证左侧。 对于任何 $s\in S$,我们有

$$\begin{array}{rl}{V}_{\pi }(s)& =\sum _{a\sim \pi (s)}[Q_{\pi }(s,a)]\\ & \le \sum _{a\sim {\pi }^{\prime }(s)}[Q_{\pi }(s,a)]\\ & =\sum _{a\sim {\pi }^{\prime }(s)}[r(s,a)+\gamma V_{\pi }(s_1)\mid s_0=s]\\ & =\sum _{a\sim {\pi }^{\prime }(s)}[r(s,a)+\gamma \sum _{a\sim {\pi }^{\prime }(s_1)}[Q_{\pi }(s_1,a_1)]\mid s_0=s]\\ & \le \sum _{a\sim {\pi }^{\prime }(s)}[r(s,a)+\gamma \sum _{a\sim {\pi }^{\prime }(s_1)}[Q_{\pi }(s_1,a_1)]\mid s_0=s]\\ & =\sum _{\begin{array}{c}a\sim {\pi }^{\prime }(s)\\ a_1\sim {\pi }^{\prime }(s_1)\end{array}}[r(s,a)+\gamma r(s_1,a_1)+{\gamma }^2{V}_{(}{s}_2)\mid s_0=s]\end{array}$$

以这种方式进行表明，对于任何$T\ge 1：$

$V_{\pi }(s)\le \sum _{a_t\sim {\pi }^{\prime }(s_t)}[\sum _{T=0}^T{\gamma }^t\sum ][r(s_t,a_t)]+{\gamma }^{T+1}{V}_{\pi }(s_{T+1})\mid s_0=s]$

由于 $V_{\pi }(s_{T+1})$ 是有范围的，取极限$T\to \infty$  给出

$V_{\pi }(s)\le \sum _{a_t\sim {\pi }^{\prime }(s_t)}[\sum _{t=0}^{+\infty }{\gamma }^t\sum [r(s_t,a_t)]\mid s_0=s]=V_{\pi }^{\prime }(s).$

最后，左侧性质中的任何严格不等式都会导致上述不等式链中的严格等式。

定理 17.7（Bellman 的最优性条件） 策略 $\pi$是最优的，当条件是任何对 $(s,a)\in S\times A$且$\pi (s)(a)>0$满足以下条件：

$a\in \underset{a^{\prime }\in A}{\mathrm{argmax}}{Q}_{\pi }(s,a^{\prime })$

证明：根据定理 $17.6$，如果条件 $(17.2)$ 对某些$(s,a)$ 不成立且 $\pi (s)(a)>0$,则策略$\pi$ 不是最优的。这是因为 $\pi$ 可以通过定义 ${\pi }^{\prime }$ 得到改进，使得 ${\pi }^{\prime }(s^{\prime })=\pi (s)for{s}^{\prime }\ne s$ 并且 ${}^{\prime }(s)集中在$argmax_{a'\in A}$Q_{\pi }(s，a^{\prime }）。$因此，根据定理$17.6$，对于至少一个 $s$ 和 $\pi ，V{\pi }^{\prime }(s)>V\pi (s)$不是最优的。
相反，让${\pi }^{\prime }$ 是一个非最优策略。 那么存在一个策略 $\pi$ 和至少一个状态 s，其中 $V{\pi }^{\prime }(s)<V\pi (s)$。 根据定理 $17.6$，这意味着存在一些状态 $s\in S$，其中 ${\sum }_{a\sim {\pi }^{\prime }(s)}<{\sum }_{a\sim \pi (s)}[Q_{\pi }(s,a)]$。 因此，${\pi }^{\prime }$能满足条件$（17.2）$。]

定理 17.8（最优确定性策略的存在）

任何有限 MDP 都承认最优确定性策略。

证明：令 ${\pi }^{\ast }$ 成为最大化${\sum }_{s\in S}{V}_{\pi }(s)$ 的确定性策略。 ${\pi }^{\ast }$ 存在是因为只有有限多个确定性策略。 如果 ${\pi }^{\ast }$ 不是最优的，根据定理 $17.7$，将存在一个状态$s$，其中 $\pi (s)\in argma{x}_{a^{\prime }\in A}{Q}_{\pi }(s,a^{\prime })$。 根据定理 $17.6$，可以通过选择策略 $\pi$ 来改进 $\pi$∗，其中 $\pi (s)\in argmaxaxa\in A{Q}_{\pi }(s,a^{\prime })$并且 $\pi$与所有其他状态的 $\pi$∗ 重合。 但随后 $\pi$ 将验证 $V\pi \ast (s)\le V\pi (s)$ 至少对于一种状态具有严格的不等式。 这与 $\pi \ast$ 最大化${\sum }_{s\in S}{V}_{\pi }(s)$的事实相矛盾。

鉴于存在确定性最优策略，在下文中，为简化讨论，我们将仅考虑确定性策略。 让${\pi }^{\ast }$ 表示一个（确定性的）最优策略，让 $Q\ast$ 和 $V\ast$ 表示其对应的状态动作价值函数和价值函数。 由定理 $17.7$，我们可以写出.

$\forall s\in S,{\pi }^{\ast }(s)=\underset{a\in A}{\mathrm{argmar}}{Q}^{\ast }(s,a)$

因此，状态-动作价值函数$Q^{\ast }$的知识足以让智能体确定最优策略，而无需直接了解奖励或转移概率。 根据定义替换 $Q^{\ast }$ 给出了以下最优策略值 $V^{\ast }(s)=Q^{\ast }(s,{\pi }^{\ast }(s))$ 的方程组：

$\forall s\in S,V^{\ast }(s)=\underset{a\in A}{\max }\sum [r(s,a)]+\gamma \sum _{s^{\prime }\in S}P[s^{\prime }\mid s,a]V^{\ast }(S^{\prime })$,

又称贝尔曼方程。 请注意，由于$max$运算符的存在，该方程组不是线性的。

17.3.4 政策评估

一个策略在状态 s 的价值可以用它在其他状态的价值来表达 状态，形成一个线性方程组。

命题 17.9（贝尔曼方程）

对于无限范围$MDP$，策略 $\pi$ 在状态 $s$的值 V$\pi$(s) 服从以下线性方程组$\in s$

$\forall s\in S,V_{\pi }(s)=\sum _{a_1\sim \pi (s)}[r(s,a_1)]+\gamma \sum _{s^{\prime }}P[s^{\prime }\mid s,\pi (s)]V_{\pi }(s^{\prime })$

证明：我们可以将策略值的表达式分解为第一项和其余项的总和，其中承认 γ 作为乘数：

$$\begin{array}{rl}{V}_{\pi }(s)& =E[\sum _{t=0}^{+\infty }{\gamma }^{t}r(s_t,\pi （s_t))\mid s_0=s].\\ & =E[r(s,\pi (s))]+\gamma E\sum _{t=0}^{+\infty }{\gamma }^{t}r(s_{t+1},\pi (s_{t+1}))\mid s_0=s]\\ & =E[r(s,\pi (s))]+\gamma E\sum _{t=0}^{+\infty }{\gamma }^{t}r(s_{t+1},\pi (s_{t+1}))\mid s_1=\delta （s,\pi (s))]\\ & =E[r(s,\pi (s)]+\gamma E[V\pi (\delta (s,\pi (s)))]\end{array}$$

至此，证明完毕。 这是一个线性方程组，也称为贝尔曼方程，不同于非线性系统 $(17.4)。$系统可以改写为
$V=R+\gamma PV$
使用以下符号：$P$表示由$P_{s,s^{\prime }}=P[s^{\prime }\mid s,\pi (s)]$定义的转移概率矩阵，对于所有$s,s^{\prime }\in S$;$V$是第$s$个分量为$V_S=V_{\pi }(s)$的值列矩阵； 和$R$是奖励列矩阵，其第$s$分量是$R_s=E[r(s,\pi (s)].$ $V$通常是贝尔曼方程中的未知变量，通过求解它来确定。

以下定理表明，对于有限$MDP$,该线性方程组允许唯一解。

定理 $17.10$ 对于有限$MDP$,$Bellman$方程允许唯一解由下式给出

$V_0=(I-\gamma P{)}^{-1}R.$

证明：贝尔曼方程$（17.6）$可以等价地写为
$(I-\gamma P)V=R.$

因此，为了证明该定理，只需证明$(I-\gamma P)$是可逆的。 为此，请注意$P$的无穷大可以使用其随机性属性计算：
$||P|{|}_{\infty }=\underset{s}{\max }\sum _{s^{\prime }}|P_{s{s}^{\prime }}|=\underset{s}{\max }\sum _{s^{\prime }}P[s^{\prime }|s,\pi (s)]=1$

这意味着 $||\gamma P|{|}_{\infty }=\gamma <1。\gamma P$的特征值因此都小于$1$,并且$(I-\gamma P)$ 是可逆的

作者：人间翩若惊鸿
链接：https://juejin.cn/post/7015947157437939719