Last active
March 9, 2023 21:03
-
-
Save GiovanniGatti/ad20ba1c38d31211419bba7b17bebeb6 to your computer and use it in GitHub Desktop.
[RL Novels][Workshop III] Baird's counter example
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": { | |
| "colab": { | |
| "name": "[RL Novels][Workshop III] Baird's counter example", | |
| "provenance": [], | |
| "collapsed_sections": [], | |
| "toc_visible": true, | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "display_name": "Python 3", | |
| "name": "python3" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/GiovanniGatti/ad20ba1c38d31211419bba7b17bebeb6/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": "RZwSfy04vKEX", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "# Baird's counterexample" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "YWWCKBBNvQPH", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Welcome to the 3rd RL Novels workshop!\n", | |
| "\n", | |
| "In this assignement we will see that even the almighty Q-Learning diverges on Baird's counterexample when used with (linear) function approximation.\n", | |
| "\n", | |
| "Your goal is to implement Q-Learning with linear function approximation and apply it to Baird's counterexample.\n", | |
| "\n", | |
| "Let's start by importing some libraries." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "iz3cmY-o47vQ", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "from typing import Optional, Tuple, List\n", | |
| "\n", | |
| "import numpy as np\n", | |
| "import itertools\n", | |
| "import random\n", | |
| "\n", | |
| "import matplotlib.pyplot as plt" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "iT0RgUJe0mnm", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Implementing the environment" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "clmzXPXgwS7Z", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "**Exercise**: As a first assingment, let's implement Baird's counterexample MDP." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "dsOv7J-1v18D", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "PYbAT1i4wjf6", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "**Hint**: transition probabilities are independent of the state.\n", | |
| "\n", | |
| "**Hint 2**: reward is always 0 for every transition\n", | |
| "\n", | |
| "**Hint 3**: use `np.random.choice(self._STATES[: self._LOWER_STATE])` for randomly select between upper states states" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "hsrp483qvOpO", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "class BairdsCounterExampleMdp:\n", | |
| "\n", | |
| " def __init__(self):\n", | |
| " self._DASHED = 0\n", | |
| " self._SOLID = 1\n", | |
| " self._ACTIONS = [self._DASHED, self._SOLID]\n", | |
| " self._STATES = np.arange(0, 7)\n", | |
| " self._LOWER_STATE = 6\n", | |
| "\n", | |
| " def step(self, action: int) -> Tuple[int, int]:\n", | |
| " \"\"\"\n", | |
| " From the current state, move to the next state.\n", | |
| "\n", | |
| " Args:\n", | |
| " action (int): 0 dashed, \n", | |
| " 1 solid \n", | |
| " Returns:\n", | |
| " Tuple containing the index of the next state and the reward\n", | |
| " \"\"\"\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " pass\n", | |
| " ### END CODE HERE ###\n", | |
| " \n", | |
| " def num_actions(self) -> int:\n", | |
| " return len(self._ACTIONS)\n", | |
| "\n", | |
| " def num_states(self) -> int:\n", | |
| " return len(self._STATES)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "yyA4IUtbyn2h", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "mdp = BairdsCounterExampleMdp()\n", | |
| "\n", | |
| "np.random.seed(0)\n", | |
| "\n", | |
| "mdp.step(1), mdp.step(0), mdp.step(0), mdp.step(1)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "6_b5aRIRy4an", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "**Expected output:**\n", | |
| "\n", | |
| " ((6, 0), (4, 0), (5, 0), (6, 0))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "XNgwuETF0ruU", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Feature vector" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "pKYkfsZGyAh8", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Our next step is to define the feature vector function $\\mathbf{x}(s, a)$. The simplest choice is a linear function, which design can be arbitrary.\n", | |
| "\n", | |
| "For this exercise, we will provide a linear function following the same \"style\" presented in the book. There is no need for implementing it yourself." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "q8kTG1ePyA63", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "class X:\n", | |
| "\n", | |
| " def __init__(self, \n", | |
| " num_states: int = 7, \n", | |
| " num_actions: int = 2, \n", | |
| " num_of_weights: int = (7 * 2 + 1)):\n", | |
| " \n", | |
| " self._FEATURES = np.zeros((num_states, num_actions, num_of_weights))\n", | |
| " for i, (s, a) in enumerate(\n", | |
| " itertools.product(range(num_states - 1), range(num_actions))):\n", | |
| " self._FEATURES[s, a, i] = 2\n", | |
| " self._FEATURES[s, a, num_of_weights - 1] = 1\n", | |
| " \n", | |
| " self._FEATURES[num_states - 1, 0, num_states * num_actions - 2] = 2\n", | |
| " self._FEATURES[num_states - 1, 0, num_of_weights - 1] = 1\n", | |
| "\n", | |
| " self._FEATURES[num_states - 1, 1, num_of_weights - 2] = 1\n", | |
| " self._FEATURES[num_states - 1, 1, num_of_weights - 1] = 2\n", | |
| " \n", | |
| " def __call__(self, state: int, action: int) -> np.array:\n", | |
| " \"\"\"\n", | |
| " Apply the the x(s, a) transformation.\n", | |
| "\n", | |
| " Args:\n", | |
| " state (int): The state index (from 0 to 6)\n", | |
| " action (int): 0 dashed\n", | |
| " 1 solid\n", | |
| " Returns:\n", | |
| " x(s, a) vector with the same shape as the weight vector\n", | |
| " \"\"\"\n", | |
| " \n", | |
| " return self._FEATURES[state, action]" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "1ujRkBs_zn1y", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "To understand how it has been designed, it is easier to look into de below examples." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "jlVSnyhqrh7q", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "x = X()\n", | |
| "\n", | |
| "print('state 0, dashed: ' + str(x(0, 0)))\n", | |
| "print('state 0, solid: ' + str(x(0, 1)))\n", | |
| "print('\\n')\n", | |
| "print('...')\n", | |
| "print('state 3, dashed: ' + str(x(3, 0)))\n", | |
| "print('state 3, solid: ' + str(x(3, 1)))\n", | |
| "print('...')\n", | |
| "print('\\n')\n", | |
| "print('state 6, dashed: ' + str(x(6, 0)))\n", | |
| "print('state 6, solid: ' + str(x(6, 1)))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "EZm2mIG80SPd", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Note that we have in total 15 features, that is, more features than state-action pairs (14)." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "rEdG1yIO0vei", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## State-value function and the policy" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "DsixlDE40ifF", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "**Exercise**: let's implement the state-value function $q(s, a, \\mathbf{w})$.\n", | |
| "\n", | |
| "**Hint**: We are approx. q with a linear function approximation.\n", | |
| "\n", | |
| "**Hint 2**: $q(s, a, \\mathbf{w}) \\doteq \\mathbf{x}(s, a) \\cdot \\mathbf{w}$\n", | |
| "\n", | |
| "**Hint 3**: See `numpy.dot` ([link to doc](https://numpy.org/doc/stable/reference/generated/numpy.dot.html?highlight=dot#numpy.dot)) for performig the dot-product\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "E5WNse0M455S", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "class Q:\n", | |
| "\n", | |
| " def __init__(self, x: X, num_actions: int = 2):\n", | |
| " self._x = x\n", | |
| " self._num_actions = num_actions\n", | |
| "\n", | |
| " def __call__(\n", | |
| " self, state: int, action: int, weights: np.ndarray\n", | |
| ") -> float:\n", | |
| " \"\"\"\n", | |
| " Computes q(s, a; w).\n", | |
| "\n", | |
| " Args:\n", | |
| " state (int): the state index\n", | |
| " action (int): 0 dashed,\n", | |
| " 1 solid\n", | |
| " weights (ndarray): the weights\n", | |
| " Returns:\n", | |
| " The estimated value of q.\n", | |
| " \"\"\"\n", | |
| "\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " x = None\n", | |
| " dot = None\n", | |
| " ### END CODE HERE ###\n", | |
| "\n", | |
| " return dot\n", | |
| "\n", | |
| " def max(self, state: int, weights: np.ndarray) -> int:\n", | |
| " return max((self(state, action, weights) for \n", | |
| " action in range(self._num_actions)))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "06f0ToB8r3xE", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "q = Q(X())\n", | |
| "weights = np.ones(15)\n", | |
| "weights[13] = 10\n", | |
| "\n", | |
| "print('q(0, 0, w) = ' + str(q(0, 0, weights)))\n", | |
| "print('q(0, 1, w) = ' + str(q(0, 1, weights)))\n", | |
| "print('q(6, 1, w) = ' + str(q(6, 1, weights)))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "FXai_c363AdM", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "**Expected Output**:\n", | |
| "\n", | |
| "q(0, 0, w) = 3.0\n", | |
| "\n", | |
| "q(0, 1, w) = 3.0\n", | |
| "\n", | |
| "q(6, 1, w) = 12.0" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "DtAXMAOt3Mgc", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "To save time, we are providing an implementation of an e-greedy policy. It's free! Nothing particular to do here.\n", | |
| "\n", | |
| "It corresponds to the same code used by our last workshop (with just some few adaptations)." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "4urPIoD5Lpar", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "class EGreedyPolicy:\n", | |
| "\n", | |
| " def __init__(self, \n", | |
| " q: Q, \n", | |
| " num_actions: int = 2, \n", | |
| " exploration_rate: float = .0, \n", | |
| " seed: Optional[int] = 0):\n", | |
| " self._q = q\n", | |
| " self._num_actions = num_actions\n", | |
| " self._exploration_rate = exploration_rate\n", | |
| " self._rand = random.Random(x=seed)\n", | |
| " \n", | |
| " def __call__(self, state: int, weights: np.ndarray) -> int:\n", | |
| " \"\"\"\n", | |
| " Selects the action to given state according to epsilon greedy exploration \n", | |
| " strategy.\n", | |
| "\n", | |
| " Args:\n", | |
| " state (int): the state index\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._num_actions - 1)\n", | |
| "\n", | |
| " f = lambda i: self._q(state, i, weights)\n", | |
| " best_action = max(range(self._num_actions), key=f)\n", | |
| "\n", | |
| " return best_action" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "bejiAXzO00kH", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Semi-gradient Q-Learning" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "lwR1rrrp3jmO", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Finally the most interesting part. We will implement the semi-gradient Q-Learning algorithm.\n", | |
| "\n", | |
| "If you recall from last workshop, the semi-gradient implementation relies at\n", | |
| "\n", | |
| "$$\n", | |
| "\\mathbf{w}_{t+1} \\doteq \\mathbf{w}_t + \\alpha \\cdot \\delta_t \\nabla_\\mathbf{w}{q(s, a, \\mathbf{w})}\n", | |
| "$$\n", | |
| "\n", | |
| "where $\\delta_t$ is the TD error which depends on the algorithm we are tring to implement. For example, for Sarsa we have:\n", | |
| "\n", | |
| "$$\n", | |
| "\\delta_t \\doteq R_{t+1} + \\gamma \\cdot q(s', a', \\mathbf{w}) - q(s, a, \\mathbf{w})\n", | |
| "$$\n", | |
| "\n", | |
| "and for Monte-Carlo we would have\n", | |
| "\n", | |
| "$$\n", | |
| "\\delta_t \\doteq R_{t+1} + \\gamma \\cdot R_{t+2} + \\cdots + \\gamma^{T-t-1} \\cdot R_{T} - q(s, a, \\mathbf{w})\n", | |
| "$$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "6xtVVhbq54SS", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "**Exercise**: implement semi-gradient Q-Learning algorithm.\n", | |
| "\n", | |
| "**Hint**: which is the equivalent TD error for Q-Learning? Recall that Q-Learing update rule for tabular methods was $Q(s, a) \\leftarrow Q(s, a) + \\alpha \\cdot \\big(R_{t+1} + \\gamma \\cdot max_{a'}{Q(s', a')} - Q(s, a) \\big)$\n", | |
| "\n", | |
| "**Hint 2**: Recall from last workshop that $\\nabla_\\mathbf{w} q(s, a, \\mathbf{w}) = \\nabla_\\mathbf{w} \\mathbf{w}^T \\mathbf{x}(s, a) = \\mathbf{x}(s, a)$\n", | |
| "\n", | |
| "**Hint 3**: To compute the $max_{a'}{\\mathbf{q}(s', a', \\mathbf{w})}$ use `q.max(next_state, weights)` \n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "paJ688ORMJWN", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "def semi_gradient_qlearning(env: BairdsCounterExampleMdp,\n", | |
| " learning_rate: float, \n", | |
| " exploration_rate: float, \n", | |
| " q: Q,\n", | |
| " x: X,\n", | |
| " weights: np.ndarray,\n", | |
| " discount_rate: float = .99,\n", | |
| " steps: int = 1000) -> List[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", | |
| " weights_snapshot = []\n", | |
| " state = np.random.choice(env.num_states())\n", | |
| " policy = EGreedyPolicy(q, env.num_actions(), exploration_rate)\n", | |
| " for _ in range(steps):\n", | |
| " weights_snapshot.append(np.copy(weights))\n", | |
| " action = policy(state, weights)\n", | |
| " next_state, reward = env.step(action)\n", | |
| "\n", | |
| " ### START CODE HERE ### (≈ 2 lines of code)\n", | |
| " delta = None\n", | |
| " weights += None\n", | |
| " ### END CODE HERE ###\n", | |
| "\n", | |
| " state = next_state\n", | |
| " \n", | |
| " return weights_snapshot" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "8QeHTZjD7-B_", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Now, if everything is set, we should see below that the weights diverge with training even for semi-gradient Q-Learning.\n", | |
| "\n", | |
| "That's bad and weird. Q-Learning is one of the best-understood bootstrapping methods and linear, semi-descent method used is arguably the simplest combination of bootstrapping and function approximation." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "EGcehs3fLuuB", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "env = BairdsCounterExampleMdp()\n", | |
| "learning_rate = 0.01\n", | |
| "exploration_rate = 0.5\n", | |
| "x = X()\n", | |
| "q = Q(x)\n", | |
| "weights = np.ones(15)\n", | |
| "weights[13] = 10\n", | |
| "\n", | |
| "snapshot = semi_gradient_qlearning(env, learning_rate, exploration_rate, q, x, weights)\n", | |
| "\n", | |
| "snapshot = np.array(snapshot).T\n", | |
| "\n", | |
| "plt.figure(figsize=(10, 5))\n", | |
| "\n", | |
| "for i in range(15):\n", | |
| " plt.plot(snapshot[i, :], label='theta' + str(i + 1))\n", | |
| "plt.xlabel('Sweeps')\n", | |
| "plt.ylabel('Theta value')\n", | |
| "plt.title('Q-Learning (\\u03b5=0.5)')\n", | |
| "plt.legend()\n", | |
| "\n", | |
| "plt.show()" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "J6xzKkpD815-", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "it is however possible to guarantee convergence of Q-Learning as long as the behavior policy is sufficiently close to the target polic, for example, an epsilon greedy policy with small ε." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "cBoLrijwuobm", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "env = BairdsCounterExampleMdp()\n", | |
| "learning_rate = 0.01\n", | |
| "exploration_rate = 0.0001\n", | |
| "x = X()\n", | |
| "q = Q(x)\n", | |
| "weights = np.ones(15)\n", | |
| "weights[13] = 10\n", | |
| "\n", | |
| "snapshot = semi_gradient_qlearning(env, learning_rate, exploration_rate, q, x, weights)\n", | |
| "\n", | |
| "snapshot = np.array(snapshot).T\n", | |
| "\n", | |
| "plt.figure(figsize=(10, 5))\n", | |
| "\n", | |
| "for i in range(15):\n", | |
| " plt.plot(snapshot[i, :], label='theta' + str(i + 1))\n", | |
| "plt.xlabel('Sweeps')\n", | |
| "plt.ylabel('Theta value')\n", | |
| "plt.title('Q-Learning (\\u03b5=0.0001)')\n", | |
| "plt.legend()\n", | |
| "\n", | |
| "plt.show()" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment