RL2 - Online Value Function Prediction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Class 2: Online Value Function Prediction.**\n",
    "\n",
    "1. [Everything you need to know](#everything)\n",
    "2. [Value prediction](#pred)\n",
    "    1. [Model-based value prediction](#model)\n",
    "    1. [Monte-Carlo evaluation](#mc)\n",
    "    3. [Temporal differences learning](#td0)\n",
    "    4. [TD($\\lambda$)](#tdlambda)\n",
    "    5. [Summary](#predsummary)\n",
    "3. [Value function approximation](#approx)\n",
    "    1. [Linear value function approximation](#linear)\n",
    "    2. [The tabular case is just a specific case of linear model](#tab)\n",
    "    3. [TD($\\lambda$) as a parametric model update](#param)\n",
    "    4. [Non-parametric models](#nonparam)\n",
    "    5. [Conclusion on value function approximation](#conc-FA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"everything\"></a>Everything you need to know\n",
    "\n",
    "\n",
    "Everything you should remember after this session.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-success\">\n",
    "<ul>\n",
    "<li> Model-based RL: infer an MDP model from samples, solve the evaluation equation for this model.\n",
    "<li> Online, stochastic approximation of $V^\\pi$:\n",
    "$$V(s_t) \\leftarrow V(s_t) + \\alpha \\left[ R - V(s_t) \\right]$$\n",
    "where $R$ is the <i>target</i> sample of $V^\\pi$.<br>\n",
    "This procedures converges to $V^\\pi$ under the Robbins-Monro conditions: $\\sum\\limits_{t=0}^\\infty \\alpha_t = \\infty$ and  $\\sum\\limits_{t=0}^\\infty \\alpha_t^2 < \\infty$.\n",
    "<li> Online Monte-Carlo estimates: given a finite length episode, target $R=R_t = \\sum_{i<t} \\gamma^{i-t} r_i$.\n",
    "<li> Given a sample $(s,a=\\pi(s),r,s')$, the temporal difference is $\\delta=r + \\gamma V(s') - V(s)$.\n",
    "<li> TD(0) update: given a sample $(s,a=\\pi(s),r,s')$, target $R=R_t^{(1)}=r + \\gamma V(s')$.\n",
    "<li> TD(0) update on $Q$-functions: given a sample $(s,a,r,s')$, the temporal difference is $\\delta = r + \\gamma Q(s',\\pi(s') - Q(s,a)$ and the update of $Q$ is $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\delta$. This update is off-policy.\n",
    "<li> $n$-step return: $R=R^{(n)}_t = r_t + \\gamma r_{t+1} + \\gamma^2 r_{t+2} + \\ldots + \\gamma^n V_t(s_{t+n})$.\n",
    "<li> $\\lambda$-return: $R=R^\\lambda_t = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^\\infty \\lambda^{n-1}R_t^{(n)}$.\n",
    "<li> TD($\\lambda$) algorithm: Given a new sample $(s_t,a_t=\\pi(s_t),r_t,s_t')$.\n",
    "<ol>\n",
    "<li> Temporal difference $\\delta = r_t+\\gamma V(s_t') - V(s_t)$.\n",
    "<li> Update eligibility traces for all states<br>\n",
    "$e(s) \\leftarrow \\left\\{\\begin{array}{ll}\n",
    "\\gamma \\lambda e(s) & \\textrm{if } s\\neq s_t\\\\\n",
    "1\\textrm{ (or }1+e(s)\\textrm{)} & \\textrm{if } s=s_t\n",
    "\\end{array}\\right.$\n",
    "<li> Update all state's values $V(s) \\leftarrow V(s) + \\alpha e(s) \\delta$\n",
    "</ol>\n",
    "<li> TD($\\lambda$) implements the $\\lambda$-return algorithm.\n",
    "<li> TD($\\lambda$) (accumulating traces) with parametric function approximation. With $V(s) = V_\\theta(s), \\theta \\in \\mathbb{R}^K$, $e \\in \\mathbb{R}^K$. Initially, $e=0$. Given a new sample $(s_t,a_t=\\pi(s_t),r_t,s_t')$.\n",
    "<ol>\n",
    "<li> Temporal difference $\\delta = r_t+\\gamma V_\\theta(s_t') - \\theta^T V_\\theta(s_t)$.\n",
    "<li> Update eligibility traces for all states $e \\leftarrow \\nabla_\\theta V_\\theta(s) + \\gamma \\lambda e$\n",
    "<li> Update value function $\\theta \\leftarrow \\theta + \\alpha e \\delta$\n",
    "</ol>\n",
    "</ul>\n",
    "</div>\n",
    "\n",
    "Of course, all this seems very obscure right now and the block above will only serve as a reminder when you re-open the notebook later. We will introduce every concept intuitively and progessively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"pred\"></a>Value prediction\n",
    "\n",
    "Back on the frozen lake example from the previous class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym\n",
    "import gym.envs.toy_text.frozen_lake as fl\n",
    "import numpy as np\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "np.set_printoptions(precision=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = gym.make('FrozenLake-v0')\n",
    "env.render()\n",
    "\n",
    "actions = {fl.LEFT: '\\u2190', fl.DOWN: '\\u2193', fl.RIGHT: '\\u2192', fl.UP: '\\u2191'}\n",
    "print(actions)\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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take a fixed policy $\\pi$. What is its expected value from the starting state (or any other state)?\n",
    "\n",
    "In this section, we will develop 5 different (but related) approches to this question:\n",
    "1. Get samples $(s,\\pi(s),r,s')$, estimate $p^\\pi$ and $r^\\pi$, then solve $V=T^\\pi V$<br>\n",
    "$\\rightarrow$ model-based prediction\n",
    "2. Run successive trials and update $V^\\pi(s)$ in all encountered $s$<br>\n",
    "$\\rightarrow$ Offline Monte Carlo\n",
    "3. Run one trial and update all visited $s$ by back-propagation<br>\n",
    "$\\rightarrow$ Online Monte Carlo\n",
    "4. Get one sample $(s,\\pi(s),r,s')$ and update $V^\\pi(s)$ given $r$ and $V^\\pi(s')$<br>\n",
    "$\\rightarrow$ TD(0)\n",
    "5. Get one sample $(s,\\pi(s),r,s')$ and update $V^\\pi(s)$ in all states<br>\n",
    "$\\rightarrow$ TD($\\lambda$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"model\"></a>Model-based Value Prediction\n",
    "\n",
    "If we can interact with the simulator, we can collect samples and approximate the transition and reward models, then use them to perform model-based resolution of the evaluation equation (as in the previous class).\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Let's implement this for the policy that always goes right. Run 10000 episodes until termination (or until a maximum limit of 1000 time steps) and reconstruct an approximation of the transition kernel and reward vector for this policy. Use them to solve the evaluation equation.\n",
    "</div>\n",
    "Watch out for states from which no transition starts (either because they are terminal states or because they were not reached by this policy): the transition matrix needs to remain valid for the corresponding lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# parameters\n",
    "gamma = 0.9\n",
    "epsilon = 1e-4\n",
    "max_steps = 1000\n",
    "max_episodes = 10000\n",
    "max_iter_VI = 100\n",
    "P_pi = np.zeros((env.observation_space.n, env.observation_space.n))\n",
    "r_pi = np.zeros((env.observation_space.n))\n",
    "x_count = np.zeros((env.observation_space.n))\n",
    "\n",
    "# collect samples, count transitions and accumulate rewards\n",
    "total_steps = 0\n",
    "for ep in range(max_episodes):\n",
    "    x = env.reset()\n",
    "    for t in range(max_steps):\n",
    "        y,r,d,_ = env.step(fl.RIGHT)\n",
    "        P_pi[x][y] += 1\n",
    "        r_pi[x] += r\n",
    "        x_count[x] += 1\n",
    "        if d==True:\n",
    "            break\n",
    "        else:\n",
    "            x=y\n",
    "\n",
    "# normalize\n",
    "for x in range(env.observation_space.n):\n",
    "    if x_count[x]==0: # unreached states\n",
    "        P_pi[x][x] = 1\n",
    "        r_pi[x] = 0\n",
    "    else:\n",
    "        P_pi[x][:] = P_pi[x][:]/x_count[x]\n",
    "        r_pi[x]    = r_pi[x]   /x_count[x]\n",
    "\n",
    "\n",
    "# compute V with value iteration\n",
    "V = np.zeros((env.observation_space.n))\n",
    "W = np.zeros((env.observation_space.n))\n",
    "residuals = np.zeros((max_iter_VI))\n",
    "for i in range(max_iter_VI):\n",
    "    W = r_pi + gamma * np.dot(P_pi, V)\n",
    "    residuals[i] = np.max(np.abs(W-V))\n",
    "    V = W\n",
    "    if residuals[i]<epsilon:\n",
    "        residuals = residuals[:i+1]\n",
    "        break\n",
    "\n",
    "print(V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compare with the true values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "r_pi = np.zeros((env.observation_space.n))\n",
    "P_pi = np.zeros((env.observation_space.n, env.observation_space.n))\n",
    "for x in range(env.observation_space.n):\n",
    "    outcomes = env.unwrapped.P[x][fl.RIGHT]\n",
    "    for o in outcomes:\n",
    "        p = o[0]\n",
    "        y = o[1]\n",
    "        r = o[2]\n",
    "        P_pi[x,y] += p\n",
    "        r_pi[x] += r*p\n",
    "\n",
    "# compute V with value iteration\n",
    "Vtrue = np.zeros((env.observation_space.n))\n",
    "W = np.zeros((env.observation_space.n))\n",
    "residuals = np.zeros((max_iter_VI))\n",
    "for i in range(max_iter_VI):\n",
    "    W = r_pi + gamma * np.dot(P_pi, Vtrue)\n",
    "    residuals[i] = np.max(np.abs(W-V))\n",
    "    Vtrue = W\n",
    "    if residuals[i]<epsilon:\n",
    "        residuals = residuals[:i+1]\n",
    "        break\n",
    "\n",
    "print(Vtrue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we can see this is a fall-back solution that happens to work reasonably well. This approach is generally called **model-based prediction** or **adaptive dynamic programming** or **indirect reinforcement learning**. It converges to the true $p(s'|s,\\pi(s))$, $r(s,\\pi(s)$ and $V^\\pi$ if the samples are identically and independently distributed (iid). It has the advantage of working both **online** and **offline**. It is however **on-policy**, that is one cannot use samples collected from the execution of $\\pi$ to evaluate $\\pi'$.\n",
    "\n",
    "But in the end there is no direct evaluation of the policy's value, and our intuition tells us that a player is generally able to tell what a policy is worth in a certain state, even though he has never explicitly estimated the transition and reward models. So we must be able to design model-free evaluation methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"mc\"></a>Monte-Carlo evaluation\n",
    "\n",
    "Monte Carlo methods are intuitive, episode-based methods. \n",
    "\n",
    "Let us start with a fully **offline Monte-Carlo**. The idea is simple: start from $s$, run the policy until termination (or for a long number of steps), repeat for a number of episodes, then update the value of all encountered states. This requires to store in memory full episodes (it also requires that the episodes be finite-length).\n",
    "\n",
    "Let us move directly to an **online Monte-Carlo** method. It is almost the same idea: start from $s$, run the policy until termination (or for a long number of steps) then update the value of all encountered states before restarting an episode. \n",
    "\n",
    "Let $(s_0, r_0, s_1, \\ldots, s_T)$ be the sequence of transitions of such an episode. Then, this procedure provides an estimate $R_t$ of the value of the state $s_t$ encountered at time step $t$:\n",
    "<div class=\"alert alert-success\"><b>Monte Carlo return:</b>\n",
    "$$R_t = \\sum_{i>t} \\gamma^{i-t} r_i$$\n",
    "</div>\n",
    "\n",
    "Let $R^\\pi(s)$ be the random variable corresponding to the sum of discounted rewards one can obtain from $s$. Then $V^\\pi(s) = \\mathbb{E}(R^\\pi(s))$. Since $R(s_t)$ is a realization of $R(s)$, one can design a **stochastic approximation** procedure that converges to $V^\\pi(s_t)$:\n",
    "<div class=\"alert alert-success\"><b>Stochastic approximation of $V^\\pi$:</b>\n",
    "$$V(s_t) \\leftarrow V(s_t) + \\alpha \\left[ R_t - V(s_t) \\right]$$\n",
    "</div>\n",
    "\n",
    "For those unfamiliar with stochastic approximation procedures, we can understand the previous update as: $R_t$ are samples estimates of $V^\\pi(s_t)$. If I already have an estimation of $V(s_t)$ of $V^\\pi(s_t)$ and I receive a new sample $R_t$, I should \"pull\" my previous estimate towards $R_t$, but $R_t$ carries a part of noise, so I should be cautious and only take a small step $\\alpha$ in the direction of $R_t$. This type of stochastic approximation procedure converges if it respects Robbins-Monro's conditions:\n",
    "<div class=\"alert alert-success\"><b>Robbins-Monro convergence conditions:</b>\n",
    "$$\\sum\\limits_{t=0}^\\infty \\alpha_t = \\infty \\quad \\textrm{  and  } \\quad \\sum\\limits_{t=0}^\\infty \\alpha_t^2 < \\infty.$$\n",
    "</div>\n",
    "Intuitive explanation. These conditions simply say that any value $V^\\pi(s)$ should be reachable given any initial guess $V(s)$, no matter how far from $V^\\pi(s)$ 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 $V^\\pi(s)$ when we get closer; so to insure convergence we impose $\\sum\\limits_{t=0}^\\infty \\alpha_t^2 < \\infty$.\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Implement an online Monte-Carlo estimation for $V^\\pi$. We decide we can tolerate a 0.001 error on $V^\\pi$ so, to keep things simple, we set $\\alpha=0.001$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# parameters\n",
    "gamma = 0.9\n",
    "alpha = 0.001\n",
    "max_steps = 1000\n",
    "max_episodes = 100000\n",
    "V = np.zeros((env.observation_space.n))\n",
    "\n",
    "# error plotting\n",
    "error = np.zeros((max_episodes)) # used to track the convergence to Vtrue...\n",
    "cumulated_steps = np.zeros((max_episodes)) # ... against the number of samples\n",
    "\n",
    "for ep in range(max_episodes):\n",
    "    x = env.reset()\n",
    "    episode = []\n",
    "    # Run episode\n",
    "    for t in range(max_steps):\n",
    "        y,r,d,_ = env.step(fl.RIGHT)\n",
    "        episode.append([x,r])\n",
    "        if d==True:\n",
    "            cumulated_steps[ep] = cumulated_steps[ep-1] + t\n",
    "            break\n",
    "        else:\n",
    "            x=y\n",
    "    # Update values\n",
    "    T = len(episode)\n",
    "    R = np.zeros((T))\n",
    "    R[-1] = episode[-1][1]\n",
    "    x = episode[-1][0]\n",
    "    V[x] = V[x] + alpha * (R[-1] - V[x])\n",
    "    for t in range(-2,-T-1,-1):\n",
    "        R[t] = episode[t][1] + gamma*R[t+1]\n",
    "        x = episode[t][0]\n",
    "        V[x] = V[x] + alpha * (R[t] - V[x])\n",
    "    error[ep] = np.max(np.abs(V-Vtrue))\n",
    "\n",
    "print(V)\n",
    "print(Vtrue)\n",
    "plt.plot(cumulated_steps,error)\n",
    "plt.figure()\n",
    "plt.semilogy(cumulated_steps,error);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So online Monte-Carlo allows us to update $V^\\pi$ episode after episode. Some values are better estimated than others depending on how often the corresponding state was visited.\n",
    "\n",
    "Monte-Carlo estimation has some flaws nonetheless. It still requires to store one full episode in memory before $V$ is updated. Also, one rare value for $r_t$ affects directly all the value of the states encountered before $s_t$. So we can question the robustness of this estimator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"td0\"></a>Temporal Differences learning\n",
    "\n",
    "We want to replace Monte-Carlo estimation by a step by step update that only takes $(s,r,s')$ as an input. The key remark we make is that once the $(s,r,s')$ transition is over we can update our knowledge of $V(s)$ by using $r+\\gamma V(s')$. This estimate uses $V(s')$ to *bootstrap*[1] the estimator of $V(s)$.\n",
    "\n",
    "[1] This *bootstrap* operation has nothing to do with the statistical procedure of *bootstrapping*.\n",
    "\n",
    "To get an intuitive understanding of why we can do that, take the following example. You are driving from home to the airport. Half-way, you realize traffic is denser than you usually estimate and you're already 5 minutes behind schedule. Home is $s$, half-way is $s'$, the elapsed time between $s$ and $s'$ is $r$. To update your belief about the average length of the trip home$\\rightarrow$airport ($V(s)$), you don't need to wait until you reach the airport (as a Monte-Carlo estimate would have required). Instead, you can update this belief using $r+V(s')$, the sum of what you observed and what you currently estimate for the rest of the trip. As long as you update all states often enough, the whole procedure should converge to the true $V$.\n",
    "\n",
    "So here is the update that we shall call TD(0):\n",
    "<div class=\"alert alert-success\"><b>TD(0) temporal difference update:</b>\n",
    "$$V(s) \\leftarrow V(s) + \\alpha \\left[ r + \\gamma V(s') - V(s) \\right]$$\n",
    "</div>\n",
    "\n",
    "$\\delta=r + \\gamma V(s') - V(s)$ is called the prediction **temporal difference** (hence the name TD(0) for the algorithm - the \"0\" will be explained in the next section). It is the difference between our estimate $V(s)$ *before* obtaining the information of $r$ and the bootstrapped value $r+\\gamma V(s')$.\n",
    "<div class=\"alert alert-success\"><b>Temporal difference:</b>\n",
    "$$\\delta=r + \\gamma V(s') - V(s)$$\n",
    "</div>\n",
    "\n",
    "**Bootstrapping** (in this particular context) is the operation of using the value of $V(s')$ to update $V(s)$.\n",
    "\n",
    "This is a sample-by-sample update (no need to remember full episodes) and, more importantly, it is adapted to non-episodic environments (with no terminal states). As for online Monte-Carlo, the update above converges to $V^\\pi$ if $\\alpha$ respects the Robbins-Monro conditions:\n",
    "$$\\sum\\limits_{t=0}^\\infty \\alpha_t = \\infty \\quad \\textrm{  and  } \\quad \\sum\\limits_{t=0}^\\infty \\alpha_t^2 < \\infty.$$\n",
    "\n",
    "Often, TD methods converge faster and are more robust estimators than Monte Carlo ones (but not always).\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Implement a TD(0) estimation for $V^\\pi$. Again, we decide we can tolerate a 0.001 error on $V^\\pi$ so, to keep things simple, we set $\\alpha=0.001$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# parameters\n",
    "gamma = 0.9\n",
    "alpha = 0.001\n",
    "max_steps = 2000000\n",
    "V = np.zeros((env.observation_space.n))\n",
    "\n",
    "# error plotting\n",
    "error = np.zeros((max_steps)) # used to track the convergence to Vtrue\n",
    "\n",
    "x = env.reset()\n",
    "for t in range(max_steps):\n",
    "    y,r,d,_ = env.step(fl.RIGHT)\n",
    "    V[x] = V[x] + alpha * (r+gamma*V[y]-V[x])\n",
    "    error[t] = np.max(np.abs(V-Vtrue))\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y\n",
    "\n",
    "print(V)\n",
    "print(Vtrue)\n",
    "plt.plot(error)\n",
    "plt.figure()\n",
    "plt.semilogy(error);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Can you design a TD(0) algorithm on state-action values functions $Q(s,a)$ that estimates $Q^\\pi$ for a given policy $\\pi$? Does this algorithm require that the transitions from $s$ to $s'$ be sampled using $\\pi$?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#TD-Q\" data-toggle=\"collapse\"><b>Answers:</b></a><br>\n",
    "<div id=\"TD-Q\" class=\"collapse\">\n",
    "We wish to estimate $Q(s,a)$:\n",
    "$$Q^\\pi(s,a) = \\mathbb{E}\\left( \\sum\\limits_{t=0}^\\infty \\gamma^t r\\left(s_t, a_t\\right) \\bigg| s_0 = s, a_0=a, \\pi \\right) = r(s,a) + \\gamma \\sum\\limits_{s'\\in S}p(s'|s,a) Q^\\pi(s',\\pi(s'))$$\n",
    "\n",
    "So we can write our temporal difference by bootstrapping with $Q(s',\\pi(s'))$. Suppose the last sample was $(s,a,r,s')$.\n",
    "$$\\delta = r + \\gamma Q(s',\\pi(s')) - Q(s,a)$$\n",
    "And the update of $Q$ goes as:\n",
    "$$Q(s,a) \\leftarrow Q(s,a) + \\alpha \\delta$$\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 should converge to $Q^\\pi$. So the transitions should be sampled for every state-action pair and thus do not require to apply $\\pi(s)$ in $s$.\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<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, in the exercice above, the samples $(s,a,r,s')$ do not require $a=\\pi(s)$. Even better, they actually require to try all possible actions in $s$ for the procedure to converge (not only $\\pi(s)$). So this TD(0) algorithm on $Q$-functions is an **off-policy** algorithm. One can obtain the value $Q^\\pi$ of a policy $\\pi$ without applying $\\pi$ for sample collection. This will prove very useful during the class on model-free control.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Let's implement TD(0) on $Q$-functions.<br>\n",
    "To insure that all states and actions are sampled infinitely often, just act randomly in each state.<br>\n",
    "In order to speed up convergence, we can initialize $Q(s,a)$ to the value found previously for $V^\\pi(s)$.<br>\n",
    "Use the class on model-based policy evaluation to retrieve the true value of $Q^\\pi$ and display convergence of TD(0).\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Policy definition and parameters\n",
    "pi0 = fl.RIGHT*np.ones((env.observation_space.n),dtype=np.int)\n",
    "gamma = 0.9\n",
    "alpha = 0.001\n",
    "\n",
    "# Model based evaluation\n",
    "def policy_Qeval_iter(pi, epsilon, max_iter):\n",
    "    Q1 = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "    Q2 = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "    residuals = np.zeros((max_iter))\n",
    "    for i in range(max_iter):\n",
    "        for x in range(env.observation_space.n):\n",
    "            for a in range(env.action_space.n):\n",
    "                Q2[x][a] = 0\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",
    "                    Q2[x][a] += p * (r + gamma*Q1[y][pi[y]])\n",
    "        residuals[i] = np.max(np.abs(Q2-Q1))\n",
    "        Q1[:] = Q2\n",
    "        if residuals[i]<epsilon:\n",
    "            residuals = residuals[:i+1]\n",
    "            break\n",
    "    return Q1, residuals\n",
    "\n",
    "Qtrue, residuals = policy_Qeval_iter(pi0,1e-4,10000)\n",
    "print(\"Qtrue:\\n\", Qtrue)\n",
    "print(\"number of iterations:\", residuals.size)\n",
    "plt.plot(residuals)\n",
    "plt.figure()\n",
    "plt.semilogy(residuals)\n",
    "\n",
    "Vtrue = np.zeros((env.observation_space.n))\n",
    "for x in range(env.observation_space.n):\n",
    "    Vtrue[x] = Qtrue[x][pi0[x]]\n",
    "print(\"Vtrue:\\n\", Vtrue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TD(0) evaluation of Qpi\n",
    "# parameters\n",
    "gamma = 0.9\n",
    "alpha = 0.001\n",
    "max_steps=2000000\n",
    "Q = np.transpose(np.tile(V, (4,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",
    "    Q[x][a] = Q[x][a] + alpha * (r+gamma*Q[y][fl.RIGHT]-Q[x][a])\n",
    "    error[t] = np.max(np.abs(Q-Qtrue))\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y\n",
    "\n",
    "print(\"Max error:\", np.max(np.abs(Q-Qtrue)))\n",
    "plt.plot(error)\n",
    "plt.figure()\n",
    "plt.semilogy(error);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## <a id=\"tdlambda\"></a>TD($\\lambda$)\n",
    "\n",
    "With MC and TD(0), we have two methods with different features:\n",
    "- TD(0): 1-sample update with bootstrapping\n",
    "- MC: $\\infty$-sample update with no bootstrapping\n",
    "\n",
    "What's inbetween?\n",
    "- inbetween: $n$-sample update with bootstrapping\n",
    "\n",
    "We define the **$n$-step target** or **$n$-step return** $R^{(n)}_t$:\n",
    "\n",
    "$$\n",
    "\\begin{array}{l|l}\n",
    "R_t = r_t + \\gamma r_{t+1} + \\gamma^2 r_{t+2} + \\ldots & \\textrm{MC}\\\\\n",
    "R^{(1)}_t = r_t + \\gamma V_t(s_{t+1}) & 1\\textrm{-step TD = TD(0)}\\\\\n",
    "R^{(2)}_t = r_t + \\gamma r_{t+1} + \\gamma^2 V_t(s_{t+2}) & 2\\textrm{-step TD}\\\\\n",
    "R^{(n)}_t = r_t + \\gamma r_{t+1} + \\gamma^2 r_{t+2} + \\ldots + \\gamma^n V_t(s_{t+n}) & n\\textrm{-step TD}\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "And we define the **$n$-step TD update** as:\n",
    "<div class=\"alert alert-success\"><b>$n$-step TD update:<b>\n",
    "$$V(s) \\leftarrow V(s) + \\alpha \\left[ R^{(n)}_t - V(s) \\right]$$\n",
    "</div>\n",
    "\n",
    "So MC corresponds to an $\\infty$-step TD update. The $n$-step TD update algorithm converges to the true $V^\\pi$ just as TD(0) or MC. It requires to wait for $n$ time steps before performing an update.\n",
    "\n",
    "Remark: for finite-length  episodes of length $T$, all $n$-step returns for $n>T-t$ are equal to the Monte Carlo return $R_t$.\n",
    "\n",
    "So $n$-step TD updates bridge a gap between MC and TD(0). But it's not quite satisfying yet because we never really know what value of $n$ is appropriate to speed up convergence for a given problem. An interesting property is that we can mix $n$ and $m$-step returns together. Consider $R^{mix}_t = \\frac{1}{3} R^{(2)}_t + \\frac{2}{3} R^{(4)}_t$.\n",
    "Then the update $V(s_t) \\leftarrow V(s_t) + \\alpha \\left[R^{mix}_t - V(s_t)\\right]$ still converges to $V^\\pi$. More generally, convex sums of $n$-step returns yield update procedures that still converge to $V^\\pi$.\n",
    "\n",
    "Now, take $\\lambda\\in [0,1]$ and consider the $\\lambda$-return $R^\\lambda_t$:\n",
    "<div class=\"alert alert-success\"><b>$\\lambda$-return:</b>\n",
    "$$R^\\lambda_t = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^\\infty \\lambda^{n-1}R_t^{(n)}$$\n",
    "</div>\n",
    "\n",
    "The $\\lambda$-return is the mixing of *all* $n$-step returns, with weights $(1-\\lambda) \\lambda^{n-1}$. So, an agent performing a $\\lambda$-return update looks one step in the future and uses that step to update $V(s)$ with weight $(1-\\lambda)$, then looks 2 steps into the future and updates $V(s)$ with a weight $\\lambda (1-\\lambda)$ and so on. The illustrative figure below is an excerpt from **Reinforcement Learning: an introduction** by Sutton and Barto.\n",
    "\n",
    "<img src=\"images/TD_lambda_forward.png\"></img>\n",
    "\n",
    "To get a better understanding of the $\\lambda$-return and to set ideas, let us consider a finite length episode $(s_t, r_t, s_{t+1}, \\ldots, s_T)$. Since the episode ends after $T$, we have $\\forall k>0, \\ R^{(T-t+k)}_t = R_t$. Thus, we can split the $\\lambda$-return sum in two:\n",
    "\n",
    "\\begin{align*}\n",
    "R^\\lambda_t & = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^{T-t-1} \\lambda^{n-1}R_t^{(n)} + \\left(1-\\lambda\\right) \\sum\\limits_{n=T-t}^{\\infty} \\lambda^{n-1}R_t^{(n)}\\\\\n",
    "& = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^{T-t-1} \\lambda^{n-1}R_t^{(n)} + \\left(1-\\lambda\\right) \\lambda^{T-t-1} \\sum\\limits_{n=T-t}^{\\infty} \\lambda^{n-T+t} R_t^{(n)}\\\\\n",
    "& = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^{T-t-1} \\lambda^{n-1}R_t^{(n)} + \\left(1-\\lambda\\right) \\lambda^{T-t-1} \\sum\\limits_{k=0}^{\\infty} \\lambda^{k} R_t^{(T-t+k)}\\\\\n",
    "& = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^{T-t-1} \\lambda^{n-1}R_t^{(n)} + \\lambda^{T-t-1} R_t\\\\\n",
    "\\end{align*}\n",
    "\n",
    "So we have $R^\\lambda_t = \\left(1-\\lambda\\right) \\sum\\limits_{n=1}^{T-t-1} \\lambda^{n-1}R_t^{(n)} + \\lambda^{T-t-1} R_t$.\n",
    "- When $\\lambda = 0$, it is a $TD(0)$ update (hence the \"0\" in TD(0)).\n",
    "- When $\\lambda = 1$, it is a MC update.\n",
    "So we can define the **$\\lambda$-return algorithm** that generalizes on TD(0) and MC:\n",
    "<div class=\"alert alert-success\"><b>$\\lambda$-return algorithm:</b>\n",
    "$$V(s_t) \\leftarrow V(s_t) + \\alpha \\left[R^{\\lambda}_t - V(s_t)\\right] $$\n",
    "</div>\n",
    "\n",
    "That's all very nice and we have replaced the choice of $n$ by the choice of $\\lambda$ that seems less sensitive. But, still, we don't know how to compute those $n$-step returns, and the $\\lambda$-return, without running $n$-step episodes (and thus infinite episodes for the $\\lambda$-return in the general case).\n",
    "\n",
    "This is where we need to flip the little man in the drawing above to make him look backwards in time. When an agent transitions from $s$ to $s'$ and obtains reward $r$, it can compute the $1$-step return for $s$ and perform the corresponding $1$-step TD update. Then, as it transitions from $s'$ to $s''$ and observes $r'$ it can perform the $1$-step TD update in $s'$, but also the $2$-step TD update in $s$! An so on for future transitions. So, incrementally, as time unrolls, the agent will include the $n$-step updates in the $\\lambda$-return of $s$ as they become available. In the limit, when $t\\rightarrow\\infty$, the $\\lambda$-return in every state will be complete and the agent will have completed a $\\lambda$-return algorithm. This figure below (excerpt from **Reinforcement Learning: an introduction** by Sutton and Barto) illustrates this *backward-view* on TD updates.\n",
    "\n",
    "<img src=\"images/TD_lambda_backward.png\"></img>\n",
    "\n",
    "This seems to imply that we need to remember the states we went through, which is quite the same as remembering full episodes for MC updates. But since we want to update a state seen $n$ steps ago with a weight $\\lambda^n (1-\\lambda)$, we just need to remember, for each state, the last time we visited it (and we can forget about the trajectory linking states together). This way, we store $|S|$ values at all time, instead of an increasingly long sequence of transitions. In order to do this, we introduce the notion of **eligibility trace**:\n",
    "<div class=\"alert alert-success\"><b>Eligibility trace of state $s$:</b>\n",
    "$$e_t(s) = \\left\\{\\begin{array}{ll}\n",
    "\\gamma \\lambda e_{t-1}(s) & \\textrm{if }s\\neq s_t\\\\\n",
    "1 & \\textrm{if }s = s_t\n",
    "\\end{array}\\right.$$\n",
    "</div>\n",
    "Initially, all states have an eligibility trace of zero. The eligibility trace of an unvisited state decays exponentially. So $e_t(s)$ measures how old the last visit of $s$ is.<br>\n",
    "<br>\n",
    "Note that two alternative definitions of eligibility traces prevail:\n",
    "<ul>\n",
    "    <li> \"<b>replacing traces</b>\": $e_t(s) = 1\\textrm{ if }s = s_t$\n",
    "    <li> \"<b>accumulating traces</b>\": $e_t(s) = e_{t-1}(s) + 1\\textrm{ if }s = s_t$\n",
    "</ul>\n",
    "Often (not always), replacing traces are used in practice.<br>\n",
    "<br>\n",
    "And finally we can define the TD($\\lambda$) algorithm:\n",
    "<div class=\"alert alert-success\"><b>TD($\\lambda$) algorithm:</b><br>\n",
    "Given a new sample $(s_t,a_t,r_t,s_t')$.\n",
    "<ol>\n",
    "<li> Temporal difference $\\delta = r_t+\\gamma V(s_t') - V(s_t)$.\n",
    "<li> Update eligibility traces for all states<br>\n",
    "$e(s) \\leftarrow \\left\\{\\begin{array}{ll}\n",
    "\\gamma \\lambda e(s) & \\textrm{if } s\\neq s_t\\\\\n",
    "1 & \\textrm{if } s=s_t\n",
    "\\end{array}\\right.$\n",
    "<li> Update all state's values $V(s) \\leftarrow V(s) + \\alpha e(s) \\delta$\n",
    "</ol>\n",
    "Initially, $e(s)=0$.\n",
    "</div>\n",
    "\n",
    "Properties and remarks:\n",
    "- Earlier states are given $e(s)$ *credit* for the TD error $\\delta$\n",
    "- If the environment contains terminal states, then $e$ should be reset to zero whenever a new trajectory begins.\n",
    "- If $\\lambda=0$, $e(s)=0$ except in $s_t$ $\\Rightarrow$ standard TD(0)\n",
    "- For $0<\\lambda<1$, $e(s)$ indicates a distance $s \\leftrightarrow s_t$ is in the episode.\n",
    "- If $\\lambda=1$, $e(s)=\\gamma^\\tau$ where $\\tau=$ duration since last visit to $s_t$ $\\Rightarrow$ MC method<br>\n",
    "TD(1) implements Monte Carlo estimation on non-episodic problems!<br>\n",
    "TD(1) learns incrementally for the same result as MC\n",
    "- **TD($\\lambda$) is equivalent to the $\\lambda$-return algorithm.**\n",
    "- The value of $\\lambda$ can even be changed during the algorithm without impacting convergence.\n",
    "\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Implement a TD($\\lambda$) algorithm to estimate $V^\\pi$. As before, take a constant $\\alpha=0.001$ and $\\lambda=0.5$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# parameters\n",
    "gamma = 0.9\n",
    "lambd = 0.5\n",
    "alpha = 0.001\n",
    "max_steps = 2000000\n",
    "V = np.zeros((env.observation_space.n))\n",
    "e = np.zeros((env.observation_space.n))\n",
    "\n",
    "# error plotting\n",
    "error = np.zeros((max_steps)) # used to track the convergence to Vtrue\n",
    "\n",
    "x = env.reset()\n",
    "for t in range(max_steps):\n",
    "    y,r,d,_ = env.step(fl.RIGHT)\n",
    "    delta = r+gamma*V[y]-V[x]\n",
    "    for s in range(env.observation_space.n):\n",
    "        if s==x:\n",
    "            e[s] = 1\n",
    "        else:\n",
    "            e[s] = e[s]*gamma*lambd\n",
    "        V[s] = V[s] + alpha * e[s] * delta\n",
    "    error[t] = np.max(np.abs(V-Vtrue))\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "        e = np.zeros((env.observation_space.n))\n",
    "    else:\n",
    "        x=y\n",
    "\n",
    "print(V)\n",
    "print(Vtrue)\n",
    "plt.plot(error)\n",
    "plt.figure()\n",
    "plt.semilogy(error);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"predsummary\"></a>Summary\n",
    "\n",
    "- Prediction = evaluation of a given behaviour\n",
    "- Model-based prediction\n",
    "- Monte Carlo (offline and online)\n",
    "- Temporal Differences, TD(0)\n",
    "- Unifying MC and TD: TD($\\lambda$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"approx\"></a>Value Function approximation\n",
    "\n",
    "If this is the first time you read this notebook, this part can be skipped (but please come back later, it's still quite important).\n",
    "\n",
    "Often, $S$ is not finite (or is just too large to be enumerated). Consequently, $\\mathcal{F}(S,\\mathbb{R})$ has infinite (or just too large) dimension. Thus, tabular representations of $V$ are not possible and one needs to turn to the function representation $V_\\theta$ with parameters $\\theta$. In this section, we work our way through approximation methods for $V$.\n",
    "\n",
    "The FrozenLake example is a toy problem with very few states (moreover discrete). It does not lend itself to a convincing demonstration of value function approximation. We shall remain at the theoretical level for the following considerations and reserve practice for later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"linear\"></a>Linear value function approximation\n",
    "\n",
    "Suppose we write $V$ as a linear model:\n",
    "$$V(s) = \\theta^T \\varphi(s) = \\sum_{i=1}^K \\theta_i \\varphi_i(s)$$\n",
    "\n",
    "We wish to approximate $V(s)$ as a linear combination of features $\\varphi(s)=\\left(\\varphi_i(s)\\right)_{i\\in[1,K]}$. This way, $V$ lives in the $K$-dimensional function space $span(\\varphi)$. We have plenty of families of functions that we can rely on and the user's expertise plays a big role in choosing a proper **functional basis**. Generally speaking, we would expect the following properties from a good basis:\n",
    "- the target $V^\\pi$ can be closely approximated by its projection on $\\varphi$\n",
    "- given an initial $V_0 \\in span(\\varphi)$ and the recurrence relation $V_{n+1} = \\Pi_\\varphi (T^\\pi V_n)$ (where $\\Pi_\\varphi$ is the projection operator on $span(\\varphi)$), $V_n$ should be a \"close enough\" approximation of $T^\\pi V_n$. This property is illustrated by the figure below (for $Q$ instead of $V$ - excerpt from Lagoudakis and Parr, 03).\n",
    "- $\\varphi$ should form a basis (that is $\\varphi_i \\bot \\varphi_j$)\n",
    "\n",
    "<img src=\"images/projection.png\" style=\"width: 600px;\"></img>\n",
    "\n",
    "If $\\sum_{i=1}^K \\varphi_i(s) = 1$, then $V_\\theta$ is called an *averager*. Averagers are known to be well-behaved for iterative function approximation. Otherwise, other non-averager, families of functions are commonly used:\n",
    "\n",
    "- $\\cos$, $\\sin$ over state variables (mimics the Fourier transform, extends to wavelet bases)\n",
    "- polynomials of the state variables (mimics the Taylor expansion)\n",
    "- radial basis functions of the state variables (performs local approximation, extends to kernel smoothing).\n",
    "- among averagers, piecewise constant local functions $\\varphi_i(s) \\in \\{0;1\\}$ group *neighborhoods* in the state space together (note the similarity with tree-based regressors).\n",
    "\n",
    "A very straightforward way of building feature sets is to define features depending on a single state variable and then using the tensor product in order to obtain all possible combinations of sigle-variable features. More formally and more generally, suppose $S \\subset S_1\\times \\ldots \\times S_k$ and suppose $\\varphi^{(i)}$ defines $d_i$ features over $S_k$; then the tensor product $\\varphi^{(1)} \\otimes \\ldots \\otimes \\varphi^{(k)}$ yields $d=d_1\\ldots d_k$ feature functions on $S$. But there is a catch, the number of these resulting features grows exponentially with $k$ and so does the dimension of the value function's search space $span(\\varphi)$: that is the **curse of dimensionality** that makes searching for a value function exponentially more difficult as the state space dimension grows.\n",
    "\n",
    "Additionnaly, there is **no guarantee** that, for a given $V_n \\in span(\\varphi)$, $T^\\pi V_n$ actually lives in $span(\\varphi)$.\n",
    "\n",
    "But on the bright side, given an initial state $s_0$, the actual reachable space $S'$ given $\\pi$ might be much smaller than $S$. So, in practice, we just need to obtain a good approximation of $V$ on the subspace $S'$ (a manifold of $S$).\n",
    "\n",
    "Anyway, to conclude this short paragraph on feature engineering:\n",
    "- good feature engineering in RL is even more crucial than in supervized learning.\n",
    "- it can be very problem-dependent.\n",
    "- good function approximators (generally non-parametric to avoid the fixed $span(\\varphi)$) are of crucial importance.\n",
    "We will discuss non-linear and non-parametric function approximation a bit further in the notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"tab\"></a>The tabular case is just a specific case of linear model\n",
    "\n",
    "In the discrete state space case, consider the averager defined as:\n",
    "$$\\varphi_i(s) = \\left\\{\\begin{array}{ll}1 & \\textrm{if }s=s_i\\\\ 0 & \\textrm{otherwise}\\end{array}\\right.$$\n",
    "Feature function $\\varphi_i$ is the indicator function of state $s_i$. Therefore, we have $|S|$ feature functions. So when we write $V(s) = \\sum_{i=1}^{|S|} \\theta_i \\varphi_i(s)$, we actually have $V(s_i) = \\theta_i$. Therefore the tabular representation of $V$ is equivalent to a linear model with the $\\varphi_i$ feature functions.\n",
    "\n",
    "Based on the previous remark, let us rewrite TD($\\lambda$) as a linear model update (we take the accumulating traces version; the replacing traces case is equivalent). We had previously:<br>\n",
    "Given a new sample $(s_t,a_t,r_t,s_t')$.\n",
    "<ol>\n",
    "<li> Temporal difference $\\delta = r_t+\\gamma V(s_t') - V(s_t)$.\n",
    "<li> Update eligibility traces for all states<br>\n",
    "$e(s) \\leftarrow \\left\\{\\begin{array}{ll}\n",
    "\\gamma \\lambda e(s) & \\textrm{if } s\\neq s_t\\\\\n",
    "1 + \\gamma \\lambda e(s)& \\textrm{if } s=s_t\n",
    "\\end{array}\\right.$\n",
    "<li> Update all state's values $V(s) \\leftarrow V(s) + \\alpha e(s) \\delta$\n",
    "</ol>\n",
    "Initially, $e(s)=0$.\n",
    "\n",
    "The temporal difference can be rewritten $\\delta = r_t+\\gamma\\theta^T \\varphi(s_t') - \\theta^T \\varphi(s_t)$.\n",
    "\n",
    "The eligibility trace update can be rewritten $e \\leftarrow \\varphi(s) + \\gamma \\lambda e$.\n",
    "\n",
    "Similarly the value update can be rewritten $\\theta \\leftarrow \\theta + \\alpha e \\delta$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"param\"></a>TD($\\lambda$) as a parametric model update\n",
    "\n",
    "We generalize the previous result to the general linear model case:\n",
    "<div class=\"alert alert-success\"><b>TD($\\lambda$) with linear model approximation:</b><br>\n",
    "With $V(s) = \\sum_{i=1}^K \\theta_i \\varphi_i(s)$, $e \\in \\mathbb{R}^K$.<br>\n",
    "Initially, $e=0$.<br>\n",
    "Given a new sample $(s_t,a_t,r_t,s_t')$.\n",
    "<ol>\n",
    "<li> Temporal difference $\\delta = r_t+\\gamma\\theta^T \\varphi(s_t') - \\theta^T \\varphi(s_t)$.\n",
    "<li> Update eligibility traces for all states $e \\leftarrow \\varphi(s) + \\gamma \\lambda e$\n",
    "<li> Update value function $\\theta \\leftarrow \\theta + \\alpha e \\delta$\n",
    "</ol>\n",
    "</div>\n",
    "\n",
    "And finally, we can further generalize the TD($\\lambda$) update above to the general case of a parametric (not necessarily linear) function approximation $V_\\theta$:\n",
    "<div class=\"alert alert-success\"><b>TD($\\lambda$) with parametric function approximation:</b><br>\n",
    "With $V(s) = V_\\theta(s), \\theta \\in \\mathbb{R}^K$, $e \\in \\mathbb{R}^K$.<br>\n",
    "Initially, $e=0$.<br>\n",
    "Given a new sample $(s_t,a_t,r_t,s_t')$.\n",
    "<ol>\n",
    "<li> Temporal difference $\\delta = r_t+\\gamma V_\\theta(s_t') - V_\\theta(s_t)$.\n",
    "<li> Update eligibility traces for all states $e \\leftarrow \\nabla_\\theta V_\\theta(s) + \\gamma \\lambda e$\n",
    "<li> Update value function $\\theta \\leftarrow \\theta + \\alpha e \\delta$\n",
    "</ol>\n",
    "</div>\n",
    "\n",
    "Note that we have provided the results above without proof. We will admit them and refer the reader to RL textbooks for a rigorous justification."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"nonparam\"></a>Non-parametric models\n",
    "\n",
    "Non-parametric models generally refer to function approximators that do not rely on an a-priori fixed finite-dimensional search space and allows the representation space to evolve as needed. Among those non-parametrics models, one can count:\n",
    "- linear approximations that incrementally enrich the functional basis.\n",
    "- general supervised learning methods: SVMs, k-nearest neighbours (kernel smoothing methods), Gaussian Processes, tree-based methods, neural networks, etc.\n",
    "\n",
    "One quickly realizes that the frontier between parametric and non-parametric models is blur. The TD($\\lambda$) update above actually holds for most methods for which a finite dimensional parameter vector $\\theta$ exists (even though the function search space changes). In the general case of a $s \\mapsto V(s)$ function approximator, the general idea is to feed this approximator with samples of the form $(s, r+\\gamma V(s'))$.\n",
    "\n",
    "## <a id=\"conc-FA\"></a>Conclusion on function approximation\n",
    "\n",
    "To conclude this overview of value function approximation issues. We make the following remarks:\n",
    "- TD($\\lambda$) is an on-policy method.<br>\n",
    "Indeed, it evaluates the policy currently applied. But one could wonder: could I apply some policy and still evaluate another one. It appears this question is non-trivial and a direct extension of TD($\\lambda$) to the off-policy case is actually non-convergent. This was solved after 2009 by the family of **Gradient temporal difference learning** algorithms.\n",
    "- TD methods solve the $V = T^\\pi V$ equation.<br>\n",
    "Then, one could see those methods as algorithms that incrementally minimize $\\|V-T^\\pi V\\|^2$, that is, least squares minimizers. This leads to the (vast) family of **Least Squares methods** that often provide good stability and accuracy properties at the cost of increased computational requirements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "47.7167px",
    "left": "1170px",
    "top": "32.5667px",
    "width": "159px"
   },
   "toc_section_display": false,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}