Lab 1 - Problem 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_1",
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "# Lab 1: Markov Decision Processes - Problem 2\n",
    "\n",
    "\n",
    "## Lab Instructions\n",
    "All your answers should be written in this notebook.  You shouldn't need to write or modify any other files.\n",
    "\n",
    "**You should execute every block of code to not miss any dependency.**\n",
    "\n",
    "\n",
    "*This project was developed by Peter Chen, Rocky Duan, Pieter Abbeel for the Berkeley Deep RL Bootcamp, August 2017. Bootcamp website with slides and lecture videos: https://sites.google.com/view/deep-rl-bootcamp/. It is adapted from Berkeley Deep RL Class [HW2](https://github.com/berkeleydeeprlcourse/homework/blob/c1027d83cd542e67ebed982d44666e0d22a00141/hw2/HW2.ipynb) [(license)](https://github.com/berkeleydeeprlcourse/homework/blob/master/LICENSE)*\n",
    "\n",
    "--------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# basic setup\n",
    "from misc import FrozenLakeEnv, make_grader\n",
    "env = FrozenLakeEnv()\n",
    "import numpy as np, numpy.random as nr, gym\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "np.set_printoptions(precision=3)\n",
    "class MDP(object):\n",
    "    def __init__(self, P, nS, nA, desc=None):\n",
    "        self.P = P # state transition and reward probabilities, explained below\n",
    "        self.nS = nS # number of states\n",
    "        self.nA = nA # number of actions\n",
    "        self.desc = desc # 2D array specifying what each grid cell means (used for plotting)\n",
    "mdp = MDP( {s : {a : [tup[:3] for tup in tups] for (a, tups) in a2d.items()} for (s, a2d) in env.P.items()}, env.nS, env.nA, env.desc)\n",
    "GAMMA = 0.95\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2: Policy Iteration\n",
    "\n",
    "The next task is to implement exact policy iteration (PI), which has the following pseudocode:\n",
    "\n",
    "---\n",
    "Initialize $\\pi_0$\n",
    "\n",
    "For $n=0, 1, 2, \\dots$\n",
    "- Compute the state-value function $V^{\\pi_{n}}$\n",
    "- Using $V^{\\pi_{n}}$, compute the state-action-value function $Q^{\\pi_{n}}$\n",
    "- Compute new policy $\\pi_{n+1}(s) = \\operatorname*{argmax}_a Q^{\\pi_{n}}(s,a)$\n",
    "---\n",
    "\n",
    "Below, you'll implement the first and second steps of the loop.\n",
    "\n",
    "### Problem 2a: state value function\n",
    "\n",
    "You'll write a function called `compute_vpi` that computes the state-value function $V^{\\pi}$ for an arbitrary policy $\\pi$.\n",
    "Recall that $V^{\\pi}$ satisfies the following linear equation:\n",
    "$$V^{\\pi}(s) = \\sum_{s'} P(s,\\pi(s),s')[ R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')]$$\n",
    "\n",
    "You can solve a linear system in your code. (Find an exact solution, e.g., with `np.linalg.solve`.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_vpi(pi, mdp, gamma):\n",
    "    A=np.zeros((mdp.nS, mdp.nS))\n",
    "    C=np.zeros((mdp.nS,1))\n",
    "\n",
    "    for state in range(mdp.nS):\n",
    "        # work out quality for each action so we can take the argm\n",
    "        action = pi[state]\n",
    "        # sum over all possible next states (s'), corresponds to the summation over s' in the above equations\n",
    "        A[state,state]=1\n",
    "        for probability, nextstate, reward in mdp.P[state][action]:\n",
    "            A[state][nextstate] += -gamma*probability\n",
    "            C[state] += probability*reward\n",
    "    v= np.linalg.solve(A,C)\n",
    "    return np.reshape(v,mdp.nS)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's compute the value of an arbitrarily-chosen policy. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test passed\n"
     ]
    }
   ],
   "source": [
    "expected_val = np.array([  1.381e-18,   1.844e-04,   1.941e-03,   1.272e-03,   2.108e-18,\n",
    "         0.000e+00,   8.319e-03,   1.727e-16,   3.944e-18,   2.768e-01,\n",
    "         8.562e-02,  -7.242e-16,   7.857e-18,   3.535e-01,   8.930e-01,\n",
    "         0.000e+00])\n",
    "\n",
    "actual_val = compute_vpi(np.arange(16) % mdp.nA, mdp, gamma=GAMMA)\n",
    "if np.all(np.isclose(actual_val, expected_val, atol=1e-4)):\n",
    "    print(\"Test passed\")\n",
    "else:\n",
    "    print(\"Expected: \", expected_val)\n",
    "    print(\"Actual: \", actual_val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2b: state-action value function\n",
    "\n",
    "Next, you'll write a function to compute the state-action value function $Q^{\\pi}$, defined as follows\n",
    "\n",
    "$$Q^{\\pi}(s, a) = \\sum_{s'} P(s,a,s')[ R(s,a,s') + \\gamma V^{\\pi}(s')]$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "compute_qpi",
     "locked": false,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test passed\n"
     ]
    }
   ],
   "source": [
    "def compute_qpi(vpi, mdp, gamma):\n",
    "    Qpi = np.zeros([mdp.nS, mdp.nA]) # REPLACE THIS LINE WITH YOUR CODE\n",
    "    for i in range(mdp.nS):\n",
    "        for j in range(mdp.nA):\n",
    "            for probability, nextstate, reward in mdp.P[i][j]:\n",
    "                Qpi[i,j] += probability*(reward + gamma*vpi[nextstate])\n",
    "    return Qpi\n",
    "\n",
    "expected_Qpi = np.array([[  0.38 ,   3.135,   1.14 ,   0.095],\n",
    "       [  0.57 ,   3.99 ,   2.09 ,   0.95 ],\n",
    "       [  1.52 ,   4.94 ,   3.04 ,   1.9  ],\n",
    "       [  2.47 ,   5.795,   3.23 ,   2.755],\n",
    "       [  3.8  ,   6.935,   4.56 ,   0.855],\n",
    "       [  4.75 ,   4.75 ,   4.75 ,   4.75 ],\n",
    "       [  4.94 ,   8.74 ,   6.46 ,   2.66 ],\n",
    "       [  6.65 ,   6.65 ,   6.65 ,   6.65 ],\n",
    "       [  7.6  ,  10.735,   8.36 ,   4.655],\n",
    "       [  7.79 ,  11.59 ,   9.31 ,   5.51 ],\n",
    "       [  8.74 ,  12.54 ,  10.26 ,   6.46 ],\n",
    "       [ 10.45 ,  10.45 ,  10.45 ,  10.45 ],\n",
    "       [ 11.4  ,  11.4  ,  11.4  ,  11.4  ],\n",
    "       [ 11.21 ,  12.35 ,  12.73 ,   9.31 ],\n",
    "       [ 12.16 ,  13.4  ,  14.48 ,  10.36 ],\n",
    "       [ 14.25 ,  14.25 ,  14.25 ,  14.25 ]])\n",
    "\n",
    "Qpi = compute_qpi(np.arange(mdp.nS), mdp, gamma=0.95)\n",
    "if np.all(np.isclose(expected_Qpi, Qpi, atol=1e-4)):\n",
    "    print(\"Test passed\")\n",
    "else:\n",
    "    print(\"Expected: \", expected_Qpi)\n",
    "    print(\"Actual: \", Qpi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're ready to run policy iteration!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration | # chg actions | V[0]\n",
      "----------+---------------+---------\n",
      "   0      |      1        | -0.00000\n",
      "   1      |      9        | 0.00000\n",
      "   2      |      2        | 0.39785\n",
      "   3      |      1        | 0.45546\n",
      "   4      |      0        | 0.53118\n",
      "   5      |      0        | 0.53118\n",
      "   6      |      0        | 0.53118\n",
      "   7      |      0        | 0.53118\n",
      "   8      |      0        | 0.53118\n",
      "   9      |      0        | 0.53118\n",
      "  10      |      0        | 0.53118\n",
      "  11      |      0        | 0.53118\n",
      "  12      |      0        | 0.53118\n",
      "  13      |      0        | 0.53118\n",
      "  14      |      0        | 0.53118\n",
      "  15      |      0        | 0.53118\n",
      "  16      |      0        | 0.53118\n",
      "  17      |      0        | 0.53118\n",
      "  18      |      0        | 0.53118\n",
      "  19      |      0        | 0.53118\n",
      "Test succeeded\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8o1d97/HP0W5ttuXds2+ZzJLJNiQhLEkTliQQ0vZy\nW6AFQhvS5JJQaAvkll7KvXSh5bYEQkjITQOhQAOUJSkdCARaQoHsyyQzmUk8+9iWN8mSrF3Pc+4f\njzxxZuyx/Ei2Zfn3fr38Gkt6pOf4ifOdM+c553eU1hohhBCNxbHYDRBCCFF7Eu5CCNGAJNyFEKIB\nSbgLIUQDknAXQogGJOEuhBANSMJdCCEakIS7EEI0IAl3IYRoQK7ZDlBK3QO8FRjWWm+f5nUFfA64\nCsgA12qtn5rtc9vb2/XatWvn3GAhhFjOnnzyyVGtdcdsx80a7sBXgC8AX53h9SuBTeWvC4E7yn+e\n1tq1a3niiScqOL0QQohJSqkjlRw367CM1vphIHaaQ64BvqotjwAtSqmeypophBBiPtRizH0FcGzK\n4+Pl54QQQiySBb2hqpS6Xin1hFLqiZGRkYU8tRBCLCu1CPd+YNWUxyvLz51Ca32X1nqn1npnR8es\n9wOEEELYVItwfwB4j7JcBCS01oM1+FwhhBA2VTIV8l+AS4F2pdRx4C8BN4DW+k5gF9Y0yD6sqZDv\nm6/GCiGEqMys4a61fucsr2vgAzVrkRBCiKpVMs9dTKG1JjaQJp8tYRoabWgMw8Q0tPXY1JiGifGK\nxy8fM/lYCLF89WxsZvXWtnk9h4T7HGhT8/P7XmTPw9PeL54bVf1HCCGWpvPetEbCvV6YhsnP/nkf\n+x+JsuOylazd3o5yKhzlL6fTgXK8/Hi655xOh/UehyS7EGJ+SbhXwCiZ/OSevRx4apgLrl7HzqvW\nYpXUEUKI+iThPotS0eDBu57n8HNjXPzfNnLuG1cvdpOEEGJWEu6nUcwb7LpjN8f3xbnkXZvZ/nqp\nqiCEWBok3GeQz5b49y88S/Rggsuv3cKZF0ktNCHE0iHhPo3cRJF/u+0ZRo9N8KbrtrPx/M7FbpIQ\nQsyJhPtJMskC99/6NInhLFfecBZrd7QvdpOEEGLOJNynmIjnuP/WZ5iI53jLB3awaktksZskhBC2\nSLiXJUay3H/r0+TTRa7+4Dn0bmxZ7CYJIYRtEu5APJrm/s8+Talkcs2Hz6VzTXixmySEEFVZ9uE+\nenyCBz73NAC/9Sfn0bYiuMgtEkKI6i3rcB86lOTfbnsGl8fJNR86h9buwGI3SQghamLZhvvAS+P8\n4PZnaQq6ueZD5xJub5rX8+lSifzBg+RfeIH8gYNoozSv5xNC1K/ABRcQvOSSeT3Hsgz3Y3tj7Lpj\nN8GIj2s+dC7BVm9NP98sFMi/+BK5vXvI7d1L7oUXyO/bj87nrQNcLpRrWV56IQSgPB4J91qLDaT5\nwRefpbUrwNv++Bz8YU9Vn2em0+T27ye3xwrx3N695Pv6oGT1zB2hEL4tW2h95zvxbduKb8sWPOvW\noZzOWvw4QggxrWUX7kOHk5glzZvfv81WsJv5POPf/CbZZ3eTe+EFCocOgbY233BGIvi2biX4+tfj\n27oV37atuFeulAqSQogFt+zCPZsqABBosTcUk/7lrxj6m7/F1dWFb9s2wldddSLIXZ2dEuRCiLqw\n7MI9kyrg8jjw+Oz96KXhYQDWfutbuLuk5owQoj45FrsBCy2bKtAUsj/OXhobBcAVaa1Vk4QQouaW\nX7gnC1XdRDXGYjibm1Fudw1bJYQQtbXswj2TKlbZcx/D2S6VIoUQ9W3ZhXs2WcAfst/rLo2N4opI\ntUghRH1bVuGuTU12orqeuzE6hrO9rYatEkKI2ltW4Z7LFNGmpqmKMfdSLIarTYZlhBD1bVmFezZZ\nBLB9Q9UsFDCTSVzScxdC1LllFe6Z8gImu8MyxtgYYK1EFUKIeraswn1ydarfZriXxmIAuGS2jBCi\nzi2rFaqZZLnnHrY3W8aYXMDUZn9YJmeY3BeNkSwZtj9DCLG0nRf289rW0LyeY1mFezZVQDkUPr+9\ncC+Nlodlqgj3/3s4yheODtt+vxBi6btpdaeEey1lkwWagm6Uw15xr1J5zN1uz/1gJs+Xjg7ztuYQ\nn9zYa+szhBBLX8A9/9Fb0RmUUlcAnwOcwN1a60+f9Hoz8DVgdfkz/6/W+ss1bmvVMqliVdMgjbEx\nHH4/jqbKdm1K5Yq8OJRiXzTF/miK7x8YwRnP8eNiPz9mn+12CCGWthsu2cAtV545r+eYNdyVUk7g\nduCNwHHgcaXUA1rrvVMO+wCwV2t9tVKqA9ivlPq61rowL622KZuqdnXq2LRDMkXD5OBImn3RJPvL\nQb4vmqJ/PHviGJ/HScbv5NxNbVy9rh2va1ndyxZCTLG1t3nez1FJz/0CoE9rfRBAKXUfcA0wNdw1\nEFJWMfMgEAPqbpPQTLJAc6f9i1oaG8XZ1sbDL47w/EDiRJAfGJmgaFgbdrgcivUdAc5b08q7LlzN\n5q4Q67oC/N6LR2h3OPj2qzbjcUiwCyHmVyXhvgI4NuXxceDCk475AvAAMACEgN/VWps1aWENVVvu\n1xiLkYx08Z57HgOgt9nH5u4Ql27u5MzuEJu7Q2zoCOI5qVd+25EhDueKfGPHegl2IcSCqNWo/puB\nZ4DLgA3AT5RSv9BaJ6cepJS6HrgeYPXq1TU6dWUKuRKlgml7jjtYwzKJ3o0A/OefXcra9sCs7xnM\nF/jskSHe3B7msraw7XMLIcRcVNKN7AdWTXm8svzcVO8DvqstfcAh4JS7BVrru7TWO7XWOzs6Ouy2\n2ZZsyio9YLfnrg0DIx5n3BPA5VCsivgret9fHRjE0Jr/s3GFrfMKIYQdlYT748AmpdQ6pZQHeAfW\nEMxUR4HLAZRSXcBm4GAtG1qtE6tTbc6WMeJxME1GXEG6wj6cFUynfHR8gu8MxblxVSdrmuzt2SqE\nEHbMOiyjtS4ppW4CHsSaCnmP1nqPUuqG8ut3Ap8CvqKUeg5QwMe01qPz2O45O7E61eZsmcnSAwOO\nJrqbfbMeb2jNx1/qp9fr5uY1steqEGJhVTTmrrXeBew66bk7p3w/ALyptk2rrap77uXSA8e0r6Jw\n//rAGM9PZLlz6xoCTqetcwohhF3LZurGZLg3Be0WDbNWpx4wPPTOEu7xYolPHxrk1S0BrulssXU+\nIYSoxrIJ90yyiNfvwum29yNPhvuQI0B38+lXqP79oSjjRYO/3rQSa+q/EEIsrGUT7tXPcR8Dt5u0\n20fPaXrueyey3Ns/yntXtLM1WFmZAiGEqLVlE+6ZZMH2zVSwKkIa4RZQasYxd601f/7icVrcTj66\nrtv2uYQQolrLJtyzqYLtm6lglR7Ih6zx85l67vcPj/NIIs0t63poXYCqb0IIMZNlE+6ZGpQemPCH\ncSjoCJ46Zz1tGPyfAwOcFWzi93plj1UhxOJaFuFuGCb5dKnKnvsY494gnSEfLuepl+22I8MM5Iv8\n9aYVOOUmqhBikS2LcM9VW3pAa4yxMUbdgWnH2w9n83zx6DD/rauVC1qCVbVVCCFqYVmEe6bKjbHN\nVApdLDLo8E873v6Xff24HIr/tUF2VxJC1IdlEe7ZaksPlPdOnW516s/Gkjw4muTDa7ro9tqfjSOE\nELW0LMJ9sudud4u9ydIDQ85X9twLpskn+vpZ3+Tl+lULW+VSCCFOZ1nM18smrTF3u8Myk6tTx70h\neqasTr37+Ch9mTxf27Eer2zCIYSoI8sikTKpAk63A7fPXgGvyXCP+4Ineu5D+SL/cDjKG9rCvEE2\n4RBC1JllEe5W6QG37TovxtgYWjlIeV6eLfNXBwcomppPySYcQog6tDzCPVmobnu90TEKwRDa4aAz\n5OOJRJpvR+P80aoO1vllEw4hRP1ZFuGeSRVs30wFKMXGSPubaQ96cTkVf/7Scbo9bj60pquGrRRC\niNpZFuFebc/dGB0jWR5v/0V8gt2pLB/f0EPAJZtwCCHqU8PPltFak00Vq6orUxobY9TbTXfYx6Fs\nHoDXtYZsf16xOI5hZGy/XwixtDmdQdzu+Z2I0fDhns+UME1ddV2Z6Kr19DT7GMgVcCno8Ni7dKNj\n/8nu3TegddF2e4QQS9ua1X/Exo0fnddzNHy4n9hez+bqVDOTQWcyDDsDrG9uYk++SLfXbas4mNYG\nfX2fxufrZe2aG2y1Rwix9AWDZ877ORo+3DPJ6lanlmIxAMa91pj7j/MZVnjtfVY0ej/p9Ets334b\nXZ1X2foMIYSoRMPfUM2mqludaoxapQfGvSG6m30M5Ir02qghY5p5Dh66lVBoO50dV9hqixBCVKrh\nw/1Ez91u6YFyzz3us8J9MF+k1zf3z+rv/xdyuX42bPgISjX8ZRdCLLKGT5lsqoBS4AvarQhZ7rl7\ngrh8Tgpaz7nnXipNcOjw7bS2vppI62tstUMIIeai4cM9kyrgC7pxOOyXHgBwRloZNUyAOY+5Hz12\nD8VijI0bPmq7BIIQQsxFw4d7NlnlxtijY+S8ftojIQby1hBPr6/ynnuhMMbRo3fT0XEF4fAO2+0Q\nQoi5aPxwr3Jj7FJsjERTyJrjnrduzvbOoed++MgdGEaWDev/xHYbhBBirho+3DNVrk41RseIuYN0\nN/vozxXwORRt7srKDmSz/Rw//nV6e95OILDBdhuEEGKuGj7cq60rUxwdZdQdoKe5iYF8kR5v5aWD\nDx36HErBunU32z6/EELY0dDhXiwYFPMGTWH7e5sWx2LEvUG6w5Nz3Cv7i2Ji4kUGo99j5Yp34/PJ\nxtlCiIXV0CtUs1XOcdfFIiQTJHqt1akDwwkubg1W9N4DB/8Bp9PP2rU3vuJ5M1PESBbQprbVJiHE\n0ucMenBWMdGjEg0d7pMbY9udLXNiAZM3RGfYS/R4cdZpkNrQxAYeZXT0IVa630/moXFKsSilWI7S\nWA6dK9lqixCicYQuWUnzlevm9RwVhbtS6grgc4ATuFtr/elpjrkUuBVwA6Na60tq2E5bJksP2O25\nG1M2xnb4XBgaer1uzFyJ0liOUiyLEcudCO5SLEdpPMux8z6NMxCm6afnk6IfV6sPZ8SHf1UIV8SH\ns8WLsjnvXgix9Lnam+b/HLMdoJRyArcDbwSOA48rpR7QWu+dckwL8EXgCq31UaVU53w1eC4mh2Vs\n99zL4V5qbiGmrQVMnakSA7f/GsyXj3MEXDgjTXhWhSiec4isaz/rIx+j9yOvwxmWIBdCLLxKeu4X\nAH1a64MASqn7gGuAvVOOeRfwXa31UQCt9XCtG2pHpspyv6VRK9w97e30lxcwdcQKYELr28/A3RvA\nFfHh8FmXUWuTvsc/gq+0ijU7rsXhmN8xNSGEmEkls2VWAMemPD5efm6qM4BWpdR/KqWeVEq9p1YN\nrEY2WcDjc+KqcF76yYwxq65MoLuDgZw1xNMxXgKXwn9eJ57e4IlgBxga/ncmJvayYf2HJdiFEIuq\nVjdUXcD5wOVAE/BrpdQjWusXpx6klLoeuB5g9erVNTr1zKpenToWI+/00NbRykC+QMDpwB/LUmrx\nnTLUYpoFDh78R4LBM+nqurrapgshRFUq6bn3A6umPF5Zfm6q48CDWuu01noUeBg4++QP0lrfpbXe\nqbXe2dHRYbfNFcukqqsrUxgZIe4NnCg90Ot1Y8QLOCO+U44dGPg22exRNqz/MynpK4RYdJWk0OPA\nJqXUOqWUB3gH8MBJx9wPvFYp5VJK+YELgRdq29S5y6aKtndgAsgOjZzYpKM/Z02DLI3lcJ0U7oaR\n4dDh22hu3klb26VVtloIIao3a7hrrUvATcCDWIH9La31HqXUDUqpG8rHvAD8CNgNPIY1XfL5+Wt2\nZTLJ6oZlCmNjxL2TRcMK9Lhc6FzplHA/duxeCoURNm74iJT0FULUhYrG3LXWu4BdJz1350mPPwN8\npnZNq45pmOTSRfw2Z8oA6FiM8eZNtIW8jBwv0W1awe1sfTnci8Vxjhz9Eu3tl9PSsnPWz5yI5/jx\nP+2hVDBnPVYI0ZjOfHU3O35j1ewHVqFhV6hmJ4qgqyg9YJo4k+OMdwZRPica6MpbJQOm9tyPHPkS\npdIEG9b/aUWfe+yFOIN9CVae2YrTLWPzQixHbu/8R2/jhvvkxtg2x9yN8XGUaZINNDOOFepdGQN4\nOdxz+SjHjt9Ld/c1BIObK/rc2OAEDqfi1detxOGUIRwhlqMmVx2sUF2qqi0aNll6QEUiDOSsz+pM\nlFBNLhxN1mU7dOjzaG2yft2HTryvaBSJpqMMpAcYmBhgMD34ij93PHEVAW8rl3/ng9X8eEKIJewP\ntv8BHz7/w/N6joYN96qLhpXD3dPRfmIHpvaxPK6Ij8OJwxwZe5TiwLcZ9WzjE499noH0AIMTg4xm\nR9G8XPFRoeho6qAn2MNZ7WexqrQRzwqTv7jwL6r8CYUQS9WZbWfO+zkaNtyzNSo94O/soD9fpMXl\nxDuWJ9Wa57e+/x7e25Znq8/k9iOHCDUV6A30cnHvxfQGe+kJ9NAb7KU30EtXoAuP0/oLplQw+NJ9\nP+eczeu44Mz5rQgnhFjeGjbcM8kCDpfC02TvRyyMWqUHwr1d7MsV6PW6KcUTDHeNs8ppcK7foHPF\nH/Dzy/8njgoXLcWHMqChtdtvq01CCFGphp2ukU1Z2+vZnXeeHByipBy0d7dZ2+s5XWBoBtzDXNNq\n4na3smXDBysOdoB4NA1ApCdgq01CCFGpBu65V7cxdiY6wrg3SHern4GRFOf4rN521PU0W7xF1q65\nEZcrNKfPjA9mUApaOqvruY9O5MkWjKo+QwixeEI+Fy1+2YnJlmqLhuVHrNIDq0NeYgMGXeUOetJp\nVTru7HrLnD8zPpimudNf1fz2O/7zAH/3o3223y+EWHw3XLKBW66c35uqDR3ubSvsD3+YsTjj3iCr\nfVYQd2YMUFBQg5i48Hq65vyZscG07fF2rTWffeglPv/Tl7jqrG4uO3Pu5xdC1IfNXXP7V78dDRnu\nWmsyVfbcHeMxUs1rSejyAqZkCR10EnEX0e7uOY/lG4ZJYjjLunPmXg1Ta82nf7iPLz18kN/ZuZK/\n/e0dOGV3JyHEaTRkuBeyJcyStj3HXWuNN5WgtLqVgUJ5k454gVyoRIdL09S0Zs6fmRjOYpqayBx7\n7qap+d//tod7f32Ed1+0hv/9tm04JNiFELNoyHCvdmNsM53GZRShNXJiAVPbcJ6R9iRtLk1raO5j\nZZMzZVrnMFPGMDUf/95z3Pf4Md7/unX8+VVbpOqkEKIiDTkVMjO5Mbbd0gPlOe7utjYGckXa3S5c\niQLD/gM4FURCW+b8mfFBK9xbuirruZcMkz/91jPc9/gxbr5sowS7EGJOGrTnXl6danNYJj88AoC/\nq4P+fIEep7UH64j7RVYBgcDcV5fGBjMEI148vtkveaFk8sf3Pc0Pn4/ykTdv5gO/sXHO5xNCLG8N\n3XO3W3og3j8EQKi3y1rAVL5M484+63Ob1s79M6PpihYv5YoGN37tSX74fJS/eMsWCXYhhC0NGe7Z\nVAEUNAXthfv4gBXukRVdDOQKdFvD7hScgxjKi9vdOqfP06ZmPJqhtfv04Z4tGLz/q0/w033D/NVv\nbue616231X4hhGjIcM+kivgCbhxOez9eOjqMiSLQ20HKMOnKmmiXIuTJgrtrzmPfqViOUtE8bc99\nIl/ivV9+jF/2jfKZt+/g9y+a+4wcIYSY1LBj7nanQQLkhkdRHj/K7wWgM1WiGDJpd2lbQzKx8s3U\nmRYwJbJFrv3yY+w+nuDWd5zL287utd12IYSARg33ZMH2eDuAEYsx7gvhclgLmDriRZKBBBGXJhK2\nMQ1yMANMPw0yli7w7n96lBeHUtz+rvO4Ynu37XYLIcSkhgz3TKpA52r7y3vVeIxcIEyqvICpfSTP\naO9BFNAW2jrr+3WphBE9ROnwPkrHDhJ9ugWfaiN+01soxRIYySxaW4ul8iWTv9car8uJ85eKQ7Zb\nLYRYKprf9Doif377vJ6jIcPd6rnbH5bxJscZ617LQK6IA2hPlejzvkQH4A+so/DMwxRe3E1p4Cil\n6AClkVFKY+OUEhmKqSKljAbz5XH50XP/FJ95jNT+o7iCLlxBL6ZDMZEtYrodBH0u3LKfqhDLhsMn\ne6jOWaloUMgZtue4A/gzSWiN0J8v0Oly4tKQcB2iA+BnP+fAx77wiuMdHo076MTV7CPQE8HVHsHV\n2YWrZwXOFev5xa5uznhVJ2d880YAjsUyvPvuR4ini3zlfa9iw9pIFT+xEEKcquHCfbL0gN3VqaVM\nlqZiDld5derkHPeCe5Ci8lN87HEAVv/VB3FvPhvX2i04QjNPjUyP5yl+/5e0rWoBYM9Agvff+wTp\ngsHXr7uQs8vPCyFELTVcuJ9YwGSz5z5yfBAAX2cHA/kim0vWcInfk8bhWU3+4GFcAU3g7TdW9Hmx\nKWUHvvLLQ/zNrn20Btx84/0Xsq232VYbhRBiNg0X7tVujD16dBAXEOzuZCBf4PU5J4ZPE3GX8PvX\nke//Nd6uYMWfN1kw7K//q48fHRjh8jM7+cx/P5tIYH53YRFCLG8Nt4ip2qJhsf5hANzdneRMTeeE\nQSqUIOyESOAM8mNFvKt7Kv68fftj5B2anx4a5RNv3crd790pwS6EmHeN23O3OSwzMThMJ2B2RSCe\npzNRIha2Jig2jztJGgrvGZtn/RzD1HzhZ30MPj9Mk8fJd//HazhrpQzDCCEWRsP13LPJIm6vE7fH\naev9uXJFyFS7NYOlfSzPWNMBAFwvRQHw7njVaT9jMJHlXf/vET770Iv0KBevPqdbgl0IsaAaLtyt\n7fWqWJ06NkrW7WOgfGm60yYpzyE0oJ4/CoD3/EtnfP9PXxjiqs/9guf6E3zm6u24iprOlZWP0Qsh\nRC005LBMNXVlGI+TCYQZyBdxA5GCJu8epOgIUew7jjsEjtZTN6fOlww+/cN9fPmXh9naE+a2d51L\n03iJ78Gs1SCFEKLWGjLcw+32V3+5k+MUQi0M5It0KScOwOedwOFZS37gGN7uU8saHBpNc9M3nmLP\nQJJrL17LLVeeic/tZM++fmDmgmFCCDFfKhqWUUpdoZTar5TqU0rdcprjXqWUKiml3l67Js5NJlmw\nfTNVa41/IoFuiVh13A0wlUmLp0DAu5p8vIR3zSsrNn7v6eO89fO/oH88y13vPp9Pvm0bPrc13h8f\nzODyOAhFfFX/XEIIMRez9tyVUk7gduCNwHHgcaXUA1rrvdMc93fAj+ejoZUwTU1uomh/GmS6QHN+\nglxbhP58kR0FyIYT+B0QmQiAqfButvZPTedL/K/7n+e7T/VzwdoIt77jHHpbXvkvhlg0TWt3AOWQ\nujFCiIVVybDMBUCf1voggFLqPuAaYO9Jx90MfAc4/VSSeZSbKKI1touGDcYmCBUymB3tRPNF3pjW\nxFsOAxA4NkEG8O64gOf7E9z8L09zeCzNBy/fxAcv24hrmo1B4oNpes+Q8gJCiIVXSbivAI5NeXwc\nuHDqAUqpFcBvAb/BacJdKXU9cD3A6tWr59rWWU3Ocbd7Q3X46BA9aBwd7RS1piNRJO4/hAdw7h8C\npTmycie//cVfWSUErruIV29om/azCrkSE/G83EwVQiyKWk2FvBX4mNbaPN1BWuu7tNY7tdY7Ozo6\nanTql2WqLD0QK++dWuq0ArtzvEjSdxgThd47jCfs4OH+IgXD5Ds3XjxjsAPEo9YGHZVsii2EELVW\nSc+9H1g15fHK8nNT7QTuK+8t2g5cpZQqaa2/X5NWVqjanntq0Ar3TMRawNSV0wx6Bik6WigMJPH2\nhHmuP0FPs4+VraefAROfZWs9IYSYT5X03B8HNiml1imlPMA7gAemHqC1Xqe1Xqu1Xgv8K/A/FjrY\nwVqdCvbH3LND1urUaCgMQHdO4/Emcbo6KYwbeNau5PmBBNtXzL7aNB5N43Aqmjvmvyi/EEKcbNZw\n11qXgJuAB4EXgG9prfcopW5QSt0w3w2ci0yqgMOh8PrtTd8vjY4CcCQQxAuEiwZhT4FgJgBa4Thj\nK4dG02yvoFRvbDBDS5cfxzQ3WoUQYr5VlIJa613ArpOeu3OGY6+tvln2TG6MXR4emrt4nJLTzVHl\nptt0UPTH8Dg0zVHrVsLgiu3oo3DWyvDsHzWYpn2V/X1chRCiGg3VrcymqlvA5ErGyYeaGSgU6S5o\nEq3WJCH/wRQozZOhbQCz9txLRYPkaJbWHhlvF0IsjoYK90yyYHsBUyJbJJRNYbZErNIDGZPx4GHr\nxf1xPK1Onh0p0hny0hk+/YrT8aEsWstMGSHE4mmscK+i5z6YyNGSn0BFIgzli3QkSySbjmDgwOib\nwNvbwvP9Fd5MPTFTRsJdCLE4GibctdZkU0XbM2WiiRwt+RS0RTCBrrRBwTtIUbVQSmhca1dxYGSi\nonCPRdMoBS1dMlNGCLE4GibcizkDo2jaHpYZjGdoyU9Qapuc427i9iXw5AKAIrViI6aGsyrsuYfb\nm3C57W0YIoQQ1WqYcD+xOjVsb3XqWHQElzbJtZVXp+ZLBDw5AjHrEu3vKN9MXVHBTJlohlYZbxdC\nLKKGCfdslRtjJwasBUxjYSu82/QYTgWh4wWUQ/ML10bagx66Z7mZahom40MZIjJTRgixiBpms45s\nqrw61eYN1ezwMAAD/hABDSpoTYP0HJjA3ebi2WiWbb3Ns86hT4xkMQ0tN1OFEIuqYXruk8Mydnvu\nxdExAI4GQnQXYTx8GAC9P4enp5WXhicqG28vFwyTYRkhxGJqmHCfLBrms1kR0ozFADjg89OVNZnw\nH6WkXZhDUFixEsPUFY23x6RgmBCiDjRMuGeSBbwBF04btVxSuSL+dALtcNDn8tGZMsh7BzELfhSK\naOd6gIoLhgVbvXh8DTPiJYRYghom3LMp+6tTo+UFTEa4hRHDpCtn4mwax5uwAvrJ0BZa/W5WtMw+\nbz0+KDNlhBCLr2HCPZMs2F7ANJDI0ZpPYbS2AtCZK9LkztE0ZKKcmgeLK9i+YvabqdrUxKNpInIz\nVQixyBogIB8qAAAS4UlEQVQm3LOpou1NOqKJrLWAqRzubTqGUtB0JI+33c2+kWxFQzKpWI5SwZSC\nYUKIRddA4W6/5z5YLj2QL+/A1OIcBMDZV4DuVkqmrqiGu8yUEULUi4YId6Nkks+U8NtcnRodz9Ka\nnyDZ3AKA33cAAMcxB6nOFUBlZQcmZ8rIsIwQYrE1xJSO7ImNse313EdHE3iNIiPBMM0lKPgPUSq5\ncGQVL7auI+xwsSpSwc3UaJqmkBtf0N5fMkIIUSsN0XM/sTrVZrhnolbpgcFAiK6cSb5pEDVhBfR/\neDdVdDMVrIJhsjJVCFEPGiLcM5N1ZWzeUC2MWuF+rClIV8bE0RTHOwoOt+ZH6c6KbqZqrYlHM7JB\nhxCiLjRUuNvpuafzJTzJcQD6fAE680U87hxNxw3c7R4KZmWLlzLJAvlMSWbKCCHqQkOE+8tj7nMf\n644mczTnJwA4HgzRbiYA8Bw2KHZYUyMrreEOMlNGCFEfGiLcM6kCLo/D1pL/aHkBE0A8FCaCVUDM\n2a8YjvQQ9LpYE5m9Nx4btKZBykwZIUQ9aIhwr36O+wSlUBjD6aLZeRwA57Bid3AN23rDOBwV3EyN\npvE0ufA322uHEELUUmOEe7Jg+2bq4Li1OrXYUp7j7u2jlHXiKCp+wMaKxtvBCvfWbn9Fs2qEEGK+\nNUS4Z6rYGHswmaOjmCbTYo2v+70v4Yw5cHo1L7h6KhpvB2tYRmbKCCHqRUOEezZZwG+zjns0kSNS\nmGA83Ewkb+JuGsIb1TjavICqqIZ7Ll0kmyzIHHchRN1Y8uGuTU12omh7e73BRI5wLsVoIERXvoTL\nVcB71CTd1orf42Rde3DWz3h5poxMgxRC1IclH+65TBFtavulB2IpfPkMg/4QHSVrxos76uBouJtt\nvWGcFd1MLc+UkWEZIUSdWPLhnk1apQfs3FDNFQ10PA7AsUCINtNazOQaUvzavYptFVSCBKtgmMvt\nIBTxzbkNQggxH5Z8uGeqKBo2dY57NBSmjRG0BucY/MK/peKbqfFompZuP6qCXr4QQiyEJR/uk6tT\n7WyxNznHHSAeaibsOoZOOnB54Jinq+JpkDEpGCaEqDMVhbtS6gql1H6lVJ9S6pZpXv89pdRupdRz\nSqlfKaXOrn1Tp3eiroyNWu7RZJaWydWp4WaC7oO4h0FHvPjcDjZ0zB7YhVyJiVhextuFEHVl1nBX\nSjmB24Erga3AO5VSW0867BBwidb6LOBTwF21buhMsqkCyqHw+ece7lN77uOhMBHvQbz9EG9pYUtP\nGJdz9r/7xocmd1+SmTJCiPpRSc/9AqBPa31Qa10A7gOumXqA1vpXWut4+eEjwMraNnNm2WSBpqDb\n1nh3NJGj20hT8vkoeLxEnCO4o4r9TV2Vj7dP7r4kPXchRB2pJNxXAMemPD5efm4mfwj8sJpGzUUm\nZX+O+8B4ji4jSzrcQluhiBMT54jiqcD6OYy3Z3A4FOGO2XdqEkKIhVLTG6pKqd/ACvePzfD69Uqp\nJ5RST4yMjNTknNlUFatTk1naihOMh5rpMKzhGdeQ4tfBbRVtiA3WTJnmLj/OCoZwhBBioVSSSP3A\nqimPV5afewWl1A7gbuAarfXYdB+ktb5La71Ta72zo6PDTntPkU0VbPfco4kczbkUo8EwbeY42gBP\nQTPe1M6mrtlXpoI1UybSLePtQoj6Ukm4Pw5sUkqtU0p5gHcAD0w9QCm1Gvgu8G6t9Yu1b+bMMkl7\n5X7zJYPRiQL+TJKhUJiIGsIxpig1N7GlO4S7gp64UTRJjmRlgw4hRN2ZdXcLrXVJKXUT8CDgBO7R\nWu9RSt1Qfv1O4BNAG/DFcsnbktZ65/w121LIlSgVTFtz3IeTeRzaxDORYjTcTLPrOJ5BiIZaKh5v\nHx/OoLXMlBFC1J+Kti7SWu8Cdp303J1Tvr8OuK62TZtdNmWVHrDTcx9M5Ajn0yhtEg81s8a1G9ew\nYk+wZ06Ll0Bmyggh6s+Svgt4YnWqjTH3wUR2yurUMG2OYVxDimdCG+ZQdiADClo6pecuhKgvSzrc\nJ1en2gn3aCL3itWpbYzhGoEnwts5oytU0WfEB9OE25tweZxzPr8QQsynJR3u2RNFw+ytTu0xrNWl\nyVCIMAk8aUXXyhV4XJVdlnhUZsoIIepTg4S7vZ77KpUDQDW5cOQhr3wVD8mYhkl8KCMzZYQQdWlJ\nh3smWcTrd+GssKc91WAyR5eZoeRy4fdlcY04GApFKq7hnhzNYZa0VIMUQtSlJR3u2ZS9Oe4Ag+NZ\nOoppEsEwrc5hXFFNX2jFHDbElq31hBD1a0mHu7WAae7j7UXDZGQiT3PemuPe6uzHNQy7mzexubvC\nm6nR8jRI6bkLIerQkg73bKpga6bMcCqP1tCUThIPNdPGKM4Rxei6C/G5K5v5Eh/MEGjx4mmqaKmA\nEEIsqCUd7hmbwzLRRBYAT2r85WmQE7BhdU/FnxGPponIkIwQok4t2XA3DJN8umRzAVMOtMadTBAP\nNRNhlELez1krKxtv16YmFs3IzVQhRN1asuGeq6L0QDSRI1jM4igVGQ+F6cjEGfa0V1x2YGI8Tylv\nyDRIIUTdWrLhnqlyY+xu0xqaSYYCtIxk6QuvZEt3uKL3v1xTRoZlhBD1acmGezZpf3VqNJFjvSsP\ngBlSuKImgyvPpqnCMgLxE9MgpecuhKhPSzfcJ1en2iwatrq8OpVwEeewid766orfHx9M4wu6aQra\nm2MvhBDzbcmGeyZpjbnbGZaJThmWcYVyMKHYsqar4vfHoxkp8yuEqGtLNtyzqQJOtwO3b24VGQ1T\nM5TK016cwFCKpmCGYq6p4pupWmtig2lapWCYEKKOLdlwt+a4uynv/FSxkVQew9QEskkSwRCtjjFG\nix1s7ansZmo2VSSfKcl4uxCiri3ZcM8mCzZnyljDMd7kOOOhZjoyCUbaziDgrWylaf+LcUDKDggh\n6tuSDfeMjdIDWmu+/uhRANwT1gKmrtg46U2Vbfc6cizFf3xtH20rAvRsrGwYRwghFsOSDfdscu6l\nBz79o33865PH+ePLN+FOWqUHOqJjhM6+eNb3Jsey/OC2Z/E2uXjrTWfL7ktCiLq2JMNda002VZzT\nNMi7Hj7Al35+kPe8eg0fesMmPIk4qZAf71iCbWs6TvveXLrID257llLR5K03n02w1VftjyCEEPNq\nSYZ7PlPCNHXFY+7ffuIYf7NrH2/d0cMnr96GzmZxF/IUQk4KGS/beme+mVoqGuy6YzeJ0SxX3XgW\nbb3BWv0YQggxb5ZkuL+8gGn21ak/2TvELd99jtdtaucff+ccHA5FKRYDwAhDWncQ8k3/OdrUPHTP\nXgb7Erzh2q2sOKO1dj+EEELMoyVZjDyTrGzv1EcPjvGBbzzF9hXN3Pn755/Y+NoYHbUOCBnkMmdP\n+16tNf/1ry9x4OkRXvP2jWzaWfkiJyGEWGxLtOc+++rUPQMJrrv3CVa1NvHla1/1iqmOEwNDAHi8\nBo7tr5v2/c88dIzdPzvO2Zet4pw3rK5h64UQYv4tyXCfred+ZCzNe+95nJDPxT//4YVEAq88buzI\noPV+VaD3/Nec8v6XHh/iV9/pY8N5nbzm7Rtr3HohhJh/SzLcs6kCSoEveOpY+XAyx+//06MYpslX\n//BCeluaTjkm3l8O92Kabasir3itf3+ch+7dS8/GZt7wvi0ox9xWwAohRD1YmmPuqQK+oBvHScGb\nyBZ5zz2PMTZR4Bvvv4iNndPPbEkN9+Nq8hOciNHc9PJfEGP9E+y68zma25u46sYduCrcT1UIIerN\n0uy5J09dnZotGFx37+McGJngrnfv5JxVLTO+vzQ+QizUjD9bOvHcRDzHD77wLC6Pg6s/eA6+wNzr\nxAshRL1YmuF+0sbYRcPkpm88xRNH4tz6u+fy2k3tp32/M5UkGQ7gb94CQD5b4gdfeJZ8tsTVN59N\nKCKLlIQQS9uSDPdMqngi3E1T87Hv7Oan+4b51DXbecuOnlnf702nyYZ8tJ/9mxhFkx/euZv4YIYr\n/+gs2leG5rv5Qggx75ZkuE9WhNRa8ze7XuC7T/XzJ288g9+/aM2s79VaE5hIUwi42Xj+xfz0qy/Q\nv3+cy967hVVbIrO+XwghloKKwl0pdYVSar9Sqk8pdcs0ryul1OfLr+9WSp1X+6ZaigWDYt6gKezm\njp8f4O7/OsS1F6/l5ssqm7JoxDMEMxmMJif7H+rnpceHuOg317P5wu75arIQQiy4WWfLKKWcwO3A\nG4HjwONKqQe01nunHHYlsKn8dSFwR/nPmpvcGPu50Qn+/vkjvO3sXj7x1q0zbtqhTY05UcBIFDCS\neYZ2vwSA6fXw9E+Osv2SFZz35tl7/EIIsZRUMhXyAqBPa30QQCl1H3ANMDXcrwG+qrXWwCNKqRal\nVI/WerDWDc6U68r88zPHeP3mNv720k0UDoxjJK3wtkK8/H2ygJkqgH75/UfNvXQAhrON9We387rf\nPWPOuzkJIUS9qyTcVwDHpjw+zqm98umOWQHUPNy/9qn34ch38vbhYzj6cnzt3+f2focJBzb0khx+\nksfGn+KxG2vdQiGEOD2H3+QTn/3ZvJ5jQRcxKaWuB64HWL3aXr0W02HgMiYoOYsom7eDsw4oyDR2\nIUQDqyTc+4FVUx6vLD8312PQWt8F3AWwc+dOffLrlfjo3ffbeZsQQiwrlfR9Hwc2KaXWKaU8wDuA\nB0465gHgPeVZMxcBifkYbxdCCFGZWXvuWuuSUuom4EHACdyjtd6jlLqh/PqdwC7gKqAPyADvm78m\nCyGEmE1FY+5a611YAT71uTunfK+BD9S2aUIIIexakitUhRBCnJ6EuxBCNCAJdyGEaEAS7kII0YAk\n3IUQogEpa6LLIpxYqRHgiM23twOjNWxOrdV7+6D+2yjtq460rzr13L41WuuO2Q5atHCvhlLqCa31\nzsVux0zqvX1Q/22U9lVH2ledem9fJWRYRgghGpCEuxBCNKClGu53LXYDZlHv7YP6b6O0rzrSvurU\ne/tmtSTH3IUQQpzeUu25CyGEOI26Dvd62ph7mnOvUkr9h1Jqr1Jqj1Lqj6c55lKlVEIp9Uz56xML\n1b7y+Q8rpZ4rn/uJaV5fzOu3ecp1eUYplVRKfeikYxb8+iml7lFKDSulnp/yXEQp9ROl1EvlP1tn\neO9pf1/nsX2fUUrtK/83/J5SqmWG957292Ee2/dJpVT/lP+OV83w3sW6ft+c0rbDSqlnZnjvvF+/\nmtJa1+UXVnnhA8B6wAM8C2w96ZirgB8CCrgIeHQB29cDnFf+PgS8OE37LgV+sIjX8DDQfprXF+36\nTfPfOoo1f3dRrx/weuA84Pkpz/09cEv5+1uAv5vhZzjt7+s8tu9NgKv8/d9N175Kfh/msX2fBP6s\ngt+BRbl+J73+D8AnFuv61fKrnnvuJzbm1loXgMmNuac6sTG31voRoEUp1bMQjdNaD2qtnyp/nwJe\nwNo3dilZtOt3ksuBA1pru4vaakZr/TAQO+npa4B7y9/fC/zmNG+t5Pd1Xtqntf6x1rpUfvgI1k5o\ni2KG61eJRbt+k5RSCvgd4F9qfd7FUM/hPtOm23M9Zt4ppdYC5wKPTvPyxeV/Lv9QKbVtQRsGGnhI\nKfVkef/ak9XF9cPa3Wum/6EW8/pN6tIv7ywWBbqmOaZeruUfYP1rbDqz/T7Mp5vL/x3vmWFYqx6u\n3+uAIa31SzO8vpjXb87qOdyXBKVUEPgO8CGtdfKkl58CVmutdwC3Ad9f4Oa9Vmt9DnAl8AGl1OsX\n+PyzUtbWjW8Dvj3Ny4t9/U6hrX+f1+UUM6XUx4ES8PUZDlms34c7sIZbzgEGsYY+6tE7OX2vve7/\nf5qqnsO9ZhtzzxellBsr2L+utf7uya9rrZNa64ny97sAt1KqfaHap7XuL/85DHwP65++Uy3q9Su7\nEnhKaz108guLff2mGJocrir/OTzNMYv9u3gt8Fbg98p/AZ2igt+HeaG1HtJaG1prE/h/M5x3sa+f\nC/ht4JszHbNY18+ueg73ut6Yuzw+90/AC1rrf5zhmO7ycSilLsC63mML1L6AUio0+T3WTbfnTzqs\nHjY2n7G3tJjX7yQPAO8tf/9e4P5pjqnk93VeKKWuAD4KvE1rnZnhmEp+H+arfVPv4/zWDOddtOtX\n9gZgn9b6+HQvLub1s22x7+ie7gtrNseLWHfRP15+7gbghvL3Cri9/PpzwM4FbNtrsf55vht4pvx1\n1UntuwnYg3Xn/xHg4gVs3/ryeZ8tt6Gurl/5/AGssG6e8tyiXj+sv2gGgSLWuO8fAm3AT4GXgIeA\nSPnYXmDX6X5fF6h9fVjj1ZO/h3ee3L6Zfh8WqH3/XP792o0V2D31dP3Kz39l8vduyrELfv1q+SUr\nVIUQogHV87CMEEIImyTchRCiAUm4CyFEA5JwF0KIBiThLoQQDUjCXQghGpCEuxBCNCAJdyGEaED/\nHxVoOKkh6BgZAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1fcffcf4518>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def policy_iteration(mdp, gamma, nIt, grade_print=print):\n",
    "    Vs = []\n",
    "    pis = []\n",
    "    pi_prev = np.zeros(mdp.nS,dtype='int')\n",
    "    pis.append(pi_prev)\n",
    "    grade_print(\"Iteration | # chg actions | V[0]\")\n",
    "    grade_print(\"----------+---------------+---------\")\n",
    "    pi = np.zeros(mdp.nS)\n",
    "    for it in range(nIt):        \n",
    "        # YOUR CODE HERE\n",
    "        # you need to compute qpi which is the state-action values for current pi\n",
    "        \n",
    "        vpi = compute_vpi(pi, mdp, gamma)\n",
    "        qpi = compute_qpi(vpi, mdp, gamma)\n",
    "        pi = qpi.argmax(axis=1)\n",
    "        grade_print(\"%4i      | %6i        | %6.5f\"%(it, (pi != pi_prev).sum(), vpi[0]))\n",
    "        Vs.append(vpi)\n",
    "        pis.append(pi)\n",
    "        pi_prev = pi\n",
    "    return Vs, pis\n",
    "\n",
    "expected_output = \"\"\"Iteration | # chg actions | V[0]\n",
    "----------+---------------+---------\n",
    "   0      |      1        | -0.00000\n",
    "   1      |      9        | 0.00000\n",
    "   2      |      2        | 0.39785\n",
    "   3      |      1        | 0.45546\n",
    "   4      |      0        | 0.53118\n",
    "   5      |      0        | 0.53118\n",
    "   6      |      0        | 0.53118\n",
    "   7      |      0        | 0.53118\n",
    "   8      |      0        | 0.53118\n",
    "   9      |      0        | 0.53118\n",
    "  10      |      0        | 0.53118\n",
    "  11      |      0        | 0.53118\n",
    "  12      |      0        | 0.53118\n",
    "  13      |      0        | 0.53118\n",
    "  14      |      0        | 0.53118\n",
    "  15      |      0        | 0.53118\n",
    "  16      |      0        | 0.53118\n",
    "  17      |      0        | 0.53118\n",
    "  18      |      0        | 0.53118\n",
    "  19      |      0        | 0.53118\"\"\"\n",
    "\n",
    "Vs_PI, pis_PI = policy_iteration(mdp, gamma=0.95, nIt=20, grade_print=make_grader(expected_output))\n",
    "plt.plot(Vs_PI);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "117px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}