强化学习要点简介与常见方法对比



  • Reinforcement Learning Basic

    定义

    强化学习涉及一个智能体,一组“状态”S和每个状态下的动作集合A。通过执行一个行动 ,该智能体从一个状态转移到另一个状态。在一个特定的状态下执行一个动作时,智能体还可以得到一个奖励。
    智能体的目标是最大化其奖励的累加。这个潜在的奖励是所有未来可以拿到的奖励值的期望的加权和。
    例如,假设现在你要上地铁,奖励就是你所花的时间的相反数。一种策略就是车门一开就往上挤,但是还有很多人要下车,逆着人流往上挤也会花费不少时间,这个时候你花的总时间可能是:

    • 0秒钟等待时间+15秒挤上去的时间
      在接下来的一天,很巧合,你决定先让别人下车。虽然这个时候看起来等待的时间稍微增加了,但是下车的人也会下的更顺畅,这个时候你可能花的时间是:
    • 5秒等待时间+0秒挤上去的时间。

    理解

    状态State动作Action存在映射关系,也就是一个state可以对应一个action,或者对应不同动作的概率(常常用概率来表示,概率最高的就是最值得执行的动作)。状态与动作的关系其实就是输入与输出的关系,而状态State到动作Action的过程就称之为一个**策略Policy,**一般用π表示,也就是需要找到以下关系(其中a是action,s是state):

    一一对应表示:a=π(s)

    概率表示:π(a|s)

    Off-Policy & On-Policy

    On-Policy 与 Off-Policy的本质区别在于:更新Q值时所使用的方法是沿用既定的策略(on-policy)还是使用新策略(off-policy)。

    Sarsa更新Q值的时候对下一步的估计采用的是Q本身的$Q(S’,A’)$,而Q-Learning更新的时候对下一步的估计部分则采用的是直接取采取动作a后环境中各个a’对应的Q的最大值,即其在选择Action的时候使用的是e-greedy算法,而更新Q值的时候则采用了直接取最大值的greedy算法。

    反映到结果上

    On-policy:必须本人在场, 并且一定是本人边玩边学习。
    Off-policy:可以选择自己玩, 也可以选择看着别人玩, 通过看别人玩来学习别人的行为准则。

    基本方法对比

    Method name Net Classes Num Net Num Net types Input Output Update method Use Memory Policy
    Q-L 0 0 None state values of actions round update F OFF
    SARSA 0 0 None state value of actions round update F ON
    DQN 1 2 target net & Eval net state values of actions round update T OFF
    PG 1 1 policy net state prob of actions round update T ON
    AC 2 2 actor net & critic net state prob of actions & rewards step update F ON
    DDPG 2 4 (actor & critic)x(target & eval) state & (state, action) continuous action value & reward step update T OFF

    规律与注解

    • 只定义了一个网络类的方法都是回合制更新
    • 除了DDPG其他方法的输入都是state
    • 回合制更新也叫蒙特卡洛更新(Monte-carlo update),单步更新也叫当时差距更新(Temporal-difference update

    Bellman equation

    简介

    贝尔曼方程(Bellman Equation)”也被称作“动态规划方程(Dynamic Programming Equation)”,由理查·贝尔曼(Richard Bellman)发现。贝尔曼方程是动态规划(Dynamic Programming)这种数学最佳化方法能够达到最佳化必要条件。此方程将“决策问题在特定时间点的值”以“来自初始选择的报酬 及 由初始选择衍生的决策问题的值”的形式表示。藉这个方式将动态最佳化问题变成较简单的子问题,而这些子问题遵守由贝尔曼所提出的“最佳化原理”。

    贝尔曼方程最早应用在工程领域的控制理论及其他应用数学领域,而后成为经济学上的重要工具。

    几乎所有可以用最佳控制理论(Optimal Control Theory)解决的问题也可以透过分析合适的贝尔曼方程得到解决。然而,“贝尔曼方程”通常指离散时间(discrete-time)最佳化问题的动态规划方程。处理连续时间(continuous-time)最佳化问题上,也有类似的偏微分方程,称作汉弥尔顿-雅各比-贝尔曼方程(Hamilton–Jacobi–Bellman Equation, HJB Equation)。

    理解

    首先我们从value function的角度进行理解,value function可以分为两部分:

    • 立即回报 Rt+1R_{t+1}
    • 后继状态的折扣价值函数 γv(St+1)\gamma v(S_{t+1})

    贝尔曼方程的推导

    :一个动作的价值函数=当前取得的回报+走这一步对后面所有的后继步骤获得的后续回报的一个折算

    Model-free Method & Model-based Method Reinforcement Learning

    简单的说,即你在知道当前state和action的时候能不能再不真正take action的情况下得知下一个state以及reward。换句话说,即你的方法能不能对环境进行建模,或是其对环境有理解还是只是把环境当做一个黑盒。

    可以参见Quora问题:Quora

    Q-Learning

    定义

    Q-学习是强化学习的一种方法。Q-学习就是要学习的政策,告诉智能体什么情况下采取什么行动。Q-learning不需要对环境进行建模,即使是对带有随机因素的转移函数或者奖励函数也不需要进行特别的改动就可以进行。
    对于任何有限的马可夫决策过程(FMDP),Q-learning可以找到一个可以最大化所有步骤的奖励期望的策略。[1],在给定一个部分随机的策略和无限的探索时间,Q-learning可以给出一个最佳的动作选择策略。“Q”这个字母在强化学习中表示一个动作的质量(quality )。[2]
    Q-Learning 最简单的实现方式就是将值存储在一个表格中,但是这种方式受限于状态和动作空间的数目。

    输入:状态(State)
    输出:该状态下可能采取的各种动作(Action)时对应的Q值

    算法

    SARSA

    SARSA非常像Q-learning。SARSA和Q-learning的关键区别在于SARSA是一种on-policy算法。这意味着SARSA是根据当前策略执行的动作而不是贪婪策略来学习q值的。

    输入:状态(State)
    输出:该状态下可能采取的各种动作(Action)时对应的Q值

    算法

    DQN

    输入(1):状态(State)

    输出(1):该状态下可能采取的各种动作(Action)时对应的Q值

    输入(2):状态(State)和动作(Action)

    输出(2):该状态下采取该动作(Action)时对应的Q值

    目标:找到一个最优的策略Policy从而使Reward最多

    Loss$$L(w)=E[(r+\gamma max_{a’}Q(s’,a’,w)-Q(s,a,w))^2]$$

    特点

    1. 不是直接输出当前状态下各动作的概率,每种动作都可能以其对应概率被选到,而是输出当前状态下选择各动作后带来的Q值,直接选择最大的,并随机以一定的可能性选择其他动作。
    2. 是一种 off-policy 离线学习法,它能学习当前经历着的, 也能学习过去经历过的, 甚至是学习别人的经历。

    类比:Q表。这里的神经网络的功能就好比一个Q表,输入要查找的内容,输出相应值。

    原理图

    算法

    更新算法

    DQN的理解

    网络更新方法

    为何使用两个网络?

    The second modification to online Q-learning aimed at further improving the stability of our method with neural networks is to use a separate network for gen- erating the targets yj in the Q-learning update. More precisely, every C updates we clone the network Q to obtain a target network Q^ and use Q^ for generating the Q-learning targets yj for the following C updates to Q. This modification makes the algorithm more stable compared to standard online Q-learning, where an update that increases Q(st,at) often also increases Q(st 1 1,a) for all a and hence also increases the target yj, possibly leading to oscillations or divergence of the policy. Generating the targets using an older set of parameters adds a delay between the time an update to Q is made and the time the update affects the targets yj, making divergence or oscillations much more unlikely.

    简单地说,每隔一段时间copy一次Eval Net成为Target Net减小了每次更新带来的震动,即使得对Q(st,a)Q(s_t,a)做出的更新不会马上影响到Q(st+1,a)Q(s_{t+1},a)

    工程实现关键点

    1. DQN网络的更新方法:同时初始化两个定义相同的网络,一个是Target Net,一个是Eval Net。前者是作为Q值的目标值出现的一个网络,且其的更新较为落后,往往是Eval Net更新千百轮之后才把后者的参数完全拷贝一份到自身;而后者则是每次学习过程必更新,总是最新的网络参数,用作估计值。
    2. 有一个记忆库用来储存之前的记忆,每次训练时随机抽一个batch扔到网络里训练。
    3. Fixed Q-targets和记忆库都是打乱经历相关性的机理,也使得神经网络更新更有效率。
    4. 刚初始化后的前面n轮是不用网络而完全随机预测的,并把结果存下来训练网络。

    Policy Gradient

    输入: 状态(State)

    输出:直接是动作(Action)(而非Q值)

    公式:a=π(s, θ) 或 a=π(a|s, θ)

    特点:输出的直接是当前状态下采取各种可能动作的概率。每种动作都可能以其对应概率被选到。另外其相对于基于值的算法如DQN而言可以handle较多action,尤其是连续action空间的问题。

    Lossloss=log(prob(action))rewardloss=-log(prob(action))*reward

    Actor Critic

    定义

    结合了 Policy Gradient (Actor) 和 Function Approximation (Critic) 的方法. Actor基于概率选行为, Critic 基于 Actor 的行为评判行为的得分, Actor 根据 Critic 的评分修改选行为的概率。简单说,相对于单纯的Policy Gradient,其不再使用回合制更新网络,而是逐步更新网络。而每一步的reward则是由critic网络给出。

    优势

    可以进行单步更新, 比传统的 Policy Gradient 要快。

    劣势

    取决于 Critic 的价值判断, 但是 Critic 难收敛, 再加上 Actor 的更新, 就更难收敛. 为了解决收敛问题。

    Actor Net

    输入:状态(State)
    输出:动作(Action)

    Critic Net

    输入:状态(State)
    输出:评价(Reward)

    Loss:

    $$
    Loss(policy/actor)=-log\space prob * (reward-critic\space value)\
    Loss(critic)=E[(reward-critic\space value)^2]
    $$

    DDPG

    定义

    输入: 状态(State)

    输出:直接是动作(Action)(而非Q值)

    公式:a=π(s, θ) 或 a=π(a|s, θ)

    特点:输出的直接是当前状态下采取各种可能动作的概率。每种动作都可能以其对应概率被选到。

    应用场景:连续行为场景

    由来

    在RL领域,DDPG主要从:PG -> DPG -> DDPG 发展而来。
    Deepmind在2016年提出DDPG,全称是:Deep Deterministic Policy Gradient,是将深度学习神经网络融合进DPG的策略学习方法。
    相对于DPG的核心改进是: 采用卷积神经网络作为策略函数μ和Q函数的模拟,即策略网络和Q网络;然后使用深度学习的方法来训练上述神经网络。
    Q函数的实现和训练方法,采用了Deepmind 2015年发表的DQN方法。

    原理图

    算法

    祝进步。


 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开,我们正在尝试重连,请耐心等待