BiasVarianceTradeoff.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bias-Variance Tradeoff in Variations of SARSA\n",
    "\n",
    "\n",
    "Here, we analyze the bias-variance tradeoff in SARSA [1], Expected SARSA [1], Double SARSA [2], and Double Expected SARSA [2].\n",
    "\n",
    "## Intro to SARSA, Expected SARSA, Double SARSA, Double Expected SARSA\n",
    "\n",
    "Information on SARSA and Expected SARSA can be found in [1] and [7], while information on the Double versions of the algorithms can be found in [2]. Briefly, we note that all algorithms generally follow the following block of pseudocode from [7].\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://webdocs.cs.ualberta.ca/~sutton/book/ebook/pseudotmp12.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import Image, display\n",
    "Image(url= \"https://webdocs.cs.ualberta.ca/~sutton/book/ebook/pseudotmp12.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We note that the difference in the algorithms comes in the $\\delta$ update rule above. \n",
    "\n",
    "In the Double versions of the algorithms, $Q$ is split among two tables $Q_a$ and $Q_b$ which are swapped with probability .5 to allow for an even distribution of sampling. \n",
    "\n",
    "Furthermore, in the expected versions, rather than using $Q(s',a')$ as part of the update, the expectation of $Q$ is used.\n",
    "\n",
    "## Theoretical\n",
    "\n",
    "### SARSA vs. Expected SARSA\n",
    "\n",
    "First, let's explore the theoretical bias-variance tradeoff as provided in [1]. Van Seijen et al. show that Expected SARSA and SARSA have the same mean, but Expected SARSA has a lower variance.\n",
    "\n",
    "Let's say that:\n",
    "\n",
    "$$X_t \\in \\{ v_t, \\hat{v_t} \\}$$\n",
    "\n",
    "where in expected SARSA:\n",
    "\n",
    "$$ v_t = r_t + \\gamma \\sum_a \\pi_t (s_{t+1}, a) Q_t (s_{t+1}, a)$$\n",
    "\n",
    "and in SARSA:\n",
    "\n",
    "$$ \\hat{v_t} = r_t + \\gamma Q_t (s_{t+1}, a_{t+1})$$\n",
    "\n",
    "Bias is represented by:\n",
    "\n",
    "$$Bias(s,a) = Q^{\\pi} (s,a) - E\\{X_t\\}$$\n",
    "\n",
    "Variance is denoted by:\n",
    "\n",
    "$$Var(s,a) = E\\{(X_t)^2\\} - (E\\{X_t\\})^2$$\n",
    "\n",
    "From [1], we get that the Variance for Expected Sarsa is:\n",
    "\n",
    "$$ Var(s,a) = \\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} (\\pi_{s'a'}Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) - (E \\{ \\hat{v}_t \\})^2$$\n",
    "\n",
    "Where does this originate from? Well, the inner term is simply:\n",
    "\n",
    "$$ v_t^2 = \\left(r_t + \\gamma \\sum_a \\pi_t (s_{t+1}, a) Q_t (s_{t+1}, a)\\right) \\left(r_t + \\gamma \\sum_a \\pi_t (s_{t+1}, a) Q_t (s_{t+1}, a)\\right)$$\n",
    "\n",
    "Muliplying together, we get:\n",
    "\n",
    "$$ = r_t^2 + 2\\gamma r_t \\sum_a \\pi_t (s_{t+1}, a) Q_t (s_{t+1}, a) + \\gamma^2 \\sum_a \\pi_t^2 (s_{t+1}, a) Q_t^2 (s_{t+1}, a)$$\n",
    "\n",
    "The paper then changes notation for the expectation, but we're finding the variance for given state action pairs so we take the overall expected transition to every other state and multiply it by the transition probability to get the expectation.\n",
    "\n",
    "The variance term becomes slightly different for SARSA:\n",
    "\n",
    "$$ \\hat{v}_t^2 = \\left(r_t + \\gamma Q_t (s_{t+1}, a_{t+1})\\right) \\left(r_t + \\gamma Q_t (s_{t+1}, a_{t+1})\\right)$$\n",
    "\n",
    "$$ = r_t^2 + 2\\gamma r_t Q_t (s_{t+1}, a_{t+1}) + \\gamma^2 Q_t^2 (s_{t+1}, a_{t+1})$$\n",
    "\n",
    "Taking the expectation of this yields:\n",
    "\n",
    "$$ Var(s,a) = \\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} \\pi_{s'a'}(Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) - (E \\{ \\hat{v}_t \\})^2$$\n",
    "\n",
    "As the expectation is over all state transitions.\n",
    "\n",
    "Noting that $E\\{v_t\\} = E\\{ \\hat{v}_t\\}$. By [1]'s notation:\n",
    "\n",
    "$$ E\\{r_t + \\gamma Q_t (s_{t+1}, a_{t+1})\\} = E\\{r_t + \\gamma \\sum_a \\pi_t (s_{t+1}, a) Q_t (s_{t+1}, a)\\}$$\n",
    "\n",
    "$$ \\sum_{s'} T^{s'}_{sa} R_{sa}^{s'} + \\gamma \\sum_{a'} \\pi_{s'a'} Q_t(s',a') =  \\sum_{s'} T^{s'}_{sa} R_{sa}^{s'} + \\gamma \\sum_{a'} \\pi_{s'a'} Q_t(s',a')$$\n",
    "\n",
    "In the bias variance tradeoff analysis, we know that the bias is equivalent. Since $E\\{v_t\\} = E\\{ \\hat{v}_t\\}$ as shown above.\n",
    "\n",
    "$$ Bias_{\\text{SARSA}}(s,a) = Q^\\pi (s,a) - E\\{v_t\\} = Q^\\pi (s,a) - E\\{\\hat{v}_t\\} = Bias_{\\text{Expected SARSA}}(s,a)$$\n",
    "\n",
    "But, what's the difference in the variance?\n",
    "\n",
    "$$Var_{\\text{SARSA}}(s,a) - Var_{\\text{Expected SARSA}} (s,a)$$\n",
    "\n",
    "$$ \\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} \\pi_{s'a'}(Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) - (E \\{ \\hat{v}_t \\})^2 - \\left(\\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} (\\pi_{s'a'}Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) - (E \\{ \\hat{v}_t \\})^2 \\right)$$\n",
    "\n",
    "Removing the equivalent terms: $(E \\{ \\hat{v}_t \\})^2 = (E \\{ v_t \\})^2$\n",
    "\n",
    "$$ \\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} \\pi_{s'a'}(Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) - \\left(\\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} (\\pi_{s'a'}Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) \\right)$$\n",
    "\n",
    "$$=\\sum_{s'} T^{s'}_{sa} \\left( \\left( \\gamma^2 \\sum_{a'} \\pi_{s'a'}(Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) - \\left( \\gamma^2 \\sum_{a'} (\\pi_{s'a'}Q_t(s', a'))^2 + (R_{sa}^{s'})^2 + 2\\gamma R_{sa}^{s'} \\sum_{a'} \\pi_{s'a'} Q_t(s',a') \\right) \\right)$$\n",
    "\n",
    "$$=\\sum_{s'} T^{s'}_{sa} \\left( \\gamma^2 \\sum_{a'} \\pi_{s'a'}(Q_t(s', a'))^2 - \\gamma^2 \\sum_{a'} (\\pi_{s'a'}Q_t(s', a'))^2 \\right) $$\n",
    "\n",
    "$$= \\gamma^2 \\sum_{s'} T^{s'}_{sa} \\left( \\sum_{a'} \\pi_{s'a'}(Q_t(s', a'))^2 - \\sum_{a'} (\\pi_{s'a'}Q_t(s', a'))^2 \\right) $$\n",
    "\n",
    "We use the notation from [1] to show the following. The difference in variance (with SARSA having increased variance) is larger when Q values have large variability across different actions and there is much exploration in the policy. \n",
    "\n",
    "From the above difference in variance, we can reformulate in simpler terms where $w = \\pi$ and $Q = x$.\n",
    "\n",
    "$$ \\sum_i w_i x_i^2 - \\left( \\sum_i w_i x_i \\right)^2$$\n",
    "\n",
    "We then assume that $w_i \\ge 0, \\forall i$ and $\\sum_i w_i = 1$ this is the case in our term because of the properties of $\\pi$. As [1] describes, we then provide an unbiased esimator (see [3-4] for more information on deriving this unbiased estimator).\n",
    "\n",
    "This estimator of variance comes in the form (where $\\bar{x} = \\sum_i w_i x_i$):\n",
    "\n",
    "$$ \\frac{\\sum_i w_i (x_i - \\bar{x})^2} {1-\\sum_i w_i^2}$$\n",
    "\n",
    "$$ = \\frac{\\sum_i w_i x_i^2 - 2 \\sum_i w_i x_i \\bar{x} + \\sum_i w_i \\bar{x}^2} {1-\\sum_i w_i^2}$$\n",
    "\n",
    "$$ = \\frac{\\sum_i w_i x_i^2 - 2 \\bar{x}^2 + \\bar{x}^2} {1-\\sum_i w_i^2}$$\n",
    "\n",
    "$$ = \\frac{\\sum_i w_i x_i^2 - \\bar{x}^2} {1-\\sum_i w_i^2}$$\n",
    "\n",
    "This unbiased estimate of the variance of the weighted $\\pi Q$ values comes in the exact form as the difference in the variance of Sarsa and Expected Sarsa as we saw earlier. Kind of neat!\n",
    "\n",
    "So what does this tell us? Well when the variance of the $\\pi Q$ values is high, then so is the difference in variance between SARSA and Expected SARSA. \n",
    "\n",
    "### But how does this help us?\n",
    "\n",
    "Well, we now know that Expected Sarsa will always have a variance lower than or equal to Sarsa (when all Q have the same value then difference in variances is at most 0). So this tells us that when there are problems where policy stochasticity is high, then Expected Sarsa will perform much better!\n",
    "\n",
    "\n",
    "### Double Sarsa\n",
    "\n",
    "Doing a strict theoretical analysis comparing Double Sarsa and Double Expected Sarsa is a bit challenging, but we will try to lay a general outline for this and back it up with experimental data. We can use the Double-Q learning proofs as a start [5].\n",
    "\n",
    "As before we can say:\n",
    "\n",
    "$$ v_\\text{Double Sarsa} = r_t + \\gamma (Q_b(s_{t+1}, a_{t+1}) $$\n",
    "\n",
    "This is exactly the same as sarsa, but instead we're using two estimators and swap the estimators with a random probability at every timestep. As in [5] this means that we sample our action space evenly (since uniformly random with probability .5) between the two estimators. In [5] it is shown that $E\\{\\mu_i^A\\} = E\\{\\mu_i^B\\} = E\\{X_i\\}$ for a two estimator space. So the two estimators in Sarsa and Double Sarsa have similar estimators. But what causes double Sarsa to be improved? \n",
    "\n",
    "Well, as described mathematically in the previous section, Expected SARSA performs better than Sarsa when the variation/change in Q is larger. That means the worst case of SARSA is caused by large changes in $Q(s,a)$. As described in [2], \"double Sarsa reduces this variation by de-coupling the two tables, preventing against large changes in $Q(s,a)$, which tends to produce a more stable policy and increase the amount of reward collected.\"\n",
    "\n",
    "Similarly, this applies to Double Expected Sarsa.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experimental\n",
    "\n",
    "Now, we show that the theoretical bias-variance tradeoff results are reflected in experiments with the various methods. \n",
    "\n",
    "NOTE: We spend more time on the SARSA algorithms since we have added Double and Double Expected SARSA and less time on adding more experiments. We only add one custom experiment on top of GridWorld since we are also comparing two additional algorithms.\n",
    "\n",
    "We mainly use the **varying_alpha_epsilon_experiment.py** script for our experiments, changing out the environment and parameters as described below.\n",
    "\n",
    "### Environments\n",
    "\n",
    "For our experimental environments we use a deterministic gridworld, a stochastic gridworld and our own custom problem a windy maze (with cliffs) problem.\n",
    "\n",
    "#### Windy Maze with Cliffs (our own custom experiment)\n",
    "\n",
    "In this maze game, we have a goal state which gives a reward of +50. Obstacles block the agent from going in certain grid cells. There are also cliffs/traps in the world which gives a penalty of -25 and resets the agent to the start position. Additionally the environment is stochastic with a probability $p$ of going into the direction you want and $\\frac{1-p}{3}$ probability of going in each of the other directions. This is a more complex problem than just the gridworld, maze or cliffs problems because it combines all of those together.\n",
    "\n",
    "Our maze looks like the following, with obstacles in grey, cliffs/traps in red, and the start and goal states in green and black respectively:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"images/maze.png\" width=\"300\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(Image(url=\"images/maze.png\", width=300, unconfined=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "#### Deterministic GridWorld\n",
    "\n",
    "In this version of gridworld, any action that is attempted is successful with 100% probability. For our experiments, we set up a grid world MDP similar to the one shown on Sutton page 82, of a larger size: 10x10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://webdocs.cs.ualberta.ca/~sutton/book/ebook/figtmp15.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Image(url= \"https://webdocs.cs.ualberta.ca/~sutton/book/ebook/figtmp15.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "#### Stochastic GridWorld\n",
    "\n",
    "In the stochastic version of our GridWorld problem, every action you take has a probability $p$ of going into the direction you want and probability $\\frac{1-p}{3}$ of going in each of the other directions. Otherwise it is identical to the deterministic GridWorld problem.\n",
    "\n",
    "### Deterministic Environment, Varying Stochasticity of Policy\n",
    "\n",
    "In [1], it is posited that the performance decrease of Expected Sarsa with a more stochastic policy will be much less than that of SARSA in the same scenario. Because we are using $\\epsilon$-greedy policies, we can drive the policy to be more or less varied by increasing the $\\epsilon$ value. To this extent we run some experiments first on a deterministic environment.\n",
    "\n",
    "For every experiment, we run 10,000 episodes and average that across 10 trials. \n",
    "\n",
    "Here we first examine the average reward as a function of $\\alpha$, the learning rate, for multiple values of $\\epsilon$. We expect that for a high $\\epsilon$, Expected Sarsa will see a larger difference in average reward, performing better than SARSA. Relating to the theory, since policy variance is higher, we expect the difference in variance for both to be higher and thus a larger difference in optimal learning rate and maximum average reward. Similarly, we expect the same benefit over SARSA in double SARSA since we smooth out the variance by using two randomly distributed estimators. Lastly, we don't expect much improvement of double SARSA over SARSA as [2] demonstrates that this only occurs in stochastic environments.\n",
    "\n",
    "We then show graphs as a function of $\\alpha$, the learning rate as in [1] and [2] for an $\\epsilon$ value of $.3,.1,.01$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .3\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/ep.03alphavreward10kx10.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .1\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/ep.1alphavreward10kx10.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .01\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/ep.01alphavreward10kx10.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print(\"Epsilon = .3\")\n",
    "display(Image(url=\"images/ep.03alphavreward10kx10.png\", width=500, unconfined=True))\n",
    "print(\"Epsilon = .1\")\n",
    "display(Image(url=\"images/ep.1alphavreward10kx10.png\", width=500, unconfined=True))\n",
    "print(\"Epsilon = .01\")\n",
    "display(Image(url=\"images/ep.01alphavreward10kx10.png\", width=500, unconfined=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "As expected from the theoretical derivation and as presented in [1,2], expected Sarsa's difference in performance with Sarsa increases as epsilon decreases. Note that the difference in the maximum average reward in Figure 1 from Sarsa and expected Sarsa is ~.1 and, as $\\epsilon$ decreases, the gap is reduced to ~.03. This reflects the results of [1] on page 6.\n",
    "\n",
    "What about the double versions? Here is where we see matching to some extent the suggested results in [2]. While Double Sarsa outperforms Sarsa at higher learning rates, Double Expected Sarsa does not outperform Expected Sarsa in average expected reward. Furthermore the difference in performance as the policy becomes less variant (lower $\\epsilon$) decreases as well. [2] suggests that double Sarsa should perform better with more variance in the Q values, and we see that here. Particularly, Double Sarsa matches the performance of Sarsa even at higher learning rates. However, Figure 6 in [2] suggests that performance differences may be negligable in deterministic environments.\n",
    "\n",
    "Double Sarsa experiences a decay in average reward as $\\alpha \\rightarrow 1$ as would be expected from [1,2]'s experiments. The same happens with Sarsa, but to a much greater extent. We found that running fewer episodes prevents Double Sarsa from experiencing this decay as well and we posit that running trials with more episodes will drive Double Sarsa and both versions of Expected Sarsa to decay more as seen in [1,2]. Furthermore, [2] shows that this decay is more prominent in stochastic environments, which we will look at next.\n",
    "\n",
    "Overall, we can see from these graphs that a higher $\\epsilon$ value indicating more variant policies, increases the gap in maximum average reward at the optimal learning rate. This reflects the formulaic intuition presented in the previous section. Furthermore, the double versions of SARSA improves on Sarsa at high learning rates (likely due to the stabilization provided by using multiple estimators).\n",
    "\n",
    "Note we also look at the average variance of Q across trials:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .3\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/var_ep.03.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .1\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/var_ep.1.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .01\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/var_ep.01.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print(\"Epsilon = .3\")\n",
    "display(Image(url=\"images/var_ep.03.png\", width=500, unconfined=True))\n",
    "print(\"Epsilon = .1\")\n",
    "display(Image(url=\"images/var_ep.1.png\", width=500, unconfined=True))\n",
    "print(\"Epsilon = .01\")\n",
    "display(Image(url=\"images/var_ep.01.png\", width=500, unconfined=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As can be seen from the above graphs, the variance of Q in Double Expected Sarsa is kept down across all $\\epsilon$ and alpha values, followed by regular double Sarsa and Expected Sarsa. As is expected, regular Sarsa has a much higher variance correlating to decreased performance on the average reward (note how the drop off is at nearly identical points in the graph as the spike in variance).\n",
    "\n",
    "### What about stochastic environments?\n",
    "\n",
    "We now hold the $\\epsilon$ value for the policy constant (= .1) and run the experiment in a stochastic gridworld environment to compare results against our deterministic environment. As in [1,2] we analyze the difference in performance across stochasticity in the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .1\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/stochastic_gw_rwd_vs_alpha.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print(\"Epsilon = .1\")\n",
    "display(Image(url=\"images/stochastic_gw_rwd_vs_alpha.png\", width=500, unconfined=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once again our results reflect findings in [1,2], with all methods experiencing a dropoff in average reward as we increase the learning rate. Similarly to [1], we find that Expected Sarsa and Sarsa perform similarly at low values of alpha, but quickly diverge as $\\alpha \\rightarrow 1$, with Expected Sarsa performing slightly better.\n",
    "Note that both Sarsa and Expected Sarsa obtain a higher average reward at lower values of $\\alpha$. This can be explained by faster learning relative to the dual-estimator methods due to the double method Q values only \"seeing\" half the data as seen in class.  \n",
    "\n",
    "However this is an environment where the double-based methods really shine in controlling variance. Similarly to [2], we find that both methods outperform the non-double methods in this stochastic environment, with a much larger gap in average reward forming as we increase as $\\alpha \\rightarrow 1$ when compared to the deterministic environment for the same $\\epsilon$ value. The dual-estimator, as described in [2,5], results in a smoothing out of the variance. This allows for a higher learning rate to be used with less rapid divergence, as shown by the lower dropoff for both Double Sarsa and Double Expected Sarsa.  \n",
    "\n",
    "Furthermore, we prove here that it is in fact the policy and Q variance that affects the maximum overall reward as described theoretically, not the environment stochasticity. As seen here, at optimal $\\alpha$ values we have the same or very similar maximum reward for all methods. \n",
    "\n",
    "\n",
    "### Other experiments (different environments)\n",
    "\n",
    "Finally, we run the experiments in our own custom maze experiment, once again with a constant $\\epsilon$ value of 0.1 while varying $\\alpha$.  \n",
    "\n",
    "\n",
    "#### Windy Maze with Cliffs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epsilon = .1\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/maze_var_vs_alpha.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<img src=\"images/maze_avg_reward.png\" width=\"500\" class=\"unconfined\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print(\"Epsilon = .1\")\n",
    "display(Image(url=\"images/maze_var_vs_alpha.png\", width=500, unconfined=True))\n",
    "\n",
    "display(Image(url=\"images/maze_avg_reward.png\", width=500, unconfined=True))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately due to this experiment taking more than an hour to run for a single trial of 10000 episodes, only a single trial of 1000 episodes could be run for each value of $\\alpha$. \n",
    "\n",
    "We see the variance rise with alpha and the average reward go down. As expected with the theory, this matches previous results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Citations and Footnotes\n",
    "\n",
    "[1] Van Seijen, Harm, et al. \"A theoretical and empirical analysis of Expected Sarsa.\" Adaptive Dynamic Programming and Reinforcement Learning, 2009. ADPRL'09. IEEE Symposium on. IEEE, 2009. http://webdocs.cs.ualberta.ca/~vanseije/resources/papers/vanseijenadprl09.pdf\n",
    "\n",
    "[2] Ganger, Michael, Ethan Duryea, and Wei Hu. \"Double Sarsa and Double Expected Sarsa with Shallow and Deep Learning.\" Journal of Data Analysis and Information Processing 4.04 (2016): 159. http://file.scirp.org/pdf/JDAIP_2016101714072270.pdf\n",
    "\n",
    "[3] Information on unbiased estimators: https://onlinecourses.science.psu.edu/stat414/node/192\n",
    "\n",
    "[4] Full derivation on providing a weighted unbiased estimate of variance: http://mathoverflow.net/questions/11803/unbiased-estimate-of-the-variance-of-a-weighted-mean\n",
    "\n",
    "[5] Double-Q Learning https://papers.nips.cc/paper/3964-double-q-learning.pdf\n",
    "\n",
    "[6] https://github.com/rlpy/rlpy/blob/master/rlpy/Domains/IntruderMonitoring.py\n",
    "\n",
    "[7] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. Vol. 1. No. 1. Cambridge: MIT press, 1998."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}