强化学习系列之五:价值函数近似

目前,我们已经介绍了一些强化学习的算法,但是我们无法在实际问题中运用这些算法。

为什么呢?因为算法估算价值函数 (v(s)) 或者 (q(s,a)),保存这些价值函数意味着保存所有状态。而实际问题中,状态的数目非常巨大,遍历一遍的事情就别想了。比如,围棋的状态总数是(3^{19}),听说比宇宙的总原子数还多,23333。解决这个问题的方法是抽特征。对于一个状态 s, 我们抽取一些特征 (\hat{\pmb{s}}),将这些特征代替状态作为价值函数的输入,即 (v(\hat{\pmb{s}})) 或者 (q(\hat{\pmb{s}},a))。这种方法我们称之为价值函数近似。价值函数近似解决了海量状态之后,我们才能实用强化学习算法。

1. 价值函数参数化

我们又要以机器人找金币为场景介绍价值函数近似。机器人从任意一个状态出发寻找金币,找到金币则获得奖励 1,碰到海盗则损失 1。找到金币或者碰到海盗,机器人都停止。衰减因子 (\gamma) 设为 0.8。

机器人找金币只有 9 个状态,但为了介绍价值函数近似,我们就假装状态非常多。我们以四个方向是否有墙作为状态特征,比如状态 1 的特征为 (\hat{s}=[1,0,0,1]), 分别表示北 (东、南、西) 方向有 (没有、没有、有) 墙。状态太多的情况下,模型无关的强化学习算法比较有用。模型无关的强化学习算法的工作对象是 (q(s,a)) (有状态特征之后为 (q(\hat{s},a))), 因此只有状态的特征是不够的。为此我们设定 (\pmb{f(\hat{s},a)}) 特征向量一共分为 |A| 部分,分别对应不同的动作。在 (\pmb{f(\hat{s},a)}) 特征向量, a 动作部分放上 (\hat{s}) 特征,其他动作部分全部置为 0。比如机器人找金币场景,状态 1 采取向北动作的特征向量 (\pmb{f(1,’n’)}) 如下。

(1)

搞出特征来了,接下来就用参数计算价值了。我们设定参数向量(\pmb{w}),然后用特征向量和权重向量的内积估计状态-动作价值。

(2)

这时强化学习其实就是学习参数 (\pmb{w}) 的值,使得参数化的 q 值 (q(\hat{s},a)) 尽量接近最优策略的 q 值 (q^{}(s,a)),优化目标如下所示。

(3)

我们用梯度下降法求解这个优化目标。梯度下降法首先要计算梯度 (\frac{\partial J}{\partial \pmb{w}} )。直接求导可得梯度。

(4)

但是状态很多,我们不可能真的按照上面的公式计算梯度 (上面的公式得遍历所有的状态)。实际的方法是让系统探索环境,遇到状态特征 (\hat{s}) 和采取动作 a, 计算梯度然后更新参数。这个类似随机梯度下降。

*** QuickLaTeX cannot compile formula:
\begin{eqnarray*}
\frac{\partial J}{\partial \pmb{w}}_{\hat{s},a} &=& { q(\hat{s},a) - q^{</em>}(s,a) }\pmb{f(\hat{s},a)} \nonumber \
\Delta \pmb{w} &=& -\alpha \frac{\partial J}{\partial \pmb{w}}_{\hat{s},a} \nonumber 
\end{eqnarray*}

*** Error message:
Extra alignment tab has been changed to \cr.
leading text: \Delta \pmb{w} &=&

参数更新的代码如下所示。

#qfunc 是最优策略的 q 值
#alpha 是学习率
def update(policy, f, a, qfunc, alpha):
    pvalue        = policy.qfunc(f, a);
    error         = pvalue - tvalue; 
    fea           = policy.get_fea_vec(f, a);
    policy.theta -= alpha * error * fea; 

2. 强化学习算法

看了上面,你可以会问。计算 (\frac{\partial J}{\partial \pmb{w}}{\hat{s},a}) 需要最优策略的 q 值,那我们上哪里去找这个值呢? 这是就是该强化学习算法上场了。我们回想一下三个模型无关的强化学习算法,都是让系统探索环境,探索时更新状态-动作价值。在更新时,MC Control 认为该样本的预期收益 (g_t) 为最优策略的 q 值,让状态-动作价值 q(s,a) 尽量接近。SARSA 认为 (r+\gamma q(s,a)) 为最优策略的 q 值,Q Learning 认为 (r+argmax{a’}{\gamma q(s’,a’)})。

*** QuickLaTeX cannot compile formula:
\begin{eqnarray*}
qfunc&=&g_t \quad &MC Control \nonumber \
qfunc&=&r+\gamma q(\hat{s},a) \quad &SARSA \nonumber \
qfunc&=&r+max_{a'}{\gamma q(\hat{s}',a')} \quad &Q Learning \nonumber 
\end{eqnarray*}

*** Error message:
Extra alignment tab has been changed to \cr.
leading text: qfunc&

有了这些想法,我们只需要简单地改变下强化学习算法的更新部分,就可以引入价值函数近似了。新的更新规则是将算法认为的最优策略的 q 值输入参数更新模块。觉个例子,价值函数近似之后的 Q Learning 算法代码如下所示。

def qlearning(grid, policy, num_iter1, alpha):
    actions = grid.actions;
    gamma   = grid.gamma;
    for i in xrange(len(policy.theta)):
        policy.theta[i] = 0.1

    for iter1 in xrange(num_iter1):
        f = grid.start();   
        #从一个随机非终止状态开始, f 是该状态的特征
        a = actions[int(random.random() * len(actions))]
        t = False
        count = 0

        while False == t and count < 100:
            t,f1,r      = grid.receive(a)
            #t  表示是否进入终止状态
            #f1 是环境接受到动作 a 之后转移到的状态的特征。
            #r  表示奖励

            qmax = -1.0
            for a1 in actions:
                pvalue = policy.qfunc(f1, a1);
                if qmax < pvalue:  qmax = pvalue;
            update(policy, f, a, r + gamma * qmax, alpha);

            f           = f1
            a           = policy.epsilon_greedy(f)
            count      += 1   
    return policy;

3. 做个实验

我们用机器人找金币做个实验吧。实验中,我们用了两种特征。一种特征是强特征,也就是上述四个方向是否有墙特征。另一种特征是 id 特征,特征向量长度为状态个数,第 i 个状态的特征向量的第 i 位为 1,其他位置为 0。实验对比了三种算法: MC Control, SARSA 和 Q Learning。(\epsilon-)贪婪策略的 (\epsilon) 设为 0.2, 学习率(\alpha) 设为 0.001。和上文一样,算法计算得到的状态(特征)-动作价值和最优策略的状态-动作价值之间的平方差,当做评价指标。实验的结果如下图所示。

这个实验结果告诉我们的第一件事就是选好特征。墙特征比 id 特征差。状态2 和 4 都是南北方向有墙,墙特征是一样的,会造成混淆。id 特征就没有这个问题。表现在实验结果上,MC Control 和 SARSA 在墙特征上都不停震荡,同时三种算法在墙特征的表现都不如其在 id 特征上的表现。

Q Learning 一如既往地表现出优越的效果。在墙特征上, Q Learning 不仅没有像 MC Control 和 SARSA 一样震荡,而且效果远远好于它们两者。在 id 特征上, Q Learning 完美拟合了最优策略的状态-动作价值。

4. 总结

实际问题中,状态的数目非常多,因此基于状态-动作价值的强化学习算法不适用。为了解决这个问题,人们提出了价值函数近似的方法。价值函数近似用特征表示状态或者状态-动作,用参数向量计算价值。价值近似之后,我们才算能把强化学习算法应用在实际问题上。本文代码可以在 Github 上找到,欢迎有兴趣的同学帮我挑挑毛病。强化学习系列的下一篇文章将介绍基于梯度的强化学习。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏量子位

刷剧不忘学CNN:TF+Keras识别辛普森一家人物 | 教程+代码+数据集

王小新 编译自 Medium 量子位 出品 | 公众号 QbitAI Alexandre Attia是《辛普森一家》的狂热粉丝。他看了一系列辛普森剧集,想建立一...

3365
来自专栏大数据挖掘DT机器学习

在数据量不足的情况下,用那种数据挖掘模型效果会更好?

雷天琪 法国电信 机器学习实习生 巴黎综合理工学院(École Polytechnique) 知乎链接:http://www.zhihu.com/ques...

4236
来自专栏大数据文摘

机器学习算法在自动驾驶汽车中扮演怎样的角色

1553
来自专栏新智元

一种端到端可训练周期CNN模型:根据自然语言陈述进行图像分割

【新智元导读】基于自然语言陈述进行语义图像分割是图像分割领域里的一个重要议题。本论文提出了一种端到端可训练周期卷积网络模型,这一模型可同时学习处理视觉与语言信息...

2493
来自专栏人工智能头条

王晓刚:图像识别中的深度学习

3242
来自专栏机器之心

训练深度神经网络失败的罪魁祸首不是梯度消失,而是退化

2415
来自专栏专知

【干货】机器学习基础算法之随机森林

【导读】在当今深度学习如此火热的背景下,其他基础的机器学习算法显得黯然失色,但是我们不得不承认深度学习并不能完全取代其他机器学习算法,诸如随机森林之类的算法凭借...

3517
来自专栏CSDN技术头条

逻辑回归 vs 决策树 vs 支持向量机(II)

本文是该系列的第二篇,第一篇参见: 逻辑回归 Vs 决策树 Vs 支持向量机: Part I. 在这篇文章,我们将讨论如何在逻辑回归、决策树和SVM之间做出最佳...

2076
来自专栏磐创AI技术团队的专栏

一个完整的机器学习项目在Python中演练(四)

1505
来自专栏AI科技评论

学界 | 如何用未标注样本解决单标注样本下的视频行人重识别问题?

本文作者为悉尼科技大学博士生武宇(Yu Wu),他根据 CVPR 2018 录用论文 Exploit the Unknown Gradually: One-Sh...

971

扫码关注云+社区

领取腾讯云代金券