Lecture 13 - Fast RL III.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "16df9564",
   "metadata": {},
   "source": [
    "# Lecture 13 - Fast RL III\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.-PAC-Criteria\">PAC Criteria</a>\n",
    "    <li>3. <a href=\"#3.-Bayesian-Model-Based-RL\">Bayesian Model-Based  RL</a>\n",
    "    <li>4. <a href=\"#4.-Generalization-and-Exploration\">Generalization and Exploration</a>\n",
    "    <li>5. <a href=\"#5.-Resource\">Resource</a></li>\n",
    "</ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8837110",
   "metadata": {},
   "source": [
    "# 1. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24456ebc",
   "metadata": {},
   "source": [
    "We defined (PAC) as a framework last lecture. But, we can also classify algorithms as PAC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a88cd62",
   "metadata": {},
   "source": [
    "# 2. PAC Criteria"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f1ff285",
   "metadata": {},
   "source": [
    "For an algorithm to be PAC, it must match these 3 criteria:\n",
    "* optimism\n",
    "    * must have optimism (assume unexplored states yield good reward)\n",
    "* accuracy\n",
    "    * must balance between being optimal and being optimistic\n",
    "    * $V^{\\pi_{t}}(s_{t}) - V^{\\pi_{t}}_{\\mu}(s_{t}) \\le \\epsilon$ where $V^{\\pi_{t}}_{\\mu}(s_{t})$ is a hybrid value function between the optimal and optimistic policy\n",
    "* bounded learning complexity (bounded by $\\epsilon, \\delta$)\n",
    "    * total \\# of Q updates is updated\n",
    "    * \\# of times visited unknown state-action pair\n",
    "    \n",
    "I won't cover the following section in the lecture: a proof of how MBIE-EB is PAC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec8c1afb",
   "metadata": {},
   "source": [
    "# 3. Bayesian Model-Based RL"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5eab8947",
   "metadata": {},
   "source": [
    "We know model-based RL is where the agent has a _model_ of the real world (transition model and reward model). For Bayesian Model-Based RL, we maintain a posterior distribution over MDP models and estimate transition and rewards. Our posterior guides our exploration."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45b52b59",
   "metadata": {},
   "source": [
    "Initialize prior over the dynamics and reward models for each $(s, a)$, $p(R_{sa}), p(T(s'~|~s, a))$ <br>\n",
    "Initialize state $s_{0}$. <br>\n",
    "loop <br>\n",
    "$\\quad$ Sample a MDP M: for each $(s, a)$ pair, sample a dynamics model $T(s'~|~s, a)$ and reward model $R(s, a)$ <br>\n",
    "$\\quad$ Compute $Q^{*}_{M}$, optimal value for MDP $M$ <br>\n",
    "$\\quad$ $a_{t} = \\underset{a \\in A}{argmax} Q^{*}_{M}(s_{t}, a)$ <br>\n",
    "$\\quad$ Observe reward $r_{t}$ and next state $s_{t + 1}$ <br>\n",
    "$\\quad$ Update posterior $p(R_{a_{t}, s_{t}}~|~r_{t})$, $p(T(s'~|~s, a)~|~s_{t + 1})$ <br>\n",
    "$\\quad$ t += 1 <br>\n",
    "<br>\n",
    "\n",
    "_Algorithm 1. Thompson Sampling for MDPs._"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62bc8c9e",
   "metadata": {},
   "source": [
    "# 4. Generalization and Exploration"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11913c8a",
   "metadata": {},
   "source": [
    "How do we do everything we just did for large state and action spaces? In large, how do we generalize or scale up?\n",
    "\n",
    "With VFA (value function approximation) for model-free settings, we can add a reward bonus term for updating our weights. \n",
    "\n",
    "Some people in class suggested embeddings or some type of way to model how similar states or actions are (maybe clustering them or reducing this high dimensionality?)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f657f6b",
   "metadata": {},
   "source": [
    "# 5. 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
}