Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
Please note that I am not knowledgeable in this research area and hence please lower the weight of my review.
strengths_and_weaknesses: - The considered problem of incorporating logical state abstraction in the AIXI framework is interesting and well motivated
- 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.
- The experiment design is timely, and prevalant to the COVID-19 situation.
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.
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
    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.

strengths_and_weaknesses: Originality:
	This 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.
	Some 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.

Quality:
	The submission is somehow technically sound. The experimental results demonstrate the effectiveness of the method. The following aspects of the paper are still insufficient.
	1. The RF-BDD only provides enough information in the epidemic model. What about scaling ability and quality in other baselines? 
	2. In feature selection comparison, this paper only makes the comparison with Random Forest feature selection. What about other methods?
Clarity:
	I think some of the points in the paper are not clear enough and not well organized. 
	1. 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$? 
	2. 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. 
	3. 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?

Significant:
	This 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.

questions: 1. In general, what configuration of RF-BDD will get a great informative feature result?
2. Dose RF-BDD significantly increase the time cost compared to random forest feature selection?

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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

strengths_and_weaknesses: ### Strengths
* The epidemic domain considered in the experiments appears challenging and interesting, and it’s obviously timely.
* The writing of the paper is crisp and clear at the sentence level.
* The paper builds nicely on an existing line of work, but should engage more with other lines of work.
* The limitations in the results section are stated clearly, especially around L331.

### Weaknesses
* 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.
* 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.
* 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.
* 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.
* 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?
* 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.

### Minor
* The acronym BCTW is used on L139 ad L143 before it is defined on L212
* Typo: “abstractions that contains” on L149
* The second summation in Definition 5 has r where it should have r’
* The use of \mathcal{A} in Definition 7, for arbitrary finite alphabet, is confusing because that symbol was previously used for the action space
* 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.
* The font sizes in the plots in Figure 1 could be increased for clarity
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.
2. 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.
review_title: null

Meta-review: metareview: The paper proposes an interesting approach and analysis for extending the AIXI agent to handle non-Markovian structured decision processes. Technically, the paper appears to be fine, and its evaluation has significantly improved after the addition of baselines. At the same time, this work could be strengthened by motivating its own significance more explicitly: despite being conceptually appealing, the practical importance of extending the AIXI agent to non-Markovian and structured environments is not entirely obvious.
confidence: Less certain
Decision: Accept