e_greedy_and_softmax_explained.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "e-greedy and softmax explained",
      "provenance": [],
      "authorship_tag": "ABX9TyMBN8kidxJ1kXeonXmf1o+j",
      "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/NicMaq/Reinforcement-Learning/blob/master/e_greedy_and_softmax_explained.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8jl8yZi1riWJ",
        "colab_type": "text"
      },
      "source": [
        "# ε-greedy and softmax policies\n",
        "\n",
        "This Google Colab was published to support the post: XXX Best Practices for Reinforcement Learning. <br> \n",
        "It also complements this [github](https://github.com/NicMaq/Reinforcement-Learning).\n",
        "<br><br>\n",
        "Here, I will detail the two policies ε-greedy and softmax.\n",
        "<br><br>\n",
        "The 𝜖-greedy policy is a special case of 𝜖-soft policies. It chooses the best action with a probability 1−𝜖 and a random action with probability 𝜖. \n",
        "<br>\n",
        "There are two problems with 𝜖-greedy. First, when it chooses the random actions, it chooses them uniformly, including the actions we know are bad. This limits the performance in training and this is bad for production environments. Therefore, when the network is used to evaluate performance or control a system, 𝜖 should be set to zero. On the flip side, setting 𝜖 to zero creates a second problem: we are now only exploiting our knowledge. We stopped exploring. If the dynamics of the system changes a little, our algorithm is unable to adapt.    \n",
        "<br>\n",
        "A solution to this problem is to select random actions with probabilities proportional to their current values. This is what softmax policies do. \n",
        "<br><br>\n",
        "**The policies have two distinct roles.** They are used **to find the best action** and they are used **to calculate the TD update**.  \n",
        "<br>\n",
        "First, in the following two cells, we import the required package and declare a few global constants.\n",
        "<br>\n",
        "I am running tensorflow 2.x.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jcVeOIxwrkMe",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%tensorflow_version 2.x\n",
        "\n",
        "import tensorflow as tf\n",
        "import numpy as np"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "B3ErgGZ2pGES",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# NUM_ACTIONS \n",
        "ACTIONS = {\n",
        "    0: \"NOOP\",\n",
        "    1: \"FIRE\",\n",
        "    3: \"RIGHT\",\n",
        "    4: \"LEFT\",\n",
        "    #5: \"RIGHTFIRE\",\n",
        "    #6: \"LEFTFIRE\",\n",
        "}\n",
        "NUM_ACTIONS = len(ACTIONS)\n",
        "\n",
        "# Tau = Softmax Policy\n",
        "TAU = 0.001\n",
        "# Epsilon = e-greedy Policy\n",
        "epsilon = 0.5\n",
        "# Gamma \n",
        "GAMMA = 0.99"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "at3xCP2bWqIa",
        "colab_type": "text"
      },
      "source": [
        "# e-greedy policy with tie management\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7rzb8WW4scAY",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "f644ea38-6468-4aca-cdbb-d45373f7cc4e"
      },
      "source": [
        "# Create a fake value of Q(s,a) for a mini batch of three experiences:\n",
        "qsa = [[-0.5, 0.7, 0.6, 0.8],[-0.6, 0.9, 0.7, 0.9],[-0.3, -0.9, -0.2, -0.4]]\n",
        "qsa_tf = tf.convert_to_tensor(qsa)\n",
        "print('qsa_tf is: ', qsa_tf)   \n",
        "\n",
        "batch_terminal = [[0],[0],[1]]\n",
        "batch_reward = [[1],[2],[3]]"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "qsa_tf is:  tf.Tensor(\n",
            "[[-0.5  0.7  0.6  0.8]\n",
            " [-0.6  0.9  0.7  0.9]\n",
            " [-0.3 -0.9 -0.2 -0.4]], shape=(3, 4), dtype=float32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M1G8PO93sgzW",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 374
        },
        "outputId": "85a43aa2-a297-4632-dedc-c21dff118626"
      },
      "source": [
        "# Find the maximums of Q(s,a)\n",
        "all_ones = tf.ones_like(qsa)\n",
        "qsa_max = tf.math.reduce_max(qsa_tf, axis=1, keepdims=True)\n",
        "print('qsa_max is: ', qsa_max)\n",
        "\n",
        "qsa_max_mat = qsa_max * all_ones\n",
        "print('qsa_max_mat is: ', qsa_max_mat)\n",
        "\n",
        "losers = tf.zeros_like(qsa_tf)\n",
        "qsa_maximums = tf.where(tf.equal(qsa_max_mat, qsa_tf), x =all_ones, y =losers)\n",
        "print('qsa_maximums is: ', qsa_maximums)\n",
        "\n",
        "qsa_maximums_ind = tf.where(tf.equal(qsa_max_mat, qsa_tf))\n",
        "print('qsa_maximums_ind is: ', qsa_maximums_ind)\n",
        "\n",
        "nb_maximums = tf.math.reduce_sum(qsa_maximums, axis=1, keepdims=True)\n",
        "print('nb_maximums is: ', nb_maximums)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "qsa_max is:  tf.Tensor(\n",
            "[[ 0.8]\n",
            " [ 0.9]\n",
            " [-0.2]], shape=(3, 1), dtype=float32)\n",
            "qsa_max_mat is:  tf.Tensor(\n",
            "[[ 0.8  0.8  0.8  0.8]\n",
            " [ 0.9  0.9  0.9  0.9]\n",
            " [-0.2 -0.2 -0.2 -0.2]], shape=(3, 4), dtype=float32)\n",
            "qsa_maximums is:  tf.Tensor(\n",
            "[[0. 0. 0. 1.]\n",
            " [0. 1. 0. 1.]\n",
            " [0. 0. 1. 0.]], shape=(3, 4), dtype=float32)\n",
            "qsa_maximums_ind is:  tf.Tensor(\n",
            "[[0 3]\n",
            " [1 1]\n",
            " [1 3]\n",
            " [2 2]], shape=(4, 2), dtype=int64)\n",
            "nb_maximums is:  tf.Tensor(\n",
            "[[1.]\n",
            " [2.]\n",
            " [1.]], shape=(3, 1), dtype=float32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uPbzav6z6z8-",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "6a0481d8-0764-46c0-d91e-fca61e4a50ea"
      },
      "source": [
        "# Without tie management the best_action is:\n",
        "\n",
        "best_action = tf.math.argmax(qsa, axis=1, output_type=tf.dtypes.int32)\n",
        "print('best_action is: ', best_action)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "best_action is:  tf.Tensor([3 1 2], shape=(3,), dtype=int32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t3Lxcvkv6Tqz",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 238
        },
        "outputId": "15699c02-d96d-40f7-bb01-36aee69e2352"
      },
      "source": [
        "# With tie management the best action is:\n",
        "\n",
        "only_one_max = tf.ones_like(nb_maximums)\n",
        "isMaxMany = nb_maximums > only_one_max\n",
        "print('isMaxMany is: ', isMaxMany)\n",
        "\n",
        "if tf.reduce_any(isMaxMany):\n",
        "\n",
        "  nbr_maximum_int = tf.reshape(nb_maximums,[-1]) \n",
        "  nbr_maximum_int = tf.dtypes.cast(nbr_maximum_int, tf.int32)\n",
        "\n",
        "  for idx in tf.range(best_action.shape[0]):\n",
        "    print('idx is', idx)\n",
        "    if isMaxMany[idx]: \n",
        "            selected_idx = tf.random.uniform((), minval=0, maxval=nbr_maximum_int[idx], dtype=tf.int32)\n",
        "            rows_index = tf.slice(qsa_maximums_ind,[0,0],[-1,1])\n",
        "            all_actions = tf.slice(qsa_maximums_ind,[0,1],[-1,-1])\n",
        "            current_index = tf.ones_like(rows_index)\n",
        "            current_index = current_index * tf.cast(idx, dtype=tf.int64)\n",
        "            selected_rows = tf.where(tf.equal(rows_index,current_index))\n",
        "            select_action = tf.slice(selected_rows,[0,0],[-1,1])\n",
        "            select_action = tf.squeeze(select_action)\n",
        "            new_action = all_actions[select_action[selected_idx]]\n",
        "            new_action = tf.cast(new_action, dtype=tf.int32)\n",
        "            tf.print('***************************************************************************************** \\n')\n",
        "            tf.print('egreedy tie management new_action is: ', new_action)\n",
        "            tf.print('***************************************************************************************** \\n')\n",
        "\n",
        "            indice = tf.reshape(idx,(1,1))\n",
        "            tf.tensor_scatter_nd_update(best_action, indice, new_action)\n",
        "\n",
        "  print('best_action is: ', best_action)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "isMaxMany is:  tf.Tensor(\n",
            "[[False]\n",
            " [ True]\n",
            " [False]], shape=(3, 1), dtype=bool)\n",
            "idx is tf.Tensor(0, shape=(), dtype=int32)\n",
            "idx is tf.Tensor(1, shape=(), dtype=int32)\n",
            "***************************************************************************************** \n",
            "\n",
            "egreedy tie management new_action is:  [3]\n",
            "***************************************************************************************** \n",
            "\n",
            "idx is tf.Tensor(2, shape=(), dtype=int32)\n",
            "best_action is:  tf.Tensor([3 1 2], shape=(3,), dtype=int32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6ZggA2eJ51y8",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 425
        },
        "outputId": "6923125d-56e1-4d7e-a068-11ad00b53c1d"
      },
      "source": [
        "# Calculate the TD update of the Bellman equation:\n",
        "\n",
        "num_actions_float = tf.dtypes.cast(NUM_ACTIONS, tf.float32)\n",
        "pi_s = tf.dtypes.cast(all_ones, tf.float32)\n",
        "print('pi_s cast  is: ', pi_s)\n",
        "pi_s = pi_s * epsilon / num_actions_float\n",
        "print('pi_s  is: ', pi_s)\n",
        "\n",
        "pi_max = (1 - epsilon)/nb_maximums\n",
        "print('pi_max  is: ', pi_max)\n",
        "pi = qsa_maximums * pi_max + pi_s\n",
        "print('pi  is: ', pi)\n",
        "pi_qsa = tf.multiply(pi, qsa)\n",
        "print('pi_qsa  is: ', pi_qsa)\n",
        "sum_piq = tf.math.reduce_sum(pi_qsa, axis=1, keepdims=True)\n",
        "print('sum_piq  is: ', sum_piq)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "pi_s cast  is:  tf.Tensor(\n",
            "[[1. 1. 1. 1.]\n",
            " [1. 1. 1. 1.]\n",
            " [1. 1. 1. 1.]], shape=(3, 4), dtype=float32)\n",
            "pi_s  is:  tf.Tensor(\n",
            "[[0.125 0.125 0.125 0.125]\n",
            " [0.125 0.125 0.125 0.125]\n",
            " [0.125 0.125 0.125 0.125]], shape=(3, 4), dtype=float32)\n",
            "pi_max  is:  tf.Tensor(\n",
            "[[0.5 ]\n",
            " [0.25]\n",
            " [0.5 ]], shape=(3, 1), dtype=float32)\n",
            "pi  is:  tf.Tensor(\n",
            "[[0.125 0.125 0.125 0.625]\n",
            " [0.125 0.375 0.125 0.375]\n",
            " [0.125 0.125 0.625 0.125]], shape=(3, 4), dtype=float32)\n",
            "pi_qsa  is:  tf.Tensor(\n",
            "[[-0.0625      0.0875      0.075       0.5       ]\n",
            " [-0.075       0.33749998  0.0875      0.33749998]\n",
            " [-0.0375     -0.1125     -0.125      -0.05      ]], shape=(3, 4), dtype=float32)\n",
            "sum_piq  is:  tf.Tensor(\n",
            "[[ 0.6       ]\n",
            " [ 0.6875    ]\n",
            " [-0.32500002]], shape=(3, 1), dtype=float32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fK8f3s0nxD-B",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 136
        },
        "outputId": "0f0936a9-ddeb-44ac-b4cc-3ec1719b509d"
      },
      "source": [
        "# To understand tf.tensor_scatter_nd_update\n",
        "indices = tf.constant([[4], [3], [1], [7]])\n",
        "print('indices is: ', indices)\n",
        "updates = tf.constant([9, 10, 11, 12])\n",
        "print('updates is: ', updates)\n",
        "tensor = tf.ones([8], dtype=tf.int32)\n",
        "print(tf.tensor_scatter_nd_update(tensor, indices, updates))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "indices is:  tf.Tensor(\n",
            "[[4]\n",
            " [3]\n",
            " [1]\n",
            " [7]], shape=(4, 1), dtype=int32)\n",
            "updates is:  tf.Tensor([ 9 10 11 12], shape=(4,), dtype=int32)\n",
            "tf.Tensor([ 1 11  1 10  9  1  1 12], shape=(8,), dtype=int32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "C-eme2UMWzN4",
        "colab_type": "text"
      },
      "source": [
        "# softmax policy "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qFI0RCL9O-X-",
        "colab_type": "text"
      },
      "source": [
        "The Boltzmann \"soft max\" probability distribution is defined as follows for a state x:\n",
        "\n",
        "![alt text](http://www.modelfit.us/uploads/7/6/0/6/76068583/softmax_orig.gif)\n",
        "\n",
        "The only change we will do is subtract from Q(s,a) a constant to prevent overflow. So we will implement:\n",
        "\n",
        "![alt text](http://www.modelfit.us/uploads/7/6/0/6/76068583/softmax2-copy_orig.png)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LQAtIF5RLjHZ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 170
        },
        "outputId": "a03fe032-6889-4e8a-df2f-114b01231b09"
      },
      "source": [
        "# Calculate the preference\n",
        "preferences = qsa_tf / TAU\n",
        "# Calculate the max preference\n",
        "max_preference =  tf.math.reduce_max(qsa, axis=1, keepdims=True) / TAU\n",
        "# Calcualte the difference\n",
        "pref_minus_max = preferences - max_preference\n",
        "# Then apply the boltzmann operator\n",
        "exp_preferences = tf.math.exp(pref_minus_max)\n",
        "sum_exp_preferences = tf.reduce_sum(exp_preferences, axis=1, keepdims=True)\n",
        "action_probs = exp_preferences / sum_exp_preferences\n",
        "print(\"Action probabilities are: \", action_probs)\n",
        "\n",
        "# The selection of the best action will be achieve by:\n",
        "best_action = np.random.choice(NUM_ACTIONS, p=action_probs[0])\n",
        "print(\"Best action is: \", best_action)\n",
        "\n",
        "# The TD update will be the following. I am using qsa for simplicity but keep in mind you should use the action-value of your next state:\n",
        "expectation = tf.multiply(action_probs, qsa)\n",
        "sum_expectation = tf.reduce_sum(expectation, axis=1, keepdims=True)\n",
        "v_next_vect = batch_terminal * sum_expectation\n",
        "target_vec = batch_reward + GAMMA * v_next_vect\n",
        "print(\"The TD update is: \", target_vec )\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Action probabilities are:  tf.Tensor(\n",
            "[[0.0e+00 0.0e+00 0.0e+00 1.0e+00]\n",
            " [0.0e+00 5.0e-01 0.0e+00 5.0e-01]\n",
            " [3.8e-44 0.0e+00 1.0e+00 0.0e+00]], shape=(3, 4), dtype=float32)\n",
            "Best action is:  3\n",
            "The TD update is:  tf.Tensor(\n",
            "[[1.   ]\n",
            " [2.   ]\n",
            " [2.802]], shape=(3, 1), dtype=float32)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pkJyFR3OT616",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}