TRPO Details

The origin paper: Schulman, John, et al. “Trust region policy optimization.” International conference on machine learning. PMLR, 2015.

Overview

This derivation comes from the Appendix A.1 of this paper: Yang, Jiachen, et al. “Adaptive incentive design with multi-agent meta-gradient reinforcement learning.” arXiv preprint arXiv:2112.10859 (2021).

The obejective is

$$J(\pi ):={\mathbb{E}}_{\pi }[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot r(s_t,a_t)].$$

The Problem is

$$\underset{\pi }{max}J(\pi ).$$

The performance difference lemma (see below) shows that

$$\begin{array}{rl}J({\pi }^{\prime })=& J(\pi )+{\mathbb{E}}_{{\pi }^{\prime }}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot A_{\pi }(s_t,a_t)]\\ =& J(\pi )+\sum _s{d}_{{\pi }^{\prime }}(s)\sum _a{\pi }^{\prime }(a\mid s)\cdot A_{\pi }(s,a),\end{array}$$

where $d_{\pi }(s)$ is the discounted state visitation frequencies and $A_{\pi }$ is the advantage function under policy $\pi$.

TRPO makes a local approximation, whereby $d_{{\pi }^{\prime }}$ is replaced by $d_{\pi }(s)$

One can define

$$L_{\pi }({\pi }^{\prime }):=J(\pi )+\sum _s{d}_{\pi }(s)\sum _a{\pi }^{\prime }(a\mid s)\cdot A_{\pi }(s,a)$$

and derive the lower bound $J({\pi }^{\prime })\ge L_{\pi }({\pi }^{\prime })-c\cdot D_{\mathrm{KL}}^{max}(\pi ,{\pi }^{\prime })$, where $D_{\mathrm{KL}}^{max}$ is the KL divergence maximized over states and $c$ depends on $\pi$. The KL divergence penalty can be replaced by a constraint, so the problem becomes

$$\begin{array}{rl}& \underset{{\theta }^{\prime }}{max}\sum _s{d}_{\theta }(s)\sum _a{{\pi }^{\prime }}_{{\theta }^{\prime }}(a\mid s)\cdot A_{\theta }(s,a)\\ & \text{ s.t. }{\overline{D}}_{\mathrm{KL}}^{\theta }(\theta ,{\theta }^{\prime })\le \delta ,\end{array}$$

where ${\overline{D}}_{\mathrm{KL}}^{\theta }$ is the KL divergence averaged over states $s\sim d_{\theta }$. Using importance sampling, the summation over actions $\sum _a(\cdot )$ is replaced by ${\mathbb{E}}_{a\sim q}[\frac{1}{q(a\mid s)}(\cdot )]$. It is convenient to choose $q={\pi }_{\theta }$, which results in:

$$\begin{array}{rl}& \underset{{\theta }^{\prime }}{max}{\mathbb{E}}_{s\sim d_{\theta },a\sim {\pi }_{\theta }}[\frac{{{\pi }^{\prime }}_{{\theta }^{\prime }}(a\mid s)}{{\pi }_{\theta }(a\mid s)}{A}_{\theta }(s,a)]\\ & \text{ s.t. }{\mathbb{E}}_{s\sim d_{\theta }}\left[D_{\mathrm{KL}}({\pi }_{\theta }(\cdot \mid s),{{\pi }^{\prime }}_{{\theta }^{\prime }}(\cdot \mid s))\right]\le \delta .\end{array}$$

During online learning, the ${\theta }^{\prime }$ that is optimized and the old $\theta$ are the same at each iteration, so the gradient estimate is

$${\mathbb{E}}_{{\pi }_{\theta }}[\frac{{\mathrm{\nabla }}_{\theta }{\pi }_{\theta }(a\mid s)}{{\pi }_{\theta }(a\mid s)}{A}_{\theta }(s,a)].$$

Performance Difference Lemma

In this section, the $\pi$ and ${\pi }^{\prime }$ from the previous text have been swapped.

For all policies $\pi ,{\pi }^{\prime }$ and states $s_0$,

$$\begin{array}{rl}{V}^{\pi }(s_0)-V^{{\pi }^{\prime }}(s_0)=& {\mathbb{E}}_{\tau \sim {Pr}^{\pi }(\tau |s_0=s)}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{A}^{{\pi }^{\prime }}(s_t,a_t)]\\ =& \frac{1}{1-\gamma }{\mathbb{E}}_{s\sim d_{s_0}^{\pi }}{\mathbb{E}}_{a\sim \pi (\cdot |s)}[A^{{\pi }^{\prime }}(s,a)].\end{array}$$

Kakade, Sham, and John Langford. “Approximately optimal approximate reinforcement learning.” Proceedings of the Nineteenth International Conference on Machine Learning. 2002.

Proof

The proof is provided in the appendix of “On the theory of policy gradient methods: Optimality, approximation, and distribution shift” and I just transcribed it here with additional details.

Let $\stackrel{\pi }{Pr}(\tau \mid s_0=s)$ denote the probability of observing a trajectory $\tau$ when starting in state $s$ and following the policy $\pi$. Using a telescoping argument, we have:

$$\begin{array}{rl}& V^{\pi }(s)-V^{{\pi }^{\prime }}(s)\\ =& {\mathbb{E}}_{\tau \sim {Pr}^{\pi }(\tau |s_0=s)}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t}r(s_t,a_t)]-V^{{\pi }^{\prime }}(s)\\ =& {\mathbb{E}}_{\tau \sim {Pr}^{\pi }(\tau |s_0=s)}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t(r(s_t,a_t)+V^{{\pi }^{\prime }}(s_t)-V^{{\pi }^{\prime }}(s_t))\right]-V^{{\pi }^{\prime }}(s)\\ \stackrel{(a)}{=}& {\mathbb{E}}_{\tau \sim {Pr}^{\pi }(\tau |s_0=s)}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t(r(s_t,a_t)+\gamma V^{{\pi }^{\prime }}(s_{t+1})-V^{{\pi }^{\prime }}(s_t))\right]\\ \stackrel{(b)}{=}& {\mathbb{E}}_{\tau \sim {Pr}^{\pi }(\tau |s_0=s)}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t(r(s_t,a_t)+\gamma \mathbb{E}[V^{{\pi }^{\prime }}(s_{t+1})|s_t,a_t]-V^{{\pi }^{\prime }}(s_t))\right]\\ \stackrel{(c)}{=}& {\mathbb{E}}_{\tau \sim {Pr}^{\pi }(\tau |s_0=s)}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{A}^{{\pi }^{\prime }}(s_t,a_t)]\\ =& \frac{1}{1-\gamma }{\mathbb{E}}_{s^{\prime }\sim d_s^{\pi }}{\mathbb{E}}_{a\sim \pi (\cdot |s^{\prime })}[A^{{\pi }^{\prime }}(s^{\prime },a)],\end{array}$$

where $(a)$ rearranges terms in the summation and cancels the $V^{{\pi }^{\prime }}(s_0)$ term with the $-V^{{\pi }^{\prime }}(s)$ outside the summation, and $(b)$ uses the tower property of conditional expectations and the final equality follows from the definition of $d_s^{\pi }$. $◼$

Details

$(a)$:

$$-a_0+\sum _{k=0}^{\mathrm{\infty }}(a_k-b_k)=\sum _{k=0}^{\mathrm{\infty }}(a_{k+1}-b_k).$$

$(b)$: The tower property of conditional expectations (or law of total probability): If $\mathcal{H}\subseteq \mathcal{G}$, then

$$\mathbb{E}[\mathbb{E}[X\mid \mathcal{G}]\mid \mathcal{H}]=\mathbb{E}[X\mid \mathcal{H}].$$

Correspondingly,

• $\mathcal{G}=\tau \sim {Pr}^{\pi }(\tau \mid s_0=s)$,
• $\mathcal{H}=(s_t,a_t)$.

$(c)$: Step $(b)$ is necessary. Note that

$$Q^{\pi }(s,a)\ne r(s,a)+\gamma \cdot V^{\pi }(s^{\prime }).$$

But

$$Q^{\pi }(s,a)=r(s,a)+\gamma \cdot \sum _{s^{\prime }}P(s^{\prime }\mid s,a)\cdot V^{\pi }(s^{\prime }).$$

Other proofs

Check other proofs here and here.

剩下的没写完…发现暂时用不到了，之后要用到再看