Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper introduces a framework for composing tasks by treating tasks as a Boolean algebra. The paper assumes an undiscounted MDP with a 0-1 reward and a fixed absorbing set G, and considers a family of tasks defined by different reward functions. Each task defers only by the value of the reward function at the absorbing set G. These restrictions are quite severe but basically describes goal-state reaching sparse reward tasks, which are quite general and valuable to study. The paper then defines a mapping onto a Boolean algebra for these tasks and shows how the mapping also allows re-using optimal Q functions for each task to solve a Boolean composition of these tasks. This is demonstrated on the tabular four-rooms environment and using deep Q learning for a 2D navigation task.

The writing is relatively clear and the experiments support the claim in the paper that the framework allows learning compositions of skills. Both experiments show that after learning a set of base tasks, the method can solve a task in a zero-shot manner by composing Q functions according to the specified task. This capability seems very useful wherever it can be applied. But I worry that since the setting is so constrained, it is not likely to be widely applicable. The method in the paper likely does not apply to non-sparse, non-goal reaching settings, and prior methods have explored compositionality in that space anyways.

The coverage of prior work seems complete. One suggestion is to discuss recent goal relabeling work such as Hindsight Experience Replay (Andrychowicz 2017). Kaelbling 1993 is mentioned already, but this line of work has recently shown significant progress in learning to achieve multiple goals at the same time from a different perspective (and also considers sparse rewards).

However, my main concern with this paper is that it is not clear the language of Boolean algebra leads to significant insights in solving these compositional problems. Take Figure 1, which shows the disjunction and conjunction of tasks. While it is true the average does not lead to the same optimal policy as the conjunction, people use it because learning from the completely sparse reward is often prohibitively difficult. This kind of reasoning is straightforward in the restricted case of MDPs considered in the paper and people can design their reward function directly without considering boolean algebra. The result and proofs about recovering optimal Q functions without extra further training are interesting, but again, seem straightforward in the restricted family of MDPs considered without looking at Boolean algebra. Therefore, I am currently considering the paper borderline.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The paper proposes a method of combining value functions for a certain class of tasks, including shortest path problems, to solve composed tasks. By expressing tasks as a Boolean algebra, they can be combined using the negation, conjunction and disjunction operations. Analogous operations are available for the optimal value functions of the tasks, which allows the agent to have immediate access to the optimal policy of these composed tasks after solving the base tasks. The theoretical composition properties are confirmed empirically on the four rooms environment and with function approximation on a more complex domain. 

The paper is generally well-written with a clear theoretical contribution and convincing experiments. The problem of composing tasks is important and I think this paper would be a good addition to the literature. My only concerns are in regards to the assumptions made in this formulation.
I would be wiling to increase my score if the authors address the following points:
1) Some further explanation on why extended value functions are necessary would be welcome at the beginning of section 3.2. Currently, it is only said that regular value functions are insufficient without any explanation. Also, additional motivation for the definition of extended value functions would be helpful to guide the reader.

2) Concerning assumption 1, it seems that the assumption that the reward functions only differ on the absorbing states is fairly limiting. For example, in a navigation task, if one goal location is A, then it must be an absorbing state under this formulation. So, if we have another goal location B, then we cannot use paths through A since it is set as absorbing, even though that A may be part of the shortest path to B. Would it be possible to modify this assumption to circumvent this problem? 

3) In a similar vein, could the authors discuss possible limitations to this framework? For example, could this task/value composition be extended to arbitrary reward functions and continuing tasks or are there some fundamental limitations to this approach? If lifelong learning is a motivating setting for this work, it seems like dealing with non-episodic tasks and more complex rewards would be an important goal. 

4) Fig. 3 b) does not seem to be particularly important as the result is clear enough in text. Perhaps the space could be used for something else. 

As an aside, the paper is well-polished and the lack of typos is appreciated.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper proposes a new framework for defining Boolean algebra over the space of tasks in goal conditioned reinforcement learning and thereby achieving composition of tasks, defined by boolean operators, in zero-shot. The paper proves that with some assumptions made about a family of MDP’s, one can build Boolean algebra over the optimal Q-functions of the individual MDP and these Q-functions are equipped with all the mathematical operations that come with the Boolean algebra (e.g negation, conjunction). The paper verify their theoretical results by experiments in both the 4-room domain with standard Q-learning and in a simple video game domain with high-dimensional observation space and DQN. The proofs of all the theoretical results seem sound and the experiments support the theory. I enjoyed reading this paper as the paper is generally well written and the idea is quite neat.

That being said, I have a few concerns and questions about the paper that I would like the authors to respond to so I am leaning towards rejecting this paper at the moment. However, I will raise my score if the revision addresses my concerns or provide additional empirical evidence. My concerns are the following:

    1. My biggest concern is whether boolean algebra is the right abstraction/primitive for task level composition. Thus far, the most important application of boolean algebra has been in designing logic circuits where the individual components are quite simple. In the proposed framework, it seems that all of base tasks are required to be a well defined task which are already quite complex, so the utilities of composing them seems limited. For example, in the video game domain the author proposed, a very reasonable base task would be “collect white objects” -- this task when composed with the task “collect blue objects” is meaningless. This seems to be true for a large number of the MDP’s in the super-exponential composition. Furthermore, [1] also considers task level composition with sparse reward but I think these compositions cannot be expressed by boolean algebra. One of the most important appeal of RL is its generality so It would be great if the author can discuss the limitations of the proposed framework and provide an complex/real-world scenarios where composing these already complex base tasks are useful. Just writing would suffice as I understand setting up new environments can be difficult in short notice (Of course, actual experiments would be even better).

    2. Does the maze not change in the environment setup? (It would be nice if source code is provided) If that is the case I would like to see additional experiments on different mazes (i.e. different placement of walls and objects). In my opinion, if there is only a single maze, then the only thing that changes is the location of the agent which makes the task pretty easy and do not show the full benefit of function approximators. I think it’d strengthen the results if the framework generalizes to multiple and possibly unseen mazes.

    3. In the current formulation, a policy is discouraged to visit goals that are not in its current goal sets (receives lowest reward). While this could be just a proof artifact, it can have some performance implications. For example, in the 4 room domain, if I place a goal in the left corridor, then the agent in the bottom left room will need to take a longer route to reach top left (bottom left -> bottom right -> top right -> top left) instead of the shorter route (bottom left -> top left). From this perspective, it seems some non-trivial efforts need to be put into designing these "basis" tasks. I am curious about the discussion on this as well.

    4. Haarnoja et al. 2018 and other works on composing Q values can be applied to high-dimensional continuous control using actor-critic style algorithms and relies on the maximum entropy principle. Can the method proposed in this paper be used with actor-critic style? Is the max-entropy principle applicable here as well? Discussion would be great and experiments would be even better.

Out of all my concerns, 1 matters the most and I am willing to raise my score to weakly accept if it’s properly addressed. If, in addition, the authors could adequately address 2-4 I will raise my score to accept.

=======================================================================
Minor comments that did not affect my decision:
    - In definition 1, it would be nice to define r_min and r_max and g \ne s \in \mathcal{G} is also somewhat confusing.
    - In definition 2, \pi_g is never defined

Reference:
[1] Language as an Abstraction for Hierarchical Deep Reinforcement Learning, Jiang et al. 2019

review_title: Official Blind Review #1

Meta-review: This paper considers the situation where a set of reinforcement learning tasks are related by means of a Boolean algebra.  The tasks considered are restricted to stochastic shortest path problems. The paper shows that learning goal-oriented value functions for subtasks enables the agent to solve new tasks (specified with boolean operations on the goal sets) in a zero-shot fashion.  Furthermore, the Boolean operations on tasks are transformed to simple arithmetic operations on the optimal action-value functions, enabling the zero short transfer to a new task to be computationally efficient. This approach to zero-shot transfer is tested in the four room domain without function approximation and a small video game with function approximation.

The reviewers found several strengths and weaknesses in the paper.  The paper was clearly written.  The experiments support the claim that the method supports zero-shot composition of goal-specified tasks.  The weaknesses lie in the restrictive assumptions.  These assumptions require deterministic transition dynamics, reward functions that only differ on the terminal absorbing states, and having only two different terminal reward values possible across all tasks.  These assumptions greatly restrict the applicability of the proposed method.  The author response and reviewer comments indicated that some aspects these restrictions can be softened in practice, but the form of composition described in this paper is restrictive.  The task restrictions also seem to limit the method's utility on general reinforcement learning problems.

The paper falls short of being ready for publication at ICLR.  Further justification of the restrictive assumptions is required to convince the readers that the forms of composition considered in this paper are adequately general. 
Decision: Reject