9. Policy-Based Methods.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Policy-Based Mthods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reinforcement learning is about learning the optimal policy.<br>\n",
    "So far we have reveiwed value-based methods; we try to find the value function and the policy is implicitly defined by that value function (like when $\\epsilon\\text{-gradient}$ is used).<br>\n",
    "We can find the optimal policy without worrying about a value function at all?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pros of Policy-Based Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Three arguments to consider:\n",
    " * Simplicity\n",
    " * Stochastic Policies\n",
    " * Continuous Action Space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simplicity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| method |_____ value-function* _____ | ____________________ policy ____________________ |\n",
    "|------|------|------|\n",
    "|value-based| $\\color{red}{\\hat{q}(s, a)\\approx q_*(s, a)}$ | $\\color{orange}{\\pi\\big(\\hat{q}(s, a)\\big) \\approx \\pi^*}$|\n",
    "| policy-based| ---------- | $\\color{orange}{\\pi \\approx \\pi^*}$|\n",
    "\n",
    "*In value-based methods like Q-Learning we use the value function as an intermediate step.\n",
    "\n",
    "So, in policy-based methods, we look for a way to estimate the optimal policy without intermediate steps.\n",
    "\n",
    "Such a policy would look like:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\text{Deterministic approach;     } &\\pi\\text{ : } s\\rightarrow a\\\\\n",
    "\\text{Stochastic approach;     } &a~\\pi(s, a) = \\mathbb{P}[a \\mid s]\n",
    "\\end{align}$$\n",
    "\n",
    "\n",
    "Where the *deterministic approach* is just a mapping and the *stochastic approach* is a conditional probability of each action, given a certain state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would then choose an action based on this probability distribution. This is simpler because:\n",
    " * we directly get at the problem at hand\n",
    " * avoid storage of a bunch of additional data that not always is or may be useful (for example large portions of the state space may have the same value. A policy formulated in this way allows to make a generalization where needed/possible and to focus more on the complicated regions of the state space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stochastic Policies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Policy-based methods -alike value vased methods- can learn true stochastic policies. Like for example: picking numbers from a machine, where the probabilities of each number to be selected depend on some state variables that can be changed. In contrast $\\epsilon\\text{-greedy}$ action selection adds some randomness - but it's really a hack. The underlying value function can still drive us towards certain actions more than others, like for example when playing rock-paper-scissors. In that game, the optimal policy is to choose an action uniformly at random because any other (deterministic or stochastic) policy with some non-uniformity could be exploited by the opponent.<br>\n",
    "Stochastic policy also helps in cases in which there are aliased states (2 or more states that are perceived by the agent like identical states but that in reallity are different states).\n",
    "\n",
    "![enyEvironment](./images/anyEnvironment.png)\n",
    "\n",
    "The status in brown are identical.  The agent cannot distinguish between them and therefore could choose to go left always when in those states, leading eventually to an oscillating situation. It could maybe come out of that oscillatory situation by chance because of $\\epsilon\\text{-greedy}$ policy but the learning would be anyways very inefficient and could take long and if we sent a high $\\epsilon\\text{-greedy}$ with the intention of helping the agent to find faster the optimal policy, it might result in bad action in other states.\n",
    "\n",
    "In an environment like the one depicted in the image above, it would be best to assign equal probabilities to moving left or right from these aliased states.\n",
    "\n",
    "A value-based approach tends to learn a deterministic or near deterministic policy. A policy-based approach -in situations like the one of the picture above- can learn the desired stochastic policy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Continuous Action Spaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In environments with discrete action spaces we used value-based methods -with or without function approximator. Here the output consist of a value for each state and the value is choosen by the agent - it chooses the highest value.\n",
    "\n",
    "But if the action space is continuous, the max operation used by the agents in environments with discrete action spaces becomes an optimization problem like for example trying to find the  global maximum of a continuous function - and that is not a trivial task (especailly if the function is not convex).<br>\n",
    "Similar issues exist in high dimensional action spaces - lots of possible actions to evaluate. It'd be nice if we could map a given state to an action directly even if the resulting policy is a bit more complex, it would significantly reduce the computation time needed to act $\\longrightarrow$ an that is something a policy based method can allows to achieve."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Policy Function Approximation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to cover large or continuous state spaces we extend policy-based methods by using a function to approximate the policy - similar to value function approximation.\n",
    "<center>\n",
    "    <h4>Policy Function Approximation</h4><br>\n",
    "    $a \\sim \\pi(s, a, \\theta) = \\mathbb{P}[a \\mid s, \\theta]$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How? By parameterizing the policy with theta, where theta is the weights of a NeuralNet or any other model. The goal is then, to *optimize theta* to find *the best policy*.<br>\n",
    "An approximation function is or could be a linear combination of features:\n",
    "$$f(s, a, \\theta) = X(s, a)^\\top\\theta$$\n",
    "\n",
    "But this approximation function does not suite us in this case because it does not produce a probability distribution from which we can sample actions and that is what we want to get - a probability distribution of actions.<br>\n",
    "So in order to produce such probability distribution, we need to use some transformation. We apply the Softmax function that exponentiates the function approximation (the linear combination results) and then normalize it (divides it by the summatory of exponentials for all actions):<br>\n",
    "$$a \\sim \\pi(s, a, \\theta) = \\frac{e^{f(s, a, \\theta)}}{\\sum_{a'}e^{f(s, a', \\theta)}}$$\n",
    "\n",
    "With this, we get a set of action probabilities that sum to one. <u>However, this works only for discrete action spaces</u>.\n",
    "\n",
    "When having an environment with a continuous action space we can use a **Gaussian Policy**. In this *Gaussian Policy*, actions are sampled from a Gaussian distribution where the parameters of the distribution are determined by our features:\n",
    "<center>\n",
    "    <h4>Linear Function with Gaussian Policy</h4><br>\n",
    "    $f(s, a, \\theta) = X(s, a)^\\top\\theta$<br>\n",
    "    $a \\sim \\pi(s, a, \\theta) = N(\\mu, \\sigma^2)$<br>\n",
    "    $\\begin{align}\n",
    "    \\text{where; }&\\\\\n",
    "    &\\mu\\text{ (mean)} = f(s,a,\\theta)\\longrightarrow \\text{Simple linear combination of features} \\\\\n",
    "    &\\sigma^2\\text{ (variance)}\\longrightarrow \\text{fixed or parameterized like }\\theta\\text{ in the Softmax Policy}\n",
    "    \\end{align}$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same trick can be applied to any approximation function that produces some values and turn them into probabilities that represent a stochastic policy.\n",
    "\n",
    "To be able to distinguish which policy is the best we need an objective function.<br>\n",
    "An objective function is an objective measure. Such measure indicates how good is the policy. This measure must be a function of the policy parameters.\n",
    "<center>\n",
    "    <h4>Objective Function</h4><br>\n",
    "    $J(\\theta) = \\mathbb{E}_\\pi\\big[R(\\tau)\\big]; \\tau = S_0, A_0, R_1, S_1 \\ldots$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function needs to capture the expected rewards obtained under the policy.<br>\n",
    "Tau (i.e. $\\tau$) is a trajectory, that is, a complete or partial episode. The expected value can be computed by sampling over multiple trajectories.\n",
    "\n",
    "If the problem we have is an episodic task:<br>\n",
    "An option is to use the mean of the return from the first time step $G_1$. The <b>Start State Value</b>:\n",
    "<center>\n",
    "    <h4>Start State Value</h4><br>\n",
    "$$J_1(\\theta) = \\mathbb{E}[G_1] = \\mathbb{E}\\big[V(S_1)\\big]\n",
    "\\begin{align}\n",
    "\\text{Where; }&\n",
    "& G_1 = R_1 + \\gamma R_2 + \\gamma^2 R_3 + \\gamma^3 R_4 + \\ldots\n",
    "\\end{align}$$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As it can be observed in the equation, the return from the first time step $G_1$ is to be used and this is equivalent to using the value of the starting state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nevertheless, for continuous environments we cannot depend on a specific starting state. It would be better (for the objective function) to have a measurement that does not depend on the first state. The average or expected state value is a good candidate for this measurement. The <b>Average State Value</b>:\n",
    "<center>\n",
    "    <h4>Average State Value</h4><br>\n",
    "    $J_\\bar{v}(\\theta) = \\mathbb{E}_\\pi\\big[V(s)\\big]$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might think that we prefer a policy that leads to a higher average, but there could be states that repeat too often. So we weight each state value by the probability of its occurrence or <u><i>stationary probability</i></u>.<br>\n",
    "$$J_\\bar{v}(\\theta) = \\mathbb{E}\\big[V(s)\\big] = \\sum_s d(s)v(s) \\\\\n",
    "\\begin{align}\n",
    "\\text{where; }& \\\\\n",
    "& d(s) = \\frac{N(s)}{\\sum_{s'}N(s')} \\\\\n",
    "\\end{align}$$\n",
    "\n",
    "The <u><i>Stationary Probability</i></u>: Divides the number of occurences of the state by the total number of occurrences of all states."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another measure is the <b>Average Action Value</b> and this one is related to the Average State Value:\n",
    "<center>\n",
    "    <h4>Average Action Values</h4><br>\n",
    "    $$\\begin{align}\n",
    "    J_\\bar{q}(\\theta) &= \\mathbb{E}_\\pi\\big[Q(s, a)\\big] \\\\\n",
    "    &= \\sum_s d(s)\\sum_a \\pi(s, a, \\theta)Q(s, a)\n",
    "    \\end{align}$$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's remember that the goal of encoding the policy directly, is so that no tracking of state values or action values should be needed. This leads us to a measure that can be directly computed; <u>the average reward at each time step</u>:<br>\n",
    "<center>\n",
    "    <h4>Average Reward</h4><br>\n",
    "    $$\\begin{align}\n",
    "    J_\\bar{r}(\\theta) & =\\mathbb{E}_\\pi[r] \\\\\n",
    "    & = \\sum_s d(s)\\sum_a\\pi(s, a, \\theta)R_s^a\n",
    "    \\end{align}$$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This four formulations work well for optimizing policies. In fact, seems to be that they work equally good.<br>\n",
    "![ObjectiveFunctionsSummary](./images/ObjectiveFunctionsSummary.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stochastic Policy Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have an objective function and once we have choosen which one we're going to use, we can try to find a policy that maximizes it.<br>\n",
    "![surfaceFunctionObjective](./images/surfaceFunctionObjective.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The figure represents an objective function of two parameters. the height inidcates the policy's  objective value $J(\\theta)$.<br>\n",
    "This idea extends to objective functions of more than two parameters.<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hill Climbing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initially, we don't know anything about this surface, so we need to find the spot where the objective value is at it's maximum. One approach would be to nudge the policy around and see what we find.\n",
    "\n",
    "Say we have an arbitrary policy: $\\pi$<br>\n",
    "The policy is defined by its $\\theta$ parameters: $\\theta: 0.1 \\mid -0.5$<br>\n",
    "We know how to evaluate the policy:\n",
    " * We apply it to the environment\n",
    " * We receive then an objective value\n",
    "Let's imagine that this obtained value lands somewhere on the objective function surface.\n",
    " * We change the $\\theta$ parameters a little bit\n",
    " * We apply the policy again to the environment\n",
    " * We receive a new value that again lands somewhere on the objective function surface.\n",
    " \n",
    "The slight change to the $\\theta$ parameters can be achieved by adding some *Gaussian noise* to the parameteres. If the new policy's value is better than our previous values, then we set this policy to be our new best policy and we iterate.<br>\n",
    "This aproach is known as <u>Hill Climbing</u>.\n",
    "\n",
    "In this approach, the agent literally walk the objective function surface to find the top of a hill.<br>\n",
    "If we use Hill Climbing, we can use any policy function even if it is not differentiable or continuous.<br>\n",
    "You can surely see, this approach is not efficient to find the top of the hill."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Steepest Ascent Hill Climbing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One improvement to Hill Climbing is to choose a number of neighbor policies at each iteration and then to pick the best of those neighbors.<br>\n",
    " * We have an arbitrary policy.\n",
    " * We apply it to the environment\n",
    " * We receive a value and find out where it lands in the surface\n",
    " * We choose a small number of neighboring policies by perturbing the parameters randomly\n",
    "  * Evaluate each neighbor policy by interacting with the environment to get an idea of the neighborhood\n",
    " * We pick the policy (the neighbor) that seems to be the bets of the neighbors\n",
    " * Iterate\n",
    " \n",
    "This approach is known as <u>Steepest Ascent Hill Climbing</u>.\n",
    "\n",
    "**Note:** With these approaches we can still get stuck in a local optima. To try to avoid that, we can use random restarts or *simulated annealing*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulated Annealing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simulated Annealing uses a schedule to control how the policy space is explored.<br>\n",
    "It starts with a large noise parameter (radius) that produces larger neighborhoods and it decreases the radius (noise parameter) as it progresses and as it gets closer to the optimal solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Adaptive Noise Scaling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another approach is the *Adaptive Noise Scaling*. This approach evolves from the Simulated Annealing approach. It adapts the amount of noise parameter (radius) according to the changes in the observed policy values. If it finds a better policy (it means the agent is ascending the Hill) it reduces the search radius (noise parameter) for generating the next policy. By doing this, the agent reduces the variance of the Gaussian noise we add. The *extension* or evolution from Simulated Annealing comes when the agent oberves a policy that is in fact worse that the best policy it has found in the past. In this case, the agent increases the noise parameter (the search radius) and continue with the exploration from the current best policy.\n",
    "\n",
    "This makes the stochastic policy search less likey to get stock - especailly in domains with a complicated objective function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Policy Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stochastic policy search may or may not always work as expected.<br>\n",
    "Stochastic policy search happens to be sensitive to the choice of individual samples and may get stuck in local optimal. Besides this it may take long until it converges.<br>\n",
    "This approach (i.e. Stochastic Policy) is used when we don't know anything about the objective function nor the policy nor the gradient.\n",
    "\n",
    "*But* if we know something about the policy, the objective function and the gradient of such objective function (or if it could be concluded), then we can take other approaches which are more efficient.<br>\n",
    "The gradient always points us into the direction of maximum change. So, if we know about such gradient, we do not need to evaluate randomly policies nor their \"neighbors\". Since -in a case like this- we know the gradient, we can compute the next set of parameters $\\theta$ that will give us a better result.<br>\n",
    "This idea is the basis of *Policy Gradients* and the approach generally goes as follows:\n",
    " * Find the gradient for the current policy parameters\n",
    " * Update them in the direction of increasing gradient\n",
    " * Iterate\n",
    " \n",
    "Since both the policy and the environments are most likely stochastic, we will make small steps i.e. $\\alpha$. But this is not strange to us.<br>\n",
    "Each policy evaluation might yield unconsistent results. For this reason we might want to evaluate a policy over multiple episodes.\n",
    "\n",
    "![PolicyGradient](./images/PolicyGradients.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But if the objective function is not differentiable (which is possible for complicated underlying policies) then we cannot calculate the gradient. In this cases we estimate the gradient by using *finite differences*.<br>\n",
    "Given any policy $\\pi$ defined by an n-dimensional parameter verctor $\\theta$, we find the partial derivative of the objective function with respect to each dimension $k$, by adding a tiny value to that particular dimension and computing the difference between the resulting policy value and the current one. Then collect all the derivatives into a single vector to get the combined derivative. Each of these policy evaluations may require at least one full episode of interaction with the environment and we do one evaluation for every parameter dimension at every iteration.\n",
    "\n",
    "![FiniteDifferences](./images/FiniteDifferences.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This procedure takes a *loooooong* time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have access to the underlying policy function, it is more efficient to try and compute the gradient analytically. Here we would need to compute the gradient of the expected value of some function. Even if it sounds difficult, this is a well studied problem. The reward function in the next picture is referred to as the \"score function\". This expression can be manipulated to estimate the gradient of the score function more easily.\n",
    "\n",
    "![Computing Gradients Analytically](./images/ComputingGradientsAnalytically.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How to do this manipulation?... to simplify things we will consider some arbitrary score function $f$ that is dependent on $X$:\n",
    "$$\\nabla_\\theta\\mathbb{E}_x\\big[f(x)\\big]$$<br>\n",
    "Values of x are drawn from a probability distribution defined by the parameter $\\theta$:\n",
    "$$x \\sim \\mathbb{P}[x \\mid \\theta]$$<br>\n",
    "We can expand the expectation into an integral or summation of the probability of $x$ given $\\theta$ times the score function.\n",
    "$$\\begin{align}\n",
    "\\nabla_\\theta\\mathbb{E}_x\\big[f(x)\\big] &= \\nabla_\\theta\\sum_x\\mathbb{P}[x \\mid \\theta]f(x) \\\\\n",
    "&= \\sum_x\\nabla_\\theta\\mathbb{P}[x\\mid\\theta]f(x)\n",
    "\\end{align}$$<br>\n",
    "Now we use something called \"Likelihood Ratio Trick\":\n",
    "$$ =\\sum_x\\mathbb{P}[x\\mid\\theta]\\frac{\\nabla_\\theta\\mathbb{P}[x\\mid\\theta]}{\\mathbb{P}[x\\mid\\theta]}f(x)$$<br>\n",
    "Then we replace the resulting fraction by the derivative of the log probability:\n",
    "$$=\\sum_x\\mathbb{P}[x\\mid\\theta]\\nabla_\\theta\\big(\\text{log }\\mathbb{P}[x\\mid\\theta]\\big)f(x)$$\n",
    "*This is a well known identity*<br>\n",
    "Finally we convert the summation back to an expectation:\n",
    "$$=\\mathbb{E}\\Big[\\nabla_\\theta\\big(\\text{log }\\mathbb{P}[x\\mid\\theta]\\big)f(x)\\Big]$$<br>\n",
    "Notice that only the derivative of the log probabilities is computed. The derivative of the score function is not computed because it doesn't depend directly on $\\theta$.\n",
    "\n",
    "The gradient expression looks like this:\n",
    "$$\\begin{align}\n",
    "\\nabla_\\theta J(\\theta) &= \\nabla_\\theta\\mathbb{E}_\\pi\\big[R(\\tau)\\big] \\\\\n",
    "&=\\mathbb{E}_\\pi\\Big[\\nabla_\\theta\\big(\\text{log }\\pi(s, a, \\theta)\\big)R(\\tau)\\Big]\n",
    "\\end{align}$$<br>\n",
    " * Policy function $\\pi$  in place of the probability distribution.\n",
    " * Our own score function $R$, which can be the sum of all rewards, discounted rewards or some other value-based function.\n",
    " * We compute the score function by interacting with the environment and summing the rewards we get. I.e. $\\color{red}{R(\\tau)}$\n",
    " * If the policy function is implemented using an approximator (NeuralNet), then we simply calculate the log of the outputs probabilites and its derivative. I.e. $\\color{red}{\\nabla_\\theta\\big(\\text{log }\\pi(s, a, \\theta)\\big)}$\n",
    " * We compute the expectation stochastically by taking a bunch of samples.\n",
    " \n",
    " And now we are able to update policy parameters to improve the objective function iteratively:<br>\n",
    " <center>\n",
    "    The Update Rule\n",
    " $$\\Delta\\theta = \\alpha\\nabla_\\theta\\big(\\text{log }\\pi(s, a, \\theta)\\big)R(\\tau)$$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monte Carlo Policy Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Algorithm Reinforce](./images/AlgorithmReinforcement.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constrained Policy Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Attention must be paid to the policy parameters in addition to the abjective function. It is actually needed to put some constraints on the policy parameters, li,ke for example, under which circumstances it is allowed to change them or by how much they can be changed (think of robotic applications in which, withouth these constraints, the mechanical parts can be damaged).<br>\n",
    "Such constraints can be implemented along in the gradient based algorithm in such a way that the difference between two policies is at most some threshold delta:\n",
    "<center>\n",
    "    $$\\begin{align}\n",
    "    J(\\theta) = \\mathbb{E}_\\pi\\big[R(\\tau)\\big] \\\\\n",
    "    D\\big(\\pi(\\cdot, \\cdot, \\theta), \\pi(\\cdot, \\cdot, \\theta')\\big) \\leq \\delta\n",
    "    \\end{align}$$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way of introducing a constrain is by introducing a penalty term to the objective function. This penalty term is a multiple of the difference between two policies:\n",
    "<center>\n",
    "    <h4>Penalty Term</h4><br>\n",
    "    $J(\\theta) = \\mathbb{E}_\\pi\\big[R(\\tau)\\big] - \\beta D\\big(\\pi(\\cdot, \\cdot, \\theta), \\pi(\\cdot, \\cdot, \\theta')\\big)$\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we optimize for this combined objective function, we will get better policies that are not too different at each step. This will stabilize the learning algorithm. This is also like adding regularization to ML algorithms.\n",
    "\n",
    "We need also a way to qualify the difference between two policies (regardless of which approach we are working with; adding a constraint or a penalty).<br>\n",
    "The naive way of computing such difference:\n",
    "$$D\\big(\\pi(\\cdot, \\cdot, \\theta), \\pi(\\cdot, \\cdot, \\theta')\\big) = \\parallel\\theta - \\theta\\parallel^2 \\longrightarrow \\text{Parameter Difference}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But if the policies are complex functions of the parameters -which is normally the case- then this parameter difference means nothing, since it doesn't accurately reflect the difference on the policy behaviours, what actions they ultimately produce.\n",
    "\n",
    "If we think of a policy as a probability distribution over actions, we will get a better distance measure between two policies. This perspective is especially useful when having a continuous action space.<br>\n",
    "When having continuous action spaces the probability distribution (meaning, the policy) over the range of actions can be different from state to state. If we have continuous states, we can unify these into a single continuous distribution over the combined range of states and actions.<br>\n",
    "Consider the following example:\n",
    "<H1>PICTURE HERE</H1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each of these policies is a distribution over states and actions. How to compare them?<br>\n",
    "We can use *Kullback Leibler* or KL divergence, which is a statistical measure.\n",
    "<center>\n",
    "    <h4>KL Divergence of P with respect to Q</h4><br>\n",
    "    $\\begin{align}\n",
    "    D_{KL}(P\\parallel q) &= \\int_{-\\infty}^\\infty P(x)\\text{log}\\frac{P(x)}{q(x)}\\partial x \\\\\n",
    "    &= \\int_{-\\infty}^\\infty P(x)\\big(\\text{log}p(x) - \\text{log}q(x)\\big)\\partial x\n",
    "    \\end{align}$\n",
    "</center>\n",
    "\n",
    "\n",
    "<H1>PICTURE HERE</H1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We scale the difference by one of the probability values:\n",
    "$$P(x)\\big(\\text{log}p(x) - \\text{log}q(x)\\big)$$\n",
    "\n",
    "And sum up over the range of x:\n",
    "$$\\int_{-\\infty}^\\infty P(x)\\big(\\text{log}p(x) - \\text{log}q(x)\\big)\\partial x$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This in blue color is the area of the non-overlaping region between the true log probability distributions, but summed up at each location $x$, using one of the probabilities as a reference.<br>\n",
    "This means that:\n",
    "$$D_{KL}(P\\parallel q) \\neq D_{KL}(q\\parallel P) \\longrightarrow \\text{Assymetric distance measure}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We apply this to policy gradient by calculating the KL divergence measured between the current policy and the candidate new policy (i.e. between $\\theta$ and $\\theta'$ and we use this difference as the constraint part of the objective function.<br>\n",
    "This term punishes the new polices that change the behaviour too much.<br>\n",
    "The new polilcy has to produce much more value to be consider a better policy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the context of the overall policy gradients algorithm, this helps create a more stable learning process where the policy is not jumping around too much.\n",
    "\n",
    "Other constraint policy gradients:\n",
    " * Trust region policy optimization (TRPO)\n",
    " * Proximal policy optimization (PPO)"
   ]
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}