monte_carlo_es_demo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Adapted from: https://github.com/lazyprogrammer/machine_learning_examples/tree/master/rl\n",
    "# the Monte Carlo Exploring-Starts method to find the optimal policy\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": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(grid, policy):\n",
    "  # returns a list of states and corresponding returns\n",
    "  # we have a deterministic policy\n",
    "  # we would never end up at certain states, but we still want to measure their value\n",
    "  # this is called the \"exploring starts\" method\n",
    "  start_states = list(grid.actions.keys())\n",
    "  start_idx = np.random.choice(len(start_states))\n",
    "  grid.set_state(start_states[start_idx])\n",
    "\n",
    "  s = grid.current_state()\n",
    "  a = np.random.choice(ALL_POSSIBLE_ACTIONS) # first action is uniformly random\n",
    "\n",
    "  # each triple 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",
    "  seen_states = set()\n",
    "  seen_states.add(grid.current_state())\n",
    "  num_steps = 0\n",
    "  while True:\n",
    "    r = grid.move(a)\n",
    "    num_steps += 1\n",
    "    s = grid.current_state()\n",
    "\n",
    "    if s in seen_states:\n",
    "      # we don't end up in an infinitely long episode\n",
    "      # bumping into the wall repeatedly\n",
    "      reward = -10. / num_steps\n",
    "      states_actions_rewards.append((s, None, reward))\n",
    "      break\n",
    "    elif grid.game_over():\n",
    "      states_actions_rewards.append((s, None, r))\n",
    "      break\n",
    "    else:\n",
    "      a = policy[s]\n",
    "      states_actions_rewards.append((s, a, r))\n",
    "    seen_states.add(s)\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": 14,
   "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": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rewards:\n---------------------------\n-0.90|-0.90|-0.90| 1.00|\n---------------------------\n-0.90| 0.00|-0.90|-1.00|\n---------------------------\n-0.90|-0.90|-0.90|-0.90|\n"
     ]
    }
   ],
   "source": [
    "grid = negative_grid(step_cost=-0.9)\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": [
      "initial policy:\n---------------------------\n  D  |  U  |  L  |     |\n---------------------------\n  D  |     |  L  |     |\n---------------------------\n  L  |  L  |  D  |  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": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (1, 2): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (0, 0): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (2, 3): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (2, 0): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (1, 0): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (2, 2): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (0, 2): {'U': 0, 'R': 0, 'L': 0, 'D': 0}, (2, 1): {'U': 0, 'R': 0, 'L': 0, 'D': 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 # needs to be initialized to something so we can argmax it\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": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# repeat until convergence\n",
    "deltas = []\n",
    "for t in range(2000):\n",
    "  # generate an episode using pi\n",
    "  biggest_change = 0\n",
    "  states_actions_returns = play_game(grid, policy)\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",
    "  # update policy\n",
    "  for s in policy.keys():\n",
    "    policy[s] = max_dict(Q[s])[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEACAYAAAC9Gb03AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAE6hJREFUeJzt3XmQldWdxvHnhy2luPuHGkXBJYpOylgaYyouITIopRWd\nME5F47jGpKwahTKGUSsxYFWqYlJljUtiogaNa9ShjFFLSyB43UaDCoJi24CKKEoryCKLsv3mj/N2\n7u2ml7u8b5/L6e+n6q13ue9y7unbzz193qXN3QUASNeg2AUAABSLoAeAxBH0AJA4gh4AEkfQA0Di\nCHoASFyfQW9mk82s3czmVizbw8ymmlmbmT1tZrsVW0wAQL2qadHfJenULsuuljTd3Q+TNEPSNXkX\nDACQD6vmhikzGybpcXc/Mpt/W9J33L3dzPaRVHL3EcUWFQBQj3r76Pdy93ZJcvelkvbKr0gAgDzl\ndTKW5ygAQJNqqXO7djPbu6Lr5pOeVjQzvgQAoA7ubnnsp9oWvWVDh8ckXZhNXyDpb71tfPjhrtDo\nD8PUqWH85JMud4ZahokTJ0YvQyoDdUl9NvOQp2our3xA0v9JOtTMFpvZRZKulzTazNokjcrme5Rz\nmQEANeiz68bdf9jDS/+ac1kAAAXgzthtzMiRI2MXIRnUZb6oz+ZF0G9j+GXKD3WZL+qzeUUNesvl\nfDIAoDf9EvScjAWAeOi6AYDEEfQAkDiCHgASR9ADQOI4GQsAiePySgBIHF03AJA4gh4AEkfQA0Di\nCHoASFzUq244GQsAxYvaoueySwAoHl03AJA4rqMHgMTRogeAxPEIBABIHC16AEgcQQ8AieNkLAAk\njhY9ACSOk7EAkDha9ACQuChBT988APSfKEFPVw4A9B+6bgAgcTymGAASx2OKASBxnIwFgMRFPRlL\n4ANA8TgZCwCJ485YAEgcLXoASFxDQW9mV5jZm2Y218zuN7PB1W3XyFEBALWoO+jNbF9Jl0s62t2P\nlNQi6exqtuVkLAD0n5YGt99O0k5mtkXSEEkf1bIxffcAULy6W/Tu/pGkGyQtlrRE0kp3n979uvUe\nBQDQqLpb9Ga2u6QzJQ2TtErSFDP7obs/0HXdFSsmVcyNzAa6bgCgQ6lUUqlUKmTf5nU2t83sLEmn\nuvuPs/nzJB3n7pd1Wc+HD3ctWlReNm2aNHq0NH26NGpUvUUHgHSZmdw9l+ZwI1fdLJb0LTPbwcxM\n0ihJrdVsSFcOAPSfRvroZ0qaImm2pDmSTNLtOZULAJCThq66cffrJF2XU1kAAAWI8giEjpOwnIwF\ngOLxCAQASBz/MxYAEkeLHgASR9ADQOKinowFABSPFj0AJC5Ki57HFANA/6FFDwCJI+gBIHGcjAWA\nxNGiB4DERQ16WvYAULyoV93wKAQAKB5dNwCQOB5TDACJo0UPAIkj6AEgcVFPxgIAikeLHgASx52x\nAJA4WvQAkDiCHgASx/PoASBxtOgBIHGcjAWAxNGiB4DEEfQAkDjujAWAxNGiB4DERQl6HlMMAP0n\nStcNAKD/0HUDAInjZCwAJI4WPQAkrqGgN7PdzOx/zazVzOaZ2XHVbdd5DAAoTkuD298k6Ul3/w8z\na5E0pLuVeuqqoQsHAIpXd9Cb2a6STnT3CyXJ3TdJWp1TuQAAOWmk6+ZAScvM7C4zm2Vmt5vZjt2t\n2FPLna4bACheI0HfIuloSb9396MlrZN0dS6lAgDkppE++g8lfeDur2bzUyRd1d2K69dPqpgbmQ0A\ngA6lUkmlUqmQfZs3cEbUzJ6V9GN3n29mEyUNcferuqzju+/uWrmyvGzaNGn0aOm556QTT6z78ACQ\nLDOTu+fSwd3oVTfjJN1vZttLelfSRY0XCQCQp4aC3t3nSDq23u05GQsAxYv6CASuoweA4vEIBABI\nHI8pBoDERWnRE/wA0H+idt0Q+ABQPLpuACBxdN0AQOKitugJfAAoXr8E/Zo1neeXL++PowIApEhd\nN+eeG+OoADAwccMUACSOyysBIHG06AEgcQQ9ACSOoAeAxNFHDwCJo0UPAImLGvRtbWHsLs2fH7Mk\nAJCuhv45eFUHMHOp52O4S48/Lp1xBl05ANAhz38O3hRdN10fkQAAyE9TBD0AoDgEPQAkjqAHgMQR\n9ACQOIIeABJH0ANA4poi6Ll+HgCKEz3oCXkAKFb0oAcAFCt60NOiB4BiRQ96AECxogc9LXoAKFb0\noJcky+X5bACA7kQPelr0AFCs6EEPAChW9KB3p1UPAEVqOOjNbJCZzTKzx/IoEAAgX3m06MdLeqve\njWnNA0CxGgp6Mxsq6TRJf8qnOACAvDXaov8fSRPU23//7gMtegAoVt1Bb2anS2p399clWTYAAJpM\nSwPbHi/pDDM7TdKOknYxs3vc/fytV51UMT0yGwJa9AAglUollUqlQvZtnkPSmtl3JF3p7md085r3\n1rOzfr30yCPSuecS+gDQwczk7rn0lDTFdfQAgOI00nXzT+7+rKRn89gXACBftOgBIHHRgx4AUKzo\nQU+LHgCKFT3oAQDFih70tOgBoFjRgx4AUKzoQU+LHgCKFT3oAQDFih70tOgBoFjRgx4AUKzoQU+L\nHgCKFT3oAQDFih70tOgBoFjRgx4AUKzoQU+LHgCKFT3oAQDFih70tOgBoFjRgx4AUKzoQU+LHgCK\nFT3oJcIeAIoUPegJeQAoFkEPAImLHvQAgGJFD3pa9ABQrOhBDwAoVvSgd5fMYpcCANIVPegBAMWK\nHvT00QNAsaIHvSTNmxfGb70lbdggPfZY3PIAQErMC25Sm5lLPR/jo4+kffctzz/yiDR2LC19AAOb\nmcndczmD2RQtegBAcaIHPS13AChW9KAHABQretB3bdHTwgeAfEUPegBAsaIHPS14AChW3UFvZkPN\nbIaZzTOzN8xsXB4F4nEIAJCvlga23STpp+7+upntLOk1M5vq7m/XshP66AGgWHW36N19qbu/nk2v\nkdQqab+8CgYAyEcuffRmNlzSUZL+Ueu2tOABoFiNdN1IkrJumymSxmct+25MqpgemQ0AgA6lUkml\nUqmQfTf0rBsza5H0hKSn3P2mHtbp9Vk3ixZJw4eX56dMkc46i5Y+gIGtmZ51c6ekt3oK+VpxxQ0A\n5K+RyyuPl3SupJPNbLaZzTKzMbXup2vLnbAHgHzV3Ufv7i9K2q7RAtx/f+U+G90bAKCr6HfGPvRQ\n53nCHgDyFT3oAQDFIugBIHHRg76yq4YTsQCQv+hBDwAoFkEPAInrl6CnSwYA4oneoq/so+fSSgDI\nX9O16Al7AMhX9BZ9Jbp4ACB/0YOeFjwAFCt60HfVU6veTHr++f4tCwCkIHof/ZYtned7a+G3teVT\nHgAYSKK36LsGfW8GRS8tAGx7okdnLX30BD0A1K7pum7q3Q8AoHvR28jvvNN5vrcWPi16AKhdv0Tn\npk357IegB4DaNV109tY9Q9cNANSu6YK+NwQ9ANSuqYLeXZo+PUyvW7f16wsX9m95ACAF5gU/g8DM\nXKr9GBdfLE2eXLmfMOaRCQAGAjOTu+fSj9FULfpK7e2xSwAAaWjaoN+8OXYJACANTRv0eV2SCQAD\nXdMG/YYN5btmCX0AqF/TBv1zz0knnBCmt9++vPzb365+Hxs35lsmANgWNe1VNx02buwc9FL1V96Y\nSe+/Lx1wQN2HB4AoBsRVNx2++GLrZeedV/32q1blVxYA2BY1fdCvX7/1svvuk954g0swAaAaTR/0\n3bXoJenII6Wzz+7fsgDAtqjpg767Fn2HUqm2bpx16zr378+aVXexAGCbESXohw6tft2+nm9z331h\nbCY9/nh5eXcnbHfaSfrjH8P0p59KxxxTfTkAYFsVJehPOqn6dU8/ve91ZswI45dekpYskW68sXxn\nbcf4iCPC+L33wrijS2jDBmnmTGnlyurLBADbkihBn/fjhkeNCuNVq6S//lW64oryTVa33x7Gra1h\n3PHPS9asKY+PO076xS/K+9u0KSx3ly64oO/LOdeuzed9AEARGgp6MxtjZm+b2Xwzu6rqg1Yc9fvf\nb6QEnd16q3T55WH6gw/C+A9/6PzFMm9eGHcEfUfXT+WzdX7+c2mXXaQvv5TuuUdasCD8JdBT4O+8\nc++Xcd5yizRtWt/lX726XG4AyEvdQW9mgyT9TtKpkv5F0jlmNqKqg2ZHHTJEuvvuMH3OOVuvt912\n9ZZOOvTQ7pc/8YT04ovSZ5+F+fHjy2XauFF64QVp0aKwrKNshx0mHXSQ9Oij0p//HP5q+NWvpMGD\ny3fffvppGL/2Whh/8YX04YfS/PnSuHHhy6M7mzeXv0AuuaTvm7tKpVLvK/TBPXzxrV4dvux+8IPu\n13nwwe7/J4CUzl8wjdYlOqM+m1cjLfpvSlrg7u+7+0ZJD0o6s5oNK1vYHXe97rBD53WuvFK6884G\nSteLE06QxozpvOzWW6UJE6QTT5R23DEsu/TSzuu0tUkXXSSNHStde20I+cGDw2u//GV4Ns83vhFO\n+O64o7T//uFLQpJeeSUc93vfk5Ytk+bMkX7yE6mlJXyhtLWVW/OzZklPPSV9/euhG2nZMunXvw6v\nlUolrVpV/gtixoxwnqFaS5eG8YsvSrfdJj388NbrLFgQvnjHjg3nLz7/vPza00+Hv2DMun/C6G67\nSc88U56fP1+6917pzTfDe6z029+G/TzzTPjiXLIkLP/88/CFu359qIslS6q7G7qju63aO6cJpnxR\nn03M3esaJP27pNsr5v9T0s3drOflX78wXHxxGA8Z4r55c5j+0Y86rzN7tvtDD4Xpk092/9rXfKv9\nDMRh0KCJPb7W1hbqc/78zst33dX9Zz8L9T5ixNbbTZ/u3trqfv31PR/3+uvdBw92v/LK8rIzz3S/\n5JKw3zvucF+2rPzazTe7Dx269X6WL3f/5BP3888vLzvggPL0bbd1f/wRI9wvvTRM33mn+1e+4v7V\nr7ofc4z7ddd1Xvfgg93Xr3cfN879gQfCsieeCOPvftf9wgvdL7jA/aSTJvqkSe4TJoTjTpni/swz\n7q++Gubfftv9gw/cn3vO/bXXwntdutT9yy/dH37Y/d133Vetcr/3XvcbbnBfvNj9kUfcb7rJfdEi\n97/8xX3BAveNG91fftl9zhz3FSvcn37a/Xe/c7/xRvcXXnD/7LOwz+XLw+u33BKOvXJl2Padd9zf\nfNN9yxb3DRvc77rLffJk9zVr3NeudX/2WffVq92nTQv7WLIkbPP882EfixeH/a5Z497eHsabNoWf\n18qV4diLFrl//nn4/GzYENZZuDAcf+FC95decncPn62pU0P9btpUXre93f3aaye6eyiTe3h93bqw\nzsyZ4ef+3nthn1u2hPHmzWF65Ur3Bx8M+92yJSx3D9Nbtvg/bdgQ9rl4cfm1L74o72f58vD6Z5+F\n/a9YEZbPnBmWd93fxx+HfXYsX7s2zC9bFurx1VfDz7DydfdwzNbW8r46Xl++PPys2tvL627cGOrt\nvfc6H7vjfVYucw914SE8vd583iqHYwT9hAnue+4ZflE9K8X48e777VdeZ+7cEECS+3nnuV9xRd8h\n+Pe/1xaahx1WTBg3MhxySF/rTIxexnQG6rKW4eCD+67PYcPyP65Z/Pee5zBsmPuxx3Zetsce7ocf\nXp4fPdo9z6Cv+6FmZvYtSZPcfUw2f3VWsN90Wa++AwDAAOc5PdSskaDfTlKbpFGSPpY0U9I57t6a\nR8EAAPloqXdDd99sZpdJmqpwUncyIQ8Azafw59EDAOIq7M7Yem+mGujMbJGZzTGz2WY2M1u2h5lN\nNbM2M3vazHarWP8aM1tgZq1mdkq8kjcHM5tsZu1mNrdiWc31Z2ZHm9nc7PN7Y3+/j2bQQ11ONLMP\nzWxWNoypeI267IWZDTWzGWY2z8zeMLNx2fLiP595ndXtcqXNIEkLJQ2TtL2k1yWNKOJYqQ2S3pW0\nR5dlv5H039n0VZKuz6aPkDRboQtueFbnFvs9RK6/EyQdJWluI/Un6R+Sjs2mn5R0auz31iR1OVHS\nT7tZ93Dqss/63EfSUdn0zgrnOEf0x+ezqBZ93TdTQaat/9I6U1J2n67ulvRv2fQZkh50903uvkjS\nAoW6H7Dc/QVJK7osrqn+zGwfSbu4+yvZevdUbDNg9FCXUviMdnWmqMteuftSd389m14jqVXSUPXD\n57OooN9PUuVTWz7MlqFvLmmamb1iZpdky/Z293YpfFgk7ZUt71rPS0Q9d2evGutvP4XPbAc+v51d\nZmavm9mfKroZqMsamNlwhb+WXlbtv98112nT/+ORAeh4dz9a0mmS/svMTpS2+u/qnEFvDPVXv1sl\nHeTuR0laKumGyOXZ5pjZzpKmSBqftewL//0uKuiXSKp8PNfQbBn64O4fZ+NPJT2q0BXTbmZ7S1L2\nZ9sn2epLJO1fsTn13L1a64967YG7f+pZx7CkO1TuKqQuq2BmLQohf6+7/y1bXPjns6igf0XSIWY2\nzMwGSzpb0mMFHSsZZjYk+7aXme0k6RRJbyjU3YXZahdI6viAPCbpbDMbbGYHSjpE4ca1gc7UuR+5\npvrL/nxeZWbfNDOTdH7FNgNNp7rMgqjDWElvZtPUZXXulPSWu99Usaz4z2eBZ5jHKJxVXiDp6thn\nvLeFQdKBClcozVYI+Kuz5XtKmp7V51RJu1dsc43C2fhWSafEfg+xB0kPSPpI0peSFku6SNIetdaf\npGOyn8ECSTfFfl9NVJf3SJqbfU4fVehfpi6rq8/jJW2u+B2fleVkzb/ftdYpN0wBQOI4GQsAiSPo\nASBxBD0AJI6gB4DEEfQAkDiCHgASR9ADQOIIegBI3P8DgcGWrb0EXnsAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x262d9eb9eb8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  U  |  R  |  U  |  U  |\n"
     ]
    }
   ],
   "source": [
    "plt.plot(deltas)\n",
    "plt.show()\n",
    "\n",
    "print(\"final policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n-1.96|-1.20| 1.00| 0.00|\n---------------------------\n-2.87| 0.00|-0.75| 0.00|\n---------------------------\n-3.17|-2.86|-1.78|-1.00|\n"
     ]
    }
   ],
   "source": [
    "# find V\n",
    "V = {}\n",
    "for s, Qs in Q.items():\n",
    "  V[s] = max_dict(Q[s])[1]\n",
    "\n",
    "print(\"final values:\")\n",
    "print_values(V, 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
}