Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems
Authors: Rushang Karia
Rashmeet Kaur Nayyar
Siddharth Srivastava
Venue: NeurIPS 2022 Accept (2022)
Keywords: Generalization
Sequential Decision Making
Transfer Learning
Stochastic Shortest Path Problems
Relational Abstractions
Model-based Policy Learning

Abstract: Several goal-oriented problems in the real-world can be naturally expressed as Stochastic Shortest Path problems (SSPs). However, the computational complexity of solving SSPs makes finding solutions to even moderately sized problems intractable. State-of-the-art SSP solvers are unable to learn generalized solutions or policies that would solve multiple problem instances with different object names and/or quantities. This paper presents an approach for learning \emph{Generalized Policy Automata} (GPA): non-deterministic partial policies that can be used to catalyze the solution process. GPAs are learned using relational, feature-based abstractions, which makes them applicable on broad classes of related problems with different object names and quantities. Theoretical analysis of this approach shows that it guarantees completeness and hierarchical optimality. Empirical analysis shows that this approach effectively learns broadly applicable policy knowledge in a few-shot fashion and significantly outperforms state-of-the-art SSP solvers on test problems whose object counts are far greater than those used during training.

Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems
Rushang Karia, Rashmeet Kaur Nayyar, Siddharth Srivastava
School of Computing and Augmented Intelligence Arizona State University
Tempe, AZ. 85281 U.S.A.
(Rushang. Karia, rmnayyar, siddharthss Gasu. edu
Abstract
Several goal-oriented problems in the real-world can be naturally expressed Stochastic Shortest Path problems (SSPs). However, the computational complex- ity of solving SSPs makes finding solutions to even moderately sized problems intractable. Sfate-of-the-ar SSP solvers are unable to learn generalized solutions policies that would solve multiple problem instances with different object names and/or quantities. This paper presents an approach for learning Generalized Policy Automata (GPAs): determimmiiiiiic partial policies that can be used to catalyze the solution process. GPAs are learned using relational, feature-base abstractions, which makes them applicable broad classes of related problems with different object names and quantities. Theoretical analysis this approach shows that it guarantees completeness and hierarchical optimality. Empirical analysis shows that this approach effectively learns broadly applicable policy knowledge a few-shot fashion and significantly outperforms state-o-thh--ae SSP solvers test problems whose object counts are far greater than those used during training.
Introduction
Goal-oriented Markov Decision Processes (MDPs) expressed as Stochastic Shortest Path problems (SSPs) have been the subject of active research since they provide a convenient framework for modeling the uncertainty in action execution that often arises in the real-world. Recently, research in deep learning has demonstrated success in solving goal- goal-oriented MDPs using image-based state representations (Tamar al., 2016; Groshev al., 2018). However, such methods require significant numan-engineeon effort in finding transformations like grayscale conversion, etc.. to yield repre- sentations that facilitate learning. Many practical problems however, are more intuitively expressed using relational representations and have been widely studied in the literature.
As example, consider planetary rover whose mission is collect all rocks of interest from planet's 's surface and deliver them to the base for analysis. Such a problem objective is not easily described in an image-based representation (e.g.. visibility is affected by line of sight) but can be easily described using relational description language such as first-order logic. Finding suitable image- based representations for such problems would be counter- productive and difficult. Furthermore. image-based deep learning methods often require large amounts of training data and/or are unable to provide guarantees of completeness and/or convergence.
counter-productive
Many real-world problems such as the rover example above can be readily expressed as SSPs using symbolic descriptions that can be solved in polynomial time in terms of the state space. SSP algorithms use combination of pruning strategies (e.g.. heuristics (Hansen and Zilberstein, 2001)) that can eliminate large parts of the search space from consideration thereby reducing the computational effort
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

expended. In spite of such optimizations, major hurdle is the state spaces grow exponentially as the total number of objects increases. Existing SSP solvers would have difficulty scaling to rover problems with many locations and/or rocks. The pruning strategies employed by these SSP solvers do not scale well because they do not use knowledge that could have been exploited from solving similar problems. One solution to this problem is to compute simple generalized policy: move the rover to the closest available location with an interesting rock, try loading the rock until it succeeds, navigate back to the base, unload it, and reiterate this process until all interesting rocks are at the base. This generalized policy can be used to solve any rover instance with larger numbers of locations and rocks sharing similar goal objective.
since the
Related work in Generalized Planning addresses the problem of computing generalized policies by learning reliable controllers for broad classes of problems (Srivastava et al., 2008; Bonet et al., 2009; Aguas et al., 2016). Recently, Deep Learning based approaches have been shown to successfully learn such policies (Toyer et al., 2018; Garg et al., 2020; Karia and Srivastava, 2022). A key limitation of such methods is the lack of interpretability and theoretical guarantees of the learned policy. this paper, we show that interpretable, generalized policies can be learned with guarantees of completeness and hierarchical optimality using solutions of very few, small problems with few objects.
The primary contribution of this paper is novel approach for few-shot learning of Generalized Policy Automata (GPAs) using solutions of SSP instances with small object counts. GPAs are non- deterministic partial policies that represent generalized knowledge that can be applied to problems with different object names and larger object counts. This process uses logical reature-based ab- stractions to lift instance-specific information like object names and counts while preserving the relationships between objects in a way that can be used to express generalized knowledge. GPAs learned using our approach can be used to accelerate any model-based SSP solver by pruning out large sets of actions in different, related, but larger SSPs with many objects. We prove that our approach is complete and guarantees hierarchical optimality. Empirical analysis on range of well-known benchmark domains shows that our approach few-shot learns GPAs using as few as three training problem instances and convincingly outperforms existing state-of-the-art SSP solvers and does so without compromising the quality of the solutions found.
The rest of this paper is organized as follows: The next section provides the necessary background. Sec. 3 describes our approach for using example policies in conjunction with abstractions to learn GPAs and using them for solving SSPs. We present our experimental setup and discuss obtained results in Sec. 4. Sec. provides a description of related work in the area. Finally, Sec. states the conclusions that we draw upon from this work followed by a brief description of future work.
2 BBcckrrond
Our problem setting considers SSPs expressed in a symbolic description language such as the Probabilistic Planning Domain Definition Language (PPDDL) (Younes et al., 2005). Let D = (P, A) be a problem domain where P and A are finite sets of predicates and parameterized actions. Object types, such as those used in PPDDL, can be equivalently represented using unary predicates. A relational SSP problem instance for domain D with a goal formula g over P and finite set of objects O is defined as a tuple P (O, S,S,AA A, C, so. g). A fact is the instantiation of a predicate p E P with the appropriate number of objects from O. A state s set of true facts and the state space S is defined as all possible sets of true facts derived using DD and O. Similarly, the action space A is instantiated using A and O. T S x x S - [0. 1] is the transition function and C: S x A x S + R+ is the cost function. An entry 1(8, a, 8') E T defines the probability of executing action a E A in a state s E and ending up in a state s E S, and c(s, a, s') E C indicates the cost incurred while doing so. Naturally, Σ. t(s, a, s') 1 for any E S and E A. Note that refers to the instantiated action a(o)...., 0,), where 01.... On E O are the action parameters. We omit the parameters when it is clear from context. 5p S is a known initial state. A goal state sy is a state such that 8g F g. For any action a E A and any goal state sg E S, c($g a. $g) = 0 and t(sg. a, sg) = 1. Additionally, termination (reaching state such that = g) in an SSP is inevitable making the length of the horizon unknown but finite (Bertsekas and Tsitsiklis, 1996).
Running example: The planetary rover example can be expressed using domain that consists of predicates connected (1z, 1y), interesting(r.)) rover-at(L,) ), in-rover(ra). rock-at(rz; 12), and param- eterized actions load(r (2), anload(rz, 12), and move(l,,, 1y). Object types can be denoted using
2

---

uary predicates location((4) and rock(rz). l.. lg. and r. are parameters that can be instantiated with different locations and rocks thus allowing for an easy way to express different problems. Action dynamics are described using closed-form probability distributions (e.g., loading a rock could be mod- eled so that the rover pieks up the rock with a probability of 0.8) and this forms the transition function. A simplified SSP problem that ignores connectivity and consists of two locations, base location, and two rocks can be described using a set of objects O = {/1, 12, husss T1, 12772.. A state in this SSP seg that describes the situation where 72 is being carried by the rover and 71 is at l2 can be written as Seg = {location(()) ), location(12). location((nae) rock(ri), ), rock(r2), in-rover(r2), rock-at(ri ) The goal of delivering all the rocks to the base can be expressed as Vx rock(z) = rock-at(2; (2, loase). Executing any action can be assumed to expend some fuel and as a result, the objective is to deliver all the rocks to the base in way that minimizes the total fuel expended.
solution to an SSP a deterministic policy æ : - A, that a mapping from states to actions.
A proper policy is one that is well-defined for all states. A complete proper policy is one for which termination is guaranteed from all possible states. By definition, SSPs must have at least one complete proper policy (Bertsekas and Tsitsiklis, 1996). This can be overly limiting in practice since such formulation does not model dead end states: states from which the goal is reachable with probability 0. A weaker formulation of an SSP stipulates that the goal must be reachable with a probability of I from Su i.e. whose solution is a partial proper policy that is well-defined for every state reachable from Sg. As such, we focus (Kolobov et al., 2012) that only require the existence of at least one partial proper policy. Henceforth, use the term SSPs to refer to GSSPs and focus only partial proper policies.
broader class of relaxed SSPs called Generalized SSPs (GSSPs)
The value of a state s when using a policy л is the expected cost of executing r(s) when starting in and following x thereafter: (s) = E>'es (s, (s)), s') [c(s, x (s), s') + (s')s) (Sutton and Barto, 1998). Naturally, V*(ss) = oo if ग is not a partial proper policy. V is known as the value function. V the optimal value function and can be described using the Bellman optimality equation: V*(s)= = m Eves t(s, a, s [c(ss, a, s') + (*))'
In this paper, we focus on optimality w.r.t. given initial state. The optimal policy x² for SSP P w.r.t. so is policy that is better than or equal to all other policies i.e. V (so) < V (50) for any policy æ. SSP solvers iteratively apply the Bellman optimality equation starting from Su to compute a policy, and under certain conditions, have been proved to converge policy that is c-consistent with nt (Hansen and Zilberstein, 2001; Bonet and Geffner, 2003).
Let Fo and F3 be two sets of features. We use feature-based abstractions to lift problem-specific characteristics like object names and numbers in order to facilitate the learning of generalized knowledge that can be applied to problems irrespective of differences in such characteristics. Given any SSP P. we define state abstraction as function & Fa, S - 5 that transforms the concrete state space S of P into a finite abstract state space S. Similarly, action abstraction 3 F3, S, A + A transforms the action space to finite abstract action space. Typically, [S] S |S] and | < |A]. We use afF..)) s) and π = 3(F s, a) to represent abstractions of a concrete state s and action a. In this paper, we utilize feature sets automatically derived using canonical abstraction (Sagiv et al., 2002) to compute such feature- based representations of and a. This described in Sec. 3.1.
3 Our Approach
Our objective is exploit knowledge from solutions of SSP instances with small object counts to learn Generalized Policy Automata (GPAs) that allow effective pruning of the search space of related SSPs with larger object counts. We accomplish this by using solutions to a small set of training instances that are easily solvable using existing SSP solvers, and using feature-based canonical abstractions to learn a GPA that encodes generalized partial policies and serves as a guide to prune the set of policies under consideration. We provide brief description of canonical abstraction in Sec. 3.1, define GPAs in See. 3.2, and describe our process to describe our method (Alg. 1) for solving SSPs and state its theoretical properties in S.c.
learn GPA in Sec. 3.2.1. We then
3.1 Canonical Abstraction
Canonical abstractions, commonly used in program analysis, have been shown to be useful in generalized planning (Srivastava et al., 2011; Karia and Srivastava, 2021). Canonical abstractions
3

---

Abstract State
Concrete State $1
rock-ad 12)
Roles
boss
4
lg
1
frock)
rock(ra) : 12
0
0
1/2
rrock, interesting)
interesting(Ts) (Fa)
location(( ( buses 1
1
0
1/3
(location)
base((.)) l
Canonical Abstraction
1/
(location, base}
rock-at(r 1x)
rock-ad (vh,, vbs)
4
1
lg
Concrete State $2
0
1
0
0
1/1
1/2
144
rock(rs) : M1, rr, Pa, 74. 76
0
0
1
0
1/2
0
0
0.5
0
interesting(rs) (Ta) To, To
0
0
0
1
1/2
0
0
0
1
location(le) booses (1, 242224 base((L)) hoase
74
0
0
0
4/3
0
0
0
0
55
0
0
0
4/4
0
0
1
0
0
0
example of how canonical abstraction can be used lift problem-specific characteristics like object names and numbers. $1 and 82 are example states of two different problems.
Figure 1:
group together multiple objects in a state using object roles. Given a concrete state s and an object o, the set of unary predicates that satisfies is known the role of o. O-ary predicates represented as unary predicates with a default 'phantom' object.
Let di be role. Then we define so (s) as function that returns the set of objects that map to tb in concrete state 8. Similarly, for any given predicate p.. E P where n is the arity, Pp- (p........)) wia) (s) is defined as the set of all n-ary predicates in that are consistent with the roles composing the predicate Pa (v. Wn),
i.., Pp.. (p..
{Pn(o1...... on) Pp) (o1......n) E s, E Pv. (s)).
The value of role 1 in concrete state is given as max(2, (s)) to indicate whether there 0, 1, or more than objects satisfying v/. Since relations between objects become imprecise when grouped as roles, the value of pm (1/1...... 1/,)) in is determined using three-valued logic and is 0 if ... (s) = 0. if (Pp..v................. (s) 1sp (+)l x... x 19 (s)]. and otherwise.
Let V be the set of all possible roles and P. be the set of predicate names p P of arity i for domain D, then P. P, x [To] is the set of all possible relations of arity i between roles. We define the feature set for state abstraction as Fa = T U,V. P, where N is the maximum arity of any predicate in D. We define state abstraction (F...) for given concrete state to return an abstract state 8 as total valuation of F,, using the process described above. Similarly, we define the feature set for action abstraction as FB+ = V. The action abstraction (FF,, a) for concrete action a(o)..... On) when applied to returns an abstract action a(v1, ......... tha) where the action name 7 = a and v) is the role of the parameter o,, i.e., Og E Po. (s) for any vi E
Fig. 1 provides an intuitive example of how canonical abstraction can be used to lift instance-specific information. The figure describes two concrete states 81 and 82 from two different problems. si contains 2 rocks and 3 locations whereas 82 contains 6 rocks and 4 locations. There are four roles in For example, in $1, 71 maps to the the role for rock 4/1, and r2 maps to the role for an interesting rock 4/2, i.e., Pu., (s1) the seree-valued representation of values between different roles. For example, rock-at (1/1, v/a) is interpreted as the set of rocks that are at some location, while rock-at 1/2, v/4) is interpreted as the set of interesting rocks that are at the base. Since rock-at(r1,4 12) does not appear in 81, rock-at v/, v/s) evaluates to 01.5 to indicate that there are some rocks that are at some, but not all, locations. Similarly, since all interesting rocks are at the base location, rock-at (22, 144) evaluates to I.
{r1} and Pu,, (s1)
{rz). The abstract relation rock-ar( sbs Wy) provides
The key aspect of abstraction comes from the observation that the relation rock-at(ws, viy) remains the same for $2 even though 82 has many more objects than $1. The same high-level interpretations of the relations are captured while lifting low-level information like object names and numbers.
3.2 Generalized Policy Automata
We introduce Generalized Policy Automata (GPAs) as compact and expressive non-deterministic finite- state automata that encode generalized knowledge and can be represented as directed hypergraphs.

---

GPAs impose hierarchical constraints on the state space of an SSP and prune the action space under consideration, thus reducing the computational effort of solving larger related SSP instances.
Definition 3.1 (Generalized Policy Automaton). Let 3 and be a set of abstract states and actions. Generalized Policy Automaton (GPA) G (V. is a non-deterministie finite-state automaton that can be represented as a directed hypergraph where the set of vertices V = 3. & C V x P(V) \ A. where P(V) the powerset of V, is set of directed hyperedges s.t. each hyperedge e & is tuple (Bwee Edess: Eacr) representing a start vertex, a set of result vertices, and an action label.
Definition 3.2 (GPA Consistent Policy). A policy и for an SSP P is defined to be consistent with a GPA 9 iff for any states 8, 8 E S and any action a E A whenever x (s) = a and t(s, a, s') > there (Esre, Ederr, Eacr) E 3 where
exists hyperedge
Eyre.
dest. and ā Eact-
Definition 3.3 (Hierarchically Optimal Policy). A policy π given a GPA 9 is hierarchically optimal for an SSP P iff ı minimal among all possible policies x that are GPA consistent w.r.t. G, i.e., (=(os)= - V" (so).
3.2.1 Learning GPAs
It is well-known that solutions to small problems can be used to con- struct generalized control structures that can assist in solving larger prob- lems. We adopt similar strategy of the learn-from- from- coom-small-exaane -xaallexamples ap- proach (Wu and Givan, 2007: Karia and Srivastava, 2021, 2022) and compute GPAs iteratively from
$0
60
small training set containing solu- tions of similar SSP instances.
$y
GPA 9 Merged GPA
To form our training set, we use a library of solution policies IT [m1, ] for small SSPs PI....,., Ps that can be casily (and optimally) computed by existing SSP solvers. We use the transition function for P; to convert each pol- icy E II to set of transitions T; {(s, a, s')ss, S A,, (s() a. t,,, s') 0}. We then construct our training set T = Ti U... U as a set of concrete transitions.
Figure 2: A high-level overview of how we merge different GPAs. All edges with the same color represent hyperedge. For example, the blue colored hyperedge ς is (अ,, (30, 31, 3y),0)).
The GPA In learned from a finite set of concrete transitions T is defined as follows. We first initialize a GPA In (1,(). Next, we convert T into an abstract transition set T = ((a(Fa s), ((F s, a), aFF,, (s,a, Tj. We then form the vertex set by using all abstract states in i.., V = [3, s²} for every (3, a. s') E T. Similarly, we convert each abstract transition into a hyperedge and add it to the edge set, i.e. E = E U (s, {s'), a) for every (s, ū, 8)) E TT. Finally, we compress In by replacing edges in E that have the same start nodes and labels but different destina- tions with single edge that combines the destinations of the edges, i.e., for any two edges e., e E deest
s.t. eT sres et dest # de dens and T = e E Σ {e U ((eT.me me, e dest Ue? dest, et act) Fig. 2 provides a high-level overview of our procedure for merging GPAs. Henceforth, we drop the subscript II from In when it is clear from context.
dest
3.3 Solving SSPs using GPAs
The key intuition behind our method is use the GPA prune policies that not consistent with the GPA from the search process. We accomplish this by solving a GPA constrained problem that satisfies the constraints encoded by the GPA. We define GPA constrained problem as follows:
Definition 3.4 (GPA constrained problem). Let P (O, S, A, T, C, so. g) be an SSP for a domain 'D
and let g = EV.E) be a GPA. A GPA constrained problem Plz (O, S, A, T, C² $o.g) g) is defined with a cost function C" S x A S + R+ such that C' C'(s,a, s Cls, a, s") when there exists
5

---

Algorithm GPA acceleration for SSPs
Require: SSP P= = A, 50, g). GPA 9 - (V, Feature Sets Fa, Pa, Abstraction Functions a, B
1: C" = C (copy over the cost function of P)
2: for (8,a, S A x S do
3: 5, 8, + a(F., s), 0,,(Fss 8, ar s')
4: if there is no edge E s.t. Ext 8, E Cdear and Eaer then
5:
a, s
6: end if
7: end for
A.T.C", 8: P' initializeValleeuunee ValueFuunction() (Typically using heuristics or randomly)
9: Vi <- initialize
Vpr, Tp. 5 -ptimallySSovvSSSP(P Vp.) (Using the Bellman optimality equation) 11: if Tp. is partial proper policy then
12: return pp. (Return constrained policy)
13: else
14: Vp. TP + optimallySotveSSPPP.Y. VT.) {Using the Bellman optimality equation)
15: return Tp [Return partial proper policy for P]
16: end if
hyperedge č = (e desr Eaci) E where 3 = Eyes s E dests and 7 = Eact and C" there is such hyperedge.
a, s. co
The goal of modifying the cost function is to prevent concrete transitions whose abstract translations absent in the GPA from being used when performing Bellman updates for Plg. Actions belonging to such transitions cannot appear in TPpp since their costs would be cc. As result, Pla is not SSP and the existence of partial proper policy is not guaranteed in Plg. Note that every optimal policy Tio for Plz is hierarchically optimal for SSP P given a GPA G. Our overall objective is to compute such hicrarchically optimal policies in a way such that they are approximately as cost effective the optimal policy while requiring fraction of the computational effort.
Given a GPA J. Alg. works as follows. Lines 1-8 create GPA constrained problem P'. Next, line 10 optimally solves p' using any off-the-shelf SSP solver with a randomly initialized value function (line 9). If the computed policy T.. is partial proper policy then it is returned immediately (lines 11-12) else Alg. uses new instance the SSP solver compute a policy for using Vp. as the bootstrapped initial value function. Information such as whether a state is dead end, etc., is not carried over. Line 14 then optimally solves using Vp, as the initial value estimates and returns a partial proper policy for P. Since Vp, is only used as an initial bootstrapping estimate for P. an SSP solver will only return a policy xp that better than or equal Tp, following standard results on policy improvement for value iteration (Sutton and Barto, 1998). The following result shows that Alg. computes bierarchically optimal policies.'
Theorem 1. When Alg. 1 returns a constrained policy Tpr (line 12) for an SSP P given a GPA g then Tp. is hierarchically optimal.
Proof (Sketch). Intuitively, Alg. 1 creates a new problem P (lines 1-8) using the original cost function of P. The cost function for a concrete transition (s, (s,a,88) S A x S is oc iff the corresponding abstract transition not part of a hyperedge in G. As result, P' Plz. and any partial policy Tp. for δ is a GPA consistent policy. Since Alg. optimally solves P' (line 10), the returned policy is hierarchically optimal.
O
Alg. 1 computes T Pl for Pla in the space cross-product of the states of the GPA ğ with the states of P. similar to HAMs (Parr and Russell, 1997). As seen in empirical analysis in Sec. 4, observe that a small set of example policies are sufficient to capture rich generalized control structures that encoded by such hierarchically optimal policies. Alg. 1 computes such policies within fraction of the original computational effort and in most cases with costs comparable to Tp.
Please see Appendix A.1 for the complete proof.

---

Theorem 2. Given a GPA 9 and an SSP P, Alg. 1 always returns partial proper policy.
Proof. Alg. I only returns if it computes partial proper policy at line 12 or partial proper policy for P line 15, which by definition always exists.
The next result indicates that the output of Alg. is hierarchically optimal or better in terms of the expected value at 80-
Theorem 3. Let V be the value funcctin for a policy я returned by Alg. for an SSP P using GPA G. Let Pla be the optimal value function for Plz. then V/ (so) _ V (sn).
Proof. If Alg. 1 finds partial proper policy TPis for Pla then it returns it immediately (lines 11-12), in which case (=(ss) = Vi (so). If Tiy is not partial proper policy then Vi (50) = co.
Since Alg. is complete (Thm. 2). æ is a partial proper policy where V*(sn) < cc.
Corollary 3.1. If (50) = V (so), then Alg. returns the optimal policy for P.
The following result indicates that only a finite set of training examples are needed to learn a GPA such that the constrained problem will always yield the optimal policy for a given domain D.
Theorem 4. Suppose D is domain, g is formula over the predicates in D's vocabulary, G is GPA s.t. for every SSP instance P of D whose goal is g, there exists an optimal policy Tp that is consistent with GI-- Then there exists finite set of policies 11* from which In- can be learned.
Proof. Since the sizes of the abstract state and action spaces 3 and A are finite, the size of In-- is finite and is bounded by |S| x |A| x [S]. For every E E & at most [Eaeu] different transitions are needed learn S. Since there is finite number of edges, a finite amount of training data will suffice for learning Gn--
In the worst case, the cost functions of P and Plg are similar and no savings are obtained. However, in our empirical evaluation, we observed that typically very few and small training problems suffice to learn a compact GPA G that allows efficient computation of solutions for problems that are significantly larger than those used during training. Finding the right set of examples IIe from which I.- can be learned is interesting and non-trivial research problem that we leave to future work.
4 Experiments
We conducted an empirical evaluation on five well-known benchmark domains that were selected from the International Planning Competition (IPC) (Long and Fox, 2003), International Probabilistic Planning Competition (IPPC) (Younes et al., 2005), and robotic planning (Shah et al., 2020). As part of our analysis, we use the time required to compute a solution and measure the quality of the solutions found to determine whether GPAs allow efficient solving of SSPs.
We chose PPDDL as our representational language, which was the default language in IPPCs until 2011, 1. after which the Relational Dynamic Influence Diagram Language (RDDL) (Sanner, 2010) became the default. We chose PPDDL over RDDL since modern state-of-the- ohetth-arttttt solvers for PPDDL are available and since RDDL does not allow specifying the goal condition easily.
For our baselines, focus on complete solvers for SSPs. Deep Learning based approaches do not guarantee completeness and thus are not directly comparable with our work. We used Labeled RTDP (LRTDP) (Bonet and Geffner, 2003) and Soft-FLARES (Pineda and Zilberstein, 2019) which are state-of-the-art (SOA), complete SSP solvers. These algorithms internally generate their own heuristies for initializing the value function using the input domain and problem file. We used the inadmissible FF heuristic (Hoffmann, 2001) as the internal heuristic function for all algorithms since the baselines performed best using it.
We ran our experiments on a cluster of Intel Xcon E5-2680 v4 CPUs running at 2.4 GHz with 16 GiB of RAM. Our implementation is Python adaptation of mdp-lib (Pineda and Zilberstein, 2019). We utilized problem generators from the IPC and IPPC suites and those in Shah et al. (2020) for
Our source code is available at https: //:::://ii http//ggtttttttt////////tt...htt com/AAIR--11 WAt.//ARRR--aGGGAAAA 1ab/GRAPL
7

---

Impact of GPA acceleration on SOA solvers
Time:
LRTDP (Ours)
GPA Soft-LARRES (Ours)
Cost:
GPA
LRTDP
Soft-FLAES
LRTDP
FLAE-
LRTDP
Solt
Keva
Rover
Schedule
Delicate can
Gripper
120
100
Time 6x10
Cost
20
20
11
12
15
24
25
10
10
Problem ID (larger IDs correspond to larger object counts)
Figure 3: Impact of learned GPAs on solver performance (lower values better). Left y-axes and bars show solution times (in units of 1000 secs) for our approach and baseline SOA solvers (LRTDP and Soft-FLARES) Right y-axes and points show cost incurred by the policy computed by our approach and the hasclines. We use the same SSP solver as the corresponding baseline in our approach. Error bars indicate standard deviation (SD) averaged across 10 rums, For clarity, we only report results for the largest test problems and omit error bars from costs due to the low SDs. Open bars at the top indicate a timeout. A complete view of our empirical results is available in Appendix B.
generating the training and test problems for all domains. We provide a brief description of the problem domains below.
Rover(r, w, 5,5,0 o) A set of r rovers need to take images of o objectives, and pickup and drop samples that are present at one of w waypoints. This is an IPC domain that was converted to a stochastic version by modifying the pickup action to fail with a probability of 0.4 (leaving the state unchanged), Gripper(b) A robot with two grippers placed in an environment consisting of two rooms A and B. The objective of the robot is to transfer all the balls initially located in room A to room B. We modified the gripper to be slippery so that picking a ball has a 20% chance of failure.
Schedule( C, p) is IPPC domain that consists of set of p packets, each belonging one of C different classes that need to be queued. A router must first process the arrival of a packet in order to route it. The interval at which the router processes arrivals is determined by probability 0.94.
Keva P. h) A robot uses P keva planks to build a tower of height h. Planks are placed in a specific order in one of two locations, preferring one location with probability 0.6. Despite this simple setting, the Keva domain has been shown to be a challenging problem in robotics (Shah et al., 2020). Delicate Can(c) An arrangement of e cans on table of which one is a delicate can. The objective is to pick up a specific goal can. Cans can obstruct the trajectory to the goal can and need to be moved. They can be crushed with probability 0.1 (delicate cans with probability 0.8) and need to be revived.
Training Setup Our method learns GPAS in a few-shot fashion requiring little to no training data. For forming our training set, we used minimum of three and maximum of ten different solution policies (obtained using LAO" (Hansen and Zilberstein, 2001)) for each domain. The time required to learn GPA was less than 10 seconds in all cases of our experiments. Our training speed highlights the advantages of GPAs that can be quickly learned in a few-shot setting. Moreover, compared to neuro-symbolic methods, GPAS are not subject catastrophic forgetting and new training data can easily be merged with the existing GPA using the process described in Sec. 3.2.1.
Test Setup We fixed the time and memory limit for each problem 7200 seconds and 16 GiB respectively. To demonstrate generalizability, our test set contains problems with object counts that are much larger than the training policies used. The largest problems in our test sets contain least twice the number of objects than those used during training. For example, in the Keva domain, we use training policies with towers of height up to 6 and evaluate on problems with towers of height up to 14. The minimum and maximum number of problems that we used in our test set are 12 and 26 problems respectively. Additional information of our empirical setup such as problem parameters, hyperparameters used for configuring baselines, etc., is included in Appendix B.
4.1 Results and Analysis
Our evaluation metric compares the time required to find a partial proper policy. We also compare the quality of the computed policies by executing the policies for 100 trials with horizon limit of
8

---

100 and averaging the obtained costs. We report our overall results averaged across 10 different runs and report results up to one standard deviation. Results of our experiments are illustrated in Fig. 3.
In four out of five domains (Schedule, Rover, Keva, and Delicate Can), our approach takes significantly less time compared to the corresponding baseline. For example, in Schedule, the baselines timed out for all of the large test problems reported. GPAS are able to successfully prune away action transitions that are not helping, leading to large savings in the computational effort. The costs obtained for executing these policies are also quite similar to each baseline (c.g., Keva), showing that GPAs are capable of learning good policies much faster without compromising solution quality.
Our approach was unable to outperform the baselines in the Gripper domain. An interesting phe- nomenon that we observed was that training policies returned by LAO' were different for the case of even/odd balls due to tie-breaking and this led to the GPA not pruning actions as effectively. Nevertheless, we expected the GPA to outperform the baselines. We performed deeper investigation and found that the FF heuristic used is already well-suited to prune away actions that the GPA would have otherwise pruned. This results in additional overhead being added in our SSP solver from the process of abstraction. However, heuristics that allow such pruning are difficult to synthesize, and in many cases, are hand-coded by an expert after employing significant effort.
There was a decrease in the gains observed in the Delicate Can domain between problem IDs 10 and 11. We investigated this issue and found that the GPA constructed was unable to effectively prune transitions in problem ID 11. This is because the training policies that were used were not sufficient to learn GPA that could generalize well to larger problems in the Delicate Can domain. As result, Plg was not a partial proper policy for problem ID 11 and thus additional computation was required.
Finally, because of the fixed timeout used, the maximum time of the baselines was bounded, making the impact of GPAs appear smaller in larger problems. For example, in problem ID 25 (10) of the Rover (Delicate Can) domain, the Soft-FLARES (LRTDP) baseline timed out in all our runs, but it had found a policy that had comparable costs. However, when allowed to run to convergence, it took over 15000 seconds in a targeted experiment that we performed for investigating this issue.
5 Related Work
There has been plenty of dedicated rescarch to improve the efficiency for solving SSPs. LAO" (Hansen and Zilberstein, 2001) computes policies by using heuristics to guide the search process. LRTDP (Bonet and Geffner, 2003) uses a labeling procedure in RTDP wherein a part of the subtree that is c-consistent is marked as solved leading to faster ending of trials. SSiPP (Trevizan and Veloso, 2012) uses higrt-sighteednes by only considering reachable states up to states away and solving this constrained SSP. Soft-FLARES (Pineda and Zilberstein, 2019) combines labeling and short-sightedness for computing solutions. These approaches are complete and can be configured to return optimal solutions, however, they do not learn any generalized knowledge and as result cannot readily scale to problems with a larger number of objects.
Determinization-base approaches (Yoon et al., 2007: Pineda and Zilberstein, 2014) build sparse representations of SSP problems by reducing the branching factor in the "environment's 's choices" (the set of probabilistic effects of an action), while our approach uses abstraction to create abstract controllers that generalize solutions to SSPs and reduces the branching factor in the agent's 's choice (the set of applicable actions). Our approach always considers all possible outcomes of every action. This is a key advantage of our approach since GPAs are able to better handle unexpected outcomes when executing an action in the policy that would otherwise require replanning.
Boutilier et al. (2001) utilize decision-thhoretiie regression to compute generalized policies for first- order MDPs represented using situation calculus. They utilize symbolic dynamic programming to compute a symbolic value function that applies to problems with varying number of objects. FOALP (Sanner and Boutilier, 2005) uses linear programming to compute an approximation of the value function for first-order MDPs while providing upper bounds on the approximation error irrespective of the domain size. A key limitation of their approach is requiring the use of representation of action models over which it is possible to regress using situation calculus. API (Fern et al., 2006) uses approximate policy iteration with taxonomic decision lists to form policies. They use Monte Carlo simulations with random walks on a single problem to construct a policy. API offers no guarantees of completeness or hierarchical optimality.

---

Parr and Russell (1997) propose the hierarchical abstract machine (HAM) framework wherein component solutions from problem instances can be combined to solve larger problem instances efficiently. Recently, Bai and Russell (2017) extended HAMs to Reinforcement Learning (RL. settings where transition dynamics are not known by leveraging internal transitions of the HAMs. A key limitation of both these approaches is that the HAMs were hand-coded by domain expert.
Related work in Generalized Planning focuses on the problem of computing generalized plans and policies such as our GPAs (Srivastava et al., 2012). Bonet et al. (2009) automatically create finite-state controllers for solving problems using a set of examples by modeling the search as a contingent problem. Their approach is limited in applicability since it only works on deterministic problems and the features they use are hand-coded. Aguas al. (2016) utilize small example policies to synthesize hierarchical fimite state controllers that can call each other. However, their approach requires all training data to be provided upfront. D2I. (Francès et al., 2021) utilizes description logics to automatically generate features and reactive policies based on those features. Their approach comes with no guarantees for finding a solution and can only work on deterministic problems.
Deep Learning based approaches such as ASNets (Toyer et al., 2018) learn generalized policies for SSPs using a neuro-symbollc approach. They use the action schema from PPDDL to create alternating action and proposition layers. They do not learn generalized controllers and instead duplicate weights in post-processing step to represent the generalized policy. GRL (Karia and Srivastava, 2022) uses Description Logic based feature evaluations of states as input to a neural network for computing generalized policies in RL settings. A common limitation of such approaches the lack of any interpretability as well as theoretical guarantees of completeness or optimality. Furthermore, these approaches can be susceptible to catastrophic forgetting. GPAs are interpretable, provide strong theoretical guarantees, and do not lose any information when training data is presented as a stream.
Our approach differs from existing work in several aspects. Our approach constructs a domain- dependent GPA automatically without any human intervention. Using canonical abstraction, we lift problem-specific characteristics like object names and object counts in a domain-indeppenden fashion. Another key difference between other techniques is that our approach can easily incorporate solutions from new examples into the GPA without having to remember any of the carlier examples. This allows our learning to scale better and can naturally utilize leapfrog learning (Groshev et al., 2018; Karia and Srivastava, 2021, 2022) when presented with large problem the absence of training data. Finally, our approach comes with guarantees of completeness and hierarchical optimality given the training data presented. This means that if a solution exists, our approach will find (Thm. 2) and it will be guaranteed to be hierarchically optimal or better (Thm. 3).
6 Conclusions and Future Work
We show that non-deterministic Generalized Policy Automata (GPAs) constructed using solutions of small example SSPs are able significantly reduce the computational effort for finding solutions for larger related SSPs. Furthermore, for many benchmark problems, the search space pruned by GPAs does not prune away relevant transitions thus allowing our approach compute policies of comparable cost in a fraction of the effort. Our approach comes with guarantees of hierarchical optimality and also comes with the guarantee of always finding solution to the SSP.
There are several interesting research directions for future work. Description Logics are more expressive than canonical abstractions and have been demonstrated to be effective at synthesizing memoryless controllers for deterministic planning problems (Bonet et al., 2019). Our approach can easily utilize any relational abstraction and it would be interesting evaluate the efficacy of description logics. Finally, our approach is applicable when solutions have a pattern. We believe that more intelligent training data generation methods could help improve performance in domains like Delicate Can. We plan to investigate these directions of research in future work.
Acknowledgements
We would like to thank Deepak Kala Vasudevan for help with a prototype implementation of the source code. We would like to thank the Research Computing Group at Arizona State University for providing compute hours for our experiments. This work was supported in part by the NSF under grants IIS 1909370 and IIS 1942856.
10

---

References
S. Aguas, S. Celorrio, and A. Jonsson. Hierarchical finite state controllers for generalized planning, In Proc. IJCAI, 2016.
A. Bai and S. J. Russell. Efficient reinforcement learning with hierarchies of machines by leveraging internal transitions. In Proc. IJCAI, 2017.
D. Bertsekas and N. Tsitsiklis. Neuro-dynamie programming. Athena Scientific, 1996. ISBN 1886529108.
B. Bonet and H. Geffner. Labeled RTDP: improving the convergence of real-time dynamic program- ming. Proc. ICAPS, 2003.
B. Bonet, H. Palacios, and H. Geffner. Automatic derivation of memoryless policies and finite-state controllers using classical planners. In Proc. ICAPS, 2009.
B. Bonet, G. Francès, and H. Geffner. Learning features and abstract actions for computing general- ized plans. In Proc. AAAI, 2019.
C. Boutiller, R. Reiter, and B. Price. Symbolic dynamic programming for first-order mdps. In Proc. IJCAI, 2001.
A. Fern, S. W. Yoon, and R. Givan. Approximate policy iteration with policy language bias: Solving relational markov decision processes. J. Artif. Intell. Res., 25:75-118, 2006.
G. Francès, B. Bonet, and H. Geffner. Learning general planning policies from small examples without supervision. Proc. AAAI, 2021.
Garg, A. Bajpai, and Mausam. Symbolic network: Generalized neural policies for relational mdps. In Proc. ICML, 2020.
E. Groshev, M. Goldstein, A. Tamar, S. Srivastava, and P. Abbeel. Learning generalized reactive policies using deep neural networks. In Proc. ICAPS, 2018.
E. A. Hansen and S. Zilberstein. Lao: A heuristic search algorithm that finds solutions with loops. Artificial Intelligence, (29(1-))335 62, 2001.
J. Hoffmaan. FF: the fortadorward planning system. Al Mag., 22(3):57-62, 2001. 2001.
R. Karia and S. Srivastava. Learning generalized relational heuristic networks for model-agnostic planning. In Proc. AAAI, 2021.
R. Karia and S. Srivastava. Relational abstractions for generalized reinforcement learning on symbolic problems. In Proc. IJCAI, 2022.
A. Kolobov, Mausam, and D. Weld. A theory of goal-oriented mdps with dead ends. In Proc. UAI, 2012.
D. Long and M. Fox. The 3rd international planning competition: Results and analysis. J. Artif. Intell. Res., 20:1-59, 2003.
R. Parr and S. Russell. Reinforcement learning with hierarchies of machines. In Proc. NeurIPS, 1997.
L. E. Pineda and S. Zilberstein. Planning under uncertainty using reduced models: Revisiting determinization. In Proc. ICAPS, 2014.
L. E. Pineda and S. Zilberstein. Soft labeling in stochastic shortest path problems. In Proc. AAMAS, 2019.
S. Sagiv, T. W. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. ACM Trans. Program. Lang. Syst. 24(3):217 2002.
Sanner. Relational dynamic influence diagram language (RDDL): Language description. http: //users. cecs. anu, edu, haa////sanner/rra (TTPPC_201//PPP00 pdf, 2010.

---

S. Sanner and C. Boutilier. Approximate linear programming for first-order mdps. In Proc. UAI, 2005.
N. Shah, D. K. Vasudevan, K. Kumar, Kamojjhala, and Srivastava. Anytime integrated task and motion policies for stochastic environments. In Proc. ICRA, 2020.
S. Srivastava, N. Immerman, and S. Zilberstein. Learning generalized plans using abstract counting. In Proc. AAAI, 2008.
S. Srivastava, N. Immerman, and S. Zilberstein. A new representation and associated algorithms for generalized planning. Artif. Intell., 175(2):615-447, 2011.
S. Srivastava, N. Immerman, and S. Zilberstein. Applicability conditions for plans with loops: Computability results and algorithms. Artif. Intell., 191-192:1-19, 2012.
R. S. Sutton and A. G. Barto. Reinforcement learning an introduction. MIT Press, 1998. ISBN 978-0-262-19398-6.
A. Tamar, Y. Wu, G. Thomas, S. Levine, and P. Abbeel. Value iteration networks. In Proc. NeurIPS, 2016.
S. Toyer, F. W. Trevizan, S. Thiébaux, and L. Xie. Action schema networks: Generalised policies with deep learning. In Proc. AAAI, 2018.
W. Trevizan and M. M. Veloso. Short-sighted stochastic shortest path problems. In Proc. ICAPS, 2012.
J. Wu and R. Givan. Discovering relational domain features for probabilistic planning. In Proc. ICAPS, 2007.
Yoon, A. Fern, and Givan. Ff-replan: A baseline for probabilistic planning. Proc. ICAPS, 2007.
H. L. S. Younes, M. L. Littman, D. Weissman, and J. Asmuth. The first probabilistic track of the international planning competition. J. Artif. Intell. Res., 24:851-855 887, 2005.
Checklist
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] See Sec. 4.1
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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] Complete proofs are included in Appendix A.
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
URL)? YYss] A link to the public version of the source code has been added to the paper as footnote.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The main paper describes significant details of training. Detailed descriptions of the entire setup are included in Appendix B.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? Yes]] Fig. 3 shows error bars for the times. Standard deviations for costs are included in Appendix B as is noted in the caption for Fig. 3.
12

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Sec.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We appropriately cite the problem generators that we used in Sec. 4.
(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're using/curating? [N/A]
(e) Did you discuss whether the data you 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 to participants and screenshots, applicable? [N/A]
(b) Did you deseribe 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 on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xF1UszT8Fzk", "reviewer": "Reviewer_3WfX", "summary": "This work presents an approach for learning state-action abstraction in stochastic shortest path problems (SSPs). The paper introduces  Generalized Policy Automata (GPA), which are hypergraphs wherein edges representing abstract actions connect a start abstract state to some set of destination abstract states. Given a planning domain described in a symbolic description language, the paper proposes to automatically learn a GPA on small instances of a given planning domain, and then use the learned GPA to accelerate planning with an off-the-shelf SSP solver in new, possibly larger, problem instances. This is done by pruning state transitions that don't correspond to any hyperedge in the learned GPA, thus reducing the amount of computation needed. If the pruned version of the problem cannot be solved, the algorithm resorts to planning with the original problem. The authors analyze some of the theoretical properties of the method. Finally, experimental results show that the proposed approach can accelerate state-of-the-art SSP solvers in a number of planning domains represented in the PPDDL symbolic language. ", "questions": "Considering the discussion above, my main questions are:\n\n- Can you motivate the choice of evaluation domains? How does your method perform in other SSP problems described in PPDDL that are commonly used (e.g., triangle tireworld or exploding blocksworld).\n\n- How were the hyperparameters for Soft-FLARES chosen?\n\n- Other recent approaches such as ASNets (Toyer et al., 2020), which is mentioned in the introduction, would also be relevant for this problem and not included in the evaluation. Can you elaborate on why this choice was made? Similarly, a natural baseline to include whenever pruning is used in PPDDL domains is a determinization-based approach, which ofter perform surprisingly well. The reference [1] above does this by learning a promising determinization in small problem instances, similarly to how the proposed approach does it. Is there a reason why this comparison is not applicable here?", "limitations": "The authors discuss several limitations of the approach in Section 6. I think it would also be important to include some discussion regarding the limitations I mentioned under \"Significance\" above. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality** \n\nThe proposed approach builds on a well-known notion of abstraction (canonical abstraction), but the proposed approach for learning and using GPAs is new, to the best of my knowledge. On the other hand, the idea of learning a sparse representation of planning problems in small instances and apply on larger instances has been explored before (see [1] below for an example), so the main novelty of this work lies in the use of GPA for this, and the completeness guarantees. \n\n-----\n[1] Pineda, L.E. and Zilberstein, S., 2014, May. Planning under uncertainty using reduced models: Revisiting determinization. In Twenty-Fourth International Conference on Automated Planning and Scheduling.\n\n**Quality** \n\nThe proposed approach is sound, and the theoretical properties look correct to me. I have some concerns about the experiments. One is the choice of problems, which seems a bit arbitrary, considering that they are different than those used in other recent work, including the Soft-FLARES baseline, but also in ASNets by Toyer et al., 2020, and Karia Srivastava, 2021. \nI also have some reservations about the hyperparameter tuning for Soft-FLARES. In the appendix it is mentioned that $t=4$ was selected, but this choice is not motivated. A look at the Soft-FLARES paper suggests that this parameter has strong impact on performance, and that policies of similar quality can be obtained faster with lower values of $t$, which would possibly decrease the perceived benefits of the GPA-based approach. Again, stronger motivation for this choice should be offered. \n\n**Clarity** \n\nThe paper is reasonably well-written and the flow of ideas in the paper seems natural; the running example was also helpful. On the other hand, the paper is notation-heavy and somewhat dense, and it took a number of careful reads before I was confident that I understood the proposed approach. It would be helpful for readers to start with a high level overview of what the proposed technique is, without using any of the formal definitions, preferably including an image/diagram to illustrate how it works. I think the basic idea is intuitive enough that such an explanation is possible, but it's currently hidden under a dense layer of formalism. \n\n**Significance** \n\nI think the proposed approach is interesting and relevant to the probabilistic planning community. The experiments show that, when a symbolic model of the environment is available, the proposed approach can be beneficial in terms of solution quality and computation time. That being said, the applicability of this approach is limited to having a symbolic model of a problem available, which I'd argue it's often a harder problem than planning itself. Indeed, the statement in line 21 about human-engineering effort can also perfectly be applied to building a symbolic model, so I'd be wary to offer this as a strong motivation in favor of this approach. One advantage of deep-learning based approaches is precisely that it avoids human effort spend in hard-coding a good representation for the task at hand. ", "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": "9xSslQ6Uez", "reviewer": "Reviewer_qjGU", "summary": "The paper introduces a learning algorithm for a class or relational stochastic shortest path problems. The algorithms specialized in relational domains where states have meaningful factors out of named relationships -called predicates– and objects. Using previous ideas for generalized planning, the algorithm defines a new cost function for the original problem that assigns infinite cost to transitions not properly rendered in the abstraction. Such a problem is used to obtain a policy using an existing algorithm. If that policy is proper, that could be returned. Otherwise, the values of the previous algorithms can be used to solve the problem with the original cost.\nIn summary, the algorithm synthesizes a generalized policy automata (GPA) and attempts a solution to the global problem using its cost.", "questions": "1. How can this be used in domains where there are no unary predicates? For instance, suppose a graph that has proportional in the edges for not in the nodes. Each proposition can be seen as a binary predicate over the notes.\n2. In the experiments, \n\t2.1. How frequently was the policy using the GPA proper? \n\t2.2. In that case, how much is gained by running the full algorithm?\n\t2.3. In the domains, how many costs changed to $\\infty$ because of the GPA\n3. Please, elaborate on the relationship between the submission and \"Learning generalized relational heuristic networks for model-agnostic planning. In AAAI, 2021.?\n4. In problems with the same GPA, could policy could be used directly?\n", "limitations": "I think the paper comments enough about the technical limitations. This is a well-defined class of problems, and their solutions are strictly algorithmic with predictable properties.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strongest points of the paper are:\n- Use of abstraction previously used for deterministic domains.\n- Clear characterization of what the generalization means.\n- Low-data requirements\n- Clearly significant empirical results\n\nWeakness\n- The paper is built around the assumption that what matters is the accuracy in comparison with other algorithms that attach the problem directly. That leads to not-so-surprising statements like theorem 3.2, as its proof applies to any algorithm that generates a candidate of the solution, returns it if it works, and falls back to a more complex solution.\n- The notion of canonical abstraction is not explained enough to understand the scope of the technique. The example right before 3.3 offers some ideas but I would not expect users unfamiliar with the previous work on generalized planning to understand that. The domains would have presented an opportunity to describe what the GPA is doing in those cases.\n- The canonical abstraction depends strongly on the relational domain.\n\nIn my opinion, the strengths outweigh the weakness. The paper is presented as an empirical algorithm, so it makes sense to focus the evaluation on existing tasks. I would have say that understanding the expressivity of the GPA is important and beyond the scope of the paper.\n\nSome additional comments:\n- please revise this paragraph: *Highlight [page 4]:* Given a predefined set of abstraction predicates, canonical abstractions group together different objects based on the subset of abstraction predicates that they satisfy in a state. Each subset of abstraction predicates is known as a summary element\n- Why? *Highlight [page 4]:* An object o belongs to exactly one summary element in any given concrete state s and this is the maximal summary element for that object.\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": {}}, {"review_id": "3UrMKxTBRcZ", "reviewer": "Reviewer_qpA1", "summary": "In this paper, the authors propose an approach to learning Generalized Policy Automata (GPA) so as to accelerate the solution process of Stochastic Shortest Path Problems (SSP). GPAs are a non-deterministic finite-state automata that compactly encodes generalized knowledge. Furthermore, GPA imposes hierarchical constraints on the state space of the SSP and prunes the considered action space. To learn GPA, they group different objects through a canonical abstraction, and then iteratively compute GPA from a small training set containing solutions like SSP instances. Finally, they theoretically proved that the method has completeness and hierarchical optimality. Experimental results also verify that the method significantly outperforms state-of-the-art SSP solvers.", "questions": "(1) You mentioned in the Solving SSPs using GPAs section that there is no abstract translation in general policy automata (line 228). When does this phenomenon happen? In addition, if it happens, does it cause the SSP solver to have no speedup or even less efficient?\n\n(2) In the experimental section, you only used a small training set when learning GPA, and finally got very good results. If you continue to increase the number of training sets, will the experimental results gain a significant improvement?\n\n(3) As I mentioned earlier, this paper can be better comprehensive by adding some explanatory pictures for some complex contents (such as the section on \"Canonical Abstraction\") and illustrating the statement of experimental standards in priority.", "limitations": "In my opinion, the authors fail to mention some limitations of their approach in the article, which may overlook some potential problems. As the authors mention in the section \"Solving SSP with GPA\", there is no abstract translation in the general policy automata (line 228). If this happens frequently, it may affect the effectiveness of their approach. Therefore, I think this is a limitation worthy of further consideration.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality：\n(1) Compared with other methods, the method of this paper can automatically construct the GPA without any human intervention. In addition, canonical abstractions are used to extract problem-specific features such as object names and object counts.\n(2) Another key difference from other techniques in existence is that the authors' method can easily incorporate solutions from new examples into the controller without having to remember any earlier examples, leading to better scalability of GPA learning.\n\nQuality：\n(1) I find that the overall structure of the paper is good, that leverages clear method structures, exhibits comprehensive comparison to related work and builds up reasonable comparative experiments.\n(2) As I said above, the overall structure of this paper is good. However, the position where the evaluation criteria appear is not very appropriate. They should be introduced at the beginning of the experimental section, which will make the whole experimental process more reasonable.\n\nClarity:\n(1) The overall meaning of this paper is transparent, most of the methods are well explained, and the theorems are clearly proved.\n(2) Although the paper contains examples, but there is only a lengthy description in the section “Canonical Abstraction”. The work would benefit by including some clear, illustrative pictures into the main body of the paper, to better motivate and illustrate the work.\n\nSignificance：\nIn my opinion, this paper addresses an interesting research topic where they exploit knowledge from solutions of SSP instances with small object counts to learn GPAs that allow effective pruning of the search space of related SSPs with larger object counts. This ability is essential for solving stochastic shortest path problems because of its excellent generalization ability and solution efficiency.\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": {}}, {"review_id": "33IbuLG057U", "reviewer": "Reviewer_4Xab", "summary": "The paper introduces the concept of generalized policy automata (GPA) to speed up the solution of stochastic shortest path problems (SSPs), defined here within a more general AI Planning perspective. The intuition is to leverage GPAs within a \"learn-from-small-examples\" framework, i.e., they capture the (abstract) states and optimal controls of small instances (the \"training\" set), and are subsequently used in a GPA-accelerated SSP solution (specifically, by adjusting the SSP cost function accordingly). Numerical results evaluate the approach on classical planning benchmarks. ", "questions": "1. Is it possible to incorporate more examples of the type of learning that is being performed by the approach?\n\n2. Do the authors have any (theoretical) intuition on when learning from small examples in this particular context is effective? What is the fundamental structure of the smaller instances that is preserved in larger problems for this approach to be successful?\n\n3. Are there any gains if more time and instances are allotted to the training set? Is there any risk, for example, of an \"oversampling\" in this context? (I believe not because of Theorem 3.3?)\n\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Innovative structure to capture knowledge associated with optimal controls\n- Good computational results for the domains tested\n\nWeaknesses\n- In my view, limited analysis or discussion of why and when the method is effective\n- Numerical results seem quite restricted\n\nMajor Comments\n\nIn general, I greatly appreciated the GPA concept; I found it to be innovative and overall intuitive to understand, as essentially it projects the original system to a smaller (abstract) set of states and actions. The results for the four planning domains tested are also promising, especially when evaluating the results for Keva and Rover. However, I have two major concerns associated with the methodology and the numerical study.\n\n(i) [Methodology.] I believe my major question, perhaps due to some misunderstanding on my part, is fundamentally \"why would this method work?\" More precisely, there is little intuition presented on when the small instances have enough information to capture good controls, or why that should always the case. What are the underlying properties of SSPs that motivate heuristics based on small optimal portions, and when (or if) would this break? Could it be the case that this information is \"deceiving,\" in that larger problem instances have significantly different controls (e.g., Gripper)? \n\nWhile I understand that the analysis is a more computational proof of concept, I felt that any intuition, such as through more informative examples, would be quite effective in demonstrating why the approach is effective.\n\n(ii) [Numerically.] Related to point (i), the numerical study essentially focuses on a horse-race comparison between approaches in terms of time and solution cost. However, I believe that for such a new idea there are other metrics that could be as important as the total runtime for drawing insights. For example, the training setup is rather limited (only ten instances!) - is there any gains in increasing the learning period? If not, why would that be the case? Furthermore, are there any properties of states that the policy was more \"accurate\" with respect to the optimal control?\n\nOverall, I enjoyed the idea but feel that a more extensive numerical analysis is critical to this work, again to shine light into when the method could be most effective. \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