Recursive Reinforcement Learning
Authors: Ernst Moritz Hahn
Mateo Perez
Sven Schewe
Fabio Somenzi
Ashutosh Trivedi
Dominik Wojtczak
Venue: NeurIPS 2022 Accept (2022)
Keywords: Recursive Markov Decision Processes
Reinforcement Learning
Probabilistic Pushdown Automata
Probabilistic Context-Free Grammars
Recursive State Machines
Branching Processes

Abstract: Recursion is the fundamental paradigm to finitely describe potentially infinite objects. As state-of-the-art reinforcement learning (RL) algorithms cannot directly reason about recursion, they must rely on the practitioner's ingenuity in designing a suitable "flat" representation of the environment. The resulting manual feature constructions and approximations are cumbersome and error-prone; their lack of transparency hampers scalability. To overcome these challenges, we develop RL algorithms capable of computing optimal policies in environments described as a collection of Markov decision processes (MDPs) that can recursively invoke one another. Each constituent MDP is characterized by several entry and exit points that correspond to input and output values of these invocations. These recursive MDPs (or RMDPs)  are expressively equivalent to probabilistic pushdown systems (with call-stack playing the role of the pushdown stack), and can model probabilistic programs with recursive procedural calls. We introduce Recursive Q-learning---a model-free RL algorithm for RMDPs---and prove that it converges for finite, single-exit and deterministic multi-exit RMDPs under mild assumptions.

Recursive Reinforcement Learning
Ernst Moritz Hahn 1
Mateo Perez University of Colorado Boulder
Sven Schewe' University Liverpool
University of Twente
Fabio Somenzi University of Colorado Boulder
Ashutosh Trivedi' University of Colorado Boulder
Dominik Wojtczak'
University of Liverpool
Abstract
Recursion the fundamental paradigm finitely describe potentially infinite objects. As state-of-the-ar reinforcement learning (RI.) algorithms cannot directly reason about recursion, they must rely on the practitioner's ingenuity in designing a suitable "flat" representation of the environment. The resulting manual feature constructions and approximations are cumbersome and error-prone; their lack transparency hampers scalability. To overcome these challenges, we develop RL algorithms capable of computing optimal policies in environments described as a collection of Markov decision processes (MDPs) that can recursively invoke one another. Each constituent MDP is characterized by several entry and exit points that correspond to input and output values of these invocations. These recursive MDPs (or RMDPs) are expressively equivalent to probabilistic pushdown systems (with call-stack playing the role of the pushdown stack), and can model probabilistic programs with recursive procedural calls. We introduce Recursive Q-learning model-free RL algorithm for RMDPs and prove that it converges for finite, single-exit and deterministic multi-exit RMDPs under mild assumptions.
Introduction
Reinforcement learning [36] (RL) is stochastic approximation based approach to optimization, where learning agents rely on scalar reward signals from the environment to converge to an optimal behavior. Watkins's seminal approach [41] to RL, known as Q-learning, judiciously combines exploration/exploitttonn with dynamic programming to provide guaranteed convergence [40] to optimal behaviors in environments modeled Markov decision processes (MDPs) with finite state and action spaces. RL has also been applied to MDPs with uncountable state and action spaces, although convergence guarantees for such environments require strong regularity assumptions. Modern variants of Q-learning (and other tabular RL algorithms) harness the universal approximability and of-te-nn-raaning rendered by deep neural networks [18] to discover creative solutions to problems traditionally considered beyond the reach of AI [30, 39, 33).
These RL algorithms designed with flat Markovian view of the environment in the form of a "state, action, reward, and next state" interface [9] in every interaction with the learning agent, When such infinitude presents itself the form
where the states/actions may come from infinite of finitely represented recursive structures, the inability of the RL algorithms to handle structured environments means that the structure present in the environment not available the RL algorithm to generalize its learning upon. The work of [41] already provides roadmap for hierarchically structured environments; since then, considerable progress has been made developing algorithms for hierarchical RL [6, 13, 37, 31] with varying optimality guarantees. Still, the hierarchical MDPs
Authors listed alphabetically.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

T
S
H
y. -0.2
+0.2
1.5
b::H
+0.2
11
0.5
0.5
u1
b1:S
0
b2:S
b3:5
u2
U3
bg:H
by:ll
m,
8
f,
0.4
b
10-000
0.3
160
Figure 1: A recursive Markov decision process with three components T. S, and H.
are expressively equivalent to finite-state state MDPs, although they may be exponentially more succinct (Lemma 1). Thus, hierarchical RL algorithms are inapplicable in the presence of unbounded recursion.
On the other hand, recursion occurs naturally in human reasoning [10], mathematics and computa- tion [34, 35], and physical environments [29]. Recursion is a powerful cognitive tool in enabling a divide-and-conquer strategy [11] problem solving (e.g., tower of Hanoi, depth-first search) and, consequently, recursive solutions enhance explainability in the form of intuitive inductive proof's of correctness. Unlike flat representations, the structure exposed by recursive definitions enables generalizability. Recursive concepts, such as recursive functions and data structures, provide scaffold- ing for efficient and transparent algorithms. Finally, the models of physical environments express the system evolution in the form of recursive equations. We posit that the lack of RL algorithms in handling recursion is an obstacle to their applicability, explainability, and generalizability. This paper aims to fill the gap by studying recursive Markov decision processes [16] as environment models in reinforcement learning. We dub this setting recursive reinforcement learning (RRL).
MDPs with Recursion. A recursive Markov Decision Process (RMDP) [16] is finite collection of special MDPs, called component MDPs, with special entry and exit nodes that take the role of input parameter and return value, respectively. The states of component MDPs may either be the standard MDP states, or they may be "boxes" with input and output ports; these boxes are mapped to other component MDPs (possibly, the component itself) with some matching of the entry and exit nodes. An RMDP where every component has only one exit is called a 1-exit RMDP, otherwise we call it general or multi-exit RMDP. Single-exit RMDPs are strictly less expressive than general RMDPs as they are equivalent to functions without any return value. Nonetheless, 1-exit RMDPs are more expressive than finite-state MDPs [32] and relate closely to controlled branching processes [17].
Example (Cloud Computing). As an example of recursive MDP, consider the Boolean program shown in Figure 2. This example (inspired from [21]) models cloud computing scenario to compute a task T depicted as the component T. Here, a decision maker is faced with two choices: either she can choose to execute the task monolithically (with cost of 8 units) chose decompose the task into three S tasks. The process of decomposition and later combining the results cost 0.5 units. Each task S can either be executed probability 0.4 the server may crash, and require a recomputation of the task. When executed on a reliable server, the task S costs 1.5 units, however the task may be interrupted by higher-priority task and the decision maker will be compensated for this delay by earning a 0.2 unit reward. During the interrupt service routine H, there is a choice to upgrade the priority of the task for cost of 0.2 units. Otherwise, the interrupt service routing costs 0.01 unit (due to added delay) and the interrupt service routine itself can be interrupted, causing the service routine be re-executed in addition to that of the new interrupt service routine. The goal of the RL. agent is to compute an optimal policy that maximize the total reward to termination.
fast, but unreliable server that costs 1 unit, but with
This example is represented as a recursive MDP in Figure 1. This RMDP has three components T, S. and H. The component T has three boxes by. b2, and by all mapped components S. The component T and S both have single entry and exit nodes, while the component H has two exit nodes. Removing the thick (maroon) transitions and the exit u7 makes the RMDP 1-exit. The edges specify both the name of the action and the corresponding reward. While the component T is non-stoo non-stochastic, components S and H both have stochastic transitions depicted by the grey circle.
Recursive MDPs strictly generalize finite-state MDPs and hierarchical MDPs, and semantically encode countable state MDPs with the context encoding the stack frame of unbounded depth. RMDPs generalize several well-known stochastic models including stochastic context-free grammars [28, 26] and multi-type branching processes [22, 38]. Moreover, RMDPs are expressively equivalent to proba-

---

def SO:
def HO: upgrade ? [yes,no)), upgradde no: try:
def TQ:
? (reliable, fast]):
[mono, divide)):
a = fast:
if a mono:
try:
peccute_monol # -S8
execute fasttsaassssaa # -S1
ISRO -50.01
clsc decompose() # -50.5
except Crash: prob 0.4
except Interrupt: #prob 0.3 if (HO):
SO
SO
else:
return if (H()
SO
try:
SO
execute retiieeeelaaale #-$1.5
return
combine() # $50.5
except Interrupt: #prob 0.3 HO +50.2
return 0
return
else #-$0.2
(a) Task 7'
return
return
(b) Task S
(c) Task H
Figure 2: A probabilistic Boolean program sketch where the choice of the hole (?) is to be filled by RI. agent.
bilistic pushdown systems (MDPs with unbounded stacks), and can model probabilistic programs with unrestricted recursion. Given their expressive power, it is not surprising that reachability and termination problems for general RMDPs are undecidable. Single-exit RMDPs, on the other hand, are considerably more well-behaved with decidable termination [16] and total reward optimization under positive reward restriction [15]. Exploiting these properties, convergent RL algorithm [21] has been proposed for 1-exit RMDPs with positive cost restriction. However, to the best of our knowledge, no RL algorithm exists for general RMDPs.
Applications of Recursive RL. Next, we present some paradigmatic applications of recursive RL.
Probabilistic Program Synthesis. As shown in Example 1, RMDPs can model procedural probabilistic Boolean program. Henee, the recursive RI. can used for program synthesis in unknown, uncertain environments. Boolean abstractions of programs [4] are particularly suited modeling as RMDPs. Potential applications include program verification [4, 5, 14]
and program synthesis [19].
Context-Free Reward Machines. Recently, reward machines [23] have been proposed to model non-Markovian reward signals in RL. In this setting, regular language extended with the reward signals (Mealy machines) over the observation sequences of the MDP is used to encode reward signals. In this setting the RL algorithms operate on the finite MDP given by the product of the MDP with the reward machine. Following the Chomsky hierarchy, context-free grammars or pushdown automata can be used to provide more expressive reward schemes than regular languages. This results in context-free reward machines: reward machines with an unbounded stack. As an example of such a more expressive reward language, consider a grid-world with a reachability objective with some designated charging stations, where 1-unit dwell-time charges the unbounded capacity battery by 1-unit. If every action discharges the battery by l-unit, the reward scheme to reach the target location without ever draining the battery cannot be captured by regular reward machine. On the other hand, this reward signal can be captured with an RMDP, where charging by 1-unit amounts to calling a component and discharging amounts to returning from the component such that the length of the call stack encodes the battery level. More generally, any context-free requirement over tintte-state MDPs can be captured using general RMDPs.
Stochastic Context-Free Grammars. Stochastic CFGs and branching decision processes can capture a structured evolution of system. These can be used for modeling disease spread, population dynamics, and natural languages. RRL can be used learn optimal behavior in systems expressed using such stochastic grammars.
Overview. We begin the technical presentation by providing the formal definition of RMDPs and the total reward problem: which we show to be undecidable in general. We then develop PAC learning results under mild restrictions. In Section 3, we develop Recursive Q-learning, a model-free RL algorithm for RMDPs. In Section 4, we show that Recursive Q-learning converges to an optimal solution the single-exit setting. Section 5 then demonstrates the empirical performance of Recursive Qelearnin..
3

---

2 Recursive Markov Decision Processes
Markov decision process M is a tuple (A,) where A is the set of actions, S is the set of states, T: S x A - D(S) is the probabilistic transition function, and r S A - IR is the reward function. We say that an MDP M is finite if both S and A are finite. For any state 8 E S, A(s) denotes the set of actions that may be selected in state 8.
recursive Markov decision process (RMDP) [16] is a tuple M = (M Ma), where each component M. N,, B, Y,, En,, Ex, 5,) consists of:
A set A, of actions;
A set N₁ of nodes, with distinguished subset En, of entry nodes and (disjoint) subset Ex; of exit nodes (we assume an arbitrary but fixed ordering on Ex; and En;);
A set B; of boxes along with a mapping Y; B, + fl...., ky that assigns to every box (the index of) a component. To each box B₁, we associate a set of call ports, Call, = {(b, en) en E (ny J. and set of return ports, Ret, = {(b, ex E (x)
we let Call' = USEB, B, Calls, Ret' UsE B, Rets, and let Q: N₁ Uall' U Ret' be the set of all nodes, call ports and return ports; we refer to these as the vertices of component M,.
A transition function 5; : Q/ x A, + D(Qi), where, for each tuple (w, a)()) - is the transition probability of transition from the source u E (N; \ Ex;) U to the destination U E (N₂ \ Em.) U Call'; we often write p(ulu, a) for 8,(u, (v)).
A reward function
Q; x A; + R is the reward associated with transitions.
We assume that the set of boxes B B,...., B5 and set of nodes N2,, Nu are mutually disjoint. We use symbols N, B, A, Q, En, Ex, denote the union of the corresponding symbols over all components. We say that an RMDP is finite if k and all A, N, and B, are finite.
An execution of an RMDP begins an entry node of some component and. depending upon the sequence of input actions, the state evolves naturally like an MDP according to the transition distributions. However, when the execution reaches entry port of box, this box is stored stack of pending calls, and the execution continues naturally from the corresponding entry node of the component mapped to that box. When exit node of a component is encountered, and if the stack of pending calls is empty then the run terminates; otherwise, it pops the box from the top of the stack and jumps the exit port of the just popped box corresponding to the just reached exit of the component. The semantics of an RMDP is an infinite state MDP, whose states are pairs consisting of sequence of boxes, called the context, mimicking the stack of pending calls and the current vertex.
The height of the call stack is incremented (decremented) when a call (return) is made. A stack height of 0 refers to termination, while the empty stack has height 1.
The semanties of a recursive MDP M (M,...., M2) with M, (As, N₁, Bú, Y,, Eng, Ex,, 6,, r:) are given as a (infinite-stact MDP [M] = (AM. SM, TM, where
Ai Am , is the set of actions;
SM S B* x is the set of states, consisting of the stack context and the current node;
TM : SM XAM + D(Sas is the transition function such that for s = ((x).9) E SM and action AM, the distribution dr (s, a) is defined as:
1. if the vertex q is a call port, i.c. q = (b, en) E Call, then 6M ((x, en) en) 1:
2. if the vertex is an exit node, i.e. q ex E Ex, then if x = (0) then the process terminates and otherwise as)
exr) where (b, ear) Ret((b) and
== (w', b):
3. otherwise, (s, (()), = 5(g. a)(')
the reward function rar Sar x A. - such that for s = ((m), 4) E SM and action a E Aas, the reward (s. is zero if is either a call port or the exit node, and otherwise TM (8, a)({s)) .q)) = =r(g, (q'). We call the maximum value of the absolute one-step reward the diameter of an RMDP and denote it by Tmax max, (r(s, a)).

---

Given the semantics of an RMDP M as an (infinite) MDP [M]. the concepts of strategies (also called policies) as well as positional strategies are well defined. We distinguish a special class of strategies- called stackless strategies that are deterministic and do not depend on the history or the stack context at all.
We are interested in computing strategies o that maximize the expected total reward. Given RMDP M, a strategy a determines sequences X, and Y, of random variables denoting the 7th state and action of the MDP [M]. The total reward under strategy and its optimal value are respectively defined as
ETotal
M (s) = lim E (s) |E ISSEN r X()
ETotal M (s)
sup ETotal," (s).
N-000
For an RMDP M and state s, strategy is called proper if the expected number of steps taken by M before termination when starting at s is finite. To ensure that the limit above exists, as the sum of rewards can otherwise oscillate arbitrarily, assume the following.
Assumption (Proper Policy Assumption). All strategies are proper for all states.
We call an RMDP that satisfies Assumption 1 a proper RMDP. This assumption is akin to proper policy assumptions [7] often posed on the stochastic shortest path problems, and ensures that the total expected reward is finite. The expected total reward optimization problem over proper RMDPs subsumes the discounted optimization problem over finite-state MDPs since discounting with factor is analogous to terminating with probability 1-À at every step [36]. The properness assumption on RMDPs can be enforced by introducing an appropriate discounting (see Appendix F).
Undecidability. Given an RMDP M, an initial node v, and threshold D, the strategy existence problem is to decide whether there exists strategy in [M] with value greater than or equal to D when starting at the initial state ((W), 9), i.e., at some entry node q with an empty context. Theorem 1 (Undecidability of the Strategy Existence Problem). Given a proper RMDP and thresh- old D, deciding whether there exists a strategy with expected value greater than D is undecidable.
PAC-Icarnabiliity Although it is undecidable to determine whether or not a strategy can exceed some threshold in proper RMDP, the problem of e-approximating the optimal value is decidable when parameters Co. À and (defined below) are known. Our approach to PAC-Icarnability [1] is to learn the distribution of the transition function ó well enough and then produce an approximate, but not necessarily efficient, evaluation of our learned model.
To allow PAC-learnability, we need further nuanced notion of e-proper policies. A policy is called e-proper, if it terminates with a uniform bound on the expected number of steps for all M' that differ from M only in the transition function, where Eygs,ee then say that M' is e-close MM), and where the support of 8 (q. a) subset of the support of dar (g, a) for all q E S and a E A. An RMDP is called e-proper, if all strategies are e-proper for M for all states of the RMDP.
[6,(q, ()) - 5x (q, a)) S E (we
Assumption 2 (PAC-learnability). We restrict our atlention to e-proper RMDPs. We further require that all policies have falling expected stack height. Namely, we require for all M' E-close to -M and all policies a that the expected stack height in step k is bounded by some function M¹, Co -.- Prun (k), where co 2 1 an offset, Il E]0, 1] is the decline per step, and Prun (k) is the likelihood that the RMDP M' with strategy a is still running after l steps. We finully require that M' (((0),9)) $ for some b. the absolute expected value from every strategy is bounded: |ETotal
Theorem 2. For every E-proper RMDP with parameters Co, 1l, and b, ETotal (s) is PAC-learnable
These parameters can be replaced by discounting. Indeed, our proofs start with discounted rewards, and then relax the assumptions to allow for using undiscounted rewards. Using a discount factor X d translates to parameters = I-x Co = =1 r-x and μ = 1-X.
3 Recursive Q-Learning for Multi-Exit RMDPs
While RMDPs with multiple exits come with undecidability results, they are the interesting cases as they represent systems with an arbitrary call stack. We suggest an abstraction that turns them into a fixed size data structure, which is well suited for neural networks.
5

---

Given proper recursive MDP M = (M My)) with M, - N;, B,, Y, En,, Ex, 8g, r2) with semantics [M]] (AM. Sas. Tas), the optimal total expected reward can be captured by the following equations OPT (M) For every & E B* and q E Q:
u(( en)
q en) Call
g E Ex, (0) E Ex, (b, E Ret(b), n=((''
v(()).g)
u(()'), (b, max (r(q. a)+ Σ p(dla, a))(()))))) aEAla)
otherwise.
d'EQ
These equations capture the optimality equations on the underlying infinite MDP [M]. It is straight- forward to see that, if these equations admit solution, then the solution equals the optimal total expected reward [32]. Moreover, an optimal policy can be computed by choosing the actions that maximize the hight-hand-sie. However, since the state space countably infinite and has an intricate structure, an algorithm to compute solution to these equations is not immediate.
To make it accessible learning. we abstract the call stack (x, b) to its exit value, i.e. the total expected reward from the exit nodes of the box b, under the stack context (K). Note that when a box called, the value of each of its exits may still be unknown, but it is (for given strategy) fixed.
Naturally, if two stack contexts (x, b) and (x', b) achieve the same expected total reward from each exit of the block b, then both the optimal strategy and the expected total reward, are the same.
This simple but precise and effective abstraction of stacks with exit values allows us to consider the following optimality equations OPT cont (.). For every s S k. q E Qi. v E IR LExl;
en)v',en)lv' + (e(v,.)) v(g)
= (b, en) E Call q Ex
r(v,g)
max a() E pla'la, aEA(g)
otherwise.
Q'EQ
Here v is vector where v(ex) is the (expected) reward that we get once we reach exit ex of the current component. Informally when a box is called, this vector is being updated with the current estimates of the reward that we get once the box is exited. The ex entry of this vector v' =y=( v==(x(v, g')) is =(v, (6, ex)), which is the value that we achieve from exit (b, ez).
This continuous-space abstraction of the countably infinite space of the stack contexts enables the application of deep feedforward neural networks [18] with finite state encoding in RL. It also provides an elegant connection to the smoothness of differences exit values: all exit costs are changed by less than s, then the cost of each state within a box changes by less than E, too. The following theorem connects both versions of optimality equations.
Theorem (Fixed Point). Ify is a fixed point of OPT and x is a fixed point of OPT then v) x0, 9) Moreover, any policy optimal from (0. q) is also optimal from (10),4). q)-
We design generalization of the Q-learning algorithm [40] for recursive MDPs based the optimality equations OPT shown in Algorithm 1. We implement several optimizations in our algorithm. We assume implicit transitions from the entry and exit ports of the box to the corresponding entry and exit nodes of the components. A further optimization is achieved by applying a dimension reduction on the representation of the exit value vector by normalizing these values in such way that one of the exits has value O. This normalization does not affect optimal strategies as, when two stacks incur similar costs that they have the same offset between the cost of each exit, the optimal strategy is still the same, with the difference in cost being this offset.
While the convergence of Algorithm 1 is not guaranteed for the general multi-exit RMDPs, the algo- rithm converges for the special cases deterministic proper RMDPs and 1-exit RMDPs (Section 4). For the deterministic multi-exit case, the observation is straightforward the properness assumption reduces the semantics to be directed acyclic graph, and the correct values are eventually propagated from the leafs backwards.
Theorem 4. Tabular Recursive Q-learming converges the optimal values for deterministic proper multi-exit RMDPs with learning rate of when all state-action pairs are visited infinitely often.

---

Algorithm 1: Recursive Q-learning
Initialize Q(s, vt a) arbitrarily
while not converged do
V -00
stack 0
Sample trajectory T ((3,a,7,)';...)) for a, in do
Update a; according to learning rate schedule if entered box then
{sexits.... :.xi: Sexit, } getExits(s'))
o' + Amixx'AAlmmm) Q (Sexity U1 a'), ..... A(saa) (feeii, U, o,)')
11
Uynin min((())
12
o' + e' 2'min
Qss + (1=,,)((s,,,)))))))))))) a max stack.push(v)
Q(5', + m'mnn)
13
14
15
v vt
16
else if exited box then
[Sexits..... Sexit,, + getExits(s))
18
Set k such that 8 Sexit,
v,) v - stack.pop()
aa)) + ar o(k)
20
21
else
Q v, (1 -11-a))((s, v, + as(r max,e v'
23
end
24
end
25 end
return Q
4
Convergence of Recursive Q-Learning for Proper 1-exit RMDPs
Recall that a proper 1-exit RMDP a proper RMDP where, for each component Mi, the of exits Ex; singleton. For this special case, show that the recursive Q-learning algorithm converges to the optimal strategy. The optimality equations OPT (M) (similar [15]) can simplified the case of 1-exit RMDPs whose unique fixed point solution will give us the optimal values of the total reward objective. For every E Q:
(r(en) + z(b, ex') max A(r) a(),))+ (().) E d'EQ
q = (b, en) E Call, ez = Exy())
x(q) =
otherwise.
We now denote the system of all these equations in a vector form as 7 F(F). Given a 1-exit RMDP, we can easily construct its associated equation system above in linear time.
Theorem (Unique Fixed Point). The vector consisting of ETotal M (g) values is the unique fixed point of F. Moreover, a solution of these equations provide optimal stackless strategies.
Note that for the 1-exit setting, Algorithm simplifies to Algorithm since v is always 0 and Vnin is always the maximum Q-value for the exit. The convergence of the recursive Q-learning algorithm for 1-exit RMDPs follows from Theorem and stochastic approximation [40, 8).
Theorem 6. Algorithmm 2 converges to the optimal values in 1-exit RMDP when the learning rates satisfy E a = Do, Exe a? < oc, and all state-action pairs are visited infinitely often.
In order to show efficient PAC learnability for e-proper 1-exit RMDP M, it suffices to know an upper bound on the expected number of steps taken by M when starting at any vertex with the empty stack content, which will be denoted by K.
Theorem (Efficient PAC Learning for 1-Exit RMDPs), For every e-proper 1-exit RMDP with diameter mao and the expected time to terminate S K, ETotal (s) is efficiently PAC-learnable.

---

Algorithm 2: Recursive Q-learning (l-exit special case)
Initialize ((s, a) arbitrarily while not converged do Sample trajectory T ~ {(,,a,7,'))..)) for T,& in do Update a; according to learning rate schedule if entered box then
Soxit f- getExit(s')) ((s,a)=
(1 - as)Q(s, a) + as(r - max Q(8, a') + maxx'eA(eeu) (Hexits d')) else if exited box then
(ss (1 Qs)Q(s,a) ar(r)
11
else
((s (1- a=)=a))((saa) + as
aax Q(s',
13
end
14
end
15
end
return Q
5 Experiments
We implemented Algorithm in tabular form well with neural network. For the tabular implementation, we quantized the vector v directly after its computation to ensure that the Q- table remains small and discrete. For the neural network implementation used the techniques used in DQN [30], replay buffers and target networks, for additional stability. The details of this implementation can be found in the appendix.
consider three examples: one to demonstrate application of Recursive Q-learning for syn- thesizing probabilistic programs, to demonstrate the use of a context-free reward machine. We compare Recursive Q-learning to Q-learning where the RMDP is treated MDP by the agent, i.c., the agent treats stack calls and returns as if they were normal MDP transitions.
demonstrate convergence in the single-exit setting, and one
5.1 Cloud computing
The cloud computing example, introduced in Example 1, is a recursive probabilistic program with decision points for RL agent optimize over. The optimal strategy is select the reliable server and to never upgrade. This strategy produces an expected total reward of 5.33425. Figure 3 shows that tabular Recursive Q-learning with discretization quickly converges to the optimal solution on this multi-exit RMDP while Q-learning oscillates around suboptimal policy.
5.2 Infinite spelunking
Consider a single-exit RMDP gridworld with two box types, 1 and 2, shown at the bottom the figure to the right. These box types are the two types of levels in infinitely deep cave. When falling or descending to another level, the level type switches. Passing over trap, shown in red, results in the agent teleporting to random position and falling with probability 0.5.
The agent has fallen into the cave at the position denoted by I without climbing equipment. However, there climbing equipment in one of the types of levels at known location denoted by E. The agent has four move directions-norte east, south, west-as well as an additional action to descend further or ascend. Until the climbing equipment is obtained, the agent can only descend. Once the climbing equipment obtained, the traps longer affect the agent and the agent can ascend

---

Cloud
Spelunking
Palindrome
50
RQL (ours)
-5.2
QL RMDP
-50
Tocll reward
0-
-5.6
-550
-5.8
-000
Qt RMDP
(ours)
-100
DON RMDP
RQL (ours)
6.0
2655
Traliiing stop
Training step
Training step
Figure 3: Learning curves. Ten runs were performed for each method. The mean is shown as dark line. The region between the 10th and 90th percentile shaded. RQL refers to tabular Recursive Q-learning, QI + RMDP refers to using tabular Q-learning on the RMDP, Deep RQL refers to Deep Recursive Q-learning, and DQN RMDP refers to using Deep Q-networks on the RMDP.
only from the position where it fell down. With probability 0.01 the agent ascends from the current level with the climbing gear. This has the effect of box-wise discounting with discount factor 0.99. The agent's objective is to leave the cave from where it fell in as soon as possible. The reward is -1 on every step.
There are two main strategies to consider. The first strategy tries to obtain the climbing gear by going over the traps. This strategy leads to an unbounded number of possible levels since the traps may repeatedly trigger. The second strategy avoids the traps entirely. The figure to the right shows partial descending trajectories from these strategies, with the actions shown in green, the trap teleportations shown in blue, and the locations the agent fell down from are shown small black squares. Which strategy is better depends on the probability of the traps triggering. With trap probability of 0.5, the optimal strategy is try and reach the climbing equipment by going over the traps. Figure 1 shows the convergence of tabular Recursive Q-learning for 1-exit RMDPs to this optimal strategy while the strategy learned by Q-learning does not improve.
5.3 Palindrome gridworld
To demonstrate the ability to incorporate context-free objectives, consider a 3 x 3 gridworld with a goal cell in the center and a randomly selected initial state. The agent has four move actions north,, east, south, west-and a special control action. The objective of the agent is to reach the goal cell while forming action sequence that is palindrome of even length. What makes this possible is that when the agent performs an action that pushes against a wall of the gridworld, no movement occurs. To monitor the progress of the property, we compose this MDP with a nondeterministic pushdown automaton. The agent must use its special action to determine when to resolve the nondeterminism in the pushdown automaton. Additionally, the agent uses its special action to declare the end of its action sequence. To ensure properness, the agent's 's selected action is corrupted into the special action with probability 0.01. The agent is given a reward of 50 upon success, -5 when the agent selects an action that causes the pushdown automaton to enter rejecting sink, and -1 on all other timesteps.
Figure 3 shows the convergence of Deep Recursive Q-learning an optimal strategy on this example, while DQN fails to find a good strategy.
6 Related Work
Hicrarchical RL is an approach for learning policies on MDPs that introduces hierarchy in policy space. There are three prevalent approaches to specify this hierarchy. The options framework [37] represents these hierarchies policies each with starting and termination condition. The hierarchy of abstract machines (HAM) framework [31] represents the policy as as hierarchical composition of nondeterministic knite-state machines. Finally, the MAXQ framework [13] represent the hierarchy using a programmatic representation with finite range variables and strict hierarchy among modules. Semi-Markov decision processes (SDMPs) and hierarchical MDPs are fundamental models that appear the context of hierarchical RI. SMDPs generalize MDPs with timed actions. The RI. algorithms for SMDPss are based on natural generalization of the Bellman equations to accommodate

---

timed actions. Hierarchical MDPs model bounded recursion and can be solved by flattening to MDP, or by producing policies that are only optimal locally.
Recursive MDPs model unbounded recursion in the environment space. The orthogonality of can consider applying ideas in hierarchical RL to find a policy in an RMDP. The authors of [3] proposed using partially specified programs with recursion to constrain the policy space, but only considered bounded recursion. Hierarchical MDPs [37, 31, 13], and factored MDPs [12, 20] indeed offer compact representations of finite MDPs. These representations can be exponentially more succinct. However, note that finite instances of these formalism are not any more expressive than finite MDPs as instances of these formalism can always be rewritten as a finite MDP. On the other hand, recursive MDPs studied in this paper are strictly more expressive than fimite MDPs. Even 1-exit RMDPs may not be expressible as finite MDPs, due to potentially unbounded stack, but remarkably they can be solved exactly with finite tabular model-free reinforcement learning algorithm (Theorem 6) without needing to resort to ad-hoe approximations of the unbounded stack configurations.
recursion in environment space and in policy space means they are complementary
Context-free grammars in RL for optimization of molecules has been considered before by introducing bound on the recursion depth induce a finite MDP [25, 42]. Combining context-free grammars and reward machines was proposed as a future research direction in [24], where context-free reward machines have been first described in this paper. Recursive MDPs have been studied outside the RL setting [16], including results for 1-exit RMDP termination [16] and total reward optimization under positive reward restriction [15]. A convergent model-free RL algorithm for 1-exit RMDPss with positive cost restriction was proposed in [21]. The results on undecidability, on PAC-learnability, the introduction of the algorithm Recursive Q-learning. convergence results for Recursive Q-learning, and its deep learning extension are novel contributions of this paper.
7 Conclusion
Reinforcement learning so far has primarily considered Markov decision processes (MDPs). Although extremely expressive, this formalism may require "flattening" a more expressive representation that contains recursion. In this paper we examine the use of recursive MDPs (RMDPs) in reinforcement learning-a setting we call recursive reinforcement learning. A recursive MDP is a collection of MDP components, where each component has the ability to recursive call each other. This allows the introduction of an unbounded stack. We propose abstracting this discrete stack with continuous abstraction in the form of the costs of the exits of a component, Using this abstraction, we introduce Recursive Q-learning-4 tabular Recursive Q-learning converges to an optimal solution on finite 1-exit RMDPs, even though the underlying MDP has an infinite state space. We demonstrate the potential of our approach on a set of examples that includes probabilistic program synthesis, a single-exit RMDP, and an MDP composed with context-free property.
model-free reinforcement learning algorithm for RMDPs. We prove that
This project has received funding from the European Union's 's Horizon 2020 research and innovation programme under grant agreements 864075 (CAESAR), and 956123 (FOCETA). This work is supported in part by the National Science Foundation (NSF) grant CCF- 2009022 and by NSF CAREER award CCF-2146563. This work utilized the Summit supercomputer, which is supported by the National Science Foundation (awards ACI-1532235 and ACI-1532236), the University of Colorado Boulder, and Colorado State University. The Summit supercomputer is joint effort of the University of Colorado Boulder and Colorado State University.
Acknowledgments.
References
[1] Alckh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept.. UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
[2] Rajeev Alur, Sampath Kannan, and Mihalis Yannakakis. Communicating hierarchical state machines. In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages and Programming, pages 169-178, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
10

---

[3] David Andre and Stuart J. Russell. State abstraction for programmable reinforcement learning agents. In Eighteenth National Conference on Artificial Intelligence, page 119-125, USA, 2002. American Association for Artificial Intelligence.
[4] Thomas Ball and Sriram K Rajamani. Bebop: symbolic model checker for boolean programs. In International SPIN Workshop on Model Checking of Software, pages 113-130. Springer, 2000.
[5] Thomas Ball and Sriram K Rajamani. The SLAM toolkit. In Proceedings of CAV'2001 (13th Conference Computer Aided Verification), volume 2102, pages 260-264, 2000.
[6] Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete event dynamic systems, 13(1-2):41-7) 2003.
[7] Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathematics of Operations Research, 16(3):580-595, 1991.
[8] Vivek Borkar and Sean Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2))447-46)) 2000.
[9] G. Brockman, V. Cheung, L. Pettersson, Schneider, J. Schulman, Tang, and W. Zaremba. OpenAl Gym. CoRR, (bs/1606.015444 2016.
[10] Michael C. Corballis. The Recursive Mind: The Origins of Human Language, Thought, and Civilization. Princeton University Press, 2014.
[11] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introdaction to algorithms. MIT press, 2022.
[12] Thomas Degris and Olivier Sigaud. Factored markov decision processes. Markov Decision Processes in Artificial Intelligence, pages 99-126, 2013.
[13] Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of artificial intelligence research, 13:227-303, 2000.
[14] Javier Esparza, David Hansel, Peter Rossmanith, and Stefan Schwoon. Efficient algorithms for model checking pushdown systems. In International Conference Computer Aided Verification, pages 232-247. Springer, 2000.
[15] Kousha Etessami, Dominik Wojtczak, and Mihalis Yannakakis. Recursive stochastic games with positive rewards. Theor. Comput. Sci., 777:308-328, 2019.
[16] Kousha Etessami and Mihalis Yannakakis. Model checking of recursive probabilistic systems. ACM Trans. Comput. Log., 13(2):1::111::4, 2012.
[17] Kousha Etessami and Mihalis Yannakakis. Recursive markov decision processes and recursive stochastic games. J. ACM, 62(2):1:1111::6)) 2015.
[18] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
[19] Andreas Griesmayer, Roderick Bloem, and Byron Cook. Repair of boolean programs with an application to c. In International Conference on Computer Aided Verification, pages 358-371. Springer, 2006.
[20] Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19:399-4P8 2003.
[21] Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. Model-free reinforcement learning for branching markov decision processes. In Alexandra Silva and K. Rustan M. Leino, editors, Computer Aided Verification 33rd Interna- tional Conference, CAV 2021, Virtual Event, July 20-23, 2021, Proceedings, Part II, volume 12760 of Lecture Notes in Computer Science, pages 651 651-673. Springer, 2021.
11

---

[22] Theodore Edward Harris. The theory of branching process. Technical Report R-381-PR, Rand Corporation, May 1964.
[23] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2107-2116. PMLR, 10-15 Jul 2018.
[24] Rodrigo Toro Icarte Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. Reward machines: Exploiting reward function structure in reinforcement learning. J. Artif. Intell. Res., 73:173-208, 2022.
[25] Egor Kraev. Grammars and reinforcement learning for molecule optimization. CoRR, abs/1811.11222, 2018.
[26] Karim Lari and Steve Young. The estimation stochastic context-free grammars using the inside-outside algorithm. Computer speech & language, 4(1):35-56, 1990.
[27] Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic plan- ning and related stochastic optimization problems. Artificial Intelligence, (47(1):5-34, 2003. Planning with Uncertainty and Incomplete Information.
[28] Christopher Manning and Hinrich Schutze. Foundations of statistical natural language process- ing. MIT press, 1999.
[29] James D Meiss. Disferential dynamical systems. SIAM, 2007.
[30] V. Mnih, K. Kavukcouglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through reinforcement learning. Nature, 518:529 533,, February 2015.
[31] Ronald Parr and Stuart J Russell. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, pages 1043-1049, 1998.
[32] M. L.. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1994.
[33] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser,, I. Antonoglou, V. Panncershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalch- brenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu. T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529:484-489, January 2016.
[34] Thoralf Skolem. Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnumgsbereich. Dybusach, 1923.
[35] Robert Soare. Turing computability: Theory and applications. Springer, 2016.
[36] R. S. Sutton and A. G. Barto. Reinforcement Learnging: An Introduction. MIT Press, second edition, 2018
[37] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1- 2):181-211, 1999.
[38] Vladimir A Vatutin and Andrei M Zubkov. Branching processes. ii. Journal of Soviet Mathe- matics, 676):3407-3485, 1993.
[39] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David H Choi, Richard Powell, Timo Ewalds, and Petko Georgiev. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782):350-33 2019.
12

---

[40] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning. 8(3):279-22) 2929 1992.
[41] Christopher John Cornish Hellaby Watkins. Learning,ron delayed rewards. PhD thesis, King's College, Cambridge United Kingdom, 1989.
[42] Zhenpeng Zhou, Steven Kearnes, Li, Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific Reports, 9(1):1-10, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We characterized the applicability
of our method in terms of decidability and approximability. See Sections 3 and 4.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] RL for Recursive MDPs is too general for meaningful discussion of societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Mostly in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See appendix.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See appendix.
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] The inspiration for example I has been cited.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "sqpsM-UXZmy", "reviewer": "Reviewer_wbL5", "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).\n\nThe 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.\n\n", "questions": "I only have a few clarifying questions:\n- Were the domains 5.1 and 5.3 general RMDPs? It would be helpful if this were stated explicitly.\n- 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.", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n- The paper provides an analysis of a novel and interesting class of MDPs\n\nQuality\n- 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\n\nClarity\n- Given the technical nature of the paper, I thought the main ideas and results were presented clearly\n\nSignificance\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_AO3z9hDRj", "reviewer": "Reviewer_aWu3", "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.", "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?\n\nExample 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.\n\nI am not sure why HRL or factored RL methods cannot cope with the example presented in lines 94 to 108. Could you please clarify?\n\nWhy 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.\n\nWhy the comparisons are only against flat Q-learning?\n\nI 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.\n\nIt would be useful if the paper was more explicit about which concepts are known and which were proposed in this paper.", "limitations": "n.a.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nRMDP 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.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "L9-ZK9tUFdh", "reviewer": "Reviewer_dojD", "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.\n\nThe 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.\n\nUsing 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.", "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?\n\n2. 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?\n\n3. 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, \n\n4. 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.\n\n5. 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.\n\n6. 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.\n\n7. 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.\n\n8. 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?\n\n9. 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?\n\nMinor comments:\n- 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nBeyond 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.\n\nMy 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.)\n\nSeparately, 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.\n\nApart from that, I enjoyed reading this paper, and I think a number of research communities will benefit from its publication.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JBVmZG2wM17", "reviewer": "Reviewer_pptt", "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.", "questions": "Some questions that would be good to address:\n1. Is it easier or harder for users to define a recursive MDP than a flat MDP?\n2. What, precisely, is the relationship with hierarchical RL? Is the recursive MDP a special case of hierarchical RL where the structure is manually provided?\n3. 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.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* The paper is generally well written, with compelling motivation for why some problems should be treated as recursive MDPs.\n* The potential applications discussed on page 3 are great for explaining the motivation for the recursive MDP. \n* The experiments in Fig. 3 nicely illustrate three applications.\n* The paper is novel to the best of my knowledge. Formalizing the connections between MDPs and computability seem potentially impactful.\n\nWeaknesses\n* The tradeoffs involved in the paper are a bit unclear. See questions below.\n* 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)?\n* The formal definition of recursive MDPs was complicated and hard to follow (esp. L124 -- L135)\n\nMinor comments\n* L1 -- I didn't understand this sentence\n* L3 \"they must rely on the practitioner's ingenuity\" -- Nicely put!\n* L23 \"regularity assumptions\" -- Cite.\n* L32 \"to generalize its learning upon\" -- I didn't understand this sentence\n* L41 \"Unlike ... enables generalizability\" -- Where is this demonstrated/proven?\n* L83 \"single-exit\" -- Be consistent with \"1-exit\" and \"single-exit\"\n* Fig 1, Fig 2 -- I found these figures pretty hard to parse.\n* 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?\n* L127 -- L129 -- I found this discussion confusing.\n* L318 -- If this task requires memory, then using a Markovian Q-learning policy as a baseline seems a bit unfair.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept