Methods and Mechanisms for Interactive Novelty Handling in Adversarial Environments

We consider $\mathcal{M}=\langle n,S,\{A_{i}\}_{i\in n},T,R,\gamma\rangle$ as the non-cooperative stochastic game environment consisting of a finite, non empty state space $\mathcal{S}$; $n$ players, $\{1,2,\cdots,n\}$; a finite set of action set $\{A_{1},A_{2},A_{3},\cdots A_{n}\}$ for each of the players; a set of conditional transition probabilities between states $T$, such that $T(s,a_{1},a_{2},\cdots,a_{n},s^{\prime})=P(s^{\prime}|s,a_{1},\cdots,a_{n})$; a reward function $R$ so that $R:\mathcal{S}\times A\rightarrow\mathbb{R}$, where $A=A_{1}\times A_{2}\times A_{3}\times\cdots\times A_{n}$. An n-person stochastic game is turn-based if at each state, there is exactly one player who determines the next state. In order to formulate the problem, we extend the action sets $A_{i}$ for $i\in\{1,2,\cdots,n\}$ to be state dependent. For each particular state $s$, there is a restricted action set $A_{ir}$, there is at most $i\in\{1,2,\cdots,n\}$ such that $|A_{ir}|>1$.

At the beginning of the game, all players start at the same initial state $s_{0}\in\mathcal{S}$. Each player independently performs an action $a_{i}^{1}\in A$ . Given $s_{0}$ and the selected actions $a_{1}=\{a_{1}^{1},a_{1}^{2},\cdots,a_{1}^{n}\}\in A$, the next state $s_{1}$ is derived based on $s_{0}$ and $a_{1}$, with a probability $P(s_{1}|s_{0},a_{1})$. Then, each player independently performs an action $a_{i}^{2}$, next state $s_{2}$ is derived based on $s_{1}$ and $a_{2}$, with a probability $P(s_{2}|s_{1},a_{2})$. The game continues in this fashion for an infinite number of steps, or until the goal is reached. Therefore, the game generates a random history $h=\{s_{0},a_{1},s_{1},a2,...\}\in H=S\times A\times S\times A...$. Based on a partial of the history $h^{\prime}=\{s_{0},a_{1},s_{1},a2,...s_{k}\}$, we can derive the conditional distribution, so-called strategy $\pi_{i}(h^{\prime})\in P(A_{i})$, with $P(A_{i})$ is the set of probability measures on $A_{i}$. A strategy set $\pi=\{\pi_{1};\pi_{2},...,\pi_{n}\}$ consists of a strategy $\pi_{i}$ for each player $i$ is used to determine the next action $a_{i}^{k+1}$. Finally, the reward function $R$ is specified based on the transition of the game, and $\gamma\in(0,1]$ is the discount factor which determines the importance of immediate and long-term future rewards.

In general, novelty refers to a change in the environment where the agent can neither apprehend the change from its own knowledge base nor from its past experience. In this paper, we want to address the challenge of detecting and accommodating interactive novelty. More specifically, interactive novelty refers to the change in agent’s actions, interactions, and relations.

• •

  Novelty Level 1 [Action]: New classes or attributes of external agent behavior.

• •

  Novelty Level 2 [Interaction]: New classes or attributes of dynamic, local properties of behaviors impacting multiple entities.

• •

  Novelty Level 3 [Relation]: New classes or attributes of static, local properties of the relationship between multiple entities.

We denote $\mathcal{C}=\{C_{1},C_{2},\cdots,C_{n}\}\in A$ as the interaction set of the agent. The set represents the agent’s capability to interact with other agents, or with the environment. The relation set $\mathcal{L}=\{L_{1},L_{2},\cdots,L_{n}\}\in H$ represents the relationship of the agent with other agents, or agent with the environment, such that the relationship is shown as a part of the history, or action sequence. Each action $a_{i}$ in the action set $A$ is defined by a preconditions set $\delta_{i}(a)$ and an effects set $\beta_{i}(a)$. A preconditions set $\delta_{i}(a)$ of an action $a_{i}$ includes all the conditions that need to be satisfied in order to execute the action. Meanwhile, the effects set $\beta_{i}$ of an action $a_{i}$ indicates the expected results after a successful execution of action $a_{i}$.

The set of interactive novelties $\mathcal{N}$ consist of all the changes that can occur in action set, interaction set, and relation set. In this scenario, action novelty refers to changes in action space, action preconditions or action effects. We denote $A^{\prime}=\{A_{1}^{\prime},A_{2}^{\prime},\cdots,A_{n}^{\prime}\}$ as the new action set, which contains all unknown actions to the agent, such that $A^{\prime}\cap A=\emptyset$, and $A^{\prime}\notin\mathcal{KB}$, where $\mathcal{KB}$ is the agent knowledge base. We assume that the preconditions $\delta^{\prime}$ and effects $\beta^{\prime}$ of the new action set $A^{\prime}$ are completely unknown to the agent, and both must be discovered through agent’s interactions. Similarly, we can present the new interaction set as $\mathcal{C}^{\prime}$, and relation set $\mathcal{L}^{\prime}$, then formulate interaction novelty and relation novelty accordingly.

The integrated architecture allows us to map all the essential information in section 3.1 of the environment to the knowledge base, $\mathcal{KB}$. Based on the information, we can construct the strategy $\pi$ using the truncated-rollout MTCS solver. However, because interactive novelties may occur throughout the course of the game, the plan must be adjusted in order to accommodate new actions, interactions, or relations.

As described in Section 3.1, the pre-novelty environment is represented as a non-cooperative stochastic turn-based game:

In order to detect and accommodate interactive novelties, we define a detection function $d(s,a,s^{\prime})$ to determine if there is any unexpected change in the environment after the agent selects an action $a$ in state $s$ and observes the next state $s^{\prime}$, or if the agent performed a new action. In addition, an identification function $\iota(s,a,s^{\prime})$ characterizes the cause of the change based on logical reasoning. The purpose of these functions is to represent the new environment after novelty (post-novelty) $\mathcal{M}^{\prime}$, such that

Monopoly is a multi-player adversarial board game where all players start at the same position. The game can support up to 4 players, described in Figure 1. All players roll dice to move across the board. The ultimate goal of the game is to be the last player standing after bankrupting other players. This objective can be achieved by buying properties, and railroads, monopolizing color sets, and developing houses on properties. If one player lands on a property owned by another player, they get charged rent or a fee. After monopolizing color sets and developing houses and hotels, players can charge higher fees when other players land on their properties. The game includes different surprise factors such as chance cards, community cards, jail, auction, and trading ability between agents. These elements can completely change the game. Hence, any action in the game needs to be adapted to dice rolls, community cards, chance cards, and the decisions of other players. These game characteristics make it more challenging for integrated planning and execution. In the game simulator, novelties can be injected on top of the standard game to study how the agent detects and accommodates these changes Haliem et al. (2021). The third-party team that ran the evaluation developed the Open-World Monopoly environment. Unlike traditional Monopoly, where we can fully observe all the states and actions of other agents, the Open-world Monopoly does not allow us to monitor all the actions and interactions on our turn Kejriwal and Thomas (2021). So, the environment is partially observable.

We implement three different categories of interactive novelty discussed in Novelty Characterization section into a classic Monopoly game. Some theoretical examples of novelty are described as below:

• •

  Action Novelty: This class of novelty can be illustrated through a stay-in-jail action. For this novelty, the player could stay in jail as long as they want. However, the player must pay a certain fee to the bank each time they receive rent (when the player decides to stay in jail by their own choice voluntarily).

• •

  Interaction Novelty: We illustrate the relation novelty through a loan interaction between two agents. For example, a player could send a loan request to another player and pay the loan back over a specific amount of time that both parties agree.

• •

  Relation Novelty: We illustrate the relation novelty through a relation property, where we enforce a relation of homogeneity between properties in a specific monopolized color group (one color group). The player must homogeneously improve a monopolized set of properties in a given move. For example, imagine the player has 3 orange properties (a monopolized set). In the default game, you could set up a house on the first property, and leave the second one unimproved. For this novelty, in the move, if you improve the first property, you must also improve the second and third so that the properties are ’homogeneously’ improved at the end of the move. Failure to do this will lead to the improvement being revoked at the end of the move.

We record the information of the game as provided by the game environment and compare it with our “expectation” state of the game board. This “expectation” state is derived from the agent’s knowledge base of the game, including expected states, actions, action preconditions, and end effects. Then, the game environment provides us with the actual game board states and actions that have occurred between the current time step and the previous time our agent performed an action (e.g., after our agent lands on a property and buys it, all other agents get to act in order until it is our agent’s turn again). When we notice a discrepancy between our expected state and the actual state, we surmise that something must have changed within the game, i.e., a novelty may have been introduced, which makes some aspects of our domain representation incorrect. Such unpredicted changes require the agent to update its knowledge base accordingly (e.g., a new action is added to the action space of Monopoly). An example of the novelty-handling component is shown in Algorithm 1. The evaluation is run in a tournament setup (many games in a tournament), discussed in section 6. Therefore, when the agent detects a novelty from the current game, this novelty information will be used to adapt to the next game.

Next, the agent uses a novelty identification module to characterize the novelty. This module has several sub-modules (which can be run in parallel), each focused on determining a specific novelty type. Each novelty identification sub-module uses the same ASP code (except for two changes) that is used for hypothetical reasoning about the effect of an action. The first change is that, a particular parameter, which is the focus of that specific sub-module, which was originally a fact, is now replaced by “choice” rules of ASP that enumerate different values that the parameter can take. The second change is that constraints are added to remove possible answer sets where the predicted game board state does not match the observed game board state. The resulting program’s answer sets give us the parameter values which reconcile the predicted game board state and the observed game board state. If there is only one answer set and thus a unique parameter value, then if this value is different from the value we had earlier, we have identified a novelty. Now we can update our ASP code that was used for hypothetical reasoning by simply replacing the earlier value of the parameter with the new value.

Below we first give a glimpse of how ASP can be used for reasoning about the next state and how that code can be minimally modified to infer a novelty.

To reason about the next state, the ASP code will first define the game parameters through facts such as the following:

dice_value(1..6).
player(player1;player2).
cash(1..1000).
asset("B&O_Railroad").
penalty(50).

Then rules of the following form are used to define actions and fluents.

action(sell_property(P,X)) :- player(P), asset(X).
fluent(asset_owned(P,V)) :- player(P), asset(V).

Properties of actions, such as their pre-conditions, and their effects are defined using rules of the following kind:

%Executability of selling assets
:- occurs(sell_property(P,V), T), player(P),
   asset(V), time(T), not holds(asset_owned(P,V),T).

%Effect of selling assets
not_holds(asset_owned(P,V),T+1) :-
              holds(asset_owned(P,V),T),
              occurs(sell_property(P,V),T),
              player(P), asset(V),time(T).
not_holds(asset_mortgaged(P,V),T+1) :-
              holds(asset_owned(P,V),T),
              occurs(sell_property(P,V), T),
              player(P), asset(V), time(T).

holds(current_cash(P,X+Y),T+1) :-
       holds(current_cash(P,X),T),
       occurs(sell_property(P,V),T),
       not holds(asset_mortgaged(P,V),T),
       asset_price(V,Y), player(P), asset(V), time(T).

not_holds(current_cash(P,X),T+1) :-
       holds(current_cash(P,X),T),
       occurs(sell_property(P,V),T),
        not holds(asset_mortgaged(P,V),T),
       asset_price(V,Y), player(P), asset(V), time(T).

holds(current_cash(P,X+Y),T+1) :-
        holds(current_cash(P,X),T),
        occurs(sell_property(P,V),T),
        holds(asset_mortgaged(P,V),T),
        asset_m_price(V,Y), player(P), asset(V), time(T).

not_holds(current_cash(P,X),T+1) :-
         holds(current_cash(P,X),T),
         occurs(sell_property(P,V),T),
         holds(asset_mortgaged(P,V),T),
        asset_m_price(V,Y), player(P), asset(V), time(T).

%Executability of paying jail fine
:- occurs(pay_jail_fine(P), T), player(P), time(T),
   not holds(in_jail(P), T).
:- occurs(pay_jail_fine(P), T), player(P), time(T),
   not holds(current_cash(P, _), T).
:- occurs(pay_jail_fine(P), T), player(P), time(T),
   holds(current_cash(P,X),T), X < 50.

%Effect of paying jail fine
not_holds(in_jail(P), T+1) :- holds(in_jail(P), T),
              occurs(pay_jail_fine(P), T),
              player(P), time(T).
not_holds(current_cash(P, X), T+1) :-
  holds(current_cash(P,X),T), holds(in_jail(P), T),
  occurs(pay_jail_fine(P), T), player(P), time(T).
holds(current_cash(P, X-50), T+1) :-
  holds(current_cash(P,X),T), holds(in_jail(P), T),
  occurs(pay_jail_fine(P), T), player(P), time(T).

The inertia rules are expressed as follows:

holds(F,T+1) :-  fluent(F), holds(F,T),
                 not not_holds(F,T+1), time(T).
not_holds(F,T+1) :-  fluent(F), not_holds(F,T),
                 not holds(F,T+1), time(T).

The initial state is defined using holds facts with respect to time step 0, such as:

holds(in_jail(player1), 0).
holds(current_cash(player1,500),0).

An action occurrence at time step 0 is then defined as a fact in the following form.

occurs(pay_jail_fine(player1),0).

Now when a complete ASP program with rules and facts of the above kind is run, we get an answer set from which we can determine the state of the world at time step 1.

Suppose that the answer set has the facts:

holds(in_jail(player1), 0).
occurs(pay_jail_fine(player1),0).
holds(current_cash(player1,500),0).
holds(current_cash(player1,450),1).

while our next observation gives us:

obs(current_cash(player1,477),1).

The discrepancy between our prediction about player1’s current_cash being 500 (at time step 1) is different from our observation that player1’s current_cash is 477. This suggests there is a novelty. This can be determined by the following two simple rules.

discrepancy(F,T) :- fluent(F), time(T),
                    holds(F,T), not observed(F,T).
discrepancy(F,T) :- fluent(F), time(T),
                    not holds(F,T), observed(F,T).

While the above could have been implemented in any language, including in the simulator language, which we also implemented in Python, having it in ASP, makes it easier for us to take the next step, which is to find out what the novelty is.

In ASP, we have to modify the above ASP code by adding the following and removing “penalty(50)” (referring to the jail fine in the Monopoly game) from the original code.

oneto200(1..500).
1 { penalty(X) : oneto200(X)} 1.  %choice rule
:- obs(current_cash(P,X),1),
   holds(current_cash(P,Y),1), X!=Y, player(P).

In the above, the first fact and the choice rule defines the range of penalty that we are exploring. If we had just those two rules, we will multiple answer sets with a penalty ranging from 1 to 500. The constraint (the last ASP rule) then eliminates all the answer sets where the observation about current_cash does not match with the holds. In the answer set that remains, we get the penalty value that would make the observation match with the holds, thus allowing us to figure out the novelty with respect to the penalty. In this particular case, the program will have the answer set with ”penalty(23)” thus characterizing the novelty that the penalty is now 23.

Since novelties in the state (features, dynamics, actions) mean the agent would have to replan often and would have to do so based on the most updated information, we were interested in developing an online planning algorithm to determine the best action. However, with environments that are both long-horizon and stochastic, using online planning approaches like Monte-Carlo tree search, quickly becomes intractable. To address this problem, we formulate a truncated-rollout-based algorithm that uses updated domain dynamics (learned from detected novelties) for a few steps of the rollout and then uses a state evaluation function to approximate the return for the rest of that rollout. In our evaluation function, we use both domain-specific components and a more general heuristic to approximate the return from the state after the truncated rollout. Furthermore, to ensure the agent adapts to the detected novelties, we made both the environment simulator used for rollouts and the evaluation function sufficiently flexible and conditioned on the environment attributes; we only used a few tuned constants. Thus, whenever a novelty was detected, we updated the relevant attributes in our simulator and evaluation function before running our algorithm to decide our actions. Using this approach, we are able to incorporate novel information into our decision-making process and adapt efficiently. An example of the whole process is shown in Algorithm 2.

We will now provide a detailed description of the rollout algorithm and the evaluation function. In our algorithm, when choosing the next best action in a given state, we execute multiple rollouts for each possible action and compute the mean return value for each action. Each rollout is terminated either when some terminal state is reached or when some $k$ number of actions have been taken. The rollouts use the updated domain dynamics of the environment. Due to potentially high branching factor, we keep these rollouts to be short (which also limits the effects of errors in our characterization of any novelties).

However, to infer some approximation of the long-term value of an action, we use an evaluation function. Our evaluation function consists of two components: one that is domain-specific and the other that is heuristic-based and can be applied to any domain in general. The heuristic component of the evaluation function involves relaxing the domain and performing another rollout on the relaxed domain for some depth $l$. Some examples of relaxations include limiting adversarial agents’ actions and determination of domain dynamics. For instance, in the case of the Monopoly domain, we prevent the agent from taking any buying or trading actions. On the other hand, the domain-specific component of the evaluation function computes the value of the state as the sum of two terms: $\mathcal{M}_{\text{assets}}$ and $\mathcal{M}_{\text{monopoly}}$ where $\mathcal{M}_{\text{assets}}$ is the value of all the assets the agent owns, whereas $\mathcal{M}_{\text{monopoly}}$ computes the maximum rent that the agent would get if it gains a Monopoly over any color, scaled down by how far the agent is to get the monopoly.

In an effort to maintain the integrity of the evaluation, all the information about the novelty was hidden from our team, and all the information about our architecture or methodologies was also hidden from the evaluation team. The external evaluations were performed by a third-party team that originally created the Open-world Monopoly domain. Our agent was evaluated on the three interactive novelties: action, interaction, and relation. For each type of interactive novelties, more than 20 different novelties were introduced during the evaluation process. Each novelty level also has three difficulty levels (shown in Table 2). The difficulty levels expressed the difficulty of detecting and using the novelty. For instance, if the novelty involved an action, an easy difficulty means the action was available for the agent to perform without any preconditions. A medium difficulty means the actions can be detected by observing other agents. A hard difficulty means the agent can only act under specific circumstances, and it may require the agent to explore the environment to learn the action. There were more than 60 novelties in which the agent was evaluated in total. At least 600 tournaments (100 games per tournament) were run to measure our agent’s performance. Tournaments were started with a traditional Monopoly game (no novelty). At a certain point throughout the tournament (non-specific, e.g., on the $5^{th}$ game), a novelty was introduced. To avoid ambiguity between novelties, only one specific novelty at a time was injected into a tournament. In our internal evaluation, ASP performed excellently in novelty detection and characterization. However, due to the characteristics of ASP, the novelty-handling component run time can be very high. Moreover, due to the nature of the game Monopoly (the game can go on indefinitely), and limited computational resources, we decided to use Python to overload the requirements of our solver and leverage the access to the simulator instead of using ASP to the first model and subsequently detect for novelties, to optimize the run time for the external evaluation.

Our agent was evaluated based on four different metrics. M1 is the percent of correctly detected trials (CDT). In this case, the percent of CDT is the percent of trails that have at least one True Positive and no False Positives (FP). M2 is the percent FP (the agent reports novelty when no novelty exists). M3 is the novelty reaction performance (NRP) before the novelty was introduced (pre-novelty). M4 is the novelty reaction performance (NRP) after the novelty was introduced (post-novelty). To measure the NRP, our agent was evaluated against a heuristic agent which embedded some of the most common strategies in Monopoly (e.g., target some specific color, never buy some properties, always reserve money, etc.). Finally, we compute the novelty reaction performance (NRP) of the agent based on the following formula:

Where, $\mathcal{W}_{agent}$ is the win rate of our agent (pre-novelty for M3, and post-novelty for M4). $\mathcal{W}_{baseline}$ is $65\%$.

The results suggest that our cognitive architecture provides outstanding solutions for the game regardless of the complexity of the environment and differing levels of novelty. Furthermore, our agent achieved a perfect precision score ($100\%$ in percent of CDT and $0\%$ of FP) at all difficulty levels of action and interaction novelties. The agent achieved a nearly perfect precision score in relation novelties. However, the agent missed $20\%$ of the novelties in the hard level of difficulty. These failures to detect certain novelties happened due to the nature of the relation novelty category: we can only detect these novelties types when a specific action is executed. Due to the stochasticity of the Monopoly game, the agent would sometimes not perform a specific action throughout the entire evaluation. To identify a relation novelty, the agent may need to perform a particular action at a specific state to reveal the novelty. For example, in the relation property novelty scenario (discussed in section 4.2), this novelty only occurs when we monopolize a green color group (one of the most challenging color groups to monopolize due to the cost of each property). The agent may then fail to detect the novelty because the agent would never monopolize the green color group throughout testing. The M3 and M4 NRP scores in all novelty levels show that our agent outperformed the baseline agent before and after when novelties were introduced. The scores in Table 1 indicate that our cognitive architecture and accommodation strategies allow the planning agent to handle interactive novelties perfectly.