q_learning_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 Q-Learning 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')\n",
    "ALPHA = 0.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_action(a, eps=0.1):\n",
    "  # epsilon-soft to ensure all states are visited\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": 4,
   "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",
    "\n",
    "# print rewards\n",
    "print(\"rewards:\")\n",
    "print_values(grid.rewards, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (1, 2): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (0, 0): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (2, 3): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (2, 0): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (1, 3): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (1, 0): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (2, 2): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (0, 3): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (0, 2): {'L': 0, 'U': 0, 'D': 0, 'R': 0}, (2, 1): {'L': 0, 'U': 0, 'D': 0, 'R': 0}}\n"
     ]
    }
   ],
   "source": [
    "# no policy initialization, policy is derived from most recent Q like SARSA\n",
    "\n",
    "# initialize Q(s,a)\n",
    "Q = {}\n",
    "states = grid.all_states()\n",
    "for s in states:\n",
    "  Q[s] = {}\n",
    "  for a in ALL_POSSIBLE_ACTIONS:\n",
    "    Q[s][a] = 0\n",
    "\n",
    "# initial Q values for all states in grid\n",
    "print(Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "update_counts = {}\n",
    "update_counts_sa = {}\n",
    "for s in states:\n",
    "  update_counts_sa[s] = {}\n",
    "  for a in ALL_POSSIBLE_ACTIONS:\n",
    "    update_counts_sa[s][a] = 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 0\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 2000\niteration:"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 4000\niteration: 6000\niteration: 8000\n"
     ]
    }
   ],
   "source": [
    "# repeat until convergence\n",
    "t = 1.0\n",
    "deltas = []\n",
    "for it in range(10000):\n",
    "  if it % 100 == 0:\n",
    "    t += 1e-2\n",
    "  if it % 2000 == 0:\n",
    "    print(\"iteration:\", it)\n",
    "\n",
    "  # instead of 'generating' an epsiode, we will PLAY\n",
    "  # an episode within this loop\n",
    "  s = (2, 0) # start state\n",
    "  grid.set_state(s)\n",
    "\n",
    "  # the first (s, r) tuple is the state we start in and 0\n",
    "  # (since we don't get a reward) for simply starting the game\n",
    "  # the last (s, r) tuple is the terminal state and the final reward\n",
    "  # the value for the terminal state is by definition 0, so we don't\n",
    "  # care about updating it.\n",
    "  a, _ = max_dict(Q[s])\n",
    "  biggest_change = 0\n",
    "  while not grid.game_over():\n",
    "    a = random_action(a, eps=0.5/t) # epsilon-greedy\n",
    "    # random action also works, but slower since you can bump into walls\n",
    "    # a = np.random.choice(ALL_POSSIBLE_ACTIONS)\n",
    "    r = grid.move(a)\n",
    "    s2 = grid.current_state()\n",
    "\n",
    "    # adaptive learning rate\n",
    "    alpha = ALPHA / update_counts_sa[s][a]\n",
    "    update_counts_sa[s][a] += 0.005\n",
    "\n",
    "    # we will update Q(s,a) AS we experience the episode\n",
    "    old_qsa = Q[s][a]\n",
    "    # the difference between SARSA and Q-Learning is with Q-Learning\n",
    "    # we will use this max[a']{ Q(s',a')} in our update\n",
    "    # even if we do not end up taking this action in the next step\n",
    "    a2, max_q_s2a2 = max_dict(Q[s2])\n",
    "    Q[s][a] = Q[s][a] + alpha*(r + GAMMA*max_q_s2a2 - Q[s][a])\n",
    "    biggest_change = max(biggest_change, np.abs(old_qsa - Q[s][a]))\n",
    "\n",
    "    # we would like to know how often Q(s) has been updated too\n",
    "    update_counts[s] = update_counts.get(s,0) + 1\n",
    "\n",
    "    # next state becomes current state\n",
    "    s = s2\n",
    "    a = a2\n",
    "   \n",
    "  deltas.append(biggest_change)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYcAAAEACAYAAABYq7oeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGdFJREFUeJzt3X+wHXV9//HnKwQEEYNOJYwJBAUEYQZS2i/mC1jviNME\nisbp+B0TabFMBzIKQv2BUP2DUP2jjoUWBmlICX4FgWD5fq352lQpwi3zTTWGHykRbsilQEgCiQZI\nIFgxP979Y/fmnpy995w95+6ePeee12Pmzj2757O779177r7OZ3+co4jAzMys1pSqCzAzs+7jcDAz\nswyHg5mZZTgczMwsw+FgZmYZDgczM8vIFQ6S5klaL2mDpKvHeP4kSf8u6TeSvlAzfqakByU9KWmd\npCuKLN7MzMqhZvc5SJoCbADOBV4E1gALImJ9TZvfAWYBHwdejYgb0vFHA0dHxFpJbwMeBebXTmtm\nZt0nT8/hTGA4IjZGxG5gOTC/tkFEbI+IR4E9deO3RsTa9PEuYAiYUUjlZmZWmjzhMAPYVDO8mTZ2\n8JKOA2YDq1ud1szMOqsjJ6TTQ0r3AVemPQgzM+tiU3O02QIcWzM8Mx2Xi6SpJMFwZ0T8oEE7f8iT\nmVmLIkJlzDdPz2ENcIKkWZIOARYAKxq0ry/0duCpiLix2YIiwj8RXHvttZXX0A0/3g7eFt4WjX/K\n1LTnEBF7JV0O3E8SJssiYkjSouTpWCppOvAIcASwT9KVwCnA6cCFwDpJjwMBfCUiflTS+piZWQHy\nHFYi3ZmfVDfu1prH24Bjxph0FXDQRAo0M7PO8x3SXWhgYKDqErqCt8Mob4tR3had0fQmuE6RFN1S\ni5lZL5BEVHhC2szM+ozDwczMMhwOZmaW4XAwM7MMh4OZmWU4HMzMLMPhYGZmGQ4HMzPLcDiYmVmG\nw8HMzDIcDmZmluFwMDOzDIeDmZllOBzMzCzD4WBmZhkOBzMzy3A4mJlZhsPBzMwyHA5mZpbhcDAz\nswyHg5mZZTgczMwsw+FgZmYZDgczM8twOJiZWYbDwczMMnKFg6R5ktZL2iDp6jGeP0nSv0v6jaQv\ntDKtmZl1H0VE4wbSFGADcC7wIrAGWBAR62va/A4wC/g48GpE3JB32pp5RLNazMxslCQiQmXMO0/P\n4UxgOCI2RsRuYDkwv7ZBRGyPiEeBPa1Oa2Zm3SdPOMwANtUMb07H5TGRac3MrCI+IW1mZhlTc7TZ\nAhxbMzwzHZdHS9MuXrx4/+OBgQEGBgZyLsbMbPIbHBxkcHCwI8vKc0L6IOBpkpPKLwE/BxZGxNAY\nba8FdkXE9W1M6xPSZmYtKPOEdNOeQ0TslXQ5cD/JYahlETEkaVHydCyVNB14BDgC2CfpSuCUiNg1\n1rRlrIiZmRWnac+hU9xzMDNrTdWXspqZWZ9xOJiZWYbDwczMMhwOZmaW4XAwM7MMh4OZmWU4HMzM\nLMPhYGZmGQ4HMzPLcDiYmVmGw8HMzDIcDmZmluFwMDOzDIeDmZllOBzMzCzD4WBmZhkOBzMzy3A4\nmJlZhsPBzMwyHA5mZpbhcDAzswyHg5mZZTgczMwsw+FgZmYZDgczM8twOJiZWYbDwczMMhwOZmaW\n4XAwM7OMXOEgaZ6k9ZI2SLp6nDY3SRqWtFbS7Jrxn5f0C0lPSLpL0iFFFW9mZuVoGg6SpgA3A3OB\nU4GFkk6ua3MecHxEnAgsApak498NfA44IyJOA6YCCwpdAzMzK1yensOZwHBEbIyI3cByYH5dm/nA\nHQARsRqYJml6+txBwOGSpgJvBV4spHIzMytNnnCYAWyqGd6cjmvUZgswIyJeBK4HXkjH7YiIB9ov\n18zMOmFqmTOXdCRJr2IWsBO4T9KnIuLusdovXrx4/+OBgQEGBgbKLM/MrKcMDg4yODjYkWUpIho3\nkOYAiyNiXjp8DRAR8Y2aNkuAhyLi3nR4PfAh4IPA3Ii4JB3/p8AHIuLyMZYTzWoxM7NRkogIlTHv\nPIeV1gAnSJqVXmm0AFhR12YFcBHsD5MdEbGN5HDSHEmHShJwLjBUWPVmZlaKpoeVImKvpMuB+0nC\nZFlEDElalDwdSyNipaTzJT0DvAFcnE77c0n3AY8Du9PfS8taGTMzK0bTw0qd4sNKZmatqfqwkpmZ\n9RmHg5mZZTgczMwsw+FgZmYZDgczM8twOJiZWYbDwczMMhwOZmaW4XAwM7MMh4OZmWU4HMzMLMPh\nYGZmGQ4HMzPLcDiYmVmGw8HMzDIcDmZmluFwMDOzDIeDmZllOBzMzCzD4WBmZhkOBzMzy3A4mJlZ\nhsPBzMwyuiocLrig6grMzAxAEVF1DQBICgi6pBwzs64niYhQGfPuqp6DmZl1B4eDmZllOBzMzCwj\nVzhImidpvaQNkq4ep81NkoYlrZU0u2b8NEn/KGlI0pOSPlBU8WZmVo6m4SBpCnAzMBc4FVgo6eS6\nNucBx0fEicAiYEnN0zcCKyPi/cDpwFBBtZuZWUny9BzOBIYjYmNE7AaWA/Pr2swH7gCIiNXANEnT\nJb0d+GBEfDt9bk9EvFZc+WZmVoY84TAD2FQzvDkd16jNlnTce4Dtkr4t6TFJSyUdNpGCzcysfFM7\nMP8zgMsi4hFJfwdcA1w7dvPFLF6cPBoYGGBgYKDk8szMesfg4CCDg4MdWVbTm+AkzQEWR8S8dPga\nICLiGzVtlgAPRcS96fB64EPp0z+NiPem488Bro6Ij46xHN8EZ2bWgqpvglsDnCBplqRDgAXAiro2\nK4CLYH+Y7IiIbRGxDdgk6X1pu3OBp4op3czMytL0sFJE7JV0OXA/SZgsi4ghSYuSp2NpRKyUdL6k\nZ4A3gItrZnEFcJekg4Fn657LePBBmDIFfETJzKw6XffZSiO6pCwzs65V9WElMzPrMw4HMzPLcDiY\nmVmGw8HMzDIcDmZmluFwMDOzDIeDmZllOBzMzCzD4WBmZhkOBzMzy3A4mJlZhsPBzMwyHA5mZpbh\ncDAzswyHg5mZZTgczMwsw+FgZmYZDgczM8twOJiZWUbXhsPu3VVXYGbWv7o2HLZurboCM7P+1bXh\nYGZm1XE4mJlZhsPBzMwyHA5mZpbhcDAzswyHg5mZZTgczMwsI1c4SJonab2kDZKuHqfNTZKGJa2V\nNLvuuSmSHpO0Im9h//Ivye81a+Ckk/JOZWZmRWgaDpKmADcDc4FTgYWSTq5rcx5wfEScCCwCltTN\n5krgqVYKW5HGyMMPw4YNrUxpZmYTlafncCYwHBEbI2I3sByYX9dmPnAHQESsBqZJmg4gaSZwPnBb\nK4Xt29dKazMzK1KecJgBbKoZ3pyOa9RmS02bvwWuAqKVwhwOZmbVmVrmzCX9EbAtItZKGgDUeIrF\n+x9t3z4ADJRVmplZzxkcHGRwcLAjy8oTDluAY2uGZ6bj6tscM0abTwAfk3Q+cBhwhKQ7IuKisRe1\neP+jI4/MUZmZWR8ZGBhgYGBg//B1111X2rLyHFZaA5wgaZakQ4AFQP1VRyuAiwAkzQF2RMS2iPhK\nRBwbEe9Np3tw/GA4kA8rmZlVp2nPISL2SrocuJ8kTJZFxJCkRcnTsTQiVko6X9IzwBvAxRMtzOFg\nZlYdRbR0nrg0kqL+nHUEXH89fOlLo8NmZpaQREQ0OZfbnq6/Q1qlrLaZmTXS9eFgZmad53AwM7MM\nh4OZmWWUehPcRH3zmzA0VHUVZmb9p6uvVqrXJaWamXWFvr5aqd769b6CycysbD0XDs89V3UFZmaT\nX8+Fg5mZla/nwsGHlMzMytdz4WBmZuVzOJiZWUZPhcPwMFx11YHjVq1K7ocwM7Pi9FQ43H03/OIX\nB477+tfhy1+uph4zs8mqp8JhLL4xzsyseD0fDmZmVjyHg5mZZfR8OPiwkplZ8Xo+HMZy6aXw+79f\ndRVmZr2rqz+yu13/+q/w/PPZ8b/+Nbz1rR0vx8ys50zKnsNYdu+Gww+vugozs97Q8+GQ95zDvn3l\n1mFmNpn0bDgMDhYzn+efh9tuK2ZeZmaTRc+GwyuvwPe+l5xfyGO8T3O9/nq45JLi6jIzmwx6Nhwi\n4KGHqq5i1BtvwA03VF2FmVkxejYcus3DD8MXv1h1FWZmxejZcCjq5jd/eZCZWVZPh0MrO/aRtu2E\nyk9+4juxzay/5AoHSfMkrZe0QdLV47S5SdKwpLWSZqfjZkp6UNKTktZJuqLI4jvlIx+Bp59u3GYk\nfHbtKr8eM7OyNQ0HSVOAm4G5wKnAQkkn17U5Dzg+Ik4EFgFL0qf2AF+IiFOB/wlcVj9tu77znfGf\na/Quv90eQN7pLr20vfmbmXWTPD2HM4HhiNgYEbuB5cD8ujbzgTsAImI1ME3S9IjYGhFr0/G7gCFg\nRhGF//M/FzGX/PKGw8svl1uHmVkn5AmHGcCmmuHNZHfw9W221LeRdBwwG1jdapEjfvWrA4fffDPb\nZvVq2LgxO35k517WuYPHHit3/mZmndSRE9KS3gbcB1yZ9iDa8q1vHTg8VjjMmdNqbfnaNdvpf/Wr\njZ+/5RbYvDnfsszMqpbnU1m3AMfWDM9Mx9W3OWasNpKmkgTDnRHxg8aLWlzzeCD9KVZV7+wvuwxe\negm+9rVqlm9mvW9wcJDBoj47qIk84bAGOEHSLOAlYAGwsK7NCuAy4F5Jc4AdEbEtfe524KmIuLH5\nohbnq7oCvh/CzKo2MDDAwMDA/uHrrruutGU1PawUEXuBy4H7gSeB5RExJGmRpEvTNiuB5yQ9A9wK\nfAZA0tnAhcCHJT0u6TFJ84oqvp0ddtlXK+WZR/25EzOzbpPry34i4kfASXXjbq0bvnyM6VYBB02k\nwEZaCYdOHU7Ks5yjjoIdO2DatPLrMTNrR8/eId2KL34RhoeTx/U776JOSLdqz55i52dmVqRJ+TWh\n9W64AQ49dOznqjpB7Utezayb9UXPAWDnzuR3KzvlnTvhd3+3uBpql/2ud8GzzxY3bzOzIvV0OLRy\nRVf9PRIjGh1Wev55WLu2lYpa4xPTZtatejocNtXck71uXb5pWuk51LZtNF1twDT7XKdVq9qrpVPW\nrYPXX6+6CjOrWk+HQ63TTqu6gnzOOafqCho77TS45pqqqzCzqk2acMirG9+td5v/+q+qKzCzqk2q\ncNi2rXmbbtKrQbVyJfzxH1ddhZmVaVKFw9FHN2/Tyn0O7ey8y/guiW5zzz3w/e9XXYWZlWlShUMe\nVX58RtGeeQZ++cvi59vuug4PwxNPFFuLmVWj78KhSkV/eN+JJ8IFFxQ7zzzGW4+zzoLTT+9sLWZW\njr4Lh3YvZS1j2UXMf+Q7q994A159deLzg+LW+4UXYOvWYuZlZp3Vd+EwWc2fD+9+d7U11PcoZs2C\ns8+uphYzm5i+C4eyzx1UdUL6P/8TfvOb8uZfqzYERj7QcDw7dpRbS9keemi0d2bWTyZ1OOzb17xN\nVZ/KWtQ8R+ZRux7btsHLL098ns08/zy8733tL6cXfPjDcNNNVVdh1nmTOhw2b57Ycf52dt7d8I1x\nJ57Y+ndpt2P37gOHx1r3brzKq1V53mT0ou9+F/7mb6quwrrVpA6HWbPgT/6kmHnl3cl1emc41vJe\nfz35vupWvflmvnYjIZAnCCdDOExWV12V/ExWv/51/te0ZU3qcAC4++4Dh6vcWXX7jnLkyqK8dU5J\nXz0j91pM1p7DZFiHsXRDL7dMp5wC551XdRW9q6vCYeHCqis4UNF3SBcx//HU/6N34pDYSPvp01tf\n1muvZYPbrEgbN5Z3U+YDD8DnPlfOvLtFV4VDJ3YWk+1d4FgnpMtWxGGlO++ECy/MfqfFK69030eG\nT7bXzIjJ3nOA8v52f//3cPPN5cy7W3RVOHTC7t0HXvI5Wf9BOtFzmFL36mnlsNJI2y1bDhx/3HEw\nd25rdVRtz57JGyA2tsm636jVd+Fw1FFw2GHw29+2Nl2Rl52WocgXa7M6izwhXf/8668X8/WpL7/c\nucNWBx8M997bmWUVqR92cA7t9vVdOIw444zkhbN9e9WVlKOKnkMrdTRaVhGXjv7DPySHrfK6446J\n3ey2YUP707Zq8eLkTU6viIC9e6uuolj9EKx9Gw5PPgmXXJLsFMZT5d3UE51HJ3op9f8g7fzDjFVn\nEeFw0EGttf/0p2HmzOy9G5BvW3byHeqqVcV8/3indnBf+xpMndqZZdUb6++yffvEL3F1OExyy5ZV\nXcHEFRkOIy/4vNNO5LBS2T2HPL2aejt3tr/T7eSNcr22Y+q2j3F/17vgiiuqrqL79XU41JJgyRL4\nj/8Y3UHU7tjKuAmu2y5lLbqGRnU0CqKqwgHGrifPtvyrv0re0XdCr4VDN3rhhaor6H4Ohxqf+QzM\nnp0cz5UOPAa9cePE59/tJ8fy7nRa2Tm1s87dFg55nXNOcldu2doNh3POOfDcyFhvKDZvbr+u8VQZ\nZmUddu2HgHY4NFD7XQTd/p3JRfYciuwltdNzKOLkZad7Du20bVe7O6ZVq+Dhh8d//oEH4Jhj2pt3\nI43qveUWuPXWYpdX+0nBVZyTmyxy/QtJmidpvaQNkq4ep81NkoYlrZU0u5Vpax1xRP7iy1b/Dvas\ns+Av/iJ5/NRTna9nLGUemipi+l465wAT357dHA5w4Latn89rr7U/30Ya1XvZZfDZzxa3rEcfPfCT\ngt1zaF/TfyFJU4CbgbnAqcBCSSfXtTkPOD4iTgQWAUvyTlvvhz9sYy1KUv8C+ulP4cYbk2A49dTk\nQ/3OOKP45Q4ODk54HmVeylrkYaVG79Qnsh1avVqpUT2tKOvEdBGvCWi8fmXt8JrNt9Vt1mhbVPGd\nJpNVnvdXZwLDEbExInYDy4H5dW3mA3cARMRqYJqk6TmnPcAf/EGLa1Ci8f6RhoaS33fdBY8/fuBz\n//ZvyfmJN99MPg751VdHu7l5X7jt7AiKeLG2erXSRHakeQ4rTWSHWFXPoRPh0O66QeOew0Tm20jR\nO9JGr4v6dfBhpfbleTnMADbVDG9Ox+Vpk2fajG9+M0dVHTDepa6f+ETj6Y47Dg49NPk45He+c7Sb\nW/9ZLJ/8JNx+exIkEtxzD7z4YnK11G23wXPPjd7J/dvfwj/9U9J+1y742c+S8eO9yPfuTa7Zr/+c\nom3bxm4fMbqsdv9xuumwUpE9h1a2Rydu9irqsFKR822k0XyLDqS88/NhpebKujVlQpvuS1/qjs+Z\nb3Tyrghbt8Kf/3nyA/CpT43d7oILDjzcNtIeko+aqH2h1j4+5JDRx8cck/RcfvWr5Hud3/GOZPwP\nf5gEWW2vZvlyWLkyewx67lz48Y9Hh2fOHH08Z87olS4zZsD735883rMn+fKhk+sOJq5Zk/z+7Gfh\n6KOTdiM3Ju3bl6zzhg3wyCPjX1Lc6Iuc1q1Lfn/0o7Tk4ouz572+/vVsD3E8CxfCW97S2jLzePrp\n5Hg6jL4WWl03gK9+FX70o+TxyBV4I/NZv779+TbSqN6RsGplmbXbot7IRSQj89u1a+x5/+QnE1vP\nifwNeoWiSYRKmgMsjoh56fA1QETEN2raLAEeioh70+H1wIeA9zSbtmYe7uiZmbUoIkrpx+TpOawB\nTpA0C3gJWADUf/PCCuAy4N40THZExDZJ23NMC5S3gmZm1rqm4RAReyVdDtxPco5iWUQMSVqUPB1L\nI2KlpPMlPQO8AVzcaNrS1sbMzArR9LCSmZn1n8rvkG71JrleJGmmpAclPSlpnaQr0vHvkHS/pKcl\n/VjStJpp/jK9qXBI0h/WjD9D0hPp9vq7KtZnoiRNkfSYpBXpcL9uh2mS/jFdtyclfaCPt8XnJf0i\nXY+7JB3ST9tC0jJJ2yQ9UTOusPVPt+fydJqfSjq2aVERUdkPSTg9A8wCDgbWAidXWVNJ63k0MDt9\n/DbgaeBk4BvAl9PxVwN/nT4+BXic5LDfcek2GunlrQb+R/p4JTC36vVrY3t8HvgusCId7tft8L+B\ni9PHU4Fp/bgtgHcDzwKHpMP3Ap/up20BnAPMBp6oGVfY+gOfAW5JH38SWN6spqp7Di3fJNeLImJr\nRKxNH+8ChoCZJOv6nbTZd4CPp48/RvLH2xMRzwPDwJmSjgaOiIj0QlDuqJmmJ0iaCZwP3FYzuh+3\nw9uBD0bEtwHSddxJH26L1EHA4ZKmAocBW+ijbRER/x94tW50ketfO6/7gHOb1VR1OLR1k1wvk3Qc\nyTuEnwHTI2IbJAECjHy/V/122cLoTYW1n5vZi9vrb4GrgNqTXf24Hd4DbJf07fQQ21JJb6UPt0VE\nvAhcD7xAsl47I+IB+nBb1DmqwPXfP01E7AV2SHpno4VXHQ59RdLbSFL7yrQHUX81wKS+OkDSHwHb\n0l5Uo0uXJ/V2SE0FzgC+FRFnkFzldw199poAkHQkyTvbWSSHmA6XdCF9uC2aKHL9m946UHU4bAFq\nT4zMTMdNOml3+T7gzoj4QTp6m5LPoCLtEv4yHb8FqP3w5JHtMt74XnE28DFJzwL3AB+WdCewtc+2\nAyTv6jZFxCPp8P8hCYt+e00AfAR4NiJeSd/Vfh84i/7cFrWKXP/9z0k6CHh7RLzSaOFVh8P+G+wk\nHUJyk9yKimsqy+3AUxFxY824FcCfpY8/DfygZvyC9AqD9wAnAD9Pu5Y7JZ0pScBFNdN0vYj4SkQc\nGxHvJflbPxgRfwr8P/poOwCkhws2SRr5gOlzgSfps9dE6gVgjqRD03U4F3iK/tsW4sB39EWu/4p0\nHgD/C3iwaTVdcJZ+HsnVO8PANVXXU9I6ng3sJbka63HgsXS93wk8kK7//cCRNdP8JclVCEPAH9aM\n/z1gXbq9bqx63SawTT7E6NVKfbkdgNNJ3iCtBf4vydVK/botrk3X6wmSE6cH99O2AO4GXgTeJAnL\ni4F3FLX+wFuA76XjfwYc16wm3wRnZmYZVR9WMjOzLuRwMDOzDIeDmZllOBzMzCzD4WBmZhkOBzMz\ny3A4mJlZhsPBzMwy/huybdWWKkcQ5gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2a1acc7f940>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(deltas)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# determine the policy from Q*\n",
    "# find V* from Q*\n",
    "policy = {}\n",
    "V = {}\n",
    "for s in grid.actions.keys():\n",
    "  a, max_q = max_dict(Q[s])\n",
    "  policy[s] = a\n",
    "  V[s] = max_q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "update counts:\n---------------------------\n 0.18| 0.18| 0.18| 0.00|\n---------------------------\n 0.18| 0.00| 0.04| 0.00|\n---------------------------\n 0.18| 0.02| 0.02| 0.00|\n"
     ]
    }
   ],
   "source": [
    "print(\"update counts:\")\n",
    "total = np.sum(list(update_counts.values()))\n",
    "for k, v in update_counts.items():\n",
    "  update_counts[k] = float(v) / total\n",
    "print_values(update_counts, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n 0.62| 0.80| 1.00| 0.00|\n---------------------------\n 0.46| 0.00| 0.80| 0.00|\n---------------------------\n 0.31| 0.46| 0.62| 0.46|\nfinal policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  U  |  R  |  U  |  L  |\n"
     ]
    }
   ],
   "source": [
    "print(\"final values:\")\n",
    "print_values(V, grid)\n",
    "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
}