RL3 - Control problems, model-free Policy Optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Class 3: Control problems, model-free Policy Optimization.**\n",
    "\n",
    "1. [Everything you need to know](#everything)\n",
    "2. [General view on policy optimization: Generalized Policy Iteration and Actor-Critic architectures](#GPI)\n",
    "3. [Online problems, the exploration vs. exploitation dilemma](#online)\n",
    "    1. [SARSA](#sarsa)\n",
    "    2. [Q-learning](#qlearning)\n",
    "    3. [Going further with SARSA and Q-learning](#further)\n",
    "4. [Interactive problems](#interactive)\n",
    "5. [Offline problems, focussing on the critic alone](#offline)\n",
    "    1. [Fitted Q-iteration](#fqi)\n",
    "    2. [Least Squares Policy Iteration](#lspi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"everything\"></a>Everything you need to know\n",
    "\n",
    "Everything you should remember after this session.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-success\">\n",
    "<ul>\n",
    "<li> Generalized Policy Iteration: perform sample-based policy evaluation and policy improvement, directly from samples (not from the model anymore), converge to $Q^*$ and $\\pi^*$\n",
    "<li> Actor-critic architecture: the actor chooses an action based on the current state and the information provided by the critic, while the critic constantly aims at learning relevant things in order to help the actor decide (value functions for example, or an approximate model).\n",
    "<li>A GLIE actor guarantees that, as $t\\rightarrow\\infty$, 1) all state-action pairs $(s,a)$ are visited infinitely often for $Q$-updates of the critic and 2) the actor's policy $\\pi$ becomes $Q$-greedy.\n",
    "<li>SARSA. Initialize : in $s$, choose (*actor*) $a$ using $Q$, then repeat:\n",
    "<ol>\n",
    "<li> Observe $r$, $s'$\n",
    "<li> Choose $a'$ (<i>GLIE actor<i>) using $Q$\n",
    "<li> Temporal difference: $\\delta=r+\\gamma Q(s',a') - Q(s,a)$\n",
    "<li> Update $Q$: $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\delta$\n",
    "<li> $s\\leftarrow s'$, $a\\leftarrow a'$\n",
    "</ol>\n",
    "<li>Q-learning.\n",
    "<ol>\n",
    "<li> In $s$, choose $a$ (<i>GLIE actor<i>)\n",
    "<li> Observe $r$, $s'$\n",
    "<li> Temporal difference: $\\delta=r+\\gamma \\max_{a'} Q(s',a') - Q(s,a)$\n",
    "<li> Update $Q$: $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\delta$\n",
    "<li> $s\\leftarrow s'$\n",
    "</ol>\n",
    "<li> Fitted Q-iteration (offline learning). For $i=1$ to $N$:\n",
    "<ol>\n",
    "<li> For each sample $(s,a,r,s')$, define $(x,y)$ with:<br>\n",
    "$x = (s,a)$<br>\n",
    "$y = r + \\gamma \\max_{a'} Q_{i-1}(s',a')$<br>\n",
    "Call $\\mathcal{T}$ the training set $\\left\\{(x,y)\\right\\}$\n",
    "<li> $Q_i$ = fit_model$(\\mathcal{T})$\n",
    "</ol>\n",
    "<li> Least Squares Policy Iteration (LSPI) uses the LSTD$Q$ (Least Squares Temporal Differences on $Q$ functions) procedure to approximate the $Q$ function of the current policy, using a set of feature functions $\\varphi$, then replaces the current policy with the $Q$-greedy policy and iterates until convergence.\n",
    "<li> LSTD$Q$ (incremental version):<br>\n",
    "$\\tilde{B} = \\frac{1}{\\delta}I$ with $\\delta$ a small positive value.<br>\n",
    "$\\tilde{b} = 0$<br>\n",
    "For each $(s,a,r,s') \\in \\mathcal{D}$:<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\\tilde{B} \\leftarrow \\tilde{B} - \\frac{B \\varphi(s,a) \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\pi(s')) \\right)^T B}{1 + \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\pi(s')) \\right)^T B \\varphi(s,a)} $<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\\tilde{b} \\leftarrow \\tilde{b} + \\varphi(s,a) r$<br>\n",
    "return $w_\\pi = \\tilde{B} b$\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=\"gpi\"></a>General view on policy optimization: Generalized Policy Iteration and Actor-Critic architectures\n",
    "\n",
    "Remember how we went from Policy Iteration (figure below) to Asynchronous Policy Iteration?\n",
    "<img src=\"images/policyiteration.png\"></img>\n",
    "\n",
    "Now recall the principle of Asynchronous Policy Iteration. If we consider the two elementary operations:\n",
    "- Bellman backup on $Q$: $Q(s,a) \\leftarrow r(s,a) + \\gamma \\sum\\limits_{s'} p(s'|s,a) Q(s',\\pi(s'))$\n",
    "- Bellman backup on $\\pi$: $\\pi(s) \\leftarrow \\arg\\max_{a} Q(s,a)$\n",
    "\n",
    "Then, as long as every state and every action is visited infinitely often for Bellman backups on $Q$ or $\\pi$, the sequences of $Q_n$ and $\\pi_n$ converge to $Q^*$ and $\\pi^*$.\n",
    "\n",
    "Value Iteration: in each state, one update of $Q$ and one improvement of $\\pi$.<br>\n",
    "Policy Iteration: update $Q$ in all states until convergence, then update $\\pi$ in all states.\n",
    "\n",
    "**Generalized Policy Iteration** is the case where one has two interacting processes: policy evaluation and policy improvement, directly from samples (not from the model anymore). If these processes converge to their respective targets, then Generalized Policy Iteration converges to $Q^*$ and $\\pi^*$. Model-free policy evaluation can take many forms: indirect RL, Monte Carlo evaluations, TD methods...\n",
    "\n",
    "This leads to the definition of the general **actor-critic architectures** (excerpt from **Algorithms for Reinforcement Learning** by C. Szepesvari):\n",
    "\n",
    "<img src=\"images/actor-critic.png\"  style=\"width: 500px;\"></img>\n",
    "\n",
    "In such architectures, an *actor* chooses an action based on the current state and the information provided by the *critic*, while the *critic* constantly aims at learning relevant things in order to help the *actor* decide (value functions for example, or an approximate model).\n",
    "\n",
    "Almost all Reinforcement Learning algorithms fall into an actor-critic architecture. The following sections separate the search for optimal policies / value functions into two distinct contexts:\n",
    "<ul>\n",
    "<li> Online interaction. The actor needs to balance exploration of new state-action pairs with the exploitation of those which are already known to be good (in order to guide the agent along reward-providing trajectories and to refine the knowledge of the value function around these trajectories). The critic aims at providing the best evaluation of state-action pairs to the actor. In this context, we derive two algorithms:\n",
    "<ul>\n",
    "<li>SARSA, where the critic evaluates the current policy being applied.\n",
    "<li>Q-learning, where the critic evaluates the optimal policy.<br>\n",
    "</ul>\n",
    "In particular, online learning is characterized by the fact that the agent chooses the action to perform, but is constrained by the state dynamics and thus does not choose the states to sample. One can think of this case as the direct interaction with an environment.\n",
    "<li> Interactive problems. These only differ from the online case by the fact that both sampled states and actions can be controled by the learning process. Think of this case as one where one has a simulator and can choose to reset it to any state before deciding on the action to undertake.\n",
    "<li> Offline policy search. In this case, there simply is no actor and the problem boils down to designing a critic that provides $Q^*$. For this problem, we explore two generalizations of Value Iteration and Policy Iterations, respectively:\n",
    "<ul>\n",
    "<li>Fitted Q-Iteration\n",
    "<li>Least Squares Policy Iteration\n",
    "</ul>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"online\"></a>Online problems, the exploration vs. exploitation dilemma\n",
    "\n",
    "In the class on value estimation problems, we introduced temporal differences algorithms such as TD(0), so we have a way to evaluate policies. But now, we are not looking for $V^\\pi$ anymore (or $Q^\\pi$), but for $Q^*$. Let's recall TD(0) on $Q$ functions. Given a sample $(s,a,r,s')$:\n",
    "$$Q(s,a) \\leftarrow Q(s,a) + \\alpha \\left( r + \\gamma Q(s',\\pi(s')) - Q(s,a) \\right)$$\n",
    "Recall that for this update to converge, we need samples for all state-action pairs $(s,a)$.\n",
    "\n",
    "Using TD(0) (or a Monte Carlo estimator), we could easily design an approximate policy iteration algorithm that evaluates $\\pi$ for a certain time, yielding a value function $Q$, then replaces $\\pi$ with the $Q$-greedy policy and starts over. So the key question becomes knowing when to switch from evaluation of $\\pi$ to improvement. As we have seen in Generalized Policy Iteration, we can interleave those two processes.\n",
    "\n",
    "For an agent interacting with a new, unknown environment, let's first learn the $Q$-function of a given policy $\\pi$. The key problem is to insure all state-action pairs will be sampled. To do this, we can make an **ergodocity** assumption on our MDP, that is we can suppose that each state is reachable from any other (non-terminal) state with non-zero probability. Therefore, acting randomly insures exploration of all state-action pairs.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Let's implement that on the policy that always goes right in the FrozenLake environment.\n",
    "<ul>\n",
    "<li> We will start by using the class on MDPs to obtain the true value of $Q^\\pi$.\n",
    "<li> We will also reproduce the TD(0) estimation of $V^\\pi$ from the class on value estimation.\n",
    "<li> Then we will use it to initialize $Q$ and implement the TD(0) update that converges to $Q^\\pi$.\n",
    "</ul>\n",
    "As before, to keep things simple, we set $\\alpha=0.001$ and we take $\\gamma=0.9$.\n",
    "</div>"
   ]
  },
  {
   "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": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "env = gym.make('FrozenLake-v0')\n",
    "actions = {fl.LEFT: '\\u2190', fl.DOWN: '\\u2193', fl.RIGHT: '\\u2192', fl.UP: '\\u2191'}"
   ]
  },
  {
   "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",
    "Qpi0true, residuals = policy_Qeval_iter(pi0,1e-4,10000)\n",
    "print(\"Qtrue:\\n\", Qpi0true)\n",
    "print(\"number of iterations:\", residuals.size)\n",
    "plt.plot(residuals)\n",
    "plt.figure()\n",
    "plt.semilogy(residuals)\n",
    "\n",
    "Vpi0true = np.zeros((env.observation_space.n))\n",
    "for x in range(env.observation_space.n):\n",
    "    Vpi0true[x] = Qpi0true[x][pi0[x]]\n",
    "print(\"Vtrue:\\n\", Vpi0true)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TD(0) evaluation of Vpi\n",
    "def TD_Veval(pi, max_steps, V=None, Vtrue=None):\n",
    "    if(V is None):\n",
    "        V = np.zeros((env.observation_space.n))\n",
    "    error = np.zeros((max_steps))\n",
    "    x = env.reset()\n",
    "    for t in range(max_steps):\n",
    "        y,r,d,_ = env.step(pi[x])\n",
    "        V[x] = V[x] + alpha * (r+gamma*V[y]-V[x])\n",
    "        if(Vtrue is not None):\n",
    "            error[t] = np.max(np.abs(V-Vtrue))\n",
    "        if d==True:\n",
    "            x = env.reset()\n",
    "        else:\n",
    "            x=y\n",
    "    return V, error\n",
    "\n",
    "Vpi0, error = TD_Veval(pi0, 1000000, Vtrue=Vpi0true)\n",
    "print(Vpi0)\n",
    "print(Vpi0true)\n",
    "plt.plot(error)\n",
    "plt.figure()\n",
    "plt.semilogy(error);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# TD(0) evaluation of Qpi\n",
    "Qpi0 = np.transpose(np.tile(Vpi0, (4,1)))\n",
    "\n",
    "def TD_Qeval(pi, max_steps, Q=None, Qtrue=None):\n",
    "    error = np.zeros((max_steps))\n",
    "    if (Q is None):\n",
    "        Q = np.zeros((env.observation_space.n, env.action_space.n))\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][pi[y]]-Q[x][a])\n",
    "        if(Qtrue is not None):\n",
    "            error[t] = np.max(np.abs(Q-Qtrue))\n",
    "        if d==True:\n",
    "            x = env.reset()\n",
    "        else:\n",
    "            x=y\n",
    "    return Q, error\n",
    "\n",
    "Qpi0, error = TD_Qeval(pi0,3000000,Qpi0,Qpi0true)\n",
    "print(\"Max error:\", np.max(np.abs(Qpi0-Qpi0true)))\n",
    "plt.plot(error)\n",
    "plt.figure()\n",
    "plt.semilogy(error);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we have a way of evaluating $Q^\\pi$. But we're interested in $Q^*$. Let's use the idea of Generalized Policy Iteration and include, inside the TD(0) loop above, the policy improvement phase $\\pi(s) \\leftarrow \\arg\\max_a Q(s,a)$. This means that at each time step, instead of evaluating the temporal difference for a fixed policy $\\pi$, we evaluate a policy that is $Q$-greedy. According to the convergence property of Generalized Policy Iteration, this should converge to $Q^*$. But then again, the policy applied by our agent remains totally random so it clearly does not converge to $\\pi^*$. To solve this issue we introduce the notion of **Greedy in the limit of infinite exploration** (GLIE) actor:<br>\n",
    "<br>\n",
    "<div class=\"alert alert-success\"><b>Greedy in the limit of infinite exploration</b> (GLIE) actor:<br>\n",
    "A GLIE actor guarantees that:<br>\n",
    "- All state-action pairs $(s,a)$ are visited infinitely often for updates of $Q$, as $t\\rightarrow\\infty$:\n",
    "$$\\lim_{t\\rightarrow\\infty} count_t(s,a) = \\infty$$\n",
    "- As $t\\rightarrow\\infty$ the actor becomes $Q$-greedy, that is:\n",
    "$$\\lim_{t\\rightarrow\\infty} \\pi_t(a|s) = \\mathbb{1}\\left(a = \\arg\\max_{\\hat{a}} Q(s,\\hat{a})\\right)$$\n",
    "</div>\n",
    "\n",
    "An example of GLIE actor is the so-called $\\epsilon$-greedy exploration strategy that uniformly picks a non-greedy action with probability $\\epsilon$:\n",
    "$$\\pi_t(a|s) = \\left\\{\\begin{array}{ll}1-\\epsilon_t & \\textrm{if }a=\\arg\\max_{\\hat{a}} Q(s,\\hat{a})\\\\\n",
    "\\frac{\\epsilon_t}{|A|-1} & \\textrm{otherwise} \\end{array}\\right.$$\n",
    "With a parameter $\\epsilon_t>0$ that goes to zero as $t$ tends to $\\infty$, one obtains a GLIE actor.\n",
    "\n",
    "GLIE actors (or policies) enforce the limits of the **exploration vs. exploitation compromise**. As long as actors respect the GLIE properties, actor-critic architectures fall within the convergence properties of Generalized Policy Iteration.\n",
    "\n",
    "With this last definition, we have all the ingredients to define algorithms that evolve to an optimal behaviour.\n",
    "\n",
    "<a href=\"#GLIEremark\" data-toggle=\"collapse\"> A remark</a><br>\n",
    "<div id=\"GLIEremark\" class=\"collapse\">\n",
    "You might have noticed that the totally random policy we applied in the TD(0) update was a very naive choice. Even if all states are reachable from anywhere in the state space (ergodicity property), they might not all be visited with the same frequency and therefore the convergence to $Q^\\pi$ might be delayed because of this uniform exploration strategy.<br>\n",
    "<br>\n",
    "The same remark applies to $\\epsilon$-greedy exploration strategies that often start with $\\epsilon=1$ and let it slowly decrease towards zero. These strategies don't account for the actual *visitation frequencies* of state-action pairs. In some states it might be good to keep a strong exploration probability because they actually have been seldom visited, while in other states, a faster decrease is desirable. This links also to the question of *value propagation* that was underpinned by the asynchronous value iteration remarks in the class on MDPs.<br>\n",
    "<br>\n",
    "The point here is to notice that $\\epsilon$-greedy is a simple, very naive exploration strategy that fits within the GLIE requirements but that much better exploration policies are possible by taking the current state into account (contextual exploration) or by using the values of the temporal difference (prioritized experience replay) and the $Q$ estimate (Boltzmann policies, $E^3$ or $R_{max}$ strategies) for instance.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"sarsa\"></a>SARSA\n",
    "\n",
    "The key idea behind the SARSA algorithm is to build a critic that constantly tries to evaluate the value $Q$ of the actor's policy $\\pi$, and an actor that tends to be greedy with respect to this critic. The algorithm is written:\n",
    "\n",
    "<div class=\"alert alert-success\"><b>SARSA</b><br>\n",
    "In $s$, choose (*actor*) $a$ using $Q$, then repeat:\n",
    "<ol>\n",
    "<li> Observe $r$, $s'$\n",
    "<li> Choose $a'$ (<i>GLIE actor</i>) using $Q$\n",
    "<li> Temporal difference: $\\delta=r+\\gamma Q(s',a') - Q(s,a)$\n",
    "<li> Update $Q$: $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\delta$\n",
    "<li> $s\\leftarrow s'$, $a\\leftarrow a'$\n",
    "</ol>\n",
    "SARSA converges if the actor is GLIE and if $\\alpha$ respects the Robbins-Monro conditions.\n",
    "</div>\n",
    "\n",
    "It is important to note that SARSA is an **on-policy** critic: it constantly evaluates the current $\\pi$... that constantly shifts towards $\\pi^*$ by being $Q$-greedy.\n",
    "\n",
    "The name SARSA comes from the usage of an augmented sample $(s,a,r,s',a')$.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Let's implement an $\\epsilon$-greedy SARSA on the FrozenLake problem.<br>\n",
    "For the decrease of $\\epsilon$ we can opt for a division by 2 every million steps.<br>\n",
    "You can compare with $Q^*$ and $\\pi^*$ obtained during the model-based class.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Model-based policy optimization and a few utility functions\n",
    "\n",
    "def value_iteration(V,epsilon,max_iter):\n",
    "    W = np.copy(V)\n",
    "    residuals = np.zeros((max_iter))\n",
    "    for i in range(max_iter):\n",
    "        for s in range(env.observation_space.n):\n",
    "            Q = np.zeros((env.action_space.n))\n",
    "            for a in range(env.action_space.n):\n",
    "                outcomes = env.unwrapped.P[s][a]\n",
    "                for o in outcomes:\n",
    "                    p  = o[0]\n",
    "                    s2 = o[1]\n",
    "                    r  = o[2]\n",
    "                    Q[a] += p*(r+gamma*V[s2])\n",
    "            W[s] = np.max(Q)\n",
    "            #print(W[s])\n",
    "        residuals[i] = np.max(np.abs(W-V))\n",
    "        #print(\"abs\", np.abs(W-V))\n",
    "        np.copyto(V,W)\n",
    "        if residuals[i]<epsilon:\n",
    "            residuals = residuals[:i+1]\n",
    "            break\n",
    "    return V, residuals\n",
    "\n",
    "def Q_from_V(V):\n",
    "    Q = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "    for s in range(env.observation_space.n):\n",
    "        for a in range(env.action_space.n):\n",
    "            outcomes = env.unwrapped.P[s][a]\n",
    "            for o in outcomes:\n",
    "                p  = o[0]\n",
    "                s2 = o[1]\n",
    "                r  = o[2]\n",
    "                Q[s,a] += p*(r+gamma*V[s2])\n",
    "    return Q\n",
    "\n",
    "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 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",
    "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",
    "Vinit = np.zeros((env.observation_space.n))\n",
    "Vstar,residuals = value_iteration(Vinit,1e-4,1000)\n",
    "Qstar = Q_from_V(Vstar)\n",
    "print(actions)\n",
    "print(Vstar)\n",
    "print(Qstar)\n",
    "pi_star = greedyQpolicy(Qstar)\n",
    "print_policy(pi_star)\n",
    "env.render();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's restart from Qpi0\n",
    "Qsarsa = Qpi0\n",
    "max_steps = 5000000\n",
    "\n",
    "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\n",
    "\n",
    "# SARSA\n",
    "count = np.zeros((env.observation_space.n,env.action_space.n)) # to track update frequencies\n",
    "epsilon = 1\n",
    "x = env.reset()\n",
    "a = epsilon_greedy(Qsarsa,x,epsilon)\n",
    "for t in range(max_steps):\n",
    "    if((t+1)%1000000==0):\n",
    "        epsilon = epsilon/2\n",
    "    y,r,d,_ = env.step(a)\n",
    "    aa = epsilon_greedy(Qsarsa,y,epsilon)\n",
    "    Qsarsa[x][a] = Qsarsa[x][a] + alpha * (r+gamma*Qsarsa[y][aa]-Qsarsa[x][a])\n",
    "    count[x][a] += 1\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "        a = epsilon_greedy(Qsarsa,x,epsilon)\n",
    "    else:\n",
    "        x=y\n",
    "        a = aa\n",
    "\n",
    "# SARSA's final value function and policy\n",
    "print(\"Max error:\", np.max(np.abs(Qsarsa-Qstar)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Final epsilon:\", epsilon)\n",
    "pi_sarsa = greedyQpolicy(Qsarsa)\n",
    "print(\"Greedy SARSA policy:\")\n",
    "print_policy(pi_sarsa)\n",
    "print(\"Difference between pi_sarsa and pi_star (recall that there are several optimal policies):\")\n",
    "print(pi_sarsa-pi_star)\n",
    "Qpi_sarsa, residuals = policy_Qeval_iter(pi_sarsa,1e-4,10000)\n",
    "print(\"Max difference in value between pi_sarsa and pi_star:\", np.max(np.abs(Qpi_sarsa-Qstar)))\n",
    "print(\"Min difference in value between pi_sarsa and pi_star:\", np.min(np.abs(Qpi_sarsa-Qstar)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same remark as for TD(0) holds: with a better exploration strategy, the convergence to Qstar could be much more efficient. We can see that some states have been visited (and updated) way more often than others. Let's plot the exploration map for each action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": 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": {},
   "source": [
    "## <a id=\"qlearning\"></a>Q-learning\n",
    "\n",
    "It is somehow regretable that the convergence of $Q$ to $Q^*$ in SARSA depends on the decrease schedule of $\\epsilon$ (because SARSA always tries to evaluate the current policy). One could wish for an algorithm that tries to infer $Q^*$ independently of the actor's policy. In other words, one could wish for an **off-policy** algorithm that converges to $Q^*$. That's Q-learning.\n",
    "\n",
    "At each time step, Q-learning aims at evaluating what would be the optimal $Q$-function, independently of the policy applied. Thus, its target is $Q^*$ rather than $Q^\\pi$. To do this, it simply changes the TD update of SARSA into:\n",
    "$$Q(s,a) \\leftarrow Q(s,a) + \\alpha \\left[r + \\gamma \\max_{a'} Q(s',a') - Q(s,a)\\right]$$\n",
    "\n",
    "<div class=\"alert alert-success\"><b>Q-learning</b><br>\n",
    "Repeat:\n",
    "<ol>\n",
    "    <li> In $s$, choose $a$ (<i>GLIE actor</i>)\n",
    "    <li> Observe $r$, $s'$\n",
    "    <li> Temporal difference: $\\delta=r+\\gamma \\max_{a'} Q(s',a') - Q(s,a)$\n",
    "    <li> Update $Q$: $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\delta$\n",
    "    <li> $s\\leftarrow s'$\n",
    "</ol>\n",
    "Q-learning converges if the actor is GLIE and if $\\alpha$ respects the Robbins-Monro conditions.\n",
    "</div>\n",
    "\n",
    "The policy applied is not the target of the TD(0) update anymore: we have replaced $Q(s',a')$ by $\\max_{a'} Q(s',a')$, so if $Q=Q^*$ we are effectively evaluating an optimal policy. While SARSA was the sample-based implementation of an estimator for the **evaluation equation** (from the MDP class), Q-learning is the implementation of an estimator for the **optimality equation**.\n",
    "\n",
    "It is important to note that Q-learning is an **off-policy** critic: its target is independent of the policy applied by the actor (but of course the samples $(s,a,r,s')$ depend on the actor).<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Let's implement an $\\epsilon$-greedy Q-learning on the FrozenLake problem.<br>\n",
    "As in the previous exercice, for the decrease of $\\epsilon$ we can opt for a division by 2 every million steps.<br>\n",
    "You can compare with $Q^*$ and $\\pi^*$ obtained during the model-based class.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's restart from Qpi0\n",
    "Qql = Qpi0\n",
    "max_steps = 5000000\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-Qstar)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(\"Final epsilon:\", epsilon)\n",
    "pi_ql = greedyQpolicy(Qql)\n",
    "print(\"Greedy Q-learning policy:\")\n",
    "print_policy(pi_ql)\n",
    "print(\"Difference between pi_ql and pi_star (recall that there are several optimal policies):\")\n",
    "print(pi_ql-pi_star)\n",
    "Qpi_ql, residuals = policy_Qeval_iter(pi_ql,1e-4,10000)\n",
    "print(\"Max difference in value between pi_sarsa and pi_star:\", np.max(np.abs(Qpi_ql-Qstar)))\n",
    "print(\"Min difference in value between pi_sarsa and pi_star:\", np.min(np.abs(Qpi_ql-Qstar)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": 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": {},
   "source": [
    "## <a id=\"further\"></a>Going further with SARSA and Q-learning\n",
    "\n",
    "The exercices below will help you go further with SARSA and Q-learning (you can skip this part if this is the first time you read this notebook). [Link to next part](#offline)\n",
    "<div class=\"alert alert-warning\"><b>Exercices:</b><br>\n",
    "<ul>\n",
    "<li><b>Context-dependent exploration</b><br>\n",
    "Can you implement an $(s,a)$-dependent $\\epsilon$-greedy exploration strategy (by using the `count` table introduced earlier for instance)?\n",
    "<li><b>Heuristic initialization on $Q$</b><br>\n",
    "For Q-learning, can you think of an initialization of $Q$ that would be better than plain zeros (for example by exploiting the maximum 1-step reward $r_{max}$)? One that, for instance, would drive the exploration towards unvisited states?\n",
    "<li><b>Reward shaping</b><br>\n",
    "Did you notice that falling into a hole brings no penalty? If we introduced a $-1$ reward for falling into a hole, would it change the optimal policy?\n",
    "<li><b>SARSA($\\lambda$)</b><br>\n",
    "SARSA is an on-policy method and we've seen that so is TD($\\lambda$) so it seems rather straightforward to implement a SARSA($\\lambda$) algorithm that, hopefully, will have better convergence properties than plain SARSA.\n",
    "<li><b>$Q(\\lambda)$</b><br>\n",
    "This time it is not as straightfoward to derive a $Q(\\lambda)$ algorithm from TD($\\lambda$), precisely because TD($\\lambda$) evaluates the policy being applied and not another one. Can you imagine a way to still perform $Q(\\lambda)$ updates? An answer is found in Watkins's thesis that introduces Q-learning in 1989. For a more recent approach and other references, see Sutton et al, <b>A new Q($\\lambda$) with interim forward view and Monte Carlo equivalence</b>, 2014)\n",
    "<li><b>SARSA and $Q$-learning with linear value function approximation</b><br>\n",
    "Can you implement an approximate version of SARSA and $Q$-learning with linear Q-function approximation $Q(s,a)=\\theta^T\\varphi(s,a)$?\n",
    "</ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-danger\"><a href=\"#going\" data-toggle=\"collapse\"><b>Answers:</b></a><br>\n",
    "<div id=\"going\" class=\"collapse\">\n",
    "TODO\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"interactive\"></a>Interactive problems\n",
    "\n",
    "The previous section focused on **online learning**, where the agent could decide, at each step, what action to take (thus making a compromise between exploration and exploitation) but suffered the consequences of this action on the next step with no control over this next states.\n",
    "\n",
    "However, in many cases, our agent does not interact with the real world but with a simulator, which we can reset to a predefined state. This case, where the agent controls both the state $s$ and the action $a$ in which it queries samples, is called **interactive learning** and online problems are a specific subset of interactive learning problems.\n",
    "\n",
    "In interactive problems, the exploration vs. exploitation compromise turn to an **active learning** problem. There, the agent should decide to sample more into promising parts or into unexplored parts of $S\\times A$.\n",
    "\n",
    "Currently, this notebook does not cover the case of interactive problems, which will be the focus of the class on Monte Carlo Tree Search. However, the reader is invited to read the excellent discussion in section 4.1 and 4.2 of the **[Algorithms in Reinforcement Learning](https://sites.ualberta.ca/~szepesva/RLBook.html)** book by Csaba Szepesvari (draft freely available online)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id=\"offline\"></a>Offline problems, focussing on the critic alone\n",
    "\n",
    "If this is the first time you read this notebook, you can skip this part. However, bear in mind that the approaches described below carry many insights as to the construction of efficient critics and, even if they are not as fashionable as Deep Q-learning approaches today, they still represent an important part of the RL literature.\n",
    "\n",
    "We now turn our attention to offline problems. These are problems where someone provides the agent with a data set $\\mathcal{D}=\\left\\{(s,a,r,s')\\right\\}$ but allows no interaction with the environment. These are also called *batch learning problems*. The agent is still required to search for an optimal policy.\n",
    "\n",
    "Obviously, in this setting, there is no *actor* anymore, since there is no interaction with the environment. The question then becomes: can we still learn an optimal policy / value function from this data set?\n",
    "\n",
    "Obviously, we could try to infer the underlying MDP's transition and reward models from $\\mathcal{D}$ and then solve the optimality equation. In the next two sections, we propose two algorithms that respectively approximate Value Iteration and Policy Iteration with the samples from $\\mathcal{D}$.\n",
    "\n",
    "Since there is no exploration in offline RL, it defines a rather specific class of problems for which the curse of dimensionality is less of an issue than in online or interactive RL. Here, the samples set is known from the start and we should make the best possible use of it, with no particular hope that we could get a better coverage of the state-action space. Of course, this translates directly to our ability to generalize well the finite set of samples at our disposal to a value function that covers the full state-action space and therefore, it moves the exploration problem towards a *representation* problem, commonly known in **Supervized Learning** (in particular via the bias-variance tradeoff).\n",
    "\n",
    "An interesting feature about methods that solve offline RL problems is that they are necessarily off-policy. However, they might still be sensitive to the distribution of samples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"fqi\"></a>Fitted Q-iteration\n",
    "\n",
    "Recall the idea of Value Iteration. In every state we performed the Bellman backup:\n",
    "$$V(s) \\leftarrow \\max_{a} r(s,a) + \\gamma \\sum_{s'\\in S} p(s'|s,a) V(s')$$\n",
    "We can write the $Q$-function version of Value Iteration, which we call $Q$-iteration:\n",
    "$$Q(s,a) \\leftarrow r(s,a) + \\gamma \\sum_{s'\\in S} p(s'|s,a) \\max_{a'} Q(s',a')$$\n",
    "\n",
    "The online version of this update leads to the Q-learning algorithm. The offline version will require a function approximator and is called **fitted Q-iteration**.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-success\"><b>Fitted Q-iteration</b><br>\n",
    "Given a regression method \"fit_model\" and an initial $Q_0=0$.<br>\n",
    "For $i=1$ to $N$:\n",
    "<ul>\n",
    "<li> For each sample $(s,a,r,s')$ in $\\mathcal{D}$, define $(x,y)$ with:<br>\n",
    "$x = (s,a)$<br>\n",
    "$y = r + \\gamma \\max_{a'} Q_{i-1}(s',a')$<br>\n",
    "Call $\\mathcal{T}$ the training set $\\left\\{(x,y)\\right\\}$\n",
    "<li> $Q_i$ = fit_model$(\\mathcal{T})$\n",
    "</ul>\n",
    "</div>\n",
    "\n",
    "Note that in the tabular case, a straightforward version of fitted Q-iteration boils down to averaging the values of $r + \\gamma \\max_{a'} Q_{i-1}(s',a')$ for all the $(r,s')$ resulting from the same $(s,a)$.\n",
    "\n",
    "Of course, the more expressive \"fit_model\" is, the less error one carries from one iteration to the other. In practice, it is known that fitted Q-iteration might diverge unless some special regressor is used. Kernel smoothing, tree-based methods or neural networks can be good candidates for the implementation of such algorithms. In the cases where fitted Q-iteration converges, it does so to a neighborhood of the optimal $Q^*$.<br>\n",
    "<br>\n",
    "A general sufficient condition for the convergence of fitted Q-iteration is to use *averagers*; these are functions that can be decomposed as $Q(s,a)=\\sum\\limits_{i} \\theta_i \\varphi_i(s,a)$ with the property that $\\forall (s,a), \\sum\\limits_{i} \\varphi_i(s,a) = 1$. Note that *kernel-based methods* are averagers (*tree-based methods* being a specific case of kernel-based methods, with constant 0/1 kernels).<br>\n",
    "<br>\n",
    "A good reference on fitted Q-iteration is the article **[Tree based batch mode Reinforcement Learning](http://www.jmlr.org/papers/volume6/ernst05a/ernst05a.pdf)** by Ernst et al. (2004).<br>\n",
    "An alternative reference, using neural networks instead to tree-based methods is **[Neural Fitted Q-Iteration - first experiences with a data efficient reinforcement learning method](https://pdfs.semanticscholar.org/2820/01869bd502c7917db8b32b75593addfbbc68.pdf)** by Riedmiller (2005).<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Implement a fitted Q-iteration method in the exact tabular case for the FrozenLake problem.<br>\n",
    "The training data will be collected by performing a uniform random walk.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data generation\n",
    "N=1000000\n",
    "XX = np.zeros((N), dtype=np.int)\n",
    "AA = np.zeros((N), dtype=np.int)\n",
    "RR = np.zeros((N))\n",
    "YY = np.zeros((N), dtype=np.int)\n",
    "count = np.zeros((env.observation_space.n,env.action_space.n)) # to track update frequencies\n",
    "x = env.reset()\n",
    "XX[0] = x\n",
    "for t in range(N):\n",
    "    a = np.random.randint(4)\n",
    "    y,r,d,_ = env.step(a)\n",
    "    XX[t] = x\n",
    "    AA[t] = a\n",
    "    RR[t] = r\n",
    "    YY[t] = y\n",
    "    count[x,a] += 1\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# FQI\n",
    "FQI_steps=20\n",
    "Q_fqi = np.zeros((env.observation_space.n, env.action_space.n, FQI_steps))\n",
    "count = np.zeros((env.observation_space.n, env.action_space.n))\n",
    "for i in range(XX.shape[0]):\n",
    "    count[XX[i], AA[i]] +=1\n",
    "\n",
    "for n in range(1,FQI_steps):\n",
    "    for i in range(XX.shape[0]):\n",
    "        Q_fqi[XX[i], AA[i], n] += RR[i] + gamma * np.max(Q_fqi[YY[i], :, n-1])\n",
    "    for s in range(env.observation_space.n):\n",
    "        for a in range(env.action_space.n):\n",
    "            if(count[s,a]!=0):\n",
    "                Q_fqi[s,a,n] = Q_fqi[s,a,n] / count[s,a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pi_fqi = greedyQpolicy(Q_fqi[:,:,FQI_steps-1])\n",
    "print(\"Greedy FQI policy:\")\n",
    "print_policy(pi_fqi)\n",
    "print(\"Difference between pi_fqi and pi_star (recall that there are several optimal policies):\")\n",
    "print(pi_fqi-pi_star)\n",
    "Qpi_fqi, residuals = policy_Qeval_iter(pi_fqi,1e-4,10000)\n",
    "print(\"Max difference in value between pi_fqi and pi_star:\", np.max(np.abs(Qpi_fqi-Qstar)))\n",
    "print(\"Min difference in value between pi_fqi and pi_star:\", np.min(np.abs(Qpi_fqi-Qstar)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "delta = np.zeros((FQI_steps))\n",
    "for n in range(FQI_steps):\n",
    "    Q, residuals = policy_Qeval_iter(greedyQpolicy(Q_fqi[:,:,n]),1e-4,10000)\n",
    "    delta[n] = np.max(np.abs(Q-Qstar))\n",
    "\n",
    "plt.plot(delta)\n",
    "plt.figure()\n",
    "plt.semilogy(delta);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In very large state and action spaces, it might be difficult to obtain samples $(s,a)$ covering efficiently the full $S\\times A$ space. However, supposing that the approximation method for $Q(s,a)$ is robust to non-uniform $(s,a)$-distributions, one can remark that fitted Q-iteration lends itself quite easily to interleaving the data acquisition phase and the value function improvement. Again, this come with no guarantees concerning convergence but can be an advantage in very large state and action spaces.<br>\n",
    "<br>\n",
    "In particular, provided that the database of samples contains enough information about reward providing transitions, it might be interesting to progressively focus the sampling strategy around the last $Q$-greedy policy's state-action distribution. For an example of application of this idea, one can refer to **Clinical data based optimal STI strategies for HIV: a Reinforcement Learning approach** by Ernst et al (2006).<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Implement a modified fitted Q-iteration algorithm that collects new samples at step $n$ by using a $Q_{n-1}$-greedy  $\\epsilon$-greedy policy and adds them to the training database.<br>\n",
    "More precisely, at each enrichment step, add $N$ new samples to the dataset, but only generate $N/10$ of them using $\\epsilon = 1 - \\frac{i}{9}$ for $i\\in [0,9]$.<br>\n",
    "Start with an initial zero $Q$-function.\n",
    "</div>\n",
    "We don't expect to see much of a difference compared to the previous exercice because FrozenLake is just too simple, but we can still do this exercice for practice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# incremental FQI\n",
    "N=100000\n",
    "XX = np.zeros((0), dtype=np.int)\n",
    "AA = np.zeros((0), dtype=np.int)\n",
    "RR = np.zeros((0))\n",
    "YY = np.zeros((0), dtype=np.int)\n",
    "FQI_steps=20\n",
    "Q_fqi = np.zeros((env.observation_space.n, env.action_space.n, FQI_steps))\n",
    "count = np.zeros((env.observation_space.n,env.action_space.n)) # to track update frequencies\n",
    "for n in range(1,FQI_steps):\n",
    "    print(\"FQI step number\", n)\n",
    "    # data generation\n",
    "    XXX = np.zeros((N), dtype=np.int)\n",
    "    AAA = np.zeros((N), dtype=np.int)\n",
    "    RRR = np.zeros((N))\n",
    "    YYY = np.zeros((N), dtype=np.int)\n",
    "    count2 = np.zeros((env.observation_space.n,env.action_space.n))\n",
    "    epsilon = 1\n",
    "    Nbatch = np.floor(N/10)\n",
    "    x = env.reset()\n",
    "    for i in range(N):\n",
    "        if (i%Nbatch == 0):\n",
    "            epsilon -= 1./9.\n",
    "        a = epsilon_greedy(Q_fqi[:,:,n-1],x,epsilon)\n",
    "        y,r,d,_ = env.step(a)\n",
    "        XXX[i] = x\n",
    "        AAA[i] = a\n",
    "        RRR[i] = r\n",
    "        YYY[i] = y\n",
    "        count2[x,a] += 1\n",
    "        if d==True:\n",
    "            x = env.reset()\n",
    "        else:\n",
    "            x=y\n",
    "    XX = np.append(XX,XXX)\n",
    "    AA = np.append(AA,AAA)\n",
    "    RR = np.append(RR,RRR)\n",
    "    YY = np.append(YY,YYY)\n",
    "    count = count + count2\n",
    "    print(\"number of samples in dataset:\", XX.shape[0])\n",
    "    # Value function computation\n",
    "    for i in range(XX.shape[0]):\n",
    "        Q_fqi[XX[i], AA[i], n] += RR[i] + gamma * np.max(Q_fqi[YY[i], :, n-1])\n",
    "    for s in range(env.observation_space.n):\n",
    "        for a in range(env.action_space.n):\n",
    "            if(count[s,a]!=0):\n",
    "                Q_fqi[s,a,n] = Q_fqi[s,a,n] / count[s,a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "delta = np.zeros((FQI_steps))\n",
    "for n in range(FQI_steps):\n",
    "    Q, residuals = policy_Qeval_iter(greedyQpolicy(Q_fqi[:,:,n]),1e-4,10000)\n",
    "    delta[n] = np.max(np.abs(Q-Qstar))\n",
    "\n",
    "plt.plot(delta)\n",
    "plt.figure()\n",
    "plt.semilogy(delta);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To alleviate the problem of the linearly increasing size of the database in the example above, one could implement, for instance, a uniform random removal over the data set, in order to keep its size bounded. These more advanced tricks and their implications are beyond the scope of this notebook but they give a first flavour of the mini-batches and experience replay tricks that are used in state-of-the-art Deep Reinforcement Learning methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FrozenLake is a very simple toy problem with (few) discrete states and actions. So the dataset above covers well the full state-action space. But in the general case, the state-action space might be continuous or just too large to sample extensively. So one has to rely on the generalization properties of a regressor.<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Let's implement a fitted Q-iteration method using Random Forests (or Extremely Randomized Trees) as a regressor over the (row, column, action) feature space.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data generation\n",
    "N=1000000\n",
    "XX = np.zeros((N), dtype=np.int)\n",
    "AA = np.zeros((N), dtype=np.int)\n",
    "RR = np.zeros((N))\n",
    "YY = np.zeros((N), dtype=np.int)\n",
    "x = env.reset()\n",
    "XX[0] = x\n",
    "print(\"data generation\")\n",
    "for t in range(N):\n",
    "    a = np.random.randint(4)\n",
    "    y,r,d,_ = env.step(a)\n",
    "    XX[t] = x\n",
    "    AA[t] = a\n",
    "    RR[t] = r\n",
    "    YY[t] = y\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#from sklearn.ensemble import RandomForestRegressor as regressor\n",
    "from sklearn.ensemble import ExtraTreesRegressor as regressor\n",
    "\n",
    "# Dataset preparation\n",
    "print(\"dataset preparation\")\n",
    "nb_samples = XX.shape[0]\n",
    "Xregr = np.zeros((nb_samples,3))\n",
    "Yregr = np.zeros((nb_samples))\n",
    "for i in range(nb_samples):\n",
    "    row,col = to_row_col(XX[i])\n",
    "    Xregr[i,0] = row\n",
    "    Xregr[i,1] = col\n",
    "    Xregr[i,2] = AA[i]\n",
    "# X_next_state is a table containing all possible pairs (s',a') ordered as (s0, a0), (s0,a1), (s0,a2), (s1,a0)...\n",
    "# It will be useful to compute max_a Q(s,a)\n",
    "X_next_state = np.zeros((env.action_space.n * nb_samples, 3))\n",
    "index = 0\n",
    "for i in range(nb_samples):\n",
    "    row,col = to_row_col(YY[i])\n",
    "    for a in range(env.action_space.n):\n",
    "        X_next_state[index,0] = row\n",
    "        X_next_state[index,1] = col\n",
    "        X_next_state[index,2] = a\n",
    "        index = index+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tree-based FQI (WARNING, the repeated training of the regressor might be very long)\n",
    "\n",
    "# hack: sink_mask is a vector that is 0 for terminal states and 1 otherwise\n",
    "# it is used to avoid having non-zero values for max_a Q(s,a), for terminal states s\n",
    "sinks = {5,7,11,12,15}\n",
    "sink_mask = np.ones((nb_samples))\n",
    "for i in range(nb_samples):\n",
    "    if (YY[i] in sinks):\n",
    "        sink_mask[i] = 0\n",
    "\n",
    "# FQI\n",
    "FQI_steps=20\n",
    "Qfunctions = []\n",
    "print(\"FQI step 0 - training regressor\")\n",
    "Qfunctions.append(regressor(n_estimators=200))\n",
    "Qfunctions[-1].fit(Xregr,Yregr)\n",
    "for n in range(1,FQI_steps):\n",
    "    print(\"FQI step\", n, end=\" - \")\n",
    "    pred_next_state = Qfunctions[-1].predict(X_next_state)\n",
    "    maxQ2 = np.max((pred_next_state.reshape(nb_samples, env.action_space.n)), axis=1)\n",
    "    maxQ2 = np.multiply(maxQ2,sink_mask)\n",
    "    Yregr = RR + gamma * maxQ2\n",
    "    print(\"training regressor\")\n",
    "    Qfunctions.append(regressor(n_estimators=200))\n",
    "    Qfunctions[-1].fit(Xregr,Yregr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build greedy policy\n",
    "pi_fqi = np.zeros((env.observation_space.n),dtype=np.int)\n",
    "for s in range(env.observation_space.n):\n",
    "    Q = np.zeros((env.action_space.n))\n",
    "    row,col = to_row_col(s)\n",
    "    for a in range(env.action_space.n):\n",
    "        xinput = np.array([row,col,a]).reshape((1,3))\n",
    "        Q[a] = Qfunctions[-1].predict(xinput)\n",
    "    pi_fqi[s] = np.argmax(Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Greedy FQI policy:\")\n",
    "print_policy(pi_fqi)\n",
    "print(\"Difference between pi_fqi and pi_star (recall that there are several optimal policies):\")\n",
    "print(pi_fqi-pi_star)\n",
    "Qpi_fqi, residuals = policy_Qeval_iter(pi_fqi,1e-4,10000)\n",
    "print(\"Max difference in value between pi_fqi and pi_star:\", np.max(np.abs(Qpi_fqi-Qstar)))\n",
    "print(\"Min difference in value between pi_fqi and pi_star:\", np.min(np.abs(Qpi_fqi-Qstar)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"#sinkmask\" data-toggle=\"collapse\">Important remark</a><br>\n",
    "<div id=\"sinkmask\" class=\"collapse\">\n",
    "Did you notice the `sink_mask` hack in the code above and its importance?<br>\n",
    "<br>\n",
    "When dealing with environments that have terminal states (such as the holes and the frisbee location here), no transitions will ever be sampled from those states. So a regression method (such as Random Forests) will never see samples starting from $(s,a)$ for a terminal $s$ and therefore will never be informed that it should return zero for any transition starting from $s$. Instead, it will return whatever value it can infer from all the other collected data. But the FQI procedure just ignores that fact: when computing $r+\\gamma \\max_{a'} Q(s',a')$ for terminal $s'$, it will request a scalar value from the regressor that was never informed that it should return value zero. Often, this will result in giving a non-zero value to transitions starting from terminal states and this will bias the resulting value functions and policies. To avoid this phenomenon, we introduced that `sink_mask` vector that zeroes down the $\\max_{a'} Q(s',a')$ term for any terminal $s'$. The regressor is still not informed that transitions from $s'$ are worth zero but at least we don't propagate this error through the iterations.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a id=\"lspi\"></a>Least Squares Policy Iteration\n",
    "\n",
    "Least Squares Policy Iteration (LSPI) answers the question: can we implement a Policy Iteration method based only on samples and given a linear model for the $Q$-function?\n",
    "\n",
    "Since we are talking about Policy Iteration, the critical step is the evaluation of a given policy.\n",
    "\n",
    "Suppose $Q^\\pi(s,a) = w^T \\varphi(s,a)$. We write $\\Phi$ the matrix of feature evaluations for all pairs $(s,a)$, that is:\n",
    "$$\\Phi = \\left[\\begin{array}{ccc}\\varphi_0(s_0,a_0) & \\cdots & \\varphi_0(s_{|S|},a_{|A|}) \\\\\n",
    "\\vdots & \\ddots & \\vdots \\\\\n",
    "\\varphi_K(s_0,a_0) & \\cdots & \\varphi_K(s_{|S|},a_{|A|}) \\end{array} \\right]$$\n",
    "\n",
    "Then, $Q^\\pi = r^\\pi + \\gamma P^\\pi Q^\\pi$ becomes:\n",
    "$$\\Phi w_\\pi = r^\\pi + \\gamma P^\\pi \\Phi w_\\pi$$\n",
    "\n",
    "But $r^\\pi + \\gamma P^\\pi \\Phi w_\\pi$ has no reason to lie within $span(\\varphi)$. So we should consider its projection on $span(\\varphi)$ as illustrated by the figure below.\n",
    "\n",
    "<img src=\"images/projection.png\" style=\"width: 600px;\"></img>\n",
    "\n",
    "The projection operator on $span(\\varphi)$ is $\\Phi\\left(\\Phi^T \\Phi\\right)^{-1} \\Phi^T$. And thus $w_\\pi$ is a solution to:\n",
    "$$\\Phi w_\\pi = \\Phi\\left(\\Phi^T \\Phi\\right)^{-1} \\Phi^T \\left( r^\\pi + \\gamma P^\\pi \\Phi w_\\pi \\right)$$\n",
    "\n",
    "And this system can be solved as (for a proof, see the seminal paper **[Least Squares Policy Iteration](http://www.jmlr.org/papers/volume4/lagoudakis03a/lagoudakis03a.pdf)** by Lagoudakis and Parr in 2003):\n",
    "$$w_\\pi  = \\left[\\Phi^T\\left(\\Phi - \\gamma P^\\pi \\Phi\\right)\\right]^{-1}\\Phi^T r^\\pi$$\n",
    "\n",
    "Let $A = \\Phi^T\\left(\\Phi - \\gamma P^\\pi \\Phi\\right)$ and $b=\\Phi^T  r^\\pi$. We have $w_\\pi = A^{-1}b$ so the question becomes: can we compute $A$ and $b$ from samples?\n",
    "\n",
    "Taking a closer look at $A$ and $b$, we have:\n",
    "$$A = \\sum\\limits_{s\\in S} \\sum\\limits_{a\\in A} \\sum\\limits_{s'\\in S} p(s'|s,a) \\left[ \\varphi(s,a) \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\pi(s')) \\right)^T \\right]$$\n",
    "$$b= \\sum\\limits_{s\\in S} \\sum\\limits_{a\\in A} \\sum\\limits_{s'\\in S} p(s'|s,a) \\left[ \\varphi(s,a) r(s,a,s')\\right]$$\n",
    "\n",
    "And thus $A$ is the sum of many matrices of the form $\\varphi(s,a) \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\varphi(s')) \\right)^T$ and $b$ is the sum of many vectors of the form $\\varphi(s,a) r(s,a,s')$.\n",
    "\n",
    "And so, finally, with $\\mathcal{D}=\\left\\{(s_i,a_i,r_i,s'_i)\\right\\}_{i=1..N}$, $A$ and $b$ can be approximated by:\n",
    "$$A \\approx \\frac{1}{N} \\sum\\limits_{i=1}^N\\left[\\varphi(s_i, a_i)\\left(\\varphi(s_i, a_i) - \\gamma \\varphi(s'_i, \\pi(s'_i))\\right)^T\\right]$$\n",
    "$$b \\approx \\frac{1}{N} \\sum\\limits_{i=1}^N \\left[ \\varphi(s_i,a_i)r_i \\right]$$\n",
    "\n",
    "From these expressions one gets the LSTD$Q$ (Least Squares Temporal Differences on $Q$ functions) algorithm that evaluates policy $\\pi$ given a function basis $\\varphi$:\n",
    "<div class=\"alert alert-success\"><b>LSTD$Q(\\pi,\\varphi)$</b>:<br>\n",
    "$K=\\dim(Im(\\varphi))$<br>\n",
    "$\\tilde{A} = 0_{K\\times K}$<br>\n",
    "$\\tilde{b} = 0_K$<br>\n",
    "For each $(s,a,r,s') \\in \\mathcal{D}$:<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\\tilde{A} \\leftarrow \\tilde{A} + \\varphi(s,a) \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\pi(s')) \\right)^T$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\\tilde{b} \\leftarrow \\tilde{b} + \\varphi(s,a) r$<br>\n",
    "return $w_\\pi = \\tilde{A}^{-1} b$\n",
    "</div>\n",
    "\n",
    "LSTD$Q$ requires the inversion of $\\tilde{A}$, which my not be full rank until a sufficient number of samples have been processed. One way to avoid  such singularities is to initialize $\\tilde{A}$ to a multiple of the identity matrix $\\delta I_K$ for some small positive $\\delta$, instead of $0_{K\\times K}$.\n",
    "\n",
    "This definition of LSTD$Q$ can be improved by using the Sherman-Morrison formula (incremental computation of the inverse $\\tilde{B}$ of $\\tilde{A}$) and the algorithm becomes:\n",
    "<div class=\"alert alert-success\"><b>LSTD$Q(\\pi,\\varphi)$ with incremental inverse computation</b>:<br>\n",
    "$\\tilde{B} = \\frac{1}{\\delta}I$ with $\\delta$ a small positive value.<br>\n",
    "$\\tilde{b} = 0$<br>\n",
    "For each $(s,a,r,s') \\in \\mathcal{D}$:<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\\tilde{B} \\leftarrow \\tilde{B} - \\frac{B \\varphi(s,a) \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\pi(s')) \\right)^T B}{1 + \\left( \\varphi(s,a) - \\gamma\\varphi(s',\\pi(s')) \\right)^T B \\varphi(s,a)} $<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\\tilde{b} \\leftarrow \\tilde{b} + \\varphi(s,a) r$<br>\n",
    "return $w_\\pi = \\tilde{B} b$\n",
    "</div>\n",
    "\n",
    "The time complexity of the algorithm above is far lesser ($O(K^2)$) than the one involving the inversion of $\\tilde{A}$ ($O(K^3)$).\n",
    "\n",
    "LSTD$Q$ as defined above computes the weights of any policy $\\pi$. We will note this operation: $w \\leftarrow$ LSTD$Q$($\\pi,\\varphi$). But we also remark that given a weights vector $w$, computing the weights for the value of the $w^T \\varphi$ -greedy policy requires building $\\tilde{B}$ and $\\tilde{b}$. This computation requires finding the $\\arg\\max_{a'\\in A} w^T\\varphi(s',a')$ in all $s'$ concerned by the updates of $\\tilde{B}$, which can be done on the fly, sample after sample, without explicitly storing the greedy policy. Thus we can define the operation $w' \\leftarrow$ LSTD$Q$($w, \\varphi$) that directly computes the weights $w$ of the policy that is greedy with respect to $w^T\\varphi$.\n",
    "\n",
    "This way, we can evaluate any policy $\\pi$ or any $w^T \\varphi$-greedy policy given the dataset $\\mathcal{D}$. The LSPI algorithm is then simply, given an initial $\\pi_0$:<br>\n",
    "$w' \\leftarrow $ LSTD$Q$($\\pi_0,\\varphi$)<br>\n",
    "Repeat:<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $w \\leftarrow w'$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $w' \\leftarrow$ LSTD$Q$($w,\\varphi$)<br>\n",
    "until $\\|w-w'\\| \\leq \\epsilon$<br>\n",
    "<br>\n",
    "<div class=\"alert alert-warning\"><b>Exercice:</b><br>\n",
    "Implement LSTQ$Q$ and LSPI as functions of an initial policy $\\pi$.<br>\n",
    "Since we can (because FrozenLake is very simple), let's use the state-action indicator functions as features.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# features\n",
    "nb_features = env.observation_space.n * env.action_space.n\n",
    "\n",
    "def phi(s,a):\n",
    "    val = np.zeros((env.observation_space.n*env.action_space.n))\n",
    "    index = a*env.observation_space.n + s\n",
    "    val[index] = 1.\n",
    "    return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# LSTDQ\n",
    "def LSTDQ_w(w, XX, AA, RR, YY, gamma, phi):\n",
    "    nb_samples = XX.shape[0]\n",
    "    delta = 1e-5\n",
    "    B = (1/delta)*np.eye(nb_features)\n",
    "    b = np.zeros((nb_features,1))\n",
    "    for i in range(nb_samples):\n",
    "        phi1 = phi(XX[i],AA[i]).reshape((nb_features,1))\n",
    "        Q2 = np.zeros(env.action_space.n)\n",
    "        for a in range(env.action_space.n):\n",
    "            phi2 = phi(YY[i],a)\n",
    "            Q2[a] = np.dot(w,phi2)\n",
    "        a2 = np.argmax(Q2)\n",
    "        phi2 = phi(YY[i],a2).reshape((nb_features,1))\n",
    "        # update B\n",
    "        B = B - ( B @ (phi1 @ (phi1-gamma*phi2).T) @ B ) / (1. + (phi1-gamma*phi2).T @ B @ phi1 )\n",
    "        # update b\n",
    "        b = b + phi1 * RR[i]\n",
    "    return (B @ b).ravel()\n",
    "\n",
    "def LSTDQ_pi(pi, XX, AA, RR, YY, gamma, phi):\n",
    "    nb_samples = XX.shape[0]\n",
    "    delta = 1e-5\n",
    "    B = (1/delta)*np.eye(nb_features)\n",
    "    b = np.zeros((nb_features,1))\n",
    "    for i in range(nb_samples):\n",
    "        phi1 = phi(XX[i],AA[i]).reshape((nb_features,1))\n",
    "        phi2 = phi(YY[i],pi[YY[i]]).reshape((nb_features,1))\n",
    "        # update B\n",
    "        B = B - ( B @ (phi1 @ (phi1-gamma*phi2).T) @ B ) / (1. + (phi1-gamma*phi2).T @ B @ phi1 )\n",
    "        # update b\n",
    "        b = b + phi1 * RR[i]\n",
    "    return (B @ b).ravel()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data generation\n",
    "N=1000000\n",
    "XX = np.zeros((N), dtype=np.int)\n",
    "AA = np.zeros((N), dtype=np.int)\n",
    "RR = np.zeros((N))\n",
    "YY = np.zeros((N), dtype=np.int)\n",
    "x = env.reset()\n",
    "XX[0] = x\n",
    "print(\"data generation\", end=\" - \")\n",
    "for t in range(N):\n",
    "    a = np.random.randint(4)\n",
    "    y,r,d,_ = env.step(a)\n",
    "    XX[t] = x\n",
    "    AA[t] = a\n",
    "    RR[t] = r\n",
    "    YY[t] = y\n",
    "    if d==True:\n",
    "        x = env.reset()\n",
    "    else:\n",
    "        x=y\n",
    "print(N, \"data points generated.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# LSPI\n",
    "pi0 = fl.RIGHT*np.ones((env.observation_space.n), dtype=np.int)\n",
    "max_iterations = 5 # maximum number of iterations for Policy Iteration\n",
    "epsilon = 1e-4\n",
    "w = np.zeros((max_iterations, nb_features))\n",
    "residual = np.zeros((max_iterations))\n",
    "print(\"LSPI iteration number 0 (evaluate first policy)\")\n",
    "w[0,:] = LSTDQ_pi(pi0, XX, AA, RR, YY, gamma, phi)\n",
    "for i in range(1,max_iterations):\n",
    "    print(\"LSPI iteration number,\", i, \"(evaluate greedy policy wrt w)\")\n",
    "    w[i,:] = LSTDQ_w(w[i-1,:], XX, AA, RR, YY, gamma, phi)\n",
    "    residual[i-1] = np.max(np.abs(w[i,:]-w[i-1,:]))\n",
    "    print(\"Residual ||w'-w|| =\", residual[i-1])\n",
    "    if (residual[i-1] < epsilon):\n",
    "        w = w[:i+1,:]\n",
    "        residual = residual[:i]\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Displaying final results\n",
    "nb_iterations = w.shape[0]\n",
    "\n",
    "def policy_from_w(w, phi):\n",
    "    pi = np.zeros((env.observation_space.n),np.int)\n",
    "    for s in range(env.observation_space.n):\n",
    "        Q = np.zeros((env.action_space.n))\n",
    "        for a in range(env.action_space.n):\n",
    "            Q[a] = np.dot(w,phi(s,a))\n",
    "        pi[s] = np.argmax(Q)\n",
    "    return pi\n",
    "\n",
    "pi_lspi = policy_from_w(w[-1,:],phi)\n",
    "\n",
    "print(\"Finished in\", nb_iterations, \"iterations.\")\n",
    "print(\"Final LSPI policy:\")\n",
    "print_policy(pi_lspi)\n",
    "print(\"Evolution of ||w' - w||:\")\n",
    "val = np.zeros((nb_iterations-1))\n",
    "for i in range(nb_iterations-1):\n",
    "    val[i] = np.max(np.abs(w[i+1,:]-w[i,:]))\n",
    "plt.plot(residual)\n",
    "plt.show()\n",
    "print(\"Difference between pi_lspi and pi_star (recall that there are several optimal policies):\")\n",
    "print(pi_lspi-pi_star)\n",
    "Qpi_lspi, residuals = policy_Qeval_iter(pi_lspi,1e-4,10000)\n",
    "print(\"Max difference in value between pi_lspi and pi_star:\", np.max(np.abs(Qpi_lspi-Qstar)))\n",
    "print(\"Min difference in value between pi_lspi and pi_star:\", np.min(np.abs(Qpi_lspi-Qstar)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Convergence to pi_star:\")\n",
    "delta = np.zeros((nb_iterations))\n",
    "for n in range(nb_iterations):\n",
    "    Q, residuals = policy_Qeval_iter(policy_from_w(w[n,:],phi),1e-4,10000)\n",
    "    delta[n] = np.max(np.abs(Q-Qstar))\n",
    "\n",
    "plt.plot(delta)\n",
    "plt.figure()\n",
    "plt.semilogy(delta);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "As we already knew from the model-based class, Policy Iteration converges in a single iteration for this initial policy. Of course, in more complex domains (continuous, large number of states/actions), more refined feature functions will be required. As an exercice, you can try implementing LSPI on the inverted-pendulum domain from OpenAI Gym."
   ]
  },
  {
   "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.8"
  },
  "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": "326.717px",
    "left": "1134px",
    "top": "67.1333px",
    "width": "159px"
   },
   "toc_section_display": false,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}