SARSA_demo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Adapted from: https://github.com/lazyprogrammer/machine_learning_examples/tree/master/rl\n",
    "# the SARSA 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": 13,
   "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": 14,
   "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": 15,
   "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": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (1, 2): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (0, 0): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (2, 3): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (2, 0): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (1, 3): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (1, 0): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (2, 2): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (0, 3): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (0, 2): {'U': 0, 'R': 0, 'D': 0, 'L': 0}, (2, 1): {'U': 0, 'R': 0, 'D': 0, 'L': 0}}\n"
     ]
    }
   ],
   "source": [
    "# no policy initialization,  policy is derived from most recent Q\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": 17,
   "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": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration:"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\niteration: 2000\niteration: 4000"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\niteration: 6000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 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])[0]\n",
    "  a = random_action(a, eps=0.5/t)\n",
    "  biggest_change = 0\n",
    "  while not grid.game_over():\n",
    "    r = grid.move(a)\n",
    "    s2 = grid.current_state()\n",
    "\n",
    "    # we need the next action as well since Q(s,a) depends on Q(s',a')\n",
    "    # if s2 not in policy then it's a terminal state, all Q are 0\n",
    "    a2 = max_dict(Q[s2])[0]\n",
    "    a2 = random_action(a2, eps=0.5/t) # epsilon-greedy\n",
    "\n",
    "    # we will update Q(s,a) AS we experience the episode\n",
    "    alpha = ALPHA / update_counts_sa[s][a]\n",
    "    update_counts_sa[s][a] += 0.005\n",
    "    old_qsa = Q[s][a]\n",
    "    Q[s][a] = Q[s][a] + alpha*(r + GAMMA*Q[s2][a2] - 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": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYcAAAEACAYAAABYq7oeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X+4HHV59/H3HSIKIkF9FDHhh/yQX4oRNISi9Sh9JMFC\nnqt9akFafGgt0RLwslYCtspJW68K1AoxVRKMFCgQMBUIGEOgcFBQYiAJgZCQhEgSTiAEISBEICT3\n88fMcvbszu7O7s7szOx+Xtd1rrM7+52Ze2Zn5575zne+Y+6OiIhIuRFZByAiIvmj5CAiIlWUHERE\npIqSg4iIVFFyEBGRKkoOIiJSJVZyMLMJZrbKzFab2dQaZaab2RozW2ZmY8uGf8XMHjGz5WZ2rZnt\nmlTwIiKSjobJwcxGADOAE4EjgdPM7LCKMhOBg9z9EGAycHk4/L3AOcDR7n4UMBI4NdElEBGRxMU5\ncxgHrHH39e6+HZgDTKooMwm4GsDdFwGjzGzv8LNdgLea2Uhgd2BTIpGLiEhq4iSH0cDGsvdPhsPq\nlRkERrv7JuA7wIZw2FZ3v7P1cEVEpBNSvSBtZnsRnFXsD7wX2MPMPpfmPEVEpH0jY5QZBPYrez8m\nHFZZZt+IMn8ErHP35wDM7CfAHwDXVc7EzNTJk4hIk9zd0phunDOHxcDBZrZ/2NLoVGBeRZl5wBkA\nZjaeoPpoM0F10ngze4uZGXACsLLWjNxdf+5ceOGFmceQhz+tB60LrYv6f2lqeObg7jvMbAqwkCCZ\nzHb3lWY2OfjYZ7n7fDM7yczWAi8DZ4bj/trM5gJLge3h/1lpLYyIiCQjTrUS7r4AOLRi2MyK91Nq\njDsNmNZqgCIi0nm6QzqH+vr6sg4hF7QehmhdDNG66AxLu94qLjPzvMQiIlIEZoZneEFaRER6jJKD\niIhUUXIQEZEqSg4iIlJFyUFERKooOYiISBUlBxERqaLkICIiVZQcRESkipKDiIhUUXIQEZEqSg4i\nIlJFyUFERKooOYiISBUlBxERqaLkICIiVZQcRESkSqzkYGYTzGyVma02s6k1ykw3szVmtszMxobD\n3m9mS81sSfj/BTM7N8kFEBEpikWLso4gvoaPCTWzEcBq4ARgE7AYONXdV5WVmQhMcffPmNmxwGXu\nPj5iOk8Cx7r7xoj56DGhItLVzGDbNthtt6Sml+1jQscBa9x9vbtvB+YAkyrKTAKuBnD3RcAoM9u7\noswfAY9HJQYREcmXOMlhNFC+Q38yHFavzGBEmT8Hrm82wFbNmAGf/Wyn5iYi0l1GdmImZvYm4BTg\n/E7MD+DKK2HJkk7NTUSku8RJDoPAfmXvx4TDKsvsW6fMROBBd99Sb0b9/f1vvO7r66Ovry9GeCIi\nvWFgYICBgYGOzCvOBeldgMcILkg/BfwaOM3dV5aVOQk4O7wgPR64tPyCtJldDyxw96vqzCfRC9LH\nHBOcOegat4jkRZEuSDc8c3D3HWY2BVhIcI1itruvNLPJwcc+y93nm9lJZrYWeBk4syz43QkuRp+V\nxgKIiEjyGp45dIrOHESk2xXpzKHr75C+9dasIxARKZ6uTw6nnJJ1BCIixdP1yUFERJqn5CAiIlWU\nHEREpIqSg4iIVFFyEBGRKkoOIiJSRclBRESqKDmIiEgVJQcREami5CAiIlWUHEREpIqSg4iIVFFy\nEBHpoKI8RkDJQUREqig5iIh0kKXyaJ7kKTmIiEgVJQcREakSKzmY2QQzW2Vmq81sao0y081sjZkt\nM7OxZcNHmdmPzWylma0ws2OTCl5ERNLRMDmY2QhgBnAicCRwmpkdVlFmInCQux8CTAYuL/v4MmC+\nux8OfAhYmVDsIiKSkjhnDuOANe6+3t23A3OASRVlJgFXA7j7ImCUme1tZnsCH3f3K8PPXnf3F5ML\nX0RE0hAnOYwGNpa9fzIcVq/MYDjsfcCzZnalmS0xs1lmtls7AYuISPpGdmD6RwNnu/sDZnYpcD5w\nYVTh/v7+N1739fXR19eXcngiIsUxMDDAwMBAR+Zl3uB2PTMbD/S7+4Tw/fmAu/tFZWUuB+529xvC\n96uAT4Qf/8rdDwyHfwyY6u4nR8zHG8XSjGOOgSVLgtdFuSNRRLqbGWzbBrslVH9iZrh7KndOxKlW\nWgwcbGb7m9muwKnAvIoy84Az4I1kstXdN7v7ZmCjmb0/LHcC8GgyoYuISFoaViu5+w4zmwIsJEgm\ns919pZlNDj72We4+38xOMrO1wMvAmWWTOBe41szeBKyr+ExERHKoYbVSp6haSUS6XbdVK4mISI9R\nchARkSpKDiIiUkXJQUREqig5iIhIFSUHERGpouQgIiJVCpccdu7MOgIRkdYV5b6rwiWHXXaBu+/O\nOgoRke5WuOQA8MQTWUcgItLdCpkc4rBUbigXEekNXZscilKvJyK9pSgHrl2bHEREpHVKDiIiUkXJ\nQUREqvREcjjvvKwjEBEplp5IDpdcknUEIiLFUsjkoJZIIiLpKmRyEBGRdMVKDmY2wcxWmdlqM5ta\no8x0M1tjZsvM7MNlw58ws4fMbKmZ/TqpwNvx+ONw8slZRyEikl8jGxUwsxHADOAEYBOw2MxucfdV\nZWUmAge5+yFmdizwA2B8+PFOoM/dn088+hbdeSfcdtvwYa+8Am95SzbxiIjkTZwzh3HAGndf7+7b\ngTnApIoyk4CrAdx9ETDKzPYOP7OY88nMa6/BbrtlHYWISH7E2WmPBjaWvX8yHFavzGBZGQfuMLPF\nZvY3rQaaph07mh/HDG6/PflYRETyoGG1UgKOd/enzOxdBElipbvfG1Wwv7//jdd9fX309fV1ILzW\nLVkCJ56Y3PQuvzz4/8UvJjdNEekeAwMDDAwMdGRecZLDILBf2fsx4bDKMvtGlXH3p8L/W8zsJoJq\nqobJoRd96UvBfyUHEYlSedA8bdq01OYVp1ppMXCwme1vZrsCpwLzKsrMA84AMLPxwFZ332xmu5vZ\nHuHwtwKfBh5JLHoREUlFwzMHd99hZlOAhQTJZLa7rzSzycHHPsvd55vZSWa2FngZODMcfW/gJjPz\ncF7XuvvCdBZFRESSEuuag7svAA6tGDaz4v2UiPF+A4xtJ0AREem8XDcxTUtRHraRZ+vXqxsTkW7W\nk8mhUlGSxcAAfPazWUcROOAAuPnmrKMQKZ6iHFQpObSh01/y9dfDj38cr+zWrenGAvDii82VP+gg\n+N730olFRJKl5NCl3v52uOOOrKMYbt06uOuu+OXXr08vFhGpL1fJIckj8aJUFaXpmWeyjqA9BxwA\njz2WdRQivSlXyWHBguSmVZR6vSLrxDp+5ZX05yEi1XKVHJ57LusIREQEcpYc4tJZgYgUVVGqvAuZ\nHKR37bYb3BvZM5eIJClXyeGhh7KZb1Eyed5kcQb3yivw4IOdn69Ir8lVcrjkkmzm2+pOLu/VW3mM\nL48xJen+++HVV7OOQqR9uUoOIkV33HEwc2bjciJ5p+TQhrxXR6UdX1ZnAXk/+9i+PX7ZJ55ILQyR\ntig5SOHMmpV1BMl53/uUICSflBykcFauzDqCZOkaheRRIZND3qtz0pL36hQR6R65TA7PP18/AbS7\nk6ycdq8mGymmpUuzjkB6QS6Tw7PPZh2B5N0LL2QdQXKaOdhZvx6OPjq9WERKcpkcepXOYKrV2nGe\ndlpn42hGmtV/r78+9Fp9kUmaYiUHM5tgZqvMbLWZTa1RZrqZrTGzZWY2tuKzEWa2xMzmJRF0J82d\nC6NHR3/W6WsASh5Dnn8+6wiytWULvPOdWUch3axhcjCzEcAM4ETgSOA0MzusosxE4CB3PwSYDFxe\nMZkvA48mEnGH3XMPbNqUdRT5pAvk2VFX5pK2OGcO44A17r7e3bcDc4BJFWUmAVcDuPsiYJSZ7Q1g\nZmOAk4AfJha19AydLSXjgQeyjkCKJk5yGA1sLHv/ZDisXpnBsjLfBb4G6DhTJEInzsA++lEYHEx/\nPmm66y54tJD1D8U0Ms2Jm9lngM3uvszM+oAGx4H99PfDb38L0Bf+9Q4zVdVIenbuzDqC9pxwAhx1\nVHa9Nyelnd/4wMAAAwMDicVST5zkMAjsV/Z+TDisssy+EWX+L3CKmZ0E7Aa8zcyudvczomcVJIe1\na2HGjFjxJ0JVF61RIsuOttnWrF8PX/4y3Hxz1pE0b+pU+Ou/7qO/v++NYdOmTUttfnGqlRYDB5vZ\n/ma2K3AqUNnqaB5wBoCZjQe2uvtmd/+6u+/n7geG491VOzHEl/edkllrXSIkvVx5XE9JxdSrO8d2\nlrvo1UpJGBiAW27JOorWXHwxXHtt5+bXMDm4+w5gCrAQWAHMcfeVZjbZzM4Ky8wHfmNma4GZwN+m\nGHMsWe88tm3Ldv4ilebMyToCKZJY1xzcfQFwaMWwmRXvpzSYxj3APc0G2KpmjlDzeISdhKwTpIgU\nl+6QzpGi7cy7NamKSE6Tg3Y6ydB67F5FO5CQZHTyN53L5JCVpFf8OecM7wunXXnb2WsHVSx52356\nVVF+N7lMDo1WXhFWrnvQHDfLPoCKsJ6ktZ22dvSt0W8ivlwmh7RpA0lGKzuoXlj32nFLN+jJ5JCV\n2bPr7ziS3nHmcSfVbEx5XAaRrOiaQwNF3WF84Qvw0ktZRyHdoBfOwCRbhUwOeZH35zloByLlinpQ\nJdlQcsjIWWelfxaR9s5AO5tkaD1KHuUyOXTDEW+jH/wVV8CKFe3P57rrYOPGxuWKqhu2BcmPom9P\nuuaQkSIewZ1+etAhV5Si/xCkWuk71XfbmiL+xrOi5JCyyo0x7Y1zyxbYsSPdeeSBdo7Sizq53Ss5\npCTOl5jUF12ecN79brj00urhadDNWyLdS8mhCz39dNYRiEgaev6ag44uk6GqFynXDb+r5cuzjqB3\n5DI5NJKXjbxeHHFiTKNaqdxXvwqTJyczD8kXJf7WaL3Fl8vk0OkvMM1k08yyNCrbbJybN8OsWc2N\nI0Hz4DPafphtujpxgGQWbEPSm3KZHLIS9YOrt8NuJYnl5axHarviCrjmms7Nr1PbRCvb63PPJR9H\n3tx0Exx+eOfm18733fPXHHpFWtVK3XrqvHRp1hEMNzgIr75aPTyvBwB5jStrCxfCqlVZR5E/sZKD\nmU0ws1VmttrMptYoM93M1pjZMjMbGw57s5ktMrOlZvawmV2YZPD1Y05mOkn/oPK24zaD115rbdxO\ndNldPo+Bgebnl6YxY6C/P5t566y1c775zd64d6hSw+RgZiOAGcCJwJHAaWZ2WEWZicBB7n4IMBm4\nHMDdXwU+6e4fBsYCE81sXLtBt7uD7eQOugg/yO3bg//uyT65LkoR1kcznn026wgkbf/8z7B1a9ZR\ndF6cM4dxwBp3X+/u24E5wKSKMpOAqwHcfREwysz2Dt9vC8u8GRgJdNnuIVoRH4RzwQWw227ZxpAH\nWX8PedJtyVzfbXxxksNooLxrtyfDYfXKDJbKmNkIM1sKPA3c4e6LWw83vk53WxFXXuKIsnRp9JnD\nAw/U7r+p1yXxfeZ5m5Dhzj0Xzjsvu/l3clsZmfYM3H0n8GEz2xO42cyOcPdHo0v3099feu5yX/iX\nX3l9nkPSR0cXXQRz51b/KLRTk6Jpd5v93vdg112zO1hav36A/v6BjswrTnIYBPYrez8mHFZZZt96\nZdz9RTO7G5gA1E0O69bB9Om1A+qWnVJaF8174VGcaVYP5PmalnplzUZefiMHHNBHf3/fG++nTZuW\n2rziVCstBg42s/3NbFfgVGBeRZl5wBkAZjYe2Orum83sf5nZqHD4bsD/BnLbaCzJDUA/3mTkfT1G\nbTN52ZFIvhRtu2h45uDuO8xsCrCQIJnMdveVZjY5+Nhnuft8MzvJzNYCLwNnhqPvA1wVtngaAdzg\n7vPTWZRGyzG0o+nEl5SH7jOkGPKcALVt5Uvurjm4+wLg0IphMyveT4kY72Hg6GaD0gZZDPqektGp\n9ajvKzoR90I1bCt68g7pTh6pVc6rU33i5FWv/LC6RZ63JUlXTyaHTqq3M8xLtZJ22L1BO/poWi/R\ncpkc0viyWt0B5mnDyduT3fK0bkR6gTre62Jp7FCzanqZ5RlHnpuyNkvXHCSPlBzKNNssMemH/WS9\nk641/zzuVPISU5GasuqZ39KMQiaHpDfYTv4AyueV1nzzXN3TTq+sMiTP33Geab3FV8jkkBfdsqE1\n2gF3y3LG1a3L263L1Ut0zSEFeTwCzUv3GUnNN61x8qxIy1OkWPOmF9ddzySHcjqCkjzpxR1Pnmj9\nR8tlcmi08+7WnXu3LpcUV7ftONXFeny5TA7dJIub4Lo1yZQvV56bsqpXVklLJ7/3nkkOecn2eYmj\nXKsx5XFZktDpO87zvKPPc2ytyMPytLN99fwF6ax2Oml0wJXkxpiHDTtL3ZqMJFu9/ruqJZfJIQlF\n+MKz6JSvFXmNKy3deoe0JKMI+5YkFDI5dPK0vxc2hDwvY55jg+7fsXf78rWiV9ZJLpNDnjreS1q9\nZUuq+4w871Dz8j0UVVHqqyUdPX/NIQmdaCXUyvzLh+elK4ki3iGdx5jyTslBmtG1yUGkVc0knk63\nm28nKSqhZt+5ZZEoOTRQhAfp9OKGm+dlznNsUk2PCY0WKzmY2QQzW2Vmq81sao0y081sjZktM7Ox\n4bAxZnaXma0ws4fN7Nwkg29GnC+0V770pGh9ZaeVI2D1hVV8ubrmYGYjgBnAicCRwGlmdlhFmYnA\nQe5+CDAZuDz86HXg79z9SOA44OzKcSv95jdNL0Nmkv6ieuG0v53rLJ1aP73wPUjnFS3RxjlzGAes\ncff17r4dmANMqigzCbgawN0XAaPMbG93f9rdl4XDXwJWAqPrzeyOO+CZZ5pcioLK2zOki7bxinRK\nLx4wjIxRZjSwsez9kwQJo16ZwXDY5tIAMzsAGAssqjezyZNjRJSwNHaKcVorFUWSMRehKWanv6Mi\nbhO9Josz2KzFSQ5tM7M9gLnAl8MziBr6y173sW1bH7vvHrx78cWhM4q81J1220aSl6a1ceRl3Uet\ng7zEloRuWpZairTdb9gwQH//QEfmFSc5DAL7lb0fEw6rLLNvVBkzG0mQGK5x91vqz6p/2LsPfADW\nrQten3463HZbjGhj6MQGH6f3zLz88OLGsW4dHHhgurHkQV6+lyjqlbW37bdfH/39fW+8nzZtWmrz\ninPNYTFwsJntb2a7AqcC8yrKzAPOADCz8cBWdy9VKf0IeNTdL2s2uPKL0+WJ4YtfDLL3c881O8V8\nS+oHn9aO46CD0plut+mmXllV5dW7GiYHd98BTAEWAiuAOe6+0swmm9lZYZn5wG/MbC0wE/gSgJkd\nD5wOfMrMlprZEjObkETgt9wC73xn8Pq++2DLFnj11SSm3Hs2bYLXXmt+PO04sqN1L2mLdc3B3RcA\nh1YMm1nxfkrEePcBu7QTYC2bNw+9/tjHgv9HHAG/+AW84x3V5Vu9z6Hdo7p6/R7lpbXS4YfDN75R\n+/M8H9mmIc93SEs28vId5eo+hyJ59NGhs4lOqPdFtdJaKcs+jrZsiVfutdfy80PpZZ26Ca4X6A7p\naF2VHEq+8x1YsiTrKJqzcye88kpr43ZyY33zm+Hii4PXnT6jyOMZjJ79UCx53IbyqrDJod6XPDWy\ng48htX5g27a1Hk+7kvzRp9252KpVzZVvZR4ltZYlLz/ybt9Zd/vySW2FTQ5pbLRHHTX8/QsvwPe+\nl/x8WhV3mZNeN722g8jz2UBekmKvSeNaYd7lPjnccANcdVVz40T92OLc4ThYcffGiy/Wn09//9Dr\nV1+F3/8+VniR2tngktp5F2mj77WEVUsz60HrrHV5WXedjKMjd0i343OfC+rjK9XbkWXxRX7qU/Db\n38Ly5cH7Whd4e/E2/KTk5QdartGBiHSfInTjn4TcJ4dGHnqoelgWK3/ZsuCaxcawh6kvfCH4/8wz\n8J73wOLF9ccvygZTrpWYi9RVgegAppflvlqpkbg9uFZWGbUjzg+mdENe6Qzik58M/o8ZAw8+mFws\nUfSDlihq/hq9DvR7iVbY5NDsF/r+9w+Nt3Vr8HrRInj++XTiqRXfK6/ARz5Sv4wUR9Y3wemaQ3O0\nDuLLfXJIo+vr0oXm8eOr76aeOjXoYO7ll1ufPsCIcM3WSwCHHx49fNOmYLzTT4c1a6KvuXRSHpNY\nmjG1O+08ri+pTU+JjFbY5JDWPC6+OOhgbo89gpvpSqZOhdWr4dln04+nVFV23XXBGc+//AuMHQs3\n3xwMf6mi0/Of/Qy2b08/rkp56To9S0kkgmamkafE89BD8MEPZh1F53XbNlxL7pNDLe38SOKOO7Os\n96iLL4Zrr4V3vWt4mVNOGaqmSsuaNcEPsXT9YuXK4Z9v2QK77gp77tn6PO68s3rYypXtNc9NWp52\njFnLww7q5z+HRx7JOgpJS2GTQydU/gCjfpC33gpvf/tQNVTpqD6LVjm/+13wv7Ibjr//e/jbv60/\n7tq11TEccQTsvjvMnRs9zpYtcMklrcXaLYrUlFVnesnI8iBFHe8V2Nixwf/HHhs+vJ2ePivHbbSB\nrF07/P13vgM/+EH8+Tfyn/8Z/L/xRjjvvOSmmxd5vkM6yXHbVcQzuVZjLuKytquwyaET1UrN7pTL\nlY7iP/Wp4e/jOPro4e8rq60aXV9odYfR6jodNSpIGPfdN3z4zp1BddyDD8Ldd9cef3AwX9VXkh8z\nZsCGDVlH0ZtnUIVNDkU92qq0enXjMrfeOvz9xz4WtIZasya6fK3le+ih+Mse5+E/pSfxvfginHnm\n0HM1Sn772+BC/kc+MpQkIUhCy5cH/zdvDu79KD0rvKR0feXDH4bp04PXX/nK8Gm8+93BdaCSJ56A\nCeGjpNzh+OOD16+/DvfcM3z6zz8PO3Y0XsbScpbi/+Uvh9/93uy2NHNm/O7RTz45XkOD9evh179u\n7YFNeXfOOcOv/eVBq/uPPO134ihscugWcZJDFPehezfiGjs2SCqLFjVOFEce2Xh6te4Ree65YB5R\nli0L/j/+ePD/6aejy5WfLf3iF9FltmwZ/tk998Dttw+9/+Uvg//z50Nf3/Bx3/EO+OhH450trVgx\ndOZz/PHDk1SzvvhFuPrqeGVvuy1eY4eTT4Zjjw26U/+TPxkafuWVcP31tcf76U+Ds7177x0a1m4f\nYWko2k41TbrmEEMn2v53shltJ7vsHj8+SBRRLZRKKq9bNONrXwvmEWXTpuB/aSdWukZTz7PP1m5C\n3Gi9udc+Q1i6tPG8W5lns+MnOb2bbhp6/Vd/NdSNS5Q//uPgbO/jHx8aNmHC8Ptvam1L73lPdO8E\n994bnDG2olYiLFpy2LatOx5ZHCs5mNkEM1tlZqvNLPJpCWY23czWmNkyM/tw2fDZZrbZzJYnFTTA\nv/976+POmtXaeGlspFlu+GlVQ7z+evvTKN8pDQzAe987/PPSeps1K2idtXNn4150680rzhF6eUyl\nPrR+//uhJFO+3C+91Pl7dKI0+4yS5cuDaqpG09+8ObhZtNLHP974eSpRtm0LWv2V7LUXTKl68PCQ\n+++vvQO+447mDh5L3+vcucFv4rXXap/Rlsdb6/dz+OFD1ZvtGhyMX/2ZtIbJwcxGADOAE4EjgdPM\n7LCKMhOBg9z9EGAyUN425spw3ES1Wh0DyfazlEdZPfchTfXq3rdtgx/+EM49d2hY+RlZnKqjuNcB\nStMsXeu4+eahBgQ/+cnQ5297G1x+ORxzDHz728E1mVbuh4mzY8jqe6w13507g3XSzA668vt94QX4\nj/+oXf6442of5H3600HyiBK1LZSW48/+DP7nf+DCC2GffaLLlIwZE5SPsmEDPPxw7dibMWYMXHHF\n0PvvfjeZ6cYR58xhHLDG3de7+3ZgDjCposwk4GoAd18EjDKzvcP39wIJ9WDUWZ1ovpblDjqteXd6\nmdxrV4NFxRJ1DSOJrtQrd3BPPBE8rnb+/KA1V+nI+GtfC+ZReaf7jTfCN74xfNg++1S3AitXawdZ\nPu2oM7l2u4epxz04m0rqrv1a21O96bdT7dzorAGC620rVtT+PMnfQCd6ZYgSJzmMBjaWvX8yHFav\nzGBEmdyK21Su26qVKufd6jOs406/GY120D//+fD5VFafDAzEG7d8GnGZRZev1fS5XtVMuW99K+gq\npVJlK7ByZ58dva7e9rah1296U3Uce+wRPb1SC7SSp54Kpv/kk7VjKKk8I//Sl4JWVCVLl9auCqq3\n/jv5G+nF+xlqKewF6ZLbbmt/GkccET28SNUuSYjaabYii5vIKqsgSi2Kmm3RlYTK5S9vDRSlle3s\nZz9rffxSo4A4nngi+H/DDdWfVS7n/PnD3195ZdCKquToo+EtbwnGq9XS7Z3vrB62cSP8678OvY9T\npfx3fxc9vNG6Kl+mqVOHzkCarfevTLLl7rsv2+fVxxXnYT+DwH5l78eEwyrL7NugTAz9Za/7wr/6\nSm3g42j2VDrpViX15pFFIkq7WqkTNyqWzy9q2Lp1wx/n2sq8o7aDNNZdnGUulYl6yFVcoyPO6X/+\nc/jDP6we3swRfSm2OOvmmWeGX4AujRu1U73++uFNcg89tPH0Gz1cK46LL4YLLghez5oF//RPwz9v\ndRuYMCG4R6fyzDGeAfr7B1qbcZPiJIfFwMFmtj/wFHAqcFpFmXnA2cANZjYe2Oru5Ytu4V8D/THC\naV2zTRdHdOC8qpvPTjq1bI3mE2dHmmWVYStJNOmm3J/4RPP9RLWTHLJ+Dkaz80i6c824DykrjyHQ\nR39/3xvvpk2bllRIVRru/tx9BzAFWAisAOa4+0ozm2xmZ4Vl5gO/MbO1wEzgjW7ezOw64JfA+81s\ng5mdmcJyxNLsxlRZB3/VVcnFUtLNyaFT4q7D22+Ht741uglmvWlEPcgpzjWHTok736Q73qv1gKtW\nkkOnfgeN1lWtz8uTcafP9rPaR8R6hrS7LwAOrRg2s+J9ZKtkd/9cy9HlTDN1tVnKuilrp59xEPco\n+pZbgrreH/2ouVjirKf+/qHqjk70bVU+jzR3HjNmxC9bij/rh1MlqZcP3gp/QboZefyis4zpssvS\nmW4S1xziBMJnAAAKmklEQVRamV+jYc32TFurG4moaw6tnN2XmkI2s75K8+nUdrNq1fD/9TRz5lBr\n3Kw12+Ksnosuaj+eLCk5ZCzLC9K1mnuWnnHdikmT4JprgtdFOu0uTWPBguAOW2i/C4RGcZWe7AfB\nxck4N06VOhDs9Pbywx82rifvdLVSO+vg0kuD/6+8MvzhWbWSVLPXYwDOP7+5mEodUZamPW9ec+Mn\nraeSQx6l8XjPdnccDz7Y+rjlG3Q718raba3UrFJTxYkTh641/epX0bFcf30y1xyuvDL4P25c0Alg\nvW5HSndwl+bbyh247a6nb34zeIRulPvuG9qWszjQ+d3v4KtfjV/+gQeC/5dcUt2EO6rKrlPLVPqe\nt24NDrSy1FPJIas+SurppvrZSt//fmfmU3r4UNJOOin438pRY7M2bqz/+T/+Y5B8Sgmo3k1+tbRb\ndfPAA9EX8yG4Ue9v/iZ4HXebfuaZ5rotaRRbZX9rxx0XnCGUeud98MHqu40r71KHbJNDlKhWYQsW\npD/fnkoOJ5yQdQTV3GH27O7si79Z3/720Otmmh1/85vVw5r9Mdcqf9ZZzU+r1JVHkjuU0s1oRRC3\nWunww4P2/jNnpnPN4f77g5shS2ewH/lIdWd+US2uorpUj3oOx86d0TcHtiPu9afliXZjGq2nkkMe\nuQfdKtd6/kErKu9ULYoLLoAPfjC4sbH8uQSdUGuHdsUVwzs+q1e+9IMuVRc18/S/RkpVXe10Gtnu\nDjhusvvxj+OVK93w9vWvd/6aQy31boCsvNdhwwY49dSh8cp7s01S1HJ2osZBySFjebxInqVHHql+\n8l0n1Pseaj1xr5Ek7tItKdWLZ9ntQqsXkRuVy6JqtRRTnD6j4nrqqeSm1SiRd2K/oeSQsTzUaeZN\nvYcQxZXk+mz1mkPpqXe9Lqr77M9/fuh1ltfdyh8zG6XTv8u41UpKDj1ASSEf9D001upOPKpJcHmL\nuFan2+lqpUbS7qusE/Mqp+SQsW5urVQkzX4Peeo+I80+nJLQiWqlpBogVPrAB1qfRyvizkPXHHpA\n6aaXPDazlUDUD/bRR6uH5eUu31tuiR4+OAjnnNP6dFvdOebxmkMtld9hM8/DTqszwdtvT2dejcTq\nW0nS8w//EPyfODHbOHrd66/XfjZI1A9x7tx042lG5Q6t9CyLSuXPgGhFqflkszduxkkO5d13tyOq\nCfTChdUJqFZM9RJ8o+R//PG1n+Nw223B40vjKp9XVEtGJQeRFkUd2dczfnztz+I+r7zd7jZKduyA\nXXaJX77T10tK3U2UdmBRN5KVS+vMoXy6P/1p8H/JkuiySXe5XUvUI0ZPPx2uuy7ew7Q2bIAPfahx\nOV1zEMmBuPcr/OVfJjO/kW0esrVyVAzDj3rrla2cfvkjSZuJpySJaqXS3dH//d/pzaOVPqMgSAxx\nY5g0Kfru98rqwHpdrSRFyUG6zgsvZB1B+x5/vPVxa+3EGj28Ku56a7b59e9+V7+7+1Z33I89Bu96\n1/BhtarOomKNumek3etG9e7sj4ph+fLgLvxyL79cXbay6/Rvfau1+JqhaiXpOn19WUfQvoMPjl+2\nsgqt1TOHqVPjza80/fJHd9bzp38ar1zJXnvFK1e6Ez2ODRuGv9+5E844o7pcvZ4K4qzXv/iL4Z/d\ndNPweVZOr1SFNGvW0PBOPIEyjpyEIZKcXr/5rHJHWNKoKiJutxdnpvwsxzTO/Cq7ob/xxuizmfPO\nqz2N++5rfr7l3cBUJod/+7eh15XPDmml192kKTmISFPiPJO7k045pbXxSl2yx/Vf/9XafEoqk0N5\nIipvEPGZz8CcOY2nl3aLOfOc3BpqZg75iEVEJGkLFsCECUlP1XD3VO6wiXXmYGYTzGyVma02s8ia\nSTObbmZrzGyZmY1tZlwRkW6XfGJIV8PkYGYjgBnAicCRwGlmdlhFmYnAQe5+CDAZuDzuuBJlIOsA\ncmIg6wByZCDrAHJkIOsAekKcM4dxwBp3X+/u24E5QOUD7CYBVwO4+yJglJntHXNcqTKQdQA5MZB1\nADkykHUAOTKQdQA9IU5yGA2UP8TwyXBYnDJxxhURkZxJq7VSIhdIfvKT+GUPPHD4+z33DJqKzZ49\nNOyzn20+hqOOglGjYJ99mh93dBekwSOPzDoCEclCw9ZKZjYe6Hf3CeH78wF394vKylwO3O3uN4Tv\nVwGfAN7XaNyyaaipkohIk9JqrRTnDunFwMFmtj/wFHAqcFpFmXnA2cANYTLZ6u6bzezZGOMC6S2g\niIg0r2FycPcdZjYFWEhQDTXb3Vea2eTgY5/l7vPN7CQzWwu8DJxZb9zUlkZERBKRm5vgREQkPzLv\nPqMXbpIzszFmdpeZrTCzh83s3HD4281soZk9Zma3m9mosnEuCG8qXGlmny4bfrSZLQ/X16VZLE+7\nzGyEmS0xs3nh+15dD6PM7Mfhsq0ws2N7eF18xcweCZfjWjPbtZfWhZnNNrPNZra8bFhiyx+uzznh\nOL8ys/0aBuXumf0RJKe1wP7Am4BlwGFZxpTScr4HGBu+3gN4DDgMuAg4Lxw+Ffh2+PoIYClBtd8B\n4ToqneUtAj4avp4PnJj18rWwPr4C/BcwL3zfq+vhP4Ezw9cjgVG9uC6A9wLrgF3D9zcAn++ldQF8\nDBgLLC8bltjyA18Cvh++/nNgTqOYsj5z6Imb5Nz9aXdfFr5+CVgJjCFY1qvCYlcB/yd8fQrBl/e6\nuz8BrAHGmdl7gLe5++Kw3NVl4xSCmY0BTgJ+WDa4F9fDnsDH3f1KgHAZX6AH10VoF+CtZjYS2A0Y\npIfWhbvfCzxfMTjJ5S+f1lzghEYxZZ0ceu4mOTM7gOAI4X5gb3ffDEECAd4dFqtcL4MM3VT4ZNnw\nIq6v7wJfY3gvi724Ht4HPGtmV4ZVbLPMbHd6cF24+ybgO8AGguV6wd3vpAfXRYV3J7j8b4zj7juA\nrWb2jnozzzo59BQz24Mga385PIOobA3Q1a0DzOwzwObwLKpe0+WuXg+hkcDRwH+4+9EErfzOp8e2\nCQAz24vgyHZ/giqmt5rZ6fTgumggyeVveOtA1slhECi/MDImHNZ1wtPlucA17n5LOHizBX1QEZ4S\nPhMOHwT2LRu9tF5qDS+K44FTzGwdcD3wKTO7Bni6x9YDBEd1G939gfD9fxMki17bJgD+CFjn7s+F\nR7U3AX9Ab66Lckku/xufmdkuwJ7uXvbU8GpZJ4c3brAzs10JbpKbl3FMafkR8Ki7X1Y2bB7w/8LX\nnwduKRt+atjC4H3AwcCvw1PLF8xsnJkZcEbZOLnn7l939/3c/UCC7/oud/9L4FZ6aD0AhNUFG83s\n/eGgE4AV9Ng2EdoAjDezt4TLcALwKL23LozhR/RJLv+8cBoAfwbc1TCaHFyln0DQemcNcH7W8aS0\njMcDOwhaYy0FloTL/Q7gznD5FwJ7lY1zAUErhJXAp8uGHwM8HK6vy7JetjbWyScYaq3Uk+sB+BDB\nAdIy4CcErZV6dV1cGC7XcoILp2/qpXUBXAdsAl4lSJZnAm9PavmBNwM3hsPvBw5oFJNughMRkSpZ\nVyuJiEgOKTmIiEgVJQcREami5CAiIlWUHEREpIqSg4iIVFFyEBGRKkoOIiJS5f8DG6+TryGFPcsA\nAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1cdec02f780>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(deltas)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "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": 22,
   "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": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n 0.48| 0.72| 1.00| 0.00|\n---------------------------\n 0.28| 0.00| 0.70| 0.00|\n---------------------------\n 0.09| 0.11| 0.37| 0.12|\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
}