Policy_Iteration_vs_Value_Iteration.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Policy Iteration vs Value Iteration.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyOyDiby6voUcdSHIUAEeHAG",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/KhangTran2503/AI/blob/master/Policy_Iteration_vs_Value_Iteration.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tMgDY2HeM-SQ",
        "colab_type": "text"
      },
      "source": [
        "### **Kết quả:**\n",
        ">  Trong toy games FrozenLakev0 và FrozeLake8x8-v0 thì Policy Iteration chạy nhanh hơn.\n",
        ">  Còn trong Taxi-v3 thì Value Iteration chạy nhanh hơn.\n",
        "\n",
        "\n",
        "###**Nhận xét:**\n",
        "> 1. Policy Iteration cài đặt phức tạp hơn Value Iteration.\n",
        "> 2. Policy Iteration thường hội tụ nhanh hơn nhưng lại phức tạp về mặt tính toán.\n",
        "> 3. Policy Iteration dựa vào optimality Bellman operator\n",
        "  còn Value Iteration thì là  Bellman operator.\n",
        "\n",
        "###**Tham Khảo:**\n",
        "1. [What is difference between value iteration and policy iteration?](https://stackoverflow.com/questions/37370015/what-is-the-difference-between-value-iteration-and-policy-iteration)\n",
        "2. [Value Iteration](http://incompleteideas.net/book/first/ebook/node44.html)\n",
        "3. [Policy Iteration](http://incompleteideas.net/book/first/ebook/node43.html)\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y06n78cmM-x3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import gym\n",
        "import numpy as np\n",
        "import time"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aVqhBJlUSgbT",
        "colab_type": "text"
      },
      "source": [
        "### **Policy Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BFMiQXl7NfsM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Policy():\n",
        "    def __init__(self, name: str, max_iters, gamma):\n",
        "        self.env = gym.make(name)\n",
        "        self.max_iters = max_iters\n",
        "        self.gamma = gamma\n",
        "        self.name = name \n",
        "    \n",
        "    def policy_evaluation(self, policy):\n",
        "    \n",
        "        # initialize value table with zeros\n",
        "        v_values = np.zeros(self.env.observation_space.n)\n",
        "        while True:\n",
        "        \n",
        "            # store prev_v_values \n",
        "            prev_v_values = np.copy(v_values)\n",
        "\n",
        "            # for each state, compute the value according to the policy\n",
        "            for state in range(self.env.observation_space.n):\n",
        "                action = policy[state]\n",
        "                q_value = 0\n",
        "                for prob, next_state, reward, done in self.env.P[state][action]:\n",
        "                    q_value += prob* (reward + self.gamma * prev_v_values[next_state])\n",
        "\n",
        "                v_values[state] = q_value\n",
        "            \n",
        "            # check convergence\n",
        "            if np.all(np.isclose(v_values, prev_v_values)):\n",
        "                break\n",
        "            \n",
        "        return v_values\n",
        "\n",
        "    def policy_extraction(self, v_values):\n",
        " \n",
        "        # Initialize the policy with zeros\n",
        "        policy = np.zeros(self.env.observation_space.n, dtype=np.int) \n",
        "    \n",
        "        for state in range(self.env.observation_space.n):\n",
        "        \n",
        "            # initialize the q_values for a state\n",
        "            q_values = np.zeros(self.env.action_space.n)\n",
        "        \n",
        "            # compute q_value for all ations in the state\n",
        "            for action in range(self.env.action_space.n):\n",
        "                q_value = 0\n",
        "                for prob, next_state, reward, done in self.env.P[state][action]:\n",
        "                    q_value += prob* (reward + self.gamma * v_values[next_state])\n",
        "                q_values[action] = q_value\n",
        "            # Select the best action\n",
        "            policy[state] = np.argmax(q_values)\n",
        "    \n",
        "        return policy \n",
        "\n",
        "    def policy_iteration(self):\n",
        "    \n",
        "        # Initialize policy with zeros\n",
        "        #old_policy = np.zeros(env.observation_space.n)\n",
        "        old_policy = np.random.choice(self.env.action_space.n, size=(self.env.observation_space.n))\n",
        "    \n",
        "        for i in range(self.max_iters):\n",
        "        \n",
        "            # compute new_value from policy_evaluation function\n",
        "            new_value = self.policy_evaluation(old_policy)\n",
        "        \n",
        "            # Extract new policy from policy_extraction function\n",
        "            new_policy = self.policy_extraction(new_value)\n",
        "\n",
        "            if (np.all(old_policy == new_policy)):\n",
        "                print('Policy-iteration coverged at {}-th iteration.'.format(i+1))\n",
        "                break\n",
        "            old_policy = new_policy\n",
        "        \n",
        "        return new_policy\n",
        "    \n",
        "    def play(self, policy):\n",
        "        state = self.env.reset()\n",
        "        steps = 0\n",
        "        done = False\n",
        "        while not done:\n",
        "            action = policy[state]\n",
        "            next_state, reward, done, info = self.env.step(action)\n",
        "            steps += 1\n",
        "            state = next_state\n",
        "    \n",
        "        return (reward, steps)\n",
        "\n",
        "    def isGoal(self,reward):\n",
        "        if self.name == 'Taxi-v3': return (reward > 0)\n",
        "        else: return (reward == 1)\n",
        "        \n",
        "    def play_multiple_times(self,policy):\n",
        "        num_episodes = 1000\n",
        "        list_of_steps = []\n",
        "        num_failures = 0\n",
        "        temp = 0\n",
        "    \n",
        "        for i in range(num_episodes):\n",
        "            reward, steps = self.play(policy)\n",
        "            if self.isGoal(reward):\n",
        "               list_of_steps.append(steps)\n",
        "            else:\n",
        "                num_failures += 1\n",
        "\n",
        "        print('# failures: {}/{}'.format(num_failures, num_episodes))\n",
        "        print('avg. # steps: {}'.format(np.mean(list_of_steps)))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1t2VYOK7SqRF",
        "colab_type": "text"
      },
      "source": [
        "### **Value Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LhWULmBxS__e",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Value():\n",
        "    def __init__(self, name: str, max_iters, gamma):\n",
        "        self.env = gym.make(name)\n",
        "        self.max_iters = max_iters\n",
        "        self.gamma = gamma\n",
        "        self.name = name \n",
        "\n",
        "    def optimal_value(self):\n",
        "        v_values = np.zeros(self.env.observation_space.n)\n",
        "        for i in range(self.max_iters):\n",
        "            prev_v_values = np.copy(v_values)\n",
        "\n",
        "            # Compute value for each state\n",
        "            for state in range(self.env.observation_space.n):\n",
        "                q_values = []\n",
        "\n",
        "                # Compute q-value for each action\n",
        "                for action in range(self.env.action_space.n):                \n",
        "                    q_value = 0\n",
        "                    for prob, next_state, reward, done in self.env.P[state][action]:\n",
        "                        q_value += prob * (reward + self.gamma * prev_v_values[next_state])\n",
        "                    q_values.append(q_value)\n",
        "                \n",
        "                # Select the best action\n",
        "                best_action = np.argmax(np.asarray(q_values))\n",
        "                v_values[state] = q_values[best_action]\n",
        "            \n",
        "            # Check convergence\n",
        "            if np.all(np.isclose(v_values, prev_v_values)):\n",
        "                print('Value-iteration converged at {}-th iteration.'.format(i))\n",
        "                break\n",
        "        \n",
        "        return v_values\n",
        "\n",
        "    def value_iteration(self):\n",
        "        v_values = self.optimal_value()\n",
        "        policy = np.zeros(self.env.observation_space.n, dtype=np.int)\n",
        "        \n",
        "        # Compute the best action for each state in the game\n",
        "        # Compute q-values for each (state-action) pair in the game\n",
        "        for state in range(self.env.observation_space.n):\n",
        "            q_values = []\n",
        "\n",
        "            # Compute q-values for each action\n",
        "            for action in range(self.env.action_space.n):\n",
        "                q_value = 0\n",
        "                for prob, next_state, reward, done in self.env.P[state][action]:\n",
        "                    q_value += prob * (reward + self.gamma * v_values[next_state])\n",
        "                q_values.append(q_value)\n",
        "\n",
        "            # Select the best action\n",
        "            best_action = np.argmax(np.asarray(q_values))\n",
        "            policy[state] = best_action\n",
        "        \n",
        "        return policy\n",
        "\n",
        "    def play(self, policy):\n",
        "        state = self.env.reset()\n",
        "        steps = 0\n",
        "        done = False\n",
        "        while not done:\n",
        "            action = policy[state]\n",
        "            next_state, reward, done, info = self.env.step(action)\n",
        "            steps += 1\n",
        "            state = next_state\n",
        "    \n",
        "        return (reward, steps)\n",
        "\n",
        "    def isGoal(self,reward):\n",
        "        if self.name == 'Taxi-v3': return (reward > 0)\n",
        "        else: return (reward == 1)\n",
        "\n",
        "    def play_multiple_times(self,policy):\n",
        "        num_episodes = 1000\n",
        "        list_of_steps = []\n",
        "        num_failures = 0\n",
        "        temp = 0\n",
        "    \n",
        "        for i in range(num_episodes):\n",
        "            reward, steps = self.play(policy)\n",
        "            if self.isGoal(reward):\n",
        "               list_of_steps.append(steps)\n",
        "            else:\n",
        "                num_failures += 1\n",
        "\n",
        "        print('# failures: {}/{}'.format(num_failures, num_episodes))\n",
        "        print('avg. # steps: {}'.format(np.mean(list_of_steps)))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fREhkg1zWK5Z",
        "colab_type": "text"
      },
      "source": [
        "####**FrozenLakev0 :**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pc-EkPd_WU_P",
        "colab_type": "text"
      },
      "source": [
        "**1. Policy Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9qEdLM98UciU",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "6285896e-485b-45b6-82b1-fee891996839"
      },
      "source": [
        "#start time \n",
        "start_time = time.time()\n",
        "\n",
        "#Run Game\n",
        "FrozenLake_v0 = Policy('FrozenLake-v0', max_iters=1000, gamma=0.9)\n",
        "policy = FrozenLake_v0.policy_iteration()\n",
        "\n",
        "#End time\n",
        "end_time = time.time()\n",
        "\n",
        "#Total time\n",
        "print(\"Execute time Policy_iteration: {}\".format(end_time-start_time))\n",
        "\n",
        "#Avg\n",
        "FrozenLake_v0.play_multiple_times(policy)"
      ],
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Policy-iteration coverged at 3-th iteration.\n",
            "Execute time Policy_iteration: 0.0345458984375\n",
            "# failures: 283/1000\n",
            "avg. # steps: 36.38772663877266\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hC0Lu_VwXmcQ",
        "colab_type": "text"
      },
      "source": [
        "**2.Value Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NXunnUPaXref",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "6b2ab678-ab9d-46cb-ee81-3d442f4a6d9b"
      },
      "source": [
        "#start time\n",
        "start_time = time.time()\n",
        "\n",
        "# Run Game\n",
        "FrozenLake_v0 = Value('FrozenLake-v0', max_iters=1000, gamma=0.9)\n",
        "policy = FrozenLake_v0.value_iteration()\n",
        "\n",
        "#End time\n",
        "end_time = time.time()\n",
        "\n",
        "#Total time\n",
        "print(\"Execute time Value_iteration: {}\".format(end_time-start_time))\n",
        "\n",
        "#Avg\n",
        "FrozenLake_v0.play_multiple_times(policy)"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Value-iteration converged at 79-th iteration.\n",
            "Execute time Value_iteration: 0.04042673110961914\n",
            "# failures: 258/1000\n",
            "avg. # steps: 37.288409703504044\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8ChinytFYEZC",
        "colab_type": "text"
      },
      "source": [
        "####**FrozenLake8x8-v0 :**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "waL_CuGKYKrQ",
        "colab_type": "text"
      },
      "source": [
        "**1. Policy Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vbRWlFZvYNur",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "a45a2475-28e4-4106-f15b-651066d99dff"
      },
      "source": [
        "#start time \n",
        "start_time = time.time()\n",
        "\n",
        "#Run Game\n",
        "FrozenLake8x8_v0 = Policy('FrozenLake8x8-v0', max_iters=1000, gamma=0.9)\n",
        "policy = FrozenLake8x8_v0.policy_iteration()\n",
        "\n",
        "#End time\n",
        "end_time = time.time()\n",
        "\n",
        "#Total time\n",
        "print(\"Execute time Policy_iteration: {}\".format(end_time-start_time))\n",
        "\n",
        "#Avg\n",
        "FrozenLake8x8_v0.play_multiple_times(policy)"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Policy-iteration coverged at 8-th iteration.\n",
            "Execute time Policy_iteration: 0.216172456741333\n",
            "# failures: 250/1000\n",
            "avg. # steps: 70.66533333333334\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RiT3VBTmYOTR",
        "colab_type": "text"
      },
      "source": [
        "**2.Value Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TED2H1Q2YRk3",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "3fcd2890-ab37-4300-c1f7-7649a5d7f70e"
      },
      "source": [
        "#start time\n",
        "start_time = time.time()\n",
        "\n",
        "# Run Game\n",
        "FrozenLake8x8_v0 = Value('FrozenLake8x8-v0', max_iters=1000, gamma=0.9)\n",
        "policy = FrozenLake8x8_v0.value_iteration()\n",
        "\n",
        "#End time\n",
        "end_time = time.time()\n",
        "\n",
        "#Total time\n",
        "print(\"Execute time Value_iteration: {}\".format(end_time-start_time))\n",
        "\n",
        "#Avg\n",
        "FrozenLake8x8_v0.play_multiple_times(policy)"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Value-iteration converged at 117-th iteration.\n",
            "Execute time Value_iteration: 0.27852559089660645\n",
            "# failures: 257/1000\n",
            "avg. # steps: 74.36339165545087\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FEVkPI7hYTX1",
        "colab_type": "text"
      },
      "source": [
        "####**Taxi-v3:**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OFUFQo78YWrW",
        "colab_type": "text"
      },
      "source": [
        "**1. Policy Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DNICtx2yYZ6Q",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "7c2ef3ef-fa38-4a53-ecf1-37d15a7fb10d"
      },
      "source": [
        "#start time \n",
        "start_time = time.time()\n",
        "\n",
        "#Run Game\n",
        "Taxi_v3 = Policy('Taxi-v3', max_iters=1000, gamma=0.9)\n",
        "policy = Taxi_v3.policy_iteration()\n",
        "\n",
        "#End time\n",
        "end_time = time.time()\n",
        "\n",
        "#Total time\n",
        "print(\"Execute time Policy_iteration: {}\".format(end_time-start_time))\n",
        "\n",
        "#Avg\n",
        "Taxi_v3.play_multiple_times(policy)"
      ],
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Policy-iteration coverged at 18-th iteration.\n",
            "Execute time Policy_iteration: 2.701164722442627\n",
            "# failures: 0/1000\n",
            "avg. # steps: 12.996\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZKC7YWZzYaeD",
        "colab_type": "text"
      },
      "source": [
        "**2.Value Iteration:**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "We3pmpc6YkUi",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "ae6d8fd5-46f4-4683-f5ac-cbff7aa12a13"
      },
      "source": [
        "#start time\n",
        "start_time = time.time()\n",
        "\n",
        "# Run Game\n",
        "Taxi_v3 = Value('Taxi-v3', max_iters=1000, gamma=0.9)\n",
        "policy = Taxi_v3.value_iteration()\n",
        "\n",
        "#End time\n",
        "end_time = time.time()\n",
        "\n",
        "#Total time\n",
        "print(\"Execute time Value_iteration: {}\".format(end_time-start_time))\n",
        "\n",
        "#Avg\n",
        "Taxi_v3.play_multiple_times(policy)"
      ],
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Value-iteration converged at 116-th iteration.\n",
            "Execute time Value_iteration: 0.9904379844665527\n",
            "# failures: 0/1000\n",
            "avg. # steps: 13.234\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}