Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces recursive MDPs (RMDPs) as a formalism for representing a large class of infinite-state MDPs as a (finite) set of component MDPs that may recursively call each other. The authors first present an example RMDP (a probabilistic program with holes, representing action choice points), then formally define RMDPs and their translation to infinite-state MDPs, such that each state in an RMDP corresponds to a node in the currently active component MDP, paired with the stack of component MDPs called so far.

The authors next derive a number of theoretical results about RMDPs under variants of the restriction that all policies terminate in a finite number of steps in expectation (achieved by adding discounting to an RMDP). In particular, they show that $\epsilon$-proper RMDPs are PAC-learnable, derive a generalized Bellman equation for proper RMDPs, and further derive a sound and effective continuous-space abstraction of RMDPs that preserves the optimal value function and optimal policy. In this abstraction, an RMDP state is abstracted to a tuple of a continuous vector and the node of the currently active component, enabling the application of deep reinforcement learning approaches that require finite-dimensional state encodings.

Using the above results, the authors derive a recursive Q-learning algorithm that they prove to converge in the special cases of 1-exit RMDPs and deterministic multi-exit MDPs. They also develop a deep Q-learning variant, presented in the Appendix. They then evaluate these algorithms on a number of example RMDPs across different application contexts, showing that they achieve convergence and higher total reward, unlike non-recursive (deep) Q-learning approaches.
strengths_and_weaknesses: This was a really interesting (albeit theoretically dense) paper that introduces a set of representational and algorithmic ideas that are (to my knowledge) original, are likely to be of interest and significance to a number of communities who might wish to apply reinforcement learning to environments that exhibit recursive dynamics (probabilistic programs, environments with non-Markovian task rewards, etc.) By taking the general principle of the "infinite use of finite means" and applying it to MDPs, RMDPs extend the space of sequential decision problems that can be succinctly modeled.

Beyond that representational insight, the authors derive a number of useful theoretical results that can be applied to a large class of RMDPs (most of the restrictions are satisfied by the common modeling assumption of a discount factor), and further show that RMDPs admit a finite-dimensional continuous-space abstraction, thereby deriving the nice result that many RMDPs can be optimally solved by finite policies that do not depend on the state of the call-stack or state history, while also enabling the use of deep RL approaches. While the derived Q-learning algorithms unfortunately are not proven to converge in a large number of other cases (multi-exit RMDPs), they empirically appear to outperform non-recursive algorithms even in those settings. Even if the authors do not prove everything one might like, all in all this seems to me like a good start for a paper that also introduces the concept of RMDPs.

My main piece of feedback is that the exposition and presentation was unclear or confusing to me at points. The example and applications at the start helped, but at least a number of statements later on that seemed obvious to the authors were not at all clear to me. I'll highlight these in my questions and suggestions below. (Due to time constraints, I'll also note that I only briefly skimmed the proofs in the Appendix.)

Separately, in discussing related work, I was surprised by the lack of discussion of programmable reinforcement learning agents [1], which provides a formalism for potentially recursive policies, specified as subroutines with choice points that may call each other. While recursive policies are not the same thing as recursive MDPs, it stuck me that they may be similar or equivalent in some contexts, especially in the Cloud Computing / probabilistic program synthesis example, where the structure of a policy program sketch corresponds exactly to the structure of the RMDP itself. I think it would be good to cite work in this field, and discuss at least some of these connections.

Apart from that, I enjoyed reading this paper, and I think a number of research communities will benefit from its publication.
questions: 1. The following statement on Lines 54-55 initially confused me: "The 1-exit RMDPs are strictly less expressive than general RMDPs as they are equivalent to functions without any return value." It took me a while to realize that having 1-exit means you can only return a constant value, which is hence equivalent to not having a return value at all. Perhaps this can be clarified?

2. Upon seeing Figure 2, it seemed to me that RMDPs are very similar to policy program sketches for programmable reinforcement learning agents. What is the relation between these two formalisms?

3. The explanation of context-free reward machines, especially the battery example, was confusing to me (I still don't understand it). Relatedly, it was not obvious to me how the palindrome gridworld can be represented as an RMDP. I think it would be good to show the formal translation of MDPs with context-free reward machines to RMDPs somewhere in the Appendix, 

4. Until I read Lines 150 to 164, I was confused by what a full state RMDP actually is. I think it'd be good to mention somewhere earlier, e.g., during the informal introduction, that the full state of an RMDP just corresponds to the current state of the active component MDP, conjoined with the stack of all component MDPs called so far. This also makes it easier to see how RMDPs have an infinite state space.

5. In lines 165 to 170, the language of "strategies" (and also "runs", later on) was unfamiliar to me -- it seems like this terminology is more common in some subfields, whereas "policy" is more standard in others. I think it would be good to briefly explain that strategies are just policies that may be history-dependent.

6. When defining the optimality equations, the terms $Ex$ and $En$ are not defined anywhere earlier in the paper. I assumed that $Ex$ is just the union of all exit nodes across component MDPs, but it's not defined on Line 137.

7. The notation for the equations defining $\text{OPT}_\texttt{cont}(M)$ was confusing. First, I was confused by the fact that $v$ seems to have varying dimension depending on what component you're in, because on the second branch, it says that $q \in Ex$ rather than $q \in Ex_i$. The notation used for the first branch is also hard to understand -- I think more explanation below in English would be helpful here.

8. Given that a *continuous* space abstraction is used for (tabular) recursive Q-learning, isn't it actually impossible to implement using a Q-table? I understand that Algorithm 2 for single-exit RMDPs avoids this, because you don't actually need to store the exit values anywhere, but for the general case, discretization is required. What impact does this have on convergence?

9. Relatedly, the Cloud Computing example is a stochastic multi-exit RMDP not covered by any of the theoretical results. Yet Algorithm 1 seems to attain convergence to the optimum, despite the lack of theoretical guarantee, and despite the use of discretization. How was this possible, and how was the true optimal strategy found and justified?

Minor comments:
- Line 66: "taks" should be task.
limitations: The authors have discussed limitations of their approach in the assumptions they make for their theoretical results. That said, there are a few questions re discretization for tabular learning that I think should also be answered or at least mentioned, as noted above.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies reinforcement learning in recursive Markov decision processes (RMDPs). RMDPs were proposed a few years ago, and the authors cited one paper in which reinforcement learning for a special type of RMDPs (1-exit RMDPs with a positive reward restriction) was presented. The goal of the current paper is to study reinforcement learning in more general RMDPs. The paper offers both theoretical and empirical contributions. A number of theoretical assertions are made, e.g., about undecidability or PAC-learnability. The RMDPs can model infinite state spaces, but the algorithms for solving them have to deal with infinite quantities in one way or the other. For this reason, an approximate algorithm for RMDPs is proposed in this paper. Empirical results are presented and the new method is compared with standard flat Q-learning.
strengths_and_weaknesses: This paper offers a competent discussion of RMDPs and adds useful extensions to reinforcement learning algorithms for solving these models. If we disregard the broader reinforcement learning literature, this paper looks like a strong contribution. This work on RL in RMDPs is, however, not placed correctly in the context of the existing methods in the reinforcement learning community. The biggest issue is that the current narrative of criticism of flat reinforcement learning muddles the waters, which makes it impossible to see how this work can be placed in the context of the existing literature. In several parts of the paper, the authors refer to flat RL saying that flat RL cannot cope with certain properties of the tasks that can be addressed by RMDPs. The problem is that there exist powerful methods in the RL literature that can cope with structured domains. Hierarchical reinforcement learning or representations with state features can exploit the fact that the state space is composed of a number of state features. This makes the empirical results in this paper unfair since the comparisons should be against hierarchical or factored algorithms. Comparisons with flat Q-learning are not sufficient since there exist algorithms that are at least as intelligent as the methods proposed here. This is certainly authors responsibility to find out how exactly their new method relates to the existing methods.

RMDP is an interesting model, but solving it has its own challenges. For example, to solve the example presented in Fig. 2, it would be possible to use a  RL algorithm with state features, and to use an integer variable to count how many times S() was executed. This would introduce a possibly infinite number of states in the representation, but the size of the stack has exactly the same problem since S() can be executed infinitely many times. So, the stack will grow too.

The relationship of this method with the existing RL literature is not clear, and it difficult to judge if the method adds anything that is not used in the current reinforcement learning methods.
questions: Line 36 criticises HRL for not being able to model infinite recursion? But, the new method has the same problem since the stack can be infinite too? Is this claim justified then?

Example 1 is great. Have you tried to find a hierarchical or maybe a PDDL-like method in RL that could model recursion? Having an integer variable seems to be sufficient.

I am not sure why HRL or factored RL methods cannot cope with the example presented in lines 94 to 108. Could you please clarify?

Why the new definition of proper strategies is required? In standard MDPs (see [26]), discounting is used to cope with summations over infinite sets. The authors talk about the discount factor in the appendix, but the definition of the proper polices seems to be redundant. I believe that the entire theory could be presented without this concept. It adds a lot of confusion.

Why the comparisons are only against flat Q-learning?

I am not sure why Q-learning oscillates in section 5.1? Given a sufficient amount of exploration, Q-learning is guaranteed to find an optimal policy. If Q-learning is put in a disadvantaged position here, the authors should implement Q-learning in a way that will allow it to use the same information as their method based on RMDPs.

It would be useful if the paper was more explicit about which concepts are known and which were proposed in this paper.
limitations: n.a.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents an analysis of a special class of infinite MDPs, recursive MDPs. Recursive MDPs are represented as a collection of components, which have nodes and boxes. Boxes call other components and have associated "call ports" and "return ports". Actions in each component affect transitions to nodes and boxes. A component reward function is defined over component transitions. The components then implicitly define an infinite MDP whose (countable) state space is defined by pairs of box stacks and nodes. Importantly, the stack acts as a context analogous to a stack in a pushdown automaton and can grow infinitely (this is the sense in which recursion is implemented).

The authors analyze RMDPs under two assumptions: 1 - all RMDP strategies have finite return (this can be enforced with a discount) and 2 - RMDPs are epsilon-proper and all policies have a fallign expected stack height. They then report a recursive Q-learning algorithm for multi-exit RMDPs based on an abstraction of the call stack. Specifically, call-stacks are equivalent if they share an exit-value--that is, the vector of total expected rewards from the exit nodes of a box given the rest of the stack. Theorem 3 states that the fixed point of the abstract/continuous version of the RMDP is equivalent to that of the original RMDP, which makes it possible to apply algorithms that operate over a fixed-size state representation (eg standard deep RL methods). Their algorithm (alg 1) is not guaranteed to converge for general multi-exit RMDPs, but they report a version (alg 2) that converges for single-exit RMDPs (single-exit RMDPs only have components with a single exit node, are more expressive than finite-MDPs, and are related to "controlled branching processes"). Experiments are then reported on 3 domains, including one in which a DQN-based learning algorithm is used. Compared to using standard Q-learning/DQN, their recusive Q-learning algorithm does better.


strengths_and_weaknesses: Originality
- The paper provides an analysis of a novel and interesting class of MDPs

Quality
- The types of analyses reported are not in my main field of study, so I cannot comment on whether they meet technical standards typical for this subfield, but I found them to be a sensible way to approach the problem

Clarity
- Given the technical nature of the paper, I thought the main ideas and results were presented clearly

Significance
- The authors note in the introduction that recursive RL can be applied to probabilistic program synthesis, context-free reward machines, and stochastic context-free grammars. These are important domains, but the main test cases they apply their method were mainly toy domains.
questions: I only have a few clarifying questions:
- Were the domains 5.1 and 5.3 general RMDPs? It would be helpful if this were stated explicitly.
- Stackless strategies are mentioned on lines 166 and then in Theorm 5 in relation to recursive Q-learing applied to 1-exit RMDPs. Do the other results apply to general stack-based strategies?
limitations: The authors have been up front about where their method applies and its limitations.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The main idea of this paper is to formulate Q-learning on a type of MDP with a recursive structure, akin to the "call stack" of operating systems. The two arguments are that (1) many realistic MDPs have this sort of structure, and that (2) an RL algorithm designed to exploit this structure will perform better than algorithms with such knowledge. The paper includes some theoretical results about when such recursive MDPs are learnable (similar to standard computability results) and then proposes a variant of Q-learning for solving these recursive MDPs. The variant of Q-learning looks like standard Q-learning, with extra bookkeepping to keep track of the stack trace. On three didactic problems, the proposed method outperforms RL methods that do not exploit the recursive problem nature.
strengths_and_weaknesses: Strengths
* The paper is generally well written, with compelling motivation for why some problems should be treated as recursive MDPs.
* The potential applications discussed on page 3 are great for explaining the motivation for the recursive MDP. 
* The experiments in Fig. 3 nicely illustrate three applications.
* The paper is novel to the best of my knowledge. Formalizing the connections between MDPs and computability seem potentially impactful.

Weaknesses
* The tradeoffs involved in the paper are a bit unclear. See questions below.
* The proposed method was a bit hard to follow. Are there some special cases where the proposed method is equivalent to Q-learning? (e.g., if the observation is augmented with the stack trace)?
* The formal definition of recursive MDPs was complicated and hard to follow (esp. L124 -- L135)

Minor comments
* L1 -- I didn't understand this sentence
* L3 "they must rely on the practitioner's ingenuity" -- Nicely put!
* L23 "regularity assumptions" -- Cite.
* L32 "to generalize its learning upon" -- I didn't understand this sentence
* L41 "Unlike ... enables generalizability" -- Where is this demonstrated/proven?
* L83 "single-exit" -- Be consistent with "1-exit" and "single-exit"
* Fig 1, Fig 2 -- I found these figures pretty hard to parse.
* L94 -- It wasn't clear to me why the charging example requires recursion. Shouldn't it be possible to formulate this as a simple, flat MDP?
* L127 -- L129 -- I found this discussion confusing.
* L318 -- If this task requires memory, then using a Markovian Q-learning policy as a baseline seems a bit unfair.

questions: Some questions that would be good to address:
1. Is it easier or harder for users to define a recursive MDP than a flat MDP?
2. What, precisely, is the relationship with hierarchical RL? Is the recursive MDP a special case of hierarchical RL where the structure is manually provided?
3. If the recursion depth is limited (say, to 3 levels), how beneficial is the proposed framework over standard Q-learning? Note that today's computers seem to work just fine with limited recursion depth.
limitations: I did not see any explicit sections on limitations.
review_title: null

Meta-review: metareview: The paper has generated a lot of discussion, and on balance the reviewers appreciate its technical contributions but find that the paper would benefit from a more in-depth discussion of its relationship to hierarchical RL.
confidence: Certain
Decision: Accept