4 -Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dynamic Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introductory example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the Dynamic Programming setting the agent knows the reward structure and it knows how transitions happen between states. So the agent knows how the environment operates (i.e. which transitions between which two states gives bac, which reward).\n",
    "\n",
    "What the agent needs to sort out now, is **how to use this information to find the optimal policy that will maximize the acummulative return**.\n",
    "\n",
    "Let us first determine the value function for a particular policy. To do so it could be usefull to record the returned value of each possible transitions between states. Let's consider the following table, which descritbes the state space of an environment. The table depicts the states, their possible transitions, the probability of each transition to take place and which state is terminal.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| states | Terminal state? |transition | probability of transition| reward | new state |\n",
    "|------|------|------|------|------|------|\n",
    "| $s1$| no | $\\rightarrow$ | $\\pi(rigth \\mid s_1) = 1/2$ | -1 | $s2$ |\n",
    "| $s1$| no | $\\downarrow$ | $\\pi(down \\mid s_1) = 1/2$ | -3 | $s3$|\n",
    "| $s2$| no | $\\leftarrow$ | $\\pi(left \\mid s_2) = 1/2$ | -1 | $s4$ |\n",
    "| $s2$| no | $\\downarrow$ | $\\pi(down \\mid s_2) = 1/2$ | 5 | $s2$ |\n",
    "| $s3$| no | $\\uparrow$ | $\\pi(up \\mid s_3) = 1/2$ | -1 | $s1$|\n",
    "| $s3$| no | $\\rightarrow$ | $\\pi(right \\mid s_3) = 1/2$ | 5 | $s4$|\n",
    "| $s4$| yes\n",
    "| $s4$| yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since state 4 is a terminal state it does not have transitions to other states.\n",
    "\n",
    "From the table above we  get that when the agent is in state $s_1$ it will got *right* half of the time and will go *down* the other half. The expected returns for each of the possible transitions of state $s_1$ are:\n",
    "$$\\mathbb{E_\\pi} = (-1 + v_\\pi(s_2) \\mid transiton= \\rightarrow)$$\n",
    "$$\\mathbb{E_\\pi} = (-3 + v_\\pi(s_3) \\mid transiton= \\downarrow)$$\n",
    "\n",
    "We can say then that the value of state $s1$ can be calculated as the average of these two values - because the agent chooses each of the potential actions whith equal probability:\n",
    "$$v_\\pi(s_1) = 1/2(-1 + v_\\pi(s_2)) + 1/2(-3 + v_\\pi(s_3))$$\n",
    "\n",
    "This is the **Bellman's equation** evaluated at $s1$.\n",
    "This is the value of state $s_1$ in the context of the values of all of its possible suceessor states.\n",
    "*Hint*: When the probability of any given transition between state $s_1$ and the possible successor states (i.e. $s_2$ and $s_3$) changes, then the value of state $s_1$ will also change.\n",
    "\n",
    "We could now write down the value function equations for each of the states. We would have then four equations and we could then solve that system of 4 equations to get the value of the states (of each state).\n",
    "\n",
    "Doing this, we would get that the values of states $s_1$ and $s_4$ is zero(0), and values of states $s_2$ and $s_3$ is (2).\n",
    "The four equations are shown below:\n",
    "\n",
    "$$v_\\pi(s_1) = 1/2(-1 + v_\\pi(s_2)) + 1/2(-3 + v_\\pi(s_3))$$\n",
    "$$v_\\pi(s_2) = 1/2(-1 + v_\\pi(s_1)) + 1/2(5 + v_\\pi(s_4))$$\n",
    "$$v_\\pi(s_3) = 1/2(-1 + v_\\pi(s_1)) + 1/2(5 + v_\\pi(s_4))$$\n",
    "$$v_\\pi(s_4) = 0$$\n",
    "\n",
    "The problem with this approach is that most fo the RL environments (for real life problems) have a huge state space and therefore it would not be practical to be solving equation systems of dozens or hundreds (or thousands maybe) of equations. \n",
    "\n",
    "So, in these cases - that is, when the state space is big- there is a better approach. An iterative approach is used to solve the system - and generally works better ;).\n",
    "\n",
    "In such iterative approach, you start off by making a guess for the values of each state $\\rightarrow$ normally they are guessed as *zero*. It really doesn't matter how the value of the states are guessed; this initial -random- value does not have to be any good.\n",
    "\n",
    "Then a state is choosen to start with -normally $s1$- and its value will be tried to be improved. For this, we will use the *Bellman equation*, but it must be adapted to work as an update rule.\n",
    "$$v_\\pi(s_1) = 1/2(-1 + v_\\pi(s_2)) + 1/2(-3 + v_\\pi(s_3))$$\n",
    "$$V(s_1) = 1/2(-1 + V(s_2)) + 1/2(-3 + V(s_3))$$\n",
    "$V$ - denotes our current guess for the value function.\n",
    "\n",
    "Basically, we sould like to update a guess with another guess. So, the current guesses of the values of states $s_2$ and $s_3$ are used to calculate a new guess for the value of state $s_1$. So we plug in the estimates of the values of states $s_2$ and $s_3$ and when we do that, we get negative 2 (i.e. $-2$). This value is our new guessed value for state $s_1$. We will recored -and use- that new value.\n",
    "\n",
    "$$V(s_1) \\longleftarrow 1/2(-1 + V(s_2)) + 1/2(-3 + V(s_3))$$\n",
    "$$V(s_1) \\longleftarrow 1/2(-1 + 0) + 1/2(-3 + 0) = -2$$\n",
    "\n",
    "What we do now, is to calculate a new guess for state $s_2$ using the new guessed value of state $s_1$ and the most current value of state $s_3$:\n",
    "\n",
    "$$V(s_2) \\longleftarrow 1/2(-1 + V(s_1)) + 1/2(5 + V(s_4))$$\n",
    "$$V(s_2) \\longleftarrow 1/2(-1 + (-2)) + 1/2(5) = 1$$\n",
    "\n",
    "Then we calculate a guess for state $s_3$, again, using the most current values of the other 3 states (the value of state $s_4$ will always be zero because state $s_4$ is the terminal state:\n",
    "\n",
    "$$V(s_3) \\longleftarrow 1/2(-1 + V(s_1)) + 1/2(5 + V(s_4))$$\n",
    "$$V(s_3) \\longleftarrow 1/2(-1 + (-2)) + 1/2(5) = 1$$\n",
    "\n",
    "Once we have completed or calculated a guess for each of the states, we start all over again calculating the new guess of state $s_1$ and based on its new guess we procceed to calculate the new guess value of state $s_2$, and $s_3$, and then we start again. Eventually it will turn out, that this iterative algorithm yields and estimate that converges to the true value function of the policy.\n",
    "\n",
    "This is the idea behind an algorithm known as <u><b><i>Iterative Policy Evaluation</i></b></u>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='PolicyEvaluation'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterative Policy Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *Iterative Policy Evaluation* algorithm assumes that the agent already has a full and perfect knowledge and understanding of the MDP that characterizes the environment (i.e. transitions available in each state and the rewards these transitions offer).\n",
    "Remember that the Bellman's equation is in reality a system of equations that holds an equation for each on of the states in the environment and that each equation relates the value of a state to the values of its successor states. Therefore we could calculate the functions values by solving this system of equations.\n",
    "Since this is not practical in real world problems -becuase of the vast number of states real worlds environments offer in RL problems- it will be easier to construct an iterative algorithm where each step gets us closer and closer to solving the system of equations:\n",
    "\n",
    "<h5><center>Bellman Expectation Equation for the State-Value Function</center></h5>\n",
    "$$v_\\pi(s) = \\sum_{a \\in A(s)}\\pi(a \\mid s) \\sum_{s' \\in S, r \\in R} p(s', r \\mid s, a)(r + \\gamma v_\\pi(s'))$$\n",
    "\n",
    "<h5><center>Update Rule for Iterative Policy Evaluation</center></h5>\n",
    "$$V(s) \\longleftarrow \\sum_{a \\in A(s)}\\pi(a \\mid s) \\sum_{s' \\in S, r \\in R} p(s', r \\mid s, a)(r + \\gamma V(s'))$$\n",
    "\n",
    "\n",
    "The algorithm of the Iterative Policy Evaluation should look like this:\n",
    "\n",
    " 1. The algorithm receives as input the MDP, and the policy $\\pi$\n",
    " 2. Our output will be the state value function ($\\approx v_\\pi$)\n",
    " 3. $V(s) \\longleftarrow 0$ for all $s \\in S^+$\n",
    " 4. The we reapeat for each state the following:\n",
    " 5. for $s \\in S$:\n",
    " $$V(s) \\longleftarrow \\sum_{a \\in A(S)}\\pi(a \\mid s)\\sum_{s' \\in S, r \\in R}p(s', r \\mid s, a)(r + \\gamma V(s'))$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But how do we know when we have to stop the algorithm? For that we need to introduce a small positive number $\\theta$. On each run, we calculate a delta $\\Delta$. $\\Delta$ is the absolute value calculated from the subtraction of the last calculated state value function from the new calculated state value function. When this delta $\\Delta$ is less than theta $\\theta$, then we should stop the algorithm.\n",
    "\n",
    "![IterativePolicyEvaluation](images/IterativePolicyEvaluation.png) \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Estimation of Action Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the dynamic programming setting, it is possible to quickly obtain the action-value function $q_\\pi$ from the state value function $v_\\pi$ with the equation:\n",
    "\n",
    "$$q_\\pi(s, a) = \\sum_{s' \\in S, r \\in R}p(s', r \\mid s, a)(r + \\gamma v_\\pi(s'))$$\n",
    "\n",
    "![EstimationActionValues ](images/EstimationActionValues.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='PolicyImprovement'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Policy Improvement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, remember that this algorithm requires that the agent has already the knowledge and understanding of the MDP.\n",
    "\n",
    "When we are searching for an optimal policy \"Policy Evaluation\" get us partially there. After all, in order to figure out the best policy, it helps to be able to evaluate candidates policies. *\"Policy Improvement\"* is an algorithm that uses the value function for a policy in order to propose a new policy that is at least as good as the current one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><h4>Iterative Policy Evaluation:</h4><center>\n",
    "\n",
    "$$\\text{policy} \\pi \\longrightarrow \\text{value function } v\\pi$$\n",
    "\n",
    "<center><h4>Policy Improvement:</h4><center>\n",
    "\n",
    "$$\\text{value function } v_\\pi \\longrightarrow \\text{policy } \\pi' \\text{(where }\\pi' \\geq \\pi\\text{)}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could then construct an algorithm that improves the policy as follow:\n",
    "\n",
    "There is already a policy $\\pi$. We apply the Iterative Policy Evaluation algorithm giving it as input such policy. From this, we will get a new value function $v_\\pi$. With this new value function, we run the Policy Improvement algorithm to get a new policy $\\pi'$ such that $\\pi' \\geq \\pi$.\n",
    "\n",
    "With this idea in mind, how might we design the policy improvement step to find a policy that's at least as good as the current one?\n",
    "\n",
    "We will break policy improvement into two steps:\n",
    " 1. Convert the state value function to an action value function\n",
    " 2. We focus on how to use this action value function to obtain a policy that is better than the equal probable random policy. The idea behind this that for each state, we'll just pick the action that maximizes the action value function, so the update step will look like:\n",
    " $$\\pi'(s) \\longleftarrow argmax_{a \\in A(s)}Q(s, a)$$\n",
    " \n",
    "The complete algorith below:\n",
    " \n",
    " ![PolicyImprovement](images/PolicyImprovement.png)\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Policy Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Policy Iteration algorithm is an algorithm that can solve an MDP in the dynamic programming setting. It consists of a repeated sequence of [policy evaluation](#PolicyEvaluation) and [improvement steps](#PolicyImprovement). This algorithm guarantees to converge to the optimal policy for an arbitrary finite MDP.\n",
    "\n",
    "![PolicyIteration](images/PolicyIteration.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Truncated Policy Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another algorithm used in the dynamic programming setting is the *Truncated Policy Iteration*. This algorithm is also used to estimate the state value function $v_\\pi$ corresponding to a policy $\\pi$. In this algorithm, the evaluation step is stopped after a <u>fixed number</u> of sweeps through the state space. We refer to the algorithm in the evaluation step as **truncated policy evaluation**.\n",
    "\n",
    "![TruncatedPolicyIteration](images/TruncatedPolicyIteration.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Value Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The last algorithm in this notebook is *Value Iteration*. This algorithm is used -in the dynamic programming setting- to estimate the state value function $v_\\pi$ corresponding to a policy $\\pi$. This algorithm performs policy evaluation and policy improvement simultaneously in each of the sweeps over the state space.\n",
    "\n",
    "![ValueIteration](images/ValueIteration.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implementation of the algorithms here described is found in [this notebook](./notesMiniProjects/DynamicPrograming/Dynamic_Programming.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}