强化学习系列之三:模型无关的策略评价

AlgorithmDog

发布于 2018-01-08 16:07:53

1K0

发布于 2018-01-08 16:07:53

上一章我们介绍了模型相关 (Model-based) 的强化学习。从现在开始我们要介绍模型无关 (Model-free) 的强化学习。

由于模型无关的强化学习比较复杂，今天先介绍其中一部分——模型无关的策略评价。模型无关的策略评价是，不知道马尔科夫决策过程转移概率和奖励函数的情况下，计算一个策略的每一个状态价值。模型无关的策略评价主要有两种算法，一个是蒙特卡罗算法，另一个叫时差学习算法。

1. 蒙特卡罗算法

一听到这个名字，我们就知道一个产生样本，通过样本计算状态价值的方法。首先，用当前策略探索产生一个完整的状态-动作-奖励序列。

(1)

\begin{eqnarray*} s_1,a_1,r_1,....,s_k,a_k,r_k \sim \pi \end{eqnarray*}

然后，在序列第一次碰到或者每次碰到一个状态s时，计算其衰减奖励之后。

(2)

\begin{eqnarray*} g_{s} = r_{t} + \gamma r_{t+1} + ... + \gamma ^{k-t} r_{k} \end{eqnarray*}

最后更新状态价值

(3)

\begin{eqnarray*} S(s) = S(s) + g_{s} \nonumber \\ N(s) = N(s) + 1 \nonumber \\ v(s) = \frac{S(s)}{N(s)} \end{eqnarray*}

蒙特卡罗算法的代码如下所示。

#state_sample, action_sample, reward_sample 分别是状态、动作和奖励系列
def mc(gamma, state_sample, action_sample, reward_sample):   
    vfunc = dict();
    nfunc = dict();
    for s in states:
        vfunc[s] = 0.0
        nfunc[s] = 0.0 

    for iter1 in xrange(len(state_sample)):
        G = 0.0
        for step in xrange(len(state_sample[iter1])-1,-1,-1):
            G *= gamma;
            G += reward_sample[iter1][step];

        for step in xrange(len(state_sample[iter1])):
            s         = state_sample[iter1][step]
            vfunc[s] += G;
            nfunc[s] += 1.0;
            G        -= reward_sample[iter1][step]
            G        /= gamma;


    for s in states:
        if nfunc[s] > 0.000001:
            vfunc[s] /= nfunc[s]

2. 时差学习算法

蒙特卡罗算法能够有效地求解模型无关的策略评估，但也存在一些问题。有时我们面临的强化学习问题是持续不断的。比如没有停止指令时，飞行器控制要求不停地根据姿势风向等因素调整，持续保持平稳飞行。这时我们得不到一个完整状态-动作-奖励系列，因此蒙特卡罗算法不适用。为了解决这个问题，人们提出了时差学习算法 (Temperal Difference, TD)。时差学习算法利用马尔科夫性质，只利用了下一步信息。时差学习算法让系统按照策略指引进行探索，在探索每一步都进行状态价值的更新，更新公式如下所示。

(4)

\begin{eqnarray*} v(s) = v(s) + \alpha (r + \gamma v(s') - v(s)) \end{eqnarray*}

为当前状态，

为下一步状态，

是系统获得的奖励，

是学习率，

是衰减因子。另外

被称为时差目标 (TD target)，

被称为时差误差

。时差学习算法的代码。

#td 算法也可以输入状态-动作-奖励序列。
def td(alpha, gamma, state_sample, action_sample, reward_sample):
    vfunc = dict()
    for s in states:
        vfunc[s] = 0.0           
 
    for iter1 in xrange(len(state_sample)):
        for step in xrange(len(state_sample[iter1])):
            s = state_sample[iter1][step]
            r = reward_sample[iter1][step]
            
            if len(state_sample[iter1]) - 1 > step:
                s1 = state_sample[iter1][step+1]
                next_v = vfunc[s1]
            else:
                next_v = 0.0;

            vfunc[s] += alpha * (r + gamma * next_v - vfunc[s]);

上面的时差学习算法对后续步骤不关心，我们称这种时差学习算法为TD (0)。有时差学习算法关心后续个步骤，我们称之为 TD(

)。这里我们就不详细展开了，有兴趣的同学可以看这里。

3. 一个例子

我们做了一个实验（代码在此）：一个马尔科夫决策过程的状态集 S={1,2,3,4,5,6,7,8}，其中 5、 6 和 8 是终止状态；动作集合 A={‘n’,’e’,’s’,’w’}；不知道奖励函数和转移概率；衰减因子

；另外我们一千个状态-动作-奖励序列，由一个策略探索得到。

1,e,0,2,e,0,3,s,1
1,s,-1
...

我们使用蒙特卡罗算法或者时差学习算法，估算策略下不同状态的价值。经过计算，我们可以得到这个策略下每个状态的价值。

mc result
{1: -0.321, 2: -0.002, 3: 0.306,  4: -0.011, 5: -0.357,}

td result
{1: -0.335, 2: -0.019, 3: 0.316,  4: -0.003, 5: -0.377}

实际上，我们实验使用的马尔科夫随机过程是之前介绍的机器人找金币，策略是随机选择选择一个方向。随机策略下每个状态的价值如下图所示。大体上，蒙特卡罗算法和时差学习算法能够得到状态价值。

4. 总结

我们在上一章介绍模型相关的策略评估的时候，已经介绍过一种策略评估。这种模型相关的策略评估利用了贝尔曼等式，其更新公式如下所示。

(5)

\begin{eqnarray*} v(s) = \sum_{a \in A}\pi(s,a)(R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v_{t}(s')) \nonumber \end{eqnarray*}

根据公式，这种策略评估需要知道转移概率和奖励函数。而蒙特卡罗算法和时差学习算法不知道转移概率和奖励函数。

本文介绍了模型无关的策略评价，指我们不知道马尔科夫决策过程转移概率和奖励函数的情况，计算一个策略的每一个状态价值。模型无关的策略评价主要有两种算法，一个是蒙特卡罗算法，另一个叫时差学习算法。本文代码可以在 Github 上找到，欢迎有兴趣的同学帮我挑挑毛病。强化学习系列的下一篇文章将介绍如何在不知道马尔科夫决策过程的情况下学到最优策略，敬请期待。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016年4月18日，如有侵权请联系 cloudcommunity@tencent.com 删除

人工智能

机器学习

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

人工智能

机器学习

登录后参与评论

0 条评论

热度