note/DoubleDQN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Double DQN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 背景"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Double DQN是DQN（Deep Q Network）的一种改进，旨在解决DQN训练过程中存在的过估计（Overestimating）问题。在训练过程中，与DQN直接选取目标网络（Target Q Network）中下一个State各个Action对应的Q值最大的那一个Q值不同，Double DQN的核心精神在于，它首先使用预测网络（Predict Q Network）计算下一个State的对应各个Action的Q值，然后选取最大的那个Q值对应Action的索引，再使用目标网络计算该状态的对应各个状态的Q值，然后选取预测网络中给定Action索引对应的Q值，但是它可能不是最大的那个，从而一定程度上避免了过度估计，提高了训练DQN的稳定性和速度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DQN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "即Deep Q Network，DQN有两个网络，分别是预测网络（Predict Q Network）和目标网络（Target Q Network），预测网络用来预测当前状态对应各个动作的Q值，目标网络用来预测下一个，或者下第几个状态各个动作的Q值，这个取决于训练过程采用时间差分（Temporal Difference）还是蒙特卡洛（MC）方法，以TD的训练过程为例，我们期望对采样过的每一个状态、动作、奖励元组最小化下式："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\left( Q \\left( s_j, a_j; \\theta \\right) - y_j \\right)^2\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中Q对应的θ即预测网络，它接受当前状态，输出一个当前状态对应各个动作的Q值，然后选取当前动作对应的那个Q值。$y_j$是Ground Truth标签，它是由目标网络计算得出："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "y_j=\n",
    "\\begin{cases}\n",
    "r_j & \\text{if episode ends at j + 1}\\\\\n",
    "r_j + \\gamma \\max_{a^{\\prime}} \\hat{Q} \\left( s_{j+1}, a^{\\prime}; \\theta^{-} \\right)& \\text{otherwise}\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中Q对应的θ-即是目标网络，当采取这个动作后回合结束，则标签即是这次动作产生的奖励，如果回合未结束，则标签将由两部分构成，第一部分即是这次动作产生的奖励，另一部分则是由目标网络计算，即计算下一个状态各个动作对应的Q值，然后选取最大的那个Q值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "需要注意的是，目标网络的参数是设定是不可train的，在训练经过M次后，我们会将预测网络被更新的全部参数复制给目标网络，其中M次的M是一个可调的超参数，这样的一个直觉的好处就是避免了震荡。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experience Replay"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在实作中，On-Policy的DQN表现非常不稳定，一种改进被称之为经验回放（Experience Replay）的技术通过缓存每一步状态、动作、奖励、下一状态元组，在一回合结束后批量训练多次，将On-Policy的过程转化为Off-Policy，提高了DQN的训练速度和稳定性，具体的实现非常直觉，即维护一个指定大小的缓存数组，每回合用新产生的N个状态、动作、奖励、下一状态元组随机替换掉缓存池中现有的N个，然后再回合结束后做数次训练。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Double DQN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正如背景中提到的："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 与DQN直接选取目标网络（Target Q Network）中下一个State各个Action对应的Q值最大的那一个Q值不同，Double DQN的核心精神在于，它首先使用预测网络（Predict Q Network）计算下一个State的对应各个Action的Q值，然后选取最大的那个Q值对应Action的索引，再使用目标网络计算该状态的对应各个状态的Q值，然后选取预测网络中给定Action索引对应的Q值，但是它可能不是最大的那个。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Double DQN与DQN相同的是他们都有被称之为预测网络与目标网络的两个网络，只是在实作过程中，标签的计算过程做了修正："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "y_j=\n",
    "\\begin{cases}\n",
    "r_j & \\text{if episode ends at j + 1}\\\\\n",
    "r_j + \\gamma Q \\left( s_{j+1}, \\max_{a^{\\prime}} Q \\left (s_{j+1}, a^{\\prime}; \\theta\\right) ; \\theta^{-} \\right)& \\text{otherwise}\n",
    "\\end{cases}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看出这个修正非常地直觉，在实验中，也确实要比原始的DQN训练稳定。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/shuyu/anaconda3/envs/quant/lib/python3.5/importlib/_bootstrap.py:222: RuntimeWarning: compiletime version 3.6 of module 'tensorflow.python.framework.fast_tensor_util' does not match runtime version 3.5\n",
      "  return f(*args, **kwds)\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "\n",
    "import numpy as np\n",
    "import gym\n",
    "\n",
    "import sys\n",
    "sys.path.append('..')\n",
    "\n",
    "from base.model import *\n",
    "from utility.launcher import start_game\n",
    "\n",
    "\n",
    "class Agent(BaseRLModel):\n",
    "\n",
    "    def __init__(self, a_space, s_space, **options):\n",
    "        super(Agent, self).__init__(a_space, s_space, **options)\n",
    "\n",
    "        self._init_input()\n",
    "        self._init_nn()\n",
    "        self._init_op()\n",
    "        self._init_saver()\n",
    "\n",
    "        self.buffer = np.zeros((self.buffer_size, self.s_space + 1 + 1 + self.s_space))\n",
    "        self.buffer_count = 0\n",
    "\n",
    "        self.update_target_net_step = 200\n",
    "\n",
    "        self.session.run(tf.global_variables_initializer())\n",
    "\n",
    "    def _init_input(self, *args):\n",
    "        with tf.variable_scope('input'):\n",
    "            self.s_n = tf.placeholder(tf.float32, [None, self.s_space])\n",
    "            self.s = tf.placeholder(tf.float32, [None, self.s_space])\n",
    "            self.q_n = tf.placeholder(tf.float32, [None, ])\n",
    "            self.r = tf.placeholder(tf.float32, [None, ])\n",
    "            self.a = tf.placeholder(tf.int32, [None, ])\n",
    "\n",
    "    def _init_nn(self, *args):\n",
    "        # w,b initializer\n",
    "        w_initializer = tf.random_normal_initializer(mean=0.0, stddev=0.3)\n",
    "        b_initializer = tf.constant_initializer(0.1)\n",
    "\n",
    "        with tf.variable_scope('predict_q_net'):\n",
    "            phi_state = tf.layers.dense(self.s,\n",
    "                                        64,\n",
    "                                        tf.nn.relu,\n",
    "                                        kernel_initializer=w_initializer,\n",
    "                                        bias_initializer=b_initializer)\n",
    "\n",
    "            self.q_predict = tf.layers.dense(phi_state,\n",
    "                                             self.a_space,\n",
    "                                             kernel_initializer=w_initializer,\n",
    "                                             bias_initializer=b_initializer)\n",
    "\n",
    "        with tf.variable_scope('target_q_net'):\n",
    "            phi_state_next = tf.layers.dense(self.s_n,\n",
    "                                             64,\n",
    "                                             tf.nn.relu,\n",
    "                                             kernel_initializer=w_initializer,\n",
    "                                             bias_initializer=b_initializer,\n",
    "                                             trainable=False)\n",
    "\n",
    "            self.q_target = tf.layers.dense(phi_state_next,\n",
    "                                            self.a_space,\n",
    "                                            kernel_initializer=w_initializer,\n",
    "                                            bias_initializer=b_initializer,\n",
    "                                            trainable=False)\n",
    "\n",
    "    def _init_op(self):\n",
    "\n",
    "        with tf.variable_scope('q_predict'):\n",
    "            # size of q_value_predict is [BATCH_SIZE, 1]\n",
    "            action_indices = tf.stack([tf.range(tf.shape(self.a)[0], dtype=tf.int32), self.a], axis=1)\n",
    "            self.q_eval = tf.gather_nd(self.q_predict, action_indices)\n",
    "\n",
    "        with tf.variable_scope('loss'):\n",
    "            self.loss_func = tf.losses.mean_squared_error(self.q_n, self.q_eval)\n",
    "\n",
    "        with tf.variable_scope('train'):\n",
    "            self.train_op = tf.train.AdamOptimizer(self.learning_rate).minimize(self.loss_func)\n",
    "\n",
    "        with tf.variable_scope('update_target_net'):\n",
    "            t_params = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope='target_q_net')\n",
    "            p_params = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope='predict_q_net')\n",
    "            self.update_q_net = [tf.assign(t, e) for t, e in zip(t_params, p_params)]\n",
    "\n",
    "    def predict(self, s):\n",
    "        if np.random.uniform() < self.epsilon or self.mode == 'test':\n",
    "            a = np.argmax(self.session.run(self.q_predict, feed_dict={self.s: s[np.newaxis, :]}))\n",
    "        else:\n",
    "            a = np.random.randint(0, self.a_space)\n",
    "        return a\n",
    "\n",
    "    def snapshot(self, s, a, r, s_n):\n",
    "        self.buffer[self.buffer_count % self.buffer_size, :] = np.hstack((s, [a, r], s_n))\n",
    "        self.buffer_count += 1\n",
    "\n",
    "    def train(self):\n",
    "\n",
    "        for train_step in range(self.train_steps):\n",
    "            # Update target net if need.\n",
    "            if self.training_step % self.update_target_net_step == 0:\n",
    "                self.session.run(self.update_q_net)\n",
    "            # Get batch.\n",
    "            if self.buffer_count < self.buffer_size:\n",
    "                batch = self.buffer[np.random.choice(self.buffer_count, size=self.batch_size), :]\n",
    "            else:\n",
    "                batch = self.buffer[np.random.choice(self.buffer_size, size=self.batch_size), :]\n",
    "\n",
    "            s = batch[:, :self.s_space]\n",
    "            s_n = batch[:, -self.s_space:]\n",
    "            a = batch[:, self.s_space].reshape((-1))\n",
    "            r = batch[:, self.s_space + 1]\n",
    "\n",
    "            # 1. Calculate q_next_predict and q_next_target.\n",
    "            q_next_predict, q_next_target = self.session.run([self.q_predict, self.q_target], {\n",
    "                self.s: s_n, self.s_n: s_n\n",
    "            })\n",
    "\n",
    "            # 2. Select a_indices in q_next_predict.\n",
    "            a_indices = np.argmax(q_next_predict, axis=1)\n",
    "\n",
    "            # 3. Select Q values with a_indices\n",
    "            q_next = q_next_target[np.arange(0, self.batch_size), a_indices]\n",
    "\n",
    "            # 4. Calculate q_real.\n",
    "            q_real = r + self.gamma * q_next\n",
    "\n",
    "            _, cost = self.session.run([self.train_op, self.loss_func], {\n",
    "                self.s: s, self.a: a, self.q_n: q_real\n",
    "            })\n",
    "\n",
    "            self.training_step += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if __name__ == '__main__':\n",
    "\n",
    "    def main(_):\n",
    "        # Make env.\n",
    "        env = gym.make('CartPole-v0')\n",
    "        env.seed(1)\n",
    "        env = env.unwrapped\n",
    "        # Init agent.\n",
    "        agent = Agent(env.action_space.n, env.observation_space.shape[0], **{\n",
    "            KEY_MODEL_NAME: 'PPO',\n",
    "            KEY_TRAIN_EPISODE: 10000\n",
    "        })\n",
    "        start_game(env, agent)\n",
    "\n",
    "\n",
    "    if __name__ == '__main__':\n",
    "        tf.app.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 结尾"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相对于DQN，运气到了可能3000步在小车倒立杆收敛，Double DQN如果运气到了可能只需要1500步。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}