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 *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Review\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 0x7fcb2826ba58>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_decision_environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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
}