CONTINUOUS CONTROL
Year: 2019

Abstract:
Some of the most successful applications of deep reinforcement learning to challenging domains in discrete and continuous control have used policy gradient methods in the on-policy setting. However, policy gradients can suffer from large variance that may limit performance, and in practice require carefully tuned entropy regularization to prevent policy collapse. As an alternative to policy gradient algorithms, we introduce V-MPO, an on-policy adaptation of Maximum a Posteriori Policy Optimization (MPO) that performs policy iteration based on a learned statevalue function. We show that V-MPO surpasses previously reported scores for both the Atari-57 and DMLab-30 benchmark suites in the multi-task setting, and does so reliably without importance weighting, entropy regularization, or population-based tuning of hyperparameters. On individual DMLab and Atari levels, the proposed algorithm can achieve scores that are substantially higher than has previously been reported. V-MPO is also applicable to problems with high-dimensional, continuous action spaces, which we demonstrate in the context of learning to control simulated humanoids with 22 degrees of freedom from full state observations and 56 degrees of freedom from pixel observations, as well as example OpenAI Gym tasks where V-MPO achieves substantially higher asymptotic scores than previously reported.

heading: 1 INTRODUCTION
text: Deep reinforcement learning (RL) with neural network function approximators has achieved superhuman performance in several challenging domains (Mnih et al., 2015; Silver et al., 2016; 2018). Some of the most successful recent applications of deep RL to difficult environments such as Dota 2 (OpenAI, 2018a), Capture the Flag (Jaderberg et al., 2019), Starcraft II (Vinyals et al., 2019), and dexterous object manipulation (OpenAI, 2018b) have used policy gradient-based methods such as Proximal Policy Optimization (PPO) (Schulman et al., 2017) and the Importance-Weighted Actor-Learner Architecture (IMPALA) (Espeholt et al., 2018), both in the approximately on-policy setting.
Policy gradients, however, can suffer from large variance that may limit performance, especially for high-dimensional action spaces (Wu et al., 2018). In practice, moreover, policy gradient methods typically employ carefully tuned entropy regularization in order to prevent policy collapse. As an alternative to policy gradient-based algorithms, in this work we introduce an approximate policy iteration algorithm that adapts Maximum a Posteriori Policy Optimization (MPO) (Abdolmaleki et al., 2018a;b) to the on-policy setting. The modified algorithm, V-MPO, relies on a learned state-value function V (s) instead of the state-action value function used in MPO. Like MPO, rather than directly updating the parameters in the direction of the policy gradient, V-MPO first constructs a target distribution for the policy update subject to a sample-based KL constraint, then calculates the gradient that partially moves the parameters toward that target, again subject to a KL constraint.
∗Equal contribution
As we are particularly interested in scalable RL algorithms that can be applied to multi-task settings where a single agent must perform a wide variety of tasks, we show for the case of discrete actions that the proposed algorithm surpasses previously reported performance in the multi-task setting for both the Atari-57 (Bellemare et al., 2012) and DMLab-30 (Beattie et al., 2016) benchmark suites, and does so reliably without population-based tuning of hyperparameters (Jaderberg et al., 2017a). For a few individual levels in DMLab and Atari we also show that V-MPO can achieve scores that are substantially higher than has previously been reported in the single-task setting, especially in the challenging Ms. Pacman.
V-MPO is also applicable to problems with high-dimensional, continuous action spaces. We demonstrate this in the context of learning to control both a 22-dimensional simulated humanoid from full state observations—where V-MPO reliably achieves higher asymptotic performance than previous algorithms—and a 56-dimensional simulated humanoid from pixel observations (Tassa et al., 2018; Merel et al., 2019). In addition, for several OpenAI Gym tasks (Brockman et al., 2016) we show that V-MPO achieves higher asymptotic performance than has previously been reported.

heading: 2 BACKGROUND AND SETTING
text: We consider the discounted RL setting, where we seek to optimize a policy π for a Markov Decision Process described by states s, actions a, initial state distribution ρenv0 (s0), transition probabilities Penv(st+1|st, at), reward function r(st, at), and discount factor γ ∈ (0, 1). In deep RL, the policy πθ(at|st), which specifies the probability that the agent takes action at in state st at time t, is described by a neural network with parameters θ. We consider problems where both the states s and actions a may be discrete or continuous. Two functions play a central role in RL: the state-value function V π(st) = Eat,st+1,at+1,... [∑∞ k=0 γ kr(st+k, at+k) ]
and the state-action value function Qπ(st, at) = Est+1,at+1,... [∑∞ k=0 γ kr(st+k, at+k) ] = r(st, at) + γEst+1 [ V π(st+1) ] , where s0 ∼ ρenv0 (s0), at ∼ π(at|st), and st+1 ∼ Penv(st+1|st, at). In the usual formulation of the RL problem, the goal is to find a policy π that maximizes the expected return given by J(π) = Es0,a0,s1,a1,... [∑∞ t=0 γ tr(st, at) ] . In policy gradient algorithms (Williams, 1992; Sutton et al., 2000; Mnih et al., 2016), for example, this objective is directly optimized by estimating the gradient of the expected return. An alternative approach to finding optimal policies derives from research that treats RL as a problem in probabilistic inference, including Maximum a Posteriori Policy Optimization (MPO) (Levine, 2018; Abdolmaleki et al., 2018a;b). Here our objective is subtly different, namely, given a suitable criterion for what are good actions to take in a certain state, how do we find a policy that achieves this goal?
As was the case for the original MPO algorithm, the following derivation is valid for any such criterion. However, the policy improvement theorem (Sutton & Barto, 1998) tells us that a policy update performed by exact policy iteration, π(s) = arg maxa[Qπ(s, a)− V π(s)], can improve the policy if there is at least one state-action pair with a positive advantage and nonzero probability of visiting the state. Motivated by this classic result, in this work we specifically choose an exponential function of the advantages Aπ(s, a) = Qπ(s, a)− V π(s). Notation. In the following we use ∑ s,a to indicate both discrete and continuous sums (i.e., integrals)
over states s and actions a depending on the setting. A sum with indices only, such as ∑ s,a, denotes
a sum over all possible states and actions, while ∑ s,a∼D, for example, denotes a sum over sample states and actions from a batch of trajectories (the “dataset”) D.

heading: 3 RELATED WORK
text: V-MPO shares many similarities, and thus relevant related work, with the original MPO algorithm (Abdolmaleki et al., 2018a;b). In particular, the general idea of using KL constraints to limit the size of policy updates is present in both Trust Region Policy Optimization (TRPO; Schulman et al., 2015) and Proximal Policy Optimization (PPO) (Schulman et al., 2017); we note, however, that this corresponds to the E-step constraint in V-MPO.
It is worth noting here the following main differences with MPO, which is conceptually quite similar to V-MPO. MPO is primarily designed to be a sample-efficient off-policy algorithm in which the
E-step constructs a conditional target distribution q(a|s), which requires a state-action value function Q(s, a) that can evaluate multiple sampled actions for a given state. In contrast, V-MPO is primarily (though not exclusively) designed to be an on-policy algorithm in which the E-step constructs a joint distribution ψ(s, a), and in the absence of a learned Q-function only one action per state is used. In this regard V-MPO can also be compared to Fitted Q-iteration by Advantage Weighted Regression (Neumann & Peters, 2009), which learns a Q-function but uses only one action per state.
V-MPO can also be related to Relative Entropy Policy Search (REPS) (Peters et al., 2008). Two distinguishing features of V-MPO from REPS are the introduction of the M-step KL constraint and the use of top-k advantages. Moreover, in REPS the value function is a linear function of a learned feature representation whose parameters are trained by matching the feature distributions under the policy’s stationary state distribution. In V-MPO, the nonlinear neural network value function is instead learned directly from n-step returns. Interestingly, previous attempts to use REPS with neural network function approximators reported very poor performance, being particularly prone to local optima (Duan et al., 2016). In contrast, we find that the principles of EM-style policy optimization, when combined with this learned value function and appropriate constraints, can reliably train powerful neural networks, including transformers, for RL tasks.
Like V-MPO, Supervised Policy Update (SPU) (Vuong et al., 2019) seeks to exactly solve an optimization problem and fit the parametric policy to this solution. As we argue in Appendix D, however, SPU uses this nonparametric distribution quite differently from V-MPO; as a result, the final algorithm is closer to a policy gradient algorithm such as PPO.

heading: 4 METHOD
text: V-MPO is an approximate policy iteration (Sutton & Barto, 1998) algorithm with a specific prescription for the policy improvement step. In general, policy iteration uses the fact that the true state-value function V π corresponding to policy π can be used to obtain an improved policy π′. Thus we can
1. Generate trajectories τ from an old policy πθold(a|s) whose parameters θold are fixed. To control the amount of data generated by a particular policy, we use a target network which is fixed for Ttarget learning steps (Fig. 1a).
2. Evaluate the policy πθold(a|s) by learning the value function V πθold (s) from empirical returns and estimating the corresponding advantages Aπθold (s, a) for the actions that were taken (Section 4.1).
3. Based onAπθold (s, a), estimate an improved policy πθ(a|s) which we call the “online” policy to distinguish it from the fixed target network (Section 4.2).
The first two steps are standard, and describing V-MPO’s approach to step 3 is the essential contribution of this work. At a high level, our strategy is to first construct a nonparametric target distribution for the policy update, then partially move the parametric policy towards this distribution subject to a KL constraint. We first review policy evaluation (step 2) in Section 4.1, then derive the V-MPO policy improvement (step 3) in Section 4.2. Ultimately, we use gradient descent to optimize a single, relatively simple loss, which is given in Eq. 10 following the derivation. A summary of the full algorithm is also presented in Algorithm 1.

heading: 4.1 POLICY EVALUATION
text: In the present setting, policy evaluation means learning an approximate state-value function V π(s) given a policy π(a|s), which we keep fixed for Ttarget learning steps (i.e., batches of trajectories). We note that the value function corresponding to the target policy is instantiated in the “online” network receiving gradient updates; bootstrapping uses the online value function, as it is the best available estimate of the value function for the target policy. Thus in this section π refers to πθold , while the value function update is performed on the current φ, which may share parameters with the current θ.
We fit a parametric value function V πφ (s) with parameters φ by minimizing the squared loss
LV (φ) = 1 2|D| ∑ st∼D ( V πφ (st)−G (n) t )2 , (1)
where G(n)t is the standard n-step target for the value function at state st at time t (Sutton & Barto, 1998). This return uses the actual rewards in the trajectory and bootstraps from the value function for the rest: for each ` = t, . . . , t + n − 1 in an unroll, G(n)` = ∑t+n−1 k=` γ k−`rk + γ t+n−`V πφ (st+n). The advantages, which are the key quantity of interest for the policy improvement step in V-MPO, are then given by Aπ(st, at) = G (n) t − V πφ (st) for each st, at in the batch of trajectories.
PopArt normalization. As we are interested in the multi-task setting where a single agent must learn a large number of tasks with differing reward scales, we used PopArt (van Hasselt et al., 2016; Hessel et al., 2018) for the value function, even when training on a single task. We observed benefits in using PopArt even in the single-task setting, partly due to the fact that we do not tune the relative weighting of the policy evaluation and policy improvement losses despite sharing most parameters for the policy and value networks. Specifically, the value function outputs a separate value for each task in normalized space, which is converted to actual returns by a shift and scaling operation, the statistics of which are learned during training. We used a scale lower bound of 10−2, scale upper bound of 106, and learning rate of 10−4 for the statistics. The lower bound guards against numerical issues when rewards are extremely sparse.
Importance-weighting for off-policy data. It is possible to importance-weight the samples using V-trace to correct for off-policy data (Espeholt et al., 2018), for example when data is taken from a replay buffer. For simplicity, however, no importance-weighting was used for the experiments presented in this work, which were mostly on-policy.

heading: 4.2 POLICY IMPROVEMENT IN V-MPO
text: In this section we show how, given the advantage function Aπθold (s, a) for the state-action distribution pθold(s, a) = πθold(a|s)p(s) induced by the old policy πθold(a|s), we can estimate an improved policy πθ(a|s). More formally, let I denote the binary event that the new policy is an improvement (in a sense to be defined below) over the previous policy: I = 1 if the policy is successfully improved and 0 otherwise. Then we would like to find the mode of the posterior distribution over parameters θ conditioned on this event, i.e., we seek the maximum a posteriori (MAP) estimate
θ∗ = arg max θ
[ log pθ(I = 1) + log p(θ) ] , (2)
where we have written p(I = 1|θ) as pθ(I = 1) to emphasize the parametric nature of the dependence on θ. We use the well-known identity log p(X) = Eψ(Z) [ log p(X,Z)ψ(Z) ] + DKL ( ψ(Z)‖p(Z|X) ) for any latent distribution ψ(Z), whereDKL(ψ(Z)‖p(Z|X)) is the Kullback-Leibler divergence between ψ(Z) and p(Z|X) with respect to Z, and the first term is a lower bound because the KL divergence is always non-negative. Then considering s, a as latent variables,
log pθ(I = 1) = ∑ s,a ψ(s, a) log pθ(I = 1, s, a) ψ(s, a) +DKL ( ψ(s, a)‖pθ(s, a|I = 1) ) . (3)
Policy improvement in V-MPO consists of the following two steps which have direct correspondences to the expectation maximization (EM) algorithm (Neal & Hinton, 1998): In the expectation (E) step, we choose the variational distribution ψ(s, a) such that the lower bound on log pθ(I = 1) is as tight as possible, by minimizing the KL term. In the maximization (M) step we then find parameters θ that maximize the corresponding lower bound, together with the prior term in Eq. 2.

heading: 4.2.1 E-STEP
text: In the E-step, our goal is to choose the variational distribution ψ(s, a) such that the lower bound on log pθ(I = 1) is as tight as possible, which is the case when the KL term in Eq. 3 is zero. Given the old parameters θold, this simply leads to ψ(s, a) = pθold(s, a|I = 1), or
ψ(s, a) = pθold(s, a)pθold(I = 1|s, a)
pθold(I = 1) , pθold(I = 1) = ∑ s,a pθold(s, a)pθold(I = 1|s, a). (4)
Intuitively, this solution weights the probability of each state-action pair with its relative improvement probability pθold(I = 1|s, a). We now choose a distribution pθold(I = 1|s, a) that leads to our desired outcome. As we prefer actions that lead to a higher advantage in each state, we suppose that this probability is given by
pθold(I = 1|s, a) ∝ exp ( Aπθold (s, a)
η
) (5)
for some temperature η > 0, from which we obtain the equation on the right in Eq. 12. This probability depends on the old parameters θold and not on the new parameters θ. Meanwhile, the value of η allows us to control the diversity of actions that contribute to the weighting, but at the moment is arbitrary. It turns out, however, that we can tune η as part of the optimization, which is desirable since the optimal value of η changes across iterations. The convex loss that achieves this, Eq. 13, is derived in Appendix A by minimizing the KL term in Eq. 3 subject to a hard constraint on ψ(s, a).
Top-k advantages. We found that learning improves substantially if we take only the samples corresponding to the highest 50% of advantages in each batch for the E-step, corresponding to the use of D̃ rather than D in Eqs. 12, 13. Importantly, these must be consistent between the maximum likelihood weights in Eq. 12 and the temperature loss in Eq. 13, since, mathematically, this corresponds to a specific choice of the policy improvement probability in Eq. 5 to only use the top half of the advantages. This is similar to the technique used in the Cross Entropy Method (CEM) (Mannor et al., 2003) and Covariance Matrix Adaptation - Evolutionary Strategy (CMAES) (Hansen et al., 1997; Abdolmaleki et al., 2017), and is a special case of the more general feature that any rank-preserving transformation is allowed under this formalism. For example, in Fig. 8 of the Appendix we show an example of an agent trained with uniform weights given to the top-k samples, instead of optimizing the temperature. Other choices are possible, and in future work we will investigate the suitability of different choices for specific applications.
Importance weighting for off-policy corrections. As for the value function, importance weights can be used in the policy improvement step to correct for off-policy data. While not used for the experiments presented in this work, details for how to carry out this correction are given in Appendix E.

heading: 4.2.2 M-STEP: CONSTRAINED SUPERVISED LEARNING OF THE PARAMETRIC POLICY
text: In the E-step we found the nonparametric variational state-action distribution ψ(s, a), Eq. 4, that gives the tightest lower bound to pθ(I = 1) in Eq. 3. In the M-step we maximize this lower bound
together with the prior term log p(θ) with respect to the parameters θ, which effectively leads to a constrained weighted maximum likelihood problem. Thus the introduction of the nonparametric distribution in Eq. 4 separates the RL procedure from the neural network fitting.
We would like to find new parameters θ that minimize L(θ) = − ∑ s,a ψ(s, a) log pθ(I = 1, s, a) ψ(s, a) − log p(θ). (6)
Note, however, that so far we have worked with the joint state-action distribution ψ(s, a) while we are in fact optimizing for the policy, which is the conditional distribution πθ(a|s). Writing pθ(s, a) = πθ(a|s)p(s) since only the policy is parametrized by θ and dropping terms that are not parametrized by θ, the first term of Eq. 6 is seen to be the weighted maximum likelihood policy loss
Lπ(θ) = − ∑ s,a ψ(s, a) log πθ(a|s). (7)
In the sample-based computation of this loss, we assume that any state-action pairs not in the batch of trajectories have zero weight, leading to the normalization in Eq. 12.
As in the original MPO algorithm, a useful prior is to keep the new policy πθ(a|s) close to the old policy πθold(a|s): log p(θ) ≈ −αEs∼p(s) [ DKL ( πθold(a|s)‖πθ(a|s) )] . While intuitive, we motivate this more formally in Appendix B. It is again more convenient to specify a bound on the KL divergence instead of tuning α directly, so we solve the constrained optimization problem
θ∗ = arg min θ − ∑ s,a ψ(s, a) log πθ(a|s) s.t. E s∼p(s) [ DKL ( πθold(a|s)‖πθ(a|s) )] < α. (8)
Intuitively, the constraint in the E-step expressed by Eq. 18 in Appendix A for tuning the temperature only constrains the nonparametric distribution; it is the constraint in Eq. 8 that directly limits the change in the parametric policy, in particular for states and actions that were not in the batch of samples and which rely on the generalization capabilities of the neural network function approximator.
To make the constrained optimization problem amenable to gradient descent, we use Lagrangian relaxation to write the unconstrained objective as
J (θ, α) = Lπ(θ) + α ( α − E
s∼p(s)
[ DKL ( πθold(a|s)‖πθ(a|s) )]) , (9)
which we can optimize by following a coordinate-descent strategy, alternating between the optimization over θ and α. Since η and α are Lagrange multipliers that must be positive, after each gradient update we project the resulting η and α to a small positive value which we choose to be ηmin = αmin = 10 −8 throughout the results presented below.
KL constraints in both the E-step and M-step are generally well satisfied, especially for the E-step since the temperature optimization is convex. Fig. 7 in the Appendix shows an example of how the KL constraints behave in the Atari Seaquest experiment presented below. We note, in particular, that it is desirable for the bounds to not just be satisfied but saturated.

heading: 4.3 FULL LOSS FUNCTION
text: In this section we provide the full loss function used to implement V-MPO, which is perhaps simpler than is suggested by the derivation. Consider a batch of data D consisting of a number of trajectories, with |D| total state-action samples. Each trajectory consists of an unroll of length n of the form τ = [ (st, at, rt+1), . . . , (st+n−1, at+n−1, rt+n), st+n ] including the bootstrapped state st+n, where rt+1 = r(st, at). The total loss is the sum of a policy evaluation loss and a policy improvement loss,
L(φ, θ, η, α) = LV (φ) + LV-MPO(θ, η, α), (10) where φ are the parameters of the value network, θ the parameters of the policy network, and η and α are Lagrange multipliers. In practice, the policy and value networks share most of their parameters in the form of a shared convolutional network (a ResNet) and recurrent LSTM core, and are optimized together (Fig. 1b) (Mnih et al., 2016). We note, however, that the value network parameters φ are considered fixed for the policy improvement loss, and gradients are not propagated.
The policy evaluation loss for the value function, LV (φ), is the standard regression to n-step returns and is given by Eq. 1 above. The policy improvement loss LV-MPO(θ, η, α) is given by
LV-MPO(θ, η, α) = Lπ(θ) + Lη(η) + Lα(θ, α). (11)
Here the policy loss is the weighted maximum likelihood loss
Lπ(θ) = − ∑ s,a∼D̃ ψ(s, a) log πθ(a|s), ψ(s, a) = exp
(Atarget(s,a) η )∑ s,a∼D̃ exp (Atarget(s,a) η
) , (12) where the advantages Atarget(s, a) for the target network policy πθtarget(a|s) are estimated according to the standard method described above. The tilde over the dataset, D̃, indicates that we take samples corresponding to the top half advantages in the batch of data. The η, or “temperature”, loss is
Lη(η) = η η + η log
[ 1
|D̃| ∑ s,a∼D̃ exp ( Atarget(s, a) η )] . (13)
We perform the alternating optimization over θ and α while keeping a single loss function by alternately applying a “stop-gradient” to the Lagrange multiplier and KL term. Then the KL constraint, which can be viewed as a form of trust-region loss, is given by
Lα(θ, α) = 1 |D| ∑ s∈D [ α ( α − sg [[ DKL ( πθtarget(a|s)‖πθ(a|s) )]]) + sg[[α]]DKL ( πθtarget(a|s)‖πθ(a|s) )] ,
(14)
where sg[[·]] indicates a stop gradient, i.e., that the enclosed term is assumed constant with respect to all variables. Note that here we use the full batch D, not D̃. For continuous action spaces parametrized by Gaussian distributions, we use decoupled KL constraints for the M-step in Eq. 14 as in Abdolmaleki et al. (2018b); the precise form is given in Appendix C.
We used the Adam optimizer (Kingma & Ba, 2015) with default TensorFlow hyperparameters to optimize the total loss in Eq. 10. In particular, the learning rate was fixed at 10−4 for all experiments.
Algorithm 1 V-MPO given Batch size B, unroll length n, Ttarget, KL bounds η , α. initialize Network parameters θonline, φonline, Lagrange multipliers η, α. repeat θtarget ← θonline for i = 1, . . . , Ttarget do
Use policy πθtarget to act in the environment and collect B trajectories τ of length n. Update θonline, φonline, η, α using Adam to minimize the total loss in Eq. 10. η ← max(η, ηmin) α← max(α, αmin)
end for until Fixed number of steps.

heading: 5 EXPERIMENTS
text: Details on the network architecture and hyperparameters used for each task are given in Appendix F.

heading: 5.1 DISCRETE ACTIONS: DMLAB, ATARI
text: DMLab. DMLab-30 (Beattie et al., 2016) is a collection of visually rich, partially observable 3D environments played from the first-person point of view. Like IMPALA, for DMLab we used pixel control as an auxiliary loss for representation learning (Jaderberg et al., 2017b; Hessel et al., 2018). However, we did not employ the optimistic asymmetric reward scaling used by previous IMPALA
experiments to aid exploration on a subset of the DMLab levels, by weighting positive rewards more than negative rewards (Espeholt et al., 2018; Hessel et al., 2018; Kapturowski et al., 2019). Unlike in Hessel et al. (2018) we also did not use population-based training (PBT) (Jaderberg et al., 2017a). Additional details for the settings used in DMLab can be found in Table 5 of the Appendix.
Fig. 2a shows the results for multi-task DMLab-30, comparing the V-MPO learning curves to data obtained from Hessel et al. (2018) for the PopArt IMPALA agent with pixel control. We note that the result for V-MPO at 10B environment frames across all levels matches the result for the Recurrent Replay Distributed DQN (R2D2) agent (Kapturowski et al., 2019) trained on individual levels for 10B environment steps per level. Fig. 3 shows example individual levels in DMLab where V-MPO achieves scores that are substantially higher than has previously been reported, for both R2D2 and IMPALA. The pixel-control IMPALA agents shown here were carefully tuned for DMLab and are similar to the “experts” used in Schmitt et al. (2018); in all cases these results match or exceed previously published results for IMPALA (Espeholt et al., 2018; Kapturowski et al., 2019).
Atari. The Atari Learning Environment (ALE) (Bellemare et al., 2012) is a collection of 57 Atari 2600 games that has served as an important benchmark for recent deep RL methods. We used the standard preprocessing scheme and a maximum episode length of 30 minutes (108,000 frames), see Table 6 in the Appendix. For the multi-task setting we followed Hessel et al. (2018) in setting the discount to zero on loss of life; for the example single tasks we did not employ this trick, since it
can prevent the agent from achieving the highest score possible by sacrificing lives. Similarly, while in the multi-task setting we followed previous work in clipping the maximum reward to 1.0, no such clipping was applied in the single-task setting in order to preserve the original reward structure. Additional details for the settings used in Atari can be found in Table 6 in the Appendix.
Fig. 2b shows the results for multi-task Atari-57, demonstrating that it is possible for a single agent to achieve “superhuman“ median performance on Atari-57 in approximately 4 billion (∼70 million per level) environment frames. Again, while we did not employ PBT in order to demonstrate that individual V-MPO runs can exceed the performance of a population of IMPALA agents, Fig. 6 shows that with population-based tuning of hyperparameters even higher performance is possible.
We also compare the performance of V-MPO on a few individual Atari levels to R2D2 (Kapturowski et al., 2019), which previously achieved some of the highest scores reported for Atari. Again, VMPO can match or exceed previously reported scores while requiring fewer interactions with the environment. In Ms. Pacman, the final performance approaches 300,000 with a 30-minute timeout (and the maximum 1M without). Inspired by the argument in Kapturowski et al. (2019) that in a fully observable environment LSTMs enable the agent to utilize more useful representations than is available in the immediate observation, for the single-task setting we used a Transformer-XL (TrXL) (Dai et al., 2019) to replace the LSTM core. Unlike previous work for single Atari levels, we did not employ any reward clipping (Mnih et al., 2015; Espeholt et al., 2018) or nonlinear value function rescaling (Kapturowski et al., 2019).

heading: 5.2 CONTINUOUS CONTROL
text: To demonstrate V-MPO’s effectiveness in high-dimensional, continuous action spaces, here we present examples of learning to control both a simulated humanoid with 22 degrees of freedom from full state observations and one with 56 degrees of freedom from pixel observations (Tassa et al., 2018; Merel et al., 2019). As shown in Fig. 5a, for the 22-dimensional humanoid V-MPO reliably achieves higher asymptotic returns than has previously been reported, including for Deep Deterministic Policy
Gradients (DDPG) (Lillicrap et al., 2015), Stochastic Value Gradients (SVG) (Heess et al., 2015), and MPO. These algorithms are far more sample-efficient but reach a lower final performance.
In the “gaps” task the 56-dimensional humanoid must run forward to match a target velocity of 4 m/s and jump over the gaps between platforms by learning to actuate joints with position-control (Merel et al., 2019). Previously, only an agent operating in the space of pre-learned motor primitives was able to solve the task from pixel observations (Merel et al., 2018; 2019); here we show that V-MPO can learn a challenging visuomotor task from scratch (Fig. 5b). For this task we also demonstrate the importance of the parametric KL constraint, without which the agent learns poorly.
In Figs. 5c-d we also show that V-MPO achieves the highest asymptotic performance reported for two OpenAI Gym tasks (Brockman et al., 2016). Again, MPO and Stochastic Actor-Critic (Haarnoja et al., 2018) are far more sample-efficient but reach a lower final performance.
These experiments are presented to demonstrate the existence of higher-return solutions than have previously been reported, and an algorithm, V-MPO, that can reliably converge to these solutions. However, in the future we desire algorithms that can do so while using fewer interactions with the environment.

heading: 6 CONCLUSION
text: In this work we have introduced a scalable on-policy deep reinforcement learning algorithm, V-MPO, that is applicable to both discrete and continuous control domains. For the results presented in this work neither importance weighting nor entropy regularization was used; moreover, since the size of neural network parameter updates is limited by KL constraints, we were also able to use the same learning rate for all experiments. This suggests that a scalable, performant RL algorithm may not require some of the tricks that have been developed over the past several years. Interestingly, both the original MPO algorithm for replay-based off-policy learning (Abdolmaleki et al., 2018a;b) and V-MPO for on-policy learning are derived from similar principles, providing evidence for the benefits of this approach as an alternative to popular policy gradient-based methods.

heading: ACKNOWLEDGMENTS
text: We thank Lorenzo Blanco, Trevor Cai, Greg Wayne, Chloe Hillier, and Vicky Langston for their assistance and support.

heading: A DERIVATION OF THE V-MPO TEMPERATURE LOSS
text: In this section we derive the E-step temperature loss in Eq. 22. To this end, we explicitly commit to the more specific improvement criterion in Eq. 5 by plugging into the original objective in Eq. 3. We seek ψ(s, a) that minimizes
J (ψ(s, a)) = DKL ( ψ(s, a)‖pθold(s, a|I = 1) ) (15)
∝ − ∑ s,a ψ(s, a)Aπθold (s, a) + η ∑ s,a ψ(s, a) log ψ(s, a) pθold(s, a) + λ ∑ s,a ψ(s, a) (16)
where λ = η log pθold(I = 1) after multiplying through by η, which up to this point in the derivation is given. We wish to automatically tune η so as to enforce a bound η on the KL term DKL ( ψ(s, a)‖pθold(s, a) ) multiplying it in Eq. 16, in which case the temperature optimization can also be viewed as a nonparametric trust region for the variational distribution with respect to the old distribution. We therefore consider the constrained optimization problem
ψ(s, a) = arg max ψ(s,a) ∑ s,a ψ(s, a)Aπθold (s, a) (17)
s.t. ∑ s,a ψ(s, a) log ψ(s, a) pθold(s, a) < η and ∑ s,a ψ(s, a) = 1. (18)
We can now use Lagrangian relaxation to transform the constrained optimization problem into one that maximizes the unconstrained objective J (ψ(s, a), η, λ) = ∑ s,a ψ(s, a)Aπθold (s, a)+η ( η− ∑ s,a ψ(s, a) log ψ(s, a) pθold(s, a) ) +λ ( 1− ∑ s,a ψ(s, a) ) (19) with η ≥ 0. (Note we are re-using the variables η and λ for the new optimization problem.) Differentiating J with respect to ψ(s, a) and setting equal to zero, we obtain
ψ(s, a) = pθold(s, a) exp
( Aπθold (s, a)
η
) exp ( − 1− λ
η
) . (20)
Normalizing over s, a (using the freedom given by λ) then gives
ψ(s, a) = pθold(s, a) exp
(Aπθold (s,a) η ) ∑ s,a pθold(s, a) exp (Aπθold (s,a) η
) , (21) which reproduces the general solution Eq. 4 for our specific choice of policy improvement in Eq. 5. However, the value of η can now be found by optimizing the corresponding dual function. Plugging Eq. 21 into the unconstrained objective in Eq. 19 gives rise to the η-dependent term
Lη(η) = η η + η log [∑ s,a pθold(s, a) exp ( Aπθold (s, a) η )] . (22)
Replacing the expectation with samples from pθold(s, a) in the batch of trajectories D leads to the loss in Eq. 13.

heading: B M-STEP KL CONSTRAINT
text: Here we give a somewhat more formal motivation for the prior log p(θ). Consider a normal prior N (θ;µ,Σ) with mean µ and covariance Σ. We choose Σ−1 = αF (θold) where α is a scaling parameter and F (θold) is the Fisher information for πθ′(a|s) evaluated at θ′ = θold. Then log p(θ) ≈ −α × 12 (θ − θold)
TF (θold)(θ − θold) + {term independent of θ}, where the first term is precisely the second-order approximation to the KL divergence DKL(θold‖θ). We now follow TRPO (Schulman et al., 2015) in heuristically approximating this as the state-averaged expression, Es∼p(s) [ DKL ( πθold(a|s)‖πθ(a|s) )] . We note that the KL divergence in either direction has the same second-order expansion, so our choice of KL is an empirical one (Abdolmaleki et al., 2018a).

heading: C DECOUPLED KL CONSTRAINTS FOR CONTINUOUS CONTROL
text: As in Abdolmaleki et al. (2018b), for continuous action spaces parametrized by Gaussian distributions we use decoupled KL constraints for the M-step. This uses the fact that the KL divergence between two d-dimensional multivariate normal distributions with means µ1, µ2 and covariances Σ1,Σ2 can be written as
DKL ( N (µ1,Σ1)‖N (µ2,Σ2) ) = 1
2
[ (µ2−µ1)TΣ−11 (µ2−µ1)+Tr(Σ −1 2 Σ1)−d+log
|Σ2| |Σ1|
] , (23)
where | · | is the matrix determinant. Since the first distribution and hence Σ1 in the KL divergence of Eq. 9 depends on the old target network parameters, we see that we can separate the overall KL divergence into a mean component and a covariance component:
DµKL ( πθold‖πθ ) = 1
2 (µθ − µθold)TΣ−1θold(µθ − µθold), (24)
DΣKL ( πθold‖πθ ) = 1
2
[ Tr(Σ−1θ Σθold)− d+ log
|Σθ| |Σθold |
] . (25)
With the replacement DKL ( πθold‖πθ ) → DCKL ( πθold‖πθ ) for C = µ,Σ and corresponding α → αµ, αΣ, we obtain the total loss LV-MPO(θ, η, αµ, αΣ) = Lπ(θ) + Lη(η) + Lαµ(θ, αµ) + LαΣ(θ, αΣ), (26) where Lπ(θ) and Lη(η) are the same as before. Note, however, that unlike in Abdolmaleki et al. (2018a) we do not decouple the policy loss.
We generally set Σ to be much smaller than µ (see Table 7). Intuitively, this allows the policy to learn quickly in action space while preventing premature collapse of the policy, and, conversely, increasing “exploration” without moving in action space.

heading: D RELATION TO SUPERVISED POLICY UPDATE
text: Like V-MPO, Supervised Policy Update (SPU) (Vuong et al., 2019) adopts the strategy of first solving a nonparametric constrained optimization problem exactly, then fitting a neural network to the resulting solution via a supervised loss function. There is, however, an important difference from V-MPO, which we describe here.
In SPU, the KL loss, which is the sole loss in SPU, leads to a parametric optimization problem that is equivalent to the nonparametric optimization problem posed initially. To see this, we observe that the SPU loss seeks parameters (note the direction of the KL divergence)
θ∗ = arg min θ ∑ s dπθk (s)DKL ( πθ(a|s)‖πλ(a|s) ) (27)
= arg min θ ∑ s dπθk (s) ∑ a πθ(a|s) log [ πθ(a|s) πθk(a|s) exp ( Aπθk (s, a)/λ ) /Zλ(s) ] (28)
= arg min θ ∑ s dπθk (s) ∑ a [ πθ(a|s) log πθ(a|s) πθk(a|s) − 1 λ πθ(a|s)Aπθk (s, a) ] + { constant terms }.
(29) Multiplying by λ since it can be treated as a constant up to this point, we then see that this corresponds exactly to the (Lagrangian form) of the problem
θ∗ = arg max θ ∑ s dπθk (s) ∑ a πθ(a|s)Aπθk (s, a) (30)
s.t. ∑ s dπθk (s)DKL ( πθ(a|s)‖πθk(a|s) ) < , (31)
which is the original nonparametric problem posed in Vuong et al. (2019).
E IMPORTANCE-WEIGHTING FOR OFF-POLICY CORRECTIONS
The network that generates the data may lag behind the target network in common distributed, asynchronous implementations (Espeholt et al., 2018). We can compensate for this by multiplying the exponentiated advantages by importance weights ρ(s, a):
ψ(s, a) = ρ(s, a)pθD (s, a) exp
(AπθD (s,a) η ) ∑ s,a ρ(s, a)pθD (s, a) exp (AπθD (s,a) η
) , (32) Lη(η) = η η + η log
[∑ s,a ρ(s, a)pθD (s, a) exp ( AπθD (s, a) η )] , (33)
where θD are the parameters of the behavior policy that generated D and which may be different from θtarget. The clipped importance weights ρ(s, a) are given by
ρ(s, a) = min ( 1, πθold(a|s) πθD (a|s) ) . (34)
As was the case with V-trace for the value function, we did not find it necessary to use importance weighting and all experiments presented in this work did not use them for the sake of simplicity.

heading: F NETWORK ARCHITECTURE AND HYPERPARAMETERS
text: For DMLab the visual observations were 72×96 RGB images, while for Atari the observations were 4 stacked frames of 84×84 grayscale images. The ResNet used to process visual observations is similar to the 3-section ResNet used in Hessel et al. (2018), except the number of channels was multiplied by 4 in each section, so that the number of channels were (64, 128, 128) (Schmitt et al., 2019). For individual DMLab levels we used the same number of channels as Hessel et al. (2018), i.e., (16, 32, 32). Each section consisted of a convolution and 3× 3 max-pooling operation (stride 2), followed by residual blocks of size 2, i.e., a convolution followed by a ReLU nonlinearity, repeated twice, and a skip connection from the input residual block input to the output. The entire stack was passed through one more ReLU nonlinearity. All convolutions had a kernel size of 3 and a stride of 1. For the humanoid control tasks from vision, the number of channels in each section were (16, 32, 32).
Since some of the levels in DMLab require simple language processing, for DMLab the agents contained an additional 256-unit LSTM receiving an embedding of hashed words as input. The output of the language LSTM was then concatenated with the output of the visual processing pathway as well as the previous reward and action, then fed to the main LSTM.
For multi-task DMLab we used a 3-layer LSTM, each with 256 units, and an unroll length of 95 with batch size 128. For the single-task setting we used a 2-layer LSTM. For multi-task Atari and the 56-dimensional humanoid-gaps control task a single 256-unit LSTM was used, while for the 22-dimensional humanoid-run task the core consisted only of a 2-layer MLP with 512 and 256 units (no LSTM). For single-task Atari a Transformer-XL was used in place of the LSTM. Note that we followed Radford et al. (2019) in placing the layer normalization on only the inputs to each sub-block. For Atari the unroll length was 63 with a batch size of 128. For both humanoid control tasks the batch size was 64, but the unroll length was 40 for the 22-dimensional humanoid and 63 for the 56-dimensional humanoid.
In all cases the policy logits (for discrete actions) and Gaussian distribution parameters (for continuous actions) consisted of a 256-unit MLP followed by a linear readout, and similarly for the value function. For discrete actions we initialized the linear policy layer with zero weights and biases to ensure a uniform policy at the start of training.
The initial values for the Lagrange multipliers in the V-MPO loss are given in Table 1
Implementation note. We implemented V-MPO in an actor-learner framework (Espeholt et al., 2018) that utilizes TF-Replicator (Buchlovsky et al., 2019) for distributed training on TPU 8-core and 16-core configurations (Google, 2018). One practical consequence of this is that a full batch of data D was in fact split into 8 or 16 minibatches, one per core/replica, and the overall result obtained by averaging the computations performed for each minibatch. More specifically, the determination of the highest advantages and the normalization of the nonparametric distribution, Eq. 12, is performed within minibatches. While it is possible to perform the full-batch computation by utilizing crossreplica communication, we found this to be unnecessary.
DMLab action set. Ignoring the “jump” and “crouch” actions which we do not use, an action in the native DMLab action space consists of 5 integers whose meaning and allowed values are given in Table 2. Following previous work on DMLab (Hessel et al., 2018), we used the reduced action set given in Table 3 with an action repeat of 4.

Review summaries:
The paper proposes an online variant of MPO, V-MPO. Compared to MPO, the main difference seems to be in the E-step. Instead of optimizing the non-parametric distribution towards a parameterized Q-function, V-MPO learns the V-function and updates the non-parametric distribution towards the advantages, which can be estimated on the samples of the last roll-outs based on the empirical returns and the learned V-function. Of course, updating towards (exponentiated and normalized) Q- or A-function does not make a difference. There are also some minor changes (which might still be crucial) such as an entropy constraint in the M-step and using only the top-k advantages during the E-Step (an option that was discussed in Abdolmaleki, et al. 2018a).