增强学习

作者: 有机会一起种地OT | 来源:发表于2019-11-01 21:28 被阅读0次

介绍
第一部分参数方法——类密度模型参数估计
第二部分监督学习——分类（基于似然的方法）
第三部分监督学习——分类（基于判别式的方法）（参数方法——判别式参数估计）
第四部分监督学习——回归
第五部分监督学习——关联规则
第六部分维度规约（特征的提取和组合）
第七部分半参数方法
第八部分非监督学习——聚类
第九部分非参数方法——密度估计
第十部分非参数方法——决策树实现的判别式
第十一部分多层感知器——非参数估计器
第十二部分局部模型
第十三部分支持向量机与核机器
第十四部分隐马尔科夫模型
第十五部分参数的贝叶斯估计
第十六部分集成学习——组合多学习器
第十七部分增强学习
第十八部分机器学习实验
第十九部分特征工程与数据预处理

在增强学习中，学习器是一个制定决策的智能系统。系统在其所处的环境中执行一系列动作，并根据其试图解决一个问题所执行的动作而获得反馈。最终需要学习的是最优策略，也就是反馈最优的动作序列。

需要考虑的环境时刻都处于某一状态下，每次系统做出某一动作，环境状态就随之改变。但不同于监督学习方法，增强学习并不会在没做出一个动作后就得到反馈，发挥监督作用。而是只有在一个完整的动作序列结束后，才能得到反馈，来描述整个动作序列的好坏。
增强学习可以看做“批评者”学习，批评者不会提前提供信息，只会在最后告诉我们结果怎么样。这是与作为“老师”的监督学习的不同之处。

在执行完一个动作序列并得到反馈后，就涉及信度分配的问题。我们希望对之前所执行的单个动作进行评估，来找到可以得到好的反馈的动作，以便以后再用。增强学习所做的就是为中间状态或动作产生一个内部值，来反应这些中间状态和动作对于达到好的结果又多大帮助。而一旦学习得到这样的内部奖励机制，智能系统主体就可以只执行最大化内部奖励的局部动作。

使用马尔科夫决策过程来对智能主体建模。类似于马尔科夫模型，对环境状态分为可观测和不可观测的情况，对于不可观测则意味着系统不能确切地知道环境所处的状态。

单状态

从一个只有一个动作的简单例子开始。K臂赌博机是一种假想的具有K个手柄的老虎机，可做的动作是选择并拉下其中一个手柄。这是一个分类问题，从K个手柄中选择一个。
对于分类问题，在监督学习下，数据会告诉我们哪个是正确的类。但在增强学习中，只能尝试不同的动作来记录其中最好的一个。在K臂赌博机的例子中，只有一个状态（赌博机），只需要决定一个动作，在执行动作后立即可得到一个反馈。所以这是一个简化的增强学习问题，其反馈是没有延迟的。

假设 $Q(a)$ 是动作 a 的价值。初始时，对所有的 a 都有 $Q(a)=0$ 。但执行了动作 a 后，得到一个反馈 $r_a\geq0$ 。
如果反馈是确定的，那么每次拉下手柄 a ，都会得到相同的 $r_a$ ，这样可以直接令 $Q(a)=r_a$ 。通过尝试不同的动作，并对所有的 a 存储 $Q(a)$ ，找到最高价值的动作 $a^*=\arg\max_aQ(a)$ 。
如果反馈不是确定的，则在采取相同动作时，每次得到的反馈都不同。用 $p(r|a)$ 来定义反馈的分布。这种情况下，定义 $Q_t(a)$ 为时刻 t 是执行动作 a 的价值估计，是在时刻 t 之前执行 a 所获得的的所有反馈的平均值。在线的更新策略可写为：
$Q_t(a)=Q_{t-1}(a)+\frac1t[r_a-Q_{t-1}(a)] \tag{a}$

以单状态的简单问题为基础，在以下几个方面进行推广成为完整的增强学习问题。
第一，有多个状态，这相当于存在多个不同奖励概率 $p(r|s_i,a_j)$ 的赌博机。按概率得到 $Q(s_i,a_j)$ ，即在状态 $s_i$ 时执行动作 $a_j$ 得到的反馈。
第二，动作不仅影响获得的反馈，还影响下一个状态，也就是马尔科夫过程的状态转移。
第三，由于存在多个动作，可观测的最终反馈被延迟。需要根据延迟的反馈信息来学习局部的信度分配。

增强学习的要素

增强学习中的学习决策系统称作智能主体。主体与环境之间进行交互，通过感知器观测主体在环境中的状态，并执行修改状态的动作。而当主体执行一个动作时，环境会提供一个反馈，但反馈存在延时。
用 $s_t \in S$ 表示主体在时刻 t 的状态， $S$ 是所有可能状态的集合。 $a_t \in A(s_t)$ 表示主体在时刻 t 所执行的动作，其中 $A(s_t)$ 是状态 $s_t$ 时所有可能的动作集合， $r_{t+1}=Q(s_t,a_t)$ 是得到的反馈。

整个问题通过马尔科夫决策过程来建模，反馈和状态转移分别对应于相应的概率 $p(r_{r+1}|s_t,a+t)$ 和 $P(s_{t+1}|s_t,a_t)$ 。注意，在这个马尔科夫系统中，仍然假设了下一时刻的状态和反馈都仅仅依赖于当前状态的状态和动作。
根据具体应用的不同，某一状态被指定为初始状态，某一状态作为停止动作的终止状态，且终止状态不具有单独地反馈信息。从初始状态到终止状态的动作序列称作片段。

策略 $\pi$ 定义了智能主体的行为，是从环境状态到动作的一个映射。定义在任意状态 $s_t$ 下执行的动作： $a_t=\pi(s_t)$ 。
策略的价值 $V^{\pi}(s_t)$ 定义为从状态 $s_t$ 开始，主体遵循策略 $\pi$ 所得到的期望累计反馈。

在有限时界模型中，主体试图最大化最后T个步骤的期望奖励：
$V^{\pi}(s_t)=E[r_{t+1}+r_{t+1}+\cdots+r_{t+T}]=E[\sum^T_{i=1}r_{t+i}]$
而在无限时界的模型中，任务不存在固定的场景长度限制，也就不存在动作序列长度的限制，但未来的反馈被打折扣，有
$V^{\pi}(s_t)=E[r_{t+1}+\lambda r_{t+1}+\lambda^2 r_{t+2}+\cdots]=E[\sum^{\infty}_{i=1}\lambda^{i-1}r_{t+i}]$
$\lambda$ 称为折扣率，如果 $\lambda=0$ ，则只有立即反馈；如果 $\lambda$ 趋向于1，未来的奖励将更多地计算在内，这时可以认为智能主体更有远见。

需要找到最优的策略 $\pi^*$ 使得：
$V^*(s_t)=\max_{\pi}V^{\pi}(s^t),\forall s^t$
用 $V(s_t)$ 表示智能主体处于状态 $s_t$ 点的价值，那么 $V^*(s_t)$ 也表示主体处于状态 $s_t$ 时可能的最高价值。
如果定义 $Q^*(s_t,a_t)$ 表示当处于状态 $s_t$ 时执行动作 $a_t$ 并在其后遵循最优策略的期望累计反馈。从而上式最优策略的价值等于在状态 $s_t$ 上采取最优动作 $a_t$ 并在其后遵循最优策略的价值。
$\begin{align} V^*(s_t)=&\max_{a_t}Q^*(s_t,a_t)\\ =&\max_{a_t} E[\sum_{i=1}^{\infty}\lambda^{i-1}r_{t+i}]\\ =&\max_{a_t} E[r_{t+1}+\lambda\sum_{i=1}^{\infty}\lambda^{i-1}r_{t+i+1}]\\ =&\max_{a_t}E[r_{t+1}+\lambda V^*(s_{t+1})]\\ =&\max_{a_t} ( E[r_{t+1}]+\lambda \sum_{s_{t+1}}P(s_{t+1}|s_t,a_t)V^*(s_{t+1})) \tag{b} \end{align}$
这可解释为以概率 $p(s_{t+1}|s_t,a_t)$ 转移到 $s_{t+1}$ 并自此遵循最优策略，所得到的期望累计反馈。在所有可能的下一状态上求和，并按转移概率加权。
类似地有
$Q^*(s_t,a_t)=E[r_{t+1}]+\lambda \sum_{s_{t+1}}P(s_{t+1}|s_t,a_t) \max_{a_{t+1}} Q^*(s_{t+1},a_{t+1}) \tag{c}$

而一旦得到 $Q^*(s_t,a_t)$ ，就可以定义策略 $\pi$ 为执行动作 $a^*_t$ ，在所有的 $Q^*(s_t,a_t)$ 中取最大值： $\pi^*(s_t):a^*_t=\arg \max_{a_t}Q^*(s_t,a_t)$
这意味着只要得到 $Q^*(s_t,a_t)$ ，那么在每个局部步骤中使用贪心搜索，就可以得到一个最优的动作序列，最大化累计反馈奖励。

基于已知模型的学习

已知模型就是指已知环境模型的参数 $p(r_{t+1}|s_t,a_t)$ 和 $P(s_{t+1}|s_t,a_t)$ 。此时，最优价值函数 (c) 是唯一的，可直接时使用动态规划对其求解。进而，最优策略就是最大化下一状态价值的动作：
$\pi^*=\arg\max_{a_t}(E[r_{t+1}|s_t,a_t]+\lambda\sum_{s_{t+1}}P(s_{t+1}|s_t,a_t)V^*(s_{t+1}))$

价值迭代
为了找到最优策略 $\pi^*$ ，价值迭代是一种迭代方法。其过程如下：
1.初始化各状态 $s$ 的价值 $V(s)=0$ ，时刻 $t=1$
2.在时刻 $t$ ，对所有的 $s\in S$ ，取智能主体处于状态 $s$ 的价值
$V^{\prime}(s)=\max_{a}(E[r|s,a]+\lambda\sum_{s^{\prime}}P(s^{\prime}|s,a)V(s^{\prime}))$
其中 $s^{\prime}$ 是在 $t$ 时刻下状态 $s$ （ $s_t$ ）的下一时刻状态，也就是前文带时刻的状态 $s_{t+1}$ ，其他符号类似。
3.令 $V(s)=V^{\prime}(s)$ ，对给定 $\delta$ ，如果 $\max_{s\in S}|V^{\prime}(s)-V(s_t)|<\delta$ ，则 $V(s)$ 收敛，停止循环。
4. $t=t+1$ ，从第二步继续。
该方法最终收敛于最优的 $V^*$ 值
策略迭代
直接存储和更新策略，而不是间接地通过价值迭代寻找最优最优策略。其思想是从一个策略开始，不断改进它直到没有改变为止。迭代过程如下：
1.随机初始化策略 $\pi$ 。
2。求解线性方程组，计算使用策略 $\pi$ 的价值
$V^{\pi}(s)=E[r|s,\pi(s)]+\lambda\sum_{s^{\prime}\in S}P(s^{\prime}|s,\pi(s))V^{\pi}(s^{\prime})$
3.在每个状态上改进策略
$\pi^{\prime}(s)=\arg\max_a(E[r|s,a]+\lambda\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)V^{\pi}(s^{\prime}))$
重新得到完整策略 $\pi^{\prime}$
4.当 $\pi=\pi^{\prime}$ 时结束，否则回到第2步。

策略迭代的复杂度更高，但所需迭代次数更少。

未知模型——时间差分学习

如上一部分所介绍的，在已知环境模型参数的情况下，可使用动态规划求得最佳策略。但这种情况往往很难实现，很少会具有完整的环境知识。增强学习更实际的应用是没有模型的情况。这时需要对环境进行探索来查询模型。
未知模型的情况下，不假定已知环境模型的知识 $p(r_{s+1}|s_t,a_t)$ 和 $P(s_{s+1}|s_t,a_t)$ 。在学习过程中，当得到下一状态的反馈价值时，据此更新当前状态的价值，并以此向前面的时刻推进。这种方法称为时间差分。

探索策略的方法

首先需要对环境进行探索，通过多组动作序列的探索得到反馈来学习参数。
一种可能的探索方式称作 $\epsilon$ 贪心搜索。该方法在当前策略 $\pi$ 的基础上，以概率 $\epsilon$ 在所有可能动作中均匀随机地选择一个动作，以概率 $1-\epsilon$ 执行策略 $\pi$ 已知的最好动作：
$\pi^{\epsilon}(s)=\left\{\begin{array}{} a \in A & p(a)=1-\epsilon \\ \pi(s) & p(\pi(s))=\epsilon \\ \end{array} \right.$
其中的随机性保证了在环境中的探索，得到不同的动作序列。但并不需要一直探索下去，随着探索次数的增加，逐渐减低 $\epsilon$ ，更倾向于利用策略 $\pi$ 。
除了 $\epsilon$ 贪心，还可根据动作的概率进行选择，使用软最大函数将动作价值转化为概率：
$P(a|s)=\frac{\exp Q(s,a)}{\sum_{b\in A}\exp Q(s,b)}$
根据概率来对动作进行选择。同样，像 $\epsilon$ 贪心中减小 $\epsilon$ 一样降低探索的程度，采用退火过程来完善上式：
$P(a|s)=\frac{\exp \frac{Q(s,a)}T}{\sum_{b\in A}\exp \frac{Q(s,b)}T}$
开始的时候采用较大的温度 $T$ ，虽有动作的概率近似，更倾向于探索。随着T减小，更好的动作被青睐。

确定性动作下的探索

先讨论较简单的确定性情况作为铺垫，此时对任意状态-动作对，只有一个可能的奖励和下一状态。也就是说 $p(r_{s+1}|s_t,a_t)$ 和 $P(s_{s+1}|s_t,a_t)$ 都在某一确定值上概率为1，其余为0。
这样，（c）式化简为
$Q^*(s_t,a_t)=r_{t+1}+\lambda \max_{a_{t+1}} Q^*(s_{t+1},a_{t+1})$
当处于状态 $s_t$ 时，采用前面所说的策略探索方法选择一个动作 $a_t$ ，返回一个奖励 $r_{t+1}$ 并转移到新状态 $s_{t+1}$ 。那么根据上市，动作 $a_t$ 的价值更新为
$\hat{Q}(s_t,a_t)=r_{t+1}+\lambda \max_{a_{t+1}} \hat{Q}(s_{t+1},a_{t+1})$
是该轮探索的估计值，并由此更新了策略 $\pi$ 。

对一次片段的初始时，所有的 $\hat{Q}(s,a)$ 作为立即奖励均为0。当到达目标状态时，得到反馈奖励 $r$ ，因而前一状态-动作价值更新为 $\lambda r$ 。但并不对片段中更前的状态-动作价值进行更新，而是在以后的片段中，通过立即奖励将 $\lambda r$ 反馈给前面的状态，更新得到 $\lambda^2 r$ 。也就是只通过立即奖励进行更新。经过多个片段后，信息被后退到更早的状态-动作对。通过多次迭代，估计得到完整的价值函数，并学习最优策略。

非确定性下的探索

如果反馈奖励 $r$ 和动作 $a$ 的转移结果状态 $s$ 不是确定的，也就是存在概率分布 $p(r_{s+1}|s_t,a_t)$ 和 $P(s_{s+1}|s_t,a_t)$ 。这些概率分布函数对环境中的不确定性进行建模。在这种情况下，有（c）式的形式
$Q(s_t,a_t)=E[r_{t+1}]+\lambda \sum_{s_{t+1}}P(s_{t+1}|s_t,a_t) \max_{a_{t+1}} Q(s_{t+1},a_{t+1})$
这时不能像确定性动作那样，直接通过后面的状态的价值给前面状态的价值赋值。因为对于相同的状态-动作，可能获得不同的奖励及不同的下一状态。需要取移动平均，这称为 $Q$ 学习：
$\hat{Q}^{\prime}(s_t,a_t)=\hat{Q}(s_t,a_t)+\frac1{t+1}(r_{t+1}+\lambda\max_{a_{t+1}} \hat{Q}(s_{t+1},a_{t+1})-\hat{Q}(s_t,a_t)) \tag{d}$
对应到单状态情况，就是式（a），是一种在线更新方式。（d）可以看做用来减小当前估计值 $\hat{Q}(s_t,a_t)$ 和从下一时刻 $\hat{Q}(s_{t+1}a_{t+1})$ 后推来的估计值之间的差。所以称之为时间差分。 $Q$ 学习收敛于最优的 $Q^*$ 值。

（d）是一种策略离线方法，因为 $t+1$ 时刻的动作采用最优动作，而没有使用策略。而在策略在线方法中， $t+1$ 时刻的动作仍然来自于当前片段策略 $\pi$ ：
$\hat{Q}^{\prime}(s_t,a_t)=\hat{Q}(s_t,a_t)+\frac1{t+1}(r_{t+1}+\lambda \hat{Q}(s_{t+1},a_{t+1})-\hat{Q}(s_t,a_t)) \tag{e}$
这称作Sarsa算法，是Q学习方法的策略在线版本。不选择所有可能的动作中最好的，而是使用从 $Q$ 值推导出的策略（如 $\epsilon$ 贪心方法）来选择动作。

完全相同的方法也可用于学习 $V(s_t)$ 。

资格迹

前面所讨论的方法中，时间差分仅用于更新前一时刻的状态-动作价值Q（或状态价值V）。资格迹是对以往出现的状态-动作的记录，可以实现时间限度分配。
以Q值为例。每个状态-动作对存在一个资格 $e(s,a)$ ，初始化为0，且每一时刻都对其进行更新。当状态-动作对 $(s,a)$ 在片段的某一时刻中出现，其资格被设置为1，同时其他所有状态-动作对的资格乘以一个迹衰减参数 $0\leq \gamma\leq 1$ ， $\lambda$ 仍是折扣率。
$e_t(s,a)=\left\{\begin{array}{} 1 & if\ s=s_t,a=a_t\\ \lambda\gamma e_{t-1}(s,a) & else\\ \end{array} \right. \tag{f}$
对于从没被访问过的状态-动作对，其资格已知保持0。如果某个状态-动作对被访问了，那么随着时间推进，它的资格逐渐衰减，直到再次被访问重置为1。
在Sarsa算法中，在时刻 t 对Q值更新的误差为 $\delta_t=r_{t+1}+\lambda \hat{Q}(s_{t+1},a_{t+1})-\hat{Q}(s_t,a_t)$ 。

具有资格迹的Sarsa方法称作Sarsa( $\gamma$ )，更新方程变为 $\hat{Q}^{\prime}(s,a)=\hat{Q}(s,a)+\frac1{t+1}e_t(s,a)\delta_t$ ，增加了一项资格参数。使用资格迹不仅更新 $Q(s_t,a_t)$ ，还更新其他所有的 $Q(s,a)$ 的。其中状态-动作对 $(s_t,a_t)$ 的资格 $e_t(s_t,a_t)=1$ ，更新方程和Sarsa方法一致。其他状态-动作对的资格依赖于它们过去出现有多久，根据（f）给出。

连续的状态及反馈

前面所讨论的问题中，状态和反馈都是离散的，根据概率 $p(r_{s+1}|s_t,a_t)$ 和 $P(s_{s+1}|s_t,a_t)$ 来得到值。并且通过将 $Q(s,a)$ 或 $V(s)$ 的值存储起来进行更新，尤其适用资格迹时还需要保存每时刻下状态-动作对的资格值。
这种基于存储表格的方法，对于状态和动作树很大时，需要非常大的表格才能覆盖问题。同时需要非常多的试验片段才嫩恶搞得到足够多的数据，来以可接受的准确度填满表格中的价值项。并且对于状态和动作是连续值时，将其离散化可能导致误差。

取代使用表格存储Q值，可以把问题看作一个监督的回归问题。其中定义归回器 $Q(s,a|\theta)$ ，将状态-动作对作为输入，通过参数 $\theta$ 来学习Q值。例如回归器可以是一个人工神经网络， $\theta$ 是连接权重。
采用回归方式需要相似的 $(s,a)$ 具有相似的价值Q，这对于连续值的情况比较符合。如果将回归方式用于前面的离散情况，也要确认相似的 $(s,a)$ 具有相似的价值Q，否则无法进行推广。

为了训练回归器，需要一个训练集。在Sarsa(0)情况下，也就是只进行但不更新的情况，用 $r_{t+1}+\lambda Q(s_{t+1},a_{t+1})$ 更新 $Q(s_t,a_t)$ 。
作为训练集来说，也就是输入为 $(s_t,a_t)$ ，输出为 $r_{t+1}+\lambda Q(s_{t+1},a_{t+1})$ 。训练中可将均方误差写作 $E^t(\theta)=[r_{t+1}+\lambda Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]^2$ 。一旦准备好数据，可用任意监督学习方法在训练集上进行学习。

部分可观测状态

强化学习中，智能主体通过传感器观测环境状态。前面的讨论中，认为环境状态 $s$ 可直接观测得到，但在某些应用中，状态是不可观测的，在执行动作 $a_t$ 后，新的状态 $s_{t+1}$ 是未知的。传感器的只有一个观测结果为 $o_{t+1}$ ，是 $s_t$ 和 $a_t$ 的概率函数 $P(o_{t+1}|s_t,a_t)$ 。这种情况，称为部分可观测马尔科夫决策过程，（就像马尔科夫过程和隐马尔科夫过程之间的差别）对应的价值成为
$Q(s_t,a_t)=E[r_{t+1}]+\lambda \sum_{o_{t+1}}[P(o_{t+1}|s_t,a_t)\sum_{t_{t+1}}p(s_{t+1}|o_{t+1})\max_{a_{t+1}}Q(s_{t+1},a_{t+1})]$

但这并不满足马尔科夫性，因为下一状态的观测不仅依赖于当前的动作和观测，还受到不可观测的状态影响。为了保持马尔科夫性，智能主体维护一个内部的信任状态 $b_t$ ，来总结片段中经历过的状态。
智能主体有一个状态估计子，它基于前一时刻的信任状态 $b_t$ 、动作 $a_t$ 以及当前观测 $o_{t+1}$ 来更新信任状态 $b_{t+1}$ ，概率为 $P(b_{t+1}|b_t,a_t)$ 。策略 $\pi$ 不再基于观测，而是基于信任状态产生动作。
这种情况下Q学习使用信任状态-动作的价值，而不是原本的状态-动作的价值：
$Q(b_t,a_t)=E[r_{t+1}]+\lambda \sum_{b_{t+1}}P(b_{t+1}|b_t,a_t)\max_{a_{t+1}}Q(b_{t+1},a_{t+1})$

增强学习

单状态

增强学习的要素

基于已知模型的学习

未知模型——时间差分学习

探索策略的方法

确定性动作下的探索

非确定性下的探索

资格迹

连续的状态及反馈

部分可观测状态

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习理论基础