mdp_apps.ipynb

    "For example, as we have the same reward regardless of the action, let's consider a reward of **r** units for a particular state and let's assume the transition probabilities to be 0.1, 0.2, 0.3 and 0.4 for 4 possible actions for that state.\n",
    "We will further assume that a particular action in a state leads to the same state every time we take that action.\n",
    "The first term inside the summation for this case will evaluate to (0.1 + 0.2 + 0.3 + 0.4)r = r which is equal to R(s) in the first update equation.\n",
    "<br>\n",
    "There are many ways to write value iteration for this situation, but we will go with the most intuitive method.\n",
    "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": [
      "['cruise', 'dispatch', 'stand']\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."
   ]
  }
 ],
 "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
}