TD_zero.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e8b56fd33339971ca5778f6972734625",
     "grade": false,
     "grade_id": "cell-6de02a4f8d8d32df",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Assignment: Policy Evaluation in Cliff Walking Environment\n",
    "\n",
    "Welcome to the Course 2 Module 2 Programming Assignment! In this assignment, you will implement one of the fundamental sample and bootstrapping based model free reinforcement learning agents for prediction. This is namely one that uses one-step temporal difference learning, also known as TD(0). The task is to design an agent for policy evaluation in the Cliff Walking environment. Recall that policy evaluation is the prediction problem where the goal is to accurately estimate the values of states given some policy.\n",
    "\n",
    "### Learning Objectives\n",
    "- Implement parts of the Cliff Walking environment, to get experience specifying MDPs [Section 1].\n",
    "- Implement an agent that uses bootstrapping and, particularly, TD(0) [Section 2].\n",
    "- Apply TD(0) to estimate value functions for different policies, i.e., run policy evaluation experiments [Section 3]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "798b4c4240e0c54b93e87f4e543970e1",
     "grade": false,
     "grade_id": "cell-5a9dadfdba2eea90",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## The Cliff Walking Environment\n",
    "\n",
    "The Cliff Walking environment is a gridworld with a discrete state space and discrete action space. The agent starts at grid cell S. The agent can move (deterministically) to the four neighboring cells by taking actions Up, Down, Left or Right. Trying to move out of the boundary results in staying in the same location. So, for example, trying to move left when at a cell on the leftmost column results in no movement at all and the agent remains in the same location. The agent receives -1 reward per step in most states, and -100 reward when falling off of the cliff. This is an episodic task; termination occurs when the agent reaches the goal grid cell G. Falling off of the cliff results in resetting to the start state, without termination.\n",
    "\n",
    "The diagram below showcases the description above and also illustrates two of the policies we will be evaluating.\n",
    "\n",
    "<img src=\"cliffwalk.png\" style=\"height:400px\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e95b77b39709873d39c9fa46afbf4700",
     "grade": false,
     "grade_id": "cell-82b38787563a7073",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Packages.\n",
    "\n",
    "We import the following libraries that are required for this assignment. We shall be using the following libraries:\n",
    "1. jdc: Jupyter magic that allows defining classes over multiple jupyter notebook cells.\n",
    "2. numpy: the fundamental package for scientific computing with Python.\n",
    "3. matplotlib: the library for plotting graphs in Python.\n",
    "4. RL-Glue: the library for reinforcement learning experiments.\n",
    "5. BaseEnvironment, BaseAgent: the base classes from which we will inherit when creating the environment and agent classes in order for them to support the RL-Glue framework.\n",
    "6. Manager: the file allowing for visualization and testing.\n",
    "7. itertools.product: the function that can be used easily to compute permutations.\n",
    "8. tqdm.tqdm: Provides progress bars for visualizing the status of loops.\n",
    "\n",
    "**Please do not import other libraries** — this will break the autograder.\n",
    "\n",
    "**NOTE: For this notebook, there is no need to make any calls to methods of random number generators. Spurious or missing calls to random number generators may affect your results.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "386dc36257995b1270913ddfcdc1a838",
     "grade": false,
     "grade_id": "cell-917f710997077ab6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Do not modify this cell!\n",
    "\n",
    "import jdc\n",
    "# --\n",
    "import numpy as np\n",
    "# --\n",
    "from rl_glue import RLGlue\n",
    "# --\n",
    "from Agent import BaseAgent \n",
    "from Environment import BaseEnvironment  \n",
    "# --\n",
    "from manager import Manager\n",
    "# --\n",
    "from itertools import product\n",
    "# --\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "83300358f840fb91d5c9ef9a3e77e09c",
     "grade": false,
     "grade_id": "cell-bb3b3151b3f4f759",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Section 1. Environment\n",
    "\n",
    "In the first part of this assignment, you will get to see how the Cliff Walking environment is implemented. You will also get to implement parts of it to aid your understanding of the environment and more generally how MDPs are specified. In particular, you will implement the logic for:\n",
    " 1. Converting 2-dimensional coordinates to a single index for the state,\n",
    " 2. One of the actions (action up), and,\n",
    " 3. Reward and termination.\n",
    " \n",
    "Given below is an annotated diagram of the environment with more details that may help in completing the tasks of this part of the assignment. Note that we will be creating a more general environment where the height and width positions can be variable but the start, goal and cliff grid cells have the same relative positions (bottom left, bottom right and the cells between the start and goal grid cells respectively).\n",
    "\n",
    "<img src=\"cliffwalk-annotated.png\" style=\"height:400px\">\n",
    "\n",
    "Once you have gone through the code and begun implementing solutions, it may be a good idea to come back here and see if you can convince yourself that the diagram above is an accurate representation of the code given and the code you have written."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "54342eceb70d3ded536ef90b397df6a9",
     "grade": false,
     "grade_id": "cell-3b0342944fae98dd",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Do not modify this cell!\n",
    "\n",
    "# Create empty CliffWalkEnvironment class.\n",
    "# These methods will be filled in later cells.\n",
    "class CliffWalkEnvironment(BaseEnvironment):\n",
    "    def env_init(self, agent_info={}):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def env_start(self, state):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def env_step(self, reward, state):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def env_end(self, reward):\n",
    "        raise NotImplementedError\n",
    "        \n",
    "    def env_cleanup(self, reward):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    # helper method\n",
    "    def state(self, loc):\n",
    "        raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4583069bbb85ef2faa1824bf57693198",
     "grade": false,
     "grade_id": "cell-ace4da9bae087ba3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## env_init()\n",
    "\n",
    "The first function we add to the environment is the initialization function which is called once when an environment object is created. In this function, the grid dimensions and special locations (start and goal locations and the cliff locations) are stored for easy use later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "386dd420b57b9661e21454eb72f9783e",
     "grade": false,
     "grade_id": "cell-fa1aefc241323c3d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to CliffWalkEnvironment\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def env_init(self, env_info={}):\n",
    "        \"\"\"Setup for the environment called when the experiment first starts.\n",
    "        Note:\n",
    "            Initialize a tuple with the reward, first state, boolean\n",
    "            indicating if it's terminal.\n",
    "        \"\"\"\n",
    "        \n",
    "        # Note, we can setup the following variables later, in env_start() as it is equivalent. \n",
    "        # Code is left here to adhere to the note above, but these variables are initialized once more\n",
    "        # in env_start() [See the env_start() function below.]\n",
    "        \n",
    "        reward = None\n",
    "        state = None # See Aside\n",
    "        termination = None\n",
    "        self.reward_state_term = (reward, state, termination)\n",
    "        \n",
    "        # AN ASIDE: Observation is a general term used in the RL-Glue files that can be interachangeably \n",
    "        # used with the term \"state\" for our purposes and for this assignment in particular. \n",
    "        # A difference arises in the use of the terms when we have what is called Partial Observability where \n",
    "        # the environment may return states that may not fully represent all the information needed to \n",
    "        # predict values or make decisions (i.e., the environment is non-Markovian.)\n",
    "        \n",
    "        # Set the default height to 4 and width to 12 (as in the diagram given above)\n",
    "        self.grid_h = env_info.get(\"grid_height\", 4) \n",
    "        self.grid_w = env_info.get(\"grid_width\", 12)\n",
    "        \n",
    "        # Now, we can define a frame of reference. Let positive x be towards the direction down and \n",
    "        # positive y be towards the direction right (following the row-major NumPy convention.)\n",
    "        # Then, keeping with the usual convention that arrays are 0-indexed, max x is then grid_h - 1 \n",
    "        # and max y is then grid_w - 1. So, we have:\n",
    "        # Starting location of agent is the bottom-left corner, (max x, min y). \n",
    "        self.start_loc = (self.grid_h - 1, 0)\n",
    "        # Goal location is the bottom-right corner. (max x, max y).\n",
    "        self.goal_loc = (self.grid_h - 1, self.grid_w - 1)\n",
    "        \n",
    "        # The cliff will contain all the cells between the start_loc and goal_loc.\n",
    "        self.cliff = [(self.grid_h - 1, i) for i in range(1, (self.grid_w - 1))]\n",
    "        \n",
    "        # Take a look at the annotated environment diagram given in the above Jupyter Notebook cell to \n",
    "        # verify that your understanding of the above code is correct for the default case, i.e., where \n",
    "        # height = 4 and width = 12."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "367f3f8ad6acdd57c117ec393126b835",
     "grade": false,
     "grade_id": "cell-3acbe101e0eef006",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## *Implement* state()\n",
    "    \n",
    "The agent location can be described as a two-tuple or coordinate (x, y) describing the agent’s position. \n",
    "However, we can convert the (x, y) tuple into a single index and provide agents with just this integer.\n",
    "One reason for this choice is that the spatial aspect of the problem is secondary and there is no need \n",
    "for the agent to know about the exact dimensions of the environment. \n",
    "From the agent’s viewpoint, it is just perceiving some states, accessing their corresponding values \n",
    "in a table, and updating them. Both the coordinate (x, y) state representation and the converted coordinate representation are thus equivalent in this sense.\n",
    "\n",
    "Given a grid cell location, the state() function should return the state; a single index corresponding to the location in the grid.\n",
    "\n",
    "\n",
    "```\n",
    "Example: Suppose grid_h is 2 and grid_w is 2. Then, we can write the grid cell two-tuple or coordinate\n",
    "states as follows (following the usual 0-index convention):\n",
    "|(0, 0) (0, 1)| |0 1|\n",
    "|(1, 0) (1, 1)| |2 3|\n",
    "Assuming row-major order as NumPy does,  we can flatten the latter to get a vector [0 1 2 3].\n",
    "So, if loc = (0, 0) we return 0. While, for loc = (1, 1) we return 3.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "bd4aefb2add249390e2b41a037d99598",
     "grade": false,
     "grade_id": "cell-f11f3394d921a585",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "%%add_to CliffWalkEnvironment\n",
    "#GRADED FUNCTION: [state]\n",
    "\n",
    "# Work Required: Yes. Modify the return statement of this function to return a correct single index as \n",
    "# the state (see the logic for this in the previous cell.)\n",
    "# Lines: 1\n",
    "def state(self, loc):\n",
    "    ### START CODE HERE ###\n",
    "    int_state = self.grid_w*loc[0] + loc[1]\n",
    "    return int_state\n",
    "    ### END CODE HERE ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5c1f5e70a8745afcdffb67c18be40958",
     "grade": true,
     "grade_id": "state",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "### AUTOGRADER TESTS FOR STATE (5 POINTS)\n",
    "# NOTE: The test below corresponds to the annotated diagram for the environment\n",
    "#       given previously and is limited in scope. Hidden tests are used in the autograder.\n",
    "#       You may wish to run other tests to check your implementation.\n",
    "def test_state():\n",
    "    env = CliffWalkEnvironment()\n",
    "    env.env_init({\"grid_height\": 4, \"grid_width\": 12})\n",
    "    coords_to_test = [(0, 0), (0, 11), (1, 5), (3, 0), (3, 9), (3, 11)]\n",
    "    true_states = [0, 11, 17, 36, 45, 47]\n",
    "    output_states = [env.state(coords) for coords in coords_to_test]\n",
    "    assert(output_states == true_states)\n",
    "test_state()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b388d1d1cccc77907f4137339943df39",
     "grade": false,
     "grade_id": "cell-dd93e8a1b24bc4cf",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## env_start()\n",
    "\n",
    "In env_start(), we initialize the agent location to be the start location and return the state corresponding to it as the first state for the agent to act upon. Additionally, we also set the reward and termination terms to be 0 and False respectively as they are consistent with the notion that there is no reward nor termination before the first action is even taken."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "58fed26db20dabd6fa4570b1f399a148",
     "grade": false,
     "grade_id": "cell-c71fa14686edfa0b",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to CliffWalkEnvironment\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def env_start(self):\n",
    "    \"\"\"The first method called when the episode starts, called before the\n",
    "    agent starts.\n",
    "\n",
    "    Returns:\n",
    "        The first state from the environment.\n",
    "    \"\"\"\n",
    "    reward = 0\n",
    "    # agent_loc will hold the current location of the agent\n",
    "    self.agent_loc = self.start_loc\n",
    "    # state is the one dimensional state representation of the agent location.\n",
    "    state = self.state(self.agent_loc)\n",
    "    termination = False\n",
    "    self.reward_state_term = (reward, state, termination)\n",
    "\n",
    "    return self.reward_state_term[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1c21e0e861d5f3220fff345e3d5e07b0",
     "grade": false,
     "grade_id": "cell-bf5f7e78e0019780",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## *Implement* env_step()\n",
    "\n",
    "Once an action is taken by the agent, the environment must provide a new state, reward and termination signal. \n",
    "\n",
    "In the Cliff Walking environment, agents move around using a 4-cell neighborhood called the Von Neumann neighborhood (https://en.wikipedia.org/wiki/Von_Neumann_neighborhood). Thus, the agent has 4 available actions at each state. Three of the actions have been implemented for you and your first task is to implement the logic for the fourth action (Action UP).\n",
    "\n",
    "Your second task for this function is to implement the reward logic. Look over the environment description given earlier in this notebook if you need a refresher for how the reward signal is defined."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "e35e399a59401a069393c4fc781bad8c",
     "grade": false,
     "grade_id": "cell-45dfc79809d59695",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "%%add_to CliffWalkEnvironment\n",
    "#GRADED FUNCTION: [env_step]\n",
    "\n",
    "# Work Required: Yes. Fill in the code for action UP and implement the logic for reward and termination.\n",
    "# Lines: ~7.\n",
    "def env_step(self, action):\n",
    "    \"\"\"A step taken by the environment.\n",
    "\n",
    "    Args:\n",
    "        action: The action taken by the agent\n",
    "\n",
    "    Returns:\n",
    "        (float, state, Boolean): a tuple of the reward, state,\n",
    "            and boolean indicating if it's terminal.\n",
    "    \"\"\"\n",
    "\n",
    "    if action == 0: # UP (Task 1)\n",
    "        ### START CODE HERE ###\n",
    "        # Hint: Look at the code given for the other actions and think about the logic in them.\n",
    "        possible_next_loc = (self.agent_loc[0]-1,self.agent_loc[1])\n",
    "        if possible_next_loc[0]>=0:\n",
    "            self.agent_loc = possible_next_loc\n",
    "        else:\n",
    "            pass\n",
    "        ### END CODE HERE ###\n",
    "    elif action == 1: # LEFT\n",
    "        possible_next_loc = (self.agent_loc[0], self.agent_loc[1] - 1)\n",
    "        if possible_next_loc[1] >= 0: # Within Bounds?\n",
    "            self.agent_loc = possible_next_loc\n",
    "        else:\n",
    "            pass # Stay.\n",
    "    elif action == 2: # DOWN\n",
    "        possible_next_loc = (self.agent_loc[0] + 1, self.agent_loc[1])\n",
    "        if possible_next_loc[0] < self.grid_h: # Within Bounds?\n",
    "            self.agent_loc = possible_next_loc\n",
    "        else:\n",
    "            pass # Stay.\n",
    "    elif action == 3: # RIGHT\n",
    "        possible_next_loc = (self.agent_loc[0], self.agent_loc[1] + 1)\n",
    "        if possible_next_loc[1] < self.grid_w: # Within Bounds?\n",
    "            self.agent_loc = possible_next_loc\n",
    "        else:\n",
    "            pass # Stay.\n",
    "    else: \n",
    "        raise Exception(str(action) + \" not in recognized actions [0: Up, 1: Left, 2: Down, 3: Right]!\")\n",
    "\n",
    "    reward = -1\n",
    "    terminal = False\n",
    "\n",
    "    ### START CODE HERE ###\n",
    "    # Hint: Consider the initialization of reward and terminal variables above. Then, note the \n",
    "    # conditional statements and comments given below and carefully ensure to set the variables reward \n",
    "    # and terminal correctly for each case.\n",
    "    if self.agent_loc == self.goal_loc: # Reached Goal!\n",
    "        reward = -1\n",
    "        terminal = True\n",
    "    elif self.agent_loc in self.cliff: # Fell into the cliff!\n",
    "        reward = -100\n",
    "        terminal = False\n",
    "        self.agent_loc = self.start_loc\n",
    "    else: \n",
    "        pass\n",
    "    ### END CODE HERE ###\n",
    "\n",
    "    self.reward_state_term = (reward, self.state(self.agent_loc), terminal)\n",
    "    return self.reward_state_term"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "265bd639fb4f3a322d51ff96597f5648",
     "grade": true,
     "grade_id": "action_up",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "### AUTOGRADER TESTS FOR ACTION UP (5 POINTS)\n",
    "# NOTE: The test below is again limited in scope. Hidden tests are used in the autograder.\n",
    "#       You may wish to run other tests to check your implementation.\n",
    "def test_action_up():\n",
    "    env = CliffWalkEnvironment()\n",
    "    env.env_init({\"grid_height\": 4, \"grid_width\": 12})\n",
    "    env.agent_loc = (0, 0)\n",
    "    env.env_step(0)\n",
    "    assert(env.agent_loc == (0, 0))\n",
    "    \n",
    "    env.agent_loc = (1, 0)\n",
    "    env.env_step(0)\n",
    "    assert(env.agent_loc == (0, 0))\n",
    "test_action_up()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "73b383e7e0a1c203a26a29b850684a52",
     "grade": true,
     "grade_id": "reward_termination",
     "locked": true,
     "points": 10,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "### AUTOGRADER TESTS FOR REWARD & TERMINATION (10 POINTS)\n",
    "# NOTE: The test below is limited in scope. Hidden tests are used in the autograder.\n",
    "#       You may wish to run other tests to check your implementation.\n",
    "def test_reward():\n",
    "    env = CliffWalkEnvironment()\n",
    "    env.env_init({\"grid_height\": 4, \"grid_width\": 12})\n",
    "    env.agent_loc = (0, 0)\n",
    "    reward_state_term = env.env_step(0)\n",
    "    assert(reward_state_term[0] == -1 and reward_state_term[1] == env.state((0, 0)) and\n",
    "           reward_state_term[2] == False)\n",
    "    \n",
    "    env.agent_loc = (3, 1)\n",
    "    reward_state_term = env.env_step(2)\n",
    "    assert(reward_state_term[0] == -100 and reward_state_term[1] == env.state((3, 0)) and\n",
    "           reward_state_term[2] == False)\n",
    "    \n",
    "    env.agent_loc = (2, 11)\n",
    "    reward_state_term = env.env_step(2)\n",
    "    assert(reward_state_term[0] == -1 and reward_state_term[1] == env.state((3, 11)) and\n",
    "           reward_state_term[2] == True)\n",
    "test_reward()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4a499bb0871653446d6b303c2625df09",
     "grade": false,
     "grade_id": "cell-88082a3dab94c4a8",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## env_cleanup()\n",
    "\n",
    "There is not much cleanup to do for the Cliff Walking environment. Here, we simply reset the agent location to be the start location in this function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ef29fa83791e5f064a53af742f2859a2",
     "grade": false,
     "grade_id": "cell-4c235eb2667f9f0d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to CliffWalkEnvironment\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def env_cleanup(self):\n",
    "    \"\"\"Cleanup done after the environment ends\"\"\"\n",
    "    self.agent_loc = self.start_loc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "180b31b525fb94442eb79f07d7097700",
     "grade": false,
     "grade_id": "cell-ff4e65eb47d735c9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Section 2. Agent\n",
    "\n",
    "In this second part of the assignment, you will be implementing the key updates for Temporal Difference Learning. There are two cases to consider depending on whether an action leads to a terminal state or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "d4eaa5e48e54f9c5e55149325b215d47",
     "grade": false,
     "grade_id": "cell-3abcfd06cde56935",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Do not modify this cell!\n",
    "\n",
    "# Create empty TDAgent class.\n",
    "# These methods will be filled in later cells.\n",
    "\n",
    "class TDAgent(BaseAgent):\n",
    "    def agent_init(self, agent_info={}):\n",
    "        raise NotImplementedError\n",
    "        \n",
    "    def agent_start(self, state):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def agent_step(self, reward, state):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def agent_end(self, reward):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def agent_cleanup(self):        \n",
    "        raise NotImplementedError\n",
    "        \n",
    "    def agent_message(self, message):\n",
    "        raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "83d69efb64983138188a2bad513622b1",
     "grade": false,
     "grade_id": "cell-edd826505e77e70a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## agent_init()\n",
    "\n",
    "As we did with the environment, we first initialize the agent once when a TDAgent object is created. In this function, we create a random number generator, seeded with the seed provided in the agent_info dictionary to get reproducible results. We also set the policy, discount and step size based on the agent_info dictionary. Finally, with a convention that the policy is always specified as a mapping from states to actions and so is an array of size (# States, # Actions), we initialize a values array of shape (# States,) to zeros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "24d451072e0b43f3ad7980887c6f5861",
     "grade": false,
     "grade_id": "cell-077135deef2f8fd9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to TDAgent\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def agent_init(self, agent_info={}):\n",
    "    \"\"\"Setup for the agent called when the experiment first starts.\"\"\"\n",
    "\n",
    "    # Create a random number generator with the provided seed to seed the agent for reproducibility.\n",
    "    self.rand_generator = np.random.RandomState(agent_info.get(\"seed\"))\n",
    "\n",
    "    # Policy will be given, recall that the goal is to accurately estimate its corresponding value function. \n",
    "    self.policy = agent_info.get(\"policy\")\n",
    "    # Discount factor (gamma) to use in the updates.\n",
    "    self.discount = agent_info.get(\"discount\")\n",
    "    # The learning rate or step size parameter (alpha) to use in updates.\n",
    "    self.step_size = agent_info.get(\"step_size\")\n",
    "\n",
    "    # Initialize an array of zeros that will hold the values.\n",
    "    # Recall that the policy can be represented as a (# States, # Actions) array. With the \n",
    "    # assumption that this is the case, we can use the first dimension of the policy to\n",
    "    # initialize the array for values.\n",
    "    self.values = np.zeros((self.policy.shape[0],))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a4f9d05505f09198739674b1b330b9cd",
     "grade": false,
     "grade_id": "cell-99e8e59cd1f7a5ef",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# agent_start()\n",
    "\n",
    "In agent_start(), we choose an action based on the initial state and policy we are evaluating. We also cache the state so that we can later update its value when we perform a Temporal Difference update. Finally, we return the action chosen so that the RL loop can continue and the environment can execute this action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8c5490c3d5fa88339b02cdf933f7f106",
     "grade": false,
     "grade_id": "cell-1b6dd05f7f49c1fc",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to TDAgent\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def agent_start(self, state):\n",
    "    \"\"\"The first method called when the episode starts, called after\n",
    "    the environment starts.\n",
    "    Args:\n",
    "        state (Numpy array): the state from the environment's env_start function.\n",
    "    Returns:\n",
    "        The first action the agent takes.\n",
    "    \"\"\"\n",
    "    # The policy can be represented as a (# States, # Actions) array. So, we can use \n",
    "    # the second dimension here when choosing an action.\n",
    "    action = self.rand_generator.choice(range(self.policy.shape[1]), p=self.policy[state])\n",
    "    self.last_state = state\n",
    "    return action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "fd9be2a7be0a8fbd3aee6b7c14f4ec37",
     "grade": false,
     "grade_id": "cell-a472a21b4a57b885",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## *Implement* agent_step()\n",
    "\n",
    "In agent_step(), the agent must:\n",
    "\n",
    "- Perform an update to improve the value estimate of the previously visited state, and\n",
    "- Act based on the state provided by the environment.\n",
    "\n",
    "The latter of the two steps above has been implemented for you. Implement the former. Note that, unlike later in agent_end(), the episode has not yet ended in agent_step(). in other words, the previously observed state was not a terminal state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "4c68b1daf60c5fbf3c75d4329048af15",
     "grade": false,
     "grade_id": "cell-2bec3235783127e8",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "%%add_to TDAgent\n",
    "\n",
    "#[GRADED] FUNCTION: [agent_step]\n",
    "\n",
    "# Work Required: Yes. Fill in the TD-target and update.\n",
    "# Lines: ~2.\n",
    "def agent_step(self, reward, state):\n",
    "    \"\"\"A step taken by the agent.\n",
    "    Args:\n",
    "        reward (float): the reward received for taking the last action taken\n",
    "        state (Numpy array): the state from the\n",
    "            environment's step after the last action, i.e., where the agent ended up after the\n",
    "            last action\n",
    "    Returns:\n",
    "        The action the agent is taking.\n",
    "    \"\"\"\n",
    "    ### START CODE HERE ###\n",
    "    # Hint: We should perform an update with the last state given that we now have the reward and\n",
    "    # next state. We break this into two steps. Recall for example that the Monte-Carlo update \n",
    "    # had the form: V[S_t] = V[S_t] + alpha * (target - V[S_t]), where the target was the return, G_t.\n",
    "    target = reward + self.discount*( self.values[state] )\n",
    "    self.values[self.last_state] = self.values[self.last_state] + self.step_size*( target - self.values[self.last_state] )\n",
    "    ### END CODE HERE ###\n",
    "\n",
    "    # Having updated the value for the last state, we now act based on the current \n",
    "    # state, and set the last state to be current one as we will next be making an \n",
    "    # update with it when agent_step is called next once the action we return from this function \n",
    "    # is executed in the environment.\n",
    "\n",
    "    action = self.rand_generator.choice(range(self.policy.shape[1]), p=self.policy[state])\n",
    "    self.last_state = state\n",
    "\n",
    "    return action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8f516e1bdb6ca3f1a1ce385cf2c56765",
     "grade": false,
     "grade_id": "cell-f5ed31e224e22cda",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## *Implement* agent_end() \n",
    "\n",
    "Implement the TD update for the case where an action leads to a terminal state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "65b123f954dd8176f089d389bc2e9735",
     "grade": false,
     "grade_id": "cell-08c5ac56c1a0a841",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "%%add_to TDAgent\n",
    "\n",
    "#[GRADED] FUNCTION: [agent_end]\n",
    "\n",
    "# Work Required: Yes. Fill in the TD-target and update.\n",
    "# Lines: ~2.\n",
    "def agent_end(self, reward):\n",
    "    \"\"\"Run when the agent terminates.\n",
    "    Args:\n",
    "        reward (float): the reward the agent received for entering the terminal state.\n",
    "    \"\"\"\n",
    "    ### START CODE HERE ###\n",
    "    # Hint: Here too, we should perform an update with the last state given that we now have the \n",
    "    # reward. Note that in this case, the action led to termination. Once more, we break this into \n",
    "    # two steps, computing the target and the update itself that uses the target and the \n",
    "    # current value estimate for the state whose value we are updating.\n",
    "    target = reward\n",
    "    self.values[self.last_state] = self.values[self.last_state] + self.step_size*( target - self.values[self.last_state] )\n",
    "    ### END CODE HERE ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8e12df5724ecfa704bc67e2577c2ea34",
     "grade": false,
     "grade_id": "cell-06cbc6053aa156bc",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## agent_cleanup()\n",
    "\n",
    "In cleanup, we simply reset the last state to be None to ensure that we are not storing any states past an episode."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "540f808d320ce14b29ee7e8ddcda6ae7",
     "grade": false,
     "grade_id": "cell-c39f860970dfe3a7",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to TDAgent\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def agent_cleanup(self):\n",
    "    \"\"\"Cleanup done after the agent ends.\"\"\"\n",
    "    self.last_state = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f62a4cb327c230937f3bc459f305e6f6",
     "grade": false,
     "grade_id": "cell-aadbaa36598224e6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## agent_message()\n",
    "\n",
    "agent_message() can generally be used to get different kinds of information about an RLGlue agent in the interaction loop of RLGlue. Here, we conditonally check for a message matching \"get_values\" and use it to retrieve the values table the agent has been updating over time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9e222e9cc5396065dafe6e39a2052097",
     "grade": false,
     "grade_id": "cell-a440254b4f0573e2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%add_to TDAgent\n",
    "\n",
    "# Do not modify this cell!\n",
    "\n",
    "# Work Required: No.\n",
    "def agent_message(self, message):\n",
    "    \"\"\"A function used to pass information from the agent to the experiment.\n",
    "    Args:\n",
    "        message: The message passed to the agent.\n",
    "    Returns:\n",
    "        The response (or answer) to the message.\n",
    "    \"\"\"\n",
    "    if message == \"get_values\":\n",
    "        return self.values\n",
    "    else:\n",
    "        raise Exception(\"TDAgent.agent_message(): Message not understood!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "6830d90d89beea893034ebe0d7b2373c",
     "grade": true,
     "grade_id": "td_updates",
     "locked": true,
     "points": 20,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "### AUTOGRADER TESTS FOR TD-UPDATES (20 POINTS)\n",
    "# NOTE: The test belows serve as a good check in debugging your code for the TD updates. However, \n",
    "#       as with the other tests, it is limited in scope. Hidden tests are used in the autograder.\n",
    "#       You may wish to run other tests to check your implementation.\n",
    "def test_td_updates():\n",
    "    # The following test checks that the TD check works for a case where the transition \n",
    "    # garners reward -1 and does not lead to a terminal state. This is in a simple two state setting \n",
    "    # where there is only one action. The first state's current value estimate is 0 while the second is 1.\n",
    "    # Note the discount and step size if you are debugging this test.\n",
    "    agent = TDAgent()\n",
    "    policy_list = np.array([[1.], [1.]])\n",
    "    agent.agent_init({\"policy\": np.array(policy_list), \"discount\": 0.99, \"step_size\": 0.1})\n",
    "    agent.values = np.array([0., 1.])\n",
    "    agent.agent_start(0)\n",
    "    reward = -1\n",
    "    next_state = 1\n",
    "    agent.agent_step(reward, next_state)\n",
    "    assert(np.isclose(agent.values[0], -0.001) and np.isclose(agent.values[1], 1.))\n",
    "    \n",
    "    # The following test checks that the TD check works for a case where the transition \n",
    "    # garners reward -100 and lead to a terminal state. This is in a simple one state setting \n",
    "    # where there is only one action. The state's current value estimate is 0.\n",
    "    # Note the discount and step size if you are debugging this test.\n",
    "    agent = TDAgent()\n",
    "    policy_list = np.array([[1.]])\n",
    "    agent.agent_init({\"policy\": np.array(policy_list), \"discount\": 0.99, \"step_size\": 0.1})\n",
    "    agent.values = np.array([0.])\n",
    "    agent.agent_start(0)\n",
    "    reward = -100\n",
    "    next_state = 0\n",
    "    agent.agent_end(reward)\n",
    "    assert(np.isclose(agent.values[0], -10))\n",
    "    \n",
    "test_td_updates()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ba2a884124c4e5c073f529f94a2bd580",
     "grade": false,
     "grade_id": "cell-3f4e7f85a3f548e9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Section 3. Policy Evaluation Experiments\n",
    "\n",
    "Finally, in this last part of the assignment, you will get to see the TD policy evaluation algorithm in action by looking at the estimated values, the per state value error and after the experiment is complete, the Mean Squared Value Error curve vs. episode number, summarizing how the value error changed over time.\n",
    "\n",
    "The code below runs one run of an experiment given env_info and agent_info dictionaries. A \"manager\" object is created for visualizations and is used in part for the autograder. By default, the run will be for 5000 episodes. The true_values_file is specified to compare the learned value function with the values stored in the true_values_file. Plotting of the learned value  function occurs by default after every 100 episodes. In addition, when true_values_file is specified, the value error per state and the root mean square value error will also be plotted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "d929e2760dd07cbdd0bea18f05639d81",
     "grade": false,
     "grade_id": "cell-7b2ee7906789af2d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib notebook\n",
    "\n",
    "# Work Required: No. \n",
    "def run_experiment(env_info, agent_info, \n",
    "                   num_episodes=5000,\n",
    "                   experiment_name=None,\n",
    "                   plot_freq=100,\n",
    "                   true_values_file=None,\n",
    "                   value_error_threshold=1e-8):\n",
    "    env = CliffWalkEnvironment\n",
    "    agent = TDAgent\n",
    "    rl_glue = RLGlue(env, agent)\n",
    "\n",
    "    rl_glue.rl_init(agent_info, env_info)\n",
    "\n",
    "    manager = Manager(env_info, agent_info, true_values_file=true_values_file, experiment_name=experiment_name)\n",
    "    for episode in range(1, num_episodes + 1):\n",
    "        rl_glue.rl_episode(0) # no step limit\n",
    "        if episode % plot_freq == 0:\n",
    "            values = rl_glue.agent.agent_message(\"get_values\")\n",
    "            manager.visualize(values, episode)\n",
    "\n",
    "    values = rl_glue.agent.agent_message(\"get_values\")\n",
    "    if true_values_file is not None:\n",
    "        # Grading: The Manager will check that the values computed using your TD agent match \n",
    "        # the true values (within some small allowance) across the states. In addition, it also\n",
    "        # checks whether the root mean squared value error is close to 0.\n",
    "        manager.run_tests(values, value_error_threshold)\n",
    "    \n",
    "    return values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4fad676a6e39768fdfe6897b2fb9032a",
     "grade": false,
     "grade_id": "cell-17e3e97164635860",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "The cell below just runs a policy evaluation experiment with the determinstic optimal policy that strides just above the cliff. You should observe that the per state value error and RMSVE curve asymptotically go towards 0. The arrows in the four directions denote the probabilities of taking each action. This experiment is ungraded but should serve as a good test for the later experiments. The true values file provided for this experiment may help with debugging as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5f6345cb14ab92ac88ba1653695a1cec",
     "grade": false,
     "grade_id": "cell-70b3816dea097209",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Do not modify this cell!\n",
    "\n",
    "env_info = {\"grid_height\": 4, \"grid_width\": 12, \"seed\": 0}\n",
    "agent_info = {\"discount\": 1, \"step_size\": 0.01, \"seed\": 0}\n",
    "\n",
    "# The Optimal Policy that strides just along the cliff\n",
    "policy = np.ones(shape=(env_info['grid_width'] * env_info['grid_height'], 4)) * 0.25\n",
    "policy[36] = [1, 0, 0, 0]\n",
    "for i in range(24, 35):\n",
    "    policy[i] = [0, 0, 0, 1]\n",
    "policy[35] = [0, 0, 1, 0]\n",
    "\n",
    "agent_info.update({\"policy\": policy})\n",
    "\n",
    "true_values_file = \"optimal_policy_value_fn.npy\"\n",
    "_ = run_experiment(env_info, agent_info, num_episodes=5000, experiment_name=\"Policy Evaluation on Optimal Policy\",\n",
    "                   plot_freq=500, true_values_file=true_values_file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9b8fd1dd026cb36082aa0d6245763627",
     "grade": false,
     "grade_id": "cell-11c76882b7939d66",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# The Safe Policy\n",
    "# Hint: Fill in the array below (as done in the previous cell) based on the safe policy illustration \n",
    "# in the environment diagram. This is the policy that strides as far as possible away from the cliff. \n",
    "# We call it a \"safe\" policy because if the environment has any stochasticity, this policy would do a good job in \n",
    "# keeping the agent from falling into the cliff (in contrast to the optimal policy shown before). \n",
    "# BOILERPLATE:\n",
    "policy = np.ones(shape=(env_info['grid_width'] * env_info['grid_height'], 4)) * 0.25\n",
    "### START CODE HERE ###\n",
    "policy[12] = [1, 0, 0, 0]\n",
    "policy[24] = [1, 0, 0, 0]\n",
    "policy[36] = [1, 0, 0, 0]\n",
    "for i in range(0, 11):\n",
    "    policy[i] = [0, 0, 0, 1]\n",
    "policy[35] = [0, 0, 1, 0]\n",
    "policy[23] = [0, 0, 1, 0]\n",
    "policy[35] = [0, 0, 1, 0]\n",
    "### END CODE HERE ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b67dc6aaaa345faed7768ab6c07a926c",
     "grade": true,
     "grade_id": "safe_policy",
     "locked": true,
     "points": 20,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "### AUTO-GRADER TESTS FOR POLICY EVALUATION WITH SAFE POLICY\n",
    "agent_info.update({\"policy\": policy})\n",
    "v = run_experiment(env_info, agent_info,\n",
    "               experiment_name=\"Policy Evaluation On Safe Policy\",\n",
    "               num_episodes=5000, plot_freq=500)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "64c386534d040888bfa2fe3ba58f1370",
     "grade": false,
     "grade_id": "cell-3a8720c5685c8716",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Do not modify this cell!\n",
    "\n",
    "# A Near Optimal Stochastic Policy\n",
    "# Now, we try a stochastic policy that deviates a little from the optimal policy seen above. \n",
    "# This means we can get different results due to randomness.\n",
    "# We will thus average the value function estimates we get over multiple runs. \n",
    "# This can take some time, upto about 5 minutes from previous testing. \n",
    "# NOTE: The autograder will compare . Re-run this cell upon making any changes.\n",
    "\n",
    "env_info = {\"grid_height\": 4, \"grid_width\": 12}\n",
    "agent_info = {\"discount\": 1, \"step_size\": 0.01}\n",
    "\n",
    "policy = np.ones(shape=(env_info['grid_width'] * env_info['grid_height'], 4)) * 0.25\n",
    "policy[36] = [0.9, 0.1/3., 0.1/3., 0.1/3.]\n",
    "for i in range(24, 35):\n",
    "    policy[i] = [0.1/3., 0.1/3., 0.1/3., 0.9]\n",
    "policy[35] = [0.1/3., 0.1/3., 0.9, 0.1/3.]\n",
    "agent_info.update({\"policy\": policy})\n",
    "agent_info.update({\"step_size\": 0.01})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c900a0e55cf506cdae6e3607890bcdbd",
     "grade": true,
     "grade_id": "near_optimal_stochastic_policy",
     "locked": true,
     "points": 40,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "### AUTO-GRADER TESTS FOR POLICY EVALUATION WITH NEAR OPTIMAL STOCHASTIC POLICY (40 POINTS)\n",
    "arr = []\n",
    "from tqdm import tqdm\n",
    "for i in tqdm(range(30)):\n",
    "    env_info['seed'] = i\n",
    "    agent_info['seed'] = i\n",
    "    v = run_experiment(env_info, agent_info,\n",
    "                   experiment_name=\"Policy Evaluation On Optimal Policy\",\n",
    "                   num_episodes=5000, plot_freq=10000)\n",
    "    arr.append(v)\n",
    "average_v = np.array(arr).mean(axis=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "74d80436e59bbf99333411fd5ac1675b",
     "grade": false,
     "grade_id": "cell-0276c863cb27066d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Wrapping Up\n",
    "Congratulations, you have completed assignment 2! In this assignment, we investigated a very useful concept for sample-based online learning: temporal difference. We particularly looked at the prediction problem where the goal is to find the value function corresponding to a given policy. In the next assignment, by learning the action-value function instead of the state-value function, you will get to see how temporal difference learning can be used in control as well."
   ]
  }
 ],
 "metadata": {
  "coursera": {
   "course_slug": "sample-based-learning-methods",
   "graded_item_id": "P4k5f",
   "launcher_item_id": "OwIbv"
  },
  "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}