Lesson_2_Exercise_1_Policy_Evaluation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Lesson-2-Exercise-1-Policy-Evaluation.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    }
  },
  "cells": [
    {
      "metadata": {
        "id": "w2c6Tfn8cqLI",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "          _____                _____                    _____                    _____                    _____                    _____          \n",
        "         /\\    \\              /\\    \\                  /\\    \\                  /\\    \\                  /\\    \\                  /\\    \\         \n",
        "        /::\\    \\            /::\\    \\                /::\\    \\                /::\\    \\                /::\\    \\                /::\\    \\        \n",
        "       /::::\\    \\           \\:::\\    \\              /::::\\    \\              /::::\\    \\              /::::\\    \\               \\:::\\    \\       \n",
        "      /::::::\\    \\           \\:::\\    \\            /::::::\\    \\            /::::::\\    \\            /::::::\\    \\               \\:::\\    \\      \n",
        "     /:::/\\:::\\    \\           \\:::\\    \\          /:::/\\:::\\    \\          /:::/\\:::\\    \\          /:::/\\:::\\    \\               \\:::\\    \\     \n",
        "    /:::/__\\:::\\    \\           \\:::\\    \\        /:::/__\\:::\\    \\        /:::/__\\:::\\    \\        /:::/__\\:::\\    \\               \\:::\\    \\    \n",
        "    \\:::\\   \\:::\\    \\          /::::\\    \\      /::::\\   \\:::\\    \\      /::::\\   \\:::\\    \\      /::::\\   \\:::\\    \\              /::::\\    \\   \n",
        "  ___\\:::\\   \\:::\\    \\        /::::::\\    \\    /::::::\\   \\:::\\    \\    /::::::\\   \\:::\\    \\    /::::::\\   \\:::\\    \\    ____    /::::::\\    \\  \n",
        " /\\   \\:::\\   \\:::\\    \\      /:::/\\:::\\    \\  /:::/\\:::\\   \\:::\\    \\  /:::/\\:::\\   \\:::\\____\\  /:::/\\:::\\   \\:::\\    \\  /\\   \\  /:::/\\:::\\    \\ \n",
        "/::\\   \\:::\\   \\:::\\____\\    /:::/  \\:::\\____\\/:::/  \\:::\\   \\:::\\____\\/:::/  \\:::\\   \\:::|    |/:::/  \\:::\\   \\:::\\____\\/::\\   \\/:::/  \\:::\\____\\\n",
        "\\:::\\   \\:::\\   \\::/    /   /:::/    \\::/    /\\::/    \\:::\\  /:::/    /\\::/   |::::\\  /:::|____|\\::/    \\:::\\  /:::/    /\\:::\\  /:::/    \\::/    /\n",
        " \\:::\\   \\:::\\   \\/____/   /:::/    / \\/____/  \\/____/ \\:::\\/:::/    /  \\/____|:::::\\/:::/    /  \\/____/ \\:::\\/:::/    /  \\:::\\/:::/    / \\/____/ \n",
        "  \\:::\\   \\:::\\    \\      /:::/    /                    \\::::::/    /         |:::::::::/    /            \\::::::/    /    \\::::::/    /          \n",
        "   \\:::\\   \\:::\\____\\    /:::/    /                      \\::::/    /          |::|\\::::/    /              \\::::/    /      \\::::/____/           \n",
        "    \\:::\\  /:::/    /    \\::/    /                       /:::/    /           |::| \\::/____/               /:::/    /        \\:::\\    \\           \n",
        "     \\:::\\/:::/    /      \\/____/                       /:::/    /            |::|  ~|                    /:::/    /          \\:::\\    \\          \n",
        "      \\::::::/    /                                    /:::/    /             |::|   |                   /:::/    /            \\:::\\    \\         \n",
        "       \\::::/    /                                    /:::/    /              \\::|   |                  /:::/    /              \\:::\\____\\        \n",
        "        \\::/    /                                     \\::/    /                \\:|   |                  \\::/    /                \\::/    /        \n",
        "         \\/____/                                       \\/____/                  \\|___|                   \\/____/                  \\/____/         "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "6qO-G91QVrYN",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Policy Evaluation Exercise"
      ]
    },
    {
      "metadata": {
        "id": "bAr7D9r8Vxns",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Dependency installation\n",
        "\n",
        "If current option doesn't work, try to execute commented lines."
      ]
    },
    {
      "metadata": {
        "id": "yUrdYdb9kN7x",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 479
        },
        "outputId": "03957dc3-f4be-4ef1-f216-1704223a8191"
      },
      "cell_type": "code",
      "source": [
        "# !python -m pip install -e git+https://github.com/star-ai/rl-environments.git#egg=rlenvs\n",
        "# !python -m pip install gym\n",
        "!pip install -e git+https://github.com/star-ai/rl-environments.git#egg=rlenvs\n",
        "!pip install gym"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Obtaining rlenvs from git+https://github.com/star-ai/rl-environments.git#egg=rlenvs\n",
            "  Cloning https://github.com/star-ai/rl-environments.git to ./src/rlenvs\n",
            "Installing collected packages: rlenvs\n",
            "  Running setup.py develop for rlenvs\n",
            "Successfully installed rlenvs\n",
            "Collecting gym\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/c3/44/3a63e8b87f642db49ac81239620e68df8cfae223dcfda4f8508aec88d204/gym-0.10.8.tar.gz (1.5MB)\n",
            "\u001b[K    100% |████████████████████████████████| 1.5MB 9.8MB/s \n",
            "\u001b[?25hRequirement already satisfied: scipy in /usr/local/lib/python3.6/dist-packages (from gym) (0.19.1)\n",
            "Requirement already satisfied: numpy>=1.10.4 in /usr/local/lib/python3.6/dist-packages (from gym) (1.14.6)\n",
            "Requirement already satisfied: requests>=2.0 in /usr/local/lib/python3.6/dist-packages (from gym) (2.18.4)\n",
            "Requirement already satisfied: six in /usr/local/lib/python3.6/dist-packages (from gym) (1.11.0)\n",
            "Collecting pyglet>=1.2.0 (from gym)\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/1c/fc/dad5eaaab68f0c21e2f906a94ddb98175662cc5a654eee404d59554ce0fa/pyglet-1.3.2-py2.py3-none-any.whl (1.0MB)\n",
            "\u001b[K    100% |████████████████████████████████| 1.0MB 13.1MB/s \n",
            "\u001b[?25hRequirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.6/dist-packages (from requests>=2.0->gym) (2018.8.24)\n",
            "Requirement already satisfied: urllib3<1.23,>=1.21.1 in /usr/local/lib/python3.6/dist-packages (from requests>=2.0->gym) (1.22)\n",
            "Requirement already satisfied: chardet<3.1.0,>=3.0.2 in /usr/local/lib/python3.6/dist-packages (from requests>=2.0->gym) (3.0.4)\n",
            "Requirement already satisfied: idna<2.7,>=2.5 in /usr/local/lib/python3.6/dist-packages (from requests>=2.0->gym) (2.6)\n",
            "Requirement already satisfied: future in /usr/local/lib/python3.6/dist-packages (from pyglet>=1.2.0->gym) (0.16.0)\n",
            "Building wheels for collected packages: gym\n",
            "  Running setup.py bdist_wheel for gym ... \u001b[?25l-\b \b\\\b \b|\b \b/\b \bdone\n",
            "\u001b[?25h  Stored in directory: /root/.cache/pip/wheels/ea/ec/dd/33bcc8801d345f0b640fced8a0864a7c8474828564bc5ccf70\n",
            "Successfully built gym\n",
            "Installing collected packages: pyglet, gym\n",
            "Successfully installed gym-0.10.8 pyglet-1.3.2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "rAqak04mWC4b",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Import dependecies"
      ]
    },
    {
      "metadata": {
        "id": "0evCgEg-kH0Y",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from IPython.core.debugger import set_trace\n",
        "import numpy as np\n",
        "import pprint\n",
        "\n",
        "# Import below can all of a sudden break\n",
        "# NOTE: if running locally, remove src.rlenvs from import\n",
        "from src.rlenvs.rlenvs.envs.gridworld import GridworldEnv"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "Bchk-IS7WTCB",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Create Environment\n",
        "\n",
        "OpenAI env. \n",
        "\n",
        "- **`env.P`** represents the transition probabilities of the environment.\n",
        "- **`env.P[s][a]`** is a list of transition tuples `(prob, next_state, reward, done).`\n",
        "- **`env.nS`** is a number of states in the environment. \n",
        "- **`env.nA`** is a number of actions in the environment."
      ]
    },
    {
      "metadata": {
        "id": "zrDI70xEkH0b",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "env = GridworldEnv()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "-4l6uZYvzRZi",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## What we implement\n",
        "\n",
        "$$\n",
        "v(s) = R_s + \\gamma \\sum_{s' \\in S} P_{ss'}V(s')\n",
        "$$"
      ]
    },
    {
      "metadata": {
        "id": "JfGUC1AcW9W3",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Implementation\n",
        "\n",
        "### Function to calculate state value"
      ]
    },
    {
      "metadata": {
        "id": "V_PdgdOzPK05",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def calculate_state_value(policy, state, env, V, discount_factor):\n",
        "    \"\"\"\n",
        "    Calculate state value given policy, state, and current state value function.\n",
        "\n",
        "    Args:\n",
        "      policy: Policy - [S, A] matrix of probabilities of action A given state S\n",
        "      env: Environment.\n",
        "        env.P[s][a] return list of transition tuples (transition_probability, \n",
        "          next_state, reward, done).\n",
        "      V: current state value function, V[s] return value for state s.\n",
        "    \"\"\"\n",
        "    v = 0\n",
        "    # Look at the possible next actions\n",
        "    for a, action_prob in enumerate(policy[state]):\n",
        "        # For each action, look at the possible next states...\n",
        "        for prob, next_state, reward, done in env.P[state][a]:\n",
        "            # Calculate the expected value\n",
        "            v += action_prob * prob * (reward + discount_factor * V[next_state])\n",
        "    return v"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "rP2wM3wfXMjN",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Function to calculate all states values and maximum change between current state values and new state values\n",
        "\n",
        "The change is required to identify if the State-value function is converged to the optimal."
      ]
    },
    {
      "metadata": {
        "id": "G702rqE2Ts__",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def run_full_sweep(policy, env, V, discount_factor):\n",
        "    \"\"\"\n",
        "    Run a full sweep over states.\n",
        "    \"\"\"\n",
        "    new_V = np.zeros(env.nS)\n",
        "    delta = 0\n",
        "    # For each state, perform a \"full backup\"\n",
        "    for s in range(env.nS):\n",
        "        v = calculate_state_value(policy, s, env, V, discount_factor)\n",
        "\n",
        "        # How much our value function changed (across any states)\n",
        "        delta = max(delta, np.abs(v - V[s]))\n",
        "        new_V[s] = v\n",
        "    return new_V, delta"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "htz1lhTWXlo-",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Function to evaluate given policy"
      ]
    },
    {
      "metadata": {
        "id": "Tub2Xxs6kH0d",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def policy_eval(policy, env, discount_factor=1.0, theta=0.00001):\n",
        "    \"\"\"\n",
        "    Evaluate a policy given an environment and a full description of the \n",
        "    environment's dynamics.\n",
        "    \n",
        "    Args:\n",
        "        policy: [S, A] shaped matrix representing the policy.\n",
        "        env: OpenAI env. env.P represents the transition probabilities of the \n",
        "          environment.\n",
        "            env.P[s][a] is a list of transition tuples (prob, next_state, reward,\n",
        "              done).\n",
        "            env.nS is a number of states in the environment. \n",
        "            env.nA is a number of actions in the environment.\n",
        "        theta: We stop evaluation once our value function change is less than \n",
        "          theta for all states.\n",
        "        discount_factor: Gamma discount factor.\n",
        "    \n",
        "    Returns:\n",
        "        Vector of length env.nS representing the value function.\n",
        "    \"\"\"\n",
        "    \n",
        "    # Start with a random (all 0) value function\n",
        "    V = np.zeros(env.nS)\n",
        "    while True:\n",
        "        V, delta = run_full_sweep(policy, env, V, discount_factor)\n",
        "        # Stop evaluating once our value function change is below a threshold\n",
        "        if delta < theta:\n",
        "            break\n",
        "    return np.array(V)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "5vBJZSdSXzH9",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Test Run\n",
        "\n",
        "### Initialise random policy (All actions have equal probabilty)"
      ]
    },
    {
      "metadata": {
        "id": "BAizPJCpkH0j",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "random_policy = np.ones([env.nS, env.nA]) / env.nA"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "AzAkuyrKX-A1",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Evaluate current policy"
      ]
    },
    {
      "metadata": {
        "id": "ztiVIB9UYCO4",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "v = policy_eval(random_policy, env)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "AmAqq4UWYD6K",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Print results"
      ]
    },
    {
      "metadata": {
        "id": "PDPM08oqkH0l",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "d962eba7-327d-4397-cf1a-01342eb3eb9a"
      },
      "cell_type": "code",
      "source": [
        "pp = pprint.PrettyPrinter(indent=2)\n",
        "print(\"Value Function:\")\n",
        "pp.pprint(np.reshape(v, (4, 4)))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Value Function:\n",
            "array([[  0.        , -13.99989315, -19.99984167, -21.99982282],\n",
            "       [-13.99989315, -17.99986052, -19.99984273, -19.99984167],\n",
            "       [-19.99984167, -19.99984273, -17.99986052, -13.99989315],\n",
            "       [-21.99982282, -19.99984167, -13.99989315,   0.        ]])\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "O7Dlq6jHYH31",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Simple test"
      ]
    },
    {
      "metadata": {
        "id": "wYM5Et6okH0o",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 136
        },
        "outputId": "ea32cda3-6058-482e-d7fa-f128a2a11d34"
      },
      "cell_type": "code",
      "source": [
        "# Test: Make sure the evaluated policy is what we expected\n",
        "expected_v = np.array([0, -14, -20, -22, -14, -18, -20, -20, -20, -20, -18, -14,\n",
        "                       -22, -20, -14, 0])\n",
        "print('Expected')\n",
        "pp.pprint(np.reshape(expected_v, (4,4)))\n",
        "print()\n",
        "np.testing.assert_array_almost_equal(v, expected_v, decimal=2)\n",
        "print('Test passed')"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Expected\n",
            "array([[  0, -14, -20, -22],\n",
            "       [-14, -18, -20, -20],\n",
            "       [-20, -20, -18, -14],\n",
            "       [-22, -20, -14,   0]])\n",
            "\n",
            "Test passed\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "ZVNYkW9cYXEN",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}