A Direct Approximation of AIXI Using Logical State Abstractions
Authors: Samuel Yang-Zhao
Tianyu Wang
Kee Siong Ng
Venue: NeurIPS 2022 Accept (2022)
Keywords: AIXI
artificial general intelligence
higher-order logic
reinforcement learning
state abstraction
feature selection
binary decision diagrams

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.

A Direct Approximation of AIXI Using Logical State Abstractions
Samuel Yang-Zhao"1
Tianyu Wang"
Australian National University Canberra ACT 2601
Australian National University Canberra ACT 2601 edu au
yanuel.yang-2 -haannuuaaaaauu..mmmmm edu. au
Kee Siong Ng
Australian National University
Canberra ACT 2601 keesiong ng@anu. edu. au
Abstract
We propose a practical integration logical state abstraction with AIXI, 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 based on higher-order logic, which can be used to define and enumer- ate 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 4-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 be integrated with different planning algorithms. Experimental results on controlling epidemics lcage-scale contact networks validates the agent's performance.
Introduction
The AIXI agent [|| is mathematical solution the general reinforcement learning problem that combines Solomonoff induction 2 with sequential decision theory. At time t, after observing the observation-rewant sequence o and performing previous actions 01:-11 the AIXI agent chooses action given by
ag arg max
max Oc---m
+r. F4+m]
Σ
2 2-1(a)
(I)
where U is a universal Turing machine, Ug, a1sn) is the output of U given program and input d1:ns N is the lookahead horizon, and I(q) is the length of q 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, fundamental issue with AIXI is that it is only asymptotically com- putable. The question of whether a good practical approximation AIXI can be constructed remains open problem twenty years after AIXI first introduced E The most direct approximation of AIXI given so far is in which the Bayesian mixture over all Turing machines is approximated over n- n-Markov environments using Context Tree Weighting [5] and the expectimax search is approximated
"Equal contribution. t Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

using pUCT, a Monte Carlo planning algorithm [6]. This paper extends in several ways. To move beyond n-Markov environments and make easy to incorporate background knowledge, we adopt 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 ? 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 [ to incorporate complex features in its context then allows a Bayesian mixture to be computed over a much larger model class. Combined with PUCT, 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-trine trivial contact networks.
Background and Related Work
2.1 The General Reinforcement Learning Setting
We consider finite action, observation and reward spaces denoted by A, O, R respectively. The agent interacts with the environment in cycles: at any time, the agent chooses an action from A and the environment returns an observation and reward from O and R. Frequently we will be considering observations and rewards together, and will denote x O X R as a percept from the percept space O R. We will denote a string 2 ... ...Tr of length n by Zimn and its length n 1 prefix as Ten- An action, observation and reward from the same time step will be denoted cor, After interacting for n cycles, the interaction string #1 0101/1.... ".,'"'". (denoted aor1:: from here on) is generated. A history h is an element of the history space H. == (Ax O x R.) An environment p is a sequence of probability distributions {po. Pl, P2....., where Pa : A" + D((O x R)" that satisfies Vaim Yor<<n ( cn)) Lor Ox R. Pn ).)) We will drop the subscript
on P. when the context is clear. The predictive probability of the next percept given history and a current action is given by p(orn/eor<nn an) p(orm///--1nn) = plorinlas for all aor such that p(or (cc)) 0.
p(oren (een)
The general reinforcement learning problem is for the agent to learn a policy т : H + D(A) mapping histories to a distribution 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 e N. Given a history h and a policy π the value function with respect to the environment p is given by V.T(h,) = Ex Eitm 1 Rs bb) where R; denotes the random variable distributed according to p for the reward at time i. The action value function is defined similarly as Vi" (h,, a++1) =
E Li=t+1 R2 he, ac+1] The agent's goal is to learn the optimal policy n", which is the policy that results the value function with the maximum reward for any given history.
2.2 AIXI agent and its Monte-Carle approximation
The following equation can be shown to be formally equivalent to Equation 1I At time f, the AIXI agent chooses action or according
a- = arg max
max
F1tmm |mm
Σ
Σ 2 Mooriitt/aaaat
OT
PEMU
where m E N is finite lookahead horizon, My is the set of all enumerable chronological semimea-
sures M. p(or1:+m (1:+m) is the probability of observing or14+m given the action sequence a1 and K ((p) denotes the Kolmogorov complexity [9] of p.
The Bayesian mixture EU Epe.M. 2 ((K(p) p(orl:c(a1:) in 2 is mixture environment model,
with (() as the prior for 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. W Let μ be the true environment and & be the mixture environment model over a model class M. For all n E N and for all a1..-
Σ
((o<<klazk) (p(ors) (arr -
min In PEM
+ Daculllo) (3)
A I orTiA
2

---

where (u(lpp is the KL divergence of p(-la1n) and p(-la1..)
To see the rapid convergence of 5 to μ. take the limit n - oc on the lhs. of 3 and observe that in the case where Min su,, Dn (14 (p) is bounded, the Lh.s. only be finite if E(or laor cor=)aa) converges sufficiently fast to (a(ork: (aor< From Theorem | it can be shown that AIXI's environment mixture model εu also enjoys this property with any computable environment.
The first practical approximation of AIXT given in 4 in which the expectimax search is approxi- mated 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 tistory-based models ITC [ 22 [K] In this paper, we generalise the Bayesian mixture learning in an orthogonal direction by adapting binarised CTW [ 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 function é H + Sp that maps every history string to an element of an abstract state space Sş- Given state abstraction d, the abstract environment is a process that generates a state s' and reward given history and action according to the distribution Pa(s', r/h, a) = Lose(haor)= p(or p(or/ha). The interaction sequence of the original process converts to state-action-reward sequence under ø.
key reason for considering abstractions is that the space 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 é 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 4MDP framework instead provides an optimisation criteria for ranking candidate mappings & based on how well the state-action-rewee reward sequence generated by & can be modelled as an MDP whilst being predictive of the rewards 77. A good é results in Markovian model where the state is sufficient statistic of the history and thus facilitates reinforcement learning.
Optimisation Criteria for Selecting Mappings. The 4MDP framework ranks candidate state abstractions based on an optimisation criteria defined over the code length of the stwar- sequence. Let Cz( denote the code length of a sequence Ii:n and C'L CL( (4mm) denote the code length of sequence Fi:m conditioned on d1m-- At time n, the Cost objective is defined as
Cost as (n, 6) == (a + Cr ( a1m) + CL())
where (h+)) = S; and hG- = aor For more details on how MDP sequences can be coded see 7
The objective is then to look for øbest = arg mins Cost (n, o). Note that CL()) is 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, imperative that state abstraction produces model that can predict the reward sequence well. However, the equal weighting given to the code lengths of the state sequence in Cost As can be suboptimal; in fact a simple environment can be constructed where Cost M gives unintuitive results (see Appendix F). Given that CL(ssmn (a.)) 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 (n, Φ) CL(rr.n (11m1/111:: a1:)) + CL(()).
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 X-calculus [[8], extended with type polymorphism to increase its expressiveness. The inference engine has two interacting components: an equational-
reasoning engine and tableau theorem prover [19] Thus, a predicate evaluation at the internal node of Context Tree takes the general form I T p(h), where I' is theory consisting of equations
3

---

and implications that reflects the agent's ' current belief base, h is the history of agent- connt-enviromment interacts, and p is a predicate mapping histories to boolean values. There also a predicate rewrite system for defining and enumerating a set of predicates.
Suitable alternatives to logical formalism are studied in the Statistical Relational Artificial Intelligence literature 200 21I, including a few that caters specifically for relational reinforcement
learning ? 2 and Symbolic MDP/POMDPs 2 2
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 incorporate domain knowledge and broaden the model class of AIXI approximations remains unchanged with an alternate formal logic.
3 The f-AIXI-CTW Agent
We now present the Q-AIXI-CTW agent. The actions and rewards are considered in their binary representation. The agent has access to a large set P predicates on histories, and each subset of P constitutes candidate state abstraction. We show that a 4-BCTW data structure performs a Bayesian mixture over all abstractions defined by P and will optimise Cost However, this is computationally infeasible in practice if P is large. We first reduce this computational burden by performing feature selection to shrink the set of predicates for Q-BCTW. Finally, the agent selects actions according to the pUCT algorithm.
3.1 Shrinking the Model Class via Feature Selection
Our method for selecting candidate state abstractions 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 Costar A simple heuristic that we employ 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 (r) == Es.a (p)(sss)), a), Po po(r")s,) = Er ( a) and po(r") = En (r()') for all r E R. For a D > po(r)/Po(r") (r))) an MDP mapping ø is D-sharp if for all r E R, there exists E Sz. E A such that Po(r(s.a) Po(151800) 2 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 Po(r)
Pa(roy if 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 E R. the sharpness of the re- ward distribution at a state-action pair determines the binary class by decision rule defined by p=(rls.a) > D) with indicator function I. Feature selection on the binary classifi- (s, a) = (r
cation task can then be performed by eliminating conditionally redundant features, defined next. Definition 2. Let di = (1... .......,pp] Pm and Φ2 = Φi \ {p,) for j E fI....,m) n) where p; is predicate function. If F2, (s.a) = F F (s a) for all s E So, and s' = S1:j- 184 then Pj is 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 decision rule for each reward r E R and eliminate the predicate features that are redundant across all rewards. practice, the probabilities used by the decision rules are estimated as frequeney 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².D So A + BDD representation of $.D contains only conditionally informative features.
{0, be the decision rule for reward r E R. Then the reduced
The proof is given in Appendix E In practice there exists simple procedures to reduce a BDD. For each reward, we determine decision rule and perform BDD reduction to get 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 feature conditionally redundant or not; sub-optimal variable ordering will keep more features than necessary. We alleviate this issue by performing BDD reduction multiple randomly selected subspaces of the feature space, corresponding to randomly selected subsets of predicates. We name approach Random Forest-BDD (RF-BDD). For each selected subset of predicates P,, let Φ; be the corresponding MDP mapping. We perform BDD reduction on the decision rule constructed from P; Po, (rls,a)
> D Once BDD reduction has been performed for all chosen subsets, choice has to be made on which predicates to keep. We employ a voting scheme where a predicate receives a vote if it kept by a BDD reduction. The votes are then normalised by the number of times each predicate was selected. The predicates that have retention rate above certain threshold will then be kept. The kept predicates for each percept are then combined into a single set.
given by F2, (s, = Il (r.(aa)).a)
We emphasise that selecting features based on a sharpness threshold does not directly optimise the Costa 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 4-BCTW, lead to model that approximately minimises Cost M over the initial set of predicates.
3.2 O-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 data structure that computes an online Bayesian mixture model over prediction suffix trees [5]. The BCTW approach is to binarize target symbol and predict each bit using separate context tree. We present the Q-BCTW algorithm which modifies BCTW by allowing nodes to correspond to arbitrary predicates on histories. We show that this extension allows 4-BCTW to compute a Bayesian mixture model over environments that can be modelled by a set of predicate functions and will optimise Cost
The BCBCTW algorithm modifies the BCTW algorithm to allow model the state and reward transitions of an abstract environment defined under set of predicate functions. Suppose we are given a set of predicates that defines the state space. The 4-BCTW models the abstract environment by assuming it has MDP structure and thus conditions on initial context given by the previous state and action. Suppose the length of a state and action symbol together d and let [z]] denote the binary representation of a symbol and [x] [x]<< denote the i-th bit and the first - bits of respectively. Given the sequence srai.. the distribution of the first bit is computed as Bayesian mixture model by depth d context tree:
p() ([sr, 1a = 2-) P((srrl (([sn-1an])) sTi:n-1)
TETa
Here T[[sn- 14,1) denotes the leaf node in the PST T that is reached by following the suffix of [8n-1a7). Limiting the context to the previous state-action symbols encodes the Markov assumption into the modelling of the state-reward transition. The distribution
88
of [srn]1 under the model T is provided by KT estimator 2 at ((s)n-1a,)) that is computed by accumulating the frequency of bits following [5,] from the history sr The function ?
measures the complexity of a model via prefix coding and the weighting term 2-v(7) provides an
Occam-like penalty on the model T. For more details on the prior weighting see [4 For the I-th bit,
the distribution conditions on the previous state-action as well as the previous - 1 bits of sr,:
pi0 ([sr (elerr]l[ssrrr Jel(srr))) sl kts 1m1
Σ TET
2 (T) (( (1( [sr,) (e),,))),,,,))))))))) 8mmm (5)
5

---

The prediction for syn using 4-BCTW is then given by composing the predictions for each bit:
P(sra as 0n) = II
((sTn) [sTn]<3 8701:n 0.
==1
Note that the conditional reward distribution P(r, |srai:n-1, ) is modelled by the last [[r=]] context trees. The following result states that 4-BCTW computes mixture environment model.
Proposition 1. Let P(srim/a1:n T) =
I ((ss -r) and
I(T) = Ei (T.). Q-BCTW computes mixture environment model of the form:
{(srim(a1>)
Σ
2 g-T(T) P(
TETax...xTatt...
The following guarantees fast reward distribution convergence for mixture environment models.
Theorem 3. Let y be the true environment and & be the mixture environment model over model class M. For all n E N, a1m; O1m
(afeellaox)\((rrlorro.. k= risk
Σ u(F=xllo<k)) [u(Tklorr -arr:aaooo)o__(rooorrra {(ralaor<xaox)) min | In wg + Dim PEM
where (um(l) = Eri.. ( (mom) ) In M4 lao.m)
p("in (00...)
The proofs of Proposition and Theorem can be found in Appendix A
As mixture environment model, B-BCTW's conditional distribution over reward sequences is guaranteed to converge quickly by Theorem B provided the true environment can be modelled by the provided predicates. Combined with 4-BCTW W's Occam-like model size penalty, 4-BCTW can be viewed as optimising Cost M over the set of abstractions defined by the given predicates.
3.3 Expectimax Approximation With pUCT
We use Monte-Carlo Tree Search perform approximation of the finite horizon expectimax operation in AIXI. We employ the pUCT algorithm ! where actions are selected according to the UCB policy criteria. Unlike pUCT however, value estimates for the duration of the agent's life-span. This is due to the feature selection and modelling by 4-BCTW reducing the environment model 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.
able to store search nodes of the tree and maintain
4 Experiments
We evaluate our 4-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 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
Jackpot and
As baseline comparison methods 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, existing node (representing state) is split if splitting results statistically significant difference in the resulting Q-values as computed by Kolmogorov-Sming 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.
Stop Heist. A full description of each of the environments is provided in Appendix C.1
test. In PARSS-DT, nodes are split if the resulting

---

Learning Curve biased RPS
Learning Curve Stop Heist
1og Reaans
1.15
Aeg Roward
1.10-
pitree
1.05
100
0.5
0.0
0.2
0.4
5.6
0.0
1.0
0.8
0.2
0.4
0.5
0.8
1.0
Traiiin Cycles
1e5
Training Cycle
1e5
Learning Curve - Jackpot
Learning Curve Surve-Tasi
pti 3ixi
phi aid utrice
u.trec
parss
optimall
Aug Reware
ANg Roware
0.0
-0.2
0-
0.0
0.4
0.5
0.8
1.0
0.0
0.4
0.5
0.8
1.0
Training Cycles
105
Traiiin Cycles
Figure 1: Learning curves on four domains.
From Figure 0 it can be seen that A-AIIIICT agent either outperforms or performs 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 producing spurious splits. This can make the state space 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, 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 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 labelled by one of four states corresponding to their infection status: Susceptible (S), Exposed (E), Infectious (I), and Recovered (R). Every node also maintains an immunity level w. The model evolves as POMDP. At time t, the temporal graph is given by G2 = (V, Eg) with V as the set of nodes and & as (S, E, I, R} x {1, m. n2} maps each node its label
networks M
35
[6]
the set of edges at time A function S. : and one of three immunity levels where 7, 7/2 E R Together, (G,, G) constitute the state. At time
I, a Susceptible node with k, Infectious neighbours becomes Exposed with probability 1-(1-8)*t where 3 E [0, 1] is the rate of transmission. An Exposed node becomes Infectious rate a. Similarly, an Infectious node becomes Recovered at rate and becomes Susceptible again at a rate p.
At every time step. the process emits an observation whether a node tests positive, negative or is unknown/untested. The observation model is parametrised such that positive tests 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
each node from {+, -,?} corresponding to
The agent can perform an action at each time step. We consider set of 11 possible actions DoNothing, Vaccinale(i,j), Quaranline(()), where E [0, 0.2, 0.4, 0.6, 0.8, 1.0) and j = i+ 0.2. Vaccinate(i, j) action increases the immunity level of the top ith to jth percent of nodes as ranked by betweenness centrality by one level, up to the maximum value. Note that a conferred immunity
7

---

level lasts for the entire length of an episode unless increased. A Quarantine(t) action quarantines the top ith 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
re(or, = -)Post - --ttiitttooooo (oott(aa-1)
where X E R4, (ositives(or) counts the number of positive tests in the observation or and Oction_Cost(en is function determining the cost of each action. Thus changing À 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 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 [ Ultimately, the differences in the modelling of epidemic processes makes comparison between results difficult. With no consensus on the appropriate model use, our model is chosen it is sufficiently complex demonstrate the efficacy of our agent.
fairly small 377 33 39
12
Experimental Setup. We use an email network dataset as the underlying contact network, licensed Seabbution-SharAAlle License, containing 1 1133 nodes and 5451 edges The transition model, observation model, Action (ost((n)) are parametrised the same way across all experiments (see Table D in Appendix B). A Quarantine(() action imparts a cost of per node that is quarantined at the given time step. A Vaccinate(i.)) action imparts a lower cost of 0.5 per node. The parameters X, 7/,, 7/2 varied across experiments. We generate 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 [ The --AIXI-CTW agent is trained in an online fashion. The agent explores with probability ea at each step until ea' < 0.03, where the agent performs in an e-greedy way with exploration rate 0.03. RF-BDD was performed with a threshold value of 0.9 across all rewards.
under Creative Commons
44 45
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 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 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 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 --AIXX-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.
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 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 performed over a moving average of 500 steps as well as moving average of the infection rate over the same window.
8

---

-200
Avg Hewwrdd
Avg Reswnrd
-400
ph-aixx u-tree gerss
-300
phi-
u-tree
-450
-350
-500
Training Cycle
Training Cycles
165
Figure 2: Baseline comparison results on X 1, 771
2, 172
4. b) A
1, 7/1
= 10, 1/2 20.
Rowdd
-150-
Qunenttre
Vecommtt
Thering Cycaa
The ma Sar
1TADE
albax
Thaniig Cycles
Thasing Cycss
35822
35833
Figure --AIXI-CTW agent with RF-BDD feature selection. a) Experiment 2, 122 4. b) Experiment 2: X = 10, mh = 10, 722 = 20.
10, 771
The remaining two graphs provide an example of the agent's 's behaviour and its impact on the infection rate over an episode collected toward the end of training.
Figure 3 depicts the -E-AIXI-CTW agent's performance with RF-BDD feature selection over two experiments with differing vaccination efficacy and infection rate weighting of À 10. RF-BDD was run with 500 trees generated using random samples of 8 features and used threshold value 0.9. In both experiments, the agent learns to be more aggressive in terminating the epidemic. In Experiment I the agent's behaviour is to quarantine almost always, and occasionally vaccinate. This 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 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 's behaviour over an episode, is clear that the agent chooses to vaccinate almost always whilst only quarantining at timely moments. This results in the agent also learning 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 &-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 '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 44) 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 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 strong motivation for constructing alternative in RF-BDD.

---

162
200
134 200
Figure 4: --AIXI-CTW agent with Random Forest feature selection. a) Experiment 3: À = 10, 171 122 4. b) Experiment 4: À 10, 171 10, 122 20.
Overall, the results demonstrate that the --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 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 further reduce the cost received. However, this 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 highly visited state 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 --AIXIICTW agent.
surprising this is difficult causal
5 Conclusion
We have introduced the 4-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, class of problems with highly structured exponential state space, partial observability and history dependency. In doing so, our result provides another piece of strong evidence that AIXI not just mathematically interesting theory, but can eventually lead to practically useful agents.
Whilst RF-BDD has demonstrated its usefulness empirically in experiments, better understand- ing of how works theoretically and how it behaves in other contexts is important. In 4S] the authors identify the epidemic control problem within 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 other problems within this domain.
A key concern for the real-world application of reinforcement learning on contact networks for control 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 individual node's contact network and extended neighbourhood. Investigating the performance of our agent under privacy preserving constraints such as differential privacy 4 is an interesting topic for future research.
10

---

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] Mareus Hutter. One decade of universal artificial intelligence. CoRR, abs//102..6l. 2012.
[4] Joel Veness, Kee Siong Ng, Marcus Hutter, William T. B. Uther, and David Silver. monte-carlo AIXI approximation. J. Artif. Intell. Res., 40:95 10095-142, 2011.
[5] F.M.J. Willems, Y.M. Shtarkov, and TJJ. Tjalkens. The context-tree weighting method: basic properties. IEEE Transactions on Information Theory, 41(3):6533-66 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 283-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 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 SagrisSagissà, 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 recursively factored environments. In Proceedings of the 30th International Conference on Machine Learning, pages 1211-1219. JMLR.org, 2013.
[13] Mare 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. 2014.
[14] David Abel, Dilip Arumugam, Lucas Lehnert, and Michael 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 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 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) 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-Fourd 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-266.
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 IB, volume 4. Addison- Wesley, 2008
[29] R. Krichevsky and V. Trofimov. The performance of universal encoding. IEEE Trans. Inf. Theor,, 27(2):199-25) 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/995990 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):117-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: 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.044 .04647, 2020.
[38] Arthur Charpentier, Romuald Elie, Mathieu Laurière, and Viet Chi Tran. Covid-19 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, Vierre-yees Oudeyer, Clément Moulin-Frier, and Mélanie Prague. Fpidemioptim: toolbox for the optimization of control policies in epidemiological models, 2020.
12

---

[40] Fred Brauer and Carlos Castillo-Chiie 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 sesource-constraing policies for covid-19 19 testing and quarantining. Journal of Communica- fions 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 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 network of human interactions. Phys. Rev. E, 68:0688:0000 100, Dec 2003.
[46] Chris Snyder, Thomas Bengtsson, and Mathias Morzfeld. Performance bounds for particle filters using the optimal proposal. Monthly Weather Review, 143(11):4700 2015.
[47] Gavin Brown, Adam Pocock, Ming-Jic Zhao, and Mikel Luján. Conditional likelihood maximi- sation: A unifying framework for information theoretic feature selection. Journal of Machine Learning Research, 13(2):27-66, 2012.
[48] Eli 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):211400) 2014.
13

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See sections for our main claims and section 4 for our empirical results.
(b) Did you describe the limitations of your work? [Yes] See the conclusion section.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the conclusion section.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [No] The results included have been proved in other papers. These papers are referenced to.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No] Some of the results presented deal with the analysis of the agent's 's behaviour averaging multiple runs.
single run/episode. This type of result is not conducive to
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes].
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "uj7DIU1hXU5", "reviewer": "Reviewer_4Mza", "summary": "This paper considers an AIXI reinforcement learning approach that combines state abstraction, model learning, and planning. For state abstraction, a subset of predicates from a large candidate set is selected on the basis of their ability to predict rewards. For model learning in the abstraction, a binarized version of CTW is used. For planning, a version of UCT is used. Experiments are in an epidemic domain that features a large structured state space with partial observability and stochastic transitions.\n", "questions": "1. How exactly do you fit the decision rules F? I am guessing, based on the name “Random Forest”, that something like decision tree learning is used (before converting to BDD)? This should be stated clearly.\n2. L261 remarks that the selected features and BCTW induce an MDP with a small state space. Is the UCT algorithm here anything other than running UCT in this abstract MDP? If there is a difference, what is it? If not, I think the entire planning approach could be explained in just this way, without necessarily even mentioning \\rho UCT.", "limitations": "Societal impact is discussed in the conclusion.\n", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* The epidemic domain considered in the experiments appears challenging and interesting, and it’s obviously timely.\n* The writing of the paper is crisp and clear at the sentence level.\n* The paper builds nicely on an existing line of work, but should engage more with other lines of work.\n* The limitations in the results section are stated clearly, especially around L331.\n\n### Weaknesses\n* The experimental results do not include any baseline comparisons. The domain does appear difficult, but baseline results would be necessary to get a sense of whether the proposed approach is on par with or better than alternative approaches. As the paper states, the results are not optimal, but other approaches may or may not fare similarly. Relational reinforcement learning / statistical relational learning methods would be good choices. But holding part of the proposed approach fixed and considering alternative implementations of the other parts would also be illuminating. For example, I am curious whether alternative feature selection strategies, alternative model learning algorithms, or alternative planning algorithms would perform better than the proposed methods.\n* Using alpha=0 in CostM (L120) arguably defeats the purpose of the CostM objective. If it were straightforward to extend the feature selection method to handle alpha>0, then using alpha=0 for simplicity in certain domains may be okay, but I am guessing that the extension is not straightforward. Presentation aside, I worry about using alpha=0 because in many domains, I would expect that certain features are not directly predictive of reward at the current time step, but are very important for predicting reward at a later time step.\n* The treatment of reward as a categorical variable is limiting, but I know there are many works that do this. But then further converting the multiclass problem into multiple binary classification problems, as implied by the feature selection approach, seems even more limiting, because it really loses sight of the fact that rewards have a canonical ordering, and that there can only be one reward given at any time step.\n* I appreciate the effort to make the paper self-contained, but I think the overall presentation would be more clear if the paper spent less time on background and more time focusing on novel contributions. For example, the BDD and UCT sections can probably be reduced significantly.\n* L133 refers to “the practical convenience of working with (the functional subset of) a language like Python.” I am wondering, then, why Section 2.4 is important: why not simply state that predicates are enumerated from a domain-specific language (DSL), as in the program synthesis literature? In other words, for the sake of the rest of this paper, why do we need to constrain predicates to be anything other than functions from histories to booleans?\n* The paper claims “the richest, direct approximation of AIXI known to date.” I wonder, though, if many existing approaches in the RL literature could be seen to approximate AIXI, even if they are not usually described through the AIXI lens. I suspect that this is the case, and in my opinion, this diminishes the significance of the work here, because there are many related works with variously rich representations that just use different framings.\n\n### Minor\n* The acronym BCTW is used on L139 ad L143 before it is defined on L212\n* Typo: “abstractions that contains” on L149\n* The second summation in Definition 5 has r where it should have r’\n* The use of \\mathcal{A} in Definition 7, for arbitrary finite alphabet, is confusing because that symbol was previously used for the action space\n* The results refer to a “random selection of different action sequence indicator functions.” Does “random” here mean “seemingly arbitrary”? If so, that word choice or something else may be more clear.\n* The font sizes in the plots in Figure 1 could be increased for clarity", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8m7gK-NrJER", "reviewer": "Reviewer_g5bg", "summary": "This paper studies the problem of state abstraction in the general reinforcment learning setting. Specifically, the paper looks at AIXI agents, and addresses the challenge of feature selection for forming the state abstractions. In the experiments, the proposed model is evaluated on a timely control task of epidemic processes. \nPlease note that I am not knowledgeable in this research area and hence please lower the weight of my review.", "questions": "- I like the design and the results demonstrated in the experiments. The only concern I have is the lack of direct comparison to baseline methods, such as heuristic ones (Line 304), prior works on AIXI, or general RL methods.\n- Apart from the considered control of epidemic processes, can the proposed method also apply to other complex sequential decision making problems?", "limitations": "The authors sufficiently discussed the potential limitations in the conclusion. The empirical study shows their method can be potentially a positive and timely contribution. I do not see any negative societal impact.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The considered problem of incorporating logical state abstraction in the AIXI framework is interesting and well motivated\n- The problem formulation and the theoretical contributions are well explained. However, I do not have sufficient expertise to judge the correctness of the theoretical contributions.\n- The experiment design is timely, and prevalant to the COVID-19 situation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "317B164umEe", "reviewer": "Reviewer_2MNv", "summary": "    This paper proposes a new approximation of AIXI which extends the previous work \"A Monte-Carlo AIXI approximation\". This novel approximation supports complex features on a non-Markovian and structured environment using formal logic. The main contributions of this paper can be listed as follow: (1) In order to select the right feature from the complex candidate features, use the BDD to remove redundant features. (2) Inspired by random forests, this paper proposed the RF-BDD algorithm to select the subset right feature using the D-sharp as a decision rule.\n    Finally, The Experiment result shows that $\\Phi$-AIXI-CTW agent model can handle the non-trivial contact network. It demonstrates that this agent can learn different behaviors under different environment configurations. In the feature selection process, the RF-BDD approach obtain a better result compared to the Random Forest feature selection.\n", "questions": "1. In general, what configuration of RF-BDD will get a great informative feature result?\n2. Dose RF-BDD significantly increase the time cost compared to random forest feature selection?\n", "limitations": "Yes, author mentioned that current agent does not carry out privacy constraints, and the follow-up needs to continue to study the performance under the constraints of privacy constraints. Make it possible to actually apply.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\tThis work is a novel combination of well-known techniques to extend previous work, specifically, abstracting the logic state border the approximation of AIXI, using $\\Phi$MDP as feature selection criterion, running BCTW for the mixture environment model, and getting the policy by $\\rho$UCT.\n\tSome new methods are also introduced in this paper. In the feature selection, this paper proposes MDP-mapping, i.e., D-sharp, and then converts the feature selection to a classification task. Finally, this paper proposes the RF-BDD to do the feature selection, which makes it possible to tackle the large classes of problems.\n\nQuality:\n\tThe submission is somehow technically sound. The experimental results demonstrate the effectiveness of the method. The following aspects of the paper are still insufficient.\n\t1. The RF-BDD only provides enough information in the epidemic model. What about scaling ability and quality in other baselines? \n\t2. In feature selection comparison, this paper only makes the comparison with Random Forest feature selection. What about other methods?\nClarity:\n\tI think some of the points in the paper are not clear enough and not well organized. \n\t1. In section 2.3, we use the $\\Phi$MDP as a feature selection criterion, however, in section 3.1, you actually use the D-sharp heuristic to do the feature selection. I don't know the relationship between them. Is it reasonable to replace it? Does it drive the feature selection result in a small $Cost_M$? \n\t2. The organization of the paper needs to be optimized, when I read section 4.3, the paper discusses Experiments 3 and 4, but I can't quickly locate their figures. \n\t3. In the experiment, I can't find details about BDDs constructed by RF-BDD to do the feature selection. How many times do you randomly select features to construct BDD for feature selection? In each time, how do you determine the subset of feature predicates to run the BDD reduction?\n\nSignificant:\n\tThis paper proposes the approximation of AIXI over the non-Markovian domain and structured knowledge by logical state abstractions, which broadens the approximation of AIXI agent model. This paper provides a new idea to approximation and feature selection via RF-BDD.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept