<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Markov decision process\n",
    "\n",
    "This week's methods are all built to solve __M__arkov __D__ecision __P__rocesses. In the broadest sense, an MDP is defined by how it changes states and how rewards are computed.\n",
    "\n",
    "State transition is defined by $P(s' |s,a)$ - how likely are you to end at state $s'$ if you take action $a$ from state $s$. Now there's more than one way to define rewards, but we'll use $r(s,a,s')$ function for convenience.\n",
    "\n",
    "_This notebook is inspired by the awesome_ [CS294](https://github.com/berkeleydeeprlcourse/homework/tree/master/sp17_hw/hw2) _by Berkeley_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For starters, let's define a simple MDP from this picture:\n",
    "<img src='https://s17.postimg.org/mawroys8f/750px-_Markov_Decision_Process_example.png' width=300px>\n",
    "_img by MistWiz (Own work) [Public domain], via Wikimedia Commons_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:32.642838Z",
     "start_time": "2018-04-02T13:44:32.545142Z"
    }
   },
   "outputs": [],
   "source": [
    "transition_probs = {\n",
    "  's0':{\n",
    "    'a0': {'s0': 0.5, 's2': 0.5},\n",
    "    'a1': {'s2': 1}\n",
    "  },\n",
    "  's1':{\n",
    "    'a0': {'s0': 0.7, 's1': 0.1, 's2': 0.2},\n",
    "    'a1': {'s1': 0.95, 's2': 0.05}\n",
    "  },\n",
    "  's2':{\n",
    "    'a0': {'s0': 0.4, 's1': 0.6},\n",
    "    'a1': {'s0': 0.3, 's1': 0.3, 's2':0.4}\n",
    "  }\n",
    "}\n",
    "rewards = {\n",
    "  's1': {'a0': {'s0': +5}},\n",
    "  's2': {'a1': {'s0': -1}}\n",
    "}\n",
    "\n",
    "from mdp import MDP\n",
    "mdp = MDP(transition_probs, rewards, initial_state='s0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now use MDP just as any other gym environment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:34.203384Z",
     "start_time": "2018-04-02T13:44:34.199297Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial state = s0\n",
      "next_state = s2, reward = 0.0, done = False\n"
     ]
    }
   ],
   "source": [
    "print('initial state =', mdp.reset())\n",
    "next_state, reward, done, info = mdp.step('a1')\n",
    "print('next_state = %s, reward = %s, done = %s' % (next_state, reward, done))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "but it also has other methods that you'll need for Value Iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:34.956122Z",
     "start_time": "2018-04-02T13:44:34.949856Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mdp.get_all_states = ('s0', 's1', 's2')\n",
      "mdp.get_possible_actions('s1') =  ('a0', 'a1')\n",
      "mdp.get_next_states('s1', 'a0') =  {'s0': 0.7, 's1': 0.1, 's2': 0.2}\n",
      "mdp.get_reward('s1', 'a0', 's0') =  5\n",
      "mdp.get_transition_prob('s1', 'a0', 's0') =  0.7\n"
     ]
    }
   ],
   "source": [
    "print(\"mdp.get_all_states =\", mdp.get_all_states())\n",
    "print(\"mdp.get_possible_actions('s1') = \", mdp.get_possible_actions('s1'))\n",
    "print(\"mdp.get_next_states('s1', 'a0') = \", mdp.get_next_states('s1', 'a0'))\n",
    "print(\"mdp.get_reward('s1', 'a0', 's0') = \", mdp.get_reward('s1', 'a0', 's0'))\n",
    "print(\"mdp.get_transition_prob('s1', 'a0', 's0') = \", mdp.get_transition_prob('s1', 'a0', 's0'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We provide drawing function. You have to install graphviz for system and for python. For ubuntu just run:\n",
    "\n",
    "`sudo apt-get install graphviz`, `pip install graphviz`\n",
    "\n",
    "Otherwise please comment `plot_graph(mdp)`, `plot_optimal_strategy_and_state_values(mdp, state_values)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:37.797182Z",
     "start_time": "2018-04-02T13:44:37.794073Z"
    }
   },
   "outputs": [],
   "source": [
    "from mdp import plot_graph, plot_graph_with_state_values, plot_graph_optimal_strategy_and_state_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:38.715883Z",
     "start_time": "2018-04-02T13:44:38.648684Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [<commit_msg>fix comment<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Markov decision process\n",
    "\n",
    "This week's methods are all built to solve __M__arkov __D__ecision __P__rocesses. In the broadest sense, an MDP is defined by how it changes states and how rewards are computed.\n",
    "\n",
    "State transition is defined by $P(s' |s,a)$ - how likely are you to end at state $s'$ if you take action $a$ from state $s$. Now there's more than one way to define rewards, but we'll use $r(s,a,s')$ function for convenience.\n",
    "\n",
    "_This notebook is inspired by the awesome_ [CS294](https://github.com/berkeleydeeprlcourse/homework/tree/master/sp17_hw/hw2) _by Berkeley_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For starters, let's define a simple MDP from this picture:\n",
    "<img src='https://s17.postimg.org/mawroys8f/750px-_Markov_Decision_Process_example.png' width=300px>\n",
    "_img by MistWiz (Own work) [Public domain], via Wikimedia Commons_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:32.642838Z",
     "start_time": "2018-04-02T13:44:32.545142Z"
    }
   },
   "outputs": [],
   "source": [
    "transition_probs = {\n",
    "  's0':{\n",
    "    'a0': {'s0': 0.5, 's2': 0.5},\n",
    "    'a1': {'s2': 1}\n",
    "  },\n",
    "  's1':{\n",
    "    'a0': {'s0': 0.7, 's1': 0.1, 's2': 0.2},\n",
    "    'a1': {'s1': 0.95, 's2': 0.05}\n",
    "  },\n",
    "  's2':{\n",
    "    'a0': {'s0': 0.4, 's1': 0.6},\n",
    "    'a1': {'s0': 0.3, 's1': 0.3, 's2':0.4}\n",
    "  }\n",
    "}\n",
    "rewards = {\n",
    "  's1': {'a0': {'s0': +5}},\n",
    "  's2': {'a1': {'s0': -1}}\n",
    "}\n",
    "\n",
    "from mdp import MDP\n",
    "mdp = MDP(transition_probs, rewards, initial_state='s0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now use MDP just as any other gym environment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:34.203384Z",
     "start_time": "2018-04-02T13:44:34.199297Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial state = s0\n",
      "next_state = s2, reward = 0.0, done = False\n"
     ]
    }
   ],
   "source": [
    "print('initial state =', mdp.reset())\n",
    "next_state, reward, done, info = mdp.step('a1')\n",
    "print('next_state = %s, reward = %s, done = %s' % (next_state, reward, done))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "but it also has other methods that you'll need for Value Iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:34.956122Z",
     "start_time": "2018-04-02T13:44:34.949856Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mdp.get_all_states = ('s0', 's1', 's2')\n",
      "mdp.get_possible_actions('s1') =  ('a0', 'a1')\n",
      "mdp.get_next_states('s1', 'a0') =  {'s0': 0.7, 's1': 0.1, 's2': 0.2}\n",
      "mdp.get_reward('s1', 'a0', 's0') =  5\n",
      "mdp.get_transition_prob('s1', 'a0', 's0') =  0.7\n"
     ]
    }
   ],
   "source": [
    "print(\"mdp.get_all_states =\", mdp.get_all_states())\n",
    "print(\"mdp.get_possible_actions('s1') = \", mdp.get_possible_actions('s1'))\n",
    "print(\"mdp.get_next_states('s1', 'a0') = \", mdp.get_next_states('s1', 'a0'))\n",
    "print(\"mdp.get_reward('s1', 'a0', 's0') = \", mdp.get_reward('s1', 'a0', 's0'))\n",
    "print(\"mdp.get_transition_prob('s1', 'a0', 's0') = \", mdp.get_transition_prob('s1', 'a0', 's0'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We provide drawing function. You have to install graphviz for system and for python. For ubuntu just run:\n",
    "\n",
    "`sudo apt-get install graphviz`\n",
    "\n",
    "`pip install graphviz`\n",
    "\n",
    "Otherwise please comment `plot_graph(mdp)`, `plot_graph_with_state_values(mdp, state_values)`, `plot_graph_optimal_strategy_and_state_values(mdp, state_values)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:37.797182Z",
     "start_time": "2018-04-02T13:44:37.794073Z"
    }
   },
   "outputs": [],
   "source": [
    "from mdp import plot_graph, plot_graph_with_state_values, plot_graph_optimal_strategy_and_state_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-04-02T13:44:38.715883Z",
     "start_time": "2018-04-02T13:44:38.648684Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
{'fraction_non_alphanumeric': 0.22583209140586188, 'fraction_numerical': 0.06497764530551416, 'mean_word_length': 2.7999244998112496, 'pattern_counts': {'":': 136, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 2}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6421084', 'n_tokens_mistral': 4566, 'n_tokens_neox': 4189, 'n_words': 802}