{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving Frozen Lake Problem Using Value Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Goal:\n",
    "\n",
    "Imagine, there is a frozen lake from your home to office, you should walk on the frozen lake\n",
    "to reach your office. But oops! there will be a hole in the frozen lake in between, so you have\n",
    "to be careful while walking in the frozen lake to avoid getting trapped at holes.\n",
    "Look at the below figure where, \n",
    "\n",
    "1. S is the starting position (Home)\n",
    "2. F is the Frozen lake where you can walk\n",
    "3. H is the Hole which you have to be so careful about\n",
    "4. G is the Goal (office)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](images/B09792_03_50.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Okay, now let us use our agent instead of you to find the correct way to reach the office.\n",
    "The agent goal is to find the optimal path to reach from S to G without getting trapped at H.\n",
    "How an agent can achieve this? We give +1 point as a reward to the agent if it correctly\n",
    "walks on the frozen lake and 0 points if it falls into the hole. So that agent could determine\n",
    "which is the right action. An agent will now try to find the optimal policy. Optimal policy\n",
    "implies taking the correct path which maximizes the agent reward. If the agent is\n",
    "maximizing the reward, apparently agent is learning to skip the hole and reach the\n",
    "destination."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we import necessary libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import gym\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initialize our gym environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[2018-06-01 11:59:38,953] Making new env: FrozenLake-v0\n"
     ]
    }
   ],
   "source": [
    "env = gym.make('FrozenLake-v0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Let us see how the environment looks like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[41mS\u001b[0mFFF\n",
      "FHFH\n",
      "FFFH\n",
      "HFFG\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<ipykernel.iostream.OutStream at 0x7f9e82c4e6a0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we define the function called value_iteration which performs value iteraion i.e it returns the optimal value\n",
    "function (value table)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def value_iteration(env, gamma = 1.0):\n",
    "    \n",
    "    # initialize value table with zeros\n",
    "    value_table = np.zeros(env.observation_space.n)\n",
    "    \n",
    "    # set number of iterations and threshold\n",
    "    no_of_iterations = 100000\n",
    "    threshold = 1e-20\n",
    "    \n",
    "    for i in range(no_of_iterations):\n",
    "        \n",
    "        # On each iteration, copy the value table to the updated_value_table\n",
    "        updated_value_table = np.copy(value_table) \n",
    "        \n",
    "        # Now we calculate Q Value for each actions in the state \n",
    "        # and update the value of a state with maximum Q value\n",
    "        \n",
    "        for state in range(env.observation_space.n):\n",
    "            Q_value = []\n",
    "            for action in range(env.action_space.n):\n",
    "                next_states_rewards = []\n",
    "                for next_sr in env.P[state][action]: \n",
    "                    trans_prob, next_state, reward_prob, _ = next_sr \n",
    "                    next_states_rewards.append((trans_prob * (reward_prob + gamma * updated_value_table[next_state]))) \n",
    "                \n",
    "                Q_value.append(np.sum(next_states_rewards))\n",
    "                \n",
    "            value_table[state] = max(Q_value) \n",
    "            \n",
    "        # we will check whether we have reached the convergence i.e whether the difference \n",
    "        # between our value table and updated value table is very small. But how do we know it is very\n",
    "        # small? We set some threshold and then we will see if the difference is less\n",
    "        # than our threshold, if it is less, we break the loop and return the value function as optimal\n",
    "        # value function\n",
    "        \n",
    "        if (np.sum(np.fabs(updated_value_table - value_table)) <= threshold):\n",
    "             print ('Value-iteration converged at iteration# %d.' %(i+1))\n",
    "             break\n",
    "    \n",
    "    return value_table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Now, we define a function called extract policy for extracting optimal policy from the optimal value function. \n",
    "i.e We calculate Q value using our optimal value function and pick up\n",
    "the actions which has the highest Q value for each state as the optimal policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_policy(value_table, gamma = 1.0):\n",
    " \n",
    "    # initialize the policy with zeros\n",
    "    policy = np.zeros(env.observation_space.n) \n",
    "    \n",
    "    \n",
    "    for state in range(env.observation_space.n):\n",
    "        \n",
    "        # initialize the Q table for a state\n",
    "        Q_table = np.zeros(env.action_space.n)\n",
    "        \n",
    "        # compute Q value for all ations in the state\n",
    "        for action in range(env.action_space.n):\n",
    "            for next_sr in env.P[state][action]: \n",
    "                trans_prob, next_state, reward_prob, _ = next_sr \n",
    "                Q_table[action] += (trans_prob * (reward_prob + gamma * value_table[next_state]))\n",
    "        \n",
    "        # select the action which has maximum Q value as an optimal action of the state\n",
    "        policy[state] = np.argmax(Q_table)\n",
    "    \n",
    "    return policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, We compute the optimal value function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value-iteration converged at iteration# 1373.\n"
     ]
    }
   ],
   "source": [
    "optimal_value_function = value_iteration(env=env,gamma=1.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and we derive the optimal policy from the optimal value function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "optimal_policy = extract_policy(optimal_value_function, gamma=1.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 3. 3. 3. 0. 0. 0. 0. 3. 1. 0. 0. 0. 2. 1. 0.]\n"
     ]
    }
   ],
   "source": [
    "print(optimal_policy)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:universe]",
   "language": "python",
   "name": "conda-env-universe-py"
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}