Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: The paper proposes a hiearchical RL framework augmented with linear temporal logic. Low-level policies are trained to reach a set of subgoals with penalty on violating safety constraints, allowing the high-level policy to adapt to different task by composing the low-level policies to reach a set of subgoals specified by an Linear Temporal Logic clause.

My first comment is on technical novelty. Although the paper states that LOF takes a step beyond RM to enable compositionality, there is no empirical comparison or evaluation. The only experiment on evaluating compositionality (c, d in Figure 2) does not compare LOF against RM.

My second major comment is on technical exposition. The paper's writing needs a lot of work, especially the method section. The method section started off by describing different concepts used by the framework, but it is unclear how these concepts constitute LOF. For example, how exactly is LTL used in LOF? The introduction mentioned that LOF provides "compositional" property, but there is not a single hint of how might each piece of LOF lead to this property. It took me a few read to understand how the low-level reward might be agnostic of the high-level task, which in turn enables fast adaptation to new task because only the high-level needs to be trained, but it is better to state that clearly.

I would suggest the authors to write one or two paragraphs at the beginning of the method to provide a high-level overview of (1) What LOF is, (2) what are different components of LOF (3) how these components interact with each other, intuitively (4) what are the technical challenges each component, or all components jointly, are trying to tackle  (e.g., enabling compositionality). 

In addition, there are many mentioning of using reward function in the form of an FSA. I understand that this was already introduced in Icarte et al., but it is worth reviewing it in the main paper.

Comments on experiments:
- For compositionality experiment, why might RM and Flat not be applicable here (related to my first comment)?
- I do not see RM curve in (e)


Minor:
- "\phi_{liveness} is represented as a finite state automaton". The paper has been using FSA through except first introduced FSA. It's better to be consistent.

review_title: Writing and exposition require a lot of work

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper is on a new RL framework that leverages logical reasoning to improve the learning performance of RL agents. In particular, the knowledge is encoded using LTL, and includes both safety knowledge (used for reward function definition) and liveness knowledge (used for constructing FSA). THe developed framework has been evaluated using tasks in both discrete and continuous domains, where the RL agent was realized using Q-learning and PPO respectively. The framework was compared with baselines including another LTL-based RL methods (Reward Machines). Results show that LOF performed better than the baseline methods in learning rate and policy quality (in most cases). 

The whole idea of leveraging human knowledge to improve RL agent's learning performance makes senses. The main concern is that the developed framework looks quite incremental in comparison to the methods from the literature. For instance, there are already methods in the literature using LTL to bias the reward function, e.g., the papers that improved the Reward Machines work. As a result, the novelty of the safety knowledge is rather incremental. At the same time, the "liveness" part is quite similar to those methods that plan at a symbolic level to guide RL agents, such as the following: 

Lyu D, Yang F, Liu B, Gustafson S. SDRL: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. 2019

It's nice to see the discussions on satisfaction, optimality, and composability. The analysis on optimality is the most important, whereas the other two points are relatively trivial due to the LTL-based FSA. But it turned out the developed approach, LOF, does not guarantee any desired properties beyond those from the literature. In particular, the LTL-based FSA cannot guarantee global optimality, where the baseline of Reward Machines does. 

The reviewer is curious about if Reward Machines can be considered an ablation of LOF, where the "liveness" component is disabled (and "safety" is retained). If not, what are the differences between the two methods? 

Knowledge-based RL can go beyond HRL methods. For instance, the following survey paper summarizes a few other ways of leveraging human knowledge in RL. Some discussions can help improve the related work section. 

Zhang S, Sridharan M. A Survey of Knowledge-based Sequential Decision Making under Uncertainty. 2020

In general, it's not surprising to see human knowledge is useful in RL. However, human knowledge is not always correct. It will be nice to evaluate the situations where human knowledge in incomplete or inaccurate, or at least some discussions can be helpful. 

----------
The reviewer appreciates the response in detail. The new figures (Figs 4-7) are helpful for demonstrating the differences between LOF and RM, while also demonstrating that their outputs can be similar or the same in many cases. The reconciliation between optimality and composability is a nice feature. Overall, the reviewer still feels positive on this work. 
review_title: Interesting work with good results, but a bit incremental to the literature

final_score: rating: 6: Marginally above acceptance threshold
review_content: In this paper, the author proposes logic option framework for learning policies that satisfy the logic  constraints.  Temporal logic rules are converted into finite state machine and each of them is then converted to a learnable option, where the logic proposition is used as the reward function. Given the options, it searches for the optimal meta-policy over all the options. The LOF is tested on a gridworld and an OpenAI Gym benchmark and is compared against baselines that do not use rules.

I find the idea of integrating logics into RL is an exciting direction for improving agent's interpretability and the proposed LOF does have some novelties in applying the FOL rules. However, I'm not familiar with the RL and option literature and it's difficult for me to tell its original work from the existing ones on the RL side.

Some questions for the author:

Judging from Algorithm 1, it seems the rules and predicates are pre-defined with the environment and their conversion into FSA and reward functions are also done with an existing method. Is there anything original in terms of rule/predicate learning or conversion for the proposed LOF?

In Algorithm 1, each rule is converted to an option and learned independently. What does the LOF do if rules are correlated or have conflicts?

- Say, rule1 is a pre-requisite of rule2: rule1: "go to dest1" and rule2:"if agent is in dest1 then go to dest2, otherwise check rule1"

- Or rule1: "go to dest1 asap" whereas rule2: "do not violate the traffic rules"

- Does the LOF provide mechanism to address the above issues?

I'm also concerned about the scalability of this method. It seems to me that the options need to be evaluated at each possible state in the environment. If the goals are fixed, probably one can store the value beforehand, but for a dynamic environment where the goal is changing, how much does it cost to update the reward function and learn the option policies? And how well does it scale with the size of the state/action space?

review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary of the work:
The authors propose the Logical Options Framework (LOF) --- a framework for reasoning over high-level plans and learning low-level control policies. This framework uses Linear Temporal Logic (LTL) to specify properties (high-level tasks) in terms of propositions. The authors propose a framework in which a separate sub-task policy is learnt to accomplish each such sub-task proposition. These low-level control policies may be reused, without further training, to accomplish new high-level tasks by performing value-iteration in the proposed Hierarchical SMDP. Experimental results demonstrate the method’s effectiveness for several tasks and experimental domains.

Quality and Clarity:
The paper does a good job at intuitively describing the value that the proposed “LOF” framework provides (satisfaction, optimality, and composability). In general, the language used in the paper is clear and easy to read. 
However, some of the technical aspects in the paper are difficult to follow concretely. There are various vague statements and definitions throughout the paper. Typos, inconsistencies, and missing explanations/discussion of seemingly important notions make some of the presented ideas imprecise. This raised several questions from me on the general applicability of the framework (as it is presented in this paper) beyond the presented experimental tasks, and on some of the specifics of Theorem 3.1. Given that the focus of this paper is on the development a new framework for RL, fixing these issues is crucial. I have included a more detailed list of feedback for the authors at the end of the review. 

Originality and Significance:
The proposed method defines “logical options” – sub-task policies whose goal is to trigger propositions that cause transitions in the automata-based description of the high-level task. Temporally extended tasks may then be accomplished by deploying the appropriate sub-task policy at the appropriate FSA state. This idea seems very similar to learning with Reward Machines. This similarity is acknowledged in the paper. The main conceptual difference between LOF and RMs, is that LOF proposes to learn policies that trigger transitions in an automaton, whereas learning with RMs instead learns separate policies for each state of the automaton. This difference means that in the LOF framework, previously learnt sub-task policies can be reused by composing them to complete new high-level tasks. This is not true for RMs. However, the policies learnt by LOF are not guaranteed to be optimal unless certain conditions are met. 

This is a very good general idea, and as far as I am aware other works have not studied how one might compose previously learned sub-task policies to accomplish new tasks described by automata in this way. However, I am concerned that the significance of the work might be limited to the specific examples of the paper.

For example, by associating a cost with each safety proposition, instead of forming the safety FSA associated with the safety property, it seems that the only safety properties that can be expressed by  LOF are those of the form: “avoid these states”. Because this is a significant limitation in comparison with all possible safety properties, an explicit discussion of the safety properties that can be represented by LOF would help the reader to understand exactly what problems LOF can solve. 

Furthermore, it is unclear how the composability results change in the presence of new and/or changed safety properties. I elaborate further on this point at the end of the next section of the review.

Questions surrounding theorem 3.1
The main theoretical result of this paper is that under appropriate conditions, the hierarchical policy learned through the LOF framework will be equivalent to the optimal policy (optimal when planning is allowed with respect to low-level actions in the FSA-MDP product).

The proof follows the logic that given the appropriate reward functions, the option policies will always reach the states corresponding to their sub-goals, and that the meta-policy will select a sequence of sub-goals that always reaches the FSA goal state.
The proposed method assumes that if an option corresponding to a particular sub-goal is selected by the meta-policy, then no other sub-goal proposition will be triggered before that option is complete. My concern with this assumption is as follows: what happens in scenarios in which an option policy passes through a state associated with a different sub-goal before reaching its own sub-goal? Would it then be possible for the meta-policy to select an option corresponding to a particular sub-goal, but for a different sub-goal proposition to be triggered first, causing an unwanted transition in the FSA? 

For example, suppose in the delivery domain we could complete a task by either of the following sequences of sub-goals: “a then b”, or “b then a then c”. If “a then b” is less costly than “b then a then c”, the optimal meta-policy should result in “a then b”. Furthermore, assume that “b” lies directly between “a” and the initial state of the agent. The optimal policy for sub-goal proposition “a” would be to move directly to “a”, which would cause it to first pass through “b”. This would cause the agent to be forced to follow “b then a then c” even if the meta-policy first chose proposition “a”. Meanwhile, the optimal policy allowing low-level planning in the FSA-MDP product space would be to move to “a” while actively avoiding “b”, and then to proceed to “b”.

Also, it is unclear whether consideration of obstacles and safety propositions are included in the consideration of theorem 3.1. It is unclear what the reward functions corresponding to the “goal-conditioned policy” is. If R_S is included in the reward function used to train sub-task policies, then these policies will learn to avoid obstacles. When we compose these sub-task policies for a new task with potentially different safety properties, the policies we learned previously could be sub-optimal in the new scenario. 

Experimental results:
The experimental results demonstrate the effectiveness of the framework for the chosen experimental tasks. I like the videos provided in the supplementary materials; they are nice visualizations of how the sub-policies are strung together to complete the overall task.

From the paper’s description, it is unclear how LOF-QL is implemented. How does this algorithm make use of the liveness FSA if it does not have access to the FSA’s transition function?

Also, I am concerned that the comparison against RMs may not be fair. As stated in the paper, the RM-based method is only rewarded when the final RM state has been reached. Conversely, the reward for the LOF method is much denser. I do not see why the RM-based method could not also be rewarded for each “good” transition.

Finally, the experiments include the “can” proposition which represents when one of the sub-goals has been canceled. It is unclear how the labeling function, which is defined to map specific MDP states to individual propositions, could return this proposition. If the proposition is returned randomly, the formalisms of the labeling function need to be altered to include these types of randomly occurring propositions.

Pros

> The general idea of the paper is good. I like the idea of pre-learning sub-task policies, and then of using automata-based task descriptions to find meta-policies that accomplish new tasks without additional training. This is the “composability” described in the paper.

>The authors do a good job of intuitively describing the benefits that this type of method could provide over competing algorithms.

>The experimental tasks (particularly the videos of the tasks being completed) provide a nice visualization/demonstration of the ideas of the paper.

Cons

>The technical aspects of the paper are hard to follow concretely.

>Some of the theory seems vague and the paper has various typos and inconsistencies. This could lead to reader misinterpretations and/or author mistakes.

>The method’s applicability seems to be somewhat limited to specific types of tasks, without explicit discussion of exactly what types of tasks can be solved.

>The questions raised surrounding theorem 3.1 need to be clarified.

Further detailed feedback:

>How are the logical options learned? In particular, how are T_{o_p}(s’|s) and R_{o_p}(s) learned. These are the components of the options that are subsequently used to find the metapolicy. Are they estimated by averaging values over rollouts of the learned policy? What if the environment is highly stochastic and their values vary greatly across different rollouts?

>The assignment for T_{o_p}(s’|s) on line 11 of algorithm 1 seems to assume there is a fixed k in which p will be reached. Would this always be the case if the environment is stochastic? This also seems to be a different definition than is given in equation 2.

>In equation 1, R_{o}(s) is defined as the expected cumulative reward of options given that the option is initiated in state s at time t and ends after k time steps; shouldn’t this make R_{o}(s) a function of k as well? 

>In the definition of T_{o}(s’|s), what is p(s’,k)? I assume this is the probability, under the option’s policy, of reaching state s’ after k timesteps from state s. If this is the case, p(s’,k) should be defined.

>In line 9 of the Algorithm 1, T_{P}(s,p) = 1 is written. On line 11 of Algorithm 1, T_{P}(s) = p is written instead, but both have the same meaning: proposition p is returned by the labeling function from state s.

>The liveness FSA’s transition function is defined and treated as a probability distribution. However, the automaton’s transitions appear to be deterministic in the presented examples. If there is a particular reason for it to be defined as a transition distribution, some discussion would be helpful for the reader. 

>In the definition of a Hierarchical SMDP, the transition function is defined as a cartesian product of the environment transition distribution, the labeling function, and the FSA transition function. The precise meaning of this notation is unclear. A brief description of how a transition proceeds would be very helpful for the reader to understand the order in which arguments are passed to these three functions. Does the environment transition first, and the proposition of the new environment state cause the FSA to transition?

>In section 3.1 and in appendix A.1, the author writes that “if the optimal option policy equals the goal-conditioned policy, the policy will always reach the sub-goal”. This will not be the case if the environment is stochastic and it is possible for the agent, under ANY policy, to slip into a state from which the sub-goal is not reachable.

>Point 2 of the contributions outlined in section 1.1 states that the options can be composed to solve new tasks with only 10-50 retraining steps. This wording is at odds with the abstract, which states that LOF’s learned policies can be composed to satisfy unseen tasks with no additional learning.

>In Section 3 “These may only appear in the liveness property and there may only be one instance of each subgoal.” The second half of this sentence is unclear. Does this mean that the inverse image of each sub-goal proposition through the labeling function is a singleton set containing only one state?

>In section 3 “Safety propositions are propositions such as ‘the agent received a call’ that the agent has no control over or does not seek out.” This sentence is unclear. It would help if you could express what it means for the agent to “have control over” or to “seek out” a proposition in terms of the MDP states, actions, and proposition labeling function.

review_title: The paper presents a good idea towards using RL to learn sub-policies which can be composed to accomplish high-level tasks specified by Finite State Automata (FSA). However, the technical components of the paper need be clarified, and in some places fixed.

Meta-review: This was a borderline paper with a split recommendation from the reviewers.  The authors took great care to answer the reviewer questions in detail, and the clarity and precision of the technical exposition was strengthened.  However, substantial technical content was added to the paper during the rebuttal process, which the reviewers were not able to fully and properly assess.

Overall, this is worthwhile research, but the paper is still maturing.  The contribution was perceived as incremental in light of previous work using LTL and FSAs in RL, despite the authors extensively re-explaining the significance of the work in the rebuttal.  A resubmission is more likely to resonate with reviewers and ultimately achieve higher impact.

For completeness, it would help to also briefly acknowledge and compare to hierarchical RL work that also seeks to capture composable subtask structures, such as:

Sohn et al. "Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies", NeurIPS-2018

Sohn et al. "Meta Reinforcement Learning with Autonomous Inference of Subtask Dependencies", ICLR-2020
Decision: Reject