5.3 贪婪算法与∈-贪婪算法

在进行策略选择的时候,有两种常见的算法:一种是单纯的仅考虑未来回报最大,我们称之为贪婪算法;一种是一方面考虑未来回报最大,另外也以一定的概率进行新的尝试,我们称为∈-贪婪算法。贪婪算法简单并易于实现,但是容易造成局部最优而并非全局最优,有点过于墨守成规,很有可能错过更美好的风景。∈-贪婪算法以一定的概率进行尝试,探索潜在的更优解,本书主要使用的都是这种算法。

∈-贪婪算法的一个最简单实现为,假设动作空间A包含n个动作,在状态s下,已知标号为max的动作Q值最大。定义参数∈,那么选择标号为max的动作的概率为1-∈,为了能有一定的探索能力,全部动作随机被选择的概率为 ,需要注意的是,探索阶段也可能选择标号为max的动作。

我们介绍一下用代码如何实现以上逻辑,我们约定Q函数以字典的形式保存:


Q = dict()

在本例中,Q函数可以理解为一个二维的数组,Q(s,a)表示状态s下执行动作a得到的Q值,那么可以定义字典的键值形式为state_action,那么就可以把这个二维数组以字典的形式保存。

动作空间保存在数组actions中,定义我们的∈-贪婪算法函数,输入参数为Q函数,当前状态state和∈值epsilon,返回的结果为动作action:


def epsilon_greedy(Q, state, epsilon):

定义变量amax用于记录当前Q值最大时对应的动作空间数组actions的索引,并初始化为0。初始化Q函数的键值key,默认使用的动作为actions数组的第一个元素,即动作空间的第一个数据。定义变量qmax用于记录对应的最大Q值,初始化为当前状态state和动作空间的第一个数据actions[0]对应的Q值,代码如下:


amax = 0
key = "%d_%s"%(state, actions[0])
qmax = Q[key]

遍历整个动作空间,查找对应的Q值最大的action,并记录下对应的索引和Q值,分别保存在变量amax和qmax中:


for i in range(len(actions)):
    key = "%d_%s"%(state, actions[i])
    q = Q[key]
    if  qmax < q:
        qmax = q
        amax = i

下面我们将进入最重要的选择环节。目前,我们已经获得了当前Q值最大的action的索引amax,我们选择它的概率为1-∈,同时探索阶段选择各个action的概率均为 ,所以amax对应的action被选择的概率为:

我们定义一个数组pro记录每个action对应的概率:


pro = [0.0 for i in range(len(actions))]

初始化amax对应的概率为1-∈:


pro[amax] += 1-epsilon

遍历整个pro,设置探索阶段的概率,每个action对应的概率都是


for i in range(len(actions)):
    pro[i] += epsilon/len(actions)

在Python环境下,随机选择通常使用random.random(),它会随机返回0~1之间的一个小数,可以认为其分布满足均匀分布,代码如下:


r = random.random()
s = 0.0
for i in range(len(actions)):
    s += pro[i]
    if s>= r: return actions[i]
return actions[len(actions)-1]

如果希望随着强化学习的过程可以进一步控制∈,让策略进一步偏向于选择现有的最优解,即更小概率探索非当前最优解,常见的∈定义还有如下几种,其中t表示学习的时间。