Generalised Task Planning with First-Order Function Approximation
Authors: Jun Hao Alvin Ng
Ron Petrick
Venue: CoRL2021 Poster (2021)
Keywords: task planning
relational reinforcement learning
transfer learning

Abstract: Real world robotics often operates in uncertain and dynamic environments where generalisation over different scenarios is of practical interest. In the absence of a model, value-based reinforcement learning can be used to learn a goal-directed policy. Typically, the interaction between robots and the objects in the environment exhibit a first-order structure. We introduce first-order, or relational, features to represent an approximation of the Q-function so that it can induce a generalised policy. Empirical results for a service robot domain show that our online relational reinforcement learning method is scalable to large scale problems and enables transfer learning between different problems and simulation environments with dissimilar transition dynamics.

Generalised Task Planning with First-Order Function Approximation
Jun Hao Alvin Ng Edinburgh Centre for Robotics
Ronald P. A. Petrick
Edinburgh Centre for Robotics
Heriot-Watt University & University of Edinburgh Edinburgh, Scotland, United Kingdom Alvin. Alvin.Ng@hr ac uk
Heriot-Wart Watt University Edinburgh, Scotland, United Kingdom R. R.Petrick0he ac. uk
Abstract: Real world robotics often operates in uncertain and dynamic environ- ments where generalisation over different scenarios is of practical interest. In the absence of a model, value-basee based reinforcement learning can be used to learn a goal-directed policy. Typically, the interaction between robots and the objects in the environment exhibit a first-order structure. We introduce first-order, or re- lational, features represent an approximation of the Q-function so that it induce generalised policy. Empirical results for a service robot domain show that our online relational reinforcement learning method is scalable to large scale problems and enables transfer learning between different problems and simulation environments with dissimilar transition dynamics.
Keywords: task planning, relational reinforcement learning, transfer learning
Introduction
Adaptation to different scenarios is essential for real world robotic applications. As motivating example, consider a service robot interacting with people and objects as shown in Figure The robot is required to attend to a person who requires assistance and complete the tasks given by the person. The uncertainty in who needs assistance, what these task could be, and the number of people and objects in the environment necessitates generalisation of learned knowledge from past observations model of the interaction between the robot and its environment is unknown due to its complexity, then value-based reinforcement learning (RL) methods can be used to solve the planning problems. sample complexity, is
order to complete new but similar tasks in a different environment. If the
The amount of observations required to achieve near-optimal behaviour, usually prohibitive, especially in large scale problems. This restricts the practicality of RL methods in applications where data collection is expensive. One solution is to utilise transfer learning which can reduce sample complexity by leveraging the knowledge learned in small scale problems where learning can be more efficient, in simulated environments where data collection is cheap and safe.
Interactions between robots and objects in environment often exhibit a first-order structure (i.e., ground actions of lifted action change the relations properties of all objects of the same type in similar manner). We model problems with a first-order structure using Relational Markov Decision Processes (RMDPs). Relational reinforcement learning (RRL) learns in first-order representation rather than a propositional representation and can achieve knowledge transfer without the need of mapping between problems [1]. In this work, we propose model-free RRL method where the action-value function, or Q-function, approximated by projecting the state space into a lower dimensional space using set of features. We utilise an existing online feature discovery algorithm, iFDD+ [2], to incrementally add conjunctive state predicates as features to reduce the approximation error. Since state predicates are ground over objects, problems with different objects numbers of objects have different sets of state predicates, or feature spaces, and generalisation is not possible. Instead, use lifted state predicates, or first-order features, approximate the Q-values of lifted actions rather than ground actions. By learning in a abstract state-action space which is common across all problems of the same domain (related problems), knowledge transfer is possible.
5th Conference on Robot Learning (CoRI. 2021), London, UK.

---

Plan Execution
find person(P1)
movefWP5, WP4)
talk(P1)
movetWP4, WP2)
pick upt01. WP2)
movetWF2, WP5)
put down(O1. WPS)
Description Object Type Objects
TIAGo robot /R1
person P2,
*
Item / obj 01, 02, 03,
2 wp WPL, WP2, WP3,
Location Confext: Rioe [wup/W
state TIAGo is tasked person P1 deliver Item OI location WP5
Goal Context: Cyostog:
[wbb sup
(owooloottooooo Lff P gosl.ojjett..ooo abjectt.tt(O) PF peraon..n (PI, WWFF
Figure 1: An environment in Gazebo for the Service Robot domain. A TIAGo robot fulfils task from person P1 who requested assistance, by bringing an item O1 to a location W P5.
Our contribution is threefold. First, we propose method to generate a first-order feature space au- tomatically given RMDP without the use of model, expert knowledge, or training data. Second, we implement an online, model-free RRL method which learns first-order linear function approx- imation of the Q-function given initial set of first-order features. The approximated Q-function induces a generalised policy which allows transfer learning between related problems independent of the objects, number of objects, initial states, and goal states. Third, we introduce the concept of contextual knowledge to reduce granularity in the first-order function approximation, improve plan optimality, and reduce computational cost. We evaluate method empirically randomised problems a service robot domain and different simulation environments.
2 Related Work
Exploitation the first-order structure of planning problems could reduce the sample complexity of RL methods. There are broadly two types of methods: model-based and model-free. Model-based methods such as [3, 4, 5, 6] learn relational models and employ planning techniques. Our work model-free RRL method and, therefore,
focus reviewing model-free learning methods. Mausam and Weld [7] and Džeroski et al. [8] partition the state space into finer regions, each of which has real-value representing the Q-value, using relational regression trees. Wu and Givan [9] perform supervised learning of relational features, represented as decision trees, by adding features which correlate well the Bellman error of value functions. A decision tree is sensitive to the order of node splitting and ill-suited in online RL where later observations yield new information which might necessitate the reconstruction of the trees. Ramon
[10] propose a tree restructuring operation but require statistics to be stored for every node. We use conjunctive features similar to SVRRL [11] which avoids the issue faced by decision trees. SVREL represents value function with a relational naive Bayes net and learns both the values and structure of the network. It utilises distance metric generalise over handcrafted non-binare binaryy relational features. Likewise, RIB [12], which uses instance-
learning where selected observed examples are stored, requires domain- specific distance metric compute Q-values of unseen state-action pairs. Our work does require any distance metric to be defined. In these aspects, [13] and [14] are most similar to our work. The former samples features from a set of features with the use of prior training data while we discover features online. The latter restricts features to have at most one free variable while our features can have any number of free variables. Other works such as [8, 10. 15, 12] do not consider free variables. Instead, only objects in the arguments of the goal predicate and action are considered which restricts the applicability their methods to problems with simple goals.
Some approaches require extensive domain knowledge to define specific representations that facili- tate efficient learning. Morales [16] defines abstract actions (r-actions) and abstract states (r-states) in relational representation, then learns policies in this abstract state-action space. Konidaris and Barto [17] learn a shaping reward in the action space, represented by sensory measurements which are common and hold the same semantics for all problems, to accelerate learning in another prob- lem. In later work [18], options in the agent-space are learned and transferred. Van Otterlo [19] solves an abstract MDP, which is created with the use of background knowledge, of the underlying

---

Algorithm 1: RRL with Online Feature Discovery
Input: RMDP (O,
T, R. 80, H, 7). Discovery threshold 5 Initialisc: 4 < initialise featurrs A):
O; Q = w"
2 for to 1 and St is not terminal state do
3 4t - (5))
S141, rt,
Execute action o, in simulation environment real-world
5 TD error 8 = 7: + max A (8 - ((st, as); Update w
(or) = Ej 4 Vds E P((P)): if mo(:) > & then append Φi to ta and 0 to w -3
RMDP. Sharma et al. [20] perform case-based learning and quantify state similarity by the Euclidean distance between pair of states which are represented by handcoded, real-valued state variables. The Q-values of an action are a weighted sum of the Q-values of matching cases, weighted by how similar these cases grounding which we posit are known in most, if not all, planning problems anyway.
the current state. Our work uses trivial domain knowledge for contextual
3 Preliminaries
We solve planning problems represented with RMDPs using RL methods where the Q-function is approximated with a linear function approximation.
Relational Markov Decision Process (RMDP). Factored Markov Decision Processes (MDPs) [21] represent a state s with a set of state predicates P where s = N Pr and E P. We use symbols with boldface to indicate sets. If the transition of p. depends only of state predicates ' C P, then the transition function T, which defines a probability distribu- tion over possible successor states after executing an action, can be represented compactly; for a predicate pi. T(p! 'P, a) = T(p PP.a) where p¹ is the predicate at the next time step and is action. A RMDP is a first-order representation of factored MDP given by the tuple D. R, so, H, 7). O is a set of objects, each associated with a type, P is defined over O, S is set of all possible state specifications over O and P. A is the set of all possible instantiated actions, T S A x + [0, 1]. R S x A + IR is the reward function, so is the initial state, H is the planning horizon, and 7 is the discount factor. Each predicate is applied over type-consistery tuple of objects. Different planning problems of domain can be constructed where their RMDPs have different O, initial states, and goal states. A generalised policy a policy s + which directly solves any problem of domain.
small number
Linear Function Approximation. The Q-function estimates the expected return, or Q-value Q(s, a), of executing an action in the state and following a policy thereafter. The Q-function can be represented with some form of parametric function approximation such linear combination of features: Q = Σ uadhi, where = [o,,...., Φx a set of features and ur = {wi, weg set of scalar weights. A feature o, maps (s, to scalar. The learning objective is to find the set of features and weights such that Q closely approximates the optimal Q-function. A policy induced by the optimal Q-function maximises the total discounted reward 3==00"r where ra the reward observed at time step f. A feature partitions the state space into regions such that states in a region are considered the same for the purpose of approximating the Q-values. The coverage of feature is the region of the state space for which the feature evaluates to non-zero [22]. Features with low coverage give fine granularity in approximation and thus have better accuracy than features with high coverage. This impacts the soundness of policies. Conversely, features with high coverage offer better generalisation as learning is done over a smaller number of partitions of the state space.
4 Online Learning with First-Order Linear Function Approximation
Our objective to learn generalised policy which can be used to directly solve every problem of the same domain. We present our online RRL method in Algorithm which learns a linear
3

---

function approximation of the Q-function, @ where the features + are first-order (initialised in line 1). Algorithm I uses iFDD+ [2] for online feature discovery. Q is defined over the abstract state space (represented by the first-order features) and lifted action space which are the same in all related problems. This allows transfer learning where Q is learned in a problem and transferred directly to solve another problem. Thus, the policy " induced by Q is generalised policy. At each time step & (line 2), the robot executes an action given by T (lines 3 and 4) and observes the successor state 8t-1, reward rt,, and duration of execution A, The temporal difference (TD) error is computed and the weights w are updated accordingly (line 5) with a TD learning method. We used Double Q-learning [23] with replacing eligibility traces for each feature [24]. iFDD+ adds new features, which are the conjunction of two existing features in 4 to d if their relevances T exceed the discovery threshold & (line 6). This reduces the approximation errors of Q by introducing a finer granularity in Q. In the remainder of this section, we elaborate on Algorithm 1.
4.1 Generalisation with First-Order Features
A feature o, is a set of conjunctive state predicates single state predicate which evaluates to 1 if it is satisfied in state; otherwise it evaluates to O. We denote function approximation which uses ground state predicates for features as a ground approximation. Let Q² be ground approximation for a RMDP with state-action space S' x AA', and Φ; be one of its features. Evaluating the value of &; = Pi A... A Pa E S is straightforward. However, in a second RMDP (i.e., a different planning problem) with state-action space S x A²,,, Φ; cannot be evaluated if any of its constituent state predicates p1. .... Pn is not in S², Extending this further, (1(s a) does not map to real value E {Aa² A²). Thus, Q' cannot induce policy for the second RMDP unless S S and A A². However, the two RMDPs trivially identical with possibly different initial states and goal states. We are interested in transfer learning between related problems with different state-action spaces. This motivates our of first-order approximation which is independent of S, A, and O. In a ground approximation, the features for each ground action a, Pa. initialised as the set of every state predicate and their negation: + == [ a.. ..... $ Pam. where m is the number of ground actions. We use to denote a lifted predicate or a set of lifted predicates and lowercase (uppercase) letters represent variables (objects). In a first-order approximation, we instantiate a set of first-order features for each lifted action à instead of every ground action. Otherwise, Q will not be independent of O because ground actions are defined over O. à can be ground with the variable binding o, = {<r X, / } to a ground action a(X, For every à E A. we initialise Pa (line of Algorithm 1) with the following steps:
if a E { }
1. We denote the set of ground actions for as Aa. The initial set of ground features for every ground action a E A. are lifted in accordance with the binding o, where objects in the arguments of a are substituted with their corresponding bound variables.
2. Pa is the union of the features from step 1. The remaining objects are substituted with freee variables, where +obj denotes a free variable of type obj.
This procedure will generate the same set of first-order features for every related problem. Since A is also the same, our first-order approximation has the same representation in all related problems. first-order feature must be fully grounded in order to evaluate its value in a state, contrast to bound variables which are ground with objects in the arguments of actions, free variables can be ground to any object of the same type. We discuss the grounding of free variables in Section 4.3.
Service robot domain. We introduce a novel domain, Service Robot (SR), which is illustrated in a Gazebo environment in Figure 1. In SR, a TIAGo robot has to assist some people. The robot navigates from location up1 to up2 with the action move(upı, wp2). A person can re- which is a prob-
quest assistance (represented by the state predicate need_assis aessssstanceepppeese abilistic exogenous effect (i.c., it is not due to the robot's actions). The robot does not initially know where the people are located and has to find them (find(person)). It then moves to the person and talks to them (talk(person)). If the person has requested assistance, the robot would receive some tasks (or goals) of two possible types: (1) bring an item obj to location upp wtw.oooeeetttthhoooe person)).
(goal.obecct.a((d) wp)), or (2) deliver obj to person

---

The robot could pick up an item (pick up(obj, up)). put down an item (put down(obj, wp)), give an item to a person (give(obj, person)), take an item from a person (take person))
Example 1. a ground approximation. we use the predicates P (need assistancel Pt), ... need assestaessttcceee (Pm) as features (i.e., [P] number of features), where P. are objects of type person. In a first-order approximation, these predicates are lifted to a first-ordrr feature. For the lifted action talk(person) features does not increase with the number of person objects unlike the ground approximation. This demonstrates that the first-order approximation does not scale with the number of objects and is independent of O. To evaluate oú, it must be grounded. The bound variable person is substituted according to the variable binding talk (e.g., for talk( (P3), person is substituted with P3). One of the featurrss for move wp2) is Φj = need assistance( (aacceepperrreeeeeeeeee
O; need sessisttaceeppeeseet
The number of first-order
because move does not have argument of type serson, P: is substituted with free variable xperson. 63 could be grounded by substituting sperson to any object of rype person.
4.2 Online Feature Discovery
In Section 4.1, we describe the initialisation of & where each feature is a lifted state predicate. There could be large approximation errors in Q each of these feature has high coverage. Hence, adding conjunctive state predicates, which have lower coverage, to & could reduce the approximation error. The problem of feature discovery is determine which features to add. We utilise iFDD+, model- free, online feature discovery algorithm (line 6 of Algorithm 1). A set of candidate features & consists of features which are the conjunction of any two features (its parent features) in o We denote the generation of T from o, as P( iFDD+ iteratively adds candidate features to o at each time step if their cumulative absolute approximation errors, relevances, exceed the discovery threshold& & which is a user-defined parameter. The relevance of a candidate feature is updated at each time step by accumulating the TD error only if the candidate feature active. A feature is active if it is true in the state and is not a parent feature of any active feature. The weight of a newly added feature is equals the sum of the weights of its parents. When a feature di added to & this in turn generates new candidate features with Φ; as one of its parent features.
4.3 Contextual Grounding of Free Variables
To evaluate the values of first-order features in state, they must be fully ground. This is required in Algorithm to determine the Q-values (lines 3 and 5) and the active features and candidate features (line 6). The grounding influences the step update of (line 5) and feature discovery (line 6). Bound variables are substituted with objects of the same type in the arguments of a ground action (see Example 1). Features with least one free variable are not fully ground. The set of possible substitutions for these features consists of every combination of objects for the free variables. The number of substitutions for a first-order feature Φi and for &g are:
II [w]. and |o = II | DEA
(1)
$.E
respectively, where oe; (o+.) is the set of possible substitutions for Φi (Ta), v is the set of free variables in di and |o] is the number of objects of the same type as If we consider every substi- tution (i.e., to treat a free variable like an existential quantifier) where Φ; is true in 8 if there exists a substitution in a which makes it true, then there would be many such states (e.g., in Example 1, need seriisttnee(ppessooo
will be true if any person needs assistance). Thus, first-order approx- imation has a coarse granularity which can deteriorate performance. We propose two methods to re- solve this. First, we use contextual knowledge to reduce the number of objects which a free variable can be grounded to (i.c., reduce uo] in Equation 1). Any substitution which conflicts with the substitu- tion due to contextual knowledge is removed from o+ Two substitutions conflict if they substitute a free variable with a different object. We introduce two forms of contextual knowledge which re- quire trivial domain knowledge: goal and location. Second, after contextual knowledge is applied, we select o as S o such that a metric M maximised: M = farg max n M (+%) }. where Φ% is the grounding of & with a. We define ( = - E 4g di(s, (lor)), where |0s| is the number of state predicates in Φs. This maximises the number of active, complex features. The choice of M must be dependent on the state only to preserve the Markovian property of RMDPs.
5

---

Goal Context. The goals G in planning problem are state predicates which can be trivially deter- mined from the definition of terminal states which are commonly assumed be known. The objects in E 9 are used for grounding free variables of the same type: ggaatg = {*21 /....... .tt. /X, where 9 = I Xn). We consider only active goals: a goal is active if it is known and has not been achieved g.. in SR, goal is known only after person has given a task). We assume that achieved goals are inconsequential for decision making in the present and future. The Q-values after applying goal context represent the expected values of actions for achieving the goal. This is similar to the goal-associated Q-function in [25] but is not the same as additive rewards as defined in [26] where each goal is assumed to contribute uniformly and additively to the reward. 6; = 1 if there exists a such that o goal=z results in o; being true; the value does not change even if more of such goals exist. A goal typically gives contextual grounding which is in conflict with another goal. We propose two goal selection schemes: (1) GA uses every goal with the maximal metric M, and (2) G1 uses only one goal at a time. G1 selects the next goal in an ordering of active goals, 9, when the currently selected goal is achieved. The order in 9 could affect the optimality and soundness of the policy. We determine & from the state trajectories observed in the previous episode. A partial order 9i < 9j is added if g; is achieved before 9j- 9 is randomly shuffled at the start of an episode such that every partial order is satisfied. If every goal is achieved, then the total order is known though might not be optimal. However, due to exploration in RL, the order of goals achieved might not be the same as G. Thus, a more optimal 9 could still be found.
Example 2. In SR. the goals are represented by the state predicates goal_object.Ht soatt_withobbr person) and goal.object.at(dte wp). Suppose that the goals are to deliver item 01 to location WP5 P5 and item 02 to person Pl. The former is denoted as 91 goallobb www..o/.tttttta...
PI). The goal I1 involves the objects 01 with type obj and W P5 with rype wp, and the corresponding contextual grounding is a goal=91
W P5) and the latter as 92 goal.object.withll
{*obj/ O1, xwp/ W P5). Likewise, ggoal=g: = {*obj/ O2, *person P1).
Location Context. Mobile robots move in an environment and can only interact with objects in their vicinity. Following this observation, location context substitutes the free variable with the current location of the robot: doo = {*wp/ / P} if the robot at location W P of type up. Location context can be used with the goal context if there is no conflict (i.e., they substitute free variables of different types)-this queries if the robot is at the same location as the goal of interest, If there is a conflict between goal context and location context, then either one takes precedence. We let location context take precedence in our experiments.
Example 3. In SR, the state predicate robot_at(wp) represents the location of a robot. If the robot is at W P4, then the contextual grounding is dloc (xwp/WP44) Following Example 2, we can apply agoal=ag and Dtoe together without any conflict to give the contextual grounding Ttoc.goat-99
{*WDp W P4, xobj /O2, *person/ P1]. On the other hand, goollmn and Tioe are conflicting as they ground kwp to WP5 and to WP4, respectively. They can still be applied to- gether by letting either one takes precedence (i.e., ignore the grounding the other one). If location context takes precedence, then Doo.gooulzg = { kup W P4).
4.4 Granularity of First-Order Approximations
The lifted state-action space S x A is often much smaller than the ground state-action space since a lifted predicate p(x, y) can be ground in [æ||y] ways. Since S ..P. and À are independent of O, the lifted state-action space does not increase with the scale of the planning problem which makes first-order approximations scalable to large scale problems (see Example 1). However, the downside is coarser granularity in approximation. The maximum number of features is E.eA (a)
23|P| |A| in a ground approximation, and Ene 1 PPal
P A in a first-order approximation.
Since P < |Pl and | < |A| (they are equal if there is one object for each type), a first-order approximation uses fewer features to partition the state space. Therefore, the size of the partitions (or granularity) must be larger than a ground approximation. Furthermore, free variables in first- order feature increase its coverage because there only needs to exist a substitution among several possible substitutions to make the feature true. This deteriorates performance if there are plateaus in the induced policy. Plateaus are regions of the state space where there are multiple non-optimal actions with the maximal Q-value. The coarse granularity limits the type of problems a first-order approximation can be applied in. Because first-order approximation does not consider every ground state predicates, it is suited for planning in factored MDPs with independent goals.

---

40
600
Ground
Mission Time (s)
Rewards
20
500
Loc. Context
GA Context
G1 Context
0
Loc. GA Context
300
-20
Loc GA Context (Transfer)
1000
3000
1000
3000
Loc. + G1 (Tanex((
Episode
Episode
1e4
50
Micsion Time (s)
1.2
Computation Time
Rewards
1.0
0.8
-50
1000
2000
3000
1000
2000
3000
1000
2000
3000
Episode
Episade
Episode
Figure 2: Results for Pmmall (top row) and Piarge (bottom row) using RDDLSim as a simulator. The performance of first-order approximation with different combinations of contextual grounding is compared with ground approximation (Ground). Results for transfer learning (T (Transfer) from Psmall to Plarge included well. The shading represents one standard deviation.
Pa Pamall (ROS)
Psmall (RDDLSim)
Ptarge (ROS)
Ptarge (RDDLSim)
Reward
22.7 7 + 10.6
28.6 + 0.9
45.2 + 21.0
46.0 + 24.7 648.6 + 122.3
Mission Time (s)
303.7 + 86.7
289.8 + 30.3
607.3 116.4
Table 1: Results for transfer learning from RDDLSim ROS aggregated 100 runs. This is compared with results from RDDLSim [Loc.+G1 for Psmall and Loc.+G1 (Transfer) for Piarge).
5 Experiments and Results
We now demonstrate empirically that our work (1) learns a generalised and goal-directed policy, (2) enables transfer learning from small scale problems (Psmali) large scale problems (Paarge) and between different simulation environments, and (3) reduces memory and computational costs. Results are averaged over 10 independent runs where a different, randomised problem used. The problems are randomised in the locations of items and in the tasks given. We assume that the preconditions of actions are known (i.e., an illegal action will never executed).
Experimental Setup. Psmall (Pharge). O contains three (six) items, one person (three people), and five (ten) locations; the probability of people needing assistance is 0.5 (0.5, 0.3, and 0.0 for three people). The size of the state- sate-action spaces are 206 x 65 for Psmall and 2216 x 264 for Ptarge- Each person who requires assistance gives two tasks when talked to. Executing action provides a reward of -1 and completing a task (or goal) provides a reward of 20. We tested our work in two simulation environments: RDDLSim [27] and ROS (Robot Operating System) [28] with the ROSPlan [29, 30] package. Both simulators return an observation for executing an action in a state (line 4 of Algorithm 1). We augment the observation from RDDLSim with the execution duration A which is the mean of the observed in ROS injected with normally distributed noise (standard deviation is 20% of the mean). We built Gazebo environment (see Figure 1) for a more realistic simulation relative to RDDLSim. Firstly, in RDDLSim, the robot loses localisation when moving with a probability of 0.1: in ROS. it deemed to have lost localisation when the covariance of the pose estimation from adaptive Monte-Carlo localisation exceeds a user-defined threshold. Secondly, in RDDLSim, the robot always succeeds in finding a person and ends up in the same location as the person. In ROS, the robot follows an exploration path to find a person. It might find the intended person and/or other people encounters along the way, and might not the person since it could detect people from distance. Lastly, in RDDLSim, picking up and putting down an item always succeeds while these actions might fail ROS. Each experiment in RDDLSim is conducted on single core AMD Opteron 6376 and with 8 GB of RAM.
the same location as
7

---

Ablation Study. We conducted an ablation study for contextual grounding in first-order approxima- tion and benchmarked it against ground approximation. RDDLSim was used. The results are shown in Figure 2. We measure performance by the total undiscounted reward received in each episode and by the total duration of plan execution (mission time). Executing an action incurs a reward of - which could result in learned policy which minimises the number of actions executed; this seems to suffice in reducing the mission time as it was observed that the mission time reduces asymptotically while the reward increases. G1 and Loc.+G1 (combination of location context and G1) generally outperforms GA and Loc.+GA. This is because the goals in SR are independent of each other and considering one goal at time reduces &, and the coarseness of granularity more than GA does. In Pemall, using no context or only location context has the worst performances. Due to our modelling choice to include up in arguments of actions (c.g., pick up(obj, wp) and put down(obj. wp)), fea- tures with #up are unnecessary to approximate the Q-values of some actions- we opt against using domain knowledge to prune these features. Nevertheless, location context is crucial in reducing the memory and computational cost; experiments for Piarge without location context are computa- tionally expensive and omitted. The computation time for Piarge is further reduced when goal context is also used. The computation time for Pemotl is comparable for all runs and is thus omitted. Although ground approximation has the best performance in Psmall, it has the worst performance and the highest computational cost in Plarge. The former is due to lack of generalisation and the latter is due the large set of features. For Pemail, ground approximation has 6894 + 2.7 (one standard deviation) features while the various configurations of first-order approximation have 280 to 316 features. In contrast, for Plarge. ground approximation has 94.1 x 10 8.1 x 100h features while the various configurations of first-order approximation have 382 to 417 features. Evidently, ground approximation has poorer scalability than first-order approximation.
Transfer Learning. In Figure 2, we show the results of transfer learning where Q trained in P Psmall (Q Pomait) is used, and continues to be updated in Pierge. The type of contextual grounding used in Pamalt must also be used in Piorge for transfer learning to work. We consider only Loc. +G1 or Loc.+GA as these are computationally tractable. The former outperforms the latter due to the aforementioned reason. The boost in performance due to transfer learning is evident in episode 1. The asymptotic performance without transfer learning approaches that of transfer learning as expected. However, for Loc. +GA, transfer learning performed asymptotically poorer than without transfer learning. This is because GA considers multiple goals for contextual grounding. Thus, it generalises poorly from Psmail, which has two goals, to Plarge. which has four goals.
Lastly, we evaluate the generalisation from RDDLSim simulations to ROS simulations. We used ten randomised problems for P Psmall and Plarge which are different from the ones used in RDDLSim. A greedy policy induced by Qº QPomctt using Loc.+G1 can directly solve Pemall but not Piarge. There- fore, we trained Q further in 500 episodes of Plarge using RDDLSim with a modified transition function (i.e., the robot's location does not change when finding a person) to solve Piarge- Without further training, the policy could fail to instruct the robot to move to a person after finding that per- son. The results are shown in Table 1 alongside the results from RDDLSim (i.e., Figure 2) for ease of comparison. For P Pemall, the performance in RDDLSim is better with smaller variances which is expected since the simulations do not consider real-world dynamics and are more optimistic. The results for l'arge are comparable for both simulation environments. Thus, the first-order approxi- mations are successful at generalising over both simulation environments.
Conclusion
In this paper, proposed model-free, online RRL algorithm which learns approximation of the Q-function with first-order features that is able to generalise across different problems of the same domain. Free variables in the first-order features caused ambiguity in how they should be substituted. The choice of a substitution influences the learning and is critical to performance. We resolve this problem by utilising contextual knowledge to substitute free variables. Empirical results showed that our method is scalable to large scale problems by keeping memory usage and computational cost tractable, and can generalise across problems of different scales and across different simulation environments. In future work, we plan to investigate other forms of contextual knowledge.
8

---

Acknowledgments
This work was partially funded by the EPSRC ORCA Hub (http://rccahu.org)) under grant number EP/R026173/1.
References
[1] M. E. Taylor and P. Stone, Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(7), 2009.
[2] A. Geramifard, C. Dann, and J. P. How. Off-policy learning combined with automatic feature expansion for solving large MDPs. In Proc. 1st Multidisciplinary Conference on Reinforcement Learning and Decision Making, pages 29-33, 2013.
[3] C. Guestrin, D. Koller, C. Gearhart, and N. Kanodia. Generalizing Plans to New Environments in Relational MDPs. In Proc. IJCAI, pages 1003-1010, 2003.
[4] Croonenborghs, J. Ramon, Blockeel, and M. Bruynooghe. Online Learning and Exploit- ing Relational Models in Reinforcement Learning, In Proc. IJCAI, pages 726-731, 2007.
[5] T. Lang, M. Toussaint, and K. Kersting. Exploration in relational domains for model-based reinforcement learning. JMLR, 13:3725-3768, 2012.
[6] D. Martínez, G. Alenya, T. Ribeiro, and C. Torras. Relational reinforcement learning for planning with exogenous effects. JMLR,
2017.
[7] Mausam and D. S. Weld. Solving Relational MDPs with Hirst-Order Machine Learning. In Proc. ICAPS Workshop on Planning Under Uncertainty And Incomplete Information, 2003.
[8] S. Džeroski, L. De Raedt, and K. Driessens. Relational reinforcement learning. Machine Learning, 43(1-2):7-55 2001.
[9] Wu and Givan. Feature- Distove--Dsso Approximate Value Iteration Methods. In Zucker and L. Saitta, editors, Abstraction, Reformulation and Approximation, Proceedings of the 6th International Symposium (SARA), volume 3607 Lecture Notes Computer Science, pages 321-331, 2005. doi: 10. 10071 1527862.25.
[10] Ramon, K. Driessens, and T. Croonenborghs. Transfer Learning in Reinforcement Learning Problems Through Partial Policy Recycling. In Proc. ECML, pages 699-707, 2007. doi: 10.10077978-3-500 5-073-------777-55..2
[11] S. Sanner. Online feature discovery in relational reinforcement learning. In Proc. Open Prob- lems in Statistical Relational Learning Workshop (SRL-06), 2006.
[12] K. Driessens and Ramon. Relational instance based regression for relational reinforcement learning. In Proc. ICML, pages 123-130, 2003.
[13] T. Walker. Relational Reinforcement Learning via Sampling the Space of First-Order Con- junetive Features. In Proc. ICML-04 Workshop on Relational RL, 2004.
[14] J. H. Wu and R. Givan. Relational State-Space Feature Learning and Its Applications in Plan- ning. AAAI Fall Symposium: Computational Approaches to Representation Change during Learning and Development, page 88, 2007.
[15] Croonenborghs, K. Driessens, and M. Bruynooghe. Learning relational options for inductive transfer in relational reinforcement learning. In Proc. International Conference on Inductive Logic Programming, pages 88 97, 2007.
[16] E. Morales.
Scaling Up Reinforcement Learning with a Relational Representation. In Proc. Workshop Adaptability in Multi-agent System, 2003.
[17] G. Konidaris and A. Barto. Autonomous shaping: Knowledge transfer in reinforcement learn- ing. In Proc. ICML, pages 489-496, 2006.

---

[18] G. D. Konidaris and A. G. Barto. Building portable options: Skill transfer in reinforcement learning. In Proc. IJCAI, pages 895-900, 2007.
[19] M. Van Otterlo. Reinforcement Learning for Relational MDPs. In Proc. Machine Learning Conference of Belgium and the Netherlands, 2004.
[20] M. Sharma, M. Holmes, J. Santamaría, A. Irani, C. Jr, and A. Ram. Transfer learning in real-time strategy games using hybrid ebr/rl. In Proc. IJCAI, pages 1041-1046, 2007.
[21] C. Boutilier, R. Dearden, and M. Goldszmidt. Stochastic dynamic programming with factored representations. Artificial intelligence, 121(1-2):49-107, 2000.
[22] A. Geramifard, T. Walsh, S. Tellex, G. Chowdhary. N. Roy, and P. How. A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning, volume 6. Now Foundations and Trends, 2013. doi: 1561/220000042..
[23] H. v. Hasselt, A. Guez, and D. Silver. Deep Reinforcement Learning with Double Q-Learning. In Proc. AAAI, page 2099-21000 2016.
[24] S. Singh, R. Sutton, and P. Kaelbling. Reinforcement Learning with Replacing Eligibility Traces. Machine Learning, 22, 11 1995. 0b::1010023/411111112222222
[25] V. Veeriah, J. Oh, and S. Singh. Many-Goals Reinforcement Learning, arXiv preprint 180i 09605, 2018.
[26] Sanner and C. Boutilier. Practical Linear Value-Approximation Techniques for First-order MDPs. In Proc. UAI, page 409-417, 06 2012.
[27] S. Sanner. Relational Dynamic Influence Diagram Language (RDDL): Language Description. http://users.cecs.amm www.anu..uuuuuuuuaaauuuu.uuuuuuw au/ ssanner/IPPC. 201 I/RDDL. 2010.
[28] M. Quigley, B. Gerkey, K. Conley, J. Faust, T. Foote, J. Leibs, E. Berger, R. Wheeler, and A. Y. Ng. ROS: open-source Robot Operating System. In Proc. ICRA Workshop Open Source Software, volume 3, 2009.
[29] M. Cashmore, M. Fox, D. Long, D. Magazzeni, B. Ridder, A. Carrera, N. Palomeras, N. Hur- tos, and M. Carreras, ROSPlan: Planning in the robot operating system. In Proc. ICAPS, 2015.
[30] G. Canal, M. Cashmore, S. Krivic, G. Alenyå, D. Magazzeni, and C. Torras. Probabilistic Planning for Roboties with ROSPlan. In Proc. TAROS, pages 236-250. Springer, 2019.
[31] S. Sanner. ICAPS 2011 International Probabilistic Planning Competition (IPPC), 2011. URL http://users. cecs. anu. edu. htt..aaa/saamer//P.2221..11
[32] M. Grzes, J. Hoey, and S. Sanner. International Probabilistic Planning Competition (IPPC) 2014. In Proc. ICAPS, 2014.
[33] J. Guerin, J. P. Hanna, L. Ferland, N. Mattei, and J. Goldsmith. The Academic Advising Planning Domain. In Proc. ICAPS Workshop on the International Planning Competition, 2012.
[34] I. Little and S. Thiebaux. Probabilistic planning vs. replanning. In Proc. ICAPS Workshop on the International Planning Competition: Past, Present and Future, 2007.
10

---

A Appendix
A.1 Relational Reinforcement Learning
We elaborate on our relational reinforcement learning method (an abridged version is outlined in Algorithm 1) which is shown in Algorithm The inputs the algorithm are a RMDP representing a planning problem, a set of features & and weights wy which approximate the Q-function Q candidate features & with their relevance 17. the discovery threshold & for iFDD+, learning rate a, contextual knowledge C'K (if any), and a maximisation metric M. 4, WD. 4², and n are learned in another planning problem and transferred the current problem. If transfer learning is not used, then they are the empty set Ø and need to be initialised (lines 1 to 5). The initial set of first-order features & is the concatenation of first-order features for each lifted action, Pa- Da is initialised with Algorithm 4 (line 4) which is described later. The weights are initialised to a vector of zeroes (line 5). In linear function approximation, the Q-value of state-action pair (s, a) is the dot product of w and (sss a) (line 6). The latter is returned by Algorithm which is described later.
Lines 7 to 25 show the planning cycle for H time steps. To select action using policy T generated by Q (line 8), the Q-values of every action must be evaluated. This implies that ((st, a) must be evaluated for every a E A. Thus, Algorithm is called |A]] times. The action returned by " is executed (line 10) which returns observation (s Te, A where 8141 is the successor state, re is the reward, and A, is the duration of the execution. The TD error is computed (line 12) and the weights are updated (line 13) following the observation.
The vector of real numbers, ( ae) (line 11), has value of 1 if the corresponding feature is active. The set of active features extracted (line 14). The set of active candidate features the set of conjunction of every pair of active features in & (line 15). For each active candidate feature, its relevance is computed (line 17). Candidate features with relevances greater than & are added to 4 with initial weights equal to the sum of the weights of their parent features (lines 18 to 22). New candidate features can be constructed from these newly added features in the next time step. The set of candidate features accumulated thus far, D", and its relevances, 17. are updated accordingly (lines 24 and 25). The algorithm terminates after H time steps or if the terminal state is reached (line 7). It returns w. 4b, 4", and 7) (line 26) which are used as inputs for the next planning problem (i.e., transfer learning).
Algorithm 3 evaluates the binary value of each feature o, E & and returns vector of real numbers. The set of possible substitutions a consists of every combination of objects for the free variables (line 2). We apply contextual grounding (line 3) by considering the state (c.g.. to determine the goal(s) and the location of the agent). Then, a selection method selects a subset of substitutions from & O OCK (line 4) such that the metric M is maximised. &" represents the grounding of & with o. Lastly, an element-wise logical disjunction operator is applied to every grounding of o with or M (line 5).
A.2 Initialisation of First-Order Features
We describe the initialisation of a set of first-order features, D.. for each lifted action à as shown in Algorithm 4. The inputs are the set of state fluents P and the set of ground ac- tions for à, Aa. For each ground action a E Aa. a set of ground features & is initialised (initialise seitiallse-groundd. features in line 4). In this work, we used the set of every state fluent and their negation, as well as the non-fluents. Each feature oy E 4 is lifted in accordance with the substitution of a, da (lift in line 5). A feature might be partially lifted if it contains objects that are not in the arguments of a. Pa is the union of these partially or fully lifted features for each a E Aa (line 5). Remaining objects in a are substituted with free variables to yield a set of fully lifted, or first-order, features (quantify in line 6).
A.3 Domain Model
RDDL [27] is a planning language for describing planning problems, and is used in recent In- ternational Probabilistic Planning Competitions (IPPCs) [31, 32). Semantically, RDDL describes dynamic Bayesian Networks extended with an influence diagram. A RDDL domain is described by object types, non-fluents, fluents, conditional probability functions (CPFs), and a reward func-
11

---

Algorithm 2: RRL with Online Feature Discovery (in details)
Input: RMDP ( R,, H)
Features 4.
Weights woo
Candidate features df with relevance
Discovery threshold ç.
Contextual knowledge CKK, Maximisation metric
if + Ø then
A + Get lifted actions from A
for E do
2 <- 4 initialise feauurres.. As)
wo then wo +
a) where (s, a) f- evaluate features(O,, &,CK, M, 7 for t to H and st is not terminal state do
((s. a) = =w"
(ss "0"
< (<TTa(s (st)
âe - -ifft((a))
81+1, A. Execute action in simulation environment real-world
(s), + evaluate fcatures C.K M, az)
8 = m @(5 a) (s1, as)
Update : wi+1 wi cd.; dx(a.a)
[[*(=,]] Vusj
14
Pcctive +- Get features + which are active $ antine a((Pacttee)
15
for di E 4 Waetime do
-0 &
17
Relevance ne(o.)
18
if
(o))) > & then Append o; to Q + Append
19
w/y wh the sub-vecton of w for â, where d. A 6z if di & then remove di from &
21
22
if n/ (o:) E 77 then remove (dbs) from 7)
else
24
if o; $ then add d; $
25
Add or update T/ (cb) in 77
return
4 $.
Algorithm 3: Evaluate a set of features
Function evaluate features (O, 4, CK, M, M,s,a);
Input: objects O. Features 4
Contextual knowledge CK,
Maximisation metric M,
State
Ground action a
2
a+ <
Get the set of possible substitutions from for + Apply contextual grounding CK given
+-
оM +- arg max nax M (s;a))
(ss Voeaw 4" (s,a)
return (s),a)
tion. State fluents (non-fluents) are state variables that change (do not change) with time. A RDDL problem is specified by objects, initial state, and values non-fluents. A domain can have different problems by randomising the initial state and non-fluents. We have included the RDDL domain and problems files for our Service Robot (SR) planning problem as supplementary material. We briefly describe the state fluents, non-fluents, and actions for SR. We omitted the argument robot for brevity
12

---

Algorithm 4: Initialise a set of first-order features for lifted action
Function initialise features A.)))
Input: Set of state predicates P. Set of ground actions A.
2
D = 2
for a E AA do
4, + initialise initialise_ground
a - Da U lift a %a)
return quantify (aa)
SR is single-agent problem but included them here for consistency with the RDDL domain and problem files.
A fluent non-fluent is represented by its name and typed variables in its arguments. We the type robot to represent a robot, wp to represent location, obj to represent an item, and person. to represent person. The state fluents which describe the states and goals are:
robot_at(robol, wp): robot is location wp,
localised(roooo)) robol is localised,
emptyhand(rohot); robot is not holding any items,
holding(robot, obj): robot holding item obj. object_at(obj, up): item obj is location wp,
object_with person): item obj is with person,
goal object at at(jjj wp): goal is for item obj to be at location wy,
goal.object.wichh person): goal for item obj to be with person.
person wp): person is at location wp,
need.assisstancee/prrss))) person needs assistance,
needed_ assisstanceeperron)) person needed assistance (a per son only needs assistance once per problem), and
reward (eccive the goal involving obj has been achieved (each obj can be in- volved in at most goal).
We use non-fluents to represent the location of each person and the tasks (goals) they would give. These non non-fluents are not made known to Algorithm 2. The non-fluents are:
PROB NEED ASSISTANCE(perssnn) the probability of person needing assistance, PERSON GOAL OBJECT AT(erson,, obj, wp): person will instruct the robot to place item obj at location up,
BAASONGGOAL.OER Www.O/BCTTTTTTeeeeeeee..eeeeeee. WITH(persHHoo)_... obj. persong): person, will instruct the robot to bring item obj to persony where person, and persony could refer to the same person, and PERSON_IS_AT(/
wp): person at location up (this is different from person_at(personn wp) which represents the knowedge of the robot).
The actions which the robot could execute are:
move(robot, waypointl, waypoint2): robot moves from waypointl I to waypoint2,
localise(robot): robot localises by performing simultancous localisation and mapping (SLAM).
Eind_person (rarsoonroooo,pprronn) robol explores the room to find person (this action termi- nates the end of the exploration path or when person found).
talk to person(robol) person): robol talks to person (if need assistance(persom) is true, then two goals from person will be made known and are represented by goal.object.at(db) wp) and/or goal.bbeect.with((ee per,,
13

---

1e5
Computation Time (s)
100
0.6
Rewards
50
1.5
0.4
Mission
1.0
0.2
-50
1000
3000
1000
Episode
Episode
Episode
Context
Loc. Clnoteext
(Tranft)r
Loc. Context(Transser)
Figure 3: Results for ablation study where different combinations of contextual grounding used. The results are aggregated over randomised large scale problems of Service Robot where three people need assistance (SR3). The shading represents one standard deviation. The simulator used is RDDLSim. For transfer learning (Transfer) the Q-function learned in SR1 is transferred to SR3.
pick.up(robot, obj, wp): robot picks up item obj from location wp, put_down down(roobot obj, wp): robot puts down item obj at location wp, take(robul, obj, person): robot takes item obj from person, and give(robot, obj. person): robot gives item obj to person.
A.4 Experiment Details
our experiments, we used an e-greedy policy with a linearly decaying over episodes. The
parameters used are Emntiill 1 for experiments without transfer learning and 0.2 otherwise,
0.3 (learning rate), Y = 0.9, À = 0.7 (decay rate for eligibility traces), and & = 3. H is 20 (40) for Pemall (Plarge). We utilise two simulators in experiments: RDDLSim [27] and ROS [28]. RDDLSim returns a successor state and reward based on the CPFs and reward function defined in the RDDL domain. It does not simulate robot operating in environment. For more realistic simulation, we use ROS which considers aspects such as sensors (for localisation, navigation and detecting people), motion planning (for navigation, manipulation planning (for grasping), etc. For manipulation planning, we observed that the robot fails to grasp the item frequently. Since our work does not deal with manipulation planning, we simulated the success of grasping. If the robot fails to grasp an item, we would still consider it success with a probability of 0.8 and update the successor state accordingly (e.g., holding(robol, obj) is true even if the robot fails pick up item obý in ROS). Regardless, we observed that our learned policy will repeatedly attempt to pick up an item if failed in previous attempts.
A.5 Additional Results for the Service Robot Domain
In Section present results for small scale (one person, three obj, and five up) and large scale (three sorson, six obj. and 10 wp) problems. Here, we denote the former as SR1 and the latter SR2. In SR1, person pl needs assistance with a probability of 0.5. In SR2, person pl needs assistance with probability of 0.5, person p2 needs assistance with a probability of 0.3, and person p3 does not require assistance. We now consider variant of SR2 where p3 also needs assistance with probability of 0.3. We denote this variant as SR3. For SR1, SR2, and SR3, the problems are randomised the initial locations objects and the types of goals:
PERSON_ WBW.GGGGALLBBB.O. AT(11, obj, wp): goal from pl where obj and up randomised
object instances,
DERSOON.CAAL.OBJEC...TITT obj, pb)p:)pppp::)). goal from pl where obj is randomised object instance,
CRASON_GDAL_OBJECT.. objj wp): goal from p2 where obj and up are randomised object instances,
14

---

Recon
Academic Advising
Triangle Tireworld 6
100
Rewards
Rewards
Rewards
50
-250
1000
2000
3000
1000
2000
3000
1000
2000
3000
Episode
Episode
Episode
0.8
Computation Time (5)
Computation Time
Computation Time
0.4
0.0
1000
2000
3000
1000
2000
3000
1000
2000
3000
Episade
Episode
Episode
Ground Approx.
No Context
Loc. Context
GA Context
G1 Context
Loc. + GA
Loc. G1
Loc. (Transfer)
(A
G1 (Transfer)
LoC. GA (Transfer)
LoC. G1 (Transfer)
Figure 4: Results for ablation study where different combinations of contextual grounding or no contextual grounding (NoConter are used. The performance for ground approximation (Ground Approx.) and transfer learning (Transfer) is also included. The results aggregated over 10 randomised problems of three IPPC domains: Recon, Academic Advising. and Tri angle Tireworld. The shading represents standard deviation. Omitted experiments either due to high computational costs or are inapplicable for problem.
PERSON GOAL OBJECT AT(22, obj, wp): goal from p2 where obj and up are randomised object instances,
popppbp::::::......p.p.:.. PERSON_GOAL CHAL.OBJECT.VV WWW.OBBBET...TT(3,.... obj. p1): a goal from p3 where obj is randomised object
instance, and
FERSON.GOALL.BBEET.WIIIII obj. p2): a goal from p3 where obj is randomised object instance.
The goals are randomised such that no obj is involved in more than one goal. The goals from p3 involve another person (i.c., p3 requires the robot to bring obj to the others). The results for SR3 shown in Figure 3. The findings similar to those discussed in Section 5 (see Figure 2): (I) the use of contextual grounding reduces computation time and improves performance, (2) transfer learning from a small scale problem (i.e., SR1) to a large scale problem (i.e., SR3) gives initial performance boost, and (3) ground approximation does not scale well to large scale problems.
A.6 Ablation Study for IPPC Domains
The IPPCs use several planning domains as benchmarks evaluate the performance of compet- ing planners. We conducted an ablation study on three benchmark domains: Recon (RC) [31], Academic Advising (AA) [33], and Triangle Tireworld (TT) [34]. These domains have prob- lems which are numbered from 1 to 10 (a larger number represents problem with a larger scale). We use Domain# to denote problem numbered # for Domain. We conducted experiments for both small and large scale problems for each domain. A Q-function is learned in the small scale prob- lems and transferred to the large scale problems. The results are shown in Figure 4. Since these domains do not involve durative actions, there are no results for mission time. The simulator used is RDDLSim.
In RC, an agent moves in a grid environment where there a base, hazard, and objects. The goal is to use the tools to get readings on objects; tools can be damaged if the agent is at adjacent to hazard and this reduces the probability of getting good reading. The agent can repair tool the base. We replaced the actions up. down, left, and right with move(up). This does not simplify
15

---

the problem but allows separate weights for each ground action of move. We used RC3 and RC6, where the size of the state-action spaces are 2 x 28 and 2 38, respectively.
In AA, a student has to pass some required courses. The passing rate of a course course depends on the number of prerequisites courseg the student has passed. A reward is given at each time step for taking a course (-1) or retaking a failed course (-3), and if any required course has not been passed (-5). Passing a required course gives reward of 5. We used AA3 and AA5, where the size of the state-action spaces are 2:t0 x 16 and 2 x 21, respectively.
In TT, vehicle moves in grid environment to reach goal location. There is probability of 0.5 of getting a flat tire when moving. The tire needs to be replaced with a spare tire; if there isn' one, deadend is reached. The vehicle can load spare tire if it doesn't have one and there is spare at its current location. We used TT3 and TT6, where the size of the state-action spaces are 233 x 242 and 259 814, respectively.
Ablation Study. We investigate the utility of contextual grounding by benchmarking the perfor- mance against two baselines: ground approximation and first-order approximation without contex- tual grounding. In RC6, first-order approximation outperforms ground approximation. The exper- iments for first-order approximation without contextual grounding could not be completed due to high computational costs. In AA5, first-order approximation performs poorly. This is because the goals could be dependent other goals- the success of passing course depends on the number of prerequisites passed. This cannot be represented by binary features. This issue is mitigated in a ground approximation due to the inclusion of every ground state fluent features which serves as implicit counting. In TT6, the use of location context or goal context (they cannot be used together in this domain) improved the performance of first-order approximation which performed comparably to ground approximation.
Next, we consider the computational time. In RC6, location context and the combination of location and GA context have the highest computation time. G1 considers only one goal at a time while GA considers every unachieved goal. The former has significantly faster computation time. In AA5, the highest computation time is incurred when no context is used. Since contextual grounding reduces the set of possible substitutions for &, the computation time decreases sharply. The same observation is seen in TT6.
Knowledge Transfer. We used greedy policy generated by the Q-functions learned in the small scale problems (i.e., RC3, AA3, and TT3) to solve the large scale problems (i.e., RC6, AA5, and тT6). The Q-functions are kept unchanged while solving the large scale problems (i.e., knowledge transfer where no learning takes place). This is different from the setup SR where an e-greedy policy is used and the Q-function continues to be updated (i.c., transfer learning). Figure 4 shows that in all problems, knowledge transfer performed significantly better than those which learn the Q- function online from scratch (i.e., online RL... Since the Q-function is not updated, the performance of knowledge transfer does not improve over episodes. Thus, in RC6 and AA5, they are outperformed by online RL in later episodes. The computation time for knowledge transfer is lower than online RL as expected since no learning is done in the former.
16


Reviews:
[{"review_id": "uB892Ehx60f", "reviewer": "Reviewer_rhBR", "summary": "The paper considers task planning in relational domains using relational RL based on learned Q functions.\nOne challenge in this setup is representing the space of all possible states compactly.\nTo address this, the authors propose to define the Q function as a linear combination of lifted features. This allows those features to be queried for different MDPs, even with different numbers of objects.\nIn order to evaluate the Q function, however, these features must be fully grounded. This is achieved by introducing a context, which is a reduced set of objects from which the features can be grounded.\nThe work largely builds upon iFDD+ [1] with the difference of how the features are defined.\n", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The idea of representing lifted features instead of grounded ones is compelling\n\nWeaknesses: \n- However, it is unclear to me if the idea of lifted features really works well when only considering task planning domains without geometric conditioning on the features. Can it be shown that the lifted approximation really is a valid assumption? In the case of Loc + goal context, how many free variables are left?\n- For a pure task planning scenario, the number of variables does not seem to be particularly high. I would assume that if the number of objects is larger, then the lifted approximation becomes less and less reliable.", "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": "As such, the paper is sound, but the method does not solve a particularly challenging or urgent topic in robotics, therefore, the potential impact is limited.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Fair: Major revision needed to improve organization or clarity.", "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": {"impact": "2: Unsure, difficult to assess.", "reviewer_expertise": "Fair: Some knowledge of the area"}, "extra_text": {"issues": "- The memory limit seems rather arbitrary and outdated. 4gb of memory is not much in today's standards.\n- Notation: Q(s,a) is a value, not a function. The function is called Q. Similarly for \\phi(s,a).\n- Section 4.1 could be written more clearly.\n- I don't particularly like that the formal method is explained using examples only, especially in sec 4.3"}}, {"review_id": "WXye_Ar28fy", "reviewer": "Reviewer_jVmG", "summary": "This paper focuses on how to generalize and transfer planning knowledge across a set of related tasks and domains. To this end, this paper presents a method for learning how to approximate q-values over first-order features (lifted features) for Relational Markov Decision Processes (RMDPs) and the ability to leverage contextual knowledge to reduce approximation errors in a specific task. By learning a generalized policy, it can be re-used and adapted for multiple planning problems to enable more efficient robot learning and planning. The method uses a feature discovery algorithm to identify first-order features so as to approximate first-order approximations of the Q-values for the RMDP, which enable the approximations to then be transferred to specific task instances. Feature discovery can also be used to discover more fine-grain features for a task so as to further reduce the approximation error based only on the first-order features. ", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper presents a novel approach to generalizing task planning by discovering first-order features that provide a feature space to learn lifted q-values and transfer the learned knowledge to specific task instances for robot planning.\n- The preliminary section is succinct and straight-forward and easy to understand.\n- The paper presents experiments for a service robot domain that is interesting and challenging since it involves waypoint locomotion, human interventions, and high-level object manipulation actions.\n- The results of this paper demonstrate that the proposed method of learning over first-order features provides useful generalization across domains and reduces computational cost and memory usage.\n\nWeaknesses:\n- The technical section (section 4) is very challenging to read, and understanding the mechanics of the method is difficult due to the writing. The introduction of first-order features (section 4.1) and first-order approximations is not immediately clear, and the example provided (Example 1) is also challenging to read. The reviewer suggests starting with the example and focus on clearly presenting the domain and associated RMDP, rather than presenting all of details on first-order features first then describing the example 1. Because of this, it also challenging to follow the online feature discovery process (Section 4.2) and the contextual grounding of free variables (section 4.3). (The authors have addressed this weakness in the revision)\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": "This paper presents a novel and interesting approach to learning generalized policies for transfer learning across planning domains, which is an important problem for robot learning. This paper also presents experimental results and analysis that support the claims that the new approach improves computational cost when learning in new domains. However, the clarity of the writing for the technical sections is not easy to follow and is unclear, making it challenging to fully assess the validity and impact of this paper.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Poor: Difficult to follow and understand.", "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": {"impact": "2: Unsure, difficult to assess.", "reviewer_expertise": "Poor: Limited knowledge of the area"}, "extra_text": {"issues": "The authors should aim to make their technical writing more clear and grounded in the example, to provide the reader with a better understanding of how the first-order features are discovered, used for the first-order q-value approximations, and grounded for the instantiated planning problem. "}}, {"review_id": "TTkVc6sPjY", "reviewer": "Reviewer_uKVc", "summary": "The authors propose utilizing the first-order structure of some robotic domains to learn abstracted object oriented policies. The first-order structure refers to the fact that in some domains, multiple objects can belong to the same object type, and learning generalized policies over object and action types can lead to fast transfer on a new domain with same object types but different instantiations of the objects. The authors propose the use of an incremental feature learning algorithm (from prior work) along with contextual ground schemes (proposed by the authors).\n\nThe authors demonstrate the benefit of first-order learning by training in small service robot domain and successfully demonstrating transfer to a larger domain", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- The authors successfully demonstrated the utility of using a first-order abstraction to MDPs while learning the important conjunctive features from experience as well. \n\n- The discussion in Section 4.4 about where the first order method is most applicable and useful is quite important, and I would like to see more of it in RL papers.\n\n**Comments:**\n\n- It seems that the grounding problem for the free variables could be a crucial bottleneck to successfully applying this approach broadly. The contextual grounding heuristics seem domain specific\n\n- It would be interesting to see if the imposed relational structure shows any benefit in terms of faster learning curves for a non-relational MDP (i.e. without exploiting the first-order structure at all)\n\n- As a non-expert in relational MDPs I found it hard to pinpoint the novel contribution of the paper. I believe the paper makes some important novel contributions, but the authors should provide an explicit description of their contributions vis-a-vis prior art in the introduction\n\n\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": "I believe that the model-free problem formulation is novel and technically sound. I quite like the idea of using incrementally constructed logical features to decision-making. I would recommend acceptance", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "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": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "reviewer_expertise": "Good: General knowledge of the area"}, "extra_text": {"issues": "- There seems to be a lot more prior research on RL for relational MDPs [1],[2] and I found the related work section quite sparse and superficial. I would request the authors to develop the text there to indicate what is known and what is the key research gap that your work addresses.\n\n[1] - Diuk, Carlos, Andre Cohen, and Michael L. Littman. \"An object-oriented representation for efficient reinforcement learning.\" Proceedings of the 25th international conference on Machine learning. 2008.\n\n[2] - Kim, Beomjoon, and Luke Shimanuki. \"Learning value functions with relational state representations for guiding task-and-motion planning.\" Conference on Robot Learning. PMLR, 2020."}}, {"review_id": "3ak2UmLxDn", "reviewer": "Reviewer_dCnP", "summary": "The paper is focused on generalization over different planning problems. Their core idea is to exploit the first-order structure of the robot-environment interaction to provide an approximation of the Q-function that can generalize to large-scale problems and adapt to different environments. This approach is useful in situations where a model is not available and where the number of interactions with the environment is restricted, which is the case for real world scenarios. \nTheir approach can deal with different objects, different number of objects, different initial conditions and final goals, without having to learn a different policy for every situation. \nIn practice, they use model-free relational RL with online feature discovery using another algorithm from literature, iFDD+. \nThey develop their method in the context of Relational MDP (RMDP), that allows them to learn a generalized policy $\\pi$ able to solve different planning problems (any of the ground MDPs of the RMDP). The policy is induced by a linear approximation of the Q-function, defined over features discovered online by iFDD+. ", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe authors focus on a problem that is not very popular in the community, yet quite relevant. They provide a simple way to derive a generalized policy, based on a first-order approximation making the formulation independent of state, action and object space. This is important for transfer learning, as showed in the experiments.\n\n\n### Weaknesses\nNevertheless, the authors do not present any baseline related to existing literature work on transfer learning. In addition to this, only one type of domain/task is considered in the main paper, the service robot domain illustrated in figure 1. ", "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": "The idea of the paper is to use domain knowledge to do contextual grounding and then use this to train a linear Q-function. The features are expressed as a set of conjunctive state predicates, discovered with the use of an off the-shelf algorithm (iFDD+).\nThe main reason motivating my recommendation us that there is not a single baseline comparison with related work on transfer learning, nor a comparison with any other Q-learning method from scratch. Like this the reader cannot understand how it compares with previous work or how faster it is compared to a setting without transfer, for example vs a policy learned with any SOTA model-free RL.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "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": {"impact": "2: Unsure, difficult to assess.", "reviewer_expertise": "Fair: Some knowledge of the area"}, "extra_text": {"issues": "- I find the writing style to be a bit raw and overloaded with notation (e.g. in Example 2 and 3). I appreciate that you provided said examples to make the reader understand how free variables are grounded. But maybe they could be complemented by another set of figures/a small scheme, also considering that there are only 2 figures in the paper.\n- The reader does not get an idea of how your work compares with related work, baselines are missing"}}]

Author rebuttal:

Meta-review: To enable generalization across different instances of a problem, the authors propose to learn a Q-function (and by extension a policy) defined over a more abstract state-action space that is oblivious to most of the specifics of the different entities composing the state save for their type (type such as 'person', 'object', 'location'...). The main technical contribution of the paper is how to resolve the ambiguity of grounding the Q-function to a specific problem instance if there are several entities of the same type. 

Pros:
- The reviewers find the idea compelling, the setting of relational RL original and relevant for transfer and planning.
- The consensus among the reviewers is that the experiments successfully demonstrate the ability of the proposed algorithm to generalize across different instances. 

Cons: 
- There are concerns regarding the generality of the proposed contextual grounding method, which is the main contribution of the paper. R-r (Reviewer rhBR) is unclear how a lifted planner could work without geometric information, and deplores that the grounding is only described informally through examples. R-u similarly thinks that the grounding appears heuristic and domain specific. 
- There are issues with the clarity of the presentation (R-r, R-j, R-d), especially the technical sections.
- R-d notes that comparisons to baselines are missing and that it is in general hard to appreciate the work in the context of the existing literature. R-u finds the related work section superficial and proposes some additional references to enrich it and better highlight the contributions of the paper.

The general consensus among reviewers is leaning towards rejection, but the authors are highly encouraged to engage with the reviewers and revise their manuscript accordingly. Among other things, addressing concerns regarding the generality of the method by improving the clarity of the technical section and better highlighting the contributions would greatly improve the quality and potential impact of the paper. 

I thank the authors for engaging with the reviewers and clarifying their submission. The reviewers are more positive about this work after the rebuttal period. The submission is original and improving generalization of RL through added abstraction is a commendable direction. I thus recommend the paper for presentation.
Decision: Accept (Poster)