session1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Session 1: Escaping GridWorld with Simple RL Agents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Colab Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#uncomment only if you're running from google colab\n",
    "# !git clone https://github.com/Datatouille/rl-workshop\n",
    "# !mv rl-workshop/* .\n",
    "# !ls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "from collections import defaultdict\n",
    "import matplotlib.pyplot as plt\n",
    "#cross check with our solutions once you finish\n",
    "# from solutions.agents import GridworldAgent\n",
    "from solutions.environments import Gridworld"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is Reinforcement Learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/SvXXpmXedHE\" frameborder=\"0\" allow=\"autoplay; encrypted-media\" allowfullscreen></iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%HTML\n",
    "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/SvXXpmXedHE\" frameborder=\"0\" allow=\"autoplay; encrypted-media\" allowfullscreen></iframe>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/Ru5xQPZPRUI\" frameborder=\"0\" allow=\"autoplay; encrypted-media\" allowfullscreen></iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%HTML\n",
    "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/Ru5xQPZPRUI\" frameborder=\"0\" allow=\"autoplay; encrypted-media\" allowfullscreen></iframe>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How Useful is Reinforcement Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deep reinforcement learning has been successful (better than or equal to supervised learning) in:\n",
    "* Beating professional [Go players](https://deepmind.com/research/alphago/), [Flappy Bird](https://www.youtube.com/watch?v=hri7ir5qhj0) and, to some extent [DotA players](https://youtu.be/UZHTNBMAfAA?t=2m40s).\n",
    "* Reduce data center power usage and [save 40% of electricity bill](https://deepmind.com/blog/deepmind-ai-reduces-google-data-centre-cooling-bill-40/)\n",
    "* Neural architecture search for better algorithms aka [AutoML](https://cloud.google.com/automl/)\n",
    "* Control tasks for robotics like [this](https://www.youtube.com/watch?v=W_gxLKSsSIE) and [this](https://www.youtube.com/watch?v=gn4nRCC9TwQ)\n",
    "* [Self-driving cars](https://www.youtube.com/watch?v=opsmd5yuBF0)\n",
    "* [Ads bidding](http://wnzhang.net/papers/rlb.pdf)\n",
    "\n",
    "And most likely being tried for:\n",
    "* [Algorithmic trading](http://www.wildml.com/2018/02/introduction-to-learning-to-trade-with-reinforcement-learning/)\n",
    "* [Supply chain management](https://www.youtube.com/watch?v=gQa6iWGcGWY)\n",
    "* Drug discovery\n",
    "* Security\n",
    "* Recommendation engines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why is Reinforcement Learning Different"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Level of workflow automation in classes of machine learning algorithm:\n",
    "* Supervised Learning\n",
    "$$\\text{Raw Data (X,y)} \\Rightarrow \\text{Labeled Data} \\rightarrow \\text{Model} \\rightarrow \\text{Predicted Labels} \\Rightarrow \\text{Actions}$$\n",
    "\n",
    "* Unsupervised Learning\n",
    "$$\\text{Raw Data (X)} \\rightarrow \\text{Model} \\rightarrow \\text{Predicted Clusters} \\Rightarrow \\text{Labled Clusters} \\Rightarrow \\text{Actions}$$\n",
    "\n",
    "* Reinforcement Learning\n",
    "$$\\text{Raw Data} \\Rightarrow \\text{RL Scheme (S,A,R,S',A')} \\rightarrow \\text{Model} \\rightarrow \\text{Action}$$\n",
    "\n",
    "\n",
    "where $\\Rightarrow$ denotes transformations that require humans and $\\rightarrow$ denotes those that do not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fill in The Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict\n",
    "import sys\n",
    "\n",
    "\"\"\"\n",
    "Coding assignment order:\n",
    "1. select_action\n",
    "2. get_v\n",
    "\"\"\"\n",
    "\n",
    "class GridworldAgent:\n",
    "    def __init__(self, env, policy, gamma = 0.9, \n",
    "                 start_epsilon = 0.9, end_epsilon = 0.1, epsilon_decay = 0.9):\n",
    "        self.env = env\n",
    "        self.n_action = len(self.env.action_space)\n",
    "        self.policy = policy\n",
    "        self.gamma = gamma\n",
    "        self.v = dict.fromkeys(self.env.state_space,0)\n",
    "        self.n_v = dict.fromkeys(self.env.state_space,0)\n",
    "        self.q = defaultdict(lambda: np.zeros(self.n_action))\n",
    "        self.n_q = defaultdict(lambda: np.zeros(self.n_action))\n",
    "        self.start_epsilon = start_epsilon\n",
    "        self.end_epsilon = end_epsilon\n",
    "        self.epsilon_decay = epsilon_decay\n",
    "    def get_epsilon(self,n_episode):\n",
    "        epsilon = max(self.start_epsilon * (self.epsilon_decay**n_episode),self.end_epsilon)\n",
    "        return(epsilon)\n",
    "    def get_v(self,start_state,epsilon = 0.):\n",
    "        episode = self.run_episode(start_state,epsilon)\n",
    "        \"\"\"\n",
    "        Write the code to calculate the state value function of a state \n",
    "        given a deterministic policy.\n",
    "        \"\"\"\n",
    "        episode = self.run_episode(start_state,epsilon)\n",
    "        v=0\n",
    "        return(v)\n",
    "    def get_q(self, start_state, first_action, epsilon=0.):\n",
    "        episode = self.run_episode(start_state,epsilon,first_action)\n",
    "        q = np.sum([episode[i][2] * self.gamma**i for i in range(len(episode))])\n",
    "        return(q)\n",
    "    def select_action(self,state,epsilon):\n",
    "        \"\"\"\n",
    "        Currently the agent only selects a random action.\n",
    "        Write the code to make the agent perform \n",
    "        according to an epsilon-greedy policy.\n",
    "        \"\"\"\n",
    "        probs = np.ones(self.n_action) * (1 / self.n_action)\n",
    "        action = np.random.choice(np.arange(self.n_action),p=probs)\n",
    "        return(action)\n",
    "    def print_policy(self):\n",
    "        for i in range(self.env.sz[0]):\n",
    "            print('\\n----------')\n",
    "            for j in range(self.env.sz[1]):\n",
    "                p=self.policy[(i,j)]\n",
    "                out = self.env.action_text[p]\n",
    "                print(f'{out} |',end='')\n",
    "    def print_v(self, decimal = 1):\n",
    "        for i in range(self.env.sz[0]):\n",
    "            print('\\n---------------')\n",
    "            for j in range(self.env.sz[1]):\n",
    "                out=np.round(self.v[(i,j)],decimal)\n",
    "                print(f'{out} |',end='')\n",
    "    def run_episode(self, start, epsilon, first_action = None):\n",
    "        result = []\n",
    "        state = self.env.reset(start)\n",
    "        #dictate first action to iterate q\n",
    "        if first_action is not None:\n",
    "            action = first_action\n",
    "            next_state,reward,done = self.env.step(action)\n",
    "            result.append((state,action,reward,next_state,done))\n",
    "            state = next_state\n",
    "            if done: return(result)\n",
    "        while True:\n",
    "            action = self.select_action(state,epsilon)\n",
    "            next_state,reward,done = self.env.step(action)\n",
    "            result.append((state,action,reward,next_state,done))\n",
    "            state = next_state\n",
    "            if done: break\n",
    "        return(result)\n",
    "    def update_policy_q(self):\n",
    "        for state in self.env.state_space:\n",
    "            self.policy[state] = np.argmax(self.q[state])\n",
    "    def mc_predict_v(self,n_episode=10000,first_visit=True):\n",
    "        for t in range(n_episode):\n",
    "            traversed = []\n",
    "            e = self.get_epsilon(t)\n",
    "            transitions = self.run_episode(self.env.start,e)\n",
    "            states,actions,rewards,next_states,dones = zip(*transitions)\n",
    "            for i in range(len(transitions)):\n",
    "                if first_visit and (states[i] not in traversed):\n",
    "                    traversed.append(states[i])\n",
    "                    self.n_v[states[i]]+=1\n",
    "                    discounts = np.array([self.gamma**j for j in range(len(transitions)+1)])\n",
    "                    self.v[states[i]]+= sum(rewards[i:]*discounts[:-(1+i)])\n",
    "        for state in self.env.state_space:\n",
    "            if state != self.env.goal:\n",
    "                self.v[state] = self.v[state] / self.n_v[state]\n",
    "            else:\n",
    "                self.v[state] = 0\n",
    "    \n",
    "    def mc_predict_q(self,n_episode=10000,first_visit=True):\n",
    "        for t in range(n_episode):\n",
    "            traversed = []\n",
    "            e = self.get_epsilon(t)\n",
    "            transitions = self.run_episode(self.env.start,e)\n",
    "            states,actions,rewards,next_states,dones = zip(*transitions)\n",
    "            for i in range(len(transitions)):\n",
    "                if first_visit and ((states[i],actions[i]) not in traversed):\n",
    "                    traversed.append((states[i],actions[i]))\n",
    "                    self.n_q[states[i]][actions[i]]+=1\n",
    "                    discounts = np.array([self.gamma**j for j in range(len(transitions)+1)])\n",
    "                    self.q[states[i]][actions[i]]+= sum(rewards[i:]*discounts[:-(1+i)])\n",
    "                elif not first_visit:\n",
    "                    self.n_q[states[i]][actions[i]]+=1\n",
    "                    discounts = np.array([self.gamma**j for j in range(len(transitions)+1)])\n",
    "                    self.q[states[i]][actions[i]]+= sum(rewards[i:]*discounts[:-(1+i)])\n",
    "\n",
    "        #print(self.q,self.n_q)\n",
    "        for state in self.env.state_space:\n",
    "            for action in range(self.n_action):\n",
    "                if state != self.env.goal:\n",
    "                    self.q[state][action] = self.q[state][action] / self.n_q[state][action]\n",
    "                else:\n",
    "                    self.q[state][action] = 0\n",
    "        \n",
    "    def mc_control_q(self,n_episode=10000,first_visit=True):\n",
    "        self.mc_predict_q(n_episode,first_visit)\n",
    "        self.update_policy_q()\n",
    "        \n",
    "    def mc_control_glie(self,n_episode=10000,first_visit=True,lr=0.):\n",
    "        for t in range(n_episode):\n",
    "            traversed = []\n",
    "            e = self.get_epsilon(t)\n",
    "            transitions = self.run_episode(self.env.start,e)\n",
    "            states,actions,rewards,next_states,dones = zip(*transitions)\n",
    "            for i in range(len(transitions)):\n",
    "                if first_visit and ((states[i],actions[i]) not in traversed):\n",
    "                    traversed.append((states[i],actions[i]))\n",
    "                    self.n_q[states[i]][actions[i]]+=1\n",
    "                    discounts = np.array([self.gamma**j for j in range(len(transitions)+1)])\n",
    "                    g = sum(rewards[i:]*discounts[:-(1+i)])\n",
    "                    if lr > 0:\n",
    "                        a = lr\n",
    "                    else:\n",
    "                        a = (1/self.n_q[states[i]][actions[i]])\n",
    "                    self.q[states[i]][actions[i]]+= a*(g - self.q[states[i]][actions[i]])\n",
    "                    self.update_policy_q()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reinforcement Learning Framework"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reinforcement learning formulates interaction between an **agent** and its **environment** as **Markov decision processes**. For a given **state**, an agent takes an **action** based on the current **state**. In response to that action at that state, the agent will then get some **reward** from the environment, and that state changes to the next one.\n",
    "\n",
    "$S_0 \\rightarrow A_0 \\rightarrow R_1 \\rightarrow S_1 \\rightarrow A_1 \\rightarrow R_2 \\rightarrow S_2 \\rightarrow ... \\rightarrow S_{t-1} \\rightarrow A_{t-1} \\rightarrow R_t \\rightarrow S_{t}$\n",
    "\n",
    "where $t$ is the last time step and $S_t$ is the **terminal state** meaning an **episode** of the interactions ended. RL problems that have an end are called **episodic tasks** and those that do not are called **continuous tasks**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![RL Framework](img/rl_framework.png)\n",
    "Source: [Sutton and Barto](https://cdn.preterhuman.net/texts/science_and_technology/artificial_intelligence/Reinforcement%20Learning%20%20An%20Introduction%20-%20Richard%20S.%20Sutton%20,%20Andrew%20G.%20Barto.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "\n",
    "* Walking robots\n",
    "    * Environment: sidewalks\n",
    "    * Agent: a robot\n",
    "    * States: positions, velocities and accelerations of body parts\n",
    "    * Actions: move arms, legs, various joints in the body\n",
    "    * Rewards: fall or not\n",
    "    * Episodes: seconds, miliseconds until fall\n",
    "* Ads bidding\n",
    "    * Environment: Google Adwords\n",
    "    * Agent: an ecommerce company\n",
    "    * States: campaign impressions, clicks, purchases\n",
    "    * Actions: adjust bid prices and budget\n",
    "    * Rewards: conversion rates, cost of new customer acquisitions\n",
    "    * Episodes: daily or hourly until campaign ends\n",
    "* Retail stock trading\n",
    "    * Environment: the stock market\n",
    "    * Agent: a retail investor who cannot influence market prices\n",
    "    * States: market prices, volumes, and other indicators\n",
    "    * Actions: buy, hold, sell\n",
    "    * Rewards: returns, returns adjusted by volatility, and so on\n",
    "    * Episodes: daily, hourly, every second until we are extremely rich or broke\n",
    "    \n",
    "**Concept Assigment** Come up with one or more scenarios that you think could be framed as a reinforcement learning problem and list their elements like the example above. Some candidates are:\n",
    "* [AlphaGo](https://deepmind.com/research/alphago/)\n",
    "* [OpenAI Five Dota Bots](https://openai.com/five/)\n",
    "* [Pancake-flipping Robots](https://www.youtube.com/watch?v=W_gxLKSsSIE&list=PL5nBAYUyJTrM48dViibyi68urttMlUv7e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Markov Property - One-step Dynamics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the most fundamental assumptions of many reinforcement learning algorithms is that the interactions of the world has **Markov property**. That is, the transitions between states only depend on the current state and action, and not the history of transitions formulated as:\n",
    "\n",
    "$$P(s_{t+1},r_{t+1}|s_t,a_t,r_t,s_{t-1},a_{t-1},...,r_1,s_0,a_0) = P(s_{t+1},r_{t+1}|s_t,a_t)$$\n",
    "\n",
    "This can be seen as unrealistic as we intuitively use cues from a history of transitions to choose our actions in real life but as you will learn its simplicity has merits in terms of reduced complexity in real-world applications and we can incorporate long-term goals into reinforcement learning. In fact, long-term goals are one of the most important research area in reinforcement learning today.\n",
    "\n",
    "![RL Framework](img/mdp_weather.png)\n",
    "\n",
    "**Quick Notation** $P(x|y)$ means the probability of $x$ occuring given $y$. For instance, $P(cold|cough)$ is probability that you have a cold, given that you are coughing.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Environment - Gridworld"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What The Gridworld Looks Like"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to work on an equivalent of a poor man's version of [Unity's Gridworld](http://awjuliani.github.io/GridGL/).\n",
    "\n",
    "* `F` - Free tiles; agent can move to\n",
    "* `T` - Traps; agent recieves some penalty\n",
    "* `G` - The Goal, episode ends once reached"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "------------------------------------\n",
      "['F', 'x'] |['F', 'x'] |['F', 'x'] |\n",
      "------------------------------------\n",
      "['F', 'x'] |['T', 'x'] |['G', 'x'] |\n",
      "------------------------------------\n",
      "['F', 'o'] |['F', 'x'] |['F', 'x'] |"
     ]
    }
   ],
   "source": [
    "env = Gridworld()\n",
    "env.print_physical(visible_only=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### States"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.state_space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Actions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([0, 1, 2, 3]), array(['U', 'L', 'D', 'R'], dtype='<U1'))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.action_space, env.action_text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rewards"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "----------\n",
      "0 |0 |0 |\n",
      "----------\n",
      "0 |-5 |5 |\n",
      "----------\n",
      "0 |0 |0 |"
     ]
    }
   ],
   "source": [
    "env.print_reward()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.move_reward"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What The Agent Usually Sees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "------------------------------------\n",
      "['NA', 'NA'] |['NA', 'NA'] |['NA', 'NA'] |\n",
      "------------------------------------\n",
      "['NA', 'NA'] |['NA', 'NA'] |['NA', 'NA'] |\n",
      "------------------------------------\n",
      "['F', 'o'] |['NA', 'NA'] |['NA', 'NA'] |"
     ]
    }
   ],
   "source": [
    "env.print_physical(visible_only=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((1, 0), -1, False, 'info')\n",
      "((1, 1), -6, False, 'info')\n",
      "\n",
      "------------------------------------\n",
      "['NA', 'NA'] |['NA', 'NA'] |['NA', 'NA'] |\n",
      "------------------------------------\n",
      "['F', 'x'] |['T', 'o'] |['NA', 'NA'] |\n",
      "------------------------------------\n",
      "['F', 'x'] |['NA', 'NA'] |['NA', 'NA'] |"
     ]
    }
   ],
   "source": [
    "#go down\n",
    "action = np.argwhere(env.action_text=='U')\n",
    "print(env.step(action))\n",
    "#then right\n",
    "action = np.argwhere(env.action_text=='R')\n",
    "print(env.step(action))\n",
    "env.print_physical(visible_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deterministic Environment vs Stochastic Environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((1, 0), -1, False, 'info')\n",
      "((1, 2), 4, True, 'info')\n",
      "\n",
      "------------------------------------\n",
      "['NA', 'NA'] |['NA', 'NA'] |['NA', 'NA'] |\n",
      "------------------------------------\n",
      "['F', 'x'] |['NA', 'NA'] |['G', 'o'] |\n",
      "------------------------------------\n",
      "['F', 'x'] |['NA', 'NA'] |['NA', 'NA'] |"
     ]
    }
   ],
   "source": [
    "env = Gridworld(wind_p=0.5)\n",
    "#go down\n",
    "action = np.argwhere(env.action_text=='U')\n",
    "print(env.step(action))\n",
    "#then right\n",
    "action = np.argwhere(env.action_text=='R')\n",
    "print(env.step(action))\n",
    "env.print_physical(visible_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Agent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deterministic Policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\pi(s) \\in \\mathcal{A}(s)$ for all $s \\in \\mathcal{S}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reward Grid\n",
      "\n",
      "----------\n",
      "0 |0 |0 |\n",
      "----------\n",
      "0 |-5 |5 |\n",
      "----------\n",
      "0 |0 |0 |\n",
      "\n",
      "Policy A: Reach Goal ASAP\n",
      "\n",
      "----------\n",
      "R |R |D |\n",
      "----------\n",
      "R |R |U |\n",
      "----------\n",
      "R |U |U |\n",
      "\n",
      "Policy B: Avoid Trap\n",
      "\n",
      "----------\n",
      "R |R |D |\n",
      "----------\n",
      "U |R |U |\n",
      "----------\n",
      "R |R |U |"
     ]
    }
   ],
   "source": [
    "#deterministic env\n",
    "env = Gridworld(wind_p=0.)\n",
    "#deterministic policy\n",
    "policy_a = {(0, 0): 3,\n",
    "          (0, 1): 3,\n",
    "          (0, 2): 2,\n",
    "          (1, 0): 3,\n",
    "          (1, 1): 3,\n",
    "          (1, 2): 0,\n",
    "          (2, 0): 3,\n",
    "          (2, 1): 0,\n",
    "          (2, 2): 0}\n",
    "policy_b = {(0, 0): 3,\n",
    "          (0, 1): 3,\n",
    "          (0, 2): 2,\n",
    "          (1, 0): 0,\n",
    "          (1, 1): 3,\n",
    "          (1, 2): 0,\n",
    "          (2, 0): 3,\n",
    "          (2, 1): 3,\n",
    "          (2, 2): 0}\n",
    "\n",
    "#peek\n",
    "print('Reward Grid')\n",
    "env.print_reward()\n",
    "print('\\n')\n",
    "a = GridworldAgent(env,policy_a)\n",
    "print('Policy A: Reach Goal ASAP')\n",
    "a.print_policy()\n",
    "print('\\n')\n",
    "print('Policy B: Avoid Trap')\n",
    "a.policy = policy_b\n",
    "a.print_policy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stochastic Policy - Epsilon Greedy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\pi(a|s) = \\mathbb{P}(A_t=a|S_t=s)$ for all $s \\in \\mathcal{S}$ and $a \\in \\mathcal{A}(s)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Coding Assignment** Implement epsilon greedy in the `select_action` function of `agent.py`.\n",
    "\n",
    "Hint: Pseudo-code looks like this\n",
    "```\n",
    "r = random number between 0 and 1\n",
    "if r > epsilon:\n",
    "    perform best action\n",
    "else:\n",
    "    perform random action\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Preferred action for (0, 0) is 3\n",
      "At epsilon 0.5, we get:\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<a list of 10 Patch objects>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAD8CAYAAAB+UHOxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAEblJREFUeJzt3X+s3XV9x/HnSwpq1FmQu4603cpiswWXqaypNS7GSVYKLpZkzrAsUglLk41tLlmy4f5YI8xE/pHJNjGNdCvGiQR1dI6NNYgx+wPkoogCOq4ooQ3YOwpVx6ape++P8yk71nu559J7z+nt5/lITs73+/5+zvd8Pvfbe173++N8m6pCktSfF026A5KkyTAAJKlTBoAkdcoAkKROGQCS1CkDQJI6ZQBIUqcMAEnqlAEgSZ1aNekOPJ+zzz67NmzYMOluSNKKct999/1nVU0t1O6kDoANGzYwPT096W5I0oqS5LFR2nkISJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwaAJHXKAJCkThkAktQpA0CSOnVSfxNYkiZpw1X/PLH3/vYH3rbs7+EegCR1ygCQpE4ZAJLUqZECIMnqJLcm+XqSh5O8MclZSfYneaQ9n9naJsn1SWaSPJDk/KH17GjtH0myY7kGJUla2Kh7AB8C/rWqfhF4LfAwcBVwZ1VtBO5s8wAXARvbYydwA0CSs4BdwBuAzcCuY6EhSRq/BQMgySuBNwM3AlTVD6vqGWA7sLc12wtc0qa3AzfVwN3A6iTnABcC+6vqcFU9DewHti3paCRJIxtlD+BcYBb4uyRfTvLRJC8D1lTVE63Nk8CaNr0WeHzo9Qdabb66JGkCRgmAVcD5wA1V9Xrgv/j/wz0AVFUBtRQdSrIzyXSS6dnZ2aVYpSRpDqMEwAHgQFXd0+ZvZRAI32mHdmjPh9ryg8D6odeva7X56j+mqnZX1aaq2jQ1teB/aSlJeoEWDICqehJ4PMkvtNIFwEPAPuDYlTw7gNva9D7gsnY10BbgSDtUdAewNcmZ7eTv1laTJE3AqLeC+EPg40nOAB4FLmcQHrckuQJ4DHhna3s7cDEwAzzb2lJVh5NcA9zb2l1dVYeXZBSSpEUbKQCq6n5g0xyLLpijbQFXzrOePcCexXRQkrQ8/CawJHXKAJCkThkAktQpA0CSOmUASFKnDABJ6pQBIEmdMgAkqVMGgCR1ygCQpE4ZAJLUKQNAkjplAEhSpwwASeqUASBJnTIAJKlTBoAkdcoAkKROGQCS1CkDQJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwaAJHVqpABI8u0kX01yf5LpVjsryf4kj7TnM1s9Sa5PMpPkgSTnD61nR2v/SJIdyzMkSdIoFrMH8GtV9bqq2tTmrwLurKqNwJ1tHuAiYGN77ARugEFgALuANwCbgV3HQkOSNH4ncghoO7C3Te8FLhmq31QDdwOrk5wDXAjsr6rDVfU0sB/YdgLvL0k6AaMGQAH/luS+JDtbbU1VPdGmnwTWtOm1wONDrz3QavPVf0ySnUmmk0zPzs6O2D1J0mKtGrHdr1bVwSQ/DexP8vXhhVVVSWopOlRVu4HdAJs2bVqSdUqSftJIewBVdbA9HwI+w+AY/nfaoR3a86HW/CCwfujl61ptvrokaQIWDIAkL0vyimPTwFbga8A+4NiVPDuA29r0PuCydjXQFuBIO1R0B7A1yZnt5O/WVpMkTcAoh4DWAJ9Jcqz9P1TVvya5F7glyRXAY8A7W/vbgYuBGeBZ4HKAqjqc5Brg3tbu6qo6vGQjkSQtyoIBUFWPAq+do/4UcMEc9QKunGdde4A9i++mJGmp+U1gSeqUASBJnTIAJKlTBoAkdcoAkKROGQCS1CkDQJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwaAJHXKAJCkThkAktQpA0CSOmUASFKnDABJ6pQBIEmdMgAkqVMGgCR1ygCQpE4ZAJLUKQNAkjplAEhSp0YOgCSnJflyks+2+XOT3JNkJsknk5zR6i9u8zNt+Yahdby31b+R5MKlHowkaXSL2QN4D/Dw0Py1wHVV9WrgaeCKVr8CeLrVr2vtSHIecCnwGmAb8OEkp51Y9yVJL9RIAZBkHfA24KNtPsBbgVtbk73AJW16e5unLb+gtd8O3FxVP6iqbwEzwOalGIQkafFG3QP4K+BPgf9t868Cnqmqo23+ALC2Ta8FHgdoy4+09s/V53jNc5LsTDKdZHp2dnYRQ5EkLcaCAZDkN4BDVXXfGPpDVe2uqk1VtWlqamocbylJXVo1Qps3AW9PcjHwEuCngA8Bq5Osan/lrwMOtvYHgfXAgSSrgFcCTw3Vjxl+jSRpzBbcA6iq91bVuqrawOAk7ueq6neAu4B3tGY7gNva9L42T1v+uaqqVr+0XSV0LrAR+OKSjUSStCij7AHM58+Am5P8JfBl4MZWvxH4WJIZ4DCD0KCqHkxyC/AQcBS4sqp+dALvL0k6AYsKgKr6PPD5Nv0oc1zFU1X/A/zWPK9/P/D+xXZSkrT0/CawJHXKAJCkThkAktQpA0CSOmUASFKnDABJ6pQBIEmdMgAkqVMGgCR1ygCQpE4ZAJLUKQNAkjplAEhSpwwASeqUASBJnTIAJKlTBoAkdcoAkKROGQCS1CkDQJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwsGQJKXJPlikq8keTDJ+1r93CT3JJlJ8skkZ7T6i9v8TFu+YWhd7231byS5cLkGJUla2Ch7AD8A3lpVrwVeB2xLsgW4Friuql4NPA1c0dpfATzd6te1diQ5D7gUeA2wDfhwktOWcjCSpNEtGAA18P02e3p7FPBW4NZW3wtc0qa3t3na8guSpNVvrqofVNW3gBlg85KMQpK0aCOdA0hyWpL7gUPAfuCbwDNVdbQ1OQCsbdNrgccB2vIjwKuG63O8Zvi9diaZTjI9Ozu7+BFJkkYyUgBU1Y+q6nXAOgZ/tf/icnWoqnZX1aaq2jQ1NbVcbyNJ3VvUVUBV9QxwF/BGYHWSVW3ROuBgmz4IrAdoy18JPDVcn+M1kqQxG+UqoKkkq9v0S4FfBx5mEATvaM12ALe16X1tnrb8c1VVrX5pu0roXGAj8MWlGogkaXFWLdyEc4C97YqdFwG3VNVnkzwE3JzkL4EvAze29jcCH0syAxxmcOUPVfVgkluAh4CjwJVV9aOlHY4kaVQLBkBVPQC8fo76o8xxFU9V/Q/wW/Os6/3A+xffTUnSUvObwJLUKQNAkjplAEhSpwwASeqUASBJnTIAJKlTBoAkdcoAkKROGQCS1CkDQJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwaAJHXKAJCkThkAktQpA0CSOmUASFKnDABJ6pQBIEmdMgAkqVMGgCR1ygCQpE4tGABJ1ie5K8lDSR5M8p5WPyvJ/iSPtOczWz1Jrk8yk+SBJOcPrWtHa/9Ikh3LNyxJ0kJG2QM4CvxJVZ0HbAGuTHIecBVwZ1VtBO5s8wAXARvbYydwAwwCA9gFvAHYDOw6FhqSpPFbMACq6omq+lKb/h7wMLAW2A7sbc32Ape06e3ATTVwN7A6yTnAhcD+qjpcVU8D+4FtSzoaSdLIFnUOIMkG4PXAPcCaqnqiLXoSWNOm1wKPD73sQKvNV5ckTcDIAZDk5cCngD+uqu8OL6uqAmopOpRkZ5LpJNOzs7NLsUpJ0hxGCoAkpzP48P94VX26lb/TDu3Qng+1+kFg/dDL17XafPUfU1W7q2pTVW2amppazFgkSYswylVAAW4EHq6qDw4t2gccu5JnB3DbUP2ydjXQFuBIO1R0B7A1yZnt5O/WVpMkTcCqEdq8CXgX8NUk97fanwMfAG5JcgXwGPDOtux24GJgBngWuBygqg4nuQa4t7W7uqoOL8koJEmLtmAAVNW/A5ln8QVztC/gynnWtQfYs5gOSpKWh98ElqROGQCS1CkDQJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwaAJHXKAJCkThkAktQpA0CSOmUASFKnDABJ6pQBIEmdMgAkqVMGgCR1ygCQpE4ZAJLUKQNAkjo1yn8KL+kksuGqf57Ye3/7A2+b2Htr6Z3SATCpX5Qef0n8WUsrj4eAJKlTBoAkdcoAkKROLRgASfYkOZTka0O1s5LsT/JIez6z1ZPk+iQzSR5Icv7Qa3a09o8k2bE8w5EkjWqUPYC/B7YdV7sKuLOqNgJ3tnmAi4CN7bETuAEGgQHsAt4AbAZ2HQsNSdJkLBgAVfUF4PBx5e3A3ja9F7hkqH5TDdwNrE5yDnAhsL+qDlfV08B+fjJUJElj9ELPAaypqifa9JPAmja9Fnh8qN2BVpuvLkmakBM+CVxVBdQS9AWAJDuTTCeZnp2dXarVSpKO80ID4Dvt0A7t+VCrHwTWD7Vb12rz1X9CVe2uqk1VtWlqauoFdk+StJAXGgD7gGNX8uwAbhuqX9auBtoCHGmHiu4AtiY5s5383dpqkqQJWfBWEEk+AbwFODvJAQZX83wAuCXJFcBjwDtb89uBi4EZ4FngcoCqOpzkGuDe1u7qqjr+xLIkaYwWDICq+u15Fl0wR9sCrpxnPXuAPYvqnSRp2fhNYEnqlAEgSZ0yACSpUwaAJHXKAJCkThkAktQpA0CSOmUASFKnDABJ6pQBIEmdMgAkqVMGgCR1ygCQpE4ZAJLUKQNAkjplAEhSpwwASeqUASBJnTIAJKlTBoAkdcoAkKROGQCS1CkDQJI6ZQBIUqfGHgBJtiX5RpKZJFeN+/0lSQNjDYAkpwF/C1wEnAf8dpLzxtkHSdLAuPcANgMzVfVoVf0QuBnYPuY+SJIYfwCsBR4fmj/QapKkMVs16Q4cL8lOYGeb/X6Sb5zA6s4G/vPEe7U4uXbJVzmRcSyTJR3LMvysF+NU2S4jj2PCP+9RnCrbhFx7QmP5uVEajTsADgLrh+bXtdpzqmo3sHsp3izJdFVtWop1TdKpMg5wLCejU2Uc4FgWa9yHgO4FNiY5N8kZwKXAvjH3QZLEmPcAqupokj8A7gBOA/ZU1YPj7IMkaWDs5wCq6nbg9jG93ZIcSjoJnCrjAMdyMjpVxgGOZVFSVcv9HpKkk5C3gpCkTq34AFjo1hJJXpzkk235PUk2jL+XoxlhLO9OMpvk/vb43Un0cyFJ9iQ5lORr8yxPkuvbOB9Icv64+ziqEcbyliRHhrbJX4y7j6NIsj7JXUkeSvJgkvfM0WZFbJcRx7JStstLknwxyVfaWN43R5vl+wyrqhX7YHAi+ZvAzwNnAF8Bzjuuze8DH2nTlwKfnHS/T2As7wb+ZtJ9HWEsbwbOB742z/KLgX8BAmwB7pl0n09gLG8BPjvpfo4wjnOA89v0K4D/mOPf14rYLiOOZaVslwAvb9OnA/cAW45rs2yfYSt9D2CUW0tsB/a26VuBC5JkjH0c1Slzm4yq+gJw+HmabAduqoG7gdVJzhlP7xZnhLGsCFX1RFV9qU1/D3iYn/wW/orYLiOOZUVoP+vvt9nT2+P4E7PL9hm20gNglFtLPNemqo4CR4BXjaV3izPqbTJ+s+2e35pk/RzLV4JT7ZYgb2y78P+S5DWT7sxC2iGE1zP4a3PYitsuzzMWWCHbJclpSe4HDgH7q2re7bLUn2ErPQB680/Ahqr6ZWA///9XgSbnS8DPVdVrgb8G/nHC/XleSV4OfAr446r67qT7cyIWGMuK2S5V9aOqeh2DOyNsTvJL43rvlR4AC95aYrhNklXAK4GnxtK7xRnlNhlPVdUP2uxHgV8ZU9+W2ijbbUWoqu8e24WvwXdcTk9y9oS7NackpzP4wPx4VX16jiYrZrssNJaVtF2OqapngLuAbcctWrbPsJUeAKPcWmIfsKNNvwP4XLWzKSeZBcdy3PHYtzM49rkS7QMua1edbAGOVNUTk+7UC5HkZ44dj02ymcHv1En3B0br443Aw1X1wXmarYjtMspYVtB2mUqyuk2/FPh14OvHNVu2z7CT7m6gi1Hz3FoiydXAdFXtY/AP5WNJZhiczLt0cj2e34hj+aMkbweOMhjLuyfW4eeR5BMMrsI4O8kBYBeDk1tU1UcYfBP8YmAGeBa4fDI9XdgIY3kH8HtJjgL/DVx6kv6B8SbgXcBX2/FmgD8HfhZW3HYZZSwrZbucA+zN4D/LehFwS1V9dlyfYX4TWJI6tdIPAUmSXiADQJI6ZQBIUqcMAEnqlAEgSZ0yACSpUwaAJHXKAJCkTv0fckc+yUK8Op8AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "state = (0,0)\n",
    "print(f'Preferred action for {state} is {a.policy[state]}')\n",
    "print('At epsilon 0.5, we get:')\n",
    "actions = np.array([a.select_action(state,epsilon=0.5) for i in range(10000)])\n",
    "plt.hist(actions)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "#epsilon decaying \n",
    "a = GridworldAgent(env,policy_a,start_epsilon=0.9,end_epsilon=0.1,epsilon_decay=0.9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fecb911e390>]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAG1ZJREFUeJzt3Xt0XWd95vHvI8lX+SJblm+SbPkWGzkXmygmEBZNAouxE7AhpTM2pcCaDJ62mNBC23EWJWXcYRhKhxaoh9aktMCCuCGl4ILBhVwolxCsXOzEt1h2fJEvsew4vsU32b/54xzTgyJZx/KRts4+z2ctrZz9njfav72282T7ffferyICMzNLl7KkCzAzs8JzuJuZpZDD3cwshRzuZmYp5HA3M0shh7uZWQo53M3MUsjhbmaWQg53M7MUqkhqx2PGjImGhoakdm9mVpSefPLJwxFR012/xMK9oaGB5ubmpHZvZlaUJO3Op5+HZczMUsjhbmaWQg53M7MUcribmaWQw93MLIXyCndJ8yVtk9QiaXkn30+W9LCkjZIek1RX+FLNzCxf3Ya7pHJgJbAAaASWSGrs0O0vga9GxPXACuBThS7UzMzyl8+V+zygJSJ2RsQ5YDWwqEOfRuCR7OdHO/m+YJp3vcSnf7AVLw9oZta1fMK9Ftibs92abcu1Abgr+/mdwHBJ1R1/kaSlkpolNbe1tfWkXp7dd4wvPraDI6fO9ejfNzMrBYWaUP0j4DckPQ38BrAPuNCxU0SsioimiGiqqen26dlOTa4eCsDuI6/0vFozs5TLJ9z3AfU523XZtl+JiP0RcVdEzAU+lm17uWBV5phcXQnA7iOneuPXm5mlQj7hvh6YIWmKpIHAYmBNbgdJYyRd+l33Al8ubJn/oW7UECRfuZuZXU634R4R7cAyYB2wBXgwIjZJWiFpYbbbrcA2Sc8D44BP9lK9DKooZ+LIIex5yeFuZtaVvN4KGRFrgbUd2u7L+fwQ8FBhS+va5Oqh7PKwjJlZl4ryCdXJ1UPZ42EZM7MuFWm4V3Lk1DlOnDmfdClmZv1ScYb7aN8OaWZ2OUUZ7pOy97p7UtXMrHNFGe6X7nX3pKqZWeeKMtyHDapgzLCBnlQ1M+tCUYY7wKTRQz3mbmbWhaIN94bqSr+CwMysC0Ub7pOqh3Lg+BnOnH/V+8nMzEpe0Yb75OqhREDrUQ/NmJl1VMThfuntkA53M7OOijfc/SCTmVmXijbcR1cOZPigCk+qmpl1omjDXRKTqoey20+pmpm9StGGO/jtkGZmXckr3CXNl7RNUouk5Z18P0nSo5KelrRR0h2FL/XVJldXsvfoK1y4GH2xOzOzotFtuEsqB1YCC4BGYImkxg7d/pTMCk1zySzD9/8KXWhnGqqHcv5CsP/l032xOzOzopHPlfs8oCUidkbEOWA1sKhDnwBGZD+PBPYXrsSuTRkzDIAdbSf7YndmZkUjn3CvBfbmbLdm23J9AniPpFYyy/F9qCDVdWNqTeZe951tvmPGzCxXoSZUlwD/GBF1wB3A1yS96ndLWiqpWVJzW1vbVe+0unIgI4cM8JW7mVkH+YT7PqA+Z7su25brbuBBgIh4HBgMjOn4iyJiVUQ0RURTTU1NzyrOIYmpNZW+cjcz6yCfcF8PzJA0RdJAMhOmazr02QO8GUDSa8iE+9Vfmudh6phh7DzsK3czs1zdhntEtAPLgHXAFjJ3xWyStELSwmy3jwIfkLQBeAB4f0T0yf2J08ZW8uLxs14s28wsR0U+nSJiLZmJ0ty2+3I+bwZuKWxp+ZmavWPmhcOnuL6uKokSzMz6naJ+QhVgWvaOGU+qmpn9h6IP90nVQykvkydVzcxyFH24D6oop37UEIe7mVmOog93gKk1wzwsY2aWIxXhPq2mkhcOn+KiXyBmZgakJNyn1gzjbPtF9vkFYmZmQFrCfYzvmDEzy5WKcJ82NnOvuydVzcwyUhHu1ZUDGTG4wq8hMDPLSkW4S2La2GHsOOQrdzMzSEm4g18gZmaWKz3hXpN5gdjJs+1Jl2JmlrjUhPu0muySe4d89W5mlppwv2ZcJtyff/FEwpWYmSUvNeE+ubqSgRVlbPeVu5lZesK9vExMrxnGtoO+cjczyyvcJc2XtE1Si6TlnXz/V5Keyf48L+nlwpfavZnjh3tYxsyMPMJdUjmwElgANAJLJDXm9omIP4yIORExB/gC8K3eKLY714wbzoFjZzjuJffMrMTlc+U+D2iJiJ0RcQ5YDSy6TP8lZNZR7XOXJlW3++rdzEpcPuFeC+zN2W7Ntr2KpMnAFOCRqy/tyl0zbjgA2w56UtXMSluhJ1QXAw9FxIXOvpS0VFKzpOa2trYC7xpqq4ZQObDc4+5mVvLyCfd9QH3Odl22rTOLucyQTESsioimiGiqqanJv8o8lZWJ6eM8qWpmlk+4rwdmSJoiaSCZAF/TsZOkWcAo4PHClnhlZo4b5nA3s5LXbbhHRDuwDFgHbAEejIhNklZIWpjTdTGwOiISXevumnHDOXzyHEdOnk2yDDOzRFXk0yki1gJrO7Td12H7E4Urq+cuTao+/+JJXj9sUMLVmJklIzVPqF4yc/ylcPfQjJmVrtSF+9jhgxg5ZIDD3cxKWurCXRLXeFLVzEpc6sIdMuPu2w6eIOG5XTOzxKQy3GeOH87xM+0cOuE7ZsysNKUy3C/dMbPlwPGEKzEzS0Yqw/0140cAsOWAx93NrDSlMtxHDh1A3aghbNp/LOlSzMwSkcpwB2icMILNHpYxsxKV2nCfPXEkLxw+xamz7UmXYmbW51Ib7o0TRxABW72mqpmVoNSG++yJmUnVzR53N7MSlNpwnzByMFVDB3jc3cxKUmrDXRKzJ45g036Hu5mVntSGO2TumNl68ATnL1xMuhQzsz6V6nCfPXEk59ovsrPtVNKlmJn1qbzCXdJ8SdsktUha3kWf/yxps6RNkr5R2DJ75tKkqh9mMrNS0224SyoHVgILgEZgiaTGDn1mAPcCt0TEbOAPeqHWKzZlTCWDKsrY7HF3Mysx+Vy5zwNaImJnRJwDVgOLOvT5ALAyIo4CRMShwpbZMxXlZcya4ElVMys9+YR7LbA3Z7s125brGuAaST+T9AtJ8zv7RZKWSmqW1NzW1taziq/QpdcQ+N3uZlZKCjWhWgHMAG4FlgBfklTVsVNErIqIpohoqqmpKdCuL2/2xBEcO32efS+f7pP9mZn1B/mE+z6gPme7LtuWqxVYExHnI+IF4HkyYZ+4xl9NqnpoxsxKRz7hvh6YIWmKpIHAYmBNhz7fJnPVjqQxZIZpdhawzh5rnDCCijLxbKvvmDGz0tFtuEdEO7AMWAdsAR6MiE2SVkhamO22DjgiaTPwKPDHEXGkt4q+EoMHlDNrwnA2tL6cdClmZn2mIp9OEbEWWNuh7b6czwF8JPvT79xQV8W/btjPxYtBWZmSLsfMrNel+gnVS26oq+L4mXZ2HfGTqmZWGkoj3OszN+54aMbMSkVJhPv0scMYOrCcDXs9qWpmpaEkwr28TFxXO5Jn9vrK3cxKQ0mEO8Cc+io27z/OuXa//tfM0q9kwv2G+irOXbjI1oN+mMnM0q+kwh1gg4dmzKwElEy4Txw5mDHDBvGMJ1XNrASUTLhLYk79SN8OaWYloWTCHTIPM+1oO8nxM+eTLsXMrFeVVrjXVxEBz/klYmaWcqUV7nWZSdUndx9NuBIzs95VUuE+cugArhk3jGaHu5mlXEmFO0BTw2ie2nOUCxe97J6ZpVfJhftNDaM4caad5188kXQpZma9Jq9wlzRf0jZJLZKWd/L9+yW1SXom+/PfCl9qYTRNHg1A866XEq7EzKz3dBvuksqBlcACoBFYIqmxk67/FBFzsj/3F7jOgqkbNYTxIwazfpfH3c0svfK5cp8HtETEzog4B6wGFvVuWb1HEk0No3zlbmaplk+41wJ7c7Zbs20d/aakjZIeklRfkOp6yU0No9l/7Az7Xj6ddClmZr2iUBOq/wo0RMT1wA+Br3TWSdJSSc2Smtva2gq06yvX1DAK8Li7maVXPuG+D8i9Eq/Ltv1KRByJiLPZzfuBGzv7RRGxKiKaIqKppqamJ/UWxKzxIxg2qIL1DnczS6l8wn09MEPSFEkDgcXAmtwOkibkbC4EthSuxMIrLxNzJ1XR7ElVM0upbsM9ItqBZcA6MqH9YERskrRC0sJst3skbZK0AbgHeH9vFVwoNzWMZtuLJzj2il8iZmbpU5FPp4hYC6zt0HZfzud7gXsLW1rvamoYRQQ8tecot80am3Q5ZmYFVXJPqF4yt34UFWXiiRc87m5m6VOy4T5kYDlzJ1Xx+I7DSZdiZlZwJRvuAK+fNoZn9x3j2GmPu5tZupR0uN8yrZqLAU/sPJJ0KWZmBVXS4T5nUhWDB5Tx8x0OdzNLl5IO90EV5dzUMJqftXjc3czSpaTDHeAN08aw/dBJDp04k3QpZmYFU/Lhfsv0agAe99CMmaVIyYf77IkjGTG4wkMzZpYqJR/u5WXi5qnVnlQ1s1Qp+XAHuGX6GFqPnmbPkVeSLsXMrCAc7sAbpmXG3X/up1XNLCUc7sD0scMYO3wQ/749uQVEzMwKyeFOZl3VW2fW8JPthzl/4WLS5ZiZXTWHe9ZtM8dy4kw7T+32Ah5mVvwc7lm3zBhDRZl4dJuHZsys+OUV7pLmS9omqUXS8sv0+01JIampcCX2jRGDB3BTw2ge23Yo6VLMzK5at+EuqRxYCSwAGoElkho76Tcc+DDwRKGL7Cu3zaph68ET7H/5dNKlmJldlXyu3OcBLRGxMyLOAauBRZ30+3Pg00DRvqTltpmZ5fZ+/LyHZsysuOUT7rXA3pzt1mzbr0h6LVAfEd8rYG19bvrYYdRWDeHRrR6aMbPidtUTqpLKgM8CH82j71JJzZKa29r639WxJG6bVcPPWg5ztv1C0uWYmfVYPuG+D6jP2a7Ltl0yHLgWeEzSLuBmYE1nk6oRsSoimiKiqaampudV96LbZo7l1LkLNO/yLZFmVrzyCff1wAxJUyQNBBYDay59GRHHImJMRDRERAPwC2BhRDT3SsW97PXTqhlYUcYjHpoxsyLWbbhHRDuwDFgHbAEejIhNklZIWtjbBfa1oQMruGVaNf+2+SARkXQ5ZmY9kteYe0SsjYhrImJaRHwy23ZfRKzppO+txXrVfsn8a8ez96XTbD5wPOlSzMx6xE+oduItrxlHmWDdcweTLsXMrEcc7p2oHjaI102p5vsOdzMrUg73Lsy/djzbD52k5dDJpEsxM7tiDvcuvHX2OADWbfLVu5kVH4d7FyaMHMKc+iqHu5kVJYf7ZSy4djwbW4+xzy8SM7Mi43C/jP80ezwAP/DEqpkVGYf7ZTSMqWTW+OGsffZA0qWYmV0Rh3s3Fs6ZyJO7j7L3pVeSLsXMLG8O924smpN5u/F3ntnXTU8zs/7D4d6N2qohzJsymn95ep/fNWNmRcPhnod3zKllR9spNu33u2bMrDg43PNwx3XjGVAuvv20h2bMrDg43PNQNXQgt80cy5oN+7lw0UMzZtb/Odzz9I65tRw6cZbHdxxJuhQzs2453PN0+6yxDB9Uwb94aMbMikBe4S5pvqRtklokLe/k+9+V9KykZyT9VFJj4UtN1uAB5dx5/QTWPnuAE2fOJ12OmdlldRvuksqBlcACoBFY0kl4fyMirouIOcBfAJ8teKX9wOJ5kzh9/gJrNuxPuhQzs8vK58p9HtASETsj4hywGliU2yEicu8RrARSOet4Q91IZo0fzgO/3JN0KWZml5VPuNcCe3O2W7Ntv0bSByXtIHPlfk9nv0jSUknNkprb2tp6Um+iJPHu103iuX3Hebb1WNLlmJl1qWATqhGxMiKmAf8D+NMu+qyKiKaIaKqpqSnUrvvUojm1DB5QxgPrffVuZv1XPuG+D6jP2a7LtnVlNfCOqymqPxs5ZAB3XjeRNc/s59TZ9qTLMTPrVD7hvh6YIWmKpIHAYmBNbgdJM3I27wS2F67E/mfJvHpOnm3nuxs9sWpm/VO34R4R7cAyYB2wBXgwIjZJWiFpYbbbMkmbJD0DfAR4X69V3A/cOHkU08cO4xtPeGjGzPqninw6RcRaYG2HtvtyPn+4wHX1a5L4nZsn82drNvHk7qPcOHlU0iWZmf0aP6HaQ++6sY4Rgyv48k9fSLoUM7NXcbj3UOWgCpbMm8T3nztA61Gv0mRm/YvD/Sq89w0NSOKrj+9OuhQzs1/jcL8KtVVDmH/teB745R7fFmlm/YrD/Srd/cYpnDjTzjeb93bf2cysjzjcr9JrJ41i7qQq/uHnu2i/cDHpcszMAId7Qfz3N01l95FX+O7GA0mXYmYGONwL4q2N45k5bjh/82gLF70Mn5n1Aw73AigrE8tun07LoZN8/7mDSZdjZuZwL5Q7rpvA1JpKvvDIdl+9m1niHO4FUl4mPnT7dLYePMEPt7yYdDlmVuIc7gX09usnMrl6KF94ZDsRvno3s+Q43AuooryMD90+g+f2HWftsx57N7PkONwL7J1za5k5bjifWbeV877v3cwS4nAvsPIysXzBLHYdecULaZtZYhzuveDWmTXcPHU0n/vRdk76nTNmloC8wl3SfEnbJLVIWt7J9x+RtFnSRkkPS5pc+FKLhyTuXfAajpw6x6of70i6HDMrQd2Gu6RyYCWwAGgElkhq7NDtaaApIq4HHgL+otCFFpsb6qu48/oJfOknL3Dg2OmkyzGzEpPPlfs8oCUidkbEOWA1sCi3Q0Q8GhGXVqz4BVBX2DKL0/L5s7gYwf/63pakSzGzEpNPuNcCue+zbc22deVu4PudfSFpqaRmSc1tbW35V1mk6kcP5YO3Ted7Gw/w0+2Hky7HzEpIQSdUJb0HaAI+09n3EbEqIpoioqmmpqaQu+63lr5pKg3VQ7nvO89xtv1C0uWYWYnIJ9z3AfU523XZtl8j6S3Ax4CFEXG2MOUVv8EDyvnEwtnsPHyK+3/ixbTNrG/kE+7rgRmSpkgaCCwG1uR2kDQX+DsywX6o8GUWt1tnjmX+7PF84ZHt7DnixbTNrPd1G+4R0Q4sA9YBW4AHI2KTpBWSFma7fQYYBnxT0jOS1nTx60rWny1sZEBZGX/80Aa/NdLMel1FPp0iYi2wtkPbfTmf31LgulJnwsghfPztjfzJQxv56uO7eP8tU5IuycxSzE+o9qHfurGO22bW8H9+sJVdh08lXY6ZpZjDvQ9J4lN3Xc+A8szwzAUPz5hZL3G497HxIwfzibfPZv2uo/ytX01gZr3E4Z6Au15by8IbJvJ//20bT+w8knQ5ZpZCDvcESOJ/33Udk6sruWf10xw56ccCzKywHO4JGTaogr9591yOvnKejzzo2yPNrLAc7gmaPXEkH39bIz9+vo2/fnh70uWYWYo43BP2ntdN4l031vH5h7fz3Y37ky7HzFLC4Z4wSXzynddy4+RR/NE3N/Bs67GkSzKzFHC49wODKsr52/fcSHXlID7w1WZePH4m6ZLMrMg53PuJmuGD+NJ7mzh+5jzv+/IvOfbK+aRLMrMi5nDvRxonjmDV7zSxo+0k//Ur6zl9zu9/N7Oecbj3M2+cMYbPLZ7LU3uO8ntff5LzFy4mXZKZFSGHez90x3UT+OQ7ruOxbW186BtPc67dAW9mV8bh3k+9+3WT+PjbGvnBpoP8/tef8hJ9ZnZF8gp3SfMlbZPUIml5J9+/SdJTktolvavwZZamu984hRWLZvOjLS/yu197kjPnHfBmlp9uw11SObASWAA0AkskNXbotgd4P/CNQhdY6t77+gY+ddd1PPZ8G/9l1S9oPepl+syse/lcuc8DWiJiZ0ScA1YDi3I7RMSuiNgIeHC4FyyZN4kv/vaN7Dx0kjs//1Me3vJi0iWZWT+XzzJ7tcDenO1W4HW9U451Zf6143nNhOH8/tef4u6vNDOtppIyKemyzKwH7nnzDN5+w8Re3Udea6gWiqSlwFKASZMm9eWuU2FydSX//HtvYOWjLexoO5l0OWbWQyOHDOj1feQT7vuA+pztumzbFYuIVcAqgKamJr/jtgcGDyjno2+dmXQZZtbP5TPmvh6YIWmKpIHAYmBN75ZlZmZXo9twj4h2YBmwDtgCPBgRmyStkLQQQNJNklqB3wL+TtKm3izazMwuL68x94hYC6zt0HZfzuf1ZIZrzMysH/ATqmZmKeRwNzNLIYe7mVkKOdzNzFLI4W5mlkKKSOZZIkltwO4e/utjgMMFLKdYlOJxl+IxQ2kedykeM1z5cU+OiJruOiUW7ldDUnNENCVdR18rxeMuxWOG0jzuUjxm6L3j9rCMmVkKOdzNzFKoWMN9VdIFJKQUj7sUjxlK87hL8Zihl467KMfczczs8or1yt3MzC6j6MK9u8W600BSvaRHJW2WtEnSh7PtoyX9UNL27D9HJV1roUkql/S0pO9mt6dIeiJ7vv8p+9rpVJFUJekhSVslbZH0+hI513+Y/fP9nKQHJA1O2/mW9GVJhyQ9l9PW6blVxuezx75R0muvZt9FFe55LtadBu3ARyOiEbgZ+GD2OJcDD0fEDODh7HbafJjMq6Uv+TTwVxExHTgK3J1IVb3rc8APImIWcAOZ40/1uZZUC9wDNEXEtUA5mbUi0na+/xGY36Gtq3O7AJiR/VkKfPFqdlxU4U4ei3WnQUQciIinsp9PkPmPvZbMsX4l2+0rwDuSqbB3SKoD7gTuz24LuB14KNsljcc8EngT8PcAEXEuIl4m5ec6qwIYIqkCGAocIGXnOyL+HXipQ3NX53YR8NXI+AVQJWlCT/ddbOHe2WLdtQnV0ickNQBzgSeAcRFxIPvVQWBcQmX1lr8G/gS4mN2uBl7OLhgD6TzfU4A24B+yw1H3S6ok5ec6IvYBfwnsIRPqx4AnSf/5hq7PbUHzrdjCvaRIGgb8M/AHEXE897vI3OaUmludJL0NOBQRTyZdSx+rAF4LfDEi5gKn6DAEk7ZzDZAdZ15E5n9uE4FKXj18kXq9eW6LLdwLtlh3fydpAJlg/3pEfCvb/OKlv6Zl/3koqfp6wS3AQkm7yAy33U5mLLoq+9d2SOf5bgVaI+KJ7PZDZMI+zeca4C3ACxHRFhHngW+R+TOQ9vMNXZ/bguZbsYV7SSzWnR1r/ntgS0R8NuerNcD7sp/fB3ynr2vrLRFxb0TURUQDmfP6SET8NvAo8K5st1QdM0BEHAT2SpqZbXozsJkUn+usPcDNkoZm/7xfOu5Un++srs7tGuC92btmbgaO5QzfXLmIKKof4A7geWAH8LGk6+mlY3wjmb+qbQSeyf7cQWYM+mFgO/AjYHTStfbS8d8KfDf7eSrwS6AF+CYwKOn6euF45wDN2fP9bWBUKZxr4H8CW4HngK8Bg9J2voEHyMwpnCfzt7S7uzq3gMjcDbgDeJbMnUQ93refUDUzS6FiG5YxM7M8ONzNzFLI4W5mlkIOdzOzFHK4m5mlkMPdzCyFHO5mZinkcDczS6H/D+1sBMy7VFuvAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "eps = np.array([a.get_epsilon(i) for i in range(100)])\n",
    "plt.plot(eps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### State Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$v_\\pi(s) = \\sum_{a \\in \\mathcal{A}(s)}\\pi(a|s)\\sum_{s' \\in \\mathcal{S}, r\\in\\mathcal{R}}p(s',r|s,a)(r + \\gamma v_\\pi(s'))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reward Grid\n",
      "\n",
      "----------\n",
      "0 |0 |0 |\n",
      "----------\n",
      "0 |-5 |5 |\n",
      "----------\n",
      "0 |0 |0 |\n",
      "\n",
      "Policy: Reach Goal ASAP\n",
      "\n",
      "----------\n",
      "R |R |D |\n",
      "----------\n",
      "R |R |U |\n",
      "----------\n",
      "R |U |U |"
     ]
    }
   ],
   "source": [
    "#deterministic env\n",
    "env = Gridworld(wind_p=0.)\n",
    "policy = {(0, 0): 3,\n",
    "          (0, 1): 3,\n",
    "          (0, 2): 2,\n",
    "          (1, 0): 3,\n",
    "          (1, 1): 3,\n",
    "          (1, 2): 0,\n",
    "          (2, 0): 3,\n",
    "          (2, 1): 0,\n",
    "          (2, 2): 0}\n",
    "a = GridworldAgent(env,policy = policy, gamma = 1)\n",
    "print('Reward Grid')\n",
    "env.print_reward()\n",
    "print('\\n')\n",
    "print('Policy: Reach Goal ASAP')\n",
    "a.print_policy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Coding Assigment** Implement `get_v` to find out the state value of each state.\n",
    "\n",
    "Hint: Pseudo-code looks like this\n",
    "\n",
    "```\n",
    "Run through the gridworld, starting at `start_state` and save transitions to `episode`\n",
    "`episode` contains n transitions and each looks like this (state,action,reward,next_state,done)\n",
    "\n",
    "value = 0\n",
    "for i in 0 to n:\n",
    "    value += reward[i] * (gamma**i)\n",
    "return(value)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "---------------\n",
      "2 |3 |4 |\n",
      "---------------\n",
      "-2 |4 |3 |\n",
      "---------------\n",
      "-3 |-2 |4 |"
     ]
    }
   ],
   "source": [
    "for state in env.state_space:\n",
    "    a.v[state] = a.get_v(start_state=state, epsilon=0.)\n",
    "a.print_v()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "---------------\n",
      "-0.5 |1.0 |4.0 |\n",
      "---------------\n",
      "-4.0 |4.0 |1.0 |\n",
      "---------------\n",
      "-3.0 |-4.0 |4.0 |"
     ]
    }
   ],
   "source": [
    "a.gamma = 0.5\n",
    "for state in env.state_space:\n",
    "    a.v[state] = a.get_v(start_state=state, epsilon=0.)\n",
    "a.print_v()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Concept assigment** What are the best discount factor $\\gamma$ for each of the following environments?\n",
    "* [CartPole OpenAI](https://github.com/openai/gym/wiki/CartPole-v0) - An agent is a cart trying to balance a pole by going left or right. It gets +1 for each step the pole stays on and +0 when the pole falls over.\n",
    "* [CartPole Alternative](http://incompleteideas.net/book/the-book-2nd.html) - An agent is a cart trying to balance a pole by going left or right. It gets -1 if the pole falls over and +0 otherwise.\n",
    "* [Banana Collector](https://www.youtube.com/watch?v=heVMs3t9qSk) - An agent is a robot who collects bananas in a room. It gets +1 for yellow bananas and -1 for blue bananas. The time limit is 300 steps."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (State-)Action Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$q_\\pi(s,a) = \\sum_{s' \\in \\mathcal{S}, r\\in\\mathcal{R}}p(s',r|s,a)(r + \\gamma\\sum_{a' \\in \\mathcal{A}(s')} \\pi(a'|s') q_\\pi(s',a'))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reward Grid\n",
      "\n",
      "----------\n",
      "0 |0 |0 |\n",
      "----------\n",
      "0 |-5 |5 |\n",
      "----------\n",
      "0 |0 |0 |\n",
      "\n",
      "Policy: Reach Goal ASAP\n",
      "\n",
      "----------\n",
      "R |R |D |\n",
      "----------\n",
      "R |R |U |\n",
      "----------\n",
      "R |U |U |\n",
      "Actions: ['U' 'L' 'D' 'R']\n",
      "(0, 0) [ 1.  1. -3.  2.]\n",
      "(0, 1) [ 2.  1. -2.  3.]\n",
      "(0, 2) [3. 2. 4. 3.]\n",
      "(1, 0) [ 1. -3. -4. -2.]\n",
      "(1, 1) [ 2. -3. -3.  4.]\n",
      "(1, 2) [ 3. -2.  3. -1.]\n",
      "(2, 0) [-3. -4. -4. -3.]\n",
      "(2, 1) [-2. -4. -3.  3.]\n",
      "(2, 2) [ 4. -3.  3.  3.]\n"
     ]
    }
   ],
   "source": [
    "print('Reward Grid')\n",
    "env.print_reward()\n",
    "print('\\n')\n",
    "print('Policy: Reach Goal ASAP')\n",
    "a.print_policy()\n",
    "\n",
    "a.gamma=1\n",
    "for state in env.state_space:\n",
    "    for action in env.action_space:\n",
    "        a.q[state][action] = a.get_q(state,action,epsilon=0.)\n",
    "\n",
    "print(f'\\nActions: {env.action_text}')\n",
    "for i in a.q: print(i,a.q[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Comparing Policies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When comparing two policies a and b:\n",
    "\n",
    "$\\pi_a > \\pi_b$ if and only if $v_{\\pi_a}(s) > v_{\\pi_b}(s)$ for all $s \\in \\mathcal{S}$\n",
    "\n",
    "An optimal policy $\\pi^*$ is defined as:\n",
    "\n",
    "$\\pi^* > \\pi$ for all $\\pi$\n",
    "\n",
    "We can also find an optimal policy from action value function as choosing the action with the highest q-value out of any action in that state:\n",
    "\n",
    "$\\pi^*(s) = argmax_{a \\in \\mathcal{A}}q^*(s,a)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Policy A: Reach Goal ASAP\n",
      "\n",
      "----------\n",
      "R |R |D |\n",
      "----------\n",
      "R |R |U |\n",
      "----------\n",
      "R |U |U |\n",
      "---------------\n",
      "1.3 |2.6 |4.0 |\n",
      "---------------\n",
      "-2.4 |4.0 |2.6 |\n",
      "---------------\n",
      "-3.2 |-2.4 |4.0 |\n",
      "\n",
      "Policy B: Avoid Trap\n",
      "\n",
      "----------\n",
      "R |R |D |\n",
      "----------\n",
      "U |R |U |\n",
      "----------\n",
      "R |R |U |\n",
      "---------------\n",
      "1.3 |2.6 |4.0 |\n",
      "---------------\n",
      "0.2 |4.0 |2.6 |\n",
      "---------------\n",
      "1.3 |2.6 |4.0 |"
     ]
    }
   ],
   "source": [
    "#deterministic env\n",
    "env = Gridworld(wind_p=0.)\n",
    "#deterministic policy\n",
    "policy_a = {(0, 0): 3,\n",
    "          (0, 1): 3,\n",
    "          (0, 2): 2,\n",
    "          (1, 0): 3,\n",
    "          (1, 1): 3,\n",
    "          (1, 2): 0,\n",
    "          (2, 0): 3,\n",
    "          (2, 1): 0,\n",
    "          (2, 2): 0}\n",
    "policy_b = {(0, 0): 3,\n",
    "          (0, 1): 3,\n",
    "          (0, 2): 2,\n",
    "          (1, 0): 0,\n",
    "          (1, 1): 3,\n",
    "          (1, 2): 0,\n",
    "          (2, 0): 3,\n",
    "          (2, 1): 3,\n",
    "          (2, 2): 0}\n",
    "\n",
    "a = GridworldAgent(env,policy_a)\n",
    "print('Policy A: Reach Goal ASAP')\n",
    "a.print_policy()\n",
    "for state in env.state_space:\n",
    "    a.v[state] = a.get_v(start_state=state, epsilon=0.)\n",
    "a.print_v()\n",
    "print('\\n')\n",
    "print('Policy B: Avoid Trap')\n",
    "a.policy = policy_b\n",
    "a.print_policy()\n",
    "for state in env.state_space:\n",
    "    a.v[state] = a.get_v(start_state=state, epsilon=0.)\n",
    "a.print_v()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Words of Caution\n",
    "\n",
    "A few reasons [Deep Reinforcement Learning Doesn't Work Yet](https://www.alexirpan.com/2018/02/14/rl-hard.html):\n",
    "* It still takes too much time to learn simple things; for instance, one of the previous state-of-the-art Rainbow model takes over 80 hours to learn to play Atari games at human level. Even a child would only need a few hours on their phone.\n",
    "* Supervised learning works so well.\n",
    "* Instead of labels, you decide on a reward to motivate the models and it is a tricky business; for example, how would give rewards to an humanoid robot agent for it to learn how to walk?\n",
    "* There are so many hyperparameters to take care of.\n",
    "* A lot of times it is [just random search](https://arxiv.org/abs/1803.07055).\n",
    "\n",
    "![Foundational Flaw](img/foundational_flaw.PNG)\n",
    "\n",
    "Source: [Reinforcement learning’s foundational flaw](https://thegradient.pub/why-rl-is-flawed/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Read up on Bellman's equations and find out where they hid in our workshop today.\n",
    "* What are you ideas about how we can find the policy policy?\n",
    "* Play around with Gridworld. Tweak these variables and see what happens:\n",
    "    * Expand the grid and/or add some more traps\n",
    "    * Wing probability\n",
    "    * Move rewards\n",
    "    * Discount factor\n",
    "    * Epsilon and how to decay it (or not)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}