func_approx_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",
    "# Function approximation using Q Learning\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\n",
    "SA2IDX = {}\n",
    "IDX = 0"
   ]
  },
  {
   "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": [],
   "source": [
    "class Model:\n",
    "  def __init__(self):\n",
    "    self.theta = np.random.randn(25) / np.sqrt(25)\n",
    "    # if we use SA2IDX, a one-hot encoding for every (s,a) pair\n",
    "    # in reality we wouldn't want to do this b/c we have just\n",
    "    # as many params as before\n",
    "    # print \"D:\", IDX\n",
    "    # self.theta = np.random.randn(IDX) / np.sqrt(IDX)\n",
    "\n",
    "  def sa2x(self, s, a):\n",
    "    # NOTE: using just (r, c, r*c, u, d, l, r, 1) is not expressive enough\n",
    "    return np.array([\n",
    "      s[0] - 1              if a == 'U' else 0,\n",
    "      s[1] - 1.5            if a == 'U' else 0,\n",
    "      (s[0]*s[1] - 3)/3     if a == 'U' else 0,\n",
    "      (s[0]*s[0] - 2)/2     if a == 'U' else 0,\n",
    "      (s[1]*s[1] - 4.5)/4.5 if a == 'U' else 0,\n",
    "      1                     if a == 'U' else 0,\n",
    "      s[0] - 1              if a == 'D' else 0,\n",
    "      s[1] - 1.5            if a == 'D' else 0,\n",
    "      (s[0]*s[1] - 3)/3     if a == 'D' else 0,\n",
    "      (s[0]*s[0] - 2)/2     if a == 'D' else 0,\n",
    "      (s[1]*s[1] - 4.5)/4.5 if a == 'D' else 0,\n",
    "      1                     if a == 'D' else 0,\n",
    "      s[0] - 1              if a == 'L' else 0,\n",
    "      s[1] - 1.5            if a == 'L' else 0,\n",
    "      (s[0]*s[1] - 3)/3     if a == 'L' else 0,\n",
    "      (s[0]*s[0] - 2)/2     if a == 'L' else 0,\n",
    "      (s[1]*s[1] - 4.5)/4.5 if a == 'L' else 0,\n",
    "      1                     if a == 'L' else 0,\n",
    "      s[0] - 1              if a == 'R' else 0,\n",
    "      s[1] - 1.5            if a == 'R' else 0,\n",
    "      (s[0]*s[1] - 3)/3     if a == 'R' else 0,\n",
    "      (s[0]*s[0] - 2)/2     if a == 'R' else 0,\n",
    "      (s[1]*s[1] - 4.5)/4.5 if a == 'R' else 0,\n",
    "      1                     if a == 'R' else 0,\n",
    "      1\n",
    "    ])\n",
    "    # if we use SA2IDX, a one-hot encoding for every (s,a) pair\n",
    "    # in reality we wouldn't want to do this b/c we have just\n",
    "    # as many params as before\n",
    "    # x = np.zeros(len(self.theta))\n",
    "    # idx = SA2IDX[s][a]\n",
    "    # x[idx] = 1\n",
    "    # return x\n",
    "\n",
    "  def predict(self, s, a):\n",
    "    x = self.sa2x(s, a)\n",
    "    return self.theta.dot(x)\n",
    "\n",
    "  def grad(self, s, a):\n",
    "    return self.sa2x(s, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getQs(model, s):\n",
    "  # we need Q(s,a) to choose an action\n",
    "  # i.e. a = argmax[a]{ Q(s,a) }\n",
    "  Qs = {}\n",
    "  for a in ALL_POSSIBLE_ACTIONS:\n",
    "    q_sa = model.predict(s, a)\n",
    "    Qs[a] = q_sa\n",
    "  return Qs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): {'D': 1, 'U': 0, 'L': 2, 'R': 3}, (1, 2): {'D': 5, 'U': 4, 'L': 6, 'R': 7}, (0, 0): {'D': 9, 'U': 8, 'L': 10, 'R': 11}, (2, 3): {'D': 25, 'U': 24, 'L': 26, 'R': 27}, (2, 0): {'D': 21, 'U': 20, 'L': 22, 'R': 23}, (1, 3): {'D': 13, 'U': 12, 'L': 14, 'R': 15}, (1, 0): {'D': 33, 'U': 32, 'L': 34, 'R': 35}, (2, 2): {'D': 29, 'U': 28, 'L': 30, 'R': 31}, (0, 3): {'D': 41, 'U': 40, 'L': 42, 'R': 43}, (0, 2): {'D': 37, 'U': 36, 'L': 38, 'R': 39}, (2, 1): {'D': 17, 'U': 16, 'L': 18, 'R': 19}}\n"
     ]
    }
   ],
   "source": [
    "# no policy initialization, policy is derived from most recent Q\n",
    "# enumerate all (s,a) pairs, each will have its own weight in our \"dumb\" model\n",
    "# essentially each weight will be a measure of Q(s,a) itself\n",
    "states = grid.all_states()\n",
    "for s in states:\n",
    "  SA2IDX[s] = {}\n",
    "  for a in ALL_POSSIBLE_ACTIONS:\n",
    "    SA2IDX[s][a] = IDX\n",
    "    IDX += 1\n",
    "\n",
    "print(SA2IDX)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialize model\n",
    "model = Model()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 0\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 1000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 2000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 3000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 4000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 5000"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\niteration: 6000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 7000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 8000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 9000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 10000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 11000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 12000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 13000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 14000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 15000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 16000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 17000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 18000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration: 19000\n"
     ]
    }
   ],
   "source": [
    "# repeat until convergence\n",
    "t = 1.0\n",
    "t2 = 1.0\n",
    "deltas = []\n",
    "for it in range(20000):\n",
    "  if it % 100 == 0:\n",
    "    t += 0.01\n",
    "    t2 += 0.01\n",
    "  if it % 1000 == 0:\n",
    "    print(\"iteration:\", it)\n",
    "  alpha = ALPHA / t2\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",
    "  # get Q(s) so we can choose the first action\n",
    "  Qs = getQs(model, 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(Qs)[0]\n",
    "  a = random_action(a, eps=0.5/t) # epsilon-greedy\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",
    "    old_theta = model.theta.copy()\n",
    "    if grid.is_terminal(s2):\n",
    "      model.theta += alpha*(r - model.predict(s, a))*model.grad(s, a)\n",
    "    else:\n",
    "      # not terminal\n",
    "      Qs2 = getQs(model, s2)\n",
    "      a2, maxQs2a2 = max_dict(Qs2)\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",
    "      model.theta += alpha*(r + GAMMA*maxQs2a2 - model.predict(s, a))*model.grad(s, a)\n",
    "      \n",
    "      # next state becomes current state\n",
    "      s = s2\n",
    "      a = a2\n",
    "\n",
    "    biggest_change = max(biggest_change, np.abs(model.theta - old_theta).sum())\n",
    "  deltas.append(biggest_change)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xm0FOWdN/DvTw3BJTEaj+a4AK7wuscomhOXJnHBJeIy\nmahJUByMvol5zcRENDkOl4mZOE406hAjKKPEkQHiFoyoqLFjdBCJoiyCoChXVgUFRcELl9/7x9Nl\nV9et6lq61q7v55w+t7u66qmn63Y/v6pnK1FVEBFROW2VdQaIiCg7DAJERCXGIEBEVGIMAkREJcYg\nQERUYgwCREQl5hsERGSciKwSkdk+6x0lIptE5Jz4skdEREkKciVwF4BTmq0gIlsBuB7A43FkioiI\n0uEbBFT1WQDv+6z2IwD3AXgnjkwREVE6Wm4TEJHdAZylqr8HIK1niYiI0hJHw/DNAEbYXjMQEBEV\nxDYxpHEkgIkiIgB2AXCqiGxS1SnOFUWEExUREUWgqomcYAe9EhB4nOGr6j61x94w7QI/cAsAtvX5\niOkxcuTIzPPQTg8eTx7LvD6S5HslICITAFQAfFFEOgGMBNDLlOc61rE6z/SJiArENwio6gVBE1PV\ni1vLDhERpakwI4a7uoD3/TqqlkylUsk6C22FxzM+PJbFIUnXNzXsTESj7u9HPwJGjwZSzC4RUS6I\nCDTjhuHMvfVW1jkgImo/hQkCREQUPwYBIqISYxAgIioxBgEiohJjECAiKjEGASKiEmMQICIqMQYB\nIqISYxAgIioxBgEiohJjECAiKjEGASKiEmMQICIqMQYBIqISYxAgIioxBgEiohIrTBCQRO6pQ0RU\nboUJAkREFD8GASKiEmMQICIqMd8gICLjRGSViMz2eP8CEXml9nhWRA6JP5tERJSEIFcCdwE4pcn7\niwEcr6qHAbgOwB1xZIyIiJK3jd8KqvqsiPRt8v7ztpfPA9gjjowREVHy4m4TGA7g0ZjTJCKihPhe\nCQQlIoMADANwbLP1Ojo6Pn1eqVRQqVRc15s3D9h6a2DAgLhySERUDNVqFdVqNZV9iar6r2Sqgx5W\n1UM93j8UwP0ABqvqG03S0SD7M+sCn/0ssHGjeX3mmcDDDwMBNyciahsiAlVNZMhs0OogqT16viHS\nByYAfK9ZAIiCo4SJiJLlWx0kIhMAVAB8UUQ6AYwE0AuAqupYANcC2BnAbSIiADap6sDkskxERHEJ\n0jvoAp/3LwFwSWw5IiKi1HDEMBFRiTEIEBGVGIMAEVGJMQgQEZVYroOAvYsou4sSEcUv10GAiIiS\nxSBARFRiDAJERCXGIEBEVGIMAkREJcYgQERUYrkOAvZuoZxCmogofrkOAkRElCwGASKiEmMQICIq\nMQYBIqISYxAgIioxBgEiohLLdRDgzKFERMnKdRAgIqJkMQgQEZUYgwARUYkVJgiwfYCIKH6+QUBE\nxonIKhGZ3WSdW0VkkYi8LCKHx5tFIiJKSpArgbsAnOL1poicCmBfVd0fwKUAbo8pb0RElDDfIKCq\nzwJ4v8kqQwD8obbuDAA7ishucWSOVUBERMmKo01gDwBv214vqy3zdMQRwIYNMeyZiIhask3aO+zo\n6MCsWcDPfw4MGVJBpVJJOwtERLlWrVZRrVZT2ZdogLu1iEhfAA+r6qEu790O4GlVnVR7vQDACaq6\nymVdVVWIAJ2dwF57Ndun+XvppcDttwNDhgBTpvDmMkRUPiICVU2kgjxodZDUHm6mABgKACJyDIC1\nbgEgqjFj4kqJiIicfKuDRGQCgAqAL4pIJ4CRAHoBUFUdq6pTReQ0EXkdwEcAhiWZYSIiio9vEFDV\nCwKsc3nYHZ9/PnDCCcCvfhV2SyIiiktmI4afew64++6s9k5ERECBpo0gIqL4MQgQEZUYgwARUYkx\nCBARlRiDABFRiWUaBDj6l4goW4W5EmhlRtGPPwYWL44vL0RE7aIwQaAV11wD7Ltv1rkgIsqfUgSB\ntWuzzgERUT6VIggQEZG73ASBzZuByZOzzgURUbnkpnfQjBnAt7+dXV6IiMooN1cCRESUPgYBIqIS\nYxAgIioxBgEiohLLTRBoNoXEunXp5YOIqExy0zuomauvTjYfRERllZsrgWa6urLOARFReypEEGhV\nK5PPERG1s1IEASIicpebIODXPsB7DxARxS9QEBCRwSKyQEQWisgIl/c/LyJTRORlEZkjIhfFmUkG\nACKiZPgGARHZCsBoAKcAOAjA+SIywLHaDwHMU9XDAQwCcKOIbBNnRlmvT0QUvyBXAgMBLFLVJaq6\nCcBEAEMc6yiAz9Wefw7AGlXd7Jcwz/CJiLIVJAjsAeBt2+ultWV2owEcKCLLAbwC4Ip4skdEREmK\nq8rmFACzVPXrIrIvgCdE5FBVXe9csaOj49PnXV0VAJWYskBE1B6q1Sqq1Woq+woSBJYB6GN7vWdt\nmd0wAL8GAFV9Q0TeBDAAwN+diXV0dGDUKPO8V6/68mZVQ3msNho7FnjoIWDq1KxzQkTtplKpoFKp\nfPp6lFVoJiBIddBMAPuJSF8R6QXgPABTHOssAXAiAIjIbgAOALA4zozmzf/8D/Doo1nngoioNb5X\nAqraLSKXA5gGEzTGqep8EbnUvK1jAVwH4G4RmV3b7CpVfS+xXIfEnkVERO4CtQmo6mMA+juWjbE9\nXwHTLhBKHqt5iIjKJDcjhomIKH2ZBoH164H5883zNK4KFi7k1QcRkV2mQWDDBuDAA/3Xa7Xgtrbv\n3x+YNq21tMLo7AS6u9PbHxFRWKWrDvr443jSCdLY3LcvcNdd8eyPiCgJuQgCL74IbPadZKKY3n8/\n6xwQEXnLRRA48kjT756IiNKViyAA+N9Cct489+Vz53IcQBa6uoCURrUTUYJyEwSaUQVWrnR/zys4\nULImTAAGDco6F0TUqkIEgTzK+upDBJgzx/v9t94CVq9Obv/s9UTUHgoTBJyF7ptvAh98EKwwzrrA\nTkpnp/d7e+8NnHlmenkhomIqTBBw2mcfYNiwrHORb+vWZZ0DIsq7wgYBAFi7NusclFe7Xl0RlU1u\ngoDfqGCvQqeVwmjCBMB2jxsiotIpRBBIar6fUaOABO/VAIBzFRFRvuUmCEShml21RB6qQ/wCDAMQ\nEfkpdBCg7OQhCBJR6woTBJJoEyAiKrvcBIEsqi4YQIio7HITBKJiQe4tycDK407UHnITBKIUWFk2\nfLIQJKJ2kJsgkKQ4C+yNG4EtW+JLj4goS4UJAmk2DC9Z4j1B2rbbAiNH5qP7ZR7yQETFVpggkASv\nANKvHzB2rPd2CxYE30e7FtSsDiNqD4GCgIgMFpEFIrJQREZ4rFMRkVkiMldEng6bkagjhpMqjFqZ\nl+jee9O5raTfZ2/XAERE8dnGbwUR2QrAaADfALAcwEwR+ZOqLrCtsyOA3wE4WVWXicguSWXYLq+F\n3He/C9x0U9a5ICLyF+RKYCCARaq6RFU3AZgIYIhjnQsA3K+qywBAVWO/nUmeBotFna5i7VrgmWfi\nz08WWB1E1B6CBIE9ALxte720tszuAAA7i8jTIjJTRL4XVwaT1KwgC1PIzZkDvP66/3qjRgEnnBA8\nXSKipPlWB4VI5wgAXwewPYDpIjJdVXsUjR0NczdXao/oU0nnwaGHArvuCqxa1Xy9uLuW5rU6jIha\nU61WUa1WU9lXkCCwDEAf2+s9a8vslgJYraobAWwUkWcAHAbANQi4Td9c5gJtxQqgd29gp53iTbfM\nx5SoyCqVCiqVyqevRyU4532Q6qCZAPYTkb4i0gvAeQCmONb5E4BjRWRrEdkOwNEA5seVSa/CLGgh\nF3dhGHd6u+8OnHxyvGkmLc9XZkQUnO+VgKp2i8jlAKbBBI1xqjpfRC41b+tYVV0gIo8DmA2gG8BY\nVX01zozG1TBsX7+VNoG4C8F33ok3PSKiIAK1CajqYwD6O5aNcbz+DYDfxJe1+NgL7LSrSHjGTER5\nlpsRw1ELy7wXsu1aL5/3405EweQmCPjJU2EaJC9x5LfV3kReeejfH7jjjtbSJqL2kJsg4DdthNf7\nrZyRxjVOIAnTpwNbb918naiBZuFC4Mkno21LRO0l9SDQbGK2ZrIulJPmLNA7O7PJRys++YTTbBMV\nTepB4NJL095jMto9KEXRuzfws59lnQsiCiM31UFRtdJFNM50s5B2N9Yg5s5Nf59EFF2hg0Crt6SM\nWkhGrYtPu1BOozH9zjuBTZuS3w8RJSM3QSDq3EGtFKx56nFUNNZxv+SSYGf/qsCzzyabJyIKLzdB\noBkW1u6SPi4zZ4bfxitP8+YBxx3XWn6IKH65CQJ5q2Lx6z4a936dnz8PbRIDBwKbN8eTltc9m6N6\n7jlg6tR40yQqo7imks61KAVq1NtdOtcp+lVMkGOXxWc85xwz31LRjy9R1nJzJeDHrTBqtQDIw9l2\nkpIsIL2OHQtlomLJTRBIq2E4qYK/6IXf0KHAypU9l8f1udo94BIVVW6CQDNxFrBB0ypboXXPPcBf\n/5p1LogobYUIAs1kdaP5sstyem7n/okousIHgVYkWZC0mnZeG2T95DFPROStMEHAq2E4iy6iSUii\n8IwjTbYJELW33ASBop9BspCLn4hpqyCi5BQiCOStgC16wIpDWm0CL73kv38iii43QaAZeyHT6nz1\nQW8036q8B4qk8pfEzX/I22GHcQI/ak0hgoDd979ff97qLKLNxDVN80MPxbO/uLYJK+tglvX+8272\nbGD9evN8xYrw20+dCpx+erx5omIpTBCwCrwXX3RfHmTbLMyYkVzafgVk2AI0zPpZn9kntf9Ro4BK\nJZm0k7b77sDy5eG2+eMfOQdT2RVu7qA8nBnmtSdPVuK4R0NePPCAObsuEvvx/+ST7PJBxRToSkBE\nBovIAhFZKCIjmqx3lIhsEpFzwmYkSiHY6myeRS+wWpH29Blp38CHiILxDQIishWA0QBOAXAQgPNF\nZIDHetcDeDxKRoLO2ml//tprwEkntZa2lzIHCDsWwsUS9v/F7zkFuRIYCGCRqi5R1U0AJgIY4rLe\njwDcB+CdGPPX1OrVae2pp7L/eLL+/O0ySJAoa0GCwB4A3ra9Xlpb9ikR2R3AWar6ewCRfkZp3TS9\nTD/ytM7ig+ynTMc9bXH+n2fMAJ56Kr70KP/iahi+GYC9raDJT77D9rxSewTvStnqF96vEdPqZtes\n0CpTFUmSPYyySK/dtXq8zjjDXGG7pXP88cAxxwA33NDaPshftVpFtVpNZV9BgsAyAH1sr/esLbM7\nEsBEEREAuwA4VUQ2qeqUnsl1RMpoGpYuBfbaK5t9R7m9ZNwFZJiz9bCD7rLMax7Szaswn/dvfwPe\nfZdBIA2VSgUVW1/lUaNGJbavIEFgJoD9RKQvgBUAzgNwvn0FVd3Hei4idwF42D0ARGMvQObMAd56\nK66UG23YEGy9qIVe3guYIp11FymvSeOxoFb4BgFV7RaRywFMg2lDGKeq80XkUvO2jnVukkA+GwrQ\nRx5JYg+tFdJ5/CHGkaewAY9dRLOV9C1X+f9oP4HaBFT1MQD9HcvGeKx7cQz56iGNs+ig+0hyCuu8\nKduPviz/V0tWn3fdOmDHHbPZNzXK3bQR774bf5pB709ctgKgyPi/qitioP7CF3pOAUPZyF0Q+MlP\nei6bPLnxR9/KrInNCo92K1jS+jxJFkJFLOCKLM3fwHvvpbcv8pa7IOBl48b683/+52T2kacgkKe8\nhFH0qaSLks+4hP28DMrtJ3cTyHl9Kdesab7dww8D779v+jEfcID3ekFvXrNmDfDxx8B224VLI6q8\nppnXQj3r/edJUQvmoua73eTuSmDSpGhfjhtuAC680EwFHJW9YLnuOpNekHWJ2gW/1+WTuyDQ1QWM\nHx9+u2efDbaevT3BeZcy5w9g6dLw+fBKK2/cAm3UM7N2mjaiKPn0kvTZdZzp80ogH3IXBABg8eLo\n265fD3z0kff7v/qV+btyJfDKK/Xlr78OvPlm47rOL+nHH3un6yw8+AUvpiL+34oeuChbuQwCs2ZF\n33bKFNMuAJhg4uxJZHVBXbeucfn++wMnnNA83e23N89VexYW79TmTh082Py1N2QXGdsE8q+IgYvy\nI5dBYPPm1rafO9f83Xdf4JZb3NexFyLz57uvY/9xvf22+zpOj9fupnDttcHW9xJHIdcOhUPan6Ho\nwaVI9xNoh+9nO8hd76C4rV3b+Nrtixf2rP3VV5ObvyiMvPyI2qlNgJrLy3eO4tP2QcD5pbVeB5kF\n84UXgHHjzD1n7d1OwwaAG280VVOdneG2S5vbcQhbHZRWIcGgUhfnMedxLZ+2DwLz5wM771x/HSYI\nAMBNN5kz/9Gjo+fh5ptNT6NttzWvN28GtvE58kkXpkX5sbM6KJwifW94VZEPuWwTiNODDzbesCbq\nFM+/+EV8efrpT4ElS4JPXd0Oil64tiuOGKa2DwKA+xwlQa8ErPecvYnCsNKw/t5yC9CvnwkGFmfb\nRRzSuisYC4ZsFbU6iN+bfChFEHCThzNTe3DasKE+4G3evHr+9t3XtE1E0dnZc0BcWFm3CaTdRTUP\n34tWsGClsEoRBPxuepL0zKJB0zjuOPP34IPrA9cWLwaOPto8f+QRYMKE5mls3Ggasi3vvx8ur1Qu\nWVYHFT3gtotSBAE3Ye+Rmza36bKHDgW+8x3grru8t/vtb4HDDqu/njSp/tyrSmvhwmh5tAQ5fnk8\nxu2iqAUzr1ryoe17BzllMZgm7h/WxU3u3eac2uKHPzRTaXzpS2ZCvEcf7bmN20hpv+Nk/0xBbi/J\n9gaifGIQQHpnP2HuZBa18HNLc8QIYPfdzfNVq/zTWLIEeOONej7+9Cdg112Br341Wp6KpGxXLGX7\nvNRT6YKAJc3qIGfvIEuzgj6pM+AgQXD4cODJJ+uvzzoL2GcfExjGjDH3hrXGPFC5cBbR9lO6NoGw\ng8Xi1Op+kppP6MMPg2932WWmiskvL1u25L/dpV2wMKVWlC4IWIIWSnlqE0jr6qCVHiPW8zB5/eUv\nTbfYoLq7W+/66qXowYoTyFFYpQ0Cdnn84Qf5gURp32i2TbMbzUQNFA884L/Ov/wLcPvt7u+tXm3+\n3n03MGyYeX7iicFndaVwonx/qNgCBQERGSwiC0RkoYiMcHn/AhF5pfZ4VkQOiT+r8Qo7YjjpPKTN\n/mMO0mAdNghY70+bFmx9L93d5u+YMSYQAI13kVu5kgGBqBW+QUBEtgIwGsApAA4CcL6IDHCsthjA\n8ap6GIDrANwRd0bjkqc2gSQu3aOcyW3V4vWgW0AJWy3k17XU6/1jjwX69DEN13ZvvGFmgC2bIp2p\nFymv7SzIz38ggEWqukRVNwGYCGCIfQVVfV5VraFIzwPYI95sxidsXXJWbQJp9g6ygkCzK4CgVwJe\nU3dH5VflZY2IfvNN065gVRldf73p5ZSk7u72uYOcJY9Vo5SsIEFgDwD2C+6laF7IDwfgMiQpX/LQ\ncyUvP7gg+YhamAcNulGvBOx5v+++epVR0Pw2u2+0nyuuyEdXWZ5RUytiHScgIoMADANwrPdaHbbn\nldojPR98YGbsTLNNIM3CPsq+wgxiC7sft+q3MPyuBLzSXbzY/J05EzjqKO/0t9/eTMNx0UXN03Pz\nt78FXzctRQoIRcpr2qrVKqrVair7ChIElgHoY3u9Z21ZAxE5FMBYAINVtcm0ZR2hMpiEE080N47P\ns6i9g6IIW0A7J6UL06soLLd0vPJrX25dgVx9NfDUU833MWwYMGAAcMwx4fJmvxe2CDB9OrDffmai\nvwsvDJdWVqKcAFDyKpUKKpXKp69HjRqV2L6CVAfNBLCfiPQVkV4AzgPQUISKSB8A9wP4nqq+EX82\n47ViRePrrEYMZyFIt1K3eYGCzA/k9l5S/fktcR1Tt3tO+HE2qL/8MnDHHfWrimZWrTJ5v/NOMy1H\nK9I8o+bZe/vxvRJQ1W4RuRzANJigMU5V54vIpeZtHQvgWgA7A7hNRATAJlUdmGTGW7F+fT7aBJqJ\n++btzda1CrMwP/Cwx6zVYxykTcBtH0lWW7XymVauNH8vuaRx/4CZCryrCzjyyPrrJ54wV7D2GWKT\nkMffAiUrUJuAqj4GoL9j2Rjb80sAXBJXpoJMY9CKDz5ofN3si99Kw6Ez/TA/sKgT3bUyWKxZGqr1\nevagefHaX5j1wsxm2koQiMJ5JaAaz0j0r37VfO+GDgXGjweuvbZefblokaly6ury/m52dZn0P/OZ\n1vJB5ZDLEcPPPZf8PoJeCSRdnRFGHJfizcZJ+KW/fn34fCVxZ7MkztajHFu3cR9xBAErL243ENp/\nfzNY7sc/BnbaqXF9y1e+Ahx4YH0m2DhxArn2k8sgkIagP9ZFi9LbVxyC9t8Puk7UcQLW36S7iPpJ\nsjqolSuBMJxpvvde/c5zTqrA3LnA66+bKwYAOOkkYM0a83yXXZIJDlRcDAIAvv/96Om88krreUlT\n2LmDvLZLu4uoV++gPE3OF1ebStztQU8+CcyZY56vWWOCw6JFZkqP3/2uvt68edEayJ1GjQrWffas\ns4BZs8zzl19uv4F3RVHaIGBnzW8TRZieHWG647kVBNbZXLN1gu47ar7CSvqS3ysgtBp8wu672bKg\n2wYV5YrD+X844ADglFMalx18sHeVXxgdHcBvfhNs3eefN3+//GVza9RmLroIOP54M49UGOvXs+qp\nmbYNAo89lnUO/M2cCbzzTuOyTz4xf5Oq/oh6I5ukp42I4/OmPbCvlf2FGaXt1/aQly6iXV31IBL0\n2Nir1PyuBO67z1xhXHZZ8/tsO33uc8BPftJ8ncsuAxYsaL5OdzewYUPw/RZF2waBU09NZz/2H8VD\nD7mv4/WDWLSo3kXQctttreXn2mujb+tW6NirY7yqZNzq/ZMcLBZGkg3DSbUJtFIdFLWXVRz+6Z/M\nXefCiHq8rrkm3Po339w4uM9pzBhg8mT/fW63XfB9ioSfvmThwvQDTdsGgSz853+G38b5xdy0KZ68\n+Jk8ud7ovaw2/juJgiLpCeTiHicQRtK9g6Jun5XXXkt2gsagAxaDbB/F/PnJ7PPtt830JQDQv79p\nU7H75jfD7zeM0gaBJAq8INMZOFnz5TvXTWMW0S9/Ofq2Qasj0mwTaEVcvYOCaqXaKe6ZWuNiPx5J\nB6ksgkCUzxRkn+vWNb52jmP685/D7zeM0gaBuASZ06bZ+84zJ2sdZyNwEj76CHj11frrMF1Eg56V\n+Z0ZLlnin4bz/SDtAGEL9bSvBJLaT5bVQVE+e5h7WWR9JZBUEHBKe2wSg0CL7KOb/a4EwgSBIN3l\n4vghHHRQz/fc8vnOO8DUqfXX9nsCq/a8R7AzeLil+d57QL9+4fIb9C5iSfUOshru7WmHOREIsl7Y\n6qC8VA1FuRKImvcoBWWaQSBMW1bWV3YMAi266abWtvcKAln8sP2+fL/4Rf35j3/cuN3BB4dPs08f\n7/ec21t/+/TxDpBux+yRR/z3EdTcuUDv3qYHzEcf9Xw/rjaBsKIOBIxblM+U5vc8zNWmm6SuBLIO\nArHeT6BIHnww/jSjtAkE/Yf/x3+Ez0/Y/SVx9tzsjM1ekIapxrC3o8R1Rhzk/2B15z38cNPt0GrM\ni/tH69cdN45xAlE1Syfpq5Osq4OiyEuAbqa0VwIdHfGn6dV7wKp3d6vndxaSXV3uaVx1Vc9lDz8c\nPG8WtzPYZsJ+if3Wd46LaFVchc0//IP/OtZne+MN8z9durRxuWrwwVZhOgs4LVrk3R3ZSxr3z4hy\nr+qojclJBIEkrgSyqLYKq7RBYNWq+NMMWl9t5ywUw3zR/G6WYmd1A23W4Gx9+eyzhQaZRbVZg7JV\n+FifK+robK8fhtvZ57vvRtuHM71murp6Nmqreo/TuOGGxgDvtZ+JExs/6/DhwEsvNa4ze3bj6yCF\nht/gyThny01qmyJdCbTSJsCG4ZJxjlK0xg3ce6//tsts93fr08fMLumnWbWS1TXN3sj7wgv+afqN\n3rzoIjOhGRD+Cx5lsNiVV/Zc9uKL5ux57lxgjyZ3yF64sP5840bgL3/pmZcoRowI1s/8f/+38fW4\ncT0ni2t2xu2VR7+ri2ajZb2q7VTNuJYPPwROP70xXw8+aIKVaj1Yxsn+PVq6NHhhO326ufFPUPYr\nu6R7BzmvLNPCIJAz1plk0Mm0REyPlbffBo47rrV9//KXPZcF+UJOnNj8/fHj61VXYb/g1vr2Xjl2\nblcC99zT86rs3HOBs88GDjkEWL7cPa0//7nxCnHbbYFvfMM/ELm939kJVKuNZ9hTp9YLr1Zme202\nbsA5H1DQdJ95xvu9HXZwn9590iSgVy8z6n3q1J5jR449FvjjH5v3AHObt8orWHp9hr32ap5/y5Yt\nplrVPmHkeeeZAO2W/pNPmrYfywMP+O/DSdV8p1avbr4OAPz3fze+vu66xpOSpDAI5EyUs4DevePZ\n97p1Pff/j/8YLo0ZM9xvCmT92P/+d/Nj/Ld/a3zf73N7/Ri8ClPnfZCDXIF4jcx84QVT0HhdabkF\ngTPPBAYNAk47rb7s5z8380U1y3eUIHDPPfXnXtWcfun6zZtjpfvhh/VjaY04t6rfnPn68EPg29+u\nP3czdGjPwVH26kgvzs/z4ovAd79rnp97LnDOOeZ+C7/+tfc2gAlk48e778N5G1ovImZOo1WrgG99\nqzFgqpp7QBx9tH861pWA5dprgbFjg+WhFaXtHUTu4rgU/fzne9ZbW0aPNmfX9u6mTrfeas4+AXM2\nbU03HIazYAn7uewF2lNPmR+oM3A507bvw1lQWqxqmTgnn/O6srHzC4J+M3Nan23dOuDGG4Gf/axn\nfppVUzWrjnIW+mecYRreX3nFBFNrvp5mbQJWFeD48Y1n7PbqtaQG8wFmbiJrv93dZrI7a58ffhis\nV55VFez2PUoSgwA1OPHEeNI59NDG1/Yqo7PP7rn+nXeaOeV32MEU/HZHHOG9H3sB4jz7t2sluFkB\nq9kEZE5ehY3fjzpKPpcvbxy3EWW/fuzbX3WVexCIWsC6feZvftP0who+3L0O3+s4Oefesuc7ybp2\n+1n8li08oacSAAAHWUlEQVQ9TwyC9JxyG3zIIECpe/rpZNK1bqzezN//3to+7Jf+dpMnu5+JWtUH\nrXKOlga854Cy8uF1dePV9mHnLFCCdBVW9W8cDquzszE/UbqIAu6Fs1X42b83QXoHWUHAmsHTuU1S\nVwL2nl9u+QzTmJ9W4LIwCFDbs+ql7eIsDL7yFfPXXrBbd5xbsQL4/e/ryysVM13Guec2prF5M7DN\nNqY3kMWr0A471gMwVwt33hl8/UceMT1+LNadySxXXtkzva239k4vSHWIndUjyj55WpAgYHUIcAsC\nXmfVVntHKwWuvZBvNQikfSUAVU3tAUDr/xo++OAj6cfFF0ffdtIk1X/91+Drf+1r3u+dfbbq2rWq\ny5erbtrkvs7Ike7Le/dWXbas5/JBg1RVG5ftsEPzPPbubf6qqm7Z4p6e5Z576uva9+Pktp/Nm83f\nNWvM3112Metu2KD6wQfmb3e3aqWiev/9Zp3LLjN/v/Odero/+IGVJjSxcjlg4T0YwAIACwGM8Fjn\nVgCLALwM4HAGAT744KNoD3sQ2XZb8/fjj1WHDq0vv+UW1SuuCJbevffWn1cqwfNhBY9dd7WWIbEg\nILXC2ZOIbFUr/L8BYDmAmQDOU9UFtnVOBXC5qp4uIkcDuEVVj3FJS4Hm+6MwqgAqGeehnVTB4xmX\nKngs4yRQ1URaNII05QwEsEhVl6jqJgATAQxxrDMEwB8AQFVnANhRRHZzS8ytF0Nck6Ml7ZNP/PtT\np6uadQbaTDXrDLSRatYZoICCBIE9ANjHXy6tLWu2zjKXdQAAv/2tGboNmEEUL70E/PSn7ju++25g\nn30aly1YADz/vHdmH33U+70g5s4FDjus5/KjjjKjI/v3by19IqI8yWTE8DHHmFquhQvrtzj84APT\nT3z1auDqq4GTTgIuvLA+5wxgRqP2729G33V1mV4W06ebwRjLl5vJ2AYPBv7613q3vQ0bzGi+t94C\nJkwA1q41/ZyHDzf7HDnS9ILo7ASGDTNB5/HHzfwyF19s0u/qapxDxz4j45VXArvsYga4AKZ3x5Yt\nJq/20aJf/7rJY79+wOWXA7vVrpPOOMN0Vbz//sZjdP317ldI9iupk08G+vb1Ps4DBtSf33gj8MQT\nje8PGuS9bRCHHNLa9hTdrbdmnQNqF0HaBI4B0KGqg2uvr4ZppPh32zq3A3haVSfVXi8AcIKqrnKk\nxQYBIqIIkmoTCDJOYCaA/USkL4AVAM4DcL5jnSkAfghgUi1orHUGACC5D0FERNH4BgFV7RaRywFM\ng6k+Gqeq80XkUvO2jlXVqSJymoi8DuAjAMOSzTYREcXBtzqIiIjaV2oNwyIyWEQWiMhCERmR1n6L\nRkTeEpFXRGSWiLxQW7aTiEwTkddE5HER2dG2/jUiskhE5ovIybblR4jI7NrxvjmLz5IFERknIqtE\nZLZtWWzHT0R6icjE2jbTRaRPep8uXR7HcqSILBWRl2qPwbb3eCybEJE9ReQvIjJPROaIyP+rLc/2\n+5nUKDTHSOGtALwOoC+Az8CMKh6Qxr6L9gCwGMBOjmX/DuCq2vMRAK6vPT8QwCyYar1+tWNsXd3N\nAHBU7flUAKdk/dlSOn7HAjgcwOwkjh+A/wvgttrzbwOYmPVnTvlYjgTwE5d1/w+Ppe/x/BJqsykA\n2AHAawAGZP39TOtKIMiAMzIEPa/QhgCwbn0xHsBZtednwvyTN6vqWzDTdgwUkS8B+Jyq1m5hgj/Y\ntmlrqvosAOek0nEeP3ta98GMpG9LHscSMN9RpyHgsWxKVVeq6su15+sBzAewJzL+fqYVBIIMOCND\nATwhIjNFZHht2W5a622lqisB7Fpb7jVIbw+YY2wp+/HeNcbj9+k2qtoNYK2I7Jxc1nPpchF5WUTu\ntFVd8FiGICL9YK6ynke8v+/Qx5S3l8yfr6nqEQBOA/BDETkOPSdcYmt+a+I8fmXr9nwbgH1U9XAA\nKwHcGGPapTiWIrIDzFn6FbUrgiR/377HNK0gsAyAvYFiz9oyclDVFbW/7wJ4CKYqbZU1F1PtUvCd\n2urLAOxl29w6rl7LyyrO4/fpeyKyNYDPq+p7yWU9X1T1Xa1VOAO4A+b7CfBYBiIi28AEgHtU9U+1\nxZl+P9MKAp8OOBORXjADzqb4bFM6IrJd7SwBIrI9gJMBzIE5VhfVVrsQgPXlmQLgvFqPgL0B7Afg\nhdol5ToRGSgiAmCobZsyEDSeAcV5/KbU0gCAbwH4S2KfIh8ajmWtkLKcA2Bu7TmPZTD/BeBVVb3F\ntizb72eKLeODYVrDFwG4OuuW+jw+AOwN03NqFkzhf3Vt+c4Anqwdv2kAvmDb5hqYXgPzAZxsW/6V\nWhqLYKb2zvzzpXQMJ8BMef4JgE6YgYs7xXX8AHwWwOTa8ucB9Mv6M6d8LP8AYHbte/oQTH02j2Ww\n4/k1AN223/hLtXIxtt93lGPKwWJERCXGhmEiohJjECAiKjEGASKiEmMQICIqMQYBIqISYxAgIiox\nBgEiohJjECAiKrH/D+bCToAkJzLSAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x23b0d957550>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(deltas)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# determine the policy from Q*\n",
    "# find V* from Q*\n",
    "policy = {}\n",
    "V = {}\n",
    "Q = {}\n",
    "for s in grid.actions.keys():\n",
    "  Qs = getQs(model, s)\n",
    "  Q[s] = Qs\n",
    "  a, max_q = max_dict(Qs)\n",
    "  policy[s] = a\n",
    "  V[s] = max_q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n 0.61| 0.79| 0.99| 0.00|\n---------------------------\n 0.45| 0.00| 0.64| 0.00|\n---------------------------\n 0.30| 0.14| 0.18| 0.41|\nfinal policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  U  |  U  |  U  |  U  |\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
}