§ INTRODUCTION

The NovGrid environments, where the agent (red triangle) must get to the goal (green box). The novelties are not directly observable; the agent must experience the novelty to be aware of it.

pre-novelty only a yellow key opens a door; post-novelty only the blue key opens the door.

pre-novelty the lava gives a -1 reward and is a terminal state; post-novelty the lava is safe to walk on.

Most realistic environments are “open-worlds,” where new and unexpected situations will likely be encountered.

Consider the following examples:
a door is re-keyed so previous keys fail to open it and a different key is required, changing the solution;
a new technology enables a vehicle to pass over previously impassible terrain, shortening the distance to a destination;
a volcano eruption suddenly changes the local climate causing native crops to fail, making it harder to feed communities.

We refer to these changes as “novelties”, previously unseen changes to the fundamental mechanics or properties of an environment <cit.>.
Novelties can dramatically alter the solution distribution for sequential decision-making tasks.

An agent—human or artificial— that fails to adapt to novelties can result in a precipitous drop in task performance if the same policies continue to be pursued.

The  architecture.
The purple module

and black arcs represent the conventional RL execution loop with loss back-propagating backward through black arcs in the purple module.
The blue module

contains rule model learning and novelty detection.
The red arcs represent information flow in a post-novelty environment, using learned rules to simulate the new environment.
Post-novelty, loss is back-propagated backward along the red arcs and black arcs within the policy model.

Fast and sample-efficient adaptation to novelties can be essential, for example when human safety is involved.
As such, humans have evolved to be good at adapting to novelties <cit.>.
By contrast, deep reinforcement learning (RL) agents, which have demonstrated super-human performance on game tasks like Go <cit.>, Atari <cit.>, and StarCraft <cit.> are particularly susceptible to failure in the face of novelty.

Novelties constitute a distributional shift in the environment dynamics.
As such novelties can be expressed as online task transfer <cit.>—during online execution the agent suddenly finds itself in an environment with new transition dynamics.
The traditional approach to transfer is to retrain from scratch in the post-novelty environment.
One can also allow the agent to continue learning post-novelty starting with the model parameters.
This, however, can be very sample-inefficient, requiring hundreds of thousands of interactions with the environment during deployment time to converge to the new optimum policy.

We propose , an efficient world model reinforcement learning system with a neural policy comprised of two novelty-focused improvements to the standard deep RL execution loop.
(1) We propose a simple, fast-updating, symbolic world model for learning a model of the transition function—how features of the environment change and can be changed over time.
Unlike neural world models which may require multiple examples of a phenomenon, our symbolic world model can be updated with a single post-novelty observation, allowing faster novelty adaptation than neural world models.

(2) We propose an imagination-based adaptation method that uses the symbolic world model to improve the efficiency of deployment-time adaptation of the policy.
After detecting novelty, the agent updates its world model and uses the updated world model to simulate environment transitions in the post-novelty world, reducing the number of real environment interactions required to update the policy.

We evaluate the sample efficiency of  in the NovGrid environment <cit.> with multiple novelty types.

We show that post-novelty adaptation with  requires fewer policy updates and environment interactions

than model-free and neural world model reinforcement learning techniques.

To summarize, our contributions are as follows:

* We present , a neuro-symbolic world model for novelty detection and adaptation.

* We define a new symbolic representation with an efficient learning algorithm and a way to use this representation to help world models adapt to novelty.

* We show that  adapts to novelties more efficiently than state-of-the-art reinforcement learners.

§ BACKGROUND

Novelties are defined as sudden, previously unseen changes to dataset, datastream, or environment fundamentals <cit.>.
Novelty handling can be broken down into three challenges: novelty detection, novelty characterization, and novelty adaptation.

Prior work on novelty-aware agents for sequential decision making problems include
adaptive mixed continuous-discrete planning and knowledge graphs used in combination with actor-critic reinforcement learning techniques to improve both detection and adaptation <cit.>.

Adaptation to “hidden” domain shifts <cit.> is also relevant, though not originally targeted toward novelty.

Explicit detection and characterization are not strictly necessary for novelty adaptation.
In online continuous or lifelong learning <cit.> and online learning <cit.>,

a learner makes the assumption that the world is too complex or unpredictable to learn offline, functionally treating the world as perpetually novel.
Instead of making a training-deployment distinction, these learners continuously update.
With these techniques, there may be little-to-no guarantee of convergence pre- or post-novelty.

When starting with some pre-novelty knowledge, even if the naive online learning approach results in post-novelty convergence, this could induce catastrophic inference <cit.>, causing the agent to transfer little, if any, of its previous model.
This forgetting phenomenon can make learning less efficient.

Transfer learning <cit.> seeks to overcome this limitation by transferring the model to an environment that differs in a small but non-trivial way.
While this approach has similarities to novelty adaptation, transfer learning techniques often assume that an agent can return to an offline training phase when encountering the new dataset or environment, whereas novelty adaptation must occur during deployment.

World Models in Reinforcement Learning.

Reinforcement learning can be broadly categorized as model-based and model-free <cit.>.
In model-based reinforcement learning, an agent learns a model of the transition function and uses it to formulate a policy with an iterative technique such as Monte Carlo tree search <cit.> or a dynamic programming approach such as value iteration.

In model-free reinforcement learning, a model of the policy is learned directly, without the need for a transition function, and then sampled to determine the actions of an agent.
For novelty adaptation, model-based methods may be more sample-efficient, however, they tend to be more sensitive to modeling error than model-free methods <cit.>.

World models learn both the transition function and the policy, using them together to drive agent performance <cit.>.

DreamerV2 <cit.> represents the state of the art in world model-based reinforcement learning.
In the Dreamer approach,

only the world model learns directly from interacting with the environment, while the policy is trained exclusively from interactions “imagined” by the world model <cit.>.
This builds on prior world model research that used imagination to help train standard RL models <cit.> and multi-agent models <cit.>.
DreamerV2 is more sample-efficient than most model-free reinforcement learning agents but still requires a very large model; it was not explicitly designed for novelty-handling.

No prior work uses world model based RL for novelty adaptation.

Reinforcement learning typically models environments as standard Markov decision processes (MDP): $M=\langle S, A, R, P, \gamma\rangle$,
where $S$ is the set of environment states, $A$ is the set of actions, $R: S \times A \rightarrow \mathbb{R}$ is the function mapping from states and actions to a scalar reward, $P: S \times A \rightarrow \mathbb{S}$ is the transition function between states, and $\gamma$ is the discount factor.
The injection of novelty, after an arbitrary and a priori unknown number of episodes or games $t$ constitutes a transformation from the original environment or MDP $M$ to a new environment or MDP $M'$.

All aspects of the problem except an agent's decision-making model are considered properties of the environment.
This includes agent morphology, action preconditions, and effects.

We constrain the problem in a few ways. We assume that each agent's observation space and action space remain consistent throughout.

We also assume that the agent's mission $T$, and therefore the extrinsic reward function, is consistent throughout.

As is typical in reinforcement learning we model our environment as standard Markov decision processes (MDP): $M=\langle S, A, R, P, \gamma\rangle$, where
$S$ is the set of environment states, $A$ is the set of actions, $R:S \times A \rightarrow \mathbb{R}$ is the function mapping from states and actions to a scalar reward, $P:S \times A \rightarrow \mathbb{S}$ is the transition function between states, and $\gamma$ is the discount factor.

The injection of novelty, after an arbitrary and a priori unknown number of episodes or games $t$ constitutes a transformation from the original environment or MDP $M$ to a new environment or MDP $M'$.

We consider all aspects of the problem except an agent's decision-making model to be property of the environment.
This includes agent morphology, sensors, and action preconditions and effects.

We assume that each agent's observation space and action space remain consistent before and after novelty is injected.
This means that the  number of actions and the size and shape of observations are consistent throughout each experiment, but some never occur pre-novelty.

For example a volcano eruption is always a possibility, but it could be rare enough to be a singular experience with no previous occurrence; more prosaically, using a certain key to open a certain door is always a possibility, but it could have different outcome post-novelty, if the door has been re-keyed.

We also assume that the agent's mission $T$ is consistent before and after the novelty, meaning that we do not consider changes to the extrinsic agent rewards.

§ WORLDCLONER

is an end-to-end trainable neuro-symbolic world model comprised of two components: (1) a neural policy and (2) a symbolic world model.
The symbolic world model (which we also refer to as the “rule model”) consists of rules that, in aggregate, approximate the environment's latent transition function.
The rule model serves two core functions.
First, the rule model learns to predict state transitions pre-novelty.
Rule violations  thus indicate the introduction of novelty and the need to update the rule model and the policy.
Second, once in a post-novelty environment,  uses the rule model to simulate the environment, enabling rollouts for retraining the neural policy model so as to require fewer interactions with the real environment.
Shown in Figure <ref>, this interaction between the world model and the policy allows  to trust its policy pre-novelty, then depend more heavily on its world model post-novelty.
Our world model algorithm is designed so that the rule model is independent of the neural policy implementation, making our approach compatible with any policy framework that uses the same data inputs as the rule model.
For our implementation of , we use Proximal Policy Optimization (PPO) <cit.> on an Advantage Actor-Critic (A2C) neural architecture.

§.§ Interval-Based Symbolic World Model

In  the symbolic world model–modeling the transition function $P$–is represented as a set of $K$ rules $\{\rho_k\}$ of the form $\langle c_s, c_a, e\rangle$.
In this representation, $c_s$ is a state precondition, $c_a$ is the action precondition (similar to a do-calculus precondition ), and $e$ is an effect.

A rule $\rho$ is determined to apply if the input state $s$ and action $a$ match that rule's preconditions.

The state preconditions contain a set of values corresponding to a subset of state features $\phi_1...\phi_m$.
When both the state and action preconditions of $\{\rho\}$ are satisfied, then $\{\rho\}$ is applicable and can be executed if chosen.

Effects $e$ are the difference between the input state and the predicted state: $e=s^{'}-s$.

This formulation has similarities to logical calculus frameworks such as ADL and PDDL <cit.> by encoding preconditions and effects.
Our approach is designed to be learned, rather than engineered, similar to “game rule” learning <cit.>.

uniquely formulates preconditions as a set of axis-aligned bounding intervals (AABIs), also known as hyperrectangles or
$n$-orthotopes <cit.> in feature space that cover the training data.
AABIs are simple, $d$-dimensional convex geometries that, given a set of sample points to group $x_1...x_n$, define the minimum interval along each dimension that encloses the entire set.
Regardless of the size of the interval, AABIs can be defined by two $d$-dimensional points—a minimum and maximum bound—which makes them very efficient to query for both training and inference.

They can accommodate a mixture of continuous and categorical (non-continuous) variables, both of which are common in symbolic methods, where categorical AABI values are simply the exact set of matching values.

For example, see the bottom of Figure <ref>, which shows the AABIs for a rule for unlocking a door in the NovGrid grid world. In this case the intervals limit the action to a single agent location $(3,5)$. Figure <ref> shows another example where the action is applicable to an interval of locations.

[roundnode/.style=circle, draw=black!60, fill=gray!5, very thick, minimum size=7mm,
squarenode/.style=rectangle, draw=black!60, fill=gray!20, very thick, minimum size=5mm]

[roundnode, align=center] (state1) State $T$
[squarenode, align=center] (action) [right=of state1] UnlockDoor;
[roundnode, align=center] (state2) [right=of action]State $T+1$
(txt) [below=of action] This state transition yields the creation of the following rule:;
[->] (state1.east) – (action.west);
[->] (action.east) – (state2.west);
[->, dotted] (action.south) – (txt.north);

Preconditions:     Effect:

AgentLocation: min=(3,5), max=(3,5)     DoorState: set={locked} $\rightarrow$ DoorState: set={closed}

AgentFacing: set={East}     Inventory: set={YellowKey} $\rightarrow$ Inventory: set=None

Inventory: set={YellowKey}

DoorState: set={Locked}

DoorLocation: min=(3,6), max=(3,6)

Action Precondition:

Top shows example environmental states passed to the rule learner (changes underlined). Bottom shows the learned world model rule describing the key opening a door.

The AABIs of the preconditions do not need to be intersecting; each unique rule can have multiple disjoint intervals. Our rule update algorithm (see next section) minimizes the number of different intervals.

Multiple rules per action will exist when actions have different effects depending on the current state.
For example, in a grid world, the  action changes the agent's $\phi$

positional feature in the state along the direction the agent is facing when nothing is in the way,
but  will have no effect on the state if there is a wall directly in front of the agent.
This same functionality enables us to account for probabilistic transitions; multiple rules will have the same action and state precondition but different effect distributions.
Using the example of opening a locked door with a key, there is the possibility that a lock is “sticky” and an agent may require several tries. The effect of the rule that predicts the opening of the lock would then be a distribution over the
rules with identical preconditions but different effects.

Prior State $s_{t-1}$, Action $a_{t-1}$, NextState $s$, WorldModel rule set $P$
Applied Rule $\rho$
StateChange $\delta s = s - s_{t-1}$
$RuleHit = \texttt{False}$
Rule $\rho_k = \langle c_{s,k}, c_{a,k}, e_k\rangle$ in $P$
$a_{t-1} == c_{a,k}$
$\delta s == e_k$
$CollisionCheck(s_{t-1}, c_{s,k})$
$RuleHit \leftarrow \texttt{True}$
return $\rho$

$RuleRelaxation(\rho, s_{t-1})$
$RuleHit \leftarrow \texttt{True}$

$CollisionCheck(s_{t-1}, c_{s,k})$
$RuleCollisionResolution(\rho, s_{t-1})$

$RuleCreation(c_{s} = s_{t-1}, c_{a} = a_{t-1}, e = \delta s)$
$RuleHit \leftarrow \texttt{True}$

$RuleHit == \texttt{False}$
$RuleCreation(c_{s} = s_{t-1}, c_{a} = a_{t-1}, e = \delta s)$

Rule Model Update

§.§ Rule Learning

The rule learning process (Algorithm <ref>) constructs a compact, collision-free set of rules that provide maximum coverage of the state-action space while minimizing the complexity of the symbolic world model.
Moreover, it is an online updating process; once a rule is learned, it can be updated without knowledge of past observations.

The rule update process begins with the rule model initialized as an empty set.
After an action is taken in the environment, the rule learner receives the prior state of the environment from which to derive a precondition,
the action taken, and a new state of the environment from which to derive an effect.
Comparing the prior state, action, and new state with the state preconditions, action preconditions, and effects (respectively) of any existing rules in the model,
the update algorithm enters one of four cases:

* No Change: The prior state falls inside the state precondition AABI of an existing rule with a matching action and effect.

* Rule Creation: There is no rule where the action precondition is satisfied or the state difference matches the effect.
A new “point” rule is created that exactly describes the prior state.

* Rule Relaxation: A rule exists where the action precondition is satisfied and state difference matches the effect, but the prior state is not covered by the existing rule's state precondition AABI.
The rule is “relaxed” by expanding the AABI.

* Rule Collision Resolution: A rule exists where the action precondition and state precondition AABI are satisfied but the effect is different.

The AABI of the existing rule is split with a minimum cut (min-cut) operation.

2|c|Rule 1

Preconditions:     Effect:

AgentLocation: min=(1,1), max=(5,2)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

[roundnode/.style=circle, draw=black!60, fill=gray!5, very thick, minimum size=7mm,
squarenode/.style=rectangle, draw=black!60, fill=gray!20, very thick, minimum size=5mm]

[roundnode, align=center] (state1) State $T$
AgentLocation: min=(3,4)
WallLocation: min=(3,6);
[squarenode, align=center] (action) [right=of state1] Forward;
[roundnode, align=center] (state2) [right=of action]State $T+1$
AgentLocation: min=(3,5)
WallLocation: min=(3,6)

(Delta from $T$:
AgentLocation += 1);
(txt1) [above=of action] The existing rule is tested against the following state transition:;
(txt2) [below=of action] The state AABI of the rule is relaxed:;
[->] (state1.east) – (action.west);
[->] (action.east) – (state2.west);
[->, dotted] (txt1.south) – (action.north);
[->, dotted] (action.south) – (txt2.north);

2|c|Rule 1'

Preconditions:     Effect:

AgentLocation: min=(1,1), max=(5,4)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

Rule Relaxation example, where the blue underlined precondition AABI corresponding to the agent location has been expanded in the modified Rule 1'

to include agent location from state S.

When the agent takes an action, the rule learner observes the prior state at time $T$, the action executed, and the next state at time $T+1$.
If rules exist where the state transition satisfies the action precondition, the state precondition, or the effect, we first try to modify existing rules using Rule Relaxation and Rule Collision Resolution.
Rule Creation is only necessary if collision resolution and relaxation do not apply.
Given the agent's performed action, we initially only consider rules where the action precondition is satisfied.
We then identify whether the state prior to the action is contained in any of these existing rules' AABI.
This is achieved using the geometric hyperplane separation theorem (also called the separating axis theorem) <cit.>.
Geometrically, we can assert that for all features $\phi_d \in \Phi$, if there exists a feature for which the point is less than the min or more than the max of an interval, then a separating hyperplane exists.
The theorem states simply that if a hyperplane exists in feature space between the point and the geometric shape, there is no collision and the point is outside the AABI.
Specifically, for prior state $s_{t-1}$ and an AABI $I = [I_{min},I_{max}]$:

\begin{equation}
s_{t-1} \not\in I \iff \exists \phi~s.t.~[ s_{t-1,\phi} > I_{max,\phi}  \cup  s_{t-1,\phi} < I_{min,\phi} ].
\end{equation}

Rule Creation
is straightforward: the combination of prior state and action in an observed state-action-state transition does not fall within the AABI of any existing rule.
A new rule is added to the rule model where the AABI for continuous state features are assigned  and  values equal to their current value, and categorical state feature values are singleton members of their features.
Similarly, the rule's action precondition is set to the action in the state transition, and the effect is equal to the difference between $s_{t-1}$ and $s$.
This process is illustrated in Figure <ref>.
We describe a rule that is circumscribed to a single set of values for each feature as a“point” rule.

Rule Relaxation seeks to expand an AABI of an existing rule to match the newly encountered action precondition and effect.
The operation is simple: for the prior state $s_{t-1}$ and AABI $I$ represented by points $I_{min}$ and $I_{max}$, the relaxed min and max points are
$I^*_{min} = \texttt{min}(s_{t-1},I_{min})$ and $I^*_{max} = \texttt{max}(s_{t-1},I_{max})$.
Figure <ref> illustrates rule relaxation.
Here, a previously learned rule exists that models the change in agent position caused by a  action.

This rule matches the action precondition and effect but not the state precondition, possibly because it simply had not been observed yet in that part of the environment.

As a result, the AgentPosition AABI is expanded to include the observation.

After this expansion, the new AABI $I^*$ is checked once more, this time for collision with other existing rules, using the same geometric hyperplane separation theorem described above.
For comparing intervals, however, we check for a hyperplane between $I*$ and the AABI $I^k$ of another rule $\rho_k$ by comparing the maxima to the minima of the intervals.
Given maximum and minimum points $[I^*_{min},I^*_{max}]$ and $[I^k_{min},I^k_{max}]$,
if there exists a feature $\phi$ for which $I^*_{min} > I^k_{max}$, or vice versa, then there is no collision.
If a collision does exist, instead of trying to compromise between the two rules, we execute Rule Collision Resolution.

2|c|Rule 1

Preconditions:     Effect:

AgentLocation: min=(1,1), max=(8,8)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

[roundnode/.style=circle, draw=black!60, fill=gray!5, very thick, minimum size=7mm,
squarenode/.style=rectangle, draw=black!60, fill=gray!20, very thick, minimum size=5mm]

[roundnode, align=center] (state1) State $T$
AgentLocation: min=(3,5)
WallLocation: min=(3,6);
[squarenode, align=center] (action) [right=of state1] Forward;
[roundnode, align=center] (state2) [right=of action]State $T+1$
AgentLocation: min=(3,5)
WallLocation: min=(3,6)

(Delta from $T$: None);
(txt1) [above=of action] The existing rule is tested against the following state transition causing a collision:;
(txt2) [below=of action] The Rule is split about the AgentLocation state precondition:;
[->] (state1.east) – (action.west);
[->] (action.east) – (state2.west);
[->, dotted] (txt1.south) – (action.north);
[->, dotted] (action.south) – (txt2.north);

2|c|Split Rule 1'

Preconditions:     Effect:

AgentLocation; min=(1,1), max=(8,5)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

2|c|Split Rule 1”

Preconditions:     Effect:

AgentLocation; min=(1,6), max=(8,8)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

And a new rule is created:

2|c|New Rule 2

Preconditions:     Effect:

AgentLocation; min=(3,5), max=(3,5)     None

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

Rule Collision, and the resulting rule split and creation. The blue-underlined preconditions in the newly split Rule 1' and Rule 1” indicate the feature dimension along which the original Rule 1 is split. The newly created Rule 2 accounts for the state transition that caused the collision with the original Rule 1.

Rule Collision Resolution finds the min-cut partition of the existing rule's state precondition AABI.
Consider the AABI as a graph, where the graph nodes are the bounding hyperplanes (“faces” of the hyperrectangle) and the edges are lines that connect opposing hyperplanes weighted by their length.
This min-cut of the AABI is simply the division along the largest feature axis that intersects with the prior state.
The new, divided AABIs are added to the existing rule's preconditions, the original AABI is removed, and the prior state is assessed for accommodation with Rule Creation or Rule Relaxation because it may not be included in either split.

Figure <ref> illustrates a situation where the  rule is observed to not correctly predict the outcome of a state transition  because the agent hits a wall.
Because the rule describing this state transition has a precondition subsumed by the existing  rule but with a different effect, there is a rule collision.
The collision is resolved by splitting the rule.
A new point rule can be created because the prior state is now outside the AABIs of the split rules.

Post-novelty, splitting rules in Rule Collision Resolution can result in one of the split rules having a precondition with a feature with empty interval or empty categorical set.

If this occurs, the “empty split” is discarded.

§.§ Novelty Detection

Once pre-novelty neural policies converge and the symbolic world model is created as described above, learning is turned off for both; this saves compute and allows the policy to focus on exploitation.
As the agent performs tasks in the environment, it looks for state-action-state transitions that are inconsistent with the rules in the world model and triggers adaptation when one of two cases occur.

(1) The same rule is violated $n$ consecutive times.

A violation is defined as the observed subsequent state of the environment not matching a rule's expected state effect, though the state and action preconditions both match.
(2) The same observed state causes a failed prediction in more than $n$ consecutive visits.
$n$ is a hyperparameter for sensitivity to novelty, set to $n=2$ in our experiments.

Once a novelty is detected,
the neural policy and the symbolic world model begin to update online again.
The post-novelty rule update process is exactly the same as pre-novelty rule learning (Algorithm <ref>).
The rule model can thus be updated with as little as a single iteration of the rule learning algorithm, with guaranteed improved next-state prediction.

Pre-Novelty Policy $\pi$, World Model $P$, Mix Ratio $\eta$

$PostNov \leftarrow False$
$s_t \leftarrow$ initial observation

Select action $a_{t}=\pi(s_{t})$

Predict next state $\hat{s}_{t+1} = P(s_{t}, a_{t})$

Execute $a_{t}$ in $Env$ and observe
next state and reward
$s_{t+1}, r_{t}$

$PostNov \leftarrow [PostNov$ OR $DetectNovelty(P,\hat{s}_{t+1}, s_{t+1})$]

Add $\langle s_t, a_t, s_{t+1}, r_t\rangle$ to $UpdateBuffer$

$P \leftarrow RuleModelUpdate(s_t, a_t, s_{t+1})$

Add $ImagineRollouts(P)$ per $\eta$ to $UpdateBuffer$

Periodically update $\pi$ with $UpdateBuffer$

$s_t \leftarrow s_{t+1}$

Imagination-Based Adaptation

Adaptive Efficiency      Pre-novelty     Asymptotic       Update Efficiency

@0.95 (steps) $\downarrow$     Performance $\uparrow$     Performance $\uparrow$       (policy updates) $\downarrow$

5c novelty

PPO     2.25E6     0.973     0.971     2.25E6

DreamerV2     5.3E5     0.971     0.973      3.82E8

Ours     9.8E5     0.972     0.970     1.63E6

5c novelty

PPO     1.39E5     0.972     0.991     1.39E5

DreamerV2     Failed to adapt     0.965     Failed to adapt     Failed to adapt

Ours     8.3E4     0.972     0.991     1.38E5

5c novelty

PPO     2.08E6     0.992     0.971     2.08E6

DreamerV2     1.05E6     0.992     0.968     7.56E8

Ours     1.07E6     0.992     0.972     1.78E6

Novelty metric results
averaged over three runs.
DreamerV2 did not adapt to the novelty on .

§.§ Imagination-Based Policy Adaptation

Post-novelty, the newly updated rules within the symbolic world model reflect the agent's belief about the post-novelty state transition function.

The agent now uses that rule model to “imagine” how sequences of actions will play out—which we refer to as “imagination-based simulation”—and update its policy without interacting or executing actions in the true environment.

Specifically, as we show in Algorithm <ref>,
we use the rule model to simulate state-action-state transitions that then populate the agent's update buffer–the data on which the policy will be trained.
The policy training algorithm generates a loss over samples drawn from the update buffer and back-propagates loss through the policy model.
Figure <ref> shows how the standard Actor-Critic neural architecture and imagination-based simulation work together to feed real and imagined state observations.

The agent follows its policy in the imagined environment and repeatedly experiences the first rule change's consequences, receiving a reduced (or increased) expected reward, pushing the policy away from (or toward) the impacted actions.
As the symbolic world model detects new discrepancies and represents the post-novelty environment more accurately, the policy may be able to “imagine” experiencing and accommodating novelty with minimal exposure to the novelty in the environment.

Continuing the example of the re-keyed door lock (Figure <ref>, top), the agent has executed its pre-novelty policy of navigating to the yellow key and then to the yellow door only to discover that the door no longer opens.
Upon arriving at the state $\langle$AgentInFrontOfDoor,  AgentCarryingYellowKey, DoorLocked$\rangle$
and performing the action , the agent expects $DoorUnlocked$ to become true.
However, since the door has been re-keyed the  action results in no change.

When this occurs, there is a rule collision, resolved by creating a rule with a $\{\emptyset\}$ effect delta, and the old rule is “split”. In this case, the split results in states with empty AABIs, in which case the rule is deleted.

The rule collision is detected as a novelty, and the agent begins updating its policy.
Specifically, the agent no longer receives the utility of walking through the door and the policy updates to reflect reduced utility of being directly in front of the door.
Over time, the utility of the state will decrease enough that the agent will prefer other states, increasing exploration and eventually coming across the blue key.
This switch from exploitation to exploration is accelerated by the agent's ability to repeatedly imagine arriving before the door and choosing alternative actions because there is no valid rule in which the door opens.

Eventually through exploration the agent will find itself before the door with the blue key: $\langle$AgentInFrontOfDoor, AgentCarryingBlueKey, DoorLocked$\rangle$
Trying to open the door with the blue key will this time result in the effect of $DoorUnlocked$ changing to $DoorClosed$.
This, in conjunction with the  action precondition does not match any existing rule, and a new rule is created, at which point imagination will facilitate faster policy learning.

Once again having access to the utility and reward of states beyond the door, the agent will converge to a new policy involving the blue key.

To account for world model error, our policy is also trained on real environment interactions.

A mixing ratio parameter controls the ratio of imagined and real environment rollouts in the policy update buffer;
For every $t$ steps in the real environment, the agent runs $\frac{t}{\eta}$ steps in the imagined environment.

This mixing effectively adds noise to the policy update and

helps drive the policy back into an “explore” mode, where actions will be selected more randomly by the policy.

§ EXPERIMENTS

We perform experiments in the NovGrid <cit.>
environment, which extends the MiniGrid <cit.> environment with novelties that can be injected at an arbitrary time during testing.
NovGrid allows for controlled, replicable experiments with stock novelties.
We use two 8x8 MiniGrid environments:
(1)  where an agent must pick up a key, unlock a door, and navigate to the goal behind that door, and
(2)  where an agent must navigate a maze that has a pool of lava lining the side of the maze nearest to the goal.
In all cases we used the default sparse MiniGrid reward.

We tested the performance of our method on three novelty types:
shortcut, delta, and barrier <cit.>.
is a shortcut novelty that makes lava in the  environment to be harmless to the agent (where pre-novelty it destroyed the agent), offering a shorter path to the goal.

is a delta novelty that changes which of two keys unlock a door in the  environment,
not changing the difficulty of reaching the goal but requiring different state-action sequences of similar length and complexity.
is a barrier novelty and the inverse of ,
changing the effect of lava in the  to destroy the agent (where pre-novelty, lava was harmless), thereby eliminating the shorter lava path to the goal.

The  and  novelties are conceptually shown in Figure <ref>.

These plots show the adaptive performance post-novelty.
Each method experiences novelty injection at 10,000 environment steps (signified by the vertical dotted black line).
Top shows novelty response for the  “delta” novelty on the  environment.
Middle shows novelty response for the  “shortcut” novelty in the  environment. Note: Dreamer does not find the shortcut.
Bottom shows novelty response for the  “barrier” novelty in the  environment, where lava is safe for the agent pre-novelty.

To evaluate performance in these test environments, we adopt two metrics for novelty adaptation from <cit.> that builds on <cit.>.
(1) Asymptotic adaptive performance is the final performance of the agent post-novelty relative to a random baseline, where higher is better.

This is used to observe whether a method fully adapted to the post-novelty environment.
(2) Adaptive efficiency is the number of time steps in the real, post-novelty environment required to converge to asymptotic adaptive performance, where fewer steps is better.
In our work, this is achieved when the 10-step moving average method reaches $95\%$ of asymptotic adaptive performance.
We add a third measure, update efficiency, which is the number of policy updates required post-novelty to reach asymptotic adaptive performance, where–again–fewer steps is better.

We compare  post-novelty performance with two baselines.
The first is a standard reinforcement learning agent using Proximal Policy Optimization (PPO) <cit.>, the same model-free reinforcement learning approach used by the neural policy in our  method.
The second baseline is DreamerV2 <cit.>, a state-of-the-art world modeling agent that learns an end-to-end neural world model.
The agents were not given any knowledge about the novelties at training time.
All methods were allowed to train for as many as 10 million time steps to ensure convergence, and results for each method were averaged over three runs.
Novelty was injected at episode 50k, well after all agents had converged.
Since the baseline agents lack novelty detection capabilities, we keep their learning on during evaluations so that agents can react immediately after novelty is injected.

The policy architectures for all agents use a convolutional neural net feature extractor and two fully connected output networks, one to estimate the value and one to serve as the policy functions of the agent.
All hyperparameters and architectures for DreamerV2 were consistent with the original publication <cit.>,
and all PPO hyperparameters are consistent with MiniGrid-suggested hyperparameters <cit.>.
For  we use a mixing ratio of 60% real rollouts to 40% imagined rollouts.
This ratio was determined empirically by looking at the trade-off between asymptotic adaptive performance and adaptive efficiency.
At higher amounts of imagination, the agent did not recover full post-novelty performance.
The  world model uses symbolic features from MiniGrid for rule learning, including the object type, color, and position of the agent and objects, the agent orientation, the agent's inventory, and whether doors are locked, unlocked, or open.

§ RESULTS

We document the results of these evaluations in Table <ref>, with the adaptation process of our method further illustrated in Figure <ref>.
The table shows that pre-novelty, as expected, all three methods converge in all three novelty scenarios to effectively the same performance.
This means that all methods were able to find solution sequences of equal length to the goal for all environments.

For the  “delta” novelty, DreamerV2 slightly outperforms  in adaptive efficiency, while both dramatically outperform PPO.
From this result we can observe that imagination is strongly beneficial to post-novelty adaptation.
However, adaptive efficiency doesn't tell the entire story.
DreamerV2 updates its policy on imagination only, which means that for each update to the world model, DreamerV2 must update its policy using many imagination iterations.
As a result, update efficiency of DreamerV2 demands nearly two orders of magnitude more policy updates than .

For the  “shortcut” novelty,  substantially outperforms PPO in adaptive efficiency while DreamerV2 never finds the shortcut novelty.
Dreamer was trained for 2.5 million post-novelty environment steps in multiple runs with the same result.
We attribute DreamerV2's failure to the unique

way in which its policy learner

depends on the accuracy of its world model.

Unfortunately, the world model continues to predict negative consequence of the lava.
Since the longer, pre-novelty solution still reaches the goal, Dreamer's world model remains fixed, imagination never varies, and the policy never updates.
As a result, the world model can overfit easily if the policy produces the same sequence of actions every time.

PPO and  do not encounter this issue because small variations in the policy occur that cause policy updates, which allows for more sensitivity to the shortcut novelty.
However, these methods aren't perfect either; as can be seen in Figure <ref>.
It takes both methods more than 25,000 environment steps to react to the shortcut novelty injection, unlike in the barrier and delta novelties.
This demonstrates a unique challenge in shortcut novelties: when the the pre-novelty optimal path still exists, converged, non-exploring agents will struggle to detect novelty.
As noted by <cit.>, future research is needed on novelty-aware exploration techniques.

This shows the  1-step prediction error vs environment steps during rule learner training in the Empty MiniGrid Environment.

Finally, the  “barrier” novelty is similar to the
novelty, where  and DreamerV2 have very similar adaptive efficiency both outperforming PPO by a wide margin, but in all cases taking a long time to converge.
What's more, in the  and  novelty, the high variance in both DreamerV2 and  shows that in some of the trials both of these methods found the new solution very early in the adaption process, but could not consistently converge to it.
Transfer learning tells us that both of these results are expected, as the simple pre-novelty solution does not prepare the policies for the more complex post-novelty environment.

In general, our model iw able to make much more efficient use of our updates than DreamerV2.
Because DreamerV2 only trains its policy in imagination, it runs hundreds of imagination policy updates for every world model update it executes.
As shown in the last column of Table <ref>, blending the environment interaction data with the imagination data,  requires significantly fewer policy updates.

We also evaluate the efficiency and accuracy of the rule learner (results shown in Figure <ref>). After every 100 training steps we would validate the model accuracy by running a random policy for 1000 steps and measure the average 1-step predictive error of the world model.
The pre-novelty rule learner requires only about 2000 training steps before it converges to near-perfect prediction accuracy.
Grid worlds are simple, deterministic environments, so this is an unsurprising result.
The key is that it converges rapidly and is sample-efficient compared to neural world model learning techniques <cit.>.

These results show that  with only 40% imagination improves adaptation efficiency across all novelties over a neural policy with no world model.
Furthermore,  is competitive with DreamerV2 across these novelties and adapts with shortcuts that DreamerV2 fails to detect.
Most interestingly, we can see from the last column of Table <ref> that  achieves these results with fewer policy updates than PPO and DreamerV2.
This, however, will vary with the amount of imagination injected into the policy learner by , and should be the subject of further study.

§ CONCLUSIONS

As autonomous agents are deployed in open-world decision-making situations, techniques designed deliberately to handle novelty will be required.
This can include novelties from learning to unlock a door with a new key to discovering a new shortcut to reduce travel time or avoiding new hazards on previous safe solutions.

To this end, we show that reinforcement learning agent policies can be adapted more efficiently to novelties using symbolic world models that (1) can be updated rapidly and (2) simulate rollouts that then can be added to the policy learning process, thereby reducing the number of direct interactions with the post-novelty environment.
Specifically, our results show that  is comparable in adaptation efficiency to state-of-the-art neural world modeling techniques while requiring only a fraction of policy updates.
This suggests that symbolic representations are an effective complement to neural representations for adapting reinforcement learning agents to novelty.

For effective novelty adaptation, future techniques should consider how to leverage world models and their ability to learn models of the transition function and the policy together.

Our observations of world model-based agents adapting to novelty suggest that exploration is key to efficient novelty adaptation.
Even with access to world models, nearly all reinforcement learning agents assume that the converged pre-novelty policy can be followed greedily.
This leads to a problematic feedback loop where policies trained with imagination are only able to access what the world model knows, which may not include the novelty, but these same policies direct the interaction with the environment.
As a result, unless the novelty is along the path of the old optimal policy, the agent may never encounter the novelty, and the world model that trains it may never adapt.

New exploration techniques that operate in more plausible “open-world” environments will need to consider how to identify a novelty using the world model and how best to trade off this “novelty exploration” with following the agent's policy.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

authorpersonJoshua Alspector.
Representation Edit Distance as a Measure of
journalarXiv preprint arXiv:2111.02770

[Badia, Piot, Kapturowski, Sprechmann,
Vitvitskyi, Guo, and BlundellBadia et al2020]
authorpersonA Badia, personB Piot,
personS Kapturowski, personP Sprechmann,
personA Vitvitskyi, personD Guo, and
personC Blundell. year2020.
Agent57: Outperforming the human Atari benchmark.
In booktitleProceedings of the 37th International Conference
on Machine Learning, Online, PMLR, Vol. volume119.

[Ball et alBall
et al1997]
authorpersonKeith Ball et al
An elementary introduction to modern convex
journalFlavors of geometry volume31,
number1-58 (year1997), pages26.

[Balloch, Kim, Inman, and RiedlBalloch
et al2022a]
authorpersonJonathan C Balloch, personJulia
Kim, personJessica L Inman, and personMark O
Riedl. year2022a.
The Role of Exploration for Task Transfer in
Reinforcement Learning.
journalIROS Workshop on Lifelong Learning of
High-level Cognitive and Reasoning Skills.

[Balloch, Lin, Hussain, Srinivas, Peng, Kim,
and RiedlBalloch et al2022b]
authorpersonJonathan C Balloch, personZhiyu
Lin, personMustafa Hussain, personAarun Srinivas,
personXiangyu Peng, personJulia Kim, and
personMark Riedl. year2022b.
NovGrid: A Flexible Grid World for Evaluating Agent
Response to Novelty. In booktitleIn Proceedings of AAAI
Symposium, Designing Artificial Intelligence for Open Worlds.

[Boult, Grabowicz, Prijatelj, Stern, Holder,
Alspector, Jafarzadeh, Ahmad, Dhamija, Li, et alBoult
et al2021]
authorpersonTerrance Boult, personPrzemyslaw
Grabowicz, personDerek Prijatelj, personRoni Stern,
personLawrence Holder, personJoshua Alspector,
personMohsen M Jafarzadeh, personToqueer Ahmad,
personAkshay Dhamija, personChunchun Li,
et al year2021.
Towards a Unifying Framework for Formal Theories of
Novelty. In booktitleProceedings of the AAAI Conference on
Artificial Intelligence, Vol. volume35.

[Braun, Aertsen, Wolpert, and MehringBraun
et al2009]
authorpersonDaniel A Braun, personAd
Aertsen, personDaniel M Wolpert, and personCarsten
Mehring. year2009.
Learning optimal adaptation strategies in
unpredictable motor tasks.
journalJournal of Neuroscience
volume29, number20 (year2009),

[Chen, Luo, Ma, and ZhangChen
et al2021]
authorpersonYining Chen, personHaipeng Luo,
personTengyu Ma, and personChicheng Zhang.
titleActive Online Learning with Hidden Shifting Domains.
[arxiv]2006.14481 [cs.LG]

[Chevalier-Boisvert, Willems, and
PalChevalier-Boisvert et al2018]
authorpersonMaxime Chevalier-Boisvert,
personLucas Willems, and personSuman Pal.
titleMinimalistic Gridworld Environment for OpenAI Gym.

authorpersonHarold Scott Macdonald Coxeter.
booktitleRegular polytopes.
publisherCourier Corporation.

[Guzdial and RiedlGuzdial and Riedl2017]
authorpersonMatthew Guzdial and
personMark O. Riedl. year2017.
Game Engine Learning from Video. In
booktitleProceedings of the 2017 International Conference on
Artificial Intelligence.

<http://www.cc.gatech.edu/ riedl/pubs/ijcai17.pdf>

[Ha and SchmidhuberHa and
authorpersonDavid Ha and personJürgen
Schmidhuber. year2018.
Recurrent World Models Facilitate Policy
Evolution. In booktitleAdvances in Neural Information
Processing Systems, editorpersonS. Bengio,
personH. Wallach, personH. Larochelle,
personK. Grauman, personN. Cesa-Bianchi, and
personR. Garnett (Eds.), Vol. volume31.
publisherCurran Associates, Inc.

[Hafner, Lillicrap, Ba, and NorouziHafner
et al2019]
authorpersonDanijar Hafner, personTimothy
Lillicrap, personJimmy Ba, and personMohammad
Norouzi. year2019.
Dream to Control: Learning Behaviors by Latent
Imagination. In booktitleInternational Conference on
Learning Representations.

[Hafner, Lillicrap, Norouzi, and BaHafner
et al2021]
authorpersonDanijar Hafner, personTimothy P
Lillicrap, personMohammad Norouzi, and personJimmy
Ba. year2021.
Mastering Atari with Discrete World Models. In
booktitleInternational Conference on Learning

[Hastie, Tibshirani, Friedman, and
FriedmanHastie et al2009]
authorpersonTrevor Hastie, personRobert
Tibshirani, personJerome H Friedman, and
personJerome H Friedman. year2009.
booktitleThe elements of statistical learning: data
mining, inference, and prediction. Vol. volume2.

authorpersonElad Hazan.
Introduction to online convex optimization.
journalFoundations and Trends® in
Optimization volume2, number3-4
(year2016), pages157–325.

[Klenk, Piotrowski, Stern, Mohan, and
de KleerKlenk et al2020]
authorpersonMatthew Klenk, personWiktor
Piotrowski, personRoni Stern, personShiwali Mohan,
and personJohan de Kleer. year2020.
Model-Based Novelty Adaptation for Open-World AI.
In booktitleInternational Workshop on Principles of
Diagnosis (DX).

[Lin, Wu, Peri, Fu, Jiang, and AhnLin
et al2020]
authorpersonZhixuan Lin, personYi-Fu Wu,
personSkand Peri, personBofeng Fu,
personJindong Jiang, and personSungjin Ahn.
Improving generative imagination in object-centric
world models. In booktitleInternational Conference on
Machine Learning. PMLR, pages6140–6149.

[Loyall, Pfeffer, Niehaus, Mayer, Rizzo, Gee,
Cvijic, Manning, Skitka, Becker, et alLoyall et al2022]
authorpersonBryan Loyall, personAvi
Pfeffer, personJames Niehaus, personTyler Mayer,
personPaola Rizzo, personAlex Gee,
personSanja Cvijic, personWilliam Manning,
personMary Kate Skitka, personMcCoy Becker,
et al year2022.
An Integrated Architecture for Online Adaptation to
Novelty in Open Worlds using Probabilistic Programming and Novelty-Aware
Planning. In booktitleIn Proceedings of AAAI Symposium,
Designing Artificial Intelligence for Open Worlds.

[McCloskey and CohenMcCloskey and
authorpersonMichael McCloskey and
personNeal J Cohen. year1989.
Catastrophic interference in connectionist
networks: The sequential learning problem.
In booktitlePsychology of learning and motivation.
Vol. volume24. publisherElsevier,

authorpersonDrew McDermott.
The 1998 AI Planning Systems Competition.
journalAI Mag.  volume21
(year2000), pages35–55.

[Peng, Balloch, and RiedlPeng
et al2021]
authorpersonXiangyu Peng, personJonathan C
Balloch, and personMark O Riedl.
Detecting and Adapting to Novelty in Games. In
booktitleAAAI Workshop on Reinforcement Learning in Games.

[Pimentel, Clifton, Clifton, and
TarassenkoPimentel et al2014]
authorpersonMarco AF Pimentel, personDavid A
Clifton, personLei Clifton, and personLionel
Tarassenko. year2014.
A review of novelty detection.
journalSignal Processing  volume99
(year2014), pages215–249.

[Pretorius, Cameron, Smit, van Biljon, Francis,
Azeez, Laterre, and BeguirPretorius et al2020]
authorpersonArnu Pretorius, personScott
Cameron, personAndries Petrus Smit, personElan van
Biljon, personLawrence Francis, personFemi Azeez,
personAlexandre Laterre, and personKarim Beguir.
titleLearning to communicate through imagination with
model-based deep multi-agent reinforcement learning.

[Racanière, Weber, Reichert, Buesing, Guez,
Jimenez Rezende, Puigdomènech Badia, Vinyals, Heess, Li, Pascanu, Battaglia,
Hassabis, Silver, and WierstraRacanière et al2017]
authorpersonSébastien Racanière,
personTheophane Weber, personDavid Reichert,
personLars Buesing, personArthur Guez,
personDanilo Jimenez Rezende, personAdrià
Puigdomènech Badia, personOriol Vinyals,
personNicolas Heess, personYujia Li,
personRazvan Pascanu, personPeter Battaglia,
personDemis Hassabis, personDavid Silver, and
personDaan Wierstra. year2017.
Imagination-Augmented Agents for Deep
Reinforcement Learning.
In booktitleAdvances in Neural Information
Processing Systems 30. publisherNeural Information
Processing Systems Foundation, Inc. (NIPS), pages5690–5701.

[Sarathy, Kasenberg, Goel, Sinapov, and
ScheutzSarathy et al2021]
authorpersonVasanth Sarathy, personDaniel
Kasenberg, personShivam Goel, personJivko Sinapov,
and personMatthias Scheutz. year2021.
SPOTTER: Extending Symbolic Planning Operators
through Targeted Reinforcement Learning. In
booktitleProceedings of the 20th International Conference on
Autonomous Agents and Multi-Agent Systems. pages1118–1126.

authorpersonJürgen Schmidhuber.
An on-line algorithm for dynamic reinforcement
learning and planning in reactive environments. In
booktitle1990 IJCNN international joint conference on neural
networks. IEEE, pages253–258.

[Schulman, Wolski, Dhariwal, Radford, and
KlimovSchulman et al2017]
authorpersonJohn Schulman, personFilip
Wolski, personPrafulla Dhariwal, personAlec Radford,
and personOleg Klimov. year2017.
Proximal policy optimization algorithms.
journalarXiv preprint arXiv:1707.06347

[Shalev-Shwartz et alShalev-Shwartz
et al2012]
authorpersonShai Shalev-Shwartz et al
Online learning and online convex optimization.
journalFoundations and Trends® in
Machine Learning volume4, number2
(year2012), pages107–194.

[Silver, Schrittwieser, Simonyan, Antonoglou,
Huang, Guez, Hubert, Baker, Lai, Bolton, et alSilver
et al2017]
authorpersonDavid Silver, personJulian
Schrittwieser, personKaren Simonyan, personIoannis
Antonoglou, personAja Huang, personArthur Guez,
personThomas Hubert, personLucas Baker,
personMatthew Lai, personAdrian Bolton,
et al year2017.
Mastering the game of go without human knowledge.
journalnature volume550,
number7676 (year2017), pages354–359.

[Silver, Yang, and LiSilver
et al2013]
authorpersonDaniel L Silver, personQiang
Yang, and personLianghao Li. year2013.
Lifelong machine learning systems: Beyond learning
algorithms. In booktitle2013 AAAI spring symposium

[Sutton and BartoSutton and Barto2018]
authorpersonRichard S Sutton and
personAndrew G Barto. year2018.
booktitleReinforcement learning: An introduction.
publisherMIT press.

[Vinyals, Babuschkin, Czarnecki, Mathieu,
Dudzik, Chung, Choi, Powell, Ewalds, Georgiev, et alVinyals
et al2019]
authorpersonOriol Vinyals, personIgor
Babuschkin, personWojciech M Czarnecki,
personMichaël Mathieu, personAndrew Dudzik,
personJunyoung Chung, personDavid H Choi,
personRichard Powell, personTimo Ewalds,
personPetko Georgiev, et al
Grandmaster level in StarCraft II using multi-agent
reinforcement learning.
journalNature volume575,
number7782 (year2019), pages350–354.

authorpersonLucas Willems.
titlelcswillems/torch-ac: Recurrent and multi-process
PyTorch implementation of deep reinforcement Actor-Critic algorithms A2C and

[Zhu, Lin, and ZhouZhu et al2021]
authorpersonZhuangdi Zhu, personKaixiang
Lin, and personJiayu Zhou. year2021.
titleTransfer Learning in Deep Reinforcement Learning: A
[arxiv]2009.07888 [cs.LG]

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

authorpersonJoshua Alspector.
Representation Edit Distance as a Measure of
journalarXiv preprint arXiv:2111.02770

[Badia, Piot, Kapturowski, Sprechmann,
Vitvitskyi, Guo, and BlundellBadia et al2020]
authorpersonA Badia, personB Piot,
personS Kapturowski, personP Sprechmann,
personA Vitvitskyi, personD Guo, and
personC Blundell. year2020.
Agent57: Outperforming the human Atari benchmark.
In booktitleProceedings of the 37th International Conference
on Machine Learning, Online, PMLR, Vol. volume119.

[Ball et alBall
et al1997]
authorpersonKeith Ball et al
An elementary introduction to modern convex
journalFlavors of geometry volume31,
number1-58 (year1997), pages26.

[Balloch, Kim, Inman, and RiedlBalloch
et al2022a]
authorpersonJonathan C Balloch, personJulia
Kim, personJessica L Inman, and personMark O
Riedl. year2022a.
The Role of Exploration for Task Transfer in
Reinforcement Learning.
journalIROS Workshop on Lifelong Learning of
High-level Cognitive and Reasoning Skills.

[Balloch, Lin, Hussain, Srinivas, Peng, Kim,
and RiedlBalloch et al2022b]
authorpersonJonathan C Balloch, personZhiyu
Lin, personMustafa Hussain, personAarun Srinivas,
personXiangyu Peng, personJulia Kim, and
personMark Riedl. year2022b.
NovGrid: A Flexible Grid World for Evaluating Agent
Response to Novelty. In booktitleIn Proceedings of AAAI
Symposium, Designing Artificial Intelligence for Open Worlds.

[Boult, Grabowicz, Prijatelj, Stern, Holder,
Alspector, Jafarzadeh, Ahmad, Dhamija, Li, et alBoult
et al2021]
authorpersonTerrance Boult, personPrzemyslaw
Grabowicz, personDerek Prijatelj, personRoni Stern,
personLawrence Holder, personJoshua Alspector,
personMohsen M Jafarzadeh, personToqueer Ahmad,
personAkshay Dhamija, personChunchun Li,
et al year2021.
Towards a Unifying Framework for Formal Theories of
Novelty. In booktitleProceedings of the AAAI Conference on
Artificial Intelligence, Vol. volume35.

[Braun, Aertsen, Wolpert, and MehringBraun
et al2009]
authorpersonDaniel A Braun, personAd
Aertsen, personDaniel M Wolpert, and personCarsten
Mehring. year2009.
Learning optimal adaptation strategies in
unpredictable motor tasks.
journalJournal of Neuroscience
volume29, number20 (year2009),

[Chen, Luo, Ma, and ZhangChen
et al2021]
authorpersonYining Chen, personHaipeng Luo,
personTengyu Ma, and personChicheng Zhang.
titleActive Online Learning with Hidden Shifting Domains.
[arxiv]2006.14481 [cs.LG]

[Chevalier-Boisvert, Willems, and
PalChevalier-Boisvert et al2018]
authorpersonMaxime Chevalier-Boisvert,
personLucas Willems, and personSuman Pal.
titleMinimalistic Gridworld Environment for OpenAI Gym.

authorpersonHarold Scott Macdonald Coxeter.
booktitleRegular polytopes.
publisherCourier Corporation.

[Guzdial and RiedlGuzdial and Riedl2017]
authorpersonMatthew Guzdial and
personMark O. Riedl. year2017.
Game Engine Learning from Video. In
booktitleProceedings of the 2017 International Conference on
Artificial Intelligence.

<http://www.cc.gatech.edu/ riedl/pubs/ijcai17.pdf>

[Ha and SchmidhuberHa and
authorpersonDavid Ha and personJürgen
Schmidhuber. year2018.
Recurrent World Models Facilitate Policy
Evolution. In booktitleAdvances in Neural Information
Processing Systems, editorpersonS. Bengio,
personH. Wallach, personH. Larochelle,
personK. Grauman, personN. Cesa-Bianchi, and
personR. Garnett (Eds.), Vol. volume31.
publisherCurran Associates, Inc.

[Hafner, Lillicrap, Ba, and NorouziHafner
et al2019]
authorpersonDanijar Hafner, personTimothy
Lillicrap, personJimmy Ba, and personMohammad
Norouzi. year2019.
Dream to Control: Learning Behaviors by Latent
Imagination. In booktitleInternational Conference on
Learning Representations.

[Hafner, Lillicrap, Norouzi, and BaHafner
et al2021]
authorpersonDanijar Hafner, personTimothy P
Lillicrap, personMohammad Norouzi, and personJimmy
Ba. year2021.
Mastering Atari with Discrete World Models. In
booktitleInternational Conference on Learning

[Hastie, Tibshirani, Friedman, and
FriedmanHastie et al2009]
authorpersonTrevor Hastie, personRobert
Tibshirani, personJerome H Friedman, and
personJerome H Friedman. year2009.
booktitleThe elements of statistical learning: data
mining, inference, and prediction. Vol. volume2.

authorpersonElad Hazan.
Introduction to online convex optimization.
journalFoundations and Trends® in
Optimization volume2, number3-4
(year2016), pages157–325.

[Klenk, Piotrowski, Stern, Mohan, and
de KleerKlenk et al2020]
authorpersonMatthew Klenk, personWiktor
Piotrowski, personRoni Stern, personShiwali Mohan,
and personJohan de Kleer. year2020.
Model-Based Novelty Adaptation for Open-World AI.
In booktitleInternational Workshop on Principles of
Diagnosis (DX).

[Lin, Wu, Peri, Fu, Jiang, and AhnLin
et al2020]
authorpersonZhixuan Lin, personYi-Fu Wu,
personSkand Peri, personBofeng Fu,
personJindong Jiang, and personSungjin Ahn.
Improving generative imagination in object-centric
world models. In booktitleInternational Conference on
Machine Learning. PMLR, pages6140–6149.

[Loyall, Pfeffer, Niehaus, Mayer, Rizzo, Gee,
Cvijic, Manning, Skitka, Becker, et alLoyall et al2022]
authorpersonBryan Loyall, personAvi
Pfeffer, personJames Niehaus, personTyler Mayer,
personPaola Rizzo, personAlex Gee,
personSanja Cvijic, personWilliam Manning,
personMary Kate Skitka, personMcCoy Becker,
et al year2022.
An Integrated Architecture for Online Adaptation to
Novelty in Open Worlds using Probabilistic Programming and Novelty-Aware
Planning. In booktitleIn Proceedings of AAAI Symposium,
Designing Artificial Intelligence for Open Worlds.

[McCloskey and CohenMcCloskey and
authorpersonMichael McCloskey and
personNeal J Cohen. year1989.
Catastrophic interference in connectionist
networks: The sequential learning problem.
In booktitlePsychology of learning and motivation.
Vol. volume24. publisherElsevier,

authorpersonDrew McDermott.
The 1998 AI Planning Systems Competition.
journalAI Mag.  volume21
(year2000), pages35–55.

[Peng, Balloch, and RiedlPeng
et al2021]
authorpersonXiangyu Peng, personJonathan C
Balloch, and personMark O Riedl.
Detecting and Adapting to Novelty in Games. In
booktitleAAAI Workshop on Reinforcement Learning in Games.

[Pimentel, Clifton, Clifton, and
TarassenkoPimentel et al2014]
authorpersonMarco AF Pimentel, personDavid A
Clifton, personLei Clifton, and personLionel
Tarassenko. year2014.
A review of novelty detection.
journalSignal Processing  volume99
(year2014), pages215–249.

[Pretorius, Cameron, Smit, van Biljon, Francis,
Azeez, Laterre, and BeguirPretorius et al2020]
authorpersonArnu Pretorius, personScott
Cameron, personAndries Petrus Smit, personElan van
Biljon, personLawrence Francis, personFemi Azeez,
personAlexandre Laterre, and personKarim Beguir.
titleLearning to communicate through imagination with
model-based deep multi-agent reinforcement learning.

[Racanière, Weber, Reichert, Buesing, Guez,
Jimenez Rezende, Puigdomènech Badia, Vinyals, Heess, Li, Pascanu, Battaglia,
Hassabis, Silver, and WierstraRacanière et al2017]
authorpersonSébastien Racanière,
personTheophane Weber, personDavid Reichert,
personLars Buesing, personArthur Guez,
personDanilo Jimenez Rezende, personAdrià
Puigdomènech Badia, personOriol Vinyals,
personNicolas Heess, personYujia Li,
personRazvan Pascanu, personPeter Battaglia,
personDemis Hassabis, personDavid Silver, and
personDaan Wierstra. year2017.
Imagination-Augmented Agents for Deep
Reinforcement Learning.
In booktitleAdvances in Neural Information
Processing Systems 30. publisherNeural Information
Processing Systems Foundation, Inc. (NIPS), pages5690–5701.

[Sarathy, Kasenberg, Goel, Sinapov, and
ScheutzSarathy et al2021]
authorpersonVasanth Sarathy, personDaniel
Kasenberg, personShivam Goel, personJivko Sinapov,
and personMatthias Scheutz. year2021.
SPOTTER: Extending Symbolic Planning Operators
through Targeted Reinforcement Learning. In
booktitleProceedings of the 20th International Conference on
Autonomous Agents and Multi-Agent Systems. pages1118–1126.

authorpersonJürgen Schmidhuber.
An on-line algorithm for dynamic reinforcement
learning and planning in reactive environments. In
booktitle1990 IJCNN international joint conference on neural
networks. IEEE, pages253–258.

[Schulman, Wolski, Dhariwal, Radford, and
KlimovSchulman et al2017]
authorpersonJohn Schulman, personFilip
Wolski, personPrafulla Dhariwal, personAlec Radford,
and personOleg Klimov. year2017.
Proximal policy optimization algorithms.
journalarXiv preprint arXiv:1707.06347

[Shalev-Shwartz et alShalev-Shwartz
et al2012]
authorpersonShai Shalev-Shwartz et al
Online learning and online convex optimization.
journalFoundations and Trends® in
Machine Learning volume4, number2
(year2012), pages107–194.

[Silver, Schrittwieser, Simonyan, Antonoglou,
Huang, Guez, Hubert, Baker, Lai, Bolton, et alSilver
et al2017]
authorpersonDavid Silver, personJulian
Schrittwieser, personKaren Simonyan, personIoannis
Antonoglou, personAja Huang, personArthur Guez,
personThomas Hubert, personLucas Baker,
personMatthew Lai, personAdrian Bolton,
et al year2017.
Mastering the game of go without human knowledge.
journalnature volume550,
number7676 (year2017), pages354–359.

[Silver, Yang, and LiSilver
et al2013]
authorpersonDaniel L Silver, personQiang
Yang, and personLianghao Li. year2013.
Lifelong machine learning systems: Beyond learning
algorithms. In booktitle2013 AAAI spring symposium

[Sutton and BartoSutton and Barto2018]
authorpersonRichard S Sutton and
personAndrew G Barto. year2018.
booktitleReinforcement learning: An introduction.
publisherMIT press.

[Vinyals, Babuschkin, Czarnecki, Mathieu,
Dudzik, Chung, Choi, Powell, Ewalds, Georgiev, et alVinyals
et al2019]
authorpersonOriol Vinyals, personIgor
Babuschkin, personWojciech M Czarnecki,
personMichaël Mathieu, personAndrew Dudzik,
personJunyoung Chung, personDavid H Choi,
personRichard Powell, personTimo Ewalds,
personPetko Georgiev, et al
Grandmaster level in StarCraft II using multi-agent
reinforcement learning.
journalNature volume575,
number7782 (year2019), pages350–354.

authorpersonLucas Willems.
titlelcswillems/torch-ac: Recurrent and multi-process
PyTorch implementation of deep reinforcement Actor-Critic algorithms A2C and

[Zhu, Lin, and ZhouZhu et al2021]
authorpersonZhuangdi Zhu, personKaixiang
Lin, and personJiayu Zhou. year2021.
titleTransfer Learning in Deep Reinforcement Learning: A
[arxiv]2009.07888 [cs.LG]

The NovGrid environments, where the agent (red triangle) must get to the goal (green box). The novelties are not directly observable; the agent must experience the novelty to be aware of it.

pre-novelty only a yellow key opens a door; post-novelty only the blue key opens the door.

pre-novelty the lava gives a -1 reward and is a terminal state; post-novelty the lava is safe to walk on.

Most realistic environments are “open-worlds,” where new and unexpected situations will likely be encountered.

Consider the following examples:
a door is re-keyed so previous keys fail to open it and a different key is required, changing the solution;
a new technology enables a vehicle to pass over previously impassible terrain, shortening the distance to a destination;
a volcano eruption suddenly changes the local climate causing native crops to fail, making it harder to feed communities.

We refer to these changes as “novelties”, previously unseen changes to the fundamental mechanics or properties of an environment <cit.>.
Novelties can dramatically alter the solution distribution for sequential decision-making tasks.

An agent—human or artificial— that fails to adapt to novelties can result in a precipitous drop in task performance if the same policies continue to be pursued.

The  architecture.
The purple module

and black arcs represent the conventional RL execution loop with loss back-propagating backward through black arcs in the purple module.
The blue module

contains rule model learning and novelty detection.
The red arcs represent information flow in a post-novelty environment, using learned rules to simulate the new environment.
Post-novelty, loss is back-propagated backward along the red arcs and black arcs within the policy model.

Fast and sample-efficient adaptation to novelties can be essential, for example when human safety is involved.
As such, humans have evolved to be good at adapting to novelties <cit.>.
By contrast, deep reinforcement learning (RL) agents, which have demonstrated super-human performance on game tasks like Go <cit.>, Atari <cit.>, and StarCraft <cit.> are particularly susceptible to failure in the face of novelty.

Novelties constitute a distributional shift in the environment dynamics.
As such novelties can be expressed as online task transfer <cit.>—during online execution the agent suddenly finds itself in an environment with new transition dynamics.
The traditional approach to transfer is to retrain from scratch in the post-novelty environment.
One can also allow the agent to continue learning post-novelty starting with the model parameters.
This, however, can be very sample-inefficient, requiring hundreds of thousands of interactions with the environment during deployment time to converge to the new optimum policy.

We propose , an efficient world model reinforcement learning system with a neural policy comprised of two novelty-focused improvements to the standard deep RL execution loop.
(1) We propose a simple, fast-updating, symbolic world model for learning a model of the transition function—how features of the environment change and can be changed over time.
Unlike neural world models which may require multiple examples of a phenomenon, our symbolic world model can be updated with a single post-novelty observation, allowing faster novelty adaptation than neural world models.

(2) We propose an imagination-based adaptation method that uses the symbolic world model to improve the efficiency of deployment-time adaptation of the policy.
After detecting novelty, the agent updates its world model and uses the updated world model to simulate environment transitions in the post-novelty world, reducing the number of real environment interactions required to update the policy.

We evaluate the sample efficiency of  in the NovGrid environment <cit.> with multiple novelty types.

We show that post-novelty adaptation with  requires fewer policy updates and environment interactions

than model-free and neural world model reinforcement learning techniques.

To summarize, our contributions are as follows:

* We present , a neuro-symbolic world model for novelty detection and adaptation.

* We define a new symbolic representation with an efficient learning algorithm and a way to use this representation to help world models adapt to novelty.

* We show that  adapts to novelties more efficiently than state-of-the-art reinforcement learners.

Novelties are defined as sudden, previously unseen changes to dataset, datastream, or environment fundamentals <cit.>.
Novelty handling can be broken down into three challenges: novelty detection, novelty characterization, and novelty adaptation.

Prior work on novelty-aware agents for sequential decision making problems include
adaptive mixed continuous-discrete planning and knowledge graphs used in combination with actor-critic reinforcement learning techniques to improve both detection and adaptation <cit.>.

Adaptation to “hidden” domain shifts <cit.> is also relevant, though not originally targeted toward novelty.

Explicit detection and characterization are not strictly necessary for novelty adaptation.
In online continuous or lifelong learning <cit.> and online learning <cit.>,

a learner makes the assumption that the world is too complex or unpredictable to learn offline, functionally treating the world as perpetually novel.
Instead of making a training-deployment distinction, these learners continuously update.
With these techniques, there may be little-to-no guarantee of convergence pre- or post-novelty.

When starting with some pre-novelty knowledge, even if the naive online learning approach results in post-novelty convergence, this could induce catastrophic inference <cit.>, causing the agent to transfer little, if any, of its previous model.
This forgetting phenomenon can make learning less efficient.

Transfer learning <cit.> seeks to overcome this limitation by transferring the model to an environment that differs in a small but non-trivial way.
While this approach has similarities to novelty adaptation, transfer learning techniques often assume that an agent can return to an offline training phase when encountering the new dataset or environment, whereas novelty adaptation must occur during deployment.

World Models in Reinforcement Learning.

Reinforcement learning can be broadly categorized as model-based and model-free <cit.>.
In model-based reinforcement learning, an agent learns a model of the transition function and uses it to formulate a policy with an iterative technique such as Monte Carlo tree search <cit.> or a dynamic programming approach such as value iteration.

In model-free reinforcement learning, a model of the policy is learned directly, without the need for a transition function, and then sampled to determine the actions of an agent.
For novelty adaptation, model-based methods may be more sample-efficient, however, they tend to be more sensitive to modeling error than model-free methods <cit.>.

World models learn both the transition function and the policy, using them together to drive agent performance <cit.>.

DreamerV2 <cit.> represents the state of the art in world model-based reinforcement learning.
In the Dreamer approach,

only the world model learns directly from interacting with the environment, while the policy is trained exclusively from interactions “imagined” by the world model <cit.>.
This builds on prior world model research that used imagination to help train standard RL models <cit.> and multi-agent models <cit.>.
DreamerV2 is more sample-efficient than most model-free reinforcement learning agents but still requires a very large model; it was not explicitly designed for novelty-handling.

No prior work uses world model based RL for novelty adaptation.

Reinforcement learning typically models environments as standard Markov decision processes (MDP): $M=\langle S, A, R, P, \gamma\rangle$,
where $S$ is the set of environment states, $A$ is the set of actions, $R: S \times A \rightarrow \mathbb{R}$ is the function mapping from states and actions to a scalar reward, $P: S \times A \rightarrow \mathbb{S}$ is the transition function between states, and $\gamma$ is the discount factor.
The injection of novelty, after an arbitrary and a priori unknown number of episodes or games $t$ constitutes a transformation from the original environment or MDP $M$ to a new environment or MDP $M'$.

All aspects of the problem except an agent's decision-making model are considered properties of the environment.
This includes agent morphology, action preconditions, and effects.

We constrain the problem in a few ways. We assume that each agent's observation space and action space remain consistent throughout.

We also assume that the agent's mission $T$, and therefore the extrinsic reward function, is consistent throughout.

As is typical in reinforcement learning we model our environment as standard Markov decision processes (MDP): $M=\langle S, A, R, P, \gamma\rangle$, where
$S$ is the set of environment states, $A$ is the set of actions, $R:S \times A \rightarrow \mathbb{R}$ is the function mapping from states and actions to a scalar reward, $P:S \times A \rightarrow \mathbb{S}$ is the transition function between states, and $\gamma$ is the discount factor.

The injection of novelty, after an arbitrary and a priori unknown number of episodes or games $t$ constitutes a transformation from the original environment or MDP $M$ to a new environment or MDP $M'$.

We consider all aspects of the problem except an agent's decision-making model to be property of the environment.
This includes agent morphology, sensors, and action preconditions and effects.

We assume that each agent's observation space and action space remain consistent before and after novelty is injected.
This means that the  number of actions and the size and shape of observations are consistent throughout each experiment, but some never occur pre-novelty.

For example a volcano eruption is always a possibility, but it could be rare enough to be a singular experience with no previous occurrence; more prosaically, using a certain key to open a certain door is always a possibility, but it could have different outcome post-novelty, if the door has been re-keyed.

We also assume that the agent's mission $T$ is consistent before and after the novelty, meaning that we do not consider changes to the extrinsic agent rewards.

is an end-to-end trainable neuro-symbolic world model comprised of two components: (1) a neural policy and (2) a symbolic world model.
The symbolic world model (which we also refer to as the “rule model”) consists of rules that, in aggregate, approximate the environment's latent transition function.
The rule model serves two core functions.
First, the rule model learns to predict state transitions pre-novelty.
Rule violations  thus indicate the introduction of novelty and the need to update the rule model and the policy.
Second, once in a post-novelty environment,  uses the rule model to simulate the environment, enabling rollouts for retraining the neural policy model so as to require fewer interactions with the real environment.
Shown in Figure <ref>, this interaction between the world model and the policy allows  to trust its policy pre-novelty, then depend more heavily on its world model post-novelty.
Our world model algorithm is designed so that the rule model is independent of the neural policy implementation, making our approach compatible with any policy framework that uses the same data inputs as the rule model.
For our implementation of , we use Proximal Policy Optimization (PPO) <cit.> on an Advantage Actor-Critic (A2C) neural architecture.

§.§ Interval-Based Symbolic World Model

In  the symbolic world model–modeling the transition function $P$–is represented as a set of $K$ rules $\{\rho_k\}$ of the form $\langle c_s, c_a, e\rangle$.
In this representation, $c_s$ is a state precondition, $c_a$ is the action precondition (similar to a do-calculus precondition ), and $e$ is an effect.

A rule $\rho$ is determined to apply if the input state $s$ and action $a$ match that rule's preconditions.

The state preconditions contain a set of values corresponding to a subset of state features $\phi_1...\phi_m$.
When both the state and action preconditions of $\{\rho\}$ are satisfied, then $\{\rho\}$ is applicable and can be executed if chosen.

Effects $e$ are the difference between the input state and the predicted state: $e=s^{'}-s$.

This formulation has similarities to logical calculus frameworks such as ADL and PDDL <cit.> by encoding preconditions and effects.
Our approach is designed to be learned, rather than engineered, similar to “game rule” learning <cit.>.

uniquely formulates preconditions as a set of axis-aligned bounding intervals (AABIs), also known as hyperrectangles or
$n$-orthotopes <cit.> in feature space that cover the training data.
AABIs are simple, $d$-dimensional convex geometries that, given a set of sample points to group $x_1...x_n$, define the minimum interval along each dimension that encloses the entire set.
Regardless of the size of the interval, AABIs can be defined by two $d$-dimensional points—a minimum and maximum bound—which makes them very efficient to query for both training and inference.

They can accommodate a mixture of continuous and categorical (non-continuous) variables, both of which are common in symbolic methods, where categorical AABI values are simply the exact set of matching values.

For example, see the bottom of Figure <ref>, which shows the AABIs for a rule for unlocking a door in the NovGrid grid world. In this case the intervals limit the action to a single agent location $(3,5)$. Figure <ref> shows another example where the action is applicable to an interval of locations.

[roundnode/.style=circle, draw=black!60, fill=gray!5, very thick, minimum size=7mm,
squarenode/.style=rectangle, draw=black!60, fill=gray!20, very thick, minimum size=5mm]

[roundnode, align=center] (state1) State $T$
[squarenode, align=center] (action) [right=of state1] UnlockDoor;
[roundnode, align=center] (state2) [right=of action]State $T+1$
(txt) [below=of action] This state transition yields the creation of the following rule:;
[->] (state1.east) – (action.west);
[->] (action.east) – (state2.west);
[->, dotted] (action.south) – (txt.north);

Preconditions:     Effect:

AgentLocation: min=(3,5), max=(3,5)     DoorState: set={locked} $\rightarrow$ DoorState: set={closed}

AgentFacing: set={East}     Inventory: set={YellowKey} $\rightarrow$ Inventory: set=None

Inventory: set={YellowKey}

DoorState: set={Locked}

DoorLocation: min=(3,6), max=(3,6)

Action Precondition:

Top shows example environmental states passed to the rule learner (changes underlined). Bottom shows the learned world model rule describing the key opening a door.

The AABIs of the preconditions do not need to be intersecting; each unique rule can have multiple disjoint intervals. Our rule update algorithm (see next section) minimizes the number of different intervals.

Multiple rules per action will exist when actions have different effects depending on the current state.
For example, in a grid world, the  action changes the agent's $\phi$

positional feature in the state along the direction the agent is facing when nothing is in the way,
but  will have no effect on the state if there is a wall directly in front of the agent.
This same functionality enables us to account for probabilistic transitions; multiple rules will have the same action and state precondition but different effect distributions.
Using the example of opening a locked door with a key, there is the possibility that a lock is “sticky” and an agent may require several tries. The effect of the rule that predicts the opening of the lock would then be a distribution over the
rules with identical preconditions but different effects.

Prior State $s_{t-1}$, Action $a_{t-1}$, NextState $s$, WorldModel rule set $P$
Applied Rule $\rho$
StateChange $\delta s = s - s_{t-1}$
$RuleHit = \texttt{False}$
Rule $\rho_k = \langle c_{s,k}, c_{a,k}, e_k\rangle$ in $P$
$a_{t-1} == c_{a,k}$
$\delta s == e_k$
$CollisionCheck(s_{t-1}, c_{s,k})$
$RuleHit \leftarrow \texttt{True}$
return $\rho$

$RuleRelaxation(\rho, s_{t-1})$
$RuleHit \leftarrow \texttt{True}$

$CollisionCheck(s_{t-1}, c_{s,k})$
$RuleCollisionResolution(\rho, s_{t-1})$

$RuleCreation(c_{s} = s_{t-1}, c_{a} = a_{t-1}, e = \delta s)$
$RuleHit \leftarrow \texttt{True}$

$RuleHit == \texttt{False}$
$RuleCreation(c_{s} = s_{t-1}, c_{a} = a_{t-1}, e = \delta s)$

Rule Model Update

§.§ Rule Learning

The rule learning process (Algorithm <ref>) constructs a compact, collision-free set of rules that provide maximum coverage of the state-action space while minimizing the complexity of the symbolic world model.
Moreover, it is an online updating process; once a rule is learned, it can be updated without knowledge of past observations.

The rule update process begins with the rule model initialized as an empty set.
After an action is taken in the environment, the rule learner receives the prior state of the environment from which to derive a precondition,
the action taken, and a new state of the environment from which to derive an effect.
Comparing the prior state, action, and new state with the state preconditions, action preconditions, and effects (respectively) of any existing rules in the model,
the update algorithm enters one of four cases:

* No Change: The prior state falls inside the state precondition AABI of an existing rule with a matching action and effect.

* Rule Creation: There is no rule where the action precondition is satisfied or the state difference matches the effect.
A new “point” rule is created that exactly describes the prior state.

* Rule Relaxation: A rule exists where the action precondition is satisfied and state difference matches the effect, but the prior state is not covered by the existing rule's state precondition AABI.
The rule is “relaxed” by expanding the AABI.

* Rule Collision Resolution: A rule exists where the action precondition and state precondition AABI are satisfied but the effect is different.

The AABI of the existing rule is split with a minimum cut (min-cut) operation.

2|c|Rule 1

Preconditions:     Effect:

AgentLocation: min=(1,1), max=(5,2)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

[roundnode/.style=circle, draw=black!60, fill=gray!5, very thick, minimum size=7mm,
squarenode/.style=rectangle, draw=black!60, fill=gray!20, very thick, minimum size=5mm]

[roundnode, align=center] (state1) State $T$
AgentLocation: min=(3,4)
WallLocation: min=(3,6);
[squarenode, align=center] (action) [right=of state1] Forward;
[roundnode, align=center] (state2) [right=of action]State $T+1$
AgentLocation: min=(3,5)
WallLocation: min=(3,6)

(Delta from $T$:
AgentLocation += 1);
(txt1) [above=of action] The existing rule is tested against the following state transition:;
(txt2) [below=of action] The state AABI of the rule is relaxed:;
[->] (state1.east) – (action.west);
[->] (action.east) – (state2.west);
[->, dotted] (txt1.south) – (action.north);
[->, dotted] (action.south) – (txt2.north);

2|c|Rule 1'

Preconditions:     Effect:

AgentLocation: min=(1,1), max=(5,4)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

Rule Relaxation example, where the blue underlined precondition AABI corresponding to the agent location has been expanded in the modified Rule 1'

to include agent location from state S.

When the agent takes an action, the rule learner observes the prior state at time $T$, the action executed, and the next state at time $T+1$.
If rules exist where the state transition satisfies the action precondition, the state precondition, or the effect, we first try to modify existing rules using Rule Relaxation and Rule Collision Resolution.
Rule Creation is only necessary if collision resolution and relaxation do not apply.
Given the agent's performed action, we initially only consider rules where the action precondition is satisfied.
We then identify whether the state prior to the action is contained in any of these existing rules' AABI.
This is achieved using the geometric hyperplane separation theorem (also called the separating axis theorem) <cit.>.
Geometrically, we can assert that for all features $\phi_d \in \Phi$, if there exists a feature for which the point is less than the min or more than the max of an interval, then a separating hyperplane exists.
The theorem states simply that if a hyperplane exists in feature space between the point and the geometric shape, there is no collision and the point is outside the AABI.
Specifically, for prior state $s_{t-1}$ and an AABI $I = [I_{min},I_{max}]$:

\begin{equation}
s_{t-1} \not\in I \iff \exists \phi~s.t.~[ s_{t-1,\phi} > I_{max,\phi}  \cup  s_{t-1,\phi} < I_{min,\phi} ].
\end{equation}

Rule Creation
is straightforward: the combination of prior state and action in an observed state-action-state transition does not fall within the AABI of any existing rule.
A new rule is added to the rule model where the AABI for continuous state features are assigned  and  values equal to their current value, and categorical state feature values are singleton members of their features.
Similarly, the rule's action precondition is set to the action in the state transition, and the effect is equal to the difference between $s_{t-1}$ and $s$.
This process is illustrated in Figure <ref>.
We describe a rule that is circumscribed to a single set of values for each feature as a“point” rule.

Rule Relaxation seeks to expand an AABI of an existing rule to match the newly encountered action precondition and effect.
The operation is simple: for the prior state $s_{t-1}$ and AABI $I$ represented by points $I_{min}$ and $I_{max}$, the relaxed min and max points are
$I^*_{min} = \texttt{min}(s_{t-1},I_{min})$ and $I^*_{max} = \texttt{max}(s_{t-1},I_{max})$.
Figure <ref> illustrates rule relaxation.
Here, a previously learned rule exists that models the change in agent position caused by a  action.

This rule matches the action precondition and effect but not the state precondition, possibly because it simply had not been observed yet in that part of the environment.

As a result, the AgentPosition AABI is expanded to include the observation.

After this expansion, the new AABI $I^*$ is checked once more, this time for collision with other existing rules, using the same geometric hyperplane separation theorem described above.
For comparing intervals, however, we check for a hyperplane between $I*$ and the AABI $I^k$ of another rule $\rho_k$ by comparing the maxima to the minima of the intervals.
Given maximum and minimum points $[I^*_{min},I^*_{max}]$ and $[I^k_{min},I^k_{max}]$,
if there exists a feature $\phi$ for which $I^*_{min} > I^k_{max}$, or vice versa, then there is no collision.
If a collision does exist, instead of trying to compromise between the two rules, we execute Rule Collision Resolution.

2|c|Rule 1

Preconditions:     Effect:

AgentLocation: min=(1,1), max=(8,8)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

[roundnode/.style=circle, draw=black!60, fill=gray!5, very thick, minimum size=7mm,
squarenode/.style=rectangle, draw=black!60, fill=gray!20, very thick, minimum size=5mm]

[roundnode, align=center] (state1) State $T$
AgentLocation: min=(3,5)
WallLocation: min=(3,6);
[squarenode, align=center] (action) [right=of state1] Forward;
[roundnode, align=center] (state2) [right=of action]State $T+1$
AgentLocation: min=(3,5)
WallLocation: min=(3,6)

(Delta from $T$: None);
(txt1) [above=of action] The existing rule is tested against the following state transition causing a collision:;
(txt2) [below=of action] The Rule is split about the AgentLocation state precondition:;
[->] (state1.east) – (action.west);
[->] (action.east) – (state2.west);
[->, dotted] (txt1.south) – (action.north);
[->, dotted] (action.south) – (txt2.north);

2|c|Split Rule 1'

Preconditions:     Effect:

AgentLocation; min=(1,1), max=(8,5)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

2|c|Split Rule 1”

Preconditions:     Effect:

AgentLocation; min=(1,6), max=(8,8)     AgentLocation += 1

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

And a new rule is created:

2|c|New Rule 2

Preconditions:     Effect:

AgentLocation; min=(3,5), max=(3,5)     None

WallLocation: min=(3,6), max=(3,6)

Action Precondition:

Rule Collision, and the resulting rule split and creation. The blue-underlined preconditions in the newly split Rule 1' and Rule 1” indicate the feature dimension along which the original Rule 1 is split. The newly created Rule 2 accounts for the state transition that caused the collision with the original Rule 1.

Rule Collision Resolution finds the min-cut partition of the existing rule's state precondition AABI.
Consider the AABI as a graph, where the graph nodes are the bounding hyperplanes (“faces” of the hyperrectangle) and the edges are lines that connect opposing hyperplanes weighted by their length.
This min-cut of the AABI is simply the division along the largest feature axis that intersects with the prior state.
The new, divided AABIs are added to the existing rule's preconditions, the original AABI is removed, and the prior state is assessed for accommodation with Rule Creation or Rule Relaxation because it may not be included in either split.

Figure <ref> illustrates a situation where the  rule is observed to not correctly predict the outcome of a state transition  because the agent hits a wall.
Because the rule describing this state transition has a precondition subsumed by the existing  rule but with a different effect, there is a rule collision.
The collision is resolved by splitting the rule.
A new point rule can be created because the prior state is now outside the AABIs of the split rules.

Post-novelty, splitting rules in Rule Collision Resolution can result in one of the split rules having a precondition with a feature with empty interval or empty categorical set.

If this occurs, the “empty split” is discarded.

§.§ Novelty Detection

Once pre-novelty neural policies converge and the symbolic world model is created as described above, learning is turned off for both; this saves compute and allows the policy to focus on exploitation.
As the agent performs tasks in the environment, it looks for state-action-state transitions that are inconsistent with the rules in the world model and triggers adaptation when one of two cases occur.

(1) The same rule is violated $n$ consecutive times.

A violation is defined as the observed subsequent state of the environment not matching a rule's expected state effect, though the state and action preconditions both match.
(2) The same observed state causes a failed prediction in more than $n$ consecutive visits.
$n$ is a hyperparameter for sensitivity to novelty, set to $n=2$ in our experiments.

Once a novelty is detected,
the neural policy and the symbolic world model begin to update online again.
The post-novelty rule update process is exactly the same as pre-novelty rule learning (Algorithm <ref>).
The rule model can thus be updated with as little as a single iteration of the rule learning algorithm, with guaranteed improved next-state prediction.

Pre-Novelty Policy $\pi$, World Model $P$, Mix Ratio $\eta$

$PostNov \leftarrow False$
$s_t \leftarrow$ initial observation

Select action $a_{t}=\pi(s_{t})$

Predict next state $\hat{s}_{t+1} = P(s_{t}, a_{t})$

Execute $a_{t}$ in $Env$ and observe
next state and reward
$s_{t+1}, r_{t}$

$PostNov \leftarrow [PostNov$ OR $DetectNovelty(P,\hat{s}_{t+1}, s_{t+1})$]

Add $\langle s_t, a_t, s_{t+1}, r_t\rangle$ to $UpdateBuffer$

$P \leftarrow RuleModelUpdate(s_t, a_t, s_{t+1})$

Add $ImagineRollouts(P)$ per $\eta$ to $UpdateBuffer$

Periodically update $\pi$ with $UpdateBuffer$

$s_t \leftarrow s_{t+1}$

Imagination-Based Adaptation

Adaptive Efficiency      Pre-novelty     Asymptotic       Update Efficiency

@0.95 (steps) $\downarrow$     Performance $\uparrow$     Performance $\uparrow$       (policy updates) $\downarrow$

5c novelty

PPO     2.25E6     0.973     0.971     2.25E6

DreamerV2     5.3E5     0.971     0.973      3.82E8

Ours     9.8E5     0.972     0.970     1.63E6

5c novelty

PPO     1.39E5     0.972     0.991     1.39E5

DreamerV2     Failed to adapt     0.965     Failed to adapt     Failed to adapt

Ours     8.3E4     0.972     0.991     1.38E5

5c novelty

PPO     2.08E6     0.992     0.971     2.08E6

DreamerV2     1.05E6     0.992     0.968     7.56E8

Ours     1.07E6     0.992     0.972     1.78E6

Novelty metric results
averaged over three runs.
DreamerV2 did not adapt to the novelty on .

§.§ Imagination-Based Policy Adaptation

Post-novelty, the newly updated rules within the symbolic world model reflect the agent's belief about the post-novelty state transition function.

The agent now uses that rule model to “imagine” how sequences of actions will play out—which we refer to as “imagination-based simulation”—and update its policy without interacting or executing actions in the true environment.

Specifically, as we show in Algorithm <ref>,
we use the rule model to simulate state-action-state transitions that then populate the agent's update buffer–the data on which the policy will be trained.
The policy training algorithm generates a loss over samples drawn from the update buffer and back-propagates loss through the policy model.
Figure <ref> shows how the standard Actor-Critic neural architecture and imagination-based simulation work together to feed real and imagined state observations.

The agent follows its policy in the imagined environment and repeatedly experiences the first rule change's consequences, receiving a reduced (or increased) expected reward, pushing the policy away from (or toward) the impacted actions.
As the symbolic world model detects new discrepancies and represents the post-novelty environment more accurately, the policy may be able to “imagine” experiencing and accommodating novelty with minimal exposure to the novelty in the environment.

Continuing the example of the re-keyed door lock (Figure <ref>, top), the agent has executed its pre-novelty policy of navigating to the yellow key and then to the yellow door only to discover that the door no longer opens.
Upon arriving at the state $\langle$AgentInFrontOfDoor,  AgentCarryingYellowKey, DoorLocked$\rangle$
and performing the action , the agent expects $DoorUnlocked$ to become true.
However, since the door has been re-keyed the  action results in no change.

When this occurs, there is a rule collision, resolved by creating a rule with a $\{\emptyset\}$ effect delta, and the old rule is “split”. In this case, the split results in states with empty AABIs, in which case the rule is deleted.

The rule collision is detected as a novelty, and the agent begins updating its policy.
Specifically, the agent no longer receives the utility of walking through the door and the policy updates to reflect reduced utility of being directly in front of the door.
Over time, the utility of the state will decrease enough that the agent will prefer other states, increasing exploration and eventually coming across the blue key.
This switch from exploitation to exploration is accelerated by the agent's ability to repeatedly imagine arriving before the door and choosing alternative actions because there is no valid rule in which the door opens.

Eventually through exploration the agent will find itself before the door with the blue key: $\langle$AgentInFrontOfDoor, AgentCarryingBlueKey, DoorLocked$\rangle$
Trying to open the door with the blue key will this time result in the effect of $DoorUnlocked$ changing to $DoorClosed$.
This, in conjunction with the  action precondition does not match any existing rule, and a new rule is created, at which point imagination will facilitate faster policy learning.

Once again having access to the utility and reward of states beyond the door, the agent will converge to a new policy involving the blue key.

To account for world model error, our policy is also trained on real environment interactions.

A mixing ratio parameter controls the ratio of imagined and real environment rollouts in the policy update buffer;
For every $t$ steps in the real environment, the agent runs $\frac{t}{\eta}$ steps in the imagined environment.

This mixing effectively adds noise to the policy update and

helps drive the policy back into an “explore” mode, where actions will be selected more randomly by the policy.

We perform experiments in the NovGrid <cit.>
environment, which extends the MiniGrid <cit.> environment with novelties that can be injected at an arbitrary time during testing.
NovGrid allows for controlled, replicable experiments with stock novelties.
We use two 8x8 MiniGrid environments:
(1)  where an agent must pick up a key, unlock a door, and navigate to the goal behind that door, and
(2)  where an agent must navigate a maze that has a pool of lava lining the side of the maze nearest to the goal.
In all cases we used the default sparse MiniGrid reward.

We tested the performance of our method on three novelty types:
shortcut, delta, and barrier <cit.>.
is a shortcut novelty that makes lava in the  environment to be harmless to the agent (where pre-novelty it destroyed the agent), offering a shorter path to the goal.

is a delta novelty that changes which of two keys unlock a door in the  environment,
not changing the difficulty of reaching the goal but requiring different state-action sequences of similar length and complexity.
is a barrier novelty and the inverse of ,
changing the effect of lava in the  to destroy the agent (where pre-novelty, lava was harmless), thereby eliminating the shorter lava path to the goal.

The  and  novelties are conceptually shown in Figure <ref>.

These plots show the adaptive performance post-novelty.
Each method experiences novelty injection at 10,000 environment steps (signified by the vertical dotted black line).
Top shows novelty response for the  “delta” novelty on the  environment.
Middle shows novelty response for the  “shortcut” novelty in the  environment. Note: Dreamer does not find the shortcut.
Bottom shows novelty response for the  “barrier” novelty in the  environment, where lava is safe for the agent pre-novelty.

To evaluate performance in these test environments, we adopt two metrics for novelty adaptation from <cit.> that builds on <cit.>.
(1) Asymptotic adaptive performance is the final performance of the agent post-novelty relative to a random baseline, where higher is better.

This is used to observe whether a method fully adapted to the post-novelty environment.
(2) Adaptive efficiency is the number of time steps in the real, post-novelty environment required to converge to asymptotic adaptive performance, where fewer steps is better.
In our work, this is achieved when the 10-step moving average method reaches $95\%$ of asymptotic adaptive performance.
We add a third measure, update efficiency, which is the number of policy updates required post-novelty to reach asymptotic adaptive performance, where–again–fewer steps is better.

We compare  post-novelty performance with two baselines.
The first is a standard reinforcement learning agent using Proximal Policy Optimization (PPO) <cit.>, the same model-free reinforcement learning approach used by the neural policy in our  method.
The second baseline is DreamerV2 <cit.>, a state-of-the-art world modeling agent that learns an end-to-end neural world model.
The agents were not given any knowledge about the novelties at training time.
All methods were allowed to train for as many as 10 million time steps to ensure convergence, and results for each method were averaged over three runs.
Novelty was injected at episode 50k, well after all agents had converged.
Since the baseline agents lack novelty detection capabilities, we keep their learning on during evaluations so that agents can react immediately after novelty is injected.

The policy architectures for all agents use a convolutional neural net feature extractor and two fully connected output networks, one to estimate the value and one to serve as the policy functions of the agent.
All hyperparameters and architectures for DreamerV2 were consistent with the original publication <cit.>,
and all PPO hyperparameters are consistent with MiniGrid-suggested hyperparameters <cit.>.
For  we use a mixing ratio of 60% real rollouts to 40% imagined rollouts.
This ratio was determined empirically by looking at the trade-off between asymptotic adaptive performance and adaptive efficiency.
At higher amounts of imagination, the agent did not recover full post-novelty performance.
The  world model uses symbolic features from MiniGrid for rule learning, including the object type, color, and position of the agent and objects, the agent orientation, the agent's inventory, and whether doors are locked, unlocked, or open.

§ RESULTS

We document the results of these evaluations in Table <ref>, with the adaptation process of our method further illustrated in Figure <ref>.
The table shows that pre-novelty, as expected, all three methods converge in all three novelty scenarios to effectively the same performance.
This means that all methods were able to find solution sequences of equal length to the goal for all environments.

For the  “delta” novelty, DreamerV2 slightly outperforms  in adaptive efficiency, while both dramatically outperform PPO.
From this result we can observe that imagination is strongly beneficial to post-novelty adaptation.
However, adaptive efficiency doesn't tell the entire story.
DreamerV2 updates its policy on imagination only, which means that for each update to the world model, DreamerV2 must update its policy using many imagination iterations.
As a result, update efficiency of DreamerV2 demands nearly two orders of magnitude more policy updates than .

For the  “shortcut” novelty,  substantially outperforms PPO in adaptive efficiency while DreamerV2 never finds the shortcut novelty.
Dreamer was trained for 2.5 million post-novelty environment steps in multiple runs with the same result.
We attribute DreamerV2's failure to the unique

way in which its policy learner

depends on the accuracy of its world model.

Unfortunately, the world model continues to predict negative consequence of the lava.
Since the longer, pre-novelty solution still reaches the goal, Dreamer's world model remains fixed, imagination never varies, and the policy never updates.
As a result, the world model can overfit easily if the policy produces the same sequence of actions every time.

PPO and  do not encounter this issue because small variations in the policy occur that cause policy updates, which allows for more sensitivity to the shortcut novelty.
However, these methods aren't perfect either; as can be seen in Figure <ref>.
It takes both methods more than 25,000 environment steps to react to the shortcut novelty injection, unlike in the barrier and delta novelties.
This demonstrates a unique challenge in shortcut novelties: when the the pre-novelty optimal path still exists, converged, non-exploring agents will struggle to detect novelty.
As noted by <cit.>, future research is needed on novelty-aware exploration techniques.

This shows the  1-step prediction error vs environment steps during rule learner training in the Empty MiniGrid Environment.

Finally, the  “barrier” novelty is similar to the
novelty, where  and DreamerV2 have very similar adaptive efficiency both outperforming PPO by a wide margin, but in all cases taking a long time to converge.
What's more, in the  and  novelty, the high variance in both DreamerV2 and  shows that in some of the trials both of these methods found the new solution very early in the adaption process, but could not consistently converge to it.
Transfer learning tells us that both of these results are expected, as the simple pre-novelty solution does not prepare the policies for the more complex post-novelty environment.

In general, our model iw able to make much more efficient use of our updates than DreamerV2.
Because DreamerV2 only trains its policy in imagination, it runs hundreds of imagination policy updates for every world model update it executes.
As shown in the last column of Table <ref>, blending the environment interaction data with the imagination data,  requires significantly fewer policy updates.

We also evaluate the efficiency and accuracy of the rule learner (results shown in Figure <ref>). After every 100 training steps we would validate the model accuracy by running a random policy for 1000 steps and measure the average 1-step predictive error of the world model.
The pre-novelty rule learner requires only about 2000 training steps before it converges to near-perfect prediction accuracy.
Grid worlds are simple, deterministic environments, so this is an unsurprising result.
The key is that it converges rapidly and is sample-efficient compared to neural world model learning techniques <cit.>.

These results show that  with only 40% imagination improves adaptation efficiency across all novelties over a neural policy with no world model.
Furthermore,  is competitive with DreamerV2 across these novelties and adapts with shortcuts that DreamerV2 fails to detect.
Most interestingly, we can see from the last column of Table <ref> that  achieves these results with fewer policy updates than PPO and DreamerV2.
This, however, will vary with the amount of imagination injected into the policy learner by , and should be the subject of further study.

This can include novelties from learning to unlock a door with a new key to discovering a new shortcut to reduce travel time or avoiding new hazards on previous safe solutions.

To this end, we show that reinforcement learning agent policies can be adapted more efficiently to novelties using symbolic world models that (1) can be updated rapidly and (2) simulate rollouts that then can be added to the policy learning process, thereby reducing the number of direct interactions with the post-novelty environment.
Specifically, our results show that  is comparable in adaptation efficiency to state-of-the-art neural world modeling techniques while requiring only a fraction of policy updates.
This suggests that symbolic representations are an effective complement to neural representations for adapting reinforcement learning agents to novelty.

For effective novelty adaptation, future techniques should consider how to leverage world models and their ability to learn models of the transition function and the policy together.

Our observations of world model-based agents adapting to novelty suggest that exploration is key to efficient novelty adaptation.
Even with access to world models, nearly all reinforcement learning agents assume that the converged pre-novelty policy can be followed greedily.
This leads to a problematic feedback loop where policies trained with imagination are only able to access what the world model knows, which may not include the novelty, but these same policies direct the interaction with the environment.
As a result, unless the novelty is along the path of the old optimal policy, the agent may never encounter the novelty, and the world model that trains it may never adapt.

New exploration techniques that operate in more plausible “open-world” environments will need to consider how to identify a novelty using the world model and how best to trade off this “novelty exploration” with following the agent's policy.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

authorpersonJoshua Alspector.
Representation Edit Distance as a Measure of
journalarXiv preprint arXiv:2111.02770

[Badia, Piot, Kapturowski, Sprechmann,
Vitvitskyi, Guo, and BlundellBadia et al2020]
authorpersonA Badia, personB Piot,
personS Kapturowski, personP Sprechmann,
personA Vitvitskyi, personD Guo, and
personC Blundell. year2020.
Agent57: Outperforming the human Atari benchmark.
In booktitleProceedings of the 37th International Conference
on Machine Learning, Online, PMLR, Vol. volume119.

[Ball et alBall
et al1997]
authorpersonKeith Ball et al
An elementary introduction to modern convex
journalFlavors of geometry volume31,
number1-58 (year1997), pages26.

[Balloch, Kim, Inman, and RiedlBalloch
et al2022a]
authorpersonJonathan C Balloch, personJulia
Kim, personJessica L Inman, and personMark O
Riedl. year2022a.
The Role of Exploration for Task Transfer in
Reinforcement Learning.
journalIROS Workshop on Lifelong Learning of
High-level Cognitive and Reasoning Skills.

[Balloch, Lin, Hussain, Srinivas, Peng, Kim,
and RiedlBalloch et al2022b]
authorpersonJonathan C Balloch, personZhiyu
Lin, personMustafa Hussain, personAarun Srinivas,
personXiangyu Peng, personJulia Kim, and
personMark Riedl. year2022b.
NovGrid: A Flexible Grid World for Evaluating Agent
Response to Novelty. In booktitleIn Proceedings of AAAI
Symposium, Designing Artificial Intelligence for Open Worlds.

[Boult, Grabowicz, Prijatelj, Stern, Holder,
Alspector, Jafarzadeh, Ahmad, Dhamija, Li, et alBoult
et al2021]
authorpersonTerrance Boult, personPrzemyslaw
Grabowicz, personDerek Prijatelj, personRoni Stern,
personLawrence Holder, personJoshua Alspector,
personMohsen M Jafarzadeh, personToqueer Ahmad,
personAkshay Dhamija, personChunchun Li,
et al year2021.
Towards a Unifying Framework for Formal Theories of
Novelty. In booktitleProceedings of the AAAI Conference on
Artificial Intelligence, Vol. volume35.

[Braun, Aertsen, Wolpert, and MehringBraun
et al2009]
authorpersonDaniel A Braun, personAd
Aertsen, personDaniel M Wolpert, and personCarsten
Mehring. year2009.
Learning optimal adaptation strategies in
unpredictable motor tasks.
journalJournal of Neuroscience
volume29, number20 (year2009),

[Chen, Luo, Ma, and ZhangChen
et al2021]
authorpersonYining Chen, personHaipeng Luo,
personTengyu Ma, and personChicheng Zhang.
titleActive Online Learning with Hidden Shifting Domains.
[arxiv]2006.14481 [cs.LG]

[Chevalier-Boisvert, Willems, and
PalChevalier-Boisvert et al2018]
authorpersonMaxime Chevalier-Boisvert,
personLucas Willems, and personSuman Pal.
titleMinimalistic Gridworld Environment for OpenAI Gym.

authorpersonHarold Scott Macdonald Coxeter.
booktitleRegular polytopes.
publisherCourier Corporation.

[Guzdial and RiedlGuzdial and Riedl2017]
authorpersonMatthew Guzdial and
personMark O. Riedl. year2017.
Game Engine Learning from Video. In
booktitleProceedings of the 2017 International Conference on
Artificial Intelligence.

<http://www.cc.gatech.edu/ riedl/pubs/ijcai17.pdf>

[Ha and SchmidhuberHa and
authorpersonDavid Ha and personJürgen
Schmidhuber. year2018.
Recurrent World Models Facilitate Policy
Evolution. In booktitleAdvances in Neural Information
Processing Systems, editorpersonS. Bengio,
personH. Wallach, personH. Larochelle,
personK. Grauman, personN. Cesa-Bianchi, and
personR. Garnett (Eds.), Vol. volume31.
publisherCurran Associates, Inc.

[Hafner, Lillicrap, Ba, and NorouziHafner
et al2019]
authorpersonDanijar Hafner, personTimothy
Lillicrap, personJimmy Ba, and personMohammad
Norouzi. year2019.
Dream to Control: Learning Behaviors by Latent
Imagination. In booktitleInternational Conference on
Learning Representations.

[Hafner, Lillicrap, Norouzi, and BaHafner
et al2021]
authorpersonDanijar Hafner, personTimothy P
Lillicrap, personMohammad Norouzi, and personJimmy
Ba. year2021.
Mastering Atari with Discrete World Models. In
booktitleInternational Conference on Learning

[Hastie, Tibshirani, Friedman, and
FriedmanHastie et al2009]
authorpersonTrevor Hastie, personRobert
Tibshirani, personJerome H Friedman, and
personJerome H Friedman. year2009.
booktitleThe elements of statistical learning: data
mining, inference, and prediction. Vol. volume2.

authorpersonElad Hazan.
Introduction to online convex optimization.
journalFoundations and Trends® in
Optimization volume2, number3-4
(year2016), pages157–325.

[Klenk, Piotrowski, Stern, Mohan, and
de KleerKlenk et al2020]
authorpersonMatthew Klenk, personWiktor
Piotrowski, personRoni Stern, personShiwali Mohan,
and personJohan de Kleer. year2020.
Model-Based Novelty Adaptation for Open-World AI.
In booktitleInternational Workshop on Principles of
Diagnosis (DX).

[Lin, Wu, Peri, Fu, Jiang, and AhnLin
et al2020]
authorpersonZhixuan Lin, personYi-Fu Wu,
personSkand Peri, personBofeng Fu,
personJindong Jiang, and personSungjin Ahn.
Improving generative imagination in object-centric
world models. In booktitleInternational Conference on
Machine Learning. PMLR, pages6140–6149.

[Loyall, Pfeffer, Niehaus, Mayer, Rizzo, Gee,
Cvijic, Manning, Skitka, Becker, et alLoyall et al2022]
authorpersonBryan Loyall, personAvi
Pfeffer, personJames Niehaus, personTyler Mayer,
personPaola Rizzo, personAlex Gee,
personSanja Cvijic, personWilliam Manning,
personMary Kate Skitka, personMcCoy Becker,
et al year2022.
An Integrated Architecture for Online Adaptation to
Novelty in Open Worlds using Probabilistic Programming and Novelty-Aware
Planning. In booktitleIn Proceedings of AAAI Symposium,
Designing Artificial Intelligence for Open Worlds.

[McCloskey and CohenMcCloskey and
authorpersonMichael McCloskey and
personNeal J Cohen. year1989.
Catastrophic interference in connectionist
networks: The sequential learning problem.
In booktitlePsychology of learning and motivation.
Vol. volume24. publisherElsevier,

authorpersonDrew McDermott.
The 1998 AI Planning Systems Competition.
journalAI Mag.  volume21
(year2000), pages35–55.

[Peng, Balloch, and RiedlPeng
et al2021]
authorpersonXiangyu Peng, personJonathan C
Balloch, and personMark O Riedl.
Detecting and Adapting to Novelty in Games. In
booktitleAAAI Workshop on Reinforcement Learning in Games.

[Pimentel, Clifton, Clifton, and
TarassenkoPimentel et al2014]
authorpersonMarco AF Pimentel, personDavid A
Clifton, personLei Clifton, and personLionel
Tarassenko. year2014.
A review of novelty detection.
journalSignal Processing  volume99
(year2014), pages215–249.

[Pretorius, Cameron, Smit, van Biljon, Francis,
Azeez, Laterre, and BeguirPretorius et al2020]
authorpersonArnu Pretorius, personScott
Cameron, personAndries Petrus Smit, personElan van
Biljon, personLawrence Francis, personFemi Azeez,
personAlexandre Laterre, and personKarim Beguir.
titleLearning to communicate through imagination with
model-based deep multi-agent reinforcement learning.

[Racanière, Weber, Reichert, Buesing, Guez,
Jimenez Rezende, Puigdomènech Badia, Vinyals, Heess, Li, Pascanu, Battaglia,
Hassabis, Silver, and WierstraRacanière et al2017]
authorpersonSébastien Racanière,
personTheophane Weber, personDavid Reichert,
personLars Buesing, personArthur Guez,
personDanilo Jimenez Rezende, personAdrià
Puigdomènech Badia, personOriol Vinyals,
personNicolas Heess, personYujia Li,
personRazvan Pascanu, personPeter Battaglia,
personDemis Hassabis, personDavid Silver, and
personDaan Wierstra. year2017.
Imagination-Augmented Agents for Deep
Reinforcement Learning.
In booktitleAdvances in Neural Information
Processing Systems 30. publisherNeural Information
Processing Systems Foundation, Inc. (NIPS), pages5690–5701.

[Sarathy, Kasenberg, Goel, Sinapov, and
ScheutzSarathy et al2021]
authorpersonVasanth Sarathy, personDaniel
Kasenberg, personShivam Goel, personJivko Sinapov,
and personMatthias Scheutz. year2021.
SPOTTER: Extending Symbolic Planning Operators
through Targeted Reinforcement Learning. In
booktitleProceedings of the 20th International Conference on
Autonomous Agents and Multi-Agent Systems. pages1118–1126.

authorpersonJürgen Schmidhuber.
An on-line algorithm for dynamic reinforcement
learning and planning in reactive environments. In
booktitle1990 IJCNN international joint conference on neural
networks. IEEE, pages253–258.

[Schulman, Wolski, Dhariwal, Radford, and
KlimovSchulman et al2017]
authorpersonJohn Schulman, personFilip
Wolski, personPrafulla Dhariwal, personAlec Radford,
and personOleg Klimov. year2017.
Proximal policy optimization algorithms.
journalarXiv preprint arXiv:1707.06347

[Shalev-Shwartz et alShalev-Shwartz
et al2012]
authorpersonShai Shalev-Shwartz et al
Online learning and online convex optimization.
journalFoundations and Trends® in
Machine Learning volume4, number2
(year2012), pages107–194.

[Silver, Schrittwieser, Simonyan, Antonoglou,
Huang, Guez, Hubert, Baker, Lai, Bolton, et alSilver
et al2017]
authorpersonDavid Silver, personJulian
Schrittwieser, personKaren Simonyan, personIoannis
Antonoglou, personAja Huang, personArthur Guez,
personThomas Hubert, personLucas Baker,
personMatthew Lai, personAdrian Bolton,
et al year2017.
Mastering the game of go without human knowledge.
journalnature volume550,
number7676 (year2017), pages354–359.

[Silver, Yang, and LiSilver
et al2013]
authorpersonDaniel L Silver, personQiang
Yang, and personLianghao Li. year2013.
Lifelong machine learning systems: Beyond learning
algorithms. In booktitle2013 AAAI spring symposium

[Sutton and BartoSutton and Barto2018]
authorpersonRichard S Sutton and
personAndrew G Barto. year2018.
booktitleReinforcement learning: An introduction.
publisherMIT press.

[Vinyals, Babuschkin, Czarnecki, Mathieu,
Dudzik, Chung, Choi, Powell, Ewalds, Georgiev, et alVinyals
et al2019]
authorpersonOriol Vinyals, personIgor
Babuschkin, personWojciech M Czarnecki,
personMichaël Mathieu, personAndrew Dudzik,
personJunyoung Chung, personDavid H Choi,
personRichard Powell, personTimo Ewalds,
personPetko Georgiev, et al
Grandmaster level in StarCraft II using multi-agent
reinforcement learning.
journalNature volume575,
number7782 (year2019), pages350–354.

authorpersonLucas Willems.
titlelcswillems/torch-ac: Recurrent and multi-process
PyTorch implementation of deep reinforcement Actor-Critic algorithms A2C and

[Zhu, Lin, and ZhouZhu et al2021]
authorpersonZhuangdi Zhu, personKaixiang
Lin, and personJiayu Zhou. year2021.
titleTransfer Learning in Deep Reinforcement Learning: A
[arxiv]2009.07888 [cs.LG]

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

authorpersonJoshua Alspector.
Representation Edit Distance as a Measure of
journalarXiv preprint arXiv:2111.02770

[Badia, Piot, Kapturowski, Sprechmann,
Vitvitskyi, Guo, and BlundellBadia et al2020]
authorpersonA Badia, personB Piot,
personS Kapturowski, personP Sprechmann,
personA Vitvitskyi, personD Guo, and
personC Blundell. year2020.
Agent57: Outperforming the human Atari benchmark.
In booktitleProceedings of the 37th International Conference
on Machine Learning, Online, PMLR, Vol. volume119.

[Ball et alBall
et al1997]
authorpersonKeith Ball et al
An elementary introduction to modern convex
journalFlavors of geometry volume31,
number1-58 (year1997), pages26.

[Balloch, Kim, Inman, and RiedlBalloch
et al2022a]
authorpersonJonathan C Balloch, personJulia
Kim, personJessica L Inman, and personMark O
Riedl. year2022a.
The Role of Exploration for Task Transfer in
Reinforcement Learning.
journalIROS Workshop on Lifelong Learning of
High-level Cognitive and Reasoning Skills.

[Balloch, Lin, Hussain, Srinivas, Peng, Kim,
and RiedlBalloch et al2022b]
authorpersonJonathan C Balloch, personZhiyu
Lin, personMustafa Hussain, personAarun Srinivas,
personXiangyu Peng, personJulia Kim, and
personMark Riedl. year2022b.
NovGrid: A Flexible Grid World for Evaluating Agent
Response to Novelty. In booktitleIn Proceedings of AAAI
Symposium, Designing Artificial Intelligence for Open Worlds.

[Boult, Grabowicz, Prijatelj, Stern, Holder,
Alspector, Jafarzadeh, Ahmad, Dhamija, Li, et alBoult
et al2021]
authorpersonTerrance Boult, personPrzemyslaw
Grabowicz, personDerek Prijatelj, personRoni Stern,
personLawrence Holder, personJoshua Alspector,
personMohsen M Jafarzadeh, personToqueer Ahmad,
personAkshay Dhamija, personChunchun Li,
et al year2021.
Towards a Unifying Framework for Formal Theories of
Novelty. In booktitleProceedings of the AAAI Conference on
Artificial Intelligence, Vol. volume35.

[Braun, Aertsen, Wolpert, and MehringBraun
et al2009]
authorpersonDaniel A Braun, personAd
Aertsen, personDaniel M Wolpert, and personCarsten
Mehring. year2009.
Learning optimal adaptation strategies in
unpredictable motor tasks.
journalJournal of Neuroscience
volume29, number20 (year2009),

[Chen, Luo, Ma, and ZhangChen
et al2021]
authorpersonYining Chen, personHaipeng Luo,
personTengyu Ma, and personChicheng Zhang.
titleActive Online Learning with Hidden Shifting Domains.
[arxiv]2006.14481 [cs.LG]

[Chevalier-Boisvert, Willems, and
PalChevalier-Boisvert et al2018]
authorpersonMaxime Chevalier-Boisvert,
personLucas Willems, and personSuman Pal.
titleMinimalistic Gridworld Environment for OpenAI Gym.

authorpersonHarold Scott Macdonald Coxeter.
booktitleRegular polytopes.
publisherCourier Corporation.

[Guzdial and RiedlGuzdial and Riedl2017]
authorpersonMatthew Guzdial and
personMark O. Riedl. year2017.
Game Engine Learning from Video. In
booktitleProceedings of the 2017 International Conference on
Artificial Intelligence.

<http://www.cc.gatech.edu/ riedl/pubs/ijcai17.pdf>

[Ha and SchmidhuberHa and
authorpersonDavid Ha and personJürgen
Schmidhuber. year2018.
Recurrent World Models Facilitate Policy
Evolution. In booktitleAdvances in Neural Information
Processing Systems, editorpersonS. Bengio,
personH. Wallach, personH. Larochelle,
personK. Grauman, personN. Cesa-Bianchi, and
personR. Garnett (Eds.), Vol. volume31.
publisherCurran Associates, Inc.

[Hafner, Lillicrap, Ba, and NorouziHafner
et al2019]
authorpersonDanijar Hafner, personTimothy
Lillicrap, personJimmy Ba, and personMohammad
Norouzi. year2019.
Dream to Control: Learning Behaviors by Latent
Imagination. In booktitleInternational Conference on
Learning Representations.

[Hafner, Lillicrap, Norouzi, and BaHafner
et al2021]
authorpersonDanijar Hafner, personTimothy P
Lillicrap, personMohammad Norouzi, and personJimmy
Ba. year2021.
Mastering Atari with Discrete World Models. In
booktitleInternational Conference on Learning

[Hastie, Tibshirani, Friedman, and
FriedmanHastie et al2009]
authorpersonTrevor Hastie, personRobert
Tibshirani, personJerome H Friedman, and
personJerome H Friedman. year2009.
booktitleThe elements of statistical learning: data
mining, inference, and prediction. Vol. volume2.

authorpersonElad Hazan.
Introduction to online convex optimization.
journalFoundations and Trends® in
Optimization volume2, number3-4
(year2016), pages157–325.

[Klenk, Piotrowski, Stern, Mohan, and
de KleerKlenk et al2020]
authorpersonMatthew Klenk, personWiktor
Piotrowski, personRoni Stern, personShiwali Mohan,
and personJohan de Kleer. year2020.
Model-Based Novelty Adaptation for Open-World AI.
In booktitleInternational Workshop on Principles of
Diagnosis (DX).

[Lin, Wu, Peri, Fu, Jiang, and AhnLin
et al2020]
authorpersonZhixuan Lin, personYi-Fu Wu,
personSkand Peri, personBofeng Fu,
personJindong Jiang, and personSungjin Ahn.
Improving generative imagination in object-centric
world models. In booktitleInternational Conference on
Machine Learning. PMLR, pages6140–6149.

[Loyall, Pfeffer, Niehaus, Mayer, Rizzo, Gee,
Cvijic, Manning, Skitka, Becker, et alLoyall et al2022]
authorpersonBryan Loyall, personAvi
Pfeffer, personJames Niehaus, personTyler Mayer,
personPaola Rizzo, personAlex Gee,
personSanja Cvijic, personWilliam Manning,
personMary Kate Skitka, personMcCoy Becker,
et al year2022.
An Integrated Architecture for Online Adaptation to
Novelty in Open Worlds using Probabilistic Programming and Novelty-Aware
Planning. In booktitleIn Proceedings of AAAI Symposium,
Designing Artificial Intelligence for Open Worlds.

[McCloskey and CohenMcCloskey and
authorpersonMichael McCloskey and
personNeal J Cohen. year1989.
Catastrophic interference in connectionist
networks: The sequential learning problem.
In booktitlePsychology of learning and motivation.
Vol. volume24. publisherElsevier,

authorpersonDrew McDermott.
The 1998 AI Planning Systems Competition.
journalAI Mag.  volume21
(year2000), pages35–55.

[Peng, Balloch, and RiedlPeng
et al2021]
authorpersonXiangyu Peng, personJonathan C
Balloch, and personMark O Riedl.
Detecting and Adapting to Novelty in Games. In
booktitleAAAI Workshop on Reinforcement Learning in Games.

[Pimentel, Clifton, Clifton, and
TarassenkoPimentel et al2014]
authorpersonMarco AF Pimentel, personDavid A
Clifton, personLei Clifton, and personLionel
Tarassenko. year2014.
A review of novelty detection.
journalSignal Processing  volume99
(year2014), pages215–249.

[Pretorius, Cameron, Smit, van Biljon, Francis,
Azeez, Laterre, and BeguirPretorius et al2020]
authorpersonArnu Pretorius, personScott
Cameron, personAndries Petrus Smit, personElan van
Biljon, personLawrence Francis, personFemi Azeez,
personAlexandre Laterre, and personKarim Beguir.
titleLearning to communicate through imagination with
model-based deep multi-agent reinforcement learning.

[Racanière, Weber, Reichert, Buesing, Guez,
Jimenez Rezende, Puigdomènech Badia, Vinyals, Heess, Li, Pascanu, Battaglia,
Hassabis, Silver, and WierstraRacanière et al2017]
authorpersonSébastien Racanière,
personTheophane Weber, personDavid Reichert,
personLars Buesing, personArthur Guez,
personDanilo Jimenez Rezende, personAdrià
Puigdomènech Badia, personOriol Vinyals,
personNicolas Heess, personYujia Li,
personRazvan Pascanu, personPeter Battaglia,
personDemis Hassabis, personDavid Silver, and
personDaan Wierstra. year2017.
Imagination-Augmented Agents for Deep
Reinforcement Learning.
In booktitleAdvances in Neural Information
Processing Systems 30. publisherNeural Information
Processing Systems Foundation, Inc. (NIPS), pages5690–5701.

[Sarathy, Kasenberg, Goel, Sinapov, and
ScheutzSarathy et al2021]
authorpersonVasanth Sarathy, personDaniel
Kasenberg, personShivam Goel, personJivko Sinapov,
and personMatthias Scheutz. year2021.
SPOTTER: Extending Symbolic Planning Operators
through Targeted Reinforcement Learning. In
booktitleProceedings of the 20th International Conference on
Autonomous Agents and Multi-Agent Systems. pages1118–1126.

authorpersonJürgen Schmidhuber.
An on-line algorithm for dynamic reinforcement
learning and planning in reactive environments. In
booktitle1990 IJCNN international joint conference on neural
networks. IEEE, pages253–258.

[Schulman, Wolski, Dhariwal, Radford, and
KlimovSchulman et al2017]
authorpersonJohn Schulman, personFilip
Wolski, personPrafulla Dhariwal, personAlec Radford,
and personOleg Klimov. year2017.
Proximal policy optimization algorithms.
journalarXiv preprint arXiv:1707.06347

[Shalev-Shwartz et alShalev-Shwartz
et al2012]
authorpersonShai Shalev-Shwartz et al