Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: = Overview = 

The 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.

Given 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.

= Positive points =

The 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. 

= Negative points =

My main criticism is, perhaps, some lack of detail on the experimental evaluation -- particularly in the DM control suite.

= Comments = 

Overall, 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.

The 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.

Overall, 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. 

Finally, 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.
review_title: The paper addresses an interesting problem, and the proposed approach is clear and well formalized. The paper analyzes the proposed approach theoretically as well as empirically, attaining good results.

final_score: rating: 7: Good paper, accept
review_content: 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:
- 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. 
- 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)
- 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.

Pros:
- the work is of very high quality, all motivations seem sound and the theoretical results seem correct
- 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
- 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

Questions:
- 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?
- 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)
- 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)? 
- 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)?

Minor comments:
- the legends in Figure 1a/b and the axis font in Figure 1c could be increased, same with Figure 2
- is the $\max_i$ necessary in equation (8)?

Overall, 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.

Arslan, 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.
review_title: Strong and non-trivial theoretical contributions, interesting empirical insight that connects directly to the theory

final_score: rating: 7: Good paper, accept
review_content: 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)).

Unfortunately the submission suffers from several serious weaknesses:
- 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).
- 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?
- 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.
- the formalization is messy and sometimes unnecessarily confusing. Please see the series of comments below:
- Definition 3 and Eq. 5: the argmax returns an index, not a policy. (minor)
- 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)
- Definition 4: the argmax returns an action not a policy. (minor)
- Equation 7: \Pi lives in? Also instead of max_{\psi\in...} \psi.w, I would use max_{i\in [n]} \psi^i.w. (minor)
- Lemma 3: what is d? (minor)
- 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?

For all these reasons, I recommend to reject the submission.
review_title: Official Blind Review #3

final_score: rating: 6: Marginally above acceptance threshold
review_content: This was a well-written, and interesting paper to read!

I 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.

1 - 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.
What 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?

2 - 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.
I don't think this lemma, as is, is particularly useful.

3 - 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?

4 - 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"?

5 - 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).

review_title: Overall interesting idea. Need some clarification.

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)