0%

Easy Reinforcement Learning Notes

极简风格

  • Q-learning
  • Sarsa
  • Sarsa(\(\lambda\))
  • DQN
  • Double DQN
  • DQN with Prioritized Experience replay
  • Dueling DQN
  • Policy Gradient

定义

  • agent:智能体,智能体处在某一状态下,依据某种策略(policy),采取一个动作,到达下一个状态
  • s:status,状态
  • a:action,动作
  • r:reward,奖励
  • s,a:可以称之为一步。智能体的行为可以描述为一系列步。强化学习里agent的行为可以用DP(决策过程)表示,s是DP里的节点状态,a是状态之间的转移路径
  • Q:Q表,Q(s,a)即状态s下执行动作a的价值(infer时的可能性),用奖励期望来估计

Q-learning

  • 随机Q表,初始化状态,开始迭代,\(\epsilon\)贪心

  • 在状态s采取动作a,观察到奖励r和状态\(s \prime\)

  • 关键迭代公式:

    \[ Q(s,a) = Q(s,a) + \alpha [r + \gamma max_{a \prime}Q(s \prime,a \prime) - Q(s,a)] \\ \]

  • Q的更新包括两部分,一部分自然是奖励(假如这一步得到奖励的话),另一部分是时间差值,即TD-error,是现实和估计之间的差值。这里的现实是在新状态采取了最好动作后得到的奖励,这里的估计是指我们所有的奖励,除了最终步得到的真实奖励,其余中间步都是用Q表值来估计现实奖励,因此Q表的更新应该是加上(现实-估计),即让Q表更加贴近现实。

  • 值得注意的是,只有最后一步得到奖励时(假如我们只有终点一个奖励),现实才真的是现实的奖励,否则还是用Q表估计的。

  • 这里Q表的更新只与未来的状态和动作有关,在最开始,应该除了真正有奖励的最后一步,其余步骤的更新都是不确定的(因为现实也是用Q表估计的,只有最后一步现实才是现实),但第一次迭代之后最后一步的价值更新是确定的(在宝藏边上还是知道怎么走向宝藏),且与LSTM那种时间序列不同,它不是从最后一个时间步往前BPTT,而是更新了一个状态的转移价值(取哪个动作好),这个状态可能出现在每一次迭代的多个时间步上(或者说和时间步无关),接下来与该状态相邻的状态更新时,用Q表估计的现实就会准确一些,慢慢的整个算法达到收敛。

Sarsa

  • Q-learning是off-policy的,因为存在着现实和估计的差距,我们朝着现实优化,而实际采取的是根据Q表估计的现实,即异步的(off)。

  • Sarsa是on-policy的,与Q-learning在算法上的区别:

    • Q-learning:根据Q表选动作-执行动作观察到奖励和新状态-更新Q表-更新状态
    • Sarsa:执行动作观察到奖励和新状态-更新状态-根据Q表在新状态上选动作,在迭代之前先来一次根据Q表选动作
  • 可以看到Sarsa更改了学习算法的步骤顺序,这种更改带来了什么效果?效果就是将新状态和新动作的选取提前到Q表更新之前,这样Q表更新时,差距里现实的部分不用\(max_{a \prime}Q(s \prime,a \prime)\)来估计,而直接用新状态和新动作:

    \[ Q(s,a) = Q(s,a) + \alpha [r + \gamma Q(s \prime,a \prime) - Q(s,a)] \\ \]

  • 也就是说现实和估计采用的是同一策略(确定的动作,而不是给定状态选最大价值),然后依然使用这个差距来更新。

  • 在更新的过程中,sarsa说到做到(因为现实采用的就是新状态和新动作,agent一定会按照这样更新),而Q-learning则比较乐观(因为现实采用的是新状态下的最大价值,但实际走不一定会采取最大价值的行动,有\(\epsilon\)的扰动)。Sarsa更为保守(每一步都想走好),而Q-learning更为激进(先rush到再说)。

Sarsa(\(\lambda\))

  • naive版本的Sarsa可以看成是Sarsa(0),因为每走一步就更新了Q表,即\(Q(s \prime,a \prime)\)只会带来上一步\(Q(s,a)\)的价值更新。假如我们考虑对所有步的更新,且离最终奖励近的步权重大,离最终奖励远的步权重小,那么调整这个权重的超参就是\(\lambda\),权重为0就是不考虑之前的步数,即naive Sarsa。

  • 具体实现是添加一个trace矩阵E(矩阵中每一个元素对应一步(s,a))保存所有步在该次路径中的权重,离最终奖励越近,权重越大,因此每走一步,执行的那一步元素对应矩阵值加1,然后用对应的trace矩阵值作为权重乘到奖励上来更新Q表(这里是所有的步和整个E矩阵乘起来),之后矩阵值会衰减一下,乘以更新衰减因子\(\gamma\)和权重超参\(\lambda\)。显然\(\gamma\)为1时,就是所有的状态得到了一样的更新(因为是所有步和整个E矩阵相乘);当\(\gamma\)为0时,除了执行步元素加了1,然后整个E矩阵都置0,因此只有执行步得到了更新,即naive Sarsa。将E矩阵的迭代展开,就可以得到与naive sarsa一样的展开,只不过衰减的时候加了一个E(s,a)来记录某一步距离奖励的距离。

    \[ \delta = r + \gamma Q(s \prime,a \prime) - Q(s,a) \\ E(s,a) = E(s,a) + 1 \\ Q = Q + \alpha \delta E \\ E = \gamma \lambda E \\ update \ \ s,a \\ \]

  • 这个E矩阵就是eligibility trace。对于某一步,如果被执行了,就增加一点值,之后慢慢衰减,直到又被执行。假如短期内被执行多次,就会上升到过高值,这时可以设置阈值来限制eligibility的增加。这个值可以解释为该步在该次迭代中对于找到最终奖励的贡献程度。

DQN

  • Q-learning + deep neural network
  • 神经网络用于把Q-table的更新过程参数化,输入一个状态向量,神经网络输出所有动作的价值,用神经网络的训练来替代简单的迭代更新。这样可以解决状态数过多导致的维度灾难问题。
  • 直接这么替换不容易训练,DQN引入两个技巧
    • experience replay
    • fix q
  • 先看神经网络的输入输出和损失
    • 有两个神经网络,一个网络参与训练(评价网络),一个网络只复制另一个网络训练得到的参数,用来生成ground truth,即目标网络
    • 参与训练的网络输入是状态,表示为s维特征向量,输出是各个动作获得的a维价值向量,损失是这个向量和ground truth的a维向量之间的均方误差。
  • DQN还包含一个记忆矩阵,维度是[记忆条数,$ 2 * s + 2$ ],每一条包含奖励、动作,老状态和新状态,即一步的所有信息。记忆只保存最近记忆条数次执行步。
  • 之后神经网络的输入输出从哪里来?其实是从记忆中采样一个Batch的数据,将老状态输入评价网络得到model output,将新状态输入目标网络得到ground truth,之后计算损失。
  • 每隔一段时间目标网络才会复制评价网络,在此期间目标网络都是固定不变的,即fix q
  • 而输入是从最近的记忆当中抽取的,即experience replay
  • 值得注意的是我们并不直接把评价网络输出价值向量用于计算损失,因为还没有采取动作。因此我们要先根据网络输出的价值向量采取动作,将价值向量里这些动作对应的价值用奖励更新,之后这个更新过的价值向量再参与损失计算。

Double DQN

  • Double DQN解决DQN over estimate的问题
  • 与DQN不同之处在于,评价网络不仅接受老状态产生一个输出\(q_{eval}\),还接受新状态产生一个输出\(q_{eval4next}\),之后依据\(q_{eval4next}\)选取动作更新\(q_{eval}\),而不是根据\(q_{eval}\)本身选取动作来更新。

DQN with Prioritized Experience replay

  • 之前是从记忆库中随机采样一段记忆,这个随机采样会导致模型训练步数过多(随机很难保证到达最终奖励)
  • 那么自然而然想到记忆应该分配优先级,优先级高的采样概率大
  • 优先级可以用TD-error值来衡量,error大的自然要多采样多优化
  • 已知优先级分布,希望得到满足该优先级分布的一个采样序列,那么这就是一个蒙特卡洛问题了,可以用MCMC,可以用Importance sampling,也可以用论文里提到的SumTree

Dueling DQN

  • Dueling DQN细化了原始DQN的内部网络输入输出关系:

    \[ Q(s,a;\theta,\alpha,\beta) = Value(s;\theta,\beta) + Advantage(s,a;\theta,\alpha) \]

  • 即拆分成了状态带来的价值和动作在该状态上带来的价值(advantage)

  • 为什么要单独考虑状态?因为有些状态是与动作无关的,无论采取什么动作都不会带来价值的改变

Policy Gradient

  • 之前介绍的都是基于值的强化学习方法,即在某状态查询各个动作带来的价值,选择最大价值动作执行

  • policy gradient(策略梯度)通过策略网络输入状态,直接输出动作,跳过了计算价值的步骤,是基于策略的方法

  • 策略网络并不计算某种损失进行反向传播,而是依据奖励来反向传播,更新的算法如下:

    \[ \theta = \theta + \alpha \nabla _{\theta} \log \pi _{\theta} (s_t, a_t) v_t \\ \]

  • 需要注意以下几个关键点:

    • 这里的PG算法神经网络只负责接收状态作为输入,奖励作为梯度调整值,实际执行的动作作为gold label,输出一个action vector,整个网络本身就是一个策略\(\pi\)(输入状态,输出动作概率分布)
    • 之后整个模型依然像DQN那样,借助策略(网络)按动作概率(网络输出)选择动作,转移状态,观察环境得到奖励
    • 那么第一个问题,这个策略梯度是怎么来的?可以看到梯度依然是损失对参数求导的形式,\(- \nabla _{\theta} \log \pi _{\theta} (s_t, a_t) v_t\),哪来的损失?实际上是执行动作的概率乘以奖励,可以看作是动作概率分布和执行动作one-hot向量之间的交叉熵(交叉熵本来就有类似look up的效果)乘以奖励。我们就看其本来的含义:执行动作的概率乘以奖励,网络本身只是一个策略,什么样的策略是好策略?假如通过这个策略选出来的动作执行之后得到了好的奖励,那么这是一个好的策略网络,也就是能选出好动作的策略网络是好网络,显然网络的目标函数就应该是执行动作的概率(网络认可的动作)乘以奖励(奖励认可的好动作)。
    • 第二个问题,对于随时能给出奖励的环境,agent可以走一步,根据奖励更新一次策略网络,那对于那些只有最后一步能够得到奖励的该咋办?事实上我们采取的是回合更新,无论是每一步都能给出奖励的环境还是只有最后一步有奖励的环境,我们都将一个回合内的所有步(s,a,r)都记录下来(除了最后一步,其余步的奖励都是0或者-1),之后每一步的奖励替换成累加奖励,并乘以一个衰减系数使得奖励随episode steps衰减。注意不同于离散的基于值的学习,基于策略的PG在没有得到奖励的那些步也能算出一个动作概率来计算损失,因此即便是无奖励(或者负奖励),也能使得策略网络优化去让不好的动作概率降低。

Actor Critic

  • 显然基于策略的方法抛弃了值,获得了优势(连续动作),也带来了劣势(每执行一步之后没得值可以用来估计即时奖励,只能进行回合更新),那么一个自然而然的想法就是结合这两点,选择一个基于策略的网络作为actor,训练出策略;选择一个基于值的网络作为critic,用来给策略网络提供值,估计即时奖励。