Tsetlin Machine for Solving Contextual Bandit Problems
Authors: Raihan Seraj
Jivitesh Sharma
Ole-Christoffer Granmo
Venue: NeurIPS 2022 Accept (2022)
Keywords: Contextual bandits
Tsetlin Machine

Abstract: This paper introduces an interpretable contextual bandit algorithm using Tsetlin Machines, which solves complex pattern recognition tasks using  propositional (Boolean) logic. The proposed bandit learning algorithm relies on straightforward bit manipulation, thus simplifying computation and interpretation. We then present a mechanism for performing Thompson sampling with Tsetlin Machine, given its non-parametric nature. Our empirical analysis shows that Tsetlin Machine as a base contextual bandit learner outperforms other popular base learners on eight out of nine datasets. We further analyze the interpretability of our learner, investigating how arms are selected based on propositional expressions that model the context.

Tsetlin Machine for Solving Contextual Bandit Problems
Raihan Seraj
Jivitesh Sharma
Electrical and Computer Engineering
Center for Artificial Intelligence Research (CAIR)
McGill University Canada raihan. seihan.serajja saraaanneeeaammala.aaaaamm mttpaafmaamm.mmgll....
University of Agder
Norway www.itesh.shamaauuul..
Ole-Christoffer Granmo
Center for Artificial Intelligence Research (CAIR) University of Agder Norway ole. granmoQuia.no no
Abstract
This paper introduces an interpretable contextual bandit algorithm using Tsetlin Machines, which is an inherently interpretable machine learning method that solves complex pattern recognition tasks using propositional (Boolean) logic. The proposed bandit learning algorithm relies straightforward bit manipulation, thus simplifying computation and interpretation. We then present a mechanism for performing Thompson sampling with Tsetlin Machine, given its non non-parametric nature. Our empirical analysis shows that Tsetlin Machine as a base contextual bandit learner outperforms other popular comparable base learners nine datasets. We further analyze the interpretability of our learner, investigating how arms are selected based propositional expressions that model the contex
eight out of
Introduction
Contextual bandits play fundamental role in many applications involving sequential decision making, ranging from personalized recommendations [19] designing effective treatment allocation strategies in clinical trials [1 77) Algorithms for contextual bandits have additionally gained significant interest because of their theoretical elegance. In brief, a decision-maker selects one of multiple bandit arms over a sequence of rounds, taking into account an observed context. Each round, the arm chosen elicits feedback in the form of a reward signal associated with the success of selecting that arm (such as user purchasing a recommended product). The contextual bandit problem is particularly intriguing because the decision-male makeer must maximize the expected reward in as few rounds as possible, trading exploitation against exploration to identify the optimal arm.
In this paper, we recast the Tsetlin Machine (TM) 14] as a contextual bandit algorithm and study the resulting scheme empirically. TM is recent machine learning approach pattern recognition that employs a team of non-contextual bandit algorithms, in the form of Tsetlin automata [27), to learn patterns expressed in propositional logic. TMs have been shown to obtain competitive accuracy, memory footprint, and learning speed on several benchmark datasets 3 T8]. They have been particularly successful in natural language processing, including explainable aspect-based sentiment analysis (28) and robust text classification with ANDed word negations (29). Being based on finite state automata, they further support Markov blain-based convergence analysis [30]. Leveraging the non-linear pattern recognition capability of TMs, our proposed scheme thus addresses the contextual
'The code is available online on: github
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

bandit problem using team of non non-contextual bandit algorithms. Although existing algorithms for contextual bandits provide theoretical guarantees, they are either difficult to interpret or make assumptions that limit their usability in real-world settings. Motivated by these limitations, our work contributes as follows:
We investigate TM as a base learner for contextual bandit problems and empirically demon- strate its effectiveness compared to other popular comparable base learners.
We propose how the Thompson sampling scheme can be leveraged by TMs through boot- strapping [12]
We provide interpretability analysis that shows how algorithms using TMs select arms based propositional expressions of context features.
To the best of our knowledge, this is the first reported work on learning arm selection strategies for contextual bandits expressed in propositional logic. The paper organized follows. Section 2 and present the problem formulation and introduces the TM algorithm, respectively. In Section 4 we show how TM can be used as base learner for contextual bandits. The numerical results and the interpretability analysis are then presented in Section 5 and respectively. We conclude the paper and provide directions for future work Section 9 literature overview on contextual bandits and different algorithms for solving them can be found in Appendix A
2 Problem Formulation
We consider an online stochastic contextual bandit setup where at time t a context-reward pair denoted by (st. re) sampled independently from past data distribution D. Here, st E represents an M dimensional context vector and ((r.(1).... re(K)) E {0, 1] is the reward vector for K possible actions. The learner chooses an arm ", E fI....,AA K} after observing the context s and receives reward (ux) for the chosen arm. The objective of the learner is to perform sequence of actions order minimize the cumulative expected regret given by
Regret
Σ (T((TT()))) ru(w)))
(I)
Here, x² = arg max (()r))~((((( (+))), where denotes the set of large (possibly infinite) policies aell and x ~ (1...., K). For our analysis we consider maximizing the expected total reward which is equivalent to minimizing regret.
Action
Action
AN
Penatly
Reward
Figure 1: A two-action Tsetlin Automaton with 2N states.
3 Tsetlin Machine
Structure. A TM in its simplest form takes a feature vector x = [21 T2. 22....,,ool E {0, 1] of propositional values as input and assigns the vector class I E {0, 1). To minimize classification error, the TM produces n self-contained patterns. In brief, the input vector x provides the literal set T, = (4, 12. 120) {#1, ( ... Foy -1, -32,. ..., -r,), consisting of the input features and 22,
their negations. By selecting subsets L,j C of the literals, the TM can build arbitrarily complex patterns, ANDing the selected literals to form conjunctive clauses:
Cx(x) = A 4
(2)
Le

---

TA
TA'
include
exclude
Include
exclude
21
22
22
=1
transition
N+1
N+1
Step1
T-1
C
12
22
Σ
Σ
c
1 j=1
11...
5=0,2,
Type feedback
Type I feedback
Step 1
21 A 22
C
22
Σ
9/
Σ C2
0 1=0
1-13.
8-0,2,
#1, 11 F2, -2
TAs
[1, #2] = [0,1]
Input
Figure 2: TM learning dynamics for an XOR-gate training sample, with input (x) = 0, = 1) and output target
Above, j E {1, .1......,7)) refers to a particular clause Cj and k E 21. 20} refers to a particular literal 4.. As an example, the clause (x) æ1 A u2 consists of the literals Lj {21, -22 and evaluates to when 211 = and 222 = 0.
The TM assigns one Tsetlin Automata (TA) per literal 4 per clause Cj build the clauses. The TA assigned to literal 4 of clause C₁ decides whether 4 is Excluded or Included in C.. Figure T depicts two-action TA with 2NV states. For states 1 to N, the TA performs action Exclude (Action 1), while for states + to 2NV it performs action Include ( (Action 2). As feedback to the action performed, the environment responds with either Reward or Penalty. If the TA receives Reward, it moves deeper into the side the action. If receives a Penalty, it moves towards the middle and eventually switches action.
With clauses and 2o literals, we get x 2o TAs. We organize the states of these in an n x 20 matrix A [a]] E f1, 2N 2 We will use the function g(-) to map the automaton state a to Action (Exclude) for states to N and to Action 1 (Include) for states N 1 to 2N: g(ag) = ag. N. We can connect the states of of the TAs assigned to clause Cj with composition as follows:
C₂(x) A 4. A (((0 = Lx)
LEL;
Here, 4 one of the literals and ag is the state of its TA clause Cy. The logical imply operator = implements the Exclude/Include action. That is, the imply operator is always if g(a = 0 (Exclude), while if (ax( 1 (Include) the truth value is decided by the truth value of the literal. The complexity of the algorithm is proportional (linear) to the number features (input bits). E.g., doubling the number of features doubles the number of computations I.)
Classification. Classification performed as a majority vote. The odd numbbeeee half of the clauses vote for class ý = 1 and the even-numbered half vote for ý = O:
20
20
i 0=
((
- 1
Σ
A
((a)) = 4
(4)
j=1,3...
2
As such, the odd-numbered clauses have positive polarity, while the even-numbered ones have negative polarity. As an example, consider the input vector x = [0, 1] in the lower part of Figure 2

---

The figure depicts two clauses of positive polarity, C1(x) - Iı A JDz and (x -1 A -22 (the negative polarity clauses are not shown). Both of the clauses evaluate to zero, leading to class prediction ;j =
CLAUSE
CLAUSE
0
INPUT
INPUT
LITERAL
LITERAL
P(REWARD)
NA
0
P(REWARD)
NA
INCLUDE LITERAL
P(INACTION)
NA
4-1
A=1
P(INACTION)
1.0
NA
1.0
1.0
P(PENALTY)
NA
P(PENALTY)
NA
0
P(REWARD)
P(REWARD)
0
0
EXCLUDE LITERAL
EXCLUDE LITERAL
P(NNACTIO)
2
P(NNACIOO)
1.0
0
1.0
1.0
P(PENALTY)
0
P(PENALTY)
1.0
Table 1: Type I Feedback
Table 2: Type II Feedback
Learning. The upper part of Figure 2 illustrates learning. A TM learns online, processing one training example (x, y) at a time. Based on (x,y), the TM rewards and penalizes its TAs, which amounts to incrementing and decrementing their states. There two kinds of feedback: Type I Feedback produces frequent patterns and Type II Feedback increases the discrimination power of the patterns. Type feedback is given stochastically to clauses with positive polarity when and to clauses with negative polarity when = 0. Conversely, Type II Feedback is given stochastically to clauses with positive polarity when y and clauses with negative polarity when y = 1. The probability of a clause being updated is based on the vote sum
v 1= AR g((a)) 1x E== A (g(aa) = lx as:
The voting error is calculated
- v y ==
(5)
T+ y-
Here, 7' is a user-configurable voting margin yielding an ensemble effect. The probability of updating each clause is P(Feedback) = 27. After random sampling from P(Feedback) has decided which clauses to update, the following TA state updates can be formulated as matrix additions, subdividing Type I Feedback into feedback Type la and Type lb:
(6) Here. = [a]] {1,2,.... 2..........." NN nx contains the states of the TAs time step 1 and Aj+1 contains the updated state for time step t 1 (before clipping). The matrices pla {0, 1 and T (0, 1) 2 contains Type Feedback. A zero-element means no feedback and a one-element means feedback. As shown Table I two rules govern Type feedback:
A = A. + F + Fl F
Type Ia Feedback is given with probability #-1 whenever both clause and literal are 1-valued It penalizes Exclude actions and rewards Include actions. The purpose is to remember and refine the patterns manifested the current input x. This achieved by increasing selected TA states. The user-configurable parameter controls pattern frequency, i.e., higher produces less frequent patterns.
Type Ib Feedback is given with probability whenever either clause or literal is O-valued. This feedback rewards Exclude actions and penalizes Include actions to coarsen patterns, combating overfitting, Thus, the selected TA states are decreased.
The matrix "! {0, 12=x20 contains Type II Feedback the TAs, given per Table
Type II Feedback penalizes Exclude actions to make the clauses more discriminative, combating false positives. That is, if the literal is 0-valued and the clause is 1-valued, TA states below N + are increased. Eventually the clause becomes 0-valued for that particular input, upon inclusion of the O-valued literal.
The final updating step for training example stay within value 1 and 2N:
(x, v) is to clip the state values to make sure that they
A = clip (Ai 1, 1,2N).
Note that the probability -_ع is replaced by 1 when boosting true positives.

---

For example, both of the clauses in Figure receives Type Feedback over several training examples, making them resemble the input associated with y
Weighted Tsetlin Machine: The learning of weights is based on increasing the weight of clauses that receive Type feedback (due to true positive output) and decreasing the weight of clauses that receive Type II feedback (due to false positive output). The overall rationale is to determine which clauses are inaccurate and thus must team up to obtain high aceuracy as a team (low weight clauses), and which clauses are sufficiently accurate to operate more independently (high weight clauses). The weight updating procedure summarized in Algorithm [ Here, w; is the weight of clause C, at the nhhh training round (ignoring polarity to simplify notation). The first step of training round is to calculate the clause output as per Equation 2 The weight of a clause is only updated if the clause output C₁ is I and the clause has been selected for feedback (P, 1). Then the polarity of the clause and the class label y decide the type of feedback given. That is, like a regular TM, positive polarity clauses receive Type Ia feedback if the clause output is a true positive and Type II feedback if the clause output is a false positive. For clauses with negative polarity, the feedback types switch roles. When clauses receive Type la or Type II feedback, their weights updated accordingly. We use the stochastic searching on the line (SSL) automaton to learn appropriate weights SSL is an optimization scheme for unknown stochastic environments pioneered by Oommen (22]. The goal is to find an unknown location X within a search interval [0. 1]. In order to find X*, the only available information for the Learning Mechanism (LM) is the possibly faulty feedback from its attached environment F. In SSL, the search space À is discretized into N points, {0, 1/N, 2/N, .... (N 1- -1)/N, 1} with N being the discretization resolution. During the search, the LM has a location À E {0, 2/N. (NV 1)/N, J, and can freely move to the left or to the right from its current location. The environment E' provides two types of feedback: E- is the environment suggestion to increase the value of by one step, and E = 0 is the environment suggestion to decrease the value of À by one step. The next location of X, i.e. An+1, can thus be expressed as follows:
An + 1/N,
if E, 1,
An+1 =
(8)
An 1/N, if E, = 0.
An= if A, = and E,, = 1,
An+1
Ans if Xr, = 0 and E,, = O.
Asymptotically, the learning mechanics is able to find a value arbitrarily close to X when N + 00 and n + co. In our case, the search space of clause weights is [0, oo). with no upper bound for X. Accordingly, we operate with integer weights. As described in Algorithm [ if the clause output a true positive, we simply increase the weight by 1. Conversely, if the clause output is a false positive, we decrease the weight by 1.
resolution N = 1,
By following the above procedure, the goal is to make low precision clauses team up by giving them low weights, so that they together can reach the summation target T. By teaming up, precision increases due to the resulting ensemble effect. Clauses with high precision, however, gets higher weight, allowing them to operate more independently.
The above weighting scheme has several advantages. First of all, increment and decrement operations on integers are computationally less costly than multiplication based updates of real-valued weights Additionally, a clause with an integer weight can be seen as multiple copies of the same clause, making it more interpretable than real-valued weighting, as studied in the next section. Additionally, clauses can be turned completely off by setting their weights to 0 they do not contribute positively to the classification task.
4 Contextual Bandits with Tsetlin Machines
We use TM as a contextual bandit learner that learns a mapping from context to actions incrementally with streaming data. Since both inputs, patterns and outputs of TM are represented as bits (4). each M dimensional context s; is binarized with appropriate number of bits. This results in a B dimensional binarized context with B Z M which is fed to each TM learner. We outline appropriate choices of bits for binarization for different datasets in the next section. The TM learner, being nan-param,tric, has the advantage that it makes few or no assumption about the underlying functions to be learned; hence it is adaptive and exhibit high degree of flexibility. Another popular non- parametric learner for contextual bandits is the decision tree, which has been thoroughly studied in the literature 22 26 13). The TM, in contrast, learns linear combination of conjunctive clauses
5

---

Algorithm Complete WTM learning process
1: Input: Training data batch (B, v) D> B 221 1
2: Initialize: Random initialization of TAs
3: Begin: nh training round
4: for = 1, ..., m do if p; =
5: if (y and i is odd) or (y 0 and i even) then
6:
if c = then
7:
W0; W/ +1
8:
for feature l- = 1.... 2o do
9:
if 4/ then
10:
Type la Feedback
11:
else:
12:
Type lb Feedback
13:
end if
14:
end for
else:
16:
Wi + wy D INo Change]
Type lb Feedback
18:
end if
else: (y and is even) or (y and is odd)
20:
if = 1 then
we > then
22:
W/: <- -1
end if
24:
for feature k = 1..., 20 do
25:
4/ = then
26:
Type II Feedback
27:
else:
28:
Inaction
29:
end if end for
30:
31:
else:
32:
Wy ut
[No Change]
33:
Inaction
34:
end if
35:
end if
36:
end for
in propositional logic by producing decision rules similar to the branches in decision trees ①.. with the added advantage of being memory and energy efficient, computationally simple and not having tendency to overfit the training data (I8). We consider two contextual bandit learning algorithms using TM: (i) TM with epsilon greedy arm selection; and (ii) TM with Thompson sampling.
trade-off is fundamental problem in learning to make decisions under uncertainty. multi-armed bandit setting, the & - greedy algorithm is one of the simplest ones. The learner either chooses the empirically best arm with probability (1 (1= (exploitation) or a random arm with probability (exploration). In the contextual bandit setting, given a set of contexts, the learner chooses to select the current empirically best arm with some high probability, maximizing immediate rewards. Otherwise, it selects a randomized arm with the hope of improving future rewards given the context. Variations of epsilon greedy algorithms have been explored the literature, including decaying the parameter and eventually dropping the probability of choosing random arm zero. In our setting, consider a fixed small value of for each TM learner associated with the arm.
Epsilon greedy TM: The
TM with Thompson sampling: We now show how Thompson sampling be achieved with TM. Our approach is similar to that presented in the Tree Bootstrap Algorithm in [12]. Since a TM learner is non-parametric, distribution. At each time instant f, N context reward pairs are bootstrapped from the Dr,,. with replacement, where Dr.,. represents the set of observations (context reward pairs) for arm and N = Dtul. A TM learner is fitted to each of these bootstrapped datasets and at each time t, the
use bootstrapping simulate the behavior of sampling from posterior

---

bootstrapping algorithm selects the arm 2e that has the maximum probability of success p. For ease of exposition, we outline Thompson Sampling with bootstrapping for TMs in Algorithm 2
Algorithm 2 Thompson Sampling with TM
for ( = 1 I do
get context St for u u......, do
Sample bootstrapped dataset Dr.. of size N from Dr.. with replacement. Fit Tsetlin Machine TM t,a to Dr,, end for Choose action dt = arg max TM t, t,))88))
Update Di. with (st, rt,ue)
end for
5 Empirical Analysis
Given the interactive aspect of contextual bandit algorithms, it is often difficult to evaluate them on real datasets except for a handful number of tasks [6]. Therefore, we use standard supervised learning classification datasets for evaluation. We consider both binary well as multiclass classification datasets. Each unique label in these datasets is considered as an arm of the equivalent contextual bandit problem, where a separate learner associated with each arm is trained independently. Our numerical analysis contrasts the performance of TM with E greedy arm selection and TM with Thompson sampling against Tree Bootstrap 12]. Linear UCB g. Neutral Network (e-gredyy) and Logistic regression (6 greedy). For our analysis we consider two scenarios described as follows. Scenario I: In this scenario, we consider five standard supervised learning classification datasets from UCI machine learning repository [10]: Iris, Breast Cancer Wisconsin (Diagnostic), Adult, Covertype, and Statlog (Shuttle). The response variables for each of these datasets are, Iris types, Diagnosis, Occupation, and Covertypes, respectively, where as for the Statlog Shuttle) dataset, we consider the last column as the response variable. Additionally we considered two other classification datasets: MNIST 9 and Noisy XOR, where the respective response variables are digits and the XOR output. The noisy XOR dataset contains the XOR operation of 12 bit input, where the output is flipped with probability 0.4. These classification datasets are converted into a contextual bandit problem where the learner receives a reward of +1 for correctly identifying the target value and 0 for incorrect classification. The datasets are processed by removing entries with missing values.
Scenario 2: In this scenario, we consider two datasets: Movielens 100 K [15] and Simulated Article 123] Both these datasets simulate recommender system. The reward function for the Movielens dataset is the user's s rating for a particular movie while for Simulated Article dataset, a reward of +1 is received if the recommended article is clicked by the user. The Moviclens dataset is preprocessed, so that top 10 rated movics are selected. One important takeaway from these two datasets is that only the reward function for correct recommendation is provided. For instance the Simulated Article dataset provides recommended articles that has been clicked by the user. Similarly, the Movielens dataset provides user movie ratings, where the users only rated the movies they have watched. In such cireumstances, the rewards are partial and sparse since there are no information on the ratings of all movies or user click information for each article. To circumvent this, we perform singular value decomposition (SVD) for both the datasets which is a popular approach in collaborative filtering [17. For the Movielens dataset, let S., be the rating of user i on movie j. Low rank SVD of this matrix results in two matrices W and X, where $ R W * X. The hh row of W represents the context features for each user and the rows of X represents the actions or the movic to be recommended. The reward for recommending a movie to user i is then the dot product of the corresponding row of W; and Xy. We perform SVD for Simulated Article dataset in a similar manner. In order to obtain binarized rewards for the actions, the maximum reward corresponding to an arm that yields a reward of 1, and the rest reward of O. For our analysis we consider rank 10 for both the Movielens and the Simulated Article dataset. For both the scenarios we use appropriate binarization before fitting the TM learners. Details of binarization and parameter choices are provided in Appendix B The results for both the scenarios are presented Figures 3 These results show that for eight datasets, TM with Thompson sampling outperforms all other algorithms except for Linear UCB on Covertype. Further, TM with E --greedy
7

---

Figure 3: Performance comparison of TM with different base learners.
(a) Iris
(b) Breast Cancer
(c) MNIST
1.0
0.9
0.9
0.6
Mean Naanard
0.8
Moan Rower
0.5
0.7
0.4
0.6
Tree bootstrap
Linear UCB
0.7
Linear UCB
boststrap
Moo
0.3
Linear UCB
Tree bootstrap
Thompson Sampling
Thompson Sampling
0.2
Thampson Sampling
TM e-greedy
TM z-gready
TM z-gready
Logistic Reg Regression egready
0.5
Logistic Regression e-gready
0.1
Logistic Regression e-grendy
Neural Network r-geadyy
r-gready
Neural Network -grwady
200
400
600
800
1000
200
400
600
800
1000
200
460
600
800
1000
Rounds
Rounds
Rourds
(d) Adult
(e) Covertype
(f) MovieLens
0.6
0.8
0.7
0.5
Mcan Reware
0.4
0.5
Linear UCB
0.3
Linear UCB
0.4
Linear UCB
Tree bootstrap
bootstrap
Tree bootstrap
Thompson Sampling
Thompson Sampling
Thompson Samplinng
TM e-gredd
TM c-gready
0.2
TM c-gready
Logistic Reg ression r-greedy
0.1
Logistic Regression - grreddy
0.1
Logistic Regression s-gready
Network egreedy
Network c-gredy
0.0
Network e-gredy
500
1000
1500
2000
500
1000
1500
2000
200
400
600
soo
1000
Rounds
Rounds
Bourds
Statlog
(h) Noisy XOR
(i) Simulated Article
1.0
0.9
0.8
0.8
0.7
0.6
Thee bootstrap
Linear UCB
Mer
0.6
Linnar UCB
bootstrap
Mege
0.4
Linear UCB
Thompson Sampling
0.5
TM Thompson Sampling
TM Thompson Sampling
TM e g-greedy
TM --grendy
0.2
TM s-grendy
Logiatic Reg regssioon rgready
0.4
Logistic Regression e-gredd
Logistic Regressten e-greddy
Neural Network egreedy
0.3
Neural Network e-gready
0.0
Naural Network a-gready
500
1000
1500
2000
600
1000
1000
1500
2000
Roundds
Rounds
provides competitive performance when compared with popular contextual bandit algorithms in the literature. Also, the TM learner learns at faster rate compared to other learners. These experiments were performed with 10 independent runs for each dataset. The average result across the independent runs are reported.
Choice of Binarization Parameters
The working principle of TM relies binarization of the context features. We use gap-based thresholding as described in (2), each threshold yielding one bit. The binarization is performed with the parameter which controls the maximum number of bits allowed to represent each feature. We varied the number of bits allowed per feature for binarization and performed an ablation study across these datasets, in order observe the effects of sub-optimal binarization. Our analysis shows that TM as a base learner is robust to the choice of maximum bits per feature allowable for binarization. Detailed evaluation results of TM with epsilon greedy and TM with Thompson sampling are provided in Appendix C
7 Interpretability
Unlike neural networks and some other complex machine learning approaches, one of the advantages of TMs is that they produce propositional logic expressions. These are in flat AND-form, which have proven to be human interpretable (21] As explained Section 3 each propositional expression is a conjunctive clause, consisting of features, in their original or negated forms, interacting with each other using logical AND operations. These clauses can form a simplified representation of the arm selection policy by combining them into single Disjunctive Normal Form (DNF) expression. Since
8

---

clauses are assigned to each arm of the multi armed contextual bandit problem, we produce single DNF expression for each arm. These DNF expressions are propositional logic expressions made up of the context. The TM is able to produce these interpretations demonstrating how it interprets the context with respect to each arm.
Here, we show the simplified propositional expressions for each arm, obtained from TMs trained with Thompson Sampling on the Iris dataset:
Arm-1: x10 214 215 V IS
Arm-2: -1 V 12 V 11 V - V F1G V V -9 V (#10 AT1 A AZ15 A I4 A AIG A
-x7) (010 A F11 A 215 A I3 A I4 A I5 A -27)
Arm-3: -0 V 11 V 115 V (α1 A 12 A T A 214 A 7166 A A2 22 A 2g A 2g) V
(-Z12 16 A x4)
The next set of propositional expressions represent the arms for the Simulated Article dataset:
Arm-l: -z V (I) -110 I A A12 A T A T A Ø A 217 A
2221 A Æз A I5 A To A 27 A as A Z9)
Arm-2: (I1 A 10 A 111 A 122 A F13 A T AI A T1e A F17 A I1S
A T19 A A 220 A 22 A
I3 A I4 A Hy A IE A #7
Is (9) V (-I) A 3TO III AZI2
Z13 T44
A I15 A T
117 A #18 A 2/9 A 42 A -20 A -221 A 23 A I4 A 25 A A -xy A Ag A (D)
Arm-3: (x1 A -10 A I11 A Z12 A Z13 A T14 A 215 A F16 A Σ17 A 219 A F2 A T20 A -221 A A 120
34 A F5 A Te A A TO) V (-riI A 222 A A T44 A T 177 A T18 A Ti9
222 A 33 A TA A 25 A 2g A Tg)
Arm-4: Z10 A I1 A D12 A F18 A F14 A T15 A T16 A Z17 A 218 A Z A
22
A 23 A
2g A Zg A 1 A 20 A 21 -I7
The propositional expressions shown above exhibit how the TM learns interactions between proposi- tional input features (literals zz). As seen, the interactions are learned with logical AND operations between original and negated features. These learnt interactions (clauses) are combined with the logical OR operation (or by addition for T >> 1). From the propositional expressions, we can see which arm is selected by TM by simply plugging in the input values. An arm is selected if its propositional expression evaluates to True (or obtains the largest net sum for T 1). This is arguably an important advantage of TMs propositional expressions. Of course, as such, any machine learning algorithm can be converted into logical form. However, the complexity of such representations can be immense for the competitive classic machine learning models, which the TM still outperforms by a large margin (24). Note that, although the length of expressions can increase with the increase in dimensionality of data, there simple ways of reducing the length of expressions in (n) time (00)
trained TM model can be reduced down to simple
8 Limitations
One of the limitations of using TM is that requires the contexts to be binarized. While such binarization leads to loss of information, sampling performs substantially better than the other evaluated learners on the majority of the datasets and TM learners are quite robust to sub-optimal binarization. While our work does provide any theoretical guarantees on performance or regret bounds for TM learners, we believe the latter will form an interesting direction of research.
empirical analysis shows that TM with Thompson
9 Conclusion
In this paper, we presented an interpretable and practical contextual bandit learner using Tsetlin Machine (TM). Our analysis showed that TM as contextual bandit learner provides competitive performance compared to other popular contextual bandit algorithms. We then presented how Thompson sampling can be implemented using TM, where our approach is derived from the Tree Bootstrap algorithm. Finally, we perform interpretability analysis where the arm selection strategy can be characterized by propositional function of the contexts.. Having such promising empirical results, we aim at providing theoretical performance guarantees for algorithms with TM as future work.

---

References
[1] Darshana Abeyrathna, Ole-Christoffer Granmo, and Morten Goodwin. Extending the tsetlin machine with integer-weighted clauses for increased interpretabilityy. IEEE Access, 2021.
[2] K Darshana Abeyrathna, Ole-Christoffer Granmo, Xuan Zhang, and Morten Goodwin. Adaptive continuous feature binarization for tsetlin machines applied to forecasting dengue incidences in the philippines. In 2020 IEEE Symposium Series Computational Intelligence (SSCT), pages 0084-2092. IEEE, 2020.
[3] Kuruge Darshana Abeyrathna, Bimal Bhattarai, Morten Goodwin, Saeed Rahimi Gorji, Ole- Christoffer Granmo, Lei Jiao, Rupsa Saha, and Rohan K Yadav. Massively parallel and asyn- chronous tsetlin machine architecture supporting almost constant-time scaling. In International Conference on Machine Learning, pages 10-20. PMLR, 2021.
[4] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135. PMLR, 2013.
[5] Robin Allesiardo, Raphaël Féraud, and Djallel Bouneffouf. neural networks committee for the contextual bandit problem. In International Conference Neural Information Processing, pages 374-381. Springer, 2014.
[6] Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. Journal of Machine Learning Research, 22(133):1-49, 2021.
[7] Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1-8. IEEE, 2020.
[8] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligncce and Statistics, pages 214. JMLR Workshop and Conference Proceedings, 2011.
[9] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-144 2012.
[10] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[11] Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in mouse model of de novo carcinogenesis. In Machine learning for healthcare conference, pages 67-82. PMLR, 2018.
[12] Adam N. Elmachtoub, Ryan McNellis, Sechan Oh, and Marek Petrik. A practical method for solving contextual bandit problems using decision trees. In Gal Elidan, Kristian Kersting, and Alexander T. Ihler, editors, Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, @articleTsetlin190 author = Tsetlin, Michael Lvovitch, journal Avtomat. Telemekh, number 10, pages 1 1345-1355 title = On behaviour of finite automata in random medium, volume 22, year 1961 UAI 2017, Sydney, Australia, August I 11-15, 2017. AUAI Press, 2017.
[13] Raphaël Féraud, Robin Allesiardo, Tanguy Urvoy, and Fabrice Clérot. Random forest for the contextual bandit problem. In Artificial intelligence and statistics, pages 93-101. PMLR, 2016.
[14] Ole-Christoffer Granmo. The tsetlin machine-a a game theoretic bandit driven approach to optimal pattern recognition with propositional logic. arXiv preprint (rXiv:1804.01508 2018.
[15] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tis), 5(4):1-19, 2015.
[16] Insaf Ismath, KB Shashika Manosha, Samad Ali, Nandana Rajatheva, and Matti Latva-aho. Deep contextual bandits for fast initial access mmwave based user-centric ultra-dense networks. In 2021 IEEE 93rd Vehicular Technology Conference (VTC2021- -Sprring),, pages 1-7. IEEE, 2021.
10

---

[17] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[18] Jie Lei, Adrian Wheeldon, Rishad Shafik, Alex Yakovlev, and Che-Christoffer Granmo. From arithmetic to logic based ai: A comparative analysis of neural networks and tsetlin machine. In 2020 27th IEEE International Conference on Electronics, Circuits and Systems (ICECS), pages 1 1-4, 2020.
[19] Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[20] Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondiej Čertík, Sergey B. Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rath- nayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pedregosa, Matthew J. Curry, Andy R. Terrel, Stěpán Roučka, Ashutosh Saboo, Isuru Fermando, Sumith Kulal, Robert Cimrman, and Anthony Sco- patz. Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103, January 2017.
[21] I. Noveck, R. B. Lea, George M. Davidson, and D. O'brien. Human reasoning is both logical and pragmatic. Intellectica, 1:81-109, 1991.
[22] B.J. Oommen. Stochastic searching the line and its applications to parameter learning in nonlinear optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cyhermetics), 27(4):733-739, 1997.
[23] Dattaraj Rao. Contextual bandits for adapting to changing user preferences over time. arXiv preprint arXiv:2009. /0073, 2020.
[24] Jivitesh Sharma, Rohan Kumar Yadav, Ole-Christoffer Granmo, and Lei Jiao. Drop clause: Enhancing performance, interpretability and robustness the tsetlin machine. CoRR, hls/2105.14508 2022.
[25] Yilin Shen, Yue Deng, Avik Ray, and Hongxia Jin. Interactive recommendation via deep neural memory augmented contextual bandits. In Proceedings of the 12th ACM Conference on Recommender Systems, pages 122-130, 2018.
[26] Dennis Soemers, Tim Brys, Kurt Driessens, Mark Winands, and Ann Nowé, Adapting to concept drift in credit card transaction data streams using contextual bandits and decision trees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[27] Michael Lvovitch Tsetlin. behaviour of finite automata in random medium. Avtomat. i Telemekh, 22(10)):345-1 1354, 1961.
[28] Rohan Kumar Yadav, Lei Jiao, Olc- Dle-Christoffer Granmo, and Morten Goodwin. Human-level interpretable learning for aspect-based sentiment analysis. In The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21). AAAI, 2021.
[29] Rohan Kumar Yadav, Lei Jiao, Ole Christoffer Granmo, and Morten Goodwin. Robust Inter- pretable Text Classification against Spurious Correlations Using AND-rules with Negation. In The 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.
[30] Xuan Zhang, Lei Jiao, -heCChristoffer Granmo, and Morten Goodwin. On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[31] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section g
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] See footnote on first page.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
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? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're '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 or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "uz5hg3dZ-Xs", "reviewer": "Reviewer_msCn", "summary": "This paper applies Tsetlin Machine into contextual bandit algorithm. \nBecause Tsetlin is an inherently interpretable machine learning method, the resulting bandit algorithm is interpretable. \nEmpirically the authors tests its performance by nine datasets. ", "questions": "(1) There lacks of further explanation why the interpretability from Tsetlin is important in contextual bandits. \nThis 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. \n\n(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. \n\n(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. \n", "limitations": "(1) The Section of Tsetlin is a little lengthy but a little redundant.  It's helpful if section 3 could be written concisely. \n\n(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. \n\n(3) The format of the article is not easy to read. I think it's important for a formal submission. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper introduces a new method to the bandit community. \n\nWeaknesses: (1) The paper lacks the theoretical support.  \n\n(2) Besides of the lack of the theoretical results, the motivation of applying Tsetlin is not clear. ", "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": "5JSMDOK7R-1", "reviewer": "Reviewer_M12R", "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. ", "questions": "My score is tentative and likely to change based on author's response. \n\n1. 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?\n\n2. 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\". \n\n3. 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?\n\n4. How is the weight of a clause used in making predictions? What is the analog of Equation 4 for weighted Tsetlin machines? \n\n5. 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)? \n\n6. 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.\n\nThe 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. \n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. 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\n2. Empirical evidence show the advantage over some other methods.\n\nWeakness:\n\n1. 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).\n\n2. 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.\n\n3. Experimental evidence against strong contextual bandit baselines like SquareCB (Foster et al.) which are known to have optimal regret is not presented.", "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": "-gfmJolGdWM", "reviewer": "Reviewer_jcuG", "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. ", "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", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWeakness: 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.\n\n[1] Kveton, Branislav, et al. \"Perturbed-history exploration in stochastic linear bandits.\" arXiv preprint arXiv:1903.09132 (2019).\n[2] Jia, Yiling, et al. \"Learning neural contextual bandits through perturbed rewards.\" International Conference on Learning Representations. 2021.", "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