01. Fundamentals of Reinforcement Learning/1.08.  Return, Discount Factor and Math Essentials.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Return, Discount Factor and Math Essentials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Return and discount factor\n",
    "A return can be defined as the sum of the rewards obtained by the agent in an episode. The return is often denoted by  $R$ or $G$. Say, the agent starts from the initial state at time step  $t=0$ and reaches the final state at a time step $T$, then the return obtained by the agent is given as:\n",
    "\n",
    "$$\\begin{aligned}R(\\tau) &= r_0 + r_1+r_2+\\dots+r_T \\\\ &\\\\\n",
    "R(\\tau) &= \\sum_{t=0}^{T-1} r_t \\end{aligned} $$\n",
    "\n",
    "Let's understand this with an example, consider the below trajectory $\\tau$:\n",
    "\n",
    "![title](Images/25.PNG)\n",
    "\n",
    "\n",
    "The return of the trajectory is the sum of the rewards, that is, $R(\\tau) = 2+ 2+1 +2 = 7$\n",
    "\n",
    "Thus, we can say that the goal of our agent is to maximize the return, that is, maximize the sum of rewards(cumulative rewards) obtained over the episode. How can we maximize the return? We can maximize the return if we perform correct action in each state. Okay, how can we perform correct action in each state? We can perform correct action in each state using the optimal policy. Thus, we can maximize the return using the optimal policy. \n",
    "\n",
    "Thus, we can redefine the optimal policy as the policy which gets our agent the maximum return (sum of rewards) by performing correct action in each state. \n",
    "\n",
    "Okay, how can we define the return for continuous tasks? We learned that in continuous tasks there are no terminal states, so we can define the return as a sum of rewards up to infinity:\n",
    "$$R(\\tau) = r_0 + r_1+r_2+\\dots+r_{\\infty} $$\n",
    "\n",
    "\n",
    "But how can we maximize the return which just sums to infinity? So, we introduce a notation of discount factor $\\gamma$ and rewrite our return as:\n",
    "\n",
    "$$\\begin{aligned}R(\\tau) &= \\gamma^0 r_0 + \\gamma^1 r_1+ \\gamma^2 r_2+\\dots+ \\gamma^nr_{\\infty} \\\\&\\\\R(\\tau) & = \\sum_{t=0}^{\\infty} \\gamma^t r_t \\end{aligned} $$\n",
    "\n",
    "Okay, but the question is how this discount factor  $\\gamma$ is going to help us?  It helps us in preventing the return reaching up to infinity by deciding how much importance we give to future rewards and immediate rewards. The value of the discount factor ranges from 0 to 1. When we set the discount factor to a small value (close to 0) then it implies that we give more importance to immediate reward than the future rewards and when we set the discount factor to a high value (close to 1) then it implies that we give more importance to future rewards than the immediate reward. Let us understand this with an example with different values of discount factor:\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Small discount factor\n",
    "\n",
    "Let's set the discount factor to a small value, say 0.2, that is, let's set $\\gamma = 0.2$, then we can write:\n",
    "$$ \\begin{aligned}R &= (\\gamma)^0 r_0 + (\\gamma)^1 r_1+ (\\gamma)^2 r_2 +  \\dots \\\\&\\\\&=(0.2)^0 r_0 + (0.2)^1 r_1+ (0.2)^2 r_2 +  \\dots\\\\&\\\\&= (1) r_0 + (0.2) r_1+ (0.04) r_2+ \\dots \\end{aligned} $$\n",
    "\n",
    "\n",
    "From the above equation, we can observe that the reward at each time step is weighted by a discount factor. As the time step increases the discount factor (weight) decreases and thus the importance of rewards at future time steps also decreases. That is, from the above equation, we can observe that:\n",
    "\n",
    "* At the time step 0, the reward $r_0$ is weighted by the discount factor 1\n",
    "* At the time step 1, the discount factor is heavily decreased and the reward  $r_1$ is weighted by the discount factor 0.2\n",
    "* At the time step 2, the discount factor is again decreased to 0.04 and the reward $r2$ is weighted by the discount 0.04\n",
    "\n",
    "As we can observe, the discount factor is heavily decreased for the subsequent time steps and more importance is given to the immediate reward $r_0$ than the rewards obtained at the future time steps. Thus, when we set the discount factor to a small value we give more importance to the immediate reward than the future rewards. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## High discount factor\n",
    "Let's set the discount factor to a high value, say 0.9, that is, let's set, $\\gamma = 0.9$ , then we can write:\n",
    "\n",
    "$$\\begin{aligned}R &=(\\gamma)^0 r_0 + (\\gamma)^1 r_1+ (\\gamma)^2 r_2 +  \\dots \\\\&\\\\ &=(0.9)^0 r_0 + (0.9)^1 r_1+ (0.9)^2 r_2 +  \\dots\\\\&\\\\&= (1) r_0 + (0.9) r_1+ (0.81) r_2+ \\dots  \\end{aligned} $$\n",
    "\n",
    "From the above equation, we can infer that as the time step increases the discount factor (weight) decreases, however, it is not decreasing heavily unlike the previous case since here we started off with $\\gamma=0.9$. So in this case, we can say that we give more importance to future rewards. That is, from the above equation, we can observe that:\n",
    "\n",
    "* At the time step 0, the reward  $r_0$ is weighted by the discount factor 1\n",
    "* At the time step 1, the discount factor is decreased but not heavily decreased and the reward $r_1$  is weighted by the discount factor 0.9\n",
    "* At the time step 2, the discount factor is decreased to 0.81 and the reward $r_2$ is weighted by the discount 0.81\n",
    "\n",
    "\n",
    "As we can observe the discount factor is decreased for the subsequent time steps but unlike the previous case, the discount factor is not decreased heavily. Thus, when we set the discount factor to high value we give more importance to future rewards than the immediate reward. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What happens when we set the discount factor to 0?\n",
    "\n",
    "When we set the discount factor to 0, that is $\\gamma=0$, then it implies that we consider only the immediate reward $r_0$ and not the reward obtained from the future time steps. Thus, when we set the discount factor to 0 then the agent will never learn considering only the immediate reward $r_0$ as shown below:\n",
    "\n",
    "$$\\begin{aligned}R &=(\\gamma)^0 r_0 + (\\gamma)^1 r_1+ (\\gamma)^2 r_2 + \\dots \\\\&\\\\ &=(0)^0 r_0 + (0)^1 r_1+ (0)^2 r_2 +  \\dots\\\\&\\\\& = r_0 \\end{aligned} $$\n",
    "\n",
    "As we can observe when we set $\\gamma=0$, then our return will be just the immediate reward $r_0$.\n",
    "\n",
    "\n",
    "\n",
    "## What happens when we set the discount factor to 1?\n",
    "\n",
    "When we set the discount factor to 1, that is $\\gamma=1$, then it implies that we consider all the future rewards. Thus, when we set the discount factor to 1 then the agent will learn forever looking for all  the future reward which may lead to infinity as shown below:\n",
    "\n",
    "$$\\begin{aligned}R &=(\\gamma)^0 r_0 + (\\gamma)^1 r_1+ (\\gamma)^2 r_2 + \\dots \\\\&\\\\&=(1)^0 r_0 + (1)^1 r_1+ (1)^2 r_2 +  \\dots\\\\&\\\\& = r_0 + r_1 + r_2 + \\dots \\end{aligned} $$\n",
    "\n",
    "As we can observe when we set $\\gamma=1$, then our return will be the sum of rewards up to infinity. \n",
    "\n",
    "Thus, we learned that we set discount factor to 0 then the agent will never learn considering only the immediate reward and when we set the discount factor to 1 the agent will learn forever looking for the future rewards which lead to infinity. So the optimal value of the discount factor lies between 0.2 to 0.8.\n",
    "\n",
    "But the question is why should we care about immediate and future rewards? we give importance to immediate reward and future rewards depending on the tasks. In some tasks, future rewards are more desirable than immediate reward and vice versa. In a chess game, the goal is to defeat the opponent's king. If we give more importance to the immediate reward, which is acquired by actions like our pawn defeating any opponent chessman and so on, then the agent will learn to perform this sub-goal instead of learning the actual goal. So, in this case, we give importance to future rewards than the immediate reward, whereas in some cases, we prefer immediate rewards over future rewards. Say, would you prefer chocolates if I gave you them today or 13 days later?\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Math Essentials \n",
    "\n",
    "\n",
    "Before looking into the next important concept in reinforcement learning, let's quickly recap expectation as we will be dealing with expectation throughout the book.\n",
    "\n",
    "\n",
    "## Expectation \n",
    "\n",
    "Let's say we have a variable X and it has the following values 1,2,3,4,5,6. To compute the average value of X, we can just sum all the values of X divided by the number of values of X. Thus, the average of X is (1+2+3+4+5+6)/6 = 3.5\n",
    "\n",
    "Now, let's suppose X is a random variable. The random variable takes value based on the random experiment such as throwing dice, tossing a coin and so on. The random variable takes different values with some probabilities. Let's suppose we are throwing a fair dice then the possible outcomes (X) are 1,2,3,4,5,6 and the probability of occurrence of each of these outcomes is 1/6 as shown below:\n",
    "\n",
    "\n",
    "![title](Images/26.PNG)\n",
    "\n",
    "How can we compute the average value of the random variable X? Since each value has a probability of an occurrence we can't just take the average. So, what we will do is that here we will compute the weighted average, that is, the sum of values of X multiplied by their respective probabilities and this is called expectation. The expectation of a random variable X can be defined as:\n",
    "\n",
    "$$E(X) = \\sum_{i=1}^N x_i p(x_i) $$\n",
    "\n",
    "\n",
    "\n",
    "Thus, the expectation of the random variable X is, E(X) = 1(1/6) + 2(1/6) + 3(1/6) + 4(1/6) + 5 (1/6) + 6(1/6) = 3.5\n",
    "\n",
    "The expectation is also known as the expected value. Thus, the expected value of the random variable X is 3.5. Thus, when we say expectation or expected value of a random variable it basically means the weighted average.\n",
    "\n",
    "Now, we will look into the expectation of a function of a random variable. Let $f(x) = x^2$ then we can write:\n",
    "\n",
    "\n",
    "![title](Images/27.PNG)\n",
    "\n",
    "The expectation of a function of a random variable can be computed as:\n",
    "\n",
    "\n",
    "$$\\mathbb{E}_{x \\sim p(x)}[f(X)] = \\sum_{i=1}^N f(x_i) p(x_i) $$\n",
    "\n",
    "Thus the expected value of f(X) is given as E(f(X)) = 1(1/6) + 4(1/6) + 9(1/6) + 16(1/6) + 25(1/6) + 36(1/6) = 15.1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}