monte_carlo_epsilon_greedy_demo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Adapted from: https://github.com/lazyprogrammer/machine_learning_examples/tree/master/rl\n",
    "# the Monte Carlo Epsilon-Greedy method to find the optimal policy and value function\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from gridWorldGame import standard_grid, negative_grid,print_values, print_policy\n",
    "\n",
    "SMALL_ENOUGH = 1e-3\n",
    "GAMMA = 0.9\n",
    "ALL_POSSIBLE_ACTIONS = ('U', 'D', 'L', 'R')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_action(a, eps=0.1):\n",
    "  # choose given a with probability 1 - eps + eps/4\n",
    "  p = np.random.random()\n",
    "  if p < (1 - eps):\n",
    "    return a\n",
    "  else:\n",
    "    return np.random.choice(ALL_POSSIBLE_ACTIONS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_dict(d):\n",
    "  # returns the argmax (key) and max (value) from a dictionary\n",
    "  max_key = None\n",
    "  max_val = float('-inf')\n",
    "  for k, v in d.items():\n",
    "    if v > max_val:\n",
    "      max_val = v\n",
    "      max_key = k\n",
    "  return max_key, max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(grid, policy):\n",
    "  # returns a list of states and corresponding returns\n",
    "  # use an epsilon-soft policy\n",
    "  s = (2, 0)\n",
    "  grid.set_state(s)\n",
    "  a = random_action(policy[s])\n",
    "\n",
    "  # each triple is s(t), a(t), r(t)\n",
    "  # but r(t) results from taking action a(t-1) from s(t-1) and landing in s(t)\n",
    "  states_actions_rewards = [(s, a, 0)]\n",
    "  while True:\n",
    "    r = grid.move(a)\n",
    "    s = grid.current_state()\n",
    "    if grid.game_over():\n",
    "      states_actions_rewards.append((s, None, r))\n",
    "      break\n",
    "    else:\n",
    "      a = random_action(policy[s]) # the next state is stochastic\n",
    "      states_actions_rewards.append((s, a, r))\n",
    "\n",
    "  # calculate the returns by working backwards from the terminal state\n",
    "  G = 0\n",
    "  states_actions_returns = []\n",
    "  first = True\n",
    "  for s, a, r in reversed(states_actions_rewards):\n",
    "    # the value of the terminal state is 0 by definition\n",
    "    # we should ignore the first state we encounter\n",
    "    # and ignore the last G, which is meaningless since it doesn't correspond to any move\n",
    "    if first:\n",
    "      first = False\n",
    "    else:\n",
    "      states_actions_returns.append((s, a, G))\n",
    "    G = r + GAMMA*G\n",
    "  states_actions_returns.reverse() # we want it to be in order of state visited\n",
    "  return states_actions_returns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rewards:\n---------------------------\n-0.10|-0.10|-0.10| 1.00|\n---------------------------\n-0.10| 0.00|-0.10|-1.00|\n---------------------------\n-0.10|-0.10|-0.10|-0.10|\n"
     ]
    }
   ],
   "source": [
    "grid = negative_grid(step_cost=-0.1)\n",
    "# print rewards\n",
    "print(\"rewards:\")\n",
    "print_values(grid.rewards, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial policy:\n---------------------------\n  L  |  R  |  R  |     |\n---------------------------\n  U  |     |  R  |     |\n---------------------------\n  D  |  R  |  R  |  L  |\n"
     ]
    }
   ],
   "source": [
    "# state -> action\n",
    "# initialize a random policy\n",
    "policy = {}\n",
    "for s in grid.actions.keys():\n",
    "  policy[s] = np.random.choice(ALL_POSSIBLE_ACTIONS)\n",
    "  \n",
    "# initial policy\n",
    "print(\"initial policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (1, 2): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (0, 0): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (2, 3): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (2, 0): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (1, 0): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (2, 2): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (0, 2): {'L': 0, 'D': 0, 'R': 0, 'U': 0}, (2, 1): {'L': 0, 'D': 0, 'R': 0, 'U': 0}}\n"
     ]
    }
   ],
   "source": [
    "# initialize Q(s,a) and returns\n",
    "Q = {}\n",
    "returns = {} # dictionary of state -> list of returns we've received\n",
    "states = grid.all_states()\n",
    "for s in states:\n",
    "  if s in grid.actions: # not a terminal state\n",
    "    Q[s] = {}\n",
    "    for a in ALL_POSSIBLE_ACTIONS:\n",
    "      Q[s][a] = 0\n",
    "      returns[(s,a)] = []\n",
    "  else:\n",
    "    # terminal state or state we can't otherwise get to\n",
    "    pass\n",
    "  \n",
    "# initial Q values for all states in grid\n",
    "print(Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# repeat\n",
    "deltas = []\n",
    "for t in range(5000):\n",
    "  # generate an episode using pi\n",
    "  biggest_change = 0\n",
    "  states_actions_returns = play_game(grid, policy)\n",
    "\n",
    "  # calculate Q(s,a)\n",
    "  seen_state_action_pairs = set()\n",
    "  for s, a, G in states_actions_returns:\n",
    "    # check if we have already seen s\n",
    "    # called \"first-visit\" MC policy evaluation\n",
    "    sa = (s, a)\n",
    "    if sa not in seen_state_action_pairs:\n",
    "      old_q = Q[s][a]\n",
    "      returns[sa].append(G)\n",
    "      Q[s][a] = np.mean(returns[sa])\n",
    "      biggest_change = max(biggest_change, np.abs(old_q - Q[s][a]))\n",
    "      seen_state_action_pairs.add(sa)\n",
    "  deltas.append(biggest_change)\n",
    "\n",
    "  # calculate new policy pi(s) = argmax[a]{ Q(s,a) }\n",
    "  for s in policy.keys():\n",
    "    a, _ = max_dict(Q[s])\n",
    "    policy[s] = a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEACAYAAABfxaZOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGMlJREFUeJzt3XuwHGWdxvHvL0RQoyLgArWJBLlGLoKK0VpxGd0FIlYR\nyy1rwVIMqAQ1XrCyImtpEgtrsUoKdLOuiWazgS1NkGtAjFzMKeSWxJIQCAk5JOR+AZSAud9++0f3\nMH0mZ87MOadn+p15n0/VnDPd09P9zjvdz7zz9mXM3RERkTgMKboAIiLSOgp9EZGIKPRFRCKi0BcR\niYhCX0QkIgp9EZGI1A19M5thZlvMbEkf0/zUzLrNbLGZnZ1vEUVEJC+NtPRnAhfWetDMPg6c6O4n\nA+OBn+dUNhERyVnd0Hf3R4BX+phkLHBzOu0C4HAzOyaf4omISJ7y6NMfDqzLDG9Ix4mISGC0I1dE\nJCJDc5jHBuCdmeER6biDmJku9CMiMgDubnnMp9GWvqW33swFLgMwsw8BW919S60Zubtu7kyaNKnw\nMoRyU12oLlQXfd/yVLelb2a/AkrAUWa2FpgEHJrkt0939/vM7CIzex7YDlyeawlFRCQ3dUPf3T/T\nwDQT8imOiIg0k3bkFqRUKhVdhGCoLipUFxWqi+awvPuL+lyYmbdyeSIincDM8BbvyBURkQ6g0BcR\niYhCX0QkIgp9EZGIKPRFRCKi0BcRiYhCX0QkIgp9EZGIKPRFRCKi0BcRiYhCX0QkIgp9EZGIKPRF\nRCKi0BcRiYhCX0QkIi0P/TvvhKVLW71UERGBAn5EBZxSCebPb9liRUTamn5ERUREBkShLyISEYW+\niEhEFPoiIhEpJPRbuO9YREQy1NIXEYmIQl9EJCIKfRGRiCj0RUQiotAXEYmIQl9EJCIKfRGRiCj0\nRUQiotAXEYmIQl9EJCIKfRGRiOjaOyIiEWko9M1sjJktN7MVZnZNL4+/zczmmtliM3vazMblXlIR\nERm0uqFvZkOAqcCFwOnApWY2qmqyrwJL3f1s4KPADWY2tNY8H364cv+RR+DFF3s+fuedcOBAYy8g\nBk89BStXFl0KEekEjbT0RwPd7r7G3fcCs4GxVdM48Nb0/luBv7j7vkYK8JGPwNVX9xz3qU/BihWN\nPDsOZ58NpVLRpRCRTtBI6A8H1mWG16fjsqYCp5nZRuAp4BuDLZjl8hPAIiKSVbMLpp8uBJ5094+Z\n2YnAA2b2HnffdvCkk5O/k6FUKgGlnIogItIZurq66Orqasq8Gwn9DcBxmeER6bisy4H/AHD3lWb2\nAjAK+NPBs5uc/J3cz5KKiESiVCqljeLElClTcpt3I907i4CTzGykmR0KXALMrZpmDfDPAGZ2DHAK\nsKrRQqgrR0SkNeq29N19v5lNAO4n+ZCY4e7LzGx88rBPB64D/tfMlqRP+7a7/7XRQvR23L6O5e9J\n9SEieWioT9/d5wGnVo2blrm/iaRfX0REAqbLMIiIRCSI0FefvohIawQR+iIi0hoKfRGRiCj0RUQi\notAXEYmIQl9EJCIKfRGRiAQb+joDtSfVh4jkIdjQFxGR/Cn0RUQiEkTo64xcEZHWCCL0RUSkNRT6\nIiIRUeiLiEREoS8iEhGFvohIRBT6IiIRCSL0dcimiEhrBBH6+mH0+lQfIpKHIEJfRERaQ6EvIhKR\nIEJfffoiIq0RROiLiEhrKPRFRCKi0BcRiYhCX0QkIgp9EZGIKPRFRCISROjrkE0RkdYIIvR1GYb6\nVB8ikocgQl9ERFojiNBX946ISGsEEfoiItIaCn0RkYg0FPpmNsbMlpvZCjO7psY0JTN70syeMbP5\n+RZTRETyMLTeBGY2BJgK/BOwEVhkZne7+/LMNIcD/wVc4O4bzOwdzSqwiIgMXCMt/dFAt7uvcfe9\nwGxgbNU0nwFud/cNAO7+cr7FFBGRPDQS+sOBdZnh9em4rFOAI81svpktMrPP5VVAERHJT93unX7M\n533Ax4BhwONm9ri7P5/T/EVEJAeNhP4G4LjM8Ih0XNZ64GV33wXsMrOHgbOAXkJ/cvJ3MpRKJaDU\n60J1BmpPqg+ReHR1ddHV1dWUeZvXSRMzOwR4jmRH7iZgIXCpuy/LTDMK+E9gDHAYsAD4V3d/tmpe\nDsnyyos1g8sug1mzstPB00/DGWcM7sV1CjM45hjYvLnokohIEcwMd8/lNNa6LX13329mE4D7SfYB\nzHD3ZWY2PnnYp7v7cjP7PbAE2A9Mrw586d3WrXDEEWrJi0hrNNSn7+7zgFOrxk2rGv4x8OOBFCLm\nyzC8+mrRJRCRmOiMXBGRiCj0RUQiotAXEYmIQl9EJCIKfRGRiCj0RUQiEkTox3zIpohIKwUR+vph\n9PpUHyKShyBCX0REWkOhLyISkSBCv1l9+s89B/v2NWfeIiLtKIjQb5ZRo2DGjKJLISISjo4OfYBt\n24ougYhIODo+9EVEpKLjQ1+HOoqIVHR86IuISIVCX0QkIkGEvi7DICLSGkGEvi7DUJ/qQ0TyEETo\ni4hIawQR+ureERFpjSBCv5nULSIiUtHxoS8iIhUKfRGRiHR86Gt/gYhIRceHvvr0RUQqOj70RUSk\nIojQVxeMiEhrBBH6zTwjt1O6dzrldYhIsYIIfRERaQ2FvohIRIII/aVLm9d9of0FIiIVQYT+woXw\n+OPNmbf6wkVEKgoL/f37YeTIyvDu3UWVREQkHoWF/p49sHZtUUsXEYlTEN070LxuGHXviIhUNBT6\nZjbGzJab2Qozu6aP6T5gZnvN7FP5FVFERPJSN/TNbAgwFbgQOB241MxG1ZjueuD3jSy4VUfV6Ogd\nEZGKRlr6o4Fud1/j7nuB2cDYXqb7GnAb8GKO5RMRkRw1EvrDgXWZ4fXpuNeZ2d8Dn3T3/wZyaVvr\nMgw9dcrrEJFi5bUj9yYg29ff7+BXqImINN/QBqbZAByXGR6Rjss6B5htZga8A/i4me1197kHz24y\nANdeC1BKbyIiUtbV1UVXV1dT5t1I6C8CTjKzkcAm4BLg0uwE7n5C+b6ZzQTu6T3woRz6w4YNpLj9\np28QItJuSqUSpVLp9eEpU6bkNu+6oe/u+81sAnA/SXfQDHdfZmbjk4d9evVTciudiIjkqpGWPu4+\nDzi1aty0GtNekUO5cqNDNkVEKgo7I1dhLCLSeroMg4hIRIIJfRERaT6FvohIRIINfXXLiIjkL9jQ\nl570ISgieVDoB27NmqJLICKdJJjQV0u2d1deWXQJRKSTBBP6zaIPExGRio4PfRERqdAZuYFTPYlI\nntTSFxGJSGGhX93Xrr53EZHmU0tfRCQiCv3AqU9fRPIU7I5c/TB6T53yOkSkWGrpi4hEJJgduYO1\nZw+MG5fvPEVEOk0wLf2rrhrc8zdtglmz8imLiEinKiz0H3qo5/ALLxRTjtBpR66I5Kmw0H/88Xzn\np3AUEakvmO6dZtFRLyIiFR0f+iIiUqHQD5y6rdrbgw/C1q1Fl0KkIrjQ/+Uv+37cDLZvb3x+Ck0p\n0vnnw/XXF10KaYWVK9sjb4IL/eqjenqzY0fj81Ofvoi0wurVRZegMcGFfllfYd3bY+3wCTsY+vCq\nb//+oksgEr7gQr/Tw1uaZ+hQuOOOokshsWqX7Aou9PPW7i3kdlmRQtHdXXQJRMLWlqHf7kEuzRPi\nuhFimSRewYV+tmU7ciTcfnv/nyci0mrtkkHBhX7W2rXQ1TW4ebTLGyEi0gpBhz4M/quxvlrHJcT3\nO8QySbyCD/3exLQR6ZuKiOQpuNAfaMgpHEWkSO2SQcGFfjV170h/6P0W6VtDoW9mY8xsuZmtMLNr\nenn8M2b2VHp7xMzOHGzB+ntGbqeL8TV3Cr13EpK6oW9mQ4CpwIXA6cClZjaqarJVwD+6+1nAdcAv\nBlqgvL8itctXrlravfwisWiXbbWRlv5ooNvd17j7XmA2MDY7gbs/4e6vpoNPAMPzKqBaSSIi+Wkk\n9IcD6zLD6+k71L8I/G4whcqTPjTiovdbpG9D85yZmX0UuBw4t/ZUkzP3S+mtf2K8yqaIxKOrq4uu\nwZ6ZWkMjob8BOC4zPCId14OZvQeYDoxx91dqz25ynwurDm+13KTdaR2OQ54Nz1KpRKlUen14ypQp\nuc27ke6dRcBJZjbSzA4FLgHmZicws+OA24HPufvK3Eon+gbTTwpYkb7Vbem7+34zmwDcT/IhMcPd\nl5nZ+ORhnw58DzgS+JmZGbDX3Uc3s+Ai7UIfRBKShvr03X0ecGrVuGmZ+18CvjTYwuzc2duyGxuX\nd4t4yxY46qjkhzlEROppl2/lQZ2RO3FiOBV37LH6Qet2pFa1SN+CCv2XX85/noMJgc2b8yvHQIXy\nISgHW7kSzjqr6FKI9E9QoZ+lyzD0FONrDt3ChbBkSdGlEOmf4EJ/oIdsNqNFrKCVvjS6zmk9ikO7\nfCsPLvQHqrxhaQOLm95/kb51TOg3gwJE8qD1SEIS1AGJfR2eeeBAZcdqvf7+dvma1YhOei2dRu+N\ntKPgWvq1NqSZM2F4btfulE6lVrUUpV0aAcGFfi31Dues1ac/mBBQgEhf2mUjF8kKPvRrdfmMHQv3\n3tv68oiItLOgQt+s8dbT3Lkwe/bB4/NsnaulL31RS1+y2mV9CCr0B6NTA7pdVqRQhLgetLpMt9wC\nK1a0dpnSPoIL/X37eg7398xctfSlVUL9QL7sMpg8uehSSKiCOmTz1lsr93UZhp5ifM0ikr/gWvr9\noZa+VGvlexbaZRieeQb+9rfWLlMqQv3mVy2oln5vGm3x15qu3Vf+dlmRpHhnngnjxxddCgldW7b0\n1fUj0rvyDxFpO5Ba2jL0y1avrj+NWspxCbF7p5V04cHihLg+9KYtQ/+115L/TzxRGaczciVUWo8k\nJMGHfm8bTKt+rUgba2dbtCj5LeSBCrFlVy6T1l2pJfjQ769OW9lDDJZOMXo0fOELRZeiOfLcDg4c\ngOefz29+UqxgQ3/79uT/zJnwxz8WU4ZO+wCJQX/fs/37B76s0A7ZbJY774STTy66FOFrlwZasKF/\n+eWV+7/+df3ps336a9fqa640plPXjzxfV/nYf+kMwYb+xo2V+/VW4N27Kyvmb35T+bGVwQopEEIq\niyTapWU3WEW9zmeegVdeKWbZnSzY0M+qF3jjxsEZZ1Tuf/CDlcfafcNs9/K3Wn8/HPVhWl9R6+CZ\nZ8JXvlLMsgeiXbbVYEN/797K/XobZnd37ce0UUtfWrF+FLEO5rnMIsNsx47ilt2pgg39rHorcLt8\nwkpnCXm965TQV6Mtf20R+i+9BN/9bu+PucOaNbWf+4MfDHy5WuHaT+zdO512Rm6nvI6QtEXo33VX\n7UPrHnss+VDoj5074ZJLBl+uVgq5VdnODhwY+HNDPGQz2y2aF7X0G9Mu22hbhH5ftm2rP82wYT2H\nV6+GOXPqPy+EFU6HnjZXp9brYD7MqjUrzMzq99l36vtTpLYP/Ubs2AFvehM88EAyHGILTdpPiC27\ncthX/wLdYAxpYkqUT8KsRdtg/qIIfYBdu+CCC2DdusrGeuONsHhxseWKxa5dsGdP85ejPv3kf56h\n38wPt3r1307vT1/1tGdPOFnT9qHf3xOxTjut8uZ861swcWL+ZeqPTtvxVsvpp8NFFxVdioMNpt5D\n/MZYXtZgLi9RrZmhX68bKs9uqiJNmwbvfW/RpUgE/8tZ9Ywb17/pt23ruRI/9FCyoWTH7dqV/M9z\nwxmoELsQBmLVqjDPruy0D9tySHZK6Ify/rz2GrztbQN//u7d+ZVlsNq+pZ+H8lfhF1+Ehx9O+v+h\n0t/4ve/Bo4/CffcVUz4IZ+UfjFa02tS9k/xX6Ofr8MMHd6JYM/eL9FdDRTGzMWa23MxWmNk1Nab5\nqZl1m9liMzs732Lm6+GHew5/7WvJ/4kT4bzzKuPLG85118G558InPpEMd3fDX/5SmW7fPnj11eaV\nt1OE+FW9Fd07rdSfHbkPPQQ339zc8tRSrvd2CX0Y3AdpW4W+mQ0BpgIXAqcDl5rZqKppPg6c6O4n\nA+OBnzehrLn54hd7Dk+blhzffMstPcffc0/vzz/lFPjsZ5MVcsoUeMMb4O1vT7qFXnkl+VZwxRXJ\nSjJ9evJDHStW9JxHV1dXbq+nXdTawIusi5BCBQZfF/3ZkXvVVfD5z9efrhkfbo2VsyvX9+fTn4Zn\nn60/3apVPQ/pzu53W7ECNmzo/7Kvvrr/z2mWRj5/RgPd7r7G3fcCs4GxVdOMBW4GcPcFwOFmdkyu\nJW2yQw/tfXz1Cj98ePJ/3rzkjZw8ufLYOefAkUcm3wpmzoShQ2H8eBg1Ck49NTkhbNasZAfy3Xd3\n8dJLlRXq3nsr81m+HP7618rPQkKlq+l3v4OlSyvja/UVbt3ad8tkx45k5W6k9f3CC/WnaUR/Q//K\nKwd3RnWjyvtw+qsZO3LzCv1GWqVDG9yj14zQb2zfQ76hf9ttPbezWr7//Z4nb5bLuH9/sh2ff37v\nz8vWUyMfLkVpJPSHA+syw+vTcX1Ns6GXaQB497v7U7zwZC/5/JOf9HwsG8ZZW7cm/+fMSXY833gj\n3HQTHH00nHBC8tjFFycrjVlSR0cdlfQj3nprZT5myREwZ5wBY8cmw298Y+V52dsRRyQbtRn89rfw\ns5/1fHzYMDjxRDjkkGQlP+ccuOGG5IOsXIbytCecACNHJiv8DTdAVxe8//1J98AddyRdBHfdlUw7\ndSosXJiUe84c+OEPYf78pPw7dyaXy509O5nHxInJcx55BE46KTmkbdGiZB/Ks8/CL34BkyYlv62w\nfTssWJB0q23cmHyDGj8++fByrxzFtX49PPhgEiobNyZXapwwITlkrrs7ec7u3ZX38dFHk304GzfC\npk3JdNmuuzVrKkH62GNw++3JZbz37IGvfz0Zv3dv8toOHEjm/dpryTe+cit2165kHtUBtmrVwT/X\nuGkT/OlPyX33pE7mzas8vn17cgb6l7+cXE22ep7lb6d79yb1NWVKz5bqxo1J/bpXGhW7d1emWbjw\n4Hlmw2z+/KSM1bZuTdaxnTsry6rlm9+snDmcff1LliT/d+yoHN7b23y2b0/G79yZdKuuX5+MG8g+\ntwULKmXZuzd538oNwH37knmW38fy/1p9++V6OnAgOVqtt8bEgQOV84UK+5bp7n3egH8BpmeGPwv8\ntGqae4B/yAw/CLyvl3m5u/sVV5Q3gZhvkwIoQyg31YXqoti6OOywgT931KjBL//4493PO6/nOLPs\nMF4vqxu9WRrGNZnZh4DJ7j4mHf5OWoAfZab5OTDf3eekw8uB89x9S9W8+l6YiIj0yt1z6WhrpFdv\nEXCSmY0ENgGXAJdWTTMX+CowJ/2Q2Fod+JBfoUVEZGDqhr677zezCcD9JPsAZrj7MjMbnzzs0939\nPjO7yMyeB7YDl/c1TxERKUbd7h0REekcLTtloJETvNqdmc0wsy1mtiQz7ggzu9/MnjOz35vZ4ZnH\nrk1PaFtmZhdkxr/PzJakdXVTq1/HYJnZCDP7g5ktNbOnzezr6fgY6+IwM1tgZk+mdTEpHR9dXZSZ\n2RAz+7OZzU2Ho6wLM1ttZk+l68bCdFzz6yKvPcJ1jgAaAjwPjATeACwGRrVi2a28AecCZwNLMuN+\nBHw7vX8NcH16/zTgSZIutuPT+il/81oAfCC9fx9wYdGvrZ/1cCxwdnr/LcBzwKgY6yIt95vT/4cA\nT5Cc+xJlXaRlvxr4P2BuOhxlXQCrgCOqxjW9LlrV0m/kBK+25+6PANWXFRsLzErvzwI+md6/GJjt\n7vvcfTXQDYw2s2OBt7r7onS6mzPPaQvuvtndF6f3twHLgBFEWBcA7l4+svswko3WibQuzGwEcBHw\ny8zoKOsCMA7ubWl6XbQq9Bs5watTHe3pkUzuvhk4Oh1f64S24ST1U9bWdWVmx5N8+3kCOCbGuki7\nM54ENgMPpBtolHUB3Aj8G8kHX1msdeHAA2a2yMzKF4dpel20/aWV21A0e87N7C3AbcA33H1bL+dp\nRFEX7n4AeK+ZvQ2408xO5+DX3vF1YWafALa4+2IzK/UxacfXRerD7r7JzP4OuN/MnqMF60WrWvob\ngOMywyPScTHYUr4OUfpV7MV0/AbgnZnpynVSa3xbMbOhJIF/i7vfnY6Osi7K3P01oAsYQ5x18WHg\nYjNbBfwa+JiZ3QJsjrAucPdN6f+XgLtIusGbvl60KvRfP8HLzA4lOcFrbouW3WqW3srmAuPS+58H\n7s6Mv8TMDjWzdwEnAQvTr3SvmtloMzPgssxz2sn/AM+6e/YKRdHVhZm9o3wEhpm9CTifZB9HdHXh\n7v/u7se5+wkkGfAHd/8cyWVcxqWTRVEXZvbm9JswZjYMuAB4mlasFy3cUz2G5CiObuA7Re85b9Jr\n/BWwEdgNrCU5Se0IkmsRPUdygtvbM9NfS7IXfhlwQWb8+9MVoBv4SdGvawD18GFgP8lRWk8Cf07f\n/yMjrIsz09e/GFgCfDcdH11dVNXLeVSO3omuLoB3ZbaPp8uZ2Iq60MlZIiIRCej3XEREpNkU+iIi\nEVHoi4hERKEvIhIRhb6ISEQU+iIiEVHoi4hERKEvIhKR/wcL5BDStSYUFwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1952d50d7f0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(deltas)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n 0.58| 0.77| 1.00| 0.00|\n---------------------------\n 0.41| 0.00| 0.78| 0.00|\n---------------------------\n 0.25| 0.09|-0.10| 0.00|\n"
     ]
    }
   ],
   "source": [
    "# find the optimal state-value function\n",
    "# V(s) = max[a]{ Q(s,a) }\n",
    "V = {}\n",
    "for s in policy.keys():\n",
    "  V[s] = max_dict(Q[s])[1]\n",
    "\n",
    "print(\"final values:\")\n",
    "print_values(V, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  U  |  L  |  L  |  R  |\n"
     ]
    }
   ],
   "source": [
    "print(\"final policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}