Modified Grid World RL Problem (Value Iteration Algorithm).ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wZQQHSt_TRjc"
      },
      "source": [
        "## Value Iteration Algorithm\n",
        "\n",
        "**Questions:**\n",
        "\n",
        "1) Write the value iteration algorithm in Python and find the optimal state value for all states. Assume a discounting factor 𝛾 = 0.8.\n",
        "\n",
        "2) Write an algorithm in Python which computes the optimal policy 𝜋 for all states.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "720cdiWXZEEB"
      },
      "source": [
        "### **1. Preparatory Processes**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "-jOPvnPEVY7_"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "\n",
        "# Define the rows and columns\n",
        "n_rows = 3\n",
        "n_cols = 5\n",
        "\n",
        "# Define the terminal states and the walls/impossible states\n",
        "terminals = [(0, 4), (2, 3)]\n",
        "walls = [(0, 3), (1, 1)]\n",
        "\n",
        "# Define the possible actions at each state\n",
        "actions = [\"UP\", \"RIGHT\", \"DOWN\", \"LEFT\"]\n",
        "\n",
        "# Define the row and column changes from each state to new states depending on actions taken\n",
        "row_change = [-1, 0, 1, 0] # up, right, down, left\n",
        "col_change = [0, 1, 0, -1] # up, right, down, left\n",
        "\n",
        "# Define the motion model\n",
        "motion_probs = {\n",
        "    'UP':    {'UP': 0.8, 'RIGHT': 0.1, 'DOWN': 0.0, 'LEFT': 0.1},\n",
        "    'RIGHT': {'UP': 0.1, 'RIGHT': 0.8, 'DOWN': 0.1, 'LEFT': 0.0},\n",
        "    'DOWN':  {'UP': 0.0, 'RIGHT': 0.1, 'DOWN': 0.8, 'LEFT': 0.1},\n",
        "    'LEFT':  {'UP': 0.1, 'RIGHT': 0.0, 'DOWN': 0.1, 'LEFT': 0.8}\n",
        "}\n",
        "\n",
        "# Definition and initialization of the reward function\n",
        "R = np.full((n_rows, n_cols), -0.1)\n",
        "R[0, 4] = 1 # Reward at terminal state I (Goal state)\n",
        "R[2, 3] = -1 # Reward at terminal state II (Bad state)\n",
        "\n",
        "# Define the number of episodes (or iterations)\n",
        "episode = 100\n",
        "\n",
        "# Define the discount factor\n",
        "gamma = 0.8\n",
        "\n",
        "# Define threshold\n",
        "threshold = 1e-6\n",
        "\n",
        "# Definition and initialization of the value for each state.\n",
        "v = np.zeros((n_rows, n_cols))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Hir3gMpM61b"
      },
      "source": [
        "### **2. Now it's time to implement the value iteration algorithm using the Bellman equation.**\n",
        "\n",
        "\n",
        "*   ### Bellman equation: **V(s) = R(s) + γmax(∑(P(s'|s,a)* V(s'))**\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fTthVQIwM1oj",
        "outputId": "5aaf0a9a-f8e0-4bae-ad9b-8fc19ca12e86"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "---------------------------------------------------\n",
            "\n",
            "Episode: 0\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.10000\n",
            "New value for state v(0, 1) = -0.10000\n",
            "New value for state v(0, 2) = -0.10000\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.10000\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = -0.10000\n",
            "New value for state v(1, 3) = -0.10000\n",
            "New value for state v(1, 4) = 0.53200\n",
            "New value for state v(2, 0) = -0.10000\n",
            "New value for state v(2, 1) = -0.10000\n",
            "New value for state v(2, 2) = -0.10800\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.16048\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 1\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.18000\n",
            "New value for state v(0, 1) = -0.18000\n",
            "New value for state v(0, 2) = -0.18000\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.18000\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = -0.18512\n",
            "New value for state v(1, 3) = 0.15248\n",
            "New value for state v(1, 4) = 0.59476\n",
            "New value for state v(2, 0) = -0.18000\n",
            "New value for state v(2, 1) = -0.18512\n",
            "New value for state v(2, 2) = -0.24193\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.21348\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 2\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.24400\n",
            "New value for state v(0, 1) = -0.24400\n",
            "New value for state v(0, 2) = -0.24441\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.24400\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = -0.04132\n",
            "New value for state v(1, 3) = 0.21284\n",
            "New value for state v(1, 4) = 0.60461\n",
            "New value for state v(2, 0) = -0.24441\n",
            "New value for state v(2, 1) = -0.25738\n",
            "New value for state v(2, 2) = -0.22704\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22403\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 3\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.29520\n",
            "New value for state v(0, 1) = -0.29546\n",
            "New value for state v(0, 2) = -0.16963\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.29546\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.00449\n",
            "New value for state v(1, 3) = 0.22398\n",
            "New value for state v(1, 4) = 0.60629\n",
            "New value for state v(2, 0) = -0.29657\n",
            "New value for state v(2, 1) = -0.28648\n",
            "New value for state v(2, 2) = -0.20005\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22595\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 4\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.33618\n",
            "New value for state v(0, 1) = -0.25584\n",
            "New value for state v(0, 2) = -0.13117\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33708\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.01685\n",
            "New value for state v(1, 3) = 0.22594\n",
            "New value for state v(1, 4) = 0.60658\n",
            "New value for state v(2, 0) = -0.33404\n",
            "New value for state v(2, 1) = -0.27387\n",
            "New value for state v(2, 2) = -0.19113\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22629\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 5\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.31760\n",
            "New value for state v(0, 1) = -0.22488\n",
            "New value for state v(0, 2) = -0.11770\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.35719\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.01990\n",
            "New value for state v(1, 3) = 0.22629\n",
            "New value for state v(1, 4) = 0.60663\n",
            "New value for state v(2, 0) = -0.33057\n",
            "New value for state v(2, 1) = -0.26614\n",
            "New value for state v(2, 2) = -0.18856\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22635\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 6\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.29791\n",
            "New value for state v(0, 1) = -0.21131\n",
            "New value for state v(0, 2) = -0.11359\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.34781\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02065\n",
            "New value for state v(1, 3) = 0.22635\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.32460\n",
            "New value for state v(2, 1) = -0.26326\n",
            "New value for state v(2, 2) = -0.18784\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 7\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.28690\n",
            "New value for state v(0, 1) = -0.20651\n",
            "New value for state v(0, 2) = -0.11239\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33926\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02084\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.32159\n",
            "New value for state v(2, 1) = -0.26234\n",
            "New value for state v(2, 2) = -0.18765\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 8\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.28226\n",
            "New value for state v(0, 1) = -0.20497\n",
            "New value for state v(0, 2) = -0.11205\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33493\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02089\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.32042\n",
            "New value for state v(2, 1) = -0.26207\n",
            "New value for state v(2, 2) = -0.18759\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 9\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.28056\n",
            "New value for state v(0, 1) = -0.20451\n",
            "New value for state v(0, 2) = -0.11195\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33314\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.32001\n",
            "New value for state v(2, 1) = -0.26199\n",
            "New value for state v(2, 2) = -0.18758\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 10\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27998\n",
            "New value for state v(0, 1) = -0.20437\n",
            "New value for state v(0, 2) = -0.11193\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33249\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31987\n",
            "New value for state v(2, 1) = -0.26197\n",
            "New value for state v(2, 2) = -0.18758\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 11\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27980\n",
            "New value for state v(0, 1) = -0.20433\n",
            "New value for state v(0, 2) = -0.11192\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33227\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31983\n",
            "New value for state v(2, 1) = -0.26196\n",
            "New value for state v(2, 2) = -0.18757\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 12\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27974\n",
            "New value for state v(0, 1) = -0.20432\n",
            "New value for state v(0, 2) = -0.11192\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33220\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31982\n",
            "New value for state v(2, 1) = -0.26196\n",
            "New value for state v(2, 2) = -0.18757\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 13\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27972\n",
            "New value for state v(0, 1) = -0.20432\n",
            "New value for state v(0, 2) = -0.11192\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33217\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31982\n",
            "New value for state v(2, 1) = -0.26196\n",
            "New value for state v(2, 2) = -0.18757\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 14\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27972\n",
            "New value for state v(0, 1) = -0.20432\n",
            "New value for state v(0, 2) = -0.11192\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33217\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31981\n",
            "New value for state v(2, 1) = -0.26196\n",
            "New value for state v(2, 2) = -0.18757\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 15\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27971\n",
            "New value for state v(0, 1) = -0.20432\n",
            "New value for state v(0, 2) = -0.11192\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33216\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31981\n",
            "New value for state v(2, 1) = -0.26196\n",
            "New value for state v(2, 2) = -0.18757\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "---------------------------------------------------\n",
            "\n",
            "Episode: 16\n",
            "\n",
            "---------------------------------------------------\n",
            "\n",
            "New value for state v(0, 0) = -0.27971\n",
            "New value for state v(0, 1) = -0.20432\n",
            "New value for state v(0, 2) = -0.11192\n",
            "Value for blocked state v (0, 3) is Nil\n",
            "Value for state v (0, 4) = 1.0\n",
            "New value for state v(1, 0) = -0.33216\n",
            "Value for blocked state v (1, 1) is Nil\n",
            "New value for state v(1, 2) = 0.02091\n",
            "New value for state v(1, 3) = 0.22636\n",
            "New value for state v(1, 4) = 0.60664\n",
            "New value for state v(2, 0) = -0.31981\n",
            "New value for state v(2, 1) = -0.26196\n",
            "New value for state v(2, 2) = -0.18757\n",
            "Value for state v (2, 3) = -1.0\n",
            "New value for state v(2, 4) = 0.22636\n",
            "----------------------------------------------\n",
            "\n",
            "\n",
            "Final value of v is: \n",
            "\n",
            " [[-0.27971321 -0.20431722 -0.11191632  0.          1.        ]\n",
            " [-0.33216257  0.          0.02090994  0.22635815  0.60663984]\n",
            " [-0.31981351 -0.26196157 -0.18757456 -1.          0.22635815]]\n"
          ]
        }
      ],
      "source": [
        "# Value iteration algorithm\n",
        "for e in range(episode):\n",
        "  print(\"---------------------------------------------------\\n\")\n",
        "  print(f\"Episode: {e}\\n\")\n",
        "  print(\"---------------------------------------------------\\n\")\n",
        "  delta = 0\n",
        "  for row in range(n_rows):\n",
        "    for col in range(n_cols):\n",
        "        if (row, col) == terminals[0]:\n",
        "          v[row, col] = 1\n",
        "          print(f\"Value for state v {row, col} = {v[row,col]}\")\n",
        "          continue\n",
        "\n",
        "        elif (row, col) == terminals[1]:\n",
        "          v[row, col] = -1\n",
        "          print(f\"Value for state v {row, col} = {v[row,col]}\")\n",
        "          continue\n",
        "\n",
        "        elif (row, col) in walls:\n",
        "          print(f\"Value for blocked state v {row, col} is Nil\")\n",
        "          continue\n",
        "\n",
        "        else:\n",
        "          p_next_states = [] # Initialize list for plausible next states\n",
        "          v_next_states = [] # Initialize list for the values of the plausible next states\n",
        "          for i, a in enumerate(actions):\n",
        "              next_row = row + row_change[i]\n",
        "              next_col = col + col_change[i]\n",
        "              if next_row < 0 or next_row >= n_rows or next_col < 0 or next_col >= n_cols or (next_row, next_col) in walls: # Checking to ensure boundaries of the environment is not violated.\n",
        "                  next_state = (row, col)\n",
        "                  p_next_states.append(next_state)\n",
        "                  v_next_states.append(v[next_state])\n",
        "              else:\n",
        "                  next_state = (next_row, next_col)\n",
        "                  p_next_states.append(next_state)\n",
        "                  v_next_states.append(v[next_state])\n",
        "\n",
        "          v_check = []  # Initialize empty list for the value of state after taking an action from up, right, down, left.\n",
        "          old_v = v[row, col] # Define old value to check for convergence\n",
        "          for a in actions:\n",
        "            act_prob = list(motion_probs[a].values())\n",
        "            temp_res = [act_prob[i] * v_next_states[i] for i in range(len(v_next_states))] # (P(s'|s,a)* V(s')\n",
        "            sum_temp_res = sum(temp_res) # ∑(P(s'|s,a)* V(s')\n",
        "            v_check.append(sum_temp_res)\n",
        "          v_selected = max(v_check)\n",
        "          v[row, col] = R[row, col] + gamma * v_selected # R(s) + γmax(∑(P(s'|s,a)* V(s'))\n",
        "          print(f\"New value for state v{row,col} = {v[row,col]:.5f}\")\n",
        "          delta = max(delta, abs(old_v - v[row,col]))\n",
        "\n",
        "  if delta < threshold:\n",
        "    print(\"----------------------------------------------\\n\")\n",
        "    print(f\"\\nFinal value of v is: \\n\\n {v}\")\n",
        "    break\n",
        "  else:\n",
        "    continue # go to next episode"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XrUfRtYOOeYZ"
      },
      "source": [
        "### **3. After the value iteration converges, the optimal policy for each state can be obtained.**\n",
        "* This is implemented by selecting the action which yields the maximum value in each state.\n",
        "* ### **π\\*(s) = argmax(∑(P(s'|s,a)* V(s'))**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OKKuFtYv4wK7",
        "outputId": "5c0f0727-594d-4552-9baa-369a6978bbee"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The optimal policy for each state is as shown below: \n",
            "\n",
            "\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "[['RIGHT', 'RIGHT', 'DOWN', 'None', 'Terminal'],\n",
              " ['UP', 'None', 'RIGHT', 'RIGHT', 'UP'],\n",
              " ['RIGHT', 'RIGHT', 'UP', 'Terminal', 'UP']]"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# Deriving the optimal policy\n",
        "\n",
        "# initialize the opt_policy with a series of texts\n",
        "opt_policy = [['undecided', 'undecided', 'undecided', 'None', 'Terminal'],\n",
        "              ['undecided', 'None', 'undecided', 'undecided', 'undecided'],\n",
        "              ['undecided', 'undecided', 'undecided', 'Terminal', 'undecided']]\n",
        "\n",
        "\n",
        "for row in range(n_rows):\n",
        "    for col in range(n_cols):\n",
        "        if (row, col) == terminals[0]:\n",
        "          v[row, col] = 1\n",
        "          continue\n",
        "        elif (row, col) == terminals[1]:\n",
        "          v[row, col] = -1\n",
        "          continue\n",
        "        elif (row, col) in walls:\n",
        "          continue\n",
        "        else:\n",
        "          p_next_states = []\n",
        "          v_next_states = []\n",
        "          for i, a in enumerate(actions):\n",
        "              next_row = row + row_change[i]\n",
        "              next_col = col + col_change[i]\n",
        "              if next_row < 0 or next_row >= n_rows or next_col < 0 or next_col >= n_cols or (next_row, next_col) in walls:\n",
        "                  next_state = (row, col)\n",
        "                  p_next_states.append(next_state)\n",
        "                  v_next_states.append(v[next_state])\n",
        "              else:\n",
        "                  next_state = (next_row, next_col)\n",
        "                  p_next_states.append(next_state)\n",
        "                  v_next_states.append(v[next_state])\n",
        "          v_check = []\n",
        "          for a in actions:\n",
        "            act_prob = list(motion_probs[a].values())\n",
        "            temp_res = [v_next_states[i] * act_prob[i] for i in range(len(v_next_states))]\n",
        "            sum_temp_res = sum(temp_res)\n",
        "            v_check.append(sum_temp_res) # ∑(P(s'|s,a)* V(s')\n",
        "          max_index = np.argmax(v_check) # Extract the index of the highest value in that state: argmax(∑(P(s'|s,a)* V(s'))\n",
        "          opt_policy[row][col] = actions[max_index] # Update the policy\n",
        "\n",
        "print(\"The optimal policy for each state is as shown below: \\n\\n\")\n",
        "opt_policy"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lvhM4ZouTP1k"
      },
      "source": [
        "### **4a. From the optimal policy, we see that:**\n",
        "* In state (0,0): Go right\n",
        "* In state (0,1): Go right\n",
        "* In state (0,2): Go down\n",
        "* state (0,3) is a wall\n",
        "* state (0,4) is the goal state (terminal)\n",
        "* In state (1,0): Go up\n",
        "* state (1,1) is a wall\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y0_0qh0Na9Q5"
      },
      "source": [
        "### **4b. From the optimal policy, we see that:**\n",
        "* In state (1,2): Go right\n",
        "* In state (1,3): Go right\n",
        "* In state (1,4): Go up\n",
        "* In state (2,0): Go right\n",
        "* In state (2,1): Go right\n",
        "* In state (2,2): Go up\n",
        "* state (2,3) is the bad state (terminal)\n",
        "* In state (2, 4): Go up"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "chCIT6I_WCpe"
      },
      "source": [
        "### **Conclusion**\n",
        "\n",
        "Hence if starting at state (2,1), in python indexing (1,0). To get to the goal i.e. (0, 4) in python indexing at the shortest time possible. The Agent would follow this sequence of actions:\n",
        "* **`up -> right -> right -> down -> right -> right -> up`**"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}