In the Trust Region Policy Optimization paper, in Lemma 2 of Appendix A, I did not quite understand deriving inequality (31) from (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?


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)| $$

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.