Created
November 2, 2023 10:38
-
-
Save GiovanniGatti/933c61340bfbc361f3effd0c25d1cf1d to your computer and use it in GitHub Desktop.
[RL Unleashed] Mountain Car Problem.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "Python 3", | |
| "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.5.2" | |
| }, | |
| "colab": { | |
| "name": "[RL Unleashed] Mountain Car Problem.ipynb", | |
| "provenance": [], | |
| "include_colab_link": true | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/GiovanniGatti/933c61340bfbc361f3effd0c25d1cf1d/notebook.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "nFRSI9zde-FK" | |
| }, | |
| "source": [ | |
| "# Mountain Car Problem\n", | |
| "\n", | |
| "Let's implement our first reinforcement learning algorithm to address the Mountain Car task.\n", | |
| "\n", | |
| "The Mountain Car task is a hard one. The agent must pilot an underpowered car up a steep mountain road. The diculty is that gravity is stronger than the car's engine, and even at full throttle the car cannot accelerate up the steep slope. The only solution is to first move away from the goal and up the opposite slope on the left. Then, by applying full throttle the car can build p enough inertia to carry it up the steep slope even though it is slowing down the whole way. This is a simple example of a continuous control task where things must get worse in a sense (farther from the goal) before they can get better. Many control methodologies have great diculties with tasks of this kind unless explicitly aided by a human designer.\n", | |
| "\n", | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "9x1U0NiThOc2" | |
| }, | |
| "source": [ | |
| "To get started, let's first install and import dependencies." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "PgwAlEjKby7P" | |
| }, | |
| "source": [ | |
| "#!sudo apt-get install python3.7 > /dev/null 2>&1\n", | |
| "!apt-get update > /dev/null 2>&1\n", | |
| "!apt-get install -y xvfb > /dev/null 2>&1\n", | |
| "!apt-get install -y python-opengl ffmpeg > /dev/null 2>&1\n", | |
| "!pip install gym==0.22.0 pyvirtualdisplay > /dev/null 2>&1" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "p3nVifUFb5qr" | |
| }, | |
| "source": [ | |
| "import gym\n", | |
| "from gym import logger as gymlogger\n", | |
| "from gym.wrappers import Monitor\n", | |
| "gymlogger.set_level(40) #error only\n", | |
| "\n", | |
| "import math\n", | |
| "import random\n", | |
| "import numpy as np\n", | |
| "\n", | |
| "from typing import Tuple, List, Optional\n", | |
| "\n", | |
| "import glob\n", | |
| "import io\n", | |
| "import base64\n", | |
| "from IPython.display import HTML\n", | |
| "from IPython import display as ipythondisplay" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "sAsZqjr4hvwn" | |
| }, | |
| "source": [ | |
| "Below we have two helper functions that enable Google Colab display videos from our agent's interaction with its environment." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "RqFDD1nTb_hN" | |
| }, | |
| "source": [ | |
| "from pyvirtualdisplay import Display\n", | |
| "display = Display(visible=0, size=(1400, 900))\n", | |
| "display.start()\n", | |
| "\n", | |
| "def show_video():\n", | |
| " mp4list = glob.glob('video/*.mp4')\n", | |
| " if len(mp4list) > 0:\n", | |
| " mp4 = mp4list[0]\n", | |
| " video = io.open(mp4, 'r+b').read()\n", | |
| " encoded = base64.b64encode(video)\n", | |
| " ipythondisplay.display(HTML(data='''<video alt=\"test\" autoplay\n", | |
| " loop controls style=\"height: 400px;\">\n", | |
| " <source src=\"data:video/mp4;base64,{0}\" type=\"video/mp4\" />\n", | |
| " </video>'''.format(encoded.decode('ascii'))))\n", | |
| " else:\n", | |
| " print(\"Could not find video\")\n", | |
| "\n", | |
| "def wrap_env(env):\n", | |
| " env = Monitor(env, './video', force=True)\n", | |
| " return env" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "wptn2PChU-JZ" | |
| }, | |
| "source": [ | |
| "# Getting Familiar with the Environment" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "7eVt8S74iI7U" | |
| }, | |
| "source": [ | |
| "As we've seen in last workshop, [Gym](https://gym.openai.com/) is a opensource plataform that provides various reinforcement learning environments. Today, we write our algorithm and test it in the environment 'MountainCar-v0'.\n", | |
| "\n", | |
| "First, let's get familiar with our environment." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "CVH1MsKpjL71" | |
| }, | |
| "source": [ | |
| "env = gym.make('MountainCar-v0')" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "GLemgYVtjbBm" | |
| }, | |
| "source": [ | |
| "Let's first take a look in our state space." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "y-RAnWiljWpw" | |
| }, | |
| "source": [ | |
| "env.observation_space" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "1iOf9qOjjoQY" | |
| }, | |
| "source": [ | |
| "From Gym documentation, the 'Box' space represents an n-dimensional box, so valid observations will be an array of 2 real numbers. Typically," | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "c9ByhYSaj_Py" | |
| }, | |
| "source": [ | |
| "env.reset()" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "lpgYXNJvkGe2" | |
| }, | |
| "source": [ | |
| "where the first index represents the x-position of the car and the second represents car velocity.\n", | |
| "\n", | |
| "Now let's take a look at the action space." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "FLNXnDmTkaEs" | |
| }, | |
| "source": [ | |
| "env.action_space" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "DDVISlQKkgEz" | |
| }, | |
| "source": [ | |
| "Again, following Gym's documentation, the Discrete space allows a fixed range of non-negative numbers, so in this case valid actions are either 0 or 1 or 2.\n", | |
| "Use the cell below to figure out what each one corresponds.\n", | |
| "\n", | |
| "**Exercise:** Modify the action to be taken by the agent (0, 1, 2) and then watch agents’ behavior. The goal is to figure out what each one corresponds to." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "4oTUA-0ncLvP" | |
| }, | |
| "source": [ | |
| "### START CODE HERE ### (≈ 1 lines of code)\n", | |
| "ACTION = None\n", | |
| "### END CODE HERE ###\n", | |
| "\n", | |
| "env = wrap_env(gym.make('MountainCar-v0'))\n", | |
| "env.seed(0)\n", | |
| "env.reset()\n", | |
| "env.render()\n", | |
| "for i in range(200):\n", | |
| " obs, reward, done, info = env.step(ACTION)\n", | |
| " env.render()\n", | |
| "\n", | |
| " if done:\n", | |
| " break\n", | |
| "\n", | |
| "env.close()\n", | |
| "show_video()" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "C1torVb4lgPH" | |
| }, | |
| "source": [ | |
| "At this point, you probably have already figured out that actions 0, 1 and 2 corresponds respectively to full throttle reverse, zero throttle and full throttle forward." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "rbfC2euck8XP" | |
| }, | |
| "source": [ | |
| "Now, we let's see how agent is rewarded." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "feYCN5s0kv1z" | |
| }, | |
| "source": [ | |
| "env.reset()\n", | |
| "obs, reward, done, info = env.step(env.action_space.sample())\n", | |
| "print(reward)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Ps-dLn4ylJCP" | |
| }, | |
| "source": [ | |
| "In fact, in this problem reward will be -1. until agent reaches the flag in the top of the mountain, which in this case it gets a reward of 0.\n", | |
| "\n", | |
| "Consider a few last precisions on the problem.\n", | |
| "\n", | |
| " Observation:\n", | |
| " Num Observation Min Max\n", | |
| " 0 Car Position -1.2 0.6\n", | |
| " 1 Car Velocity -0.07 0.07\n", | |
| "\n", | |
| " Starting State:\n", | |
| " The position of the car is assigned a uniform random value in [-0.6 , -0.4]\n", | |
| " The velocity of the car is always assigned to 0\n", | |
| " \n", | |
| " Episode Termination:\n", | |
| " The car position is more than 0.5 (flag position)\n", | |
| " Episode length is greater than 200" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "eIguxrqwmDMY" | |
| }, | |
| "source": [ | |
| "# Code Tiling\n", | |
| "\n", | |
| "In this exercise we will be using code titling as discussed during the \"On-policy prediction with approximation\" talk.\n", | |
| "\n", | |
| "Again, the general idea behind tile coding is to create a binary feature vector $x(s,a)$ in which there is some overlapping between features. After each update, the approximate value function will be affected at all states within the union of the features, with a greater effect the more features a point has \"in common\" with the state.\n", | |
| "\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "0Af4s8D7n2xP" | |
| }, | |
| "source": [ | |
| "We've also seen that generalization works the best with tile coding when tile are asymmetrically offset.\n", | |
| "\n", | |
| "The code tiling can be offered in standard libraries, so in practice we don't need to implement them ourselves. Below, we will use the implementation suggested by Sutton and Barto at [Tile Coding Software version 3.0beta\n", | |
| "by Richard Sutton](http://incompleteideas.net/tiles/tiles3.py-remove)." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "rYawmRw0q5c9" | |
| }, | |
| "source": [ | |
| "class IHT:\n", | |
| " \"Structure to handle collisions\"\n", | |
| " def __init__(self, size_val):\n", | |
| " self.size = size_val\n", | |
| " self.overfull_count = 0\n", | |
| " self.dictionary = {}\n", | |
| "\n", | |
| " def count(self):\n", | |
| " return len(self.dictionary)\n", | |
| "\n", | |
| " def full(self):\n", | |
| " return len(self.dictionary) >= self.size\n", | |
| "\n", | |
| " def get_index(self, obj, read_only=False):\n", | |
| " d = self.dictionary\n", | |
| " if obj in d:\n", | |
| " return d[obj]\n", | |
| " elif read_only:\n", | |
| " return None\n", | |
| " size = self.size\n", | |
| " count = self.count()\n", | |
| " if count >= size:\n", | |
| " if self.overfull_count == 0: print('IHT full, starting to allow collisions')\n", | |
| " self.overfull_count += 1\n", | |
| " return hash(obj) % self.size\n", | |
| " else:\n", | |
| " d[obj] = count\n", | |
| " return count\n", | |
| "\n", | |
| "def hash_coords(coordinates, m, read_only=False):\n", | |
| " if isinstance(m, IHT): return m.get_index(tuple(coordinates), read_only)\n", | |
| " if isinstance(m, int): return hash(tuple(coordinates)) % m\n", | |
| " if m is None: return coordinates\n", | |
| "\n", | |
| "def tiles(iht_or_size, num_tilings, floats, ints=None, read_only=False):\n", | |
| " \"\"\"returns num-tilings tile indices corresponding to the floats and ints\"\"\"\n", | |
| " if ints is None:\n", | |
| " ints = []\n", | |
| " qfloats = [math.floor(f * num_tilings) for f in floats]\n", | |
| " tiles = []\n", | |
| " for tiling in range(num_tilings):\n", | |
| " tilingX2 = tiling * 2\n", | |
| " coords = [tiling]\n", | |
| " b = tiling\n", | |
| " for q in qfloats:\n", | |
| " coords.append((q + b) // num_tilings)\n", | |
| " b += tilingX2\n", | |
| " coords.extend(ints)\n", | |
| " tiles.append(hash_coords(coords, iht_or_size, read_only))\n", | |
| " return tiles" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "jcTJykMNq-0f" | |
| }, | |
| "source": [ | |
| "Here is a simple example of the use of the tile coding software from Python.\n", | |
| "\n", | |
| "Whatever you are tiling, you will need an index hash table, or IHT. You make one by calling IHT(size), e.g.," | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "baF-lhu4rZCa" | |
| }, | |
| "source": [ | |
| "iht = IHT(1024)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "ZYvr8GRMrirC" | |
| }, | |
| "source": [ | |
| "Suppose you wish to tile a two-dimensional x,y space, where each dimension runs from 0 to 10. The tiling software will partition this using multiple 10 by 10 partitions, each offset from the other (it is 10 by 10 because the software partitions at integer boundaries). You obtain a list of tile indices for a point (here the point (x, y) = (3.6, 7.21)) by calling" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "Gv7KcOPZrhzU" | |
| }, | |
| "source": [ | |
| "indices = tiles(iht, 8, [3.6, 7.21])\n", | |
| "print(indices)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "CBA_RUiGrhhH" | |
| }, | |
| "source": [ | |
| "The second argument (8) is the number of offset tilings. The point will fall in one tile in each of the 8 tilings, so the returned list will have exactly eight positive integers in it, all between 0 and one less than the size of iht. In general, the indices may be something like $[374, 971, 246, 435, 23, 739, 336, 827]$, though in this special case, if this is the first time you've used iht, the indices will be $[0, 1, 2, 3, 4, 5, 6, 7]$. You are guaranteed that all of these exact indices will be returned if ever in the future you tile this same point. If you tile a new point within a distance of about 1 in both x and y directions, then the returned indices will have some in common with this point. Thus:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "h8oEV6c9sRc9" | |
| }, | |
| "source": [ | |
| "tiles(iht, 8, [3.7, 7.21]) # a nearby point" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "61NwRxLTsVbU" | |
| }, | |
| "source": [ | |
| "Results differ from one tile!" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "rjw7J6sRsbB6" | |
| }, | |
| "source": [ | |
| "tiles(iht, 8, [4, 7]) # while a farther away point" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "qmitmYXQsekI" | |
| }, | |
| "source": [ | |
| "It differs differs by 4 (or 5) tiles." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "pQ6k-2nKsktE" | |
| }, | |
| "source": [ | |
| "tiles(iht, 8, [-37.2, 7]) # and a point more than one away in any dim" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "IQD8s6wHsmFu" | |
| }, | |
| "source": [ | |
| "Will have all different tiles. For more details, see full documentation at [Tile Coding Software -- Reference Manual, Version 3.0](http://incompleteideas.net/tiles/tiles3.html)." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "k3rxXoPMsvdL" | |
| }, | |
| "source": [ | |
| "In the tabular world, the state-action value function $Q(s,a)$ was represented by a matrix containing all state-action pairs, also known as Q-Table. That's unfortunately not possible in a continuous world like the Mountain Car, because this Q-Table would be to be arbitrarily large.\n", | |
| "\n", | |
| "We seek then to represent the state-action value function by a set of weights such\n", | |
| "\n", | |
| "$$\\hat{q}(s, a; \\mathbf{w}) \\doteq \\mathbf{w}^T \\mathbf{x}(s,a) = \\sum_{i=1}^{d}{w_i \\cdot x_i(s,a)}$$\n", | |
| "\n", | |
| "where $\\mathbf{x}(s,a)$ is generated by tile coding.\n", | |
| "\n", | |
| "Remember that $\\mathbf{x}$ is a **binary vector**, that is, $x_i \\in \\{0, 1\\}, \\forall x_i \\in \\mathbf{x}(s, a)$, thus computing $\\hat{q}(s, a; \\mathbf{x})$ become as simple as summing the weights of all 'active features'." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "7J2eXaw1oH8v" | |
| }, | |
| "source": [ | |
| "**Exercise:** Implement the $\\mathbf{x}(s,a)$ function.\n", | |
| "\n", | |
| "**Hint 1:** Let's say x and y run each from 1 to 3, and that you would like to use 10 x 10 grid tilings. Because the tile coding software always partitions at the *integer boundaries*, you will need to scale your points to a 10 x 10 region.\n", | |
| "\n", | |
| "**Hint 2:** In the previous example 10 x 10 grid example, we want to scale points so for $ x_{scaled} = x \\cdot \\frac{10}{3 - 1}$\n", | |
| "\n", | |
| "**Hint 3:** The scale factor is already computed for you during class initialization and stored to the class private variables `_position_scale` and `_velocity_scale`." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "-zAVXDfioqtw" | |
| }, | |
| "source": [ | |
| "class X:\n", | |
| "\n", | |
| " def __init__(self,\n", | |
| " num_of_tilings: int = 8,\n", | |
| " num_of_tiles: int = 8,\n", | |
| " position_bounds: Tuple[float, float] = (-1.2, 0.6),\n", | |
| " velocity_bounds: Tuple[float, float] = (-0.07, 0.07),\n", | |
| " max_size: int = 2048):\n", | |
| "\n", | |
| " self._iht = IHT(max_size)\n", | |
| " self._num_of_tilings = num_of_tilings\n", | |
| " self._num_of_tiles = num_of_tiles\n", | |
| "\n", | |
| " self._position_scale = \\\n", | |
| " num_of_tiles / (position_bounds[1] - position_bounds[0])\n", | |
| " self._velocity_scale = \\\n", | |
| " num_of_tiles / (velocity_bounds[1] - velocity_bounds[0])\n", | |
| " self._position_max = position_bounds[0]\n", | |
| "\n", | |
| " @property\n", | |
| " def num_of_tilings(self) -> int:\n", | |
| " return self._num_of_tilings\n", | |
| "\n", | |
| " @property\n", | |
| " def num_of_tiles(self) -> int:\n", | |
| " return self._num_of_tiles\n", | |
| "\n", | |
| " def __call__(self, state: np.ndarray, action: int) -> List[int]:\n", | |
| " \"\"\"\n", | |
| " Apply the the x(s, a) transformation.\n", | |
| "\n", | |
| " Args:\n", | |
| " state (ndarray): The position-velocity pair\n", | |
| " action (int): 0 throttle reverse,\n", | |
| " 1 zero throttle and\n", | |
| " 2 throttle forward.\n", | |
| " Returns:\n", | |
| " List of activated features.\n", | |
| " \"\"\"\n", | |
| "\n", | |
| " position, velocity = state\n", | |
| "\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " scaled_position = None\n", | |
| " scaled_velocity = None\n", | |
| " ### END CODE HERE ###\n", | |
| "\n", | |
| " active_tiles = tiles(self._iht,\n", | |
| " self._num_of_tilings,\n", | |
| " (scaled_position, scaled_velocity),\n", | |
| " (action,))\n", | |
| "\n", | |
| " return active_tiles" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "-IPY1zf62EzD" | |
| }, | |
| "source": [ | |
| "x = X(num_of_tilings=3, num_of_tiles=4,\n", | |
| " position_bounds=(0, 10), velocity_bounds=(0, 10))\n", | |
| "\n", | |
| "for i, state in enumerate((np.array([0, 0]),\n", | |
| " np.array([1, 0]),\n", | |
| " np.array([2, 2]),\n", | |
| " np.array([1, 1]))):\n", | |
| " print(str(i) + ': ' + str(x(state, i % 2)))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "IGpMCgVc6qAF" | |
| }, | |
| "source": [ | |
| "**Expected Output**:\n", | |
| "\n", | |
| "<table>\n", | |
| " <tr>\n", | |
| " <td>0:</td>\n", | |
| " <td>[0, 1, 2]</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <td>1:</td>\n", | |
| " <td>[3, 4, 5]</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <td>2:</td>\n", | |
| " <td>[0, 6, 7]</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <td>3:</td>\n", | |
| " <td>[3, 4, 5]</td>\n", | |
| " </tr>\n", | |
| "</table>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "QizjJo7m8zE-" | |
| }, | |
| "source": [ | |
| "Next step is to implement our state-action value function $\\hat{q}(s, a; \\mathbf{w})$. Remember that $\\mathbf{x}(s, a)$ is a binary feature vector and that our implementation of it returns a vector containing the indexes of the activated features." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "0vI7Ejdc9ld9" | |
| }, | |
| "source": [ | |
| "**Exercise**: Implement $\\hat{q}(s, a; \\mathbf{w})$." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "2D0vFnmEyLrp" | |
| }, | |
| "source": [ | |
| "from IPython.utils.contexts import NoOpContext\n", | |
| "class Q:\n", | |
| "\n", | |
| " def __init__(self, x: X, position_max: float = 0.6):\n", | |
| " self._x = x\n", | |
| " self._position_max = position_max\n", | |
| "\n", | |
| " def __call__(\n", | |
| " self, state: np.ndarray, action: int, weights: np.ndarray\n", | |
| ") -> float:\n", | |
| " \"\"\"\n", | |
| " Computes q(s, a; w) transformation.\n", | |
| "\n", | |
| " Args:\n", | |
| " state (ndarray): The position-velocity pair\n", | |
| " action (int): 0 throttle reverse,\n", | |
| " 1 zero throttle and\n", | |
| " 2 throttle forward.\n", | |
| " weights (ndarray): the weights\n", | |
| " Returns:\n", | |
| " The estimated value of q.\n", | |
| " \"\"\"\n", | |
| "\n", | |
| " position, _ = state\n", | |
| "\n", | |
| " if position >= self._position_max:\n", | |
| " return 0.\n", | |
| "\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " active_tiles = None\n", | |
| " _sum = None\n", | |
| " ### END CODE HERE ###\n", | |
| "\n", | |
| " return _sum" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "WKN9ywSg-wnU" | |
| }, | |
| "source": [ | |
| "x = X(num_of_tilings=2, num_of_tiles=8)\n", | |
| "q = Q(x)\n", | |
| "weights = np.array([.1, .2, .3, .4, .5, .6])\n", | |
| "\n", | |
| "for i, state in enumerate((np.array([.3, .03]),\n", | |
| " np.array([.28, .032]),\n", | |
| " np.array([-.5, -.05]))):\n", | |
| " print(str(i) + ': ' + str(q(state, 0, weights)))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "C-QQjtLBsR4V" | |
| }, | |
| "source": [ | |
| "**Expected Output**:\n", | |
| "\n", | |
| "<table>\n", | |
| " <tr>\n", | |
| " <td>0:</td>\n", | |
| " <td>0.30000000000000004</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <td>1:</td>\n", | |
| " <td>0.30000000000000004</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <td>2:</td>\n", | |
| " <td>0.7</td>\n", | |
| " </tr>\n", | |
| "</table>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "YQhXVW1WyawN" | |
| }, | |
| "source": [ | |
| "## Implementing the Policy" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "8H2NkGacyd1r" | |
| }, | |
| "source": [ | |
| "The last missing brick to build our reinforcement learning agent is the implementation of an epsilon greedy policy. Given an action-state value function, we want to select the best action for any given state by picking the action that gives the best expected return, e. g.\n", | |
| "\n", | |
| "$$\n", | |
| "\\pi(s) = max_a \\hat{q}(s,a; \\mathbf{w})\n", | |
| "$$\n", | |
| "\n", | |
| "However, given some $\\epsilon$ probability, we want to select an action at random, representing the agent's exploration, thus\n", | |
| "\n", | |
| "$$\n", | |
| "\\pi(s, a) \\leftarrow\n", | |
| "\\begin{equation}\n", | |
| " \\begin{cases}\n", | |
| " 1 - \\epsilon + \\epsilon / |\\mathcal{A}(s),& \\text{if } a = A^* \\\\\n", | |
| " \\epsilon / |\\mathcal{A}(s)|,& \\text{if } a \\neq A^*\n", | |
| " \\end{cases}\\,.\n", | |
| "\\end{equation}\n", | |
| "$$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "fRQH3HseyeIH" | |
| }, | |
| "source": [ | |
| "**Exercise**: Complete the epsilon greedy policy below code.\n", | |
| "\n", | |
| "**Hint**: Exploration is already implemented to you\n", | |
| "\n", | |
| "**Hint 2**: One can implement the argmax function in pure python with" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "c9BSdCcX9d-K" | |
| }, | |
| "source": [ | |
| "l = [3, 5, 7, 1]\n", | |
| "f = lambda i: l[i]\n", | |
| "argmax = max(range(len(l)), key=f)\n", | |
| "print('argmax l: ' + str(argmax))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "LBhvxQvK1-h_" | |
| }, | |
| "source": [ | |
| "class EGreedyPolicy:\n", | |
| "\n", | |
| " def __init__(self,\n", | |
| " q: Q,\n", | |
| " action_space: gym.Space,\n", | |
| " exploration_rate: float = .0,\n", | |
| " seed: Optional[int] = 0):\n", | |
| " self._q = q\n", | |
| " self._action_space = action_space\n", | |
| " self._exploration_rate = exploration_rate\n", | |
| " self._rand = random.Random(x=seed)\n", | |
| "\n", | |
| " def __call__(self, state: np.ndarray, weights: np.ndarray) -> int:\n", | |
| " \"\"\"\n", | |
| " Selects the action to given state according to epsilon greedy exploration\n", | |
| " strategy.\n", | |
| "\n", | |
| " Args:\n", | |
| " state (np.ndarray): an input state\n", | |
| " weights (np.ndarray): the weigths\n", | |
| "\n", | |
| " Returns:\n", | |
| " the selected action\n", | |
| " \"\"\"\n", | |
| "\n", | |
| " if self._rand.random() < self._exploration_rate:\n", | |
| " return self._rand.randint(0, self._action_space.n - 1)\n", | |
| "\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " f = None\n", | |
| " best_action = None\n", | |
| " ### END CODE HERE ###\n", | |
| "\n", | |
| " return best_action" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "Ti-IwCbM7T3g" | |
| }, | |
| "source": [ | |
| "def q_1(s, a, weights):\n", | |
| " return 1 if a == 0 else 2 if a == 1 else -1\n", | |
| "\n", | |
| "def q_2(s, a, weights):\n", | |
| " return 0 if a == 0 else -1 if a == 1 else 2\n", | |
| "\n", | |
| "weights = np.zeros((1,))\n", | |
| "\n", | |
| "policy = EGreedyPolicy(q_1, gym.spaces.Discrete(3), exploration_rate=0.)\n", | |
| "print('i: ' + str(policy(np.zeros((1,)), weights)))\n", | |
| "\n", | |
| "policy = EGreedyPolicy(q_2, gym.spaces.Discrete(3), exploration_rate=0.)\n", | |
| "print('i: ' + str(policy(np.zeros((1,)), weights)))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "q2Wc9d7x-DmP" | |
| }, | |
| "source": [ | |
| "**Expected Output**:\n", | |
| "\n", | |
| "<table>\n", | |
| " <tr>\n", | |
| " <td>i:</td>\n", | |
| " <td>1</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <td>i:</td>\n", | |
| " <td>2</td>\n", | |
| " </tr>\n", | |
| "</table>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "lqzYpNtnsweD" | |
| }, | |
| "source": [ | |
| "## Implementing Semi-gradient Sarsa for Estimating $\\hat{q} \\approx q^*$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "PriHqj2ZuDlY" | |
| }, | |
| "source": [ | |
| "Now we have our basic functions, it's about time to implement our agent. As we have seen during the talk, the *episodic semi-gradient* one-step Sarsa updates are given by\n", | |
| "\n", | |
| "$$\\mathbf{w}_{t+1} \\doteq \\mathbf{w}_t + \\alpha \\big[ R_{t+1} + \\gamma \\hat{q}(S_{t+1}, A_{t+1}; \\mathbf{w}_t) - \\hat{q}(s_t, A_t; \\mathbf{w}_t) \\big] \\nabla \\hat{q}(S_t, A_t; \\mathbf{w}_t)$$\n", | |
| "\n", | |
| "The pseudocode for the algorithm is given below." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "b5PzT2MTtmUB" | |
| }, | |
| "source": [ | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "7DCLV4AJvX_2" | |
| }, | |
| "source": [ | |
| "**Exercise**: Complete the update equations on the below code.\n", | |
| "\n", | |
| "**Hint**: Remember that $\\nabla_w \\hat{q}(s, a; \\mathbf{w}) = \\nabla_w \\mathbf{w}^T \\mathbf{x}(s,a) = \\mathbf{x}(s,a)$\n", | |
| "\n", | |
| "**Hint 2**: $\\mathbf{x}(s,a)$ is a *binary vector*\n", | |
| "\n", | |
| "**Hint 3**: We want to update weights only on active features.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "NW4Zc-M6sdUJ" | |
| }, | |
| "source": [ | |
| "def semi_gradient_sarsa(env: gym.Env,\n", | |
| " learning_rate: float,\n", | |
| " exploration_rate: float,\n", | |
| " q: Q,\n", | |
| " x: X,\n", | |
| " weights: np.ndarray,\n", | |
| " discount_rate: float = .99,\n", | |
| " num_episodes: int = 300) -> np.ndarray:\n", | |
| " \"\"\"\n", | |
| " Perform Learning using episodic semi-gradient Sarsa\n", | |
| "\n", | |
| " Args:\n", | |
| " env (gym.Env): the environment\n", | |
| " learning_rate (float): aka alpha\n", | |
| " exploration_rate (float): aka epsilon\n", | |
| " q (Q): a parameterized differentiable action-value function q(s,a)\n", | |
| " x (X): the feature mapping function x(s)\n", | |
| " discount_rate (float): aka gamma\n", | |
| " num_episodes (int): number of episodes to play\n", | |
| "\n", | |
| " Returns:\n", | |
| " Returns que approximate Q-Function q(s, a; w)\n", | |
| " \"\"\"\n", | |
| "\n", | |
| " policy = EGreedyPolicy(q, env.action_space, exploration_rate)\n", | |
| " for _ in range(num_episodes):\n", | |
| " state = env.reset()\n", | |
| " action = policy(state, weights)\n", | |
| " done = False\n", | |
| "\n", | |
| " while True:\n", | |
| " next_state, reward, done, _ = env.step(action)\n", | |
| " if done:\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " active_tiles = None\n", | |
| " weights[active_tiles] = None\n", | |
| " ### END CODE HERE ###\n", | |
| " break\n", | |
| "\n", | |
| " next_action = policy(next_state, weights)\n", | |
| "\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " active_tiles = None\n", | |
| " weights[active_tiles] = None\n", | |
| " ### END CODE HERE ###\n", | |
| "\n", | |
| " state = next_state\n", | |
| " action = next_action" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "S9dsEIpjdD_4" | |
| }, | |
| "source": [ | |
| "Now let's run it for a while to see if our learning agent can figure out how to leave the hole." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "IYkcvGc2bRw6" | |
| }, | |
| "source": [ | |
| "env = gym.make('MountainCar-v0')\n", | |
| "\n", | |
| "x = X()\n", | |
| "q = Q(x)\n", | |
| "\n", | |
| "learning_rate = .5 / x.num_of_tilings\n", | |
| "exploration_rate = 0.\n", | |
| "weights = np.zeros(2048)\n", | |
| "\n", | |
| "semi_gradient_sarsa(env, learning_rate, exploration_rate, q, x, weights)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "R_XthbwClY_z" | |
| }, | |
| "source": [ | |
| "def play_greedy_episode(q: Q, weights: np.ndarray) -> None:\n", | |
| " env = wrap_env(gym.make('MountainCar-v0'))\n", | |
| " state = env.reset()\n", | |
| " env.render()\n", | |
| "\n", | |
| " policy = EGreedyPolicy(q, env.action_space, exploration_rate=0.)\n", | |
| "\n", | |
| " while True:\n", | |
| " action = policy(state, weights)\n", | |
| " state, _, done, _ = env.step(action)\n", | |
| " env.render()\n", | |
| "\n", | |
| " if done:\n", | |
| " break\n", | |
| "\n", | |
| " env.close()\n", | |
| " show_video()" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "zl9BgWlemhbR" | |
| }, | |
| "source": [ | |
| "play_greedy_episode(q, weights)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "IC0JRLN-m4uI" | |
| }, | |
| "source": [ | |
| "If the car gets to its goal, congratulations! You've done it!" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "2X6qDL8un1b0" | |
| }, | |
| "source": [ | |
| "" | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment