DQN改进算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_type": "code",
    "id": "71B2C03334E24D66B5E6DB93C8387937",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# DQN改进算法\n",
    "## 简介\n",
    "DQN算法敲开了深度强化学习的大门，但是作为先驱性的工作，其本身也存在着一些问题以及一些可以改进的地方，于是在DQN之后学术界涌现出了非常多的改进算法。在本节课程中，我们将介绍其中两个非常著名的算法：Double DQN和Dueling DQN，这两个算法实现非常简单，只需要在DQN上进行略微修改，但能一定程度改善DQN的效果。如果想要了解更加详细的各种DQN改进方法，我们推荐读者阅读论文Rainbow以及其中的引用文献。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "D47F7231B53449B98161F7E4E8B91F15",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Double DQN\n",
    "\n",
    "普通的DQN算法通常会导致对$Q$值的过高估计。我们可以观察到，传统DQN优化的TD目标为\n",
    "$$\n",
    "r+\\gamma \\max _{a'} Q_{\\omega^-}\\left(s', a' \\right)\n",
    "$$\n",
    "其中$\\max _{a'} Q_{\\omega^-}\\left(s', a' \\right)$由目标网络（参数为$\\omega^-$）计算得出，我们还可以将其写成如下形式\n",
    "\n",
    "$$\n",
    "Q_{\\omega^-}\\left(s', \\arg\\max_{a'} Q_{\\omega^-}\\left(s',  a' \\right) \\right)\n",
    "$$\n",
    "\n",
    "换句话说，max操作实际可以被拆解为两部分，首先选取状态$s'$下的最优动作$a^{*} = \\underset{a'}{\\operatorname{argmax}} Q_{\\omega^-}\\left(s', a' \\right)$，接着计算该动作对应的价值$Q\\left(s', a^* \\right)$。\n",
    "当这两部分采用同一套$Q$网络进行计算时，每次得到的都是神经网络当前估算的所有动作价值中的最大值。考虑到我们通过神经网络估算的$Q$值本身在某些时候会产生或正或负的误差，在DQN的更新方式下神经网络会将正误差累积。比如我们考虑一个特殊情形，在状态$s'$下所有动作的$Q$值均为0，即$Q(s', a_i)=0,\\forall i$，此时正确的更新目标应为$r+0=r$。但是由于神经网络拟合的误差通常会出现某些动作的估算有正误差，即存在$Q(s', a_j) > 0$，此时我们的更新目标出现了过高估计，$r+\\gamma \\max Q > r+0$。所以当我们用DQN的更新公式进行更新时，$Q(s, a)$也就会被过高估计了。同理，我们拿这个$Q(s,a)$来作为更新目标来更新上一步的$Q$值时，同样会过高估计，并且误差将会逐步累积。\n",
    "\n",
    "\n",
    "为了解决这一问题，Double DQN算法提出利用两个独立训练的神经网络估算$\\max_{a'} Q_*(s', a')$。具体做法是将原有的$\\max _{a'} Q_{\\omega^-}\\left(s', a'\\right)$更改为\n",
    "\n",
    "$$\n",
    "Q_{\\omega^-}\\left(s', \\arg\\max_{a'} Q_{\\omega}\\left(s',  a' \\right) \\right)\n",
    "$$\n",
    "\n",
    "即我们利用一套神经网络$Q_{\\boldsymbol{\\omega}}$的输出选取价值最大的动作，然而在使用该动作的价值时，用另一套神经网络$Q_{\\boldsymbol{\\omega}^{-}}$计算该动作的价值。这样，就算其中一套神经网络某个动作存在比较严重的过高估计，由于另一套神经网络的存在，这个动作最终使用的$Q$值不会存在很大的过高估计，从一定程度上解决了这个问题。\n",
    "\n",
    "而我们注意到，在传统的DQN算法中，本来就存在两套$Q$函数的神经网络——目标网络和训练网络，只不过$\\max_{a'} Q_{\\omega^-}\\left(s', a' \\right)$的计算只用到了其中的目标网络，那么我们恰好可以直接将训练网络作为Double DQN算法中的第一套神经网络选取动作，将目标网络作为第二套神经网络计算Q值，这便是Double DQN的主要思想。由于在DQN算法中我们就将训练网络的参数记为$\\omega$，将目标网络的参数记为$\\omega^{-}$，这与之前Double DQN中写下的两套神经网络的参数是统一的，我们可以直接写出如下Double DQN的优化目标\n",
    "\n",
    "$$\n",
    "r+\\gamma Q_{\\omega^-}\\left(s', \\arg\\max_{a'} Q_\\omega\\left(s', a'\\right)\\right)\n",
    "$$\n",
    "\n",
    "<img src=\"https://staticcdn.boyuai.com/user-assets/358/K3gRHxosX5FugJc2dAwxHL/qipg4vdji5.png!png\" width = \"900\" height = \"900\" align=center />\n",
    " \n",
    "<center>Double DQN和DQN对比图</center>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EB4366B054774487A4C29B270E018DCA",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Double DQN代码实践\n",
    "显然，Double DQN与DQN的差别只是在于计算状态$s'$下$Q$值时动作的选取上：\n",
    "* DQN的优化目标可以写为$r+\\gamma Q_{\\omega^-}\\left(s', \\arg\\max_{a'} Q_{\\omega^-}\\left(s', a'\\right)\\right)$，动作的选取依靠目标网络$Q_{\\omega^-}$\n",
    "* Double DQN的优化目标为$r+\\gamma Q_{\\omega^-}\\left(s', \\arg\\max_{a'} Q_\\omega\\left(s', a' \\right)\\right)$，动作的选取依靠训练网络$Q_\\omega$\n",
    "\n",
    "所以代码实现可以直接在原DQN的基础上进行，无需做过多修改。\n",
    "\n",
    "本次采用的环境是[Pendulum](https://gym.openai.com/envs/Pendulum-v0/)，该环境下有一个从随机位置开始的钟摆，钟摆向上保持直立时奖励为0，钟摆在其他位置时奖励为负数，环境本身没有终止状态。环境的状态为钟摆角度的正弦值$\\sin \\theta$，余弦值$\\cos \\theta$，角速度$\\dot\\theta$，动作为对钟摆施加的力矩。每一步会根据当前摆的状态的好坏给予不同的奖励。200步后自动结束游戏。\n",
    "\n",
    "该环境的状态有三个参数：\n",
    "\n",
    "标号 | 名称  | 最小值 | 最大值  \n",
    "----|--------------|-----|----   \n",
    "0   | $\\cos \\theta$  | -1.0| 1.0\n",
    "1   | $\\sin \\theta$  | -1.0| 1.0\n",
    "2   | $\\dot \\theta$  | -8.0| 8.0\n",
    "\n",
    "该环境只有一类动作（连续动作）：\n",
    "\n",
    "标号 | 动作  | 最小值 | 最大值  \n",
    "----|--------------|-----|----   \n",
    "0   | 力矩 | -2.0| 2.0\n",
    "\n",
    "\n",
    "<img src=\"https://staticcdn.boyuai.com/user-assets/358/ksRQPrDqHFAKjynictbYiG/pendulum.gif\" width = \"300\" height = \"300\" align=center />\n",
    " \n",
    "<center>Pendulum环境示意图</center>\n",
    "\n",
    "**由于Pendulum-v0环境的动作是力矩大小，是在[-2,2]范围内的连续值。我么之前提到过，DQN只能处理离散动作环境，无法直接来解决Pendulum环境。但该环境可以比较方便我们来验证DQN对$Q$值的过高估计：该环境下$Q$值的最大估计应为0(钟摆向上保持竖直时能选取的最大$Q$值)，$Q$值出现大于0的情况则说明出现了过高估计。为了能够应用DQN，我们采用离散化动作的技巧。如下面的代码中我们将连续的动作空间离散为11个动作。动作[0，1，..., 9, 10]分别代表力矩为[-2, -1.6, -1.4， ..., 1.4, 1.6, 2]**。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "ECFA99FC348347838E9E515E565E5756",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import gym\n",
    "import numpy as np\n",
    "import torch\n",
    "import torch.nn.functional as F\n",
    "import matplotlib.pyplot as plt\n",
    "import rl_utils\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "9C74FCDC478B4D2D92FD6B4CE4BC6D0D",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class Qnet(torch.nn.Module):\n",
    "    ''' 一层隐层的Q网络 '''\n",
    "    def __init__(self, state_dim, hidden_dim, action_dim):\n",
    "        super(Qnet, self).__init__()\n",
    "        self.fc1 = torch.nn.Linear(state_dim, hidden_dim)\n",
    "        self.fc2 = torch.nn.Linear(hidden_dim, action_dim)\n",
    "\n",
    "    def forward(self, x):\n",
    "        x = F.relu(self.fc1(x))\n",
    "        return self.fc2(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "C98550822C794F1A81C909D31D18DF7F",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class DQN:\n",
    "    ''' DQN算法，包括DoubleDQN '''\n",
    "    def __init__(self, state_dim, hidden_dim, action_dim, learning_rate, gamma, epsilon, target_update, device, dqn_type='VanillaDQN'):\n",
    "        self.action_dim = action_dim \n",
    "        self.q_net = Qnet(state_dim, hidden_dim, self.action_dim).to(device) \n",
    "        self.target_q_net = Qnet(state_dim, hidden_dim, self.action_dim).to(device) \n",
    "        self.optimizer= torch.optim.Adam(self.q_net.parameters(), lr=learning_rate) \n",
    "        self.gamma = gamma \n",
    "        self.epsilon = epsilon \n",
    "        self.target_update = target_update \n",
    "        self.count = 0\n",
    "        self.dqn_type = dqn_type\n",
    "    \n",
    "    def take_action(self, state): \n",
    "        if np.random.random() < self.epsilon:\n",
    "            action = np.random.randint(self.action_dim)\n",
    "        else:\n",
    "            state = torch.tensor([state], dtype=torch.float)\n",
    "            action = self.q_net(state).argmax().item()\n",
    "        return action\n",
    "    \n",
    "    def max_q_value(self, state):\n",
    "        state = torch.tensor([state], dtype=torch.float)\n",
    "        return self.q_net(state).max().item()\n",
    "\n",
    "    def update(self, transition_dict):\n",
    "        states = torch.tensor(transition_dict['states'], dtype=torch.float)\n",
    "        actions =  torch.tensor(transition_dict['actions']).view(-1, 1)\n",
    "        rewards = torch.tensor(transition_dict['rewards'], dtype=torch.float).view(-1, 1)\n",
    "        next_states = torch.tensor(transition_dict['next_states'], dtype=torch.float)\n",
    "        dones = torch.tensor(transition_dict['dones'], dtype=torch.float).view(-1, 1)\n",
    "\n",
    "        q_values = self.q_net(states).gather(1, actions) \n",
    "        if self.dqn_type == 'DoubleDQN': # Double DQN的区别\n",
    "            max_action = self.q_net(next_states).max(1)[1].view(-1, 1)\n",
    "            max_next_q_values = self.target_q_net(next_states).gather(1, max_action)\n",
    "        else:\n",
    "            max_next_q_values = self.target_q_net(next_states).max(1)[0].view(-1, 1) \n",
    "        q_targets = rewards + self.gamma * max_next_q_values * (1 - dones) \n",
    "        dqn_loss = torch.mean(F.mse_loss(q_values, q_targets))\n",
    "        self.optimizer.zero_grad()\n",
    "        dqn_loss.backward() \n",
    "        self.optimizer.step()\n",
    "\n",
    "        if self.count % self.target_update == 0:\n",
    "            self.target_q_net.load_state_dict(self.q_net.state_dict())\n",
    "        self.count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "9A59FFCF9C914B11984141BD5040EC4A",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "lr = 1e-2\n",
    "num_episodes = 200\n",
    "hidden_dim = 128\n",
    "gamma = 0.98\n",
    "epsilon = 0.01\n",
    "target_update = 50\n",
    "buffer_size = 5000\n",
    "minimal_size = 1000\n",
    "batch_size = 64\n",
    "device = torch.device(\"cuda\") if torch.cuda.is_available() else torch.device(\"cpu\")\n",
    "\n",
    "env_name = 'Pendulum-v0'\n",
    "env = gym.make(env_name)\n",
    "state_dim = env.observation_space.shape[0]\n",
    "action_dim = 11  # 将连续动作分成11个离散动作\n",
    "\n",
    "def dis_to_con(discrete_action, env, action_dim): # 离散动作转回连续的函数\n",
    "    action_lowbound = env.action_space.low[0] # 连续动作的最小值\n",
    "    action_upbound = env.action_space.high[0] # 连续动作的最大值\n",
    "    return action_lowbound + (discrete_action / (action_dim - 1)) * (action_upbound - action_lowbound)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "B1501F0C47F04228AD07FF6B33F7F732",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def train_DQN(agent, env, num_episodes, replay_buffer, minimal_size, batch_size):\n",
    "    return_list = []\n",
    "    max_q_value_list = []\n",
    "    max_q_value = 0\n",
    "    for i in range(10):\n",
    "        with tqdm(total=int(num_episodes/10), desc='Iteration %d' % i) as pbar:\n",
    "            for i_episode in range(int(num_episodes/10)):\n",
    "                episode_return = 0\n",
    "                state = env.reset()\n",
    "                done = False\n",
    "                while not done:\n",
    "                    action = agent.take_action(state)\n",
    "                    max_q_value = agent.max_q_value(state) * 0.005 + max_q_value * 0.995 # 平滑处理\n",
    "                    max_q_value_list.append(max_q_value) # 保存每个状态的最大Q值\n",
    "                    action_continuous = dis_to_con(action, env, agent.action_dim)\n",
    "                    next_state, reward, done, _ = env.step([action_continuous])\n",
    "                    replay_buffer.add(state, action, reward, next_state, done)\n",
    "                    state = next_state\n",
    "                    episode_return += reward\n",
    "                    if replay_buffer.size() > minimal_size:\n",
    "                        b_s, b_a, b_r, b_ns, b_d = replay_buffer.sample(batch_size)\n",
    "                        transition_dict = {'states': b_s, 'actions': b_a, 'next_states': b_ns, 'rewards': b_r, 'dones': b_d}\n",
    "                        agent.update(transition_dict)\n",
    "                return_list.append(episode_return)\n",
    "                if (i_episode+1) % 10 == 0:\n",
    "                    pbar.set_postfix({'episode': '%d' % (num_episodes/10 * i + i_episode+1), 'return': '%.3f' % np.mean(return_list[-10:])})\n",
    "                pbar.update(1)\n",
    "    return return_list, max_q_value_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "095A714A7CF041BE838535BF29CA91DA",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Iteration 0: 100%|██████████| 20/20 [00:07<00:00,  2.19it/s, episode=20, return=-1063.629]\n",
      "Iteration 1: 100%|██████████| 20/20 [00:09<00:00,  2.15it/s, episode=40, return=-869.863] \n",
      "Iteration 2: 100%|██████████| 20/20 [00:09<00:00,  2.16it/s, episode=60, return=-246.865]\n",
      "Iteration 3: 100%|██████████| 20/20 [00:09<00:00,  2.15it/s, episode=80, return=-226.042]\n",
      "Iteration 4: 100%|██████████| 20/20 [00:09<00:00,  2.17it/s, episode=100, return=-210.614]\n",
      "Iteration 5: 100%|██████████| 20/20 [00:09<00:00,  2.16it/s, episode=120, return=-251.662]\n",
      "Iteration 6: 100%|██████████| 20/20 [00:09<00:00,  2.15it/s, episode=140, return=-239.768]\n",
      "Iteration 7: 100%|██████████| 20/20 [00:09<00:00,  2.19it/s, episode=160, return=-174.586]\n",
      "Iteration 8: 100%|██████████| 20/20 [00:09<00:00,  2.14it/s, episode=180, return=-263.318]\n",
      "Iteration 9: 100%|██████████| 20/20 [00:09<00:00,  2.12it/s, episode=200, return=-219.349]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"https://staticcdn.boyuai.com/user-assets/358/Ho4Xs5zqo7h76AnkJDeXZy/qwdrlmztem.png!png\">"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<img src=\"https://staticcdn.boyuai.com/user-assets/358/Vf29LWfX3Grf4ckYXD3Qzr/qwdrlmvuw0.png!png\">"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "random.seed(0)\n",
    "np.random.seed(0)\n",
    "env.seed(0)\n",
    "torch.manual_seed(0)\n",
    "replay_buffer = rl_utils.ReplayBuffer(buffer_size)\n",
    "agent = DQN(state_dim, hidden_dim, action_dim, lr, gamma, epsilon, target_update, device)\n",
    "return_list, max_q_value_list = train_DQN(agent, env, num_episodes, replay_buffer, minimal_size, batch_size)\n",
    "\n",
    "episodes_list = list(range(len(return_list)))\n",
    "mv_return = rl_utils.moving_average(return_list, 5)\n",
    "plt.plot(episodes_list, mv_return)\n",
    "plt.xlabel('Episodes')   \n",
    "plt.ylabel('Returns')  \n",
    "plt.title('DQN on {}'.format(env_name))  \n",
    "plt.show()\n",
    "\n",
    "frames_list = list(range(len(max_q_value_list)))\n",
    "plt.plot(frames_list, max_q_value_list)\n",
    "plt.axhline(0, c='orange', ls='--')\n",
    "plt.axhline(10, c='red', ls='--')\n",
    "plt.xlabel('Frames')   \n",
    "plt.ylabel('Q value')  \n",
    "plt.title('DQN on {}'.format(env_name))  \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F5E78E3688294E3E8FB39E468CDF903E",
    "jupyter": {},
    "mdEditEnable": false,
    "notebookId": "5f8f31e546ba5e0030780165",
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "根据实验结果我们发现，DQN算法在Pendulum环境上能取得不错的回报，最后的平均回报在-200左右，但是Q值可视化之后发现不少超过了0，并且有一些还超过了10，该现象便是DQN算法中的Q值过高估计。我们现在看一下Double DQN是否能对此进行改善。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "id": "033BAA809E8948918AFD76B329B601F3",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Iteration 0: 100%|██████████| 20/20 [00:07<00:00,  2.05it/s, episode=20, return=-1167.778]\n",
      "Iteration 1: 100%|██████████| 20/20 [00:09<00:00,  2.03it/s, episode=40, return=-649.008]\n",
      "Iteration 2: 100%|██████████| 20/20 [00:09<00:00,  2.05it/s, episode=60, return=-297.516]\n",
      "Iteration 3: 100%|██████████| 20/20 [00:09<00:00,  2.02it/s, episode=80, return=-262.276]\n",
      "Iteration 4: 100%|██████████| 20/20 [00:09<00:00,  2.03it/s, episode=100, return=-277.412]\n",
      "Iteration 5: 100%|██████████| 20/20 [00:09<00:00,  2.03it/s, episode=120, return=-289.226]\n",
      "Iteration 6: 100%|██████████| 20/20 [00:09<00:00,  2.02it/s, episode=140, return=-307.092]\n",
      "Iteration 7: 100%|██████████| 20/20 [00:09<00:00,  2.02it/s, episode=160, return=-236.051]\n",
      "Iteration 8: 100%|██████████| 20/20 [00:09<00:00,  2.02it/s, episode=180, return=-260.574]\n",
      "Iteration 9: 100%|██████████| 20/20 [00:09<00:00,  2.04it/s, episode=200, return=-285.691]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"https://staticcdn.boyuai.com/user-assets/358/E5Q1uVSZdC28MDshZLo475/qwdrq1fc1r.png!png\">"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<img src=\"https://staticcdn.boyuai.com/user-assets/358/4QmRhPNVks1FNXH4kAgCan/qwdrq1vg7c.png!png\">"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "random.seed(0)\n",
    "np.random.seed(0)\n",
    "env.seed(0)\n",
    "torch.manual_seed(0)\n",
    "replay_buffer = rl_utils.ReplayBuffer(buffer_size)\n",
    "agent = DQN(state_dim, hidden_dim, action_dim, lr, gamma, epsilon, target_update, device, 'DoubleDQN')\n",
    "return_list, max_q_value_list = train_DQN(agent, env, num_episodes, replay_buffer, minimal_size, batch_size)\n",
    "\n",
    "episodes_list = list(range(len(return_list)))\n",
    "mv_return = rl_utils.moving_average(return_list, 5)\n",
    "plt.plot(episodes_list, mv_return)\n",
    "plt.xlabel('Episodes')   \n",
    "plt.ylabel('Returns')  \n",
    "plt.title('Double DQN on {}'.format(env_name))  \n",
    "plt.show()\n",
    "\n",
    "frames_list = list(range(len(max_q_value_list)))\n",
    "plt.plot(frames_list, max_q_value_list)\n",
    "plt.axhline(0, c='orange', ls='--')\n",
    "plt.axhline(10, c='red', ls='--')\n",
    "plt.xlabel('Frames')   \n",
    "plt.ylabel('Q value')  \n",
    "plt.title('Double DQN on {}'.format(env_name))  \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "C88F499B85ED42C4832BB76FA134C369",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "我们可以发现，相比于普通的DQN，Double DQN算法比较少出现Q值大于0的情况，说明Q值过高估计的问题得到了很大缓解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "B83470FC97C04F3EBA8D74E9A398137A",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Dueling DQN\n",
    "\n",
    "[Dueling DQN](https://arxiv.org/abs/1511.06581)是另一种DQN的改进算法。它在传统DQN的基础上只进行了稍稍改动，但却能大幅提升DQN的表现。在强化学习中，我们将状态动作价值函数减去状态函数定义为优势函数，即$A(s,a) = Q(s,a)-V(s)$。在同一个状态下，所有动作的优势值之和为0，因为所有动作的动作价值的平均就是这个状态的状态价值。据此，在Dueling DQN中，Q网络被建模为：\n",
    "\n",
    "$$\n",
    "Q_{\\eta, \\alpha, \\beta}(s, a)=V_{\\eta, \\alpha}(s)+A_{\\eta, \\beta}(s, a)\n",
    "$$\n",
    "\n",
    "其中$V_{\\eta, \\alpha}(s)$为状态价值函数，而$A_{\\eta, \\beta}(s, a )$则为该状态下采取不同动作的优势函数，表征的是采取不同动作的差异性。$\\eta$是状态价值函数和优势函数共享的网络参数，一般为神经网络用来提取特征的前几层。而$\\alpha$和$\\beta$为两者各自的参数。在这样的建模下我们不再让神经网络直接输出$Q$值，而是训练神经网络的两部分分别输出价值函数和优势函数，再求和得到$Q$值。DQN和Dueling DQN的网络结构图区别如下：\n",
    "\n",
    "<img src=\"https://staticcdn.boyuai.com/user-assets/358/XRT3k5AYGLF233uvCsmTN4/qfmiegdc53.png!png\" width = \"300\" height = \"300\" align=center />\n",
    " \n",
    "<center>DQN与Dueling DQN网络结构的区别</center>\n",
    "\n",
    "将状态价值函数和优势函数分别建模的好处在于某些情境下智能体只会关注状态的价值，而并不关心不同动作导致的差异，此时将二者分开建模能够使智能体更好地处理与动作关联较小的状态。如下图的驾驶车辆游戏中，智能体注意力集中的部位被显示为偏橙色，在智能体前面没有车时，车子自身动作并没有太大差异，此时智能体更关注于状态价值，而在有车时（智能体需要超车），智能体开始关注不同动作优势值上的差异。\n",
    "\n",
    "<img src=\"https://staticcdn.boyuai.com/user-assets/358/hvt243eeywugHYf6AEdiNG/qwdfh8aa3t.png!png\" width = \"300\" height = \"300\" align=center />\n",
    " \n",
    "<center>状态价值和优势值的简单例子</center>\n",
    "\n",
    "对于上述Dueling DQN中的公式$Q_{\\eta, \\alpha, \\beta}(s, a)=V_{\\eta, \\alpha}(s)+A_{\\eta, \\beta}(s, a)$，它存在对于$A$值和$V$值建模不唯一性的问题（比如对于同样的$Q$值，如果将$V$值加上任意大小的常数$C$，再将所有$A$值减去$C$，则我们得到的$Q$值依然不变，这就给训练造成了不稳定）。为了解决这一问题，Dueling DQN强制最优动作的优势函数的实际输出为$0$，即\n",
    "$$\n",
    "Q_{\\eta, \\alpha, \\beta}(s, a )=V_{\\eta, \\alpha}(s)+A_{\\eta, \\beta}(s, a )-\\max _{a^{\\prime}} A_{\\eta, \\beta}\\left(s, a^{\\prime}\\right)\n",
    "$$\n",
    "此时$V(s) = \\max_a Q(s,a)$，可以确保$V$值建模的唯一性。\n",
    "在实际实现过程中，我们还可以用平均代替最大化操作，即\n",
    "$$\n",
    "Q_{\\eta, \\alpha, \\beta}(s, a)=V_{\\eta, \\alpha}(s)+ A_{\\eta, \\beta}(s, a)-\\frac{1}{|\\mathcal{A}|} \\sum_{a^{\\prime}} A_{\\eta, \\beta}\\left(s, a^{\\prime}\\right)\n",
    "$$\n",
    "此时$V(s) = \\frac{1}{|\\mathcal{A}|} \\sum_{a^{\\prime}}Q(s,a')$。在下面的代码实现中，我们将采取此种方式，虽然它不再满足最优策略的贝尔曼方程，但实际应用时更加稳定。\n",
    "\n",
    "有人可能能会问：为什么Dueling DQN会比DQN好？原论文里写道Dueling DQN能更高效学习状态价值函数。每一次更新时，$V$函数都会被更新到，这也会影响到其他动作的$Q$值；而传统的DQN只会更新某个动作的$Q$值，其他动作的$Q$值就不会更新。这样能够更加频繁准确的学习到状态价值函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "79E9A4FE236A4AB185798B1820CC7854",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Dueling DQN代码实践\n",
    "Dueling DQN与DQN相比的差异只是在网络结构上，大部分代码依然可以继续沿用。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "A189C0B312204F8C8BEF41CEE38FB8B9",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class VAnet(torch.nn.Module):\n",
    "    ''' 一层隐层的A网络和V网络 '''\n",
    "    def __init__(self, state_dim, hidden_dim, action_dim):\n",
    "        super(VAnet, self).__init__()\n",
    "        self.fc1 = torch.nn.Linear(state_dim, hidden_dim) # 共享网络部分\n",
    "        self.fc_A = torch.nn.Linear(hidden_dim, action_dim)\n",
    "        self.fc_V = torch.nn.Linear(hidden_dim, 1)\n",
    "\n",
    "    def forward(self, x):\n",
    "        A = self.fc_A(F.relu(self.fc1(x)))\n",
    "        V = self.fc_V(F.relu(self.fc1(x)))\n",
    "        Q = V + A - A.mean(1).view(-1, 1) # Q值由V值和A值计算得到\n",
    "        return Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "id": "79A3C41B705148038CB60C49CEA604EE",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class DQN:\n",
    "    ''' DQN算法，包括Double DQN和Dueling DQN '''\n",
    "    def __init__(self, state_dim, hidden_dim, action_dim, learning_rate, gamma, epsilon, target_update, device, dqn_type='VanillaDQN'):\n",
    "        self.action_dim = action_dim \n",
    "        if dqn_type == 'DuelingDQN': # Dueling DQN采取不一样的网络框架\n",
    "            self.q_net = VAnet(state_dim, hidden_dim, self.action_dim).to(device) \n",
    "            self.target_q_net = VAnet(state_dim, hidden_dim, self.action_dim).to(device)\n",
    "        else:\n",
    "            self.q_net = Qnet(state_dim, hidden_dim, self.action_dim).to(device) \n",
    "            self.target_q_net = Qnet(state_dim, hidden_dim, self.action_dim).to(device) \n",
    "        self.optimizer= torch.optim.Adam(self.q_net.parameters(), lr=learning_rate) \n",
    "        self.gamma = gamma \n",
    "        self.epsilon = epsilon \n",
    "        self.target_update = target_update \n",
    "        self.count = 0\n",
    "        self.dqn_type = dqn_type\n",
    "    \n",
    "    def take_action(self, state): \n",
    "        if np.random.random() < self.epsilon:\n",
    "            action = np.random.randint(self.action_dim)\n",
    "        else:\n",
    "            state = torch.tensor([state], dtype=torch.float)\n",
    "            action = self.q_net(state).argmax().item()\n",
    "        return action\n",
    "    \n",
    "    def max_q_value(self, state):\n",
    "        state = torch.tensor([state], dtype=torch.float)\n",
    "        return self.q_net(state).max().item()\n",
    "\n",
    "    def update(self, transition_dict):\n",
    "        states = torch.tensor(transition_dict['states'], dtype=torch.float)\n",
    "        actions =  torch.tensor(transition_dict['actions']).view(-1, 1)\n",
    "        rewards = torch.tensor(transition_dict['rewards'], dtype=torch.float).view(-1, 1)\n",
    "        next_states = torch.tensor(transition_dict['next_states'], dtype=torch.float)\n",
    "        dones = torch.tensor(transition_dict['dones'], dtype=torch.float).view(-1, 1)\n",
    "\n",
    "        q_values = self.q_net(states).gather(1, actions) \n",
    "        if self.dqn_type == 'DoubleDQN':\n",
    "            max_action = self.q_net(next_states).max(1)[1].view(-1, 1)\n",
    "            max_next_q_values = self.target_q_net(next_states).gather(1, max_action)\n",
    "        else:\n",
    "            max_next_q_values = self.target_q_net(next_states).max(1)[0].view(-1, 1) \n",
    "        q_targets = rewards + self.gamma * max_next_q_values * (1 - dones) \n",
    "        dqn_loss = torch.mean(F.mse_loss(q_values, q_targets))\n",
    "        self.optimizer.zero_grad()\n",
    "        dqn_loss.backward() \n",
    "        self.optimizer.step()\n",
    "\n",
    "        if self.count % self.target_update == 0:\n",
    "            self.target_q_net.load_state_dict(self.q_net.state_dict())\n",
    "        self.count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "id": "BCBCB5296F494695898180CD7EC00CF3",
    "jupyter": {},
    "notebookId": "5f8f31e546ba5e0030780165",
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Iteration 0: 100%|██████████| 20/20 [00:10<00:00,  1.46it/s, episode=20, return=-566.544] \n",
      "Iteration 1: 100%|██████████| 20/20 [00:13<00:00,  1.46it/s, episode=40, return=-305.875]\n",
      "Iteration 2: 100%|██████████| 20/20 [00:13<00:00,  1.44it/s, episode=60, return=-260.326]\n",
      "Iteration 3: 100%|██████████| 20/20 [00:13<00:00,  1.44it/s, episode=80, return=-171.342]\n",
      "Iteration 4: 100%|██████████| 20/20 [00:13<00:00,  1.45it/s, episode=100, return=-246.607]\n",
      "Iteration 5: 100%|██████████| 20/20 [00:13<00:00,  1.44it/s, episode=120, return=-340.761]\n",
      "Iteration 6: 100%|██████████| 20/20 [00:13<00:00,  1.43it/s, episode=140, return=-234.315]\n",
      "Iteration 7: 100%|██████████| 20/20 [00:14<00:00,  1.43it/s, episode=160, return=-160.320]\n",
      "Iteration 8: 100%|██████████| 20/20 [00:13<00:00,  1.43it/s, episode=180, return=-254.963]\n",
      "Iteration 9: 100%|██████████| 20/20 [00:13<00:00,  1.44it/s, episode=200, return=-192.522]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"https://staticcdn.boyuai.com/user-assets/358/fzMS3WuHVjMgUR4bN7EEQc/qwdrxpy09u.png!png\">"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<img src=\"https://staticcdn.boyuai.com/user-assets/358/N2KjSjGMpfX9xGnpW7zH9B/qwdrxp5ayx.png!png\">"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "random.seed(0)\n",
    "np.random.seed(0)\n",
    "env.seed(0)\n",
    "torch.manual_seed(0)\n",
    "replay_buffer = rl_utils.ReplayBuffer(buffer_size)\n",
    "agent = DQN(state_dim, hidden_dim, action_dim, lr, gamma, epsilon, target_update, device, 'DuelingDQN')\n",
    "return_list, max_q_value_list = train_DQN(agent, env, num_episodes, replay_buffer, minimal_size, batch_size)\n",
    "\n",
    "episodes_list = list(range(len(return_list)))\n",
    "mv_return = rl_utils.moving_average(return_list, 5)\n",
    "plt.plot(episodes_list, mv_return)\n",
    "plt.xlabel('Episodes')   \n",
    "plt.ylabel('Returns')  \n",
    "plt.title('Dueling DQN on {}'.format(env_name))  \n",
    "plt.show()\n",
    "\n",
    "frames_list = list(range(len(max_q_value_list)))\n",
    "plt.plot(frames_list, max_q_value_list)\n",
    "plt.axhline(0, c='orange', ls='--')\n",
    "plt.axhline(10, c='red', ls='--')\n",
    "plt.xlabel('Frames')   \n",
    "plt.ylabel('Q value')  \n",
    "plt.title('Dueling DQN on {}'.format(env_name))  \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "1804E104A298468F8BFBFE09F880EB7E",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "由曲线可知，相比于传统的DQN，Dueling DQN相比于DQN在多个动作选择下的学习更加稳定，并且得到的回报最大值也更大。由Dueling DQN的原理可知随着动作空间的增大，Dueling DQN相比于DQN的优势更为明显。之前我们在环境中设置的离散动作为11个，如果将离散动作数增多（15， 25， ...），我们可以继续进行对比实验。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "D53DD29948FB42ED81E45AD5BE159B59",
    "jupyter": {},
    "mdEditEnable": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## 总结\n",
    "在传统的DQN基础上，有两种非常容易实现的变式——Double DQN和Dueling DQN，Double DQN解决了DQN中对Q值的过高估计，而Dueling DQN能够很好地学习到不同动作的差异性，在动作空间较大的环境下非常有效。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "81902069238D479588134D7F7A7371AC",
    "jupyter": {},
    "mdEditEnable": true,
    "notebookId": "5f8f31e546ba5e0030780165",
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## 扩展阅读： 对Q值过高估计的定量分析\n",
    "我们可以对Q值的过估计做一个简化的定量分析。假设在状态$s$下所有动作的期望回报均无差异，即$Q_*(s,a) = V_*(s)$（此情形是为了定量分析所简化的情形，实际上不同动作的期望回报通常会存在差异）。假设神经网络估算误差$Q_{\\omega^-}(s, a)-V_{*}$服从$[-1,1]$之间的均匀独立同分布。假设动作空间大小为$m$，那么对于任意状态$s$我们有\n",
    "$$\n",
    "\\mathbb{E}\\left[\\max _{a} Q_{\\omega^-}(s, a)- \\max_{a'} Q_{*}(s,a')\\right]=\\frac{m-1}{m+1}\n",
    "$$\n",
    "**证明：**\n",
    "我们将估算误差记为$\\epsilon_{a}=Q_{\\omega^-}(s, a)-\\max_{a'}Q_{*}(s, a')$，由于估算误差对于不同的动作是独立的，我们有\n",
    "$$\n",
    "\\begin{aligned}\n",
    "P\\left(\\max _{a} \\epsilon_{a} \\leq x\\right) =\\prod_{a=1}^{m} P\\left(\\epsilon_{a} \\leq x\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "$P(\\epsilon_a \\leq x)$是$\\epsilon_a$的累积分布函数（CDF）,它可以具体被写为\n",
    "$$\n",
    "P\\left(\\epsilon_{a} \\leq x\\right)=\\left\\{\\begin{array}{ll}\n",
    "0 & \\text { if } x \\leq-1 \\\\\n",
    "\\frac{1+x}{2} & \\text { if } x \\in(-1,1) \\\\\n",
    "1 & \\text { if } x \\geq 1\n",
    "\\end{array}\\right.\n",
    "$$\n",
    "因此，我们有关于$\\max_a \\epsilon_a$的累积密度函数(CDF)\n",
    "$$\n",
    "\\begin{aligned}\n",
    "P\\left(\\max _{a} \\epsilon_{a} \\leq x\\right) &=\\prod_{a=1}^{m} P\\left(\\epsilon_{a} \\leq x\\right) \\\\\n",
    "&=\\left\\{\\begin{array}{ll}\n",
    "0 & \\text { if } x \\leq-1 \\\\\n",
    "\\left(\\frac{1+x}{2}\\right)^{m} & \\text { if } x \\in(-1,1) \\\\\n",
    "1 & \\text { if } x \\geq 1\n",
    "\\end{array}\\right.\n",
    "\\end{aligned}\n",
    "$$\n",
    "最后我们可以得到\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbb{E}\\left[\\max _{a} \\epsilon_{a}\\right] &=\\int_{-1}^{1} x \\frac{\\mathrm{d}}{\\mathrm{d} x} P\\left(\\max _{a} \\epsilon_{a} \\leq x \\right) \\mathrm{d} x \\\\\n",
    "&=\\left[\\left(\\frac{x+1}{2}\\right)^{m} \\frac{m x-1}{m+1}\\right]_{-1}^{1} \\\\\n",
    "&=\\frac{m-1}{m+1}\n",
    "\\end{aligned}\n",
    "$$\n",
    "虽然这一分析简化了实际环境，但它正确刻画了Q值过高估计的一些性质，比如Q值的过高估计随动作数目$m$的增加而增加，换而言之，在动作选择数更多的环境中Q值的过高估计会更严重。"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}