Ex12.ReinforcementLearning.FrozenLakeGame.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b9bdaa1f",
   "metadata": {},
   "source": [
    "<img src=\"https://www.th-koeln.de/img/logo.svg\" style=\"float:right;\" width=\"200\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25c621fd",
   "metadata": {},
   "source": [
    "# 12th exercise: <font color=\"#C70039\">First Reinforcement Learning Game (*Frozen Lake*) using OpenAI Gym</font>\n",
    "* Course: AML\n",
    "* Lecturer: <a href=\"https://www.gernotheisenberg.de/\">Gernot Heisenberg</a>\n",
    "* Author of notebook: <a href=\"https://www.gernotheisenberg.de/\">Gernot Heisenberg</a>. This notebook is based on the great post and notebook from [Rodolfo Mendes](https://morioh.com/p/18a96b9091d3).\n",
    "* Date:   04.09.2024\n",
    "\n",
    "<img src=\"https://miro.medium.com/v2/resize:fit:720/format:webp/1*i53DAlKJx_91HgcSiFwyJQ.png\" style=\"float: center;\" width=\"600\">\n",
    "\n",
    "---------------------------------\n",
    "**GENERAL NOTE 1**: \n",
    "Please make sure you are reading the entire notebook, since it contains a lot of information on your tasks (e.g. regarding the set of certain paramaters or a specific computational trick), and the written mark downs as well as comments contain a lot of information on how things work together as a whole. \n",
    "\n",
    "**GENERAL NOTE 2**: \n",
    "* Please, when commenting source code, just use English language only. \n",
    "* When describing an observation please use English language, too.\n",
    "* This applies to all exercises throughout this course.\n",
    "\n",
    "---------------------------------\n",
    "\n",
    "### <font color=\"ce33ff\">DESCRIPTION</font>:\n",
    "\n",
    "#### OpenAI Gym\n",
    "In this exercise you will be using Python and OpenAI Gym to develop your reinforcement learning algorithm. The Gym library is a collection of environments that can be used freely with the reinforcement learning algorithms.\n",
    "\n",
    "Gym has a ton of environments ranging from simple text based games to Atari games like Breakout and Space Invaders. The library is intuitive to use and simple to install. Just run **pip install gym** and you are good to go! The link to Gym's installation instructions, requirements, and documentation is included in the description. \n",
    "\n",
    "Further reading about OpenAI Gym is available under https://www.gymlibrary.dev/.\n",
    "This notebook is based on this great post and notebook from [Rodolfo Mendes](https://morioh.com/p/18a96b9091d3).\n",
    "\n",
    "#### Frozen Lake\n",
    "This description of the game is copied directly from Gym's website. \n",
    "\n",
    "*Winter is coming. You and your friends were tossing around a frisbee at the park when you made a wild throw that left the frisbee out in the middle of the lake. The water is mostly frozen, but there are a few holes where the ice has melted. If you step into one of those holes, you'll fall into the freezing water and die (Game over). At this time, there's an international frisbee shortage, so it's absolutely imperative that you navigate across the lake and retrieve the disc. However, the ice is slippery, so you won't always move in the direction you intend. The surface is described using a grid like the following:*\n",
    "\n",
    "* SFFF\n",
    "* FHFH\n",
    "* FFFH\n",
    "* HFFG\n",
    "\n",
    "This grid is your environment! S is your (the agent's) starting point and it's safe. F represents the frozen surface and is also safe. H represents a hole and if your agent steps in a hole in the middle of a frozen lake, the game is over because the agent dies. Finally, G represents the goal, which is the space on the grid where the frisbee is located.\n",
    "\n",
    "The agent can navigate *left, right, up, down* and the episode ends when the agent reaches the goal or falls in a hole. It receives a reward of **1** if it reaches the goal and **0** otherwise.\n",
    "\n",
    "Here is the summary:\n",
    "<img src=\"./images/FrozenLake.States.Rewards.png\" style=\"float: center;\" width=\"800\">\n",
    "\n",
    "---------------------------------\n",
    "\n",
    "### <font color=\"FFC300\">TASKS</font>:\n",
    "The tasks that you need to work on within this notebook are always indicated below as bullet points. \n",
    "If a task is more challenging and consists of several steps, this is indicated as well. \n",
    "Make sure you have worked down the task list and commented your doings. \n",
    "This should be done by using markdown.<br> \n",
    "<font color=red>Make sure you don't forget to specify your name and your matriculation number in the notebook.</font>\n",
    "\n",
    "**YOUR TASKS in this exercise are as follows**:\n",
    "1. import the notebook to Google Colab or use your local machine.\n",
    "2. make sure you specified you name and your matriculation number in the header below my name and date. \n",
    "    * set the date too and remove mine.\n",
    "3. read the entire notebook carefully \n",
    "    * add comments whereever you feel it necessary for better understanding\n",
    "    * run the notebook for the first time. \n",
    "4. install gym into your env!\n",
    "5. You will train an agent to play the *Frozen Lake* game using Q-learning and you will get a playback of how the agent does after being trained.\n",
    "6. Again the task: Your agent has to navigate the grid by staying on the frozen surface without falling into any holes until it reaches the frisbee. If it reaches the frisbee, it wins with a reward of plus one. If it falls in a hole, it loses and receives no points for the entire episode.\n",
    "7. Your tasks are highlighted in the notebook (see below)\n",
    "---------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c8e1838",
   "metadata": {},
   "source": [
    "### Imports \n",
    "import all important libs including gym"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a8a696b3",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import gym\n",
    "import random\n",
    "import time\n",
    "from   IPython.display import clear_output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ffb30fd8-4661-4d87-a050-91ce38444d8f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(gym.__version__)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87efa371",
   "metadata": {},
   "source": [
    "### Creating the Environment\n",
    "For creating your environment, just call *gym.make()* and pass a string of the name of the environment you want to set up. \n",
    "All the environments with their corresponding names you can use here are available on Gym's website (see above).\n",
    "With this *env* object, you are able to query for information about the environment, sample states and actions, retrieve rewards and have your agent navigate the frozen lake. That is all made available to you conveniently with Gym."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d88423b6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "env = gym.make(\"FrozenLake-v1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ba3fd99",
   "metadata": {},
   "source": [
    "### Creating the Q-Table\n",
    "Now, construct your Q-table, and initialize all the Q-values to zero for each state-action pair.\n",
    "The number of rows in the table is equivalent to the size of the state space in the environment, and the number of columns is equivalent to the size of the action space (see above). You can get this information using *env.observation_space.n* and *env.action_space.n* as shown below in the code. Then, you can use this information to build the Q-table and initialize it with zeros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "349627df",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "action_space_size = env.action_space.n\n",
    "state_space_size = env.observation_space.n\n",
    "\n",
    "q_table = np.zeros((state_space_size, action_space_size))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ac22125",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(q_table)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d662212",
   "metadata": {},
   "source": [
    "### Initializing Q-Learning hyperparameters\n",
    "Now, we're going to create and initialize all the parameters needed to implement the Q-learning algorithm.\n",
    "\n",
    "First, with *num_episodes*, you define the total number of episodes you want the agent to play during training. Then, with *max_steps_per_episode*, you define a maximum number of steps that your agent is allowed to take within a single episode. So, if by the 100th step, the agent has not reached the frisbee or fallen through a hole, then the episode will terminate with the agent receiving zero points.\n",
    "\n",
    "Next, you will set your *learning_rate* and your *discount_rate* as well, which was represented with the symbol (lambda) in the course slides (keyword: discounted return G_t).\n",
    "\n",
    "Now, the last four parameters are all related to the exploration-exploitation dilemma with respect to the epsilon-greedy policy. You are initializing your *exploration_rate* to **1** and setting the *max_exploration_rate* to **1** and a *min_exploration_rate* to **0.01**. The *max* and *min* are just bounds to how large or small your exploration rate can be. Remember, the exploration rate was represented with the symbol (epsilon) when discussed in the course slides.\n",
    "\n",
    "Lastly, you will set the *exploration_decay_rate* to **0.01** to determine the rate at which the *exploration_rate* will decay."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40f34d94",
   "metadata": {},
   "source": [
    "**YOUR <font color=\"FFC300\">TASK</font> in this exercise is as follows** (point 7 from the task list above):\n",
    "\n",
    "All of the above parameters can change!\n",
    "Your task is to create a *testplan* and tune all parameters by yourself and observe how they influence and change the performance of the algorithm. \n",
    "Make notes! They will help you during the exam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3dde16e1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "num_episodes = 10000\n",
    "max_steps_per_episode = 100\n",
    "\n",
    "learning_rate = 0.1\n",
    "discount_rate = 0.99\n",
    "\n",
    "exploration_rate = 1\n",
    "max_exploration_rate = 1\n",
    "min_exploration_rate = 0.01\n",
    "exploration_decay_rate = 0.01"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac087582",
   "metadata": {},
   "source": [
    "Create a list to hold all of the rewards you will get from each episode. \n",
    "By means of this you can observe how your game score changes over time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7bf6194e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "rewards_all_episodes = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39502e30",
   "metadata": {},
   "source": [
    "In the following code section, the entire Q-learning algorithm is implemented as discussed in detail in the AML course. \n",
    "When this code is executed, this is exactly where the training will take place. \n",
    "* The first for-loop contains everything that happens within a single episode. \n",
    "* The second nested loop contains everything that happens for a single time-step.\n",
    "\n",
    "Read all the red comments, as they contain lots of important information on the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6dad9e9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Q-learning algorithm\n",
    "\n",
    "# loop: for a single episode\n",
    "for episode in range(num_episodes):\n",
    "    # initialize 'new episode' parameters\n",
    "    state, info = env.reset()\n",
    "    ''' The done variable just keeps track of whether or not your episode is finished.\n",
    "    Initialize it to False when first starting the episode and you will see later where \n",
    "    it will get updated to notify you when the episode is over.'''\n",
    "    done = False\n",
    "    \n",
    "    ''' Keep track of the rewards within the current episode as well.\n",
    "    Hence, set rewards_current_episode = 0 since you start \n",
    "    with no rewards at the beginning of each episode.'''\n",
    "    rewards_current_episode = 0\n",
    "\n",
    "    # nested loop: for a single time-step\n",
    "    for step in range(max_steps_per_episode): \n",
    "        # Exploration-exploitation trade-off\n",
    "        '''For each time-step within an episode set your exploration_rate_threshold \n",
    "        to a random number between 0 and 1. This will be used to determine whether \n",
    "        your agent will explore or exploit the environment in this time-step.'''\n",
    "        exploration_rate_threshold = random.uniform(0, 1)\n",
    "        if exploration_rate_threshold > exploration_rate:\n",
    "            action = np.argmax(q_table[state,:]) \n",
    "        else:\n",
    "            action = env.action_space.sample()\n",
    "\n",
    "        # Take new action\n",
    "        '''After action is chosen, take that action by calling step() on your env object and \n",
    "        pass your action to it. The function step() returns a tuple containing the new state, \n",
    "        the reward for the action you took, whether or not the action ended the episode and \n",
    "        diagnostic information regarding the environment (helpful for debugging).'''\n",
    "        new_state, reward, done, truncated, info = env.step(action)\n",
    "\n",
    "        # Update Q-table for Q(s,a)\n",
    "        '''Compare this implementation with the equation in the course slides.'''\n",
    "        q_table[state, action] = q_table[state, action] * (1 - learning_rate) + learning_rate * (reward + discount_rate * np.max(q_table[new_state, :]))\n",
    "        \n",
    "        '''Set your current state to the new_state that was returned when taking the last action \n",
    "        and then update the rewards from your current episode by adding the reward you received \n",
    "        for your previous action.'''\n",
    "        # Set new state\n",
    "        state = new_state\n",
    "        # Add new reward \n",
    "        rewards_current_episode += reward \n",
    "        '''Then, check to see if your last action ended the episode \n",
    "        (game over by agent stepping in a hole or reaching the goal)! \n",
    "        If the action did end the episode, then jump out of this loop and start the next episode.\n",
    "        Otherwise, transition to the next time-step.'''\n",
    "        if done == True: \n",
    "            break\n",
    "            \n",
    "    # Exploration rate decay\n",
    "    '''Once an episode is finished, you need to update your exploration_rate using exponential decay, \n",
    "    which just means that the exploration rate decays at a rate proportional to its current value. \n",
    "    You can decay the exploration_rate using the formula above, which makes use of all the exploration \n",
    "    rate parameters that were defined above in the hyperparameter section.'''\n",
    "    exploration_rate = min_exploration_rate + (max_exploration_rate - min_exploration_rate) * np.exp(-exploration_decay_rate*episode)\n",
    "    \n",
    "    # Add current episode reward to total rewards list and move on to the next episode\n",
    "    rewards_all_episodes.append(rewards_current_episode)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3acbce7",
   "metadata": {},
   "source": [
    "### All episodes training completed\n",
    "After all episodes are finished you now just calculate the average reward per thousand episodes from your list that contains the rewards for all episodes so that you can print it out and see how the rewards changed over time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "03097b41",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate and print the average reward per thousand episodes\n",
    "rewards_per_thousand_episodes = np.split(np.array(rewards_all_episodes),num_episodes/1000)\n",
    "count = 1000\n",
    "\n",
    "print(\"********Average reward per thousand episodes********\\n\")\n",
    "for r in rewards_per_thousand_episodes:\n",
    "    print(count, \": \", str(sum(r/1000)))\n",
    "    count += 1000"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d66e875b",
   "metadata": {},
   "source": [
    "### Interpretation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6771b72f",
   "metadata": {},
   "source": [
    "From this print, you can see that the average reward per thousand episodes did indeed progress over time. When the algorithm first started training, the first thousand episodes only averaged a reward of almost **0.18**, but by the time it got to its last thousand episodes, the reward drastically improved to almost **0.7**.\n",
    "\n",
    "Let's take a second to understand how you can interpret these results. Your agent played **10000** episodes. At each time step within an episode, the agent received a reward of **1** if it reached the frisbee, otherwise, it received a reward of **0**. If the agent did indeed reach the frisbee, then the episode finished at that time-step.\n",
    "\n",
    "Hence, that means for each episode, the total reward received by the agent for the entire episode is either **1** or **0**. So, for the first thousand episodes, you can interpret this score as meaning that **18%** of the time the agent received a reward of **1** and won the episode. And by the last thousand episodes from a total of **10000**, the agent was winning almost **70%** of the time.\n",
    "\n",
    "By analyzing the grid of the game, you can see it is a lot more likely that the agent would fall in a hole or perhaps reach the max time steps than it is to reach the frisbee, so reaching the frisbee **70%** of the time is not too bad, especially since the agent had no explicit instructions to reach the frisbee. It learned that this is the correct thing to do.\n",
    "\n",
    "* SFFF\n",
    "* FHFH\n",
    "* FFFH\n",
    "* HFFG\n",
    "\n",
    "At last, print out your updated Q-table to see how that has transitioned from its initial state of all zeros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68fbc5bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print updated Q-table\n",
    "print(\"\\n\\n********Q-table********\\n\")\n",
    "print(q_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6729c35",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}