Frozen_Lake_Value_Policy_Iteration.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "from __future__ import division\n",
    "import numpy as np\n",
    "import gym\n",
    "from gym import wrappers\n",
    "import time\n",
    "import scipy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\u001b[41mS\u001b[0mFFFFFFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n"
     ]
    }
   ],
   "source": [
    "env=gym.make('FrozenLake8x8-v0')\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "Discrete(4)\n",
      "64\n",
      "[(0.3333333333333333, 0, 0.0, False), (0.3333333333333333, 8, 0.0, False), (0.3333333333333333, 1, 0.0, False)]\n"
     ]
    }
   ],
   "source": [
    "print(env.nA)\n",
    "print(env.action_space)\n",
    "print(env.env.nS)\n",
    "print(env.env.P[0][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (Right)\n",
      "SFFFFFFF\n",
      "\u001b[41mF\u001b[0mFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "SFFFFFFF\n",
      "\u001b[41mF\u001b[0mFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Up)\n",
      "SFFFFFFF\n",
      "\u001b[41mF\u001b[0mFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFFFFFF\n",
      "F\u001b[41mF\u001b[0mFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "S\u001b[41mF\u001b[0mFFFFFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Down)\n",
      "SF\u001b[41mF\u001b[0mFFFFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFFFFFF\n",
      "FFF\u001b[41mF\u001b[0mFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Down)\n",
      "SFFFFFFF\n",
      "FFF\u001b[41mF\u001b[0mFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFF\u001b[41mF\u001b[0mFFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFFFFFF\n",
      "FFFFF\u001b[41mF\u001b[0mFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Up)\n",
      "SFFFFF\u001b[41mF\u001b[0mF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "SFFFFF\u001b[41mF\u001b[0mF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "SFFFFF\u001b[41mF\u001b[0mF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Down)\n",
      "SFFFF\u001b[41mF\u001b[0mFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFFFFFF\n",
      "FFFFFF\u001b[41mF\u001b[0mF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "SFFFFFFF\n",
      "FFFFFF\u001b[41mF\u001b[0mF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Up)\n",
      "SFFFFFFF\n",
      "FFFFFF\u001b[41mF\u001b[0mF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "SFFFF\u001b[41mF\u001b[0mFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFFFFFF\n",
      "FFFFFFFF\n",
      "FFFHF\u001b[41mF\u001b[0mFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Left)\n",
      "SFFFF\u001b[41mF\u001b[0mFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Down)\n",
      "SFFF\u001b[41mF\u001b[0mFFF\n",
      "FFFFFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n",
      "  (Right)\n",
      "SFFFFFFF\n",
      "FFF\u001b[41mF\u001b[0mFFFF\n",
      "FFFHFFFF\n",
      "FFFFFHFF\n",
      "FFFHFFFF\n",
      "FHHFFFHF\n",
      "FHFFHFHF\n",
      "FFFHFFFG\n"
     ]
    }
   ],
   "source": [
    " for episode in range(1):\n",
    "        state = env.reset() \n",
    "        for time_step in range(1000): \n",
    "            action = env.action_space.sample()\n",
    "            env.step(action)\n",
    "            env.render()\n",
    "            state, reward, done, _ = env.step(action)\n",
    "            if done:\n",
    "                break \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Value Iteration\n",
    "Value iteration computes the optimal state value function by iteratively improving the estimate of V(s). The algorithm initialize V(s) to arbitrary random values. It repeatedly updates the Q(s, a) and V(s) values until they converges. Value iteration is guaranteed to converge to the optimal values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------- Gamma=0.9 ----------\n",
      "Value-iteration converged at iteration# 2357.\n",
      "Value iteration took 1.3260037899017334 seconds.\n",
      "Average score =  0.0016816714389826229\n",
      "---------- Gamma=0.95 ----------\n",
      "Value-iteration converged at iteration# 2357.\n",
      "Value iteration took 1.2873561382293701 seconds.\n",
      "Average score =  0.02526921672502035\n",
      "---------- Gamma=0.99 ----------\n",
      "Value-iteration converged at iteration# 2357.\n",
      "Value iteration took 1.343747615814209 seconds.\n",
      "Average score =  0.3615459976890162\n",
      "---------- Gamma=0.9999 ----------\n",
      "Value-iteration converged at iteration# 2357.\n",
      "Value iteration took 1.3305723667144775 seconds.\n",
      "Average score =  0.8724275875603766\n",
      "---------- Gamma=1 ----------\n",
      "Value-iteration converged at iteration# 2357.\n",
      "Value iteration took 1.353240966796875 seconds.\n",
      "Average score =  0.867\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def run_episode(env, policy, gamma, render = False):\n",
    "    \"\"\" Evaluates policy by using it to run an episode and finding its\n",
    "    total reward.\n",
    "    args:\n",
    "    env: gym environment.\n",
    "    policy: the policy to be used.\n",
    "    gamma: discount factor.\n",
    "    render: boolean to turn rendering on/off.\n",
    "    returns:\n",
    "    total reward: real value of the total reward recieved by agent under policy.\n",
    "    \"\"\"\n",
    "    obs = env.reset()\n",
    "    total_reward = 0\n",
    "    step_idx = 0\n",
    "    while True:\n",
    "        if render:\n",
    "            env.render()\n",
    "        obs, reward, done , _ = env.step(int(policy[obs]))\n",
    "        total_reward += (gamma ** step_idx * reward)\n",
    "        step_idx += 1\n",
    "        if done:\n",
    "            break\n",
    "    return total_reward\n",
    "\n",
    "\n",
    "def evaluate_policy(env, policy, gamma,  n = 100):\n",
    "    \"\"\" Evaluates a policy by running it n times.\n",
    "    returns:\n",
    "    average total reward\n",
    "    \"\"\"\n",
    "    scores = [\n",
    "            run_episode(env, policy, gamma=gamma, render = False)\n",
    "            for _ in range(n)]\n",
    "    return np.mean(scores)\n",
    "\n",
    "def extract_policy(v, gamma):\n",
    "    \"\"\" Extract the policy given a value-function \"\"\"\n",
    "    policy = np.zeros(env.nS)\n",
    "    for s in range(env.nS):\n",
    "        q_sa = np.zeros(env.action_space.n)\n",
    "        for a in range(env.action_space.n):\n",
    "            for next_sr in env.P[s][a]:\n",
    "                # next_sr is a tuple of (probability, next state, reward, done)\n",
    "                p, s_, r, _ = next_sr\n",
    "                q_sa[a] += (p * (r + gamma * v[s_]))\n",
    "        policy[s] = np.argmax(q_sa)\n",
    "    return policy\n",
    "\n",
    "\n",
    "def value_iteration(env, gamma, epsilon=1e-20, max_iterations=100000):\n",
    "    \"\"\"\n",
    "    This function implements value iteration algorithm for the infinite\n",
    "    horizon discounted MDPs. If the sup norm of v_k - v_{k-1} is less than\n",
    "    epsilon or number of iterations reaches max_iterations, it should return\n",
    "    the value function.\n",
    "    \"\"\"\n",
    "    start = time.time()\n",
    "    v = np.zeros(env.nS)  # initialize value-function\n",
    "    ########################### Your Code Here ###########################\n",
    "    # Hint: see implementation of extract_policy\n",
    "    \n",
    "    for i in range(max_iterations):\n",
    "        prev_v = np.copy(v)\n",
    "        for s in range(env.nS):\n",
    "            q_sa = [sum([p*(r + prev_v[s_]) for p, s_, r, _ in env.P[s][a]]) for a in range(env.nA)] \n",
    "            v[s] = max(q_sa)\n",
    "        if (np.sum(np.fabs(prev_v - v)) <= epsilon):\n",
    "            print ('Value-iteration converged at iteration# %d.' %(i+1))\n",
    "            break\n",
    "    \n",
    "                    \n",
    "    ########################### End of your code #########################\n",
    "    end = time.time()\n",
    "    print(\"Value iteration took {0} seconds.\".format(end - start))\n",
    "    return v\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    np.random.seed(1111)\n",
    "    env_name  = 'FrozenLake8x8-v0'\n",
    "    for gamma in [.9, .95, .99, .9999, 1]:\n",
    "        print(\"-\"*10, \"Gamma={0}\".format(gamma) ,\"-\"*10)\n",
    "        env = gym.make(env_name)\n",
    "        optimal_v = value_iteration(env, gamma);\n",
    "        policy = extract_policy(optimal_v, gamma)\n",
    "        policy_score = evaluate_policy(env, policy, gamma, n=1000)\n",
    "        print('Average score = ', policy_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Policy Iteration\n",
    "policy-iteration instead of repeated improving the value-function estimate, it will re-define the policy at each step and compute the value according to this new policy until the policy converges. Policy iteration is also guaranteed to converge to the optimal policy and it often takes less iterations to converge than the value-iteration algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------- Gamma=0.9 ----------\n",
      "Policy iteration took 0.15405559539794922 seconds.\n",
      "Policy-Iteration converged at step 5.\n",
      "Average scores =  0.00473197770117812\n",
      "---------- Gamma=0.95 ----------\n",
      "Policy iteration took 0.15418267250061035 seconds.\n",
      "Policy-Iteration converged at step 3.\n",
      "Average scores =  0.05249329649060406\n",
      "---------- Gamma=0.99 ----------\n",
      "Policy iteration took 0.8403522968292236 seconds.\n",
      "Policy-Iteration converged at step 8.\n",
      "Average scores =  0.38577824957168594\n",
      "---------- Gamma=0.9999 ----------\n",
      "Policy iteration took 2.7064201831817627 seconds.\n",
      "Policy-Iteration converged at step 12.\n",
      "Average scores =  0.9009111682246035\n",
      "---------- Gamma=1 ----------\n",
      "Policy iteration took 1.6615610122680664 seconds.\n",
      "Policy-Iteration converged at step 6.\n",
      "Average scores =  0.92\n"
     ]
    }
   ],
   "source": [
    "def compute_policy_v(env, policy, gamma):\n",
    "    \"\"\" Iteratively evaluate the value-function under policy.\n",
    "    Alternatively, we could formulate a set of linear equations in iterms of v[s] \n",
    "    and solve them to find the value function.\n",
    "    \"\"\"\n",
    "    v = np.zeros(env.nS)\n",
    "    eps = 1e-10\n",
    "    while True:\n",
    "        prev_v = np.copy(v)\n",
    "        for s in range(env.nS):\n",
    "            policy_a = policy[s]\n",
    "            v[s] = sum([p * (r + gamma * prev_v[s_]) for p, s_, r, _ in env.P[s][policy_a]])\n",
    "        if (np.sum((np.fabs(prev_v - v))) <= eps):\n",
    "            # value converged\n",
    "            break\n",
    "    return v\n",
    "\n",
    "def policy_iteration(env, gamma, max_iterations=100000):\n",
    "    \"\"\"\n",
    "    This function implements policy iteration algorithm.\n",
    "    \"\"\"\n",
    "    start = time.time()\n",
    "    policy = np.random.choice(env.nA, size=(env.nS))  # initialize a random policy\n",
    "    ########################### Your Code Here ###########################\n",
    "    for i in range(max_iterations):\n",
    "        old_policy_v = compute_policy_v(env, policy, gamma)\n",
    "        new_policy = extract_policy(old_policy_v, gamma)\n",
    "        if (np.all(policy == new_policy)):\n",
    "            end = time.time()\n",
    "            print(\"Policy iteration took {0} seconds.\".format(end - start))\n",
    "            print ('Policy-Iteration converged at step %d.' %(i+1))\n",
    "            break\n",
    "        policy = new_policy\n",
    "    return policy\n",
    "    \n",
    "    \n",
    "    ########################### End of your code #########################\n",
    "    end = time.time()\n",
    "    print(\"Policy iteration took {0} seconds.\".format(end - start))\n",
    "    return policy\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    np.random.seed(1111)\n",
    "    env_name  = 'FrozenLake8x8-v0'\n",
    "    for gamma in [.9, .95, .99, .9999, 1]:\n",
    "        print(\"-\"*10, \"Gamma={0}\".format(gamma) ,\"-\"*10)\n",
    "        env = gym.make(env_name)\n",
    "        optimal_policy = policy_iteration(env, gamma=gamma)\n",
    "        scores = evaluate_policy(env, optimal_policy, gamma=gamma)\n",
    "        print('Average scores = ', np.mean(scores))"
   ]
  },
  {
   "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.6.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}