Discovering a set of policies for the worst case reward
Authors: Tom Zahavy
Andre Barreto
Daniel J Mankowitz
Shaobo Hou
Brendan O'Donoghue
Iurii Kemaev
Satinder Singh
Venue: ICLR 2021 Spotlight (2021)

Abstract: We study the problem of how to construct a set of policies that can be composed together to solve a collection of reinforcement learning tasks. Each task is a different reward function defined as a linear combination of  known features. We consider a specific class of policy compositions which we call set improving policies (SIPs): given a set of policies and a set of tasks, a SIP is any composition of the former whose performance is at least as good as that of its constituents across all the tasks. We focus on the most conservative instantiation of SIPs, set-max policies (SMPs), so our analysis extends to any SIP. This includes known policy-composition operators like generalized policy improvement. Our main contribution is an algorithm that builds a set of policies in order to maximize the worst-case performance of the resulting SMP on the set of tasks. The algorithm works by successively adding new policies to the set. We show that the worst-case performance of the resulting SMP strictly improves at each iteration, and the algorithm only stops when there does not exist a policy that leads to improved performance. We empirically evaluate our algorithm on a grid world and also on a set of domains from the DeepMind control suite. We confirm our theoretical results regarding the monotonically improving performance of our algorithm. Interestingly, we also show empirically that the sets of policies computed by the algorithm are diverse, leading to different trajectories in the grid world and very distinct locomotion skills in the control suite.

Published as a conference paper at ICLR 2021
DISCOVERING A SET OF POLICIES FOR THE WORST CASE REWARD
Tom Zahavy, Andre Barreto, Daniel Mankowitz, Shaobo Hou, Brendan O'Donoghue, Turii Kemaev and Satinder Singh DeepMind
ABSTRACT
We study the problem of how to construct a set of policies that can be composed together solve a collection of reinforcement learning tasks. Each task is a different reward function defined as a linear combination of known features. We consider a specific class of policy compositions which we call set improving policies (SIPs): given of the former whose performance is at least as good as that of its constituents across all the tasks. We focus on the most conservative instantiation of SIPs, set- max policies (SMPs), so our analysis extends to any SIP. This includes known policy-composition operators like generalized policy improvement. Our main contribution is a policy iteration algorithm that builds a set of policies in order to maximize the worst-case performance of the resulting SMP on the set of tasks. The algorithm works by successively adding new policies to the set. We show that the worst-case performance of the resulting SMP strictly improves at each iteration, and the algorithm only stops when there does not exist a policy that leads to improved performance. We empirically evaluate our algorithm a grid world and also on set of domains from the DeepMind control suite. We confirm our theoretical results regarding the monotonically improving performance of our algorithm. Interestingly, we also show empirically that the sets of policies computed by the algorithm are diverse, leading to different trajectories in the grid world and very distinct locomotion skills in the control suite.
of policies and set of tasks, STP is any composition
INTRODUCTION
Reinforcement learning (RL) is concerned with building agents that can learn act so as to maximize reward through trial-and-error interaction with the environment. There are several reasons why it can be useful for agent to learn about multiple ways of behaving, i.e., learn about multiple policies. The agent may want to achieve multiple tasks (or subgoals) in lifelong learning setting and may learn a separate policy for each task, reusing them as needed when tasks reoccur. The agent may have a hierarchical architecture in which many policies are learned at lower level while an upper level policy learns combine them in useful ways, such as accelerate learning transfer efficiently to a new task. Learning about multiple policies in the form of options (Sutton et al. 1999a) can be a good way to achieve temporal abstraction; again this can be used to quickly plan good policies for new tasks. In this paper we abstract away from these specific scenarios and ask the following question: what set of policies should the agent pre-learn in order to guarantee good performance under the worst-case reward? A satisfactory answer to this question could be useful in all the scenarios discussed above and potentially many others.
a single task to
There are components to the question above: (i) what policies should be in the set, and (ii) how to compose policy to be used on new task from the policies in the set. To answer (ii). we propose the concept of a set improving policy (SIP). Given any set of n policies, a SIP is any composition of these policies whose performance is at least as good as, and generally better than, that of all of the constituent policies the set. We present two policy composition (or improvement) operators that lead to a SIP. The first is called set-max policy (SMP). Given a distribution over states, SMP chooses from n. policies the one that leads to the highest expected value. The second SIP operator is generalized policy improvement (Barreto al.] 2017]] GPT). Given a set of n policies and their associated action-value functions, GPI is a natural extension of regular policy improvement in which the agent acts greedily in each state with respect to the maximum over the set of action-values
ttomzahavy@gooogee..c com

---

Published as a conference paper at ICLR 2021
functions. Although SMP provides weaker guarantees than GPI (we will show this below), is more amenable to analysis and thus we will use it exclusively for our theoretical results. However, since SMP's performance serve as a lower bound to GPI's, the results we derive for the former also apply to the latter. In our illustrative experiments we will show this result empirically.
Now that we have fixed the answer (ti), i.e., how compose pre-leamned policies for new reward function, we can leverage it to address (i): what criterion to use to pre-learn the policies. Here, one can appeal to heuristics such as the ones ad advocating that the set of pre-learned policies should be as diverse as possible (Eysenbach et al. 2018 Gregor et al. 2016 Grimm et al., 2019 Hansen et al. 2019). In this paper we will use the formal criterion of robustness, Lee, we will seek a set of policies that do as well as possible in the worst-case scenario. Thus, the problem of interest to this paper is as follows: how to define and discover a set of n policies that maximize the worst possible performance of the resulting SMP across all possible tasks? Interestingly, as we will discuss, the solution this robustness problem naturally leads to a diverse set of policies.
To solve the problem posed above we make two assumptions: (AI) l) that tasks differ only in their reward functions, and (A2) that reward functions are linear combinations of known features. These two assumptions allow us to leverage the concept of successor features (SFs) and work in apprenticeship learning. As our main contribution in this paper, we present an algorithm that iteratively builds a set of policies such that SMP's performance with respect to the worst case reward provably improves in each iteration, stopping when such greedy improvement is possible. We also provide closed-form expression to compute the worst-case performance of our algorithm at each iteration. This means that, given tasks satisfying Assumptions AI and A2, we are able to provably construct SIP that can quickly adapt to any task with guaranteed worst-case performance.
Related Work. The proposed approach has interesting connections with hierarchical RL (HRL) (Sut- ton et al. 1999b Dietterich, 2000). We can think of SMP (and GPI) as a higher-level policy mechanism that is fixed a priori. Under this interpretation, the problem we are solving can be seen as the definition and discovery of lower-level policies that will lead to a robust hierarchical agent.
There are interesting parallels between robustness and diversity. For example, diverse stock portfolios have less risk. In robust least squares (El Ghaoui & Lebret 1997] Xuu et al.) (009), the goal is to find a solution that will perform well with respect to (w.r.t) data perturbations. This leads to min-max formulation, and there are known equivalences between solving a robust (min-max) problem and the diversity of the solution (via regularization) (Xu & Mannor 2012). Our work is also related to robust Markov decision processes (MDPs) (Nilim & El Ghaoui 2005). but our focus is on different aspect of the problem. While in robust MDPs the uncertainty w.r. the dynamics of the environment, here we focus on uncertainty w.r.t the reward and assume that the dynamics are fixed. More importantly, we are interested in the hierarchical aspect of the problem - how to discover and compose a set of policies. In contrast, solutions to robust MDPs are typically composed of a single policy.
In Apprenticeship Learning (AL:[Abbec) & Ng. 2004) the goal is also to solve a min-max problem in which the agent is expected to perform as well as an expert w.r.t any reward. If we ignore the expert, AL algorithms can be used to find a single policy that performs well w.r.f any reward. The solution to this problem (when there is no expert) is the policy whose SFs have the smallest possible norm. When the SFs are in the simplex (as in tabular MDPs) the vector with the smallest l norm puts equal probabilities on its coordinates, and is therefore "diverse" (making an equivalence between the robust min- mix formulation and the diversity perspective). In that sense, our problem can be seen as a modified AL setup where: (a) no expert demonstrations are available (b) the agent is allowed to observe the reward at test time, and (c) the goal is to learn a set of constituent policies.
2 PRELIMINARIES
We will model our problem of interest using family of Markov Decision Processes (MDPs). An MDP is tuple M e (S, A.r. P.r,y, ",,,,,) D). where S is the set of states, A is the set of actions, P P= (P" a E A} is the set of transition kernels, 7 E [0, 1] is the discount factor and D is the initial state distribution. The function r : S x A x S + IR defines the rewards, and thus the agent's objective; here we are interested in multiple reward functions, as we explain next.
Let Φ(s, a, 8') E [o. 1jd be an observable vector of features (our analysis only requires the features to be bounded; we use [6, 1] for ease of exposition). We are interested in the set of tasks induced by all possible linear combinations of the features &. Specifically, for any w E Rd. we can define a reward function rw (8, x') = w Φ0s, a, s'). Given w, the reward Fw is well defined and we will use the terms and Tw interchangeably to refer to the RL task induced by it. Formally, we are interested in
2

---

Published as a conference paper at ICLR 2021
the following set of MDPs:
Mg - P,T, D,D w EW)
In general, W is any convex set, but we will focus on the &2 d-dimensional ball denoted by W B2. This choice is not restricting, since the optimal policy in an MDP is invariant with respect to the scale of the rewards and the &g ball contains all the directions.
A policy in an MDP M E .Ms. denoted by E II. is mapping - P(A), where P(A) is the space of probability distributions over A. For a policy i we define the successor features (SFs) as
a)) - (1 7)
"' de, S141) a,
(2)
together with the fact that the features & are in [0, 1] assures that (8, a) E [0, 1] for all (s, a) E S x A We also define SFs that are conditioned on the initial state distribution D and the policy as: 26- Eleb" a) D, T] = EE x/")///(( (s, a). It should be clear that the SFs are conditioned on D and π whenever they are not written as function of states and actions like in Eq. (2). Note that, given policy n, 16" is simply vector in [0. 1j Since we will be dealing with multiple policies, we will use superscripts to refer to them that is, we use n² to refer to the i-th policy. To keep the notation simple, we will refer to the SFs of policy x² as ap¹. We define the action-value function (or Q-function) of policy ıT under reward rw as
The multiplication by
Q (s. a) - (1 - B)
Σ 1=
7' (' Ge, 81+1) w/ P. 8, = a) 2/= (s, W.
We define the value of policy as ou - (1-7) o 7'w ww (s:))TT, P.D] :J w. Note that uw is a scalar, corresponding to the expected value of policy क under the initial state distribution D, given by
ww ElQ (8, D, T] EenDavvn(e) Ow (8,
3 COMPOSING POLICIES TO SOLVE A SET OF MDPs
As described, we are interested in solving all the tasks w E W the set of MDPs Ma defined IT. We will approach this problem by learning policies associated with specific rewards w and then composing them build higher-level policy that performs well across all the tasks. We call this higher-level policy a generalized policy, defined as (Barreto et al. 2020):
Definition 1 (Generalized policy). Given a set of MDPs Ma. generalized policy is a function : T: S x W + P(A) that maps a state s and a task w onto a distribution over actions.
We can think of a generalized policy as regular policy parameterized by task, since for a fixed w we have (:; w) S - P(A). We now focus attention on specific class of generalized policies that are composed of other policies:
Definition (SIP). Given a set of MDPs MA and a set policy (SIP) SSP is any generalized policy such that:
set of policies IIT { " D set improving
UTI. for for all n¹ E III and all w W,
(4)
where ui and byy are the value functions of oHp (+ w) and the policies xO E II under reward Tw-
We have been deliberately vague about the specific way the policies n' E 11 are combined to form SIP to have as inclusive a concept as possible. We now describe two concrete ways to construct SIP.
Definition 3 (SMP). Let IT {
= be set of n policies and let u² be the corresponding value for an arbitrary reward. A set-max policy (SMP) is defined as
functions defined analogously to 3
T (s; w) (s),,, with ls arg max [E(I.....m)
'hhile we focus the most common, discounted RL criteria, all of our results will hold in the finite horizon and average reward criteria (see, for example, [Puterman] (1984)). Concretcly, in these scenarios there exist normalizations for the SF's whose effect are equivalent to that of the multiplication by 7. In the hinite-horizon case we simply multiply the SFs by 1/ H.. In the average reward case, there is no multiplication (Zahavy 2020b) and the value function is measured under the stationary distribution (instead of D)).
3

---

Published as a conference paper at ICLR 2021
Combining the concepts of SMP and SFs can build SIP for Ma- Given the SFs of the policies x' II",, (xb))= >i=1, we can quickly compute a generalized SMP
SMP THh
(s: w) x² (s), with k arg max {w "/"
(5)
iEln.....
Since the value of SMP under reward is given by "il" [ o it trivially qualifies as a SIP as per Definition 2 In fact, the generalized policy "T"" most conservative SIP possible, as it will always satisfy (4) with equality. This means that any other SIP will perform at least as well as the SIP induced by SMP. We formalize this notion below:
-aMe defined in 5 is in some sense the
Let SMP be SMP defined as in (5) and let π S x W + (PA) be any generalized policy. Then, given set of policies II", x is SIP if and only if uf w 2 "II" for all w W.
Lemma 1.
Due to space constraints, all the proofs can be found in the suppiementary material. Lemma allows us to use SMP to derive results that apply to all SIPs. For example, a lower bound for SSMP VTT".w
automatically applies to all possible "I[". .w. Lemmal ] also allows us to treat SMP as criterion to determine whether a given generalized policy qualifies as a SIP. We illustrate this by introducing second candidate to construct a SIP called generalized policy improvement (Barreto et al., 2017 2018 2020 GPI):
Definition 4 (GPI policy). Given set of policies IT {x²)²= and corresponding Q-functions Qu computed under an arbitrary reward w, the GPI policy is defined
GPT "Th (s; w) = arg max max (s,sa)
Again, we can combine GPI and SFs to build a generalized policy. Given the SFs of the poli-
cies क² E II", [ we can quickly compute the generalized GPI policy as GPI (8; w) = arg max, max; 2p (8. a) w. Note that the maximization in GPI is performed in each state and uses the Q-functions of the constituent policies. In contrast, SMP maximizes over value functions (not Q-functions), with an expectation over states taken with respect to the initial state distribution D. For this reason, GPI is a stronger composition than SMP. We now formalize this intuition:
Lemma 2. For any reward w E W and any set of policies II", we have that GPI "1
SMP V11"
Lemma 2 implies that for any of policies it is always better to use GPI policy rather than an SMP (as we will confirm the experiments). As a consequence, it also certifies that the generalized GPI policy = (s; w) qualifies as a SIP (Lemma
We have described two ways of constructing a SIP by combining SMP and GPI with SFs. Other similar strategies might be possible, for example by using local SARSA (Russell & Zimdars] 2203 Sprague & Ballard, (003)
the basic mechanism compose set of value functions. We also note that in some cases it is possible to define a generalized policy (Definition D.. that is not necessarily a SIP (Eq. (5)) but is guaranteed to perform better than any SIP in expectation. For example, a combination of maximization, randomization and local search have been shown to be optimal in expectation among generalized policies in tabular MDPs with collectible rewards (Zahavy 2020c). That said, we note that some compositions of policies that may at first seem like SIP do not qualify as such. For example, a mixed policy is linear (convex) combination of policies that assigns probabilities to the policies in the set and samples from them. When the mixed policy is mixing the best policy in the set with less performant policy then will result in policy that not as good as the best single policy in the set (Zahavy et al. 2020c).
al.
Problem formulation. We are now ready to formalize the problem we are interested in. Given set of MDPs Ma. as defined in [1. we want to construct set policies IIT" = { ) such that the performance of the SMP defined on that set SMP will have the optimal worst-case performance over all rewards w E W. That is, we want to solve the following problem:
arg max min SMP C w UTT",
(6)
Note that, since " S "II", w for any SIP, II" and w, as shown in Lemma by finding good set for (6) are also improving the performance of all SIPs (including GPI).
4

---

Published as a conference paper at ICLR 2021
4 AN ITERATIVE METHOD TO CONSTRUCT A SET-MAX POLICY
We now present and analyze an iterative algorithm solve problem 6 We begin by defining the worst case or adversarial reward associated with the generalized SMP policy:
Definition 5 (Adversarial reward for an SMP). Given a set of policies II", we denote by w
arg min Bg VI1" w the worst case reward w.r.t the SMP "I" defined in (5) In addition, the value
of the SMP w.r. to WSM is defined by SSMP miilwwes UTI", .w'
SMMP
We are interested in finding a of policies II such that the performance of the resulting SMP will be optimal w.r.t its adversarial reward Wij" This leads to reformulation of (6 as max-min-max optimization for discovering robust policies:
arg max SMP = arg max min IIC
SMP [l "II",. w = arg max min max &p² w.
II IIl ie (E(,....))
The order in which the maximizations and the minimization are performed in (7) is important. (i) The inner maximization over policies (or SFs), by the SMP, is performed last. This means that, for a fixed set of policies II" and a fixed reward SMP selects the best policy in the set. (it) The minimization over rewards happens second, that is, for a fixed set of policies 11", we compute the value of the generalized SMP SMP (:: w) for any reward w, and then minimize the maximum of these values. (tii) Finally, for any set of policies, there is an associated worst case reward for the SMP, and we are looking for policies that maximize this value.
Algorithm 1 SMP worst case policy iteration
Initialize: Sample w N(O IIo
{ x' t arg max w >6" t
SMP 111
repeat
II +- IT 1 + (='}
W SMP
+ solution to R
II
+ solution of the RL task SMP
TTH"
t 1
until
SMP VII
SMP return II
The inner maximization (i) is simple: it comes down to computing dot-products sb² w, i 2. n. and comparing the resulting values. The minimization problem (ti) slightly more complicated, but fortunately easy to solve. To see this, note that this problem can be rewritten as:
SMP W ITS = arg min max {w 26b
W " s.t. ||w| | 1 S 0.
WE32 (E[L......
Eq. (8) is a convex optimization problem that can be easily solved using standard techniques, like gradient descent, and off-the-shell solvers (Diamond & Boyd 2016 Boyd et al. 2004). We note that the minimizer of Eq. (8) is function of policy set. As a result, the set forces the worst case reward to make a trade-off - it has to "choose" the coordinates it "wants" to be more adversarial for. This tradc-off is what encourages the worst case reward to be diverse across iterations (w.nt different sets). We note that this property holds since we are optimizing over 18 but it will not necessary be the case for other convex sets. For example, in the case of Bo the internal minimization problem in the above has single solution a vector with -1 in all of its coordinates.
The outer maximization problem (iit) can be difficult to solve if are searching over all possible sets of policies II"" C II. Instead, we propose an incremental approach in which policies x' are successively added to an initially empty set II This is possible because the solution SMP of 88 gives rise to a well-defined RL problem in which the rewards are given by (w a, s') = SMM a') This problem can be solved using any standard RL algorithm. So, once we have a solution w-SMP for we solve the induced RL problem using any algorithm and add the resulting policy -=+ to T (or, rather, the associated SFs *b*+)).
Algorithm hass a step by step description of the proposed method. The algorithm is initialized by adding policy n² that maximizes random reward vector w to the set 119, such that 112 = {T²), At each subsequent iteration the algorithm computes the worst case reward SMP "I'' w.r.t to the current set I by solving (). The algorithm then finds policy r'+1 that solves the task induced by wSMP If the value of - w.r.t SMM is strictly larger than #SMP the algorithm continues for another iteration, with -++1 added to the set. Otherwise, the algorithm stops. As mentioned before, the set of policies II' computed by Algorithm eean also be used with GPI. The resulting GPI policy will do at least as well as the SMP counterpart on any task w (Lemma 2); in particular, the GPI's worst-case performance will be lower bounded by Vil"
5

---

Published as a conference paper at ICLR 2021
4.1 THEORETICAL ANALYSIS
Algorithm I produces a sequence of policy sets II', II,, The definition of SMP guarantees that enlarging set of policies always leads soft improvement in performance, o II UII >
We now show that the improvement in each iteration of our algorithm is in fact strict.
Theorem (Strict improvement). Let IT,, IT...... ..... IIo be the sets of policies constructed by Algorithm We have that the worst-case performance of the SMP induced by these set strictly improving each iteration, that is: UI!--1 > "ill' Furthermore, when the algorithm stops, there does not exist single policy 7*+1 such that adding 11' will result in improvement: 1 x s.t. "I1 +[1++(+) > o
In general we cannot say anything about the value of the SMP returned by Algorithm However, in some special cases we can upper bound it. One such case is when the SF's lie in the simplex.
Lemma (Impossibilityy result). For the special case where the SFs associated with any policy are in the simplex, the value of the SMP w.r. the worst case reward for any set of policies is less than or equal to - 1/vd. In addition, there exists an MDP where this upper bound is attainable.
One example where the SFs are the simplex is when the features & are "one-hot vectors", that is, they only have one nonzero element. This happens for example in a tabular representation, in which case the SF's correspond to stationary state distributions. Another example are the features induced by state aggregation, since these are simple indicator functions associating states to clusters (Singh et al.) 1995). We will show in our experiments that when state aggregation is used our algorithm achieves the upper bound of Lemma 3 in practice.
Finally, observe that not all the policies in the set II' are needed at each point in time, and guarantee strict improvement even if we remove the "inactive" policies from II', as we show below.
Definition 6 (Active policies). Given a set of policies 11", and an associated worst case reward SMP SMP the subsel of active policies II, (II)) are the policies in Il that achieve UT w.rl SMP (11") = { E II zb"
SMP
SMMP
WII
"11"
Theorem (Sufficiency of Active policies). For any set of policies 11", SMP (II( achieves the same
value w.r.f the worst case reward as SMP that is, ViI"
SMP (I")"
Theorem 2 implies that once we have found II1 we can remove the inactive policies from the set and still guarantee the same worst case performance. Furthermore, we can continue with Algorithm| [ to find the next policy by maximizing WSMP and guarantee strict improvement via Theorem This is important in applications that have memory constraints, since allows us to store fewer poticies.
EXPERIMENTS
We begin with 10 x 10 grid- world environment (Fig. place the grid (marked in a black color) and gains/loses reward from collecting items (marked with white color). Each item belongs to one of d 1 classes (here with d = 5) and is associated with a marker: 8, O, X. Y.H. In addition, there is one "no item" feature (marked in gray color). The features are one-hot vectors, i.c., for i E [1,d- - 1], (s)s equals one when item is in state s and zero otherwise (similarly (s) equals one when there no item in state s). The objective of the agent to pick up the "good" objects and avoid "bad" objects, depending on the weights of the vector w.
I(d) where the agent starts in random
SMP for d 5. At each iteration In Fig. ((a) we report the performance of the SMP SMP w.r. w T!' (x-axis) of Algorithm] we train policy for 5 10 steps to maximize w We then compute the SFs of that policy using additional 10 steps and evaluate it w.n.t w-MP
As we can see, the performance of SMP strictly improves as we add more policies to the set (as we stated in Theorem IT.. In addition, we compare the performance of SMP with that of GPI, defined on the same sets of policies (II') that were discovered by Algorithm | Since we do not know how to compute w TT
(the worst case reward for GPI), we evaluate GPI w.r.t w I1 (the blue line in Fig. ((a).
Inspecting Fig. ((a) we can that the GPI policy indeed performs better than the SMP Lemma indicates. We note that the blue line (in Fig. ((a)) does not correspond to the worst case performance of the GPI policy. Instead,
get good approximation for because have that: wSMM

---

Published as a conference paper at ICLR 2021
-315
30-1
-264
20
<iteratoon
(a) SMP vs. GPI
(b) Baselines
(C) SFs
(d) Trajectories
Figure I: Experimental results in 2D grid world. Fig. I(a) presents the performance of the SMP and GPI w.r. the worst case reward. Fig. l(b) compares Algorithm| | with two baselines, where we show the worst case performance, relative to the upper bound, in logarithmic scale. Fig. [(c) visualizes the SFs of the policies in the set and Fig. ((d) presents trajectories that were taken by different policies.
SMP) W 11" (-"""* GPI) S W "1 (MTT
W-MP 3/( GPI) i.e., the worst case performance of GPI (in the middle) is guaranteed to be between the green and blue lines in Fig. T(a) This also implies that the upper
GPI
bound in Lemma 3 does not apply for the blue line.
We also compare our algorithm
baselines in Fig. I(b) (for d 10): (i) Orthogonal
iteration t we train policy x' to maximize the reward w = e' (a vector of zeroes with a one on the t-th coordinate) such that a matrix with the vectors w in its columns forms the identity matrix; (ii) Random: at iteration & we train policy n' to maximize reward w (ō, I), i.e. we sample a vector of dimension d from Normal Gaussian distribution and normalize it to have norm of 1. While all the methods improve as we add policies to the set, Algorithm cllerrl outperforms the baselines.
In Fig. I(c) and Fig. I(d) we visualize the policies that were discovered by Algorithm I Fig. [(c) presents the SFs of the discovered policies, where each row (color) corresponds to different policy and the columns correspond to the different features. We do not enumerate the features from 1 to d, but instead we label them with markers that correspond to specific items (the x-axis labels). In Fig. I(d) we present a trajectory from each policy. We note that both the colors and the markers match between the two figures: the red color corresponds to the same policy in both figures, and the item markers in Fig. [(d) correspond to the coordinates in the x-axis of Fig. I(c)
Inspecting the figures we can see that the discovered policies are qualitatively diverse: in Fig. [(c) we can see that the SFs of the different policies have different weights for different items, and in
Fig. [[d] we can see that the policies visit different states. For example, we
that the teal policy
has larger weight for the no item feature (Fig. [(e]] and visits only no-item states (Fig. [(d) and
that the green policy has higher weights for the "Y" and 'X" items (Fig. [(c) and indeed visits them
(Fig. I(d).
0.32
0.08
# pelicies
0.06
0.04
0.00
0.00
(a) SMP vs. GPI, d=5
(b) SMP vs. GPI, d=5
Figure 2: Experimental results with regularized w.
Finally, in Fig. we compare the performance of our algorithm with that of the baseline methods over test set of rewards. The only difference is in how we evaluate the algorithms. Specifically, sampled 500 reward signals from the uniform distribution over the unit ball. Recall that at iteration t each algorithm has set of policies IT' so evaluate the SMP defined each one of the test rewards. Then, for each method, we report the mean value obtained over the test rewards and repeat this procedure for 10 different seeds. Finally, we report the mean and the confidence interval over the seeds. Note that the performance in this experiment will necessarily be better than the in Fig. ((a) because here we evaluate average performance rather than worst-case performance. Also note that our algorithm was not designed to optimize the performance on this "test set", but to optimize the performance w.r.f the worst case. Therefore it is not necessarily expected to outperform the baselines when measured this metric.
this set, "II w.r.
7

---

Published as a conference paper at ICLR 2021
Inspecting Figure Fig. 2(a) can see that our algorithm (denoted by SMP) performs better than the two baselines. This is bit surprising for the reasons mentioned above, and suggests that optimising for the worst case also improves the performance w.r.t the entire distribution (transfer learning result). At first glance, the relative gain in performance might seem small. Therefore, the baselines might seem preferable for computing the worst case reward is small compared to finding the policy the maximizes it, and therefore the relative cost of the added complexity is low.
some users due to their simplicity. However, recall that the computational cost
The last observation suggests that we should care about how many policies are needed by each method to achieve the same value. We present these results Fig. 2(6) Note that we use exactly the same data as in Fig. 2(a) but present it in a different manner. Inspecting the figure, we can see that the baselines require more policies to achieve the same value. For example, to achieve value of 0.07, the SMP required policies, while the baselines needed 4; and for value of 0.1 the SMP required 4 policies while the baselines needed 7 and 9 respectively.
Deep Control Suite. Next, we conducted a set of experiments in the DM Control Suite (Tassa et al. 2018). We focused on the setup where the agent is learning from feature observations cor- responding the positions and velocities of the "body" in the task (pixels were only used for visualization). We considered the following six domains: 'Acrobot', 'Cheetah', 'Fish', 'Hopper', 'Pendulum', and 'Walker', In each of these tasks we do not use the extrinsic reward that is defined by the task, but instead consider rewards that are linear in the observations (of dimensions 6, 17, 21, 15, 3, and 24 respectively). At each iteration of Algorithm 1 we train a policy for 2 10th steps using an actor-critic (and specifically STACX ZZhhavy et al. 2020db) maximize WT add it to the set, and compute a new w SMP 11
-4.4
Acmbet
Cheersh
Fil
-375
Hooper
Perduum
Walker
Expaaved Vollnori Hoaper
colahee Virtinent
Esplanss Var 209 Walker
Pandilum
polcic
poliddsa theast
po
Lo VantanstL
Expa Varanon
(a) Convergence
(b) Diversity
Figure 3: Experimental results in Deepmind Control Suite.
presents the performance of SMP in each iteration w.I.t w As we can see, our algorithm is indeed improving each iteration. In addition, we present the average number of active policies (Definition in each iteration with bars. All the results are averaged over 10 seeds and presented with 95% Gaussian confidence intervals. Fig. ((b) presents the SFs of the active policies at the end of training (the seed with the maximum number of active policies was selected). We perform PCA dimensionality reduction such that each point in the scatter plot corresponds the active policies. We also report the variance explained by PCA: values close to indicate that the dimensionality reduction has preserved the original variance. Examining the figures we can see that algorithm is strictly improving (as Theorem predicts)) and that the active policies in the set indeed diverse; we can also see that adding more policies is correlated with improving performance.
Fig. 3(a)
the SFF of one of
Finally, in Fig. 4(a) Fig. 4(b) and Fig. 4C) we visualize the trajectories of the discovered policies in the Cheetah, Hopper and Walker environments. Although the algorithm was oblivious to the extrinsic reward of the tasks, it was still able to discover different locomotion skills, postures, and even some "yoga poses" (as noted by the label we gave each policy on the left). The other bodies (Acrobot, Pendulum and Fish) have simpler bodies and exhibited simpler movement in various directions and velocities, e.g. the Pendulum learned to balance itself up and down. The supplementary material contains videos from all the bodies.
6 CONCLUSION
We have presented an algorithm that incrementally builds a set of policies to solve a collection of tasks defined as linear combinations of known features. The policies returned by our algorithm can be composed in multiple ways. We have shown that when the composition is SMP its worst-case
8

---

Published as a conference paper at ICLR 2021
performance the set of tasks will strictly improve each iteration of our algorithm. More generally. the performance guarantees we have derived also serve as a lower bound for any composition of policies that qualifies as a SIP. The composition of policies has many applications in RL, such as for example to build hierarchical agents to tackle sequence of tasks in a continual learning scenario. Our algorithm provides simple and principled way build diverse of policies that can be used these and potentially many other scenarios.
ACKNOWLEDGEMENTS
We would like to thank Remi Munos and Will Dabney for their comments and feedback on this paper.
lrad Stats
Run Torwed Walk Sandoen Soandng
I
(a) Cheetah
Ove Stunsh
4
J
4
A
A
A
A
A
A
Hour Stand
(b) Hopper
Sata
PAAM
Cual
(c) Walker
Figure 4: Experimental results in Deepmind Control Suite.

---

Published as a conference paper at ICLR 2021
REFERENCES
Pieter Abbeel and Andrew Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp- 1. ACM, 2004.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances in neural information processing systems, pp. 4055 4065-4065, 2017.
Andre Barreto, Diana Borsa, John Quan, Tom Schaul, David Silver, Matteo Hessel, Daniel Mankowitz, Augustin Zidek, and Remi Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. International Conference on Machine Learning, pp. 501- 510. PMLR, 2018.
André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. learning with generalized policy updates. Proceedings of the National Academy of Sciences, 2020.
Fast reinforcement
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Steven Diamond and Stephen Boyd. CVXPY: A
Python- modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
G. Dietterich. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13:227-303, 2000.
Laurent BI Ghaoui and Hervé Lebret. Robust solutions to least-squares problems with uncertain data. SIAM Journal on matrix analysis and applications, 1035-10035 1997.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:1802.06070, 2018.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1 3(1-2):95-100 1956.
Dan Garber and Elad Hazan. A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. arXiv preprint arXiv:1301.4660 2013.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv I. .07507, 2016.
preprint /61
Christopher Grimm, Irina Higgins, Andre Barreto, Denis Teplyashin, Markus Wulfmeier, Tim Her- tweek, Raia Hadsell, and Satinder Singh. Disentangled cumulants help successor representations transfer to new tasks. arXiv preprint arXiv: 10866, 2019.
Jacques Guélat and Patrice Marcotte. Some comments on wolfe's 'away step'. Mathernatiaal Programming, 35(1):110-119) 1986.
Steven Hansen, Will Dabney, Andre Barreto, Tom Van de Wiele, David Warde-Farles and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. arXiv preprint 1906.00000000000 2019.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. 2013.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
Martin L Puterman. Markov decision processex: discrete stochastic dynamic programming. John
Wiley& & Sons, 1984.
Stuart J Russell and Andrew Zimdars. Q-decomposition for reinforcement learning agents. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 656-663, 2003.
Satinder P Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. In Advances in neural information processing systems, pp. 361-368, 1995.
Nathan Sprague and Dana Ballard. Multiple-goal reinforcement learning with modular sarsa (0). 2003.
10

---

Published as a conference paper at ICLR 2021
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-11) 1999a.
Richard S. Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 11: 181-211, August 1999b. doi:
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint arXiv: 00690, 2018.
Philip Wolfe. Convergence theory in nonlinear programming. Integer and nonlinear programmingg pp. 1-36, 1970.
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-423 2012.
Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and lasso. In Advances in neural information processing systems, pp. 1801-1808, 2009.
Tom Zahavy, Alon Cohen, Haim Kaplan, and Yishay Mansour. Apprenticeship learning via frank- wolfe. AAAI, 2020, 2020a.
Tom Zahavy, Alon Cohen, Haim Kaplan, and Yishay Mansour. Average reward reinforcement learning with unknown mixing times. The Conference on Uncertainty in Artificial Intelligence (UAI), 2020b.
Tom Zahavy, Avinatan Hasidim, Haim Kaplan, and Yishay Mansour. Planning in hierarchical reinforcement learning: Guarantees for using local policies. In Algorithmic Learning Theory, pp. 906-934, 2020c.
Tom Zahavy, Zhongwen Xu, Vivek Veeriah, Matteo Hessel, Junhyuk Oh, Hado van Hasselt, David Silver, and Satinder Singh. A self-tuning actor-critic algorithm. Advances in neural information processing systems, 2020d.

---

Published as a conference paper at ICLR 2021
A PROOFS
Lemma 1. Let Th"" be SMP defined in ( and let क S W P(A) be any generalized
policy. Then, given set of n. policies II is SIP and only of 2 ii for all W.
SMP
Proof. We first show that the fact that æ is SIP implies that Vir w
2
11 w
for all w. For any
E W, we have
Vw for all n' E IIo
(SIP in Definition 2
"11"
max w < me......
SMP
w
We now show the converse:
SMP UTT" w
UTT ww
max w iE(I......]
(SMP as in Definition 3
2 w for all n' II..
GPI Lemma 2. For any reward E W and any of policies IT", have that "i
SMP "II
Proof. We know from previous results the literature Barreto et al. (017)) that QGPI (s, @* (s,a) a) for all (s,4) E S A and any π E IT"
Thus, we have that Vs E S:
GPI 111.
(8)
Qir'wws, GPI
max
(s,
RETT",
max E. Ea (Q (s,a)) a)]
a aEll
max U (s)
wEll"
"TT" w (8),
where the second inequality is due to Jensen's 's inequality. Therefore:
GPI UII w (s) 2 VII" w
SMP
(s)
Ep P11" (s)] ED [ Vir" (s)]
GPI
SMP
0TT" w 2 UTI w
SMP
Lemma (Impossibility result). For the special case where the SFs associated with any policy are in the simplex, the value the SMP w.r. the worst case reward for any set of policies less than or equal -
/ Vd. In addition, there exists an MDP where this upper bound attainable.
12

---

Published as a conference paper at ICLR 2021
Proof. For the impossibility result. we have that
max min
SMP fllx.w
min max vi weB, sell
(9)
min max (((T) - we sell
min max ((xx).0
(10)
weB2 WEA"
min max W2 wEB2 1
(11)
(12)
Vd
The equality in Eq. (9) follows from the fact that is set of all possible policies and therefore the largest possible subset (the maximizer of the first maximization). In that case the second maximization (by the SMP) is equivalent to selecting the optimal policy the MDP. Notice that the order of citimmiattoo-mmnnmmzzene
here is in the reversed when compared to AL, i.e., for each reward the SMP chooses the best policy in the MDP, while in AL the reward is chosen to be the worst possible w.r.t any policy. The inequality in Eq. (10) follows from the fact that increase the size of the optimization set in the inner loop, and the equality Eq. (12) follows from the fact that maximizer in the inner loop puts maximal distribution on the largest component of w.
Feasibility. To show the feasibility of the upper bound in the previous impossibility result we give an example of an MDP in which set of d policies achieves the upper bound. The d policies chosen such that their stationary distributions form an orthogonal basis.
1 Vd
min 22
SMP "I
min wEB, (E("......dd))
min wEB, WEA
W
(13)
which follows from the fact that the maximization over the simplex is equivalent to a maximization pure strategies.
Lemma (Reformulation of the worst-case reward for an SMP). Let V== be n successor feature vectors. Let w be the adversarial reward, w.n. the SMP defined given these successor features. That is, w is the solution for
arg min
{w v0 ...., w } vE(2.....n
max
8.L.
||||| - 50
(14)
Let w be the solution to the following problem E ml.....m]
arg min
w z/²²
s.t.
w 2 1 $ 0
w (1b5) r5t) 50
(15)
Then, w" = arg min; w..
Proof. For any solution w² to Eq. (8) there is some policy in the set that is one of its maximizers. Since it the maximizer w.r.t w", Its value w.r.t w" is bigger or equal to that of any other policy in the set. Since we are checking the solution among all [I. one of them must be the solution.
Theorem 2 (Sufficiency of Active policies). For any set of policies II" SMP
(I. achieves the same
value w.r.t the worst case reward as SMP that is, oif = I1, (II")*
SMP
Proof. Let n ( Denote by J a subset of the indices [1...., n| that corresponds to the indices of the active policies such that II, (II") = {Tibjes' We can rewrite problem Eq. (14) as follows:
minimize
7
S.t.
7 gid
i= 1, 1,...,m
(16)
| < 1.
13

---

Published as a conference paper at ICLR 2021
Let (y", -w=) be any optimal points. The set of inactive policies & J satisfy 7 w vf. Since these constraints are not binding we can drop them from the formulation and maintain the same optimal objective value, i.e.
minimize s.t.
7
7 2 vi jEJ J |
(17)
1
has the same optimal objective value, DMM the full problem. This in turn can be rewritten
minimize
max w 1/5
(18)
s.t.
| S 1,
with optimal value SMP (I1)) which is therefore equal to U1l"
Lemma 5 (Is is binding).
Proof. Denote by ú a possible solution where the constraint || < 1 is not binding, i.c., (/|=|| <
1, k 0). In addition, denote the primal objective for úi by ma..g (t v²)). To prove the lemma, we are going to inspect two cases: (i) è 2 0 and (ii) ú < 0. For each of these two cases we will show that there exists another feasible solution ú that achieves lower value for the primal objective (w < t), and therefore úù is not the minimizer.
For the first case 2 0, consider the vector
(-1,- 1)/Va. (-1/-
is feasible solution to the problem, since || 1. Since all the SFs have positive coordinates, we have that if they are not all exactly 0, then the primal objective evaluated at ö is stictly negative: ma
w v/1 ...., / "/ < O.
We now consider the second case of ú < O. Notice that multiplying v by positive constant e would not change the maximizer, i.c., arg max,e (cw 3 = arg mI... { (i
vb'). ). Since é < 0, means that ui zl:l (c 1/|| [) feasible solution and better minimizer than w. Therefore ab is not the minimizer.
We conclude that the constraint is always binding, i.e. ||w|| 1, > 0.
Theorem (Strict improvement). Let ITI IT be the sets of policies constructed by Algorithm We have that the worst-case performance of the SMP induced by these set is strictly improving in each iteration, that is: +SMP > SMM Furthermore, when the algorithm stops, there does not exist a single policy r11 such that adding to IT's will result in improvement: 7 11+1 E II s.I. SMM
(m)) > SMP
"T1
Proof. We have that
"TT
SMP min max 4/ w < max 2b WEB2 Pe
SMP De WIT+
S
max 2b DEV 11++1 = SMP
W
SMP
U11++1
(19)
The first inequality true because we replace the minimization over w with SMP inequality is true because we add a new policy to the set. Thus, we will focus on showing that the first inequality is strict. We do it in two steps. In the first step, we will show that the problem minwee, maXper 1b has unique solution wł. Thus, for the first inequality to hold with equality it must be that SMP r0+11 SMP > SMP hence contradiction.
11: and the second
*I wSMPP, However, we know that, since the algorithm did not stop,
We will now show that minweB, max &b w has a unique solution. Before we begin, we refer the reader to Lemma 4 and Theorem 2 where reformulate the problem to form that is simpler to analyze. We begin by looking the partial Lagrangian of Eq. [7p:
L(w, Y, K, A) = Ay(1 (2 7) < <6(11011 1).
JEJ
14

---

Published as a conference paper at ICLR 2021
The variable x 2 0 is associated with the constraint || 1. Denote by (A*, (²) any optimal dual variables and note that by complementary slackness we know that either K²* > and | 2l2 or K= = 0 and ||ll|2 < 1. Lemma above, guarantees that the constraint is in fact binding only solutions with K* > 0 and ||w||2
are possible solutions. Notice that this is correct due to the fact that the SFs have positive coordinates and not all of them are (as in our problem formulation).
Consequently we focus on the case where k* > under which the Lagrangian is strongly convex in w, and therefore the problem
min L(w, 7, x*) Myy?
has a unique solution. Every optimizer of the original problem must also minimize the Lagrangian evaluated at an optimal dual value, and since this minimizer is unique, it implies that the minimizer of the original problem is unique (Boyd al. 2004, Sect. 5.5.5).
For the second part of the proof, notice that the new policy x++1 does not achieve better reward w.r.t VI1' than the policies in IIO then we have that:
SMP SMP min max (T()) w S max (TT) WIF' U
max (TT)
SMP W II
SMP
"II'
wEB2 #E|l++1
+E
WEll
SMP thus, it is necessary that the policy n²*1 will achieve better reward w.r.t ITF improvement.
to guarantee strict
B AL
In AL there is no reward signal, and the goal is to observe and mimic an expert. The literature on AL is quite vast and dates back to the work of (Abbeel & Ng 2004), who proposed a novel framework of trajectories that used to estimate the SFs of
for AL. In this setting, an expert demonstrates its policy gg, denoted by v.. The goal is to find policy ग, whose SFs are close to this estimate, and hence will have similar return with respect any weight vector w, given by
arg max min a wEB,
(15= B)
arg max
1|gbT vf
arg min 1| 11.
(20)
The projection algorithm (Abeel & Ng 2004) solves this problem in the following manner. The algorithm starts with an arbitrary policy To and computes its feature expectation vo At step t, the reward function is defined using weight vector wa E _t and the algorithm finds a policy Te that maximizes it, where &6 is a convex combination of SFs of previous (deterministic) policies th E aypb In order to get that || f <
the authors show that it suffices to run the
algorithm for = 0 ((1)))()))))))))000)00 (1-7)222 log( (1-2))) iterations.
Recently, it was shown that this algorithm can be viewed as a Frank- method, also known as the Conditional Gradient (CG) algorithm (Zahavy et al.) (020a)). The idea is that solving Eq. (20) can be seen as a constrained convex optimization problem, where the optimization variable the SFs. the objective is convex, and the SFs are constrained to be in the SFs polytope X., given as the following convex set:
Definition 7 (The SFs polytope). K. K= (a: E any 2 E. 0; 1, 1, m mm)
In general, convex optimization problems can be solved via the more familiar projected gradient descent algorithm. This algorithm takes step in the reverse gradient direction žτ+11 Iz + (xz), and then projects 21+1 back into XC to obtain Ft+1- However, in some cases, computing this projection may be computationally hard. In our case, projecting into K. is challenging since has |A|lS| vertices (feature expectations of deterministic policies). Thus, computing the projection explicitly and then close to this projection, is computationally prohibitive.
finding whose feature expectations
The CG algorithm (Frank & Wolfe 1956) (Algorithm 2 avoids this projection by finding a point Yt E IC that has the largest correlation with the negative gradient. In AL, this step is cquivalent to finding policy whose SFs has the maximal inner product with the current gradient, i.e., solve an MDP whose reward vector is the negative gradient. This is standard RI. (planning) problem and
15

---

Published as a conference paper at ICLR 2021
can be solved efficiently, for example, with policy iteration. We also know that there exists least one optimal deterministic policy for it and that PI will return solution that is deterministic policy (Puterman 1984).
Algorithm 2 The CG method Frank & Wolfe (1956)
1: Input: convex set K., convex function h, learning rate schedule oz-
2: Initiation: let xig E K.
3: for = 1,..,, do
4: Vt arg m (Z
5: Zt = (1 01) + Ox3
6: end for
For smooth functions, CG requires ((1/12) iterations to find an s-optimal solution to Eq. 220). This gives logarithmic improvement on the result of (Abbeel & Ng, 2004). In addition, was shown in (Zahavy et al.) 2020a) that since the optimization objective is strongly convex, and the constraint set a polytope, it possible to use variant of the CG algorithm, known as Away steps conditional gradient (ASCG) (Wolfe 1970). ASCG attains a linear rate of convergence when the set is a polytope (Guélat & Marcotte 1966 Garber & Hazan 2013 Jaggi 2013), i.e., converges after O (log(1/e) iterations. See (Zahavy et al. 2020a) for the exact constants and analysis.
There are some interesting relations between our problem and AL with "no expert", that is, solving
arg min
[
(21)
31
In terms of optimization, this problem is equivalent to Eq. (20). and the same algorithms can be used to solve them.
Both AL with "no expert" and our algorithm can be used to solve the same goal: achieve good performance w.r.t the worst case reward. However, AL concerned with finding single policy, while our algorithm explicitly designed to find set policies. There is no direct connection between the policies that are discovered from following these two processes. This is because the intrinsic rewards that are maximised by each algorithm are essentially different. Another way think about this is that since the policy that is returned by AL is a mixed policy, its goal is to return a set of policies that are similar to the expert, but not diverse from one another. From a geometric perspective, the policies returned by AL are the nodes of the face in the polytope that is closest to the demonstrated SFs. Even more concretely, if the SFs of the expert are given exactly (instead of being approximated from trajectories), then the AL algorithm would return a single vertex (policy). Finally, while a mixed policy can be viewed as composition of policies, it is not SIP. Therefore, it does not encourage diversity in the set.
C REGULARIZING W
In this section we experimented with constraining the set of rewards to include only vectors wo whose mean is zero. Since we are using CVXPY (Diamond & Boyd (016) to optimize for w (Eq. (8), this requires adding simple constraint i- W/ 0 the minimization problem. Note that constraining the mean to zero does not change the overall problem qualitatively, but does potentially increase the difference in the relative magnitude of the elements in w. Since it makes the resulting w's have more zero elements, i.e., it makes the w's 's more sparse, it can also be viewed as a method to regularize the worst case reward. Adding this constraint increased the number of w's (and corresponding policies) that made a difference to the optimal value (Definition [5). To see this, note that the green curve in Fig. converges to the optimal value in 2 iterations while the the green curve in Fig. I(a)) does so in 3 ilerations. As result, the policies that were discovered by the algorithm are more diverse, To see this observe that the SFs in Fig. (bb) are more focused on specific items than the SFs in Fig. [[c] In Fig. 5(c) and Fig. ((d) we verified that this increased diversity continues to be the case when we increase the feature dimension d.
d
16

---

Published as a conference paper at ICLR 2021
-0.5
valae
0.00
boyles
Chiecs
SMP vs. GPI, 5=5
(b) SFs, d=5
(c) SMP GPI, d=9
(d) SFs, d=9
Figure 5: Experimental results with regularized w.
17


Reviews:
[{"review_id": "xysqyfLEoyN", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: the authors propose to solve a family of related tasks with shared features and rewards that are linear in the features and equivalent up to scaling factor. The main contributions are as follows:\n- a novel framework for analyzing a broad family of generalized policies (policies that are generalized to arbitrary rewards in the task space), including the concept of a set improving policy (SIP), and providing two practical examples that fit this definition, namely the worst case set max policy (SMP) and the well known and studied generalized policy iteration (GPI). It is shown that it is always better to use GPI over SMP, making it an instance of SIP. \n- a novel iterative method for building a policy library for solving the worst-case reward, formulated as a convex optimization problem, along with policy improvement guarantees, an informed method for stopping the algorithm, and the ability to remove redundant policies (termed inactive policies)\n- an empirical evaluation that connects the proposed method to learning a policy library with a diverse set of skills. The theoretical results are also validated experimentally, on a grid world example and control problems from Deepmind.\n\nPros:\n- the work is of very high quality, all motivations seem sound and the theoretical results seem correct\n- the idea of active task selection for building the policy library is very interesting, and it is surprising that this has not been considered within the framework of Barreto et al., 2017 so far\n- the work could be of significance in the apprenticeship/curriculum/meta-RL community, and it is nice to see a more theoretical treatment of this topic\n\nQuestions:\n- If my understanding is correct, the authors use the orthogonal and random basis to propose w at each iteration, but evaluate the resulting SMP policies with respect to the optimized rewards from (8). I am wondering if this is a fair evaluation for the baselines, given that the policies are always evaluated on $w_t^{SMP}$, or whether a new set of tasks (a proper \"test\" set) sampled from B (the standard ball) should be used to fairly compare (8) with the baselines? This would really test the generalization of the method on new instances as well, and is also often standard in the literature for evaluating the performance of a learning policy set. In other words, how robust is the resulting policy library to solving new task instances not previously seen before?\n- Also, one thing that could explain the poor performance of the orthogonal baseline is that the reward seems to be quite sparse when most of the basis elements are set to zero (in the one-hot phi case, wouldn't they be almost always uninformative?) In this case, a more suitable baseline that directly targets diversity could be defined as finding the $w_1, w_2 \\dots w_T$ such that their coverage of the task space is maximized under some prior belief over w (e.g. the standard ball). If I am not mistaken, this problem is similar to the maximum coverage or voronoi tessellation problem, which could be solved in advance and then deployed. (e.g. Arslan, 2016)\n- Performing well relative to the worst-case performance seems reasonable so that the agent does not do poorly on any one task, but it could also be overly conservative. That is, could there be situations where optimizing the worst case leads to the agent not successfully completing the desired objective (e.g getting stuck on locally optimal solution)? \n- at each iteration when the new optimal policy is learned with respect to $w_\\Pi^{SMP}$, is the idea of SMP or GPI and previously learned policies used to help learn this new policy, or is it learned entirely from scratch (e.g. by simple epsilon-greedy)?\n\nMinor comments:\n- the legends in Figure 1a/b and the axis font in Figure 1c could be increased, same with Figure 2\n- is the $\\max_i$ necessary in equation (8)?\n\nOverall, this works proposes a coherent theory for policy improvement, that also leads to useful implementation and interesting empirical insight (and cool visualizations). It can often be hard to obtain all of these at once.\n\nArslan, Omur, and Daniel E. Koditschek. \"Voronoi-based coverage control of heterogeneous disk-shaped robots.\" 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016.", "extra_scores": {}, "extra_text": {}}, {"review_id": "o7lbMx2EyM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This was a well-written, and interesting paper to read!\n\nI went over the paper many times, and I am still failing to see the use case for such an approach. I have some questions and comments that need some clarification for me to properly evaluate the submission. Please, take the time to answer the following, so my review can better reflect the paper.\n\n1 - The theory developed in the paper relies on reward functions that can be represented as linear combinations of the features of the MDP. This seems to be restrictive, and intuitively, this would be the exception rather than the rule.\nWhat class of problem could be modeled under this restriction?  In many problems, there is no linear reward function that would allow an agent to achieve the desired behavior, so these techniques would not be helpful. What are some practical setting where this approach would be beneficial?\n\n2 - Lemma 3... this statement is putting an upper-bound on the worst case performance, but since the paper focuses on improvement of worst case performance, it would be beneficial to have a lower bound, but an upper bound doesn't seem too useful.   Essentially, this lemma is saying \"I can guarantee that the worst-case won't be better than this upper bound, and that for some MDP with linear reward function this upper bound is attainable.\" The problem is that we don't know what that MDP is, how likely it is that we would find it, and this lemma allow for the worst case performance to be arbitrarily bad.\nI don't think this lemma, as is, is particularly useful.\n\n3 - On the experimental section, I think there's a baseline that should be included that's missing. What if we have 1 policy and add a task descriptor or extra features to the features vector that corresponds to the type of task? How would the performance empirically compare?\n\n4 - In the learning curves for fig 1.a or 2.a, what does \"value\" (y-axis) represent? If it the return of the agent after training? If so, is it using the extrinsic reward or the transformed linear reward described in line 5 of \"DeepMind Control Suite\"?\n\n5 - Based on equation 4, for definition 2 of SIP. There is always a trivial set improving policy, right? That would correspond to picking the policy for max(v^i_w).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "M0--Zyjkn1f", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Given a rewardless environment MDP, the authors want to find a set of policies for the worst case reward function. Their process involves two steps: first to select the right set of policies and second to combine them to generate a new policy. The policy selection is made with the only goal to maximize the expected return of highest achieving policy of the set in the worst-case reward function (Equation (7)).\n\nUnfortunately the submission suffers from several serious weaknesses:\n- although the reward-set setting is quite general: within a ball in the feature space, it includes very unnatural cases that make the problem artificially too complex, in my opinion. Indeed, usually, one should consider that the worst case reward function r_min in a reward function family R is the one that is minimal in every state-action-state : r_min(s,a,s') \\eqdef \\inf_{r\\in R} r(s,a,s'). In this case, the solution to equation (7) is straightforwardly the single policy that optimizes the return on r_min. Please discuss more the interest of considering r=\\psi.w with w in a ball (it implies that if some feature takes sometimes positive and sometimes negative values, there is not clear w_min, and therefore no clear r_min).\n- besides ensuring that SMP performance is at least achieved, could the authors elaborate a bit more on why optimize the policy set according to SMP?\n- the authors never theoretically consider combining the policy, apart for stating that a good combination of policy should achieve higher performance than the best of the policy set. For clarity, I would recommend to either stick to the simplest setting of choosing the best policy given a reward function, or to consider policy election that take into account the way the policies are going to be used/combined.\n- the formalization is messy and sometimes unnecessarily confusing. Please see the series of comments below:\n- Definition 3 and Eq. 5: the argmax returns an index, not a policy. (minor)\n- v is not a value, it's a policy performance. It has been very confusing to me, as it led me to think for too long that Lemma 1 was false: choosing the policy that maximizes the value in each state is a form policy improvement that may lead to policies that are stricty better than the best of the policies. Also, I would not use the notation v, that is usually the value-function: a function of the station and not the policy performance like here, i.e. the expectation of the value-function over the initial states distribution. (easy to fix)\n- Definition 4: the argmax returns an action not a policy. (minor)\n- Equation 7: \\Pi lives in? Also instead of max_{\\psi\\in...} \\psi.w, I would use max_{i\\in [n]} \\psi^i.w. (minor)\n- Lemma 3: what is d? (minor)\n- I am still not understanding Definition 6 and Theorem 2. How do we know that the worst-case reward is unique? If we keep only the policies that achieve max performance on \\overline{w}, then we probably only keep one? How do we ensure that there is not another w that makes this policy (or set of policies) to fail?\n\nFor all these reasons, I recommend to reject the submission.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-f-vjNDSLiV", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "= Overview = \n\nThe paper introduces an approach that, given a set of \"basis\" policies, constructs a high-level policy from the basis policies that is able to perform well in a variety of distinct (but related) tasks. Such tasks are described by MDPs with similar state-action spaces and similar dynamics, and differing only on the reward functions, all of which are built as a linear combination of common features.\n\nGiven a set of policies, the paper introduces the notion of \"set improving policy\" as a policy that outperforms any policy in the given set on the family of considered tasks. It provides two examples of such policies (SMP and GPI) and formalizes the problem of computing a SIP with maximal worst-case performance on the set of considered tasks as a max-min problem. It then contributes an incremental algorithm for this problem. The proposed approach is tested in a grid-world environment and the DM control suite.\n\n= Positive points =\n\nThe paper is very well written, with the proposed approach clearly motivated, presented and analyzed. The proposed approach is novel, to the extent of my knowledge, and analyzed both theoretically and empirically. \n\n= Negative points =\n\nMy main criticism is, perhaps, some lack of detail on the experimental evaluation -- particularly in the DM control suite.\n\n= Comments = \n\nOverall, I really enjoyed reading the paper. The problem addressed -- that of building a policy that performs well in a number of related tasks from a set of \"simpler\" policies -- is, in my view, quite relevant for the RL community, and has potentially interesting applications in domains such as robotics.\n\nThe proposed approach is, as far as I know, original and contributes to the state of the art. The paper briefly links its contributions to the existing literature on apprenticeship learning and hierarchical RL, but I would have appreciated some more discussion on these topics -- particularly, I'd like to better understand how the learned policy relates with policies taught through apprenticeship learning.\n\nOverall, the ideas in the paper are presented in a very clear and elegant manner and the results strike me as technically sound. The proposed approach focuses on building a set of \"basis\" policies in such a way that the policy built from them performs as well as possible in all the considered family of tasks. The method is derived from first principles, and the performance bounds provided (framed in terms of the performance of the SMP policy) are then validated empirically. \n\nFinally, the paper is evaluated in a smaller grid-world domain and in the DM control suite. One aspect that could, perhaps, be improved is concerned with the description of the empirical evaluation in the DM control suite: the paper does describe how the family of rewards for these tasks were built, but it would be good to provide some description of the types of policies that the different rewards lead to and how the policy computed by the proposed approach relates (or differs) from them.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are positive or very positive about this work. The authors successfully addressed all questions. I believe this paper should be accepted.
Decision: Accept (Spotlight)