Deep_Reinforcement_Learning_Part_3_.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Deep Reinforcement Learning- Part-3 .ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PATe-8dtmfVs",
        "colab_type": "text"
      },
      "source": [
        "This is the Part-3 of Deep Reinforcement Learning Notebook series.***In this Notebook I have introduced introduces our first Value-based Algorithm known as SARSA***.\n",
        "\n",
        "\n",
        "The Notebook series is about Deep RL algorithms so it excludes all other techniques that can be used to learn functions in reinforcement learning and also the Notebook Series is not exhaustive i.e. it contains the most widely used Deep RL algorithms only.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8txpwAVSmpAM",
        "colab_type": "text"
      },
      "source": [
        "Value-based algorithms evaluate state-action pairs (s, a) by learning one of the value functions — $V^π(s) or Q^π(s, a)$— and use these evaluations to select action.Learning value functions stands in contrast to REINFORCE(which we discussed in Notebook-2 in this series) in which an agent directly learns a policy which maps states to actions\n",
        "The SARSA algorithm learns $Q^π(s, a)$, however other algorithms such as the Actor-Critic algorithm learns $V^π(s)$. Hence first and foremost we will discuss why learning $Q^π(s, a)$ is a good choice in this case.The SARSA algorithm consists of two core ideas. First, a technique for learning the Q-function known as Temporal Difference (TD) learning. It is an alternative to Monte Carlo sampling for estimating state or state-action values from the experiences an agent gathers in an environment.Second, a method for generating actions using the Q-function.\n",
        "This also raises the question of how agents discover good actions with the help of value-function. One of the fundamental challenges in RL is how to achieve a good balance between exploiting what an agent knows and exploring the environment in order to learn more. This is known as the exploration-exploitation tradeoff, and is covered later in this notebook. We also introduce a simple approach for solving this problem — an ∊-greedy policy.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bBJxJ3GonbPn",
        "colab_type": "text"
      },
      "source": [
        "#Why a SARSA learns the Q-function instead of the V -function\n",
        "Lets us first define the Q-function and the V-function.\n",
        "\n",
        "\n",
        "The Q-function measures the value of state-action pairs (s, a) under a particular policy π.The value of (s, a) is the expected cumulative discounted reward from taking action a in state s, and then continuing to act under the policy π.\n",
        "\n",
        "$V^π(s)$ measures the value of states s under a particular policy π.\n",
        "The value of a state $V^π(s)$, is the expected cumulative discounted reward from that state s onwards under a specific policy π.$Q^π(s, a)$ is closely related to $V^π(s)$. $V^π(s)$ is the expectation over the Q-values for all of the actions a available in a particular state s under the policy π.\n",
        "\n",
        "Q and V functions are defined by below equations:\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-03%20at%208.10.25%20PM.png?raw=true)\n",
        "\n",
        "Equations 3.1\n",
        "\n",
        "Relation between V and Q is show below in Equation 3.2:\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-06%20at%203.59.46%20PM.png?raw=true)\n",
        "\n",
        "Equation 3.2\n",
        "\n",
        "Value functions are always defined with respect to a particular policy π, which is why they are denoted with the π superscript. The reason behind it is because $Q^π(s, a)$ depends on the sequences of rewards an agent can expect to experience after taking action a in state s. The rewards depend on the future sequences of states and actions, and these depend on a policy. Different policies may generate different future action sequences given (s, a), which may result in different rewards."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A2DTFjTNrmS2",
        "colab_type": "text"
      },
      "source": [
        "# Intuition about V-function and Q-Function\n",
        "Let’s first put this in context by considering the game of chess from one player's perspective. This player can be represented as a policy π. A certain configuration of the chessboard pieces is a state s. A good chess player will have an intuition about whether π certain chess positions are good or bad. $V^π(s)$ is this intuition expressed quantitatively with a number.\n",
        "We can consider the next state s′ from a legal move a, calculate $V^π(s′)$ for each of these next states, and select the action leading to the best s'.\n",
        "\n",
        "In addition to evaluating positions, a chess player will also consider many alternative moves and the likely consequences of making them. $Q^π$(s, a) provides a quantitative value for each move. This value can be used to decide on the best move (action) to make in a particular position (state).\n",
        "# Prons and Cons of Q and V function\n",
        "The action selection form V-function is time-consuming and relies on knowing the transition function, which is not available for many environments.\n",
        "\n",
        "$Q^π(s, a)$ has the benefit of giving agents a direct method for acting. Agents can calculate $Q^π(s, a)$ for each of the actions a ∈ $A_s$ available in a particular state s, and select the action with the maximum value. In the optimal case, $Q^π(s, a)$ represents the optimal expected value from taking action a in state s, denoted Q(s, a). It represents the best you could possibly do if you acted optimally in all subsequent states. Knowing Q(s, a) therefore yields an optimal policy.\n",
        "\n",
        "The disadvantage of learning $Q^π(s, a)$ is that the function approximation is more computationally complex, and requires more data to learn from when compared with $V^π(s)$. Learning a good estimate for $V^π(s)$ requires that the data covers the state space reasonably well, whereas learning a good estimate for $Q^π(s, a)$ requires that data covers all (s, a) pairs, not just all states s. The combined state-action space is often significantly larger than the state space and so more data is needed to learn a good Q-function estimate.\n",
        "\n",
        "$V^π(s)$ maybe a simpler function to approximate but it has one significant disadvantage. To use $V^π(s)$ to choose actions, agents need to be able to take each of the available actions a ∈ $A_s$ in a state s, and observe the next state the environment transitions to $s^{′2}$, along with the next reward r. Then an agent can act optimally by selecting the action which led to the largest expected cumulative discounted rewards E[r + $V^π$ (s′)]. However, if state transitions are stochastic (taking action a in state s can result in different next states s′) the agent may need to repeat this process many times to get a good estimation of the expected value of taking a particular action. This is a potentially computationally expensive process.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GmRf0Q6nvzoA",
        "colab_type": "text"
      },
      "source": [
        "# TEMPORAL DIFFERENCE LEARNING\n",
        "The main idea is to use a neural network that produces Q-value estimates given (s, a) pairs as inputs. This is known as a value network.\n",
        "The workflow for learning the value network parameters goes as follows: generate trajectories τ s and predict a $Q_@$ value for each (s, a) pair. Then use the trajectories to generate target Q-values $Q_{tar}$. Finally, minimize the distance between $Q_@$ and $Q_{tar}$ using a standard regression loss such as MSE (mean squared error). Repeat this process many times.\n",
        "\n",
        "TD learning is how we will produce the target values $Q_{tar}$ in SARSA. To motivate this, it is helpful to consider how it can be done with Monte Carlo sampling(which was discussed in notebook-part-2 of this series).\n",
        "\n",
        "Given N trajectories $τ_i$, i∈ {1, . . . , N} starting in state s, where the agent took action a, the Monte Carlo (MC) estimate of $Q^π_{tar}$\n",
        "(s, a) is the average of all the trajectories’ returns shown in below Equation 3.3\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-06%20at%204.47.59%20PM.png?raw=true)\n",
        "\n",
        "Equation 3.3\n",
        "\n",
        "\n",
        "If we have access to an entire trajectory $τ_i$, it is possible to calculate the actual Q-value the agent received in that particular case for each (s, a) pair in $τ_i$. This follows from the definition of the Q-function since the expectation of future cumulative discounted rewards from a single example is just the cumulative discounted reward from the current time step to the end of the episode for that example. Equation 3.3 shows that this is also the Monte Carlo estimate for $Q^π(s, a)$ where the number of trajectories used in the estimate is equal to N = 1. Now each (s, a) pair in the dataset is associated with a target Q- value. The dataset can be said to be “labeled” since each datapoint (s, a) has a corresponding target value $Q^π_{tar}(s, a)$.\n",
        "\n",
        "One disadvantage of Monte Carlo sampling is that an agent has to wait for episodes to end before any of the data from that episode can be used to learn from. This is evident from Equation 3.3. To calculate $Q^π_{tarMC}(s, a)$, the rewards for the remainder of the trajectory starting from (s, a) are required. Episodes might have many time steps as measured by T, delaying training. This motivates an alternative approach to learning Q-values, TD learning.\n",
        "\n",
        "The key insight in TD learning is that Q-values for the current time step can be defined in terms of Q-values of the next time step. That is, $Q^π(s, a)$ is defined recursively as shown below in Equation 3.4\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-06%20at%204.53.45%20PM.png?raw=true)\n",
        "\n",
        "Equation 3.4"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1_4CKv1V4r8I",
        "colab_type": "text"
      },
      "source": [
        "The equation 3.4 is known as Bellman equation.If the Q- function is correct for the policy π Equation 3.4 holds exactly. It also suggests a way of learning Q-values. We just saw how Monte Carlo sampling can be used to learn $Q^π(s, a)$ given many trajectories of experiences. The same idea can be applied here, using TD learning to derive the target value $Q^π_{tar}(s,a)$  for each (s, a) pair.Assume we have a neural network to represent the Q-function.In TD learning, $Q^π_{tar}(s_t,a_t)$ is derived by estimating the right hand side of Equation 3.4 using the Q-function(obtained by neural network).Each training iteration, $Q^π_@(s_t,a_t)$ is updated to bring it closer to $Q^π_{tar}(s_t,a_t)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "obRCZbcP6gLd",
        "colab_type": "text"
      },
      "source": [
        "# Problems with Equation 3.4\n",
        "There are two problems with Equation 3.4 if it is to be used to construct $Q^π_{tar}(s_t,a_t)$— the two expectations. \n",
        "\n",
        "The first problem is the outer expectation. This can be illustrated by supposing we had collections of trajectories, {$τ_1, τ_2, . . . , τ_M$}. Each trajectory $τ_i$ contains (s, a, r, s′) tuples. For each tuple (s, a, r, s′), only one example of the next state s′, is available given the action selected.\n",
        "If the environment is deterministic then it is correct to only consider the actual next state when calculating the expectation over the next states. However, if the environment is stochastic, this breaks down. Taking action a in states s could transition the environment into several different next states, but only one next state was actually observed at each step. This problem can be overcome by considering only one example — the one that actually happened. This does mean that the Q-value estimate may have high variance if the environment is stochastic, but helps make the estimation more tractable. Using just one example to estimate the distribution over the next states s′ and rewards s, we can take the outer expectation out and the Bellman equation can be rewritten as shown below in Equation 3.5.\n",
        "\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-06%20at%205.09.47%20PM.png?raw=true)\n",
        "\n",
        "Equation 3.5\n",
        "\n",
        "The second problem is the inner expectation of Equation 3.4 over the actions. We have access to the Q-value estimates for all of the actions in the next state s′ because we are using the current estimate of the Q-function to calculate the values. The problem arises from not knowing the probability distributions over actions that are needed to calculate the expectation. There are two ways to solve this, each of which corresponds to a different algorithm; SARSA and DQN(DQN will be discussed in Notebook-4 of this series).SARSA’s solution is to use the action actually taken in the next state, a′ (Equation 3.6). Over the course of many examples, the proportion of actions selected should approximate the\n",
        "probability distribution over actions, given states. DQN’s\n",
        "solution is to use the maximum valued Q-value (Equation 3.7).\n",
        "A third alternative is to derive the probability distribution over actions from the policy and calculate the expectation. This algorithm is known as expected SARSA. This corresponds to an implicit policy of selecting the action with the maximum Q-value with probability 1. As we will see in\n",
        "Notebook-4 the implicit policy in Q-learning is greedy with\n",
        "respect to Q-values, and so the transformation of the equation is valid.\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-06%20at%205.14.04%20PM.png?raw=true)\n",
        "\n",
        "Equation 3.6\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-06%20at%205.14.14%20PM.png?raw=true)\n",
        "\n",
        "Equation 3.7\n",
        "\n",
        "Now  $Q^π_{tar}(s_t,a_t)$ can be calculated using the right hand side Equation 3.6 for each tuple (s,a,r,s,a)\n",
        "\n",
        "Notice that only the information from the next step in the environment was required to calculate the target Q-values instead of a whole episode’s trajectory. This makes it possible to update the Q-function in a batched (after a few examples) or online (after one example) manner when using TD learning instead of having to wait for an entire trajectory to finish.\n",
        "TD learning is a bootstrapped learning method because the existing estimate of Q-values for  (s, a) pair are used when calculating $Q^π_{tar}(s_t,a_t)$. This has the advantage of lowering the variance of the estimate when compared to Monte Carlo sampling. TD learning only uses the actual reward r, from the next state s′, and combines it with Q-value estimates to approximate the remaining part of the value. The Q-function represents an expectation over different trajectories and so typically has a lower variance than the whole trajectory used by Monte Carlo sampling. However, it also introduces bias into the learning approach since the Q-function approximator is not perfect."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E4d7GTZPSQKE",
        "colab_type": "text"
      },
      "source": [
        "# ACTION SELECTION IN SARSA \n",
        "TD learning gives us a method for learning how to evaluate actions. What is missing is a policy, a mechanism for selecting actions. Suppose we had already learned the optimal Q-function. Then the value of each state-action pair will represent the best possible expected value from taking that action. This gives us a way to reverse engineer the optimal way of acting. If the agent always selects the action which corresponds to the maximum Q-\n",
        "value in each state, if the agent acts greedily with respect to the Q-values, then it will be acting optimally. This also implies that the SARSA algorithm is limited to discrete action spaces(To identify the maximum Q-value in state s, we need to compute the Q-values for all the possible actions in that state. When actions are discrete, this is straightforward because we can list all the possible actions and compute their Q-value. However, when actions are continuous, the actions cannot be fully enumerated, and this becomes a problem. For this reason, SARSA and other value-based methods are generally restricted to only discrete action spaces. However, there are methods such as QT– Opt which approximate the maximum Q-value by sampling from a continuous action space. We will not cover QT-Opt in this series).\n",
        "\n",
        "\n",
        "Unfortunately, the optimal Q-function is typically not known. However, the relationship between the optimal Q-function and acting optimally tells us that if we have a good Q-function then we can derive a good policy. It also suggests an iterative approach to improving the Q-value.\n",
        "First, randomly initialize a neural network with parameters θ to represent the Q-function, denoted $Q^π(s, a; θ)$ Then repeat the following steps until the agent stops improving, as evaluated by the total un-discounted5 cumulative rewards received during an episode.\n",
        "1. Use $Q^π(s, a; θ)$ to act in the environment, by acting greedily with respect to the Q-values. Store all of the (s, a, r, s′) experiences.\n",
        "2. Use the stored experiences to update Qπ(s, a; θ) using the SARSA Bellman equation (Equation 3.6). This improves the Q-function estimate, which in turn improves the policy since the Q-value estimates are now better.\n",
        "\n",
        "# Exploration and Exploitation\n",
        "One issue with acting greedily with respect to the Q-values is that it is deterministic, which means that an agent may not explore the entire state-action space sufficiently. If an agent always selects the same action a in state s, then there may be many (s, a) pairs that an agent never experiences. This can result in the Q-function estimates for some (s, a) pairs being inaccurate since they were randomly initialized and there were no experiences of (s, a). So there is no opportunity for a network to learn about this part of the state-action space. Consequently, the agent may make suboptimal actions and get stuck in local minima.\n",
        "\n",
        "To mitigate this issue, it is common to use an ∊-greedy policy instead of a purely greedy policy for the agent. Under this policy, an agent selects the greedy action with probability 1 – ∊, and acts randomly with probability ∊. So ∊ is known as the exploration probability since the acting randomly ∊× 100% of the time helps an agent explore the state-action space. Unfortunately, this comes at a cost. Now the policy may not be as good as the greedy policy because the agent is taking random actions with non-zero probability instead of the Q-value maximizing action.\n",
        "\n",
        "\n",
        "The tension between the potential value of exploring during training and taking the best actions based on the information available to an agent (Q-values) is known as the exploration-exploitation trade-off. A common approach to managing this trade-off is to start with high ∊, 1.0, or close to this so that the agent acts almost randomly and rapidly explores the state-action space. Also, the agent has not learned anything at the beginning of training so there is nothing to exploit. Overtime ∊ is gradually decayed so that after many steps the policy hopefully approaches the optimal policy. As the agent learns better Q-function and so better policies, there is less benefit to exploring and the agent should act more greedily. In the ideal case, the agent will have discovered the optimal Q- function after some time and so ∊ can be reduced to 0. In practice, due to limited time, continuous or high dimensional discrete state spaces, and non-linear function approximators the learned Q-function does not converge to the optimal policy. Instead ∊ is typically annealed to a small value, \n",
        "0.1 – 0.001, for example, and fixed to allow a small amount of continued exploration.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QH9d3iVQfizb",
        "colab_type": "text"
      },
      "source": [
        "# **SARSA ALGORITHM**\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-07%20at%207.07.44%20PM.png?raw=true)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "log14s_1iFZY",
        "colab_type": "text"
      },
      "source": [
        "# **IMPLEMENTING SARSA**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o_0e9uW__Hdp",
        "colab_type": "text"
      },
      "source": [
        "Below is the implementation in code of this algorithm on a simple example of Cliff-Walking where agent tries to "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pp3qnViHAQrO",
        "colab_type": "text"
      },
      "source": [
        "Below code setups the environment required to run the game."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YXaahb2vATSP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Installing the dependencies\n",
        "!pip install gym\n",
        "!apt-get install python-opengl -y\n",
        "!apt install xvfb -y"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FEvs7kGpAXpr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!pip install gym[atari]\n",
        "!pip install pyvirtualdisplay\n",
        "!pip install piglet"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7Xvjn8HsAapx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from pyvirtualdisplay import Display\n",
        "display = Display(visible=0, size=(1400, 900))\n",
        "display.start()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4VfPSzr0Ac8r",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# This code creates a virtual display to draw game images on. \n",
        "# If you are running locally, just ignore it\n",
        "import os\n",
        "if type(os.environ.get(\"DISPLAY\")) is not str or len(os.environ.get(\"DISPLAY\"))==0:\n",
        "    !bash ../xvfb start\n",
        "    %env DISPLAY=:1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PTGMaqtpAfDO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import tensorflow as tf\n",
        "from tensorflow.keras.layers import Dense\n",
        "from tensorflow.keras.models import Sequential\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "%matplotlib inline\n",
        "import random\n",
        "from IPython import display\n",
        "from gym import logger as gymlogger\n",
        "from gym.wrappers import Monitor\n",
        "gymlogger.set_level(40) # error only\n",
        "import tensorflow as tf\n",
        "import numpy as np\n",
        "import random\n",
        "import matplotlib\n",
        "import matplotlib.pyplot as plt\n",
        "%matplotlib inline\n",
        "import math\n",
        "import glob\n",
        "import io\n",
        "import base64\n",
        "from IPython.display import HTML\n",
        "from IPython.display import clear_output\n",
        "\n",
        "from IPython import display as ipythondisplay"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2gcjUYiSAjon",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\"\n",
        "Utility functions to enable video recording of gym environment and displaying it\n",
        "To enable video, just do \"env = wrap_env(env)\"\"\n",
        "\"\"\"\n",
        "\n",
        "def show_video():\n",
        "  mp4list = glob.glob('video/*.mp4')\n",
        "  if len(mp4list) > 0:\n",
        "    mp4 = mp4list[0]\n",
        "    video = io.open(mp4, 'r+b').read()\n",
        "    encoded = base64.b64encode(video)\n",
        "    ipythondisplay.display(HTML(data='''<video alt=\"test\" autoplay \n",
        "                loop controls style=\"height: 400px;\">\n",
        "                <source src=\"data:video/mp4;base64,{0}\" type=\"video/mp4\" />\n",
        "             </video>'''.format(encoded.decode('ascii'))))\n",
        "  else: \n",
        "    print(\"Could not find video\")\n",
        "    \n",
        "\n",
        "def wrap_env(env):\n",
        "  env = Monitor(env, './video', force=True)\n",
        "  return env"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1B_fXupQAl86",
        "colab_type": "text"
      },
      "source": [
        "This part ensures the reproducibility of the code below by using a random seed and setups the environment."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dHkBUrFbAllU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import gym.envs.toy_text \n",
        "RANDOM_SEED=1\n",
        "N_EPISODES=500\n",
        "\n",
        "# random seed (reproduciblity)\n",
        "np.random.seed(RANDOM_SEED)\n",
        "tf.random.set_seed(RANDOM_SEED)\n",
        "\n",
        "# set the env\n",
        "env=gym.envs.toy_text.CliffWalkingEnv() # env to import\n",
        "#env=wrap_env(env)\n",
        "env.seed(RANDOM_SEED)\n",
        "env.reset() # reset to env"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-5A1sy6phz1-",
        "colab_type": "text"
      },
      "source": [
        "Defining the SARSA Class\n",
        "At initiation, the SARSA object sets a few parameters. First, is the environment in which the model learns and its properties. Second, are both the parameters of the REINFORCE algorithm — Gamma (𝛾) , alpha (𝛼) and epsilon(∊). Gamma, is the decay rate of past observations,alpha is the learning rate by which the gradients affect the policy update and epsilon is the value used for ∊-greedy policy.\n",
        "Lastly, it sets the learning rate for the neural network."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wxTe5mcZAuON",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Sarsa:\n",
        "\n",
        "  def __init__(self, env, path=None):\n",
        "    self.env=env #import env\n",
        "    self.state_shape=(1,) # the state space\n",
        "    self.action_shape=env.action_space.n # the action space\n",
        "    self.gamma=[0.99] # decay rate of past observations\n",
        "    self.alpha=1e-4 # learning rate in the policy gradient\n",
        "    self.learning_rate=0.01 # learning rate in deep learning\n",
        "    self.epsilon_initial_value=1.0 # initial value of epsilon\n",
        "    self.epsilon_current_value=1.0 # current value of epsilon\n",
        "    self.epsilon_final_value=0.0001 # final value of epsilon\n",
        "  \n",
        "    if not path:\n",
        "      self.model=self._create_model() #build model\n",
        "    else:\n",
        "      self.model=load_model(path) #import model"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R_I-ONrTjlME",
        "colab_type": "text"
      },
      "source": [
        "Creating a Neural Network Model\n",
        "I chose to use a neural network to implement this agent. The network is a simple feedforward network with a few hidden layers. The output layer incorporates a softmax activation.The model takes the state as input and outputs Q(s,a) values for that state following the current policy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QVmVpRKajibY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\n",
        "  def _create_model(self):\n",
        "    ''' builds the model using keras'''\n",
        "    model=Sequential()\n",
        "\n",
        "    # input shape is of observations\n",
        "    model.add(Dense(64, activation=\"relu\",input_shape=self.state_shape))\n",
        "    # add a relu layer \n",
        "    model.add(Dense(32, activation=\"relu\"))\n",
        "\n",
        "    # output shape is according to the number of action\n",
        "    # The softmax function outputs a probability distribution over the actions\n",
        "    model.add(Dense(env.action_space.n, activation=\"softmax\")) \n",
        "    model.compile(loss=\"CategoricalCrossentropy\",\n",
        "            optimizer=tf.keras.optimizers.Adam(learning_rate=self.learning_rate))\n",
        "    return model"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LJyMm9TfBPwB",
        "colab_type": "text"
      },
      "source": [
        "Action Selection\n",
        "The get_action method guides its action choice. It uses ∊-greedy policy for choosing the action. Initially, since the value of ∊ is high agent choose randomly but later in training the agent chooses the actions that produces maximum Q value."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gCyoPHA2kXpM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def get_action(self, state):\n",
        "        '''samples the next action based on the E-greedy policy'''\n",
        "\n",
        "        state=int(state)\n",
        "        state=np.array([state],dtype='float32')\n",
        "        state=tf.convert_to_tensor(state)\n",
        "        x=random.random()\n",
        "        if x < self.epsilon_current_value: \n",
        "          action=random.randrange(0,4) #Exlporation\n",
        "          q_values=self.model.predict(state)\n",
        "          \n",
        "          q_act=q_values[0][action]\n",
        "\n",
        "        else:\n",
        "          q_values=self.model.predict(state) #Exploitation\n",
        "          max_Q = np.argmax(q_values)\n",
        "          action = max_Q\n",
        "          q_act=q_values[0][action]\n",
        "\n",
        "        return action"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QsYz0FvqlJ1I",
        "colab_type": "text"
      },
      "source": [
        "Updating the Policy\n",
        "Following each timestep, the model uses the data collected to update the policy parameters. Here, training the neural network updates the policy.To update the network we first calculate the loss.First $Q_@(s,a)$ is calculated for the action a taken by the agent in the current state s for each experience in the batch. This involves a forward pass through the value network to obtain the Q-value estimates for all of the (s, a) pairs. Recall that in the SARSA version of the Bellman equation, we use the action actually taken by the agent in the next state to calculate.So we repeat the same step with next states instead of states.Next, we extract the Q-value estimate for the action actually taken in both cases.With this, we can estimate $Q_{tar}(s,a)$.\n",
        "\n",
        "One important element to be aware of is for each experience, the agent only received information about the action actually taken. Consequently it can only learn something about this action, not the other actions available. This is why the loss is only calculated using values which correspond to the actions taken in the current and next states.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sm0cOn-ElI1O",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def update_policy(self,delta,state,next_state,action,next_state_action,reward):\n",
        "    '''\n",
        "    Updates the policy network using the NN model.\n",
        "      '''\n",
        "\n",
        "    state=int(state)\n",
        "    state=np.array([state],dtype='float32')\n",
        "    state=tf.convert_to_tensor(state)\n",
        "\n",
        "    next_state=int(next_state)\n",
        "    next_state=np.array([next_state],dtype='float32')\n",
        "    next_state=tf.convert_to_tensor(next_state)\n",
        "    preds=(self.model.predict(next_state))          \n",
        "    next_state_q_act=preds[0][next_state_action]      #This is 𝑄𝑡𝑎𝑟(𝑠,𝑎) \n",
        "    target=reward+np.asarray(delta)*np.asarray(self.gamma)*next_state_q_act\n",
        "    target=np.reshape(target,(1,1))\n",
        "\n",
        "    mse=tf.keras.losses.MeanSquaredError()\n",
        "    optimizer = tf.keras.optimizers.Adam(learning_rate=self.learning_rate)\n",
        "\n",
        "    def train_step(state, target):\n",
        "      with tf.GradientTape() as tape:\n",
        "        preds= (self.model)(state,training=True) \n",
        "        logits=(preds[0][action])                   #This is the 𝑄@(𝑠,𝑎)\n",
        "        logits=tf.reshape(logits,(1,1))\n",
        "        loss=mse(target,logits)\n",
        "        print(loss)\n",
        "      grads = tape.gradient(loss,self.model.trainable_variables)\n",
        "      optimizer.apply_gradients(zip(grads, self.model.trainable_variables))\n",
        "    train_step(state,target)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KeOVp6iKn23t",
        "colab_type": "text"
      },
      "source": [
        "Training the model\n",
        "This method creates a training environment for the model. Iterating through a set number of episodes, it uses the model to sample actions and play them. When such a timestep ends, the model is using the observations to update the policy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EmvkmsqNlh4I",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def train(self, episodes):\n",
        "    '''\n",
        "          train the model\n",
        "          episodes - number of training iterations \n",
        "          ''' \n",
        "    env=self.env\n",
        "    total_rewards=np.zeros(episodes)\n",
        "\n",
        "    for episode in range(episodes):\n",
        "      # each episode is a new game env\n",
        "      state=env.reset()\n",
        "      done=False          \n",
        "      episode_reward=0 #record episode reward\n",
        "      action=self.get_action(state)\n",
        "      print(\"Episode Started\")\n",
        "      while not done:\n",
        "        # play an action and record the game state & reward per episode\n",
        "        next_state, reward, done, _=env.step(action)\n",
        "        if done:\n",
        "          delta=0.0\n",
        "        else:\n",
        "          delta=1.0\n",
        "        next_state_action=self.get_action(next_state)\n",
        "        state=next_state\n",
        "        print(\"Episode Going On.Action taken:\",action)\n",
        "        action=next_state_action\n",
        "        episode_reward+=reward\n",
        "        self.update_policy(delta,state,next_state,action,next_state_action,reward)\n",
        "        total_rewards[episode]=episode_reward\n",
        "      print(\"Episode_reward{}\".format(episode_reward))\n",
        "      self.model.save('model_{}.h5'.format(episode))\n",
        "      print(\"Episode Ended\")\n",
        "    if self.epsilon_current_value > self.epsilon_final_value:\n",
        "      self.epsilon_current_value=self.epsilon_current_value-(self.epsilon_initial_value_-self.epsilon_final_value)/1000\n",
        "  \n",
        "Agent=Sarsa(env)\n",
        "Agent.train(episodes=200)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Rn9Ty4QhBaSN",
        "colab_type": "text"
      },
      "source": [
        "With the help of below code we run our algorithm and see the success of it.(Before running this set self.epsilon_current_value=0.001 in SARSA class so that model does not choose actions randomly)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nw5xIqSIBanG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from tensorflow.keras.models import load_model\n",
        "Agent_3=Sarsa(env,path='model.h5')\n",
        "\n",
        "state=env.reset()\n",
        "action=Agent_3.get_action(state)\n",
        "done=False\n",
        "while not done:\n",
        "    action=Agent_3.get_action(state)\n",
        "    next_state, reward, done, _=env.step(action)\n",
        "    state=next_state\n",
        "env.render(mode=\"ipython\")"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}