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 use of Tsetlin Machines for the contextual bandit problem. Tsetlin Machines learn a classifier using propositional logic assuming the given context is also binarized. The key proposed advantage is that such a system yields an interpretable model which is useful for many applications. The paper discusses the background and learning mechanism for Tsetlin Machines and then applies Tsetlin Machines in contextual bandit using epsilon-greedy and Thomson sampling-based exploration approaches. Experimental evidence in several datasets is provided showing that the new methods outperform neural networks using epsilon-greedy and decision trees. 
strengths_and_weaknesses: Strength:

1. Interpretability is an important topic in machine learning, and interpretable models are very much sought after in certain domains. The proposed work can be useful, therefore
2. Empirical evidence show the advantage over some other methods.

Weakness:

1. The paper while promising falls short on several details. Firstly, while a discussion of the learning mechanism for Tsetlin machine is presented, very little is offered in why such a learning rule is advantageous. No theoretical results are stated to show that it converges, and no details are given for certain decisions (see questions below for examples).

2. It is unclear why the rules generated by the model are necessary interpretable. If the context was an image and each pixel was somehow transformed into a set of 0-1 features, then a rule that talks about the conjunction of these features would not be interpretable. Such a model will not yield any more insight than a neural network that given an input generates a certain output.

3. Experimental evidence against strong contextual bandit baselines like SquareCB (Foster et al.) which are known to have optimal regret is not presented.
questions: My score is tentative and likely to change based on author's response. 

1. Why does Equation 4 consist of the sum of odd-numbered clauses minus the sum of the even-numbered clauses? Can we not simply use a single sum of all clauses and see whether this value is greater than n/2 or less than n/2?

2. On line 83, does voting for anything mean output 1? And Equation 4 seems to suggest that when odd-numbered clauses vote 1, then the sum is greater than 0 and so \hat{y}=1, but the text says that odd-numbered clauses vote for \hat{y}=0. Same on the last line on line 88-89. Do you mean "leading to class prediction \hat{y}=0". 

3. What does this line mean, "Here, T is a user-configurable voting margin yielding an ensemble effect."? How is this leading to an ensemble effect?

4. How is the weight of a clause used in making predictions? What is the analog of Equation 4 for weighted Tsetlin machines? 

5. How does this work compare with methods for interoperability in deep neural networks (e.g., if we use neural networks and a contextual bandit approach like SquareCB)? 

6. On line 32, it says, "make assumptions that limit their usability in real-world settings". Please provide examples of these assumptions.
limitations: The paper discusses the limitations of binarization of context.

The presentation can be improved. E.g., Algorithms 1 and 2 can be shortened or moved to Appendix and the space freed can be used for more qualitative discussion. The discussion on "Weighted Tsetlin Machine" can use more motivation and an explicit equation showing how the decision is made when clauses have weights.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper applies Tsetlin Machine into contextual bandit algorithm. 
Because Tsetlin is an inherently interpretable machine learning method, the resulting bandit algorithm is interpretable. 
Empirically the authors tests its performance by nine datasets. 
strengths_and_weaknesses: Strength: The paper introduces a new method to the bandit community. 

Weaknesses: (1) The paper lacks the theoretical support.  

(2) Besides of the lack of the theoretical results, the motivation of applying Tsetlin is not clear. 
questions: (1) There lacks of further explanation why the interpretability from Tsetlin is important in contextual bandits. 
This is not clear from the introduction.  The second paragraph in the introduction looks messy to relate the interpretability of Tsetlin to contextual bandits. For example, If we concern the features in bandits, there are many methods about variable selection and importance of features. 

(2) About Tselin Machine in Section 3, it looks to be related to tree methods. Are there more information for this relation? I think it's helpful for readers like me to understand this method. 

(3) In Section 4, the authors do not provide the motivation of applying the method to contextual bandits.  It looks like just applying it. This makes the contribution weak. 

limitations: (1) The Section of Tsetlin is a little lengthy but a little redundant.  It's helpful if section 3 could be written concisely. 

(2) For empirically supporting the application of Tsetlin, more empirical studies are needed. Algorithm 2 makes use of boostrap technique in the bandit algorithm, so it's important to show the contributions of boostrap and Tsetlin separately.  The current version is not clear to show them. 

(3) The format of the article is not easy to read. I think it's important for a formal submission.
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 studies the contextual bandit problem using the Tsetlin Machine framework. In detail, the authors propose a method to learn the binary-valued data and a Thompson sampling-based algorithm to balance the exploration for contextual bandits. Experiments are conducted to evaluate the performance of the algorithm compared to several baseline algorithms. 
strengths_and_weaknesses: Strengths: studying the contextual bandits with binary contexts under the Tsetlin framework sounds novel to me. Experiments are comprehensive. The paper is carefully written and easy to read.

Weakness: The sampling is conducted by perturbing the collected historical data according to the authors. This raises two major concerns in my view. First, keeping the historical data and randomly changing them in **each** episode sounds inefficient. Second, according to [1] or [2], to guarantee a sublinear regret bound by perturbing historical data, one may need some special warm-up procedures in the algorithm (see lines 5-9, Alg. 1 in [1], lines 4-8 Alg. 1 in [2]). I wonder if the same procedure should be applied here to guarantee a good result.

[1] Kveton, Branislav, et al. "Perturbed-history exploration in stochastic linear bandits." arXiv preprint arXiv:1903.09132 (2019).
[2] Jia, Yiling, et al. "Learning neural contextual bandits through perturbed rewards." International Conference on Learning Representations. 2021.
questions: What's the space complexity of the algorithm? How will the number of bits during the binarization and the coding methods will affect the performance of the algorithm?
limitations: NA
review_title: null

Meta-review: metareview: Thank you for submitting your paper to NeurIPS! The authors introduce a new contextual bandit algorithm using propositional logic (Tsetlin Machines), offering a more interpretable learning approach. The method interfaces with existing bandit algorithms like Thompson Sampling and \epsilon-greedy, and achieves favorable empirical results in an extensive suite of experiments. While the paper does not provide any technical regret guarantees, the review team found the empirical results intriguing and could lead to future work. I am pleased to recommend acceptance.
confidence: Less certain
Decision: Accept