5 - Monte Carlo Method.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Monte Carlo Method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MC Prediction: State Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recapitulating a littel bit, remember that in a RL environment, an *episode* is basically a sequence of *states*, *actions* and *rewards* that are obtained at each time step. Remember that time is broken down into discrete time steps and that at each one of this time steps, the agent receives a reward and a state and chooses an action to perform in response.\n",
    "$$S_0, A_0, R_1, S_1, A_1, R_2, ..., S_T$$\n",
    "\n",
    "where $S_T$ is the terminal state of an episode."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also remember that in the Dynamic Programing setting, the goal of the agent is to find the optimal policy in order to maximize the <u>expected cumulative reward</u>:\n",
    "\n",
    "$$\\text{Find } \\pi \\text{that maximizes }\\mathbb{E}_\\pi[\\sum_{t=1}^T R_t]$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Towards this goal, we'll start with the prediction problem, which is the following:\n",
    "\n",
    "$$\\text{Given a policy }\\pi\\text{, determine (from interaction with the environment) }v_\\pi \\text{(or }q_\\pi\\text{)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But in order to do this, the agent must have a policy to follow. Remember (again) that there are two kinds of methods for function value estimation: *Off-Policy Methods* and *On-Policy Methods*.\n",
    "\n",
    " + *Off-Policy methods* generate episodes from following a policy $b$, where $b \\neq \\pi$. Then uses the episdoe to estimate $v_\\pi$.\n",
    " + *On-Policy methods* generate episodes from following policy $\\pi$. Then uses the episodes to estimate $v_\\pi$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, what does MC prediction of the state values does?.\n",
    "\n",
    "This is an agent that interacts with the environment following a given policy, collecting or keeping a record of all the states, the rewards and the actions it observed until it reaches the terminal estate. Then, for each different state in the steate space (i.e. $S^+$) in the recorded episode, it estimate its value function as the average of the sum of the rewards it got after the state was visited (observed).\n",
    "\n",
    "If a state appears more than once in the episode there are then two flavors of the Monte Carlo predicton algorithm to choose from:\n",
    " * First visit\n",
    "     - For each episdoe, only consider the first visti to the state and average those returns (of all episodes). This is called the **first visit MC method**.\n",
    " * Every visit\n",
    "     - Average the return following all visits to a given state in all episodes. Thsi is called the **every visit MC method**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see a very simple example to ilustrate how this algorithm works.\n",
    "\n",
    "Let's assume we have an MDP with 3 states, and two possible actions:\n",
    "\n",
    "$\\quad S^+ = \\{X, Y, Z\\};$<br>\n",
    "Where:<br>\n",
    "$\\quad\\text{    Z = Terminal state}$<br>\n",
    "$\\quad\\text{    A = }\\{\\uparrow, \\downarrow\\}$\n",
    "\n",
    "Similar to the [frozen lake environment](https://gym.openai.com/envs/FrozenLake-v0), the world is slippery, so the agent could choose action $\\downarrow$ but it could actually move up or stay in its original position (this is given by a positive probability).\n",
    "\n",
    "The agent could interact with the environment by following this policy:\n",
    "$$\\pi(X) = \\uparrow$$\n",
    "$$\\pi(Y) = \\downarrow$$\n",
    "\n",
    "\n",
    "The agent has to determine $v_\\pi$.\n",
    "\n",
    "When the environment starts, it throws to the agent the first initial state. Let's assume this first state is the state $X$. Then the agent follows the policy presented above until it reaches the terminal state. The agent keeps a record of the states, the rewards and the actoins it took:\n",
    " * Episode 1:\n",
    "  + $X$, $\\uparrow$, $-2$, $Y$, $\\downarrow$, $0$, $Y$, $\\downarrow$, $3$, $Z$\n",
    " * Episode 2:\n",
    "  + $Y$, $\\downarrow$, $2$, $Y$, $\\downarrow$, $1$, $Y$, $\\downarrow$, $0$, $Z$\n",
    " * Episode 3:\n",
    "  + $Y$, $\\uparrow$, $1$, $X$, $\\uparrow$, $-3$, $Y$, $\\downarrow$, $3$, $Z$\n",
    "  \n",
    "We can then use these episodes to estimate the value function (let's assume they are sufficient for the agent to gain a great deal of understanding of the environment).\n",
    "  \n",
    "First we take **state $X$**, and *sum the rewards* we got after this state was visited (we assume gamma = 1).\n",
    " * Episode 1: $-2 + 0 + 3 = 1$\n",
    " * Episode 2: $-3 + 3 = 0$\n",
    " \n",
    "The Monte Carlo prediction algorithm takes the average of these values and plugs it in as an estimate for the values of state X:\n",
    "$$v_\\pi(X) = \\frac{1 + 0}{2} \\approx \\frac{1}{2}$$\n",
    "\n",
    "When trying to estimate the state Y, we see it appears more than once in every episode - <u><i>What to do in this case?</i></u>\n",
    "\n",
    "Under this circumstance, we need to decide if we apply the *first-visit method* or the *every-visit method*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<u>The *MC prediction for state values* algorithm is described as follows:</u>\n",
    "\n",
    "**Input:** policy $\\pi$, positive integer num_episodes<br>\n",
    "**Output:** value function $V$ ($\\approx v_\\pi$ if num_episodes is large enough)<br>\n",
    "Initialize $N(s) = 0$ for all $s \\in S$<br>\n",
    "Initialize $returns\\_sum(s) = 0$ for all $s \\in S$<br>\n",
    "**for** $i \\leftarrow 1$ to $num\\_episodes$ **do**<br>\n",
    "|     Generate an episdoe $S_0, A_0, R_0, ..., S_T$ using $\\pi$<br>\n",
    "|     **for** $t \\leftarrow 0$ to $T -1$ **do**<br>\n",
    "|     |     **if** $S_t$ is a first visit (with return $G_t$ **then**<br>\n",
    "|     |     |     $N(S_t) \\leftarrow N(S_t) + 1$<br>\n",
    "|     |     |     $returns\\_sum(S_t) \\leftarrow returns\\_sum(S_t) + G_t$<br>\n",
    "|     **end**<br>\n",
    "**end**<br>\n",
    "$V(s) \\leftarrow \\frac{returns\\_sum(s)}{N(s)}$ for all $s \\in S$<br>\n",
    "**return** $V$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MC Prediction: Action Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have seen how to use the MC Prediction algorithm to get a state's value. We can use this algorith to get also the action values. The way this works is, instead of looking at the visits to each state, we will loot at the visits to each possible state-action pair. Then we will compute the returns that followed from each state-action pair and average them as before."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, let's take the resulted three episodes from our last example:\n",
    "\n",
    "$\\quad S^+ = \\{X, Y, Z\\}$<br>\n",
    "$\\quad A = \\{\\uparrow, \\downarrow\\}$<br>\n",
    "The plociy:<br>\n",
    "$\\quad\\pi(X) = \\uparrow$<br>\n",
    "$\\quad\\pi(Y) = \\downarrow$<br>\n",
    "The episodes:<br>\n",
    "$\\quad \\text{Episode 1: }X, \\uparrow, -2, Y, \\downarrow, 0, Y, \\downarrow, 3, Z$<br>\n",
    "$\\quad \\text{Episode 2: }Y, \\downarrow, 2, Y, \\downarrow, 1, Y, \\downarrow, 0, Z$<br>\n",
    "$\\quad \\text{Episode 3: }Y, \\downarrow, 1, X, \\uparrow, -3, Y, \\downarrow, 3, Z$<br>\n",
    "\n",
    "Following a virst visit,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To calculate the action value for the state-action pair $\\{X,\\uparrow\\}$, we have to spot the first visit of such state-action pair in each one of the episodes:<br>\n",
    "    Episode 1: $\\underline{X, \\uparrow}, -2, Y, \\downarrow, 0, Y, \\downarrow, 3, Z$<br>\n",
    "    Episode 2: $Y, \\downarrow, 2, Y, \\downarrow, 1, Y, \\downarrow, 0, Z$<br>\n",
    "    Episode 3: $Y, \\downarrow, 1, \\underline{X, \\uparrow}, -3, Y, \\downarrow, 3, Z$<br>\n",
    "    \n",
    "Now, we have the following rewards found after the first visit of the state-action pair $\\{X, \\uparrow\\}$ on each episodes:<br>\n",
    "    For episode 1: $-2 + 0 + 3 = 1$<br>\n",
    "    For episode 2: $0$<br>\n",
    "    For episode 3: $-3 + 3 = 0$<br>\n",
    "And the final value of this state-action pair will be the average of the total amount of reward found on each of the episodes:\n",
    "\n",
    "$$q_\\pi(X, \\uparrow) = \\frac{1 + 0}{2} \\approx \\frac{1}{2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To calculate the action value for the state-action pair $\\{Y,\\downarrow\\}$, we have to spot the first visit of such state-action pair in each one of the episodes:<br>\n",
    "    Episode 1: $X, \\uparrow, -2, \\underline{Y, \\downarrow}, 0, Y, \\downarrow, 3, Z$<br>\n",
    "    Episode 2: $\\underline{Y, \\downarrow}, 2, Y, \\downarrow, 1, Y, \\downarrow, 0, Z$<br>\n",
    "    Episode 3: $\\underline{Y, \\downarrow}, 1, X, \\uparrow, -3, Y, \\downarrow, 3, Z$<br>\n",
    "    \n",
    "Now, we have the following rewards found after the first visit of the state-action pair $\\{Y, \\downarrow\\}$ on each episodes:<br>\n",
    "    For episode 1: $0 + 3 = 3$<br>\n",
    "    For episode 2: $2 + 1 + 0 = 3$<br>\n",
    "    For episode 3: $1 -3 + 3 = 1$<br>\n",
    "And the final value of this state-action pair will be the average of the total amount of reward found on each of the episodes:\n",
    "\n",
    "$$q_\\pi(X) = \\frac{3 + 3 + 1}{3} \\approx \\frac{7}{3}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If a pair is visited more than once in each episode, (like the pair $\\{Y, \\downarrow\\}$ in this example), we have the choise of either only taking into consideration the first-visit to the pair or using every visit to calculate the aciton value estimate. The returned value on each of these approaches is differet. I.e. the first visit method returns seven thirds while the every-visit MC method returns two."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the agent gets more experienced by collecting more episodes, these values will converge to the same number.\n",
    "\n",
    "**Remeber this:** Do not try to evaluate the action value function for a deterministic policy. Otherwise the action-value function estimate will always be incomplete. So, in the examples avobe we used a deterministic policy to illustrate how the methods work. In reality we should have evaluated a policy like the following:\n",
    "\n",
    "$\\pi(\\uparrow \\mid X) = 0.9$     $\\pi(\\uparrow \\mid Y) = 0.2$<br>\n",
    "$\\pi(\\downarrow \\mid X) = 0.1$     $\\pi(\\downarrow \\mid Y) = 0.8$<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For stochastic policies (all actions have a non-zero probability of being taken at each state), each state-action pair is eventually visitied by the agent and furthermore, in the limit as the number of episodes goes to infinity, so does the nu ber of visits to each state-action pair. That guarranties that we'll be able to calculate a nice action value function estimate for each state-action pair as long as the agent interacts with the environment in enough episodes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<u>The *MC prediction for action values* algorithm is described as follows:</u>\n",
    "\n",
    "**Input:** policy $\\pi$, positive integer num_episodes<br>\n",
    "**Output:** value function $Q$ ($\\approx q_\\pi$ if num_episodes is large enough)<br>\n",
    "Initialize $N(s, a) = 0$ for all $s \\in S, a \\in A(s)$<br>\n",
    "Initialize $returns\\_sum(s, a) = 0$ for all $s \\in S, a \\in A(s)$<br>\n",
    "**for** $i \\leftarrow 1$ to $num\\_episodes$ **do**<br>\n",
    "|     Generate an episdoe $S_0, A_0, R_0, ..., S_T$ using $\\pi$<br>\n",
    "|     **for** $t \\leftarrow 0$ to $T -1$ **do**<br>\n",
    "|     |     **if** $(S_t, A_t)$ is a first visit (with return $G_t$ **then**<br>\n",
    "|     |     |     $N(S_t, A_t) \\leftarrow N(S_t, A_t) + 1$<br>\n",
    "|     |     |     $returns\\_sum(S_t, A_t) \\leftarrow returns\\_sum(S_t, A_t) + G_t$<br>\n",
    "|     **end**<br>\n",
    "**end**<br>\n",
    "$Q(s, a) \\leftarrow \\frac{returns\\_sum(s, a)}{N(s, a)}$ for all $s \\in S, a \\in A(s)$<br>\n",
    "**return** $Q$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generalized Policy Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the Monte Carlo Prediction method to solve the \"*Prediction Problem*\"; that is, given a policy $\\pi$, determine $v_\\pi$ (or $q_\\pi$).\n",
    "\n",
    "**How might an agent learn an optimal policy through interaction with the environment?**\n",
    "\n",
    "That is the question tha *MC Control* method solves.\n",
    "\n",
    "To understand the MC Control, it is usefull to first revisit what it has been done in the [Dynamic Programming setting](./4%20-%20Dynamic%20Programming.ipynb) and refresh our undestanding of how such setting is done.<br>\n",
    "Even when these algorithms are different, it will be useful to focus on what they have in common, and  that is basically a cycle between evaluation step(s) and Improvement step(s) that repeat again and again until a condition is fullfiled (i.e. the algorithm converges to a value)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monte Carlo Control Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *Monte Carlo Control Algorithm* will draw inspiration from the *generalized policy iteration*.\n",
    "Previously we have seen some implementation in which an agent goes through huge amounts of episodes before it gets a good estimate of the value functions (remember the implementation done for Black Jack, in which the agent had to go through 500 000 games before making a good estimate). <br>\n",
    "In the context of policy iteration, this seems to be too long to spend evaluating a policy before trying to improve it.<br>\n",
    "*We will try to improve the policy after every single episode.*\n",
    "\n",
    "But before, let's remember some stuff; in the prediction problem, the return that follows after a certain state is visited by the agent (the first visit of such state) is calculated (summed) and then we take the average.<br>\n",
    "In a more general way, we visit the same state-action pair *\"n\"* times\n",
    "<center>\n",
    "\n",
    "$$x_1, x_2, x_3, ..., x_n \\rightarrow \\text{Returns that follow the same (state, action) pair.}$$\n",
    "\n",
    "</center>\n",
    "\n",
    "So, the value function estimation can be calculated as the average of those values:\n",
    "\n",
    "$$\\mu_n = \\frac{1}{n}\\sum_{j = 1}^n x_j$$\n",
    "Thsi is the action-value estimate.\n",
    "\n",
    "Now, instead of calculating the average at the end of all episodes, we could instead iteratively update the estimate after every visit.\n",
    "![IterativeEstimateReturns](./images/IterativeEstimateReturns.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will do some math tricks to be able to accomplish this calculation efficiently:<br>\n",
    "$\\mu_k = \\frac{1}{k}\\sum_{j = 1}^kx_j \\rightarrow \\text{Estimate for the return}$<br>\n",
    "Rewrite the sum of the first $k$ returns, as the sum of the first $(k - 1)$ returns, plus the $k_{th}$ return:<br>\n",
    "$\\quad = \\frac{1}{k}(x_k + \\sum_{j = 1}^{k - 1}x_j)$<br>\n",
    "We are going to need this formula in a couple of steps, but first:<br>\n",
    " - $\\mu_{k - 1} = \\frac{1}{k -1}\\sum_{j = 1}^{k - 1}x_j \\rightarrow \\text{here we rewrite the sum of the k - 1 returns, and from here we get:}$ <br>\n",
    " - $(k-1)\\mu_{k-1} = \\sum_{j=1}^{k-1}x_j$<br>\n",
    "\n",
    "Now we will re-express the sum of the first $(k-1)$ returns as the $k-1$ mean times $(k-1)$:\n",
    "\n",
    "$\\quad = \\frac{1}{k}(x_k + (k-1)\\mu_{k-1}$\n",
    "\n",
    "Finally, if we rearrange this term, we get the following formula:\n",
    "$$\\mu_k = \\mu_{k-1} + \\frac{1}{k}(x_k - \\mu_{k-1})$$\n",
    "This formula is used to design an algorithm that keeps a running mean of the returns:<br>\n",
    "$\\mu \\leftarrow 0$ initialize the mean<br>\n",
    "$k \\leftarrow 0$ initialize return index<br>\n",
    "While $k < n$<br>\n",
    "|     $k \\leftarrow k + 1$ update return index<br>\n",
    "|     $\\mu \\leftarrow \\mu + \\frac{1}{k}(x_k - \\mu)$ update the mean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This last algorithm can only update the value function estimate corresponding to a single state-value pair. This algorithm will be changed a little bit so that it can mantain estimates of value for many state-action pairs. This new algorithm will be used as a new and improved *evaluation step*:\n",
    "![MCControlPolicyEvaluation](./images/MCControlPolicyEvaluation.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Having this *MC Control Policy* evaluation algorithm, let's explore if there is a way to improve our policy.\n",
    "\n",
    "We could use the *Policy Improvement algorithm* from the Dynamic Programming case together with the *Policy Evaluation* algorithm that we just learned, but we need to make some modifications.\n",
    "First of all, we do not want to use a greedy policy. When we are in a situation in which an action seems to be more favorable than other, we need to spend more time making sure of that to make sure our early perceptions are correct. That means that we need to be more explorative - that is, we need to explore other actions even if they do not seem more favorable, to either be sure they are not or to find out that in fact they are more favorable. So, instead of constructing a greey policy, a better policy would be a stochastic one. A policy that picks a favorable action with - let's say - 95% probability and another action - not so favorable - with - let's say - 5% probability. That is still close to a greedy policy, but at some point the agent will pick other actions (not so favorable at the time of picking) which could lead to a better and more complete understanding of the environment and that allow us to improve our policy in a more \"informed\" way.\n",
    "With this idea in mind we can define the Monte Carlo version of policy improvement. This improvement is the **Epsilon-Greedy Policy**.\n",
    "\n",
    "Let's see a comparison between a *Greedy Policy* and an *Epsilon Greedy Policy*:\n",
    "<center><h2>Greedy Poliy</h2></center>\n",
    "\n",
    "$$\\pi(s) \\longleftarrow arg\\ max_{a \\in A(s)} Q(s, a) \\text{ for all } s \\in S$$\n",
    "\n",
    "<center><h2>Epsilon-Greedy Poliy</h2></center>\n",
    "\n",
    "$$\\pi(a \\mid s) \\longleftarrow \\begin{cases}1 - \\epsilon + \\frac{\\epsilon}{\\vert A(s)\\vert}; & \\text{if } a = arg\\ max_{a' \\in A(s)} Q(s, a')\\\\\n",
    "\\frac{\\epsilon}{\\vert A(s)\\vert}; & \\text{otherwise}\n",
    "\\end{cases}$$\n",
    "\n",
    "<br>\n",
    "<center><span style=\"color:green\">\n",
    "\n",
    "$\\text(\\vert A(s)\\vert) = \\text{number of possible actions from state } s \\in S$\n",
    "\n",
    "</span></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In an Epsilon-Greedy Policy we'll choose a value $\\epsilon$ such that $0 < \\epsilon \\leq 1$, but here the idea is to have $\\epsilon$ closer to zero than to one.\n",
    "\n",
    "So, with <span style=\"color:blue\">probability $\\epsilon$</span>, the agen will randomly select an action and with <span style=\"color:red\">probability $1 - \\epsilon$</span> the agent will select a value returned by its greedy policy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, taking our new Epsilon-Greedy Policy into consideration and integrating it to our MC Control algorithm it finally looks as follow:\n",
    "![MCControlAllTogether](./images/MCControlAllTogether.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MC Control: Constant-alpha"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far, with our *MC Control algorithm* our agent generates an episode based on the interaction it does with the environment. While interacting with the environment, it run through the episodes it generates, and whenever it visits a state-action pair (either on the first visit or in the every-visit version) it calculates the return that follows at each time step. Then the agent uses that return to update its estimate. Such update step for the policy evaluation is done following the following formula:\n",
    "$$Q(S_t, A_t) \\longleftarrow Q(S_t, A_T) + \\frac{1}{N(S_t, A_t)}\\big(G_t - Q(S_t,A_T)\\big)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this formula we have the following:\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "G_t & \\text{This is the most recently sampled return} \\\\\n",
    "Q(S_t, A_t) & \\text{Value of the (state-action) pair}\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we also have the following:\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "G_t & \\text{What the return actually was} \\\\\n",
    "Q(S_t, A_t) & \\text{The return that we expected}\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we know that $\\big(G_t - Q(S_t, A_t)\\big)$ is our error. We define this error as $\\delta_t$:<br>\n",
    "if $\\delta_t > 0$, then the algorithm increases $(Q(S_t, A_t).$<br>\n",
    "if $\\delta _t< 0$, then the algorithm decreases $Q(S_t,A_t)$\n",
    "\n",
    "Let's think about how much the algorithm increases or decreases the estimation and the action value function at each step. These increases and decreases are currently defined by an amount inversely proportional to the number of times that we've visited the state-action pair:\n",
    "$\\frac{1}{N(S_t, A_t)}$.<br>\n",
    "At the begining (and during the first few times) each change is going to be quite large. But as the algorithm visits more and more state-action pairs, the denominator of this fraction gets bigger and bigger and therefore the changes get smaller and smaller. This has the efect that the algorithm tends to \"remember\" too much what it \"learned\" at the very early steps, and tends to -kind of- ignore what it learns at later steps. It does not really ignore what it learns, it simply does not learn from this later experiences as much as it did from the earlier experiences.\n",
    "\n",
    "So, instead of changing the estimate and the actual value function by $\\frac{1}{N(S_t,A_t)}$, we could change it by a cosntant - denoted here by alpha $\\alpha$.\n",
    "\n",
    "$$Q(S_t, A_t) \\longleftarrow Q(S_t, A_t) + \\alpha\\big(G_t - Q(S_t, A_t)\\big)$$\n",
    "\n",
    "This ensures that returns that come later are more emphasized than those that arrived earlier. In this way, the agent will mostly trust the most recent returns, and gradually will forget about those that came in the past.\n",
    "\n",
    "**This is quite important because remember that the policy is constantly changing, and with every step becoming more optimal**.\n",
    "\n",
    "Our final MC Control algorithm as follows:\n",
    "\n",
    "![MCControl-Constant Alpha](./images/MCControl-ConstantAlpha.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![MCControl-Constant Alpha](./images/MonteCarloSummary1.png)\n",
    "![MCControl-Constant Alpha](./images/MonteCarloSummary2.png)\n",
    "![MCControl-Constant Alpha](./images/MonteCarloSummary3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implementation of the algorithms here described is found in this [notebook](./notesMiniProjects/MonteCarlo/Monte_Carlo.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.10 ('base')",
   "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.9.10"
  },
  "vscode": {
   "interpreter": {
    "hash": "d4d1e4263499bec80672ea0156c357c1ee493ec2b1c70f0acce89fc37c4a6abe"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}