labs/MAB.Bandits.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "StGsDuF_Whon"
   },
   "source": [
    "# Practical Session : Playing Stochastic Multi-Armed Bandit Games\n",
    "\n",
    "Code inspired by the [Pyma bandit library](https://www.di.ens.fr/~cappe/Code/PymaBandits/) by O. Cappé and A. Garivier and the [SMPyBandit library](https://github.com/SMPyBandits/SMPyBandits) of Lilian Besson."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ld0sIxwm2afO"
   },
   "outputs": [],
   "source": [
    "# If you are running this notebook on Colab, setup with the following:\n",
    "!git clone https://github.com/yfletberliac/rlss2019-hands-on.git > /dev/null 2>&1\n",
    "import sys\n",
    "sys.path.insert(0, './rlss2019-hands-on/utils/bandits')\n",
    "# If using the notebook locally, replace by:\n",
    "# sys.path.insert(0, '../utils/bandits')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "xm3EFUiMWho1"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "import time\n",
    "\n",
    "# Bandit specific functions and classes \n",
    "import Arms as arm\n",
    "from StochasticBandit import *\n",
    "from BanditTools import * \n",
    "import BanditBaselines as alg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CnC90yPhWhpQ"
   },
   "source": [
    "# I) Understanding the experimental setup with naive bandit strategies\n",
    "\n",
    "\n",
    "### 1) Creating a bandit environnement\n",
    "\n",
    "Different arm classes are defined in `Arms.py` (you are welcome to add more!). To define a multi-armed bandit (a `MAB` object), you need to input a list of such arms. Some functions in `StochasticBandits.py` also define directly some particular MAB objects. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "P1bpRGo1WhpW"
   },
   "outputs": [],
   "source": [
    "nbArms = 3\n",
    "bandit1 = MAB([arm.Bernoulli(0.2), arm.Gaussian(3, 1), arm.TruncatedExponential(2, 1)])\n",
    "bandit2 = BernoulliBandit([0.3, 0.4, 0.5]) # directly creates a Bernoulli bandit from a vector of means\n",
    "\n",
    "print(\"The means of bandit instance 1 are\", bandit1.means)\n",
    "print(\"The means of bandit instance 2 are\", bandit2.means)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "TQceO7tuWhpq"
   },
   "source": [
    "### 2) Executing a simple bandit strategy\n",
    "\n",
    "The function given below executes one bandit algorithm on one MAB instance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Mc53yKUNWhpw"
   },
   "outputs": [],
   "source": [
    "def OneBanditOneLearnerOneRun(bandit, learner, timeHorizon):\n",
    "    \"\"\"\n",
    "    Run a bandit strategy (learner) on a MAB instance (bandit) for (timeHorizon) time steps\n",
    "    output : sequence of arms chosen, sequence of rewards obtained\n",
    "    \"\"\"\n",
    "    selections = []\n",
    "    rewards = []\n",
    "    learner.clear() # reset previous history\n",
    "    for t in range(timeHorizon):\n",
    "        arm = learner.chooseArmToPlay()\n",
    "        reward = bandit.generateReward(arm)\n",
    "        learner.receiveReward(arm, reward)\n",
    "        # Update statistics\n",
    "        selections.append(arm)\n",
    "        rewards.append(reward)\n",
    "    return selections, rewards\n",
    "    \n",
    "def CumulativeRegret(bandit,selections):\n",
    "    \"\"\"Compute the pseudo-regret associated to a sequence of arm selections\"\"\"\n",
    "    return np.cumsum(max(bandit.means)*np.ones(len(selections)) - np.array(bandit.means)[selections])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ghgw0SD1WhqA"
   },
   "source": [
    "For the moment, we implemented two naive bandit strategies : the greedy strategy (or Follow-the-Leader, `FTL`) and a strategy that explores arms uniformly at random (`UniformExploration`). Such strategies (as the one you will implement) are defined as objects in `BanditsAlgorithms.py`. Below we run `FTL` on one of the bandit instances defined above, and visualize its behavior."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3KdllLxJWhqF",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "timeHorizon = 200\n",
    "bandit = bandit2\n",
    "learner = alg.FTL(nbArms)\n",
    "\n",
    "selections, rewards = OneBanditOneLearnerOneRun(bandit, learner, timeHorizon)\n",
    "regret = CumulativeRegret(bandit, selections)\n",
    "\n",
    "# Visualize results (on one run) \n",
    "\n",
    "# Histogram of the number of arms selections\n",
    "plt.clf()\n",
    "plt.xlabel(\"Arms\", fontsize=14)\n",
    "plt.ylabel(\"Number of arms selections\", fontsize=14)\n",
    "plt.hist(selections, max(selections) + 1)\n",
    "plt.title(\"Number of selections of each arm\", fontsize=14)\n",
    "# plt.savefig('./Figure/test'+ learner.name() + '.pdf')\n",
    "\n",
    "# Cumulative regret as a function of time\n",
    "plt.figure(2)\n",
    "plt.clf()\n",
    "plt.xlabel(\"Time steps\", fontsize=14)\n",
    "plt.ylabel(\"Cumulative regret\", fontsize=14)\n",
    "plt.title(\"Regret as a function of time\")\n",
    "plt.plot(range(timeHorizon), regret, 'black', linewidth=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5a1exjgTWhqX"
   },
   "source": [
    "### 3) Comparing two (bad) learners on one run\n",
    "\n",
    "We now compare pure exploration and pure exploitation on a single run. If you run this code multiple time, you will have very different results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "CPZrSPFqWhqd"
   },
   "outputs": [],
   "source": [
    "learner1 = alg.UniformExploration(nbArms)\n",
    "learner2 = alg.FTL(nbArms)\n",
    "\n",
    "# Run the two learners\n",
    "selections, rewards = OneBanditOneLearnerOneRun(bandit, learner1, timeHorizon)\n",
    "regret1 = CumulativeRegret(bandit, selections)\n",
    "selections, rewards = OneBanditOneLearnerOneRun(bandit, learner2, timeHorizon)\n",
    "regret2 = CumulativeRegret(bandit, selections)\n",
    "\n",
    "# Compare their regret\n",
    "plt.xlabel(\"Time steps\", fontsize=14)\n",
    "plt.ylabel(\"Cumulative regret\", fontsize=14)\n",
    "plt.title(\"Regret as a function of time\")\n",
    "plt.plot(range(0, timeHorizon), regret1,label=learner1.name())\n",
    "plt.plot(range(0, timeHorizon), regret2,label=learner2.name())\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "EOyZy5FIWhqu"
   },
   "source": [
    "### 4) Comparison averaged over multiple runs\n",
    "\n",
    "The regret is defined as an **expectation**, so we need several runs to **estimate** its value. We can also take a look at the distribution of the pseudo-regret. The function below gathers results accross multiple runs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "06GnW6mFWhqz"
   },
   "outputs": [],
   "source": [
    "def OneBanditOneLearnerMultipleRuns(bandit, learner, timeHorizon, N_exp, tsave=[]):\n",
    "    if (len(tsave) == 0):\n",
    "        tsave = np.arange(timeHorizon)\n",
    "    savedTimes = len(tsave)\n",
    "    Regret = np.zeros((N_exp, savedTimes)) # Store the regret values on different runs\n",
    "    for n in range(N_exp):\n",
    "        np.random.seed()\n",
    "        selections, rewards = OneBanditOneLearnerOneRun(bandit, learner, timeHorizon)\n",
    "        regret_one_run = CumulativeRegret(bandit, selections)\n",
    "        Regret[n, :] = np.array(regret_one_run)[tsave] # Store a sub-sampling of the cumulative regret\n",
    "    return Regret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "I0bXeovUWhrD"
   },
   "source": [
    "#### a) For one algorithm (FTL)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gUcd8vO6WhrU"
   },
   "source": [
    "One can start by displaying the mean regret and some quantiles. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jeFrpgpRWhra"
   },
   "outputs": [],
   "source": [
    "def plot_regret(learner, bandit, N_exp=200, timeHorizon=200):\n",
    "    tsave = np.arange(1, timeHorizon, 10)\n",
    "\n",
    "    regret = OneBanditOneLearnerMultipleRuns(bandit, learner, timeHorizon, N_exp, tsave)\n",
    "    meanRegret = np.mean(regret, 0)\n",
    "    upperQuantile = np.quantile(regret, 0.95, 0) # requires numpy 1.15\n",
    "    lowerQuantile = np.quantile(regret, 0.05, 0)\n",
    "\n",
    "    plt.clf()\n",
    "    plt.plot(tsave, meanRegret, linewidth=3.0, color=\"b\", label=\"Mean regret for \"+learner.name())\n",
    "    plt.plot(tsave, upperQuantile, linestyle=\"dashed\", color=\"b\")\n",
    "    plt.plot(tsave, lowerQuantile, linestyle=\"dashed\", color=\"b\")\n",
    "    plt.legend()\n",
    "\n",
    "    \n",
    "plot_regret(learner2, bandit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0hsd6WNUWhro"
   },
   "source": [
    "To highlight the variability of the regret, one can also look at the histogram of the value of $R_T$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "-egGMZbgWhrs"
   },
   "outputs": [],
   "source": [
    "def plot_regret(learner, bandit, N_exp=200, timeHorizon=200):\n",
    "    tsave = np.arange(1, timeHorizon, 10)\n",
    "\n",
    "    regret = OneBanditOneLearnerMultipleRuns(bandit, learner, timeHorizon, N_exp, tsave)\n",
    "    meanRegret = np.mean(regret, 0)\n",
    "    upperQuantile = np.quantile(regret, 0.95, 0) # requires numpy 1.15\n",
    "    lowerQuantile = np.quantile(regret, 0.05, 0)\n",
    "\n",
    "    plt.clf()\n",
    "    plt.plot(tsave, meanRegret, linewidth=3.0, color=\"b\", label=\"Mean regret for \"+learner.name())\n",
    "    plt.plot(tsave, upperQuantile, linestyle=\"dashed\", color=\"b\")\n",
    "    plt.plot(tsave, lowerQuantile, linestyle=\"dashed\", color=\"b\")\n",
    "    plt.legend()\n",
    "    plt.show()\n",
    "    \n",
    "    finalRegret = regret[:, len(tsave)-1]\n",
    "    plt.clf()\n",
    "    plt.xlabel(\"Regret at time T=\"+str(timeHorizon), fontsize=14)\n",
    "    plt.ylabel(\"Counts\", fontsize=14)\n",
    "    plt.hist(finalRegret, 15)\n",
    "    plt.title(\"Histogram of the final regret\", fontsize=14)\n",
    "    plt.show()\n",
    "\n",
    "\n",
    "plot_regret(learner2, bandit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "S4rliwcrWhrz"
   },
   "source": [
    "#### b) FTL versus Uniform"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "p3NgdcgIWhr1"
   },
   "outputs": [],
   "source": [
    "N_exp = 200\n",
    "timeHorizon = 500\n",
    "tsave = np.arange(1, timeHorizon, 10)\n",
    "\n",
    "regret1 = OneBanditOneLearnerMultipleRuns(bandit, learner1, timeHorizon, N_exp, tsave)\n",
    "regret2 = OneBanditOneLearnerMultipleRuns(bandit, learner2, timeHorizon, N_exp, tsave)\n",
    "\n",
    "plt.clf()\n",
    "plt.plot(tsave, np.mean(regret1, 0), linewidth=2.0, color=\"b\", label=\"mean regret of \"+learner1.name())\n",
    "plt.plot(tsave, np.quantile(regret1, 0.95, 0), tsave, np.quantile(regret1,0.05,0), linestyle=\"dashed\", color=\"b\")\n",
    "plt.plot(tsave, np.mean(regret2, 0), linewidth=2.0, color=\"r\", label=\"mean regret of \"+learner2.name())\n",
    "plt.plot(tsave, np.quantile(regret2, 0.95, 0), tsave, np.quantile(regret2,0.05,0), linestyle=\"dashed\", color=\"r\")\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Njkcs6cnWhr6"
   },
   "source": [
    "As you can see, both algorithms have **linear regret**, although the pseudo-regret of FTL has a much higher variance. You are now ready to try smarter algorithms!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "58Yfb2ZMWhr8"
   },
   "source": [
    "# II) The UCB1 algorithm\n",
    "\n",
    "The UCB1 algorithm is proposed by [Auer et al](https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf) for bandit instances with bounded rewards (in $[0,1]$ to fix the ideas). One can extend it to depend on some parameter $\\alpha$: \n",
    "\n",
    "$$A_{t} = \\underset{a}{\\text{argmax}} \\left[\\hat{\\mu}_a(t-1) + \\sqrt{\\frac{\\alpha \\log(t)}{N_a(t-1)}}\\right],$$\n",
    "where $\\hat{\\mu}_a(t)$ is the empirical mean of arm $a$ after $t$ rounds and $N_a(t)$ is the number of selections of arm $a$ till that time. \n",
    "\n",
    "UCB1 was originally proposed with $\\alpha = 2$. Its analysis was later refined to allow for $\\alpha > 1/2$ (see [here](http://sbubeck.com/Bubeckthesis.pdf) or [here](https://hal.archives-ouvertes.fr/hal-00738209/file/klucb.pdf)).\n",
    "\n",
    "* Implement UCB($\\alpha$).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "gAN6mcu3Whr-"
   },
   "outputs": [],
   "source": [
    "class UCB:\n",
    "    def __init__(self, nbArms, alpha=0.5):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def clear(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def chooseArmToPlay(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def receiveReward(self, arm, reward):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def name(self):\n",
    "        return \"UCB\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Ov3yqTOiWhsD"
   },
   "source": [
    "* Pick a bounded bandit instance of your choice, and run UCB. Is the regret still linear?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZaJ_WQvpBSQ1"
   },
   "outputs": [],
   "source": [
    "bandit = ...\n",
    "learner = UCB(nbArms)\n",
    "plot_regret(learner, bandit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YdQdxPYpWhsO"
   },
   "source": [
    "This looks much safer than FTL! The regret of UCB is logarithmic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "P4BbRWHoWhsP"
   },
   "source": [
    "#### Influence of the parameter $\\alpha$\n",
    "\n",
    "* On a fixed bandit problem, run UCB with several values for the parameter $\\alpha$, and find the best value for this problem. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4Un42nRzWhsZ"
   },
   "source": [
    "#### Influence of the minimal gap (regret on different instances)\n",
    "\n",
    "The function `RandomBernoulliBandit()` in `Stochastic_Bandits.py` allows to generate random Bernoulli bandit instance in which the gap between the best and second best arm has a certain value. \n",
    "\n",
    "* Visualize the regret for several instances with different values of the minimal gap $\\Delta$, and comment on its influence on the regret."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "uUa8ac-vWhsb",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nbArms = 3\n",
    "bandit = RandomBernoulliBandit(0.05, nbArms)\n",
    "raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OHQ9fnUhWhsg"
   },
   "source": [
    "On a MAB instance with bounded rewards, UCB (with parameter alpha = 1/2) is known to satisfy \n",
    "\n",
    "$$ \\mathcal{R}_T \\simeq  \\sum_{a,\\Delta_{a} > 0} \\frac{\\log(T)}{2\\Delta_{a}} \\simeq \\frac{K-1}{\\Delta}\\log(T)$$\n",
    "\n",
    "where $\\Delta$ is the minimal gap. In the above experiment, we indeed observe that the regret increases when $\\Delta$ gets smaller. But we will later be more precise on what really influences the regret rate of a bandit algorithm. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "we-1f1t2Whsi"
   },
   "source": [
    "# III) Tweaking the UCB algorithm\n",
    "\n",
    "Applying the UCB algorithm to bounded rewards, the following tweaks are quite natural. First, the rewards are in $[0,1]$, but the UCB values may be outside this interval, so in practice one may want to \"clip\" them to be in the interval $[0,1]$. Then, when breaking ties, instead of choosing at random, one may do it in favor of the least selected arm instead of uniformly at random. This suggests the following modification of UCB($\\alpha$):\n",
    "\n",
    "$$A_{t+1} = \\text{argmin}_{a} \\left\\{N_a(t) : a \\in \\text{argmax}_{a} \\min\\left[\\mathrm{UCB}_a(t) , 1\\right] \\right\\}$$\n",
    "\n",
    "* Implement this simple modification of UCB. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "_HAtA3v5Whsj"
   },
   "outputs": [],
   "source": [
    "class UCB_Tweak:\n",
    "    \"\"\"UCB1 with parameter alpha, taking the minimum between the UCB and one and breaking ties in favor of the least drawn arm\"\"\"\n",
    "    def __init__(self, nbArms, alpha=0.5):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def clear(self):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    def chooseArmToPlay(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def receiveReward(self, arm, reward):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def name(self):\n",
    "        return \"UCB-Tweaked\"\n",
    "\n",
    "\n",
    "learner = UCB_Tweak(nbArms)\n",
    "plot_regret(learner, bandit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qmjg4gzLWhsp"
   },
   "source": [
    "#### Different regret guarantees\n",
    "\n",
    "The guarantees of UCB1 are given in terms of expected regret. Some authors have proposed a variant of the algorithm with high probability guarantees (see, e.g., Section 6 of [this paper](https://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf)). For some small value of the parameter $\\delta$ (e.g. $\\delta = 0.05$), you can try the alternative UCB algorithm, based on the index \n",
    "\n",
    "$$\\widetilde{\\mathrm{UCB}}_a(t) = \\hat{\\mu}_a(t) + \\sqrt{\\frac{1 + \\frac{1}{N_a(t)}}{2N_a(t)}\\left(1 + 2\\ln\\left(\\frac{K\\sqrt{N_a(t) + 1}}{\\delta}\\right)\\right)}$$\n",
    "\n",
    "* Implement this \"high-probability\" UCB and compare it with the previous algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "kHRcVsTfWhsq"
   },
   "outputs": [],
   "source": [
    "class UCB_Laplace:\n",
    "    \"\"\"UCB using other types of deviation inequalities\"\"\"\n",
    "    def __init__(self, nbArms, delta=0.01):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def clear(self):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    def chooseArmToPlay(self):\n",
    "        raise NotImplementedError\n",
    "        \n",
    "    def receiveReward(self, arm, reward):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    def name(self):\n",
    "        return \"UCB-Laplace\"      \n",
    "\n",
    "\n",
    "learner = UCB_Laplace(nbArms)\n",
    "plot_regret(learner, bandit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZjnQJvVLWhs0"
   },
   "source": [
    "UCB-Laplace performs really well! However, it has different regret guarantees compared to the other algorithms: something like \n",
    "$$\\mathbb{P}\\left(\\forall t\\in \\mathbb{N}, \\mathcal{R}_t \\leq  C\\sum_{a : \\mu_a < \\mu_\\star}\\frac{1}{\\Delta_a}\\ln\\left(\\frac{K}{\\Delta_a \\delta}\\right) \\right)\\geq 1 - \\delta.$$\n",
    "This high probability upper-bound is constant with respect to $T$ ! However, in expectation, one should control the probability $\\\\delta$ of the unfavorable event on which the regret can be as bad as $T$. Choosing $\\delta = 1/T$ would yield (again) to a logarithmic upper bound on the expected regret at time $T$ but possibly worse performance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0XFMLs4GWhs2"
   },
   "source": [
    "# IV) Complexity of a bandit problem \n",
    "\n",
    "On a Bernoulli bandit instance, the Lai and Robbins lower bound tells us that the regret is **asymptotically** no smaller than \n",
    "\n",
    "$$\\left(\\sum_{a ,\\Delta_a > 0} \\frac{\\Delta_a}{\\mathrm{kl}(\\mu_a,\\mu_\\star)}\\right) \\log(T),$$\n",
    "where $\\mathrm{kl}(\\mu_a,\\mu_\\star)$ is the KL-divergence between the Bernoulli distribution of parameter $\\mu_a$ and the Bernoulli distribution of parameter $\\mu_\\star$. The constant in front of the $\\log(T)$ may be called the **complexity** of the bandit problem.\n",
    "\n",
    "* Write a function that computes the complexity of a Bernoulli bandit instance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "EGn-NJ59Whs6"
   },
   "outputs": [],
   "source": [
    "def Complexity(bandit):\n",
    "    raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_wY8XreCWhtE"
   },
   "source": [
    "* On a Bernoulli bandit instance of your choice, add the theoretical lower bound $t \\mapsto C(\\nu) \\log(t)$ where $C(\\nu)$ is the complexity of the bandit problem to the regret curve of UCB. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Rw0eGdSTFF_4"
   },
   "outputs": [],
   "source": [
    "# Plot the Lai and Robbins lower bound, along with UCB regret\n",
    "raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ADvA4c5KWhtk"
   },
   "source": [
    "* Is UCB matching the lower bound? You may want to plot $\\mathcal{R}_t$ as a function of $\\log(t)$ (and look at large horizons) for a better check"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Ek6txqfsWhtr"
   },
   "source": [
    "The lower bound is super asymptotic! We see that UCB will eventually have a sub-optimal regret for large horizons... "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6iIV2R_7Whts"
   },
   "source": [
    "# V) From UCB to kl-UCB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lNa5Qyp_Whtt"
   },
   "source": [
    "In the Bernoulli case, we now investigate an algorithm designed for matching the Lai and Robbins lower bound, that is $\\mathrm{kl}$-UCB, proposed by [Cappé et al](https://hal.archives-ouvertes.fr/hal-00738209/file/klucb.pdf). It is also a UCB algorithm, but the upper confidence bound is more sophisticated: \n",
    "\n",
    "$$\\mathrm{UCB}_a(t) = \\max \\left\\{ q : N_a(t) \\mathrm{kl}\\left(\\hat{\\mu}_a(t),q\\right) \\leq \\log(t) + c\\log\\log(t) \\right\\},$$\n",
    "where $\\mathrm{kl}(\\mu,\\mu')$ is the KL-divergence between the distribution with mean $\\mu$ and that of mean $\\mu'$ in some exponential family and $c$ is some real parameter (often chosen to be zero in practice).\n",
    "\n",
    "In the Bernoulli case, this is the Bernoulli KL-divergence $\\mathrm{kl}(x,y) = x\\log(x/y) + (1-x)\\log((1-x)/(1-y)).$\n",
    "\n",
    "Useful KL-divergence functions are already given in `BanditTools.py`.\n",
    "\n",
    "Here is a visualization of the computation of $\\mathrm{UCB}_a(t)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ADlw-3ub4HJP"
   },
   "outputs": [],
   "source": [
    "mu_hat = 0.4\n",
    "log_t_N = np.log(100)/10\n",
    "\n",
    "# Plot kl-divergence kl(mu_hat, q)\n",
    "qq = np.linspace(0, 1, 200)\n",
    "bern_kl_div = [klBern(mu_hat, q) for q in qq]\n",
    "plt.plot(qq, bern_kl_div, label=\"kl divergence\")\n",
    "plt.xlim([0, 1])\n",
    "plt.ylim([0, 1.5])\n",
    "\n",
    "# Plot kl-UCB = max(q: kl(mu_hat,q) <= log_t/N)\n",
    "plt.axhline(log_t_N, color=\"black\")\n",
    "plt.axvline(klucbBern(mu_hat, log_t_N), color=\"black\")\n",
    "plt.xticks([0, mu_hat, klucbBern(mu_hat, log_t_N), 1], ('0', r'$\\hat{\\mu}_a$', r'$UCB_a$', '1'))\n",
    "\n",
    "# Plot quadratic divergence\n",
    "plt.plot(qq, 2*(qq - mu_hat)**2, label=\"quadratic divergence\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "l3_HInv2_6QF"
   },
   "source": [
    "* Implement the kl-UCB algorithm. Some help for the computation of the indices can be found in BanditTools.py. You may want to code a generic version of kl-UCB, based on a divergence function to specify."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "8fNB8HHUWhtx"
   },
   "outputs": [],
   "source": [
    "class klUCB:\n",
    "    \"\"\"klUCB (Bernoulli divergence by default)\"\"\"\n",
    "    def __init__(self, nbArms, divergence=klucbBern, c=0):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def clear(self):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    def chooseArmToPlay(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def receiveReward(self, arm, reward):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def name(self):\n",
    "        return \"kl-UCB\"\n",
    "      \n",
    "learner = klUCB(nbArms)\n",
    "plot_regret(learner, bandit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "-bhYNT5cWht1"
   },
   "source": [
    "* Compare the regret of UCB, kl-UCB and the lower bound on at least the following two instances.\n",
    "\n",
    "The first instance has means very close to 0.5, and $\\mathrm{kl}(x,y) \\simeq 2(x-y)^2$ is a good approximation in this regime.\n",
    "Hence we expect UCB and kl-UCB to perform similarly on such an instance. \n",
    "\n",
    "On the second instance where the means are very low (a scenario inspired by online advertisement), the choice of algorithm is expected to make a bigger difference. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "DYRevVPWWht3"
   },
   "outputs": [],
   "source": [
    "banditA = BernoulliBandit([0.45, 0.5, 0.6])  \n",
    "banditB = BernoulliBandit([0.1, 0.05, 0.02, 0.01])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0EJAQda3WhuN"
   },
   "source": [
    "#### Beyond Bernoulli Bandits\n",
    "\n",
    "kl-UCB is also suited for rewards that belong to other one-dimensional exponential family, like Gaussian distributions with known variance, Poisson distributions or Exponential distributions (all the corresponding kl-divergences are given in `BanditTools.py`).\n",
    "\n",
    "* Try kl-UCB for a different family of distributions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "9sSC8oJtWhuT"
   },
   "source": [
    "# VI) A Bayesian strategy: Thompson Sampling "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "sSa6cBV2WhuV"
   },
   "source": [
    "We now explore one of the Bayesian strategies discussed in class: **Thompson Sampling**. This heuristic is very old, and its theoretical understanding is still quite partial beyond simple settings. Still, in the Bernoulli case, it is proved to be asymptotically optimal. Letting $\\pi_a(t)$ denote the posterior distribution on arm $a$ after $t$ rounds, the algorithm can be implemented as follows: \n",
    "\n",
    "$$\\forall a, \\theta_a(t) \\sim \\pi_a(t-1), \\ \\ \\ A_{t} = \\underset{a}{\\text{argmax }} \\theta_a(t)$$\n",
    "\n",
    "In the Bernoulli case, with a uniform (or more generally a Beta$(\\alpha,\\beta)$) prior distribution on each mean, the posterior distribution remains a Beta distribution. More precisely, one has\n",
    "\n",
    "$$\\pi_a(t) = \\mathrm{Beta}\\left(\\alpha + S_a(t), \\beta + N_a(t) - S_a(t)\\right),$$\n",
    "\n",
    "where $S_a(t)$ is the sum of rewards received from arm $a$ after $t$ rounds, and $N_a(t)$ is the number of selections of that arm, as before.\n",
    "\n",
    "* Implement Thompson Sampling for binary bandits with a Beta prior. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZI0LxWsuWhuY"
   },
   "outputs": [],
   "source": [
    "class ThompsonSampling:\n",
    "    \"\"\"Thompson Sampling with Beta(a,b) prior and Bernoulli likelihood\"\"\"\n",
    "    def __init__(self, nbArms, a=1, b=1):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def clear(self):\n",
    "        raise NotImplementedError\n",
    "    \n",
    "    def chooseArmToPlay(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def receiveReward(self, arm, reward):\n",
    "        raise NotImplementedError\n",
    "\n",
    "    def name(self):\n",
    "        return \"Thompson Sampling\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fBBnL_QlWhud"
   },
   "source": [
    "* Compare this algorithm to UCB and kl-UCB on a binary instance of your choice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Yfr3Sjv3Whuj"
   },
   "source": [
    "#### kl-UCB and Thompson Sampling for bounded rewards\n",
    "\n",
    "kl-UCB and Thompson Sampling can both be used for any bandit instance with rewards that are bounded in $[0,1]$. kl-UCB can be used without any modification (its analysis just extends to bounded distribution, as the sample concentration inequality can be used). However, for Thompson Sampling it is not the case: the algorithm needs to be modified to handle possibly non-binary rewards. The \"binarization trick\" that can be employed is described [here](http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf).\n",
    "\n",
    "* Check that your implementation of Thompson Sampling incorporates this binarization trick, and run the 3 previous algorithms on a bandit instance with bounded rewards that are not only binary. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lM4zvCNGWhus"
   },
   "source": [
    "# VII) Trying other bandit strategies \n",
    "\n",
    "You are welcome to try other approaches from the (rich) multi-armed bandit literature. \n",
    "\n",
    "* If you are interested in further understanding some randomized algorithm, you can try BESA, a puzzling strategy based on sub sampling: https://hal.archives-ouvertes.fr/file/index/docid/1025651/filename/BESA2.pdf\n",
    "\n",
    "* We did not (yet) talk about adversarial bandit approaches, for you may want to add the EXP3 strategy to this comparison at some point: http://rob.schapire.net/papers/AuerCeFrSc01.pdf\n",
    "\n",
    "* Or maybe a recent paper who tries to propose an algorithm efficient for stochastic and adversarial bandits: \n",
    "https://arxiv.org/abs/1807.07623"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "VjEgol6dWhuu"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "name": "MAB.Bandits.ipynb",
   "provenance": [],
   "toc_visible": true,
   "version": "0.3.2"
  },
  "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}