Epistemic Exploration for Generalizable Planning and Learning in Non-Stationary Settings

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 21:10:24

Abstract: This paper introduces a new approach for continual planning and model learning in non-stationary stochastic environments expressed using relational representations. Such capabilities are essential for the deployment of sequential decision-making systems in the uncertain, constantly evolving real world. Working in such practical settings with unknown (and non-stationary) transition systems and changing tasks, the proposed framework models gaps in the agent's current state of knowledge and uses them to conduct focused, investigative explorations. Data collected using these explorations is used for learning generalizable probabilistic models for solving the current task despite continual changes in the environment dynamics. Empirical evaluations on several benchmark domains show that this approach significantly outperforms planning and RL baselines in terms of sample complexity in non-stationary settings. Theoretical results show that the system reverts to exhibit desirable convergence properties when stationarity holds.

Main paper: 
 introduction: 
 This paper addresses the problem of planning in non-20 stationary stochastic settings with unknown domain dynamics. In particular, we consider problems where a goaloriented agent is not given a closed-form model of the probabilities of states that may result upon execution of an action. Furthermore, these probabilities can change at potentially unknown time steps as the agent is executing in the environment. Such settings are commonly encountered by planning systems in the real-world. For example, an autonomous warehouse robot would be expected to continue achieving goals through different paths when some corridors get blocked due to spills or when the layouts of storage racks change to accommodate changing inventory pro-les. Currently, such changes require renewed modeling by domain experts thus limiting the scope and deployability of automated planning methods.These settings are technically challenging due to the need to correctly model uncertainty about the agent's knowledge when a discrepancy is detected, and to conduct focused exploration that can improve the agent's knowledge for subsequent planning. Prior work on the problem investigates the role of randomized exploration for addressing non-stationarity. E.g., if the rate of novelty events inducing non-stationarity are sufciently low compared to the timesteps available for learning in each epoch of stationary dynamics, Reinforcement Learning (RL) techniques such as Q-Learning with variations of ϵ-greedy exploration can be guaranteed to successively converge to optimal policies. However, these methods are likely to be sample-inefcient as the collection of new data is not easily focused towards parts of the environment that changed.We present a new framework for continual learning and planning under non-stationarity for such settings (Sec. 3.2), develop solution algorithms for this paradigm (Sec. 3.4) and evaluate their performance across various forms of the problem, depending on whether the change in dynamics is known to the agent and whether the agent conducts comprehensive re-learning or need-based learning (Sec. 4).Our approach addresses the challenges discussed above with autonomous processes for deliberative data gathering, planning, and model learning. It starts with the inputs available to a standard RL agent (a simulator, action names, and a reward generator), but instead of learning a policy, it interacts with the environment to rst learn a relational probabilistic planning model geared towards solving the current goal, and then uses it to compute solution policies. When a discrepancy is detected, it ags aspects of the currently learned model that are no longer accurate, and conducts investigative exploration with auto-generated epistemicallyguided policies to re-learn aspects that may have changed. The problem of computing useful investigative policies is non-trivial. This is reduced to a fully-observable nondeterministic (FOND) (Cimatti, Roveri, and Traverso 1998) planning problem and solved without interacting with the simulator. The computed investigative policies are then executed and the resulting data is used to learn more accurate models. Although these executions are not focused on policy learning for the current task, they are used to learn and maintain relational Probabilistic Planning Domain Description Language (PPDDL) style models. We show that (i) this signicantly increases transferability and generalizability of learning, and (ii) the resulting paradigm vastly outperforms SOTA RL and existing model-based RL paradigms.Our main contribution is the rst known approach for using information about epistemic uncertainty of a logic-based internal probabilistic model to create exploration strategies, learn better models, and then compute plans even as transition systems change. Additionally, this is also the rst ap-proach to interleave active learning with epistemic exploration to discover a stochastic symbolic model suited for task transfer in non-stationary environments. Empirical analysis on non-stationary versions of benchmark domains show that in such settings our approach (i) signicantly reduces the sample complexity compared to SOTA baselines; (ii) can quickly adapt to changes in environment dynamics; and (iii) performs very close to an oracle that has access to all the information about changes in the environment apriori. 
background: 
 Relational Markov Decision Processes (RMDPs) We model tasks as RMDPs expressed in PPDDL (Younes et al. 2005 ). An RMDP environment or domain D ↑ = ⟨P ↑ , A ↑ ⟩ is a tuple consisting of a set of parameterized predicates P ↑ and actions A ↑ . Here, P ↑ contains predicates of the form p ↑ (x 1 , . . . , x m ), and A ↑ contains actions of the form a ↑ (x 1 , . . . , x n ), where x i are the parameters. We use ↑ to specify lifted predicates and actions with variables as arguments and omit the parameterization when it is clear from context. A grounded RMDP task (or problem) is dened as a tuple M = ⟨D ↑ , O, S, A, δ, R, s 0 , g, γ⟩ where O is a set of objects. A literal p(o 1 , . . . , o n ) represents a grounded predicate parameterized with objects o i ∈ O. Formally, predicates are grounded by computing a mapping between their parameters to the objects,σ(p ↑ (x 1 , . . . , x n ), [o 1 , . . . , o n ]) = p(o 1 , . . . , o n ), where p ↑ ∈ P ↑ , o i ∈ O.Similarly, σ can also be used to lift grounded predicates and actions. We refer to P as the set of all possible grounded predicates derivable using P ↑ and O. For clarity, we use the notation e ↑ to denote whether an entity e is lifted and use e otherwise.A state s is a complete valuation of all possible predicates p ∈ P. Following the closed-world assumption, predicates whose values are false are omitted from the state representation. The set of all possible subsets of predicates forms the state space S of the RMDP M . Similarly, the action space A of M is formed by grounding each action a ↑ ∈ A ↑ . δ : S ×A×S → [0, 1] is the transition function and is implemented by a simulator. For a given transition τ = (s, a, s ′ ), δ(s, a, s ′ ) species the probability of executing action a ∈ A in a state s ∈ S and reaching a state s ′ ∈ S. Naturally,  s ′ ∈S δ(s, a, s ′ ) = 1 for any s ∈ S and a ∈ A. Running Example Consider a robot that is deployed to assist in a warehouse. The robot is equipped with sensors and actuators (e.g., camera, wheels, grippers, etc.) that can help it perform a variety of tasks such as cleaning oors, restocking shelves, etc. Such 150 tasks could be specied by using a domain with P ↑ = {robot-at ↑ (r x , l x ), box-at ↑ (l x , b x ),holding ↑ (r x , b x ), handempty ↑ (r x )}. A ↑ would consist of actions such as move-from ↑ (r x , l x , l y ), pick-up ↑ (r x , l x , b x ), etc. with their transition function implemented by a simulator.Example RMDP task Consider an environment with one robot r 1 , two locations l 1 , l 2 , and one box b 1 . An RMDP task of moving b 1 to l 1 and parking r 1 anywhere could be modeled as M where O = {r 1 , l 1 , l 2 , b 1 }, s 0 = {handempty(r 1 ), robot-at(r 1 , l 1 ), box-at(b 1 , l 2 )}, 160 and g = box-at(b 1 , l 1 ) ∧ ∃l x robot-at(r 1 , l x ).A solution to an RMDP is a deterministic policy π : S → A that maps states to actions. The value of a state s when following a policy π is dened as the expected cumulative reward obtained when executing a in s and following π there-165 after, i.e., V π (s) = R(s, a)+ γ  s ′ ∈S δ(s, a, s ′ )V π (s ′ )The objective of an RMDP is to compute an optimal policy π * that maximizes the expected reward obtained by following it.1 Model-based RMDP algorithms compute π * (s 0 ) by solving the Bellman Optimality Equation iteratively starting 170 from s 0 (Sutton and Barto 1998) :EQUATIONThe above equation requires access to closed-form knowledge of the transition function δ. When such information is unavailable, RL-based RMDP algorithms use sample estimates of Q-values instead. Given a policy π, 175 the Q-value of a state s when executing action a is dened as the expected reward obtained when executing a in s and following π thereafter, i.e.Q π (s, a) = E π [  ∞ t=0 γ t R(S t , A t )|S 0 = s, A 0 = a].The Q-Learning Equation (Watkins 1989 ) can be written as: as:180 Q(s, a) = (1 -α)Q(s, a)+α  R(s, a)+γ max a ′ ∈A Q(s ′ , a ′ ) where α ∈ [0, 1] is the learning rate. It employs an exploration strategy such as ϵ-greedy wherein a random action is selected with probability ϵ and selecting the greedy action arg max a Q(s, a) otherwise. Q-Learning has been shown to converge to the optimal policy (Sutton and Barto 1998) .PPDDL transition models Our approach learns lifted PPDDL models that can be used for stochastic planning using Eqn. 1. We note that the simulator's implementation of the transition function could be arbitrary and does not need to be a PPDDL model. Given an RMDP M , a PPDDL 190 model M a for an action a(o 1 , . . . , o n ) ∈ A is a tuple ⟨Pre a , Prob a , Eff a ⟩. We omit the subscript when it is clear from context. Pre represents the precondition and is expressed as a conjunctive formula of predicates p ∈ P a whereP a = {σ(p ↑ (x 1 , . . . , x m ), [o i , . . . , o j ]|p ↑ ∈ P ↑ }. Prob is a list of probabilities such that  i Prob[i] = 1. Eff is a list of effects. Each effect Eff[i] ∈ Eff is a tuple ⟨Eff[i] -, Eff[i] + ⟩ both of which are sets composed of predicates p ∈ P a .An action a is applicable in a state s iff s |= Pre. An effect Eff[i] when applied to a state s results in a states \ Eff[i] -∪ Eff[i] + .Applying an action a to a state s results in exactly one effect Eff[i] being applied with probability Prob[i] if the action is applicable else the state remains unchanged. A PPDDL transition model M = {M a |a ∈ A} translates to a closed-form specication of the transition function δ of M , i.e., M ≡ δ. A lifted (grounded) PPDDL model M a ↑ (M a ) can be easily obtained from M a (M a ↑ ) using σ. As is the case with RMDP domains, several RMDP tasks from a single domain can also share the same lifted PPDDL modelM ↑ = {M a ↑ |a ∈ A ↑ }.Example The pick-up ↑ (r x , l x , b x ) action described in the running example could be modeled as a PPDDL modelM pick-up ↑ with precondition Pre = box-at ↑ (b x , l x ) ∧ robot-at ↑ (r x , l x ) ∧ handempty ↑ (r x ) to indicatethat the action is applicable only when the robot is not holding anything is at the same location as the box. The effects could be modeled as Eff[0] = ⟨{¬box-at ↑ (b x , l x ), ¬handempty ↑ (r x )} {holding ↑ (r x , b x )}⟩ to. , o n ) ∈ A of an RMDP M , a transition τ = (s, a, s ′ ) where s, s ′ ∈ S is said to be M- consistent, τ ⇌ M, iff s = s ′ when s ̸ |= Pre or ∃i such that Prob[i] > 0 and s ′ = s\Eff[i] -∪Eff[i] + whenever s |= Pre.A lifted PPDDL model M a ↑ is implicitly converted to a grounded PPDDL model M σ(a ↑ ,o1,...,on) when checking for M-consistency w.r.t. a transition τ .PPDDL Model-Learning Given a dataset T that is composed of a set of transitions τ = (s, a, s ′ ) obtained from an RMDP task, the PPDDL model-learning problem is to compute a model M s.t. τ ⇌ M for any τ ∈ T . The two major techniques of model learning are active and passive learning. Active learners interactively explore the state space to generate T for learning the model whereas passive learners require T to be provided as input. We use active learning as it has been shown to work well for deterministic, nonstationary settings (Nayyar, Verma, and Srivastava 2022). 
our approach: 
 We now begin by describing the problem that we address, followed by a detailed overview of our approach. Denition 3.1 (RMDP equivalence). Given a domain D ↑ and RMDP tasks M i and M j derived using D, we dene M i = M j iffM i ̸ = M i+1, a simulator ∆ with budget ∆ S per task, and with the simulators transition system changing at arbitrary intervals, the objective is to maximize the total tasks accomplished within |M |∆ S .The above problem setting captures many real-world sce-255 narios where environment dynamics often change in situ, i.e., while the agent is actively solving a stream of tasks and without informing the agent. E.g., events like liquid spills on the gripper affecting its friction, navigation pathways being blocked, etc. are outside the robot's control and can arbitrar-260 ily change at any given moment. Implicitly, this translates to the agent indirectly optimizing a new RMDP task with the same goal but different transition system. The overall objective is to enable solving all tasks in a sample-efcient fashion thus making it essential to learn-and-transfer knowl-265 edge. An agent that learns a xed model of the environment or one that is incapable of detecting such change can thus perform quite poorly or dangerously.We consider the following taxonomy of the methods for continual planning under non-stationarity; (a) Adaptive vs. 270 Non-adaptive learners where adaptive learners can automatically adapt to unknown changes in the transition system, whereas the other cannot; (b) Comprehensive vs. Needbased learners where the former completely learn a new model from scratch whereas the latter only perform updates 275 to x the model w.r.t. transitions that are not M-consistent.Our approach integrates planning and learning by continually learning and updating a PPDDL model of the environment and using it to accomplish tasks. We develop an active, 280 need-based learner that automatically detects and adapts to changes in the transition system. Our approach actively monitors simulator execution and performs active learning when transitions are inconsistent with the current model. We maintain sample efciency by performing directed explo-285 ration while learning the model. We now describe the components that facilitate continual learning for planning. Active Query-based Model Learning (AQML) We use an active learning approach as it can cope with non-stationarity. Existing approaches using active learning are sample inef-290 cient since they are comprehensive learners that relearn from scratch. Building upon the Active Query-based Model Learning framework (AQML) (Verma, Karia, and Srivastava 2023) , we develop a paradigm that can work in the presence of non-stationarity.Denition 3.3 (Policy Trace). Given an RMDP M and simulator ∆, a policy trace ∆ π = ⟨s 0 , a 0 , . . . , a n-1 , s n ⟩ of a policy π is a sequence of states and actions wheres i ∈ S, a i ∈ A s.t. a i = π(s i ) and s i+1 = ∆(s i , a i ).Denition 3.4 (p-distinguishing policies). Given an RMDP 300 M , a predicate p, policies π 1 , π 2 and a simulator ∆, π 1 and π 2 are p-distinguishing policies iff ∃i s.t. for policy traces ∆ π1 and ∆ π2 , p ∈ s∆π 1 i and p ̸ ∈ s ∆π 2 i .AQML is an epistemic method that seeks to prune the space of models under consideration by guiding exploration 305 towards states that can help update the model. The key observation is that for any given a ↑ ∈ A ↑ , a predicate p ↑ can appear as a positive precondition, a negative precondition, or not appear at all in M a ↑ . Similarly, p ↑ could appear in any of these modes in any of the effect lists of M a ↑ .This induces an exponentially large number of models over which a model-learner must search. We can prune this search space by selecting a predicate p ↑ and generating candidate modelsM +p (Pre|Eff) a ↑ M -p (Pre|Eff) a ↑ M ⊗p (Pre|Eff) a ↑where p ↑ appears in a positive (+), negative (-), or absent (⊗) mode in the preconditions Pre ↑ or effects Eff ↑ respectively. Ignoring probabilities, AQML uses a combination of any two pairs of these models, and reduces query synthesis to a Fully Observable Non-Deterministic (FOND) problem. The central idea behind this reduction is that the two models being used correspond to two separate copies of each predicate in the FOND problem, and a solution is found when a state is reached such that the two copies of predicates do not match. This problem can be passed to off-the-shelf solvers and the solution to these FOND problems are policies that 325 AQML uses as queries to the planning agent. Due to the nature of these models where only a single predicate is changed, solution policies of any pair of these models are guaranteed to be p-distinguishing or unsolvable. AQML then checks which model of the predicate p ↑ is consistent with the simulator and updates M a ↑ appropriately (either in preconditions or one of the effects). The process repeats for the next predicate p ′↑ with the difference being that the learned information about p ↑ can now be considered by the FOND planner in the subsequent learning process.Example Upon identifying that ¬handempty ↑ (r x ) is an effect of the pick-up ↑ (r x , l x , b x ) action, AQML can generate distinguishing queries by using a FOND planner to resolve other uncertainties such as whether ¬handempty ↑ (r x ) is a precondition of put-down ↑ (r x , l x , b x ). AQML does this by generating two abstract models, one with predicate handempty ↑ (r x ) in the precondition of put-down ↑ (r x , l x , b x ), and another where it is absent. As part of the policy generated by the FOND planner it would be ensured that ¬handempty ↑ (r x ) is true in the state before executing the put-down action (possibly by executing a pick-up action).The key insight is that unlike other methods, this learning methodology does not wait for random exploration to generate p-distinguishing policies but rather actively encourages exploration by utilizing information about parts of the model that are inaccurate. We discuss how such components are annotated in Sec. 3.2. This leads to improved sample efciency in converging to a model M ≡ δ, i.e., M translates to a closed-form specication of the transition function δ. Once a p-distinguishing policy is identied, probabilities can be estimated using Maximum Likelihood Estimation (MLE) by executing the policy η times where η is a congurable hyperparameter that represents the sampling frequency.There are two difculties with vanilla AQML. Firstly, complete models are learned in a single pass in order to guarantee correctness. Secondly, this framework assumes stationarity of the simulator and the query synthesis process is not resilient to changing environment dynamics during the model-learning loop. As a result, AQML cannot efciently use learned information to update the model when only small parts of the transition system change.We signicantly alter the AQML framework so that it can work even if the transition system changes during the modellearning process (as policy traces are being generated using the simulator) and enable it to selectively and correctly learn information that is not consistent with the learned model. We accomplish this by always monitoring executions of the simulator. If a transition τ = (s, a, s ′ ) is not consistent w.r.t. the learned model M, i.e., τ ̸ ⇌ M, then we simultaneously update the model-learning process since a new query now needs to be synthesized that can resolve the inconsistency.To do so, we identify the predicates p ↑ in the preconditions (or effects) of a that were inconsistent with the model and then we add p ↑ in the precondition (or effect) of a to be relearned. This also applies to inconsistencies identied as policy traces are being generated as a part of the modellearning process. The new FOND problem will not include p ↑ in the action a in any form in its precondition (or effect) and thus the planner will need to compute an alternate solution for the current query.Example If a predicate ¬p ↑ ∈ Pre a , p ∈ s and s ̸ = s ′ then this means that the action executed successfully on the simulator and the precondition ¬p ↑ is incorrectly represented in the currently learned model M ↑ a and must be relearned. We then add M +lpre a and M ⊗lpre a to the list of models that need to be considered again by the query-synthesis process.Another key difculty when operating in non-stationary environments is when the transitions themselves are consistent w.r.t. the preconditions and effects but are drawn from a sig-nicantly different distribution. For example, two models of an action with similar preconditions and effects but differing only in the probabilities of effects can impact the ability of an agent to solve a task. Example In our running example of a slippery gripper, as the probability of slippage increases, the optimal policy might switch to navigating to a human operator and communicating to them to pick up the object. Such changes cannot be quickly reected if only MLE estimates are used to compute probabilities since these estimates can be slow to adapt to the new distribution. We mitigate this by including goodness-of-t tests in the planning and learning loop that actively invigilate whether the distributions have undergone shift and can promptly restart the MLE estimation process.We use Pearson's chi-square test (Pearson 1992) : M ↑ 1 s ← s0; h ← 0; f ← 0 2 π ← modelBasedSolver(S, A, s0, g, M ↑ , R, γ, H) 3 while |∆| < ∆S do 4 if f > β or unreachableGoal(s0, g, M ↑ , π) then 5 explore(M ↑ , ∆) 6 if needsLearning(M) then 7 M ↑ ← learnModel(∆, M ↑ ) 8 π ← modelBasedSolver(S, A, s0, g, M ↑ , R, γ, H) 9 a ← π(s) 10 s ′ ← ∆(s, a) 11 h ← h + 1 12 if (s, a, s ′ ) ⇌ M ↑ then 13 M ←goodnessOfFitTest(s, a, s ′ , ∆, M ↑ , θ, Freq) 14 else 15 M ↑ ←addInconsistentPredicates(s, a, s ′ , M ↑ ) 16 if s |= g or h ≥ H then 17 s ← s0; f ← f + 1 iff s ̸ |= g 18 else 19 s ← s ′ 20 return M ↑ chi-square test with 0 degrees of freedom. χ 2 = n  i=1 (Freq a ↑ [i] -F × Prob a ↑ [i])) 2 F × Prob a ↑ [i]whereF = n  i=1Freq a ↑ [i] is total observed frequency for a. If the condence computed using χ 2 is less than some threshold θ (0.05 in our experiments), the goodness-of-t test is deemed to have failed and we reset the probabilities for all effects in a. To ensure that we have enough samples, we only perform this test when F > 100. We then update the probabilities using the recorded frequencies via MLE, i.e.,Prob a ↑ [i] = Freq a ↑ [i] F .Our approach of continual learning of PPDDL models has two key advantages. Firstly, since we learn models, Eqn. 1 can be used to compute policies for the task without needing to collect experience from the simulator. Secondly, lifted PPDDL models are generalizable in that they can be zero-shot transferred to tasks with differing object names, quantities, and/or goals. For example, the same pick-up ↑ (r x , l x , b x ) action described earlier can be reused by different RMDP tasks with differing numbers of robots, locations, and/or packages. This methodology allows our approach to solve tasks efciently.Alg. 1 describes our overall process for continual learning and planning. The algorithm takes as input an RMDP task M , a simulator ∆, a simulator budget ∆ S , a learned model M ↑ , and hyperparameters H, η, β, and θ representing the horizon, sampling count, failure threshold, and condence threshold respectively. Note that in the context of Alg. 1, M only species the initial state s 0 and goal g for the task. The transition system represented by the simulator can arbitrarily change at any time but the agent still perceives it as the same task. Alg. 1 attempts to compute a policy π for M using the learned model M ↑ (line 2) using an off-the-shelf RMDP solver such as LAO* (Hansen and Zilberstein 2001) .If the transition graph of π derived using M ↑ has no path to the goal or if the goal has not been reached for a certain threshold (lines 4-5) the agent performs an exploration of the state space using the simulator in order to nd a transition that is not M-consistent. Initially, when the learned model is empty, this step allows the agent to quickly discover transitions for which useful learning can be performed. We used random walks of length H to conduct this exploration step in our experiments. If an inconsistent transition is discovered as part of the exploration process, then several models to consider are added to the model learner using the approach in Sec. 3.2. This causes model learning to be invoked to resolve the inconsistency and updates the learned model M ↑ (line 7). We note that, as mentioned in Sec. 3.2, if new inconsistencies are identied during the model learning then they are resolved as well. Since the model has been updated, a new policy is computed (line 8).Once any learning steps are complete and π has been computed, we execute an action a = π(s) on the simulator (lines 9-10). If (s, a, ∆(s, a)) ⇌ M, then a goodness of t test is performed to improve probability estimates as noted in Sec. 3.3 (line 13 ). An inconsistent transition always adds new models for the inconsistencies that need to be resolved by the model learner (line 15). If the goal is reached or the horizon is exceeded, the simulator is reset to the initial state and the total failures are incremented accordingly (lines 16-17). Finally, once the budget is exhausted (line 3) the learned model is returned (line 20) that can be used for solving future tasks.Denition 3.5 (Variational Distance (VD)). Given an RMDP M , let Z = {(s, a, s ′ )|s, s ′ ∈ S, a ∈ A} be a set of transitions. Also let M and M ′ be two models. The Variational Distance (VD) between these two models is then de-ned as VD Z (M, M ′ ) = 1 |Z|  ζ∈Z |1 ζ⇌M -1 ζ⇌M ′ |.Given an RMDP M , let M be the current model and M δ be the accurate (unknown) model s.t. M δ ≡ δ. Consider ε to be an error bound on the variational distance between two models. Model learning is locally convergent iff ∀ε such that 0 < ε < VD τn (M, M δ ), ∃n ∈ N and a set τ n of n distinct transitions sampled from δ, s.t. the model M ′ learned using any T containing τ n (τ n ⊆ T ) will satisfy:VD T (M ′ , M δ ) ≤ ε < VD τn (M, M δ ).Theorem 1. Let M be an RMDP with a series of transition system changes δ 1 , . . . , δ n at timesteps t 1 , . . . , t n implemented using a simulator ∆, then during each stationary epoch between t i and t i+1 Alg. 1 performs locally convergent model learning.Proof (Sketch). Let M be the learned model at timestep i. By the correctness property of AQML (Thm. 2 in Verma, Karia, and Srivastava (2023) ) the set of transitions that M can generate must be a subset of the ones that M δi can. Let Z = {s : (s, a, s ′ )|s, s ′ ∈ S, a ∈ A)} and let z = |Z|. Let VD(M, M δ ) be x/z. ε has to be such that 0 < ε < x/z. Let M ′ be the model learned using a set of transitions τ n that are consistent with M δ but cannot be generated by M.Choose τ n such that τ n has exactly n(> zϵ) elements. Now, using the model M ′ that AQML learns, it will be able to generate τ n in addition to all the transitions that M could generate. This implies:VD (M, M δ ) -V D(M ′ , M δ )= x/z-(x-n)/z > x/z-(x-zϵ)/z = x/z-x/z+(zϵ)/z =ε, and we have the desired result with τ n as the set that is required for local convergence. By properties of AQML (Thm. 1 in Verma, Karia, and Srivastava ( 2023)) any superset of transitions valid under M δ that contains τ n will also reduce VD by at least ε. 
analysis of results: 
 As mentioned in Sec. 2, we consider a task accomplished when a goal state is reached. We used a simulator budget ∆ S = 100k for each task. The transition system is kept stationary for ∆ S steps. The simulator is then loaded with a new task M i+1 and a new transition system δ i+1 .Fig. 1 shows the obtained results from our experiments with 10 different random seeds used by the algorithms. We Evaluation Metrics We use the following evaluation metrics to answer the questions above; We answer (a) by plotting learning curves that showcase how many tasks were accomplished during the learning process; We answer (b) by comparing the policy quality wherein at every k = 100 simulator steps, we freeze the computed policy and generate 10 policy traces each starting from the initial state s 0 of the task with a maximum horizon of 40. These simulations do not count towards the simulators budget. We report the average reward obtained while doing so; We answer (c) by computing the adaptive delay (Balloch et al. 2022 ) which measures how many steps are necessary in the environment before the steady-state performance converges to that of the Oracle's.It is clear from Fig. 1 that our approach of continual learning and planning (CLaP) outperforms both non-transfer (Q-Learning) and model-based methods; A+C/U+C-Learner. (a) Sample Efciency Our results in Fig. 1(a) show that CLaP has a much better sample complexity compared to the baselines. The learning curves from FirstResponders, Elevators and Blocksworld show that our approach can accomplish signicantly more tasks than the baselines. Q-Learning does not learn and transfer any knowledge and thus needs to collect large amounts of experience to solve tasks.A+C-Learner and U+C-Learner cannot efciently correct the model when transition systems change since they need to learn all actions to converge. This drawback of comprehensive learners is highlighted in the results on the Elevators domain where even Q-Learning was able to outperform these methods. For the Elevators domain, the transition system change rendered some actions executable from states that 645 were reachable only over very long horizons. The transition system of most of these actions had not changed and were not very useful to solve the task. The comprehensive learners exhausted the simulator's budget trying to relearn these task-irrelevant actions and thus were not able to solve the 650 task. CLaP on the other hand only lazily-evaluates whether to learn a fraction of the model or not and was able to quickly x the learned model and compute a policy that could solve the task. These trends can also be seen in FirstResponders where comprehensive learners must relearn 10 actions from 655 scratch every time an inconsistency is observed. (b) Better Task Performance Fig. 1(b) shows that avg. rewards of CLaP policies are very close to the Oracle's. This suggests that our learned models are often good approximations of the transition system. CLaP's policies converge to 660 those of the Oracle's across all tasks in our evaluation. (c) Better Generalizablity Our approach has a signicantly lower adaptive delay (Fig. 1(c )), i.e., CLaP is able to utilize and transfer the learned knowledge across problems efciently compared to the baselines that take a signicant num-665 ber of samples to converge to the Oracle's performance. For example, CLaP zero-shot transferred (adaptive delay was 0) between Blocksworld tasks M 1 and M 2 requiring no learning to solve task M 2 while also matching the Oracle's per-formance. In cases where adaptation was needed (e.g., between Blocksworld tasks M 0 , M 1 , and M 2 , M 3 ) CLaP fewshot learns the required knowledge to accomplish the task with policy qualities similar to that of the Oracle. In general, CLaP's adaptive delay was the best amongst all baselines.We also conducted a directed experiment to evaluate the adaptability of our method to changing distributions. To do this, we generate two tasks from a 2-armed bandit domain.Pulling any of the levers stochastically takes the agent to the goal. Thus, the optimal policy is to repeatedly pull the lever with the highest probability of reaching the goal. In task one, the rst (second) lever would succeed with probability 0.8 (0.5). In the second, it was 0.1 (0.9) respectively with preconditions and effects unchanged. CLaP utilizes goodness of t tests and thus was able to adapt to this distribution shift and chose lever 1 (2) for task one (two). A+C-Learner can-When is it better to learn-from-scratch There were not many performance gains compared to A+C/U+C-Learner in the Tireworld domain. This is because Tireworld is a small domain with only 2 (4) actions (predicates) that need to be learned. It is intuitively clear that if the transition system sig-705 nicantly changes then relearning from scratch could save some computational effort. Devising heuristics that can evaluate whether learning from scratch would be easier than correcting the model is an interesting problem that we plan to investigate in future work. 
conclusions: 
 We developed a sample-efcient method for transferring epistemial knowledge between an interleaved learning and planning process. Our approach can easily handle nonstationary environments on-the-y by automatically detecting any changes that are inconsistent with the learned model. We reduce sample complexity by only considering the parts of the model that are inconsistent with the simulator's execution and selectively update the model. We are resilient to changes in the transition system even if it occurs during the model learning process. We show that when the transition system is stationary our approach is locally convergent. Furthermore, our learned lifted models easily transfer to new tasks. Our empirical results show that our approach signicantly reduces sample complexity whilst remaining performant w.r.t. the optimal policy. 
4 experiments: 
 We implemented our approach (Alg. 1) in Python and performed an empirical evaluation on four benchmark domains using a single core on a Xeon E5-2680 v4 CPU running at 2.4 GHz with a memory limit of 8 GiB. We found that our approach leads to signicantly better transfer performance as compared to the baselines. We describe the empirical setup that we used for conducting the experiments followed by a discussion of the obtained results (Sec. 4.1). 2 Domains We used four benchmark domains that have been used in various International Probabilistic Planning Competitions (IPPCs) 3 for our experiments. We used these benchmark domains since ground truth models for them are available and we synthesized simulators using these domains.We briey describe the domains that we used below. We refer to each domain as D ↑ (|P ↑ |, |A ↑ |) to indicate the total number of predicates and actions in the domain. Tireworld(4, 2) is a popular domain that has been used in several IPPCs. The objective of this IPPC benchmark is to drive from the initial position to the goal position (accounting for at tires that can stochastically occur). FirstResponders(13, 10) is a domain inspired from emergency services. The objective is to put out all res and treat all victims. To do so, a planning agent needs to be able to plan to reach locations under re and put them out (relling water as needed) and also treat victims either at the re site or ferry them to a hospital if the injuries are too severe. Elevators(9, 10) is a stochastic extension of the deterministic Miconic (Long and Fox 2003) domain wherein there are several new objectives such as coins to be collected and 550 elements such as shafts and gates that constrain navigation. Blocksworld(5, 4) is an environment where the goal is to arrange blocks in specic congurations. The IPPC variant is 2 Source code is included in the submission (see App. B).3 https://www.icaps-conference.org/competitions/ ExplodingBlocks wherein the table can be destroyed whilst stacking blocks. We tried to generate problems for Explod-ingBlocks but were unsuccessful and as a result used the ergodic version instead where stacking blocks has a chance to drop them on the table. Nevertheless, the non-stationarity we introduce (described below) can often introduce dead-end states (i.e., states from which the goal cannot be reached).Task Generation All tasks in the benchmark suite share a single transition system and, to the best of our knowledge, there are no ofcial problem generators that can introduce non-stationarity and generate tasks for it. Thus, we introduced non-stationarity by generating new domain les obtained by changing a randomly selected action from the domain le of the previous task that was generated. We performed between 0-3 changes in both the preconditions and effects of the selected action by adding or deleting a predicate or by modifying an existing predicate in the action's model and ensured that at least one change was made. This method of introducing non-stationarity resulted in the transition system of the nal task being signicantly different from the benchmark task with several actions changed.Task Setup We generated ve different tasks M 0 , . . . , M 4 with different initial states and goals. M 0 was the benchmark task and the others were generated using Breadth First Search. We used γ = 0.9 and horizon H = 40 for all tasks.Baselines We used Q-Learning as our non-transfer RL baseline. We also used an Oracle that has complete access to the closed-form model of the simulator and uses LAO * to compute policies. This baseline provides an upper bound on the performance achievable by any algorithm. We also use two AQML-based methods: A+C-Learner and U+C-Learner. Both approaches learn comprehensive models. The former (latter) is adaptive (non-adaptive) to transition system changes, i.e., A+C-Learner tries to compute a policy and if an inconsistency is detected, learns from scratch whereas U+C-Learner is informed that the transition system has changed in order to relearn. We used QACE (Verma, Karia, and Srivastava 2023) as the AQML-based modellearning algorithm in these baselines. These methods are compared against our learner (CLaP) which is an active, adaptive, need-based learning system implementing Alg. 1. A+C/U+C-Learner are SOTA methods for learning stochastic PPDDL models (deterministic model learners are inapplicable in our setting). We also considered ILM (Ng and Petrick 2019) since it can learn stochastic noisy deictic rules but were unable to get it to work despite employing signicant effort (and contacting the authors).Hyperparameters We used α = 0.3 for Q-Learning, η = 100 for the AQML-based methods and CLaP. Additionally, we used β = 10 and θ = 0.05 for CLaP. 
5 related work: 
 There has been plenty of work for transfer in RL (Mnih et al. 2013; Schulman et al. 2017 ) and on non-stationarity (commonly referred to as novelty in the RL literature). We focus on approaches that transfer across RMDP tasks. Tadepalli, Givan, and Driessens (2004) provides an extensive overview for relational RL approaches. Model-Based Reinforcement Learning The Dyna framework (Sutton 1990 ) forms the basis of several model-based reinforcement learning (MBRL) approaches wherein experience from the environment is used to simultaneously learn a model and use the model to generate synthetic experience that is used for learning updates. Ng and Petrick (2019) use conjunctive rst-order features to learn models and generalizable policies that transfer to related classes of 725 RMDPs. Their approach does not perform guided exploration to resolve ambiguities. REX (Lang, Toussaint, and Kersting 2012) enables MBRL to automatically learn tasks autonomously. One challenge with this approach is learning accurate models since exploration can be sparse when using REX. V-MIN (Martínez et al. 2017 ) integrates modellearning and planning with RL by requesting demonstrations from a teacher if it cannot nd a policy whose expected value is greater than a certain threshold. The requirement of an available teacher limits the transfer capabilities of this approach. Taskable RL (TRL) (Illanes et al. 2020) and RePReL (Kokel et al. 2023) show how Hierarchical Reinforcement Learning (HRL) using the options framework can be used for TRL. They use symbolic plans to guide the RL process. This approach requires models provided as input and are not learned. In contrast, our generates its own data for learning models using an active learning process. Learning Models for Non-Stationary Settings GRL (Karia and Srivastava 2022) train a neural network to learn reactive policies that can transfer to problems from the same domain but with different state spaces. Their approach is limited to only changes in the state space and cannot adapt to changes in the transition dynamics. Nayyar, Verma, and Srivastava (2022) and Musliner et al. (2021) learn models for non-stationary environments that can be integrated into the interleaved learning and planning loop. However, their approach only learns deterministic models and requires the use of optimal agents and observation traces to identify changes in transition dynamics. Bryce, Benton, and Boldt (2016) address the problem of learning the updated mental model of a user using particle ltering given prior knowledge about the user's mental model. However, they assume that the entity being modeled can tell the learning system about aws in the learned model if needed. Eiter et al. (2010) propose a framework for updating action laws depicted in the form of graphs representing the state space. They assume that changes can only happen in effects, and that knowledge about the state space and what effects might change is available beforehand. There is a recent body of work on adapting symbolic models to novelties in open-world environments for reinforcement learning (Goel et al. 2022; Balloch et al. 2023; Sreedharan and Katz 2023; Mohan et al. 2023) . These methods are limited to deterministic settings and/or can only learn new models from passively collected data. 
: 
 ing real world. Working in such practical settings with unknown (and non-stationary) transition systems and changing tasks, the proposed framework models gaps in the agent's current state of knowledge and uses them to conduct focused, investigative explorations. Data collected using these explorations is used for learning generalizable probabilistic models for solving the current task despite continual changes in the environment dynamics. Empirical evaluations on several benchmark domains show that this approach signicantly outperforms planning and RL baselines in terms of sample complexity in non-stationary settings. Theoretical results show that the system reverts to exhibit desirable convergence properties when stationarity holds. 
 
 Appendix: Without loss of generality, we focus on optimal policies that are optimal w.r.t. the initial state s0. 


Decision: The authors propose a novel continual planning and learning approach specifically for a relational MDP (RMDP). The approach uses epistemic uncertainty of a probabilistic model that is logic-based to explore and learn, as well as incorporate active learning with epistemic exploration, both of which help it in non-stationary environments. It provides a theoretical/definitional description with a bit of theory, followed by experiments on canonical domains such as Tireworld, Blocksworld, and so on.

The reviewers praised the paper on a number of points, such as the ability to transfer epistemic knowledge between the learning and planning processes; incorporation of relational representations; some theoretical results; and empirical evaluation on benchmarks and against good baselines. There are some issues that were raised, ranging from a bit of clarity/novelty issues that should be discussed (e.g. from AQML) to a rationale for the domains (versus others mentioned by reviewers, which were explained in the rebuttal).

The paper could use a bit of refinement in the points raised by the reviewers, but overall the paper does a great job of explaining the approach and demonstrating its use, with some light theoretical grounding as well. We hope that the reviewers' feedback will prove useful towards the goal of applying further refinements to this paper.

Reviews: review: strength_weakness: strength_weakness: (1) The paper introduces a method for learning models in changing environments, but it fails to explicitly specify the distinctions between its approach and existing works on transfer learning in Non-Stationary MDPs, such as [1]. Moreover, the paper neglects to discuss how its approach relates to meta-reinforcement learning in non-stationary environments, as exemplified in [2].

(2) The paper lacks a comprehensive comparison with existing baselines, such as those presented in [3,4]. While the paper claims superiority over state-of-the-art methods, the absence of a detailed and rigorous comparison raises concerns about the robustness and generalizability of the proposed approach. 

(3) The empirical evaluations focus on benchmark domains, and there is limited exploration of real-world applications. Extending the analysis to diverse and complex real-world scenarios would enhance the generalizability of the proposed approach. Moreover, The paper does not explicitly discuss scalability concerns. As the proposed framework involves focused explorations, scalability to larger and more complex environments might be a potential challenge worth addressing.

[1] Mahmud, MM Hassan, and Subramanian Ramamoorthy. "Learning in non-stationary MDPs as transfer learning." AAMAS. 2013.
[2] Bing, Zhenshan, et al. "Meta-reinforcement learning in non-stationary and dynamic environments." IEEE Transactions on Pattern Analysis and Machine Intelligence 45.3 (2022): 3476-3491.
[3] Feng, Songtao, et al. "Non-stationary Reinforcement Learning under General Function Approximation." arXiv preprint arXiv:2306.00861 (2023).
[4] Padakandla, Sindhu, Prabuchandran KJ, and Shalabh Bhatnagar. "Reinforcement learning algorithm for non-stationary environments." Applied Intelligence 50 (2020): 3590-3606.
questions: questions: See above that felt confusing or unclear and please feel free to clarify.
strength_weakness: strength_weakness: The way Section 3 is structured made it hard to understand what are the novel aspects of this work wrt to AQML since most of the section seems to describe existing work. The learning for both AQML and CLaP operates in the same way: generate FOND policies that allow them to eliminate uncertainty in the learned model. The main difference I see is in the source of uncertainty which I believe is correlated to the assumptions regarding stationarity of the transition system. In AQML, uncertainty emerges from the internal representation of the space of solutions that AQML maintains. Here, uncertainty emerges when an inconsistency is detected and we need to find what is the new correct representation of some predicate. From the algorithm perspective, this feels like a trivial extension that leverages the query-based learning of AQML inside a different outer loop (which in my opinion is actually simpler than the original AQML). That being said, the fact that methodologically this extension is quite incremental does not mean that it is not worthy or practical.

I don’t think the capability of CLaP to adapt to changes in the environment that can arbitrarily occur at any moment is well demonstrated. For some reason, in the experiments the changes in the environment are synchronized with the changes in task and, therefore, new calls to CLaP. It is unclear to me how CLaP would cope with an environment change during its execution.

Minor:
line 392: incorrect notation
line 682: 0.5 -> 0.2?
questions: questions: Q1. What is the point of the failure threshold? How is this different from having a bigger simulator budget?

Q2. In line 458, what do you mean by an empty learned model?

Q3. Are the two comprehensive baselines defined in previous AQML works or did you define them here for the first time? Can the adaptive one be seen as an ablated version of CLaP?

Q4. In the experiments, I found it weird that you synchronize the change of transition system with the change of planning task. Why did you choose to do so? Can CLaP cope with changes in the transition system during its execution or does it need to be restarted?

POST-REBUTTAL
Thank you for your feedback. Your answers clarified some of my doubts about your work.
strength_weakness: strength_weakness: There are few unclear aspects which I would like to be better explained by the authors, to totally convince me. They are reported below as questions.
questions: questions: 1. In the algorithm, at line 2, you use a model based solver, which I assume is based on the simulator. However, in the text you mention that, at the beginning, only the initial and goal states are assumed to be known. How do you generate traces in this way? You just randomly perform actions, then observe the simulator’s output, but then you know something about the transition model also at the beginning, right? Please clarify the initial knowledge
2. In the experiments, the definition of tasks is unclear to me. A task seems to be M_i, but then they should be 5, so what is the number of tasks on the y axis of figure 1a? 
3. How did you choose the simulation budget (100k)? It affects also the rate of model change, hence the convergence. What is the minimum number for your performance to remain the best? It would be interesting to challenge your methodology with faster dynamics (hence lower budget)
4. Can inductive logic programming be applied in your framework, e.g., to increase expressiveness, support non-monotonicity or include some temporal fragments, e.g., event calculus theories? E.g., though in a different setting for offline learning, inductive learning of answer set programs was used by Mazzi et al. (2023, https://dl.acm.org/doi/abs/10.5555/3545946.3598660) to derive action preconditions, and extensions as FastLAS (https://github.com/spike-imperial/FastLAS) exist for faster (online) learning and event calculus learning. I am curious whether you considered inductive logic programming, or you envision its usage in future extensions. In general, please discuss the expressiveness of the logical formalism as a possible limitation.
5. I think you should at least cite the work about relational learning by Sridharan et al. (http://www.cogsys.org/journal/volume7/article-7-7.pdf and https://ojs.aaai.org/index.php/ICAPS/article/view/13852), where an action theory or affordance theory for robotics is progressively refined from traces and/or human feedback.