深度强化学习-玩游戏

2018-05-05 本文已影响5人初七123

RL

强化学习问题的定义

<A, S, R, P>
Action space : A  动作空间
State space : S 状态空间
Reward: R : S × A × S → R 奖赏
Transition : P :S × A → S  转移概率

贝尔曼等式
这个公式定义了 Reward 的计算

时间差分
计算N步的 Reward 值误差作为损失函数

DQN

在普通的Q-learning中，当状态和动作空间是离散且维数不高时可使用Q-Table储存每个状态动作对的Q值，而当状态和动作空间是高维连续时，使用Q-Table不现实。

通常做法是把Q-Table的更新问题变成一个函数拟合问题，相近的状态得到相近的输出动作。如下式，通过更新参数 θ 使Q函数逼近最优Q值

DRL是将深度学习（DL）与强化学习（RL）结合，直接从高维原始数据学习控制策略。而DQN是DRL的其中一种算法，它要做的就是将卷积神经网络（CNN）和Q-Learning结合起来，CNN的输入是原始图像数据（作为状态State），输出则是每个动作Action对应的价值评估Value Function（Q值）。

网络结构
输入是游戏画面
输出是一个每个动作对应的Q值

损失函数
1-stage 时间差分得到损失

经验回放
经验池的功能主要是解决相关性及非静态分布问题。具体做法是把每个时间步agent与环境交互得到的转移样本 (s(t),a(t),r(t),s(t+1)) 储存到回放记忆单元，要训练时就随机拿出一些（minibatch）来训练。为了解决：
（1）深度神经网络作为有监督学习模型，要求数据满足独立同分布
（2）但 Q Learning 算法得到的样本前后是有关系的。为了打破数据之间的关联性，Experience Replay 方法通过存储-采样的方法将这个关联性打破了。）

目标网络
原始的Q-learning中，在1-step TD return，样本标签y使用的是和训练的Q-network相同的网络。这样通常情况下，能够使得Q大的样本，y也会大，这样模型震荡和发散可能性变大。而构建一个独立的慢于当前Q-Network的target Q-Network来计算y，使得训练震荡发散可能性降低，更加稳定

伪代码

Double-DQN

Thrun 和 Schwartz 在古老的 1993 年观察到 Q-Learning 的过优化 (overoptimism) 现象，并且指出过优化现象是由于 Q-Learning 算法中的 max 操作造成的。

max操作使得估计的值函数比值函数的真实值大。如果值函数每一点的值都被过估计了相同的幅度，即过估计量是均匀的，那么由于最优策略是贪婪策略，即找到最大的值函数所对应的动作，这时候最优策略是保持不变的。也就是说，在这种情况下，即使值函数被过估计了，也不影响最优的策略。强化学习的目标是找到最优的策略，而不是要得到值函数，所以这时候就算是值函数被过估计了，最终也不影响我们解决问题。然而，在实际情况中，过估计量并非是均匀的，因此值函数的过估计会影响最终的策略决策，从而导致最终的策略并非最优，而只是次优

Hasselt 等进一步分析了过优化的现象，并将 Double Q 的想法应用在 DQN 上，从而提出了 Double DQN。Double DQN 训练两个 Q 网络，一个负责选择动作，另一个负责计算。两个 Q 网络交替进行更新，具体算法如下所示。

Prioritized Replay

DQN 用了 Experience Replay 算法，将系统探索环境获得的样本保存起来，然后从中采样出样本以更新模型参数。对于采样，一个常见的改进是改变采样的概率。Prioritized Replay [3] 便是采取了这个策略，采用 TD-err 作为评判标准进行采样。

Duel-DQN

在网络内部把Q(s,a) 分解成 V(s) + A(s, a)，V(s)与动作无关，A(s, a)与动作相关，是a相对s平均回报的相对好坏，是优势，解决reward-bias问题。RL中真正关心的还是策略的好坏，更关系的是优势，另外在某些情况下，任何策略都不影响回报，显然需要剔除。
Dueling Network网络架构如下，Dueling Network把网络分成一个输出标量V(s)另一个输出动作上Advantage值两部分，最后合成Q值。非常巧妙的设计，当然还是end-to-end的，效果也是state-of-art。Advantage是一个比较有意思的问题，A3C中有一个A就是Advantage

DDPG

DQN虽然在Atari游戏问题中取得了巨大的成功，但适用范围还是在低维、离散动作空间。DQN是求每个action的Q(s, a)，在连续空间就不适用了，原因如下：
如果采用把连续动作空间离散化，动作空间则会过大，极难收敛。比如连续动作空间=10，每个动作划分成3个离散动作3^10，动作空间将扩大到。而且每个动作空间划分成3个离散动作无法做到fine-tuning，划分本身也带来了信息损失。

Policy Gradient直的策略网络直接输出的就是策略，比如采取每一种行动的概率（对于离散控制问题），或者每一个动作的值（对于连续控制问题）。

DPG
随机性策略和确定性策略介绍
https://zhuanlan.zhihu.com/p/26441204
DPG一文中提供了随机性/确定性策略梯度的公式证明

actor-critic
actor-critic算法是一种TD method。结合了value-based和policy-based方法。policy网络是actor（行动者），输出动作（action-selection）。value网络是critic（评价者），用来评价actor网络所选动作的好坏（action value estimated），并生成TD_error信号同时指导actor网络critic网络的更新。下图为actor-critic算法的一个架构图，DDPG就是这一类算法。

DDPG基于AC算法用DNN来拟合策略函数和值函数

Noise sample
连续动作空间的RL学习的一个困难时action的探索。DDPG中通过在action基础上增加Noise方式解决这个问题。

伪代码

Asynchronous Advantage Actor-Critic

asynchronous
异步，对应的异步分布式RL框架。相对应的是15年google的Gorila平台Massively Parallel Methods for Deep Reinforcement Learning，Gorilla采用的不同机器，同一个PS。而A3C中，则是同一台机器，多核CPU，降低了参数和梯度的传输成本，论文里验证迭代速度明显更快。并且更为重要的是，它是采用同机多线程的actor-learner对，每个线程对应不同的探索策略，总体上看样本间是低相关的，因此不再需要DQN中引入experience replay机制来进行训练。这样能够采用on-policy的方法进行训练。此外，训练中采用的是CPU而非GPU，原因是RL在训练过程中batch一般很小，GPU在等待新数据时空闲很多。附异步方法抽象的架构图见下：

Advantage Actor-Critic
与DDPG不同的是A3C利用的是max(Advantage)而非max(Q)