Balancing_a_Cartpol_Using_Deep_Q-Network_code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Balancing a Cartpole Using Deep Q-Network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will develop a Deep Q network from scratch to balancing a cartpole using tensorflow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective of environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A pole is attaced by an un-actuated joint to a cart, which moves along a frictionless track. The system is controlled by applying a force of +1 or -1 to the cart. The pendulum starts upright and the goal is to prevent it from falling over. <br>\n",
    "The cart can move left or right by applying force on left or right direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import necessary libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym\n",
    "import random\n",
    "import numpy as np\n",
    "import tensorflow as tf\n",
    "from collections import deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = gym.make(\"CartPole-v0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initialization and rendering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Action space Discrete(2)\n",
      "State space Box(4,)\n",
      "Initial space [0.01667933 0.02495509 0.00306789 0.02814474]\n"
     ]
    }
   ],
   "source": [
    "print('Action space {}'.format(env.action_space))\n",
    "print('State space {}'.format(env.observation_space))\n",
    "init_state = env.reset()\n",
    "print('Initial space {}'.format(init_state))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the above we can see that, Action space is 2 because cartpole can move in two direction: left or right. The discrete space allows a fixed range of non-negative values.<br><br>\n",
    "The state space represents an n-dimentional box, so valid observatio will be an array of 4 numbers. The cartpole environment consists of 4 state (shows value in initial state result): Cart position (From the position of frame), Cart velocity (direction that it's travelling), Pole angle (from center axis) and Pole velocity at tip (angular velocity of pole).<br><br>\n",
    "Let's check state space size (set by environment gym):\n",
    "<table>\n",
    "    <thead>\n",
    "        <th>Information</th>\n",
    "        <th>Minimum</th>\n",
    "        <th>Maximum</th>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>Cart position</td>\n",
    "            <td>-2.4</td>\n",
    "            <td>2.4</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>Cart velocity</td>\n",
    "            <td>-Infinity</td>\n",
    "            <td>Infinity</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>Pole angle</td>\n",
    "            <td>~-41.8 degree</td>\n",
    "            <td>~41.8 degree</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>Pole velocity at tip</td>\n",
    "            <td>-Infinity</td>\n",
    "            <td>Infinity</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "So state size is infinity. <br><br>\n",
    "The episode is over when cart postion and cart velocity is more than the range or episode length is greater than 200.<br><br>\n",
    "Reward is +1 for every step.<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initial agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reward achieved 21.81\n",
      "Avg time steps per episode 21.81\n"
     ]
    }
   ],
   "source": [
    "epochs, total_rewards = 0, 0\n",
    "num_episodes = 100 #we are running for 100 times\n",
    "current_episode = 0\n",
    "while current_episode < num_episodes:\n",
    "    reward = 0\n",
    "    done = False\n",
    "    while not done:\n",
    "        \n",
    "        #picking up a random action from action space and current position\n",
    "        action = env.action_space.sample()\n",
    "        \n",
    "        #executing that action. This returns us next stage, the reward we got from taking that step, boolean value\n",
    "        #which indicates whether our episode is done or not and some additional debugging info\n",
    "        state, reward, done, info = env.step(action)\n",
    "        \n",
    "        epochs += 1\n",
    "        \n",
    "        #if the reward is -10, that means we have taken a wrong action and number of penalty is incremented by 1\n",
    "        total_rewards += reward\n",
    "    current_episode += 1\n",
    "    env.reset()\n",
    "print(\"Reward achieved {}\".format(total_rewards/float(num_episodes)))\n",
    "print(\"Avg time steps per episode {}\".format(epochs/float(num_episodes)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avg reward is very poor because the maximum reward we can from environment is 200 and also time steps are much more per episode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Build a Deep Q Network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Neural network architecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Deep Q Network is a deep neural network to model the q learning function for reinforcement learning. As the reward of environment is unknown to agent, it needs to explore environment rewards from taking different actions in various states in order build q network. It follows this equation:\n",
    "\n",
    "![https://s31.postimg.cc/tmim26kqx/q_learning_equation.png](https://s31.postimg.cc/tmim26kqx/q_learning_equation.png?dl=1)\n",
    "<br>\n",
    "\n",
    "So to model this function with q network, we need to approximate two outputs: values for each action in given state and individual q value for a single action in that state vector. So to build our network architecture we start with the state vector which we will pass through a dense layer acting as the hidden layer with a certain number of hidden nodes. Then we can pass that layer to another layer to transform it to have an output length to match the number of action available. This will be our vector of Q values for the input state. Then for the Q value for a single input action, we just want the value at the index corresponding to that action which we can get by multiplying this vector with an one hot coded action vector whichh has a 1 in the index of action and 0 elsewhere. Because as we have seen from about that action space is discrete and it has two value: 0 or 1. Then we get the sum to get a single value. So now, with our target value calculated from the above equation, we can calculate the mean squared error of the network's output with the target to get our loss."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Now we need to build our deep neural network model class.\"\"\"\n",
    "class DeepQNetwork():\n",
    "    \n",
    "    #this function takes state dimension as network size and action size as network output size\n",
    "    def __init__(self, state_dimension, action_size):\n",
    "        \n",
    "        #initializing input layer\n",
    "        self.state_input = tf.placeholder(tf.float32, shape=[None, *state_dimension])\n",
    "        \n",
    "        #initializing action layer\n",
    "        self.action_input = tf.placeholder(tf.int32, shape=[None])\n",
    "        \n",
    "        #initializing target q\n",
    "        self.q_target_input = tf.placeholder(tf.float32, shape=[None])\n",
    "        \n",
    "        #converting action to one hot encoded vector\n",
    "        action_one_hot_encoded = tf.one_hot(self.action_input, depth=action_size)\n",
    "        \n",
    "        \n",
    "        #we are initializing our hidden layer and then passing in the state to a dense layer\n",
    "        #with a 100 hidden units and ReLU as activation function \n",
    "        #because ReLU is sparsity and reduced likelihood of vanishing gradient.\n",
    "        self.hidden_layer1 = tf.layers.dense(self.state_input, 100, activation=tf.nn.relu)\n",
    "        \n",
    "        #getting the q value for each action in a state by passing it to another dense layer\n",
    "        #outputting action size unit\n",
    "        self.q_state = tf.layers.dense(self.hidden_layer1, action_size, activation=None)\n",
    "        \n",
    "        #then for our single Q value for state action comes from multiplying states Q values with the\n",
    "        #one hot action vector and then reducing this to a single value summing across the columns\n",
    "        self.q_state_action = tf.reduce_sum(tf.multiply(self.q_state, action_one_hot_encoded), axis=1)\n",
    "        \n",
    "        #our loss is the squared difference between the predicted q state action and q target\n",
    "        #Q target will be averaged of out of the batch\n",
    "        self.loss = tf.reduce_mean(tf.square(self.q_state_action - self.q_target_input))\n",
    "        \n",
    "        #for our optimizer,we are using adam optimizer with learning rate 0.001\n",
    "        self.optimizer = tf.train.AdamOptimizer(learning_rate=0.001).minimize(self.loss)\n",
    "        \n",
    "    def update_dqnmodel(self, session, state, action, q_target):\n",
    "        feed = {self.state_input: state, self.action_input: action, self.q_target_input: q_target}\n",
    "        session.run(self.optimizer, feed_dict=feed)\n",
    "    \n",
    "    #to get the q state output which take tf session and state as parameter\n",
    "    def obtain_q_state(self, session, state):\n",
    "        q_state = session.run(self.q_state, feed_dict={self.state_input: state})\n",
    "        return q_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"To stablize the model training time and result, we need to stable our model. So for that we can implement\n",
    "experience replay.\"\"\"\n",
    "\n",
    "class ExperienceReplay():\n",
    "    \n",
    "    #this function takes maximum of the buffer using collection's deque\n",
    "    def __init__(self, maxlen):\n",
    "        self.buffer = deque(maxlen=maxlen)\n",
    "    \n",
    "    #then we create a function to add experience to the buffer so that we can stable the time and result\n",
    "    def add(self, experience):\n",
    "        self.buffer.append(experience)\n",
    "    \n",
    "    \n",
    "    #then we create a function to sample the batch of experience tuples\n",
    "    def sample(self, batch_size):\n",
    "        \n",
    "        #saving batch size or minimum length of buffer in sample in case we have less buffer size then batch\n",
    "        sample_size = min(len(self.buffer), batch_size)\n",
    "        \n",
    "        #getting list randomly from buffer \n",
    "        sample = random.choices(self.buffer, k=sample_size)\n",
    "        \n",
    "        #to get all the result in list we unpack the sample and map it\n",
    "        return map(list, zip(*sample))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Defining agent class\"\"\"\n",
    "class DeepQNetworkAgent():\n",
    "    def __init__(self, env):\n",
    "        \n",
    "        #getting the state size from environment\n",
    "        self.state_dimension = env.observation_space.shape\n",
    "        \n",
    "        #getting the action size from the environment\n",
    "        self.action_size = env.action_space.n\n",
    "        \n",
    "        #initialing instance of deep q network\n",
    "        self.deep_q_network = DeepQNetwork(self.state_dimension, self.action_size)\n",
    "        self.experience_replay = ExperienceReplay(maxlen=10000)\n",
    "        self.gamma = 0.97\n",
    "        self.epsilon = 1.0\n",
    "        \n",
    "        #initializing session\n",
    "        self.sess = tf.Session()\n",
    "        \n",
    "        #initializing global variables\n",
    "        self.sess.run(tf.global_variables_initializer())\n",
    "        \n",
    "    #to get the updated action for given state using deep q network\n",
    "    #so agent needs to predict the action with the highest predicted q value\n",
    "    def get_action(self, state):\n",
    "        \n",
    "        #getting updated q state for certain action\n",
    "        q_state = self.deep_q_network.obtain_q_state(self.sess, [state])\n",
    "        \n",
    "        #getting the highest q value for that state\n",
    "        action_highest_q_value = np.argmax(q_state)\n",
    "        \n",
    "        #if we don't use epsilon model will select one action for each state and won't explore other actions\n",
    "        #For that, we tell our agent to initially explore the environment by selecting actions randomly earlier\n",
    "        #in training and gradually selecting the action greedily more often as the Q network moves closer to \n",
    "        #true estimate\n",
    "        \n",
    "        action_random = np.random.randint(self.action_size)\n",
    "        action = action_random if random.random() < self.epsilon else action_highest_q_value\n",
    "        \n",
    "        return action\n",
    "    \n",
    "    #target the q value and train the network\n",
    "    def trainAgent(self, state, action, next_state, reward, done):\n",
    "        \n",
    "        #adding experience in buffer\n",
    "        self.experience_replay.add((state, action, next_state, reward, done))\n",
    "        \n",
    "        #getting list of each experience type sampling from the buffer\n",
    "        states, actions, next_states, rewards, dones = self.experience_replay.sample(50)\n",
    "        \n",
    "        #getting the q for next state\n",
    "        q_next_state = self.deep_q_network.obtain_q_state(self.sess, next_states)\n",
    "        \n",
    "        #adjustment if there is no next state after the terminal state \n",
    "        q_next_state[dones] = np.zeros([self.action_size])\n",
    "        \n",
    "        #calculate targetted q value using mentioned equation\n",
    "        q_target = rewards + self.gamma * np.max(q_next_state, axis=1)\n",
    "        \n",
    "        #update the model\n",
    "        self.deep_q_network.update_dqnmodel(self.sess, states, actions, q_target)\n",
    "        \n",
    "        #we need to decrease epsilon after each episode because we want our model to trust its learning more\n",
    "        #after some learning\n",
    "        if done: \n",
    "            self.epsilon = max(0.1, 0.99*self.epsilon)\n",
    "    \n",
    "    #closing tensorflow session\n",
    "    def __del__(self):\n",
    "        self.sess.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solved!\n"
     ]
    }
   ],
   "source": [
    "dqn_agent = DeepQNetworkAgent(env)\n",
    "num_episodes = 400 #running for 400 episodes\n",
    "epochs = 0\n",
    "for ep in range(num_episodes):\n",
    "    state = env.reset()\n",
    "    total_reward = 0\n",
    "    done = False\n",
    "    while not done:\n",
    "        \n",
    "        #getting optimal action\n",
    "        action = dqn_agent.get_action(state)\n",
    "        \n",
    "        #getting all info\n",
    "        next_state, reward, done, info = env.step(action)\n",
    "        \n",
    "        #training the agent\n",
    "        dqn_agent.trainAgent(state, action, next_state, reward, done)\n",
    "#         env.render()\n",
    "        total_reward += reward\n",
    "        state = next_state\n",
    "        epochs += 1\n",
    "    #if our reward is more than 195 from 200, we will break the loop\n",
    "    if total_reward > 195:\n",
    "        print(\"Solved!\")\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reward achieved 200.0\n",
      "Avg time steps per episode 9.86\n"
     ]
    }
   ],
   "source": [
    "print(\"Reward achieved {}\".format(total_reward))\n",
    "print(\"Avg time steps per episode {}\".format(epochs/float(num_episodes)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, we have achieved highest reward with a few time steps using Deep Q Network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Discussion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compare agent performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table>\n",
    "    <thead>\n",
    "        <th></th>\n",
    "        <th>Initial Agent</th>\n",
    "        <th>Deep Q-Network Agent</th>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>Time steps</td>\n",
    "            <td>21.81</td>\n",
    "            <td>9.86</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>Reward achieved</td>\n",
    "            <td>21.81</td>\n",
    "            <td>200.0</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "As we can see from this performance table that, our agent learns better after implementing the Deep Q-Network method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Improvement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Hyperparameter tuning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://towardsdatascience.com/cartpole-introduction-to-reinforcement-learning-ed0eb5b58288\n",
    "- https://dev.to/n1try/cartpole-with-a-deep-q-network"
   ]
  },
  {
   "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}