mdp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Markov decision processes (MDPs)\n",
    "\n",
    "This IPy notebook acts as supporting material for topics covered in **Chapter 17 Making Complex Decisions** of the book* Artificial Intelligence: A Modern Approach*. We makes use of the implementations in mdp.py module. This notebook also includes a brief summary of the main topics as a review. Let us import everything from the mdp module to get started."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from mdp import MDP, GridMDP, sequential_decision_environment, value_iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Review\n",
    "\n",
    "Before we start playing with the actual implementations let us review a couple of things about MDPs.\n",
    "\n",
    "- A stochastic process has the **Markov property** if the conditional probability distribution of future states of the process (conditional on both past and present states) depends only upon the present state, not on the sequence of events that preceded it.\n",
    "\n",
    "    -- Source: [Wikipedia](https://en.wikipedia.org/wiki/Markov_property)\n",
    "\n",
    "Often it is possible to model many different phenomena as a Markov process by being flexible with our definition of state.\n",
    "   \n",
    "\n",
    "- MDPs help us deal with fully-observable and non-deterministic/stochastic environments. For dealing with partially-observable and stochastic cases we make use of generalization of MDPs named POMDPs (partially observable Markov decision process).\n",
    "\n",
    "Our overall goal to solve a MDP is to come up with a policy which guides us to select the best action in each state so as to maximize the expected sum of future rewards."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MDP\n",
    "\n",
    "To begin with let us look at the implementation of MDP class defined in mdp.py The docstring tells us what all is required to define a MDP namely - set of states,actions, initial state, transition model, and a reward function. Each of these are implemented as methods. Do not close the popup so that you can follow along the description of code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%psource MDP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **_ _init_ _** method takes in the following parameters:\n",
    "\n",
    "- init: the initial state.\n",
    "- actlist: List of actions possible in each state.\n",
    "- terminals: List of terminal states where only possible action is exit\n",
    "- gamma: Discounting factor. This makes sure that delayed rewards have less value compared to immediate ones.\n",
    "\n",
    "**R** method returns the reward for each state by using the self.reward dict.\n",
    "\n",
    "**T** method is not implemented and is somewhat different from the text. Here we return (probability, s') pairs where s' belongs to list of possible state by taking action a in state s.\n",
    "\n",
    "**actions** method returns list of actions possible in each state. By default it returns all actions for states other than terminal states.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let us implement the simple MDP in the image below. States A, B have actions X, Y available in them. Their probabilities are shown just above the arrows. We start with using MDP as base class for our CustomMDP. Obviously we need to make a few changes to suit our case. We make use of a transition matrix as our transitions are not very simple.\n",
    "<img src=\"files/images/mdp-a.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Transition Matrix as nested dict. State -> Actions in state -> States by each action -> Probabilty\n",
    "t = {\n",
    "    \"A\": {\n",
    "            \"X\": {\"A\":0.3, \"B\":0.7},\n",
    "            \"Y\": {\"A\":1.0}\n",
    "         },\n",
    "    \"B\": {\n",
    "            \"X\": {\"End\":0.8, \"B\":0.2},\n",
    "            \"Y\": {\"A\":1.0}\n",
    "         },\n",
    "    \"End\": {}\n",
    "}\n",
    "\n",
    "init = \"A\"\n",
    "\n",
    "terminals = [\"End\"]\n",
    "\n",
    "rewards = {\n",
    "    \"A\": 5,\n",
    "    \"B\": -10,\n",
    "    \"End\": 100\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class CustomMDP(MDP):\n",
    "\n",
    "    def __init__(self, transition_matrix, rewards, terminals, init, gamma=.9):\n",
    "        # All possible actions.\n",
    "        actlist = []\n",
    "        for state in transition_matrix.keys():\n",
    "            actlist.extend(transition_matrix.keys())\n",
    "        actlist = list(set(actlist))\n",
    "\n",
    "        MDP.__init__(self, init, actlist, terminals=terminals, gamma=gamma)\n",
    "        self.t = transition_matrix\n",
    "        self.reward = rewards\n",
    "        for state in self.t:\n",
    "            self.states.add(state)\n",
    "\n",
    "    def T(self, state, action):\n",
    "        return [(new_state, prob) for new_state, prob in self.t[state][action].items()]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally we instantize the class with the parameters for our MDP in the picture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "our_mdp = CustomMDP(t, rewards, terminals, init, gamma=.9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this we have sucessfully represented our MDP. Later we will look at ways to solve this MDP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grid MDP\n",
    "\n",
    "Now we look at a concrete implementation that makes use of the MDP as base class. The GridMDP class in the mdp module is used to represent a grid world MDP like the one shown in  in **Fig 17.1** of the AIMA Book. The code should be easy to understand if you have gone through the CustomMDP example.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource GridMDP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **_ _init_ _** method takes **grid** as an extra parameter compared to the MDP class. The grid is a nested list of rewards in states.\n",
    "\n",
    "**go** method returns the state by going in particular direction by using vector_add.\n",
    "\n",
    "**T** method is not implemented and is somewhat different from the text. Here we return (probability, s') pairs where s' belongs to list of possible state by taking action a in state s.\n",
    "\n",
    "**actions** method returns list of actions possible in each state. By default it returns all actions for states other than terminal states.\n",
    "\n",
    "**to_arrows** are used for representing the policy in a grid like format."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create a GridMDP like the one in **Fig 17.1** as follows: \n",
    "\n",
    "    GridMDP([[-0.04, -0.04, -0.04, +1],\n",
    "            [-0.04, None,  -0.04, -1],\n",
    "            [-0.04, -0.04, -0.04, -0.04]],\n",
    "            terminals=[(3, 2), (3, 1)])\n",
    "            \n",
    "In fact the **sequential_decision_environment** in mdp module has been instantized using the exact same code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<mdp.GridMDP at 0x1040162b0>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_decision_environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Value Iteration\n",
    "\n",
    "Now that we have looked how to represent MDPs. Let's aim at solving them. Our ultimate goal is to obtain an optimal policy. We start with looking at Value Iteration and a visualisation that should help us understanding it better.\n",
    "\n",
    "We start by calculating Value/Utility for each of the states. The Value of each state is the expected sum of discounted future rewards given we start in that state and follow a particular policy pi.The algorithm Value Iteration (**Fig. 17.4** in the book) relies on finding solutions of the Bellman's Equation. The intuition Value Iteration works is because values propagate. This point will we more clear after we encounter the visualisation. For more information you can refer to **Section 17.2** of the book. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%psource value_iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It takes as inputs two parameters an MDP to solve and epsilon the maximum error allowed in the utility of any state. It returns a dictionary containing utilities where the keys are the states and values represent utilities. Let us solve the **sequencial_decision_enviornment** GridMDP.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 0): 0.2962883154554812,\n",
       " (0, 1): 0.3984432178350045,\n",
       " (0, 2): 0.5093943765842497,\n",
       " (1, 0): 0.25386699846479516,\n",
       " (1, 2): 0.649585681261095,\n",
       " (2, 0): 0.3447542300124158,\n",
       " (2, 1): 0.48644001739269643,\n",
       " (2, 2): 0.7953620878466678,\n",
       " (3, 0): 0.12987274656746342,\n",
       " (3, 1): -1.0,\n",
       " (3, 2): 1.0}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value_iteration(sequential_decision_environment)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To illustrate that values propagate out of states let us create a simple visualisation. We will be using a modified version of the value_iteration function which will store U over time. We will also remove the parameter epsilon and instead add the number of iterations we want."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def value_iteration_instru(mdp, iterations=20):\n",
    "    U_over_time = []\n",
    "    U1 = {s: 0 for s in mdp.states}\n",
    "    R, T, gamma = mdp.R, mdp.T, mdp.gamma\n",
    "    for _ in range(iterations):\n",
    "        U = U1.copy()\n",
    "        for s in mdp.states:\n",
    "            U1[s] = R(s) + gamma * max([sum([p * U[s1] for (p, s1) in T(s, a)])\n",
    "                                        for a in mdp.actions(s)])\n",
    "        U_over_time.append(U)\n",
    "    return U_over_time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we define a function to create the visualisation from the utilities returned by **value_iteration_instru**. The reader need not concern himself with the code that immediately follows as it is the usage of Matplotib with IPython Widgets. If you are interested in reading more about these visit [ipywidgets.readthedocs.io](http://ipywidgets.readthedocs.io)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "columns = 4\n",
    "rows = 3\n",
    "U_over_time = value_iteration_instru(sequential_decision_environment)\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def plot_grid(iteration):\n",
    "    data = U_over_time[iteration]\n",
    "    grid = []\n",
    "    for row in range(rows):\n",
    "        current_row = []\n",
    "        for column in range(columns):\n",
    "            try:\n",
    "                current_row.append(data[(column, row)])\n",
    "            except KeyError:\n",
    "                current_row.append(0)\n",
    "        grid.append(current_row)\n",
    "    grid.reverse() # output like book\n",
    "    fig = plt.matshow(grid, cmap=plt.cm.bwr);\n",
    "    plt.axis('off')\n",
    "    fig.axes.get_xaxis().set_visible(False)\n",
    "    fig.axes.get_yaxis().set_visible(False) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAATgAAADtCAYAAAAr+2lCAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAAzZJREFUeJzt2rENwzAMAEExyP4r0wsE6Qwbj7uSalg9WGh29wAUfZ5e\nAOAuAgdkCRyQJXBAlsABWQIHZH3/Pc4cf0iA19s982vuggOyBA7IEjggS+CALIEDsgQOyBI4IEvg\ngCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOy\nBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4\nIEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAs\ngQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQO\nyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL\n4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIED\nsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgS\nOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CA\nLIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IE\nDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjgg\nS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyB\nA7IEDsgSOCBL4IAsgQOyBA7IEjggS+CALIEDsgQOyBI4IEvggCyBA7IEDsgSOCBL4IAsgQOyBA7I\nEjggS+CALIEDsgQOyJrdfXoHgFu44IAsgQOyBA7IEjggS+CALIEDsi6WyArVfE1QKgAAAABJRU5E\nrkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x104040b38>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import ipywidgets as widgets\n",
    "from IPython.display import display\n",
    "\n",
    "iteration_slider = widgets.IntSlider(min=0, max=15, step=1, value=0)\n",
    "w=widgets.interactive(plot_grid,iteration=iteration_slider)\n",
    "display(w)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Move the slider above to observe how the utility changes across iterations."
   ]
  }
 ],
 "metadata": {
  "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}