Answers.Body: <p>I did not read those two specified linked/cited papers and I am not currently familiar with the <a href="https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures" rel="nofollow noreferrer">total variation distance</a>, but I think I can answer some of your questions, given that I am reasonably familiar with the KL divergence.</p>
  <blockquote>
  <p>When you compute the <span class="math-container">$D_{KL}$</span> between two polices, what does that tell you about them</p>
  </blockquote>
  <p>The KL divergence is a measure of &quot;distance&quot; (or divergence, as the name suggests) between two probability distributions (i.e. probability measures) or probability densities. In reinforcement learning, <a href="https://ai.stackexchange.com/q/12274/2444">(stochastic) policies</a> are probability distributions. For example, in the case your Markov decision process (MDP) has a discrete set of actions, then your policy can be denoted as <span class="math-container">$$\pi(a \mid s),$$</span>which is the conditional probability distribution over all possible actions, given a specific state <span class="math-container">$s$</span>. Hence, the KL divergence is a natural measure of how two policies are similar or different.</p>
  <p>There are 4 properties of the KL divergence that you always need to keep in mind</p>
  <ol>
  <li>It is asymmetric, i.e., in general, <span class="math-container">$D_{KL}(q, p) \neq D_{KL}(p, q)$</span> (where <span class="math-container">$p$</span> and <span class="math-container">$q$</span> are p.d.s); consequently, the KL divergence <strong>cannot</strong> be a <a href="https://en.wikipedia.org/wiki/Metric_(mathematics)" rel="nofollow noreferrer">metric</a> (because metrics are symmetric!)</li>
  <li>It is always non-negative</li>
  <li>It is zero when <span class="math-container">$p = q$</span>.</li>
  <li>It is unbounded, i.e. it can be arbitrarily large; so, in other words, two probability distributions can be infinitely different, which may not be very intuitive: in fact, in the past, I used the KL divergence and, because of this property, it wasn't always clear how I should interpret the KL divergence (but this may also be due to my not extremely solid understanding of this measure).</li>
  </ol>
  <blockquote>
  <p>and how is it different from what a <span class="math-container">$D_{TV}$</span> between the same two policies tells you?</p>
  </blockquote>
  <p><span class="math-container">$D_{TV}$</span> is also a measure of the distance between two probability distributions, but it is <strong>bounded</strong>, specifically, in the range <span class="math-container">$[0, 1]$</span> [<a href="https://arxiv.org/pdf/math/0209021.pdf" rel="nofollow noreferrer">1</a>]. This property may be useful in some circumstances (which ones?). In any case, the fact that it lies in the range <span class="math-container">$[0, 1]$</span> potentially makes its interpretation more <em>intuitive</em>. More precisely, if you know the maximum and minimum values that a measure can give you, you can have a better idea of the relative difference between probability distributions. For instance, imagine that you have p.d.s <span class="math-container">$q$</span>, <span class="math-container">$p$</span> and <span class="math-container">$p'$</span>. If you compute <span class="math-container">$D_{TV}(q, p)$</span> and <span class="math-container">$D_{TV}(q, p')$</span>, you can have a sense (in terms of percentage) of how much <span class="math-container">$p'$</span> and <span class="math-container">$p$</span> differ with respect to <span class="math-container">$q$</span>.</p>
  <p>The choice between <span class="math-container">$D_{TV}$</span> and <span class="math-container">$D_{KL}$</span> is probably motivated by their specific properties (and it will probably depend on a case by case basis, and I expect the authors of the research papers to motivate the usage of a specific measure/<a href="https://en.wikipedia.org/wiki/Metric_(mathematics)" rel="nofollow noreferrer">metric</a>). However, keep in mind that there is not always a closed-form solution not even to calculate the KL divergence, so you may need to approximate it (e.g. by sampling: note that the KL divergence is defined as an expectation/integral so you can approximate it with a sampling technique). So, this (computability and/or approximability) may also be a parameter to take into account when choosing one over the other.</p>
  <p>By the way, I think that your definition of the <em>total variational divergence</em> is wrong, although the DTV is related to the DKL, specifically, as follows [<a href="https://arxiv.org/pdf/math/0209021.pdf" rel="nofollow noreferrer">1</a>]</p>
  <p><span class="math-container">\begin{align}
  D_{TV} \leq \sqrt{\frac{1}{2} D_{KL}}
  \end{align}</span></p>
  <p>So the DTV is bounded by the KL divergence. Given that the KL divergence is unbounded (e.g. it can take very big values, such as 600k, this bound should be very loose).</p>
  <p>Take a look at the paper <a href="https://arxiv.org/pdf/math/0209021.pdf" rel="nofollow noreferrer">On choosing and bounding probability metrics
  </a> (2002, by Alison L. Gibbs and  Francis Edward Su) or <a href="http://www.yaroslavvb.com/papers/peres-markov.pdf#page=58" rel="nofollow noreferrer">this book</a> for information about <span class="math-container">$D_{TV}$</span> (and other measures/metrics).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-08T04:44:13.873Z
Answers.Text: So $D_{TV}$ being bounded is a distinguishing property.  "the fact that it lies in the range [0,1] potentially makes its interpretation more intuitive". Please clarify what it "...makes its interpretation more intuitive" means because I don't understand that part well. Thanks for pointing out the correct definition of $D_{TV}$. I'll look at the paper and book you've pointed out.
Answers.UserDisplayName: mugoh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-08T08:08:30.657Z
Answers.Text: @mugoh When I say that boundedness makes it more intuitive it's because you know exactly what is the maximum, but in the case of the KL divergence you don't know if the current value of the KL divergence is really big or actually not so big.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-08T10:43:57.367Z
Answers.Text: Anyway, the bound shown in my answer is probably very loose, given that the KL divergence can really be arbitrarily large (e.g. 600k) and the total variational is between $0$ and $1$ (according to the sources I've seen).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-09T05:37:48.200Z
Answers.Text: That's much clear. Emphasizing that the bound is very loose especially gives a better picture on the difference between the two.
Answers.UserDisplayName: mugoh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-09T05:40:09.107Z
Answers.Text: I've looked at the referenced book and paper. And they both explain $D_{TV}$ in depth. One point I picked is that $D_{TV}$ as a metric, converges fast because it's insensitive to element-wise differences when total difference remains the same. So $D_{TV}$ converges while $D_{KL}$, being a non-metric, doesn't. This might also influence the choice. (2) It admits *natural interpretations* and bounding techniques, as you emphasized in your answer.
Answers.UserDisplayName: mugoh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-07T22:08:47.063Z
Answers.LastActivityDate: 2020-10-08T14:59:14.223Z
Answers.LastEditDate: 2020-10-08T14:59:14.223Z
Answers.UserDisplayName: nbro
Answers.Body: <p>To add to nbro's answer, I'd say also that much of the time the distance measure isn't simply a design decision, rather it comes up naturally from the model of the problem. For instance, minimizing the KL divergence between your policy and the softmax of the Q values at a given state is equivalent to policy optimization where the optimality at a given state is Bernoulli with respect to the exponential of the reward (see maximum entropy RL algorithms). As another example, the KL divergence in the VAE loss is a result of the model and not just a blind decision.</p>
  <p>I'm less familiar with total variation distance, but I know there's a nice relationship between the total variation distance of a state probability vector and a Markov chain stationary distribution relative to the timestep and the mixing time of the chain.</p>
  <p>Finally, another thing to consider is the properties of the gradients of these divergence measures. Note that the gradient of the total variation distance might blow up as the distance tends to <span class="math-container">$0$</span>. Additionally, one must consider if unbiased estimators of the gradients from samples can be feasible. While this is generally the case with KL divergence, I'm not sure about total variation distance (as in, I literally don't know), and this is generally <em>not</em> the case with the Wasserstein metric (see Marc G. Bellemare et. al's paper &quot;The Cramér distance as a solution to biased wasserstein gradients&quot;). However, of course there's other scenarios where the tables are turned -- for instance, the distributional bellman operator is a contraction in the supremal Wasserstein metric but <em>not</em> in KL or total variation distance.</p>
  <p><strong>TL; DR:</strong> Many times mathematical/statistical constraints suggest particular metrics.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-09T05:41:31.860Z
Answers.Text: This point is quite useful. I've looked at the Constrained Policy Optimization paper again and I identify their use for $D_{TV}$ as a choice that relates to satisfying a mathematical constraint, if I'm not wrong. Specifically, in deriving a safe policy improvement, the authors bound the difference in objective between 2 policies $J(\pi') - J(\pi)$ to an equation where the $D_{TV}({\pi^\prime ||  \pi}) $ is a multiplying factor of the advantange $A_{\pi'}$. Something I'm guessing the $D_{KL}$ will probably not hold
Answers.UserDisplayName: mugoh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-09T12:51:33.257Z
Answers.Text: Interesting. I haven't read that paper yet, but I'll likely take a look. As I understand it TRPO uses KL to stop the policy from changing too drastically, and the paper "Taylor Expansion Policy Optimization" from ICML this year generalized it. Cool stuff.
Answers.UserDisplayName: harwiltz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-10T05:07:44.843Z
Answers.Text: I'll have a look at the mentioned mentioned paper. Coincidentally, Constrained Policy Optimization tries to make TRPO safe. It's safe policy search algorithms in general, but authors used TRPO as their example
Answers.UserDisplayName: mugoh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-08T14:50:34.117Z
Answers.LastActivityDate: 2020-10-08T14:50:34.117Z
Answers.UserDisplayName: harwiltz
Body: <p>In RL, both the KL divergence (DKL) and Total variational divergence (DTV) are used to measure the distance between two policies. I'm most familiar with using DKL as an early stopping metric during policy updates to ensure the new policy doesn't deviate much from the old policy.</p>
  <p>I've seen DTV mostly being used in papers giving approaches to safe RL when placing safety constraints on action distributions. Such as in <a href="https://arxiv.org/pdf/1705.10528" rel="nofollow noreferrer">Constrained Policy Optimization</a> and <a href="https://arxiv.org/pdf/1805.07708" rel="nofollow noreferrer">Lyapunov Approach to safe RL</a>.</p>
  <p>I've also seen that they are related by this formula:</p>
  <p><span class="math-container">$$
  D_{TV} = \sqrt{0.5 D_{KL}}
  $$</span></p>
  <p>When you compute the <span class="math-container">$D_{KL}$</span> between two polices, what does that tell you about them, and how is it different from what a <span class="math-container">$D_{TV}$</span> between the same two policies tells you?</p>
  <p>Based on that, are there any specific instances to prefer one over the other?</p>
  
Tags: <reinforcement-learning><comparison><probability-distribution><kl-divergence><total-variational-distance>
Title: When should one prefer using Total Variational Divergence over KL divergence in RL
UserDisplayName: mugoh
ThreadText: # When should one prefer using Total Variational Divergence over KL divergence in RL
  
  (Asked by: username_0 on 2020-10-07)
  
  In RL, both the KL divergence (DKL) and Total variational divergence (DTV) are used to measure the distance between two policies. I'm most familiar with using DKL as an early stopping metric during policy updates to ensure the new policy doesn't deviate much from the old policy.
  
  I've seen DTV mostly being used in papers giving approaches to safe RL when placing safety constraints on action distributions. Such as in [Constrained Policy Optimization](https://arxiv.org/pdf/1705.10528) and [Lyapunov Approach to safe RL](https://arxiv.org/pdf/1805.07708).
  
  I've also seen that they are related by this formula:
  
  $$
  D\_{TV} = \sqrt{0.5 D\_{KL}}
  $$
  
  When you compute the $D\_{KL}$ between two polices, what does that tell you about them, and how is it different from what a $D\_{TV}$ between the same two policies tells you?
  
  Based on that, are there any specific instances to prefer one over the other?
  
  **Tags:** reinforcement-learning, comparison, probability-distribution, kl-divergence, total-variational-distance
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-10-07. Score: 1 | Accepted answer
  
  I did not read those two specified linked/cited papers and I am not currently familiar with the [total variation distance](https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures), but I think I can answer some of your questions, given that I am reasonably familiar with the KL divergence.
  
  > When you compute the $D\_{KL}$ between two polices, what does that tell you about them
  
  The KL divergence is a measure of "distance" (or divergence, as the name suggests) between two probability distributions (i.e. probability measures) or probability densities. In reinforcement learning, [(stochastic) policies](https://ai.stackexchange.com/q/12274/2444) are probability distributions. For example, in the case your Markov decision process (MDP) has a discrete set of actions, then your policy can be denoted as $$\pi(a \mid s),$$which is the conditional probability distribution over all possible actions, given a specific state $s$. Hence, the KL divergence is a natural measure of how two policies are similar or different.
  
  There are 4 properties of the KL divergence that you always need to keep in mind
  
  1. It is asymmetric, i.e., in general, $D\_{KL}(q, p) \neq D\_{KL}(p, q)$ (where $p$ and $q$ are p.d.s); consequently, the KL divergence **cannot** be a [metric](https://en.wikipedia.org/wiki/Metric_(mathematics)) (because metrics are symmetric!)
  2. It is always non-negative
  3. It is zero when $p = q$.
  4. It is unbounded, i.e. it can be arbitrarily large; so, in other words, two probability distributions can be infinitely different, which may not be very intuitive: in fact, in the past, I used the KL divergence and, because of this property, it wasn't always clear how I should interpret the KL divergence (but this may also be due to my not extremely solid understanding of this measure).
  
  > and how is it different from what a $D\_{TV}$ between the same two policies tells you?
  
  $D\_{TV}$ is also a measure of the distance between two probability distributions, but it is **bounded**, specifically, in the range $[0, 1]$ [[1](https://arxiv.org/pdf/math/0209021.pdf)]. This property may be useful in some circumstances (which ones?). In any case, the fact that it lies in the range $[0, 1]$ potentially makes its interpretation more *intuitive*. More precisely, if you know the maximum and minimum values that a measure can give you, you can have a better idea of the relative difference between probability distributions. For instance, imagine that you have p.d.s $q$, $p$ and $p'$. If you compute $D\_{TV}(q, p)$ and $D\_{TV}(q, p')$, you can have a sense (in terms of percentage) of how much $p'$ and $p$ differ with respect to $q$.
  
  The choice between $D\_{TV}$ and $D\_{KL}$ is probably motivated by their specific properties (and it will probably depend on a case by case basis, and I expect the authors of the research papers to motivate the usage of a specific measure/[metric](https://en.wikipedia.org/wiki/Metric_(mathematics))). However, keep in mind that there is not always a closed-form solution not even to calculate the KL divergence, so you may need to approximate it (e.g. by sampling: note that the KL divergence is defined as an expectation/integral so you can approximate it with a sampling technique). So, this (computability and/or approximability) may also be a parameter to take into account when choosing one over the other.
  
  By the way, I think that your definition of the *total variational divergence* is wrong, although the DTV is related to the DKL, specifically, as follows [[1](https://arxiv.org/pdf/math/0209021.pdf)]
  
  \begin{align}
  D\_{TV} \leq \sqrt{\frac{1}{2} D\_{KL}}
  \end{align}
  
  So the DTV is bounded by the KL divergence. Given that the KL divergence is unbounded (e.g. it can take very big values, such as 600k, this bound should be very loose).
  
  Take a look at the paper [On choosing and bounding probability metrics](https://arxiv.org/pdf/math/0209021.pdf) (2002, by Alison L. Gibbs and Francis Edward Su) or [this book](http://www.yaroslavvb.com/papers/peres-markov.pdf#page=58) for information about $D\_{TV}$ (and other measures/metrics).
  
  > **Comments:**
  > **username_0**: So $D_{TV}$ being bounded is a distinguishing property.  "the fact that it lies in the range [0,1] potentially makes its interpretation more intuitive". Please clarify what it "...makes its interpretation more intuitive" means because I don't understand that part well. Thanks for pointing out the correct definition of $D_{TV}$. I'll look at the paper and book you've pointed out.  
  > **username_1**: @username_0 When I say that boundedness makes it more intuitive it's because you know exactly what is the maximum, but in the case of the KL divergence you don't know if the current value of the KL divergence is really big or actually not so big.  
  > **username_1**: Anyway, the bound shown in my answer is probably very loose, given that the KL divergence can really be arbitrarily large (e.g. 600k) and the total variational is between $0$ and $1$ (according to the sources I've seen).  
  > **username_0**: That's much clear. Emphasizing that the bound is very loose especially gives a better picture on the difference between the two.  
  > **username_0**: I've looked at the referenced book and paper. And they both explain $D_{TV}$ in depth. One point I picked is that $D_{TV}$ as a metric, converges fast because it's insensitive to element-wise differences when total difference remains the same. So $D_{TV}$ converges while $D_{KL}$, being a non-metric, doesn't. This might also influence the choice. (2) It admits *natural interpretations* and bounding techniques, as you emphasized in your answer.  
  
  ---
  
  ### Answer by username_2 on 2020-10-08. Score: 2
  
  To add to username_1's answer, I'd say also that much of the time the distance measure isn't simply a design decision, rather it comes up naturally from the model of the problem. For instance, minimizing the KL divergence between your policy and the softmax of the Q values at a given state is equivalent to policy optimization where the optimality at a given state is Bernoulli with respect to the exponential of the reward (see maximum entropy RL algorithms). As another example, the KL divergence in the VAE loss is a result of the model and not just a blind decision.
  
  I'm less familiar with total variation distance, but I know there's a nice relationship between the total variation distance of a state probability vector and a Markov chain stationary distribution relative to the timestep and the mixing time of the chain.
  
  Finally, another thing to consider is the properties of the gradients of these divergence measures. Note that the gradient of the total variation distance might blow up as the distance tends to $0$. Additionally, one must consider if unbiased estimators of the gradients from samples can be feasible. While this is generally the case with KL divergence, I'm not sure about total variation distance (as in, I literally don't know), and this is generally *not* the case with the Wasserstein metric (see Marc G. Bellemare et. al's paper "The Cramér distance as a solution to biased wasserstein gradients"). However, of course there's other scenarios where the tables are turned -- for instance, the distributional bellman operator is a contraction in the supremal Wasserstein metric but *not* in KL or total variation distance.
  
  **TL; DR:** Many times mathematical/statistical constraints suggest particular metrics.
  
  > **Comments:**
  > **username_0**: This point is quite useful. I've looked at the Constrained Policy Optimization paper again and I identify their use for $D_{TV}$ as a choice that relates to satisfying a mathematical constraint, if I'm not wrong. Specifically, in deriving a safe policy improvement, the authors bound the difference in objective between 2 policies $J(\pi') - J(\pi)$ to an equation where the $D_{TV}({\pi^\prime ||  \pi}) $ is a multiplying factor of the advantange $A_{\pi'}$. Something I'm guessing the $D_{KL}$ will probably not hold  
  > **username_2**: Interesting. I haven't read that paper yet, but I'll likely take a look. As I understand it TRPO uses KL to stop the policy from changing too drastically, and the paper "Taylor Expansion Policy Optimization" from ICML this year generalized it. Cool stuff.  
  > **username_0**: I'll have a look at the mentioned mentioned paper. Coincidentally, Constrained Policy Optimization tries to make TRPO safe. It's safe policy search algorithms in general, but authors used TRPO as their example  
  
  ---
  
  