RL fundamentals.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Reinforcement Learning fundamentals\n",
    "\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc-sa/4.0/\"><img alt=\"Creative Commons License\" align=\"left\" src=\"https://i.creativecommons.org/l/by-nc-sa/4.0/80x15.png\" /></a>&nbsp;| Emmanuel Rachelson | <a href=\"#\">#</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Foreword <a class=\"tocSkip\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "How this course works (pedagogically):\n",
    "- one notebook to rule them all (them = the concepts)\n",
    "- no slides\n",
    "- short exercices along the way\n",
    "- a bit of live coding\n",
    "- two class breaks for you to breathe\n",
    "    \n",
    "What you should expect:\n",
    "- some plain words notions,\n",
    "- but avoidance of over-simplification,\n",
    "- and also a fair amount of (hopefully painless) rigorous notations and abstract concepts.\n",
    "- Also most things will be fully written down to increase your autonomy in replaying the notebook.\n",
    "\n",
    "Color code:\n",
    "<div class=\"alert alert-success\">Key results in green boxes</div>\n",
    "<div class=\"alert alert-warning\">Exercices in yellow boxes</div>\n",
    "<div class=\"alert alert-danger\">Solutions in red boxes</div>\n",
    "\n",
    "And a first yellow box:\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "\n",
    "**Prerequisites:**\n",
    "- Basic algebra.\n",
    "- Random variables, probability distributions.\n",
    "    \n",
    "**Useful but not compulsory:**\n",
    "- Random processes, Markov chains.\n",
    "- Notion of contraction mapping.\n",
    "<div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "toc": true
   },
   "source": [
    "<h1><span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Class-goals\" data-toc-modified-id=\"Class-goals-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Class goals</a></span></li><li><span><a href=\"#Ruining-the-suspense-with-a-general-abstract-definition-(5-minutes)\" data-toc-modified-id=\"Ruining-the-suspense-with-a-general-abstract-definition-(5-minutes)-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Ruining the suspense with a general abstract definition (5 minutes)</a></span></li><li><span><a href=\"#RL-within-Machine-Learning-(5-minutes)\" data-toc-modified-id=\"RL-within-Machine-Learning-(5-minutes)-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>RL within Machine Learning (5 minutes)</a></span></li><li><span><a href=\"#From-plain-words-to-first-variables-(5-minutes)\" data-toc-modified-id=\"From-plain-words-to-first-variables-(5-minutes)-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>From plain words to first variables (5 minutes)</a></span></li><li><span><a href=\"#Modeling-sequential-decision-problems-with-Markov-Decision-Processes-(30-minutes)\" data-toc-modified-id=\"Modeling-sequential-decision-problems-with-Markov-Decision-Processes-(30-minutes)-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Modeling sequential decision problems with Markov Decision Processes (30 minutes)</a></span><ul class=\"toc-item\"><li><span><a href=\"#Definition\" data-toc-modified-id=\"Definition-5.1\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span>Definition</a></span></li><li><span><a href=\"#Value-of-a-trajectory-/-of-a-policy\" data-toc-modified-id=\"Value-of-a-trajectory-/-of-a-policy-5.2\"><span class=\"toc-item-num\">5.2&nbsp;&nbsp;</span>Value of a trajectory / of a policy</a></span></li><li><span><a href=\"#Optimal-policies\" data-toc-modified-id=\"Optimal-policies-5.3\"><span class=\"toc-item-num\">5.3&nbsp;&nbsp;</span>Optimal policies</a></span></li><li><span><a href=\"#Summary\" data-toc-modified-id=\"Summary-5.4\"><span class=\"toc-item-num\">5.4&nbsp;&nbsp;</span>Summary</a></span></li></ul></li><li><span><a href=\"#Characterizing-value-functions:-the-Bellman-equations-(40-minutes)\" data-toc-modified-id=\"Characterizing-value-functions:-the-Bellman-equations-(40-minutes)-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>Characterizing value functions: the Bellman equations (40 minutes)</a></span><ul class=\"toc-item\"><li><span><a href=\"#Intuitions\" data-toc-modified-id=\"Intuitions-6.1\"><span class=\"toc-item-num\">6.1&nbsp;&nbsp;</span>Intuitions</a></span></li><li><span><a href=\"#The-evaluation-equation\" data-toc-modified-id=\"The-evaluation-equation-6.2\"><span class=\"toc-item-num\">6.2&nbsp;&nbsp;</span>The evaluation equation</a></span></li><li><span><a href=\"#The-optimality-equation\" data-toc-modified-id=\"The-optimality-equation-6.3\"><span class=\"toc-item-num\">6.3&nbsp;&nbsp;</span>The optimality equation</a></span></li><li><span><a href=\"#Dynamic-Programming-for-the-optimality-equation\" data-toc-modified-id=\"Dynamic-Programming-for-the-optimality-equation-6.4\"><span class=\"toc-item-num\">6.4&nbsp;&nbsp;</span>Dynamic Programming for the optimality equation</a></span></li><li><span><a href=\"#Approximate-Dynamic-Programming\" data-toc-modified-id=\"Approximate-Dynamic-Programming-6.5\"><span class=\"toc-item-num\">6.5&nbsp;&nbsp;</span>Approximate Dynamic Programming</a></span></li><li><span><a href=\"#Summary\" data-toc-modified-id=\"Summary-6.6\"><span class=\"toc-item-num\">6.6&nbsp;&nbsp;</span>Summary</a></span></li></ul></li><li><span><a href=\"#Learning-optimal-value-functions-(40-minutes)\" data-toc-modified-id=\"Learning-optimal-value-functions-(40-minutes)-7\"><span class=\"toc-item-num\">7&nbsp;&nbsp;</span>Learning optimal value functions (40 minutes)</a></span><ul class=\"toc-item\"><li><span><a href=\"#Policy-evaluation-as-Stochastic-Approximation:-Temporal-Differences\" data-toc-modified-id=\"Policy-evaluation-as-Stochastic-Approximation:-Temporal-Differences-7.1\"><span class=\"toc-item-num\">7.1&nbsp;&nbsp;</span>Policy evaluation as Stochastic Approximation: Temporal Differences</a></span></li><li><span><a href=\"#Approximate-Value-Iteration-as-Stochastic-Approximation:-Q-learning\" data-toc-modified-id=\"Approximate-Value-Iteration-as-Stochastic-Approximation:-Q-learning-7.2\"><span class=\"toc-item-num\">7.2&nbsp;&nbsp;</span>Approximate Value Iteration as Stochastic Approximation: Q-learning</a></span></li><li><span><a href=\"#Summary\" data-toc-modified-id=\"Summary-7.3\"><span class=\"toc-item-num\">7.3&nbsp;&nbsp;</span>Summary</a></span></li></ul></li><li><span><a href=\"#Challenges-in-RL-and-RLVS-classes-(10-minutes)\" data-toc-modified-id=\"Challenges-in-RL-and-RLVS-classes-(10-minutes)-8\"><span class=\"toc-item-num\">8&nbsp;&nbsp;</span>Challenges in RL and RLVS classes (10 minutes)</a></span><ul class=\"toc-item\"><li><span><a href=\"#General-summary\" data-toc-modified-id=\"General-summary-8.1\"><span class=\"toc-item-num\">8.1&nbsp;&nbsp;</span>General summary</a></span></li><li><span><a href=\"#Three-intrinsic-challenges-in-Reinforcement-Learning\" data-toc-modified-id=\"Three-intrinsic-challenges-in-Reinforcement-Learning-8.2\"><span class=\"toc-item-num\">8.2&nbsp;&nbsp;</span>Three intrinsic challenges in Reinforcement Learning</a></span></li><li><span><a href=\"#Specific-questions-and-challenges-in-RL\" data-toc-modified-id=\"Specific-questions-and-challenges-in-RL-8.3\"><span class=\"toc-item-num\">8.3&nbsp;&nbsp;</span>Specific questions and challenges in RL</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Class goals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- acquire the fundamental building blocks of RL:\n",
    "    - plain word notions\n",
    "    - MDPs, policies, optimality equations, etc.\n",
    "    - common notations\n",
    "    - key algorithms\n",
    "    - common misconceptions\n",
    "- key challenges in RL and their connection to RLVS lectures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Ruining the suspense with a general abstract definition (5 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "What is Reinforcement Learning about?\n",
    "\n",
    "It is about learning to control dynamic systems.\n",
    "<img src=\"img/dynamic.png\" style=\"width: 400px;\"></img>\n",
    "Dynamic systems? **dynamic** evolution of $s$ and $o$ under $\\pi$ over a certain time horizon.\n",
    "\n",
    "Our object of study:<br>\n",
    "We want to find a control policy $\\pi$ (with $u = \\pi(o)$) such that the system $\\Sigma$ behaves as we desire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Examples of RL problems <a class=\"tocSkip\">\n",
    "\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "  <td><img src=\"img/spiral.jpg\" style=\"width: 200px;\"></td>\n",
    "  <td style=\"border-right:1px solid;\">Exiting a spiral</td>\n",
    "  <td><img src=\"img/tests.jpg\" style=\"width: 200px;\"></td>\n",
    "  <td>Dynamic treatment regimes for HIV patients</td>\n",
    "</tr>\n",
    "<tr>\n",
    "  <td><img src=\"img/pend.png\" style=\"width: 200px;\"></td>\n",
    "  <td style=\"border-right:1px solid;\">Cart-pole balancing</td>\n",
    "  <td><img src=\"img/waiting.jpg\" style=\"width: 200px;\"></td>\n",
    "  <td>Queueing problems</td>\n",
    "</tr>\n",
    "<tr>\n",
    "  <td><img src=\"img/market.jpg\" style=\"width: 200px;\"></td>\n",
    "  <td style=\"border-right:1px solid;\">Portfolio management</td>\n",
    "  <td><img src=\"img/dam.jpg\" style=\"width: 200px;\"></td>\n",
    "  <td>Hydroelectric production</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "But also:\n",
    "- Elevator scheduling\n",
    "- Bicyle riding\n",
    "- Ship steering\n",
    "- Bioreactor control\n",
    "- Aerobatics helicopter control\n",
    "- Airport departures scheduling\n",
    "- Ecosystem regulation and preservation\n",
    "- Robocup soccer\n",
    "- Video game playing (Atari, Starcraft...)\n",
    "- Game of Go\n",
    "- ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "So, learning to play a board game, learning to juggle, learning to take good strategic decisions, learning to drive... all fall into the same category of **control problems** and Reinforcement Learning studies the process of **elaborating a good control strategy through interaction samples**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "Reinforcement Learning is about learning an optimal sequential behavior in a given environment.\n",
    "</div>\n",
    "\n",
    "Let's break this down.\n",
    "- sequential behavior in a given environment  \n",
    "$\\rightarrow$ discrete time steps, sequence of actions\n",
    "- optimal  \n",
    "$\\rightarrow$ a reward signal informs us of the quality of the last action\n",
    "- learning  \n",
    "$\\rightarrow$ no known model, just interaction samples, behavior adaptation.\n",
    "\n",
    "<center><img src=\"img/dynamic.png\" style=\"width: 400px;\"></img></center>\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "**Keywords:**\n",
    "- system to control / environment\n",
    "- control policy\n",
    "- optimality\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Warm-up poll:** \n",
    "How do you do today?  \n",
    "[https://linkto.run/p/BOOR15YA](https://linkto.run/p/BOOR15YA)\n",
    "- Great, I'm learning RL!\n",
    "- Great, but I'm scared the RL unicorn will turn into a difficult to tame rhino.\n",
    "- Great, bring the math on (as long as you do it step by step).\n",
    "- Why do you ask the question if the only answer is \"Great\"?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "**Standing on the shoulders of giants**\n",
    "\n",
    "> The idea that we learn by interacting with our environment is probably the first to occur to us when we think about the nature of learning. When an infant plays, waves its arms, or looks about, it has no explicit teacher, but it does have a direct sensorimotor connection to its environment. Exercising this connection produces a wealth of information about cause and effect, about the consequences of actions, and about what to do in order to achieve goals. Throughout our lives, such interactions are undoubtedly a major source of knowledge about our environment and ourselves. Whether we are learning to drive a car or to hold a conversation, we are acutely aware of how our environment responds to what we do, and we seek to influence what happens through our behavior. Learning from interaction is a foundational idea underlying nearly all theories of learning and intelligence. (Sutton & Barto, 2018, [Reinforcement Learning: an Introduction](http://incompleteideas.net/book/the-book-2nd.html))\n",
    "\n",
    "Caveat: this is a definition of *learning*, not specifically of *reinforcement learning* (although it applies to RL), so it is worth giving some context."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## RL within Machine Learning (5 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "You may have had classes on Machine Learning before. There are three strongly distinct categories of problems in ML:\n",
    "- Supervised Learning\n",
    "- Unsupervised Learning\n",
    "- Reinforcement Learning\n",
    "\n",
    "Let's try to answer the following questions for each category.\n",
    "- What's the abstract problem we are trying to solve?\n",
    "- What's the data provided to the algorithms?\n",
    "- Give examples of algorithms in SL/UL/RL.  \n",
    "\n",
    "<center>\n",
    "<table border=\"1\">\n",
    "<tr>\n",
    "    <td> <b>Question</b> </td>\n",
    "    <td style=\"border-left: 1px solid black\"> <b>Supervised</b> </td>\n",
    "    <td style=\"border-left: 1px solid black\"> <b>Unsupervised</b> </td>\n",
    "    <td style=\"border-left: 1px solid black\"> <b>Reinforcement</b> </td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td> Target </td>\n",
    "    <td style=\"border-left: 1px solid black\"> $f(x)=y$ </td>\n",
    "    <td style=\"border-left: 1px solid black\"> $x\\in X$ </td>\n",
    "    <td style=\"border-left: 1px solid black\"> $\\pi(s)=a$ </td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td> Target (rephrased) </td>\n",
    "    <td style=\"border-left: 1px solid black\"> Predict outputs given inputs</td>\n",
    "    <td style=\"border-left: 1px solid black\"> Discover structure in data </td>\n",
    "    <td style=\"border-left: 1px solid black\"> Find an optimal behavior </td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td> Data </td>\n",
    "    <td style=\"border-left: 1px solid black\"> $\\left\\{\\left(x,y\\right)\\right\\}$ supervisor's labels </td>\n",
    "    <td style=\"border-left: 1px solid black\"> $\\left\\{x\\right\\}$ unlabelled data </td>\n",
    "    <td style=\"border-left: 1px solid black\"> $\\left\\{\\left(s,a,r,s'\\right)\\right\\}$ experience samples </td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td> Output </td>\n",
    "    <td style=\"border-left: 1px solid black\"> Classifier or regressor</td>\n",
    "    <td style=\"border-left: 1px solid black\"> Clusters or dimension reduction </td>\n",
    "    <td style=\"border-left: 1px solid black\"> Policies, value functions </td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td> Key algorithms </td>\n",
    "    <td style=\"border-left: 1px solid black\"> Neural networks, SVMs, etc.</td>\n",
    "    <td style=\"border-left: 1px solid black\"> k-means, PCA, etc. </td>\n",
    "    <td style=\"border-left: 1px solid black\"> Q-learning, Policy Gradients, etc. </td>\n",
    "</tr>\n",
    "</table>\n",
    "</center>\n",
    "\n",
    "This table helps distinguish the different natures of the problems tackled. The RL problem is about finding the optimal policy for a given environment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "How is this different from Supervised Learning?\n",
    "- no correct $(s,a)$ example, rather $(s,a,r,s')$ samples\n",
    "- Delayed rewards, credit assignment, trajectories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Poll:** Pick the true statement(s).  \n",
    "[https://linkto.run/p/3OG3IJO3](https://linkto.run/p/3OG3IJO3)\n",
    "- Sorting new emails as spam (or not) given a million labelled emails is a reinforcement learning task.\n",
    "- Deciding what move to play at chess, based on thousands of previous games is a reinforcement learning task.\n",
    "- Incrementally improving the accuracy of a radar detection software from online collected data is a reinforcement learning task.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Inspirations for RL:\n",
    "- Control theory and Stochastic processes for the **modeling** part\n",
    "- Statistics, Optimization and Cognitive Psychology for the **learning** part"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## From plain words to first variables (5 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### A medical prescription example <a class=\"tocSkip\">\n",
    "\n",
    "<img src=\"img/patient-doctor.png\" style=\"height: 200px;\">\n",
    "    \n",
    "A patient walks into a clinic with her medical file (medical history, x-rays, blood work, etc.). You, as her doctor, need to write a prescription. Let us use this example to formalize the process of deciding what to write on the prescription."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Patient variables <a class=\"tocSkip\">\n",
    "\n",
    "<center>\n",
    "<img src=\"img/patient_file.png\" style=\"height: 100px;\"> </img> <br>\n",
    "Patient state now: $S_0$  <br>\n",
    "Future states: $S_t$\n",
    "</center>\n",
    "\n",
    "The medical file of the patient allows us to define a number of variables that characterize the patient now. We will write $S_0$ the vector of these variables. Future measurements will be noted $S_t$.\n",
    "\n",
    "$S_t$ is a random vector, taking different values in a *patient description space* $S$ at different time steps."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Prescription <a class=\"tocSkip\">\n",
    "\n",
    "<center>\n",
    "<img src=\"img/prescription.png\" style=\"height: 100px;\"> </img> <br>\n",
    "Prescription: $\\left( A_t \\right)_{t\\in\\mathbb{N}} = (A_0, A_1, A_2, ...)$\n",
    "</center>\n",
    "\n",
    "The prescription is a series of recommendations we give to the patient over the course of treatment. It is thus a sequence $\\left( A_t \\right)_{t\\in\\mathbb{N}} = (A_0, A_1, A_2, ...)$ of variables $A_t$.\n",
    "\n",
    "These treatments $A_t$ are random variables too, taking their value in some space $A$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Patient evolution <a class=\"tocSkip\">\n",
    "\n",
    "\n",
    "<center>\n",
    "<img src=\"img/patient_evolution.png\" style=\"height: 100px;\"> </img> <br>\n",
    "    $\\mathbb{P}(S_t)$?\n",
    "</center>\n",
    "\n",
    "The patient evolves over time steps. Her evolution follows a certain probability distribution $\\mathbb{P}(S_t)$ over descriptive states.\n",
    "\n",
    "So $\\left( S_t \\right)_{t\\in\\mathbb{N}}$ defines a *random process* that describes the patient's evolution under the influence of past $S_t$ and $A_t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Physician's goal <a class=\"tocSkip\">\n",
    "\n",
    "<img src=\"img/patient_happy.png\" style=\"height: 100px;\"> </img> <br>\n",
    "\n",
    "$$J \\left( \\left(S_t\\right)_{t\\in \\mathbb{N}}, \\left( A_t \\right)_{t\\in \\mathbb{N}} \\right)?$$\n",
    "\n",
    "The physician's goal is to bring the patient from an unhealthy state $S_0$ to a healthy situation.  \n",
    "\n",
    "This goal is not only defined by a final state of the patient but by the full trajectory followed by the variables $S_t$ and $A_t$. For example, prescribing a drug that damages the patient's liver, or letting the patient experience too much pain over the course of treatment is discouraged.\n",
    "\n",
    "We define a criterion $J \\left( \\left(S_t\\right)_{t\\in \\mathbb{N}}, \\left( A_t \\right)_{t\\in \\mathbb{N}} \\right)$ that allows to quantify how good a trajectory in the joint $S\\times A$ space is."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Wrap-up <a class=\"tocSkip\">\n",
    "\n",
    "- Patient state $S_t$  (random variable)\n",
    "- Physician instruction $A_t$ (random variable)\n",
    "- Prescription $\\left( A_t \\right)_{t\\in\\mathbb{N}}$   \n",
    "- Patient's evolution $\\mathbb{P}(S_t)$  \n",
    "- Patient's trajectory $\\left( S_t \\right)_{t\\in\\mathbb{N}}$ random process\n",
    "- Value of a trajectory $J \\left( \\left(S_t\\right)_{t\\in \\mathbb{N}}, \\left( A_t \\right)_{t\\in \\mathbb{N}} \\right)$  \n",
    "\n",
    "It seems reasonable that the physician's recommendation $\\mathbb{P}(A_t)$ at step $t$ be dependent on previously observed states $\\left(S_0, \\ldots, S_t\\right)$ and recommended treatments $\\left(A_0, \\ldots, A_{t-1}\\right)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Common misconception <a class=\"tocSkip\">\n",
    "\n",
    "You will often see the following type of drawing, along with a sentence like \"RL is concerned with the problem on an agent performing actions to control an environment\". \n",
    "\n",
    "<img src=\"img/misconception.png\" style=\"height: 300px;\"></img>\n",
    "\n",
    "Although this sentence is not false *per se*, it conveys an important misconception that may be grounded in too simple anthropomorphic analogies. One often talks about the *state of the agent* or the *state of the environment*. The distinction here is confusing at best: there is no separation between agent and environment. A better vocabulary is to talk about a *system to control*, that is described through its observed *state*. This system is controlled by the application of actions issued from a *policy* or *control law*. The process of *learning* this policy is what RL is concerned with.\n",
    "\n",
    "Although less shiny, the drawing below may be less misleading.\n",
    "\n",
    "<img src=\"img/dynamic.png\" style=\"height: 300px;\"></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Three key notions <a class=\"tocSkip\">\n",
    "\n",
    "Understanding RL is a three-stage rocket, answering the questions:  \n",
    "1. What is the system to control?  \n",
    "2. What is an optimal strategy?  \n",
    "3. How do we learn such a strategy?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Exercise (no poll, 1 minute):**  \n",
    "Suppose that, instead of treating a patient, we want to learn to swing the pole up in the cart-pole example.  \n",
    "What are the state description variables?  \n",
    "What are the action variables?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<img src=\"img/pend.png\" style=\"width: 300px;\">\n",
    "\n",
    "<div class=\"alert alert-danger\"><a href=\"#answers0\" data-toggle=\"collapse\"><b>Answers:</b></a><br>\n",
    "<div id=\"answers0\" class=\"collapse\">\n",
    "\n",
    "State: cart position and velocity $x, \\dot{x}$, pole angle and velocity $\\theta, \\dot{\\theta}$\n",
    "    \n",
    "Action: force $F$ applied on the cart.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Modeling sequential decision problems with Markov Decision Processes (30 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Definition\n",
    "\n",
    "Let's take a higher view and develop a general theory for describing problems such as writing a prescription for our patient.\n",
    "\n",
    "Let us assume we have:\n",
    "- a set of states $S$ describing the system to control,\n",
    "- a set of actions $A$ we can apply.\n",
    "\n",
    "Curing patients is a conceptually difficult task. \n",
    "To keep things grounded, we shall use a toy example called [FrozenLake](https://gym.openai.com/envs/FrozenLake-v0/) and work our way to more general concepts. It's also the occasion to familiarize with [OpenAI Gym](https://gym.openai.com/).\n",
    "\n",
    "<img src=\"img/frisbee.jpg\" style=\"height: 300px;\"></img>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import gym\n",
    "import gym.envs.toy_text.frozen_lake as fl\n",
    "\n",
    "env = gym.make('FrozenLake-v0')\n",
    "_=env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "The game's goal is to navigate across this lake, from position S to position G, in order to retrieve a frisbee, while avoiding falling into the holes H. Frozen positions are slippery so you don't always move in the intended direction. Reaching the goal provides a reward of 1, and zero otherwise. Falling into a hole or reaching the goal ends an episode.\n",
    "\n",
    "Take a look at the funny description in `help(fl.FrozenLakeEnv)` if you are curious."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Poll:**  \n",
    "[https://linkto.run/p/65E9EO4Q](https://linkto.run/p/65E9EO4Q)  \n",
    "How many states are there in this game?  \n",
    "How many actions?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#answers1\" data-toggle=\"collapse\"><b>Answers:</b></a><br>\n",
    "<div id=\"answers1\" class=\"collapse\">\n",
    "States set: the 16 positions on the map.<br>\n",
    "Actions set: the 4 actions $\\{$N,S,E,W$\\}$\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Let's confirm that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "print(env.observation_space)\n",
    "print(env.action_space)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "At every time step, the system state is $S_t$ and we decide to apply action $A_t$. This results in observing a new state $S_{t+1}$ and receiving a scalar reward signal $R_t$ for this transition.\n",
    "\n",
    "$R_t$ tells us how happy we are with the last transition.\n",
    "\n",
    "For example, in FrozenLake, all transitions have reward 0 except for the one that reaches the goal, which yields reward 1. Let's verify this and introduce a few utility functions on the way.\n",
    "\n",
    "Note that $S_t$, $A_t$, $S_{t+1}$ and $R_t$ are random variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "actions = {fl.LEFT: '\\u2190', fl.DOWN: '\\u2193', fl.RIGHT: '\\u2192', fl.UP: '\\u2191'}\n",
    "\n",
    "def to_s(row,col):\n",
    "    return row*env.unwrapped.ncol+col\n",
    "\n",
    "def to_row_col(s):\n",
    "    col = s%env.unwrapped.ncol\n",
    "    row = int((s-col)/env.unwrapped.ncol)\n",
    "    return row,col\n",
    "\n",
    "print(actions)\n",
    "row=3\n",
    "col=2\n",
    "a=2\n",
    "print(\"Apply \", actions[2], \" from (\", row, \", \", col, \"):\", sep='')\n",
    "for tr in env.unwrapped.P[to_s(row,col)][a]:\n",
    "    print(\"  Reach (\", to_row_col(tr[1]), \") and get reward \", tr[2], \" with proba \", tr[0], \".\", sep='')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We will now make our main assumption about the systems we want to control.\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "**Fundamental assumption (Markov property)**\n",
    "$$\\mathbb{P}(S_{t+1},R_t|S_t, A_t, S_{t-1}, A_{t-1}, \\ldots, S_0, A_0) = \\mathbb{P}(S_{t+1},R_t|S_t, A_t)$$\n",
    "</div>\n",
    "    \n",
    "Such a system will be called a Markov Decision Process (MDP).\n",
    "\n",
    "One generally separates the state dynamics and the rewards by:\n",
    "$$\\mathbb{P}(S_{t+1},R_t|S_t, A_t) = \\mathbb{P}(S_{t+1}|S_t, A_t)\\cdot \\mathbb{P}(R_t|S_t, A_t, S_{t+1})$$\n",
    "\n",
    "Which leads in turn to the general definition of an MDP:\n",
    "<div class=\"alert alert-success\"><b>Markov Decision Process (MDP)</b><br>\n",
    "A Markov Decision Process is given by:\n",
    "<ul>\n",
    "<li> A set of states $S$\n",
    "<li> A set of actions $A$\n",
    "<li> A (Markovian) transition model $\\mathbb{P}\\left(S_{t+1} | S_t, A_t \\right)$, noted $p(s'|s,a)$\n",
    "<li> A reward model $\\mathbb{P}\\left( R_t | S_t, A_t, S_{t+1} \\right)$, noted $r(s,a)$ or $r(s,a,s')$\n",
    "<li> A set of discrete decision epochs $T=\\{0,1,\\ldots,H\\}$\n",
    "</ul>\n",
    "</div>\n",
    "\n",
    "Most of the results presented here can be found in M. L. Puterman's classic book, [Markov Decision Processes: Discrete Stochastic Dynamic Programming](https://www.wiley.com/en-us/Markov+Decision+Processes%3A+Discrete+Stochastic+Dynamic+Programming-p-9781118625873).\n",
    "\n",
    "If $H\\rightarrow\\infty$ we have an infinite horizon control problem.\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "Since we will only work with infinite horizon problems, we shall identify the MDP with the 4-tuple $\\langle S,A,p,r\\rangle$.\n",
    "</div>\n",
    "    \n",
    "So, in RL, we wish to control the trajectory of a system that, we suppose, behaves as a Markov Decision Process.\n",
    "\n",
    "<img src=\"img/dynamic.png\" style=\"height: 240px;\"></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Value of a trajectory / of a policy\n",
    "\n",
    "An oracle decides on how to choose actions at each time step:\n",
    "$$\\mathbb{P}(A_t)=\\pi_t.$$\n",
    "\n",
    "The collection of $\\pi_t$ is the oracle's **policy**.\n",
    "\n",
    "<img src=\"img/frisbee.jpg\" style=\"height: 100px;\"></img>\n",
    "\n",
    "One policy implies one specific distribution over trajectories over the frozen lake. More generally, the policy and $S_0$ condition the sequence $S_0, A_0, R_0, S_1, A_1, R_1, \\ldots$\n",
    "\n",
    "In FrozenLake as in the patient's example, some trajectories are better than others. We need a criterion to compare trajectories. Intuitively, this criterion should reflect the idea that a good policy accumulates as much reward as possible along a trajectory.\n",
    "\n",
    "Let's compare the policy that always moves to the right and the policy that always moves left by summing the rewards obtained along trajectories and then averaging these rewards across trajectories."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "nb_episodes = 50000\n",
    "horizon = 200\n",
    "\n",
    "Vright = np.zeros(nb_episodes)\n",
    "for i in range(nb_episodes):\n",
    "    env.reset()\n",
    "    for t in range(horizon):\n",
    "        next_state, r, done,_ = env.step(fl.RIGHT)\n",
    "        Vright[i] += r\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "Vleft  = np.zeros(nb_episodes)\n",
    "for i in range(nb_episodes):\n",
    "    env.reset()\n",
    "    for t in range(horizon):\n",
    "        next_state, r, done,_ = env.step(fl.LEFT)\n",
    "        Vleft[i] += r\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "print(\"est. value of 'right' policy:\", np.mean(Vright), \"variance:\", np.std(Vright))\n",
    "print(\"est. value of 'left'  policy:\", np.mean(Vleft),  \"variance:\", np.std(Vleft))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "In the general case, this sum of rewards on an infinite horizon might be unbounded. So let us introduce the **$\\gamma$-discounted sum of rewards** (from a starting state $s$, under policy $\\pi$) random variable:\n",
    "$$G^\\pi(s) = \\sum\\limits_{t = 0}^\\infty \\gamma^t R_t \\quad \\Bigg| \\quad \\begin{array}{l}S_0 = s,\\\\ A_t \\sim \\pi_t,\\\\ S_{t+1}\\sim p(\\cdot|S_t,A_t),\\\\R_t = r(S_t,A_t,S_{t+1}).\\end{array}$$\n",
    "\n",
    "$G^\\pi(s)$ represents what we can gain in the long-term by applying the actions from $\\pi$.\n",
    "\n",
    "Then, given a starting state $s$, we can define the value of $s$ under policy $\\pi$:\n",
    "$$V^\\pi(s) = \\mathbb{E} \\left[ G^\\pi(s) \\right]$$\n",
    "\n",
    "This defines the value function $V^\\pi$ of policy $\\pi$:\n",
    "<div class=\"alert alert-success\"><b>Value function $V^\\pi$ of a policy $\\pi$ under a $\\gamma$-discounted criterion</b><br>\n",
    "$$V^\\pi : \\left\\{\\begin{array}{ccl}\n",
    "S & \\rightarrow & \\mathbb{R}\\\\\n",
    "s & \\mapsto & V^\\pi(s)=\\mathbb{E}\\left( \\sum\\limits_{t = 0}^\\infty \\gamma^t R_t \\bigg| S_0 = s, \\pi \\right)\\end{array}\\right. $$\n",
    "</div>\n",
    "\n",
    "\n",
    "And, given a distribution $\\rho_0$ on starting states, we can map $\\pi$ to the scalar value:\n",
    "$$J(\\pi) = \\mathbb{E}_{s \\sim \\rho_0} \\left[ V^\\pi(s) \\right]$$\n",
    "\n",
    "Note that this definition is quite arbitrary: instead of the expected (discounted) sum of rewards, we could have taken the average reward over all time steps, or some other (more or less exotic) comparison criterion between policies.\n",
    "\n",
    "Most of the RL literature uses this discounted criterion (in some cases with $\\gamma=1$), some uses the average reward criterion, and few works venture into more exotic criteria. Today, we will limit ourselves to the discounted criterion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Optimal policies\n",
    "\n",
    "The fog clears up a bit: we can now compare policies given an initial state (or initial state distribution).  \n",
    "\n",
    "Thus, an **optimal** policy is one that is better than any other.\n",
    "\n",
    "<div class=\"alert alert-success\"><b>Optimal policy $\\pi^*$</b><br>\n",
    "$\\pi^*$ is said to be optimal iff $\\pi^* \\in \\arg\\max\\limits_{\\pi} V^\\pi$.<br>\n",
    "<br>\n",
    "    \n",
    "A policy is optimal if it **dominates** over any other policy in every state:\n",
    "$$\\pi^* \\textrm{ is optimal}\\Leftrightarrow \\forall s\\in S, \\ \\forall \\pi, \\ V^{\\pi^*}(s) \\geq V^\\pi(s)$$\n",
    "</div>\n",
    "\n",
    "Note that although there may be several optimal policies, they all share the same value function $V^* = V^{\\pi^*}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We now get to our first fundamental result. Fortunately for us...  \n",
    "\n",
    "<div class=\"alert alert-success\"><b>Optimal policy theorem</b><br>\n",
    "For $\\left\\{\\begin{array}{l}\n",
    "\\gamma\\textrm{-discounted criterion}\\\\\n",
    "\\textrm{infinite horizon}\n",
    "\\end{array}\\right.$, \n",
    "there always exists at least one optimal stationary, deterministic, Markovian policy.\n",
    "</div>\n",
    "\n",
    "Let's explain a little:\n",
    "- Markovian : $\\left\\{\\begin{array}{l}\n",
    "\\forall \\left(s_i,a_i\\right)\\in \\left(S\\times A\\right)^{t-1}\\\\\n",
    "\\forall \\left(s'_i,a'_i\\right)\\in \\left(S\\times A\\right)^{t-1}\n",
    "\\end{array}\\right., \\pi\\left(A_t|S_0, A_0, \\ldots, S_t\\right) = \\pi\\left(A_t|S'_0, A'_0, \\ldots, S_t\\right)$.  \n",
    "One writes $\\pi(A_t|S_t)$.\n",
    "- Stationary : $\\forall (t,t')\\in \\mathbb{N}^2, \\pi(A_t|S_t=s) = \\pi(A_{t'}|S_{t'}=s)$.\n",
    "- Deterministic : $\\pi(A_t|history) = \\left\\{\\begin{array}{l}\n",
    "1\\textrm{ for a single }a\\\\\n",
    "0\\textrm{ otherwise}\n",
    "\\end{array}\\right.$.\n",
    "\n",
    "So in simpler words, we know that among all possible optimal ways of picking $A_t$, at least one is a function $\\pi:S\\rightarrow A$.\n",
    "\n",
    "That helps a lot: we don't have to search for optimal policies in a complex family of history-dependent, stochastic, non-stationary policies; instead we can simply search for a function $\\pi(s)=a$ that maps states to actions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Summary\n",
    "\n",
    "Let's wrap this whole section up. Our goal was to formally define the search for the best strategy for our game of FrozenLake and the medical prescription problem. This has led us to formalizing the general **discrete-time stochastic optimal control problem**:\n",
    "- Environment (discrete time, non-deterministic, non-linear, Markov) $\\leftrightarrow$ MDP.\n",
    "- Behaviour $\\leftrightarrow$ control policy $\\pi : s\\mapsto a$.\n",
    "- Policy evaluation criterion $\\leftrightarrow$ $\\gamma$-discounted criterion.\n",
    "- Goal $\\leftrightarrow$ Maximize value function $V^\\pi(s)$.\n",
    "\n",
    "So we have built the first stage of our three-stage rocket:  \n",
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "**What is the system to control?**  \n",
    "The system to control is a Markov Decision Process $\\langle S, A, p, r \\rangle$ and we will control it with a policy $\\pi:s\\mapsto a$ in order to optimize $\\mathbb{E} \\left( \\sum_t \\gamma^t R_t\\right)$\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "\n",
    "**Poll** The limits of MDP modeling  \n",
    "[https://linkto.run/p/0WG7WNER](https://linkto.run/p/0WG7WNER)  \n",
    "Can these systems be modeled as MDPs?   \n",
    "- Playing a tennis video game based on a single video frame\n",
    "- Playing a tennis video game based on a full physical description of the ball and the players\n",
    "- The game of Poker\n",
    "- The collaborative game of [Hanabi](https://en.wikipedia.org/wiki/Hanabi_(card_game))\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#answersMDPlimits\" data-toggle=\"collapse\"><b>Answers:</b></a><br>\n",
    "<div id=\"answersMDPlimits\" class=\"collapse\">\n",
    "\n",
    "A single video frame does not contain enough information to accurately represent the current state of the game. The velocities are absent for instance. Hence the dynamics might not be Markovian.\n",
    "    \n",
    "A full physical description, however, may contain enough information so that $\\mathbb{P}(S_{t+1})$ is only conditioned by $S_t$ and $A_t$.\n",
    "    \n",
    "Poker is a two-player, adversarial, stochastic game. MDPs only model one-player games.\n",
    "\n",
    "Beyond the fact that it is a multi-player game. Hanabi is a game based mainly on epistemic reasoning. That is, reasoning on beliefs about the state of the world (specifically, the state of the other players' hand). This type of state description is difficult to encode within a Markovian dynamics model.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Let's take a short break.**  \n",
    "**If there is time, I can take questions.**\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Characterizing value functions: the Bellman equations (40 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Intuitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Consider the maze below, where an agent can move North, South, East or West. The resulting transition is deterministic and a reward of $+1$ is gained when exiting the maze (which terminates the game). Otherwise all rewards are zero. Bumping into a wall terminates the game with a reward of zero.\n",
    "\n",
    "<img src=\"img/grid_raw.png\" width=\"200px\"></img>\n",
    "\n",
    "Let's consider the policy $\\pi$ that always moves East.\n",
    "\n",
    "<img src=\"img/grid_policy.png\" width=\"200px\"></img>\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Poll**  \n",
    "[https://linkto.run/p/NO9LB7NP](https://linkto.run/p/NO9LB7NP)  \n",
    "Without writing any equation, what is the value of the top-right cell under this policy?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim1\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim1\" class=\"collapse\">\n",
    "$V^\\pi((3,3)) = 1$\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Now let's take $\\gamma=0.9$.\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Poll**  \n",
    "[https://linkto.run/p/03LL2V5H](https://linkto.run/p/03LL2V5H)  \n",
    "Without writing any equation, what is the value of the top-middle cell under this policy? What is the value of the bottom-right cell?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim2\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim2\" class=\"collapse\">\n",
    "\n",
    "The value of $(2,3)$ is the expected discounted sum of what one gets from applying $\\pi$ from $(2,3)$. Since the $\\pi$ is deterministic and the transitions are deterministic too, $\\pi(2,3)$ always take us to state $(3,3)$. So $V^\\pi((2,3)) = 0 + \\gamma \\times V^\\pi((3,3)) = 0.9$.\n",
    "    \n",
    "The value of $(3,1)$ is the expected infinite sum of discounted rewards from $(3,1)$. Since the agent keeps bumping into the wall when applying $\\pi$, it never exits the maze and this is an infinite sum of zero terms. Hence $V^\\pi((2,3)) = 0$.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Let's draw the value function.\n",
    "\n",
    "<img src=\"img/grid_vpi.png\" width=\"200px\"></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Suppose you are currently in cell $(1,2)$ and would like to choose what action to take. Suppose also that you know the value function above. You need to put a scalar value on all four actions. To evaluate each action, let's estimate what we can get by applying the action and then using $\\gamma \\times V^\\pi(s)$ to estimate what can obtain in the long run after this first action. Define $Q^\\pi((x,y),a)$ as the utility we estimate for each action $a$ in $(x,y)$.\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Question / Poll**  \n",
    "What is $Q^\\pi((1,2),a)$ for action $a$ in $\\{N,S,E,W\\}$? What seems to be the most interesting first action to take, if we follow $\\pi$ after?  \n",
    "[https://linkto.run/p/5WV5GU62](https://linkto.run/p/5WV5GU62)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim3\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim3\" class=\"collapse\">\n",
    "\n",
    "$Q^\\pi((1,2),N) = 0 + \\gamma \\cdot \\gamma^2 = 0.729$  \n",
    "$Q^\\pi((1,2),S) = 0 + \\gamma \\cdot 0 = 0$  \n",
    "$Q^\\pi((1,2),E) = 0 + \\gamma \\cdot 0 = 0$  \n",
    "$Q^\\pi((1,2),W) = 0$  \n",
    "The best action seems to be $N$.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "An optimal policy is quite easy to guess. Let's draw the optimal value function (the value function of any optimal policy).\n",
    "\n",
    "<img src=\"img/grid_vopt.png\" width=\"200px\"></img>\n",
    "\n",
    "Define $Q^*((x,y),a)$ as the utility we estimate for each action $a$ in $(x,y)$ if it is followed by an optimal policy.\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Question**   \n",
    "What is $Q^*((1,2),a)$ for action $a$ in $\\{N,S,E,W\\}$? What seems to be the most interesting first action to take, if we act optimally after? Rank the actions by utility.  \n",
    "https://linkto.run/p/3OG6IJO3\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim4\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim4\" class=\"collapse\">\n",
    "\n",
    "$Q^*$ is what we gain immediately, plus $\\gamma$ times what we expect to receive from applying an optimal policy in the state we reach by applying $a$.  \n",
    "$Q^*((1,2),N) = 0 + \\gamma\\times\\gamma^2=\\gamma^3$  \n",
    "$Q^*((1,2),S) = 0 + \\gamma\\times\\gamma^4=\\gamma^5$  \n",
    "$Q^*((1,2),E) = 0 + \\gamma\\times\\gamma^4=\\gamma^5$  \n",
    "$Q^*((1,2),W) = 0 + \\gamma\\times\\gamma^3=\\gamma^4$  \n",
    "The best action seems to be $N$, followed by $W$, after that $S$ and $E$ are tied.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\"><b>Question (no poll)</b><br>\n",
    "What property has the policy that always picks greedily the $Q^*$ maximizing action in each state?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim5\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim5\" class=\"collapse\">\n",
    "\n",
    "It is an optimal policy.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Now suppose $(1,2)$ is a special slippery cell. Going North has a $0.7$ probability of actually reaching $(1,3)$, but also a $0.2$ probability of staying in $(1,2)$ and a $0.1$ probability of ending in $(2,2)$. Note that this changes the problem and the optimal expected return function $V^*$.\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Question (no poll)</b><br>\n",
    "Given this new problem, can you write $Q^*((1,2),N)$ as a function of $V^*(1,3)$, $V^*(1,2)$ and $V^*(2,2)$?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim6\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim6\" class=\"collapse\">\n",
    "\n",
    "When we take action $N$ in $(1,2)$, there are 3 possible outcomes:\n",
    "- with probability $0.7$, reach $(1,3)$ and get reward $0$,\n",
    "- with probability $0.2$, reach $(1,2)$ and get reward $0$,\n",
    "- with probability $0.1$, reach $(2,2)$ and get reward $0$.\n",
    "\n",
    "So what we can expect to get from applying $N$ in $(1,2)$ is:  \n",
    "\\begin{align*}\n",
    "    Q^*((1,2), N) &= 0.7 \\times (0+\\gamma V^*(1,3)) + 0.2\\times(0+\\gamma V^*(1,2)) + 0.1\\times(0+\\gamma V^*(2,2))\\\\\n",
    "    &= \\gamma \\left(0.7\\times V^*(1,3) + 0.2\\times V^*(1,2)+ 0.1\\times V^*(2,2)\\right)\n",
    "\\end{align*}\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Now you can remark that if we knew the action $\\pi^*((1,2))$ taken by an optimal policy in $(1,2)$, then $Q^*((1,2), \\pi^*(1,2))$ would actually be precisely the optimal long-term return $V^*$ (since it would be the expected return of a policy that acts optimally at every time step, including the first one).\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Question</b><br>\n",
    "Suppose an oracle tells us that $\\pi^*((1,2))=N$. Using the previous exercice, write $V^*(1,2)$ as a function of $V^*(1,3)$, $V^*(1,2)$ and $V^*(2,2)$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#prelim7\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"prelim7\" class=\"collapse\">\n",
    "\n",
    "We have $V^*((1,2)) = Q^*((1,2),N)$, so\n",
    "$$V^*((1,2)) = \\gamma \\left(0.7\\times V^*(1,3) + 0.2\\times V^*(1,2)+ 0.1\\times V^*(2,2)\\right)$$\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We have introduced the key concepts upon which this secton is built: $V$ and $Q$ functions, and the relation between $V(s)$ and $V(s')$ when $s'$ can be reached from $s$ in one action. The next steps are now to write all this formally, prove strong properties and derive algorithms for computing value functions and policies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### The evaluation equation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Drawing inspiration from the exercises above, we can define the very important state-action value function $Q^\\pi$.\n",
    "<div class=\"alert alert-success\"><b>State-action value function</b><br>\n",
    "$$Q^\\pi(s,a) = \\mathbb{E}\\left( \\sum\\limits_{t=0}^\\infty \\gamma^t r\\left(S_t, A_t, S_{t+1}\\right) \\bigg| S_0 = s, A_0=a, \\pi \\right)$$\n",
    "</div>\n",
    "\n",
    "To be precise and reuse the full notations from the MDP definition:\n",
    "\\begin{align*}\n",
    "Q^\\pi(s,a) &=\\mathbb{E}\\left[ \\sum\\limits_{t = 0}^\\infty \\gamma^t R_t \\quad \\Bigg| \\quad \\begin{array}{l}S_0 = s, A_0=a,\\\\ A_t=\\pi(S_t)\\textrm{ for }t>0,\\\\ S_{t+1}\\sim p(\\cdot|S_t,A_t),\\\\R_t = r(S_t,A_t,S_{t+1})\\end{array} \\right],\\\\\n",
    " &= \\mathbb{E}_{s'} \\left[ r(s,a,s') + \\gamma V^\\pi(s') \\right], \\\\\n",
    " &= r(s,a) + \\gamma \\mathbb{E}_{s'} \\left[ V^\\pi(s') \\right]\n",
    "\\end{align*}\n",
    "\n",
    "<br>\n",
    "<br>\n",
    "<img src=\"img/Qfunctions.png\" style=\"height: 200px;\"></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Let's remark that $V^\\pi(s) = Q^\\pi(s,\\pi(s))$. Let's replace $a$ by $\\pi(s)$ above and we obtain an important equation to characterize $V^\\pi$.\n",
    "<br>\n",
    "<br>\n",
    "<img src=\"img/V-DP.png\" style=\"height: 200px;\"></img>\n",
    "$$V^\\pi(s) = r(s,\\pi(s)) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,\\pi(s))} \\left[ V^\\pi(s') \\right]$$\n",
    "\n",
    "This equation uses $V^\\pi(s')$ in all $s'$ reachable from $s$ to define $V^\\pi(s)$.  \n",
    "Since this equation is true in all $s$, this provides as many equations as we have states."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-success\"><b>Evaluation equation</b><br>\n",
    "$V^\\pi$ obeys the linear system of equations:\n",
    "$$\n",
    "V^\\pi\\left(s\\right) = r(s,\\pi(s)) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,\\pi(s))} \\left[ V^\\pi(s') \\right]\\\\\n",
    "$$\n",
    "Similarly:\n",
    "$$\n",
    "Q^\\pi\\left(s,a\\right) = r(s,a) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,a)} \\left[ Q^\\pi(s',\\pi(s')) \\right]\n",
    "$$\n",
    "</div>\n",
    "\n",
    "This leads to the introduction of the **Bellman evaluation operator**:\n",
    "<div class=\"alert alert-success\"><b>Evaluation operator $T^\\pi$</b><br>\n",
    "$T^\\pi$ is an operator on value functions, that transforms a function $V:S\\rightarrow \\mathbb{R}$ into:\n",
    "\\begin{align*}\n",
    "T^\\pi V\\left(s\\right) &= r(s,\\pi(s)) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,\\pi(s))} \\left[ V(s') \\right]\\\\\n",
    " &= r\\left(s,\\pi\\left(s\\right)\\right) + \\gamma \\sum\\limits_{s'\\in S} p\\left(s'|s,\\pi\\left(s\\right)\\right) V\\left(s'\\right)\n",
    "\\end{align*}\n",
    "    \n",
    "Similarly we can introduce an evaluation operator (with the same name $T^\\pi$) over state-action value functions. <br> \n",
    "$T^\\pi$ is an operator on state-action value functions, that transforms a function $Q:S\\times A\\rightarrow \\mathbb{R}$ into:\n",
    "\\begin{align*}\n",
    "T^\\pi Q\\left(s,a\\right) &= r(s,a) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,a)} \\left[ Q^\\pi(s',\\pi(s')) \\right]\\\\\n",
    " &= r\\left(s,a\\right) + \\gamma \\sum\\limits_{s'\\in S} p\\left(s'|s,a\\right) Q^\\pi\\left(s', \\pi\\left(s'\\right)\\right)\n",
    "\\end{align*}\n",
    "</div>\n",
    "\n",
    "Note that, fundamentally, we have written 4 times the same thing in the block above.  \n",
    "So finding $V^\\pi$ (resp. $Q^\\pi$) boils down to solving the evaluation equation $V= T^\\pi V$ (resp. $Q = T^\\pi Q$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We've gone far from our original FrozenLake problem. Let's make all this very concrete:\n",
    "- A policy $\\pi$ is an agent's behaviour\n",
    "- In every state $s$, one can expect to gain $V^\\pi(s)$ in the long run by applying $\\pi$\n",
    "- $V^\\pi(s)$ is the sum of the reward on the first step $r(s,\\pi(s))$ and the expected long-term return from the next state $\\gamma \\mathbb{E}_{s'} \\left[V^\\pi(s')\\right]$ \n",
    "- The function $V^\\pi$ actually obeys the linear system of equations above that simply link the value of a state with the values of its successors in an episode.\n",
    "\n",
    "We can stop for a minute on the $T^\\pi$ evaluation operator (that maps a function $S\\rightarrow\\mathbb{R}$ to a function $S\\rightarrow\\mathbb{R}$) and the search for $V^\\pi$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-success\"><b>Properties of $T^\\pi$</b><br>\n",
    "<ol>\n",
    "<li> $T^\\pi$ is an affine operator, it defines a linear system of equations.<br>\n",
    "<li> $T^\\pi$ is a contraction mapping<br>\n",
    "    Specifically, with $\\gamma<1$, $T^\\pi$ is a $\\| \\cdot \\|_\\infty$-contraction mapping over the $\\mathcal{F}(S,\\mathbb{R})$ (resp. $\\mathcal{F}(S\\times A,\\mathbb{R})$) Banach space.<br>\n",
    "$\\Rightarrow$ With $\\gamma<1$, $V^\\pi$ (resp. $Q^\\pi$) is the unique solution to the (linear) fixed point equation:<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$V=T^\\pi V$ (resp. $Q=T^\\pi Q$).\n",
    "</ol>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Let's use this second property to compute $Q^\\pi$ for the policy that always moves right on FrozenLake.\n",
    "\n",
    "Suppose we start with $Q_0(s,a) = 0$ for all $(s,a)$.\n",
    "\n",
    "Recall that, in FrozenLake, rewards are provided under the $r(s,a,s')$ form.\n",
    "\n",
    "Applying $T^\\pi$ once results in:\n",
    "$$Q_1(s,a) = \\sum_{s'} p(s'|s,a) \\left[ r(s,a,s') + \\gamma Q_0(s',\\pi(s')) \\right]$$\n",
    "\n",
    "In plain words, $Q_1$ is the one-step expected return under policy $\\pi$.\n",
    "\n",
    "Applying $T^\\pi$ twice results in:\n",
    "$$Q_2(s,a) = \\sum_{s'} p(s'|s,a) \\left[ r(s,a,s') + \\gamma Q_1(s',\\pi(s')) \\right]$$\n",
    "\n",
    "This is the two-step expected return.\n",
    "\n",
    "And so on.\n",
    "\n",
    "If we apply $T^\\pi$ enough times, $Q_n$ should become closer to $Q^\\pi$, whatever the chosen value for $Q_0$.\n",
    "\n",
    "In more formal words, because $T^\\pi$ is a contraction mapping, the sequence $Q_{n+1} = T^\\pi Q_n$ converges to $T^\\pi$'s fixed point.\n",
    "\n",
    "Let us live-code this.\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Live coding</b><br>\n",
    "Let's compute the sequence $Q_{n+1} = T^\\pi Q_n$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "pi = fl.RIGHT*np.ones((env.observation_space.n), dtype=np.uint8)\n",
    "nb_iter = 20\n",
    "gamma = 0.9\n",
    "\n",
    "Q = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "Qpi_sequence = [Q]\n",
    "for i in range(nb_iter):\n",
    "    Qnew = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "    for x in range(env.observation_space.n):\n",
    "        for a in range(env.action_space.n):\n",
    "            outcomes = env.unwrapped.P[x][a]\n",
    "            for o in outcomes:\n",
    "                p = o[0]\n",
    "                y = o[1]\n",
    "                r = o[2]\n",
    "                Qnew[x,a] += p * (r + gamma * Q[y,pi[y]])\n",
    "    Q = Qnew\n",
    "    Qpi_sequence.append(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\"><b>Live coding</b><br>\n",
    "Let's plot the sequence of $\\| Q_n - Q_{n-1} \\|_\\infty$ to verify the convergence of the sequence.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "residuals = []\n",
    "for i in range(1, len(Qsequence)):\n",
    "    residuals.append(np.max(np.abs(Qpi_sequence[i]-Qpi_sequence[i-1])))\n",
    "\n",
    "plt.plot(residuals)\n",
    "plt.figure()\n",
    "plt.semilogy(residuals);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### The optimality equation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We can unfold the same kind of reasoning on the value of an optimal policy. We write:\n",
    "$$V^{\\pi^*} = V^*, \\quad Q^{\\pi^*} = Q^*$$\n",
    "\n",
    "<div class=\"alert alert-success\"><b>Optimal greedy policy</b><br>\n",
    "Any policy $\\pi$ defined by $\\pi(s) \\in \\arg\\max\\limits_{a\\in A} Q^*(s,a)$ is an optimal policy.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "And $Q^*$ obeys the same type of recurrence relation:\n",
    "\n",
    "<div class=\"alert alert-success\"><b>Bellman optimality equation</b><br>\n",
    "The optimal value function obeys:\n",
    "\\begin{align*}\n",
    "    V^*(s) &= \\max\\limits_{a\\in A} \\left[ r(s,a) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,a)} V^*(s') \\right]\\\\\n",
    "        &= \\max\\limits_{a\\in A} \\left[ r(s,a) + \\gamma \\sum\\limits_{s'\\in S} p(s'|s,a) V^*(s') \\right]\n",
    "\\end{align*}\n",
    "or in terms of $Q$-functions:\n",
    "\\begin{align*}\n",
    "    Q^*(s,a) &= r(s,a) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,a)} \\left[ \\max_{a'\\in A} Q^*(s',a') \\right]\\\\\n",
    "        &= r(s,a) + \\gamma \\sum\\limits_{s'\\in S}p(s'|s,a) \\max\\limits_{a'\\in A} Q^*(s',a')\n",
    "\\end{align*}\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "As for the evaluation equation, we have actually written 4 times the same thing in the block above.  \n",
    "We have also defined the **Bellman optimality operator $T^*$** (on $V$ and $Q$ functions) as:\n",
    "<div class=\"alert alert-success\"><b>Bellman optimality operator</b><br>\n",
    "$$\\left(T^*V\\right)(s) = \\max\\limits_{a\\in A} \\left[ r(s,a) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,a)} V(s') \\right]$$\n",
    "$$\\left(T^*Q\\right)(s,a) = r(s,a) + \\gamma \\mathbb{E}_{s'\\sim p(s'|s,a)} \\left[ \\max_{a'\\in A} Q(s',a') \\right]$$\n",
    "</div>\n",
    "\n",
    "So finding $V^*$ (resp. $Q^*$) boils down to solving $V= T^* V$ (resp. $Q = T^* Q$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-success\"><b>Properties of $T^*$</b><br>\n",
    "<ol>\n",
    "<li> $T^*$ is non-linear.<br>\n",
    "<li> $T^*$ is a contraction mapping<br>\n",
    "With $\\gamma<1$, $T^*$ is a $\\| \\cdot \\|_\\infty$-contraction mapping over the $\\mathcal{F}(S,\\mathbb{R})$ (resp. $\\mathcal{F}(S\\times A,\\mathbb{R})$) Banach space.<br>\n",
    "$\\Rightarrow$ With $\\gamma<1$, $V^*$ (resp. $Q^*$) is the unique solution to the fixed point equation:<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$V=T^* V$ (resp. $Q=T^* Q$).\n",
    "</ol>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Dynamic Programming for the optimality equation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Repeatedly applying $T^*$ to an initial function $Q_0$ yields the sequence $Q_{n+1} = T^* Q_n$ that converges to $Q^*$.\n",
    "\n",
    "The implementation of this sequence's computation is the algorithm called **Value Iteration**.\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Live coding</b><br>\n",
    "Let's compute the sequence $Q_{n+1} = T^* Q_n$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "gamma = 0.9\n",
    "Q = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "Qopt_sequence = [Q]\n",
    "for i in range(nb_iter):\n",
    "    Qnew = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "    for x in range(env.observation_space.n):\n",
    "        for a in range(env.action_space.n):\n",
    "            outcomes = env.unwrapped.P[x][a]\n",
    "            for o in outcomes:\n",
    "                p = o[0]\n",
    "                y = o[1]\n",
    "                r = o[2]\n",
    "                Qnew[x,a] += p * (r + np.max(Q[y,:]) )\n",
    "    Q = Qnew\n",
    "    Qopt_sequence.append(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\"><b>Live coding</b><br>\n",
    "Let's plot the sequence of $\\| Q_n - Q_{n-1} \\|_\\infty$ to verify the convergence of the sequence.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "residuals = []\n",
    "for i in range(1, len(Qsequence)):\n",
    "    residuals.append(np.max(np.abs(Qopt_sequence[i]-Qopt_sequence[i-1])))\n",
    "\n",
    "plt.plot(residuals)\n",
    "plt.figure()\n",
    "plt.semilogy(residuals);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "There are alternatives to Value Iteration with algorithms such as Gauss-Seidel Value Iteration, Asynchronous Value Iteration, Policy Iteration or Modified Policy Iteration for instance. We unfortunately won't have time to cover them today."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Approximate Dynamic Programming\n",
    "\n",
    "Let's take a step back.\n",
    "\n",
    "With the Bellman equation, we have a way to **characterize** $Q^*$. This characterization directly translates to the **Value Iteration** algorithm. In turn, once we know $Q^*$, we can deduce $\\pi^*$.\n",
    "\n",
    "That's all very nice, but is it applicable in practice, on real world examples? In particular, how does the computation of $Q^*$ scale with large state and action spaces?\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Poll**  \n",
    "What is the time complexity of the Value Iteration algorithm implemented above, in terms of $|S|$ and $|A|$?  \n",
    "[https://linkto.run/p/6DVFBR0J](https://linkto.run/p/6DVFBR0J)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#answersComplexVI\" data-toggle=\"collapse\"><b>Answer:</b></a><br>\n",
    "<div id=\"answersComplexVI\" class=\"collapse\">\n",
    "$O(S^2 A)$\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "The curse of dimensionality makes the number of states and actions scale exponentially with the dimension of the state and action spaces. So exact computation of $Q^*$ quickly becomes intractable.\n",
    "\n",
    "Instead, one can try to *approximate* the resolution of $T^* Q_n$ at each step of Value Iteration. This yields the Approximate Value Iteration algorithm.\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "**Approximate Value Iteration** is the algorithm that computes the sequence $Q_{n+1} = \\mathcal{A} T^* Q_n$, where $\\mathcal{A}$ is an approximation procedure.\n",
    "</div>\n",
    "\n",
    "Note in particular that when dealing with parametric functions $Q_\\theta$, finding a minimizer of the loss\n",
    "$L_n(\\theta) = \\| Q_\\theta - T^* Q_n \\|$\n",
    "is such an approximation procedure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Let us suppose that $\\mathcal{A}$ is not a bad approximation procedure and that its approximation error is uniformly bounded, that is, \n",
    "$$\\forall f \\in \\mathcal{F}(S\\times A,\\mathbb{R}), \\ \\| f-\\mathcal{A}f \\|_\\infty \\leq \\epsilon.$$\n",
    "\n",
    "The first important result is that Approximate Value Iteration does not converge. However, one can prove that $Q_n$ reaches a neighborhood of $Q^*$. Specifically:\n",
    "$$\\lim_{n\\rightarrow \\infty} \\| Q^* - Q_n \\|_\\infty \\leq \\frac{\\epsilon}{1-\\gamma}.$$\n",
    "\n",
    "More importantly:  \n",
    "Let $\\pi_n$ be the greedy policy with respect to $Q_n$. Then:\n",
    "$$\\|Q^*-Q^{\\pi_n}\\|_\\infty \\leq \\frac{2\\gamma}{1-\\gamma} \\|Q^*-Q_n\\|_\\infty.$$\n",
    "\n",
    "And consequently:\n",
    "$$\\lim_{n\\rightarrow \\infty} \\|Q^*-Q^{\\pi_n}\\|_\\infty \\leq \\frac{2\\gamma\\epsilon}{(1-\\gamma)^2}.$$\n",
    "\n",
    "So,\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "Approximate Value Iteration does not necessarily converge but reaches policies whose values are close to optimal.\n",
    "</div>\n",
    "\n",
    "These results are proven in the **[Neuro-dynamic programming](http://athenasc.com/ndpbook.html)** book by D. P. Bertsekas and J. Tsitsiklis (1996).\n",
    "\n",
    "Most supervised learning algorithms minimize a loss that is expressed as a weighted $L_2$ norm. Thus, they don't explicitly provide guarantees in $L_\\infty$ norm. R. Munos provided **[error bounds for approximate value iteration](https://www.aaai.org/Papers/AAAI/2005/AAAI05-159.pdf)** in the general case of weighted $L_p$ norms. Those bounds are similar to the one in $L_\\infty$ norm, thus justifying the use of supervised learning techniques (such as neural networks learning from samples for instance) in Approximate Value Iteration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Summary\n",
    "\n",
    "In this section, we have built upon the MDP properties of the environment we wish to control, in order to characterize policies through their value functions.\n",
    "\n",
    "We have learned that:\n",
    "- $Q^\\pi$ is a solution to the Bellman evaluation equation\n",
    "$$Q = T^\\pi Q$$\n",
    "- $Q^*$ is a solution to the Bellman optimality equation\n",
    "$$Q = T^* Q$$\n",
    "- Value Iteration constructs the sequence of $Q_{n+1} = T^* Q_n$ value functions\n",
    "- Approximate Value Iteration trades exact construction of this sequence for scalability by constructing an approximate sequence $Q_{n+1} = \\mathcal{A} T^* Q_n$ that still provides good policies if $\\mathcal{A}$ is a good approximation procedure.\n",
    "\n",
    "So we have built the second stage of our three-stage rocket:\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "**What is an optimal strategy?**  \n",
    "An optimal policy is one that yields optimal cumulated rewards. It is a policy that is *greedy* with respect to an optimal value function $Q^*$. Such a value function obeys Bellman's optimality equation and can be (approximately) computed via (approximate) dynamic programming.\n",
    "</div>\n",
    "\n",
    "Still, we are still relying on a characterization of $\\pi^*$ that relies on the knowledge of the MDP.\n",
    "\n",
    "But we could imagine that $\\mathcal{A}$ is a procedure that *learns* $Q_{n+1}$ from samples of $T^* Q_n$. If such samples can be obtained from interaction with the system to control, it might be possible to learn $Q^*$ without knowing the MDP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Let's take a short break.**  \n",
    "**If there is time, I can take questions.**\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Learning optimal value functions (40 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "The key idea we develop in this section is that one can actually *learn* the sequence of AVI functions using interaction samples rather than *calculate* it using a model.\n",
    "\n",
    "<img src=\"img/brain.png\" width=\"400px\"></img>\n",
    "\n",
    "Although we have introduced a fair amount of abstract concepts, it is important to keep in mind that these maths simply formalize an intuitive cognitive process. By experiencing rewards and punishments, we (humans) incrementally learn to evaluate the outcomes of our actions and then decide to act accordingly. This cognitive process is thus in line with the formalism we have introduced."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Policy evaluation as Stochastic Approximation: Temporal Differences\n",
    "\n",
    "Recall that evaluating $Q^\\pi(s,a)$ is estimating the mathematical expectation of $G^\\pi(s,a)$.\n",
    "\n",
    "Stochastic approximation theory tells us that, for a given $s,a$ pair, given a series $g^\\pi_t$ of independent realizations of $G^\\pi(s,a)$, the sequence\n",
    "$q_{t+1} = q_t + \\alpha_t \\left(g^\\pi_t - q_t\\right)$\n",
    "converges to $\\mathbb{E}\\left(G^\\pi(s,a)\\right)$, if the sequence of $\\alpha_t$ respects the Robbins-Monro conditions ($\\sum_t \\alpha_t = \\infty$ and $\\sum_t \\alpha_t^2 < \\infty$).\n",
    "\n",
    "<a href=\"#morePpi\" data-toggle=\"collapse\">Intuitive explanation of Stochastic Approximation.</a><br>\n",
    "<div id=\"morePpi\" class=\"collapse\">\n",
    "    \n",
    "For those unfamiliar with stochastic approximation procedures, we can understand the previous update as: $g^\\pi_t$ are samples estimates of $\\mathbb{E}\\left(G^\\pi(s,a)\\right)$. If I already have an estimate $q_t$ of $\\mathbb{E}\\left(G^\\pi(s,a)\\right)$ and I receive a new sample $g^\\pi_t$, I should \"pull\" my previous estimate towards $g^\\pi_t$. But $g^\\pi_t$ carries a part of noise, so I should be cautious and only take a small step $\\alpha$ in the direction of $g^\\pi_t$.\n",
    "    \n",
    "In turn, the convergence conditions simply state that any value $Q^\\pi(s,a)$ should be reachable given any initial guess $Q(s,a)$, no matter how far from $Q^\\pi(s,a)$ is from this first guess; hence the $\\sum\\limits_{t=0}^\\infty \\alpha_t = \\infty$. However, we still need the step-size to be decreasing so that we don't start oscillating around $Q^\\pi(s,a)$ when we get closer; so to insure convergence we impose $\\sum\\limits_{t=0}^\\infty \\alpha_t^2 < \\infty$.\n",
    "</div>\n",
    "\n",
    "So this provides us with a way to estimate $Q^\\pi(s,a)$ from experience samples rather than from a model.  \n",
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "**Policy evaluation as stochastic approximation**  \n",
    "If we can obtain independent realizations $g^\\pi(s,a)$ of $G^\\pi(s,a)$ in all $s,a$, we can perform stochastic approximation updates of $Q$ under the form:\n",
    "$$Q(s,a) \\leftarrow Q(s,a) + \\alpha \\left(g^\\pi(s,a) - Q(s,a)\\right).$$\n",
    "Then $Q$ converges to $Q^\\pi$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "A more modern formulation of Stochastic Approximation is Stochastic Gradient Descent. So we will slightly generalize the formulation above.  \n",
    "\n",
    "$Q^\\pi$ is the function that minimizes\n",
    "$$L(Q) = \\frac{1}{2} \\int_{S\\times A} \\left[ Q(s,a) - \\mathbb{E}\\left(G^\\pi(s,a)\\right)\\right]^2 dsda.$$\n",
    "\n",
    "Recall that in the most general case, $Q$ is a function, but for the sake of clarity, we will momentarily suppose that $S\\times A$ is finite and thus $Q$ is equivalent to the vector of all $Q(s,a)$ values.\n",
    "\n",
    "Then, minimizing $L(Q)$ can be done via gradient descent:\n",
    "$$\\nabla_Q L(Q) = \\int_{S\\times A} \\left[ Q(s,a) - \\mathbb{E}\\left(G^\\pi(s,a)\\right) \\right] \\nabla_Q Q(s,a) dsda.$$\n",
    "\n",
    "Suppose we have a set of independently drawn states and actions $\\left\\{(s_i, a_i)\\right\\}_{i\\in [1,N]}$. Then, this gradient can be approached via a Monte Carlo estimator:\n",
    "$$\\sum_{i=1}^N \\left[ Q(s_i,a_i) - \\mathbb{E}\\left(G^\\pi(s_i,a_i)\\right)\\right] \\nabla_Q Q(s_i, a_i).$$\n",
    "\n",
    "In our example where $Q$ is the vector of values taken in each state and action, \n",
    "$\\nabla_Q Q(s_i,a_i) = \\left[ \\begin{array}{c} 0\\\\ \\vdots\\\\ 0\\\\ 1 \\\\ 0\\\\ \\vdots\\\\ 0 \\end{array} \\right]$ \n",
    "where the \"1\" is at the position corresponding to $s_i,a_i$ in the vector $Q$.\n",
    "\n",
    "As for Stochastic Approximation, if we can obtain independent realizations $g^\\pi(s_i,a_i)$ of $G^\\pi(s_i,a_i)$, then we can estimate this gradient as:\n",
    "$$d = \\sum_{i=1}^N \\left[ Q(s_i,a_i) - g^\\pi(s_i,a_i)\\right] \\nabla_Q Q(s_i,a_i).$$\n",
    "\n",
    "And thus we have the Stochastic Gradient Descent update:\n",
    "$$Q \\leftarrow Q - \\alpha \\sum_{i=1}^N \\left[ Q(s_i,a_i) - g^\\pi(s_i,a_i)\\right] \\nabla_Q Q(s_i,a_i)$$\n",
    "\n",
    "This update mechanism yields a sequence $Q_t$ of value functions that converges to $Q^\\pi$ if the gradient steps $\\alpha$ respect Robbins-Monro conditions.\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "**Policy evaluation as Stochastic Gradient Descent**  \n",
    "If we can obtain independent realizations $g^\\pi(s,a)$ of $G^\\pi(s,a)$ in all $s,a$, we can perform Stochastic Gradient Descent updates on $Q$:\n",
    "$$Q \\leftarrow Q + \\alpha \\sum_{i=1}^N \\left[ g^\\pi(s_i,a_i) - Q(s_i,a_i)\\right] \\nabla_Q Q(s_i,a_i).$$\n",
    "Then $Q$ converges to $Q^\\pi$.\n",
    "</div>\n",
    "\n",
    "Note that if $N=1$, the update above falls back to the Stochastic Approximation update: having a sample in $s_i,a_i$ only updates $Q(s_i,a_i)$.\n",
    "\n",
    "For the sake of simplicity, we will keep the Stochastic Approximation perspective in further developments. The transition to SGD is straightforward.\n",
    "\n",
    "So, overall, if we manage to draw independent samples $g^\\pi(s_i)$ of $G^\\pi(s)$ in all $s\\in S$, we can **learn** the value $V^\\pi$ (or $Q^\\pi$) of policy $\\pi$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Consider the sample $(s_t,a_t,r_t,s_{t+1})$ obtained at time $t$.\n",
    "\n",
    "Once this transition is over we can update our knowledge of $Q(s_t, a_t)$ by using $r_t+\\gamma Q(s_{t+1},\\pi(s_{t+1}))$. This estimate uses $Q(s_{t+1},\\pi(s_{t+1}))$ to *bootstrap*[1] the estimator of $Q(s_t, a_t)$.\n",
    "\n",
    "[1] This *bootstrap* operation has nothing to do with the statistical procedure of *bootstrapping*.\n",
    "\n",
    "This idea, which was first introduced in R. Sutton's **[Learning to predict by the methods of temporal differences](https://link.springer.com/article/10.1007/BF00115009)** article, has a strong parallel with the evaluation equation. This equation was:\n",
    "$$Q^\\pi \\left(s,a\\right) = \\mathbb{E}_{s' \\sim p\\left(s'|s,a\\right)} \\left[ r\\left(s,a,s'\\right) + \\gamma Q^\\pi \\left(s', \\pi(s')\\right) \\right]$$  \n",
    "\n",
    "The key remark is that the sample $g^\\pi_t$ of $Q^\\pi(s_t,a_t)$ can be built by summing $r_t$ and $\\gamma Q_t(s_{t+1}, \\pi(s_{t+1}) )$:\n",
    "$$g_t = r_t + \\gamma Q_t(s_{t+1}, \\pi(s_{t+1})).$$\n",
    "\n",
    "Note that in the expression above, we have used $Q_t$ to emphasize that we use the function $Q$ as it was at time step $t$, to define the target $g^\\pi_t$ used in the update that will provide $Q_{t+1}$.\n",
    "\n",
    "Formally, this comes directly from the evaluation operator. Let's rewrite $T^\\pi$ in terms of random variables.\n",
    "$$(T^\\pi Q)(s,a) = \\mathbb{E}_{R,S'}\\left[ R + \\gamma Q(S', \\pi(S')) \\right]$$\n",
    "\n",
    "Since $Q^\\pi$ is the fixed point of $T^\\pi$, by taking $g_t = r_t + \\gamma Q_t(s_{t+1},\\pi(s_{t+1}))$ we are taking one stochastic approximation step in the direction of $T^\\pi Q_t$. \n",
    "\n",
    "**Bootstrapping** (in this particular context) is the operation of using the value of $Q_t(s_{t+1},\\pi(s_{t+1}))$ in the update of $Q$.\n",
    "\n",
    "Then the stochastic approximation update becomes what is called the **TD(0) update**:\n",
    "<div class=\"alert alert-success\">\n",
    "    \n",
    "**TD(0) update:**  \n",
    "$$Q(s_t,a_t) \\leftarrow Q(s_t,a_t) + \\alpha \\left(r_t + \\gamma Q(s_{t+1}, \\pi(s_{t+1})) - Q(s_t,a_t)\\right).$$\n",
    "    \n",
    "This update consists in taking one stochastic approximation step in the direction of $T^\\pi V$.\n",
    "</div>\n",
    "\n",
    "The SGD update is almost the same."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Let's insist on this point:  \n",
    "TD(0) does not directly solve $Q=\\mathbb{E}\\left[\\sum_t\\gamma^t R_t \\right]$ (this is what other methods, called *Monte Carlo*, do). Instead, it implements stochastic approximation on top of the repeated application of the $T^\\pi$ operator. So it solves $Q_{n+1} = T^\\pi Q_n$. At each step $t$, it takes the current value function $Q_t$, draws one or several samples from $T^\\pi Q_t$ and approximates $T^\\pi Q_t$ by taking one step of gradient descent from $Q_t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "$\\delta_t=r_t + \\gamma Q_t(s_{t+1},\\pi(s_{t+1})) - Q_t(s_t,a_t)$ is called the prediction **temporal difference** (hence the name of the algorithm - the \"0\" won't be explained here). It is the difference between our estimate $Q_t(s_t,a_t)$ *before* obtaining the information of $r_t$, and the bootstrapped value $r_t + \\gamma Q_t(s_{t+1},\\pi(s_{t+1}))$.\n",
    "<div class=\"alert alert-success\"><b>Temporal difference:</b>\n",
    "$$\\delta=r + \\gamma Q(s',\\pi(s')) - Q(s,a)$$\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Now it seems obvious that if some state-action pair $s,a$ is never visited, then no update of its $Q(s,a)$ can ever take place. Therefore, for the TD(0) update to converge, we need to guarantee that all state action pairs will be visited frequently enough for $Q$ to converge to $Q^\\pi$.\n",
    "\n",
    "<div class=\"alert alert-success\"><b>TD(0) temporal difference update on $Q$-functions:</b><br>\n",
    "For a sample $(s,a,r,s')$, the temporal difference is:\n",
    "$$\\delta = r + \\gamma Q(s',\\pi(s')) - Q(s,a)$$\n",
    "And the TD update is:\n",
    "$$Q(s,a) \\leftarrow Q(s,a) + \\alpha \\left[ r + \\gamma Q(s',\\pi(s')) - Q(s,a) \\right]$$\n",
    "As long as all state-action pairs $(s,a)$ are sampled infinitely often as $t\\rightarrow\\infty$, and under the Robbins-Monro conditions, this procedure converges to $Q^\\pi$.\n",
    "</div>\n",
    "\n",
    "Interestingly, this algorithm puts restrictions on the policy we apply when interacting with the environment. We will call such a policy a **behavior policy**. The behavior policy and the policy being learned might be different (in the case of TD(0), this even is an obligation since we need to enforce visitation of all state-action pairs).\n",
    "\n",
    "Vocabulary: **Off-policy** evaluation algorithms can use a behavior policy that is different than the policy being evaluated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\"><b>Live coding:</b><br>\n",
    "Let's implement TD(0) on $Q$-functions.<br>\n",
    "To insure that all states and actions are sampled infinitely often, we take a behavior policy that acts randomly in each state.<br>\n",
    "We take $\\gamma=0.9$ and run the algorithm for 2000000 time steps.<br>\n",
    "To keep things simple, we take a constant $\\alpha=0.01$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "gamma = 0.9\n",
    "alpha = 0.01\n",
    "max_steps=1000000\n",
    "Qtd = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "Qtrue = Qpi_sequence[-1]\n",
    "\n",
    "error = np.zeros((max_steps))\n",
    "x = env.reset()\n",
    "for t in range(max_steps):\n",
    "    a = np.random.randint(4)\n",
    "    y,r,d,_ = env.step(a)\n",
    "    Qtd[x][a] = Qtd[x][a] + alpha * (r+gamma*Qtd[y][fl.RIGHT]-Qtd[x][a])\n",
    "    error[t] = np.max(np.abs(Qtd-Qtrue))\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "print(\"Max error:\", np.max(np.abs(Q-Qtrue)))\n",
    "plt.figure()\n",
    "plt.plot(error)\n",
    "plt.figure()\n",
    "plt.semilogy(error);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Many improvements, like [Experience Replay (Lin, 1992)](https://link.springer.com/article/10.1007/BF00992699) for instance, produce better gradient estimates. We won't cover them here and reserve them for future classes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Approximate Value Iteration as Stochastic Approximation: Q-learning\n",
    "\n",
    "We can directly adapt the idea of temporal difference learning to the Approximate Value Iteration case.\n",
    "\n",
    "In this case, we want to learn $T^* Q_t$ (instead of $T^\\pi Q_t$) so our samples are:\n",
    "$$g_t = r_t + \\gamma \\max_{a'} Q_t(s_{t+1},a').$$\n",
    "\n",
    "And the learning algorithm becomes the famous Q-learning algorithm, introduced by C. J. Watkins in 1989:\n",
    "<div class=\"alert alert-success\"><b>Q-learning</b><br>\n",
    "For a sample $(s,a,r,s')$, the temporal difference is:\n",
    "$$\\delta = r + \\gamma \\max_{a'} Q(s',a') - Q(s,a)$$\n",
    "And the TD update is:\n",
    "$$Q(s,a) \\leftarrow Q(s,a) + \\alpha \\left[ r + \\gamma \\max_{a'} Q(s',a') - Q(s,a) \\right]$$\n",
    "As long as all state-action pairs $(s,a)$ are sampled infinitely often as $t\\rightarrow\\infty$, and under the Robbins-Monro conditions, this procedure converges to $Q^*$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "To implement a Q-learning algorithm, one needs to decide on a behavior policy. As for TD(0), Q-learning will converge to $Q^*$, provided that all states and actions are visited infinitely often. It is actually notable that $Q$ converges to $Q^*$ even if the behavior policy does not. But it also looks like a waste of computational resources to keep exploring uniformly around the starting state.\n",
    "\n",
    "This tradeoff between exploring new actions and exploiting what has already been inferred in $Q$ is called the **exploration versus exploitation tradeoff**. It is a crucial problem that strongly affects the ability of the algorithm to discover new, interesting rewards.\n",
    "\n",
    "Here we will implement a rather naive tradeoff strategy called an $\\epsilon$-greedy behavior. It consists in picking the $Q$-greedy action with probability $1-\\epsilon$ and a random action with probability $\\epsilon$.\n",
    "\n",
    "$\\epsilon$ will start at 1 and then will periodically be divided by 2.\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Live coding:**\n",
    "\n",
    "Write a function that picks an epsilon-greedy action.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def epsilon_greedy(Q, s, epsilon):\n",
    "    a = np.argmax(Q[s,:])\n",
    "    if(np.random.rand()<=epsilon): # random action\n",
    "        aa = np.random.randint(env.action_space.n-1)\n",
    "        if aa==a:\n",
    "            a=env.action_space.n-1\n",
    "        else:\n",
    "            a=aa\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Live coding:**\n",
    "\n",
    "Write a Q-learning algorithm on FrozenLake. Keep track of the error w.r.t. $Q^*$ and the number of times each state-action pair is visited.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "# Let's restart from the previous Qpi\n",
    "Qql = Qpi_sequence[-1]\n",
    "max_steps = 2000000\n",
    "\n",
    "# Q-learning\n",
    "count = np.zeros((env.observation_space.n,env.action_space.n)) # to track update frequencies\n",
    "epsilon = 1\n",
    "x = env.reset()\n",
    "for t in range(max_steps):\n",
    "    if((t+1)%1000000==0):\n",
    "        epsilon = epsilon/2\n",
    "    a = epsilon_greedy(Qql,x,epsilon)\n",
    "    y,r,d,_ = env.step(a)\n",
    "    Qql[x][a] = Qql[x][a] + alpha * (r+gamma*np.max(Qql[y][:])-Qql[x][a])\n",
    "    count[x][a] += 1\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y\n",
    "\n",
    "# Q-learning's final value function and policy\n",
    "print(\"Max error:\", np.max(np.abs(Qql-Qopt_sequence[-1])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Live coding:**\n",
    "\n",
    "Display the visitation frequency</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "count_map = np.zeros((env.unwrapped.nrow, env.unwrapped.ncol, env.action_space.n))\n",
    "for a in range(env.action_space.n):\n",
    "    for x in range(env.observation_space.n):\n",
    "        row,col = to_row_col(x)\n",
    "        count_map[row, col, a] = count[x,a]\n",
    "\n",
    "fig, axs = plt.subplots(ncols=4)\n",
    "for a in range(env.action_space.n):\n",
    "    name = \"a = \" + actions[a]\n",
    "    axs[a].set_title(name)\n",
    "    axs[a].imshow(np.log(count_map[:,:,a]+1), interpolation='nearest')\n",
    "    #print(\"a=\", a, \":\", sep='')\n",
    "    #print(count_map[:,:,a])\n",
    "plt.show()\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "    \n",
    "**Live coding:**\n",
    "\n",
    "Display the final policy.</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def greedyQpolicy(Q):\n",
    "    pi = np.zeros((env.observation_space.n),dtype=np.int)\n",
    "    for s in range(env.observation_space.n):\n",
    "        pi[s] = np.argmax(Q[s,:])\n",
    "    return pi\n",
    "\n",
    "def print_policy(pi):\n",
    "    for row in range(env.unwrapped.nrow):\n",
    "        for col in range(env.unwrapped.ncol):\n",
    "            print(actions[pi[to_s(row,col)]], end='')\n",
    "        print()\n",
    "    return\n",
    "\n",
    "print(\"Final epsilon:\", epsilon)\n",
    "pi_ql = greedyQpolicy(Qql)\n",
    "print(\"Greedy Q-learning policy:\")\n",
    "print_policy(pi_ql)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Previous sections had shown how to charaterize and find optimal policies given the MDP model. We have built on the results of Approximate Dynamic Programming to **learn** optimal value functions from interaction samples.\n",
    "\n",
    "So we have built the third stage of our three-stage rocket:\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "**How do we learn an optimal strategy?**  \n",
    "To learn an optimal strategy, we rely on a stochastic approximation of $Q^*$, given samples drawn from the MDP. This stochastic approximation of $Q^*$ is actually a stochastic approximation of the $Q_n$ sequence of approximate value iteration. In the end, we need to find good approximation architectures and to control the exploration versus exploitation tradeoff.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Challenges in RL and RLVS classes (10 minutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### General summary\n",
    "\n",
    "We are reaching the end of this class and it is time to summarize the take-away messages.\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "**What is Reinforcement Learning?**  \n",
    "RL is the discipline that studies the *learning* process of optimal control policies in the MDP framework.  \n",
    "Its roots overlap Cognitive Psychology, Control Theory, Artificial Intelligence, Machine Learning.\n",
    "</div>\n",
    "\n",
    "<div class=\"alert alert-success\">\n",
    "\n",
    "**What are the building blocks of RL?**  \n",
    "RL is built upon the framework of Markov Decision Processes.  \n",
    "It draws from the characterization of optimal policies that maximize a given criterion, notably through Bellman's equations.  \n",
    "It learns stochastic approximation (or SGD) solutions to these equations using interaction samples.\n",
    "</div>\n",
    "\n",
    "Of course we have barely touched the surface of RL. Some methods do not rely on the Bellman equations, some others don't use Value Iteration for instance. The overall goal of this class was to acquire a common vocabulary and set of concepts, so that you become comfortable with the objects often manipulated in RL."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "###  Three intrinsic challenges in Reinforcement Learning\n",
    "\n",
    "Many topics covered in this class would deserve a more in-depth coverage, but we can already identify three challenges that make the RL problem intrinsically difficult:\n",
    "- Function approximation,\n",
    "- The exploration versus exploitation trade-off,\n",
    "- The improvement problem.\n",
    "\n",
    "As we have seen, **function approximation** is key in finding good policies. Although it needs not be tackled with stochastic gradient descent, the interplay between Deep Learning and Reinforcement Learning has trigger major advances in RL.\n",
    "\n",
    "The classes on April 1st about [Deep Q-Networks and its variants](https://rl-vs.github.io/rlvs2021/dqn.html) will dive deeper into how one can implement Approximate Value Iteration with Deep Neural Networks, and what really are the associated optimization problems. A particular focus will be given to how [Regularized MDPs](https://rl-vs.github.io/rlvs2021/regularized-mdps.html) bring a new perspective to Approximate Dynamic Programming.\n",
    "\n",
    "Behavior policies are a cornerstone of RL: which action should one take to obtain informative samples? Should one explore uniformly the environment or rather follow a policy that takes the system towards promising states before exploring more agressively? This is called the **tradeoff between exploration and exploitation**.\n",
    "\n",
    "The classes on March 26th about [Stochastic Bandits](https://rl-vs.github.io/rlvs2021/stochastic-bandits.html) algorithms, and [Monte Carlo Tree Search](https://rl-vs.github.io/rlvs2021/mcts.html) will explore this aspect more in-depth. They will be complemented by the [Exploration in Deep RL](https://rl-vs.github.io/rlvs2021/exploration.html) class on April 2nd.\n",
    "\n",
    "The ideas we developped in this class relied on estimating value functions to deduce greedy policies. Finding such greedy policies was made easy because actions were discrete. But **finding improving policies** is actually a challenge in itself. This problem is present both when one searches for a greedy action with respect to $Q$, and when one directly aims at solving the $\\max_\\pi J(\\pi)$ problem without going through the proxy of the optimality equation.\n",
    "\n",
    "The classes of April 2nd will cover the question of gradient-based policy search methods, called [Policy Gradient](https://rl-vs.github.io/rlvs2021/pg.html) methods.\n",
    "Conversely, the morning of April 8th will cover gradient-free [evolutionary RL](https://rl-vs.github.io/rlvs2021/evo-rl.html) methods and how [Evolving Agents that Learn More Like Animals](https://rl-vs.github.io/rlvs2021/evolving-agents.html) is an efficient way of solving the RL problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "### Specific questions and challenges in RL\n",
    "\n",
    "Beyond these three intrinsic challenges, there are countless, context-dependent, open questions in RL:\n",
    "- Can one define and exploit temporal abstractions (macro-actions) in Reinforcement Learning?  \n",
    "This will be covered in the [Introduction to Hierarchical RL](https://rl-vs.github.io/rlvs2021/hierarchical.html) class on March 25th.\n",
    "- What connection can we draw between human preferences and formal reward models for better RL?  \n",
    "This is the topic of the [Reward Processing Biases in Humans and RL Agents](https://rl-vs.github.io/rlvs2021/human-behavioral-agents.html) class on March 25th.\n",
    "- How can one leverage prior knowledge about the system to control in order to learn faster or to obtain more meaningful policies? What is the interplay between learning and reasoning?    \n",
    "These will be covered in the [Micro-data Policy Search](https://rl-vs.github.io/rlvs2021/micro-data.html), the [Symbolic Representations and Reinforcement Learning](https://rl-vs.github.io/rlvs2021/symbolic.html) and the [Leveraging model-learning for extreme generalization](https://rl-vs.github.io/rlvs2021/model-learning.html) classes (April 8th and 9th respectively).\n",
    "- What are the obstacles that arise when applying RL to real-world systems?  \n",
    "The classes on [Multi-armed bandits in clinical trials](https://rl-vs.github.io/rlvs2021/clinical.html) (March 26th) and [Efficient Motor Skills Learning in Robotics](https://rl-vs.github.io/rlvs2021/efficient-motor.html) (April 8th) will illustrate them while the [RL tips and tricks](https://rl-vs.github.io/rlvs2021/tips-and-tricks.html) class (April 9th) will cover the development and usage of a comprehensive RL library.\n",
    "\n",
    "And among the topics that RLVS will not cover but that deserve to be mentionned here we can list:\n",
    "- Multi-agent RL\n",
    "- Partially observable MDPs\n",
    "- Robust RL\n",
    "- Offline RL\n",
    "- Consolidation and Transfer in RL\n",
    "- Causal RL\n",
    "- and many more !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<center><b>Welcome to the field of Reinforcement Learning!</b></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "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.7.6"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "12px",
    "width": "186px"
   },
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "410.667px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}