RL

种类

• Model-Free RL

  不理解环境，通过试错来学习

• Model-Based RL

  理解环境，通过想象学习

• Policy-Based RL

  基于概率

• Value-Based RL

  基于价值

• Monte-Carlo update

  回合更行

• Temporal Difference update

  单步更新

• On-Policy

  在线学习

• Off-Policy

  离线学习

Q Table

Q Learning

属于Off-Policy

算法伪代码

rl-q-learning

解析

• 初始Q table

• 循环回合

  • 通过e-greedy选择在Q table走一步

    e-greedy: 90%的概率选择Q最大为下一步；10%随机选择下一步

  • 走出下一步：step-current

  • 获取step-current下一步的最大的Q值，更新current的Q值

Q Learning的下一步的选择跟Q值的更新是不一致的，Q值永远获取最大的下一步Q值来更新，而下一步通过e-greedy来选择。

因此Q值的学习永远是最佳的Q值，通过迭代，寻找最佳的路线获得最大的奖励

而通过e-greedy来选择下一步，可以有效的跳出Q值的局部最优点，从而有效的找到全局最优点

Q Learning是一种激进的算法

Sarsa

属于On-Policy

算法伪代码

rl-sarsa

解析

• 初始Q table
• 循环回合
  • 通过e-greedy选择下一步a‘到达状态s'
  • 通过Q(s', a')的值更新当前的Q值
  • 走下一步a'

Sarsa和Q Learning大部分是相同的

唯一的不同是，Q Learning通过下一步最大的Q值来更新当前的Q值；而Sarsa通过e-greedy选择的下一步的Q值来更新当前的Q值。

Sarsa在选择下一步和更新Q值的行为是一致的

而Q Learning在选择下一步和更新Q值的行为是不一致的

Sarsa相对于Q Learning相对保守，因为每次更新Q table并不是获得最佳的Q值

Sarsa Lambda

lambda = 0：为原始的Sarsa算法

lambda = 1：如果当前步骤获得reward，则更新此前所有的步骤的Q值

伪代码

rl-sarsa-lambda

解析

• 初始Q table
• 循环每个回合
  • 初始E
  • 通过e-greedy选择下一步
  • 更新当前到历史的所有步骤的Q值

Sarsa Lambda是Sarsa的升级版本，相对于Sarsa不那么保守，相对于Q Learning不那么激进

Deep Q Network

出现的原因

对于传统的Q Learning，由于Q table的建立，限制了只能描述有穷的状态。而对于一些无穷的状态或者超大规模的状态，则无法使用Q Table来描述。

此时出现了Deep Q Network。通过深度神经网络来生成Q值，从而可以实现可以预测无穷多的Q值的状态。

伪代码

rl-deep-q-network

神经网络

rl-dqn

解析

• 循环每个回合
  • 通过e-greedy选择下一步骤
  • 通过神经网络，计算max Q(s', a')
  • 得到New Q value
  • 把New Q value放入Memory
  • 从Memory随机抽取batch，训练神经网络

Double Deep Q Network

rl-double-Deep-Q-Network

Deep Q Network通过更新单个网络来更新Q table。由于太频繁的更新，导致输出Q值不稳定。

Double Deep Q Network通过构造一新一旧两个一样的神经网络来计算Q值，新的神经网络不断的使用新的Q值来更新；旧的神经网络来生成新的Q值。在一段时间内，旧的神经网络的输出是稳定的。

这样使得模型收敛得更加稳定

Policy Gradients

于Q Learning不同，Policy Gradients通过输出行为的概率，来选择下一步怎么走

rl-Policy-Gradients

优点是除了可以预测离散值，还可以预测连续值

Actor Critic

考虑Policy Gradients

rl-pg-formula

vt一般为通过蒙特卡洛算法得到的reward，这导致reward的值是随机的，方差往往过大，导致难以收敛，通过引入Q Learning，计算Q值，使用Q值代替reward，可以有效得得到收敛。

而Q值的估计可以引入Q Learning来计算

然后Policy Gradients使用Q值，来计算每个动作的概率

这就是Actor Critic

rl-Actor-critic

AC的引入是由于PG由于Vt的方差过大，导致收敛慢；而Q Learning只能输出离散的action，对于连续的action很难处理。

这时候通过组合两个模型，有了Q learning输出稳定的Q值，和PG输出连续的动作值，就可以很好的解决连续动作输出的问题了

Deep Deterministic Policy Gradients

rl-Actor-critic

通过把Q-learning改造成DQN，AC就成了Deep Deterministic Policy Gradients了

Q-learning可以是DQN/DDQN等

Policy Gradients可以是DPG/Double-DPG

A3C

A3C: Asynchronous Advantage Actor-critic

通过神经网络预测Q value时，往往会导致神经网络不稳定，上面的DQN通过回放历史Q值，同步的来解决这个问题。

而A3C通过异步方法来解决神经网络在逼近value不稳定的问题。

AC由于没有采用历史回放的方式，因此导致收敛并不理想。

A3C通过引入历史回放，和多线程并发训练的方式，使得AC收敛得更加稳定

整体架构

rl-a3c

伪代码

rl-a3c-code

解析

• worker于环境交互，得到loss
• worker回传lost和action等参数到global
• global收集数据，并进行反向传播
• global发布新版本到worker

PPO

对于AC，在参数更新上，有可能参数在某一次reward时变化过大，导致此次的行为预测与上一次的行为预测差别很大。

这种波动太大的行为，其实是不好的。

PPO通过设置条件，抑制每次参数更新的限度，从而解决这个问题。

伪代码如下

rl-ppo-code

DPPO

在PPO的基础上加入了分布式。

伪代码如下

rl-dppo