Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of using logical specifications of a task to derive an abstract graph, come up with a plan, and train low-level policies more effectively. Given a logical specification written in SPECTRL syntax, it is first converted into an abstract MDP. Dijkstra's algorithm is executed on this abstract MDP, assigning probabilities to edges when they are encountered for the first time. A policy is trained for each edge (S_0, S_1) in the abstract MDP where a random state in S_0 is the initial state and a random state in S_1 is the goal state. The success probability of the policy is used to assign the probability of the corresponding edge. The model is evaluated on two rooms environments and a fetch environment from OpenAI gym. The model is shown to outperform previous models.
main_review: Originality: It is not clear how the proposed DIRL model differs from available abstract MDP literature. Different from previous logical specification literature, this work explores utilizing abstract MDPs for effective planning. The paper mentions that it is different from previous abstract mdp literature since this work focuses on learning from logical specifications. I believe, if the corresponding abstract mdp is given, this would be a planning on abstract mdp problem where there is only a few related work in the paper. Especially, [1] is very relevant to this paper and shares some similarities. Please compare and clarify.

Quality: 
There are multiple assumptions in the paper that makes the problem a bit synthetic and not applicable to broader RL problems. It feels like the problem is very simplified as conversion from logical specifications to abstract mdp, planning on the abstract mdp, and training the agent on sub-tasks are all straightforward. I detailed some of these below.

(i) Mapping from sub-regions to abstract states is assumed to be given. This is a crucial assumption where both terminal conditions for each subtask and execution of the high level plan depends on.

(ii) The paper assumes the simulator can be modified. This allows the model to sample states more uniformly, especially since the set of states that correspond to a given abstract state is given. It is not clear if previous work that the paper compares also utilizes this. Please clarify.

(iii) Is the safety constrain really required? There might be different safety requirements in general but this is already implied by the success of the low-level policy (and their edge probabilities) and the example in Figure 1 is more related to task success rather than a safety constrain. It is not clear if this is used in experiments as well. Please clarify.

Clarity: Paper is overall clear but it makes heavy use of notations which at times feel repetitive.

Significance: Results are significant and relevant to the RL community.

[1] "Abstract Value Iteration for Hierarchical Reinforcement Learning", https://arxiv.org/pdf/2010.15638.pdf
limitations_and_societal_impact: The paper makes several assumptions. In addition to the ones listed in the paper, it assumes logical specifications can be converted into an abstract mdp deterministically and a set of states that correspond to an abstract state is known.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses the problem of synthesizing (using reinforcement
learning) a policy that satisfies a logical specification. The key
insight in this, and related works, is that the implicit structure
of the specification can be used to decompose the learning problem
into several, ideally simpler, learning problems.

Technically, this work operates by first syntactically restricting the
space of (infinite horizon) tasks. This class is fairly expressive and
has the important property that tasks can be abstractly monitored
using a *finite* DAG - with (abstract) satisfaction now being a path
finding problem on the DAG abstraction. The conversion is automatic
and the complexity grows linearly in the syntactic structure.

The graph structure then admits a nature mechanism to split the task
into sub-tasks, corresponding to traversing an edge in the DAG. Thus,
by leveraging classic shortest path finding algorithms, where the cost
is determined by the traversal probability - which is itself
determined by training a policy in the workspace and empirical
evaluation - one obtains a hierarchical policy. This defines an iterative algorithm which the paper shows
can be used to increase sample efficiency compared to various baselines.


main_review: At a high level, I found the writing and the exposition of the topics
well done. Furthermore, I feel that the topic of using logical
formalisms for defining tasks in RL is a rich and important topic.
This work illustrates, for example, tasks can be naturally decomposed
increasing the efficiency of learning - and perhaps even the
interpretability and verifiability of the agent.

## Empirical Evaluation
I think the authors have done a fairly good empirical evaluation. I
particularly appreciated the inclusion of the two reward machine based
algorithms, which I would have a-priori considered to be natural
comparisons. One missing comparison I would have liked to see, but am
ok not having is an off-the-shelf hierarchical RL algorithm where the
specification DAG is treated as an MDP. This would have given me a
better sense if the primary contribution is the decomposition of the
problem or the shortest path training scheme. That said, I am fairly
confident this approach would outperform such a base-line.

## Clarification about Path policies
My understanding is that it may not always be the case that an edge is
successfully traversed in the DAG abstraction. One thing I would like
clarified is what the high level polices do in such cases. The path
policies defined on line 238 seem to suggest that a path is first
selected and then the system updates the path index. But if the edge
traversal fails, is this a stuttering transition? Or is it just that
it takes an unbounded (possibly infinite) amount of time?  For example,
if the agent accidentally enters a sink in the underlying MDP? While I think
I understand how to fill in these holes, a more explicit discussion would
have been appreciated.

## Role of reward shaping
The class of tasks considered in inherently sparse. The authors
propose a reward shaping scheme, but I can't help but wonder how such
an approach would compare with recent advances in learning directly
from sparse rewards, e.g., Hindsight Experience Replay. It seems that
one of the reasons splitting up the task would improve performance
would be that sparse rewards need less long term planning. This would
be with the benefit of not accidentally introducing a reward bug due
to shaping, which without knowing the dynamics, cannot be performed
safely in general.


limitations_and_societal_impact: I believe that this line of research, in particular incorporating high
level reasoning based on logical properties, is an important
ingredient safe AI.

Regarding the limitations, I was pleased to see that the major
limitation I had noting when reading the paper was explicitly
addressed in the conclusion. Namely, in order to trade edge policies
it is important to be able to reliably initialize the system to an
arbitrary state, or a similar assumption. While in many domains, e.g.,
simulation, this may be reasonable, in other complex domains this
presents a non-trivial problem and sub-task of its own. Nevertheless,
I feel that this work is still valuable and the above limitation could
be overcome.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a framework for combining RL with logical specifications. In particular, the task is specified using local statements, which are then converted into a graph and high-level planning (using Dijkstra's algorithm) is used to attain the goal while adhering to any safety constraints. Within this graph, nodes are sets of low-level states, while edges represent the probability of a policy (learned using model-free RL) transitioning between nodes. While there exist other approaches that combine logical (e.g. LTL) specifications with RL, experiments in two continuous control domains demonstrate that the method outperforms these existing approaches, and scales only linearly with the complexity of the specification. 

main_review: The paper tackles the problem of solving tasks whose goals and constraints are specified using logical predicates, instead of reward functions. I feel this is an important direction (since the ability to encode goals and safety constraints in a human-understandable form will be critical to real-world applications) and, to the best of my knowledge, the paper makes a novel and interesting contribution towards this. Although the paper was generally well written, I found that certain parts were very hard to follow due to space constraints (reading the supplementary material helped, but it would be better if the main text were more self-contained). I have a few questions to help with clarification, and also one concern about how the graph is constructed in the first place, which I'll outline below. 

Main comments

1. One aspect I'm not clear on is the grounding of predicates to MDP states. How exactly is the link between predicates and low-level states established?. Line 177 implies that this mapping needs to be done manually. If so, is this then akin to a human designer manually specifying a symbolic representation (which could be hard for very complex domains) and then learning how the symbolic states are connected? If so, this seems like a fair amount of information that must be encoded manually (other approaches like [1] can autonomously construct them). Are the other baselines provided with similar information? 
2. A follow-up question is the following: since the subgoal regions can contain overlapping states, we could have a low-level state s be in both nodes A and B. If we are learning a low-level policy to reach A, but the agent observes state s, how could it be certain that it has not reached B instead?
3. I found that I couldn't follow Section 5 without the supplementary material at all. Terms like "sub-specification" and "half sub-specification" were completely opaque to me, but the longer explanation in the appendix made sense. If possible, more detail could be incorporated into the main text (I feel like a few of the definitions in Section 4.2 could be removed to make room).   
4. I don't quite follow why on Line 114 the policy is not the regular Markov policy, but rather a function of the history. My understanding is that each edge policy is Markov and acts according to the MDP state, while the path policy could act based on the current node only. Any clarification would be appreciated.

Minor comments

1. In the absence of rewards, it makes sense that the agent should seek a maximally likely policy that reaches the goal. However, are there use cases where this wouldn't work? For example, in a tabular deterministic shortest path setting, all policies are equally capable of reaching the goal with probability 1 (but may take varying amounts of time). Is there any way this can be overcome? 
2. The blue/grey colours in Figure 1 (left) are a bit faint and hard to pick up on, especially when printed. 
3. Line 153 cyclic -> acyclic
4. Line 164: What is s_{i_j}?

[1] Pacheck, Adam, George Konidaris, and Hadas Kress-Gazit. "Automatic Encoding and Repair of Reactive High-Level Tasks with Learned Abstract Representations." Robotics Research: the 18th Annual Symposium. 2019.


****** POST REBUTTAL ******

Thank you for the response, which has helped clear up the questions and misconceptions that I had. As one of the other reviewers recommended, emphasising the exact novel contributions of the work in the introduction would be extremely helpful for an updated version. 



limitations_and_societal_impact: While the paper discusses a few of its limitations, if I'm understanding correctly, then one additional limitation is that a mapping from states to predicates be given upfront, and all predicates (nodes) be known before learning begins. This requires human expertise, and may be very hard for complex tasks.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper addresses problems where the task to be accomplished is given by a specification language (Spectrl). Tasks given in this specification language can be represented as reachability problems on an abstracted graph, where nodes in the abstracted graph represent regions of the underlying state space of the original problem. To find a high-level plan to satisfy the task specification, Dijkstra's algorithm is used. To learn low-level controllers to complete each of the subtasks, reinforcement learning is used. The probability of a subtask being completed by a low-level controller is evaluated empirically, and used to update costs in the high level graph so that the lowest cost path in the high-level graph corresponds to the path maximising the probability of completing the task.
 
I think the paper is well written, and addresses an interesting problem. To my understanding, the general idea of combining high-level model-based planning with RL for low-level control has been addressed in existing works. However, this is the first work to do so for more complex task specifications.

main_review: I think the authors need to be clearer about the contributions made by this paper (I would suggest that the authors explicitly enumerate their contributions in the introduction). In the introduction, the authors seem to indicate that a novelty of their work is integrating high-level model-based planning with learning of low-level control. However, this general idea has been presented in other papers such as Illanes (2020), where the high-level specification is given in PDDL (and also considers MaxProb formulations), or arguably even Eysenback (2019).
 
Therefore, my understanding is that while other works have considered the idea of high-level planning over subtasks + low-level controllers via reinforcement learning, this is the first work consider more powerful task specifications in the form of tasks specified by Spectrl.
 
Question 1).
Can the authors please compare their work with Illanes (2020). Is the main difference that Illanes (2020) considers high-level goals specified in PDDL, whereas here goals may be specified using Spectrl, or are there other significant advances made by this work?
 
The high-level planner operates on a deterministic graph, and outputs the maximum probability path (rather than a policy for all high-level states). Therefore, if the low-level controller fails to reach the desired sub-goal, and accidentally reaches a different sub-goal, the algorithm will not switch appropriately to a different sub-policy. Given that the empirical transition probabilities between high-level abstract states are computed empirically anyway (to compute the edge costs in the graph), I wonder why we wouldn't just treat the high-level abstract graph as an MDP, and compute a high-level policy for that MDP rather than a path? I understand that this would increase the computational burden as we have to learn sub-policies for more states, but this seems like a more natural formulation for stochastic environments, especially considering that the transition probabilities need to be empirically estimated anyway.
 
Question 2).
Can the authors comment on the advantages of treating the high-level planning problem as deterministic, rather than an MDP? It seems that an MDP would more naturally handle cases where the sub-policy fails to reach the desired sub-goal, and transition probabilities between sub-goals are already being computed empirically anyway.
 
Minor comment: It might aid in the writing of the paper by referring to the sub-policies as "options" as is often done within RL literature.

References: 
 
Illanes, León, et al. "Symbolic plans as high-level instructions for reinforcement learning." Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30. 2020.
 
Eysenbach, Benjamin, Ruslan Salakhutdinov, and Sergey Levine. "Search on the replay buffer: Bridging planning and reinforcement learning." NeurIPS 2019

limitations_and_societal_impact: Some technical contribution limitations identified.
review_title: null

Meta-review: This paper presents an approach to learning to solve a task from logical specifications by defining an abstract graph, planning on it, and learning the required low-level skills.
There were several concerns raised by the reviewers that were largely addressed in the discussion, leading to a positive evaluation of the paper.
Specifically, there were questions about the exact contribution, which the authors should make explicit in the final paper. The authors are expected to make the promised changes, including the suggested background and additional baselines, as well as further providing further discussions on the assumptions.

Decision: Accept (Poster)