Neural Episodic Control

Neural Episodic Control

Alexander Pritzel, etc

Google

Intro

Deep RL的训练效率很低，需要比人工训练的指数级别的数据量（这是在一般gaming的情况下）。

需要大量的数据的原因有这么几个：

1. SGD为了能够达到局部最优点，需要将lr设置比较小，从而converge比较慢
2. reward signal通常非常sparse，只有每一个episode结束的时候才知道reward（非0）
3. 通过value-bootstrapping实现的reward signal propagation，比如Q-learning。每一步将一个reward information进行propagate。为了使得结果稳定，需要很慢的更新target network。（这一块不是太确定）

最近已经有其他的方法来解决RL中的data efficiency问题，比如advances in exploration (Osband 2016), hierarchical RL (Vezhnevets 2016), transfer learning (Rusu 2016; Fernando 2017)。

这篇paper提出了Neural Episodic Control (NEC)来解决上述的三个问题，从而实现能够快速找到策略，而不需要等待过多的epoch。

Deep RL

DQN使用了Q-learning来学习一个value function，给定一个state和action，返回reward数值。根据返回的数值高低来确定选择哪一个action，根据$$\epsilon$$-greedy选择。

DQN的经典应用中，action-value function是将2D的image作为输入特征，然后输出是一个one-hot vector表示选择某一个action。每当DQN agent观测到一个transition (state的改变），那么就记录下这个四元集合 $$\langle st, a_t, r_t, s{t+1} \rangle$$，这些会用于最终agent模型（也是target network）的训练。

还有很多基于DQN的变形，比如Double DQN和A3C等。

Neural Episodic Control

由三部分组成：一个cnn（将状态s作为输入），一个memory module set （每一个action一个module），和一个最终将action memory转换成Q-value的network函数。第一个cnn就是我们以往在DQN中使用的。

Differentiable Neural Dictionary (DND)

对于每一个action a，NEC都有一个对应的memory module $$M_a = (K_a, V_a)$$，其中$$K_a$$和$$V_a$$都包含了动态个数的arrays，前者是arrays of key vectors，后者是arrays of values。这个memory module工作原理类似字典，从key -> value，主要有两个操作：lookup和write。

lookup操作，将某一个key $$h$$映射到一个输出的数值，这么定义：

$$ o = \sum_i w_i, v_i \ w_i = \frac{k(h, h_i)}{\sum_j k(h, h_j)}

$$

$$k(h,h_i)$$是Gaussian或者inverse kernel。上述lookup操作有点类似kNN。当一个lookup操作结束，$$\langle h, o \rangle$$就会被重新写到memory中。

Agent Architecture

根据图二，上述的DND其实就是一个利用kNN（外加一些限制和加速）对Q-value（即为上述地点$$V_a$$）进行估计。然后根据整个框架的结构进行gradient update。

CNN是将pixel image作为输入，生成key $$h$$；而对应估计的Q-value则是类似kNN的方式approximate。每一个action都有这样一个对应的memory module：同样的状态$$s$$，通过某一个$$a$$之后的Q-value。

Adding $$(s,a)$$ pairs to memory

使用N-step Q-value estimation。还有一些细节的实习，比如如何求解公式3中的bootstrap term。

Learning

将$$\langle s_t, a_t, R_t \rangle$$-tuple 放到relay buffer中，每次更新network随机均匀选取一些minibatch进行SGD。

Appendix

很显然还是对于Atari Game的最基本应用的延伸，action space都是离散。最核心的就是图二，利用类似kNN的办法估计Q-value。

将来可以考虑如何将action memory module也应用在连续的action space。