MEMORY-CONSTRAINED POLICY OPTIMIZATION
Year: 2021

Abstract:
We introduce a new constrained optimization method for policy gradient reinforcement learning, which uses two trust regions to regulate each policy update. In addition to using the proximity of one single old policy as the first trust region as done by prior works, we propose to form a second trust region through the construction of another virtual policy that represents a wide range of past policies. We then enforce the new policy to stay closer to the virtual policy, which is beneficial in case the old policy performs badly. More importantly, we propose a mechanism to automatically build the virtual policy from a memory buffer of past policies, providing a new capability for dynamically selecting appropriate trust regions during the optimization process. Our proposed method, dubbed as MemoryConstrained Policy Optimization (MCPO), is examined on a diverse suite of environments including robotic locomotion control, navigation with sparse rewards and Atari games, consistently demonstrating competitive performance against recent on-policy constrained policy gradient methods.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) combined with neural networks is the current workhorse in machine learning. Using neural networks to approximate value and policy functions enables classical approaches such as Q-learning and policy gradient to achieve promising results on many challenging problems such as Go, Atari games and robotics (Silver et al., 2017; Mnih et al., 2015; Lillicrap et al., 2016; Mnih et al., 2016). Compared to Deep Q-learning, deep policy gradient (PG) methods are often more flexible and applicable to both discrete and continuous action problems. However, these methods tend to suffer from high sample complexity and training instability since the gradient may not accurately reflect the policy gain when the policy changes substantially (Kakade & Langford, 2002). This is exacerbated for deep policy networks where numerous parameters need to be optimized and small updates in parameter space can lead to huge changes in policy space.
To address this issue, one solution is to regularize each policy update by restricting the Kullback– Leibler (KL) divergence between the new policy and the previous one, which can guarantee monotonic policy improvement (Schulman et al., 2015a). However, jointly optimizing the approximate advantage function and the KL term does not work in practice. Therefore, Schulman et al. (2015a) proposed Trust Region Policy Optimization (TRPO) to constrain the new policy within a KL divergence radius, which requires second-order gradients. Alternatives such as Proximal Policy Optimization (PPO) (Schulman et al., 2017) use a simpler first-order optimization with adaptive KL or clipped surrogate objective while still maintaining the reliable performance of TRPO. Recent methods recast the problem through a new lens using Expectation-Maximization or Mirror Descent Optimization, and this also results in first-order optimization with KL divergence term in the loss function (Abdolmaleki et al., 2018; Song et al., 2019; Yang et al., 2019; Tomar et al., 2020).
An issue with the above methods is that the previous policy used to restrict the new policy may be suboptimal and thus unreliable in practice. For example, due to stochasticity and imperfect approximations, consider that the new policy may fall into a local optimum even under trust-region optimizations. Then in the next update, this policy will become the “previous” policy, and will continue pulling the next policy to stay in the local optimum, thus slowing down the training progress. For on-policy methods using mini-batch updates like PPO, the situation is more complicated as the “previous” policy is defined as the old policy that was used to collect data, which can be either very far or close to the current policy. There is no guarantee that the old policy defines a reasonable trust region for regulating the new policy.
In this paper, we propose a novel constrained policy iteration procedure, dubbed as MemoryConstrained Policy Optimization (MCPO), wherein a virtual policy representing past policies takes part in regularizing each policy update. The virtual and the old policy together form two trust regions that attract the new policy by minimizing two KL divergences. The virtual policy is designed to complement the old policy, attracting the new policy more when the old policy performs badly. As such, we assign different coefficient weights to the two KL terms. The coefficient weights are computed dynamically based on the performance of the two policies (the higher performer yields higher coefficient weights). To create the virtual policy, we maintain a memory buffer of past policies, from which we build a mixture of policies. In particular, we use a neural network–named the attention network, which takes the context surrounding the current, the old and the virtual policy, to generate the attention weights to each policy in the memory. Then, we use the attention weights to perform a convex combination of the parameters of each policy, forming the virtual policy. The attention network is optimized to maximize the approximate expected advantages of the virtual policy. To train our system, we jointly optimize the policy and attention networks, alternating between sampling data from the policy and updating the networks in a mini-batch manner.
We verify our proposed MCPO through a diverse set of experiments and compare ours with the performance of recent constrained policy optimization baselines. In our experiment on classical control tasks, amongst tested models, MCPO shows minimal sensitivity to hyperparameter changes, consistently achieving good performance across tasks and hyperparameters. Our testbed on 6 Mujoco tasks shows that MCPO with a big policy memory consistently outperforms others where the attention network plays an important role. We also demonstrate MCPO’s capability of learning efficiently on sparse reward and high-dimensional problems such as navigation and Atari games. Finally, our ablation study highlights the necessity of each component in MCPO.

heading: 2 BACKGROUND: POLICY OPTIMIZATION WITH TRUST REGION
text: In this section, we briefly review some fundamental constrained policy optimization approaches. A general idea is to force the new policy πθ to be close to a recent policy πθold . In this paper, we refer to a policy as its parameters (i.e. policy θ means policy πθ).
Conservative Policy Iteration (CPI) The method starts with a basic objective of policy gradient algorithms, which is to maximize the expected advantage Ât.
LCPI (θ) = Êt [ πθ (at|st) πθold (at|st) Ât ] where the advantage Ât is a function of returns collected from (st, at) by using πθold (see Appendix A.2) and Êt [·] indicates the empirical average over a finite batch of data. To constrain policy updates, the new policy is a mixture of the old and the greedy policy: θ̃ = argmax LCPI (θ). That is, θ = αθold + (1 − α)θ̃ where α is the mixture hyperparameter (Kakade & Langford, 2002). As the data is sampled from previous iteration’s policy θold, the objective needs importance sampling estimation. Hereafter, we denote πθ(at|st)πθold (at|st) as ratt (θ) for short.
KL-Regularized Policy Optimization (with fixed or adaptive KL coefficient) Another way to enforce the constraint is to jointly maximize the expected advantage and minimize KL divergence between the new and old policy, which ensures monotonic improvement (Schulman et al., 2015a).
LKLPO (θ) = Êt [ ratt (θ) Ât − βKL [πθold (·|st) , πθ (·|st)] ] where β is a hyperparameter that controls the degree of update conservativeness, which can be fixed (KL Fixed) or changed (KL Adaptive) during training (Schulman et al., 2017).
Trust Region Policy Optimization (TRPO) The method optimizes the expected advantage with hard constraint (Schulman et al., 2015a). This is claimed as a practical implementation that is less conservative than the theoretically justified algorithm using KL regularizer mentioned above.
LTRPO (θ) = Êt [ ratt (θ) Ât ] st δ ≥ KL [πθold (·|st) , πθ (·|st)]
where δ is the KL constraint radius.
Proximal Policy Optimization (PPO) PPO is a family of constrained policy optimization, which uses first-order optimization and mini-batch updates including KL Adaptive and clipped PPO. In this paper, we use PPO to refer to the method that limits the change in policy by clipping the loss function (clipped PPO) (Schulman et al., 2017).
LPPO (θ) = Êt [ min ( ratt (θ) Ât, clip (ratt (θ) , 1− , 1 + ) Ât )] where is the clip hyperparameter.
In the above equations, θ is the currently optimized policy, which is also referred to as the current policy. θold represents a past policy, which can be one step before the current policy or the last policy used to interact with the environment. In either case, the rule to decide θold is fixed throughout training. If for some reason, θold is not optimal, it is unavoidable that the following updates will be negatively impacted. We will address this issue in the next section.

heading: 3 MEMORY-CONSTRAINED POLICY OPTIMIZATION (MCPO)

heading: 3.1 TWO KL DIVERGENCE CONSTRAINTS
text: In trust-region methods with mini-batch updates such as PPO, the old policy θold is often chosen as the last policy that is used to collect observations from the environment. Before the next environment interaction, this old policy is fixed across policy updates, and can be one or many steps before the current policy depending on the mini-batch size and the number of update loops. This can be detrimental to the optimization if this old policy is poor in quality, forcing the following updates to be close to a poor solution. To tackle this issue, we propose to constrain the new policy not only to the policy θold, but also to a changeable policy that is representative of many past policies. Let ψ denote the virtual policy that represents the history of policies. ψ is dynamically computed based on the past policies using attention mechanism (see Sec. 3.2). In contrast to the fixed θold, depending on the attention weights, ψ can represent a further or closer checkpoint to the current policy than θold. We use both ψ and θold to construct the objective function as follows,
L1 (θ) = Êt [ ratt (θ) Ât ] − βÊt [(1− αt (·|st))KL [πθold (·|st) , πθ (·|st)]] (1) − βÊt [αt (·|st)KL [πψ (·|st) , πθ (·|st)]]
where αt (·|st) is the coefficient weight resembling a forget gate, and β is the scaling coefficient of the KL constraint terms. In this paper, the expectation is estimated by taking average over t in a mini-batch of sampled data.
The forget gate determines how much the new policy should forget the virtual policy from the memory and focus on the θold. Intuitively, if the virtual policy is better than the old policy, the new policy should be kept close to the virtual policy and vice versa. Hence, αt = e Rt(ψ)
eRt(ψ)+eRt(θold) where
Rt (ψ) measures the performance of the policy ψ, which can be estimated by weighted importance sampling. That is Rt (ψ) = ratt (ψ) Ât.
Besides deciding which trust region the new policy should rely on, we dynamically weigh the whole KL terms via adjusting β. Using a fixed threshold dtarg to change β (e.g in KL Adaptive, if KL [πθold (·|st) , πθ (·|st)] > dtarg, increase β (Schulman et al., 2017)) showed limited performance since dtarg should vary depending on the current learning. We instead make use of ψ as a
reference for selecting β. Let d (a, b) = Êt [KL [πa (·|st) , πb (·|st)]] denote the “distance” between 2 policies πa and πb, we propose a switching-β rule as follows,
{ β = βmax if d (θold, θ) > d (θold, ψ) β = βmin otherwise
(2)
The intuition is that we encourage the enforcement of the constraint when πθ is too far from πθold using the distance between πθold and πψ as a reference.
Algorithm 1 Memory-Constrained Policy Optimization (for 1 actor). Require: A policy bufferM, an initial policy πθold . T , K, B are the learning horizon, number of
update epochs, and batch size, respectively. 1: Initialize ψold ← θold, θ ← θold 2: for iteration = 1, 2, ... do 3: Run policy πθold in environment for T timesteps. Compute advantage estimates Â1, ..., ÂT 4: for epoch = 1, 2, ...K do 5: for batch = 1, 2, ...T/B do 6: Compute ψ (Eq. 4) using ψold, θ, θold, then optimize LMCPO wrt θ (Eq. 5) 7: if d (θ, ψ) > d (θold, ψ) then add θ toM 8: if |M| > N then remove the last item fromM 9: ψold ← ψ
10: end for 11: end for 12: θold ← θ 13: end for

heading: 3.2 LEARNING TO GENERATE THE VIRTUAL POLICY
text: It is critical to compute a suitable virtual policy. On one hand, if the virtual policy is too far from the currently optimizing point, it will be irrelevant, pulling the new policy back and postponing the learning. On the other hand, if the virtual policy is too recent, it will not complement θold and cannot prevent major changes in the policy update. Also, it is reasonable to find a virtual policy that has good performance on current data. Otherwise, using trust regions near poor policies could destroy the learning. We will utilize these intuitions to build the virtual policy.
Policy Memory We first maintain a memory buffer M that stores past policy parameters M = {θj}|M|j=1 . During optimization, we add a policy’s parameter to M if it is far enough from ψ. In particular, we measure the distances d (θold, ψ) and d (θ, ψ), then propose conditional writing:
Add θ to M if d (θ, ψ) > d (θold, ψ) (3) The memory capacity is N . When the memory is full, we discard the earliest policy inM. Context Vector We hypothesize that the context surrounding θold, ψold and θ, where ψold is the last virtual policy, plays a role in determining the next virtual policy. We build the context by extracting specific features: pair-wise distances between policies (d (θold, ψold), d (θ, ψold), d (θold, θ)), the empirical returns of these policies (Êt [Rt (ψold)], Êt [Rt (θ)], Êt [Rt (θold)]), policy entropy (Êt [− log (πψold (·|st))], Êt [− log (πθ (·|st))], Êt [− log (πθold (·|st))]) and value losses (Êt (Vψold (st)− Vtarget (st)) 2, Êt (Vθ (st)− Vtarget (st))2, Êt (Vθold (st)− Vtarget (st)) 2). These features form a context vector vcontext that captures the properties of each policy and the relationship between them, which can represent the context that generates the attention weights.
Attention Mechanism We argue that the virtual policy should be determined based on the context. A simple strategy such as taking average of policies in M is likely sub-optimal as the quality of these policies vary and some can be irrelevant to the current learning context. Hence, we propose to sum the policies in a weighted manner wherein the weights are generated by a neural network whose input is vcontext. We compute ψ by performing “attention” in the parameter space as follows,
ψ = |M|∑ j fϕ (vcontext)j θj (4)
where fϕ is the attention network– a feed-forward neural network parameterized by ϕ with softmax activation. The network outputs a N -dimensional output vector establishing the attention weights. Here ψ is a function of ϕ and we train ϕ to improve ψ’s performance.
Objective function Given the virtual policy ψ (ϕ), we find ϕ to maximize its performance L2 (ϕ) = Êt [Rt (ψ (ϕ))]. We aim to obtain the best representative of past policies without examining the performance of each individual policy inM since evaluating all policies is highly expensive, especially when |M| is large. In addition, learning a “soft” attention is more flexible than searching for a “hard” policy that performs best (in terms of L2) since the performance measurement itself can be noisy and not always reliable. To train the whole system, we use gradient ascent to maximize
LMCPO = L1 (θ) + L2 (ϕ) . (5)
When optimizingL1, we fix ϕ and only update θ to avoid gradient back-propagation via ϕ (similarly, when optimizing L2, we fix θ and only update ϕ). Theoretical motivation for the design of L1 and L2 is given in Appendix C. We implement MCPO using minibatch update procedure (Schulman et al., 2017). Algo. 1 illustrates a high-level implementation of MCPO with 1 actor.

heading: 4 EXPERIMENTAL RESULTS
text: In our experiments, the main baselines are recent on-policy constrained methods that use first-order optimization, in which most of them employ KL terms in the objective function. They are KL Adaptive, KL Fixed, PPO (Schulman et al., 2017), MDPO (Tomar et al., 2020) and VMPO (Song et al., 2019). We also include second-order methods such as TRPO (Schulman et al., 2015a) and ACKTR (Wu et al., 2017). Across experiments, for MCPO, we fix βmax = 10, βmin = 0.01 and only tune N . More details on the baselines and tasks are given in Appendix B.1.

heading: 4.1 CLASSICAL CONTROL: HYPERPARAMETER SENSITIVITY TEST
text: In this section, we compare MCPO to other first-order policy gradient methods (KL Adaptive, KL Fixed, PPO, MDPO and VMPO) on 3 classical control tasks: Pendulum, LunarLander and BipedalWalker, which are trained for one, one and five million environment steps, respectively. Here, we are curious to know whether tuning hyperparameters helps the baselines solve these simple tasks, and how their performances fluctuate as the hyperparameters vary. For each model, we choose one hyperparameter that controls the conservativeness of policy update, and we try different values for the signature hyperparameter while keeping the others the same. For example, for PPO, we tune the clip value ; for KL Fixed we tune β coefficient and these possible values are chosen following prior works. For our MCPO, we tune the size of the policy memory N (5, 10 and 40). We do not try bigger policy memory size to keep MCPO running efficiently (see Appendix B.2 for details of baselines, the choice of hyperparameters and running time analysis).
Table 1 reports the results of MCPO and 5 baselines with different hyperparameters. For these simple tasks, tuning the hyperparameters often helps the model achieve at least moderate performance. However, models like KL Adaptive and VMPO cannot reach good performance despite being tuned. PPO shows good results on LunarLander and BipedalWalker, yet underperfoms others on Pendulum. Interestingly, if tuned properly, the vanilla KL Fixed can show competitive results compared to PPO and MDPO in BipedalWalker. Amongst all, our MCPO with suitable N achieves the best performance on all tasks. Remarkably, its performance does not fluctuate much as N changes from 5 to 40, often obtaining good and best results. On the contrary, other methods observe clear drop in performance if the hyperparameters are set incorrectly (see Appendix B.2 for full learning curves).

heading: 4.2 NAVIGATION TASKS: SAMPLE EFFICIENCY TEST
text: Here, we validate our method on sparse reward environments using MiniGrid library (ChevalierBoisvert et al., 2018). In particular, we test MCPO and other baselines (same as above) on Unlock and UnlockPickup tasks. In these tasks, the agent navigates through rooms and picks up objects to complete the episode. The agent only receives reward +1 if it can complete the episode successfully. For sample efficiency test, we train all models on Unlock (find key and open the door) and UnlockPickup (find key, open the door and pickup an object), for only 100,000 and 1 million environment steps, respectively. The models use the best conservative hyperparameters found in the previous task (more in Appendix B.3).
Fig. 1 shows the learning curves of examined models on these two tasks. For Unlock task, except for MCPO and VMPO, 100,000 steps seem not enough for the models to learn useful policies. When trained with 1 million steps on UnlockPickup, the baselines can find better policies, yet still underpefrom MCPO. Here VMPO shows faster learning progress than MCPO at the beginning, however it fails to converge to the best solution. Our MCPO is the best performer, consistently ending up with average return of 0.9 (90% of episodes finished successfully).
To illustrate how the virtual policy supports building trust regions to boost MCPO’s performance, we analyze the relationships amongst the old (θ), the virtual policy (ψ) and the policies stored in M (θj) throughout Unlock training. Fig. 2 (a) plots the location of these policies over a truncated period of training (from update step 5160 to 7070). Due to conditional writing rule, the steps where policies are added toM can be uneven (first row-red lines), often distributed right after the locations of the old policy (second row-green lines). We query at 10-th step behind the old policy (fourth rowcyan lines) to find which policy in M has the highest attention (third row-yellow lines, linked by blue arrows). As shown in Fig. 2 (a) (second and third row), the attended policy, which mostly
resembles ψ, can be further or closer to the query step than the old policy depending on the training stage. Since we let the attention network learn to attend to the policy that maximizes the advantage of current mini-batch data, the attended one is not necessarily the same as the old policy.
The choice of the chosen virtual policy being better than the old policy is shown in Fig. 2 (b) where we collect several checkpoints of virtual and old policies across training and evaluate each of them on 10 testing episodes. Here using ψ to form the second KL constraint is beneficial as the new policy is generally pulled toward a better policy during training. That contributes to the excellent performance of MCPO compared to other single trust-region baselines, especially KL Fixed and Adaptive, which are very close to MCPO in term of objective function style.
4.3 MUJOCO CONTINUOUS CONTROL: EFFECTIVENESS OF LEARNED ψ
Next, we examine MCPO and some trust-region methods from the literature that are known to have good performance on continuous control problems: TRPO, PPO and MDPO. To understand the role of the attention network in MCPO, we design a variant of MCPO: Mean ψ, which simply constructs ψ by taking average over policy parameters in M. We pick 6 hard Mujoco tasks and train each model for 10 million environment steps. For each baseline, we again only tune the conservative hyperparameters and report the best configurations in Table 2 (see Appendix B.4 for full results).
The results show that MCPO is the best performer on 5 out of 6 tasks, where clear outperformance gaps can be found in HalfCheetah, Ant, Humanoid and HumanoidStandup. We note that this is only achieved as MCPO uses N = 40, which indicates that bigger policy memory (more conservativeness) is beneficial in this case. The variant Mean ψ demonstrates reasonable performance for the first 4 tasks, yet almost fails to learn on the last two, which means using a mean virtual policy is unsuitable in these tasks.
To understand the effectiveness of the attention network, we visualize the attention pattern of MCPO on the last two tasks and on Hopper-a task that Mean ψ performs well. Fig. 2 (c) illustrates that for the first two harder tasks, MCPO gradually learns to favour older policies inM (j∗ > 35), which puts more restriction on the policy change as the model converges. This strategy seems critical for those tasks as the difference in average return between learned ψ and Mean ψ is huge in these cases. On the other hand, on Hopper, the top attended slots are just above the middle policies inM (j∗ ∼ 25), which means this task prefers an average restriction.

heading: 4.4 ATARI GAMES: SCALING TO HIGHER DIMENSIONS
text: As showcasing the robustness of our method to high-dimensional inputs, we execute an experiment on a subset of Atari games wherein the states are screen images and the policy and value function approximator uses deep convolutional neural networks. We choose 6 typical games (Mnih et al., 2013) and benchmark MCPO against PPO, ACKTR and VMPO, training all models for only 10 million environment steps. In this experiment, MCPO uses N = 10 and other baselines’ hyperparameters are selected based on the original papers (see Appendix B.5).
Fig. 3 visualizes the learning curves of the models. Regardless of our regular tuning, VMPO performs poorly, indicating that this method is unsuitable or needs extensive tuning to work for lowsample training regime. ACKTR, works extremely well on certain games (Breakout and Seaquest), but shows mediocre results on others (Enduro, BeamRider), overall underperfoming MCPO. PPO is always similar or inferior to MCPO on this testbed. Our MCPO always demonstrates competitive results, outperforming all other models in 4 games, especially on Enduro and Gopher, and showing comparable results with that of the best model in the other 2 games.

heading: 4.5 ABLATION STUDY
text: Finally, we verify MCPO’s 3 components: virtual policy (Eq. 1), switching-β (Eq. 2) and conditional writing rule (Eq. 3). We also confirm the role of choosing the right memory size N and learning to attend to the virtual policy ψ. As such, we pick BipedalWalkerHardcore from OpenAI Gym and train MCPO with different configurations for 50M steps. First, we tune N (5,10 and 40) using the normal MCPO with all components on and find out thatN = 10 is the best, reaching about 169 return score. Keeping N = 10, for each component, we ablate or replace our component with an alternative and report the findings as follows.
Virtual policy To show the benefit of pushing the new policy toward the virtual policy, we implement a variant of MCPO that does not use ψ’s KL term in Eq. 1 (a.k.a. αt = 0). This variant underperfoms the normal MCPO by a margin of 100 return. Switching-β The results show that compared to the annealed β strategy adopted from MDPO, our switching-β achieves significantly better results with about 50 return score higher. Conditional writing We compare our proposal with the vanilla approach that adds a new policy toM at every update step (frequent writing) and another
version that writes toM every interval of 10 update steps (uniform writing). Both frequent and uniform writing show slow learning progress, and ends up with negative rewards. Perhaps, frequently adding policies toM makes the memory content similar, hastening the removal of older, yet maybe valuable policies. Uniform writing is better, yet it can still add similar policies toM and requires additional effort for tuning the writing interval. Learned ψ To benchmark, we try alternatives: (1) using Mean ψ and (2) only using half of the features in vcontext to generate ψ (Eq. 4). The results confirm that the Mean ψ is not a strong baseline for this task, only reaping moderate rewards. Using less features for the context causes information loss, hinder generations of useful ψ, and thus, underperforms the full-feature version by a margin of 50 return. For completeness, we also compare our methods to heavily tuned baselines and confirm that the normal MCPO (N = 10) is the best performer. All the learning curves and details can be found in Appendix B.6.

heading: 5 RELATED WORKS
text: A framework for model-free reinforcement learning with policy gradient is approximate policy iteration (API), which alternates between estimating the advantage of the current policy, and updating the current policy’s parameters to obtain a new policy by maximizing the expected advantage (Bertsekas & Tsitsiklis, 1995; Sutton et al., 2000). Theoretical studies have shown that constraining policy updates is critical for API (Kakade & Langford, 2002; Schulman et al., 2015a; Shani et al., 2020; Vieillard et al., 2020b). An early attempt to improve API is Conservative Policy Iteration (CPI), which sets the new policy as a stochastic mixture of previous greedy policies (Kakade & Langford, 2002). The mixture idea of CPI inspires other methods which explore different ways to estimate the greedy policy (Pirotta et al., 2013) or employs neural networks as function approximators (Vieillard et al., 2020a). Our paper differs from these works in three aspects: (1) we do not directly set the new policy to the mixture, rather, we use a mixture of previously found policies (the virtual policy) to define the trust region constraining the new policy via KL regularization; (2) our mixture can consist of more than 2 modes, and thus using multiple mixture weights (attention weights); (3) we use the attention network to learn these weights based on the training context.
Also motivated by Kakade & Langford (2002), TRPO extends the theory to general stochastic policies, rather than just mixture polices, ensuring monotonic improvement by combining maximizing the approximate expected advantage with minimizing the KL divergence between two consecutive policies (Schulman et al., 2015a). Arguing that optimizing this way is too conservative and hard to tune, the authors reformulate the objective as a constrained optimization problem to solve it with conjugate gradient and line search. To simplify the implementation of TRPO, Schulman et al. (2017) introduces first-order optimization methods and code-level improvement, which results in PPO–an API method that optimizes a clipped surrogate objective using minibatch updates.
Another line of works views constrained policy improvement as Expectation-Maximization algorithm where minimizing KL-term corresponds to the Expectation step, which can be off-policy (Abdolmaleki et al., 2018) or on-policy (Song et al., 2019). From mirror descent perspective, several works also use KL divergence to regularize policy updates (Yang et al., 2019; Tomar et al., 2020; Shani et al., 2020). A recent analysis also points out the advantages of using KL term as a regularizer over a hard constraint (Lazić et al., 2021). Some other works improve the standard trust-region with adaptive clip range (Wang et al., 2019) or off-policy data (Fakoor et al., 2020). Our approach shares similarities with them where we also jointly optimize the approximate expected advantage and KL constraint terms for multiple epochs of minibatch updates. However, we propose a novel dynamic virtual policy to construct the second trust region as a supplement to the traditional trust region defined by the old or previous policy.

heading: 6 DISCUSSION
text: We have presented Memory-Constrained Policy Optimization, a new method to regularize each policy update with two-trust regions with respect to one single old policy and another virtual policy representing history of past policies. The new policy is encouraged to stay closer to the region surrounding the policy that performs better. The virtual policy is determined online through a learned attention to a memory of past policies. MCPO is applicable in various problems and settings, less sensitive to hyperparameter changes, and showing better performance in many environments.

heading: APPENDIX

heading: A METHOD DETAILS

heading: A.1 THE ATTENTION NETWORK
text: The attention network is implemented as a feedforward neural network with one hidden layer:
• Input layer: 12 units • Hidden layer: N units coupled with a dropout layer p = 0.5 • Output layer: N units, softmax activation function
N is the capacity of policy memory. The 12 features of the input vcontext is listed in Table 3.

heading: A.2 THE ADVANTAGE FUNCTION
text: In this paper, we use GAE (Schulman et al., 2015b) as the advantage function for all models and experiments
Ât = 1
Nactor Nactor∑ i T−t−1∑ k=0 (γλ) k ( rit+k + γV ( sit+k+1 ) − V ( sit+k )) where γ is the discounted factor and Nactor is the number of actors. The term rit+k + γV ( sit+k+1
) is also known as Vtarget in computing the value loss. Note that Algo. 1 illustrates the procedure for 1 actor. In practice, we use Nactor depending on the tasks.

heading: A.3 THE OBJECTIVE FUNCTION
text: Following Schulman et al. (2017), our objective function also includes value loss and entropy terms. This is applied to all of the baselines. For example, the complete objective function for MCPO reads
L = LMCPO − c1Êt (Vθ (st)− Vtarget (st))2 + c2Êt [− log (πψold (·|st))] where c1 and c2 are value and entropy coefficient hyperparameters, respectively. Vθ is the value network, also parameterized with θ.

heading: B EXPERIMENTAL DETAILS

heading: B.1 BASELINES AND TASKS
text: All baselines in this paper share the same setting of policy and value networks. Except for TRPO, all other baselines use minibatch training. The only difference is the objective function, which revolves around KL and advantage terms. We train all models with Adam optimizer. We summarize the policy and value network architecture in Table 4.
The baselines ACKTR, PPO1, TRPO2 use available public code. They are Pytorch reimplementation of OpenAI’s stable baselines, which can reproduce the original performance relatively well. For MDPO, we refer to the authors’ source code3 to reimplement the method. For VMPO, we refer to this open source code4 to reimplement the method. We implement KL Fixed and KL Adaptive, using objective function defined in Sec. 2.
We use environments from Open AI gyms 5, which are public and using The MIT License. Mujoco environments use Mujoco software6 (our license is academic lab). Table 5 lists all the environments.
1https://github.com/ikostrikov/pytorch-a2c-ppo-acktr-gail 2https://github.com/ikostrikov/pytorch-trpo 3https://github.com/manantomar/Mirror-Descent-Policy-Optimization 4https://github.com/YYCAAA/V-MPO_Lunarlander 5https://gym.openai.com/envs/ 6https://www.roboti.us/license.html

heading: B.2 DETAILS ON CLASSICAL CONTROL
text: For these tasks, all models share hyperparameters listed in Table 6. Besides, each method has its own set of additional hyperparameters. For example, PPO, KL Fixed and KL Adaptive have , β and dtarg, respectively. These hyperparameters directly control the conservativeness of the policy update for each method. For MDPO, β is automatically reduced overtime through an annealing process from 1 to 0 and thus should not be considered as a hyperparameter. However, we can still control the conservativeness if β is annealed from a different value β0 rather 1. We realize that tuning β0 helped MDPO (Table 1). We quickly tried with several values β0 ranging from 0.01 to 10 on Pendulum, and realize that only β0 ∈ {0.5, 1, 2} gave reasonable results. Thus, we only tuned MDPO with these β0 in other tasks. For VMPO there are many other hyperparameters such as η0, α0, η and α. Due to limited compute, we do not tune all of them. Rather, we only tune α0-the initial value of the Lagrange multiplier that scale the KL term in the objective function. We refer to the paper’s and the code repository’s default values of α0 to determine possible values α0 ∈ {0.1, 1, 5}. For our MCPO, we can tune several hyperparameters such as N , βmin, and βmax. However, for simplicity, we only tune N ∈ {5, 10, 40} and fix βmin = 0.01 and βmax = 10. On our machines using 1 GPU Tesla V100-SXM2, we measure the running time of MCPO with different N compared to PPO on Pendulum task, which is reported in Table 7. As N increases, the running speed of MCPO decreases. For this reason, we do not test with N > 40. However, we realize that with N = 5 or N = 10, MCPO only runs slightly slower than PPO. We also realize that the speed gap is even reduced when we increase the number of actorsNactor as in other experiments. In terms of memory usage, maintaining a policy memory will definitely cost more. However, as our policy, value and attention networks are very simple. The maximum storage even for N = 40 is less than 5GB.
In addition to the configurations reported in Table 1, for KL Fixed and PPO, we also tested with extreme values β = 10 and ∈ {0.5, 0.8}. Figs. 6, 7 and 8 visualize the learning curves of all configurations for all models.

heading: B.3 DETAILS ON MINIGRID NAVIGATION
text: Based on the results from the above tasks, we pick the best signature hyperparameters for the models to use in this task as in Table 8. In particular, for each model, we rank the hyperparameters per task (higher rank is better), and choose the one that has the maximum total rank. For hyperparameters
that share the same total rank, we prefer the middle value. The other hyperparameters for this task is listed in Table 6.

heading: B.4 DETAILS ON MUJOCO
text: For shared hyperparameters, we use the values suggested in the PPO’s paper, except for the number of actors, which we increase to 16 for faster training as our models are trained for 10M environment steps (see Table 9).
For the signature hyperparameter of each method, we select some of the reasonable values. For PPO, the authors already examined with ∈ {0.1, 0.2, 0.3} on the same task and found 0.2 the best. This is somehow backed up in our previous experiments where we did not see major difference in performance between these values. Hence, seeking for other rather than the optimal = 0.2, we ran our PPO implementation with ∈ {0.2, 0.5, 0.8}. For TRPO, the authors only used the KL radius threshold δ = 0.01, which may be already the optimal hyperparameter. Hence, we only tried δ ∈ {0.005, 0.01}. The results showed that δ = 0.005 always performed worse. For MCPO and Mean ψ, we only ran with extreme N ∈ {5, 40}. For MDPO, we still tested with β0 ∈ {0.5, 1, 2}. Full learning curves with different hyperparameter are reported in Fig. 9. Learning curves including TRGPPO7 are reported in Fig. 10

heading: B.5 DETAILS ON ATARI
text: For shared hyperparameters, we use the values suggested in the PPO’s paper, except for the number of actors, which we increase to 32 for faster training (see Table 9). For the signature hyperparameter of the baselines, we used the recommended value in the original papers. For MCPO, we use N = 10 to balance between running time and performance. Table 10 shows the values of these hyperparameters.
We also report the average normalized human score (mean and median) of the models over 6 games in Table 11. As seen, MCPO is significantly better than other baselines in terms of both mean and median normalized human score. We also report full learning curves of models and normalized human score including TRGPPO in 9 games in Fig. 4 and Table 12, respectively.
7We use the authors’ source code https://github.com/wangyuhuix/TRGPPO using default configuration. Training setting is adjusted to follow the common setting as for other baselines (see Table 9).
To verify whether MCPO can maintain its performance over longer training, we examine Atari training for 40 million frames. As shown in Fig. 5, MCPO is still the best performer in this training regime.

heading: B.6 DETAILS ON ABLATION STUDY
text: In this section, we give more details on the ablated baselines.
ψ = |M|∑ j θj (7)
• Half feature We only use features from 1 to 6 listed in Table 3.
The other baselines including KL Adaptive, KL Fixed, MDPO, PPO, and VMPO are the same as in B.2. The full learning curves of all models with different hyperparameters are plotted in Fig. 11.

heading: C THEORETICAL ANALYSIS OF MCPO
text: In this section, we explain the design of our objective function L1 and L2. Similar to Schulman et al. (2015a), we can construct a theoretically guaranteed version of our practical objective functions that ensures monotonic policy improvement.
First, we explain the design of L1 by recasting L1 as
L1θold (θ) = Lθold (θ)
− C1DmaxKL (θold, θ) − C2DmaxKL (ψ, θ)
where Lθold (θ) = η (πθold) + ∑ s ρπθold (s) ∑ a πθ (a|s)Aπθold (s, a)–the local approximation to the expected discounted reward η (θ), DmaxKL (a, b) = maxsKL (πa (·|s) , πb (·|s)), C1 = 4maxs,a|Aπ(s,a)|γ
(1−γ)2 and C2 > 0.
As the KL is non-negative, L1θold (θ) ≤ Lθold (θ) − C1DmaxKL (θold, θ). According to Schulman et al. (2015a), the RHS is a lower bound on η (θ), so L1 is also a lower bound on η (θ) and thus, it is reasonable to maximize the practical L1, which is an approximation of L1θold .
Next, we show that by optimizing both L1 and L2, we can interpret our algorithm as a monotonic policy improvement procedure. As such, we need to reformulate L2 as
L2θold (ψ) = Lθold (ψ)− C1DmaxKL (θold, ψ)
Note that compared to the practical L2 (as defined in the main paper on page 5), we have introduced here an additional KL term, which means we need to find ψ that is close to θold and maximizes the approximate advantage Lθold (ψ). As we maximize L2θold (ψ), the maximizer ψ satisfies
L2θold (ψ) ≥ L2θold (θold) = Lθold (θold)
We also have
η (θ) ≥ L1θold (θ) (8) η (θold) = Lθold (θold) ≤ L2θold (ψ)
= Lθold (ψ)− C1DmaxKL (θold, ψ) = L1θold (ψ) (9)
Subtracting both sides of Eq. 9 from Eq. 8 yields
η (θ)− η (θold) ≥ L1θold (θ)− L1θold (ψ) Thus by maximizing L1θold (θ), we guarantee that the true objective η (θ) is non-decreasing.
Although the theory suggests that the practical L2 could be L∗2 = Êt [Rt (ψ (ϕ))− C1KL [πθold (·|st) , πψ (·|st)]], it would require additional tuning of C1. More importantly, optimizing an objective in form of L∗2 needs a very small step size, and could converge slowly. Hence, we simply discard the KL term and only optimize L2 = Êt [Rt (ψ (ϕ))] instead. Empirical results show that using this simplification, MCPO’s learning curves still generally improve monotonically over training time.

Review summaries:
This paper proposes a new approach to regularize on-policy methods utilizing two soft trust region terms. The first term encourages the new policy to stay close to old policy like PPO and the second term enforces the new policy to stay close to the combination of past policies called virtual policy. The virtual policy is built by a convex combination of past policies in the memory through attention weights. The motivation to use attention is to ensure the virtual policy has good performance on current data. To evaluate their method, this paper uses 3 control tasks (i.e. Pendulum, LunarLander and Bipedal- Walker), MiniGrid library for sparse reward environments evaluation, 6 Mujoco tasks, and 6 Atari games.

In this work, the authors propose the use a trust-region method in the vein of Proximal Policy Optimization (PPO). In contrast to previous work, the author propose to use two trust regions instead of a single one. Instead of constraining the policy to stay near to the previous policy, the author's proposed algorithm includes an extra virtual policy constructed from a memory buffer of past policies.