unifying_count_based_exploration_intrinsic_motivation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "unifying_count_based_exploration_intrinsic_motivation.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPoHbUfiZdct2Y+tueYQR+G",
      "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/jarrydmartinx/deep-rl/blob/master/unifying_count_based_exploration_intrinsic_motivation.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k9xDtkFsqL9W",
        "colab_type": "text"
      },
      "source": [
        "# Unifying Count-Based Exploration and Intrinsic Motivation (Bellemare (2016)\n",
        "\n",
        "@(Exploration)[Papers, Bellemare] \n",
        "## Overview\n",
        "### Problem\n",
        "Generalising uncertainty across states\n",
        "\n",
        "### Context \n",
        "Non-tabular RL (with FA)\n",
        "\n",
        "### Approaches\n",
        "*   Use (visit-)density models to measure uncertainty\n",
        "*   A method for deriving a pseudo-count from any density model. These pseudo-counts are best thought of as \"function approximation for exploration\"\n",
        "*   Allows generalisation of count-based exploration algorithms to the non-tabular case\n",
        "*   Achieves sensible pseudocounts from raw pixels\n",
        "*   Transforms pseudo-counts into exploration bonuses\n",
        "*  Show that intrinsic motivation and count-based exploration are two sides of the same coin\n",
        "\n",
        "##Notes\n",
        "### I Introduction\n",
        "* What is the uncertainty over: reward and transition functions\n",
        " * In tabular setting can quantify uncertainty using counts and Chernoff bounds, or inferred from a posterior over the environment parameters.\n",
        "* Both confidence intervals and posterior shrink as the inverse square root of the state-action visit count $N(x,a)$\n",
        "* This is fundamental to most theoretical results on exploration\n",
        "####MBIE-EB\n",
        "* Adds exploration bonus of $N(x,a)^{-\\frac{1}{2}}$\n",
        "* Accounts for uncertainties in both T and R\n",
        "* Enables a finite time bound on the agent's suboptimality\n",
        "#### Large Domains\n",
        "* States are visited at most once $\\rightarrow$ counts are useless\n",
        "#### Intrinsic Motivation\n",
        "* Provides qualitative guidance for exploration\n",
        "* Explore what surprises you, what's new, get curious\n",
        "\t* *Prediction error*, or \n",
        "\t* *Learning Progress* ($\\Delta$ pred. err.): if $e_t(A)$ is the error made by the agent at $t$ over some event $A$, and $e_{t+1}$ the same error after observing a new piece of information, then learning progress is: $$e_t(A) - e_{t-1}(A) $$ \n",
        "\t* *Compression Progress*\n",
        "\t* *Information Gain*\n",
        "* IM methods are attractive because they (seem to) remain applicable even in the absence of the Markov Property (and in absence of tabular representation), both of which are required for count-based algorithms\n",
        "* Yet the theoretical foundations of IM remain basically absent\n",
        "\n",
        "### Notation and Concepts\n",
        "* A *density model* is any model that assumes the states are independently distributed (but not necessarily identically distributed)\n",
        "\n",
        "\n",
        "### III From Densities to Pseudo-counts\n",
        "* To do IM exploration, we need to be able to answer the question: \"How novel is this (possibly unseen) state\"? \n",
        "\t* Empirical counts can't do it.\n",
        "\t* Nor is the problem solved by a Bayesian approach: even variable alphabet models (e.g. Hutter et al., 2013), can only assign a small diminishing probability to unseen states.\n",
        "* Approach: Extract pseudo-counts from a simple density model and use them within a variant of MBIE-EB\n",
        "* Which Density model: a simplified, pixel-level version of the CTS model for Atari 2600 frames (Bellemare et al., 2014). An impoverished model compared to SOA density models for images. Being count-based, it is very fast though.\n",
        "\n",
        "#### Pseudo-Counts and the Recoding Probability\n",
        "Suppose we have a density model $\\rho$ over $\\mathcal{X}$. \n",
        "* The model, may be approximate, biased or even inconsistent.\n",
        "Define the *recoding probability* of a state $$\n",
        "\n",
        "### IV The Connection to Intrinsic Motivation\n",
        "* Pseudocounts are closely related to Information Gain\n",
        "* IG is commonly used to quantify uncertainty or novelty\n",
        "* IG is defined w.r.t. a *mixture model* $\\xi$ over a class of density models $\\mathcal{M}$ \n",
        "\t* The model makes predictions according to a weighted combination from $\\mathcal{M}$, with $w_n(\\rho)$ the posterior weight on $\\rho$. $$ \\xi_n(x) := \\xi(x ; x_{1:n}) := \\int_{\\rho\\in\\mathcal{M}} w_n(\\rho)\\rho(x ; x_{1:n})\\ d\\rho$$\n",
        "\t* The posterior weights are defined recursively, starting from a prior distribution $$w_{n+1}(\\rho) := w_n(\\rho, x_{n+1})\\qquad \\qquad w_n(\\rho, x):= \\frac{w_n(\\rho)\\rho(x ; x_{1:n})}{\\xi_n(x)}$$\n",
        "\t* Information gain is then the KL-divergence from prior to posterior that results from observing $x$. $$IG_n(x):= IG(x ; x_{1:n}) := KL(w_n(. , x)\\ \\Vert\\ w_n )$$\n",
        "\n",
        "* Note that this means that something is really only novel with respect to your model, or with respect to your predictions. If it violates your predictions in some broad sense, or changes the way you would predict, then it is novel.\n",
        "* Note also the point from Algorithmic Information Theory, that an uncompressible string is not interesting, OR is this a failing of AIT. **TODO**\n",
        "* Or rather Schmidhuber's notion that if it doesn't improve your ability to predict, it's not interesting.\n",
        "\n",
        "\n",
        "### Experiments\n",
        "* Focus on Atari 2600 games from the ALE, focusing on games where myopic exploration fails. Great improvement over then SOA in Montezuma's Revenge.\n",
        "* Apply them to an experience replay setting and to an actor-critic setting, improved performance in both cases. \n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M4LYzuFDqQm-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}