# A Direct Approximation of AIXI Using Logical State Abstractions

Samuel Yang-Zhao
Australian National University
Canberra ACT 2601
<EMAIL_ADDRESS>
Tianyu Wang11footnotemark: 1
Australian National University
Canberra ACT 2601
<EMAIL_ADDRESS>
Kee Siong Ng
Australian National University
Canberra ACT 2601
<EMAIL_ADDRESS>Equal contribution.Corresponding author.

###### Abstract

We propose a practical integration of logical state abstraction with AIXI, a
Bayesian optimality notion for reinforcement learning agents, to significantly
expand the model class that AIXI agents can be approximated over to complex
history-dependent and structured environments. The state representation and
reasoning framework is based on higher-order logic, which can be used to
define and enumerate complex features on non-Markovian and structured
environments. We address the problem of selecting the right subset of features
to form state abstractions by adapting the $\Phi$-MDP optimisation criterion
from state abstraction theory. Exact Bayesian model learning is then achieved
using a suitable generalisation of Context Tree Weighting over abstract state
sequences. The resultant architecture can be integrated with different
planning algorithms. Experimental results on controlling epidemics on large-
scale contact networks validates the agent’s performance.

##  1 Introduction

The AIXI agent [1] is a mathematical solution to the general reinforcement
learning problem that combines Solomonoff induction [2] with sequential
decision theory. At time $t$, after observing the observation-reward sequence
$or_{1:t-1}$ and performing previous actions $a_{1:t-1}$ the AIXI agent
chooses action $a_{t}$ given by

$\displaystyle
a_{t}=\arg\max_{a_{t}}\sum_{or_{t}}\ldots\max_{a_{t+m}}\sum_{or_{t+m}}[r_{t}+\ldots+r_{t+m}]\sum_{q:U(q,a_{1:t+m})=or_{1:t+m}}2^{-l(q)},$
(1)

where $U$ is a universal Turing machine, $U(q,a_{1:n})$ is the output of $U$
given program $q$ and input $a_{1:n}$, $m\in\mathbb{N}$ is the lookahead
horizon, and $l(q)$ is the length of $q$ in bits. [1] shows that AIXI’s
environment model converges rapidly to the true environment and its policy is
pareto optimal and self-optimising.

While mathematically elegant, a fundamental issue with AIXI is that it is only
asymptotically computable. The question of whether a good practical
approximation of AIXI can be constructed remains an open problem twenty years
after AIXI was first introduced [3]. The most direct approximation of AIXI
given so far is [4], in which the Bayesian mixture over all Turing machines is
approximated over $n$-Markov environments using Context Tree Weighting [5] and
the expectimax search is approximated using $\rho$UCT, a Monte Carlo planning
algorithm [6]. This paper extends [4] in several ways. To move beyond
$n$-Markov environments and make it easy to incorporate background knowledge,
we adopt a formal knowledge representation and reasoning framework based on
higher-order logic to allow complex features to be defined on non-Markovian,
structured environments. The Feature Reinforcement Learning framework [7] is
adapted to define an optimisation problem for selecting the best state
abstractions and we present an algorithm based on Binary Decision Diagrams to
constrain the set of solutions. Generalizing binarised CTW [8] to incorporate
complex features in its context then allows a Bayesian mixture to be computed
over a much larger model class. Combined with $\rho$UCT, the resulting agent
is the richest, direct approximation of AIXI known to date. The practicality
of the resultant agent is shown on epidemic control on non-trivial contact
networks.

##  2 Background and Related Work

###  2.1 The General Reinforcement Learning Setting

We consider finite action, observation and reward spaces denoted by
$\mathcal{A},\mathcal{O},\mathcal{R}$ respectively. The agent interacts with
the environment in cycles: at any time, the agent chooses an action from
$\mathcal{A}$ and the environment returns an observation and reward from
$\mathcal{O}$ and $\mathcal{R}$. Frequently we will be considering
observations and rewards together, and will denote
$x\in\mathcal{O}\times\mathcal{R}$ as a percept $x$ from the percept space
$\mathcal{O}\times\mathcal{R}$. We will denote a string $x_{1}x_{2}\ldots
x_{n}$ of length $n$ by $x_{1:n}$ and its length $n-1$ prefix as $x_{<n}$. An
action, observation and reward from the same time step will be denoted
$aor_{t}$. After interacting for $n$ cycles, the interaction string
$a_{1}o_{1}r_{1}\ldots a_{n}o_{n}r_{n}$ (denoted $aor_{1:n}$ from here on) is
generated. A history $h$ is an element of the history space
$\mathcal{H}\coloneqq(\mathcal{A}\times\mathcal{O}\times\mathcal{R})^{*}$. An
environment $\rho$ is a sequence of probability distributions
$\\{\rho_{0},\rho_{1},\rho_{2},\ldots\\}$, where
$\rho_{n}:\mathcal{A}^{n}\to\mathcal{D}((\mathcal{O}\times\mathcal{R})^{n})$,
that satisfies $\forall a_{1:n}~{}\forall
or_{<n}\;\rho_{n-1}(or_{<n}|a_{<n})=\sum_{or\in\mathcal{O}\times\mathcal{R}}\rho_{n}(or_{1:n}|a_{1:n})$.
We will drop the subscript on $\rho_{n}$ when the context is clear. The
predictive probability of the next percept given history and a current action
is given by
$\rho(or_{n}|aor_{<n},a_{n})=\rho(or_{n}|h_{n-1}a_{n})\coloneqq\frac{\rho(or_{1:n}|a_{1:n})}{\rho(or_{<n}|a_{<n})}$
for all $aor_{1:n}$ such that $\rho(or_{<n}|a_{<n})>0$.

The general reinforcement learning problem is for the agent to learn a policy
$\pi:\mathcal{H}\to\mathcal{D}(A)$ mapping histories to a distribution on
possible actions that will allow it to maximise its future expected reward. In
this paper, we consider the future expected reward up to a finite horizon
$m\in\mathbb{N}$. Given a history $h$ and a policy $\pi$ the value function
with respect to the environment $\rho$ is given by
$V_{\rho}^{\pi}(h_{t})\coloneqq\mathbb{E}_{\rho}^{\pi}\left[\sum_{i=t+1}^{t+m}R_{i}\big{|}h_{t}\right]$,
where $R_{i}$ denotes the random variable distributed according to $\rho$ for
the reward at time $i$. The action value function is defined similarly as
$V_{\rho}^{\pi}(h_{t},a_{t+1})\coloneqq\mathbb{E}_{\rho}^{\pi}\left[\sum_{i=t+1}^{t+m}R_{i}\big{|}h_{t},a_{t+1}\right]$.
The agent’s goal is to learn the optimal policy $\pi^{*}$, which is the policy
that results in the value function with the maximum reward for any given
history.

###  2.2 AIXI agent and its Monte-Carlo approximation

The following equation can be shown to be formally equivalent to Equation (1).
At time $t$, the AIXI agent chooses action $a^{*}_{t}$ according to

$\displaystyle
a^{*}_{t}=\arg\max_{a_{t}}\sum_{or_{t}}\ldots\max_{a_{t+m}}\sum_{or_{t+m}}[r_{t}+\ldots
r_{t+m}]\sum_{\rho\in\mathcal{M}_{U}}2^{-K(\rho)}\rho(or_{1:{t+m}}|a_{1:t+m}),$
(2)

where $m\in\mathbb{N}$ is a finite lookahead horizon, $\mathcal{M}_{U}$ is the
set of all enumerable chronological semimeasures [1],
$\rho(or_{1:{t+m}}|a_{1:t+m})$ is the probability of observing $or_{1:t+m}$
given the action sequence $a_{1:t+m}$, and $K(\rho)$ denotes the Kolmogorov
complexity [9] of $\rho$.

The Bayesian mixture
$\xi_{U}:=\sum_{\rho\in\mathcal{M}_{U}}2^{-K(\rho)}\rho(or_{1:t}|a_{1:t})$ in
(2) is a mixture environment model, with $2^{-K(\rho)}$ as the prior for
$\rho$. A mixture environment model enjoys the property that it converges
rapidly to the true environment if there exists a ‘good’ model in the model
class.

######  Theorem 1.

[1] Let $\mu$ be the true environment and $\xi$ be the mixture environment
model over a model class $\mathcal{M}$. For all $n\in\mathbb{N}$ and for all
$a_{1:n}$,

$\displaystyle\sum_{k=1}^{n}\sum_{or_{1:k}}\mu(or_{<k}|a_{<k})\left(\mu(or_{k}|aor_{<k}a_{k})-\xi(or_{k}|aor_{<k}a_{k})\right)^{2}\leq\min_{\rho\in\mathcal{M}}\left\\{\ln\frac{1}{w^{\rho}_{0}}+D_{n}(\mu||\rho)\right\\}$
(3)

where $D_{n}(\mu||\rho)$ is the KL divergence of $\mu(\cdot|a_{1:n})$ and
$\rho(\cdot|a_{1:n})$.

To see the rapid convergence of $\xi$ to $\mu$, take the limit $n\to\infty$ on
the l.h.s of (3) and observe that in the case where
$\min_{\rho\in\mathcal{M}}\sup_{n}D_{n}(\mu||\rho)$ is bounded, the l.h.s. can
only be finite if $\xi(or_{k}|aor_{<k}a_{k})$ converges sufficiently fast to
$\mu(or_{k}|aor_{<k}a_{k})$. From Theorem 1, it can be shown that AIXI’s
environment mixture model $\xi_{U}$ also enjoys this property with any
computable environment.

The first practical approximation of AIXI is given in [4], in which the
expectimax search is approximated using Monte Carlo Tree Search [6] and
Bayesian mixture learning is performed using Context Tree Weighting (CTW) [5].
There is a body of work on extending the Bayesian mixture learning to larger
classes of history-based models [10, 11, 12, 13]. In this paper, we generalise
the Bayesian mixture learning in an orthogonal direction by adapting binarised
CTW [8] to run on sequences defined by logical state abstractions, thus
significantly improving the ease with which symbolic and statistical
background knowledge can be incorporated into the AIXI framework.

###  2.3 State Abstraction and Feature Reinforcement Learning

In the general reinforcement learning setting, the state abstraction framework
is concerned with finding a function $\phi:\mathcal{H}\to\mathcal{S}_{\phi}$
that maps every history string to an element of an abstract state space
$\mathcal{S}_{\phi}$. Given a state abstraction $\phi$, the abstract
environment is a process that generates a state $s^{\prime}$ and a reward $r$
given a history and action according to the distribution
$\rho_{\phi}(s^{\prime},r|h,a)\coloneqq\sum_{o:\phi(haor)=s^{\prime}}\rho(or|ha)$.
The interaction sequence of the original process converts to a state-action-
reward sequence under $\phi$.

A key reason for considering abstractions is that the space $\mathcal{H}$ is
too large and the underlying process may be highly irregular and difficult to
learn on. The aim is thus to select a mapping $\phi$ such that the induced
process can facilitate learning without severely compromising performance.
Theoretical approaches to this question have typically focused on providing
conditions that minimise the error in the action-value function between the
abstract and original process [14, 15]. The $\Phi$MDP framework instead
provides an optimisation criteria for ranking candidate mappings $\phi$ based
on how well the state-action-reward sequence generated by $\phi$ can be
modelled as an MDP whilst being predictive of the rewards [7]. A good $\phi$
results in a Markovian model where the state is a sufficient statistic of the
history and thus facilitates reinforcement learning.

Optimisation Criteria for Selecting Mappings. The $\Phi$MDP framework ranks
candidate state abstractions based on an optimisation criteria defined over
the code length of the state-reward sequence. Let $CL(x_{1:n})$ denote the
code length of a sequence $x_{1:n}$ and $CL(x_{1:n}|a_{1:n})$ denote the code
length of sequence $x_{1:n}$ conditioned on $a_{1:n}$. At time $n$, the
$Cost_{M}$ objective is defined as

$\displaystyle Cost_{M}(n,\phi)\coloneqq
CL(s_{1:n}|a_{1:n})+CL(r_{1:n}|s_{1:n},a_{1:n})+CL(\phi)$ (4)

where $\phi(h_{t})=s_{t}$ and $h_{t}=aor_{1:t}$. For more details on how MDP
sequences can be coded see [7].

The objective is then to look for
$\phi^{best}_{n}\coloneqq\arg\min_{\phi}Cost_{M}(n,\phi)$. Note that
$CL(\phi)$ is a term that imposes a Occam’s razor-like penalty on the
candidate mapping; if different candidate abstractions result in the same
$Cost_{M}$ value, the simplest model is preferred.

For the agent to achieve high expected long-term reward, it is imperative that
a state abstraction produces a model that can predict the reward sequence
well. However, the equal weighting given to the code lengths of the state
sequence in $Cost_{M}$ can be suboptimal; in fact a simple environment can be
constructed where $Cost_{M}$ gives unintuitive results (see Appendix F). Given
that $CL(s_{1:n}|a_{1:n})$ is optimised independent of any reward signal it
does not inherently provide any information about the long-term reward. Thus,
it is best thought of as a regularisation term to make the resulting MDP
easier to learn. We drop the code length of the state sequence from the
optimisation criteria to focus purely on reward predictability and hence
consider $Cost_{M}^{0}(n,\phi)=CL(r_{1:n}|s_{1:n},a_{1:n})+CL(\phi)$.

###  2.4 Knowledge Representation and Reasoning Formalism

The formal agent knowledge representation and reasoning language is the one
described in [16, 17]. The syntax of the language are the terms of the
$\lambda$-calculus [18], extended with type polymorphism to increase its
expressiveness. The inference engine has two interacting components: an
equational-reasoning engine and a tableau theorem prover [19]. Thus, a
predicate evaluation at the internal node of a Context Tree takes the general
form $\Gamma\vdash p(h)$, where $\Gamma$ is a theory consisting of equations
and implications that reflects the agent’s current belief base, $h$ is the
history of agent-environment interacts, and $p$ is a predicate mapping
histories to boolean values. There is also a predicate rewrite system for
defining and enumerating a set of predicates.

Suitable alternatives to our logical formalism are studied in the Statistical
Relational Artificial Intelligence literature [20, 21], including a few that
caters specifically for relational reinforcement learning [22, 23] and
Symbolic MDP/POMDPs [24, 25]. Our choice is informed by the standard arguments
given in [26, 27] and the practical convenience of working with (the
functional subset of) a language like Python. Our thesis that formal logic can
be used to incorporate domain knowledge and broaden the model class of AIXI
approximations remains unchanged with an alternate formal logic.

##  3 The $\Phi$-AIXI-CTW Agent

We now present the $\Phi$-AIXI-CTW agent. The actions and rewards are
considered in their binary representation. The agent has access to a large set
$\mathcal{P}$ of predicates on histories, and each subset of $\mathcal{P}$
constitutes a candidate state abstraction. We show that a $\Phi$-BCTW data
structure performs a Bayesian mixture over all abstractions defined by
$\mathcal{P}$ and will optimise $Cost_{M}^{0}$. However, this is
computationally infeasible in practice if $\mathcal{P}$ is large. We first
reduce this computational burden by performing feature selection to shrink the
set of predicates for $\Phi$-BCTW. Finally, the agent selects actions
according to the $\rho$UCT algorithm.

###  3.1 Shrinking the Model Class via Feature Selection

Our method for selecting candidate state abstractions is centred around the
detection of predicate features that result in low entropy conditional reward
distributions since lower entropy results in smaller code lengths and lower
$Cost_{M}^{0}$. A simple heuristic that we employ is to look for candidate
state abstractions that contain states that maximise the probability of
receiving a given reward. We call such abstractions sharp mappings.

######  Definition 1.

Let $p_{\phi}(r)\coloneqq\sum_{s,a}p_{\phi}(r|s,a)$,
$p_{\phi}(r^{c}|s,a)\coloneqq\sum_{r^{\prime}\neq
r\in\mathcal{R}}p_{\phi}(r^{\prime}|s,a)$ and
$p_{\phi}(r^{c})\coloneqq\sum_{r^{\prime}\neq
r\in\mathcal{R}}p_{\phi}(r^{\prime})$ for all $r\in\mathcal{R}$. For a
$D>p_{\phi}(r)/p_{\phi}(r^{c})$, an MDP mapping $\phi$ is $D$-sharp if for all
$r\in\mathcal{R}$, there exists $s\in S_{\phi}$, $a\in\mathcal{A}$ such that
$\frac{p_{\phi}(r|s,a)}{p_{\phi}(r^{c}|s,a)}\geq D$.

Sharp mappings are defined in this manner to help select candidate state
abstractions that are predictive of all rewards. It is often the case in
reinforcement learning environments that informative reward signals are sparse
during learning. Treating rewards as class labels, the problem of predicting
rewards can be viewed as an unbalanced data classification task. If the
unbalanced nature of the data is not taken into account, feature selection
methods will tend to ignore features that may be predictive of rewards that
occur infrequently but are important for performance. Thus, we adjust for this
fact by ensuring that the threshold chosen for each reward is bounded from
below by $\frac{p_{\phi}(r)}{p_{\phi}(r^{c})}$; if a reward $r$ occurs
infrequently relative to the frequency of all other rewards, then the lower
bound on $D$ will be small. Our approach is to select predicate features that
lead to sharp mappings.

Feature Selection Using Decision Boundaries. Using the sharpness threshold, we
frame the problem as a binary classification task. For each reward
$r\in\mathcal{R}$, the sharpness of the reward distribution at a state-action
pair determines the binary class by a decision rule defined by
$F_{\phi,D}^{r}(s,a)\coloneqq\mathbb{I}\left[\frac{p_{\phi}(r|s,a)}{p_{\phi}(r^{c}|s,a)}>D\right]$
with indicator function $\mathbb{I}$. Feature selection on the binary
classification task can then be performed by eliminating conditionally
redundant features, defined next.

######  Definition 2.

Let $\phi_{1}=\\{p_{1},\ldots,p_{n}\\}$ and
$\phi_{2}=\phi_{1}\setminus\\{p_{j}\\}$ for $j\in\\{1,\ldots,n\\}$ where
$p_{i}$ is a predicate function. If
$F^{r}_{\phi_{1},D}(s,a)=F^{r}_{\phi_{2},D}(s^{\prime},a)$ for all
$s\in\mathcal{S}_{\phi_{1}}$ and $s^{\prime}=s_{1:j-1}s_{j+1:n}$, then $p_{j}$
is a conditionally redundant feature.

A conditionally redundant feature does not affect the output of the decision
rule given the feature ordering and thus does not contribute to discriminating
between different classes. As this property only depends upon the feature
ordering upon construction, removing a conditionally redundant feature does
not change whether the remaining features are redundant or not. To select
candidate predicate features, we set up a decision rule for each reward
$r\in\mathcal{R}$ and eliminate the predicate features that are redundant
across all rewards. In practice, the probabilities used by the decision rules
are estimated as frequency counts.

To remove conditionally redundant features, we use a Binary Decision Diagram
(BDD) data structure [28] to represent each decision rule. A reduction
procedure on the BDD representation then guarantees that only informative
features remain.

######  Theorem 2.

Let $F^{r}_{\phi,D}:\mathcal{S}_{\phi}\times\mathcal{A}\to\\{0,1\\}$ be the
decision rule for reward $r\in\mathcal{R}$. Then the reduced BDD
representation of $F^{r}_{\phi,D}$ contains only conditionally informative
features.

The proof is given in Appendix E. In practice there exists simple procedures
to reduce a BDD. For each reward, we determine a decision rule and perform BDD
reduction to get a set of informative predicates. The union of the sets of
selected predicates is then chosen.

One issue with BDD reduction is that the given variable ordering can impact
whether a feature is conditionally redundant or not; a sub-optimal variable
ordering will keep more features than necessary. We alleviate this issue by
performing BDD reduction on multiple randomly selected subspaces of the
feature space, corresponding to randomly selected subsets of predicates. We
name our approach Random Forest-BDD (RF-BDD). For each selected subset of
predicates $\mathcal{P}_{i}$, let $\phi_{i}$ be the corresponding MDP mapping.
We perform BDD reduction on the decision rule constructed from
$\mathcal{P}_{i}$ given by
$F^{r}_{\mathcal{P}_{i}}(s,a)\coloneqq\mathbb{I}\left[\frac{p_{\phi_{i}}(r|s,a)}{p_{\phi_{i}}(r^{c}|s,a)}>D\right]$.
Once BDD reduction has been performed for all chosen subsets, a choice has to
be made on which predicates to keep. We employ a voting scheme where a
predicate receives a vote if it is kept by a BDD reduction. The votes are then
normalised by the number of times each predicate was selected. The predicates
that have a retention rate above a certain threshold will then be kept. The
kept predicates for each percept are then combined into a single set.

We emphasise that selecting features based on a sharpness threshold does not
directly optimise the $Cost_{M}^{0}$ criteria but rather constrains the set of
possible solutions by their reward predictability. Thus the set of predicates
selected by the RF-BDD procedure above, when input into $\Phi$-BCTW, lead to a
model that approximately minimises $Cost_{M}^{0}$ over the initial set of
predicates.

###  3.2 $\Phi$-Binarized Context Tree Weighting

The binarized context-tree weighting (BCTW) algorithm is a universal data
compression scheme that extends the context-tree weighting algorithm to non-
binary alphabets. The context-tree weighting algorithm is a data structure
that computes an online Bayesian mixture model over prediction suffix trees
[5]. The BCTW approach is to binarize a target symbol and predict each bit
using a separate context tree. We present the $\Phi$-BCTW algorithm which
modifies BCTW by allowing nodes to correspond to arbitrary predicates on
histories. We show that this extension allows $\Phi$-BCTW to compute a
Bayesian mixture model over environments that can be modelled by a set of
predicate functions and will optimise $Cost_{M}^{0}$.

The $\Phi$-BCTW algorithm modifies the BCTW algorithm to allow it to model the
state and reward transitions of an abstract environment defined under a set of
predicate functions. Suppose we are given a set of predicates that defines the
state space. The $\Phi$-BCTW models the abstract environment by assuming it
has MDP structure and thus conditions on an initial context given by the
previous state and action. Suppose the length of a state and action symbol
together is $d$ and let $[x]$ denote the binary representation of a symbol $x$
and $[x]_{i},[x]_{<i}$ denote the $i$-th bit and the first $i-1$ bits of $x$
respectively. Given the sequence $sra_{1:n}$, the distribution of the first
bit is computed as a Bayesian mixture model by a depth $d$ context tree:

$\displaystyle\hat{P}^{(1)}([sr_{n}]_{1}|asr_{1:n-1},a_{n})$
$\displaystyle=\sum_{T\in\mathcal{T}_{d}}2^{-\gamma(T)}\hat{P}([sr_{n}]_{1}|T([s_{n-1}a_{n}]),sr_{1:n-1})$

Here $T([s_{n-1}a_{n}])$ denotes the leaf node in the PST $T$ that is reached
by following the suffix of $[s_{n-1}a_{n}]$. Limiting the context to the
previous state-action symbols encodes the Markov assumption into the modelling
of the state-reward transition. The distribution
$\hat{P}([sr_{n}]_{1}|T([s_{n-1}a_{n}]),sr_{1:n-1})$ of $[sr_{n}]_{1}$ under
the model $T$ is provided by a KT estimator [29] at $T([s_{n-1}a_{n}])$ that
is computed by accumulating the frequency of bits following $[s_{n-1}a_{n}]$
from the history $sr_{1:n}$. The function $\gamma$ measures the complexity of
a model via a prefix coding and the weighting term $2^{-\gamma(T)}$ provides
an Occam-like penalty on the model $T$. For more details on the prior
weighting see [4]. For the $l$-th bit, the distribution conditions on the
previous state-action as well as the previous $l-1$ bits of $sr_{n}$:

$\displaystyle\hat{P}^{(l)}([sr_{n}]_{l}|[sr_{n}]_{<l},asr_{1:n-1},a_{n})=\sum_{T\in\mathcal{T}_{d+l-1}}2^{-\gamma(T)}\hat{P}([sr_{n}]_{l}|T([s_{n-1}a_{n}][sr_{n}]_{<l}),sr_{1:n-1})$
(5)

The prediction for $sr_{n}$ using $\Phi$-BCTW is then given by composing the
predictions for each bit:

$\displaystyle\hat{P}(sr_{n}|asr_{1:n-1},a_{n})=\prod_{j=1}^{k}\hat{P}^{(j)}([sr_{n}]_{j}|[sr_{n}]_{<j},sra_{1:n-1},a_{n})$

Note that the conditional reward distribution
$\hat{P}(r_{n}|sra_{1:n-1},s_{n})$ is modelled by the last
$\lvert[r_{n}]\rvert$ context trees. The following result states that
$\Phi$-BCTW computes a mixture environment model.

######  Proposition 1.

Let
$\hat{P}(sr_{1:n}|a_{1:n},T)=\prod_{i=1}^{n}\prod_{j=1}^{k}\hat{P}([sr_{i}]_{j}|T([s_{i-1}a_{i}][sr_{i}]_{<j}),sr_{1:i-1})$
and $\Gamma(T)=\sum_{j=1}^{k}\gamma(T_{i})$. $\Phi$-BCTW computes a mixture
environment model of the form:

$\displaystyle\xi(sr_{1:n}|a_{1:n})=\sum_{T\in\mathcal{T}_{d}\times\ldots\times\mathcal{T}_{d+k-1}}2^{-\Gamma(T)}\hat{P}(sr_{1:n}|a_{1:n},T)$

The following guarantees fast reward distribution convergence for mixture
environment models.

######  Theorem 3.

Let $\mu$ be the true environment and $\xi$ be the mixture environment model
over a model class $\mathcal{M}$. For all $n\in\mathbb{N},a_{1:n},o_{1:n}$

$\displaystyle\sum_{k=1}^{n}\sum_{r_{1:k}}\mu(r_{<k}|ao_{<k})\left[\mu(r_{k}|aor_{<k}ao_{k})-\xi(r_{k}|aor_{<k}ao_{k})\right]^{2}\leq\min_{\rho\in\mathcal{M}}\left[-\ln
w^{\rho}_{0}+D_{1:n}(\mu||\rho)\right]$

where
$D_{1:n}(\mu||\rho)\coloneqq\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\ln\frac{\mu(r_{1:n}|ao_{1:n})}{\rho(r_{1:n}|ao_{1:n})}$.

The proofs of Proposition 1 and Theorem 3 can be found in Appendix A.

As a mixture environment model, $\Phi$-BCTW’s conditional distribution over
reward sequences is guaranteed to converge quickly by Theorem 3 provided the
true environment can be modelled by the provided predicates. Combined with
$\Phi$-BCTW’s Occam-like model size penalty, $\Phi$-BCTW can be viewed as
optimising $Cost_{M}^{0}$ over the set of abstractions defined by the given
predicates.

###  3.3 Expectimax Approximation With $\rho$UCT

We use Monte-Carlo Tree Search to perform an approximation of the finite
horizon expectimax operation in AIXI. We employ the $\rho$UCT algorithm [4]
where actions are selected according to the UCB policy criteria. Unlike
$\rho$UCT however, we are able to store search nodes of the tree and maintain
value estimates for the duration of the agent’s life-span. This is due to the
feature selection and modelling by $\Phi$-BCTW reducing the environment model
to an MDP with a ‘small’ state space. Thus, the number of samples through the
search tree that need to be generated per step is greatly reduced.

##  4 Experiments

We evaluate our $\Phi$-AIXI-CTW agent’s performance across a number of
different domains. We begin by evaluating our agent’s performance on four
simpler domains before considering the epidemic control problem. All
experiments were performed on a 12-Core AMD Ryzen Threadripper 1920x processor
and 32 gigabytes of memory.

###  4.1 Simple Domains

We consider four simple domains: Biased rock paper scissors (RPS) [30], Taxi
[31], Jackpot and Stop Heist. A full description of each of the environments
is provided in Appendix C.1. As baseline comparison methods we compare against
two decision-tree based, iterative state abstraction methods using splitting
criteria as defined in U-Tree [32] and PARSS-DT [33]. In U-Tree, an existing
node (representing a state) is split if splitting results in a statistically
significant difference in the resulting Q-values as computed by a Kolmogorov-
Smirnov test. In PARSS-DT, nodes are split if the resulting value functions
are sufficiently far apart. Model learning is simply done by frequency
estimation. To ensure our method does not have an informational advantage,
both baseline methods are given the same initial set of predicate functions to
consider node splits from. In both baselines, leaf nodes were tested for
splits every 100 steps.

|
---|---
|

Figure 1: Learning curves on four domains.

From Figure 1, it can be seen that our $\Phi$-AIXI-CTW agent either
outperforms or performs on par with the two baseline decision tree methods.
U-Tree was able to perform well in the biased RPS and Stop Heist domains. The
PARSS based method was able to perform well on the Stop Heist domain and was
displaying evidence of learning, albeit slowly, on the biased RPS domain.
U-Tree and PARSS were both unable to perform well in the Jackpot and Taxi
environments. One possible issue is that Jackpot and Taxi require more
predicates than biased RPS and Stop Heist to be able to perform well. Also,
both methods can be susceptible to producing spurious splits. This can make
the state space too large and the resulting transition model can become too
difficult to learn with.

###  4.2 Epidemic Control over Contact Networks

We now evaluate the agent’s performance on the novel task of learning to
control an epidemic process over large-scale contact networks, a highly
structured environment that exhibits an exponential state space, partial
observability and history dependency.

Epidemic Processes on Contact Networks. In this paper epidemic processes are
modelled on contact networks [34, 35, 36]. A contact network is an undirected
graph where the nodes represent individuals and the edges represent
interactions between individuals. Each individual node in the graph is
labelled by one of four states corresponding to their infection status:
Susceptible ($\mathsf{S}$), Exposed ($\mathsf{E}$), Infectious ($\mathsf{I}$),
and Recovered ($\mathsf{R}$). Every node also maintains an immunity level
$\omega$. The model evolves as a POMDP. At time $t$, the temporal graph is
given by $G_{t}=(V,\mathcal{E}_{t})$ with $V$ as the set of nodes and
$\mathcal{E}_{t}$ as the set of edges at time $t$. A function
$\zeta_{t}:V\to\\{\mathsf{S},\mathsf{E},\mathsf{I},\mathsf{R}\\}\times\\{1,\eta_{1},\eta_{2}\\}$
maps each node to its label and one of three immunity levels where
$\eta_{1},\eta_{2}\in\mathbb{R}_{+}$. Together, $(G_{t},\zeta_{t})$ constitute
the state. At time $t$, a Susceptible node with $k_{t}$ Infectious neighbours
becomes Exposed with probability $\frac{1-(1-\beta)^{k_{t}}}{\omega}$, where
$\beta\in[0,1]$ is the rate of transmission. An Exposed node becomes
Infectious at rate $\sigma$. Similarly, an Infectious node becomes Recovered
at a rate $\gamma$ and becomes Susceptible again at a rate $\rho$.

At every time step, the process emits an observation on each node from
$\\{+,-,?\\}$ corresponding to whether a node tests positive, negative or is
unknown/untested. The observation model is parametrised such that positive
tests are more likely if the underlying node is Infectious, corresponding to
the realistic scenario where sick individuals are more likely to test and also
test positive. A more detailed exposition on the exact transition and
observation models is given in Appendix B.

The agent can perform an action at each time step. We consider a set of 11
possible actions
$\\{\mathit{DoNothing},\mathit{Vaccinate}(i,j),\mathit{Quarantine}(i)\\}$,
where $i\in[0,0.2,0.4,0.6,0.8,1.0]$ and $j=i+0.2$. A $\mathit{Vaccinate}(i,j)$
action increases the immunity level of the top $i$th to $j$th percent of nodes
as ranked by betweenness centrality by one level, up to the maximum value.
Note that a conferred immunity level lasts for the entire length of an episode
unless increased. A $\mathit{Quarantine}(i)$ action quarantines the top $i$th
percent of nodes by removing all edges incident on those nodes for one time
step. The reward function is parametrised to evaluate the agent’s ability to
balance the cost of its actions against the cost of the epidemic. At each time
step, the instantaneous reward is given by

$\displaystyle r_{t}(o_{t},a_{t-1})\coloneqq-\lambda
Positives(o_{t})-Action\\_Cost(a_{t-1})$

where $\lambda\in R_{+}$, $Positives(o_{t})$ counts the number of positive
tests in the observation $o_{t}$ and $Action\\_Cost(a_{t-1})$ is a function
determining the cost of each action. Thus changing $\lambda$ changes the ratio
of contributions to the reward received at each time step. If the agent
successfully terminates the epidemic, i.e. there are no more Exposed or
Infectious nodes, the agent receives a positive reward of $2$ per node. During
a run, it is possible the environment never reaches an absorbing state. If the
agent has not successfully stopped the epidemic process after 1000 steps, we
terminate the episode.

Epidemic control is a topical subject given the prevalance of COVID-19 and
recent approaches to this question vary wildly in terms of the how the problem
is modelled. Most approaches vary in the different ways they model the
dynamics of an epidemic and the action space considered is usually fairly
small [37, 38, 39, 40, 41, 42, 43]. Ultimately, the differences in the
modelling of epidemic processes makes comparison between results difficult.
With no consensus on the appropriate model to use, our model is chosen as it
is sufficiently complex to demonstrate the efficacy of our agent.

Experimental Setup. We use an email network dataset as the underlying contact
network, licensed under a Creative Commons Attribution-ShareAlike License,
containing 1133 nodes and 5451 edges [44, 45]. The transition model,
observation model, $Action\\_Cost(a_{t})$ are parametrised the same way across
all experiments (see Table 1 in Appendix B). A $\mathit{Quarantine}(i)$ action
imparts a cost of $1$ per node that is quarantined at the given time step. A
$\mathit{Vaccinate}(i,j)$ action imparts a lower cost of $0.5$ per node. The
parameters $\lambda,\eta_{1},\eta_{2}$ are varied across experiments. We
generate a set of 1489 predicate functions consisting of predicates on top of
functions such as the percentage each action was selected in the last $N$
steps, the observed infection rate on different subsets of nodes, and also the
infection rate on different subset of nodes as computed by particle filtering.
A full description of how the predicates were generated is given in Appendix
D. The $\Phi$-AIXI-CTW agent is trained in an online fashion. The agent
explores with probability $\epsilon\alpha^{t}$ at each step $t$ until
$\epsilon\alpha^{t}<0.03$, where the agent performs in an $\epsilon$-greedy
way with exploration rate $0.03$. RF-BDD was performed with a threshold value
of $0.9$ across all rewards.

####  4.2.1 Results

Selected Features. The set of predicates chosen in each experiment by RF-BDD
are described in Appendix D. In general, RF-BDD tended to select predicates
representing bits in the binary representation of the observed infection rate
and the rate of change of the observed infection rate on different subsets of
the betweenness centrality nodes. A random selection of different action
sequence indicator functions were also kept. Note that predicates on the
infection rate as computed by particle filtering were not selected and this
can be attributed to the particle degeneracy issue that occurs in high
dimensional problems [46]. These choices by RF-BDD highlight its ability to
select a small set of predicates that provided useful information for epidemic
control. The inclusion of a random selection of different action sequence
indicator functions also demonstrates that it is not perfect. A more thorough
investigation is the topic of future work.

Comparison to Baseline Methods. Both U-Tree and PARSS were used as baseline
methods in the same configuration as in the simpler domains. From Figure 2,
$\Phi$-AIXI-CTW outperforms the two baseline methods and both U-Tree and PARSS
were unable to improve. The epidemic problem as formulated is likely difficult
for both U-Tree and PARSS as the number of predicates required to perform well
is fairly large. Also, both methods can be susceptible to producing spurious
splits. This can make the resulting state space and transition model too large
and difficult to learn with.

|
---|---
a) | b)

Figure 2: Baseline comparison results on a) $\lambda=1,\eta_{1}=2,\eta_{2}=4$.
b) $\lambda=1,\eta_{1}=10,\eta_{2}=20$.

RF-BDD vs. Random Forest Feature Selection. We also compare the performance of
our agent under RF-BDD or Random Forest feature selection. Other feature
selection methods such as forward selection methods [47] were also considered
but were found to offer no advantage over Random Forest. For each experiment,
we plot four graphs. The first graph plots the learning curve computed as a
moving average over 5000 steps of the reward per cycle. The remaining graphs
provide insight into the learnt policy. The second graph plots the percentage
each type of action is performed over a moving average of 500 steps as well as
a moving average of the infection rate over the same window. The remaining two
graphs provide an example of the agent’s behaviour and its impact on the
infection rate over an episode collected toward the end of training.

Figure 3 depicts the $\Phi$-AIXI-CTW agent’s performance with RF-BDD feature
selection over two experiments with differing vaccination efficacy and an
infection rate weighting of $\lambda=10$. RF-BDD was run with 500 trees
generated using random samples of 8 features and used a threshold value of
0.9. In both experiments, the agent learns to be more aggressive in
terminating the epidemic. In Experiment 1 the agent’s behaviour is to
quarantine almost always, and occasionally vaccinate. This is reflected in the
plots of the agent’s behaviour in an episode toward the end of training.
Quarantine actions are performed the entire time except once, resulting in a
fast termination of the epidemic process. In contrast, Experiment 2 shows that
the agent prefers to vaccinate more often. This preference can be attributed
to the added effectiveness that a stronger vaccination action imparts to
lowering the infection rate. When analysing the agent’s behaviour over an
episode, it is clear that the agent chooses to vaccinate almost always whilst
only quarantining at timely moments. This results in the agent also learning
to terminate the episode early, albeit not as quickly. In comparison to
Experiment 1, the average reward per cycle is also higher at the end of
learning.

Figure 4 depicts the $\Phi$-AIXI-CTW agent’s performance with Random Forest
feature selection. Random Forest was initialized with 500 trees and splits
were chosen using either the gini impurity or entropy and the top thirty
highest weighting features were chosen. The resulting predicate sets were very
similar for the two criteria and so we only present results for the entropy
criteria case. When comparing the agent’s performance when using RF-BDD
(Figure 3) versus Random Forest (Figure 4), it is quite clear that the agent
performs better with the predicates chosen using RF-BDD. As can be seen from
Figure 4a) and 4b), the agent’s learning curve when using the predicates
chosen by Random Forest did not improve in either case and actually decreased.
The remaining three plots also show that there is no clear discernible pattern
of behaviour learnt by the agent. This suggests that the features chosen by
Random Forest were not informative enough to allow the agent to learn to
perform well. The inability of traditional feature selection methods like
Random Forest to pick out useful features for the agent was a strong
motivation for constructing an alternative in RF-BDD.

|  |  |
---|---|---|---

a)

|  |  |
---|---|---|---

b)

Figure 3: $\Phi$-AIXI-CTW agent with RF-BDD feature selection. a) Experiment
1: $\lambda=10,\eta_{1}=2,\eta_{2}=4$. b) Experiment 2:
$\lambda=10,\eta_{1}=10,\eta_{2}=20$.

|  |  |
---|---|---|---

a)

|  |  |
---|---|---|---

b)

Figure 4: $\Phi$-AIXI-CTW agent with Random Forest feature selection. a)
Experiment 3: $\lambda=10,\eta_{1}=2,\eta_{2}=4$. b) Experiment 4:
$\lambda=10,\eta_{1}=10,\eta_{2}=20$.

Overall, the results demonstrate that the $\Phi$-AIXI-CTW agent is able to
learn plausible behaviours under the different environment settings. This
demonstrates the potential of our approach in reducing a complex environment
to a simpler problem whilst still maintaining performance. Nevertheless, it is
also quite clear that the agent did not learn optimal behaviour except
potentially in the case of Experiment 1. In Experiment 2, the agent did not
learn that vaccinating a node more than twice does not further reduce the cost
received. However, this is not surprising as this is a difficult causal
relationship to learn from data alone. Furthermore, the full set of generated
predicates do not contain enough information to isolate this particular
history dependency. In fact, the predicates selected generally capture
different statistics about the infection rate at the current time step. If the
value estimate of vaccinating in a highly visited state is high due to it
lowering future received costs, the agent will learn to perform the
vaccination action every time the state is encountered, even if it has done so
many times before. We expect that importing better domain knowledge into the
original set of predicates would solve this issue for the $\Phi$-AIXI-CTW
agent.

##  5 Conclusion

We have introduced the $\Phi$-AIXI-CTW agent model, an agent that expands the
model class that AIXI may be approximated over to structured and non-Markovian
domains via logical state abstractions. We show that our approach is
competitive on simple domains and is sufficiently powerful to handle control
of epidemic processes on contact networks, a class of problems with a highly
structured exponential state space, partial observability and history
dependency. In doing so, our result provides another piece of strong evidence
that AIXI is not just a mathematically interesting theory, but can eventually
lead to practically useful agents.

Whilst RF-BDD has demonstrated its usefulness empirically in our experiments,
a better understanding of how it works theoretically and how it behaves in
other contexts is important. In [48] the authors identify the epidemic control
problem within a class of problems they call the control of diffusion
processes over networks through nodal interventions. The epidemic control
problem constitutes an instance of this class of problems and it would be
interesting to extend our agent setup to other problems within this domain.

A key concern for the real-world application of reinforcement learning on
contact networks for control is the preservation of privacy for individual
nodes. Our agent setup does not restrict the usage of any form of domain
knowledge on the complete graph such as an individual node’s contact network
and extended neighbourhood. Investigating the performance of our agent under
privacy preserving constraints such as differential privacy [49] is an
interesting topic for future research.

## References

  * [1] Marcus Hutter.  Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability.  Springer, Berlin, 2005.
  * [2] Ray J. Solomonoff.  The discovery of algorithmic probability.  J. Comput. Syst. Sci., 55(1):73–88, 1997.
  * [3] Marcus Hutter.  One decade of universal artificial intelligence.  CoRR, abs/1202.6153, 2012.
  * [4] Joel Veness, Kee Siong Ng, Marcus Hutter, William T. B. Uther, and David Silver.  A monte-carlo AIXI approximation.  J. Artif. Intell. Res., 40:95–142, 2011.
  * [5] F.M.J. Willems, Y.M. Shtarkov, and T.J. Tjalkens.  The context-tree weighting method: basic properties.  IEEE Transactions on Information Theory, 41(3):653–664, 1995.
  * [6] Levente Kocsis and Csaba Szepesvári.  Bandit based monte-carlo planning.  In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou, editors, ECML 2006, pages 282–293. Springer Berlin Heidelberg, 2006.
  * [7] Marcus Hutter.  Feature reinforcement learning: Part I. Unstructured MDPs.  In J. Artif. Gen. Intell., 2009.
  * [8] Badri N. Vellambi and Marcus Hutter.  Convergence of binarized context-tree weighting for estimating distributions of stationary sources.  In 2018 IEEE International Symposium on Information Theory (ISIT), pages 731–735, 2018.
  * [9] Ming Li and Paul Vitányi.  An Introduction to Kolmogorov Complexity and Its Applications.  Springer, 1997.
  * [10] Joel Veness, Kee Siong Ng, Marcus Hutter, and Michael H. Bowling.  Context tree switching.  In James A. Storer and Michael W. Marcellin, editors, 2012 Data Compression Conference, pages 327–336. IEEE Computer Society, 2012.
  * [11] Joel Veness, Martha White, Michael Bowling, and András György.  Partition tree weighting.  In Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagristà, and James A. Storer, editors, 2013 Data Compression Conference, pages 321–330. IEEE, 2013.
  * [12] Marc G. Bellemare, Joel Veness, and Michael Bowling.  Bayesian learning of recursively factored environments.  In Proceedings of the 30th International Conference on Machine Learning, pages 1211–1219. JMLR.org, 2013.
  * [13] Marc G. Bellemare, Joel Veness, and Erik Talvitie.  Skip context tree switching.  In Proceedings of the 31th International Conference on Machine Learning, pages 1458–1466. JMLR.org, 2014.
  * [14] David Abel, Dilip Arumugam, Lucas Lehnert, and Michael L. Littman.  State abstractions for lifelong reinforcement learning.  In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, pages 10–19. PMLR, 2018\.
  * [15] Lihong Li, Thomas J. Walsh, and Michael L. Littman.  Towards a unified theory of state abstraction for MDPs.  In International Symposium on Artificial Intelligence and Mathematics, 2006.
  * [16] John W. Lloyd and Kee Siong Ng.  Declarative programming for agent applications.  Autonomous Agents Multi Agent Systems, 23(2):224–272, 2011.
  * [17] John W. Lloyd.  Logic for Learning: Learning Comprehensible Theories from Structured Data.  Springer, 2003.
  * [18] Alonzo Church.  A formulation of the simple theory of types.  Journal of Symbolic Logic, 5:56–68, 1940.
  * [19] Luis Fariñas del Cerro and Olivier Gasquet.  A general framework for pattern-driven modal tableaux.  Logic Journal of the IGPL, 10(1):51–83, 2002.
  * [20] L. Getoor and B. Taskar, editors.  Introduction to Statistical Relational Learning.  MIT Press, 2007.
  * [21] Luc De Raedt, Kristian Kersting, Sriraam Natarajan, and David Poole.  Statistical Relational Artificial Intelligence: Logic, Probability, and Computation.  Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2016.
  * [22] Saso Dzeroski, Luc De Raedt, and Kurt Driessens.  Relational reinforcement learning.  Mach. Learn., 43(1/2):7–52, 2001.
  * [23] Kurt Driessens.  Relational reinforcement learning.  In Claude Sammut and Geoffrey I. Webb, editors, Encyclopedia of Machine Learning and Data Mining, pages 1096–1103. Springer, 2017.
  * [24] Kristian Kersting, Martijn van Otterlo, and Luc De Raedt.  Bellman goes relational.  In Carla E. Brodley, editor, Proceedings of the Twenty-first International Conference on Machine Learning, volume 69 of ACM International Conference Proceeding Series. ACM, 2004.
  * [25] Scott Sanner and Kristian Kersting.  Symbolic dynamic programming for first-order POMDPs.  In Maria Fox and David Poole, editors, Proceedings of the Twenty-Fourth Conference on Artificial Intelligence. AAAI Press, 2010.
  * [26] W.M. Farmer.  The seven virtues of simple type theory.  Journal of Applied Logic, 6(3):267–286, 2008.
  * [27] John Hughes.  Why functional programming matters.  The Computer Journal, 32(2):98–107, 1989.
  * [28] Donald E. Knuth.  The Art of Computer Programming, Pre-Fascicle 1B, volume 4.  Addison-Wesley, 2008.
  * [29] R. Krichevsky and V. Trofimov.  The performance of universal encoding.  IEEE Trans. Inf. Theor., 27(2):199–207, sep 2006.
  * [30] Vivek F. Farias, Ciamac Cyrus Moallemi, Tsachy Weissman, and Benjamin Van Roy.  Universal reinforcement learning.  CoRR, abs/0707.3087, 2007.
  * [31] Thomas G. Dietterich.  Hierarchical reinforcement learning with the MAXQ value function decomposition.  CoRR, cs.LG/9905014, 1999.
  * [32] Andrew Kachites McCallum.  Reinforcement learning with selective perception and hidden state.  1996\.
  * [33] Jesse Hostetler, Alan Fern, and Thomas Dietterich.  Sample-based tree search with fixed and adaptive state abstractions.  J. Artif. Int. Res., 60(1):717–777, sep 2017.
  * [34] Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani.  Epidemic processes in complex networks.  Reviews of Modern Physics, 87(3), 2015.
  * [35] Cameron Nowzari, Victor M Preciado, and George J Pappas.  Analysis and control of epidemics: A survey of spreading processes on complex networks.  IEEE Control Systems Magazine, 36(1):26–46, 2016.
  * [36] Mark Newman.  Networks.  Oxford University Press, 2018.
  * [37] Mauricio Arango and Lyudmil Pelov.  COVID-19 pandemic cyclic lockdown optimization using reinforcement learning.  CoRR, abs/2009.04647, 2020.
  * [38] Arthur Charpentier, Romuald Elie, Mathieu Laurière, and Viet Chi Tran.  Covid-19 pandemic control: balancing detection policy and lockdown intervention under ICU sustainability, 2020.
  * [39] Cédric Colas, Boris Hejblum, Sébastien Rouillon, Rodolphe Thiébaut, Pierre-Yves Oudeyer, Clément Moulin-Frier, and Mélanie Prague.  Epidemioptim: A toolbox for the optimization of control policies in epidemiological models, 2020.
  * [40] Fred Brauer and Carlos Castillo-Chávez.  Mathematical Models in Population Biology and Epidemiology.  Springer, 2012.
  * [41] Roy M Anderson.  The population dynamics of infectious diseases: theory and applications.  Springer, 2013.
  * [42] Konstantin Berestizshevsky, Koffi-Emmanuel Sadzi, Guy Even, and Moni Shahar.  Optimization of resource-constrained policies for covid-19 testing and quarantining.  Journal of Communications and Networks, 23(5):326–339, 2021.
  * [43] Varun Kompella, Roberto Capobianco, Stacy Jong, Jonathan Browne, Spencer Fox, Lauren Meyers, Peter Wurman, and Peter Stone.  Reinforcement learning for optimization of covid-19 mitigation policies, 2020.
  * [44] Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In AAAI, 2015.
  * [45] R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas.  Self-similar community structure in a network of human interactions.  Phys. Rev. E, 68:065103, Dec 2003.
  * [46] Chris Snyder, Thomas Bengtsson, and Mathias Morzfeld.  Performance bounds for particle filters using the optimal proposal.  Monthly Weather Review, 143(11):4750 – 4761, 2015.
  * [47] Gavin Brown, Adam Pocock, Ming-Jie Zhao, and Mikel Luján.  Conditional likelihood maximisation: A unifying framework for information theoretic feature selection.  Journal of Machine Learning Research, 13(2):27–66, 2012.
  * [48] Eli A. Meirom, Haggai Maron, Shie Mannor, and Gal Chechik.  Controlling graph dynamics with reinforcement learning and graph neural networks, 2020.
  * [49] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.

##  Appendix A $\Phi$-BCTW Results

The following proves Proposition 1.

###### Proof.

Under $\Phi$-BCTW, the conditional probability of $sr_{1:n}$ given the actions
$a_{1:n}$ can be expressed as

$\displaystyle\xi(sr_{1:n}|a_{1:n})$
$\displaystyle=\prod_{i=1}^{n}\hat{P}(sr_{i}|asr_{1:i-1},a_{i})$
$\displaystyle=\prod_{i=1}^{n}\prod_{j=1}^{k}\hat{P}^{(j)}([sr_{i}]_{j}|[sr_{i}]_{<j},asr_{1:i-1},a_{i})$
$\displaystyle\overset{(a)}{=}\prod_{i=1}^{n}\prod_{j=1}^{k}\left(\sum_{T\in\mathcal{T}_{d+j-1}}2^{-\gamma(T)}\hat{P}([sr_{i}]_{j}|T([s_{i-1}a_{i}][sr_{i}]_{<j}),sr_{1:i-1})\right)$
$\displaystyle=\sum_{T_{1}\in\mathcal{T}_{d}}\ldots\sum_{T_{k}\in\mathcal{T}_{d+k-1}}\left(\prod_{j=1}^{k}2^{-\gamma(t)}\right)\left(\prod_{j=1}^{k}\prod_{i=1}^{n}\hat{P}([sr_{i}]_{j}|T([s_{i-1}a_{i}][sr_{i}]_{<j}),sr_{1:i-1})\right)$
$\displaystyle\overset{(b)}{=}\sum_{T\in\mathcal{T}_{d}\times\ldots\times\mathcal{T}_{d+k-1}}2^{-\Gamma(T)}\hat{P}(sr_{1:n}|a_{1:n},T).$

Note that (a) follows from Equation 5 and (b) follows by definition. ∎

The following proof of Theorem 3 follows the same steps as Theorem 1 in [4].

###### Proof.

$\displaystyle\sum_{k=1}^{n}\sum_{r_{1:k}}\mu(r_{<k}|ao_{<k})\left(\mu(r_{k}|aor_{<k}ao_{k})-\xi(r_{k}|aor_{<k}ao_{k})\right)^{2}$
$\displaystyle=\sum_{k=1}^{n}\sum_{r_{<k}}\mu(r_{<k}|ao_{<k})\sum_{r_{k}}\left(\mu(r_{k}|aor_{<k}ao_{k})-\xi(r_{k}|aor_{<k}ao_{k})\right)^{2}$
$\displaystyle\overset{(a)}{\leq}\sum_{k=1}^{n}\sum_{r_{<k}}\mu(r_{<k}|ao_{<k})\sum_{r_{k}}\mu(r_{k}|aor_{<k}ao_{k})\ln\frac{\mu(r_{k}|aor_{<k}ao_{k})}{\rho(r_{k}|aor_{<k}ao_{k})}$
$\displaystyle=\sum_{k=1}^{n}\sum_{r_{1:k}}\mu(r_{1:k}|ao_{1:k})\ln\frac{\mu(r_{k}|aor_{<k}ao_{k})}{\xi(r_{k}|aor_{<k}ao_{k})}$
$\displaystyle=\sum_{k=1}^{n}\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\ln\frac{\mu(r_{k}|aor_{<k}ao_{k})}{\xi(r_{k}|aor_{<k}ao_{k})}$
$\displaystyle=\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\sum_{k=1}^{n}\ln\frac{\mu(r_{k}|aor_{<k}ao_{k})}{\xi(r_{k}|aor_{<k}ao_{k})}$
$\displaystyle\overset{(b)}{=}\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\ln\frac{\mu(r_{1:n}|ao_{1:n})}{\xi(r_{1:n}|ao_{1:n})}$
$\displaystyle=\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\ln\frac{\mu(r_{1:n}|ao_{1:n})}{\rho(r_{1:n}|ao_{1:n})}+\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\ln\frac{\rho(r_{1:n}|ao_{1:n})}{\xi(r_{1:n}|ao_{1:n})}$
$\displaystyle\overset{(c)}{\leq}D_{1:n}(\mu||\rho)+\sum_{r_{1:n}}\mu(r_{1:n}|ao_{1:n})\ln\frac{\rho(r_{1:n}|ao_{1:n})}{w_{0}^{\rho}\rho(r_{1:n}|ao_{1:n})}$
$\displaystyle=D_{1:n}(\mu||\rho)-\ln w_{0}^{\rho}$

The inequality in (a) follows as
$\sum_{i}(y_{i}-z_{i})^{2}\leq\sum_{i}y_{i}\ln\frac{y_{i}}{z_{i}}$ for
$y_{i},z_{i}\geq 0,~{}\sum_{i}y_{i}=1,~{}\sum_{i}z_{i}=1$. The equality in (b)
follows by definition as
$\xi(r_{1:n}|ao_{1:n})\coloneqq\prod_{k=1}^{n}\xi(r_{k}|aor_{<k}ao_{k})$.
Finally, (c) follows by definition of a mixture environment model. Note that a
$\Phi$-BCTW mixture environment model is a model where
$\xi(r_{k}|aor_{<k}ao_{k})=\hat{p}(r_{k}|sra_{<k}sa_{k})$. ∎

##  Appendix B Dynamics for epidemic processes on contact networks

$S$$E$$I$$R$$\kappa$$\sigma$$\gamma$$\rho$ Figure 5: SEIRS compartmental model
on contact networks with transmission rate
$\kappa=\frac{1-(1-\beta)^{k_{t}}}{\omega}$ (where $\beta$ is the contact
rate), latency rate $\sigma$, recovery rate $\gamma$ and loss of immunity rate
$\rho$.

Recall that the state of the epidemic process on contact networks is given by
$(G_{t},\zeta_{t})$ at time $t$ where $G_{t}=(V,\mathcal{E}_{t})$ is the
temporal graph at time $t$ and
$\zeta_{t}:V\to\\{S,E,I,R\\}\times\\{1,\eta_{1},\eta_{2}\\}$ maps each node to
its label and one of three immunity levels. Let
$\zeta_{t}(v)=(\zeta_{1,t}(v),\zeta_{2,t}(v))$ where $\zeta_{1,t}$ maps a node
to its infection status and $\zeta_{2,t}$ maps a node to its immunity level.
The agent performs an action $a_{t}$. Quarantine actions modify the underlying
connectivity of the graph $G_{t}$ by removing any edges that contain a
quarantined node; this leads to the graph at time $t+1$ $G_{t+1}$. Vaccinate
actions modify $\zeta_{2,t}$ such that vaccinated nodes have updated immunity
levels in $\zeta_{2,t+1}$. The infection status label of every node evolves
according to the following equations:

$\displaystyle\tau(\zeta_{1,{t+1}}(v)|\zeta_{1,t}(v),s_{t})=\begin{cases}\frac{1-(1-\beta)^{k_{t}}}{\zeta_{2,t}(v)}\;\;&\text{if
}\zeta_{1,{t+1}}(v)=E\text{ and }\zeta_{1,t}(v)=S\\\
1-\frac{1-(1-\beta)^{k_{t}}}{\zeta_{2,t}(v)}\;\;&\text{if
}\zeta_{1,{t+1}}(v)=S\text{ and }\zeta_{1,t}(v)=S\\\ \sigma\;\;&\text{if
}\zeta_{1,{t+1}}(v)=I\text{ and }\zeta_{1,t}(v)=E\\\ 1-\sigma\;\;&\text{if
}\zeta_{1,{t+1}}(v)=E\text{ and }\zeta_{1,t}(v)=E\\\ \gamma\;\;&\text{if
}\zeta_{1,{t+1}}(v)=R\text{ and }\zeta_{1,t}(v)=I\\\ 1-\gamma\;\;&\text{if
}\zeta_{1,{t+1}}(v)=I\text{ and }\zeta_{1,t}(v)=I\\\ \rho\;\;&\text{if
}\zeta_{1,{t+1}}(v)=S\text{ and }\zeta_{1,t}(v)=R\\\
1-\rho\;\;&\text{otherwise,}\end{cases}$ (6)

where $k_{t}$ denotes the number of Infectious, connected neighbours that $v$
has at time $t$.

The observations resemble the testing for an infectious disease with positive
$+$ and negative $-$ outcomes. Recall that the observations on each node are
from $\mathcal{O}=\\{+,-,?\\}$ where $?$ indicates the corresponding
individual has unknown/untested status. At time $t$, node $v\in V$ emits an
observation according to the following distribution:

$\displaystyle\xi_{t}^{v}(+|\zeta_{1,t}(v)=S)=\alpha_{S}\mu_{S},$
$\displaystyle\xi_{t}^{v}(+|\zeta_{1,t}(v)=E)=\alpha_{E}\mu_{E},$ (7)
$\displaystyle\xi_{t}^{v}(-|\zeta_{1,t}(v)=S)=\alpha_{S}(1-\mu_{S}),$
$\displaystyle\xi_{t}^{v}(-|\zeta_{1,t}(v)=E)=\alpha_{\mathsf{E}}(1-\mu_{E}),$
$\displaystyle\xi_{t}^{v}(?|\zeta_{1,t}(v)=S)=1-\alpha_{S},$
$\displaystyle\xi_{t}^{v}(?|\zeta_{1,t}(v)=E)=1-\alpha_{E},$
$\displaystyle\xi_{t}^{v}(+|\zeta_{1,t}(v)=I)=\alpha_{I}\mu_{I},$
$\displaystyle\xi_{t}^{v}(+|\zeta_{1,t}(v)=R)=\alpha_{R}\mu_{R},$
$\displaystyle\xi_{t}^{v}(-|\zeta_{1,t}(v)=I)=\alpha_{I}(1-\mu_{I}),$
$\displaystyle\xi_{t}^{v}(-|\zeta_{1,t}(v)=R)=\alpha_{R}(1-\mu_{R}),$
$\displaystyle\xi_{t}^{v}(?|\zeta_{1,t}(v)=I)=1-\alpha_{I},$
$\displaystyle\xi_{t}^{v}(?|\zeta_{1,t}(v)=R)=1-\alpha_{R}.$

Here, $\alpha_{S},\alpha_{E},\alpha_{I},\alpha_{R}$ denote the fraction of
Susceptible, Exposed, Infectious and Recovered individuals, respectively, that
are tested on average at each time step. The parameters
$\mu_{S},\mu_{E},\mu_{I},\mu_{R}$ denote the probability that a node that is
Susceptible, Exposed, Infectious, Recovered respectively tests positive. Table
1 lists the transition and observation model parameters that were used in all
experiments.

$\beta$ | $\sigma$ | $\gamma$ | $\rho$ | $\alpha_{S}$ | $\alpha_{E}$ | $\alpha_{I}$ | $\alpha_{R}$ | $\mu_{S}$ | $\mu_{E}$ | $\mu_{I}$ | $\mu_{R}$
---|---|---|---|---|---|---|---|---|---|---|---
0.2 | 0.3 | 0.08 | 0.1 | 0.1 | 0.1 | 0.8 | 0.05 | 0.1 | 0.9 | 0.9 | 0.1
Table 1: Transition and observation model parameters.

##  Appendix C Extra Experimental Results

|  |  |
---|---|---|---

a)

|  |  |
---|---|---|---

b)

Figure 6: a) Experiment 5 $\lambda=1,\eta_{1}=2,\eta_{2}=4$. b) Experiment 6
$\lambda=1,\eta_{1}=10,\eta_{2}=20$.

Figure 6 depicts the agents behaviour over two experiments with differing
vaccination efficacy and an infection rate weighting of $\lambda=1$. With
$\lambda=1$, an observed positive node is equivalent in cost to quarantining a
node or vaccinating two nodes. In Experiment 5 (Figure 6a)), the agent learns
to perform quarantine and vaccination actions almost equally frequently and
slightly more often that doing nothing. Whilst there is no clear discernible
pattern in the agent’s policy and it appears almost random, the learning curve
shows that the agent has learnt to perform better than random. In Experiment 6
the agent prefers to do nothing most of the time and quarantine/vaccinate
less. This difference between Experiments 5 and 6 can be attributed to the
increased efficacy of vaccination actions in reducing the infection rate
throughout an episode. In comparison to Experiments 1 and 2 (Figure 3), where
$\lambda=10$, the action percentages indicate that the agent is more
conservative; the agent tends to be less active in managing the epidemic and
is more likely to do nothing. This difference in behaviour directly reflects
the different cost function between the two sets of experiments.

###  C.1 Additional Domains

Biased rock paper scissors (RPS). This domain is taken from [30]. Biased RPS
is an environment where the agent repeatedly plays RPS against the environment
which has a slight bias in its strategy. The environment plays randomly unless
it won the previous round playing rock. In this case, the environment will
always play rock at the current time step. This bias can be simply captured by
a predicate $\it{IsRockAndLose}_{t-1}(h)$ which returns whether the
environment played rock and the agent lost at the previous time step. A set of
1000 predicates were generated including predicates that detect whether the
nth bit of the suffix of the history equals 1,
$\it{Suffix}_{N}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(=1)(h)$,
and uninformative predicates such as returning whether a random bit equals 1.

Stop Heist. The Stop Heist environment is an environment exhibiting history
dependency where the agent acts as the surveillance team for a bank. At every
time step, the agent receives a binary observation representing whether a
known suspect arrives at the bank. The suspect’s arrival times are determined
by a Hawkes process. As a Hawkes process is self-exciting, recent arrivals
increase the chance of arriving in the near term. The chance that a suspect
performs a heist is also modelled as a self-exciting process, increasing the
more frequently the suspect arrives. The agent has two actions it can perform:
Do Nothing or Stop Suspect. The agent incurs a penalty of -100 if the suspect
performs a heist and the agent chose to Do Nothing. If the agent chooses to
Stop Suspect and the suspect was performing a heist, it receives a reward of
100. If the agent performs Stop Suspect but the suspect did not plan to
perform a heist, it receives a minor penalty of -1. Otherwise, the agent
receives 0 reward. This environment requires the agent to capture predicates
that maintain some knowledge of the history of arrivals. To facilitate this,
predicates of the following form were provided:

  * •

$\it{Percent}_{o,n}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(\geq
p)(h)$ for various values of $o\in\mathcal{O},n\in\mathbb{N}$ and $p\in[0,1]$.

$\it{Percent}_{o,n}$ computes the percentage of times that observation $o$ was
received in the past $n$ steps. $(\geq p)$ returns whether the provided
argument is greater than $p$. A set of 1000 predicates were generated for
various values of $n$ and $p$ as well as including uninformative predicates
such as returning whether a random bit equals 1.

Jackpot. The Jackpot environment is an environment where the agent plays a
betting game against the environment at every time step. At every time step,
the agent can choose to either Bet or Pass. If the agent performs Pass, it
receives 0 reward. The environment is initiated with a pre-defined list of
numbers. If the agent chooses to Bet on a time step that is a multiple of a
number in the pre-defined list of numbers, it receives reward 1 with 70%
chance. If instead the agent chooses to Bet on a time step that is not a
multiple of a number in the pre-defined list of numbers, then the agent
receives reward -1 with 70% chance. The observation received at every time
step is constant and is uninformative. This environment requires the agent to
capture predicates that provide some knowledge about arithmetic and also be
able to count the time steps. Predicates of the following form were provided:

  * •

$\it{Count}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{IsMultiple}_{j}(h)$
for various values of $j\in\mathbb{N}$.

$\it{Count}$ returns the number of steps that have occurred in the provided
history $h$ and $\it{IsMultiple}_{j}$ returns whether the provided argument is
a multiple of $j$. A set of 1000 predicates were generated for various values
of $j\in\mathbb{N}$ as well as including uninformative predicates such as
returning whether a random bit equals 1.

Taxi. The Taxi environment is the well-known environment first introduced in
[31]. The agent acts as a Taxi in a grid world and must move to pick up a
passenger and drop the passenger off at their desired destination. Instead of
the 5x5 grid traditionally considered, we consider a 2x5 grid with no
intermediate walls. We also change the reward for dropping the passenger at
its destination successfully to 100. These modifications were made to shrink
the planning horizon as well as make the original problem less sensitive to
parameters for the three algorithms tested. Four destination locations are
still used. The predicates available to the agent are suffix predicates that
determine whether different bits of the history sequence are equal to 1. The
agent will be able to recover the original MDP if it captures the suffix
predicates that comprise the last observation received.

##  Appendix D Predicates

We assume that the agent has a background theory $\Gamma$ consisting of:

  * •

a graph $G=(V,\mathcal{E})$ that captures, either exactly or approximately,
the structure of the initial graph $G_{0}$ but not the disease status of nodes
(the connectivity between people could be inferred from census data,
telecommunication records, contact tracing apps, etc);

  * •

the transition and observation functions of a dynamics model (i.e. Equations 6
and 7 for an SEIRS model) of the underlying disease but not the parameters.
This information would be provided by experts in the chosen domain, i.e.
epidemiologists working on epidemic modelling.

The agent has access to the following functions:

  * •

$\it{Encode}_{i}$ splits the possible range of its argument into $2^{i}$ equal
sized buckets and encodes its argument by the number of whichever bucket it
falls into. If the range is unbounded, it is first truncated.

  * •

$\it{Bit}_{i}$ takes a bit string and returns the $ith$ bit.

  * •

$\it{NaiveInfectionRate}_{t,\nu}$ takes a history sequence $h\in\mathcal{H}$
and computes the infection rate at time $t$ over the set of nodes
$\nu\subseteq V$ as the observed infection rate plus a constant multiplied by
the number of nodes observed as unknown.

  * •

$\it{InfectionRateOfChange}_{t,\nu}$ takes a history sequence
$h\in\mathcal{H}$ and computes the change in infection rate between timesteps
$t-1$ and $t$ over the set of nodes $\nu\subseteq V$.

  * •

$\it{PercentAction}_{a,N}$ takes a history and returns the percentage of time
action $a$ was selected in the last $N$ timesteps.

  * •

$\it{ActionSequenceIndicator}_{a_{1:k}}$ is an indicator function returning 1
if the last $k$ actions performed match $a_{1:k}$ and 0 otherwise.

  * •

$\it{MAReward}_{w}$ takes a history and returns the moving average of the
reward over a window of size $w$.

  * •

$\it{RateOfChange}$ takes two real numbers and computes the ratio between
them.

  * •

$\it{ParticleFilter}_{\theta,M}$ takes a history sequence and approximates the
belief state using the transition and observation models given by $\theta$ and
$M$ particles.

  * •

$\it{ParticleInfRate}$ takes a belief state represented by a set of particles
and computes the expected infection rate.

Function composition is handled by the (reverse) composition function

$\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,:(a\rightarrow
b)\rightarrow(b\rightarrow c)\rightarrow(a\rightarrow c)$

defined by
$((f\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,g)\;x)=(g\;(f\;x)).$

The set of predicates generated using the above functions were of the
following form:

  * (1)

$\it{NaiveInfectionRate}_{t,\nu}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Encode}_{5}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Bit}_{i}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(=1)(h)\;\;\;\text{for
various }\;i,\nu\subseteq V,\;t=1$

  * (2)

$\it{InfectionRateOfChange}_{t,\nu}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Encode}_{7}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Bit}_{i}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(=1)(h)\;\;\;\text{for
various}\;i,\nu\subseteq V,\;t=1$

  * (3)

$\it{PercentAction}_{a,N}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Encode}_{8}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Bit}_{i}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(=1)(h)\;\;\;\text{for
all }a\in\mathcal{A}\text{ and various values of }N$

  * (4)

$\it{ActionSequenceIndicator}_{a_{1:k}}(h)\;\;\;\text{for various
}a_{1:k},\;k\geq 1$

  * (5)

$\lambda
s.\it{RateOfChange}(\it{MAReward}_{w_{1}}(s),\it{MAReward}_{w_{2}}(s))\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(\geq
1)(h)$ for  $w_{1},w_{2}\in\mathbb{N}$

  * (6)

$\it{ParticleFilter}_{\theta,M}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{ParticleInfRate}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Encode}_{5}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,\it{Bit}_{i}\,\raisebox{1.00006pt}{$\scriptscriptstyle\circ$}\,(=1)(h)$
for various $\theta,M=100$

The choice of subsets of nodes were limited to 20% percentile ranges of the
nodes ranked by betweenness centrality and degree centrality. Note that
retrieving a subset of the bits from an encoded value essentially selects a
range that the encoded value falls within. For example, suppose we have two
bits encoding values from 0 to 3. The largest bit indicates whether the
encoded value is greater than 2 or not.

Table 2 lists the number of each type of predicate that were generated in the
initial set. Table 3 details the type of predicates that were chosen in each
experiment.

Predicate type | Number generated
---|---
(1) | 55
(2) | 80
(3) | 693
(4) | 633
(5) | 8
(6) | 20
Table 2: Number of predicates generated of each type. In total there are 1489 predicates generated. |  | Predicate Type
---|---|---
Experiment |  FS Method | (1) | (2) | (3) | (4) | (5) | (6) | Total
1 | RF-BDD | 8 | 7 | 17 | 2 | 0 | 0 | 34
2 | RF-BDD | 3 | 9 | 9 | 2 | 0 | 0 | 23
3 | Random Forest | 16 | 0 | 6 | 0 | 8 | 0 | 30
4 | Random Forest | 10 | 0 | 12 | 0 | 8 | 0 | 30
5 | RF-BDD | 6 | 9 | 9 | 5 | 0 | 0 | 29
6 | RF-BDD | 10 | 4 | 16 | 4 | 0 | 0 | 34
Table 3: Number of predicates generated of each type for each experiment.

As can be seen from Table 3, the RF-BDD feature selection method was able to
pick out predicates that provided information about the current infection rate
(type (1)), its rate of change (type (2)), action percentages (type (3)) and a
few action sequence indicators (type (4)). This behaviour was consistent
across all experiments where RF-BDD was used.

Random Forest feature selection chose predicates that provided information
about the current infection rate (type (1)), action percentages (type (3)),
and the reward rate of change (type (5)).

Note that predicates on the infection rate as computed by particle filtering
were not selected by either method. This can be attributed to the particle
degeneracy issue that occurs in high dimensional problems [46]. When the size
of the state space is very high dimensional and the number of particles used
is not sufficient, the particle set can collapse to a very small number of
points when updated, resulting in poor estimates.

It is likely that the difference in performance when comparing Experiments 1,
2, 3, and 4 (see Appendix C stems from the fact that RF-BDD chose type (2)
predicates whereas Random Forest chose type (5) predicates. It is unlikely
that type (4) predicates provided much useful information as the sequences
chosen were not insightful and varied across the four experiments. In
contrast, type (2) predicates inform the agent about the infection rate of
change, which can provide useful information about the next state of the
epidemic process provided the transition is sufficiently smooth.

##  Appendix E Feature Selection Using Binary Decision Diagrams

for tree = l sep = 1cm, , [ $x_{1}$, circle, draw, [ $x_{2}$, circle, draw,
edge=dashed [ $x_{3}$, circle, draw, edge=dashed [$0$, r, edge=dashed], [$0$,
r] ] [$x_{3}$, circle, draw [$0$, r, edge=dashed], [$0$, r] ] ] [ $x_{2}$,
circle, draw [$x_{3}$, circle, draw, edge=dashed [$0$, r, edge=dashed], [$1$,
r] ] [$x_{3}$, circle, draw [$0$, r, edge=dashed], [$1$, r] ] ] ]

Figure 7: Full binary tree representation of the boolean function
$f(x_{1},x_{2},x_{3})=1\text{ if }x_{1}\text{ and }x_{3}$.
$x_{1}$$x_{3}$$0$$1$ Figure 8: Reduced BDD for the boolean function
$f(x_{1},x_{2},x_{3})=1\text{ if }x_{1}\text{ and }x_{3}$.

Figure 7 depicts the full binary tree representation of the boolean function
$f(x_{1},x_{2},x_{3})=1\text{ if }x_{1}\text{ and }x_{3}$. Dotted lines
indicate a path that is traversed when the boolean variable at the node equals
$0$ and solid lines are traversed when the boolean variable equals $1$. We
will always place variables $x_{i}$ higher in the tree than variables $x_{j}$
if $i<j$. Figure 8 depicts the same Boolean function but in reduced BDD form;
as can be seen, the redundant feature $x_{2}$ has been eliminated.

We now consider the properties of reduced BDDs that make them appropriate for
feature extraction. Every Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$
corresponds to a $2^{n}$ bit string representing the function’s output on a
canonical ordering of its input. More specifically, let $\beta$ be the $2^{n}$
bit string representing $f$. Then $\beta$ starts with $f(0,\ldots,0)$ and
continues with $f(0,\ldots,0,1)$, $f(0,\ldots,1,0)$, $f(0,\ldots,1,1)$,
$\ldots$, until $f(1,\ldots,1,1)$. The $2^{n}$ bit string is known as a
Boolean function’s truth table. For example, the truth table of
$f(x_{1},x_{2},x_{3})=1\text{ if }x_{1}\text{ and }x_{3}$ is $00000101$. The
truth table also corresponds to the sequence of outputs we would get from the
BDD representing the Boolean function if we traversed the BDD by taking $0$
paths before $1$ paths. We now define the notion of a bead.

######  Definition 3 (Bead).

A bead of order $n$ is a truth table $\beta$ such that there does not exist a
string $\alpha$ of length $2^{n-1}$ such that $\beta=\alpha\alpha$.

In other words, a bead is a truth table that does not repeat itself at its
mid-point. Now note that every node in a BDD can be identified with a
substring of the truth table. Consider the full binary tree in Figure 7 again.
The root node of the BDD can be identified with the full truth table of length
$2^{3}$. The nodes one layer below correspond to a length $2^{2}$ partition of
of the truth table. The full identification is shown in Figure 9. Depending on
the truth table, nodes in a non-reduced BDD can correspond to either beads and
non-beads. A key property of reduced BDD structures is that they only maintain
nodes corresponding to beads.

for tree = l sep = 1cm, , [ $00000101$, draw, rounded corners [ $0000$, draw,
rounded corners, edge=dashed [ $00$, draw, rounded corners, edge=dashed [$0$,
r, edge=dashed], [$0$, r] ] [$00$, draw, rounded corners [$0$, r,
edge=dashed], [$0$, r] ] ] [ $0101$, draw, rounded corners [$01$, draw,
rounded corners, edge=dashed [$0$, r, edge=dashed], [$1$, r] ] [$01$, draw,
rounded corners, [$0$, r, edge=dashed], [$1$, r] ] ] ]

Figure 9: Full binary tree of the $f(x_{1},x_{2},x_{3})=1\text{ if
}x_{1}\text{ and }x_{3}$ with nodes identified with corresponding beads.

######  Theorem 4.

Suppose $G=(V,E)$ is a reduced BDD representing a Boolean function $f$ of $n$
variables with truth table $\beta$. Let $h$ be a function mapping all nodes
$v\in V$ to its relevant substring of $\beta$. Then $h(v)$ is a bead for all
nodes $v\in V$.

###### Proof.

First note that the terminal nodes always correspond to the length 1 beads $0$
and $1$. We thus focus on internal nodes. Suppose an internal node $v$ is such
that $h(v)$ is not a bead. Then its two children $v_{0}$ and $v_{1}$ found by
following paths $0$ and $1$ respectively have equivalent representations, i.e.
$h(v_{0})=h(v_{1})$. This means that the two strings $h(v_{0})$ and $h(v_{1})$
are the same length. The substrings being the same length implies that both
nodes are of the same depth in a full tree representation of the BDD and hence
are labelled with the same Boolean variable. Furthermore, having the same
substring also means that the subtrees starting with $v_{0}$ and $v_{1}$ as
the root are the same. Thus, nodes $v_{0}$ and $v_{1}$ are equivalent,
contradicting the claim that the BDD is reduced. ∎

The following proposition shows that conditionally redundant features
correspond directly to non-beads in any BDD representation of a given decision
rule.

######  Proposition 2.

Let $G_{x}$ be a BDD representation of the decision rule
$F^{r}_{\phi,D}:\mathcal{S}_{\phi}\times\mathcal{A}\to\\{0,1\\}$. Then any
node in $G_{x}$ labelled with a conditionally redundant feature will
correspond to a non-bead.

###### Proof.

Let $\phi_{1}=\\{p_{1},\ldots,p_{n}\\}$ be the predicate set and a predicate
$p_{i}$ labels nodes on the $ith$ depth of $G_{x}$. Recall that a feature
$p_{j}$ is conditionally redundant iff for all $s\in\mathcal{S}_{\phi_{1}},$
$F^{r}_{\phi_{1},D}(s,a)=F^{r}_{\phi_{2},D}(s^{\prime},a)$ where
$\phi_{2}=\phi_{1}\setminus\\{p_{j}\\}$ and $s^{\prime}=s_{1:j-1}s_{j+1:n}$.

Suppose that a predicate $p_{j}$ is conditionally redundant. Let
$a\in\\{0,1\\}^{j-1}$ and $b\in\\{0,1\\}^{n-j}$. Since $p_{j}$ is
conditionally redundant, we must have $F_{\phi_{1}}(a0b)=F_{\phi_{2}}(ab)$.
Similarly, $F_{\phi_{1}}(a1b)=F_{\phi_{2}}(ab)$. Thus,
$F_{\phi_{1}}(a0b)=F_{\phi_{1}}(a1b)$. Therefore any node labelled by $p_{j}$
has a truth table that repeats a binary string of length $2^{j-1}$ about its
midpoint and is thus a non-bead. ∎

Theorem 4 guarantees that a BDD reduction procedure will remove all non-beads
and Proposition 2 guarantees that conditionally redundant features correspond
to non-beads in any BDD representation of a decision rule. Thus, Theorem 4 and
Proposition 2 provide the basis upon which BDD reduction can be utilised to
remove conditionally redundant features. The proof of Theorem 2 follows
directly from combining Proposition 2 and Theorem 4.

Whilst Theorem 2 shows that BDD reduction can remove conditionally redundant
features, it is important to note that the definition of a conditionally
redundant feature is dependent upon the ordering of the predicates. This is
part of the motivation for performing RF-BDD.

##  Appendix F Coding $MDP$ Sequences and a $Cost_{M}$ Counter-example

###  F.1 Coding $MDP$ Sequences

To evaluate candidate state abstractions, the $\Phi$MDP approach ranks
mappings based on the code length of the state-action-reward sequence. For
this approach to be well formed, the underlying interaction sequence must be
ergodic: the frequencies of every finite substring of the sequence converge
asymptotically. Consider the set of states
$\left\\{s_{t_{1}},\ldots,s_{t_{k}}\right\\}$ transitioned to from a
particular state $s$ and action $a$. This set of states will be an i.i.d.
sequence generated according to
$\theta_{s,s^{\prime}}^{a}=\mathbb{P}(s_{t_{i}}=s^{\prime}|s,a)$. The state
sequence can then be considered a combination of i.i.d. sequences and the
probability of the state sequence conditioned on actions is given by

$\displaystyle\mathbb{P}(s_{1:n}|a_{1:n},\theta)$
$\displaystyle=\prod_{s,a}\prod_{j=t_{1}}^{t_{k}}\mathbb{P}(s_{j}|s,a)=\prod_{s,a}\prod_{j=t_{1}}^{t_{k}}\theta_{s,s_{j}}^{a}=\prod_{s,a}\prod_{s^{\prime}}\left(\theta_{s,s^{\prime}}^{a}\right)^{n_{s,s^{\prime}}^{a}}$
(8)

In practice, $\theta$ is unknown and we instead rely on estimates
$\hat{\theta}$. If $\theta_{s,s^{\prime}}^{a}$ is estimated by a frequency
estimator
$\hat{\theta}_{s,s^{\prime}}^{a}=\frac{n^{a}_{s,s^{\prime}}}{n_{s}^{a}}$, then
the code length of $s_{1:n}$ given $a_{1:n}$ is given by

$\displaystyle
CL(s_{1:n}|a_{1:n})=-\log\mathbb{P}(s_{1:n}|a_{1:n},\hat{\theta})=-\sum_{s,a}\sum_{s^{\prime}}n_{s,s^{\prime}}^{a}\log(\hat{\theta}_{s,s^{\prime}}^{a})=\sum_{s,a}CL(\bm{\hat{\theta}_{s}^{a}})~{},$
(9)

where
$\bm{\hat{\theta}_{s}^{a}}=(\hat{\theta}_{s,s^{\prime}}^{a})_{s^{\prime}}$ and
$CL(\bm{\hat{\theta}_{s}^{a}})=-\sum_{s^{\prime}}n_{s,s^{\prime}}^{a}\log(\hat{\theta}_{s,s^{\prime}}^{a})=n^{a}_{s}H(\bm{n^{a}_{s}}/n^{a}_{s})$.
Similarly, the code length for the reward sequence is given by
$CL(r_{1:n}|s_{1:n},a_{1:n})=\sum_{s,a,s^{\prime}}CL(\bm{\hat{\theta}_{s,s^{\prime}}^{a}})$,
where
$\bm{\hat{\theta}_{s,s^{\prime}}^{a}}=(\hat{\theta}_{s,s^{\prime}}^{a,r})_{r}$
and
$CL(\bm{\hat{\theta}_{s,s^{\prime}}^{a}})\coloneqq\sum_{s,a,s^{\prime}}n_{s,s^{\prime}}^{a,r}\log(\theta_{s,s^{\prime}}^{a,r})$.

###  F.2 $Cost_{M}$ Counter-example

$o$$o^{\prime}$0.10.90.90.1 Figure 10: A diagram illustrating the observation
transition probabilities of the environment in the counter-example.

Consider the counter-example presented in Figure 10. The environment emits two
observations $o,o^{\prime}$ and two rewards 0, 1 with the following
distribution:

$\displaystyle p(o_{t}|h_{t-1},a_{t-1})=\begin{cases*}0.9\quad&\text{if
$o_{t}=o_{t-1}$}\\\ 0.1\quad&\text{otherwise.}\end{cases*}$ if $o_{t}\neq
o_{t-1}$: $\displaystyle
p(r_{t}|h_{t-1},a_{t-1},o_{t})=\begin{cases*}0.1\quad&\text{if $r_{t}=1$}\\\
0.9\quad&\text{if $r_{t}=0$}\end{cases*}$ if $o_{t}=o_{t-1}$: $\displaystyle
p(r_{t}|h_{t-1},a_{t-1},o_{t})=\begin{cases*}0\quad&\text{if $r_{t}=1$}\\\
1\quad&\text{if $r_{t}=0$}\end{cases*}$

Note that the given percept dynamics of the given environment are effectively
independent of the actions performed. Now consider two candidate MDP mappings
$\phi_{0}$ and $\phi_{1}$. For all $h_{t}\in\mathcal{H}$,

$\displaystyle\phi_{0}(h_{t})$ $\displaystyle=\begin{cases*}1\quad&\text{if
$o_{t-1}\neq o_{t}$}\\\ 0\quad&\text{otherwise.}\end{cases*}$
$\displaystyle\phi_{1}(h_{t})$ $\displaystyle=0~{}.$

Clearly the mapping $\phi_{0}$ is more informative and provides direct
indication of the dynamics under which positive reward is received. Let us
consider $Cost_{M}$ in the limit normalised by $n$. For ergodic sequences, the
frequency estimates will converge to the true probabilities. Thus we have

$\displaystyle\lim_{n\to\infty}\frac{Cost_{M}(n,\phi)}{n}$
$\displaystyle=\lim_{n\to\infty}\frac{CL(s_{1:n}|a_{1:n})+CL(r_{1:n}|s_{1:n},a_{1:n})+CL(\phi)}{n}$
$\displaystyle\overset{(a)}{=}-\lim_{n\to\infty}\sum_{s,a}\sum_{s^{\prime}}\frac{n_{s,s^{\prime}}^{a}}{n}\log\left(\frac{n_{s,s^{\prime}}^{a}}{n_{s}^{a}}\right)-\lim_{n\to\infty}\sum_{s,a}\sum_{r}\frac{n_{s}^{ar}}{n}\log\left(\frac{n_{s}^{ar}}{n_{s}^{a}}\right)$
$\displaystyle\overset{(b)}{=}-\sum_{s,a}p_{\phi}(s,a)\sum_{s^{\prime}}p_{\phi}(s^{\prime}|s,a)\log
p_{\phi}(s^{\prime}|s,a)-$
$\displaystyle\quad\quad\sum_{s,a}p_{\phi}(s,a)\sum_{r}p_{\phi}(r|s,a)\log
p_{\phi}(r|s,a)$
$\displaystyle\overset{(c)}{=}-\sum_{s}p_{\phi}(s)\sum_{s^{\prime}}p_{\phi}(s^{\prime}|s)\log(p_{\phi}(s^{\prime}|s))-\sum_{s}p_{\phi}(s)\sum_{r}p_{\phi}(r|s)\log
p_{\phi}(r|s)$
$\displaystyle\overset{(d)}{=}\sum_{s}p_{\phi}(s)H_{\phi}(S^{\prime}|S=s)+\sum_{s}p_{\phi}(s)H_{\phi}(R|S=s)$

Here (a) follows by definition, (b) follows since the frequency estimates
converge, (c) follows since the actions do not affect the state or reward
probabilities and (d) uses the definition of conditional entropy where we
subscript by $\phi$ to indicate that the distribution is under the $\phi$
mapping.

We can now compute $\lim_{n\to\infty}\frac{Cost_{M}(n,\phi_{0})}{n}$:

$\displaystyle\sum_{s}p_{\phi_{0}}(s)H_{\phi_{0}}(S^{\prime}|S=s)$
$\displaystyle=p_{\phi_{0}}(s=0)H_{\phi_{0}}(S^{\prime}|S=0)+p_{\phi_{0}}(s=1)H_{\phi_{0}}(S^{\prime}|S=1)$
$\displaystyle=0.9\cdot 0.47+0.1\cdot 0.47$ $\displaystyle=0.47$
$\displaystyle\sum_{s}p_{\phi_{0}}(s)H_{\phi_{0}}(R|S=s)$
$\displaystyle=p_{\phi_{0}}(S=0)H_{\phi_{0}}(R|S=0)+p_{\phi_{0}}(S=1)H_{\phi_{0}}(R|S=1)$
$\displaystyle=0.9\cdot 0+0.1\cdot 0.47$ $\displaystyle=0.047$

We thus have that
$\lim_{n\to\infty}\frac{Cost_{M}(n,\phi_{0})}{n}=0.47+0.047=0.517$. For
$\phi_{1}$ we have

$\displaystyle\sum_{s}p_{\phi_{1}}(s)H_{\phi_{1}}(S^{\prime}|S=s)$
$\displaystyle=0$ $\displaystyle\sum_{s}p_{\phi_{1}}(s)H_{\phi_{1}}(R|S=s)$
$\displaystyle=p_{\phi_{1}}(S=0)H_{\phi_{1}}(R|S=0)+p_{\phi_{1}}(S=1)H_{\phi_{1}}(R|S=1)$
$\displaystyle=0.08$

We then have $\lim_{n\to\infty}\frac{Cost_{M}(n,\phi_{1})}{n}=0.08$. Thus the
uninformative mapping $\phi_{1}$ minimises $Cost_{M}$ even though it is less
predictive of the rewards. As mentioned earlier, this phenomenon occurs due to
the heavy weighting given to the code length of the state sequence. Even if
the model is no good for predicting reward, a simple transition model can
cause decreases in the state sequence code length that can offset increases in
the reward sequence code length. This issue will be exacerbated in
environments where the reward signal is sparse; the cost associated with being
unable to predict a sparse reward is negligible relative to the modest
reduction in complexity of the state transition model.