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

This paper addresses the problem of planning in non-stationary stochastic settings with unknown domain dynamics. In particular, we consider problems where a goal-oriented 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 profiles. 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 sufficiently 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 $\epsilon$-greedy exploration can be guaranteed to successively converge to optimal policies. However, these methods are likely to be sample-inefficient 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.1), develop solution algorithms for this paradigm (Sec. 3.3) 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 first 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 flags aspects of the currently learned model that are no longer accurate, and conducts investigative exploration with auto-generated epistemically-guided 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 non-deterministic (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 significantly 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 first 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 first approach 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) significantly 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.

Relational Markov Decision Processes (RMDPs) We model tasks as RMDPs expressed in PPDDL (Younes et al. 2005). An RMDP environment or domain $\mathcal{D}^{\uparrow}=\langle\mathcal{P}^{\uparrow},\mathcal{A}^{\uparrow}\rangle$ is a tuple consisting of a set of parameterized predicates $\mathcal{P}^{\uparrow}$  and actions $\mathcal{A}^{\uparrow}$. Here, $\mathcal{P}^{\uparrow}$contains predicates of the form $p^{\uparrow}(x_{1},\dots,x_{m})$, and $\mathcal{A}^{\uparrow}$contains actions of the form $a^{\uparrow}(x_{1},\dots,x_{n})$, where $x_{i}$ are the parameters. We use $\uparrow$ 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 defined as a tuple $M=\langle\mathcal{D}^{\uparrow},O,S,A,\delta,R,s_{0},g,\gamma\rangle$ where $O$ is a set of objects. A literal $p(o_{1},\ldots,o_{n})$ represents a grounded predicate parameterized with objects $o_{i}\in O$. Formally, predicates are grounded by computing a mapping between their parameters to the objects, $\sigma(p^{\uparrow}(x_{1},\dots,x_{n}),[o_{1},\dots,o_{n}])=p(o_{1},\ldots,o_{n})$, where $p^{\uparrow}\in$ $\mathcal{P}^{\uparrow}$, $o_{i}\in O$. Similarly, $\sigma$ can also be used to lift grounded predicates and actions. We refer to $\mathcal{P}$ as the set of all possible grounded predicates derivable using $\mathcal{P}^{\uparrow}$ and $O$. For clarity, we use the notation $e^{\uparrow}$ to denote whether an entity $e$ is lifted and use $e$ otherwise.

A state $s$ is a complete valuation of all possible predicates $p\in\mathcal{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^{\uparrow}\in\mathcal{A}^{\uparrow}$. $\delta:S\times A\times S\rightarrow[0,1]$ is the transition function and is implemented by a simulator. For a given transition $\tau=(s,a,s^{\prime})$, $\delta(s,a,s^{\prime})$ specifies the probability of executing action $a\in A$ in a state $s\in S$ and reaching a state $s^{\prime}\in S$. Naturally, $\sum_{s^{\prime}\in S}\delta(s,a,s^{\prime})=1$ for any $s\in S$ and $a\in A$.

The simulator $\Delta:S\times A\rightarrow S$ is a function that returns a state $s^{\prime}$ on executing $a$ in $s$ by sampling over $\delta$. Executing an action $\Delta(s,a)$ constitutes one step on the simulator. $|\Delta|$ represents the total steps executed by the simulator and $\Delta_{\mathcal{S}}\in\mathbb{N}^{+}$ indicates the simulator step budget after which the simulator cannot be used. $s_{0}$ is the initial state and $g$ is a conjunctive first-order logic goal formula obtained using $\mathcal{P}^{\uparrow}$and $O$. A goal state $s_{g}\in S$ is a state such that $s_{g}\models g$. $R:S\times A\rightarrow\{0,-1\}$ is the reward function and $R(s,a)$ indicates the reward obtained for executing action $a$ in state $s$. For all $a\in A$, we set $R(s_{g},a)=0$ for any goal state $s_{g}$ and $R(s,a)=-1$ otherwise. $\gamma\in[0,1)$ is the discount factor. Execution begins in the initial state and terminates when a goal state is reached or when a horizon $H\in\mathbb{N}^{+}$ has been exceeded. An RMDP task is accomplished whenever execution terminates in a goal state.

A solution to an RMDP is a deterministic policy $\pi:S\rightarrow A$ that maps states to actions. The value of a state $s$ when following a policy $\pi$ is defined as the expected cumulative reward obtained when executing $a$ in $s$ and following $\pi$ thereafter, i.e., $V^{\pi}(s)=R(s,a)+\gamma\sum_{s^{\prime}\in S}\delta(s,a,s^{\prime})V^{\pi}(s^{\prime})$ The objective of an RMDP is to compute an optimal policy $\pi^{*}$ that maximizes the expected reward obtained by following it.¹¹1Without loss of generality, we focus on optimal policies that are optimal w.r.t. the initial state $s_{0}$. Model-based RMDP algorithms compute $\pi^{*}(s_{0})$ by solving the Bellman Optimality Equation iteratively starting from $s_{0}$ (Sutton and Barto 1998):

The above equation requires access to closed-form knowledge of the transition function $\delta$. When such information is unavailable, RL-based RMDP algorithms use sample estimates of Q-values instead. Given a policy $\pi$, the Q-value of a state $s$ when executing action $a$ is defined as the expected reward obtained when executing $a$ in $s$ and following $\pi$ thereafter, i.e. $Q^{\pi}(s,a)=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R(S_{t},A_{t})|S_{0}=s,A_{0}=a\right]$. The Q-Learning Equation (Watkins 1989) can be written as: as:

where $\alpha\in[0,1]$ is the learning rate. It employs an exploration strategy such as $\epsilon$-greedy wherein a random action is selected with probability $\epsilon$ and selecting the greedy action $\arg\max\limits_{a}Q(s,a)$ otherwise. Q-Learning has been shown to converge to the optimal policy (Sutton and Barto 1998).

An action $a$ is applicable in a state $s$ iff $s\models\textit{Pre}$. An effect $\textit{Eff}[i]$ when applied to a state $s$ results in a state $s\setminus\textit{Eff}[i]^{-}\cup\text{ }\textit{Eff}[i]^{+}$. Applying an action $a$ to a state $s$ results in exactly one effect $\textit{Eff}[i]$ being applied with probability $\textit{Prob}[i]$ if the action is applicable else the state remains unchanged. A PPDDL transition model $\mathcal{M}=\{\mathcal{M}_{a}|a\in A\}$ translates to a closed-form specification of the transition function $\delta$ of $M$, i.e., $\mathcal{M}\equiv\delta$. A lifted (grounded) PPDDL model $\mathcal{M}_{a^{\uparrow}}(\mathcal{M}_{a})$ can be easily obtained from $\mathcal{M}_{a}(\mathcal{M}_{a^{\uparrow}})$ using $\sigma$. As is the case with RMDP domains, several RMDP tasks from a single domain can also share the same lifted PPDDL model $\mathcal{M}^{\uparrow}=\{\mathcal{M}_{a^{\uparrow}}|a\in\mathcal{A}^{\uparrow}\}$.
Example The $\texttt{pick-up}^{\uparrow}(r_{x},l_{x},b_{x})$ action described in the running example could be modeled as a PPDDL model $\mathcal{M}_{\textit{pick-up}^{\uparrow}}$ with precondition $\textit{Pre}=$ $\texttt{box-at}^{\uparrow}(b_{x},l_{x})\text{ }\land$ $\texttt{robot-at}^{\uparrow}(r_{x},l_{x})\text{ }\land$ $\texttt{handempty}^{\uparrow}(r_{x})$ to indicate that 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 $\textit{Eff}[0]=$ $\langle\{\neg\texttt{box-at}^{\uparrow}(b_{x},l_{x}),$ $\neg\texttt{handempty}^{\uparrow}(r_{x})\}$ $\{\texttt{holding}^{\uparrow}(r_{x},b_{x})\}\rangle$ to indicate that the robot successfully picked up the box and is currently holding it. Similarly, another effect $\textit{Eff}[1]=\{\}$ with $\textit{Prob}[1]=$ $0.1$ could be used to model a slippery gripper with a 10% chance to fail to pick-up the box.

A lifted PPDDL model $\mathcal{M}_{a^{\uparrow}}$ is implicitly converted to a grounded PPDDL model $\mathcal{M}_{\sigma(a^{\uparrow},o_{1},\ldots,o_{n})}$ when checking for $\mathcal{M}$-consistency w.r.t. a transition $\tau$.

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.1. This leads to improved sample efficiency in converging to a model $\mathcal{M}\equiv\delta$, i.e., $\mathcal{M}$ translates to a closed-form specification of the transition function $\delta$. Once a $p$-distinguishing policy is identified, probabilities can be estimated using Maximum Likelihood Estimation (MLE) by executing the policy $\eta$ times where $\eta$ is a configurable hyperparameter that represents the sampling frequency.

There are two difficulties 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 efficiently use learned information to update the model when only small parts of the transition system change.

We use an active learning approach as it can cope with non-stationarity. Existing approaches using active learning are sample inefficient 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. We now begin by describing the problem that we address, followed by a detailed overview of our approach.

The above problem setting captures many real-world scenarios 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 arbitrarily 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-efficient fashion thus making it essential to learn-and-transfer knowledge. An agent that learns a fixed 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. Non-adaptive learners where adaptive learners can automatically adapt to unknown changes in the transition system, whereas the latter cannot and needs to be informed that a change has occurred and in some cases need to be informed of exactly what changed; (b) Comprehensive vs. Need-based learners where the former completely learn a new model from scratch whereas the latter only perform updates to fix the model w.r.t. transitions that are not $\mathcal{M}$-consistent.

We integrate planning and learning by continually learning and updating a PPDDL model of the environment and using it to accomplish tasks. We develop an active, need-based learner that automatically detects and adapts to changes in the transition system. Our approach actively monitors simulator execution and performs sample efficient active learning via directed exploration when transitions are inconsistent w.r.t. the current model. We now describe the components that facilitate continual learning for planning.

We implemented our approach (Alg. 1) in Python 3 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 significantly 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).

We briefly describe the domains that we used below. We refer to each domain as $\mathcal{D}^{\uparrow}(|\mathcal{P}^{\uparrow}|,|\mathcal{A}^{\uparrow}|)$ to indicate the total number of predicates and actions in the domain.

We utilized QACE (Verma, Karia, and Srivastava 2023), a SOTA stochastic model learner, as the AQML-based model-learning algorithm for developing our second baseline. We modified QACE to detect changes in the transition system thus creating a SOTA adaptive baseline called Adaptive QACE. When an inconsistency is detected, Adaptive QACE invokes QACE to relearn the model from scratch. The extended version (Karia et al. 2024) includes an ablation called Non-adaptive QACE wherein QACE is informed when a change in the transition system occurs.

We also considered ILM (Ng and Petrick 2019) since it can learn noisy deictic rules but could not use it despite employing significant effort (and contacting the authors).

We compare the baselines against our system (CLaP): an active, adaptive, need-based learner implementing Alg. 1.
Hyperparameters We used $\alpha=0.3$ for Q-Learning, $\eta=100$ for the AQML-based methods and CLaP. Additionally, we used $\beta=10$ and $\theta=0.05$ for CLaP.

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.

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 large body of work on adapting symbolic models to novelties in open-world environments for RL (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.

We developed a sample-efficient method for transferring epistemial knowledge between an interleaved learning and planning process. Our approach can easily handle non-stationary environments on-the-fly by automatically detecting any changes that are inconsistent with the learned model. We reduce sample complexity by only updating parts of the model that are inconsistent with the simulator’s execution. Our approach is 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 significantly reduces sample complexity whilst remaining performant with respect to the optimal policy.

We would like to thank Gaurav Vipat for help with an earlier version of the source code. This work was performed in collaboration with Lockheed Martin and was supported in part by the ONR under grant N00014-21-1-2045.