We propose a framework for defining a Boolean algebra over the space of tasks. This allows us to formulate new tasks in terms of the negation, disjunction and conjunction of a set of base tasks. We then show that by learning goal-oriented value functions and restricting the transition dynamics of the tasks, an agent can solve these new tasks with no further learning. We prove that by composing these value functions in specific ways, we immediately recover the optimal policies for all tasks expressible under the Boolean algebra. We verify our approach in two domains-including a high-dimensional video game environment requiring function approximation-where an agent first learns a set of base skills, and then composes them to solve a super-exponential number of new tasks.
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