grid_problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "First we need to define our Markov Decision Process, which consists of the following: <br>\n",
    "- **States**\n",
    "- **Actions**\n",
    "- **Transition model**\n",
    "- **Reward model**\n",
    "\n",
    "We do so in the code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are 16 states for the 4x4 grid plus 1 for the end state. Furthermore, we use number 1 to 4 to denote the 4 possible actions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "states  = np.arange(17) # 1, 2, ..., 17\n",
    "actions = np.arange(4)  # up, down, left, right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the reward model, the statement says every state has a reward of -1 except for the goal state, the bad state and the end state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "R = -np.ones(17)\n",
    "R[15] = 100;  # goal state\n",
    "R[9]  = -70;  # bad state\n",
    "R[16] = 0;    # end state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The transition model is a bit more tricky, since it depends on a and b. So we will make a function that produces the transition model given a and b."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transition_model(a, b):\n",
    "    # Transitions are stored in a 3 dimensional array T[s,s',a] such that\n",
    "    # T[s,s',a] = Pr(s'|s,a)\n",
    "\n",
    "    # initialize all transition probabilities to 0\n",
    "    T = np.zeros((17,17,4))\n",
    "\n",
    "    # For a given action, the agent has probability a of moving \n",
    "    # by one square in the intended direction and probability b \n",
    "    # of moving sideways.  When the agent bumps into a wall, it\n",
    "    # stays in its current location.\n",
    "\n",
    "    # up (a = 0)\n",
    "\n",
    "    T[0,0,0] = a+b  \n",
    "    T[0,1,0] = b\n",
    "\n",
    "    T[1,0,0] = b\n",
    "    T[1,1,0] = a\n",
    "    T[1,2,0] = b\n",
    "    \n",
    "    T[2,1,0] = b\n",
    "    T[2,2,0] = a\n",
    "    T[2,3,0] = b\n",
    "    \n",
    "    T[3,2,0] = b\n",
    "    T[3,3,0] = a+b\n",
    "\n",
    "    T[4,4,0] = b\n",
    "    T[4,0,0] = a\n",
    "    T[4,5,0] = b\n",
    "    \n",
    "    T[5,4,0] = b\n",
    "    T[5,1,0] = a\n",
    "    T[5,6,0] = b\n",
    "    \n",
    "    T[6,5,0] = b\n",
    "    T[6,2,0] = a\n",
    "    T[6,7,0] = b\n",
    "    \n",
    "    T[7,6,0] = b\n",
    "    T[7,3,0] = a\n",
    "    T[7,7,0] = b\n",
    "    \n",
    "    T[8,8,0] = b\n",
    "    T[8,4,0] = a\n",
    "    T[8,9,0] = b\n",
    "    \n",
    "    T[9,8,0] = b\n",
    "    T[9,5,0] = a\n",
    "    T[9,10,0] = b\n",
    "    \n",
    "    T[10,9,0] = b\n",
    "    T[10,6,0] = a\n",
    "    T[10,11,0] = b\n",
    "    \n",
    "    T[11,10,0] = b\n",
    "    T[11,7,0] = a\n",
    "    T[11,11,0] = b\n",
    "    \n",
    "    T[12,12,0] = b\n",
    "    T[12,8,0] = a\n",
    "    T[12,13,0] = b\n",
    "    \n",
    "    T[13,12,0] = b\n",
    "    T[13,9,0] = a\n",
    "    T[13,14,0] = b\n",
    "    \n",
    "    T[14,13,0] = b\n",
    "    T[14,10,0] = a\n",
    "    T[14,15,0] = b\n",
    "    \n",
    "    T[15,16,0] = 1\n",
    "    T[16,16,0] = 1\n",
    "    \n",
    "    # down (a = 1)\n",
    "\n",
    "    T[0,0,1] = b\n",
    "    T[0,4,1] = a\n",
    "    T[0,1,1] = b\n",
    "    \n",
    "    T[1,0,1] = b\n",
    "    T[1,5,1] = a\n",
    "    T[1,2,1] = b\n",
    "    \n",
    "    T[2,1,1] = b\n",
    "    T[2,6,1] = a\n",
    "    T[2,3,1] = b\n",
    "    \n",
    "    T[3,2,1] = b\n",
    "    T[3,7,1] = a\n",
    "    T[3,3,1] = b\n",
    "    \n",
    "    T[4,4,1] = b\n",
    "    T[4,8,1] = a\n",
    "    T[4,5,1] = b\n",
    "    \n",
    "    T[5,4,1] = b\n",
    "    T[5,9,1] = a\n",
    "    T[5,6,1] = b\n",
    "    \n",
    "    T[6,5,1] = b\n",
    "    T[6,10,1] = a\n",
    "    T[6,7,1] = b\n",
    "    \n",
    "    T[7,6,1] = b\n",
    "    T[7,11,1] = a\n",
    "    T[7,7,1] = b\n",
    "    \n",
    "    T[8,8,1] = b\n",
    "    T[8,12,1] = a\n",
    "    T[8,9,1] = b\n",
    "    \n",
    "    T[9,8,1] = b\n",
    "    T[9,13,1] = a\n",
    "    T[9,10,1] = b\n",
    "    \n",
    "    T[10,9,1] = b\n",
    "    T[10,14,1] = a\n",
    "    T[10,11,1] = b\n",
    "    \n",
    "    T[11,10,1] = b\n",
    "    T[11,15,1] = a\n",
    "    T[11,11,1] = b\n",
    "    \n",
    "    T[12,12,1] = a+b\n",
    "    T[12,13,1] = b\n",
    "    \n",
    "    T[13,12,1] = b\n",
    "    T[13,13,1] = a\n",
    "    T[13,14,1] = b\n",
    "    \n",
    "    T[14,13,1] = b\n",
    "    T[14,14,1] = a\n",
    "    T[14,15,1] = b\n",
    "    \n",
    "    T[15,16,1] = 1\n",
    "    T[16,16,1] = 1\n",
    "    \n",
    "    # left (a = 2)\n",
    "\n",
    "    T[0,0,2] = a+b\n",
    "    T[0,4,2] = b\n",
    "    \n",
    "    T[1,1,2] = b\n",
    "    T[1,0,2] = a\n",
    "    T[1,5,2] = b\n",
    "    \n",
    "    T[2,2,2] = b\n",
    "    T[2,1,2] = a\n",
    "    T[2,6,2] = b\n",
    "    \n",
    "    T[3,3,2] = b\n",
    "    T[3,2,2] = a\n",
    "    T[3,7,2] = b\n",
    "    \n",
    "    T[4,0,2] = b\n",
    "    T[4,4,2] = a\n",
    "    T[4,8,2] = b\n",
    "    \n",
    "    T[5,1,2] = b\n",
    "    T[5,4,2] = a\n",
    "    T[5,9,2] = b\n",
    "    \n",
    "    T[6,2,2] = b\n",
    "    T[6,5,2] = a\n",
    "    T[6,10,2] = b\n",
    "    \n",
    "    T[7,3,2] = b\n",
    "    T[7,6,2] = a\n",
    "    T[7,11,2] = b\n",
    "    \n",
    "    T[8,4,2] = b\n",
    "    T[8,8,2] = a\n",
    "    T[8,12,2] = b\n",
    "    \n",
    "    T[9,5,2] = b\n",
    "    T[9,8,2] = a\n",
    "    T[9,13,2] = b\n",
    "    \n",
    "    T[10,6,2] = b\n",
    "    T[10,9,2] = a\n",
    "    T[10,14,2] = b\n",
    "    \n",
    "    T[11,7,2] = b\n",
    "    T[11,10,2] = a\n",
    "    T[11,15,2] = b\n",
    "    \n",
    "    T[12,8,2] = b\n",
    "    T[12,12,2] = a+b\n",
    "    \n",
    "    T[13,9,2] = b\n",
    "    T[13,12,2] = a\n",
    "    T[13,13,2] = b\n",
    "    \n",
    "    T[14,10,2] = b\n",
    "    T[14,13,2] = a\n",
    "    T[14,14,2] = b\n",
    "    \n",
    "    T[15,16,2] = 1\n",
    "    T[16,16,2] = 1\n",
    "    \n",
    "    # right (a = 3)\n",
    "\n",
    "    T[0,0,3] = b\n",
    "    T[0,1,3] = a\n",
    "    T[0,4,3] = b\n",
    "    \n",
    "    T[1,1,3] = b\n",
    "    T[1,2,3] = a\n",
    "    T[1,5,3] = b\n",
    "    \n",
    "    T[2,2,3] = b\n",
    "    T[2,3,3] = a\n",
    "    T[2,6,3] = b\n",
    "    \n",
    "    T[3,3,3] = a+b\n",
    "    T[3,7,3] = b\n",
    "    \n",
    "    T[4,0,3] = b\n",
    "    T[4,5,3] = a\n",
    "    T[4,8,3] = b\n",
    "    \n",
    "    T[5,1,3] = b\n",
    "    T[5,6,3] = a\n",
    "    T[5,9,3] = b\n",
    "    \n",
    "    T[6,2,3] = b\n",
    "    T[6,7,3] = a\n",
    "    T[6,10,3] = b\n",
    "    \n",
    "    T[7,3,3] = b\n",
    "    T[7,7,3] = a\n",
    "    T[7,11,3] = b\n",
    "    \n",
    "    T[8,4,3] = b\n",
    "    T[8,9,3] = a\n",
    "    T[8,12,3] = b\n",
    "    \n",
    "    T[9,5,3] = b\n",
    "    T[9,10,3] = a\n",
    "    T[9,13,3] = b\n",
    "    \n",
    "    T[10,6,3] = b\n",
    "    T[10,11,3] = a\n",
    "    T[10,14,3] = b\n",
    "    \n",
    "    T[11,7,3] = b\n",
    "    T[11,11,3] = a\n",
    "    T[11,15,3] = b\n",
    "    \n",
    "    T[12,8,3] = b\n",
    "    T[12,13,3] = a\n",
    "    T[12,12,3] = b\n",
    "    \n",
    "    T[13,9,3] = b\n",
    "    T[13,14,3] = a\n",
    "    T[13,13,3] = b\n",
    "    \n",
    "    T[14,10,3] = b\n",
    "    T[14,15,3] = a\n",
    "    T[14,14,3] = b\n",
    "    \n",
    "    T[15,16,3] = 1\n",
    "    T[16,16,3] = 1\n",
    "    \n",
    "    return T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Value Iteration\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have formulated our problem, it's time to implement the **Value Iteration** algorithm. \n",
    "The Value Iteration algirithm first finds the best possible score from each state, and then the best policy given the optimal scores.\n",
    "<br><br>\n",
    "The **Q(s, a)** denotes the expected reward if from state *s* we perform the action *a*. It is the function inside the maximum of the **Bellman equation**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def value_iteration(states, actions, R, T, gamma=0.99, eps=0.01):\n",
    "    \"\"\" Value-iteration algorithm \"\"\"\n",
    "    V = np.zeros(states.shape)  # initialize value-function\n",
    "    \n",
    "    max_iterations = 10000\n",
    "    for i in range(max_iterations):\n",
    "        prev_V = np.copy(V)\n",
    "        Q = np.zeros(states.shape + actions.shape) # Q(state, action)\n",
    "        \n",
    "        # Value iteration - Bellman's equation in recursive version\n",
    "        for s in states:\n",
    "            for a in actions:\n",
    "                Q[s, a] = sum([(R[next_s] + gamma * prev_V[next_s]) * T[s, next_s, a] for next_s in states])\n",
    "            V[s] = np.max(Q[s, :])\n",
    "        \n",
    "        if all(np.fabs(prev_V - V) <= eps):\n",
    "            print('Value-iteration converged at iteration #{}.'.format(i+1))\n",
    "            break\n",
    "    \n",
    "    # Optimal policy\n",
    "    policy = -np.ones(states.shape)\n",
    "    for s in states:\n",
    "        policy[s] = np.argmax(Q[s, :])\n",
    "    \n",
    "    return policy, V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now for the best visualization of the results, it would be cool to pretty print our policies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_results(policy, V):\n",
    "    \"\"\" Pretty print the results \"\"\"\n",
    "    move = {0: 'up', 1: 'down', 2: 'left', 3: 'right'}\n",
    "    \n",
    "    print()\n",
    "    print('{:^33}\\t\\t{:^33}'.format('Optimal Policy', 'Optimal Scores'))\n",
    "    print('┌────────┬────────┬────────┬────────┐\\t\\t┌────────┬────────┬────────┬────────┐');\n",
    "    for i in range(4):\n",
    "        for j in range(4):\n",
    "            idx = i*4+j\n",
    "            print('│ {:^6} '.format(move[policy[idx]]), end='')\n",
    "        print('│\\t\\t', end='')\n",
    "        for j in range(4):\n",
    "            idx = i*4+j\n",
    "            print('│ {:6.2f} '.format(V[idx]), end='')\n",
    "        print('│')\n",
    "        if i < 3:\n",
    "            print('├────────┼────────┼────────┼────────┤\\t\\t├────────┼────────┼────────┼────────┤');\n",
    "        else:\n",
    "            print('└────────┴────────┴────────┴────────┘\\t\\t└────────┴────────┴────────┴────────┘');\n",
    "    print()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "We need to compute the optimal policies for:\n",
    "\n",
    "#### (a, b) = (0.9, 0.05)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value-iteration converged at iteration #16.\n",
      "\n",
      "         Optimal Policy          \t\t         Optimal Scores          \n",
      "┌────────┬────────┬────────┬────────┐\t\t┌────────┬────────┬────────┬────────┐\n",
      "│ right  │ right  │ right  │  down  │\t\t│  88.58 │  90.76 │  92.97 │  95.02 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│ right  │ right  │ right  │  down  │\t\t│  87.38 │  89.51 │  95.14 │  97.32 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│  down  │ right  │ right  │  down  │\t\t│  85.78 │  94.88 │  97.44 │  99.66 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│ right  │ right  │ right  │   up   │\t\t│  91.23 │  93.68 │  99.66 │   0.00 │\n",
      "└────────┴────────┴────────┴────────┘\t\t└────────┴────────┴────────┴────────┘\n",
      "\n"
     ]
    }
   ],
   "source": [
    "T = transition_model(0.9, 0.05)\n",
    "policy, V = value_iteration(states, actions, R, T)\n",
    "print_results(policy, V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### (a, b) = (0.8, 0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value-iteration converged at iteration #23.\n",
      "\n",
      "         Optimal Policy          \t\t         Optimal Scores          \n",
      "┌────────┬────────┬────────┬────────┐\t\t┌────────┬────────┬────────┬────────┐\n",
      "│ right  │ right  │ right  │  down  │\t\t│  86.36 │  88.96 │  91.58 │  93.70 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│   up   │   up   │ right  │  down  │\t\t│  84.37 │  87.12 │  94.00 │  96.41 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│  down  │ right  │ right  │  down  │\t\t│  76.33 │  92.97 │  96.69 │  99.19 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│ right  │ right  │ right  │   up   │\t\t│  85.19 │  88.64 │  99.19 │   0.00 │\n",
      "└────────┴────────┴────────┴────────┘\t\t└────────┴────────┴────────┴────────┘\n",
      "\n"
     ]
    }
   ],
   "source": [
    "T = transition_model(0.8, 0.1)\n",
    "policy, V = value_iteration(states, actions, R, T)\n",
    "print_results(policy, V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explanation\n",
    "\n",
    "In the first case where (a, b) = (0.9, 0.05), the agent is more sure if it's moves.\n",
    "\n",
    "This for example impacts the policy in the cells (1, 0) and (1, 1) where in the more confident model the agent goes to the right since it's the faster way to go to it's target but in the less confident model, the agent goes up to run away from the bad state.\n",
    "\n",
    "Also we see that the optimal scores are a bit higher in the more confident model, which agains makes sense since the agent has higher probability of moving in the desired direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Q-Learning\n",
    "\n",
    "Finally we need to implement a Q-Learning algorithm for the case where the model's environment is unknown. \n",
    "\n",
    "The algorithm randomly assigns the Q-values at first, and then runs many simulations (episodes) to update the Q-values by experience. Each simulation starts at the start state (s=4) and moves according to the optiomal action with probability 1-ε and with a randomly chosen action with probability ε, in order to explore the state space. Upon arrival to the end state, the episode is over. \n",
    "\n",
    "The algorithm is provided below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def qLearning(states, actions, R, T, epsilon, episodes, gamma=0.99):\n",
    "    \n",
    "    N = np.zeros([states.shape[0],actions.shape[0]])\n",
    "    Q = np.random.rand(states.shape[0], actions.shape[0])\n",
    "    Q_obs = np.zeros([states.shape[0],actions.shape[0]])\n",
    "    \n",
    "    max_iterations = 100 # max number of updates per episode\n",
    "    \n",
    "    # Run the same simulations many times\n",
    "    for episode in range(episodes):\n",
    "        \n",
    "        s = 4 # the start state - the 5th cell in the grid\n",
    "        \n",
    "        for i in range(max_iterations):\n",
    "            # Choose next action\n",
    "            a_optimal = np.argmax(Q[s, :])\n",
    "            a_random  = np.random.choice(actions)\n",
    "            a = np.random.choice([a_optimal, a_random], p=[1-epsilon, epsilon])   \n",
    "                                                                            \n",
    "            # Get next state\n",
    "            next_s = np.random.choice(states, p=T[s, :, a])\n",
    "            N[s, a] += 1\n",
    "\n",
    "            # Observer reward\n",
    "            Q_obs[s, a] = R[next_s] + gamma * max(Q[next_s, :])\n",
    "\n",
    "            # Update\n",
    "            alpha = 1 / N[s, a]\n",
    "            Q[s, a] = (1 - alpha) * Q[s, a] + alpha * Q_obs[s, a]\n",
    "\n",
    "            if s == 16:\n",
    "                break   # exit upon arrival on the end state ( and go to the next episode )\n",
    "            else:\n",
    "                s = next_s # move agent to the next state\n",
    "    \n",
    "    # Optimal policy\n",
    "    V = np.zeros(states.shape)\n",
    "    policy = -np.ones(states.shape)\n",
    "    for s in states:\n",
    "        V[s] = np.max(Q[s, :])\n",
    "        policy[s] = np.argmax(Q[s, :])\n",
    "    \n",
    "    return policy, V\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to test it for:\n",
    "\n",
    "#### ε = 0.05"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "         Optimal Policy          \t\t         Optimal Scores          \n",
      "┌────────┬────────┬────────┬────────┐\t\t┌────────┬────────┬────────┬────────┐\n",
      "│  down  │  left  │  down  │  down  │\t\t│  67.62 │  57.85 │  86.45 │  78.06 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│ right  │ right  │  down  │  down  │\t\t│  77.10 │  84.06 │  94.10 │  97.51 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│  down  │  down  │ right  │  down  │\t\t│  81.71 │  90.65 │  98.03 │ 100.51 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│ right  │ right  │ right  │  down  │\t\t│  90.20 │  94.12 │ 100.35 │   0.90 │\n",
      "└────────┴────────┴────────┴────────┘\t\t└────────┴────────┴────────┴────────┘\n",
      "\n"
     ]
    }
   ],
   "source": [
    "T = transition_model(0.9, 0.05)\n",
    "policy, V = qLearning(states, actions, R, T, 0.05, 10000)\n",
    "print_results(policy, V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ε = 0.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "         Optimal Policy          \t\t         Optimal Scores          \n",
      "┌────────┬────────┬────────┬────────┐\t\t┌────────┬────────┬────────┬────────┐\n",
      "│  down  │  down  │  down  │  down  │\t\t│  74.01 │  67.46 │  84.72 │  61.88 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│  down  │ right  │  down  │  down  │\t\t│  81.21 │  84.49 │  94.06 │  96.17 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│  down  │  down  │ right  │  down  │\t\t│  85.34 │  91.71 │  97.76 │ 100.39 │\n",
      "├────────┼────────┼────────┼────────┤\t\t├────────┼────────┼────────┼────────┤\n",
      "│ right  │ right  │ right  │   up   │\t\t│  91.49 │  93.97 │ 100.37 │   0.78 │\n",
      "└────────┴────────┴────────┴────────┘\t\t└────────┴────────┴────────┴────────┘\n",
      "\n"
     ]
    }
   ],
   "source": [
    "T = transition_model(0.9, 0.05)\n",
    "policy, V = qLearning(states, actions, R, T, 0.2, 10000)\n",
    "print_results(policy, V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explanation\n",
    "\n",
    "We observe that the first implementation where we are less eager to explore may converge faster but is more prone to erros, as in cell (0, 1) the policy suggest to move in the opposite direction of the desired. This doesn't happen when ε = 0.2 since the model explores more option and learns a better policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}