03B_RL_Complete.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Reinforcement Learning (RL) in TensorFlow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recap of Supervised Learning\n",
    "\n",
    "In previous days, we've primarily concerned ourselves with supervised learning problems (mostly classification).\n",
    "In supervised learning, we are given some sort of training data consisting of input/output pairs, with the goal being to be able to predict the output given some new inputs after learning the model.\n",
    "For example, yesterday's homework was CNN classification model for MNIST; given a training set of 55000 digit images and corresponding digit labels (e.g. '5'), we learned a model that was capable of predicting the digit label of new MNIST images.\n",
    "In order words, something like (but not exactly) this:\n",
    "<img src=\"Figures/mnist_cnn_ex.png\" alt=\"mnist_cnn_ex\" style=\"width: 700px;\"/>\n",
    "<center>Figure from *[Getting started with PyTorch for Deep Learning (Part 3: Neural Network basics)]( https://codetolight.wordpress.com/2017/11/29/getting-started-with-pytorch-for-deep-learning-part-3-neural-network-basics/)*</center>\n",
    "\n",
    "What if we want to learn how to perform more complex behaviors, where data collection can be expensive? \n",
    "How do you teach a robot to walk? \n",
    "Self-driving cars? \n",
    "How do you defeat human champions in the game of Go? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reinforcement Learning\n",
    "Enter Reinforcement Learning. \n",
    "In Reinforcement Learning, our model (commonly referred to as an *agent* in this context) interacts with an *environment* by taking *actions* $a$ and receives some sort of feedback from the environment in the form of a *reward* $r$. \n",
    "In this sense, reinforcement learning algorithms learn by experience.\n",
    "We call the trajectory of going from start to finish of a task an *episode*, and often our agent will learn by undergoing many episodes.\n",
    "<img src=\"Figures/RL.PNG\" alt=\"RL\" style=\"width: 400px;\"/>\n",
    "\n",
    "#### Markov Decision Processes (MDPs)\n",
    "Many reinforcement learning algorithms are modeled as Markov Decision Processes (MDPs). \n",
    "In these settings, we have a concept of a *state* $s$, which encapsulates the situation of the agent (e.g. location, velocity).\n",
    "From each state $s_t$, the agent takes an action $a_t$, which results in a transition from one state $s_t$ to another $s_{t+1}$.\n",
    "In many settings, there is stochasticity in this transition, meaning that there's is a distribution over $s_{t+1}$ conditioned on $s_t$ and $a_t$.\n",
    "Often, several of these states are considered episode ending, after which the agent can no longer make any transitions or collect any more reward.\n",
    "These correspond to states such as reaching the final goal, a game concluding, or falling of a cliff.\n",
    "In the end, our goal is to learn a *policy* $\\pi$, or a mapping from states to actions.\n",
    "\n",
    "#### Partially Observable Markov Decision Processes (POMDPs)\n",
    "In an MDP, we assume that we can always tell which state $s_t$ our agents is in.\n",
    "However, this isn't always the case.\n",
    "Sometimes, all we have access to are observations $o_t$ that provide information the state $s_t$, but enough to precisely pinpoint the exact one.\n",
    "We call such settings Partially Observable Markov Decision Processes (POMDPs).\n",
    "Imagine for example a [Roomba](https://en.wikipedia.org/wiki/Roomba) being trained to navigate a living room with RL.\n",
    "From its infrared and mechanical \"bump\" sensors, it receives partial information ($o_t$) as to where it might be, but not a definitive location ($s_t$).\n",
    "Operating as a POMDP adds a whole layer of complexity to RL algorithms.\n",
    "For the rest of day though, we'll focus on MDPs, as their much simpler and easier to use to teach basic concepts.\n",
    "\n",
    "\n",
    "#### A simple MDP example\n",
    "\n",
    "<img src=\"Figures/MDP.png\" alt=\"MDP\" style=\"width: 400px;\"/>\n",
    "<center>Figure from *[Markov decision process](https://en.wikipedia.org/wiki/Markov_decision_process)*</center>\n",
    "\n",
    "In the above example, we can see the 3 possible states for the agent as $s_0$, $s_1$, and $s_2$, with 2 actions $a_0$ and $a_1$ available from each state.\n",
    "We can see that the each action doesn't lead to a determinstic transition to the next state, as shown by multiple paths from each action. \n",
    "Note that each of the outcomes of an action are labeled with a small black number between 0 and 1.\n",
    "This denotes the probability of that outcome (which state we end up at) given the the action; as these are probabilites, the sum of the probabilities of arriving at each of the next states $s_{t+1}$ given a previous state $s_t$ and selected action $a_t$ is 1.\n",
    "\n",
    "#### Objective\n",
    "\n",
    "The goal of the agent is to maximize the total reward $R$ it can receive over some number of steps.\n",
    "It is important to ensure the reward actually captures the true goal we want the agent to achieve.\n",
    "The agent will dutifully attempt maximize the objective it is given, without any considerations to any implicit objectives that a human may desire.\n",
    "There are more than a few (amusing) anecdotes of RL agents learning undesirable behaviors by exploiting some aspect of the reward function.\n",
    "As such, defining this reward requires special care.\n",
    "\n",
    "One countermeasure commonly deployed by RL researchers is the concept of *discounted* rewards.\n",
    "This is done with a multiplicative term $\\gamma$: a reward $T$ steps in the future is discounted as $\\gamma^T r_T$.\n",
    "Using discounting encourages the agent to finish the task sooner rather than later, a common implicit criterion.\n",
    "With discounting then, the RL agent's goal is to maximize:\n",
    "\\begin{align*}\n",
    "\\mathbb{E}[\\sum_{t=0}^{\\infty} \\gamma^t r_t]\n",
    "\\end{align*}\n",
    "This is far from the complete solution to making our rewards accurately capture our desired objectives, but achieving higher rewards sooner rather than later is an almost universal preference, so we almost always add it.\n",
    "Designing a good reward function can be an art is highly dependent on the task.\n",
    "\n",
    "#### Reinforcement Learning as Supervised Learning?\n",
    "At first, this doesn't seem too different from the supervised methods we've looked at before, and some natural questions might arise:\n",
    "- Why can't we just treat RL as a supervised task? \n",
    "Why can't we use the reward (or rather, the negative of the reward) as our supervised loss?\n",
    "\n",
    "Unlike in supervised learning, in reinforcement learning, we often don't have a pre-apportioned dataset to learn from.\n",
    "In some problems set-ups, we may have examples of other agents (oftentimes humans) performing the desired task, but these aren't necessarily optimal examples of how to maximize the reward, which is what we want to learn.\n",
    "In most RL settings, we don't have any examples of state-action trajectories beyond what our agent experiences through trial-and-error, which are even more suboptimal. \n",
    "Learning from the reward signal itself is also not the way to do it, as such an approach would be myopic: it would maximize reward that can be earned now instead of maximizing the overall reward over a trajectory.\n",
    "\n",
    "\n",
    "### Open AI Gym\n",
    "Before we dive any deeper into implementing reinforcement learning models, first we need an environment.\n",
    "Remember, the goal is to learn an agent that can interact with an environment in the way we want, so we need something that our agent can interact with and receive rewards from.\n",
    "In robotics, this is often the real world (or some set-up in the real world).\n",
    "However, it is oftentimes cheaper and quicker to first test our algorithms in simulated settings.\n",
    "There are a number of tasks that are popular benchmarks for the reinforcement learning community, such as [cart pole](https://en.wikipedia.org/wiki/Inverted_pendulum), [mountain car](https://en.wikipedia.org/wiki/Mountain_car_problem), or [Atari 2600 games](https://gym.openai.com/envs/#atari). \n",
    "In the spirit of accelerating progress and promoting openness in the research community, Open AI has very nicely coded up [Open AI Gym](https://gym.openai.com/), which has implementations of many of these environments for public use.\n",
    "We will be using these environments, as it allows us to focus on the algorithms themselves, instead of worrying about implementing each problem setting ourselves.\n",
    "\n",
    "To use it, we first need to download and install it. Make sure you're in your TensorFlow environment first!\n",
    "\n",
    "```Shell\n",
    "# If you environment isn't currently active, activate it (include the word \"source\", without [] if on Windows):\n",
    "# [source] activate tensorflow\n",
    "\n",
    "pip install gym\n",
    "```\n",
    "\n",
    "Once it's installed, we can import it like any other Python module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: gym in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (0.10.5)\n",
      "Requirement already satisfied: requests>=2.0 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from gym) (2.19.1)\n",
      "Requirement already satisfied: six in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from gym) (1.11.0)\n",
      "Requirement already satisfied: pyglet>=1.2.0 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from gym) (1.3.2)\n",
      "Requirement already satisfied: numpy>=1.10.4 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from gym) (1.14.3)\n",
      "Requirement already satisfied: urllib3<1.24,>=1.21.1 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from requests>=2.0->gym) (1.23)\n",
      "Requirement already satisfied: certifi>=2017.4.17 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from requests>=2.0->gym) (2018.4.16)\n",
      "Requirement already satisfied: chardet<3.1.0,>=3.0.2 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from requests>=2.0->gym) (3.0.4)\n",
      "Requirement already satisfied: idna<2.8,>=2.5 in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from requests>=2.0->gym) (2.7)\n",
      "Requirement already satisfied: future in /anaconda3/envs/tf1.8/lib/python3.6/site-packages (from pyglet>=1.2.0->gym) (0.16.0)\n"
     ]
    }
   ],
   "source": [
    "!pip install gym"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FrozenLake (a Grid World)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's start with a simple environment: FrozenLake.\n",
    "Here's the official description from OpenAI gym:\n",
    "\n",
    "> *Winter is here. You and your friends were tossing around a frisbee at the park when you made a wild throw that left the frisbee out in the middle of the lake. The water is mostly frozen, but there are a few holes where the ice has melted. If you step into one of those holes, you'll fall into the freezing water. At this time, there's an international frisbee shortage, so it's absolutely imperative that you navigate across the lake and retrieve the disc. However, the ice is slippery, so you won't always move in the direction you intend.*\n",
    "\n",
    "A visualization of FrozenLake as a grid world:\n",
    "\n",
    "<img src=\"Figures/FrozenLake.PNG\" alt=\"FrozenLake\" style=\"width: 400px;\"/>\n",
    "<center>Figure from *[Frozen Lake: Beginners Guide To Reinforcement Learning With OpenAI Gym](https://analyticsindiamag.com/openai-gym-frozen-lake-beginners-guide-reinforcement-learning/)*</center>\n",
    "\n",
    "At the start of an episode, we begin in the upper left corner (S).\n",
    "Our goal is to move ourself to the lower right corner (G), avoiding falling into the holes (H).\n",
    "Icy water is cold.\n",
    "\n",
    "In reinforcement learning terms, each of the 16 locations on the grid are a state, and an action is attempting to move in one of four directions (left, down, right, up).\n",
    "Each move will result in the agent's state changing from $s_t$ to $s_{t+1}$ as it changes location, unless it attempts to move in the direction of a wall, which results in the agent's state not changing (the agent doesn't move).\n",
    "We receive a positive reward of \"+1\" for reaching the goal (G), discounted according to how long it took.\n",
    "While there is not a negative reward for falling into a hole (H), the agent still pays a penalty in the sense that falling into the hole is episode-ending and therefore prevents it from receiving any reward. \n",
    "We want to learn a policy $\\pi$ that takes us from our starting location (S) to the goal (G) in as few steps as possible.\n",
    "\n",
    "To really establish what we are trying to accomplish here, it's worth debunking a few common initial misconceptions:\n",
    "\n",
    "- **Knowledge of the states and transition probabilties:** From the top-down view, your first thought might be to plot out a path from the start to the finish, just as you would with a maze.\n",
    "However, this view is provided to us the algorithm designers so we can visualize the problem at hand.\n",
    "The agent learning the task does *not* get this prior knowledge; all we are about to tell it is that there are going to be 16 states and 4 possible actions from each state.\n",
    "A more proper analogy would be if I blindfolded you and dropped you in the middle of a frozen lake, and told you your state (location) every time you decided to take a step in one of four directions, then set off fireworks when you stepped on the frisbee.\n",
    "\n",
    "- **Knowledge of the goal (reward):** In OpenAI's official description of the environment, you (the agent) know what you're hoping to accomplish: You want to retrieve the frisbee, while avoiding falling through the ice.\n",
    "The agent does *not* know this.\n",
    "Rather, it learns the goal by experiencing rewards (or penalties), and the algorithm updates its policy such that it will be more (or less) likely to do those actions again.\n",
    "Note that this means that if an agent never experiences certain rewards, it won't know they exist.\n",
    "\n",
    "- **Prior knowledge of pathfinding, physics, etc.:** As a human, even if you haven't solved this task before, you still bring a tremondous amount of prior knowledge to this problem.\n",
    "For example, you know the shortest path to a destination is a line.\n",
    "You know that North, South, East, and West, are directions, and that going North and then South brings you back to where you already were.\n",
    "You know ice is slippery.\n",
    "You know icy water is cold.\n",
    "You know being in icy cold water is bad.\n",
    "It's important to keep in mind that our agent will begin knowing none of these things; it's initial policy is essentially picking actions completely at random.\n",
    "By the end of the training, it still won't know what abstract concepts like \"North/South,\" \"cold,\" or \"slippery\" mean\\*, but it will have (hopefully) learned a good policy that allows it to complete the goal.\n",
    "\n",
    "\\* *Apologies. Didn't mean to get philosophical.*\n",
    "\n",
    "#### Interacting with FrozenLake\n",
    "This example is simple enough that we could code the environment and its interface ourselves fairly easily, but OpenAI has already done it, and we'd like to focus on the algorithm of solving it as much as possible.\n",
    "We can create an instantiation of FrozenLake in a single line of code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = gym.make(\"FrozenLake-v0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Open AI Gym environments provide a mechanism to observe the state of the environment, and since FrozenLake is an MDP (as opposed to POMDP), the observation is the state itself.\n",
    "For FrozenLake, there are 16 grid locations on the map, meaning we have 16 states.\n",
    "We can confirm this by looking at the size of the `observation_space` attribute for the environment we just created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Discrete(16)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.observation_space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our agent will interact with this environment causing its state to change.\n",
    "For FrozenLake, we have 4 options, each corresponding to attempting to step in a particular direction: `[Left, Down, Right, Up]`.\n",
    "We can confirm this by looking at the size of the `action_space` of our environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Discrete(4)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.action_space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before interacting with the environment, we have to first reset it to initialize it. \n",
    "Resetting also returns an observation of the first state after resetting.\n",
    "In FrozenLake, we always start in the upper left corner, which corresponds to state 0.\n",
    "As such, we see the `reset()` command returning `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.reset()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can visualize the FrozenLake environment by calling `render()`. \n",
    "In more complex tasks this will actually add frames to a video showing our agent's progress, but for FrozenLake, it just prints out a text representation, with the highlighted character showing our agent's current location.\n",
    "We can see that we started in the upper-left corner, on the \"S,\" as promised."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n"
     ]
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's try moving.\n",
    "On thing to keep in mind is that the original FrozenLake environment is \"slippery.\" \n",
    "Because of the ice, if you try to go in one direction, you end up with a 1/3 chance of going in the direction you meant and the two adjacent directions each. \n",
    "For example, if we try going right, we have equal probabilities of slipping and going up and down instead.\n",
    "This makes things a little more complicated, so for now, let's first turn off the stochasticity and make this a deterministic transition instead.\n",
    "We do this by registering a new type of environment, and then instantiating a copy of said environment, making sure to reset it first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Non-slippery version\n",
    "\n",
    "from gym.envs.registration import register\n",
    "register(\n",
    "    id='FrozenLakeNotSlippery-v1',\n",
    "    entry_point='gym.envs.toy_text:FrozenLakeEnv',\n",
    "    kwargs={'map_name' : '4x4', 'is_slippery': False},\n",
    ")\n",
    "env = gym.make('FrozenLakeNotSlippery-v1')\n",
    "env.reset()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We advance time in an OpenAI environment with the `step()` method, which takes as argument an `action`.\n",
    "Let's trying moving right, which corresponds to action `2`.\n",
    "Notice that the output is a tuple of four elements: the next observation (`object`), the reward (`float`), whether or not the episode is done (`boolean`), and a dictionary of information (`dict`) that may be useful for debugging (this dict shouldn't be used in the final algorithm itself)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 0.0, False, {'prob': 1.0})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.step(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let's `render()` to visualize what happened.\n",
    "Observe that this particular environment prints out the action we took in parentheses up top, in this case \"(Right)\", and then shows the result of that action.\n",
    "Notice that while most of the time, we succeed in going in the direction we want to, occasionally we slip on the ice and go in a direction we didn't intend."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (Right)\n",
      "S\u001b[41mF\u001b[0mFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n"
     ]
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can keep doing this as many times as we want.\n",
    "Since we're in Jupyter, we can just keep running the same cell (making small edits to change our action).\n",
    "\n",
    "Notice that once we fall into a hole, the episode is over, and we can no longer do anything.\n",
    "The same is true after reaching the goal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (Right)\n",
      "SF\u001b[41mF\u001b[0mF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n"
     ]
    }
   ],
   "source": [
    "env.step(2)\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we get into any RL, let's see how random actions perform in this environment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Left)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Up)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Down)\n",
      "SFFF\n",
      "\u001b[41mF\u001b[0mHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Left)\n",
      "SFFF\n",
      "\u001b[41mF\u001b[0mHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Up)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Up)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Up)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Up)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Down)\n",
      "SFFF\n",
      "\u001b[41mF\u001b[0mHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Up)\n",
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "  (Down)\n",
      "SFFF\n",
      "\u001b[41mF\u001b[0mHFH\n",
      "FFFH\n",
      "HFFG\n"
     ]
    }
   ],
   "source": [
    "env.reset()\n",
    "done = False\n",
    "\n",
    "while not done:\n",
    "    env.render()\n",
    "    action = env.action_space.sample()\n",
    "    _, _, done, _ = env.step(action)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hm. \n",
    "Not great. \n",
    "Alright, so clearly picking random steps isn't very likely to take us to the goal.\n",
    "It's apparent just from looking at the map that there're much better policies that we can learn.\n",
    "How are we going to do so?\n",
    "\n",
    "#### Q-learning\n",
    "There are many algorithms that we can use, but let's choose Q-learning, which we covered earlier today.\n",
    "Remember, in Q-learning (and SARSA, it turns out), we're trying learn the Q values for the states in our system.\n",
    "\n",
    "The Q value for a policy $\\pi$ is a function of the state $s$ and action $a$ and is defined as the following:\n",
    "\\begin{equation}\n",
    "Q_\\pi (s,a) = \\mathbb{E}\\big[\\sum_{t=0}^{\\infty} \\gamma^t r_t \\big|\\pi, s_0 = s, a_0 = a\\big]\n",
    "\\end{equation}\n",
    "Intuitively, the Q value is the total reward (including discounting) that the agent will gain if it takes action $a$ from state $s$ and then follows policy $\\pi$ for the rest of the episode.\n",
    "As one might expect, if Q is known exactly, the agent will attain the highest reward from $s$ if the policy $\\pi$ is to pick the $a$ with the highest Q value.\n",
    "\n",
    "Okay, so if we know the Q values for the system, then we can trivially find the optimal policy.\n",
    "So what are the Q values of the system?\n",
    "Well, at the beginning, we don't know, but we can try to learn them through experience.\n",
    "This is where Q-learning comes in.\n",
    "Q-learning iteratively updates the Q values in the following way:\n",
    "\\begin{equation}\n",
    "Q_\\pi (s_t, a_t) \\leftarrow (1 - \\alpha) \\cdot Q_\\pi(s_t, a_t) + \\alpha \\cdot \\big(r_t + \\gamma \\max_a Q_\\pi(s_{t+1}, a)\\big)\n",
    "\\end{equation}\n",
    "Notice that Q-learning is an *off-policy* method, in the sense that you don't actually learn from the trajectory you actually took (otherwise it'd be SARSA).\n",
    "Instead, we learn from the *greedy* transition, i.e. the best action we know how to take.\n",
    "\n",
    "And that's it! \n",
    "We run our agent through many episodes, experiencing many $s_t \\rightarrow a_t \\rightarrow s_{t+1}$ transitions and rewards, and just like that, we eventually learn a good Q function (and thus a good policy).\n",
    "Now of course, there are a bunch of small details and tweaks to make this work in practice, but we'll get to those later.\n",
    "\n",
    "#### Q-learning in FrozenLake\n",
    "FrozenLake is a very simple setting, one that we would call a toy problem.\n",
    "With only 16 states and 4 actions, there are only 64 state-action pairs possible (16x4=64), less if we account for the goal and the holes being episode ending (for simplicity though, we won't). \n",
    "With this few state-action pairs, we can actually solve this problem tabularly.\n",
    "Let's set up a Q table, and initialize the Q-values for all state-action pairs to zeros.\n",
    "Note that we're actually not going to need TensorFlow in this example; we'll use a Numpy array to store the Q table."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]\n",
      " [0. 0. 0. 0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "#Initialize table with all zeros to be uniform\n",
    "Q = np.zeros([env.observation_space.n, env.action_space.n])\n",
    "\n",
    "print(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A few hyperparameters we're going to set:\n",
    "- `alpha`: learning rate for the Q function\n",
    "- `gamma`: discount rate for future rewards\n",
    "- `num_episodes`: number of episodes (trajectories from start to goal/hole) our agent will learn from\n",
    "\n",
    "We're also going to store our rewards in an array called `rs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Learning parameters\n",
    "alpha = 0.1\n",
    "gamma = 0.95\n",
    "num_episodes = 2000\n",
    "\n",
    "# array of reward for each episode\n",
    "rs = np.zeros([num_episodes])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now for the bulk of algorithm itself.\n",
    "Notice that we're going to loop through the process `num_episodes` times, resetting the environment each time.\n",
    "At each step, we take the action with the highest Q value for our current state, with some randomness added in (especially at the beginning) to encourage exploration.\n",
    "After each action, we update our Q table greedily based on the reward experienced and the next best action.\n",
    "We also make sure to update our state, rinse, and repeat. \n",
    "We continue taking actions in an episode until it is `done`, storing the final total reward for the episode."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(num_episodes):\n",
    "    # Set total reward and time to zero, done to False\n",
    "    r_sum_i = 0\n",
    "    t = 0\n",
    "    done = False\n",
    "\n",
    "    # Reset environment and get first new observation\n",
    "    s = env.reset()\n",
    "\n",
    "    while not done:\n",
    "        # Choose an action by greedily (with noise) from Q table\n",
    "        a = np.argmax(Q[s,:] + np.random.randn(1, env.action_space.n)*(1./(i/10 + 1)))\n",
    "        \n",
    "        # Get new state and reward from environment\n",
    "        s1, r, done, _ = env.step(a)\n",
    "\n",
    "        # Update Q-Table with new knowledge\n",
    "        Q[s,a] = (1 - alpha)*Q[s,a] + alpha*(r + gamma*np.max(Q[s1,:]))\n",
    "\n",
    "        # Update state and time\n",
    "        s = s1\n",
    "        t += 1\n",
    "        \n",
    "        # Add reward to episode total\n",
    "        r_sum_i += r*gamma**t\n",
    "\n",
    "    rs[i] = r_sum_i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How did we do?\n",
    "Let's take a look at the rewards that we saved.\n",
    "We can plot the reward versus the episode number, and hopefully we'll see some sort of an increase over time.\n",
    "RL performance can be extremely noisy, so let's instead plot a moving average."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD8CAYAAACSCdTiAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGepJREFUeJzt3XtwXOd93vHvQ5AAwZtuhC4mKZGSKDWU40QyLMtxbMeNJVNuQiaO41KTxpLjlOOp2SR1kolct7SjTqZje5rMdMJpQo/U2BnLtGxHNdLSw9iJ20SeSCZ0s0RKlGDqQoi6QJREUsACiwV+/WMPwBW8AM4udrHnrJ/PDIZ7zr5Y/HgWePDiPee8ryICMzNrT0taXYCZmTWPQ97MrI055M3M2phD3sysjTnkzczamEPezKyNOeTNzNqYQ97MrI055M3M2tjSVn3htWvXxsaNG1v15c3Mcun+++9/OSJ60rZvWchv3LiR/v7+Vn15M7NckvRMLe09XGNm1sYc8mZmbcwhb2bWxhzyZmZtzCFvZtbGHPJmZm3MIW9m1sZadp18u/rBU69wz5NDrS7DzDLsF3/qAn5mw9mL8rUc8g30vcdf4qN/dRAAqcXFmFlmnb9muUM+j775wCAA3/3ke7j8/FUtrsbMzGPyDTMxGdwz8DIfvGadA97MMsMh3yBPvTzMayPjXHfpea0uxcxsmkO+QR57/hQAWy5a0+JKzMzOcMg3yL1HT9DZsYTNF3ioxsyyI1XIS9oq6YikAUm3Vnn+zyQ9lHw8Iem1xpeabQ8++xpvv/RcupZ2tLoUM7Np815dI6kD2ANcDwwCByX1RcThqTYR8R8q2v974Oom1Jppr44UuepNHqoxs2xJ05O/FhiIiKMRUQT2AdvnaH8T8NVGFJcnr4+VWNnlK1LNLFvShPw64FjF9mCy78dIugTYBPzDwkvLj4hgeKzEKoe8mWVMmpCvdu9mzNJ2B/CNiJio+kLSTkn9kvqHhtrn1v/C+ASTAauWO+TNLFvShPwgsKFiez1wfJa2O5hjqCYi9kZEb0T09vSkXoc2814fLQF4uMbMMidNyB8ENkvaJKmTcpD3zWwk6UrgHOCfG1ti9r10egyANe7Jm1nGzBvyEVECdgEHgMeAuyLikKTbJG2raHoTsC8iZhvKaVtPvHgagKvedFaLKzEze6NUXc+I2A/sn7Fv94ztzzaurHx55sQIErzp7OWtLsXM7A18x2sDPHNimHVnd7Oi08M1ZpYtDvkGKIxPsNIBb2YZ5JBvgML4JMs7PZ2BmWWPQ74BRosTrFjmkDez7HHIN0BhfIJu9+TNLIMc8g1QGJ+g2z15M8sgh3wDFIoTLHfIm1kGOeQbYHR8gu5OH0ozyx4nUwN4uMbMssohv0AR4ZA3s8xyyC/QWGmSCHydvJllkkN+gYaSGSjdkzezLHLIL9AzJ0YAzyVvZtnkkF+gwnh5EawtF3kRbzPLHof8Ak2FvK+TN7Mscsgv0GixHPKe1sDMssghv0AjxfL6rj7xamZZ5JBfoOGkJ7/CPXkzy6BUIS9pq6QjkgYk3TpLmw9LOizpkKQ7G1tmdhWKEywRdC3170szy555r/uT1AHsAa4HBoGDkvoi4nBFm83Ap4B3RsSrks5vVsFZM1KcYEXnUiS1uhQzsx+Tpvt5LTAQEUcjogjsA7bPaPNvgT0R8SpARLzU2DKza6RY8klXM8usNCG/DjhWsT2Y7Kt0BXCFpO9LulfS1kYVmHUjxQlWOuTNLKPS3KZZbRwiqrzOZuAXgPXAP0l6c0S89oYXknYCOwEuvvjimovNopHiBN1exNvMMipNT34Q2FCxvR44XqXNtyJiPCKeAo5QDv03iIi9EdEbEb09PT311pwpI8WSr6wxs8xKE/IHgc2SNknqBHYAfTPa/C/gvQCS1lIevjnayEKzqnzi1SFvZtk0b8hHRAnYBRwAHgPuiohDkm6TtC1pdgA4Iekw8D3gDyPiRLOKzpKCQ97MMizVYHJE7Af2z9i3u+JxAJ9MPn6iDBdLrPSYvJlllO/gWaBCccKXUJpZZjnkF8hj8maWZQ75BZicLK/vusLDNWaWUQ75BZiaS949eTPLKof8Aox4BkozyziH/AJMzSXv4RozyyqH/AK4J29mWeeQX4ARL/1nZhnnkF+AqeGalV0erjGzbHLIL8B0T97ru5pZRjnkF6CQhLx78maWVQ75BRievrrGPXkzyyaH/AIUfOLVzDLOIb8Ar48lPXmPyZtZRjnkF+DYKwUuWNPF0g4fRjPLJqdTnYqlSb75wCCb1q5sdSlmZrNyyNfp+GsFAH7+8rUtrsTMbHYO+TpNzUB5Wc+qFldiZja7VCEvaaukI5IGJN1a5flbJA1Jeij5+O3Gl5otUyG/3FfWmFmGzXsXj6QOYA9wPTAIHJTUFxGHZzT9WkTsakKNmTTqu13NLAfS9OSvBQYi4mhEFIF9wPbmlpV9noHSzPIgTcivA45VbA8m+2b6NUk/lPQNSRsaUl2GDXtyMjPLgTQhryr7Ysb23wIbI+ItwHeBL1V9IWmnpH5J/UNDQ7VVmjHDY8m8NV4wxMwyLE3IDwKVPfP1wPHKBhFxIiLGks0vAm+t9kIRsTcieiOit6enp556M2N6VaguD9eYWXalCfmDwGZJmyR1AjuAvsoGki6q2NwGPNa4ErNpakoD9+TNLMvmTaiIKEnaBRwAOoA7IuKQpNuA/ojoA35H0jagBLwC3NLEmjNhpDjB8mVL6FhSbTTLzCwbUnVDI2I/sH/Gvt0Vjz8FfKqxpWXbc68VOLu7s9VlmJnNyXe81umFk6Ncdr7nrTGzbHPI16lQnKB7mcfjzSzbHPJ1Gh2f8GIhZpZ5Dvk6FcYn6F7mw2dm2eaUqlM55N2TN7Nsc8jXqVCc8AyUZpZ5Dvk6TE4GY6VJ9+TNLPMc8nUYLXmaYTPLB4d8HQpTc8l7uMbMMs4hX4epueSXuydvZhnnkK/D6LiHa8wsHxzydSg45M0sJxzydfCYvJnlhUO+DlM9eY/Jm1nWOeTr4DF5M8sLh3wdpsfkPVxjZhnnkK9DoTgJuCdvZtnnkK+Dr64xs7xwyNdhakx+eacPn5llW6qUkrRV0hFJA5JunaPdhySFpN7GlZg9heIESwSdHQ55M8u2eVNKUgewB7gR2ALcJGlLlXargd8B7mt0kVkzNZe8pFaXYmY2pzRd0WuBgYg4GhFFYB+wvUq7/wJ8HhhtYH2ZVPDSf2aWE2lCfh1wrGJ7MNk3TdLVwIaI+N9zvZCknZL6JfUPDQ3VXGxWjBYnfCOUmeVCmpCvNiYR009KS4A/A35/vheKiL0R0RsRvT09PemrzBgv/WdmeZEm5AeBDRXb64HjFdurgTcD/1fS08B1QF87n3z1cI2Z5UWakD8IbJa0SVInsAPom3oyIk5GxNqI2BgRG4F7gW0R0d+UijOg4OEaM8uJeUM+IkrALuAA8BhwV0QcknSbpG3NLjCLRj1cY2Y5sTRNo4jYD+yfsW/3LG1/YeFlZVthfIKLHPJmlgO+m6cOHpM3s7xwyNehUJz0mLyZ5YJDvg4ekzezvHDI1ygikuEaHzozyz4nVY3GJ4KJyXBP3sxywSFfI6/vamZ54pCv0aiX/jOzHHHI16hQ9KpQZpYfDvkaDRdLAKxwT97McsAhX6OpnvyKzlQ3C5uZtZRDvkbDSciv7HJP3syyzyFfo0IyXNO9zD15M8s+h3yNhsfckzez/HDI12jEl1CaWY445Gs0MlYerlnpE69mlgMO+RqN+Dp5M8sRh3yNRoolupd1sGRJtfXNzcyyxSFfo5HihE+6mllupAp5SVslHZE0IOnWKs9/XNIjkh6SdI+kLY0vNRtGil4VyszyY96Ql9QB7AFuBLYAN1UJ8Tsj4qcj4meBzwN/2vBKM2J4rOSTrmaWG2l68tcCAxFxNCKKwD5ge2WDiDhVsbkSiMaVmC1e39XM8iRNl3QdcKxiexB4+8xGkj4BfBLoBP5ltReStBPYCXDxxRfXWmsmuCdvZnmSpidf7TKSH+upR8SeiLgM+CPgP1V7oYjYGxG9EdHb09NTW6UZ4TF5M8uTNCE/CGyo2F4PHJ+j/T7gVxZSVJaNFCdY6ZA3s5xIE/IHgc2SNknqBHYAfZUNJG2u2PxXwJONKzFbRooTrOjycI2Z5cO8aRURJUm7gANAB3BHRBySdBvQHxF9wC5J7wPGgVeBm5tZdCuNFEus8N2uZpYTqbqkEbEf2D9j3+6Kx7/b4LoyaXIyKIy7J29m+eE7XmswWpogwkv/mVl+OORrMD2XvEPezHLCIV8Dr+9qZnnjkK/BcLL0n4drzCwvHPI1mJpL3idezSwvHPI1GHFP3sxyxiFfg+mevEPezHLCIV+DMz15D9eYWT445Gsw1ZP3JZRmlhcO+RqMjPnEq5nli0O+BlM9+W7PXWNmOeGQr8FIscTyZUvoWFJtin0zs+xxyNdguFjySVczyxWHfA1GihO+fNLMcsUhX4PXR0sOeTPLFYd8DQZeep3zVna1ugwzs9Qc8jU4WRjn0p6VrS7DzCw1h3wNhoslVvoaeTPLkVQhL2mrpCOSBiTdWuX5T0o6LOmHkv5e0iWNL7W1JiaD0fFJj8mbWa7MG/KSOoA9wI3AFuAmSVtmNHsQ6I2ItwDfAD7f6EJbbWou+VXuyZtZjqTpyV8LDETE0YgoAvuA7ZUNIuJ7ETGSbN4LrG9sma03PaWBr5M3sxxJE/LrgGMV24PJvtl8DPh2tSck7ZTUL6l/aGgofZUZMNWTX9nl4Rozy480IV/tHv6o2lD6N0Av8IVqz0fE3ojojYjenp6e9FVmgHvyZpZHaRJrENhQsb0eOD6zkaT3AZ8G3hMRY40pLzume/I+8WpmOZKmJ38Q2Cxpk6ROYAfQV9lA0tXAXwLbIuKlxpfZetMLhvjEq5nlyLwhHxElYBdwAHgMuCsiDkm6TdK2pNkXgFXA1yU9JKlvlpfLreExLxhiZvmTqlsaEfuB/TP27a54/L4G15U57smbWR75jteU3JM3szxyyKc0POZFvM0sfxzyKZ0eK9G1dAmdS33IzCw/nFgpnR4dZ/XyZa0uw8ysJg75lE4VSqzp9lCNmeWLQz6lE8NjrHFP3sxyxiGfwsnCOPcefYVTo+OtLsXMrCYO+RReOjUKwLUbz21xJWZmtXHIp/DHf3sYgPdfdWGLKzEzq41DPoV7Bl4G8NJ/ZpY7DvkaeC55M8sbh/w8Is5Mnb+6y1fXmFm+OOTn8ftff3j68VndDnkzyxeH/ByKpUn+5oHnAPjjbVdx1gqHvJnli88kzuF0cl38bduv4iPv2NjaYszM6uCe/Bxefr0IeJjGzPLLIT+HZ04MA7Bp7coWV2JmVh+H/BxGiuWFQjz7pJnlVaqQl7RV0hFJA5JurfL8uyU9IKkk6UONL7M1hqeW/PNqUGaWU/OGvKQOYA9wI7AFuEnSlhnNngVuAe5sdIGtNJIs+eeQN7O8SnN1zbXAQEQcBZC0D9gOHJ5qEBFPJ89NNqHGljnTk/dFSGaWT2mGa9YBxyq2B5N9ba9QnKBr6RI6lqjVpZiZ1SVNyFdLuKiyb/4XknZK6pfUPzQ0VM9LLKrhYsmTkplZrqUJ+UFgQ8X2euB4PV8sIvZGRG9E9Pb09NTzEotqZGzC4/FmlmtpQv4gsFnSJkmdwA6gr7llZcNI0SFvZvk2b8hHRAnYBRwAHgPuiohDkm6TtA1A0tskDQK/DvylpEPNLHqxDBdLPulqZrmWKsEiYj+wf8a+3RWPD1IexmkrI8UJzyFvZrnmO17nMDzmnryZ5ZtDfg6FcY/Jm1m+OeRnMXR6jGdOjDjkzSzXPBYxw90PDtL30HG+/6MTAFzWs6rFFZmZ1c8hP8NX7zvG4edPUSyVZ2h41+bsX89vZjYbD9fM8PpYiesuPXd6e023fw+aWX455CsceeE0h58/9YapDNZ4Lnkzy7G2DflHBk9y+z1P8dUfPDs99DKfux8sL9r9zsvWTu/ziVczy7O2HYv4TN+jPPDsawBceNZy3nvl+fN+zvBYiXNWLOPDb9vAs6+M8MpIEckzUJpZfrVtyJ8eLfEvLlzN4y+c5okXTvPuzT1zThl8dOh1Hn/h1PTNT3/w/isXq1Qzs6Zp2+GakeIEF5+7giWC//rtx9n7j0fnbP8f736Eg0+/yrpzuhepQjOz5mvbnnxhfILz13Tx9Y+/g9+8/Qf8n0eO073szO+0VcuX8cGr17FkiXj+ZIF7j77Cz6w/iy//1rUtrNrMrLHaNuRHkhkk33rJuaxevpRHnzvFo88dfkObKy5YxVvWn83//P7TADw8eJLly3yi1czaR1sM19x537O87U++y2e+9SgAk5PB6Pgk3UlgTwX3LT+3kQf/8/XcfnMvUB63h/Iyf2Zm7agtQv7eoycYOj3Gdw6/yPBYiRPDReDM5Y/rk3H2n7poNees7KRndRcAJwvjFEuT09fF/8mvvrkF1ZuZNU9bDNcUxss98eMnR7nqMwem969aXv7v3XHL23h1eJwL1pTDfSr8/91XHphu272sg994+yWLVbKZ2aLIfciPlSY4WRhn3dndfPSdG5mM8hrjS5cs4Zd++k0AdC3t4MKzzoy1d1fMEf+HyaWSl5/vicjMrP3kPuR37L2XB599jfdc0cNvv+vSVJ+zouLk6ifee3mzSjMza7lUY/KStko6ImlA0q1Vnu+S9LXk+fskbWx0obM5OjTMz112Hrt/eUvqz+n2VAVm9hNi3p68pA5gD3A9MAgclNQXEZXXI34MeDUiLpe0A/gc8K+bUfBdB4/xxX86c2PTycI4vZecU9O8711Ly7/bLlyzvOH1mZllSZrhmmuBgYg4CiBpH7AdqAz57cBnk8ffAP5ckiKSAfIGOnvFMjZfcCbQr7xwNR94y0U1vYYk9v7mW7nkvJWNLs/MLFPShPw64FjF9iDw9tnaRERJ0kngPODlRhRZ6YarLuSGqy5syOuYmbW7NGPy1Wb1mtlDT9MGSTsl9UvqHxoaSlOfmZktQJqQHwQ2VGyvB47P1kbSUuAs4JWZLxQReyOiNyJ6e3q8rJ6ZWbOlCfmDwGZJmyR1AjuAvhlt+oCbk8cfAv6hGePxZmZWm3nH5JMx9l3AAaADuCMiDkm6DeiPiD7gduCvJQ1Q7sHvaGbRZmaWTqqboSJiP7B/xr7dFY9HgV9vbGlmZrZQbTFBmZmZVeeQNzNrYw55M7M2plZdBCNpCHimzk9fSxNutGoQ11Yf11Yf11afPNd2SUSkvga9ZSG/EJL6I6K31XVU49rq49rq49rq85NUm4drzMzamEPezKyN5TXk97a6gDm4tvq4tvq4tvr8xNSWyzF5MzNLJ689eTMzSyF3IT/fUoSL8PU3SPqepMckHZL0u8n+z0p6TtJDyccHKj7nU0m9RyS9v8n1PS3pkaSG/mTfuZK+I+nJ5N9zkv2S9N+T2n4o6Zom1nVlxbF5SNIpSb/XquMm6Q5JL0l6tGJfzcdJ0s1J+ycl3VztazWoti9Iejz5+ndLOjvZv1FSoeL4/UXF57w1+V4YSOqvNiV4I2qr+T1sxs/xLLV9raKupyU9lOxf7OM2W240/3suInLzQXmCtB8BlwKdwMPAlkWu4SLgmuTxauAJYAvllbH+oEr7LUmdXcCmpP6OJtb3NLB2xr7PA7cmj28FPpc8/gDwbcrrAVwH3LeI7+MLwCWtOm7Au4FrgEfrPU7AucDR5N9zksfnNKm2G4ClyePPVdS2sbLdjNf5AfCOpO5vAzc2qbaa3sNm/RxXq23G8/8N2N2i4zZbbjT9ey5vPfnppQgjoghMLUW4aCLi+Yh4IHl8GniM8spYs9kO7IuIsYh4Chig/P9YTNuBLyWPvwT8SsX+L0fZvcDZkmpbS7E+vwj8KCLmuhmuqcctIv6RH1/zoNbj9H7gOxHxSkS8CnwH2NqM2iLi7yKilGzeS3ldh1kl9a2JiH+Ocjp8ueL/09Da5jDbe9iUn+O5akt64x8GvjrXazTxuM2WG03/nstbyFdbinCugG0qSRuBq4H7kl27kj+t7pj6s4vFrzmAv5N0v6Sdyb4LIuJ5KH+zAee3qLYpO3jjD1sWjhvUfpxadfx+i3Ivb8omSQ9K+n+S3pXsW5fUs1i11fIetuK4vQt4MSKerNjXkuM2Izea/j2Xt5BPtczgYpC0Cvgm8HsRcQr4H8BlwM8Cz1P+0xAWv+Z3RsQ1wI3AJyS9e462i348VV54Zhvw9WRXVo7bXGarpRXH79NACfhKsut54OKIuBr4JHCnpDWLXFut72Er3tubeGPHoiXHrUpuzNp0ljpqri9vIZ9mKcKmk7SM8hv1lYj4G4CIeDEiJiJiEvgiZ4YWFrXmiDie/PsScHdSx4tTwzDJvy+1orbEjcADEfFiUmcmjlui1uO0qDUmJ9l+CfiNZCiBZCjkRPL4fspj3VcktVUO6TSttjrew8U+bkuBDwJfq6h50Y9btdxgEb7n8hbyaZYibKpkbO924LGI+NOK/ZVj2b8KTJ3h7wN2SOqStAnYTPnETjNqWylp9dRjyifrHuWNyzPeDHyroraPJGfyrwNOTv3p2ERv6FFl4bhVqPU4HQBukHROMkRxQ7Kv4SRtBf4I2BYRIxX7eyR1JI8vpXycjib1nZZ0XfI9+5GK/0+ja6v1PVzsn+P3AY9HxPQwzGIft9lyg8X4nlvoWePF/qB81vkJyr95P92Cr//zlP88+iHwUPLxAeCvgUeS/X3ARRWf8+mk3iM04Ez9HLVdSvlKhYeBQ1PHBzgP+HvgyeTfc5P9AvYktT0C9Db52K0ATgBnVexryXGj/IvmeWCccu/oY/UcJ8rj4wPJx0ebWNsA5bHYqe+5v0ja/lryXj8MPAD8csXr9FIO3B8Bf05y82MTaqv5PWzGz3G12pL9fwV8fEbbxT5us+VG07/nfMermVkby9twjZmZ1cAhb2bWxhzyZmZtzCFvZtbGHPJmZm3MIW9m1sYc8mZmbcwhb2bWxv4/uY3W5stGQ00AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "## Plot reward vs episodes\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# Sliding window average\n",
    "r_cumsum = np.cumsum(np.insert(rs, 0, 0))\n",
    "r_smoothed = (r_cumsum[50:] - r_cumsum[:-50]) / 50\n",
    "\n",
    "# Plot\n",
    "plt.plot(r_smoothed)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7350918906249998"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0.95**6*1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretty good.\n",
    "We might also be interested in how often our agent actually reached the goal.\n",
    "This won't account for how quickly the agent got there (which might also of interest), but let's ignore that for now.\n",
    "To prevent us from being overwhelmed by data points, let's bucket the values into 10 stages, printing out how many episodes of each stage resulted in finding the goal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rewards: [ 10. 173. 200. 200. 200. 200. 200. 200. 200. 200.]\n"
     ]
    }
   ],
   "source": [
    "# Print number of times the goal was reached\n",
    "N = len(rs)//10\n",
    "num_Gs = np.zeros(10)\n",
    "\n",
    "for i in range(10):\n",
    "    num_Gs[i] = np.sum(rs[i*N:(i+1)*N] > 0)\n",
    "    \n",
    "print(\"Rewards: {0}\".format(num_Gs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our RL agent does a really good job at navigating the FrozenLake when its moves are deterministic, but after all, this is\n",
    "supposed to be *Frozen*Lake, so where's the fun without the slipperiness?\n",
    "Let's go back to the original environment and see how the agent does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Slippery version\n",
    "env = gym.make(\"FrozenLake-v0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TensorFlow in RL\n",
    "Hey, not bad.\n",
    "However, while the previous example was fun and simple, it was noticeably lacking any hint of TensorFlow.\n",
    "After all, this is supposed to be a TensorFlow session, so we should probably remedy that.\n",
    "\n",
    "We could have used a TensorFlow `Variable` to store the Q table and added the appropriate update ops to our computation graph, but that's a rather contrived way to force TensorFlow into the problem.\n",
    "TensorFlow's true utility comes from building neural networks and calculating/applying gradients automatically, which learning the Q table didn't need. \n",
    "\n",
    "#### Continuous domains\n",
    "In our previous example, we mentioned that with only 16 discrete states and 4 actions/state, the Q table only needed to hold 64 values, which is very manageable.\n",
    "However, what if the state or action space is continuous?\n",
    "You could discretize it, but then you have to pick a resolution, and your state-action space could explode exponentially.\n",
    "Treating these binned states or actions as completely different states is also ignoring that two consecutive bins are likely very similar in the needed policy.\n",
    "You can learn these relationships, but doing so is horriby sample inefficient.\n",
    "\n",
    "Instead of learning a Q table then, perhaps a Q function would be more appropriate.\n",
    "This function would take in a state and action as an input and return a Q value as an output.\n",
    "The Q function may be very complex, but as we've learned over the past few days, neural networks are very flexible and good for approximating arbitrary functions.\n",
    "Such an approach is called a [Deep Q Network](https://deepmind.com/research/dqn/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cart Pole"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the cart pole problem next. \n",
    "In this setting, we have a pole attached to a hinge on a cart, with the goal being to keep the pole as vertical as possible.\n",
    "Because of gravity, the pole will fall unless the cart is exactly beneath the the pole's center of gravity.\n",
    "To prevent the pole from falling, the agent can apply a force of +1 or -1 to the cart to move it left and right along a track.\n",
    "The agent receives a reward of +1 for every timestamp the pole remains vertical; the game ends when the pole fall past 15 degrees from vertical or the cart moves more than 2.4 units away from the center.\n",
    "\n",
    "<img src=\"Figures/polebalance.gif\" alt=\"polebalance\" style=\"width: 400px;\"/>\n",
    "\n",
    "First, let's create an instance of the cart pole environment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[33mWARN: gym.spaces.Box autodetected dtype as <class 'numpy.float32'>. Please provide explicit dtype.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "env = gym.make(\"CartPole-v0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, we can look at the `observation_space` for this environment.\n",
    "Also similar to FrozenLake, since this version of cart pole is an MDP (as opposed to POMDP), the observation is the state itself.\n",
    "We can see that the states for cart pole have 4 dimensions, which correspond to `[cart position, cart velocity, pole angle, pole angular velocity]`.\n",
    "Importantly, notice these states are *continuous* values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Box(4,)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.observation_space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can look at the `action_space` again too.\n",
    "In cart pole, there are two actions available to the agent: `[apply force left, apply force right]`.\n",
    "We can see this by examining the `action_space` attribute:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Discrete(2)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.action_space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Resetting the environment return our first observations, which we can see has 4 values corresponding to the 4 previously mentioned state variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-0.0021503 ,  0.02720107,  0.01242241, -0.04324103])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.reset()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we get into any reinforcement learning, let's see how we perform actions within the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "done = False\n",
    "\n",
    "while not done:\n",
    "    env.render()\n",
    "    action = env.action_space.sample()\n",
    "    _, _, done, _ = env.step(action)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Okay, so clearly choosing a random action at every time step doesn't really achieve our goal of keeping the pole vertical.\n",
    "Let's close that rendering window."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cart pole is actually a fairly simple problem (it's very low dimensional), and so there are simpler ways to do this, but since we've been having so much fun with neural networks these past few days, let's use a neural network.\n",
    "Specifically, let's build a DQN that uses Q-learning to learn how to balance the pole.\n",
    "There are a lot of small details that go into making these models work well, so instead of coding it live, I've included the full code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[33mWARN: gym.spaces.Box autodetected dtype as <class 'numpy.float32'>. Please provide explicit dtype.\u001b[0m\n",
      "[Episode 0] - Mean survival time over last 100 episodes was 15.0 ticks.\n",
      "[Episode 100] - Mean survival time over last 100 episodes was 11.36 ticks.\n",
      "[Episode 200] - Mean survival time over last 100 episodes was 22.66 ticks.\n",
      "[Episode 300] - Mean survival time over last 100 episodes was 30.94 ticks.\n",
      "[Episode 400] - Mean survival time over last 100 episodes was 41.22 ticks.\n",
      "[Episode 500] - Mean survival time over last 100 episodes was 142.94 ticks.\n",
      "[Episode 600] - Mean survival time over last 100 episodes was 116.0 ticks.\n",
      "[Episode 700] - Mean survival time over last 100 episodes was 129.9 ticks.\n",
      "[Episode 800] - Mean survival time over last 100 episodes was 135.51 ticks.\n",
      "[Episode 900] - Mean survival time over last 100 episodes was 156.83 ticks.\n",
      "Did not solve after 999 episodes 😞\n"
     ]
    }
   ],
   "source": [
    "# Based on: https://gym.openai.com/evaluations/eval_EIcM1ZBnQW2LBaFN6FY65g/\n",
    "\n",
    "import random\n",
    "import gym\n",
    "import math\n",
    "import numpy as np\n",
    "import tensorflow as tf\n",
    "from collections import deque\n",
    "\n",
    "class DQNCartPoleSolver():\n",
    "    def __init__(self, n_episodes=1000, n_win_ticks=195, max_env_steps=None, gamma=1.0, epsilon=1.0, epsilon_min=0.01, epsilon_log_decay=0.995, alpha=0.01, alpha_decay=0.01, batch_size=64, monitor=False, quiet=False):\n",
    "        self.memory = deque(maxlen=100000)\n",
    "        self.env = gym.make('CartPole-v0')\n",
    "        if monitor: self.env = gym.wrappers.Monitor(self.env, '../data/cartpole-1', force=True)\n",
    "        self.gamma = gamma\n",
    "        self.epsilon = epsilon\n",
    "        self.epsilon_min = epsilon_min\n",
    "        self.epsilon_decay = epsilon_log_decay\n",
    "        self.alpha = alpha\n",
    "        self.alpha_decay = alpha_decay\n",
    "        self.n_episodes = n_episodes\n",
    "        self.n_win_ticks = n_win_ticks\n",
    "        self.batch_size = batch_size\n",
    "        self.quiet = quiet\n",
    "        if max_env_steps is not None: self.env._max_episode_steps = max_env_steps\n",
    "\n",
    "        # Init model\n",
    "        self.state_ = tf.placeholder(tf.float32, shape=[None, 4])\n",
    "        h = tf.layers.dense(self.state_, units=24, activation=tf.nn.tanh)\n",
    "        h = tf.layers.dense(h, units=48, activation=tf.nn.tanh)\n",
    "        self.Q = tf.layers.dense(h, units=2)\n",
    "        \n",
    "        self.Q_ = tf.placeholder(tf.float32, shape=[None, 2])\n",
    "        loss = tf.losses.mean_squared_error(self.Q_, self.Q)\n",
    "        self.global_step = tf.Variable(0, name='global_step', trainable=False)\n",
    "        lr = tf.train.exponential_decay(0.01, self.global_step, 0.995, 1)\n",
    "        self.train_step = tf.train.AdamOptimizer(lr).minimize(loss, global_step=self.global_step)\n",
    "        \n",
    "        self.sess = tf.Session()\n",
    "        self.sess.run(tf.global_variables_initializer())\n",
    "\n",
    "    def remember(self, state, action, reward, next_state, done):\n",
    "        self.memory.append((state, action, reward, next_state, done))\n",
    "\n",
    "    def choose_action(self, state, epsilon):\n",
    "        return self.env.action_space.sample() if (np.random.random() <= epsilon) else np.argmax(self.sess.run(self.Q, feed_dict={self.state_: state}))\n",
    "\n",
    "    def get_epsilon(self, t):\n",
    "        return max(self.epsilon_min, min(self.epsilon, 1.0 - math.log10((t + 1) * self.epsilon_decay)))\n",
    "\n",
    "    def preprocess_state(self, state):\n",
    "        return np.reshape(state, [1, 4])\n",
    "\n",
    "    def replay(self, batch_size):\n",
    "        x_batch, y_batch = [], []\n",
    "        minibatch = random.sample(\n",
    "            self.memory, min(len(self.memory), batch_size))\n",
    "        for state, action, reward, next_state, done in minibatch:\n",
    "            y_target = self.sess.run(self.Q, feed_dict={self.state_: state})\n",
    "            y_target[0][action] = reward if done else reward + self.gamma * np.max(self.sess.run(self.Q, feed_dict={self.state_: next_state})[0])\n",
    "            x_batch.append(state[0])\n",
    "            y_batch.append(y_target[0])\n",
    "        \n",
    "        self.sess.run(self.train_step, feed_dict={self.state_: np.array(x_batch), self.Q_: np.array(y_batch)})\n",
    "\n",
    "        if self.epsilon > self.epsilon_min:\n",
    "            self.epsilon *= self.epsilon_decay\n",
    "\n",
    "    def run(self):\n",
    "        scores = deque(maxlen=100)\n",
    "\n",
    "        for e in range(self.n_episodes):\n",
    "            state = self.preprocess_state(self.env.reset())\n",
    "            done = False\n",
    "            i = 0\n",
    "            while not done:\n",
    "                if e % 100 == 0 and not self.quiet:\n",
    "                    self.env.render()\n",
    "                action = self.choose_action(state, self.get_epsilon(e))\n",
    "                next_state, reward, done, _ = self.env.step(action)\n",
    "                next_state = self.preprocess_state(next_state)\n",
    "                self.remember(state, action, reward, next_state, done)\n",
    "                state = next_state\n",
    "                i += 1\n",
    "\n",
    "            scores.append(i)\n",
    "            mean_score = np.mean(scores)\n",
    "            if mean_score >= self.n_win_ticks and e >= 100:\n",
    "                if not self.quiet: print('Ran {} episodes. Solved after {} trials ✔'.format(e, e - 100))\n",
    "                return e - 100\n",
    "            if e % 100 == 0 and not self.quiet:\n",
    "                print('[Episode {}] - Mean survival time over last 100 episodes was {} ticks.'.format(e, mean_score))\n",
    "\n",
    "            self.replay(self.batch_size)\n",
    "        \n",
    "        if not self.quiet: print('Did not solve after {} episodes 😞'.format(e))\n",
    "        return e\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    agent = DQNCartPoleSolver()\n",
    "    agent.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Other materials:\n",
    "Reinforcement Learning can easily be a full course (or 2) on its own at most universities.\n",
    "Given limited time, we can only touch on a couple points.\n",
    "If you're interested in *exploring* this field further, a few recommendations to get you started:\n",
    "\n",
    "- [The definitive textbook on Reinforcement Learning](http://incompleteideas.net/book/the-book-2nd.html)\n",
    "- [Video lectures by David Silver](https://www.youtube.com/playlist?list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ)\n",
    "- [Deep Q-Networks (DQN) for Atari 2600 games](https://deepmind.com/research/dqn/) \n",
    "- [Popular blog post on using policy gradients to learn to play Pong from pixels](http://karpathy.github.io/2016/05/31/rl/)\n",
    "- [An amusing video of DeepMind AI learning to walk](https://www.youtube.com/watch?v=gn4nRCC9TwQ) "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}