Policy Optimization

This is an automatically translated post by LLM. The original post is in Chinese. If you find any translation errors, please leave a comment to help me improve the translation. Thanks!

This article mainly reviews and summarizes reinforcement learning algorithms based on policy optimization theorems and related variants.

Preliminaries

A Markov decision process (MDP) can be defined by a five-tuple $<\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{T},\gamma ,{\rho }_0>$, where:

• $\mathcal{S}$ represents the state space, a set of states
• $\mathcal{A}$ represents the action space, a set of actions
• $\mathcal{R}:\mathcal{S}\times \mathcal{A}\to \mathbb{R}$ represents the reward function, $\mathcal{R}(s,a)$ is the reward obtained by taking action $a$ in state $s$
• $\mathcal{T}:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to [0,1]$ represents the state transition probability function, $\mathcal{T}(s^{\prime }|s,a)$ is the probability of transitioning from state $s$ to state $s^{\prime }$ by taking action $a$
• $\gamma$ represents the discount factor
• ${\rho }_0:\mathcal{S}\to [0,1]$ represents the initial state distribution

The decision process of an agent is represented by a stochastic policy $\pi :\mathcal{S}\times \mathcal{A}\to [0,1]$, where $\pi (a|s)$ is the probability of the agent choosing action $a$ in state $s$. Based on policy $\pi$, the state value function can be defined as: $$\begin{array}{}\text{(1)}& V_{\pi }(s)=\mathbb{E}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\mathcal{R}(s_t,a_t)|\pi ,s]\end{array}$$ The state-action value function is: $$\begin{array}{}\text{(2)}& Q_{\pi }(s,a)=\mathcal{R}(s,a)+\gamma {\mathbb{E}}_{s^{\prime }\sim \mathcal{T}(\cdot |s,a)}[V_{\pi }(s^{\prime })]\end{array}$$

Advantage function: $$\begin{array}{}\text{(3)}& A_{\pi }(s,a)=Q_{\pi }(s,a)-V_{\pi }(s)\end{array}$$ The agent's optimization goal is usually to maximize the discounted return on the initial state distribution, i.e.: $$\begin{array}{}\text{(4)}& \eta (\pi )={\mathbb{E}}_{s\sim {\rho }_0}[V_{\pi }(s)]\end{array}$$ The discounted visit frequency of a state is represented as: $$\begin{array}{}\text{(5)}& {\rho }_{\pi }(s)=(P(s_0=s)+\gamma P(s_1=s)+{\gamma }^{2}P(s_2=s)+...)\end{array}$$

Policy gradient theorem: $$\begin{array}{}\text{(6)}& \mathrm{\nabla }\eta (\pi )=\sum _{s,a}{\rho }_{\pi }(s)\mathrm{\nabla }\pi (a|s)Q_{\pi }(s,a)\end{array}$$

Approximately Optimal Approximate Reinforcement Learning

Kakade, S. & Langford, J. Approximately Optimal Approximate Reinforcement Learning. in Proceedings of the Nineteenth International Conference on Machine Learning 267–274 (Morgan Kaufmann Publishers Inc., 2002).

This paper addresses three questions:

1. Is there a performance metric that guarantees improvement at each update step?
2. How difficult is it to verify that an update improves this performance metric?
3. What level of performance can be achieved after a reasonable number of policy updates?

Consider the following conservative policy update rule: $$\begin{array}{}\text{(7)}& {\pi }_{new}(a|s)=(1-\alpha )\pi (a|s)+\alpha {\pi }^{\prime }(a|s)\end{array}$$ where $\alpha \in [0,1]$. To ensure policy improvement at $\alpha =1$, ${\pi }^{\prime }$ needs to take better actions than $\pi$ in every state. For $0<\alpha <1$, policy improvement only requires ${\pi }^{\prime }$ to choose better actions in most states rather than all. Define the policy advantage ${\mathbb{A}}_{\pi ,{\rho }_0}({\pi }^{\prime })$ as: $$\begin{array}{}\text{(8)}& {\mathbb{A}}_{\pi ,{\rho }_0}({\pi }^{\prime })={\mathbb{E}}_{s\sim {\rho }_{\pi }}[{\mathbb{E}}_{a\sim {\pi }^{\prime }(\cdot |s)}[A_{\pi }(s,a)]]\end{array}$$ This policy advantage function measures the extent to which ${\pi }^{\prime }$ selects actions with greater advantage under the initial state distribution ${\rho }_0$. For $\alpha =0$, it is evident that $\frac{\partial \eta }{\partial \alpha }{|}_{\alpha =0}=\frac{1}{1-\gamma }{\mathbb{A}}_{\pi ,{\rho }_0}$.

to be continue......

TRPO

Schulman, J., Levine, S., Moritz, P., Jordan, M. & Abbeel, P. Trust region policy optimization. in Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37 1889–1897 (JMLR.org, 2015).

Policy advantage theorem: $$\begin{array}{}\text{(9)}& \eta (\tilde{\pi })=\eta (\pi )+{\mathbb{E}}_{s_0\sim {\rho }_0,a\sim \tilde{\pi }(\cdot |s),s^{\prime }\sim \mathcal{T}(\cdot |s,a)}[\sum _{t=1}^{\mathrm{\infty }}{\gamma }^t{A}_{\pi }(s_t,a_t)]\end{array}$$ Proof is as follows (for ease of writing, omit the expectation subscripts $s_0\sim {\rho }_0,s^{\prime }\sim \mathcal{T}(\cdot |s,a)$, $a\sim \pi (\cdot |s)$ is abbreviated as $a\sim \pi$): $$\begin{array}{}\text{(10)}& & {\mathbb{E}}_{a\sim \tilde{\pi }}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{A}_{\pi }(s_t,a_t)]\text{(11)}& & ={\mathbb{E}}_{a\sim \tilde{\pi }}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t[Q_{\pi }(s_t,a_t)-V_{\pi }(s_t)]\right]\text{(12)}& & ={\mathbb{E}}_{a\sim \tilde{\pi }}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t[r_t+\gamma V_{\pi }(s_{t+1})-V_{\pi }(s_t)]\right]\text{(13)}& & ={\mathbb{E}}_{a\sim \tilde{\pi }}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{r}_t\right]+{\mathbb{E}}_{a\sim \tilde{\pi }}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t+1}{V}_{\pi }(s_{t+1})]-{\mathbb{E}}_{a\sim \tilde{\pi }}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{V}_{\pi }(s_t)]\text{(14)}& & =\eta (\tilde{\pi })-{\mathbb{E}}_{a\sim \tilde{\pi }}[V_{\pi }(s_0)]\text{(15)}& & =\eta (\tilde{\pi })-\eta (\pi )\end{array}$$

Based on the state visitation frequency ${\rho }_{\pi }$, equation $\text{???}$ can also be written in the following form: $$\begin{array}{}\text{(16)}& \eta (\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\tilde{\pi }}(s)\sum _a\tilde{\pi }(a|s)A_{\pi }(s,a)\end{array}$$ According to equation $\text{???}$, if for each state $s$, $\sum _a\tilde{\pi }(a|s)A_{\pi }(s,a)\ge 0$, then the new policy is guaranteed to be better than the old policy. However, due to the dependence of equation $\text{???}$ on ${\rho }_{\tilde{\pi }}$, it is not directly computable in practical optimization. Therefore, considering a local estimate of $\eta$: $$\begin{array}{}\text{(17)}& L_{\pi }(\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\pi }(s)\sum _a\tilde{\pi }(a|s)A_{\pi }(s,a)\end{array}$$ The difference between $L_{\pi }(\tilde{\pi })$ and $\eta (\tilde{\pi })$ lies in replacing ${\rho }_{\tilde{\pi }}$ with ${\rho }_{\pi }$. Next, the analysis of $L_{\pi }(\tilde{\pi })$ is performed. If there is a parameterized policy ${\pi }_{\theta }$ that is differentiable with respect to $\theta$, then: $$\begin{gathered} \begin{array}{}\text{(18)}& L_{{\pi }_{{\theta }_0}}({\pi }_{{\theta }_0})=\eta ({\pi }_{{\theta }_0}) \\ {\mathrm{\nabla }}_{\theta }{L}_{{\pi }_{{\theta }_0}}({\pi }_{\theta }){|}_{\theta ={\theta }_0}={\mathrm{\nabla }}_{\theta }\eta ({\pi }_{\theta }){|}_{\theta ={\theta }_0}\end{array} \end{gathered}$$ Therefore, if the update of $\pi$ is small enough, improving $L_{\pi }$ will also improve $\eta$. Considering the following policy update: $$\begin{array}{}\text{(19)}& \tilde{\pi }(a|s)=(1-\alpha )\pi (a|s)+\alpha {\pi }^{\prime }(a|s)\end{array}$$ where ${\pi }^{\prime }=\arg \underset{{\pi }^{\prime }}{max}{L}_{\pi }(\tilde{\pi })$, it can be shown (proof in [(Kakade & Langford, 2002)][approximately_optimal]): $$\begin{array}{}\text{(20)}& \eta (\tilde{\pi })\ge L_{\pi }(\tilde{\pi })-\frac{2ϵ\gamma }{(1-\gamma (1-\alpha ))(1-\gamma )}{\alpha }^2\end{array}$$ where $ϵ=\underset{s}{max}|{\mathbb{E}}_{a\sim \tilde{\pi }(\cdot |s)}{A}_{\pi }(s,a)|$

Continued in the next message...