Answers.Body: <p>We can start with equation (30):</p>
  
  <p><span class="math-container">$$
  \bar{A}(s) = P(a \neq \tilde{a}) \mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]
  $$</span></p>
  
  <p>Taking the absolute value of both sides, the equality remains true. We can pull the probability term out of the absolute value since it is guaranteed to be nonnegative.</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| = P(a \neq \tilde{a}) |\mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]|
  $$</span></p>
  
  <p>By Definition 1, <span class="math-container">$P(a \neq \tilde{a}) \leq \alpha$</span>. Substituting this definition in, we get:</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| \leq \alpha \cdot |\mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]|
  $$</span></p>
  
  <p>By Jensen's Inequality, we can take the absolute value inside the expectation.</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| \leq \alpha \cdot \mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [|A_\pi(s, \tilde{a}) - A_\pi(s, a)|]
  $$</span></p>
  
  <p>The expectation of a random variable is always upper bounded by the max value of that variable.</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| \leq \alpha \cdot \max_{a,\tilde{a}|a\neq\tilde{a}} |A_\pi(s, \tilde{a}) - A_\pi(s, a)|
  $$</span></p>
  
  <p>This part is a little strange, and I'm not sure if this is the logic that the authors followed, but it is still true. For any <span class="math-container">$a,b$</span>, we have that <span class="math-container">$|a - b| \leq |a| + |b|$</span>.</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| \leq \alpha \cdot \max_{a,\tilde{a}|a\neq\tilde{a}} (|A_\pi(s, \tilde{a})| + |A_\pi(s, a)|)
  $$</span></p>
  
  <p>For <span class="math-container">$a \neq \tilde{a}$</span>, it must be that either <span class="math-container">$|A_\pi(s, \tilde{a})| \geq |A_\pi(s, a)|$</span> or vice versa. We can use this to replace the pair of advantage functions with 2 times the max of the two.</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| \leq \alpha \cdot 2 \max_{a} |A_\pi(s, a)|
  $$</span></p>
  
  <p>Now, if we take the max over <span class="math-container">$a$</span> and <span class="math-container">$s'$</span>, our inequality still holds, since we are taking the maximum over a set that contains <span class="math-container">$s$</span>. Making this substitution gives us (31).</p>
  
  <p><span class="math-container">$$
  |\bar{A}(s)| \leq \alpha \cdot 2 \max_{a,s'} |A_\pi(s', a)|
  $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-29T00:29:36.057Z
Answers.LastActivityDate: 2018-11-29T00:29:36.057Z
Answers.UserDisplayName: Nishant Desai
Body: <p>In <a href="https://arxiv.org/pdf/1502.05477.pdf" rel="nofollow noreferrer">the <em>Trust Region Policy Optimization</em> paper</a>, in <a href="https://arxiv.org/pdf/1502.05477.pdf#page=11" rel="nofollow noreferrer">Lemma 2 of Appendix A (p. 11)</a>, I didn't quite understand how inequality (31) is derived from equality (30), which is:</p>
  <p><span class="math-container">$$\bar{A}(s) = P(a \neq \tilde{a} | s) \mathbb{E}_{(a, \tilde{a}) \sim (\pi, \tilde{\pi})|a \neq  \tilde{a}} \left[ A_{\pi}(s, \tilde{a}) - A_{\pi}(s,a) \right]$$</span>
  <span class="math-container">$$|\bar{A}(s)| \le \alpha. 2 \max_{s,a} |A_{\pi}(s,a)|$$</span></p>
  <p>Would you mind let me know how the inequality is derived?</p>
  
Tags: <reinforcement-learning><deep-rl><papers><proofs><trust-region-policy-optimization>
Title: How is inequality 31 derived from equality 30 in lemma 2 of the "Trust Region Policy Optimization" paper?
UserDisplayName: Afshin Oroojlooy
ThreadText: # How is inequality 31 derived from equality 30 in lemma 2 of the "Trust Region Policy Optimization" paper?
  
  (Asked by: username_0 on 2018-11-27)
  
  In [the *Trust Region Policy Optimization* paper](https://arxiv.org/pdf/1502.05477.pdf), in [Lemma 2 of Appendix A (p. 11)](https://arxiv.org/pdf/1502.05477.pdf#page=11), I didn't quite understand how inequality (31) is derived from equality (30), which is:
  
  $$\bar{A}(s) = P(a \neq \tilde{a} | s) \mathbb{E}\_{(a, \tilde{a}) \sim (\pi, \tilde{\pi})|a \neq \tilde{a}} \left[ A\_{\pi}(s, \tilde{a}) - A\_{\pi}(s,a) \right]$$
  $$|\bar{A}(s)| \le \alpha. 2 \max\_{s,a} |A\_{\pi}(s,a)|$$
  
  Would you mind let me know how the inequality is derived?
  
  **Tags:** reinforcement-learning, deep-rl, papers, proofs, trust-region-policy-optimization
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-29. Score: 5 | Accepted answer
  
  We can start with equation (30):
  
  $$
  \bar{A}(s) = P(a \neq \tilde{a}) \mathbb{E}\_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A\_\pi(s, \tilde{a}) - A\_\pi(s, a)]
  $$
  
  Taking the absolute value of both sides, the equality remains true. We can pull the probability term out of the absolute value since it is guaranteed to be nonnegative.
  
  $$
  |\bar{A}(s)| = P(a \neq \tilde{a}) |\mathbb{E}\_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A\_\pi(s, \tilde{a}) - A\_\pi(s, a)]|
  $$
  
  By Definition 1, $P(a \neq \tilde{a}) \leq \alpha$. Substituting this definition in, we get:
  
  $$
  |\bar{A}(s)| \leq \alpha \cdot |\mathbb{E}\_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A\_\pi(s, \tilde{a}) - A\_\pi(s, a)]|
  $$
  
  By Jensen's Inequality, we can take the absolute value inside the expectation.
  
  $$
  |\bar{A}(s)| \leq \alpha \cdot \mathbb{E}\_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [|A\_\pi(s, \tilde{a}) - A\_\pi(s, a)|]
  $$
  
  The expectation of a random variable is always upper bounded by the max value of that variable.
  
  $$
  |\bar{A}(s)| \leq \alpha \cdot \max\_{a,\tilde{a}|a\neq\tilde{a}} |A\_\pi(s, \tilde{a}) - A\_\pi(s, a)|
  $$
  
  This part is a little strange, and I'm not sure if this is the logic that the authors followed, but it is still true. For any $a,b$, we have that $|a - b| \leq |a| + |b|$.
  
  $$
  |\bar{A}(s)| \leq \alpha \cdot \max\_{a,\tilde{a}|a\neq\tilde{a}} (|A\_\pi(s, \tilde{a})| + |A\_\pi(s, a)|)
  $$
  
  For $a \neq \tilde{a}$, it must be that either $|A\_\pi(s, \tilde{a})| \geq |A\_\pi(s, a)|$ or vice versa. We can use this to replace the pair of advantage functions with 2 times the max of the two.
  
  $$
  |\bar{A}(s)| \leq \alpha \cdot 2 \max\_{a} |A\_\pi(s, a)|
  $$
  
  Now, if we take the max over $a$ and $s'$, our inequality still holds, since we are taking the maximum over a set that contains $s$. Making this substitution gives us (31).
  
  $$
  |\bar{A}(s)| \leq \alpha \cdot 2 \max\_{a,s'} |A\_\pi(s', a)|
  $$
  
  
  ---
  
  