Ray Zhang:对Sutton和Barton《强化学习导论》第六章《时序差分学习》的读书笔记

原文地址: https://oneraynyday.github.io/ml/2018/09/30/Reinforcement-Learning-TD/

之前,“机器之心”翻译过他对蒙特卡洛方法做的笔记:

https://zhuanlan.zhihu.com/p/37926601

  • 回顾
  • 蒙特卡洛方法
  • 时序差分预测
  • 时序差分学习与动态规划的相似性
  • 时序差分学习与蒙特卡洛方法的相似性
  • TD(0)的优化特性
  • 在轨策略(on-policy)方法:Sarsa算法
  • 离轨策略(off-policy)方法:Q-学习算法
  • 案例:悬崖行走
  • Sarsa模型
  • Q-学习模型
  • 悬崖行走的地图
  • 学习曲线

时序差分学习是强化学习里最中心的概念之一。它是之前讨论的蒙特卡洛方法与动态规划的结合体。在蒙特卡洛方法中,我们有一个在给定策略π获取期望奖励V的更新法则。通常,我们会对每一幕(episode)进行仿真并得到总的奖励,然后将动作序列里每个动作对应到奖赏的值。回想下我们在蒙特卡洛仿真里的不同方法——“每次访问”与“首次访问”。我们有状态序列 Sj=(s0,s1,…)和动作序列Aj=(a0,a1,…),每一幕(episode)索引记为 j,首次蒙特卡洛方法执行如下的算法:

任意奖励

可以看作经过时间t在episode为i时候的折扣奖励。换句话说,如果一个状态在整个一集中发生一次、两次或五十次,我们只计算第一次发生的状态。以及所有奖励值的平均值得到

对每次蒙特卡洛方法,我们有:

其中#s是我们在所有剧集中看到状态的总次数。换句话说,如果一个状态不止一次发生,我们将把这些发生加到我们的近似值中,并对所有要得到的奖励值取平均得到


在许多情况下,V(S)是平稳的,两种方法(首次访问和每次访问)都将收敛到最优解。然而,在非平稳环境中,我们不希望我们的“更新幅度”接近0。下面是一个适用于非平稳情况下的每次访问蒙特卡洛方法(比如0)的法则:

常数α>0。时序差分学习在上式中,我们使用变量Gt作为时间t之后的幕(episode)的剩余奖励,它可能是由折扣系数γ所决定的。它只有在一幕结束的时候能得知。对于时序差分学习来说,这一切不再需要了。时序差分学习方法是如何做到这一点的?他们只需要向前看一步,因为他们的近似是稍微不精确和较少的样本基础。他们没有使用Gt,而是使用:

回想求Gt的式子:

然后,我们对V(St)求期望:

可以“逼近”剩下的轨迹:

是的,它不那么精确,但作为回报,我们可以在中间幕的episode进行学习。得出的V(St)在eq(0)模拟中的更新方程是:

在这种情况下,由于我们只向前看一步,所以称为TD(0)。下面是一些伪代码逻辑:

pi = init_pi()
V = init_V()
for i in range(NUM_ITER):
    s = init_state()
    episode = init_episode(s)
    while episode:
        prev_s = s
        action = get_action(pi, V)
        reward, s = episode.run(action)
        V(prev_s) += alpha * (reward + gamma * V(s) - V(prev_s))

TD(0)被认为是一种自助(bootstrap)方法,因为它使用以前的近似,而不是完全使用整个轨迹的回报。

时序差分学习与动态规划的相似性

回顾一下,我们使用Bellman方程操作符来解决强化学习问题的动态规划方法。这允许对V(S)进行有效的增量计算,我们先前证明了:

这样,我们就可以有效地得到越来越多的v的精确逼近。类似的性质,我们在上面方程中的V(St)的逼近也是迭代的,并且由于V(St)作为一个函数是未知的,所以我们从先前的估计中进行自助抽样(bootstrap)。

时序差分学习与蒙特卡洛方法的相似性

回想一下,蒙特卡洛方法要求我们估计期望值,因为我们采集了一些episode里的样本,并试图从对每一个动作中近似中求出潜在的期望值。这样,时序差分学习就像每次访问蒙特卡洛方法,因为它的V(St)近似于Gt的期望值。由于不知道期望,时序差分学习和蒙特卡洛方法都通过抽样近似V(St)。然而,蒙特卡洛方法并没有尝试在其收敛过程中使用以前的V估计,而是采用完整的样本轨迹进行估计。

TD(0)优化特性:人们可能期望TD(0)收敛到与蒙特卡洛方法相同的值。然而,事实并非如此。Sutton列举的病理例子非常清楚地解释了这一点:

在这个案例里,我们有6个episode里B的奖励为1,有2个episode奖励为0,最后V(B)=34。对于A,我们可以提出两个“合理”的建议:1. 如果A事件发生,得到的累积奖励为G。因此,V(A)=0。2. 如果A事件发生,下一个状态始终为B。因此,有:

由于唯一的下一个状态是B,而我们现在的奖励是从我们所拥有的单个样本中得到的,结果应该是0+γV(B)=3γ/4≠0。从马尔可夫的假设来看,这是有意义的,因为St⊥Rt+2是相互正交的,所以A发生在B之前的事实不应该使B产生零奖励。从某种意义上说,蒙特卡洛方法最小化了值函数近似的均方误差,时序差分学习算法则收敛于确定的等效估计上。确定等效估计是在假定过程为马尔科夫决策过程的前提下,对值函数做最大似然估计。

在轨策略算法:SARSA

在在轨策略里,我们不学习v(s),我们学习动作价值函数 q(s,a)。 这个式子比较直白:

求解v(s)的做法:

我们之所以称这个算法为sarsa,是因为它是一个经典的状态-动作-奖励-状态-动作强化学习算法,我们估计了一些π的Qπ.此π是根据当前状态输出动作概率的策略。 通常来说,在轨策略学习算法可能无法充分探索搜索空间,导致一个次优答案,或者永远停留在其当前策略中而无法终止。因此,我们通常使用ϵ-贪婪来寻找策略π,以一个较小的概率ϵ选择所有其他操作。

轨策略算法:Q-学习

时序差分学习算法的离轨策略形式叫做Q-学习,他的更新法则为:

之前,我们用:

来逼近

是用ϵ-贪婪算法求解的。现在,为了获得真实的最优值,需要得到:

ϵ-贪婪算法的选择方法就是离轨时序差分学习,而在轨策略利用argmax逼近真实的Q。悬崖行走我们可以再去看一下“悬崖行走”的例子,之前我们是在gym用蒙特卡洛方法去计算的。就像之前看到的,图上的收敛路径是这样的:

这是一种在轨策略的蒙特卡洛方法。路径如此保守、而演员一直移动到边缘的原因是由于演员有ε的概率向一个随机的方向移动,这会让他掉下悬崖摔死。即使ε接近0,策略也不是最优的,而只是安全的。现在,我在同一个蒙特卡洛方法上添加了TD功能,并重构了大部分核心功能。我们直接将上面的更新规则转换为UPDATE_Q()函数,然后传入元组(状态、动作、奖励、状态、动作),而不是一集,即[(状态,动作,奖励),…]

SARSA模型

SARSA模型的更新法则:

class FiniteSarsaModel(FiniteModel):
    def __init__(self, state_space, action_space, gamma=1.0, epsilon=0.1, alpha=0.01):
        """SarsaModel takes in state_space and action_space (finite)
        Arguments
        ---------

        state_space: int OR list[observation], where observation is any hashable type from env's obs.
        action_space: int OR list[action], where action is any hashable type from env's actions.
        gamma: float, discounting factor.
        epsilon: float, epsilon-greedy parameter.

        If the parameter is an int, then we generate a list, and otherwise we generate a dictionary.
        >>> m = FiniteSarsaModel(2,3,epsilon=0)
        >>> m.Q
        [[0, 0, 0], [0, 0, 0]]
        >>> m.Q[0][1] = 1
        >>> m.Q
        [[0, 1, 0], [0, 0, 0]]
        >>> m.pi(1, 0)
        1
        >>> m.pi(1, 1)
        0
        """
        super(FiniteSarsaModel, self).__init__(state_space, action_space, gamma, epsilon)
        self.alpha = alpha


    def update_Q(self, sarsa):
        """Performs a TD(0) action-value update using a single step.
        Arguments
        ---------

        sarsa: (state, action, reward, state, action), an event in an episode.
        """
        # Generate returns, return ratio
        p_state, p_action, reward, n_state, n_action = sarsa
        q = self.Q[p_state][p_action]
        self.Q[p_state][p_action] = q + self.alpha * \
            (reward + self.gamma * self.Q[n_state][n_action] - q)


    def score(self, env, policy, n_samples=1000):
        """Evaluates a specific policy with regards to the env.
        Arguments
        ---------

        env: an openai gym env, or anything that follows the api.
        policy: a function, could be self.pi, self.b, etc.
        """
        rewards = []
        for _ in range(n_samples):
            observation = env.reset()
            cum_rewards = 0
            while True:
                action = self.choose_action(policy, observation)
                observation, reward, done, _ = env.step(action)
                cum_rewards += reward
                if done:
                    rewards.append(cum_rewards)
                    break
        return np.mean(rewards)


Q学习模型

Q学习模型更新法则:

Python代码:

class FiniteQLearningModel(FiniteModel):
    def __init__(self, state_space, action_space, gamma=1.0, epsilon=0.1, alpha=0.01):
        """FiniteQLearningModel takes in state_space and action_space (finite)
        Arguments
        ---------

        state_space: int OR list[observation], where observation is any hashable type from env's obs.
        action_space: int OR list[action], where action is any hashable type from env's actions.
        gamma: float, discounting factor.
        epsilon: float, epsilon-greedy parameter.

        If the parameter is an int, then we generate a list, and otherwise we generate a dictionary.
        >>> m = FiniteQLearningModel(2,3,epsilon=0)
        >>> m.Q
        [[0, 0, 0], [0, 0, 0]]
        >>> m.Q[0][1] = 1
        >>> m.Q
        [[0, 1, 0], [0, 0, 0]]
        >>> m.pi(1, 0)
        1
        >>> m.pi(1, 1)
        0
        """
        super(FiniteQLearningModel, self).__init__(state_space, action_space, gamma, epsilon)
        self.alpha = alpha


    def update_Q(self, sars):
        """Performs a TD(0) action-value update using a single step.
        Arguments
        ---------

        sars: (state, action, reward, state, action) or (state, action, reward, state),
            an event in an episode.

        NOTE: For Q-Learning, we don't actually use the next action, since we argmax.
        """
        # Generate returns, return ratio
        if len(sars) > 4:
            sars = sars[:4]

        p_state, p_action, reward, n_state = sars
        q = self.Q[p_state][p_action]
        max_q = max(self.Q[n_state].values()) if isinstance(self.Q[n_state], dict) else max(self.Q[n_state])
        self.Q[p_state][p_action] = q + self.alpha * \
            (reward + self.gamma * max_q - q)


    def score(self, env, policy, n_samples=1000):
        """Evaluates a specific policy with regards to the env.
        Arguments
        ---------

        env: an openai gym env, or anything that follows the api.
        policy: a function, could be self.pi, self.b, etc.
        """
        rewards = []
        for _ in range(n_samples):
            observation = env.reset()
            cum_rewards = 0
            while True:
                action = self.choose_action(policy, observation)
                observation, reward, done, _ = env.step(action)
                cum_rewards += reward
                if done:
                    rewards.append(cum_rewards)
                    break
        return np.mean(rewards)


if __name__ == "__main__":
    import doctest
    doctest.testmod()

SARSA方法得到的悬崖地图

正如我们所看到的,它类似于蒙特卡洛方法的地图。这个动作是保守的,因为它不假定过程具有任何马尔可夫特性。蒙特卡洛方法的过程是积极意识到环境中的随机性,并试图移动到最安全的角落,然后再向右,最终走向终点。

Q学习的地图

这是一个与SARSA方法和蒙特卡洛方法非常不同的地图。Q-学习基于潜在的马尔可夫假设,因而忽略了选择其行动时的随机性,这也是它选择最优路径的原因(它理解马尔可夫假设,并因此选择了贪婪的行为,在强马尔可夫的MDP下,这是最优的)。离轨策略的方法允许Q学习有一个最优的策略,而它的ϵ贪婪的模拟允许它探索。笔者(Ray Zhang)认为Q学习更有优势。

学习曲线

我们同时运行这三种模式,并记录随着幕数的增加而增加的总回报。*_interp是日志奖励的移动平均值。看来,SARSA虽然产生了与蒙特卡洛方法大致相同的解决方案(回想起来它并不准确),但收敛到更高的回报的速度要快得多。这是因为它的价值功能能够按步骤而不是每集更新。这种引导方法允许模型比蒙特卡洛方法学习得快得多。

我们可以观察到的另一个现象是,Q学习的平均回报是不好的。这是因为Q-学习试图采取最优的行动,但会被搅乱,由于它用来进行探索的贪婪策略的随机性,它会以ϵ的概率从悬崖上掉下来。

在上面的图表中观察到的另一个有趣的现象是,蒙特卡洛方法实际上在接近结束时开始降低性能。这个…Ray Zhang没有解释(但Ray Zhang又很想讨论它)!)。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s