Title: COMPOSING ENTROPIC POLICIES USING DIVERGENCE CORRECTION

Abstract: Deep reinforcement learning (RL) algorithms have made great strides in recent years. An important remaining challenge is the ability to quickly transfer existing skills to novel tasks, and to combine existing skills with newly acquired ones. In domains where tasks are solved by composing skills this capacity holds the promise of dramatically reducing the data requirements of deep RL algorithms, and hence increasing their applicability. Recent work has studied ways of composing behaviors represented in the form of action-value functions. We analyze these methods to highlight their strengths and weaknesses, and point out situations where each of them is susceptible to poor performance. To perform this analysis we extend generalized policy improvement to the max-entropy framework and introduce a method for the practical implementation of successor features in continuous action spaces. Then we propose a novel approach which, in principle, recovers the optimal policy during transfer. This method works by explicitly learning the (discounted, future) divergence between policies. We study this approach in the tabular case and propose a scalable variant that is applicable in multi-dimensional continuous action spaces. We compare our approach with existing ones on a range of non-trivial continuous control problems with compositional structure, and demonstrate qualitatively better performance despite not requiring simultaneous observation of all task rewards.

1. INTRODUCTION:

Reinforcement learning algorithms coupled with powerful function approximators have recently achieved a series of successes (Mnih et al., 2015; Silver et al., 2016; Lillicrap et al., 2015; Kalashnikov et al., 2018) . Unfortunately, while being extremely powerful, deep reinforcement learning (DRL) algorithms often require a large number of interactions with the environment to achieve good results, partially because they are often applied "from scratch" rather than in settings where they can leverage existing experience. This reduces their applicability in domains where generating experience is expensive, or learning from scratch is challenging.

The data efficiency of DRL algorithms is affected by various factors and significant research effort has been directed at achieving improvements (e.g. Popov et al., 2017) . At the same time the development of basic locomotor behavior in humans can, in fact, require large amounts of experience and practice (Adolph et al., 2012) , and it can take significant effort and training to master complex, high-speed skills (Haith & Krakauer, 2013) . Once such skills have been acquired, however, humans rapidly put them to work in new contexts and to solve new tasks, suggesting transfer learning as an important mechanism.

Transfer learning has been explored extensively in multiple fields of the machine learning community (see e.g. Weiss et al., 2016 , for a recent review). In RL and robotics the transfer of knowledge from one task to another has been studied from a variety of angles.

For the purpose of this paper we are interested in methods that are suitable for transfer in the context of high-dimensional motor control problems. We further focus on model-free approaches, which are evident in human motor control (Haith & Krakauer, 2013) , and have recently been used by a variety of scalable deep RL methods (e.g. Lillicrap et al., 2015; Mnih et al., 2015; Schulman et al., 2017; Kalashnikov et al., 2018) .

Transfer may be especially valuable in domains where a small set of skills can be composed, in different combinations, to solve a variety of tasks. Different notions of compositionality have been considered in the RL and robotics literature. For instance, 'options' are associated with discrete units of behavior that can be sequenced, thus emphasizing composition in time (Precup et al., 1998) .

In this paper we are concerned with a rather distinct notion of compositionality, namely how to combine and blend potentially concurrent behaviors. This form of composition is particularly relevant in high-dimensional continuous action spaces, where it is possible to achieve more than one task simultaneously (e.g. walking somewhere while juggling).

One approach to this challenge is via the composition of task rewards. Specifically, we are interested in the following question: If we have previously solved a set of tasks with similar transition dynamics but different reward functions, how can we leverage this knowledge to solve new tasks which can be expressed as a convex combination of those rewards functions? This question has recently been studied in two independent lines of work: by Barreto et al. (2017; 2018) in the context of successor feature (SF) representations used for Generalized Policy Improvement (GPI) with deterministic policies, and by Haarnoja et al. (2018a) ; van Niekerk et al. (2018) in the context of maximum entropy policies. These approaches operate in distinct frameworks but both achieve skill composition by combining the Q-functions associated with previously learned skills.

We clarify the relationship between the two approaches and show that both can perform well in some situations but achieve poor results in others, often in complementary ways. We introduce a novel method of behavior composition that that can consistently achieve good performance.

Our contributions are as follows:

1. We introduce succcessor features (SF) in the context of maximum entropy and extend the GPI theorem to this case (max-ent GPI).

2. We provide an analysis of when GPI, and compositional "optimism" (Haarnoja et al., 2018a) of entropy-regularized policies transfer. We construct both tabular and continuous action tasks where both fail to transfer well.

3. We propose a correction term -which we call Divergence Correction (DC)-based on the Rényi divergence between policies which allows us, in principle, to recover the optimal policy for transfer for any convex combination of rewards.

4. We demonstrate a practical implementation of these methods in continuous action spaces using adaptive importance sampling and compare the approaches introduced here: max-ent GPI and DC with optimism (Haarnoja et al., 2018a) and Conditional Q functions (Schaul et al., 2015) in a variety of non-trivial continuous action transfer tasks.

2. BACKGROUND:



2.1. MULTI-TASK RL:

We consider Markov Decision Processes defined by the tuple M containing: a state space S, action space A, a start state distribution p(s 1 ), a transition function p(s t+1 |s t , a t ), a discount γ ∈ [0, 1) and a reward function r(s t , a t , s t+1 ). The objective of RL is to find a policy π(a|s) : S → P(A) which maximises the discounted expected return from any state

J(π) = E π,M [ ∞ τ =t γ τ -t r τ ]

where the expected reward is dependent on the policy π and the MDP M.

We formalize transfer as in Barreto et al. (2017) ; Haarnoja et al. (2018a) , as the desire to perform well across all tasks in a set M ∈ T after having learned policies for tasks M ∈ T , without additional experience. We assume that T and T are related in two ways: all tasks share the same state transition function, and tasks in T can be expressed as convex combinations of rewards associated with tasks in set T . So if we write the reward functions for tasks in T as the vector φ = (r 1 , r 2 , . . . ), tasks in T can be expressed as r w = φ • w.

We focus on combinations of two policies r b = br i + (1 -b)r j but the methods can be extended to more than two tasks. We refer to a transfer method as optimal, if it achieves optimal returns on tasks in T , using only experience on tasks T .

2.2. SUCCESSOR FEATURES:

Successor Features (SF) (Dayan, 1993) and Generalised Policy Improvement (GPI) (Barreto et al., 2017; 2018) provide a principled solution to transfer in the setting defined above. SF make the additional assumption that the reward feature φ is fully observable, that is, the agent has access to the rewards of all tasks in T but not T during training on each individual task.

The key observation of SF representations is that linearity of the reward r w with respect to the features φ implies the following decomposition of the value policy of π:

Q π w (s t , a t ) = E π ∞ τ =t γ τ -t φ τ • w|a t = E π ∞ i=t γ τ -t φ τ |a t • w ≡ ψ π (s t , a t ) • w, (1)

where ψ π is the expected discounted sum of features φ induced by policy π. This decomposition allows us to compute the action-value for π on any task w by learning ψ π .

If we have a set of policies π 1 , π 2 , ..., π n indexed by i, SF and GPI provide a principled approach to transfer on task π w . Namely, we act according to the deterministic GPI policy π GP I w

(s t ) ≡ arg max at Q GP I w (s t , a t ))

where

Q GP I w (s t , a t ) ≡ max i Q πi w (s t , a t ) = max i ψ πi (s, a) • w (2)

The GPI theorem guarantees the GPI policy has a return at least as good as any component policy, that is,

V π GP I w (s) ≥ max i V πi w (s) ∀s ∈ S.

2.3. MAXIMUM ENTROPY RL:

The maximum entropy (max-ent) RL objective augments the reward to favor entropic solutions

EQUATION

where α is a parameter that determines the relative importance of the entropy term.

This objective has been considered in a number of works including Kappen (2005); Todorov (2009); Haarnoja et al. (2017; 2018a) ; Ziebart et al. (2008) ; Fox et al. (2015) .

We define the action-value Q π associated with eq. 3 as

EQUATION

(notice Q π (s t , a t ) does not include any entropy terms for the state s t ). Soft Q iteration Q(s t , a t ) ← r(s t , a t , s t+1 ) + γE p(st+1|st,at) [V (s t+1 )]

(5)

V (s t ) ← E π [Q(s t , a t )] + αH[π(•|s t )] = α log A exp( 1 α Q(s t , a t ))da ≡ α log Z(s t ) (6)

where π(a t |s t ) ∝ exp( 1 α Q(s t , a t )) converges to the optimal policy with standard assumptions (Haarnoja et al., 2017) .

3. COMPOSING POLICIES IN MAX-ENT REINFORCEMENT LEARNING:

In this section we present two novel approaches for max-ent transfer learning. In section 4 we then outline a practical method for making use of these results.

3.1. MAX-ENT SUCCESSOR FEATURES AND GENERALIZED POLICY IMPROVEMENT:

We introduce max-ent SF, which provide a practical method for computing the value of a maximum entropy policy under any convex combination of rewards. We then show the GPI theorem (Barreto et al., 2017) holds for maximum entropy policies.

We define the action-dependent SF to include the entropy of the policy, excluding the current state, analogous to the max-entropy definition of Q π in (4):

EQUATION

)

where 1 is a vector of ones of the same dimensionality as φ and we define the state-dependent successor features as the expected ψ π in analogy with V π (s):

EQUATION

The max-entropy action-value of π for any convex combination of rewards w is then given by Q π w (s, a) = ψ π (s, a) • w. Max-ent SF allow us to estimate the action-value of previous policies on a new task. We show that, as in the deterministic case, there is a principled way to combine multiple policies using their action-values on task w.

Theorem 3.1 (Max-Ent Generalized Policy Improvement) Let π 1 , π 2 , ..., π n be n policies with α-max-ent action-value functions

EQUATION

EQUATION

where Q π (s, a) and V π (s) are the α-max-ent action-value and value function respectively of π.

Proof: See appendix A.1. In our setup, we learn ψ πi (s, a), the SFs of policies π i for each task in T , we define the max-ent GPI policy for task w ∈ T as

π GP I w (a|s) ∝ exp( 1 α max i Q πi w (s, a)) = exp( 1 α max i ψ πi (s, a) • w).

3.2 DIVERGENCE CORRECTION (DC) Haarnoja et al. (2018a) introduced a simple approach to policy composition by estimating the actionvalue for the transfer task r b = br i + (1 -b)r j from the optimal action-values of the component tasks

EQUATION

When using Boltzmann policies defined by Q, the resulting policy, π Opt b (a|s) ∝ exp(1 α Q Opt b (s, a)), is the product distribution of the two component policies. We refer to π Opt b as the compositionally "optimistic" (CO) policy, as it acts according to the optimistic assumption that the optimal returns of Q i and Q j will be, simultaneously, achievable 1 .

Both max-ent GPI we presented above, and CO can, in different ways, fail to transfer well in some situations (see fig. 1 for some examples in tabular case). Neither approach consistently performs optimally during transfer, even if all component terms are known exactly. We desire a solution for transfer that, in principle, can perform optimally.

Here we show, at the cost of learning a function conditional on the task weightings b, it is in principle possible to recover the optimal policy for the transfer tasks, without direct experience on those tasks, by correcting for the compositional optimism bias in Q Opt b . For simplicity, as in Haarnoja et al. (2018a) , we restrict this to the case with only 2 tasks, but it can be extended to multiple tasks.

The correction term for CO uses a property noted, but not exploited in Haarnoja et al. (2018a) . The bias in Q Opt is related to the the discounted sum of Rényi divergences of the two component policies. Intuitively, if the two policies result in trajectories with low divergence between the policies in each state, the CO assumption that both policies can achieve good returns is approximately correct. When the divergences are large, the CO assumption is being overly optimistic and the correction term will be large.

Theorem 3.2 (DC Optimality) Let π i , π j be α max-ent optimal policies for tasks with rewards r i and r j with max-ent action-value functions

Q i , Q j . Define C ∞ b (s t , a t ) as the fixed point of C (k+1) b (s t , a t ) = -αγE p(st+1|st,at) log A π i (a t+1 |s t+1 ) b π j (a t+1 |s t+1 ) (1-b) exp(-1 α C (k) b (s t+1 , a t+1 ))da t+1

Given the conditions for Soft Q convergence, the max-ent optimal

Q * b (s, a) for r b = br i + (1 -b)r j is Q * b (s, a) = bQ i (s, a) + (1 -b)Q j (s, a) -C ∞ b (s, a) ∀s ∈ S, a ∈ A, b ∈ [0, 1].

Proof: See appendix A.2. We call this Divergence Correction (DC) as the quantity C ∞ b is related to the Rényi divergence between policies (see appendix A.2 for details). Learning C ∞ b does not require any additional information (in principle) than that required to learn policies π i and π j . Unlike with SF, it is not necessary to observe other task features while training the policies. On the other hand, unlike with GPI, which can be used to naturally combine any number of tasks with arbitrary weight vectors w, in order to apply DC one must estimate C ∞ b (s, a) for all values of b. so the complexity of learning C ∞ increases significantly if more than 2 tasks are combined.

Supplementary Table 1 provides a comparison on the properties of the methods we consider here. We also compare with simply learning a conditional Q function Q(s, a|b) (CondQ) (e.g. Schaul et al., 2015; Andrychowicz et al., 2017) . As with GPI, this requires observing the full set of task features φ, in order to compute r b for arbitrary b.

In this section we have introduced two new theoretical approaches to max-ent transfer composition: max-ent GPI and DC. We have shown how these are related to relevant prior methods. In the next section we address the question of how to practically learn and sample with these approaches in continuous action spaces.

4. ADAPTIVE IMPORTANCE SAMPLING FOR BOLTZMAN POLICIES ALGORITHM:

The control of robotic systems with high-dimensional continuous action spaces is a promising use case for the ideas presented in this paper. Such control problems may allow for multiple solutions, and can exhibit exploitable compositional structure. Unfortunately, learning and sampling of general Boltzmann policies defined over continuous action spaces is challenging. While this can be mitigated by learning a parametric sampling distribution, during transfer we want to sample from the Boltzmann policy associated with a newly synthesized action-value function without having to learn such an approximation first. To address this issue we introduce Adaptive Importance Sampling for Boltzmann Policies (AISBP), a method which provides a practical solution to this challenge.

In the following we parametrise all functions with neural nets (denoting parameters by the subscript θ), including the soft action-value for reward i: Q i θ Q (s, a); the associated soft value function V i θ V (s) and a proposal distribution q i θq (a|s), the role of which we explain below. We use an off-policy algorithm, so that experience generated by training on policy i can be used to improve policy j. This is especially important since our analysis requires the action-value Q i (s, a) to be known in all states. This is less likely to be the case for a on on-policy algorithm, that only updates Q i using trajectories generated by policy π i . During training experience generated by all tasks are stored in a replay buffer R, and mini-batches are sampled uniformly and used to update all function approximators. Soft Q iteration (see eq. 4) is used to learn Q i and V i . These updates are, in principle, straightforward using transitions sampled from the replay buffer.

Sampling from the Boltzmann policy defined by

Q i θ Q , π i (a|s) ∝ exp 1 α Q i θ Q (s, a

) is challenging as is estimating the partition function (the log of which is also the value, c.f. Eq. 6). One approach is to fit an expressible, tractable sampler, such as a stochastic neural network to approximate π i (e.g. Haarnoja et al., 2018a) . This approach works well when learning a single policy. However, during transfer this may require learning a new sampler for each new value composition. AISBP instead uses importance sampling to sample π and estimate the partition function. The scalability of this approach is improved by using using a learned proposal distribution q θq (a|s), and by observing that modern architectures allow for efficient batch computation of a large number of importance samples. To facilitate transfer we restrict the parametric form of the proposals to mixtures of (truncated) Normal distributions. The well-known result that the product of Normal distributions can be computed in closed-form then allows us to construct effective compositional proposals during transfer.

More formally, for each policy in T we learn an action-value Q i θ Q (s, a), and value V i θ V (s) network, and a proposal distribution q i θq (a|s) (we drop the task index i here when writing the losses for nota-tional clarify, and write the losses for a single policy). The proposal distribution is a mixture of M truncated Normal distributions N T , truncated to the square a ∈ [-1, 1) n with diagonal covariances

EQUATION

The proposal distribution is optimized by minimizing the forward KL divergence with the Boltzmann policy π(a|s

) ∝ exp 1 α Q θ Q (s, a)

. This KL is "zero avoiding" and over-estimates the support of π (Murphy, 2012) which is desirable for a proposal distribution (Gu et al., 2015) ,

EQUATION

where the expectation is over the replay buffer state density.

The inner expectation in the proposal loss itself requires sampling from π. We approximate his expectation by self-normalized importance sampling and use a target proposal distribution p(a t |s t ) which is a mixture distribution consisting of the proposals for all policies along with a uniform distribution. For batchsize B and N proposal samples the estimator of the proposal loss is then

L(θ q ) ≈ - 1 B B k=1 N l=1

w kl log q θq (a|s t );

EQUATION

The value function loss is defined as the L2 error on the Soft Q estimate of value

EQUATION

which is estimated using importance sampling to compute the integral.

EQUATION

)

This introduces bias due to the finite-sample approximation of the expectation inside the (concave) log. In practice we found this estimator sufficiently accurate, provided the proposal distribution was close to π. We also use importance sampling to sample from π while acting.

The action-value loss is just the L2 norm with the Soft Q target:

EQUATION

)

To improve stability we employ target networks for the value V θ V and proposal q θ q networks (Mnih et al., 2015; Lillicrap et al., 2015) We also parameterize Q as an advantage , 1994; Wang et al., 2015; Harmon et al., 1995) which is more stable when the advantage is small compared with the value. The full algorithm is give in Algorithm Box 1 and more details are provided in appendix C.

Q θ Q (s, a) = V θ V (s) + A θ A (s, a) (Baird

4.1. IMPORTANCE SAMPLED MAX-ENT GPI:

The same importance sampling approach can also be used to estimate max-ent SF. Max-ent GPI requires us to learn the expected (maximum entropy) features ψ i for each policy π i , in order to estimate its (entropic) value under a new convex combination task w. This requires that experience tuple in the replay contain the full feature vector φ, rather than just the reward for the policy which generated the experience r i . Given this information ψ θ ψ and Υ θ Υ can be learned with analogous updates to V and Q, which again requires importance sampling to estimate Υ.

As with V θ V , we use a target network for Υ θ Υ and advantage parametrization. We found that, because these updates when using experience shared between tasks is far off-policy, it is necessary to have a longer target update period than for V . Full details are of the losses and samplers are in appendix C.

Algorithm 1 AISBP training algorithm Initialize proposal network θ q , value network parameters θ V and action-value network parameters θ Q and replay R while training do in parallel on each actor Obtain parameters θ from learner Sample task i ∼ T Roll out episode using q i θq to importance sample π i (a|s

) ∝ exp 1 α Q i θ Q (s, a) Add experience to replay R end while while training do in parallel on the learner Sample SARS tuple from R Improve L(θ q ), L(θ V ), L(θ Q ) Improve additional losses for transfer L(θ Υ ), L(θ ψ ), L(θ C ), L(θ V b ) L(θ Q b ), if target update period then Update target network parameters θ V ← θ V , θ q ← θ q , θ Υ ← θ Υ , θ V b ← θ V b end if end while 4.2 DIVERGENCE CORRECTION

All that is required for transfer using compositional optimism (eq. 11, Haarnoja et al. (2018a) ) is the max-ent action values of each task, so no additional training is required beyond the base policies. In section 3. 

(1 -b)π j (a |s ) - 1 α C θ C (s , a , b))da ]) 2 ].

As with other integrals of the action space, we approximate this loss using importance sampling to estimate the integral. Note that, unlike GPI and CondQ (next section), learning C ∞ b does not require observing φ while training.

We also considered a heuristic approach where we learned C only for b = 1 2 (this is typically approximately the largest divergence). This avoids the complexity of a conditional estimator and we estimate

C ∞ b as Ĉ∞ b (s, a) ∼ 4b(1 -b)C ∞ 1/2 (s, a)

. This heuristic, we denote DC-Cheap, can be motivated by considering Gaussian policies with similar variance (see appendix D) The max-ent GPI bound can be used to correct for over-estimates of the heuristic

C ∞ b , Q DC-Cheap+GP I (s, a) = max(Q OP T (s, a) -Ĉ∞ b (s, a), Q GP I (s, a)).

4.3. COND Q:

As a baseline, we directly learn a conditional Q function using a similar approach to DC of sampling b each update Q(s, a, b) (Schaul et al., 2015) . This, like GPI but unlike DC, requires observing φ during training so the reward on task b can be estimated. We provide the full details in appendix C.

4.4. SAMPLING COMPOSITIONAL POLICIES:

During transfer we would like to be able to sample from the Boltzmann policy defined by our estimate of the transfer action-value Q b (the estimate is computed using the methods we enumerated above) without having to, offline, learn a new proposal or sampling distribution first (which is the approach employed by Haarnoja et al. (2018a) ).

As outlined earlier, we chose the proposal distributions so that the product of proposals is tractable, meaning we can sample from q ij b (a|s) ∝ (q i θq (a|s)) b (q j θ (a|s)) (1-b) . This is a good proposal distribution when the CO bias is low, since Q Opt b defines a Boltzmann policy which is the product of the base policies 2 However, when C ∞ b (s, a) is large, meaning the CO bias is large, q ij may not be a good proposal, as we show in the experiments. In this case none of the existing proposal distributions may be a good fit. Therefore we sample from a mixture distribution of all policies, all policy products and the uniform distribution. p b (a|s) ≡ 1 4 (q i θq (a|s) + q j θq (a|s

EQUATION

where V A is the volume of the action space. Empirically, we find this is sufficient to result in good performance during transfer. The algorithm for transfer is given in supplementary algorithm 2.

5. EXPERIMENTS:



5.1. DISCRETE, TABULAR ENVIRONMENT:

We first consider some illustrative tabular cases of compositional transfer. These highlight situations in which GPI and CO transfer can perform poorly (Figure 1 ). As expected, we find that GPI performs well when the optimal transfer policy is close to one of the existing policies; CO performs well when both subtask policies are compatible. The task we refer to as "tricky" is illustrative of in which the optimal policy for the transfer task does not resemble either existing policy: In the grid world nonoverlapping rewards for each task are provided in one corner of the grid world, while lower value overlapping rewards are provided in the other corner (cf. Fig. 1 ). As a consequence both GPI and CO perform poorly while DC performs well in all cases.

5.2. CONTINUOUS ACTION SPACES:

We next compare the different approaches in more challenging continuous control tasks. We train max-ent policies to solve individual tasks using the importance sampling approach from section 4 and then assess transfer on convex combinations of the rewards. All approaches use the same experience and proposal distribution.

Figure 2 examines the transfer policies in detail in a simple point-mass task and shows how the estimated C ∞ b corrects the CO Q Opt and dramatically changes the policy. We then examine conceptually similar tasks in more difficult domains: a 5 DOF planar manipulator reaching task (figure 3 ), 3 DOF jumping ball and 8 DOF ant (figure 4 ). We see that DC recovers a qualitatively better policy in all cases. The performance of GPI depends noticeably on the choice of α. DC-Cheap, which is a simpler heuristic, performs almost as well as DC in the tasks we consider except for the point mass task. When bounded by GPI (DC-Cheap+GPI) it performs well for the point mass task as well, suggesting simple approximations of C ∞ b may be sufficient in some cases. 3 We focussed on "tricky" tasks as they are challenging form of transfer. In general, we would expect DC to perform well in most situations where OC performs well, since in this case the correction term C ∞ b that DC must learn is inconsequential (OC is equivalent to assuming C ∞ b = 0). Supplementary figure 5 demonstrates on a task with non-composible solutions (i.e. C ∞ b is large and potentially challenging to learn), DC continues to perform as well as GPI, slightly better than CondQ, and as expected, OC performs poorly.

6. DISCUSSION:

We have presented two approaches to transfer learning via convex combinations of rewards in the maximum entropy framework: max-ent GPI and DC. We have shown that, under standard assump-

EQUATION

a|s)π2(a|s). 3 We provide videos of the more interesting tasks at https://tinyurl.com/yaplfwaq. (d) GPI performs well when the subtasks are incompatible, meaning the optimal policy is near one of the component policies. (g) CO performs poorly in these situations, resulting in indecision about which subtask to commit to. (e) Conversely, when the subpolicies are compatible, such as on the LU task, CO transfers well while the GPI policy (h) does not consistently take advantage of the compatibility of the two tasks to simultaneously achieve both subgoals.

(f) Neither GPI nor CO policies (i shows the GPI policy, but CO is similar) perform well when the optimal transfer policy is dissimilar to either existing task policy. The two tricky task policies are compatible in many states but have a high-divergence in the bottom-left corner since the rewards are non-overlapping there (k), thus the optimal policy on the composed task is to move to the top right corner where there are overlapping rewards. By learning, and correcting for, this future divergence between policies, DC results in optimal policies for all task combinations including tricky (j). (0, 1 ) and (0.75, 0.75) for the green, red and yellow squares. Lines show sampled trajectories (starting in the center) for the compositional task r 1/2 with CO (red), GPI (blue) and DC (black). Only DC, DC heuristics and CondQ (not shown) find the optimal transfer policy of navigating to yellow reward area for the joint task which is the optimal solution for the compositional task. (b) The returns for each transfer method. DC and CondQ methods recover significantly better performance than GPI, and the CO policy performs poorly. (c) The Rényi divergence of the two base policies as a function of position: the two policies are compatible except near the bottom left corner where the rewards are non-overlapping. (d) Q Opt at the center position for the combined task. As both policies prefer moving left and down, most of the energy is on these actions. (e) However, the future divergence C ∞ 1/2 under these actions is high, which results in the (f) DC differing significantly from CO.

tions, the max-ent GPI policy performs at least as well as its component policies, and that DC recovers the optimal transfer policy. Todorov (2009) and (Saxe et al., 2017; van Niekerk et al., 2018) previously considered optimal composition of max-ent policies. However, these approaches Figure 4 : "Tricky" task with mobile bodies. "Tricky" task with two bodies: a 3 DOF jumping ball (supplementary figure 6 ) and (a) 8 DOF ant (both torque controlled). The task has rewards (1, 0), (0, 1) in the green and red boxes respectively and (0.75, 0.75) in the blue square. (b-c) Returns for both walkers when started in the center position. CO approach does not recover the optimal policy for the compositional task while the other approaches largely do, although CondQ does not learn a good policy on the ant (shaded bars show SEM, 3 seeds for jumping ball, 5 seeds for ant). (e) Sampled trajectories of the ant on the transfer task starting from a neutral position for b = 1 2 . GPI and DC consistently go to the blue square (optimal), CondQ and CO do not. require stronger assumptions than max-ent SF or DC, namely that reward states are absorbing and that the joint reward is restricted to the softmax of the component rewards (soft OR). By contrast, DC does not restrict the class of MDPs and learns how compatible policies are, allowing approximate recovery of optimal transfer policies both when the component rewards are jointly achievable (AND), and when only one sub-goal can be achieved (OR).

We have compared our methods with conditional action-value functions (CondQ) (Schaul et al., 2015, e.g.) and optimistic policy combination (Haarnoja et al., 2018a) . Further, we have presented AISBP, a practical algorithm for training DC and max-ent GPI models in continuous action spaces using adaptive importance sampling. We have compared these approaches, along with heuristic approximations of DC, and demonstrated that DC recovers an approximately optimal policy during transfer across a variety of high-dimensional control tasks. Empirically we have found CondQ may be harder to learn than DC, and it requires additional observation of φ during training.

A PROOFS:

A.1 MAX-ENT GENERALIZED POLICY IMPROVEMENT Theorem 3.1 (Max-Ent Generalized Policy Improvement) Let π 1 , π 2 , ..., π n be n policies with α-max-ent action-value functions Q 1 , Q 2 , ..., Q n and value functions V 1 , V 2 , ..., V n . Define

π(a|s) ∝ exp 1 α max i Q i (s, a) . Then, Q π (s, a) ≥ max i Q i (s, a)

for all s ∈ S and all a ∈ A, (9)

EQUATION

where Q π (s, a) and V π (s) are the α-max-ent action-value and value function respectively of π.

For brevity we denote Q max ≡ max i Q i . Define the soft Bellman operator associated with policy π as 

T π Q(s, a) ≡

T π Q max (s, a) = r(s, a, s ) + γE s ∼p(•|s,a),a ∼π(•|s ) [-α log π(a |s ) + Q max (s , a )] = r(s, a, s ) + γE s ∼p(•|s,a),a ∼π(•|s ) -α log exp(α -1 Q max (s , a )) Z π (s ) + Q max (s , a ) = r(s, a, s ) + γE s ∼p(•|s,a) [α log Z π (s )] .

Similarly, if we apply T πi , the soft Bellman operator induced by policy π i , to Q max (s, a), we obtain: We now note that the Kullback-Leibler divergence between π i and π can be written as

T πi Q max (

D KL (π i (•|s) π(•|s)) = E a∼πi(•|s) [log π i (a|s) -log π(a|s)] = E a∼πi(•|s) log π i (a|s) - 1 α Q max (s, a) + log Z π (s) .

The quantity above, which is always nonnegative, will be useful in the subsequent derivations. Next we write

EQUATION

From ( 20) we have that

T π Q max (s, a) ≥ T πi Q max (s, a) ≥ T πi Q i (s, a) = Q i (s, a) for all i.

Using the contraction and monotonicity of the soft Bellman operator T π we have

Q π (s, a) = lim k→∞ (T π ) k Q max (s, a) ≥ Q i (s, a) for all i.

We have just showed (9). In order to show (10), we note that

EQUATION

Under review as a conference paper at ICLR 2019 Similarly, we have, for all i,

EQUATION

The bound (10) follows from ( 21) and ( 22).

A.2 DC PROOF Theorem 3.2 (DC Optimality) Let π i , π j be α max-ent optimal policies for tasks with rewards r i and r j with max-ent action-value functions

Q i , Q j . Define C ∞ b (s t , a t ) as the fixed point of C (k+1) b (s t , a t ) = -αγE p(st+1|st,at) log A π i (a t+1 |s t+1 ) b π j (a t+1 |s t+1 ) (1-b) exp(-1 α C (k) b (s t+1 , a t+1 ))da t+1

Given the conditions for Soft Q convergence, the max-ent optimal

Q * b (s, a) for r b = br i + (1 -b)r j is Q * b (s, a) = bQ i (s, a) + (1 -b)Q j (s, a) -C ∞ b (s, a) ∀s ∈ S, a ∈ A, b ∈ [0, 1].

We follow a similar approach to Haarnoja et al. (2018a) but without making approximations and generalizing to all convex combinations.

First note that since π i and π j are optimal then π i (a|s

) = exp( 1 α (Q i (s, a) -V i (s))

). For brevity we use s and s notation rather than writing the time index.

Define:

EQUATION

EQUATION

and consider soft Q-iteration on r b starting from Q

b . We prove, inductively, that at each iteration Q

(k+1) b = bQ i (s, a) + (1 -b)Q j (s, a) -C (k+1) (s, a).

This is true by definition for:

EQUATION

Since soft Q-iteration converges to the α max-ent optimal soft Q then equation 31 holds at the limit.

One can get an intuition for C ∞ b (s, a) by noting that C

EQUATION

where D b is the Rényi divergence of order b. C ∞ b (s, a) can be seen as the discount sum of divergences, weighted by the unnormalized product distribution π 1 (a|s) b π 2 (a|s) 1-b .

A.3 N POLICIES:

It is possible to extend Theorem 3.2 to the case with N policies in a straightforward way.

Theorem A.1 (Multi-policy DC Optimality) Let π 1 , π 2 , ..., π N be α max-ent optimal policies for tasks with rewards r 1 , r 2 , ..., r N with max-ent action-value functions Q

1 , Q 2 , ..., Q N . Define C ∞ w (s t , a t ) as the fixed point of C (k+1) w (s t , a t ) = -αγE p(st+1|st,at) log A N i=1 π i (a t+1 |s t+1 ) wi exp(-1 α C (k) w (s t+1 , a t+1 ))da t+1

Given the conditions for Soft Q convergence, the max-ent optimal Q * w (s, a) for and convex combination of rewards r w =

N i=1 r i w i is Q * w (s, a) = N i=1 w i Q i (s, a) -C ∞ w (s, a) ∀s ∈ S, a ∈ A, w ∈ {w| N i=1 w i = 1 and w i ≥ 0}

Note that w i refers to component i of the vector w i .

The proof is very similar to the two reward case above.

Define

EQUATION

EQUATION

and again consider soft Q-iteration on r w . We prove by induction that at each iteration

EQUATION

Again, this is true by definition for k = 0. Now we consider a step of Soft Q iteration

EQUATION

Since soft Q-iteration converges to the α max-ent optimal soft Q then

Q * w (s, a) = N i=1 w i Q i (s, a) -C (k+1) w

(s, a) for all s ∈ S, a ∈ A.

Note that, in practise, estimating C ∞ w may be more challenging for larger N . For compositions of many policies, GPI may be more practical. (c) Returns as a function of b, SEM across 5 seeds is plotted, but is smaller than the line thickness.

E ADDITIONAL EXPERIMENT F EXPERIMENT DETAILS:

All control tasks were simulated using the MuJoCo physics simulator and constructed using the DM control suite (Tassa et al., 2018) which uses the MuJoCo physics simulator (Todorov et al., 2012) . The point mass was velocity controlled, all other tasks were torque controlled. The planar manipulator task was based off the planar manipulator in the DM control suite. The reward in all tasks was sparse as described in the main text.

During training for all tasks we start states from the randomly sampled positions and orientations.

For the point mass, jumping ball and ant we evaluated transfer starting from the center (in the walker environments, the starting orientation was randomly sampled during transfer, the point mass does not have an orientation). For the planar manipulator transfer was tested from same random distribution as in training. For all tasks were learned infinite time horizon policies.

Transfer is made challenging by the need for good exploration. That was not the focus on this work. We aided exploration in several ways: during training we acted according to a higher-temperature policy α e = 2α. We also sampled actions uniformly in an -greedy fashion with = 0.1 and added Gaussian exploration noise during training. This was sufficient to explore the state space for most tasks. For the planar manipulator and the jumping ball, we found it necessary to induce behavior tasks by learning tasks for reaching the blue target. This behavior policy was, of course, only used for experience and not during transfer.

Below we list the hyper-parameters and networks use for all experiment. The discount γ and α were the only sensitive parameters that we needed to vary between tasks to adjust for the differing magnitudes of returns and sensitivity of the action space between bodies. If α is too small then the policies often only find one solution and all transfer approaches behave similarly, while for large α the resulting policies are too stochastic and do not perform well.

Proposal The state vector was preprocessed by a linear projection of 3× its dimension and then a tanh nonlinearity. All action-state networks (Q, ψ, C) consisted of 3 hidden layers with elu non-linearities (Clevert et al., 2015) , with both action and preprocessed state projected by linear layers to be of the same dimensionality and used for input the first layer. All value networks and proposal networks consisted of 2 layers with elu non-linearities. The number of neurons in each layer was varied between environments, but was kept the same in all networks and layers (we did not sweep over this parameter, but choose a reasonable number based on our prior on the complexity of the task).

Below we list the per task hyper-parameters 

:

Compositional optimism is not the same as optimism under uncertainty, often used in RL for exploration.

Figures and Tables:

2 we have shown that if we can learn the fixed point of C ∞ b (s, a) we can correct this compositional optimism and recover the optimal action-value Q * b (s, a). We exploit the recursive relationship in C ∞ b (s, a) to fit a neural net C θ C (s, a, b) with a TD(0) estimator. This requires learning a conditional estimator for any value of b, so as to support arbitrary task combinations. Fortunately, since C ∞ b depends only on the policies and transition function it is possible to learn an estimator C ∞ b for different values of b by sampling b during each update. As before, we use target networks and an advantage parametrization for C θ C (s, a, b) We learn C ∞ b as C θ C (s, a, b), for each pair of policies π i , π j resulting in the loss L(θ C ) = E s∼R,b∼U (0,1) [ 1 2 (C θ C (s, a, b) + αγE p(s |s,a) [log A exp(b log π i (a |s )+ (18)

Figure 1: Policy composition in the tabular case. All tasks are in an infinite-horizon tabular 8x8 world. The action space is the 4 diagonal movements (actions at the boundary transition back to the same state) (a-c) shows 3 reward functions (color indicates reward, dark blue r = +1, light blue r = 0.75). The arrows indicate the action likelihoods for the max-ent optimal policy for each task. (d-f) The log regret for the max-ent returns for 3 qualitatively distinct compositional tasks r b = br i +(1-b)r j , using different approaches to transfer from the base policies. The compositional tasks we consider are left-right (LR), left-up (LU) and the "tricky" tasks (T).(d) GPI performs well when the subtasks are incompatible, meaning the optimal policy is near one of the component policies. (g) CO performs poorly in these situations, resulting in indecision about which subtask to commit to. (e) Conversely, when the subpolicies are compatible, such as on the LU task, CO transfers well while the GPI policy (h) does not consistently take advantage of the compatibility of the two tasks to simultaneously achieve both subgoals. (f) Neither GPI nor CO policies (i shows the GPI policy, but CO is similar) perform well when the optimal transfer policy is dissimilar to either existing task policy. The two tricky task policies are compatible in many states but have a high-divergence in the bottom-left corner since the rewards are non-overlapping there (k), thus the optimal policy on the composed task is to move to the top right corner where there are overlapping rewards. By learning, and correcting for, this future divergence between policies, DC results in optimal policies for all task combinations including tricky (j).

Figure2: Tricky point mass. The continuous "tricky" task with a simple 2-D velocity controlled pointed mass. (a) Environment and example trajectories. The rewards are (r 1 = 1, r 2 = 0), (0, 1) and (0.75, 0.75) for the green, red and yellow squares. Lines show sampled trajectories (starting in the center) for the compositional task r 1/2 with CO (red), GPI (blue) and DC (black). Only DC, DC heuristics and CondQ (not shown) find the optimal transfer policy of navigating to yellow reward area for the joint task which is the optimal solution for the compositional task. (b) The returns for each transfer method. DC and CondQ methods recover significantly better performance than GPI, and the CO policy performs poorly. (c) The Rényi divergence of the two base policies as a function of position: the two policies are compatible except near the bottom left corner where the rewards are non-overlapping. (d) Q Opt at the center position for the combined task. As both policies prefer moving left and down, most of the energy is on these actions. (e) However, the future divergence C ∞ 1/2 under these actions is high, which results in the (f) DC differing significantly from CO.

Figure 3: "Tricky" task with planar manipulator. The "tricky" tasks with a 5D torque-controlled planar manipulator. The training tasks consists of (mutually exclusive) rewards of (1, 0), (0, 1) when the finger is at the green and red targets respectively and reward (0.75, 0.75) at the blue target. (b) Finger position at the end of the trajectories starting from randomly sampled start states) for the transfer task with circles indicating the rewards. DC and CondQ trajectories reach towards the blue target (the optimal solution) while CO and GPI trajectories primarily reach towards one of the suboptimal partial solutions. (c) The returns on the transfer tasks (shaded bars show SEM, 5 seeds).

s, a) = r(s, a, s ) + γE s ∼p(•|s,a),a ∼πi(•|s ) [-α log π i (a |s ) + Q max (s , a )] .

Figure5: (a) Trajectories of the ant during transfer on non-composable subtasks. In this experiment the two base tasks consists of rewards at the red and green square respectively. As expected, in this task, where the two base tasks have no compositional solution, CO (red) performs poorly with trajectories that end up between the two solutions. GPI (blue) performs well, as does DC (black). CondQ does slightly worse. (b) Box-plot of returns from 5 seeds (at b = 0.5). (c) Returns as a function of b, SEM across 5 seeds is plotted, but is smaller than the line thickness.

Figure 6: Jumping ball tricky task

r(s, a, s ) + γE p(s |s,a) αH[π(•|s )] + E a ∼π(•|s ) [Q(s , a )] .Haarnojaet al. (2018b)  have pointed out that the soft Bellman operator T π corresponds to a conventional, "hard", Bellman operator defined over the same MDP but with reward r π (s, a, s ) = r(s, a, s ) + γαE p(s |s,a)[H[π(•|s )]]. Thus, as long as r(s, a, s ) and H[π(•|s )] are bounded, T π is a contraction with Q π as its fixed point. Appplying T π to Q max (s, a) we have:

Table content: <table/>

Number of importance samples for all estimators during learning 200 Number of importance samples for acting during training 50 Number of importance samples for acting during transfer 1000 Parameters the same across all experiments

Table content: <table><tr><td>learning rate</td><td>10 -3</td></tr><tr><td>All other learning rates</td><td>10 -4</td></tr><tr><td>Value target update period</td><td>200</td></tr><tr><td>Proposal target update period</td><td>200</td></tr><tr><td>Υ target update period</td><td>500</td></tr></table>

Parameters varied between experiments

Table content: <table><tr><td>Task</td><td>Number of units</td><td>α</td><td>γ</td></tr><tr><td>Point mass</td><td>22</td><td>1</td><td>0.99</td></tr><tr><td>Planar Manipulator</td><td>192</td><td colspan="2">0.05 0.99</td></tr><tr><td>Jumping Ball</td><td>192</td><td>0.2</td><td>0.9</td></tr><tr><td>Ant</td><td>252</td><td colspan="2">0.1 0.95</td></tr></table>

Peer review (iclr2019):
 The authors introduce Divergence Correction (DC) for the problem of transfer learning by composing policies. There approach builds on GPI with a maximum entropy objective. They also prove that DC solves for the max-entropy optimal interpolation between two policies and derive a practical approximation for this algorithm. They provide experimental results in a gridworld problem and study their approximate algorithm in two continuous control problems. While this paper has some interesting ideas (combining GPI with a Max-Entropy objective and DC), these ideas are not properly motivated. The main problem seems to be clarity. One big problem is that the paper never defines the notion of a notion of optimality (or near-optimality). Also, considering that the DC algorithm is one of the main contributions of the paper it is barely motivated. Theorem 3.2 is presented with almost no explanation about how DC was derived. Why do the authors believe that DC is a good idea on a conceptual level? It*s very interesting that the paper presents cases where previous approaches (Optimistic and GPI) don*t perform well. But the authors don*t explain why they believe DC should perform well in these cases. The authors make the unjustified claim in the abstract that their approach has "near-optimal performance and requires less information". I say this is unjustified because they only try this approach on three benchmarks. In addition, there should be situations where DC also performs poorly since there are known hardness results for solving MDPs. Admittedly, those results may not apply if the authors are making assumptions that are not being clearly discussed in the paper. Minor Comments: 1. In the abstract, "requiring less information" is very imprecise. Are you referring to sample complexity? 2. In the introduction, "can consistently achieve good performance" is imprecise. What is the notion of near-optimality? What does consistent mean? Having experimental results on 3 tasks doesn*t seem to be enough to me to justify this claim. 3. In the introduction (and rest of the paper), please don*t call Haarnoja et al.*s approach optimistic. Optimism already has another widely used meaning in RL literature. Maybe call it "Uncorrected". 4. In section 2.2, the authors introduce .pi_1, .pi_2, ... , .pi_n but never actually use that notation. This section does not clearly explain how GPI works. 5. In Theorem 3.1, the authors should introduce Q^1, Q^2, ... , Q^n and define the policies in terms of the action-value functions. Also, the statement of this theorem is not self contained, what is the reward function of the MDP? The proof below should be called a proof sketch. 6. The paper mentions that extending to multiple tasks is possible. Is it trivial? What is the basic idea? It seems straightforward but it might be helpful to explicitly state the idea. 7. In Theorem 3.2, how was C derived? Please add some commentary explaining the conceptual idea. 8. In Table 1, what is f(s, a|b)? I don*t see where this was defined? 9. CondQ is usually referred to as UVFA in the literature. 10. Section 3 really needs a conclusion statement. 11. Section 4 is very unclear and hard to follow. 12. In figure 1f, what is LTD? It*s never defined. I*m guessing it*s DC. 13. All of the figures are too small and some are not clear in black and white.