Reinforcement_Learning.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Reinforcement Learning.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/SounakPal212/CPP/blob/master/Reinforcement_Learning.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-ADWvu7NKN2r",
        "colab_type": "text"
      },
      "source": [
        "##Reinforcement Learning\n",
        "The next and final topic in this course covers *Reinforcement Learning*. This technique is different than many of the other machine learning techniques we have seen earlier and has many applications in training agents (an AI) to interact with enviornments like games. Rather than feeding our machine learning model millions of examples we let our model come up with its own examples by exploring an enviornemt. The concept is simple. Humans learn by exploring and learning from mistakes and past experiences so let's have our computer do the same.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HGCR3JWQLaQb",
        "colab_type": "text"
      },
      "source": [
        "###Terminology\n",
        "Before we dive into explaining reinforcement learning we need to define a few key peices of terminology.\n",
        "\n",
        "**Enviornemt** In reinforcement learning tasks we have a notion of the enviornment. This is what our *agent* will explore. An example of an enviornment in the case of training an AI to play say a game of mario would be the level we are training the agent on.\n",
        "\n",
        "**Agent** an agent is an entity that is exploring the enviornment. Our agent will interact and take different actions within the enviornment. In our mario example the mario character within the game would be our agent. \n",
        "\n",
        "**State** always our agent will be in what we call a *state*. The state simply tells us about the status of the agent. The most common example of a state is the location of the agent within the enviornment. Moving locations would change the agents state.\n",
        "\n",
        "**Action** any interaction between the agent and enviornment would be considered an action. For example, moving to the left or jumping would be an action. An action may or may not change the current *state* of the agent. In fact, the act of doing nothing is an action as well! The action of say not pressing a key if we are using our mario example.\n",
        "\n",
        "**Reward** every action that our agent takes will result in a reward of some magnitude (positive or negative). The goal of our agent will be to maximize its reward in an enviornment. Sometimes the reward will be clear, for example if an agent performs an action which increases their score in the enviornment we could say they've recieved a positive reward. If the agent were to perform an action which results in them losing score or possibly dying in the enviornment then they would recieve a negative reward. \n",
        "\n",
        "The most important part of reinforcement learning is determing how to reward the agent. After all, the goal of the agent is to maximize its rewards. This means we should reward the agent appropiatly such that it reaches the desired goal.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AoOJy9s4ZJJt",
        "colab_type": "text"
      },
      "source": [
        "###Q-Learning\n",
        "Now that we have a vague idea of how reinforcement learning works it's time to talk about a specific technique in reinforcement learning called *Q-Learning*.\n",
        "\n",
        "Q-Learning is a simple yet quite powerful technique in machine learning that involves learning a matrix of action-reward values. This matrix is often reffered to as a Q-Table or Q-Matrix. The matrix is in shape (number of possible states, number of possible actions) where each value at matrix[n, m] represents the agents expected reward given they are in state n and take action m. The Q-learning algorithm defines the way we update the values in the matrix and decide what action to take at each state. The idea is that after a succesful training/learning of this Q-Table/matrix we can determine the action an agent should take in any state by looking at that states row in the matrix and taking the maximium value column as the action.\n",
        "\n",
        "**Consider this example.**\n",
        "\n",
        "Let's say A1-A4 are the possible actions and we have 3 states represented by each row (state 1 - state 3).\n",
        "\n",
        "| A1  | A2  | A3  | A4  |\n",
        "|:--: |:--: |:--: |:--: |\n",
        "|  0  |  0  | 10  |  5  |\n",
        "|  5  | 10  |  0  |  0  |\n",
        "| 10  |  5  |  0  |  0  |\n",
        "\n",
        "If that was our Q-Table/matrix then the following would be the preffered actions in each state.\n",
        "\n",
        "> State 1: A3\n",
        "\n",
        "> State 2: A2\n",
        "\n",
        "> State 3: A1\n",
        "\n",
        "We can see that this is because the values in each of those columns are the highest for those states!\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "u5uLpN1yemTx",
        "colab_type": "text"
      },
      "source": [
        "###Learning the Q-Table\n",
        "So that's simple, right? Now how do we create this table and find those values. Well this is where we will dicuss how the Q-Learning algorithm updates the values in our Q-Table. \n",
        "\n",
        "I'll start by noting that our Q-Table starts of with all 0 values. This is because the agent has yet to learn anything about the enviornment. \n",
        "\n",
        "Our agent learns by exploring the enviornment and observing the outcome/reward from each action it takes in each state. But how does it know what action to take in each state? There are two ways that our agent can decide on which action to take.\n",
        "1. Randomly picking a valid action\n",
        "2. Using the current Q-Table to find the best action.\n",
        "\n",
        "Near the beginning of our agents learning it will mostly take random actions in order to explore the enviornment and enter many different states. As it starts to explore more of the enviornment it will start to gradually rely more on it's learned values (Q-Table) to take actions. This means that as our agent explores more of the enviornment it will develop a better understanding and start to take \"correct\" or better actions more often. It's important that the agent has a good balance of taking random actions and using learned values to ensure it does get trapped in a local maximum. \n",
        "\n",
        "After each new action our agent wil record the new state (if any) that it has entered and the reward that it recieved from taking that action. These values will be used to update the Q-Table. The agent will stop taking new actions only once a certain time limit is reached or it has acheived the goal or reached the end of the enviornment. \n",
        "\n",
        "####Updating Q-Values\n",
        "The formula for updating the Q-Table after each action is as follows:\n",
        "> $ Q[state, action] = Q[state, action] + \\alpha * (reward + \\gamma * max(Q[newState, :]) - Q[state, action]) $\n",
        "\n",
        "- $\\alpha$ stands for the **Learning Rate**\n",
        "\n",
        "- $\\gamma$ stands for the **Discount Factor**\n",
        "\n",
        "####Learning Rate $\\alpha$\n",
        "The learning rate $\\alpha$ is a numeric constant that defines how much change is permitted on each QTable update. A high learning rate means that each update will introduce a large change to the current state-action value. A small learning rate means that each update has a more subtle change. Modifying the learning rate will change how the agent explores the enviornment and how quickly it determines the final values in the QTable.\n",
        "\n",
        "####Discount Factor $\\gamma$\n",
        "Discount factor also know as gamma ($\\gamma$) is used to balance how much focus is put on the current and future reward. A high discount factor means that future rewards will be considered more heavily.\n",
        "\n",
        "<br/>\n",
        "<p>To perform updates on this table we will let the agent explpore the enviornment for a certain period of time and use each of its actions to make an update. Slowly we should start to notice the agent learning and choosing better actions. </p>\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rwIl0sJgmu4D",
        "colab_type": "text"
      },
      "source": [
        "##Q-Learning Example\n",
        "For this example we will use the Q-Learning algorithm to train an agent to navigate a popular enviornment from the [Open AI Gym](https://gym.openai.com/). The Open AI Gym was developed so programmers could practice machine learning using unique enviornments. Intersting fact, Elon Musk is one of the founders of OpenAI!\n",
        "\n",
        "Let's start by looking at what Open AI Gym is. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rSETF0zqokYr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import gym   # all you have to do to import and use open ai gym!"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8cH3AmCzotO1",
        "colab_type": "text"
      },
      "source": [
        "Once you import gym you can load an enviornment using the line ```gym.make(\"enviornment\")```."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UKN1ScBco3dp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "env = gym.make('FrozenLake-v0')  # we are going to use the FrozenLake enviornment"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3SvSlmVwo8cY",
        "colab_type": "text"
      },
      "source": [
        "There are a few other commands that can be used to interact and get information about the enviornment."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FF3icIeapFct",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(env.observation_space.n)   # get number of states\n",
        "print(env.action_space.n)   # get number of actions"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lc9cwp03pQVn",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "env.reset()  # reset enviornment to default state"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sngyjPDapUt7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "action = env.action_space.sample()  # get a random action "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HeEfi8xypXya",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "new_state, reward, done, info = env.step(action)  # take action, notice it returns information about the action"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_1W3D81ipdaS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "env.render()   # render the GUI for the enviornment "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vmW6HAbQp01f",
        "colab_type": "text"
      },
      "source": [
        "###Frozen Lake Enviornment\n",
        "Now that we have a basic understanding of how the gym enviornment works it's time to discuss the specific problem we will be solving.\n",
        "\n",
        "The enviornment we loaded above ```FrozenLake-v0``` is one of the simplest enviornments in Open AI Gym. The goal of the agent is to navigate a frozen lake and find the Goal without falling through the ice (render the enviornment above to see an example).\n",
        "\n",
        "There are:\n",
        "- 16 states (one for each square) \n",
        "- 4 possible actions (LEFT, RIGHT, DOWN, UP)\n",
        "- 4 different types of blocks (F: frozen, H: hole, S: start, G: goal)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YlWoK75ZrK2b",
        "colab_type": "text"
      },
      "source": [
        "###Building the Q-Table\n",
        "The first thing we need to do is build an empty Q-Table that we can use to store and update our values."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r767K4s0rR2p",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import gym\n",
        "import numpy as np\n",
        "import time\n",
        "\n",
        "env = gym.make('FrozenLake-v0')\n",
        "STATES = env.observation_space.n\n",
        "ACTIONS = env.action_space.n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UAzMWGatrVIk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "Q = np.zeros((STATES, ACTIONS))  # create a matrix with all 0 values \n",
        "Q"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vc_h8tLSrpmc",
        "colab_type": "text"
      },
      "source": [
        "###Constants\n",
        "As we discussed we need to define some constants that will be used to update our Q-Table and tell our agent when to stop training."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-FQapdnnr6P1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "EPISODES = 2000 # how many times to run the enviornment from the beginning\n",
        "MAX_STEPS = 100  # max number of steps allowed for each run of enviornment\n",
        "\n",
        "LEARNING_RATE = 0.81  # learning rate\n",
        "GAMMA = 0.96"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NxrAj91rsMfm",
        "colab_type": "text"
      },
      "source": [
        "###Picking an Action\n",
        "Remember that we can pick an action using one of two methods:\n",
        "1. Randomly picking a valid action\n",
        "2. Using the current Q-Table to find the best action.\n",
        "\n",
        "Here we will define a new value $\\epsilon$ that will tell us the probabillity of selecting a random action. This value will start off very high and slowly decrease as the agent learns more about the enviornment."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YUAQVyX0sWDb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "epsilon = 0.9  # start with a 90% chance of picking a random action\n",
        "\n",
        "# code to pick action\n",
        "if np.random.uniform(0, 1) < epsilon:  # we will check if a randomly selected value is less than epsilon.\n",
        "    action = env.action_space.sample()  # take random action\n",
        "else:\n",
        "    action = np.argmax(Q[state, :])  # use Q table to pick best action based on current values"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5n-i0B7Atige",
        "colab_type": "text"
      },
      "source": [
        "###Updating Q Values\n",
        "The code below implements the formula discussed above."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9r7R1W6Qtnh8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "Q[state, action] = Q[state, action] + LEARNING_RATE * (reward + GAMMA * np.max(Q[new_state, :]) - Q[state, action])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "__afaD62uh8G",
        "colab_type": "text"
      },
      "source": [
        "###Putting it Together\n",
        "Now that we know how to do some basic things we can combine these together to create our Q-Learning algorithm,"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AGiYCiNuutHz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import gym\n",
        "import numpy as np\n",
        "import time\n",
        "\n",
        "env = gym.make('FrozenLake-v0')\n",
        "STATES = env.observation_space.n\n",
        "ACTIONS = env.action_space.n\n",
        "\n",
        "Q = np.zeros((STATES, ACTIONS))\n",
        "\n",
        "EPISODES = 1500 # how many times to run the enviornment from the beginning\n",
        "MAX_STEPS = 100  # max number of steps allowed for each run of enviornment\n",
        "\n",
        "LEARNING_RATE = 0.81  # learning rate\n",
        "GAMMA = 0.96\n",
        "\n",
        "RENDER = False # if you want to see training set to true\n",
        "\n",
        "epsilon = 0.9\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jFRtn5dUu5ZI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "rewards = []\n",
        "for episode in range(EPISODES):\n",
        "\n",
        "  state = env.reset()\n",
        "  for _ in range(MAX_STEPS):\n",
        "    \n",
        "    if RENDER:\n",
        "      env.render()\n",
        "\n",
        "    if np.random.uniform(0, 1) < epsilon:\n",
        "      action = env.action_space.sample()  \n",
        "    else:\n",
        "      action = np.argmax(Q[state, :])\n",
        "\n",
        "    next_state, reward, done, _ = env.step(action)\n",
        "\n",
        "    Q[state, action] = Q[state, action] + LEARNING_RATE * (reward + GAMMA * np.max(Q[next_state, :]) - Q[state, action])\n",
        "\n",
        "    state = next_state\n",
        "\n",
        "    if done: \n",
        "      rewards.append(reward)\n",
        "      epsilon -= 0.001\n",
        "      break  # reached goal\n",
        "\n",
        "print(Q)\n",
        "print(f\"Average reward: {sum(rewards)/len(rewards)}:\")\n",
        "# and now we can see our Q values!"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Zo-tNznd65US",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# we can plot the training progress and see how the agent improved\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "def get_average(values):\n",
        "  return sum(values)/len(values)\n",
        "\n",
        "avg_rewards = []\n",
        "for i in range(0, len(rewards), 100):\n",
        "  avg_rewards.append(get_average(rewards[i:i+100])) \n",
        "\n",
        "plt.plot(avg_rewards)\n",
        "plt.ylabel('average reward')\n",
        "plt.xlabel('episodes (100\\'s)')\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gy4YH2m9s1ww",
        "colab_type": "text"
      },
      "source": [
        "##Sources\n",
        "1. Violante, Andre. “Simple Reinforcement Learning: Q-Learning.” Medium, Towards Data Science, 1 July 2019, https://towardsdatascience.com/simple-reinforcement-learning-q-learning-fcddc4b6fe56.\n",
        "\n",
        "2. Openai. “Openai/Gym.” GitHub, https://github.com/openai/gym/wiki/FrozenLake-v0."
      ]
    }
  ]
}