David Silver 强化学习 第九讲

探索与利用

Posted by Pelhans on January 27, 2018

本部分主要介绍在强化学习领域如何进行有效的探索.

简介

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

利用: 做出当前信息下的最佳决定.

探索: 尝试不同的行为继而收集更多的信息.

可以看出利用和探索是一对矛盾的策略.因此我们需要在二者之间均衡.一个理想的策略应该可以牺牲一些短期利益,通过探索收集足够多的信息得到整体上的最佳策略.几种基本的探索方法为:

  1. 朴素探索(Naive Exploration): 在贪婪搜索的基础上增加一个Ɛ以实现朴素探索.

  2. 乐观初始估计(Optimistic Initialization): 优先选择当前被认为是最高价值的行为,除非新信息的获取推翻了该行为具有最高价值这一认知.

  3. 不确定优先(Optimism in the Face of Uncertainty): 优先尝试不确定价值的行为.

  4. 概率匹配(Probability Matching): 根据当前估计的概率分布采样行为.

  5. 信息状态搜索(Information State Search): 将已探索的信息作为状态的一部分联合个体的状态组成新的状态,以新状态为基础进行前向探索.

根据搜索过程中使用的数据结构,可将搜索分为:依据状态行为空间的探索(State-Action Exploration,根据算法尝试之前该状态下没有尝试的行为.)和参数化搜索(Parameter Exploration,用不同的参数设置实现探索)。

多臂赌博机上的探索例子

多臂赌博机简单来说就是那种拉一下就给出显示中没中奖那种机器,多臂就是很多个这种机器.原文图示是这种:

因此多臂赌博机可以看做行为空间和奖励组成的元组,不包含状态.<A, R>.假设该多臂赌博机由m个单臂的组成,行为就是落下某一个单臂赌博机,则数学表述为:在t时刻,个体从状态行为空间A选择一个行为,随后环境产生一个即时的奖励.采取行为a得到的即时奖励 r 服从一个个体未知的概率分布: .

那么问题就变成利用得到的即时奖励,个体使用怎样的搜索策略可以最大化它的累积即时奖励R.我们用Q代表行为价值,代表最优价值,为能带来该价值的最优行为,则:

但实际上我们不知道哪个赌博机由最高奖励,因此实际获得的Q可能与最优价值由一定差距,我们称之为后悔值:

随着行为的累积,后悔值也会累积,则总后悔值为:

这样就将最大化累计奖励的问题转化为最小化总后悔值了.但最优的奖励我们还不知道,因此我们就要采取额外的办法来解决问题.同时由于这是个优化问题,我们希望该后悔值能随着时间的推移,后悔值的增加逐渐变小.下面介绍几种较好的探索方法.

蒙特卡洛评估

先介绍一个评估方法,该方法使用每次的即时奖励计算得到t时刻止某一行为的平均价值:

该方法通过该平均价值来近似行为的实际价值Q(a).知道行为的实际价值,那通过比较也就知道哪个奖励最大了.

乐观初始估计(Optimistic Initialization)

前面说过,乐观初始估计会优先选择当前被认为是最高价值的行为,因此它会使得总后悔值线性增加,但实际应用的而效果却非常好.**其主要思想为在初始时给行为A一个较高的价值,随后使用递增蒙特卡罗评估来更新该行为的价值.这样通过蒙特卡洛的不断取样尽可能的尝试所有可能的行为.理论上,该方法与greedy或Ɛ-greedy结合带来的结果同样是线性增加的总后悔值。

衰减Ɛ-greedy(Decaying Ɛ-greedy)

假设我们现在知道每一个行为的最优价值 ,那么我们可以根据行为的价值计算出所有行为的差距 。可设置为:如果一个行为的差距越小,则尝试该行为的机会越多;如果一个行为的差距越大,则尝试该行为的几率越小。数学表达为:

它能够使得总的后悔值呈现出与时间步长的次线性(sublinear)关系:对数关系.但它需要知道每个行为差距.实际不可用.

不确定行为优先探索(optimism in the face of uncertainty)

核心思想为优先尝试不确定价值的行为.由下图可以看出,单纯用行为的奖励均值作为行为价值的估计进而知道后续行为的选择因为采样数量的原因可能会不够准确,更加准确的办法是估计行为价值在一定可信度上的价值上限,比如可以设置一个行为价值95%的可信区间上限,将其作为指导后续行为的参考。如此一个行为的价值将有较高的可信度不高于某一个值:

当某一行为的计数较少时,该行为价值某一可信度上的价值上限将偏离均值较多;随着针对某一行为的奖励数据越来越多,该行为价值在某一可信度的上限将越来越接近均值。我们可以用置信区间上界(Upper Confidence Bound, UCB)来指导行为的选择.即上式中最优的a.对于一般的分布未知的执行区间上界,根据定理与结合实际应用,我们有:

其中是行为a的计数,Q(a)是根据历史数据获得的奖励平均值.由UCB算法设计的探索方法可以使得总后悔值满足对数渐进关系

概率匹配 Probability Matching

概率匹配的想法先估计每一个行为可能是最佳行为的概率,然后依据这个概率来选择后续行为。越不确定价值的行为有着越高的几率被选择,这种被选择的目的是通过采样减少其不确定性,进而调整后续策略.

信息价值 Value of Information

探索之所以有价值是因为它会带来更多的信息,那么能否量化被探索信息的价值和探索本身的开销,以此来决定是否有探索该信息的必要呢?为了能够确定信息本身的价值,可以设计一个MDP,将信息作为MDP的状态构建对其价值的估计:

参考

《强化学习》第九讲 探索与利用