1_MDP_Review-solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_1",
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "# Assignment 1: Markov Decision Processes\n",
    "\n",
    "\n",
    "<br />\n",
    "<div class=\"alert alert-warning\">\n",
    "All your answers should be written inside this notebook.\n",
    "Look for four instances of \"YOUR CODE HERE\".\n",
    "If you want to clear all variables from the current session, follow these steps:\n",
    "<br/>1. Find the ``Kernel`` menu (on top) and click ``Kernel - Restart`` and choose ``Clear all Outputs and Restart``.\n",
    "<br/>2. Find the ``Cell`` menu (on top) and click ``Cell - Run`` All to re-run all of your code in order\"\n",
    "</div>\n",
    "<div class=\"alert alert-danger\">\n",
    "Before turning in the homework, you should check that your code works when this notebook is run in order from a clean start. To do so, please clear and re-run the notebook as described above.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_2",
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "\n",
    "This assignment will review exact methods for solving Markov Decision Processes (MDPs) with finite state and action spaces.\n",
    "We will implement value iteration (VI) and policy iteration (PI) for a finite MDP, both of which find the optimal policy in a finite number of iterations.\n",
    "\n",
    "For this assignment, we will consider discounted infinite-horizon MDPs. Recall that the MDP is defined by the tuple $(S, A, R, P, \\rho, \\gamma)$, where\n",
    "\n",
    "- S: state space (set)\n",
    "- A: action space (set)\n",
    "- R(s,a,s'): reward function, $S \\times A \\times S \\rightarrow \\mathbb{R}$, where $s$ is current state and $s'$ is next state \n",
    "- P(s,a,s'): transition probability distribution $Pr(s' | s, a)$, $S \\times A \\times S \\rightarrow \\mathbb{R}$\n",
    "- $\\rho(s)$: initial state distribution, $S \\rightarrow \\mathbb{R}$\n",
    "- $\\gamma$: discount $\\in (0,1)$\n",
    "\n",
    "Here we will consider MDPs where $S,A$ are finite sets, hence $R$ and $P$ are 3D arrays.\n",
    "\n",
    "We'll randomly generate an MDP which your algorithms should be able to solve.\n",
    "Using randomly generated MDPs is a bit dry, but it emphasizes that policy iteration can be expressed with a few array operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "init_1",
     "locked": false,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np, numpy.random as nr\n",
    "import hw_utils"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "4",
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "## Part 1: Value Iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "gen_mdp",
     "locked": true,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "nr.seed(0) # seed random number generator\n",
    "nS = 10\n",
    "nA = 2\n",
    "# nS: number of states\n",
    "# nA: number of actions\n",
    "R_rand = nr.rand(nS, nA, nS) # reward function\n",
    "# R[i,j,k] := R(s=i, a=j, s'=k), \n",
    "# i.e., the dimensions are (current state, action, next state)\n",
    "P_rand = nr.rand(nS, nA, nS) \n",
    "# P[i,j,k] := P(s'=k | s=i, a=j)\n",
    "# i.e., dimensions are (current state, action, next state)\n",
    "\n",
    "P_rand /= P_rand.sum(axis=2,keepdims=True) # normalize conditional probabilities\n",
    "gamma = 0.90"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "<div class=\"alert alert-danger\">\n",
    "Be careful that you don't mix up the 0th and 2nd dimension of R and P--here we follow the convention that the axes correspond to s,a,s', not s',a,s.\n",
    "</div>\n",
    "\n",
    "\n",
    "### Problem 1a: implement value iteration update\n",
    "You'll implement the Bellman backup operator value operator, called `vstar_backup` below. It should compute $V^{(n+1)}$, defined as\n",
    "$$V^{(n+1)}(s) = \\max_a \\sum_{s'} P(s,a,s') [ R(s,a,s') + \\gamma V^{(n)}(s')]$$\n",
    "\n",
    "This update is often called a **backup**, since we are updating the state $s$ based on possible  future states $s'$, i.e., we are propagating the value function *backwards in time*, in a sense. \n",
    "The function is called **vstar**_backup because this update converges to the optimal value function, which is conventionally called $V^*$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "vstar_backup",
     "locked": false,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def vstar_backup(v_n, P_pan, R_pan, gamma):\n",
    "    \"\"\"\n",
    "    Apply Bellman backup operator V -> T[V], i.e., perform one step of value iteration\n",
    "    \n",
    "    :param v_n: the state-value function (1D array) for the previous iteration, i.e. V^(n).\n",
    "    :param P_pan: the transition function (3D array: S*A*S -> R)\n",
    "    :param R_pan: the reward function (3D array: S*A*S -> R)\n",
    "    :param gamma: the discount factor (scalar)\n",
    "    :return: a pair (v_p, a_p), where v_p is the updated state-value function and should be a 1D array (S -> R),\n",
    "    and a_p is the updated (deterministic) policy, which should also be a 1D array (S -> A)\n",
    "\n",
    "    We're using the subscript letters to label the axes\n",
    "    E.g., \"pan\" refers to \"Previous state\", \"Action\", \"Next state\"\n",
    "    \n",
    "    \"\"\"\n",
    "    nS = P_pan.shape[0] # number of states\n",
    "    ### BEGIN SOLUTION\n",
    "    q_sa = np.sum(P_pan * R_pan + gamma * (P_pan * np.reshape(v_n, (1, 1, -1))), axis=2)\n",
    "    v_p = np.max(q_sa, axis=1)\n",
    "    a_p = np.argmax(q_sa, axis=1)\n",
    "    ### END SOLUTION\n",
    "    assert v_p.shape == (nS,)\n",
    "    assert a_p.shape == (nS,)\n",
    "    return (v_p, a_p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's test value iteration on a randomly generated MDP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "value_iteration",
     "locked": true,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         iter |  max|V-Vprev| | # chg actions |          V[0]\n",
      "-------------------------------------------------------------\n",
      "            1 |      0.707147 |           N/A |      0.618258\n",
      "            2 |      0.514599 |             1 |       1.13286\n",
      "            3 |      0.452404 |             0 |       1.58322\n",
      "            4 |      0.405723 |             0 |       1.98855\n",
      "            5 |      0.364829 |             0 |       2.35327\n",
      "            6 |      0.328307 |             0 |       2.68157\n",
      "            7 |      0.295474 |             0 |       2.97704\n",
      "            8 |      0.265926 |             0 |       3.24297\n",
      "            9 |      0.239333 |             0 |        3.4823\n",
      "           10 |        0.2154 |             0 |        3.6977\n",
      "           11 |       0.19386 |             0 |       3.89156\n",
      "           12 |      0.174474 |             0 |       4.06604\n",
      "           13 |      0.157026 |             0 |       4.22306\n",
      "           14 |      0.141324 |             0 |       4.36439\n",
      "           15 |      0.127191 |             0 |       4.49158\n",
      "           16 |      0.114472 |             0 |       4.60605\n",
      "           17 |      0.103025 |             0 |       4.70908\n",
      "           18 |     0.0927225 |             0 |        4.8018\n",
      "           19 |     0.0834503 |             0 |       4.88525\n",
      "           20 |     0.0751053 |             0 |       4.96035\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(array([ 4.96035322,  4.94026426,  4.76583539,  4.75638532,  4.77191448,\n",
       "         5.02720043,  4.84790383,  5.01408695,  4.88751565,  4.85806614]),\n",
       " array([1, 0, 0, 1, 0, 1, 1, 0, 0, 0]),\n",
       " ['N/A', 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# DO NOT CHANGE THIS PART!\n",
    "\n",
    "def value_iteration(P, R, gamma, n_iter, verbose=False):\n",
    "    nS = P.shape[0]\n",
    "    Vprev = np.zeros(nS)\n",
    "    Aprev = None\n",
    "    chg_actions_seq = []\n",
    "    if verbose:\n",
    "        print(hw_utils.fmt_row(13, [\"iter\", \"max|V-Vprev|\", \"# chg actions\", \"V[0]\"], header=True))\n",
    "    for i in range(n_iter):\n",
    "        V, A = vstar_backup(Vprev, P, R, gamma)\n",
    "        chg_actions = \"N/A\" if Aprev is None else (A != Aprev).sum()\n",
    "        chg_actions_seq.append(chg_actions)\n",
    "        if verbose:\n",
    "            print(hw_utils.fmt_row(13, [i+1, np.abs(V-Vprev).max(), chg_actions, V[0]]))\n",
    "        Vprev, Aprev = V, A\n",
    "    return V, A, chg_actions_seq\n",
    "        \n",
    "value_iteration(P_rand, R_rand, gamma, n_iter=20, verbose=True);\n",
    "\n",
    "# Expected output:\n",
    "#          iter |  max|V-Vprev| | # chg actions |          V[0]\n",
    "# -------------------------------------------------------------\n",
    "#             1 |      0.707147 |           N/A |      0.618258\n",
    "#             2 |      0.514599 |             1 |       1.13286\n",
    "#             3 |      0.452404 |             0 |       1.58322\n",
    "#             4 |      0.405723 |             0 |       1.98855\n",
    "#             5 |      0.364829 |             0 |       2.35327\n",
    "#             6 |      0.328307 |             0 |       2.68157\n",
    "#             7 |      0.295474 |             0 |       2.97704\n",
    "#             8 |      0.265926 |             0 |       3.24297\n",
    "#             9 |      0.239333 |             0 |        3.4823\n",
    "#            10 |        0.2154 |             0 |        3.6977\n",
    "#            11 |       0.19386 |             0 |       3.89156\n",
    "#            12 |      0.174474 |             0 |       4.06604\n",
    "#            13 |      0.157026 |             0 |       4.22306\n",
    "#            14 |      0.141324 |             0 |       4.36439\n",
    "#            15 |      0.127191 |             0 |       4.49158\n",
    "#            16 |      0.114472 |             0 |       4.60605\n",
    "#            17 |      0.103025 |             0 |       4.70908\n",
    "#            18 |     0.0927225 |             0 |        4.8018\n",
    "#            19 |     0.0834503 |             0 |       4.88525\n",
    "#            20 |     0.0751053 |             0 |       4.96035"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You'll notice that value iteration only takes two iterations to converge to the right actions everywhere. (However, note that the actual values converge rather slowly.) That's because most randomly generated MDPs aren't very interesting.\n",
    "Also, note that the value of any particular state (e.g., V[0], shown in the rightmost column) increases monotonically. Under which conditions is that true? [question will not be graded]\n",
    "\n",
    "### Problem 1b: create an MDP such for which value iteration takes a long time to converge\n",
    "Specifically, the requirement is that your MDP should have 10 states and 2 actions, and the policy should be updated for each of the first 10 iterations.\n",
    "\n",
    "Here's a hint for one solution: arrange the states on a line, so that state `i` can only transition to one of `{i-1, i, i+1}`.\n",
    "You should create 3D arrays P,R in `hw1.py` that define the MDP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "slow_mdp",
     "locked": false,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         iter |  max|V-Vprev| | # chg actions |          V[0]\n",
      "-------------------------------------------------------------\n",
      "            1 |           100 |           N/A |             0\n",
      "            2 |            90 |             2 |             0\n",
      "            3 |            81 |             1 |             0\n",
      "            4 |          72.9 |             1 |             0\n",
      "            5 |         65.61 |             1 |             0\n",
      "            6 |        59.049 |             1 |             0\n",
      "            7 |       53.1441 |             1 |             0\n",
      "            8 |       47.8297 |             1 |             0\n",
      "            9 |       43.0467 |             1 |             0\n",
      "           10 |        38.742 |             1 |       32.6163\n",
      "           11 |       34.8678 |             0 |       67.4841\n",
      "           12 |       31.3811 |             0 |       98.8652\n",
      "           13 |        28.243 |             0 |       127.108\n",
      "           14 |       25.4187 |             0 |       152.527\n",
      "           15 |       22.8768 |             0 |       175.404\n",
      "           16 |       20.5891 |             0 |       195.993\n",
      "           17 |       18.5302 |             0 |       214.523\n",
      "           18 |       16.6772 |             0 |         231.2\n",
      "           19 |       15.0095 |             0 |        246.21\n",
      "           20 |       13.5085 |             0 |       259.718\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(array([ 259.7180393 ,  303.19522751,  351.50321441,  405.17875541,\n",
       "         464.81824541,  531.08434541,  604.71334541,  686.52334541,\n",
       "         777.42334541,  878.42334541]),\n",
       " array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),\n",
       " ['N/A', 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pslow = np.zeros((10, 2, 10)) # YOUR CODE SHOULD FILL IN THE VALUES OF Pslow\n",
    "Rslow = np.zeros((10, 2, 10)) # YOUR CODE SHOULD FILL IN THE VALUES OF Rslow\n",
    "\n",
    "# Problem 1b\n",
    "\n",
    "### BEGIN SOLUTION\n",
    "for i in range(10):\n",
    "    Pslow[i, 0, max(i-1, 0)] = 1\n",
    "    Pslow[i, 1, min(i+1, 9)] = 1\n",
    "Rslow = np.zeros((10,2,10))\n",
    "Rslow[:, 1, :] = -1\n",
    "Rslow[9, :, :] = 100\n",
    "### END SOLUTION\n",
    "\n",
    "assert Pslow.shape == (10,2,10), \"P has the wrong shape\"\n",
    "assert Rslow.shape == (10,2,10), \"R has the wrong shape\"\n",
    "assert np.allclose(Pslow.sum(axis=2), np.ones((10,2))), \"Transition probabilities should sum to 1\"\n",
    "\n",
    "value_iteration(Pslow, Rslow, gamma, n_iter=20, verbose=True);\n",
    "\n",
    "# The first 10 rows of the third column of the output should be something like\n",
    "# # chg actions\n",
    "# -------------\n",
    "#           N/A\n",
    "#             2\n",
    "#             1\n",
    "#             1\n",
    "#             1\n",
    "#             1\n",
    "#             1\n",
    "#             1\n",
    "#             1\n",
    "#             1\n",
    "# The actual numbers can differ, as long as they are > 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Policy Iteration\n",
    "\n",
    "The next task is to implement exact policy iteration (PI).\n",
    "\n",
    "PI first initializes the policy $\\pi_0(s)$, and then it performs the following two steps on the $n$th iteration:\n",
    "1. Compute state-action value function $Q^{\\pi_{n-1}}(s,a)$ of policy $\\pi_{n-1}$\n",
    "2. Compute new policy $\\pi_n(s) = \\operatorname*{argmax}_a Q^{\\pi_{n-1}}(s,a)$\n",
    "\n",
    "We'll break step 1 into two parts.\n",
    "\n",
    "### Problem 2a: state value function\n",
    "\n",
    "First 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",
    "You'll have to solve a linear system in your code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "compute_vpi",
     "locked": false,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 5.206217  ,  5.15900351,  5.01725926,  4.76913715,  5.03154609,\n",
       "        5.06171323,  4.97964471,  5.28555573,  5.13320501,  5.08988046])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def compute_vpi(pi, P, R, gamma):\n",
    "    \"\"\"\n",
    "    :param pi: a deterministic policy (1D array: S -> A)\n",
    "    :param P: the transition probabilities (3D array: S*A*S -> R)\n",
    "    :param R: the reward function (3D array: S*A*S -> R)\n",
    "    :param gamma: the discount factor (scalar)\n",
    "    :return: vpi, the state-value function for the policy pi\n",
    "    \"\"\"\n",
    "    nS = P.shape[0]\n",
    "    ### BEGIN SOLUTION\n",
    "    Ppi = P[np.arange(nS), pi]\n",
    "    Rpi = R[np.arange(nS), pi]\n",
    "    b = np.sum(Ppi * Rpi, axis=1)\n",
    "    a = np.eye(nS) - gamma * Ppi\n",
    "    vpi = np.linalg.solve(a, b)\n",
    "    ### END SOLUTION\n",
    "    assert vpi.shape == (nS,)\n",
    "    return vpi\n",
    "\n",
    "\n",
    "pi0 = np.zeros(nS,dtype='i')\n",
    "compute_vpi(pi0, P_rand, R_rand, gamma)\n",
    "\n",
    "# Expected output:\n",
    "# array([ 5.206217  ,  5.15900351,  5.01725926,  4.76913715,  5.03154609,\n",
    "#         5.06171323,  4.97964471,  5.28555573,  5.13320501,  5.08988046])"
   ]
  },
  {
   "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": 7,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "compute_qpi",
     "locked": false,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5.206217  ,  5.20238706],\n",
       "       [ 5.15900351,  5.1664316 ],\n",
       "       [ 5.01725926,  4.99211906],\n",
       "       [ 4.76913715,  4.98080235],\n",
       "       [ 5.03154609,  4.89448888],\n",
       "       [ 5.06171323,  5.29418621],\n",
       "       [ 4.97964471,  5.06868986],\n",
       "       [ 5.28555573,  4.9156956 ],\n",
       "       [ 5.13320501,  4.97736801],\n",
       "       [ 5.08988046,  5.00511597]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def compute_qpi(vpi, pi, P, R, gamma):\n",
    "    \"\"\"\n",
    "    :param pi: a deterministic policy (1D array: S -> A)\n",
    "    :param T: the transition function (3D array: S*A*S -> R)\n",
    "    :param R: the reward function (3D array: S*A*S -> R)\n",
    "    :param gamma: the discount factor (scalar)\n",
    "    :return: qpi, the state-action-value function for the policy pi\n",
    "    \"\"\"\n",
    "    nS = P.shape[0]\n",
    "    nA = P.shape[1]\n",
    "    ### BEGIN SOLUTION\n",
    "    qpi = np.sum(P * (R + gamma * vpi.reshape((1, 1, -1))), axis=2)\n",
    "    ### END SOLUTION\n",
    "    assert qpi.shape == (nS, nA)\n",
    "    return qpi\n",
    "\n",
    "vpi = compute_vpi(pi0, P_rand, R_rand, gamma)\n",
    "compute_qpi(vpi, pi0, P_rand, R_rand, gamma)\n",
    "\n",
    "# Expected output:\n",
    "# array([[ 5.206217  ,  5.20238706],\n",
    "#        [ 5.15900351,  5.1664316 ],\n",
    "#        [ 5.01725926,  4.99211906],\n",
    "#        [ 4.76913715,  4.98080235],\n",
    "#        [ 5.03154609,  4.89448888],\n",
    "#        [ 5.06171323,  5.29418621],\n",
    "#        [ 4.97964471,  5.06868986],\n",
    "#        [ 5.28555573,  4.9156956 ],\n",
    "#        [ 5.13320501,  4.97736801],\n",
    "#        [ 5.08988046,  5.00511597]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're ready to run policy iteration!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         iter | # chg actions |        Q[0,0]\n",
      "---------------------------------------------\n",
      "            1 |             4 |       5.20622\n",
      "            2 |             2 |       5.59042\n",
      "            3 |             0 |        5.6255\n",
      "            4 |             0 |        5.6255\n",
      "            5 |             0 |        5.6255\n",
      "            6 |             0 |        5.6255\n",
      "            7 |             0 |        5.6255\n",
      "            8 |             0 |        5.6255\n",
      "            9 |             0 |        5.6255\n",
      "           10 |             0 |        5.6255\n"
     ]
    }
   ],
   "source": [
    "def policy_iteration(P, R, gamma, n_iter):\n",
    "    pi_prev = np.zeros(P.shape[0],dtype='i')\n",
    "    \n",
    "    print(hw_utils.fmt_row(13, [\"iter\", \"# chg actions\", \"Q[0,0]\"], header=True))\n",
    "    \n",
    "    for i in range(n_iter):\n",
    "        vpi = compute_vpi(pi_prev, P_rand, R_rand, gamma)\n",
    "        qpi = compute_qpi(vpi, pi_prev, P, R, gamma)\n",
    "        pi = qpi.argmax(axis=1)\n",
    "        print(hw_utils.fmt_row(13, [i+1, (pi != pi_prev).sum(),  qpi[0,0]]))\n",
    "        pi_prev = pi\n",
    "        \n",
    "policy_iteration(P_rand, R_rand, gamma, 10);\n",
    "\n",
    "# Expected output:\n",
    "#          iter | # chg actions |        Q[0,0]\n",
    "# ---------------------------------------------\n",
    "#             1 |             4 |       5.20622\n",
    "#             2 |             2 |       5.59042\n",
    "#             3 |             0 |        5.6255\n",
    "#             4 |             0 |        5.6255\n",
    "#             5 |             0 |        5.6255\n",
    "#             6 |             0 |        5.6255\n",
    "#             7 |             0 |        5.6255\n",
    "#             8 |             0 |        5.6255\n",
    "#             9 |             0 |        5.6255\n",
    "#            10 |             0 |        5.6255"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "The following cells will just be used by instructors for grading. Please ignore them.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    import autograder\n",
    "    instructor=True\n",
    "except ImportError:\n",
    "    instructor=False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "value_iteration_test",
     "locked": true,
     "points": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Check that value iteration computes the correct result\"\"\"\n",
    "# INSTRUCTOR ONLY -- DO NOT CHANGE THIS PART\n",
    "if instructor: autograder.grade_value_iteration(value_iteration)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "slow_mdp_test",
     "locked": true,
     "points": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Check that Pslow and Rslow updates the policy for each of the first 10 iterations\"\"\"\n",
    "# INSTRUCTOR ONLY -- DO NOT CHANGE THIS PART\n",
    "if instructor: autograder.grade_slow_mdp(value_iteration, Pslow, Rslow, gamma)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "compute_vpi_test",
     "locked": true,
     "points": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Check that compute_vpi computes the correct result\"\"\"\n",
    "# INSTRUCTOR ONLY -- DO NOT CHANGE THIS PART\n",
    "if instructor: autograder.grade_compute_vpi(compute_vpi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "compute_qpi_test",
     "locked": true,
     "points": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Check that compute_qpi computes the correct result\"\"\"\n",
    "# INSTRUCTOR ONLY -- DO NOT CHANGE THIS PART\n",
    "if instructor: autograder.grade_compute_qpi(compute_qpi)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}