mdp_apps.ipynb

    "One that can be implemented with minor alterations to the existing `value_iteration` algorithm.\n",
    "<br>\n",
    "Our `DMDP` class will be slightly different.\n",
    "More specifically, the `R` method will have one more index to go through now that we have three levels of nesting in the reward model.\n",
    "We will call the new class `DMDP2` as I have run out of creative names."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class DMDP2:\n",
    "\n",
    "    \"\"\"A Markov Decision Process, defined by an initial state, transition model,\n",
    "    and reward model. We also keep track of a gamma value, for use by\n",
    "    algorithms. The transition model is represented somewhat differently from\n",
    "    the text. Instead of P(s' | s, a) being a probability number for each\n",
    "    state/state/action triplet, we instead have T(s, a) return a\n",
    "    list of (p, s') pairs. The reward function is very similar.\n",
    "    We also keep track of the possible states,\n",
    "    terminal states, and actions for each state.\"\"\"\n",
    "\n",
    "    def __init__(self, init, actlist, terminals, transitions={}, rewards={}, states=None, gamma=.9):\n",
    "        if not (0 < gamma <= 1):\n",
    "            raise ValueError(\"An MDP must have 0 < gamma <= 1\")\n",
    "\n",
    "        if states:\n",
    "            self.states = states\n",
    "        else:\n",
    "            self.states = set()\n",
    "        self.init = init\n",
    "        self.actlist = actlist\n",
    "        self.terminals = terminals\n",
    "        self.transitions = transitions\n",
    "        self.rewards = rewards\n",
    "        self.gamma = gamma\n",
    "\n",
    "    def R(self, state, action, state_):\n",
    "        \"\"\"Return a numeric reward for this state, this action and the next state_\"\"\"\n",
    "        if (self.rewards == {}):\n",
    "            raise ValueError('Reward model is missing')\n",
    "        else:\n",
    "            return self.rewards[state][action][state_]\n",
    "\n",
    "    def T(self, state, action):\n",
    "        \"\"\"Transition model. From a state and an action, return a list\n",
    "        of (probability, result-state) pairs.\"\"\"\n",
    "        if(self.transitions == {}):\n",
    "            raise ValueError(\"Transition model is missing\")\n",
    "        else:\n",
    "            return self.transitions[state][action]\n",
    "\n",
    "    def actions(self, state):\n",
    "        \"\"\"Set of actions that can be performed in this state. By default, a\n",
    "        fixed list of actions, except for terminal states. Override this\n",
    "        method if you need to specialize by state.\"\"\"\n",
    "        if state in self.terminals:\n",
    "            return [None]\n",
    "        else:\n",
    "            return self.actlist\n",
    "        \n",
    "    def actions(self, state):\n",
    "        \"\"\"Set of actions that can be performed in this state. By default, a\n",
    "        fixed list of actions, except for terminal states. Override this\n",
    "        method if you need to specialize by state.\"\"\"\n",
    "        if state in self.terminals:\n",
    "            return [None]\n",
    "        else:\n",
    "            return self.actlist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only the `R` method is different from the previous `DMDP` class.\n",
    "<br>\n",
    "Our traditional custom class will be required to implement the transition model and the reward model.\n",
    "<br>\n",
    "We call this class `CustomDMDP2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class CustomDMDP2(DMDP2):\n",
    "    \n",
    "    def __init__(self, transition_matrix, rewards, terminals, init, gamma=.9):\n",
    "        actlist = []\n",
    "        for state in transition_matrix.keys():\n",
    "            actlist.extend(transition_matrix[state])\n",
    "        actlist = list(set(actlist))\n",
    "        print(actlist)\n",
    "        \n",
    "        DMDP2.__init__(self, init, actlist, terminals=terminals, gamma=gamma)\n",
    "        self.t = transition_matrix\n",
    "        self.rewards = rewards\n",
    "        for state in self.t:\n",
    "            self.states.add(state)\n",
    "                      \n",
    "    def T(self, state, action):\n",
    "        if action is None:\n",
    "            return [(0.0, state)]\n",
    "        else:\n",
    "            return [(prob, new_state) for new_state, prob in self.t[state][action].items()]\n",
    "        \n",
    "    def R(self, state, action, state_):\n",
    "        if action is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.rewards[state][action][state_]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can finally write value iteration for this problem.\n",
    "The latest update equation will be used."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def value_iteration_taxi_mdp(dmdp2, epsilon=0.001):\n",
    "    U1 = {s: 0 for s in dmdp2.states}\n",
    "    R, T, gamma = dmdp2.R, dmdp2.T, dmdp2.gamma\n",
    "    while True:\n",
    "        U = U1.copy()\n",
    "        delta = 0\n",
    "        for s in dmdp2.states:\n",
    "            U1[s] = max([sum([(p*(R(s, a, s1) + gamma*U[s1])) for (p, s1) in T(s, a)]) for a in dmdp2.actions(s)])\n",
    "            delta = max(delta, abs(U1[s] - U[s]))\n",
    "        if delta < epsilon * (1 - gamma) / gamma:\n",
    "            return U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These algorithms can be made more pythonic by using cleverer list comprehensions.\n",
    "We can also write the variants of value iteration in such a way that all problems are solved using the same base class, regardless of the reward function and the number of arguments it takes.\n",
    "Quite a few things can be done to refactor the code and reduce repetition, but we have done it this way for the sake of clarity.\n",
    "Perhaps you can try this as an exercise.\n",
    "<br>\n",
    "We now need to define terminals and initial state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "terminals = ['end']\n",
    "init = 'A'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's instantiate our class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['stand', 'dispatch', 'cruise']\n"
     ]
    }
   ],
   "source": [
    "dmdp2 = CustomDMDP2(t, r, terminals, init, gamma=.9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 124.4881543573768, 'B': 137.70885410461636, 'C': 129.08041190693115}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value_iteration_taxi_mdp(dmdp2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the expected utility values for the states of our MDP.\n",
    "Let's proceed to write a helper function to find the expected utility and another to find the best policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def expected_utility_dmdp2(a, s, U, dmdp2):\n",
    "    return sum([(p*(dmdp2.R(s, a, s1) + dmdp2.gamma*U[s1])) for (p, s1) in dmdp2.T(s, a)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from utils import argmax\n",
    "def best_policy_dmdp2(dmdp2, U):\n",
    "    pi = {}\n",
    "    for s in dmdp2.states:\n",
    "        pi[s] = argmax(dmdp2.actions(s), key=lambda a: expected_utility_dmdp2(a, s, U, dmdp2))\n",
    "    return pi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the best policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'C': 'cruise', 'A': 'stand', 'B': 'stand'}\n"
     ]
    }
   ],
   "source": [
    "pi = best_policy_dmdp2(dmdp2, value_iteration_taxi_mdp(dmdp2, .01))\n",
    "print(pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have successfully adapted the existing code to a different scenario yet again.\n",
    "The takeaway from this section is that you can convert the vast majority of reinforcement learning problems into MDPs and solve for the best policy using simple yet efficient tools."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GRID MDP\n",
    "---\n",
    "### Pathfinding Problem\n",
    "Markov Decision Processes can be used to find the best path through a maze. Let us consider this simple maze.\n",
    "![title](images/maze.png)\n",
    "\n",
    "This environment can be formulated as a GridMDP.\n",
    "<br>\n",
    "To make the grid matrix, we will consider the state-reward to be -0.1 for every state.\n",
    "<br>\n",
    "State (1, 1) will have a reward of -5 to signify that this state is to be prohibited.\n",
    "<br>\n",
    "State (9, 9) will have a reward of +5.\n",
    "This will be the terminal state.\n",
    "<br>\n",
    "The matrix can be generated using the GridMDP editor or we can write it ourselves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "grid = [\n",
    "    [None, None, None, None, None, None, None, None, None, None, None], \n",
    "    [None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None, +5.0, None], \n",
    "    [None, -0.1, None, None, None, None, None, None, None, -0.1, None], \n",
    "    [None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None], \n",
    "    [None, -0.1, None, None, None, None, None, None, None, None, None], \n",
    "    [None, -0.1, None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None], \n",
    "    [None, -0.1, None, None, None, None, None, -0.1, None, -0.1, None], \n",
    "    [None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None, -0.1, None], \n",
    "    [None, None, None, None, None, -0.1, None, -0.1, None, -0.1, None], \n",
    "    [None, -5.0, -0.1, -0.1, -0.1, -0.1, None, -0.1, None, -0.1, None], \n",
    "    [None, None, None, None, None, None, None, None, None, None, None]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have only one terminal state, (9, 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "terminals = [(9, 9)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define our maze environment below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze = GridMDP(grid, terminals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To solve the maze, we can use the `best_policy` function along with `value_iteration`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pi = best_policy(maze, value_iteration(maze))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the heatmap generated by the GridMDP editor using `value_iteration` on this environment\n",
    "<br>\n",
    "![title](images/mdp-d.png)\n",
    "<br>\n",
    "Let's print out the best policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None   None   None   None   None   None   None   None   None   None   None\n",
      "None   v      <      <      <      <      <      <      None   .      None\n",
      "None   v      None   None   None   None   None   None   None   ^      None\n",
      "None   >      >      >      >      >      >      >      >      ^      None\n",
      "None   ^      None   None   None   None   None   None   None   None   None\n",
      "None   ^      None   >      >      >      >      v      <      <      None\n",
      "None   ^      None   None   None   None   None   v      None   ^      None\n",
      "None   ^      <      <      <      <      <      <      None   ^      None\n",
      "None   None   None   None   None   ^      None   ^      None   ^      None\n",
      "None   >      >      >      >      ^      None   ^      None   ^      None\n",
      "None   None   None   None   None   None   None   None   None   None   None\n"
     ]
    }
   ],
   "source": [
    "from utils import print_table\n",
    "print_table(maze.to_arrows(pi))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can infer, we can find the path to the terminal state starting from any given state using this policy.\n",
    "All maze problems can be solved by formulating it as a MDP."
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}