Lecture 11 - Fast RL I.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "16df9564",
   "metadata": {},
   "source": [
    "# Lecture 11 - Fast RL I\n",
    "\n",
    "provided by [Stanford CS234](https://www.youtube.com/watch?v=FgzM3zpZ55o)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "618c06cf",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "Table of Contents: <br>\n",
    "    \n",
    "<ul>\n",
    "    <li>1. <a href=\"#1.-Introduction\">Introduction</a>\n",
    "    <li>2. <a href=\"#2.-Multi-Armed-Bandits\">Multi-Armed Bandits</a>\n",
    "        <ul>\n",
    "            <li>2.1. <a href=\"#2.1.-Greedy-Algorithm\">Greedy Algorithm</a></li>\n",
    "            <li>2.2. <a href=\"#2.2.-Upper-Confidence-Bounds\">Upper Confidence Bounds</a></li>\n",
    "        </ul>\n",
    "    </li>\n",
    "    <li>3. <a href=\"#3.-Resource\">Resource</a></li>\n",
    "</ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8837110",
   "metadata": {},
   "source": [
    "# 1. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c0b90ce",
   "metadata": {},
   "source": [
    "2 Categories:\n",
    "* _Computationally efficiency_\n",
    "    * takes a long time to compute something (an AV needs to calculate something fast as it is moving)\n",
    "* _Sample efficiency_\n",
    "    * sometimes experience/data is hard to gather\n",
    "    \n",
    "How do we evaluate our algorithm?\n",
    "* how good is it?\n",
    "* does it converge?\n",
    "* how quickly does it converge?\n",
    "\n",
    "We usually evaluate an algorithm based on its performance, but today we will evaluate it based on the amount of data it needs to make good decisions.\n",
    "\n",
    "The next 3 lectures (including this one) will cover the following:\n",
    "* __settings__: (bandits, MDPs, etc)\n",
    "* __frameworks__: evaluation criteria for evaluating RL algorithms\n",
    "* __approaches__: classes of algorithms for achieving particular evaluation criterias\n",
    "\n",
    "Specifically, for today's lecture we will cover:\n",
    "* setting: multi-armed bandits\n",
    "* framework: regret\n",
    "* approach: optimism under uncertainty\n",
    "* framework: bayesian regret\n",
    "* approach: probability matching/thompson sampling"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3892c2d3",
   "metadata": {},
   "source": [
    "# 2. Multi-Armed Bandits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33d94b9a",
   "metadata": {},
   "source": [
    "* Multi-armed bandits is a tuple of $(\\mathcal{A}, \\mathcal{R})$\n",
    "* $\\mathcal{A}$ is a known set of $m$ actions (arms)\n",
    "* $R^{a}(r) = \\mathbb{P}[r~|~a]$ is an unknown probability distribution over rewards\n",
    "* each step $t$, the agent selects an action $a_{t} \\in \\mathcal{A}$ (pulling an arm)\n",
    "* environment produces a reward $r_{t} \\sim \\mathcal{R}^{a_{t}}$\n",
    "* Goal: maximize cumulative reward $\\sum_{\\tau = 1}^{t}r_{\\tau}$\n",
    "\n",
    "$$\n",
    "Q(a) = \\mathbb{E}[r~|~a]\\hspace{1em} (Eq.~1)\\\\\n",
    "V^{*} = Q(a^{*}) = \\underset{a \\in \\mathcal{A}}{max}Q(a) \\hspace{1em} (Eq.~2)\\\\\n",
    "l_{t} = \\mathbb{E}[V^{*} - Q(a_{t})] \\hspace{1em} (Eq.~3)\\\\\n",
    "L_{t} = \\mathbb{E}[\\sum_{\\tau = 0}^{t} V^{*} - Q(a_{\\tau})] \\hspace{1em} (Eq.~4)\n",
    "$$\n",
    "\n",
    "Eq. 1 is the expected reward (mean reward) given an action (we ignore states in the multi-armed bandit setting). Eq. 2: Take the action $a$ that yields the largest action-value. Eq. 3: opportunity loss (the difference between the optimal action-value at time step $t$ and the action you took). Eq. 4 is the total opportunity loss (the sum of regrets across all time steps for an episode).\n",
    "\n",
    "$$\n",
    "\\Delta_{i} = V^{*} - Q(a_{i})\\\\\n",
    "\\begin{equation}\n",
    "    \\begin{split}\n",
    "    L_{t} & = \\mathbb{E}[\\sum_{\\tau = 1}^{t}V^{*} - Q(a_{\\tau})]\\\\\n",
    "    & = \\sum_{a \\in \\mathcal{A}} \\mathbb{E}[N_{t}(a)](v^{*} - Q(a))\\\\\n",
    "    & = \\sum_{a \\in \\mathcal{A}} \\mathbb{E}[N_{t}(a)]\\Delta_{a}\\\\\n",
    "    \\end{split}\n",
    "\\end{equation} \\hspace{1em} (Eq.~5)\n",
    "$$\n",
    "\n",
    "$N_{t}(a)$ is the number of times action $a$ has been picked up to time step $t$.\n",
    "\n",
    "By maximizing cumulative reward, we minimize total regret."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64dfd2d6",
   "metadata": {},
   "source": [
    "## 2.1. Greedy Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf977655",
   "metadata": {},
   "source": [
    "The simplest approach is the greedy algorithm.\n",
    "\n",
    "$$\n",
    "\\hat{Q}_{t}(a) = \\frac{1}{N_{t}(a)} \\sum_{t = 1}^{T} r_{t} \\mathcal{1}(a_{t} = a) \\hspace{1em} (Eq.~6)\\\\\n",
    "a^{*}_{t} = \\underset{a \\in \\mathcal{A}}{argmax} \\hat{Q}_{t}(a) \\hspace{1em} (Eq.~7)\\\\\n",
    "$$\n",
    "\n",
    "A slightly more nuanced version of this is the $\\epsilon$-greedy algorithm. It will select $a_{t} = \\underset{a \\in \\mathcal{A}}{argmax} \\hat{Q}_{t}(a)$ with probability $1 - \\epsilon$ and a random action with probability $\\epsilon$.\n",
    "\n",
    "The problem with these is that they can get stuck in suboptimal actions forever."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "466a4566",
   "metadata": {},
   "source": [
    "## 2.2. Upper Confidence Bounds"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b97a2764",
   "metadata": {},
   "source": [
    "Types of Regret bounds:\n",
    "* __problem independent__: bound on regret is a function of $T$\n",
    "* __problem dependent__: bound regret as a function of number of times we pull each arm and gap between reward and optimal action\n",
    "\n",
    "From past work, we find that the lower bound is sublinear.\n",
    "\n",
    "$$\n",
    "\\underset{t \\rightarrow \\infty}{lim} L_{t} \\ge log(t) \\sum_{a~|~\\Delta_{a} > 0} \\frac{\\Delta_{a}}{D_{KL}(\\mathcal{R}^{a}||\\mathcal{R}^{a*})} \\hspace{1em} (Eq.~8)\\\\\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25a2ab8c",
   "metadata": {},
   "source": [
    "In Upper Confidence Bounds (UCB),\n",
    "* we estimate an upper confidence $U_{t}(a)$ for each action value such that $Q(a) \\le U_{t}(a)$\n",
    "* depends on number of times $N_{t}(a)$\n",
    "* select action to maximize UCB: $a_{t} = \\underset{a \\in \\mathcal{A}}{argmax}[U_{t}(a)]$\n",
    "\n",
    "We leverage __Hoeffding's Inequality__:\n",
    "\n",
    "Consider X to be an i.i.d. random variable in $[0, 1]$ from 1 to n. $\\bar{X}_{n}$ to be the sample mean.\n",
    "$$\n",
    "\\mathcal{P}[\\mathcal{E}[X] > \\bar{X}_{n} + u] \\le exp(-2nu^{2}) \\hspace{1em} (Eq.~9)\\\\\n",
    "$$\n",
    "\n",
    "We then derive the UCB equation for selecting an action at timestep $t$. \n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "    \\begin{split}\n",
    "    U_{t}(a) = \\hat{Q}(a) + \\sqrt{\\frac{2 log(t)}{N_{t}(a)}}\\\\\n",
    "    a_{t} = \\underset{a \\in \\mathcal{A}}{argmax}[U_{t}(a)]\n",
    "    \\end{split}\n",
    "\\end{equation} \\hspace{1em} (Eq.~10)\\\\\n",
    "$$\n",
    "\n",
    "UCB achieves logarithmic asymptotic total regret:\n",
    "\n",
    "$$\n",
    "\\underset{t \\rightarrow \\infty}{lim} L_{t} \\le 8 log(t) \\sum_{a~|~\\Delta_{a} > 0} \\Delta_{a} \\hspace{1em} (Eq.~11)\\\\\n",
    "$$\n",
    "\n",
    "For an example of how UCB works refer to this: https://www.youtube.com/watch?v=FgmMK6RPU1c&t=507s&ab_channel=ritvikmath."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f657f6b",
   "metadata": {},
   "source": [
    "# 3. Resource"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32e04a27",
   "metadata": {},
   "source": [
    "If you missed the link right below the title, I'm providing the resource here again along with the course website.\n",
    "\n",
    "- [Stanford CS234](https://www.youtube.com/watch?v=FgzM3zpZ55o)\n",
    "- [Course Website](http://web.stanford.edu/class/cs234/index.html)\n",
    "\n",
    "This is a series of 15 lectures provided by Stanford.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5c15c5c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}